要約

  • TridgellとMackerrasの原技術報告では、受信側が手元のファイルをブロックに分け、各ブロックの２種類の検査値を送る。送信側は新ファイルの任意の位置から一致を探し、旧ブロックの参照と一致しない実データを返す。
  • rsync計画の実装説明は代価も記す。探索は送信側のCPUを使い、再構築は受信側のディスクを使う。最後にはファイル全体の検査値で組み立てた結果を確かめる。

宛先から届いたのは在庫表だった

大きなファイルが通信路の両端にあり、片方だけ新しいとする。冒頭に一段落が挿入されただけなら、古い側は残りの文章をほぼ持っている。丸ごとコピーすれば同じ内容がまた回線を渡る。同じ位置の塊どうしを比べるだけでも、挿入によって後半の位置がずれ、一致を見逃す。rsyncの原報告が扱ったのは、低帯域で遅延の大きい接続に２つのファイルが離れている問題だ。普通の差分計算のために両方を一台へ集めては、節約したい転送を先に行うことになる。

そこで最初に送るのは宛先である。古いファイルを重ならないブロックに切り、各々について素早いローリング検査値と、より強い検査値を作って送る。当初の方式では前者が32ビット、後者にMD4を使った。これは歴史的な設計値で、現在のあらゆる版の設定を示すものではない。大切なのは、新しいファイルを持つ側が古いファイル本体を受け取らずに、相手の手持ち部品の要約を得る点だ。

送信側は自分の新ファイルを走査する。受信側にもあるブロックが見つかれば、そのブロックを指す番号を送る。見つからない部分だけ実際のバイトを送る。受信側は手元の旧ファイルから該当ブロックを取り出し、新しいバイトと合わせて目標のファイルを組み立てる。検査値やブロック番号も回線を通るので、通信量が文字どおり差分だけになるわけではない。それでも似たファイルを細い回線で更新するなら、丸ごとの再配送より小さな荷物で済み得る。

１バイトずつずれても見つける

旧ファイルの区切り位置と同じ場所だけ探しては、冒頭に文章が入った後の一致部分を逃す。新ファイルのどのバイト位置からでも旧ブロックを探さなければならない。毎回ブロック全体を計算し直せば、今度はCPUの負担が大きい。

原報告のローリング検査値の節では、窓を１バイト進めた次の値を、前の値から出ていくバイトを引き、新しく入るバイトを加えて求める。まず安い検査で候補を選び、一致したときだけ強い検査を行う。検索方法の節は、さらにハッシュ表による一次選別を示す。内容が別の位置へ動いても見つけられるのはこのためだ。機械が計算することで、細い回線は同じ文章をもう一度運ばずに済む。

計算と送信を重ねる工夫もあった。一致が見つかるたびに、それまでの新しい部分と参照番号を送り、探索を先へ進められる。当初のアルゴリズムが要する往復は一回で、長い待ち時間のある接続では会話回数の削減も効いた。

節約したバイトの請求先

計画の実装説明は、宛先の既存ファイルを使って検査値を作る生成役、元ファイルを探す送信役、完成版を組み立てる受信役を分けている。送信役は検査値の検索にCPUを使う。受信役は旧ファイルの離れた場所を読みながら一時ファイルを書き、ディスクの負荷が高い。最後にファイル全体の検査値を照合し、合わなければ一時ファイルを破棄する。

同じ説明は通信方式の扱いにくさも隠さない。データは短い一続きの流れで、明確な区切りが少なく、各バイトの意味が文脈やプロトコル版に依存する。転送の余分な荷物は少ないが、文書化、調査、拡張は難しくなる。細い回線を守る代わりに、保守者が複雑な流れを読む費用を払う。

旧版に再利用できる部分がなければ、参照番号はほとんど役に立たない。通信が速くディスクが遅ければ、検査や読み書きの追加費用が勝ることもある。原報告が最も効果的だとしたのは、内容の近いファイルを遅い回線越しに合わせる場面である。

発言する順番を変えた発明

送信側は完成させたいファイルを知り、受信側は手元に残る部品を知る。rsyncはまず受信側にその部品を説明させ、送信側にブロック参照と実データを選ばせた。２つの完全なファイルを一台へ集めなくても、使える差分が見つかる。戻ってくるのは組立書のようなものだ。この旧ブロック、次の旧ブロック、そして新しい数行。

受信側には組立と最終確認が残る。「少なく送る」という成果は、計算、ディスクアクセス、扱いにくい通信方式と交換された。運送屋は図書館を丸ごと二度運ばずに済んだが、両方の倉庫は棚を調べる仕事を引き受けた。