- 協調テキスト編集の問題を解決する新しいアプローチを紹介。複雑なアルゴリズムなしでも実現可能
- 従来のCRDTおよびOT方式の複雑さと制約を避け、シンプルなIDベースの挿入方式を使用
- この方式ではサーバーが「何をどこに挿入するか」を直接指定されて処理するため、柔軟性が高い
- 楽観的ローカル更新のためにサーバーリコンシリエーション戦略を活用し、状態同期の問題を解決
- 拡張性と理解しやすさを備えたこの方式は、既存の協調アプリ開発に直接実装可能な代替案を提示する
Collaborative Text Editing without CRDTs or OT
問題提起
- テキストの協調編集は非常に難しい機能で、とくに同時編集時にはテキストインデックスが崩れる問題(index rebasing) が発生する
- 従来方式であるCRDT(コンフリクトフリー複製データ型) とOT(Operational Transformation) は、それぞれ複雑な数学モデルに基づいている
- CRDT: 各文字をIDで追跡し、ツリーベースで整列
- OT: 他ユーザーの入力を反映してインデックスを動的に再調整
- どちらの方式もライブラリ依存性が高く、開発者ごとのカスタマイズが難しい
新しいアプローチ
中核アイデア
- 各文字を一意のID(UUID)で表し、クライアントはサーバーに**「どのIDの後にどの文字を挿入するか」という命令**を送る
- 例: "insert ' the' after
f1bdb70a" → f1bdb70a は挿入対象の文字ID
- サーバーはこれをそのまま解釈して挿入することで競合を回避する
削除処理
- 文字を削除する場合も、そのIDは内部リストに残し、isDeletedフラグで処理する
- 実際のユーザー向けテキストでは見えないが、参照は維持されるため後続の操作が可能
クライアント処理と楽観的更新
- ユーザーは入力直後に結果を見られる必要があるため、サーバー応答前にローカルへ反映する(楽観的更新)
- サーバーリコンシリエーション戦略を使って:
- ローカルの未確定操作をすべて巻き戻す
- サーバー操作を適用する
- 再びローカル操作を再適用して最終的な同期状態を確保する
従来方式との違い
- CRDTは自動ID整列アルゴリズムを内包するが、この方式は明示的な挿入位置だけをサーバーに渡す
- 結果として、よりシンプルで明確な動作方式を確保できる
同時挿入の処理
- 例: "My name is" に対して2人のユーザーが同時に " Charlie" と " Dave" を同じ位置へ挿入
- サーバーの受信順に応じて "My name is Dave Charlie" になる
- これは自然な処理とみなされ、一部のCRDT方式のような文字単位で混ざる(interleaving) 現象は起きない
柔軟な操作のサポート
- 基本的なinsert/delete以外にも、さまざまな操作をサポート可能:
- insert-before
- 条件付き挿入("color" が存在する場合のみ "u" を追加)
- drag & drop時の位置再調整
- この柔軟性は決まった数学的特性に縛られない
リッチテキスト(書式付きテキスト)対応
- 範囲をIDベースで定義して書式を適用できる("ID XからID Yまでbold" など)
- ProseMirrorのようなエディタと連携する際も、シンプルな方法で競合解決が可能
- 基本構造を維持したままリッチテキスト機能を追加できる
分散バージョン(Decentralized)
- 中央サーバーがなくても、Lamportタイムスタンプベースで操作順を決めれば同じ方式で動作可能
- この場合、RGA, Peritext, Fugue などのCRDTと似た結果を示す
- ツリーや数学的証明がなくてもCRDTレベルの一貫性を確保可能
補助ライブラリ: Articulated
Array<{ id, isDeleted }> 形式を効率的に扱うためのライブラリ- UUIDの代わりに
{ bunchId, counter } 構造を使ってメモリを最適化
- B+Treeベースの構造で高速なID探索と挿入をサポート
- 永続(persistent)データ構造のため、サーバーリコンシリエーションと相性が良い
結論
- この方式はCRDT/OTに比べて理解しやすく、直接実装しやすい
- 多様な編集機能、権限、制約、書式などを自由に適用でき、現実的な協調エディタ実装に有利
- Articulated ライブラリは、このアプローチを実用化するためのツールとして提供される
1件のコメント
Hacker Newsのコメント
このアルゴリズムはかなり巧妙に見える。各文字にグローバルに一意なID（例: UUID）を付けて、いつでも一貫して参照できるようにする方式を説明しており、クライアントは特定のIDの後ろに文字を挿入するとサーバーに伝え、サーバーはその位置への挿入を処理する。削除は画面上で隠すだけで、内部的には位置参照の目的で保持し続ける。この方式はテキスト編集だけでなく、ゲームワールド同期など他分野にも応用できそうだと想像できる
ctrl+a、ctrl+x、ctrl+vのような大量選択・コピー・貼り付け操作には幸運を祈る、というジョークCRDTとの差異は、中央サーバーが順序付けなどの同期役を担うため、実際のデータ構造にあらかじめ定義された順序を与えなくてよい点にある、という見方の共有。クライアントとサーバー間の通信しか存在しないので、サーバーはクライアントのローカル操作をすべて処理してからリモート更新を送ることができる
dict/map のような別のデータ構造や、任意型の配列について話がないのが意外だ、という意見。実際のアプリでは、純粋なテキストの共同編集よりも、さまざまな協調データ構造のほうが必要になることが多い。データ検証、部分読み込み、より高レベルな操作など興味深い例はあるが、Yjs などにその機能がない理由は、CRDT自体というより、そうした機能そのものの実装がもともと難しいからだろうという判断
複数のデータ構造の話には深く同意する、との意見。「原子的」なオブジェクト配列を作る際、オブジェクトのプロパティ変更が不可能なら、文字列の代わりに型を変えるだけでよく、オブジェクト内部の変更もツリー探索・保存の問題なので少し複雑なだけだという言及。また、ヘルパーライブラリの利用者側で独自の「意味モデル」ロジックをフックのように接続し、不正な状態（例: 1つの todo が
isDone: trueでありながらstate: inProgressでもある場合）を防げるとよい、という期待。リンク先の記事で触れられていたリッチテキスト整形と似た文脈CRDTは衝突が起きたとき、一貫した方法でどちらか一方を選んでマージするが、問題はその結果としてデータ損失や無効なデータが生じうる点にある。git merge の衝突を常に片方だけ選んで解決すると考えれば、たいてい誤った結果やコンパイルエラーになる状況だ。自動解決だけではデータの真正性や意味が適切に保全されないことがある、という指摘。だからこそCRDTがまだ広く使われていない理由だと思う
こうしたアプローチの解説記事は面白く読めたし、自分も以前から同じ方法を使っていたが、学術界でほとんど言及されないのが不思議だ、というコメント。自分はこれを分散化された環境でCRDTとして実装し、結合性・不変性・交換可能性などの性質を維持できたと述べている
中央サーバーがない場合にだけ、複雑なCRDT/OTが本当に必要なのか、という本文メッセージの要約の試み
中央サーバーがなくても、分散方式で操作の全順序を合意して適用できるなら、CRDT/OTの複雑さは避けられる、という意見。リンクされた記事も紹介。ただしこれも一種のCRDTではあるが（より一般化された形）、undo/replay の実装は簡単ではなく、従来のCRDT/OT構造が複雑すぎると感じるときの代替として検討できる、と強調
OT（Operational Transformation）は中央サーバーを必要とする、との言及
本質的にはこれもCRDTに当たるが、文書に適用される操作順序を中央サーバーが決める点が違う、という意見。Google Docs と Zoho Writer も OT + 中央サーバー方式であり、提示されたアプローチはCRDT風ではあるが、実際には中央サーバー型サービスではより実用的だと認めている
Automerge のようなCRDTとの主な違いは、サーバーによる調停方法にある、という意見。Automerge はシーケンス番号とエージェントIDの定義済み順序で同時挿入を並べるが、このアプローチではサーバーが到着順に処理する。参照された記事の説明を引用して、「いろいろな fancy なアルゴリズムが不要なので単純化される」とある。多くのサービスはどうせ中央サーバーを使うのだから、この方式は実用的に見える一方で、サーバー調停時にはローカル編集の取り消し・再適用が必要になるため、実際にどれほど単純なのかは確信しにくい
rewind/replayも fancy なアプローチに感じるし、Persistent B+Tree もそれほど単純ではない、というコメントAutomerge も結局内部的には全順序を作れるが、実際には従来型のCRDT（RGAなど）の方式でテキスト操作を処理している。undo/replay が簡単ではないからだ、という説明
最適化されていないCRDTという感じで、max set size=1 に設定して雑に使っているだけではないか、というジョーク
サーバーリコンシリエーションを使うなら、クライアント側でマージ問題が難しくなる危険がある、という指摘。サーバー更新が順次届く中で、エディタのUXをどう滑らかに保つのか、という質問。たとえば挿入要求が失敗したら再試行するのか、その間に別の更新が来たらどうするのか、など。提案されている方法としては、編集履歴を巻き戻して再適用するか、待機してキューをフラッシュすることになるが、フロントエンドの観点では明示されていないUI/UXのエッジケースがかなりありそうで、その意味ではCRDTのほうがむしろ単純かもしれない。特にネットワーク接続が不安定な環境（例: 地下鉄）でのユーザー体験が気になる
誰かが LLM（例: 4b モデルなど）を使って、特に複雑なCRDTやOTを使わなくても、単純なケース以外のマージ衝突を解決してみたらどうか、という提案。エネルギー効率は悪いかもしれないが、案外うまく動く可能性もある
My name isに対してisの後へCharlieとDaveをそれぞれ挿入する衝突の場合、LLMがどうマージするのか疑問だ