ファイル同期システムの設計：Dropbox 型の同期の仕組み

ノート PC で 300 MB のプレゼンテーションを保存すると、1 分後にはスマートフォンで開けます。次に 1 枚のスライドの誤字を直すと、更新は 1 秒で済みます。変更した部分だけが転送されるからです。ファイル同期サービスはこれを簡単そうに見せますが、その下には、性質のまったく異なる 2 種類のデータの慎重な分離と、不安定なネットワーク、オフライン編集、数日後に目を覚ますデバイスに耐えるプロトコルがあります。

この記事では、Dropbox 型の同期サービスを設計します。要件と数値、メタデータとコンテンツの分離、チャンク分割とコンテンツハッシュ、アップロードとコミットのプロトコル、メタデータジャーナルとカーソル、通知、競合、ガベージコレクションを、アーキテクチャ図とともに扱います。

要件

• あるデバイスで保存したファイルが、数秒から数分以内にユーザーのほかのデバイスに現れること。
• 変更されたデータだけをアップロード、ダウンロードすること。
• オフラインで行った編集はデバイスの再接続時に同期され、同時編集が黙って互いを上書きしないこと。
• 共有フォルダーがアカウントをまたいで機能すること。
• データを決して失わず、復元用のバージョン履歴があること。

容量

アクティブなデバイスが 1,000 万台あり、それぞれが 1 日に 20 件の変更を同期し、重複排除後の新しいデータが変更 1 件あたり平均 256 KB だと仮定します。

メタデータのレートは控えめで、データ量は大きいものの保存は単純です。この非対称性が設計を決めます。

メタデータとコンテンツを分ける

最も重要な判断は、ファイルの内容とファイルのメタデータを 2 つの異なるシステムとして扱うことです。

• コンテンツは、バイト列のハッシュでアドレス指定される不変のブロックとして保存します。ブロックは大きく、一度だけ書き込まれ、オブジェクトストレージで簡単に複製できます。
• メタデータは、どのパスのどのファイルが、どのバージョンで、どのブロックから成るかを記録します。小さく、絶えず変わり、トランザクションと厳密な順序付けが必要です。

Dropbox はこの分離をストリーミング同期の記事で説明しています。すべてのファイルは 4 MB のブロックに分割され、各ブロックは SHA-256 でハッシュされ、ファイルの内容はそのハッシュのリスト、つまりブロックリストで識別されます。公開 API は今も同じ考え方をコンテンツハッシュとして提供しています。各 4 MB ブロックの SHA-256 を求め、それらを連結したものの SHA-256 を取ります。

チャンク分割：固定長か内容定義か

固定サイズのブロックは単純で、高速に計算できます。弱点は、ファイルの先頭付近にバイトが挿入されたときに現れます。挿入位置より後ろのブロック境界がすべてずれ、すべてのブロックハッシュが変わってしまいます。

内容定義チャンク分割（content-defined chunking）は、内容に対するローリングハッシュがあるパターンに一致した位置に境界を置きます。rsync のローリングチェックサムや、FastCDC のような新しいアルゴリズムがこの方式です。境界は内容とともに動くので、挿入によって変わるのはその周辺のチャンクだけです。

主に末尾への追記か丸ごとの置き換えで変わるファイルなら、固定ブロックで十分です。大きなドキュメント、ディスクイメージ、データベースのように途中が編集されるファイルでは、内容定義チャンク分割のほうがはるかに帯域を節約できます。

アップロードとコミットのプロトコル

1. デスクトップクライアントは OS のファイル監視機能で変更に気づき、ファイルの変更が止まるのを待ってから、チャンクに分割してハッシュを計算します。
2. メタデータサービスにコミットを送ります。内容は、このパス、この新しいブロックリスト、親バージョン N を基にしていること、です。
3. メタデータサービスは、すでに保存しているハッシュを確認し、必要なハッシュを返します。
4. クライアントはそのブロックだけを、並列に、それぞれハッシュで検証しながらブロックサービスにアップロードします。中断したアップロードは、足りないブロックから再開します。
5. クライアントはコミットを再試行します。今度はすべてのブロックが存在するので、メタデータサービスはファイルの新しいバージョンをジャーナルに追記します。

順序こそが安全性の要です。ブロックを参照するバージョンは、そのすべてが保存されるまで決してコミットされません。どの時点でクラッシュしても、残るのは古いバージョンか新しいバージョンのどちらかで、存在しないデータを指すファイルが残ることはありません。

コンテンツアドレス方式では、重複排除も無料で手に入ります。3 つのフォルダーにコピーしたファイルや、以前のバージョンに戻したファイルは、何も新しくアップロードしません。アカウントをまたいだ重複排除はさらに容量を節約できますが、誰かが同じファイルを保存していることが明らかになりかねないため、多くの設計では 1 つのアカウントか共有フォルダーの中でだけ重複排除します。

メタデータジャーナルとカーソル

ファイルを名前空間にまとめます。たとえば、ユーザー自身のフォルダーツリーや 1 つの共有フォルダーです。メタデータサービスは名前空間ごとに追記専用のジャーナルを持ちます。各変更には次のシーケンス番号が付き、パス、バージョン、ブロックリストが記録されます。

各クライアントは名前空間ごとにカーソル、つまり最後に適用したシーケンス番号を保存します。すると、下り方向の同期は「この名前空間で自分のカーソル以降をすべてください」という 1 つの問いになります。ジャーナルのおかげで、これは安価で、順序が保たれ、再開も可能です。1 週間オフラインだったデバイスも同じ問いを投げ、1 週間分の変更を受け取ります。メタデータは名前空間でシャーディングします。ある名前空間の変更が、別の名前空間とのトランザクションを必要とすることはないからです。

通知：デバイスに同期を促す

アイドル状態のすべてのデバイスからジャーナルをポーリングするのは無駄です。代わりに、アイドル状態のデスクトップクライアントは通知サービスへのロングポール接続を保持します。ある名前空間のジャーナルが進むと、サービスは待機中のリクエストに「変更あり」と応答し、各クライアントはカーソル以降の変更を一覧して、持っていないブロックをダウンロードします。Dropbox の公開 API も、同じパターンを list_folder/longpoll と list_folder/continue として提供しています。

モバイルアプリはバックグラウンドで接続を開いたままにできないため、プラットフォームのプッシュ通知に頼り、アプリを開いたときに同期します。

クライアント側

デスクトップクライアントはシステムの半分を担います。各ファイルの最後に同期した状態、つまりパス、バージョン、ブロックリスト、サイズ、更新日時をローカルのデータベースに保持します。3 つの状態を比べて、それぞれの動作を決めます。

ローカルのブロックキャッシュがあれば、デバイスがほかのファイルですでに持っているブロックをダウンロードせずに済みます。

競合

2 台のデバイスがオフラインのまま同じファイルを編集します。どちらも後で親バージョン N を基にコミットします。メタデータサービスは最初のコミットを受け入れてバージョン N+1 を作り、2 つ目は親がもう最新ではないので拒否します。理解できないバイナリファイルをマージする代わりに、負けたクライアントは自分のバージョンを競合コピーとして元のファイルの隣に保存し、両方を同期します。判断するのはユーザーです。

これは楽観的並行性制御です。すべてのコミットは、基にしたバージョンを示します。同じチェックで、実際にはもっと難しいディレクトリ操作も扱います。あるデバイスでの名前変更と別のデバイスでの編集、あるいは編集と競合する削除などです。こうしたケースは明示的に書き出しておきましょう。同期エンジンがデータを失うのはそこです。

バージョン履歴とガベージコレクション

古いバージョンはブロックリストを保持しているので、ファイルの復元は、古いブロックリストを最新バージョンとしてコミットするだけです。ブロックがゴミになるのは、保持期間内のどのバージョンからも参照されなくなったときだけです。ガベージコレクションは猶予期間付きのマークアンドスイープで実行し、最後の参照が消えた時点ですぐ削除するようなことはしません。サーバーが孤立していると考えているブロックを再利用するブロックリストを、クライアントがまさにコミットしようとしているかもしれないからです。

ファイル同期の図

図の読み方は次のとおりです。

• 左のノート PC がブロックリストをメタデータサービスにコミットし、サーバーに足りないハッシュを受け取ります。
• ブロックのアップロードはブロックサービスに送られ、ハッシュをキーとしてオブジェクトストレージに格納されます。
• メタデータサービスは新しいバージョンを Postgres の名前空間ジャーナルに追記し、変更を発行します。
• 通知サービスはスマートフォンのロングポールに応答します。スマートフォンはカーソル以降の変更を一覧し、足りないブロックだけをダウンロードします。
• Markdown ブロックは、プロトコルの 6 つのステップを順に並べています。

同期システムをわかりやすく描く

• メタデータとコンテンツを別々の経路として描きます。 ストアも、スケーリングも、障害の現れ方も異なります。
• プロトコルのステップ番号をエッジに付けます。 コミット、足りないハッシュ、アップロード、再コミット。順序そのものが正しさの根拠です。
• 2 台目のデバイスを描きます。 同期は書き手と同じくらい読み手の問題です。クライアントが 1 つだけの図では、通知とカーソルが見えません。
• パーティションキーをラベルに書きます。 メタデータは名前空間、ブロックはハッシュです。

一般的な進め方はシステム設計図の例を参照してください。プッシュの部分は通知システムの設計に似ており、オブジェクトストレージへのチャンク単位のアップロードは動画ストリーミングのアーキテクチャ図にも登場します。メタデータの分割はデータベースシャーディング図に従います。

Archboard で作る

1. Google または GitHub でサインインし、図を作成します。
2. ネットワークパックの デバイス ノードを 2 つ追加します。ノート PC とスマートフォンです。
3. 同期バックエンド用に基本パックの フレーム を追加し、その端にクラウドパックの APIゲートウェイ を置きます。
4. フレームの中に、メタデータ、ブロック、通知の各サービス用としてクラウドパックの コンピューティング ノードを 3 つ、ジャーナル用にデータパックの Postgres ノード、ブロック用にクラウドパックの オブジェクトストレージ ノード、ジャーナルのイベント用にデータパックの Kafka ノードを追加します。
5. エッジにプロトコルの順で番号を付けます。コミット、足りないハッシュ、アップロード、再コミット、通知、一覧とダウンロードです。
6. プロトコルと容量を書いた基本パックの Markdown ブロックを追加します。

この例で使うダイアグラムノードは 11 個で、Free プランの範囲に収まります。

よくある質問

同期サービスがファイルをブロックに分割するのはなぜですか？ ブロックにすると、クライアントは変更部分だけをアップロードし、中断した転送を再開し、同一のデータを重複排除できます。ブロックのハッシュがその ID なので、サーバーはどのブロックをすでに持っているかをすぐに判断できます。

固定サイズと内容定義のどちらのチャンク分割を使うべきですか？ 固定サイズのブロックのほうが単純で、計算コストも低くなります。内容定義チャンク分割は、ファイルの途中にバイトが挿入されてもチャンク境界を安定に保つので、その場で編集されるファイルでは帯域を節約できます。

クライアントはサーバー側で何が変わったかをどう知るのですか？ 名前空間ごとにカーソルを持ち、それ以降のジャーナルエントリーをすべてメタデータサービスに問い合わせます。いつ問い合わせるかは、ロングポールかプッシュ通知が知らせます。

競合する編集はどう扱われますか？ 各コミットは基にしたバージョンを示します。別のデバイスが先にコミットしていればコミットは失敗し、クライアントは相手の編集を上書きせず、自分の編集を競合コピーとして残します。

重複排除はユーザーをまたいで機能しますか？ 機能させることはできますが、別のアカウントが同じファイルを保存していることが明らかになるおそれがあり、ユーザーごとの暗号化とは両立しません。多くのサービスは、重複排除を 1 つのアカウントか共有フォルダーの中に限っています。

無料で始める — 1 シート、クレジットカード不要。