cola: リアルタイム共同編集のためのテキストCRDT技術

• Rustで書かれた、cola というリアルタイム共同編集向けテキストCRDT（Conflict-free Replicated Data Type）の理論的背景と技術的実装についての説明
• CRDTは、複数のサイトで同時に複製・変更できるデータ構造であり、中央権限による調整なしでも収束が保証される
• 記事の内容は、文書の状態表現とそれを変換する編集、コード内でフレームワークを効率的に実装する方法、そして cola と他のRust製CRDTライブラリとのベンチマーク比較に分かれている
• 著者はテキストにおける Anchors という概念を紹介しており、これは並行性を可能にする形で挿入と削除の両方を指定するために使われる
• 論文では、Lamport timestamps を使用し、Lamport timestamp に従って降順に並べることで競合する挿入を処理する方法について論じている
• 著者は削除を処理するために tombstones という概念を導入している。tombstone化された文字は削除済みとしてマークされるが、文書内には保持され続ける
• 論文では、G-trees（grow-only trees）の利用によってシステム性能を向上させる方法について論じている。G-trees は双方向に走査できるため、同じカーソル位置での反復的な編集が非常に高速である
• 著者は、cola と Rust で実装された他の3つのCRDT、diamond-types、automerge、yrs とのベンチマーク比較で論文を締めくくっている。cola はアップストリームとダウンストリームの両方向で他の3つを上回っている
• 著者は、cola は現時点で知られている中で最速のテキストCRDT実装だが、本番利用に向けてはまだ取り組むべき作業があると指摘している。たとえば、undo/redo やその他の機能のサポートなど

[GN⁺]

Hacker Newsの意見

• あるコメントでは、G-tree は本質的に親ポインタが追加された B-tree であり、これを配列に格納してもその構造は根本的には変わらないと主張している
• Cola が太字やイタリックなどのリッチテキスト書式の範囲をサポートしていない可能性への懸念があり、コメント投稿者はリッチテキスト CRDT アルゴリズムの最先端技術として Peritext を提案している
• Cola と Automerge や Y.js/Yrs のような類似技術との性能や機能の比較についての質問がある
• 動的配列におけるノード所有権の問題に対する解決策が議論され、この場合すべてのノードは動的配列に保存され、インデックスが他のノードを参照するために使われる
• slotmap という crate を使って、インデックスが移動したり別の値を指したりすることを心配せずに削除をサポートする案が提案されている
• 一部のユーザーは、Etherpad や Word のような他のツールが失敗したプロジェクトで Cola を試してみたいという関心を示している
• 使用されたベンチマークの公平性に対する批判が提起されており、その理由は処理や実際のテキストを計算・保存していないためである
• この Cola は Ian Piumarta の同名作品と混同すべきではないという指摘もある
• テキスト CRDT を使ってブラウザ上でフォームの共同編集を可能にできるかという質問もある
• 「CRDT」という略語を文書内で定義すべきだという提案があり、これはあまり一般的ではないため読者が混乱する可能性があるからだ
• Cola を tiptap/prosemirror や他のテキストエディタと組み合わせて使い、CRDT ベースの共同編集を追加できる可能性についての質問も出ている