Merkle-CRDTs Merkle-DAGs meet CRDTs
日本語もあったらしい
mameta.iconに教えてもらった
分散システムで最終的な一貫性を得るためのアプローチとしてCRDTがある 状態ベースのCRDT
レプリカの状態が結合セミラティスを形成し、マージされる
演算ベースのCRDT
可換演算がブロードキャストされ、全てのレプリカによってローカル状態に適用される
関連技術:
分散システムの一貫性モデルの1つで、全てのレプリカが最終的に一致する状態に達することを保証するが、一致するまでの時間や状態の違いについては明確な保証がない: 状態がいつ一致するのか、状態がどれだけ異なることが許されるかの保証がない
追加の安全保障を提供する= 2つのレプリカが同じ更新を受け取った場合、その状態は同じになるという保証
この実装を行うためにCRDTがあるらしいYudai.icon 各ノードが識別子を持ち、識別子はノードの内容をSHA256のようなハッシュ関数を使用してハッシュ化することで得られる
Leafからの構築
Leaf(子を持たないノード)から構築される。子ノードが先に存在し、その識別子が計算された後に親ノードが追加される
自己含有的なサブグラフ
不変性
ノードに変更を加えると識別子が変わり、DAG全体が変更される
分散システムにおいて異なるレプリカ間で発生したイベントの因果関係を追跡し、状態の発散を調整するために使用される
単調性: 全ての更新が状態を膨張させるという概念で、状態のサイズが増えるのではなく、以前の状態に対して成長させる => 状態間には常に順序が存在する
言わんことはわからなくはないけどいまいち理解していないYudai.icon*2
「成長」ってのは過程があり、つまり順序があるって考えろ！ってことが言いたいだけ？
一方向にしか進まないことを保証するらしいYudai.icon
主要なタイプ
状態事態には特性を課せず、変更を行う操作に特性を課する
いまいち分かっていないYudai.icon
chatGPT.iconコンフリクトが起きた場合、
同じデータに対する異なる更新：例えば、二人のユーザーが同時に異なる場所から同じ文書の同じ部分を編集する場合、各操作はそれぞれのユーザーによる変更を反映します。操作が可換であれば、これらの編集をどの順序で適用しても、最終的には同じ結果が得られます。
要素の追加と削除：あるレプリカがリストに要素を追加する操作と、別のレプリカがそのリストから別の要素を削除する操作が同時に行われた場合、これらの操作は独立しており、適用の順序は最終的なリストの内容に影響しません。
これだとどちらが順序的に先かを定義づける必要がある気がするんだよねYudai.iconYudai.icon
例について下にもある
ICN: ネットワーク層で直接コンテンツ名を命名し、名前に基づいてルーティングと転送を行うアーキテクチャ
データの名前を直接ネットワーク層で扱うことに焦点を当てており、異なるデータセット間での状態同期を行う
同時発行を部分的に解決している。同期プロセスをラウンドに分割することで同時に発生する更新をより効率的に扱うことが可能
バージョンベクターを使用してPeer間の同期をより効率的に行う
レプリカが他のレプリカからMerkle DAGノードを取得し、自身のノードを他のレプリカに提供する機能を持つコンポーネント。 各ノードはその直接の子孫へのリンクを含んでおり、ルートノードのCIDから初めて、DAG-Syncerを使用して各ノードの子リンクを辿りながら完全なDAGをフェッチする 定義:
Get(CID): Node
指定されたCIDに関連づけられたノードを取得する
Put(Node):
新しいノードまたは更新されたノードをDAGに追加する
あるレプリカから他の全てのレプリカに任意のデータを配布するためのコンポーネント
定義:
Broadcast(Data)
各ノードがシステム内のイベントを表すMerkle DAGで、システム内の任意のイベントに対して、表すDAG内のノードを見つけることができ、他のイベントと比較することができる ex)
$ \alpha = \beta: 同じDAGを意味する
$ \alpha \in M\betaの場合: すでに$ M\alphaの履歴が$ M\betaに含まれているから、$ M\betaを保持する。 = $ M\alpha <M\betaと言える
$ \beta \in M\alphaの場合: 同じ理由で$ M\alphaを保持する。 = $ M\beta < M\alpha
それ以外の場合: 両方のClockをそのまま保持し、2つのルートノードを持つように両方のClockをマージする。新しいイベントを記録したい場合2つの子ノード$ \alphaと$ \betaを持つ新しいルート$ \gammaを作成できる
マージ:
マージすることで作成されたMerkle Clockは常に両方のMerkle Clockの因果関係を含む = 同じMerkle Clockに収束する
Merkle Clockの定義
Merkle-Clock node $ Naはトリプルである= $ a, ea, Ca
eaはイベント, aは nodeCIDで, Caはnaの直接の子孫のCID集合,
Merkle-Clockはペアである: $ (N, \le)
部分順序は,
$ n_{\alpha}, n_{\beta} \in \mathbb{N}: n_{\alpha} < n_{\beta} \Leftrightarrow n_{\alpha} is a descendant of $ n_{\beta}
維持するために下記のようになる
既存のMerkle-Clock DAGの新しいノードとして実現されなければならない
Merkle-clock Mはイベント$ e_{\alpha}\in Sが与えられた時にMerkle-Clock DAG Nからノードを返す関数 => $ M: S\rightarrow N
Merkle-clockはCRDTの一種として機能し、データの収束を保証する
Merkle-Clockの集合は結合半格子として構成される 任意の2つのMerkle-Clock DAGが集合の要素かんで部分順序を形成する
=> 異なるレプリカが独立して更新を行なっても時間と共に一貫性が保たれる
同期メカニズム
プル方式の採用
ルートCIDのブロードキャスト
ルートCIDのみをブロードキャストする。必要に応じてDAGを辿る
イミュータブルな性質
もっちないノードのみをプルする
自己検証機能
信頼されたソースからではなくても、任意のソースからノードを安全にプルできる
重複の排除
同一のイベントは設計により、一意の表現を持った上で重複が排除される
ペイロードを持つMerkle CRDT
ペイロードが収束するためにはペイロード自身が収束データである必要がある => ($ \alpha, P, C)
$ \alpha: CIDでノードを一意に識別する
P: 不透明なデータオブジェクトでCRDTの特性を持つ
C: 子ノードの識別子の集合で、ノード間のリンクと階層関係を形成する
操作の失われない保証:
順序通りに適用されることを保証する. CRDTとMerkle DAGの不変性が組み合わさって達成される
ギャップの検出と補完:
CRDTペイロードの処理を容易にするため, シンプルで一般的なアンチエントロピーアルゴリズムが導入される
How?手順
新しいペイローの発行
レプリカRBは新しいDAGノード($ \beta, P,{\theta})を作成する.新しいルートとして自身のMerkle-CRDTに追加する -> $ M_{\beta}
ブロードキャスト
RBは新しいルート$ \betaをシステム内の他のレプリカにブロードキャストする
受信とデータの取得
レプリカRAは$ \betaのブロードキャストを受信し、ルート$ \betaから初めてDAGをたどりながら, 自身の$ M_{\alpha}にない全てのノードを取得する -> CID-Set D
データの確認
Dが空であれば, RAは$ M_{\beta}の全てのペイロードをすでに処理していることを表す
CIDの整理
Dが空で無い場合, CIDをMerkle-Clockによって提供された順序でソートする
ペイロードの処理
Dに含まれるCIDに対応するノードのペイロードを最も低いものから順に処理する
データの統合
もし$ \alphaがDに含まれていない場合, $ M_{\alpha}\not\subset M_{\beta}かつ$ M_{\beta}\not\subset M_{\alpha}である.RAは両方のノードをルートとして保持する
あれ？両方持っているならマージできていないやんYudai.icon
結局何かしらが必要説.......????
Operation-based Merkle-CRDTs
メッセージの配信保証
操作の状態が収束するためには全ての操作が確実に受け取らなければならない
信頼性のあるメッセージングlayerが必要だけど、レプリカの数が多い場合、失われる可能性がある
これ少なければいけるのでは？(仮説)Yudai.icon
State-based Merkle-CRDTs
各ノードが完全な状態情報を含むCRDTペイロードを埋め込む
課題
大きな状態オブジェクトを取り扱う際に問題が生じる. DAG-Syncerコンポーネントがこれらの状態を保村する必要があり、非効率
限界と最適化
限界:
増加し続けるDAGサイズ
永久的にMerkle-DAGを構築する
サイズは許容範囲を超えて大きくなる可能性がある
ブロックチェーンに似ている
初期同期の遅延
新しいレプリカが大きなMerkle DAGから始める場合、ローカルで利用可能であっても全DAGを再処理する必要がある
Merkle-Clockのソーティングコスト
違いを見つける必要があるが、大規模な変更や時間が経過しているとコストがかかる
DAG Syncerの遅延
ノードの取得とメッセージングレイヤーへの提供を依頼する
最適:
遅延DAGノード
複数のペイロードをまとめてから単一のノードを発行することで更新の頻度を減らす
高速なMerkle-DAG含有チェック
ローカルDAGとリモートDAGをマージする際に、一方のDAGが他方に含まれているかどうかを効率的に確認をするためにキーバリューストアを使用する
ブロードキャストペイロードの調整
新しいルートのCIDのみを含むことでペイロードサイズを削除する
Merkle-DAGノードサイズの削除
ペイロードの圧縮や冗長な情報の削除により、ノードのサイズをできるだけ小さくする
ノード内の追加ポインター
新しいノードを発行する際に、DAGのより深い部分への参照を定期的に追加することで、データの取得を並列化し、トラバーサル高速化する
メモ:
Monotonic Join-Semilattice:
単調結合半束（Monotonic Join-Semilattice）
単調結合半束は、集合の理論において、要素間に一定の順序関係が定義されているデータ構造です。この構造では、任意の二つの要素に対して、それらを結合（マージ）する操作が定義されており、その結果として得られる要素も同じ集合内に存在します。この結合操作は以下の三つの特性を持ちます。chatGPT.icon
たとえば、レプリカAが状態Xを、レプリカBが状態Yを持っているとします。XとYが異なる場合、X ⊔ Yの操作によって、XとYの両方の情報を含む新しい状態が生成されます。この新しい状態は、XとYのどちらか一方だけではなく、両方の状態から派生した情報を反映しています。
これはわかりやすいね、$ X\cup Yを合わせる(マージ)するだけだから
で、最善な状態(LUB)をどのように求めるのかをプロトコル側が設定する必要があるYudai.icon*3
多分理解した
可変性の例
カウンターのインクリメント/デクリメント: カウンターCRDTでのインクリメントとデクリメントは、それぞれの操作が加算や減算として独立しているため、適用の順序に関わらず最終的なカウンターの値は同じになります。例えば、カウンターが0から始まり、一つのレプリカが+1、もう一つのレプリカが-1を適用した場合、これらをどの順序で適用しても結果は0になります。
集合の要素の追加と削除: 要素の追加と削除を扱うCRDTでは、要素の追加操作と削除操作が互いに独立しており、それぞれの操作が一意の識別子を持つ場合、これらの操作の順序を入れ替えても、最終的には同じ集合の状態になります。ただし、同じ要素に対する追加と削除が競合する場合、CRDTの設計次第で最終的な結果が異なることもあります（例: どちらかが優先される）。
これ一つ目はわかりやすい例で、後者が言いたいことやねYudai.icon
そこはお前らで定義づけろってことなんだろうね
リアルタイム同期の課題
操作ベースのCRDTでの編集のような複雑な操作を扱う場合、たとえばテキストドキュメントの同時編集など、実際には「どの順序で適用しても同じ結果」というわけにはいかないことがあります。このような場合、CRDTは操作を特定の方法で「解釈」または「統合」するためのルールを定義することで一貫性を保証します。たとえば、同じ位置の文字の同時挿入に対して、一意の識別子やタイムスタンプを用いてどちらかの操作を優先させるなどです。
まさしくこれYudai.icon*2
想定しうるオートでできない場合を書き足すことで、プロトコル側で決定するようにする必要がある
ちなみに勝手に思ったんだけど、そここそブロックチェーンの役割じゃね？？Yudai.icon