この規模でCRDTベースのコラボレーティブシステムを設計するためには、操作を直列化するために中央の権威を必要とする従来のオペレーショントランスフォーメーション（OT）モデルを放棄する必要があります。これらの古典的アプローチは、衝突解決のために調整サーバーへの常時接続を要求するため、本質的に真のオフラインファースト機能を妨げます。代わりに、調整や合意プロトコルなしで収束を保証するために、可換性、結合性、冪等性の数学的特性を活用する状態ベースのCRDT（具体的には、列データ用の複製可能な成長配列（RGA））を実装します。
デルタ状態アンチエントロピープロトコルを展開し、クライアントが完全な状態スナップショットではなく、ローカル状態間の違いのみを交換します。このアプローチは、ナイーブな状態ベースの複製と比較して、同期中の帯域幅消費を桁違いに減少させます。物理的なタイムスタンプと論理的カウンタを組み合わせたハイブリッド論理クロック（HLC）を利用して、因果関係を確立し、厳密なNTP依存なしに地域間のクロックスキューを処理します。最後に、削除マーカーからの非制限のメモリ成長を防ぎつつ、遅延またはパーティションされたレプリカの因果関係トラッキングを維持するために、エポックベースのプルーニングを使用したトンボーンガベージコレクションを実装します。
私たちのチームは、50,000の企業チームをサポートするFigmaのようなデザインツールのリアルタイムコラボレーションエンジンを再構築するよう依頼されました。レガシーシステムは、中央のNode.jsサーバーを通じてRedisのpub/subとWebSocket接続を利用していましたが、業界会議中に10,000人以上のユーザーがオフライン編集を試みると、サーバーは崩壊しました。この急増は、不可逆的な状態の分岐と文書の永久的な破損を引き起こし、48時間のダウンタイムと大規模な顧客離れをもたらしました。
私たちはまず、オフラインで編集する前に、ユーザーが文書セクションに独占ロックを取得する必要がある集中型OTとリースロックを評価しました。このソリューションは、従来のデータベースに類似した強い一貫性と無熟のACIDセマンティクスを約束しました。しかし、それはロック更新には常時接続を必要とし、オフラインファーストの要件を完全に無視し、ロックサーバーにおける壊滅的な単一障害点を生み出し、ネットワーク分断中に製品全体が使用不能となることがありました。
次に提案された候補ソリューションは、衝突を決定論的に解決するためにAWS DynamoDBのタイムスタンプを利用した最終書き込み勝ち（LWW）とベクタクロックでした。このアプローチは真のオフライン編集をサポートし、既存のクラウドインフラストラクチャで実装するのは簡単でしたが、同時編集中に壊滅的なデータ損失をもたらしました。2人のデザイナーがオフラインで同時に同じコンポーネントを移動させると、最後の同期のタイムスタンプだけが生き残り、一方のユーザーの作業が完全に警告なしに破棄されてしまいました。
私たちは最終的に、Yjsライブラリを使用した状態ベースのCRDTを選択し、QUICプロトコル経由で送信されたカスタムデルタ状態同期を実装しました。このアーキテクチャの選択は、編集中の中央調整の必要性を排除し、ネットワークパーティションの持続時間に関わらず収束の数学的保証を可能にし、インターネット接続がなくても同じLAN上のユーザー間のP2P同期をサポートしました。私たちは、完全な状態転送と比較して94%の同期ペイロードを削減するために、メルクルツリーデルタエンコーディングを実装し、文書履歴の暗号的完全性を維持しています。
6ヶ月の運用トラフィックの後、このシステムは全体の地域に影響を与えた72時間のCloudflareのダウンタイムを成功裏に処理し、ユーザーはオフラインでの編集を続け、再接続時にゼロデータ損失でシームレスにマージされました。文書の読み込み時間は、サーバーの往復を排除することで4.2秒から180ミリ秒に改善されました。インフラストラクチャコストは、調整オーバーヘッドの排除と、強力な中央計算インスタンスの代わりにエッジキャッシングを使用できる能力により、60%削減されました。
ユーザーがコンテンツを削除したとき、CRDTはトンボーンの無制限の成長をどのように処理し、安全に削除されるトリガーは何ですか？
ほとんどの候補者は、削除がメモリから即座に削除できると仮定していますが、CRDTはトンボーンを使用して因果関係を追跡し、遅延したレプリカとのマージ中に削除されたデータが復活しないようにします。このソリューションでは、ベクタークロック比較を使用して因果的安定性検出を実装します。ノードが他のすべてのレプリカが特定のタイムスタンプまでの削除を確認したことを観察すると、トンボーンは安定し、削除の対象となります。あなたは、トンボーンが取り除かれるために設定可能な有効期限を過ぎた後に削除の対象としてマークされ、因果的カットが収束のために遅延レプリカを必要としないことが証明されるまで物理的に削除されるエポックベースのガベージコレクションを展開する必要があります。このメカニズムがなければ、6ヶ月前のオフラインデバイスが再接続時に古いデータを復活させ、ユーザーの恒久的削除およびプライバシー遵守に対する期待を侵害する可能性があります。
状態ベースのCRDTと操作ベースのCRDTの根本的な違いは何ですか？ネットワーク要件に関して、そしてバンド幅制約のあるモバイル環境での選択理由は何ですか？
操作ベースのCRDTは、Apache KafkaやRabbitMQのようなトランスポート層からの一度だけの配信と因果的ブロードキャストの保証を必要とし、メッセージが警告なしに失われたり重複したりする可能性のある信頼性のないモバイルネットワークには不向きです。状態ベースのCRDTはメッセージの重複や任意の遅延に耐えますが、従来は全体の文書状態を送信する必要があり、大きなデザインファイルにとっては経済的に禁止されるものでした。高度なソリューションは、直近の成功した同期以降の変異のみを転送するデルタ状態CRDTを使用し、状態ベースの堅牢性と操作ベースの効率を組み合わせます。モバイル環境では、Bloomフィルタを使用して既に見た更新を再送信しないようにする指数バックオフデルタ同期を実装し、オフラインファーストの機能を維持しつつ、完全な状態同期と比較してモバイルデータ使用量を99%削減します。
2人のユーザーが同じカーソル位置に同時にテキストを挿入したとき、シーケンスCRDTにおける「インターリーヴィングの異常」をどのように防止し、編集を連続したブロックとして表示するのではなく無作為にインターリーブされた文字として表示するのを防ぎますか？
標準のLWWまたは単純なカウンタベースのCRDTは、同時に「hi」と「bye」を同じ位置に挿入すると、意味不明な「hbyeio」になります。この解決策では、ノードIDと論理タイムスタンプに基づいて各文字にグローバリユニーク識別子（GUID）を割り当て、決定論的なタイブレイキングルールを持つ複製可能な成長配列（RGA）またはWootアルゴリズムが必要です。挿入時には、新しい要素を数値インデックスではなく特定の前のIDに付着させ、同時挿入がインターリーブされずに決定論的にマージされる独立したブランチを形成するリンクリスト構造を作成します。また、通常、20%未満のメタデータオーバーヘッドでテキスト文書の意図を保持する直感的なマージセマンティクスを維持しながら、GUIDオーバーヘッドが文書サイズを支配しないようにランレングスエンコーディングの最適化も実装する必要があります。