rsyncは遅い回線でデータではなくチェックサムを送ってファイルを更新する

遅い回線でファイルをコピーすると、両方のマシンがすでに共有しているものすべてが無駄になる。圧縮は2倍から4倍程度の効果しかなく、通常のdiffツールは両方のファイルが同じマシン上にあることを必要とするが、まさにそのことが回線によって不可能になっている。

Andrew TridgellとPaul Mackerrasは1996年にリモートdiffでこれを解決した。受信側は自分のファイルをブロックに分割し、各ブロックのチェックサムを送信する。送信側は1回のパスで、任意のオフセットで自分のどのブロックが一致するかを見つける。そのために、すべてのバイト位置で計算できるほど安価なローリングチェックサムを使う。一致しないデータと参照だけが回線を流れる。

この設計は1回の往復しか必要としないため、レイテンシはほとんど問題にならず、ファイルがかなり異なっていても正しく動作する。Tridgellは1996年6月19日に、このリモート更新アルゴリズムを備えたrcpの代替としてこのツールを発表した。さらに、通信と計算を重ね合わせるパイプライン処理も備えていた。

差分をリモートで計算する。内容ではなくチェックサムを送る

ローリングチェックサムにより、送信側はすべてのオフセットを安価に走査できる

1回の往復で済むため、高レイテンシの回線でも高速

強いチェックサムが弱い一致を確認してからデータを移動する

一致しないブロックだけを送ることで、類似度に比例して帯域を節約できる

帯域が乏しくファイルに重複がある場合、データではなく証拠を送る。ローリングチェックサムは、両方のファイルを1か所に置くことなく、遠端にすでに存在するものを明らかにする。

rsyncはバックアップ、ミラー、ソフトウェア配布のための標準的なUnixツールとなり、そのブロックチェックサムdiffは今日でもツールの中核である。1996年の報告書は今なおアルゴリズムの参照文献として引用されており、1回の往復という設計は後の同期システムに影響を与えた。