協調テキスト編集: CRDTやOTなしで実装する

 (mattweidner.com)
4 ポイント 投稿者 GN⁺ 2025-05-23 | 1件のコメント | WhatsAppで共有
  • 中央サーバー型の協調アプリでテキストを配列インデックスで編集すると、同時編集時に位置がずれるため、各文字に グローバル一意 ID を付けて「特定の ID の後に挿入」する形でサーバー状態を更新する
  • 実サービスで使われる CRDT と OT は強力だが、全順序アルゴリズムや操作変換ルールが複雑で、アプリの要件に合わせて内部動作を変えにくい
  • 提案手法では、クライアントとサーバーが Array<{ id: ID; char?: string; isDeleted: boolean }> 形式の ID リストを保持し、削除された文字も tombstone のように残して、後続の挿入位置参照が壊れないようにする
  • 楽観的ローカル更新は サーバー調停(server reconciliation) で処理し、リモート操作を受け取った際には保留中のローカル操作を巻き戻したうえで、リモート操作と未承認のローカル操作を順に再適用する
  • 同時挿入の順序、リッチテキスト書式、分散型への変形、Articulated ライブラリまで扱い、サーバーはアプリごとの意味に合わせて挿入・削除を超えた 柔軟な操作 を定義できる

インデックスベース編集が同時編集で壊れる理由

  • 協調テキスト編集では、クライアントはユーザー入力の操作をサーバーへ送り、サーバーは自分の 権威ある状態 を更新する必要がある
  • テキストを文字配列とみなして index 17 に " the" を挿入 のような操作を送ると、サーバー到着前に他ユーザーの挿入があることで、同じインデックスが別の位置を指してしまうことがある
    • たとえば Alice が前方に " gray" を挿入すると、Bob の index 17 はもはや元の位置ではない
    • サーバーは Bob の操作を index 22 に リベース しなければならない
  • 核心は、クライアントがどんな操作をサーバーへ送れば、そしてサーバーがそれをどう解釈すれば、テキストを「明らかに正しい」形で更新できるかという点にある
  • このインデックスのリベース問題は、Google Docs のようなリアルタイム協調アプリだけでなく、リスト項目を挿入する Web フォームや、インラインコメント・編集履歴を扱う単一スレッドのローカルアプリでも起こりうる

CRDT と OT が実務で重荷になりやすい点

  • 既存の解決策は大きく CRDT と OT に分かれる
    • CRDT は各文字に不変 ID または「position」を与え、特殊な木の走査のような数学的全順序で ID を並べる
    • OT は同時編集を考慮して操作そのものを変換し、例では index 17 挿入 を index 22 挿入 に変える
  • どちらのアプローチもすでに実サービスで使われている
    • Google Docs は OT を使っている
    • Yjs CRDT ライブラリは多くのアプリで活用されている
  • 負担は 概念的な複雑さ から生じる
    • テキスト編集 CRDT の全順序は、学術論文で定義される微妙なアルゴリズムであることが多い
    • OT アルゴリズムは代数的な「変換特性」を満たす必要があり、場合の数は二乗で増え、形式検証なしでは欠陥が起きやすい
  • 複雑なアルゴリズムは実装も複雑にし、通常は専門家が作ったライブラリを ネットワークのブラックボックス のように使うことになる
  • ライブラリが想定していない機能が必要になると、モノリシックな構造が足かせになる
    • 大きな文書で必要な部分だけをメモリに載せ、残りはディスクに置く
    • 段落ごとの編集権限や、特定書式の使用権限といったサブドキュメント権限をサーバーで強制する
    • Google Docs 風の変更提案を本文内や脇に表示する
    • Replicache のようなキー・バリューストアと同期しやすい表現でテキストを保存する
    • 挿入・削除以外に、テキスト移動、文書ツリー操作、段落の分割・結合といった操作をサポートする

文字 ID と「insert after」方式

  • 基本アイデアは、配列インデックスの代わりに各文字へ グローバル一意 ID を付けること
    • 中核データ構造は Array<{ id: ID; char: string }> という形になる
    • クライアントは index 17 に挿入 の代わりに、f1bdb70a の後に " the" を挿入 のような操作をサーバーへ送る
    • サーバーは対象 ID を見つけ、その直後に新しい文字を入れる
  • 新しい文字の ID もクライアントが一緒に指定する必要がある
    • 例: f1bdb70a の後に " the" を ids [...] で挿入
    • クライアントが ID を生成すれば、サーバー応答を受け取る前でも、続く insert after 操作でその新しい ID を参照できる
  • 削除された文字を完全に取り除くと、挿入位置を失うことがある
    • Bob が 26085702 の後に挿入しようとしている間に、別ユーザーが 26085702 の文字を削除すると、サーバーはどこに挿入すべきか分からなくなる
    • サーバーは削除済み ID も内部リストに保持しておく必要がある
  • 補正後の状態表現は次のようになる
Array<{ id: ID; char?: string; isDeleted: boolean }>
  • ユーザーに見せるテキストは、削除されていない項目だけを連結して作れる
list.filter(elt => !elt.isDeleted).map(elt => elt.char).join('')

挿入と削除の処理

  • 文字入力時のクライアントとサーバーの動作は単純である
    • クライアントは挿入位置の直前にある文字の ID、つまり before を見つける
    • 新しい文字に対して UUID のようなグローバル一意 ID id を生成する
    • サーバーへ、before の後に char を id で挿入せよという操作を送る
    • サーバーは削除済み項目も含めて before を探し、その直後に { id, char, isDeleted: false } を挿入する
  • 文字削除も ID ベースで処理する
    • クライアントは削除対象文字の id を探す
    • サーバーへ、その ID の項目を削除せよという操作を送る
    • サーバーは該当項目を見つけ、まだ削除されていなければ entry.isDeleted = true に設定する
  • この方式は CRDT や OT の論文をなぞらなくても、サーバーへ送る 編集操作の位置問題 を直接解決する
  • 単純な配列実装では文字ごとに UUID を保存する必要があるため非効率になりうるが、最適化は Articulated で扱われる

楽観的更新とサーバー調停

  • Google Docs スタイルの協調編集では、ユーザーはサーバー応答を待たずに自分の入力結果を即座に見られる必要がある
  • 難しいのは、クライアントにまだサーバー未承認の 保留中ローカル操作 がある状態で、それと同時なリモート操作をサーバーから受け取る場合である
  • この場合、CRDT は必須ではなく、サーバー調停(server reconciliation) で処理できる
    1. 保留中のすべてのローカル操作を巻き戻し、クライアント状態を以前のサーバー状態の観点まで戻す
    2. リモート操作を適用し、クライアントをサーバー状態に合わせる
    3. まだ承認されていないローカル操作を再適用する
  • より単純な戦略として、保留中のローカル操作がある間はリモート操作の処理を禁止する Wait for Ack がある
    • Bob のクライアントは、自分のメッセージが処理されたサーバー状態を受け取るまで、最初のサーバーメッセージを無視できる
    • Bob が入力を続けたりネットワーク遅延が大きかったりすると遅延が無限に伸びうるため、サーバー調停よりリアルタイム性に劣る

CRDT と異なる点

  • 提案手法は、文字ごとに ID を付けて isDeleted マークを使う点で CRDT といくつかの特徴を共有する
  • 違いは順序の扱い方にある
    • この方式では、クライアントが X を Y の後に挿入 とサーバーに伝え、サーバーはそのまま実行するか、あるいは開発者が定義した別の方法で処理する
    • テキスト編集 CRDT では、ID が複雑なアルゴリズムによって整列される
  • 複数のテキスト編集 CRDT の違いを生み出す核もこの ID 整列アルゴリズム であり、このアプローチはその部分を避けている

同時挿入が生む結果

  • 同じ位置に複数ユーザーが同時入力すると、サーバーが操作を受け取った順序の 逆順 で結果が並ぶ
  • たとえばテキストが "My name is" で、Charlie が " Charlie"、Dave が " Dave" を同時入力するとする
    • Charlie の操作が先に到着すると、サーバーは "My name is Charlie" を作る
    • Dave の操作も同じ is の s ID の後に挿入されるため、結果は "My name is Dave Charlie" になる
  • 同じ対象 ID の後に対する insert after 操作は、同時性がなくてもサーバー受信順の逆順になる
  • それでも、左から右に入力した単語同士が文字単位で入り混じることはない
    • Dave が各文字を別操作で送っても、a は D の後、v は a の後に挿入される
    • サーバー状態は "My name is D Charlie" → "My name is Da Charlie" → "My name is Dav Charlie" → "My name is Dave Charlie" のように変化する
  • 右から左へ入力する場合は、Charlie と Dave の操作が交差順でサーバーに届くと、結果テキストも交差する可能性がある
    • 実際には、両ユーザーが同時オンラインで、互いの進行中編集を無視しているときに起こりうる

サーバーはより柔軟な操作を定義できる

  • サーバー調停を使えば、サーバーはクライアント操作を事実上好きな方法で処理でき、クライアントは最終的に同じ状態へ到達する
  • これは、厳密な代数規則を満たす操作しか許さない CRDT・OT と対照的である
  • 同じ位置への同時挿入に対して、サーバーはさまざまな対応ができる
    • その操作を無視して no-op として扱う
    • ID は内部リストに追加するが即座に削除済みとしてマークし、後続の Dave の操作がその直前 ID を参照できるようにする
    • テキストは挿入しつつ、両単語にレビュー用の特殊書式を適用する
    • Dave の編集を本文脇に表示される「提案」に変換する
    • LLM にどうテキストを直すべきか尋ねる
  • クライアントは、ユーザー意図をよりよく表す操作を送ることもできる
    • insert before は、段落の上に見出しを作る際、前の段落末尾への同時挿入の途中に見出しが入ってしまうのを避けるのに使える
    • fix typo 操作は、ID X を持つ color の o の後に u を挿入するが、周辺の単語がまだ color のままのときだけ のような条件を含められる
  • サーバーは、挿入位置そのものがサーバー到着後に変わる操作も定義できる
    • 同じ位置への同時挿入をアルファベット順に再整列できる
    • ドラッグ＆ドロップ用の move 操作を追加すれば、移動されたテキスト内部への insert after を、元位置ではなく移動後のテキスト内部へ適用できる

リッチテキスト書式の処理

  • リッチテキストでは、太字、文字サイズ、ハイパーリンクのようなインライン書式を扱う
  • 範囲書式もインデックスではなく文字 ID で表現できる
    • 例: ID X から ID Y まで bold を適用
    • ID X inclusive から ID Y exclusive まで と定義すれば、範囲終端への同時挿入も太字として扱える
  • ProseMirror のようなリッチテキストエディタと組み合わせる場合、サーバーは ID X と Y の現在の配列インデックスを見つけ、ローカル ProseMirror 状態に対してその範囲を太字にせよと指示できる
  • ProseMirror は、その後その範囲内に挿入されるテキストにも太字を維持できる
    • ただしサーバーが bold set to false のような挿入操作に応じて別の処理をすることもできる
  • 協調リッチテキストのセマンティクスを理解するには、Peritext essay が参考になる

分散型への変形と CRDT とのつながり

  • ここまでは、中央サーバーが操作の全順序をサーバー受信順で決め、権威ある状態を更新すると仮定していた
  • 中央サーバーがない、あるいはサーバーが任意のアプリでは、操作に対する 最終的な全順序 を分散的に与えることができる
    • たとえば Lamport timestamps で操作を整列する
    • 各クライアントは、これまで受け取った操作を順番に処理した結果を権威ある状態とみなす
  • この場合、文字ごとの ID と insert after 操作は、分散型の「サーバーレス」調停でも機能する
  • 技術的には、この結果はテキスト編集 CRDT になる
    • 分散型で、最終的整合性を持つ協調テキスト編集アルゴリズムだからである
  • どの順序方式を使うかによって、既存 CRDT とのつながりが見えてくる
    • Lamport timestamp で操作を整列すると、結果リスト順序は RGA / Causal Trees と等価になる
    • Lamport timestamp と書式操作を組み合わせると、動作は Peritext とかなり似る
    • 深さ優先トポロジカルソートを使うと、結果リスト順序は Fugue と等価になる
  • この等価性の主張についての詳細な証明はまだ書かれていない

Articulated: 実装補助ライブラリ

  • 実際の実装では、テキスト本体は ProseMirror 状態のような別の場所に保存し、このアプローチには次の形の ID リストだけが必要になる場合もある
Array<{ id: ID; isDeleted: boolean }>
  • このリストで頻繁に必要になる操作は 4 つある
    • ID と現在の配列インデックスの相互変換
    • 指定 ID の後に新しい ID を挿入
    • ID に削除マークを付ける
    • 保存のために状態をシリアライズし、復元する
  • 単純な配列はこれらの操作に向いていない
    • 操作 1〜3 は線形時間がかかる
    • 文字ごとにオブジェクトと UUID を保存するため、メモリと保存容量が大きい
  • Articulated は、この配列と同等の機能を提供する小さな npm ライブラリである
  • 中核データ構造 IdList は、人気の高いテキスト編集 CRDT ライブラリと似た最適化を使っている
    • ID は { bunchId, counter } 形式で、bunchId は複数の ID で共有できる UUID である
    • 左から右への挿入が続く一般的なケースのように、同じ bunch の ID が連続していると、メモリ上でもシリアライズ状態でも 1 つのオブジェクトとして保存する
    • 中核データ構造は配列ではなく B+Tree なので、メソッド呼び出し時間は log または log^2 になる
  • IdList は 永続データ構造(persistent data structure) でもある
    • クライアントは、サーバーから最後に受け取った状態と楽観的状態を安価に同時保存できる
    • リモート操作を受け取った際に、サーバーの最後の状態へロールバックしやすい
  • 追加資料として docs、初期の demos、300 SLOC 未満の単純実装である IdListSimple が提供されている
  • IdListSimple は最適化と永続性を省いているが、機能的には同等であり、fuzz tests で検証されている

関連記事

1件のコメント

 
GN⁺ 2025-05-23
Hacker News のコメント

  • かなりすっきりしている。アルゴリズムは、各テキスト文字に UUID のような グローバルに一意な ID を付け、変化し続ける配列インデックスの代わりに、時間がたっても一貫して参照できるようにする方式。
    クライアントは既存の ID を参照する “insert after” 操作をサーバーへ送り、サーバーは対象 ID を探して新しい文字をその直後に挿入する。削除は表示上隠すだけで、“insert after” の位置計算のために文字は保持し続ける。テキスト編集の外でも、たとえば ゲームワールドの同期 のような用途に可能性がありそう。

    • これは文字どおり退化した CRDT だ。衝突の順序を中央サーバーが決める方式は Google Wave のころからあった。
    • これが本当にそんなに新しいのか疑問。分散システムを直列化するために 中央プロセス を使うのは、ネットワーク分断や CAP のようなものを気にし始めるまでは、当然の出発点に近い。これで 単一障害点 も生まれる。ざっと読んだだけだが、性能の話があったのかも気になる。
    • 説明しているのは CRDT では？
    • ctrl+a, ctrl+x, ctrl+v したら幸運を祈るしかなさそう。

  • こういう記事を見るとうれしい。数年前に同じ方法を見つけて、なぜ 学術文献 ではあまり見かけないのか不思議に思っていた。
    ただし私はこれを分散型の文脈で CRDT として実装し、可換性、冪等性、結合性のような性質が保たれるようにした。

    • CRDT の代替を作ろうというアイデアなら、それを CRDT にして何が得られたのか気になる。

  • dict/map や任意型の配列のような、ほかの データ構造 の話がないのは意外だった。そういうものにも簡単に拡張できるとよい。経験上、アプリでは純粋な共同テキスト編集より 協調データ構造 が必要になることのほうが多い。
    同期の例である更新の検証、部分ロード、高レベル操作は興味深いが、Yjs のようなものにこうした機能がない理由が基盤の CRDT 実装にあるのか、それともそもそもこうした機能を作るのが難しいからなのかは、説得力が弱いように見える。

    • 完全に同意。プロパティを変更できない「アトミック」なオブジェクト配列なら、文字列を独自の型に置き換えるだけでもできそう。オブジェクト内部の変更はもっと厄介だろうが、あるいはツリーを効率よく保存して走査する問題なのかもしれない。
      OP の用語で言えば、ヘルパーライブラリの利用者が軽量な セマンティックモデル のロジックを差し込んで、不正な状態を防いだり管理したりできるべきだと常々思っていた。たとえば ToDo 項目が isDone: true でありながら同時に state: inProgress であることはできない。リンク先の記事で述べられているリッチテキスト書式のセマンティクスに似ている。
    • CRDT は本質的に、衝突が起きたときに一方を 決定的に選ぶ 方式で動作する。問題は、一般にこの方式ではデータ損失がないことやデータが有効であることを保証しない点にある。
      すべての Git マージコンフリクトが、一方を自動的に選ぶ形で解決されると想像すればよい。たいていは間違った結果になり、時にはコンパイルすら通らないコードになる。その場で直す人がいなければ、さらに混乱した結果につながる。
      だから CRDT はより広く普及しなかったのだと思う。CRDT は「あると思っていた問題」だけを直し、実際の問題である データと妥当性、意味を保つ衝突解決 は解決しない。むしろ衝突解決方法を決定的に複製可能な方式にだけ制限するため、この問題を悪化させるとも言える。

  • CRDT と異なる核心は、中央サーバーがあるなら同期、つまり同時イベント間の順序確定を データ構造自体 が辞書順で処理するのではなく サーバー にやらせよう、という点に見える。
    すべての通信がクライアントとサーバーの間でのみ行われ、クライアント同士では行われないので、クライアントがサーバーに接続するとき、サーバーは新しいリモート更新を送る前に、そのクライアントのローカル操作を先にすべて処理すると保証できる。

  • この記事の要点は、CRDT/OT の全体的な複雑さ は中央サーバーがない場合にだけ必要、ということなのか？

    • 中央サーバーがなくても、操作を最終的に 全順序 に並べ、その順序で適用する分散型の方法があれば、CRDT/OT の複雑さは避けられる: https://mattweidner.com/2025/05/21/text-without-crdts.html#d...
      ほかのコメントが言うように、技術的にはこれも CRDT で、かなり一般的な形でもある。また、操作を巻き戻して再生する実装自体も簡単ではない。それでも各データ型ごとに従来型の CRDT/OT を使うよりは単純であってほしい。
    • それが CRDT の核心だ。同じデータ構造の複数の レプリカ が複数ノードにわたって管理され、各レプリカは独立に更新され、最終的にすべて収束する。
    • OT には 中央サーバー が必要。

  • この分野の専門家ではないが、Automerge のような CRDT との主な違いは サーバー調整 に見える。たとえばこの記事 [1] を見ると、Automerge は同時挿入を処理する際に順序番号を使い、挿入が同時に起きた場合は合意されたエージェント ID の順序に依存する。一方、この方式はサーバーが到着順に処理することに依存している。
    記事には「テキスト編集 CRDT では、気の利いたアルゴリズムが ID の順序を決める。その順序アルゴリズムが各種テキスト編集 CRDT の違いを生み、CRDT 論文の複雑な部分になっている。私たちはそれを完全に避ける」という内容がある。多くのアプリにはいずれにせよ中央サーバーがあるので、「気の利いたアルゴリズム」を避けられるという話は納得できる。ただしサーバー調整にはローカル編集の巻き戻しと再生が必要なので、それがはるかに単純なのかは 100% 確信しにくい。 [1] https://josephg.com/blog/crdts-go-brrr/

    • 巻き戻しと再生も特に単純ではない、という点には同意する。永続 B+Tree もあまり単純な代物ではない。
    • Automerge は内部的にすべての操作を最終的に一貫した 全順序 で保存していると理解しており、それをサーバー調整におけるサーバーの代替として使える: https://mattweidner.com/2025/05/21/text-without-crdts.html#d...
      しかし Automerge は実際にはそうしておらず、テキスト操作を従来型 CRDT である RGA で処理している。おそらく指摘のとおり、操作の巻き戻しと再生の実装が簡単ではないからだろう。

  • つまり 最適化されていない CRDT ということ？ 最大集合サイズを 1 にして、そのまま押し通すような？

    • 一種の削れない複雑さのように見えて魅力的だ。実際に起きていることに近く、単純。言うとおり最適化はされていないだろうけど。

  • サーバー調整 を使う点からすると、クライアント側の調整は難しそうだ。サーバー更新が届くたびに適用しながら、どうやって滑らかなエディタ UX を保つのだろう？
    たとえばクライアントが送った文字挿入リクエストが失敗したら、単にリトライするのか？ その間に更新が届いていたら？ 追記: “Client-Side” セクションでこのケースを認め、巻き戻してから再生することを提案し、より単純な案として待機キューが空になるまでブロックする方法も提案している。フロントエンドの観点では、明示されていない UI/UX の例外が長く尾を引きかねないので、全体としては CRDT のほうが単純かもしれないように見える。そして通信が途切れがちな ニューヨーク地下鉄 での編集感がどうなのかも気になる。

    • ProseMirror と最新の CodeMirror には、この問題に対するかなり洗練された解法がある。文書の各変更をノード/テキスト識別子ではなく、インデックスを追跡する ステップ(step) としてモデル化し、「位置マップ」というデータ構造を使って、バッファされたステップを新しい位置へマッピングしたうえで文書に適用する。
      実際かなりうまく動く。詳しくはこちら:
      https://marijnhaverbeke.nl/blog/collaborative-editing.html
      https://marijnhaverbeke.nl/blog/collaborative-editing-cm.htm...