移動可能なツリーCRDTとLoroの実装

 (loro.dev)
2 ポイント 投稿者 GN⁺ 2024-07-30 | 1件のコメント | WhatsAppで共有
  • コラボレーションソフトウェアで階層構造を同時に編集すると、重複ノード、循環、削除された祖先の下位ノード移動のようなツリー衝突が発生し、Loroはこれを移動可能なツリーCRDTとして実装している
  • Martin Kleppmannらの方式は、作成・削除・移動を Move t p m c に統合し、削除を TRASH ノードへの移動として処理することで、同時の下位ノード移動を保持する
  • グローバルな順序は Lamport Timestamp と Peer ID で作り、リモート操作が既存の順序の途中に入る場合は undo-do-redo によって循環を回避する
  • Loroは兄弟ノードの並び替えのために Fractional Index を組み合わせ、同じ位置への同時挿入でインデックスが重複した場合は PeerID、jitter、インデックスの再設定で処理する
  • ベンチマークでは Loro Movable Tree は1000個のノードを作成した後、ランダム移動10000回を28msで実行し、リアルタイム共同編集と過去バージョンの checkout に十分な性能を示した

コラボレーションツリーで発生する衝突

  • 分散システムとコラボレーションソフトウェアで階層関係を管理する際、移動を削除と挿入の組み合わせとしてモデル化すると、ユーザーの期待と衝突解決の方式が食い違いやすい
  • 同じノードが複数の replica で異なる親へ同時に移動されると、1つのノードが2回削除され、2つの親の下に再作成されて、同じ内容を持つ重複ノードが生じうる
  • 移動可能なツリーの基本操作は 作成、削除、移動 の3つである
  • 同期時に主に問題となる状況は次のとおりである
    • 同じノードが削除されるのと同時に移動される
    • 同じノードが異なる親の下へ移動される
    • 異なるノードの移動が組み合わさって 循環 が生じる
    • 祖先ノードが削除されている間に下位ノードが移動される

衝突タイプごとの処理方式

  • 同じノードの削除と移動が衝突した場合、分散システムの timestamp やアプリケーション要件に応じて、一方の操作を適用し、もう一方を無視できる
  • 同じノードが異なる親の下へ移動される場合は、アプリケーションによって選択肢が変わる
    • ノードを削除した後、異なる親の下にコピーを作り、その後は独立して扱う
    • 1つのノードが2つの親を指せるようにすることもできるが、これはツリー構造を壊すため一般には受け入れにくい
    • すべての操作を整列して順番に適用すれば、すべての peer で同じ結果を作れる
  • 異なるノードの移動が循環を作る場合、移動可能なツリーの衝突解決は特に複雑になる
    • Matthew Weidner は、エラー処理、「time-out」領域のレンダリング、サーバーベースの拒否、トポロジカルソート後に循環生成操作をスキップする方法、レンダリング時に特定の edge を隠す方法、以前の親に戻す方法などを整理している
  • 祖先ノードの削除中に下位ノードが移動される状況も見落としやすい
    • 祖先のすべての下位ノードを即座に削除すると、ユーザーは自分のデータが失われたと誤解する可能性がある

DropboxとFigmaのアプローチ

  • Dropbox は当初、ファイル移動を元の場所での削除と新しい場所での作成という2段階で処理していた
    • 削除と作成の間に停電やシステムクラッシュが発生すると、データ損失のリスク があった
    • 現在は、複数人が同じファイルを同時に移動して保存しようとすると衝突を検出し、通常は元ファイルの1バージョンを保存したうえで、あるユーザーの変更に対して “conflicted copy” を作成する
  • Figma はツリー構造を共同編集システムで最も複雑な部分とみなし、各要素に parent 属性を持たせている
    • 中央サーバーが複数ユーザーの更新を監視し、ある操作が循環を作る可能性があればその操作を拒否する
    • ネットワーク遅延のため、サーバーが拒否する前に一時的に循環が生じることがある
    • この場合 Figma は循環に含まれる要素を一時的に隠し、サーバーが操作を正式に拒否するまで状態を保持する
    • 関連説明は Figmaの multiplayer technology 記事 で確認できる

移動可能なツリーCRDTの2つのアプローチ

  • 中央集権的な解決策の代わりに、CRDT によって共同編集ツリー構造を扱うことができる
  • 初期のCRDTベースのツリーアルゴリズムは実装が難しく、保存オーバーヘッドも大きかったが、最適化と改善を経て、一部の本番環境に適したツリー同期アルゴリズムが登場した
  • 代表的なCRDTベースのアプローチは2つある

Kleppmann方式: すべての操作をMoveに統合

  • A highly-available move operation for replicated trees は、ツリーの作成・削除・移動を1つの move 操作 に統合する
  • move 操作は Move t p m c の4つの値で定義される
    • t: Lamport timestamp のような、一意で整列可能な timestamp
    • p: 親ノード ID
    • m: ノードに関連付けられた metadata
    • c: 子ノード ID
  • ツリーに c が存在しなければ、親 p の下に子 c を作る 作成 操作になる
  • すでに c があれば、既存の親から新しい親 p へ移す 移動 操作になる
  • 削除は指定された TRASH ノードへの移動として処理する
    • TRASH のすべての下位ノードは削除されたものとみなされる
    • ただしメモリには残し、同時編集によってそのノードを別のノードへ移動できるようにする
    • 祖先削除と下位ノード移動が同時に発生する状況に対処するための仕組みである

順序付けとunsafe operation

  • 削除も move 操作として定義されるため、「同じノードの削除と移動」は2つの move 操作の衝突へと変わる
  • 残る主要な問題は2つである
    • 同じノードを異なる親の下へ移動すること
    • 異なるノードを移動して 循環 を生成すること
  • Lamport timestamp と Peer ID ですべての操作を線形順序に整列すれば、同じノードの同時移動も順序を持つ2つの操作として表現される
  • ツリーを move 操作だけでモデル化すると、同時編集の例外的な状況は循環生成へと還元される
  • 循環を作る操作は unsafe operation として扱われる
    • アルゴリズムは timestamp 順にすべての move 操作を整列する
    • 各操作の適用前に循環を検出する
    • 循環を作る場合はその unsafe operation を無視し、正しいツリー構造を維持する

Lamport Timestampとリモート操作の適用

  • Lamport Timestamp は分散システムのイベントの因果順序を判断できるようにする
    • 各 peer は 0 から始まる counter を持つ
    • ローカルイベントが発生すると counter を 1 増やし、その値を timestamp として使う
    • peer A が B にメッセージを送るとき、timestamp を添付する
    • B は自分の論理時計と受け取った timestamp を比較し、より大きい値に更新する
  • グローバル整列ではまず Lamport Timestamp を比較し、値が同じなら peer の一意 ID を tie-breaker として使う
  • リモート更新が既存の整列済み操作列の途中に入る場合は undo-do-redo が必要になる
    • 直近の操作を取り消す
    • 新しい操作を挿入して適用する
    • 取り消した操作を再適用する
  • move 操作を素早く取り消すために、各 move 適用前に対象ノードの old parent をキャッシュする
  • unsafe operation は効果を無視しても記録自体は保持しなければならない
    • 操作の安全性は動的に決まる
    • 後になって、循環を引き起こしていた別ノードが先に削除される更新を受け取ると、以前は unsafe だった操作が safe になることがある
    • undo の過程で最後に効果を持っていた操作の対象親を見つけるため、ineffective の印が必要になる

undo-do-redo の例

  • 新しい操作がローカルにない操作に依存する場合、中間バージョンの更新がまだ欠けている状態のため、一時的にキャッシュした後、不足している更新を受信してから適用する必要がある
  • 新しい opId が既存のすべての操作より大きければ、すぐに適用できる
    • safe であれば対象ノードの現在の親を old parent として記録し、move を適用する
    • unsafe であれば ineffective としてマークし、効果を無視する
  • 新しい opId が既存の順序の途中に入る場合、その後の操作を1つずつ取り出して巻き戻し、新しい操作を適用した後、巻き戻した操作を順番に再適用する
  • 例の流れでは、Peer1 がローカルで C を B の下へ移動した後、Peer0 が B を C の下へ移動した操作を受信する
    • Lamport timestamp の順序では 0:3 が 1:3 より前なので、まず 1:3 を undo して C を old parent の A に戻す
    • その後 0:3 によって B を C の下へ移動する
    • 再び 1:3 を redo して C を B の下へ移動しようとするが、循環が検出されるため適用されない
    • ツリーの状態は変わらないまま、undo-do-redo の過程が完了する

Evan Wallace 方式: 過去の親の追跡

  • Evan Wallace の CRDT: Mutable Tree Hierarchy では、各ノードが過去のすべての親ノードを追跡する
  • 各記録された親には counter が付く
    • 新しい親の count 値は、そのノードのすべての過去の親の count より 1 大きい
    • 最も高い count を持つ親が現在の親になる
  • 同期時には親の記録も一緒に同期される
  • 循環が発生すると、ヒューリスティックアルゴリズムが循環を起こしたノードを、最も近い過去の親のうち循環を作らず root に接続された親へ再接続する
  • この過程を、循環ノードがすべてツリーに再接続されるまで繰り返し、replica 間のツリー構造を同期する
  • この方式は高コストな undo-do-redo 手順を必要としないが、リモートの move を受け取るたびに全ノードが root に接続されているかを確認し、循環ノードを再接続しなければならないため、ノード数が多い場合は性能が悪化する可能性がある
  • 性能比較用の benchmark が別途作成されている

Loro の Movable Tree 実装

  • Loro は Martin Kleppmann らの A highly-available move operation for replicated trees アルゴリズムを実装している
  • このアルゴリズムは、ほとんどの実運用シナリオで高い性能を発揮する
  • 中核となる undo-do-redo の過程は、Loro における Eg-walker(Event Graph Walker) がリモート更新を適用する方式と非常によく似ている
  • 移動可能なツリーだけでは、兄弟ノードの順序の問題は解決できない
    • outline notes やグラフィックデザインソフトウェアの layer 管理では、子ノードの整列が必要になる
    • ユーザーはノード順を調整し、それを他の共同編集者やデバイスと同期しなければならない
  • Loro は Fractional Index アルゴリズムを統合し、移動可能なツリーの子ノードを順序付け可能にしている

Fractional Index と同時挿入の衝突

  • Fractional Index は各オブジェクトにソート可能な値を付与する
    • 2つのオブジェクトの間に新しい挿入が起きると、新しいオブジェクトの Fractional Index は左右の値の間になる
    • 関連説明は Figma blog と Evan blog で確認できる
  • 分散環境で複数の peer が同じ位置に新しいノードを挿入すると、内容の異なるノードに同じ Fractional Index が割り当てられることがある
  • Loro は同一の Fractional Index を維持し、同じインデックス同士の相対順序は各 peer の固有 ID である PeerID で決定する
  • 同じ Fractional Index が両側にある場合、その間に新しい Fractional Index を作ることはできない
  • Loro はこの問題を2つの方法で処理する
    • 生成される Fractional Index に一定量の jitter を追加し、同一インデックスの発生可能性を大幅に下げる
    • たとえば 0 と 1 の間の値が本来 0.5 である場合、random jitter によって 0.52712、0.58312、0.52834 のような値になりうる
    • 0.7@A と 0.7@B の間に挿入する必要がある場合、0.7 と 1 の間で新しいノードと 0.7@B ノードにそれぞれ新しい Fractional Index を割り当てる形で再設定できる

エンコードサイズと jitter 設定

  • Loro は drifting-in-space の Vec<u8> ベースの Fractional Index 実装を使用している
  • この実装は base 256 である
    • デフォルト値では、前方または後方に 128 個の値を連続で挿入して初めて Fractional Index の byte サイズが 1 増える
  • 最悪の保存オーバーヘッドは、毎回新しい値を交互に挿入する場合に発生する
    • たとえば ab に対して a と b の間に c を入れ、さらに c と b の間に d、c と d の間に e を入れるようなケースである
    • この場合、新しい操作1つが追加の byte を必要とする可能性があるが、非常にまれな状況である
  • Loro は元の実装にシンプルな jitter 解法を追加している
    • Fractional Index に jitter 値の長さぶん random bytes を append する
    • JavaScript では doc.setFractionalIndexJitter(number) に正の値を入れることで jitter を有効化できる
    • エンコードサイズはやや増加し、各 Fractional Index ごとに jitter bytes が追加される
  • 同じ位置で Fractional Index を作成するとき、99% の確率で衝突を避けるための jitter と最大同時編集数 n の関係は次のとおりである
jitter 最大同時編集数
1 3
2 37
3 582
  • 順序付けされた多数の Fractional Index には共通 prefix が多くなる
  • Loro はエンコード時に、前の値と同じ prefix bit 数と残りの bytes だけを保存する prefix 最適化 により、全体のエンコードサイズを削減している

関連研究と選択理由

  • Fractional Index のほかにも、ツリーの sibling ノードを順序付けできる movable list CRDT がある
  • Martin Kleppmann の Moving Elements in List CRDTs は Loro の Movable List で使われている
  • Fractional Index の解法は実装がよりシンプルである
  • ツリーノードをモデル化する際、子ノードに stable position representation を提供しないと、ツリー全体の構造が過度に複雑になる
  • Fractional Index には interleaving の問題がある
    • Figma の layer item や multi-level bookmark のように、相対順序だけが必要で厳密な逐次セマンティクスが不要な場合には受け入れ可能である

ベンチマーク結果

  • Loro は Movable Tree 実装について、ランダムなノード移動、過去バージョンへの切り替え、非常に深いツリー構造という極限条件での性能をベンチマークした
  • リアルタイムコラボレーションとスムーズな過去バージョン checkout をサポートできる水準の結果が得られた
  • テスト環境は M2 Max CPU で、ベンチコードは tree.rs にある
作業 時間 設定
ランダム移動 10000 回 28ms 先に 1000 個のノードを生成
異なるバージョンへ 1000 回切り替え 153ms 先に 1000 個のノードを生成した後、1000 回移動
深さ 300 のツリーで異なるバージョンへ 1000 回切り替え 701ms 新しいノードは直前のノードの子

使用例とデモ

  • loro-crdt の LoroTree は、ノード生成、位置指定での生成、移動、root への移動、別ノードの前後への移動、親内での index 取得、Fractional Index 取得、ノードの data map へのアクセスを提供する
import { Loro, LoroTree, LoroTreeNode, LoroMap } from "loro-crdt";

let doc = new Loro();
let tree: LoroTree = doc.getTree("tree");
let root: LoroTreeNode = tree.createNode();
// By default, append to the end of the parent node's children list
let node = root.createNode();
// Specify the child's position
let node2 = root.createNode(0);
// Move `node2` to be the last child of `node`
node2.move(node);
// Move `node` to be the first child of `node2`
node.move(node2, 0);
// Move the node to become the root node
node.move();
// Move the node to be positioned after another node
node.moveAfter(node2);
// Move the node to be positioned before another node
node.moveBefore(node2);
// Retrieve the index of the node within its parent's children
let index = node.index();
// Get the `Fractional Index` of the node
let fractionalIndex = node.fractionalIndex();
// Access the associated data map container
let nodeData: LoroMap = node.data;
  • Loro により、複数 peer 間のデータ同期をシミュレーションする Todo アプリのデモが作られた
    • Movable Tree は subtask 関係を表す
    • Map は task のさまざまな属性を表す
    • Text は task title を表す
    • 生成、移動、修正、削除に加えて、Loro ベースのバージョン切り替えも実装されている
    • scrollbar をドラッグして、実行されたすべての過去バージョン間を切り替えられる

まとめ

  • 移動可能なツリー CRDT の実装は、同時移動、削除、循環、祖先削除と子孫移動の組み合わせのため難しい
  • Loro は Kleppmann らの高可用 move 演算アルゴリズムでツリー階層の移動を実装している
  • 子ノード間の移動と整列は、drifting-in-space の Fractional Index 実装を統合して処理している
  • この組み合わせは、多様なコラボレーションアプリケーションのシナリオ要件を満たせる

関連記事

1件のコメント

 
GN⁺ 2024-07-30
Hacker News のコメント

  • タスク／ノート用の新しいマルチプレイヤーエディタ [1] を作っており、テキストとアウトライナーの操作の両方に対応している
    表面的にはフラットなテキスト文書のように動作するが、アウトライナー機能のため内部的には大きなツリーになる。変更の同期には、高可用な移動操作に似た方式を使っている。ツリーを変更する操作は insmov ただ一つで、クライアントがオンラインなら変更セット C をサーバーと同期する。サーバー側にリモート変更があれば、最後の同期以降のすべての変更 R をグローバルな線形順序で返し、ローカル変更 C の insmov を取り消したうえで、R とまだ同期していない新しい変更を再適用する
    分数インデックスは使わず、insmov タプルには親 P だけでなく直前の兄弟 guid A も含める。すべてのツリー操作は最終的にサーバーが決めたグローバルな線形順序で適用されるため、並び順は insmov 操作そのもので処理される。ほとんどの場合は取り消しは不要で、サーバー上に自分の知らない insmov 変更があり、同時に自分が新しい insmov を送る場合にだけ、正しい順序での再生が必要になる。長いフライトの後に Wi-Fi へ再接続するときには起こり得るが、オンライン状態で WebSocket によるリアルタイムプッシュを受けている場合にはそれほど一般的ではなく、テキスト更新のような非 insmov 操作には必要ない
    [1] https://thymer.com

    • この方式は、サーバーのグローバルな線形順序を論理タイムスタンプとして使う RGA リスト CRDT [1] と同等に見える
      たとえば Lamport タイムスタンプの代わりにサーバー順序を使う形だ
      [1] https://inria.hal.science/inria-00555588/
    • 昨日たまたま古いスレッド[0]を読んでいて Thymer についての投稿を見つけ、興味を持った
      HN で Thymer を検索してみると 2009 年の Show HN[1] が出てきて、Thymer はこの15年間、非公開ベータだったように見える
      0. https://news.ycombinator.com/item?id=40786425
      1. https://news.ycombinator.com/item?id=518803
    • どのリッチテキストを使っているのか気になる

  • この記事はぜひ読まなければ。フリーランスのクライアント案件で React Table Library [0] をオープンソース公開し、ツリー操作に焦点を当てた
    彼らは 10 万ノード規模のフォルダ／ファイルのツリー構造を扱っており、フォルダとファイルの移動、複製、最上位およびネストしたレベルでの遅延読み込みなどを、同じテーブル構造の中で処理している。プロジェクトを終えてみると、Google Drive がなぜ同じ階層レベルでしか表示と編集を許可しないのか分かった気がした。多数のノードを持つネストされたビューでこれを実装しようとすると、考慮すべき制約があまりにも多い
    [0] https://react-table-library.com/

    • 良さそうだが、いつ完全にヘッドレスになるのか気になる

  • アドバイスが欲しい。マルチプレイヤーアプリではないが、フロントエンドにはユーザープロフィールとして使う、大きく相互接続された非正規化ツリーがある
    タイル型レイアウトのように、ユーザーがタイルを追加／削除／リサイズし、各タイルスロットに複数のコンポーネントを追加し、そのコンポーネントにもそれぞれプロフィールがある構造を想像してほしい。異なるタイル配置を持つ複数のレイアウトが存在し得るし、個別のタイルがグローバル状態の別の断片を参照または共有するという複雑さもある
    通常の REST で安全に更新するのが難しい。同じユーザーがタブを 2 つ開き、タブ 1 で更新した後にタブ 2 でも更新して、プロフィール全体が不正な状態にならないことを保証しなければならないためだ。全体として順序も重要になる。クライアント側では正しく適用された更新をサーバー側で飛ばすと壊れる可能性がある
    ごく単純な解決策として、特定の状態断片を完全に上書きできる最小データを送り、キューの後ろに入れる方式を使っていた。通常は問題ないが、実際の変更は数バイトだけなのに 50KB を送る、といった無駄が生じることがある
    一般的に CRDT が必要になる理由はないが、単一ユーザーでも状態管理がはるかに楽になりそうだと思っている。まずユーザーのブラウザタブ間で同期できるし、より重要なのは、フロントエンドの状態を単に変更すれば CRDT がサーバーとうまく調整してくれると信頼できることだ。もう自分で処理しなくてよくなる。これが理にかなっているのか、それともマルチプレイヤーやローカルファーストが不要な状況で Yjs のようなものを組み込むオーバーヘッドに価値がないのか、気になっている

    • アプリケーションが複数タブを積極的に使うなら、YJS のようなものを使うのは理にかなっているかもしれない。その種の問題を解くのに非常に効果的だからだ
      ただしプロフィール編集が単一ユーザー専用なら、CRDT の導入はやりすぎに見える。見たところ、タブを 2 つ開いたシナリオが最大のバグ要因なので、BroadcastChannel で更新イベントを他のすべてのタブに通知する方法を使える
    • このユースケースには CRDT が合っているように見える
      サーバー状態の一部を上書きする REST 呼び出しで共有状態を維持する方法は実際に脆弱で、フラットなデータレコードのフィールドを上書きする程度にしか向いていない。また、サーバーとクライアントの状態調整を常に慎重に考える必要があり、正常系でない経路では簡単に同期がずれる
      言っているように、更新がどのようにマージされるかを明示する CRDT を作れば、認知負荷は大きく下がるはずだ

  • Google Docs や Zoho Writer のようなリッチテキストコンテンツでは、リスト項目を下に移動したり新しい列を追加したりする操作、テーブル／リスト操作は本質的にツリー操作である
    このような場合の同時衝突は、文脈ごとの特別な処理がないと収束させるのが難しいことで悪名高い [1]。この実装がそうしたユースケースにも一般化された解決策を提供するのか気になる
    おそらくリーフノード、つまりテキストブロックにはリストや文字列 CRDT を使い、構造ノードであるリストやテーブルにはこのツリー CRDT を組み合わせられそうだ。ただしそうすると、すべての操作に 2 次元アドレス (parent-id, index_offset_into_that_parent) を付け加える必要がある
    [1] https://github.com/inkandswitch/peritext/issues/27

    • ずっとそう想像していた。リッチテキストはプレーンテキストに 2 つのものが追加されたものだ。太字で表示された区間のような注釈範囲と、テーブルや埋め込み画像のような非文字要素である
      テキスト CRDT は根本的には文字データを保持するリスト CRDT にすぎない。したがって埋め込み要素は、文字列内の他の項目と同じように、サイズ 1 の特殊な項目、つまり埋め込み子ノードとして簡単にモデル化できる。適切なアプローチを使えば、必要に応じてツリー内で異なる CRDT を混在させられる。たとえばリッチテキスト内にテーブルがあり、そのセルの 1 つに画像がある、といった形だ
      すべての操作に parent-crdt-id フィールドを付けるのは残念だが、避けるのは難しそうだ。幸い、実際のユースケースの大半では、連続する操作が同じ親 CRDT を共有することが非常に多そうなので、こうした ID フィールドはランレングス符号化でうまく圧縮できそうだ
    • 実装上、複数種類の CRDT を実際に組み合わせることができる。Loro の内部実装では、各操作が親 ID を保存する必要がある
      ただし Seph が言うように、同じ親の下での連続操作は効果的に圧縮できるため、このような親 ID の償却オーバーヘッドは通常大きくない

  • 画像のピクセルや 3D モデルのようにデータ密度の高いアプリケーション向けに実用的な CRDT があったのか気になる

    • コラボレーションアプリケーションでは、まずユーザーが行う編集についての概念的な枠組みと、そうした編集が非同期に起きたときにユーザーの意図と結果文書の一貫性を最もよく保つ方法を定める必要がある
      文書の具体的な表現がデータ集約的であっても、ユーザーの個々の編集や操作をエンコードする方法は依然として小さくできる
      Photoshop のような画像編集ソフトを作るとしよう。チャンネルあたり 16 ビット色深度の非圧縮 1 億 200 万画素画像、たとえば Fujifilm GFX100 の写真は TIFF で約 610MB になる。各ピクセルを個別の last-write-wins レジスタとして表現するとオーバーヘッドは大きいが、そのような表現はユーザーの意図を保つには実際には合っていない。ユーザーが行う編集は「画像のコントラストを 15% 上げる」や「ブラシ Q と色 #000 でスプライン [(0,0), (1500, 1500)] を塗る」のようなものだ。各ピクセルを Lamport タイムスタンプで同期すると、ユーザー 1 のコントラスト変更が、ユーザー 2 が塗ったピクセルを除くすべてのピクセルに適用され、上塗りされたピクセルが不自然に見える可能性がある
      代わりに、ユーザーの意図を編集操作のリストとして表現する方がよい。これは 102MB のピクセルグリッド全体よりはるかに小さい。CRDT データ構造はそうしたユーザーの意図を同期するための可能な技術的メカニズムの 1 つだが、構造は出力の具体的なデータ配置ではなく、ユーザー意図の意味論に合わせて選ぶべきだ
      それでも "add new layer named bgbelow layerfgwith pixelsdata:(10mb of pixels) at (1500, 1500)" のように大量データを含む編集操作は生じ得る。ただし、このような編集コマンドの同期オーバーヘッドは非常に低く、サイズは O(1) であり、編集コマンド内のピクセル数に比例する O(pixels) ではない
    • 完全に同じではないが、Figma は同時編集をサポートしており、CRDT に似たアプローチを使っていると理解している (https://www.figma.com/blog/how-figmas-multiplayer-technology...)
    • 画像編集では、衝突する編集はすべて最後の作者が勝つ方式で簡単に解決できるので、CRDT が本当に必要なのかは分からない
      3D モデルは別の問題で、協調 3D モデリングツールが市場にあるのは見たことがない。積極的に探したわけではない
    • 高性能なピクセルベース CRDTがどのようなものになり得るかを、大きな CRDT 記事でスケッチしたことがある: http://archagon.net/blog/2018/03/24/data-laced-with-history/...
      自分で作ってみたわけではなく、実際に実用的かどうかも確信はない。それでも少なくとも文書の全履歴は保存できる
    • 見た中でクールな例は、ラスターグラフィック向けの非破壊編集エディタである Modyfi だ
      Yjs でデータを表現しているが、生のピクセルを保存する代わりに変換の全履歴を保存している
      https://digest.browsertech.com/archive/browsertech-digest-ho...

  • この記事を GPT でチェックしたのか気になる。最初の段落からChatGPT っぽい文体が強く感じられる

    • そうではなさそうだ。こういう文法ミスは ChatGPT らしくない:
      This article introduces the implementation difficulties and challenges of Movable Tree CRDTs when collaboration, and how Loro implements it and sorts child nodes.