cola: リアルタイム共同編集のためのテキストCRDT技術
(nomad.foo)- cola は Rust で書かれたリアルタイム共同編集向けのテキスト CRDT で、中央コーディネーターなしに複数のピアが同時に修正した文書を同じ状態へ収束させることに焦点を当てている
- 文書内の位置を単純なオフセットではなく
ReplicaId.n形式の Anchor として固定し、同時編集によって位置の意味が揺らぐ問題を避ける - 挿入の衝突は Lamport timestamp と
ReplicaIdの順序付けによって一貫して処理し、削除は実際に取り除く代わりに tombstone と version vector で統合条件を管理する - 実装面では
EditRunベースの RLE と Vec インデックスで表現した G-tree を使い、Rust の安全な所有権モデルの中で対数時間の探索・挿入を狙う - ベンチマークでは cola は
diamond-types、automerge、yrsと比較され、upstream ではdiamond-typesより 1.4〜2 倍速く、downstream でも非常に高速な性能を示した
cola が扱う共同編集の問題
- cola は Rust で書かれた テキスト CRDT であり、リアルタイム共同編集において中央権限なしで複数のレプリカが同じ状態に収束するよう設計されている
- ネットワーク層には、すべての編集が最終的にすべてのピアへ届くという最小限の前提だけを置く
- 編集は複数回送信されることがある
- 編集は任意の順序で到着することがある
- すべてのピアが最終的にすべての編集を受け取らなければならない
- 目標は、すべての編集を受け取った後に文書状態が一致することだけでなく、ユーザーの視点でも結果の文書が納得できる形になることでもある
オフセットではなく Anchor で位置を固定
insert "abc" at offset 8のような オフセットベースの編集 は、ほかのピアが前方の領域を同時に修正すると意味が変わり、レプリカが分岐する可能性がある- cola は文書内の位置を文字内容やオフセットではなく、安定した識別子で参照する
nの値はローカルカウンターの増加で一意性を保証できるが、中央サーバーなしでReplicaIdのグローバルな一意性を保証するのは難しい- cola は UUID のように、衝突確率を無視できるほど大きなランダム整数を使うことを前提としている
- 挿入は 1 つの Anchor で位置を指定し、削除は開始と終了の 2 つの Anchor で範囲を指定する
挿入衝突を同じ順序で整列
- 同じ Anchor に複数の挿入が入ると、cola は Lamport timestamp で順序を決める
- Lamport clock は次の規則で更新される
- ローカルでテキストを挿入するとき、clock を 1 増やす
- リモート挿入を受け取るとき、
max(current, remote_timestamp) + 1に設定する
- ある挿入
Aが挿入Bをすでに統合した環境で作られたなら、Aの Lamport timestamp はBより大きくなる - 衝突する挿入は Lamport timestamp の降順で並べられる
- Anchor と Lamport timestamp の両方が同じ 同時挿入 には、ユーザー視点でより正しい順序は存在しないため、
ReplicaIdの昇順で並べてピア間の一貫性を保つ
削除は tombstone と version vector で処理
- 削除は開始・終了オフセットを Anchor に変換したうえで、ほかのピアへ伝播する
- 2 つのピアが同じ領域を同時に削除しても、undo を考慮しない限り、一度削除したのと同じ結果になる
- cola は現在、削除の undo をサポートしていない
- 削除処理には 3 つの難点がある
- 削除されたテキストを完全に取り除くと、まだ到着していない編集の Anchor がその領域内にある可能性がある
- リモート削除を早すぎる段階で統合すると、削除を作成したピアが見ていた内容と受信側ピアの内容が異なり、レプリカが分岐する可能性がある
- 削除範囲の中でも、削除を作成したピアがまだ見ていなかった文字は削除してはならない
- 最初の問題は tombstone で解決する
- 削除された文字は文書内に残るが、削除済みとしてマークされる
- この方式はメモリ使用量を増やす
- 残りの問題は、削除メッセージに version vector を含めることで解決する
- キーは
ReplicaId、値は削除を作成したピアがその時点で見ていた最後の文字 timestamp である - 受信側ピアの version vector が削除メッセージの version vector 以上になるまで、削除の統合を待つ
- 削除 version vector の timestamp より大きい文字は削除対象からスキップする
- キーは
- cola では version vector を version map と呼んでいる
Replica とテキストバッファの分離
- 各ピアのローカル文書状態は cola では
Replicaで表現される - cola の CRDT アルゴリズムは実際の文字列内容を知る必要がない
- API 関数は文字列を引数に取らない
- cola が扱うのは文書内容ではなく数値ブロックだけである
- この設計は CRDT の仕組み と実際のテキストバッファ実装を分離する
RLE と EditRun でメタデータを削減
- 文字ごとにメタデータを付けると高性能な実装を作りにくいため、cola は連続した timestamp を持つブロックを run-length encoding でまとめる
- たとえば Wikipedia の Manhattan Project ページ全体を貼り付けると、107,000 個のブロックではなく 1 つのブロックとして表現できる
- カーソルを動かしたり削除したりせず、文を 1 文字ずつ入力する場合も、キー入力ごとにブロックを作らず 1 つの run として表現できる
- cola ではこのような連続ブロックを
EditRunと呼ぶ- 一度分割された
EditRunは文書の寿命のあいだ固定され、それ以上拡張されない - まだ分割されていない run は active 状態である
- 一度分割された
- 既存の
EditRunの途中にテキストを挿入すると、その run を 2 つに分けて、その間に新しいテキストを入れる - テキストを削除すると、該当部分を run から分離して tombstone としてマークする
- 削除された run も同じ方法で RLE できるため、tombstone のメモリ負担を抑えられる
連結リストから B-tree へ
- ローカル編集の upstream 経路は、オフセットベースの編集をほかのピアへ送れる編集に変換する過程である
- 挿入と削除のどちらでも、オフセットを含む run を見つけて Anchor を作る必要がある
- 必要に応じて run を、挿入では最大 2 つ、削除では最大 3 つに分割する
- 連結リストでは run の分割は
O(1)だが、オフセットを含む run を見つけるには先頭から走査する必要があり、線形時間 がかかる - 現在の active run とそのオフセットをキャッシュすれば、同じ位置での反復編集は高速になるが、最悪ケースは依然として線形である
- cola は対数時間の最悪性能を得るために B-tree 構造を検討する
- run は B-tree の leaf として表現される
- inode は子ノード群と子ノード長の合計を保持する
- tombstone run は長さ 0 として寄与する
- root の長さは文書全体の長さと等しい
- B-tree は探索と挿入を
O(log n)で行えるため、ローカル編集を対数時間で処理できる - ただし、リモート編集で
Anchor -> run変換を効率化するには、Anchor が含まれる leaf を見つけなければならない
G-tree: Vec インデックスで表現した B-tree
- 通常の B-tree の leaf へのポインタだけでは、top-down の挿入過程で leaf までどう降りるかが分かりにくい
- bottom-up の操作には各ノードの親ポインタが必要であり、Rust の安全な所有権モデルでは
Rc<RefCell<_>>のような構造が必要になって遅く複雑になり得る - cola はすべてのノードを
Vecのような動的配列に保存し、ノード間参照をポインタではなく インデックス で表現する- ベクタがすべてのノードを所有する
- 各ノードは親インデックスを保存できる
unsafeコードなしで双方向探索が可能になる
- この構造は、ノードインデックスが変わらないという前提に依存している
- 新しいノードはベクタの末尾に append される
- cola は run を削除せず tombstone としてマークするため、インデックス無効化の問題が起きない
- このような grow-only tree-in-a-vector 構造を cola では G-tree と呼ぶ
- G-tree Rust コード は、B-tree の親子構造を保ったままメモリ表現だけを変えた形である
G-tree が生む性能特性
- G-tree は B-tree と同様に top-down の探索と挿入を対数時間で実行する
- leaf のベクタインデックスである
LeafIdxを安定した leaf 識別子として使える - 現在の active run をポインタではなく
LeafIdxでキャッシュできる- 同じカーソル位置で反復編集すると active run を拡張し、祖先の長さだけを root まで更新する
- ツリー走査や新規割り当てなしで、数回の整数比較と 2〜4 回の整数加算だけで処理できる
- cola の G-tree は branching factor 32 を使い、inode の平均占有率は約 20 子ノードである
- 4 レベルだけで通常は約 160k 個の異なる
EditRunを保存できる automerge-paper編集トレース処理後の cola の G-tree には約 15k 個のEditRunがある- このトレースには 260k 件の編集が含まれ、数日にわたって記録されたものだ
- 4 レベルだけで通常は約 160k 個の異なる
- G-tree はノードがすでに線形メモリに保存されているため、シリアライズとデシリアライズも簡単である
Anchor を LeafIdx に変換
- リモート編集の downstream 経路は、
insert 2.3..7 at 1.2、delete between 3.4 and 2.2のような Anchor ベース編集をローカル文書のオフセット編集に変換する過程である - G-tree は上下方向に探索できるため、ある Anchor を含む run の
LeafIdxが分かれば、そのオフセットを計算できる - 重要なのは Anchor -> LeafIdx 変換である
- 単純な設計としては、補助 G-tree または B-tree を置き、leaf に
ReplicaId、temporal range、メイン G-tree のLeafIdxを保存する方法がある- leaf は
ReplicaIdと temporal range の順で完全にソートされる - Anchor を基準に木をたどって目的の
LeafIdxを見つけられる - 検索と挿入はいずれも
O(log n)である
- leaf は
- 実際の cola ソースコードは、この補助 G-tree 方式をそのまま使ってはいない
- 実際の実装では検索と挿入は
O(log f)である fは Anchor を含むEditRunが時間の経過で分割された fragment 数であるfは常にn以下であり、通常ははるかに小さい
- 実際の実装では検索と挿入は
現在の完成度と残作業
- cola の設計は、収束性、意図保存、性能を目標とする基盤を備えている
- 本番投入に向けては、undo/redo サポートといくつかの追加作業が残っている
Rust CRDT ベンチマーク
- cola は Rust ベースの 3 つの CRDT と比較されている
- ベンチマークでは、実際の character-by-character 編集トレースを処理する時間を測定する
- Rust ベンチマークライブラリ criterion を使用する
- upstream と downstream の両方向を測定する
- ベンチマークコードは crdt-benches にある
- グラフは cola の性能の 100 倍を基準線とし、cola より 100 倍以上遅い測定値は表示しない
- 実行環境は 2018 MacBook Pro、2.2GHz 6-Core Intel Core i7 である
- 別のマシンでは数値が異なる可能性はあるが、相対性能は似た傾向になると見られる
ベンチマーク結果
- upstream 方向では
yrsとautomergeが基準線を超える - upstream で cola は
diamond-typesより 1.4〜2 倍高速 である - downstream 方向では
diamond-typesがすべてのトレースで crash し、測定値を得られなかった- ライブラリの使い方が誤っていたなら結果を更新する、という留保が付いている
- downstream で cola は以前より約 2 倍遅い
- リモート編集の統合は一般にローカル編集生成より高コストであるため、予想された結果である
- cola は両方向とも高速な rope ライブラリ群と同等か、それ以上に速い水準で動作し、現時点で最速のテキスト CRDT 実装と評価されている
1件のコメント
Hacker News のコメント
G-tree は今でも 親ポインタが追加された B-tree だと思う
配列に格納されているというのは表現方法の問題にすぎず、構造を根本的に変えるものではない
依然としてポインタを保存しているが、バイト単位ではなくノードサイズ単位であり、アドレス空間の先頭ではなく最初の配列要素を基準にした相対位置であるだけ
たとえば、明示的な参照なしに配列へ格納された完全二分木も、インデックス x の子が 2x + 1 と 2x + 2 にあるという 暗黙的な表現 にすぎず、それでも二分木と呼ばれる
特に、絶対参照よりも相対的で自己管理される参照へ誘導する言語ではなおさらだ
興味深いと思った木の表現方法の一つは、ノードを深さ優先探索順にフラットな配列へ格納するもの
読み取り専用で、読み手がいずれにせよ深さ優先で走査するつもりなら、かなり効率的になり得る
S-expression と HTML が思い浮かぶ
API で見落としていなければ、これは太字・斜体のような 書式範囲 をサポートしていないように見える
私の知る限り、リッチテキスト CRDT アルゴリズムではまだ Peritext が最先端 https://www.inkandswitch.com/peritext/
このプロジェクトが Peritext アルゴリズムのリッチテキスト機能まで取り込んでくれるとよい
ユーザーが意味的に有効な状態を説明するモデルやスキーマを定義する方式だ
たとえば JSON を単純にマージすると、構文的には有効でも意味的にはおかしな状態になり得る
Peritext アルゴリズムが、太字・斜体・下線は加算的な演算で、ハイライト色はそうではないと知っているように、ユーザーがスキーマで
state: notStartedとcompletionDate: 2023-09-04は両立できないと宣言できるとよいと思うそれなら HTML のように 書式そのものをテキスト内に表現 できるのでは？
ほかのリッチテキスト表現に詳しいわけではないので確信はない
さらに、上でリンクされている Peritext の文書を見たところ、まさにこうした RTF 特有の難しさを扱っていて、かなり興味深く読んだ
Automerge や Y.js/Yrs と比べたとき、性能や機能面の違いはある？
この cola ライブラリは演算速度の面ではかなり有利に見える
メモリ使用量も気になる
Ian Piumarta の同名の成果物と混同しないように
https://www.piumarta.com/software/cola/
https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=91...
よくできた仕事だが、公平なベンチマーク には見えない
演算を計算して保存してもいないし、実際のテキストも保存していない
ここにデルタ更新をサポートするテキスト CRDT を作るには、ユーザーが別構造に
OpID => Textを保存する必要があり、このコストは安くないslotmapクレート(https://docs.rs/slotmap/latest/slotmap/)を使えば、インデックスの移動や「インデックス」が別の値を指す心配なしに削除をサポートできるslotmap ではこれをキーと呼び、キーには バージョン番号 も一緒に入っている
順序付けが難しく、バージョンはローカルでしか意味を持たない可能性があるので気になる
Etherpad と Word が扱いきれなかったプロジェクトで、これを一度使ってみようと思う
接続されているすべてのクライアントがすべての編集を受け取ると仮定するなら、オフセットと挿入/削除/置換コマンドの前に、既存テキスト状態の 期待ハッシュ を入れてはだめなのか？
そうすれば編集が適切な状態にだけ適用されることをほぼ保証でき、その後の変更は「適用されると期待されるデータ状態のハッシュ」をキーにした辞書に蓄積できる
もちろん同じデータでハッシュ演算を重複計算する必要があるためコストは大きいが、理解して実装するのは非常に単純だ
私が文書にローカル編集をして、あなたがリモート編集をすると、あなたの「期待状態」のハッシュは今後も私の文書状態と絶対に一致しない
私はすでにローカル変更をしてしまっているからだ
CRDT が収束を保証するには、すべてのクライアントがすべての編集を受け取る必要があるのはその通りだが、更新を特定の順序で適用しなくてもよいという性質が、現実の分散ユースケースでは重要になる
ブラウザで フォームの共同編集 を簡単に有効にする方法があるのか気になる
2人が同じページやフォームを開くと、相手が現在どの入力フィールドを編集中かが見え、テキスト入力フィールドにはテキスト CRDT が使われる、という形だとよい
Yjs で似たように実装してみようとしたが、かなり難しく、うまく動かなかった
その用途にはぴったりに見えるのだが