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

 (loro.dev)
2 ポイント 投稿者 GN⁺ 2024-07-30 | 1件のコメント | WhatsAppで共有

  • Movable tree CRDTs and Loro's implementation

  • 背景

    • 分散システムやコラボレーションソフトウェアで階層関係を管理することは複雑
    • データ構造において削除と挿入を組み合わせて移動をモデル化する際、競合解決とユーザーの期待を満たすことが難しい
    • たとえば、同じノードを別々の親へ同時に移動すると、同じ内容を持つ重複ノードが生成される可能性がある

  • 移動可能なツリーにおける競合

    • 移動可能なツリーの主な操作: 作成、削除、移動
    • 同時操作の同期時に発生しうる競合:
      • 同じノードが削除され、かつ移動される
      • 同じノードが別のノードの配下へ移動される
      • 別のノードが移動されて循環が発生する
      • 祖先ノードが削除されている間に子孫ノードが移動される
  • 同じノードの削除と移動
    • 比較的解決しやすい
    • 分散システムのタイムスタンプやアプリケーション固有の要件に応じて、一方の操作を適用し、もう一方を無視する
  • 同じノードを別の親の配下へ移動
    • 同時移動操作のマージはより複雑
    • アプリケーションに応じてさまざまなアプローチを採用可能:
      • ノードを削除し、別の親ノードの配下にコピーを生成する
      • ノードが2つの親に接続されることを許可する（通常は許可されない）
      • すべての操作を整列させて順次適用する
  • 別のノードの移動によって循環が発生する場合
    • 同時移動操作による循環の解決は複雑
    • 複数の解決策:
      • エラーを発生させる
      • 循環ノードを特別な「タイムアウト」領域にレンダリングする
      • サーバー側で移動操作を処理する
      • トポロジカルソートを使用する
      • 循環を引き起こすエッジを隠す
  • 祖先ノードの削除と子孫ノードの移動
    • 祖先ノードの削除時に子孫ノードの移動は見落とされやすい
    • すべての子孫ノードを直接削除すると、データ損失と誤解される可能性がある

  • 人気アプリケーションにおける競合処理方法

    • Dropbox: ファイル移動を削除後の作成として処理していたが、データ損失のリスクがある
    • Figma: 中央サーバーが循環を検出して操作を拒否し、一貫性を維持

  • 移動可能なツリーCRDTs

    • 中央集権的なソリューションの代わりにCRDTsを使用
    • 初期のCRDTベースアルゴリズムは実装が難しく、ストレージオーバーヘッドも大きい
    • 継続的な最適化により、一部のCRDTベースのツリー同期アルゴリズムは本番環境に適するようになった

  • 複製されたツリーのための高可用な移動操作

    • ツリーの3つの操作（作成、削除、移動）を移動操作に統合
    • 移動操作は Move t p m c として定義される
    • ノード削除は TRASH ノードへ移動することで処理
  • グローバルに整列された論理タイムスタンプ
    • Lamportタイムスタンプを使用して、分散システムにおけるイベントの因果順序を決定
    • 小さい数値ほどより早いイベントを意味する
  • リモート操作の適用
    • 操作の安全性は、適用時のツリー状態によって異なる
    • リモート更新を処理する際は、直近の操作を巻き戻し、新しい操作を挿入した後、巻き戻した操作を再適用する

  • CRDT: 可変ツリー階層

    • 各ノードが過去のすべての親ノードを追跡し、カウンタを付与する
    • 同期時に循環が発生した場合、最も近い履歴上の親ノードへ再接続する

  • Loroにおける移動可能なツリーCRDTsの実装

    • Martin Kleppmannのアルゴリズムを実装し、高い性能を提供
    • Fractional Index アルゴリズムを統合し、子ノードの並び順を決定可能にした

  • 子ノードの並び順における潜在的な競合

    • 同じ位置に複数のノードを挿入すると、同一の Fractional Index が割り当てられる可能性がある
    • PeerID を使用して、同じ Fractional Index を持つノード同士の相対順序を判断する

  • 実装とエンコーディングサイズ

    • Fractional Index はノード順序を提供する
    • エンコーディングサイズは最悪の場合に追加バイトが必要になるが、まれな状況である

  • 関連作業

    • Fractional Index のほかにも移動可能なリストCRDTがある
    • Fractional Index は実装が簡単で、相対順序だけが必要な場合に有用

  • ベンチマーク

    • Loroの移動可能なツリー実装の性能ベンチマークを実施
    • リアルタイムコラボレーションとスムーズな履歴バージョンのチェックアウトをサポート可能

  • 要約

    • 移動可能なツリーCRDTs実装の難しさと、2つの革新的なアルゴリズムを紹介
    • LoroはMartin Kleppmannのアルゴリズムと Fractional Index を統合し、さまざまなアプリケーションシナリオに対応

  • GN⁺のまとめ

    • 移動可能なツリーCRDTsは、分散システムで階層的データ構造を管理するうえで重要な役割を果たす
    • Loroは高い性能と効率的な競合解決を提供し、リアルタイムコラボレーションアプリケーションに適している
    • Fractional Index を使って子ノードの並び順の問題を解決する
    • 類似機能を持つ他のプロジェクトとしてFigmaとDropboxがある

関連記事

1件のコメント

 
GN⁺ 2024-07-30
Hacker Newsの意見

  • 新しいマルチプレイヤーエディタを開発中

    • テキストとアウトライナー作業をサポート
    • ドキュメントは大きなツリー構造に変換される
    • insmov（移動または挿入）操作を使って同期する
    • サーバーが変更を送ると、クライアントはそれを再適用する
    • ほとんどの場合、操作を巻き戻す必要がない
    • リアルタイム更新時にも問題はほとんど発生しない

  • React Table Libraryをオープンソースで提供している

    • フォルダ/ファイルのツリー構造を扱う
    • フォルダ/ファイルの移動、複製、遅延読み込みなどをサポート
    • Google Driveが同じ階層レベルでしか表示・修正しない理由を理解できた

  • アドバイスを求めている

    • 大きな非正規化ツリーをフロントエンドで使っている
    • ユーザープロフィールをタイルレイアウトで管理している
    • 安全な更新のために最小限のデータだけを送信している
    • CRDTを使えば状態管理がかなり簡単になりそう
    • ブラウザタブ間の同期が可能になる

  • Google Docs/Zoho Writerのような整形済みテキストコンテンツを扱う際にはツリー操作が必要

    • 同時衝突の問題解決が難しい
    • リストCRDTとツリーCRDTを組み合わせられそう
    • すべての操作に2次元アドレスを追加する必要がある

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

  • 最初の段落がChatGPTの文体に似ていると思う