共同編集システムの設計：OT と CRDT、プレゼンス、同期

2 人が同じ段落に同時に入力します。一瞬のうちに両方の画面に同じテキストが表示され、どちらが入力した文字も消えていません。これを実現するには、共有状態への同時編集という 1 つの特有の問題と、ルーティング、永続化、プレゼンス、再接続といった一連のありふれたインフラの問題を解く必要があります。

この記事では、リアルタイムの共同編集エディターを設計します。具体例で並行性の問題を確認し、Operational Transformation（OT）と Conflict-free Replicated Data Types（CRDT）を比較し、Figma が採用しているサーバー主導のアプローチと、それらを取り巻くアーキテクチャを図とともに説明します。

5 文字で見る核心の問題

ドキュメント ABC から始めます。位置は 0 から数えます。

• Alice が位置 1 に X を挿入し、画面は AXBC になります。
• 同時に Bob が位置 2 の C を削除し、画面は AB になります。

各クライアントは相手の操作を受け取り、そのまま適用します。

• Bob は「位置 1 に X を挿入」を AB に適用し、AXB を得ます。
• Alice は「位置 2 を削除」を AXBC に適用して B を消してしまい、AXC を得ます。

ドキュメントが食い違い、Alice のコピーからは誰も削除していない文字が失われました。共同編集エディターはどれも、これを防ぐために存在します。解決策には 2 つの系統があります。

Operational Transformation

OT は操作を位置として保持し、届いた操作を、それがまだ見ていない並行操作に対して変換します。Bob の「位置 2 を削除」は、Alice の位置 1 への挿入より前に作られました。この挿入は、それより後ろのすべてを 1 つ右にずらします。挿入に対して変換すると「位置 3 を削除」になり、Alice の AXBC は AXB になって、Bob と一致します。

本番の OT システムは、操作を順序付けるために中央サーバーを使います。このアプローチは 1995 年の Jupiter システムにさかのぼり、Google Docs も 2010 年にエディターを作り直した際に説明しています。

1. 各クライアントは、操作の基になったサーバーのリビジョンを付けて操作を送ります。
2. サーバーは、そのリビジョン以降に受け入れたすべての操作に対して各操作を変換し、次のリビジョン番号を割り当てて結果をブロードキャストします。
3. 各クライアントは、届いた操作を、自分のまだ確認されていない操作に対して変換します。

OT の強みは、操作がコンパクトであることと、テキストでの長い実績です。弱みは変換関数そのものです。リッチテキスト、表、入れ子構造では、あらゆる操作タイプの組み合わせを正しく扱うのが難しいことで知られており、設計は順序を決めるサーバーに依存します。

CRDT

CRDT は、並行する更新をどの順序で適用しても、すべてのレプリカが同じ状態に収束するように設計されたデータ型で、2011 年に Shapiro らによって定式化されました。テキストの場合、挿入された各文字には、クライアント ID とカウンターのような一意で順序付きの識別子が付き、挿入は「位置 1 に」ではなく「ID が○○の文字の後に」と指定します。削除は文字に削除済みの印を付け、トゥームストーンを残します。操作はずれていく位置ではなく安定した ID を参照するので、変換する必要がありません。

例では、Alice の挿入は「X は A の後に入る」、Bob の削除は「C を削除する」となります。どの順序で適用しても、両方のレプリカは AXB になります。

Yjs や Automerge のような CRDT ライブラリによって、これは実用的になりました。強みは、中央での順序付けが不要なため、オフライン編集やピアツーピアの同期が自然に機能し、いつでもマージできることです。コストは、文字ごとの追加メタデータ、圧縮が必要なトゥームストーン、そしてマージ結果は一貫しているものの、どちらのユーザーの意図とも違うというエッジケースです。サーバーは、アクセス制御、永続化、ファンアウトのためにはやはり役に立ちます。ただ、順序を決める必要がないだけです。

サーバー主導という中間の道

すべてのエディターが長いテキストを編集するわけではありません。Figma は古典的な OT も本来の CRDT も選びませんでした。サーバーがイベントの順序を決め、ドキュメントはプロパティを持つオブジェクトのツリーで、2 人が同じオブジェクトの同じプロパティを変更した場合は、サーバーが最後に受け取った値が勝ちます。サーバーはマルチプレイヤーのドキュメントごとに別々のプロセスを動かし、そのドキュメントを編集する全員がそのプロセスに接続します。競合がプロパティ単位で起きるデザインツール、スプレッドシート、ボードでは、どちらの代替案よりもシンプルです。

アーキテクチャ

どのアルゴリズムを選んでも、周囲のシステムは似た形になります。

1. クライアントは WebSocket でコラボレーションサービスに接続し、ドキュメントを開いている間は接続を維持します。
2. 各ドキュメントを所有するセッションサーバーは 1 台です。 doc-123 のクライアントはすべて同じサーバーに到達する必要があり、そうすることでサーバーはメモリ上で編集を順序付けたりマージしたりできます。たとえば Redis にあるディレクトリが、リースを使ってドキュメントをサーバーに対応付け、ロードバランサーやルーティング層が接続をそこへ送ります。ドキュメント ID によるコンシステントハッシュでも構いませんが、2 台のサーバーが同時に同じドキュメントを所有していると信じることが決してないようにする必要があります。
3. セッションサーバーはライブのドキュメントをメモリに保持し、届いた編集を適用して、ほかのクライアントにブロードキャストします。
4. すべての編集は、サーバーが確認応答する前に永続的な操作ログに追記されます。 ドキュメント全体の定期的なスナップショットはオブジェクトストレージに送られるので、ドキュメントを読み込むときは最新のスナップショットとそれ以降の操作を読みます。
5. 権限は接続時と操作のたびに確認します。 閲覧者の編集は、単に隠すのではなく拒否します。

コメント、バージョン履歴、検索、エクスポートは、操作ログを消費する別のサービスです。リアルタイムの経路には置きません。

プレゼンスは別種のデータ

カーソル、選択範囲、「誰がいるか」は絶えず変わり、その瞬間にしか意味がなく、1 分後には価値がありません。プレゼンスは一時的なものとして扱いましょう。同じセッションサーバーを通してブロードキャストし、ユーザーあたり毎秒数回の更新に抑え、クライアントが切断したら破棄し、操作ログには決して書き込みません。たとえば Yjs は、プレゼンスをドキュメントの状態とは別の awareness チャネルで保持します。

オフライン編集と再接続

接続は電車やエレベーターの中で頻繁に切れます。クライアントは確認応答されていない操作をローカルに保持し、再接続時に再送します。

• OT の場合、クライアントは保留中の操作を、最後に見たリビジョンとともに送ります。サーバーは、それ以降のすべての操作に対してそれらを変換します。
• CRDT の場合、クライアントとサーバーは、それぞれが何を見たかのコンパクトな要約（ステートベクターと呼ばれることが多い）を交換し、足りない更新だけを送り合います。

長いオフライン期間こそ CRDT が真価を発揮する場面です。OT でも、1 日オフラインだったクライアントは再接続できますが、サーバーは 1 日分の操作に対して変換しなければなりません。

スケーリングと障害

• ホットなドキュメント。 閲覧者が数千人、編集者が数人のドキュメントで、セッションサーバーがキーストロークのたびに数千のソケットへ自分で送信するべきではありません。閲覧者には pub/sub 層を通じてファンアウトし、更新をまとめて送ります。
• セッションサーバーのクラッシュ。 クライアントが再接続し、ディレクトリのリースが期限切れになり、新しいサーバーがスナップショットと操作ログを読み込み、クライアントが保留中の操作を再送します。永続的に記録された編集だけに確認応答を返すことが、これを無損失にしています。
• スプリットブレイン。 同じドキュメントを所有する 2 台のサーバーは、矛盾する順序を受け入れてしまいます。所有権をリースでフェンシングし、リースが切れたサーバーからの書き込みは拒否します。
• 元に戻す操作は、共同作業者ではなく自分の直前の変更を取り消す必要があります。そのため、ほかの操作と同様に変換またはマージされる新しい逆操作になります。

共同編集の図

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

• 2 つのクライアントが、ロードバランサーを経由して WebSocket で接続します。
• Redis のディレクトリが、doc-123 を所有するセッションサーバーを示します。両方の接続はサーバー A に届きます。
• サーバー A はメモリ上で編集を順序付けまたはマージし、編集とプレゼンスを両方のクライアントにブロードキャストします。
• 永続性：すべての編集は、確認応答の前に Postgres の操作ログへ送られます。スナップショットはオブジェクトストレージに送られます。
• ID プロバイダーは、クライアントの接続時にアクセスを確認します。サーバー B は別のドキュメントを所有し、サービスがどうスケールアウトするかを示しています。
• Markdown ブロックは、OT と CRDT を 3 行で比較しています。

リアルタイムシステムをわかりやすく描く

• 所有関係を示します。 ここで最も重要な事実は、1 台のサーバーが 1 つのドキュメントを所有することです。ディレクトリとルーティングを描きましょう。
• 永続データと一時データを分けます。 操作ログとスナップショットを描き、プレゼンスには永続化しないとラベルを付けます。
• クライアントを少なくとも 2 つ描きます。 問題の本質は並行性です。クライアントが 1 つではそれが見えません。
• 確認応答のポイントを示します。 編集は操作ログに入った時点で安全になります。

長時間の接続とファンアウトについては、チャットアプリのアーキテクチャ図が近い内容を扱っています。ドキュメントをサーバーにルーティングするのはロードバランサー図の考え方の応用で、一般的な手法はシステム設計図の例にあります。

Archboard で作る

1. Google または GitHub でサインインし、図を作成します。
2. クライアント用にネットワークパックの デバイス ノードを 2 つ、WebSocket の入口としてクラウドパックの クラウドロードバランサー を追加します。
3. コラボレーションサービス用に基本パックの フレーム を追加し、その中に コンピューティング ノードを 2 つ置きます。doc-123 を所有するセッションサーバー A と、セッションサーバー B です。
4. ドキュメントのディレクトリ用にデータパックの Redis ノード、操作ログ用に Postgres ノード、スナップショット用にクラウドパックの オブジェクトストレージ ノードを追加します。
5. セキュリティパックの IDプロバイダー を追加し、すべてをラベル付きのエッジでつなぎます。WebSocket、編集とプレゼンス、追記、スナップショット、リースです。
6. OT と CRDT の要約を書いた基本パックの Markdown ブロックを追加します。

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

よくある質問

OT と CRDT の違いは何ですか？ OT は並行する操作を互いに対して変換し、通常はサーバーが順序を決めます。CRDT は各要素に安定した ID を与えるので、操作は可換になり、中央での順序付けなしに、どの順序でもレプリカが収束します。

Google Docs は OT と CRDT のどちらを使っていますか？ Google は、2010 年のエディターの作り直しについて、サーバーが変更を順序付ける Operational Transformation を使っていると説明しました。新しいエディターの多くは、Yjs や Automerge のような CRDT ライブラリを使っています。

ドキュメントの編集者全員が同じサーバーに接続しなければならないのはなぜですか？ そのサーバーがライブのドキュメントを保持し、編集の順序を決めるからです。2 台のサーバーが 1 つのドキュメントの編集を独立して受け付けると、キーストロークのたびに調整が必要になります。

プレゼンスはどう保存されますか？ ほとんどの場合、保存しません。カーソルと選択範囲はリアルタイムでブロードキャストされ、頻度を抑えられ、クライアントが切断すると破棄されます。永続化しても負荷が増えるだけで、価値はありません。

共同編集エディターはオフラインでも動きますか？ はい。クライアントは操作をローカルのキューに入れ、再接続時に同期します。長いオフライン期間を最も自然に扱えるのは CRDT です。OT でも動きますが、復帰時に変換する操作が多くなります。

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