rsyncのアルゴリズム

あるマシン上のファイルを別のマシン上のファイルと同一に更新するためのアルゴリズム

低帯域高レイテンシの回線でも使えるように設計されている

このアルゴリズムは差分を計算して送信するので双方のファイルが類似している際に最もよく機能する

そうでない場合でも有用

A,Bという2つのファイルがあり、BをAと同じに更新したい

低速の通信(例えばダイヤルアップ)ではAが大きいと時間がかかる

圧縮したら多少はマシになるが、それでも遅い

そこでrsyncでは2つのファイルがとてもよく似ていて1つのオリジンから派生していると仮定する

(注:実際にこのようなファイルはよくある)

本当に高速化するにはこれを利用する必要がある

一般的にはAとBの差分リストを送るのが効率的ではあるが、これを普通にやるにはAとB両方が必要

要件から考えると本末転倒である

once you had copied the file over, you wouldn't need the differences

rsyncのアルゴリズムはどの部分がどの部分と一致しているのかを効率的に計算する

(後で読む)

α、βの2台のマシンがある

αはA、βはBのファイルを持つ

βはBをSバイトの重複しない固定サイズのブロックに分割する

最後のブロックはSバイトでなくてもよい

Sは500から1000バイトくらいの間の何でもいい

各ブロックごとに2つのチェックサムを計算してαに送る

ローリングチェックサム

32bitの弱い物

後述する

αは送られてきたチェックサムと一致する場所を調べる(Sの倍数ではなく任意のオフセットで計算する)

調べた場所を元にAを構築するための命令をβに送る

更新命令は以下のいずれかを羅列したもの

Bのブロックのインデックス

リテラルデータ

Bのブロックのいずれにもマッチしなかった物を送るための物

βはこの命令を元にAのコピーを得る

この際に重要なのは

チェックサム、インデックスと見付からなかった部分のデータだけが送られること

1回のラウンドトリップしか行われないのでレイテンシの影響が少ないこと

$ \mathcal{X_2}...\mathcal{X_{N+1}}