共同編集は想像以上に難しい

Google Docsは、何百万人ものユーザーのリアルタイム共同編集を支えています。入力するとカーソルが動き、共同編集者の変更も即座に反映される。一見すると手軽ですが、その簡単さは見せかけです。裏側では、共同編集は分散システムの中でも特に難しい問題の一つで、その解決策であるOperational Transformation（OT）とCRDTには、実際に作ってみるまで分からないトレードオフがそれぞれあります。

CRDT（Conflict-free Replicated Data Types）の売り文句は魅力的です。データ構造が衝突なく自動的にマージされ、中央サーバーは不要で、数学的に結果整合性が保証される。ところが、CRDTを選んだ複数のチームが経験したように、現実はもっと泥臭いものです。理論は美しい。しかし実装は過酷です。

課題：同時編集の衝突

根本的な課題は、ネットワーク遅延がある状況で二人のユーザーが同じドキュメントを同時に編集することです。ユーザーAが位置5に「Hello」を挿入します。一方、Aの編集をまだ見ていないユーザーBは、位置5の文字を削除します。最終的なドキュメントはどうなるべきでしょうか。

これは曖昧です。Bの削除は、Aの挿入前に位置5にあった文字に適用すべきなのか、挿入後の文字に適用すべきなのか。前者なら元の文字が消えて「Hello」が残り、後者なら「Hello」の「H」が消えます。どちらの解釈も妥当です。システムはどちらかを選び、すべてのクライアントが同じ結果に収束するよう保証しなければなりません。結果がずれると二人が違うドキュメントを見ることになり、これは絶対に許されない失敗です。

The convergence problem:
Initial document: "The quick brown fox"
^ position 10
User A (at time T):  Insert "very " at position 10
User B (at time T):  Delete character at position 10
A sees locally: "The quick very brown fox"
B sees locally: "The quick rown fox"  (deleted 'b')
Now A receives B's operation: delete at position 10
But A already inserted 5 chars at position 10...
Should B's delete now apply at position 10? (deletes 'v' from 'very')
Or at position 15? (deletes 'b' from 'brown' — the original target)
Both A and B must arrive at the same document.
This is the problem OT and CRDTs solve differently.

Operational Transformation（OT）

古い手法であるOT（1989年）は、操作同士を互いに変換することでこの問題を解決します。AがBの「位置10の削除」を受け取ると、AはまだBが見ていない自分の操作を確認します。Aが位置10に5文字挿入していたなら、Bの削除は位置15（元の対象文字が右にずれた位置）に適用する、というように変換するわけです。

これは機能しますし、Google Docsもこの方式を使っています。問題は変換関数です。挿入と削除だけのテキストエディタでも、すべての操作の組み合わせについて変換ルールを定義する必要があります。操作が2種類なら変換パターンは4通りです。書式、表、画像、リスト、コメントを加えると、パターン数は組み合わせ的に爆発します。どのパターンも正しくなければならず、わずかなバグがドキュメントの不一致を引き起こします。しかもそれは再現もデバッグも非常に困難です。

OTは従来、操作の全順序を決めるために中央サーバーを必要とします。サーバーがないと、同時の操作が各クライアントで異なる順序で変換され、異なる結果を生みかねません。Googleは Docs のために中央サーバーを用意できますが、P2Pアプリケーションでは OT を簡単には使えません。

CRDT：理論上の約束

CRDTはまったく異なるアプローチを取ります。操作を変換する代わりに、どんなマージ順序でも同じ結果になるデータ構造を使います。これは数学的な保証です。データ構造が有効なCRDTであれば、収束は自動的に成立します。変換関数も中央サーバーも、順序への依存も要りません。

テキスト編集で主要なCRDTは、RGA（Replicated Growable Array）などの系列CRDTです。編集によって位置が変わってしまう代わりに、各文字に一意でグローバルに順序づけられたIDを割り当てます。挿入は既存のIDの間に新しいIDを作り、削除はIDを墓石（tombstone）としてマークします。削除されても取り除かれるわけではなく、これについては後ほど詳しく説明します。

CRDT sequence representation:
Document: "cat"
Internal representation (simplified):
ID: (A,1) → 'c'   (user A, logical clock 1)
ID: (A,2) → 'a'   (user A, logical clock 2)
ID: (A,3) → 't'   (user A, logical clock 3)
User B inserts 'h' between 'c' and 'a':
ID: (B,1) → 'h'   position: between (A,1) and (A,2)
Document: "chat"
User A (concurrently) inserts 'r' between 'c' and 'a':
ID: (A,4) → 'r'   position: between (A,1) and (A,2)
Both IDs go between the same characters.
The CRDT uses a deterministic tie-breaking rule
(e.g., higher user ID wins) to order them.
Final document: "chart" or "chrat"
(deterministic — all clients get the same result)

CRDT：現実の姿

衝突がなく、分散していて、数学的に収束が保証されるというCRDTの約束は本物です。しかし、エンジニアリング上の課題は非常に大きいです。

墓石が蓄積する。CRDTで文字を削除しても、データ構造から取り除くことはできません。他のレプリカがまだその削除を見ていない可能性があり、自分の編集を正しく配置するためにそのIDが必要だからです。そこで削除された文字は墓石としてマークされ、見えないけれど残り続けます。大量に編集されたドキュメントには数千もの墓石が溜まります。1000文字のドキュメントでも、編集履歴から5万個の墓石が生じることがあります。これはメモリを圧迫し、操作を遅くします。

メタデータのオーバーヘッドが非常に大きい。各文字には一意のID（ユーザー識別子と論理タイムスタンプ）、隣接するIDへのポインタ、墓石フラグが必要です。文字あたりのメタデータは50〜100バイトに達することもあります。100KBのドキュメントなら、CRDTの表現は5〜10MBになるかもしれません。これは同期に響きます。CRDTの状態全体をネットワークで送るのは、コストがかさみます。

履歴が増えるほど性能が落ちる。系列CRDTの操作はO(1)ではありません。文字を挿入するには、ID順に並んだ系列の中で正しい位置を探す必要があり、その探索は墓石を含むIDの総数に依存します。編集履歴が長いドキュメントでは、これははっきりと遅くなります。

意図の保持は難しい。CRDTは収束を保証します。つまり、すべてのレプリカが同じ状態に到達します。しかし、それが「正しい」状態かどうかは別問題です。二人が同じ単語を同時に編集すると、CRDTは両者の文字を決定的な方法で混ぜ合わせます。結果は収束しますが、意味をなさないかもしれません。OTなら、一方のユーザーの編集をそのまま保ち、もう一方をその周囲に適用するよう設計できます。CRDTは機械的にマージするだけです。

Yjsと現実的な中間地点

Yjsは JavaScript で最も人気のあるCRDTライブラリで、多くのWebアプリケーションの共同編集機能を支えています。よくできたライブラリで、コンパクトなバイナリエンコーディングでメタデータのオーバーヘッドを減らし、全クライアントがオンラインのときには墓石のガベージコレクションも機能します。理論上のCRDTの問題の多くを、実用的な最適化で緩和しています。

ただし、Yjsは魔法ではありません。採用したチームは、CRDTライブラリが解決するのは収束の問題であって、共同編集の問題ではないと気づきます。依然として必要なものがあります。ピア発見のためのシグナリングサーバー、オフライン中の変更を保存する永続化層、高レベルの操作の衝突解決（二人が同じセクションを再構成したらどうなるか）、プレゼンス管理（カーソルや選択範囲）、他のユーザーの編集を尊重するundo/redo、そして権限管理です。

Yjsで共同編集エディタを作った後、CRDTのアプローチは不要な複雑さを加えるだけだと結論づけたチームもあります。アプリケーションに中央サーバーがあるなら（ほとんどはあります）、OTや、もっと単純な手法（競合検出付きのlast-write-wins）の方が実用的かもしれません。CRDTが真価を発揮するのは、オフラインファーストのアプリケーション、ローカルファーストのソフトウェア、中央の権威を想定できない本物のP2Pシナリオです。

多くのアプリケーションがすべきこと

自分のアプリケーションに共同編集を追加するなら、実用的な判断の枠組みは次のとおりです。

• 中央サーバーがあり、ドキュメントが小さいなら：OTを使いましょう。Googleのアプローチは機能します。Node.js向けにはShareDBのようなOT実装のライブラリがあります。中央サーバーがあれば、順序付け、永続化、衝突解決、権限管理のすべてが単純になります。
• オフライン対応やP2Pが必要なら：CRDT（YjsまたはAutomerge）を使いましょう。真のオフライン編集やP2P同期を正しく扱えるのは、現状CRDTだけです。メタデータのオーバーヘッドと墓石の蓄積は、分散化のコストとして受け入れましょう。
• 共同編集者がめったに同じセクションを同時に編集しないなら：どちらも不要かもしれません。セクションごとに編集者を一人に限るシンプルなロックや、よいコンフリクトUIを備えたlast-write-winsで、多くの実際の共同作業パターンはOTやCRDTの複雑さなしにカバーできます。
• Google Docsの競合サービスを作ろうとしているなら：分散システムのエンジニアチームと数年の開発期間が必要です。週末のプロジェクトではありません。共同編集の表面的なシンプルさの裏には、途方もない複雑さが隠れています。

率直な評価

共同編集は、難しさが一見して分かりにくい問題の一つです。ハッピーパス、つまり二人が重ならない編集をするケースは、ほぼどのアプローチでも動きます。難しいのは、同じ領域への同時編集、後から同期されるオフライン編集、表やネストされたリスト、埋め込みオブジェクトといった複雑なドキュメント構造などです。これらにはOTとCRDTのトレードオフへの深い理解が求められます。

どちらか一方が厳密に優れているわけではありません。OTはサーバーがあれば単純ですが、なければ難しくなります。CRDTはサーバーなしで動きますが、メタデータのオーバーヘッドと墓石の蓄積を抱えます。どちらも、コアアルゴリズムを超えた慎重なエンジニアリングを必要とします。そして、そのエンジニアリング（プレゼンス、永続化、権限、undo）は、収束の問題そのものより難しいことがよくあります。

業界は徐々に、実用的なハイブリッドへと収束しつつあります。データモデルにはCRDTを使い（自動マージの保証）、調整（プレゼンス、権限、ガベージコレクション）にはサーバーを使う方式です。数学的な収束と実用的なインフラの両方を得られます。しかし、それは両方の世界の複雑さも抱え込むことになります。だからこそ、35年の研究を経ても共同編集は依然として難しい問題なのです。