rsync の効率化(?)
magicant起点
rsync は転送元で 1 バイトごとにローリングハッシュの差分生成と (転送先から受け取った) 既存ファイルのローリングハッシュ値との比較を行ってをり、なんか遅さう。64 ビットプロセッサーが広く普及した現在は 8 バイト単位でハッシュを処理できる仕組みがあるともっと速くなるのでは?
新しい分割方法に基づいた転送方法
- 転送先にある古いファイルを適当な固定長のブロックに区切る。最後のブロックは短くてもよい。
- 各ブロックの中から一つづつ分割点を選ぶ。分割点の選び方はそのブロック内にあるデータのみで決まる函数とする。
- 隣り合ふブロック同士の分割点から分割点までの間にあるデータに対しチェックサムを計算する。各分割の長さは高々ブロックサイズの 2 倍以下となる。
- 各チェックサム値を転送先から転送元に送る。
- 転送元側も同様に送信したいファイルを同じ固定長のブロックに区切り、同じ分割点選択函数で分割し、各分割のチェックサムを取る。
- チェックサムが一致すれば、同じ分割が転送先に既にあるので、分割の中身のデータではなくて、分割 (のチェックサム) (の ID) を送ればよい。一致するチェックサムがなければ、転送元はその分割のデータをそのまま送る。
このやり方だと、転送元は 1 バイトごとにローリングハッシュを計算・検索する必要はなく、分割の個数だけチェックサムの生成と検索を行えばよい。一方、分割点を選ぶという新たな操作が加はる。
分割点選択函数に求められる性質
同じ部分バイト列を含む異なるブロックに対して、部分バイト列内の同じ位置で分割するやうな選択が好ましい。例えば 123456 といふ 6 文字のブロックを与へた時に 4 と 5 の間で分割した場合、 345678 といふブロックを与へた時にも高い確率で 4 と 5 の間で分割されるとよい。これにより、ファイルの前半に差分があってファイルの後半のデータの位置がずれた場合でも同じデータへの分割に帰着してチェックサムが一致することが期待される。
magicant上の方法だと、分割の長さに上限があり、極端に長い分割が生成されてしまうことを防ぐことができるが、分割の位置が必ずしも一定しない。
分割点として選ばれやすい箇所が二つ近くにある場合、それらが異なるブロックに属すれば両方が分割点となるが、同一ブロック内にあればどちらか片方しか分割点になれない。どちらが分割点に選ばれるかは周囲の状況に依存し、一定でない。
しかし、同一の部分バイト列に対する分割の有無と位置はブロックの区切り位置や他の部分バイト列の内容とは無関係になるべく一定になってほしい。といふことを前提とすると、上の固定サイズのブロックから分割点を選ぶやり方は課題がある。
magicantファイルの中身(のみ)に基づいてファイルを適度な大きさに分割する操作を content-defined chunking といふらしい。21 世紀に入ってから、ナントカ CDC みたいな名前のアルゴリズムがいくつも提唱されてゐるやうだ。
適当にググって https://joshleeb.com/posts/content-defined-chunking.html といふページを見付けた。(まだ読んでない)
magicantImproving on Gear Hashing with FastCDC ではローリングハッシュに対するマスクとして 0x9111111111111110 みたいに分散したビットを持つ値を推奨してゐる。
0xFFF0000000000000 みたいに上位に固めたマスクでは駄目なのだらうか。ギアハッシュの下位ビットの方は最近ウィンドウ内に入ったバイトの影響しか受けてゐないため、ウィンドウ内のより多くのバイトの影響が残ってゐる上位ビットを優先的に判断材料にした方が結果がより広く分散するのでは?
magicant一方で、ウィンドウ幅よりも短い同一バイト列がコンテンツ内に繰り返し現れるのなら、それらを分割点として選出されやすくするために、ウィンドウ内の比較的前方にあるバイトによる影響を少なくしたい。この場合はギアハッシュの値の下位ビットを重視した方が良いことになる。
magicantQuickCDC の発想 (分割の長さと始まり数バイト分の中身をキャッシュしておいて、投機的に分割位置を推測する) は rsync にも応用できさう。
magicantImproving on Gear Hashing with FastCDC に書かれてゐる FastCDC のアルゴリズムでは、分割の長さを揃へるために二種類のマスクを使ひ分けるとされてゐる。なかなか分割点が見付からないときに、立ってゐるビットが少ないマスクに取り換へることでより早く分割点が見付かるやうに仕向ける。
しかし、マスクを切り換へる地点は前回の分割点からの距離で決まるので、それまでの間に長さが変はるやうなファイル差分が生じてゐる場合は切り換へ位置がずれる。この影響で分割点の候補が採用されたりされなかったりする可能性がある。
特に、新しいマスクで見付けた分割点のすぐあと (分割の長さの下限以内の距離) に、本来のマスクで見付かる分割点がある場合は、それをスキップするよりも、そちらを分割点として優先した方がその後の分割のされ方が共通のパターンに収束する可能性が高い。
magicant実際の rsync の動作速度を測ってみると、CPU 使用率は数割程度にとどまり、CPU でのハッシュ計算が性能に大きく影響してゐるやうには見えない。
むしろ、ネットワーク通信速度と記憶装置の入出力速度が重要さうだ。特に、ファイルを受信する側の入出力の負荷が大きい。ファイルの一部についてチェックサムが一致してファイルの中身ではなくチェックサム (の ID) が送られてきた場合、受信側は手元にある既存ファイルの中からそのチェックサムに相当する部分の中身を読み取り、結果をファイルに書き出す必要がある。これは、実質的に 1 kiB の内容を転送するために受信側で 1 kiB の書き込みだけでなく 1 kiB の読み込みも必要になるといふことであり、記憶装置の速度が遅い場合やファイルの中身が OS のメモリキャッシュに載らない位に大きい場合にボトルネックとなる。つまり、ネットワーク通信のスループットと受信側記憶装置の書き込みスループットがほぼ同じ (またはネットワークの方が速い) なら、チェックサムを使って通信量を削減するよりも、ファイルをそのまま送ってそのまま書き込んだ方が速いといふことだ。