rsyncのコアアルゴリズム

Rsync は、Unix/Linux でファイルを同期するための効率的なアルゴリズムです。2 台のコンピューター上のファイルとディレクトリを同期的に更新し、検索ファイル内の異なるブロックを適切に使用してデータ転送を削減できます。他のほとんどの同様のプログラムやプロトコルには見られない rsync の重要な機能は、イメージの変更された部分だけが転送されることです。 rsync は、ディレクトリ属性のコピー/表示、ファイルのコピー、オプションで圧縮および再帰的なコピーを行うことができます。 rsync は Andrew Tridgell によって発明されたアルゴリズムを使用します。ここではその使用法は紹介せず、コアアルゴリズムのみ紹介します。 Unix のあらゆるもの、あらゆるコマンドやツールには、多くの微妙な要素が含まれており、そのすべてを学ぶことは不可能であることがわかります。これが Unix の文化です。

もともとこの記事を書きたくなかったのは、多くの中国のブログがこのアルゴリズムについて語っていたからです。しかし、調べてみると、これらの中国のブログは外国の記事を非常に下手に翻訳していたり、アルゴリズムをわかりにくい混乱した方法で紹介していたり、誤りもあり、非常に誤解を招きやすいことが分かりました。そこで、rsync アルゴリズムを紹介する記事を書く必要があると感じました。 (もちろん急いで書いたので、間違いがあるかもしれません。ご指摘いただければ幸いです。) 問題まず、rsync が解決しようとしている問題について考えてみましょう。同期したいファイルの異なる部分だけを転送したい場合、両側のファイルの diff を実行する必要がありますが、これら 2 つの問題は 2 つの異なるマシン上にあるため、diff を実行することはできません。 diff を実行する場合、diff を実行するためにファイルを別のマシンに転送する必要がありますが、この方法ではファイル全体を転送する必要があり、異なる部分のみを転送するという当初の目的に反します。したがって、2 つのファイルが互いを認識しないようにしながらも、それらの違いを認識する方法を考えなければなりません。ここで rsync アルゴリズムが登場します。アルゴリズム rsync のアルゴリズムは次のとおりです (同期元ファイルが fileSrc、同期先ファイルが fileDst であると仮定) 1) ブロックチェックサムアルゴリズム。まず、ファイル fileDst をいくつかの小さなブロックに均等に分割します。たとえば、各ブロックは 512 バイト (最後のブロックはこの数より小さくなります) で、各ブロックに対して 2 つのチェックサムを計算します。1 つはローリングチェックサムと呼ばれる弱いチェックサムで、32 ビットチェックサムです。これは、Mark Adler が発明した adler-32 アルゴリズムを使用します。もう 1 つは強力なチェックサムで、128 ビットです。以前は md4 を使用していましたが、現在は md5 ハッシュアルゴリズムを使用しています。なぜこんなことをするのですか？数年前にハードウェア上で実行されていた md4 アルゴリズムは遅すぎるため、ファイルブロック間の違いを識別するための高速アルゴリズムが必要です。ただし、弱い adler32 アルゴリズムの衝突確率が高すぎるため、2 つのファイルブロックが同じであることを確認するために、強力なチェックサムアルゴリズムも導入する必要があります。つまり、弱いチェックサムは相違点を区別するために使用され、強いチェックサムは類似点を確認するために使用されます。（チェックサムの具体的な計算式については、こちらの記事を参照してください） 2) 送信アルゴリズム。同期ターゲットは、fileDst のチェックサムリストを同期ソースに渡します。このリストには、ローリングチェックサム (32 ビット)、md5 チェックサム (128 ビット)、およびファイルブロック番号の 3 つが含まれます。同期ソースマシンがこのリストを取得した後、fileSrc に対して同じチェックサムを実行し、それを fileDst のチェックサムと比較して、どのファイルブロックが変更されたかを認識することはご想像のとおりです。しかし、賢い人として、次の 2 つの疑問があるはずです。fileSrc 側でファイルの途中に文字を追加すると、後続のファイルブロックが 1 文字シフトされ、fileDst 側とはまったく異なるものになります。ただし、理論的には、1 文字を渡すだけでよいはずです。これをどうやって解決すればいいでしょうか? チェックサムリストが非常に長く、両側の同じファイルブロックが同じ順序になっていない可能性がある場合は、検索が必要になり、線形検索は非常に遅くなります。これをどうやって解決すればいいでしょうか? では、同期ソース側のアルゴリズムを見てみましょう。 3) チェックサム検索アルゴリズム。同期ソースは、fileDst のチェックサム配列を取得した後、データをハッシュテーブルに保存し、ローリングチェックサムをハッシュとして使用して、O(1) 時間計算量の検索パフォーマンスを実現します。このハッシュテーブルは 16 ビットなので、ハッシュテーブルのサイズは 2 の 16 乗となり、ローリングチェックサムのハッシュは 0 – 2^16 – 1 の間の値にハッシュされます。 (ハッシュテーブルについては、よくわからない場合は、大学のデータ構造の教科書に戻って読んでみてください。) ちなみに、ネット上で「ローリングチェックサムをソートする」という記事を多く見かけます(この記事やこの記事など)。どちらの記事も原文を引用して翻訳していますが、どちらも誤解しています。ソートしているわけではなく、fileDst のチェックサムデータをローリングチェックサムとして 2^16 ハッシュテーブルに格納しているだけです。もちろん衝突は発生します。衝突へのリンクを張ればいいのです。これは、元のテキストに記載されている 2 番目のステップです。 4) 比較アルゴリズム。これは最も重要なアルゴリズムです。詳細は次のとおりです。4.1) fileSrc の最初のファイルブロック (長さは 512 と想定)、つまり fileSrc の 1 バイト目から 512 バイト目までを取得し、取り出した後にローリングチェックサム計算を実行します。計算された値はハッシュテーブルで検索されます。 4.2) 見つかった場合、fileDst に潜在的に同一のファイルブロックが存在することを意味し、md5 チェックサムが再度比較されます。ローリングチェックサムが弱すぎるため、衝突が発生する可能性があります。したがって、md5 の 128 ビットチェックサムも計算する必要があります。この方法では、衝突の確率は 2^-(32+128) = 2^-160 となり、無視できないほど小さくなります。ローリングチェックサムと md5 チェックサムが同じ場合は、fileDst に同一のブロックがあることを意味します。このブロックのファイル番号を fileDst の下に記録する必要があります。 4.3) fileSrc のローリングチェックサムがハッシュテーブルに見つからない場合、md5 チェックサムを計算する必要はありません。このブロックに異なる情報があることを示します。つまり、ローリングチェックサムまたは md5 チェックサムのいずれかが fileDst のチェックサムハッシュテーブルで一致するものを見つけられない限り、アルゴリズムは fileSrc でローリングアクションをトリガーします。したがって、アルゴリズムは 1 バイト戻って、fileSrc のバイト 2 から 513 までのファイルブロックを取得してチェックサムを作成します。(4.1) に進みます - これで、ローリングチェックサムの意味がわかりました。 4.4) このようにして、同期ターゲットに転送するファイルの内容である、fileSrc の連続する 2 つの一致内のテキスト文字を見つけることができます。え、分からないの？わかりました。手伝って、図を描いて見てみましょう（図にあるものについてはこれ以上説明しません）。このようにして、最終的に、同期ソース側では、rsync アルゴリズムは次のようなデータ配列を取得する可能性があります。図では、赤いブロックはターゲット側で一致したため送信する必要がないことを示しています (注: 2 つのチャンク #5 を具体的に示しています。理解していただけると思います)。白い領域は送信する必要があるコンテンツです (注: これらの白いブロックは可変長です)。このように、同期ソース側はこの配列を圧縮し (白いものが実際のコンテンツで、赤いものはラベル付き)、宛先側に送信します。宛先側の rsync はこのテーブルに従ってファイルを再生成し、同期が完了します。最後に、圧縮ファイルによっては、圧縮ファイルが大きく異なる可能性があるため、rsync を使用して転送すると転送量が増える可能性があることを述べておきます。このためには、gzip や bzip2 などのコマンドに対して「rsyncalbe」モードを有効にすることを忘れないでください。

【編集者のおすすめ】