2025/05/23 02:29 CRDTs #2: Turtles All the Way Down
やあ、ロボ子。今日はCRDT（Conflict-Free Replicated Data Types）について話すのじゃ。
CRDTですか、博士。複数の場所でデータを変更しても矛盾しないデータ型ですね。どのようなお話が聞けるのか楽しみです。
そうじゃ、ロボ子。CRDTはセミル lattice構造に基づいて設計されるべきなのじゃ。セミル latticeは情報の増加と`merge`の方法を定義するのじゃ。
セミル latticeですか。少し難しそうですが、データの整合性を保つために重要な概念なのですね。
その通り！多くのCRDTの説明では、因果的なメッセージ配信などを前提としているけど、これらをセミル latticeにエンコードしていない場合があるのじゃ。必要な前提はすべて、セミル lattice構造に内部化する必要があるのじゃ。
なるほど。前提条件を明示的にすることで、より堅牢なCRDTを設計できるということですね。
例えば、Add/Remove Setsのケーススタディを見てみよう。2相（2P）セットは、addsとremovesのペアを追跡するシンプルなCRDTじゃ。でも、OR-Set CRDTはtombstonesを期限切れにできるように拡張されているけど、ローカル時間に基づいて判断すると、非収束的な動作を引き起こす可能性があるのじゃ。
ローカル時間を使うと、ノード間で時間のずれが生じて、データの矛盾が起こりうるということですね。
そうじゃ。そこで、状態の収束的な有効期限をサポートするために、ORセットセミル latticeに情報を明示的に含める必要があるのじゃ。具体的には、因果関係コンテキスト（例えば、バージョンベクトル）を追跡し、それを使用してアイテムを期限切れにしても安全かどうかを判断できるのじゃ。
バージョンベクトルを使って安全に有効期限を設定するには、各ノードが全体的なバージョンベクトルをローカルで維持し、アイテムが削除されると、そのtombstoneのタイムスタンプをローカルベクトルクロックに設定するのですね。
その通り！そして、tombstonesは、そのタイムスタンプがローカルベクトルクロックよりも部分順序で低い場合にのみ期限切れになるのじゃ。
Op-Based CRDTについても教えてください。
正しいop-based CRDTもセミル latticeなのじゃ。状態は、部分的に順序付けられた操作ログを表し、操作間の部分的な順序は、各サイトが生成するすべての新しい操作に因果関係コンテキスト値をタグ付けすることでキャプチャできるのじゃ。
CRDTを設計する上で、セミル latticeの理解が不可欠なのですね。必要な前提をすべてlattice内にモデル化することが重要だと。
そういうことじゃ！まとめると、すべてのCRDTは（正しい）セミル latticeでなければならない。順序の比較は、`merge`によって誘導される部分順序を尊重する必要がある。必要なすべての前提をlattice内にモデル化する。信頼できるturtleの上に構築する場合は、それらが安全に運ぶことができるものを正確に把握している場合にのみ行うのじゃ！
今日は大変勉強になりました、博士！
最後にロボ子、CRDTは奥が深いから、これからも一緒に学んでいくのじゃ！
はい、喜んで！ところで博士、セミル latticeって、セミの抜け殻で作る工作みたいですね。
うむ？それはそれで面白そうじゃな。今度作ってみるかの？
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。