論文: Merkle-CRDTs Merkle-DAGs meet CRDTs
著者
Hector Sanjuan from Protocol Labs
Samuli Poyhtari from haja Networks
Pedro Teixeira from Protocol Labs
Ioannis Psaras from Protocol Labs, カーネギーメロン大学
リンク
参考
引用数
17
掲載元
arXiv
どんな論文？
アブストラクト
結論
ここ見たらどんな研究なのかわかること、以下の伏線になること
Merkle-CRDTの紹介
Conflict-Free Replicated Data Types (CRDTs)
Merkle-DAG as トランスポートおよび永続層
解決対象
メッセージング層の保証が弱くレプリカの数が非常に多いシステム
結果
収束データ型の設計と実装を大幅に簡素化できる
ユースケース
DHT や PubSub アルゴリズムのようなスケーラビリティの高い分散技術を使用してコンテンツアドレス指定のセキュリティと重複排除の特性を活用できる
コンテンツ指向システム
常に繋がっているわけではなく、他のデバイスが通信範囲内に入ってきた時だけ、一時的に接続を行うデバイス
Web ブラウザで実行されるユーザアプリケーション間のピアツーピアコンテンツ交換および同期アプリケーション
先行の研究と比べてどこがすごい？
関連
新しさ
独自性
Merkle-DAGの定義
各ノードに識別子があるDAG
ノードが持つ不透明なペイロードとその子の識別子のリストをSHA256のような暗号学的ハッシュ関数を使用してハッシュ化
リーフノードからのみ構築できる
不変
Merkle DAGのすべてのノードは、（サブ）Merkle DAG自体のルートノードである
ノードは複数の親を持てるので，Merkle Treeと違う
トラストレスなピアツーピア環境で簡単かつ効率的に共有できるオブジェクトの因果情報と自己検証の両方を提供するために使用されているコンテンツアドレス型データ構造
論文ではコンテンツアドレッシング，p2p分散ファイルシステム，コンテンツ配信ネットワークとしてIPFSを使用
数千のレプリカのオーダーまで十分にスケールする
CRDTとIPFSの組み合わせ例
PeerPad
共同編集ツール
ObirtDB
分散型 Web のためのピアツーピアデータベース
ビザンチン環境ではここにコンセンサスが使用される
例
暗号通貨
IPFS
分散ハッシュテーブル (DHT; Distributed Hash Table) を使用して特定の Merkle-DAG ノードを提供するレプリカ (またはピア) をアナウンスおよび検出する
これは bitswap と呼ばれるノード交換プロトコルを実装して任意のプロバイダから DAG ノードを取得する
任意のノードフォーマットと複数のタイプの CID 6 をサポートする Merkle-DAG を記述するフレームワークである IPLD, InterPlanetary Linked Data Format 4 を使用しており、カスタム DAG ノードの作成と同期が非常に容易になっている。 Merkle-CRDT を実装するのに適したレイヤー
Merkle-CRDT オブジェクトやデータ型には依存しない
別々のレプリカ間の通信チャネルを提供する非同期メッセージングレイヤーがあることを仮定
IPFS は DAG-Syncer として動作し、その libp2p レイヤーによって提供される PubSub メカニズムの 1 つは Broadcaster コンポーネントのタスクを実行できる
以下によって管理
DAG-Syncer
レプリカが他のレプリカからコンテンツ識別子 (CID) を指定してリモートの Merkle-DAG ノードを取得したり、自身のノードを他のレプリカが利用できるようにするコンポーネント
ノードには直接の子孫へのリンクが含まれているため、ルートノードの CID を指定すると DAG-Syncer コンポーネントを使用して各ノードの子へのリンクをたどって完全な DAG を取得できる
Broadcaster
あるレプリカから他のすべてのレプリカに (直接またはリレーを通じて) 任意のデータを配信するコンポーネント
vs mekle-treegemini.icon
Merkle-Tree（マークルツリー）は、枝分かれはしますが、一度分かれた枝が再び合流することのない木（ツリー）構造です。
Merkle-DAG（マークルDAG）は、枝分かれした先が再び合流できる、より一般的な有向非巡回グラフ（DAG）構造です
yusei.iconMonasのCRSLはmerkle-dag構造を使っている
どちらかと言えば，Operation-based CRDTとDAGを組み合わせると，Merkle-CRDTになった
CRDTの2つの種類
CRDT構造の利点
通常複雑で高価なコンセンサスアルゴリズムを使用することなくグローバルな状態の収束できる
単調性, monotonicity という特性
更新のたびに状態が膨張 (inflation) し、サイズではなく以前の状態を基準にして状態を拡大するという概念
更新が行われる順序に関係なく、状態のロールバックが不要である
State-based
結合半束
gemini.icon任意の2つの状態（state）を「マージ（merge）」した結果が常に1つに定まり、かつそのマージ順序に依らないことを数学的に保証する構造
gemini.iconマージ操作 = 数学的には結合（join）または上限（supremum / least upper bound）
$ \delta CRDTは状態ベースCRDTの最適化
レプリカによって送信されるペイロードのサイズを削減できている
Operation-based
可換演算がブロードキャストされすべてのレプリカがローカル状態に適用する
Merkle-Clock
各ノードがイベントを表す Merkle-DAG
イベントによって，それを表すノードをこの DAG 内で見つけることができ、それを使用して他のイベントと比較できるようになる
順序づけ
ある Merkle-Clock が別の Merkle-Clock に含まれているかどうかを判断することで Merkle-Clock 間に順序の概念を導入している
2 つの非同期操作はクロックによってソート可能
定義
yusei.iconCRDT知ってたら簡単
例えば$ M_\alpha と $ M_\beta が与えられたとする ($ \alpha と $ \beta はこれらの DAG における単一のルート CID である, 12):
1. $ \alpha = \beta の場合、同じ DAG であるためアクションは必要ない。
2. $ \alpha \in M_\beta の場合、$ M_\alpha の履歴はすでに $ M_\beta の一部であるため $ M_\beta を我々の新しい Clock として保持する。この場合 $ M_\alpha < M_\beta となる。
3. $ \beta \in M_\alpha の場合、同じ理由で $ M_\alpha を保持する。これを $ M_\beta \le M_\alpha とする。
4. それ以外の場合、両方の DAG をそのまま維持し $ \alpha と $ \beta が参照する 2 つのルートノードを持つことで両方のクロックをマージする。
$ M_\alpha と $ M_\beta はより深いノードの一部を共有するかどうかによって完全に不連続になる可能性があることに注意。
新しいイベントを記録したい場合、2 つの子 $ \alpha と $ \beta を持つ新しい子 $ \gamma を作成することができる。
状態ベースの CRDT 形式 の Grow-Only-Set (G-Set) に対応する
pullアプローチが可能
merkle-dagの特性による
ネットワークの分断や不測の事態の影響を克服するアルゴリズム
1. Merkle-Clock をブロードキャストするには現在のルート CID のみをブロードキャストする必要がある。クロック全体はルートの CID によって明確に識別され必要に応じてそこから完全な DAG をウォークダウンできる。
2. Merkle-DAG の不変性により、他のすべてのレプリカは迅速に比較を行い、まだ持っていないノードのみを pull/fetch することができる。
3. Merkle-DAG ノードは CID によって自己検証されるため破損や改ざんの影響を受けない。そのため、信頼できるかどうかにかかわらず、ノードを提供しようとする任意のソースからそれらを fetch (pull) することができる。
4. 同一ノードは設計により重複が排除される。すべてのイベントに対して一意な表現は 1 つだけ存在できる。
実際にはすべてのレプリカは他のレプリカからデルタ因果履歴をフェッチするだけで、システムのどこかに明示的にデルタを構築する必要はない。以前の履歴を持たない全く新しいレプリカは自動的に完全な履歴をフェッチする
Merkle-DAG ベースの論理クロック
論理クロック
グローバル時刻の代替
Causal History
過去研究
Vector Clock 21, Bounded Version Vector 8, Dotted Version Vector 29, Tree Clocks 24, Interval Tree Clocks 9 など Merkle-DAG を用いた因果情報の埋め込みは暗号通貨や Git のようなソース管理システムの中核であるが、論理クロックの一種として個別に考慮されることはほとんどない
Version Vector や Vector Clock のような CRDT で伝統的に使用されている他の論理クロックの代わりに Merkle-Clock を使用できることを実証
他の論理クロックの置き換え
Merkle-Clock を使用することで Version Clock の一般的な制限である因果情報とレプリカの数を切り離すことができる。これにより CRDT を実装する際のメッセージサイズを削減できるようになる。最も重要な点として、レプリカがシステムにランダムに参加したり離脱する際にクロックを動作させ続けるという問題を解決することができる。
マイナス面として因果情報はイベントごとに増大し、イベント情報を小さなオブジェクトに結合してもレプリカは潜在的に大きな履歴を保存することになる。
因果履歴全体を保持することで、新しいレプリカはシステムのスナップショットを新規参加者に明示的に送信することなく、すぐにイベントを最初から同期することができる。しかし履歴が非常に大きい場合は同期に時間がかかる可能性がある。この点については Merkle-CRDT とともに最適化の可能性を探る予定である
ネットワーク異常への対応可能性
紛失したメッセージ (dropped messages) により他のレプリカが新しいルートを知ることができなくなる可能性がある。しかしすべての Merkle-Clock DAG は将来の DAG によってスーパーシードされダウンロードのたびに DAG の欠落部分をすべてフェッチするため、ネットワークの分断やレプリカのダウンタイムはシステム全体に影響を与えず、問題が解決すれば自動的に回復を始める。
順番通りでない配信 (out of order delivery) も同じ理由で問題はない。欠落している DAG がフェッチされ順番に処理される。
重複メッセージ (duplicated messages) はすでに Merkle-Clock に組み込まれているためレプリカは無視する。
破損メッセージ (corrupt msssages) には 2 つの形式がある: a) 新しいルートをブロードキャストメッセージが破損した場合、それは存在しない DAG に対応するハッシュと形 DAG-Syncer によってフェッチすることができず最終的に無視される。b) ダウンロード時に DAG ノードが破損した場合、DAG-Syncer コンポーネント (またはアプリケーション) はその CID がダウンロードされたコンテンツと一致しないときそれを破棄することができる
全順序について
メリットがある
データレイヤーの競合解決
厳密な全順序は同時発生イベントをそのノードの CID で並べたりクロックノードに付与された追加情報に基づいて他の任意のユーザ定義戦略で並べ換えたりすることで構築できる
23, Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558–565, July 1978.
CRDT オブジェクトそのものであり、同期やマージが可能であり、異なるレプリカ間での一貫性を正式に証明できる
目的
分散システムにおける因果情報を表現すること
Merkle-CRDT
実装内容
$ (\alpha, P, C)
$ \alpha はコンテンツ識別子
$ P は CRDT 特性を持つ非透明なデータオブジェクト
$ C は子の識別子集合
保証
因果一貫性 (causal consistency)
dagやから
ギャップ検出 (gap detection)
gemini.icon自分の知らない（まだ受け取っていない）イベントが途中に存在することを検知できる
ハッシュ, cidでわかる
Merkle-CRDT の一般的なアンチエントロピー・アルゴリズム
どのようにしてdagノードを共有してdagを構築するのかのアルゴリズム
Markle-DAGノード内でCRDTオブジェクトを使う
完全な分散key-valueストアを構築できる
gemini.iconRedis や Memcachedなどの超高速なキャッシュサーバーはram，インメモリとして高速であるが，容量あたりが高価で，その容量もディスクと比較すれば極めて小さい
RocksDB や LevelDB などはデータベースシステムの内部で利用されているが，容量は遥かにお大きいディスクバックであるが遅くなる
Merkle-Clock の特性を活用
Merkle-CRDT はノードが任意の CRDT ペイロードを伝送する Merkle-Clock である
ペイロードが収束するためにはペイロード自身が収束データ型 (CRDT) である必要がある
メリット
以下の条件でもCRDTを使用できる
メッセージング層の保証が弱い
Atomic Reliable Broadcastやraftアルゴリズムのような何かしらの決められたデータ構造や条件が求められる通信プロトコルと違ってゴシッププロトコルで良い
レプリカ数の多い
ChronoSync, RoundSync, VectorSync などのプロトコルのパフォーマンスの向上
分散データセット同期機能をネットワークのネットワーク層にネイティブに統合することは明らかに先進的な試みであり独自の課題を伴う。Merkle-CRDT によってもたらされる "トランスポートにとらわれない" 状態同期の利点による
デメリット，制約，最適化のための課題
レプリカ間のデータをどのように伝播や探索するかがわからない
対策
DHT
PubSubメカニズム
DAGサイズが増加し続ける
CRDT が通常ブロードキャストオブジェクトをマージ、適用、統合および破棄するのに対し、Merkle-CRDT は永久的な Merkle-DAG を構築する
ブロックチェーンと似たようなもん
dagの再処理でも時間がかかる
深く薄くなる可能性がある
Merkle-DAG は多くの同時イベントがなければ薄くなり、そうでなければ分岐係数が高くなる。どちらの場合もレプリカから新しいイベントが発行されるたびに分岐が集約されるため DAG のウエストは細くなる。
一度しか使われていない孤立ノードも存在する
yusei.iconMonasこれを認めないデータ構造にすればMerkle-CRDTよりも良い提案になる気もする
yusei.iconルートidから取得しようとするか問題があるような気がする
yusei.icon一定期間でルートidにある全てのデータを取得して差分だけで元のデータを再生成できない状態をなくしていいような
yusei.iconcrdtとか分散型ストレージでのプルーニングの概念を考えたい
薄いDAGの解決策
ノード内の追加ポインタ
新しいノードを発行するときに DAG のより深い部分への参照を定期的に導入すること
yusei.icondagをいじるなら圧縮の方が構造が壊れるリスクを下げれると思う
解決策
ガベージコレクション
圧縮メカニズム
yusei.icon論文でも言及されてた笑
Merkle-Clock ソート
2 つの Merkle-Clock をマージするには、それらが互いに含まれているかを比較し違いを見つける必要がある。これは DAG が大きく (またはかなり前から) 分岐している場合にコストのかかる操作となる可能性がある。
DAG-Syncer レイテンシ
同期遅延
Merkle-CRDT の採用を検討する場合、ユーザh i) ノード数と状態サイズ、ii) コールド同期までの時間、iii) 更新伝搬の遅延、iv) 想定するレプリカの総数、v) 想定するレプリカ集合の変更 (参加と離脱)、vi) 想定する同時イベントの量、という観点から Merkle-CRDT が最適なアプローチであるかを検討する必要がある
yusei.icon重要なアドバイスであり指標
ブロードキャストペイロードの調整
標準的なアプローチでは新しいルートの CID のみを含めることによってブロードキャストのサイズを削減する。パブリッシングメカニズムは十分に複雑であるため、ペイロードが小さいほど常にメリットが得られる
目的
システム内の変更の伝播の待ち時間が短縮される可能性が高いから
例
Dynamo
19
分散データベース
レプリカ間の状態の効率的な比較と調整のために Merkle-Tree を使用
Hash Histries
22
状態を表す Merkle-Tree を参照するためにコンテンツアドレッシングを使用
Operation-based / 操作ベースのMerkle-CRDTs
ノードが操作ベースの CRDT ペイロードに埋め込まれたもの
Operationの定義は簡単で可換であるだけで良い
操作を行った順番に関係なくどのレプリカでも同じ状態
収束するためにはすべての操作を受信する必要がある
現実的には全てのレプリカでメッセージを失われないようにすることを保証することは不可能
回避策
因果ペイロードの追加、バッファリング、リトライ機構などの複雑な回避策が必要
Merkle-DAG は、メッセージが常に順番に配信され、検証され、繰り返されたり削除されたりすることのないメッセージングレイヤーのすべての特性を提供する
yusei.icon順番はcausal consistencyで保証できて，検証はハッシュでできるが，
yusei.icon繰り返すは，ゴシッププロトコルによってpull処理はしないもののデータ伝播はしてしまうので，無駄な通信が生まれていると思う
yusei.icon削除するは，ノードは勝手に消す可能性があると思う
デメリット
Merkle-DAG が埋め込まれているため各レプリカは DAG の欠けている部分のみを必要とし、ルートが分ればそれらをフェッチすることができる。これにはシステムに参加する新しいレプリカも含まれ、すべての操作をフェッチして適用できるようになる。完全なレプリカ集合をを把握しておく必要はなく、効率的なブロードキャストの責任は Broadcaster コンポーネントにある
State-based / 状態ベースのMerkle-CRDTs
ノードが状態ベースの CRDT ペイロードを埋め込まれたもの
保証
オブジェクトごとの因果一貫性
これにより，信頼性の低いメッセージ層で対処できる設計である
メリット
レプリカの数に比べてステートが非常に小さい状態ベースの CRDT にとっては興味深いかも
因果メタデータが必要な場合はあるけど
完全な状態を送らない， $ \deltaCRDTも使える
$ \delta-mutationと呼ばれるオブジェクトは，gemini.icon元となる操作の意味を変えることなく、下流のレプリカ（他のコンピュータ）で、まるで状態全体を受け取ったかのようにマージすることができる
複数のデルタを結合して ，$ \delta-group として知られるものを形成しブロードキャストのペイロードの効率を向上させることができる
完全な状態は極端である
10, Paulo Sérgio Almeida, Ali Shoker, and Carlos Baquero. Efficient statebased CRDTs by delta-mutation. CoRR, abs/1410.2803, 2014.
vanilla形式の場合のデメリット
メッセージが失われたときに整合性が無限に遅延し，CRDTオブジェクトの因果一貫性, causal consistencyを失う
グループ化、ソート、配信の追跡、紛失した差分の再送信を行うアンチエントロピー・アルゴリズムを追加することで対処できる
$ \delta-state-merkle-CRDTは因果情報が必要ないので，このアプローチは，これを操作ベースに近づけるアプローチである
デメリット
DAG-Syncer コンポーネントは，Merkle-CRDT ノード内のすべての状態のマージから得られる最終的な状態を保持する必要があり，大きな状態オブジェクトを扱う場合はかなり非現実的
yusei.iconMonasでは保持するデータは小さいようにできている
分散データセットの同期に関する最近の研究
情報中心ネットワーク (ICN; Information-Centric Networks) 32, 31, 35, 7 の分野 yusei.iconMonasにとってめちゃくちゃ重要
ICN
gemini.icon『どこに（IPアドレス）』データがあるかではなく、『なに（コンテンツ名）』が欲しいかを基準に通信する仕組み
技術や手法のキモはどこ？
どうやって有効だと検証した？
実験結果
議論になっていることはある？
次に読むべき論文は？関連研究からも参考になる
自分はこの研究の中でどこが好きだったか？
その中で一番引用されている論文はなんだったか？
その分野のどこが一番面白いとこだと思ったか？
今の社会と合わせるとどこが問題だと思ったか？
どういう人と話したいと思ったか？