Merkle-Tree

論文翻訳: Merkle Search Trees: Efficient State-Based CRDTs in Open Networks

Takami Torao 2009年の論文 #MerkleSearchTree #MerkleTree #MST
  • このエントリーをはてなブックマークに追加

ABSTRACT

最近の CRDT 技術の多くは、操作デルタの配信を保証するために因果ブロードキャストプリミティブ (caucal broadcast primitive) に依存している。しかしながら、このようなプリミティブは、メンバーシップの追跡が困難な大規模オープンネットワークでは効率的に実装することが困難である。代替案としてこの論文では、状態を特殊なマークル木としてエンコードすることで、ジュンスない状態ベースの CRDT を効率的に実装できること、および、このアプローチが多くのノードが参加/離脱する可能性のあるオープンネットワークに適していることを主張する。我々の貢献の核心は、キー順序を維持しながら並行検索木を実装する新しい種類のマークル木であるマークル検索木 (MST; Merkle Search Tree) である。この後者の特性により、多くのアプリケーションで一般的に発生する、連続したキーの集合に対する更新の場合に特に効率的となる。我々はこの新しいデータ構造を使用して分散イベントストアを実装し、更新頻度の低い非常に大規模なシステムでその効率性を示す。特に、いくつかのシナリオにおいて我々のアプローチはベクタークロックアプローチと比較して帯域幅コストを 66% 削減し、一貫性レベルを 34% 向上させることを示している。最後に、オープンネットワーク上の分散データベースにおける我々の構成の他の用途を提案する。

索引用語 ─ マークル木、検索木、CRDT、IoT、地理分散システム、ピアツーピア、アンチエントロピー

Table of Contents

  1. ABSTRACT
  2. I. 導入
  3. II. 文脈と関連研究
    1. A. CRDT と CAP 定理
    2. B. ゴシップアルゴリズム
    3. C. ハッシュ関数とマークル木
    4. D. B 木
    5. E. その他の最新手法とその限界
  4. III. マークル検索木データ構造
    1. A. MST 構成
    2. B. MST の単一性と演算
    3. C. 構造的特性: 平衡と深さ
    4. D. データセット比較の効率性
    5. E. CRDT としてのマークル検索木
  5. IV. 大規模オープンネットワークにおける CRDT
    1. A. 状態ベース CRDT のゴシップベース調整
    2. B. マークル検索木を使用した大規模 CRDT の実装
    3. C. 因果一貫性
    4. D. A Note on Crashes
    5. E. Extension to Distributed MSTs
  6. V. APPLICATION: A CAUSALLY-CONSISTENT DISTRIBUTED EVENT STORE
    1. A. Scuttlebutt anti-entropy
    2. B. Merkle Search Tree anti-entropy
  7. VI. EXPERIMENTAL EVALUATION
    1. A. Methodology
    2. B. A Metric for Event Dissemination
    3. C. Results
  8. VII. CONCLUSION AND OUTLOOK
    1. A. Adaptive Algorithms
    2. B. Merkle DAGs as Persistent Data Structures
    3. C. Other Applications of Merkle Search Trees
  9. ACKNOWLEDGEMENTS
  10. References
  11. 翻訳抄

I. 導入

大規模地理分散システム [1][2] の登場により、一貫性とスケーラビリティを両立したデータレプリケーション技術への関心が高まっている。中でも競合フリー複製データ型 (CRDT; Conflict-free Replicated Data Types) [3] は、開発者に自然でモジュール化されたプログラミングパラダイスを提供しながら結果整合性を実現する能力において際立っている。

CRDT は並行操作を事後的に結合できる解決ルールを提供することで、同期処理なしに複製が並行して操作を実行することを可能にする。このため CRDT は結果整合性を備えた弱い一貫性システムを構築するために使用できる。

最近の CRDT 技術は主に因果ブロードキャストプリミティブとベクタークロックを活用することで、操作デルタの信頼性のある因果配信を保証することに重点を置いており [4][5]、これにより二つの完全な状態を直接比較する必要がない。しかし、これらのアプローチは多くのノードが参加・離脱するオープンネットワークでは限界がある。これは因果ブロードキャストプリミティブとベクタークロックはどちらもそのような状況には適していないためである。最近になってようやく因果ブロードキャストがスケーラブルな形で動的構造を持つネットワークに拡張されたが [6]、このアプローチの実用性はまだ実証されていない。一方、ベクタークロックはネットワークに参加した過去および現在のノードの数に比例して増加するメタデータを必要とし、これは大規模な最適化を行った場合でも重要なスケーラビリティ障壁となる [7]。

これらの制限を回避しながらオープンネットワークを対象とするために、この論文では因果ブロードキャストもベクタークロックも必要としない純粋な状態ベース CRDT に焦点を当て、この根本的な問題である「事前の相互作用がなく互いの状態について何も知らない可能性のあるノード間での大規模な状態のリモート状態マージを実装する方法」に焦点を当てる。この問題はアンチエントロピーと類似しており、CRDT を形式化する以前に研究されていた。以下ではアンチエントロピー、状態マージ、状態調整という用語を同じ意味として使用する。より具体的には、我々は他の CRDT セマンティクスと組み合わせることができる 2 つの基本的な構成要素である集合またはマップを実装する CRDT を対象とし、2 つの非常に大規模な集合またはマップ間の差異を低レイテンシーかつ最小限の帯域幅使用で解決することを目指す。

集合とマップの調整のための一般的な戦略は、集合間の差異を迅速に識別するために使用できるハッシュベースのデータ構造であるマークル木 [8] を使用する [9]。しかし、マークル木を使用する通常のアンチエントロピーアルゴリズムは要素の順序を保持しないため、近接する項目の連続に更新を適用する場合に特に非効率となる。これは非常に一般的なシナリオであり、基本的な例としては要素がタイムスタンプによって順序付けられたイベントである場合が挙げられる。

この論文では、項目の集合から決定論的に平衡検索木を構築し、それをマークル木として符号化するマークル検索木 (Merkle Search Tree) と呼ぶ新しいデータ構造を用いることでこの根本的な課題を克服することを提案する。我々は、マークル探索木を使用してすべての接続されたノードに過去のすべてのイベントの最終的な配信を保証する因果一貫性のあるイベントストアを構築する方法を実証する。我々はこの手法をベクタークロックベースのアプローチ [10] および順序を保持しないマークル木構成と比較し、大規模ネットワークにおいて低から中程度の更新率の下でマークル検索木が最良のトレードオフを提供することを示す。我々のシミュレーションでは、ベクタークロックアプローチと比較して帯域幅使用量が 66% 削減され、一貫性測定では 34% の改善、99 パーセンタイルの配信遅延では 32% の改善が示された。順序を持たないマークル木と比較した場合、マークル検索木は 3 つの指標すべてにおいてより優れていることが示された。

我々の研究は、このセクションで紹介する分散システム、データベース、ファイルシステムなどのよく研究されているドメインに基づいている。

A. CRDT と CAP 定理

CRDT [3] は結果整合性アルゴリズムを定式化できる汎用的なフレームワークである。CAP 定理 [11] [12] は、分散システムが強い一貫性、可用性、ネットワーク分断耐性の 3 つの特性のうち 2 つしか達成できないことを述べている。CRDT ベースのシステムは通常、複製が一時的に分岐することを許容することで、強い一貫性より可用性を重視する。システムが使用する特定の CRDT は、信頼性のある通信が可能になり次第、分岐状態にある複製が自動的に一意の共有状態に調整する方法を定義する。

この論文では CRDT を複製状態における結合半順序集合 (join-semilattice) として定式化する。すなはち、CRDT は対象結合演算子 \(\sqcup\) を持つ可能な状態の集合 \(\mathbb{V}\) である。状態 \(x \in \mathbb{V}\) に対する操作は \(\sqcup\) にしたがって \(x\) を厳密に上位の状態 \(x'\) に変更することあり、つまり \(x'=x \sqcup o\) となるような項目 \(o \in \mathbb{V}\) が存在する状態である。たとえば、実装したいデータ型が成長専用集合である場合、\(\mathbb{V}\) は可能な集合の空間であり、\(\sqcup\) は和集合演算子である。集合 \(x\) に要素 \(e\) を追加することは \(x\) を状態 \(x' = x \cup \{e\}\) に変更することである。

演算子 \(\sqcup\) はまた、異なるノードで実行された並行操作を結合し、それらを決定論的に解決するためにも使用される。あるノードが状態 \(x_1\) にあり、別のノードが状態 \(x_2\) にある場合、両方のノードの状態は \(x_1 \sqcup x_2\) (これは \(x_2 \sqcup x_1\) と同じ) に解決される。例えば成長専用集合 CRDT の場合、マージ操作は集合の和集合として定義され、結果の状態はすべてのノードで追加されたすべての項目を含む集合として定義される。より複雑な CRDT を定義することで削除や異なるデータ型 (マップやカウンターなど) などの追加操作を実装できる。必要な要件は可換、結合、冪等な結合演算子 \(\sqcup\) を実装することだけである。

この研究では集合 CRDT とマップ CRDT に焦点を当て、\(x_1\) と \(x_2\) が異なる 2 つのノードにある場合の \(x_1 \sqcup x_2\) の効率的な計算を実装する方法を考察する。ここで効率とはネットワークラウンドトリップ数と帯域幅の使用量で測定される。

B. ゴシップアルゴリズム

アンチエントロピープロトコルは一般的に伝染型調整戦略 (epidemic reconciliation strategy) を採用している。これは、分散システムのノードが合意された状態に収束するためにランダムに選択された他のノードと繰り返し差異を調整する戦略である [13]。我々はこの戦略を採用して CRDT を実装し、ゴシップアルゴリズムを CRDT 状態マージ演算子と組み合わせてすべてのノードでの最新の最終配信を保証する。ゴシップアルゴリズム [13] は大規模分散システムにおけるデータ配信の効率的なスキームであり、ランダムピアサンプリング [14] と組み合わせて使用するとオープンネットワークに適している。ゴシップアルゴリズムはよく研究された配信特性を持ち [15] 分散コンピューティングの基盤として広く利用されている [16]。

C. ハッシュ関数とマークル木

ハッシュ関数とそれが生成するチェックサムはデータの識別や完全性・真正性の検証に広く用いられている。そのため、異なるコンピュータ上に存在するデータを比較し、効率的な分散調整メカニズムの実装に役立つ自然な選択のように思われる。しかし非常に大きなデータ編を検証するには、データ全体に対してハッシュ関数を計算する必要があり、これは典型的な Key-Value データストアのような大規模な分散オブジェクトを扱う場合には特にコストのかかる提案である。このコストを削減するため、データをチャンクに分割し、各チャンクを個別にハッシュする方法があるが、その場合、単一のハッシュがデータサイズに比例して増加するハッシュのリストに置き換えられることになるため、依然として問題は残る。

この線形コストを克服するため Merkle [8] はデータをチャンクに分割し、ハッシュツリーを計算することで大規模なデータをハッシュ化する手法を方法を導入した。ハッシュツリーにおいて、葉はデータチャンクのハッシュ、中間ノードはそれぞれの子ノードの値の連結のハッシュである。単一のルートハッシュですべてのデータを識別することができ、1 つのブロックの妥当性は対応する葉への経路をたどることで確認できる。木が適切に平衡していれば、対数個のハッシュのみを検証すれば良い。この検証はデータ全体にアクセスすることなく実行することも可能である。

元のマークル木は二分木だが、マークル木の核となる原理は一般化され他の文脈にも適用できる。特に ZFS [17] や IPFS [18] などのプロジェクトはファイルシステム全体の真正性と完全性を保証するためにマークル木のような再帰ハッシュを利用している。このようなデータ構造の再帰ハッシュによりデータの重複排除も可能にする [17][18]。この場合、マークル木はノードが複数の親を持つ DAG となる。

分散システムにおいてマークル木は特に有用であることが示されている。データセットをマークル木に符号化する決定論的な方法が与えられれば、2 つのノードはルートハッシュを交換して比較するだけで同じバージョンのデータを持っているかどうかを判断できる。バージョンが異なる場合、同じ内容を表す枝は両方のノードで同じハッシュを持つため、データセットの異なる部分のみを交換できる。

マークル木には様々な形状がある。標準的な二分マークル木は番号付きのデータブロックの列を識別・交換するために使用できるが、2 つのノードに存在するキーセットが異なる場合、任意のキー空間で効率的に差異を検出することができない。Dynamo [9] などのデータベースシステムは任意の Key-Value のマッピングからなる状態を交換・修復するためにマークル木を使用するが、木が適切に平衡することを保証するためにキーの順序を破壊し、キーをハッシュ化して一様分布に投影する必要がある。これにより、近接するキーのシーケンスが更新されるシナリオではこの方法は最適ではない。任意のキー範囲で平衡を保ちながらキー順序を保持するマークル木構造は [19] で導入されたが、この方法は決定論的ではない。同じデータセットで複数のマークル木表現が存在する可能性があり、これはアンチエントロピーには適さない。任意のキー範囲でキー順序を保持する最初の決定論的平衡マークル木の構築は二分トリープ (binary treap) [20] を使用して導入された。我々が提案する構成は、より広い木ノードで同じ性質を実現し、より浅い木を作成してリモート差分計算に必要なラウンドトリップ数を削減する。これにより、二分マークル木と比較して計算・保存する必要のあるハッシュ数も削減される。

D. B 木

我々が提案するマークル検索木は、いくつか重要な違いはあるものの、B 木 [21] に類似した構造を用いる。B 木は関連データベース管理システム (RDBMS) で使用される索引データ構造である。B 木は大きな出次数を持つノードによって浅い検索木を実装し、標準的な二分検索木よりも高速な探索を可能にする。ノードは通常、木ノードの機械表現がメモリページのサイズとなるような出次数を持つ。B 木において、ノードはキー空間の分割方法を定義する値の集合と、分割の各区間の値を含む部分木へのポインタの集合で構成される。我々が導入するマークル検索木にも子ノードのキー空間を分割する役割を果たす値を含む中間ノードを含んでいる。しかし、これらの中間ノードは一定のサイズを持たず、そのサイズは確率的のみの制限される。

E. その他の最新手法とその限界

マークル木に基づかないリモートデータ集合比較のための他の手法も提案されている。特に、集合差分を計算するための数学的手法は十分に研究されているが、ブルームフィルタ [22][23] を用いた近似的な差異検出に限定されていたり、データセット全体に対して高コストな計算を必要とするなど制約が厳しいものであったりする [24]。実際には、典型的なアンチエントロピープロトコルは 2 つのノード間の更新の欠落を識別を検出するためにベクタークロック [25] を用いている [10] が、DottedDB [7] で使用されるような大規模な最適化を施したとしても、ベクタークロックは過去および現在の参加者の総数に比例するメタデータを必要とせずにデータセットの 2 つのバージョン間の分岐を特定することができない。

III. マークル検索木データ構造

大規模なマップや集合を実装する CRDT の効率的な照合手順を実装するため、我々はマークル検索木 (MST と表記) と呼ぶ木構造を提案する。これは、我々の知る限り以下の 3 つの特徴を組み合わせた初めての木構造である:

  • 与えられた項目の集合は、木として一意の決定論的表現を持つ。

  • キーの順序が保持される。

  • 木は常に (確率的に) 平衡している。

これらの特性の組み合わせにより、アンチエントロピーのためのリモート木比較が極めて効率的となる。

A. MST 構成

マークル検索木は全順序空間 \(\mathbb{K}\) から抽出した要素による順序集合を実装する。マップを実装するために、要素は集合 \(\mathbb{V}\) (値; この場合、\(\mathbb{K}\) はキーの集合) のタグを付与することができる。\(\mathbb{V}\) には、マップに \(f:\mathbb{K}\to\mathbb{V}\) にキーが存在しないことを示すためのデフォルト要素 \(\bot\) を含む。

MST 構成は任意のバイト列に対するハッシュ関数に基づいている。このハッシュ関数は衝突耐性を前提としており、同じハッシュを持つ 2 つの列が見つかる確率は無視できると仮定する。これはマークル木構成に不可欠な一般的な仮定である。我々はまた、ハッシュ関数のサイズが \(B\) のべき乗である特定の区間の値に一様に射影されると仮定する。この追加の性質は、ハッシュ関数を空間 \(\mathbb{K}\) 上の決定論的乱数源を提供するという二次的な目的にも使用するため、我々の構成に必要である。これらの特性は両方とも SHA-512 などの最新のハッシュ関数によって実際に実現されている。

MST は検索木であり、内部の木ノードが複数の値を持ち、その値が \(\mathbb{K}\) のパーティションを定義し、そのパーティション内で子の値が分離されるという点で B 木に似ている。木は層に分割され、層 0 は葉ノードの層に対応する (Fig. 1)。層 1 の木ノードは連続する項目のブロックであり、その境界は \(l' \gt l\) の項目に対応する。例えば Fig. 1 では、層 0 の最初のノードには境界 \(x_1\) と \(x_5\) の間に含まれる値 \(\{x_2\), \(x_3\), \(x_4\}\) が格納されており、\(x_1\) と \(x_5\) はレイヤー 1 に格納されている。以前の構成 [20] と同様に、値をハッシュすることで得られる決定論的なランダム性を使用して木の形状が決定される。MST に格納される値は、ハッシュを計算し、その値を基数 \(B\) の進数で記述することによって層が割り当てらる。これを \(h_B(x)\) と呼ぶ。項目 \(x\) が割り当てられる層 \(l(x)\) は、\(h_B(x)\) においてゼロのみで構成される最長プレフィクスの長さと同じ番号の層である。

Fig. 1: マークル検索木の構造

B. MST の単一性と演算

ここまで我々が記述した構成は決定論的である。つまり、与えられた項目の集合に対して MST としての可能な表現は一つしか存在しないしないことを意味している。これは照合手順を実装するために重要な性質である。標準的な演算の実装はこの定義から導かれる。

MST をマップとして使用する場合、木 \(f\) 内の単一の項目に対する読み取り操作 \({\tt get}(f,k)\)、連続する項目の範囲に対する読み取り操作 \({\tt getrange}(f,[k_0,k_1))\)、書き込み操作 \({\tt put}(f,k,v)\)、\({\tt delete}(f,k)\) を効率的に実装できる。put 操作によって項目 \(x\) が非葉層 \(l \gt 0\) に挿入される場合、下位層 \(l' \lt l\) の木ノードの一部は境界 \(x\) で 2 つに分割する必要があるかもしれない。同様に、非葉層で値が削除される場合、海曹の一部のノードを結合する必要があるかもしれない。与えられた put 操作または delete 操作に対して、各層 \(l' \lt l\) で最大 1 回の分割または結合しか発生しないため、これらの操作の複雑さは木の深さに比例する。

構造的単一性 (structural unicity) の結果として、同じ要素を異なる順序で挿入しても常に同じ表現に収束し、ルートのマークルハッシュも同じになる。構造的単一性は中間ノードでも有効である。2 つの中間ノードが同じマークルハッシュを持つのは、これらのノードから始まる部分木にまったく同じ項目が含まれている場合のみである。したがって、2 つの木を比較して差異を探す際に同じマークルハッシュを持つ部分木が見つかった場合、それらの間に差異がないことが分かるため、それらの部分木全体をスキップできる。

C. 構造的特性: 平衡と深さ

\(B\) を基数とする数値を書き出す定数長の文字列に一様に投射するハッシュ関数を使用しているため、項目が層 \(l\) にある確率は \(p_l=\left(\frac{1}{B}\right)^l \frac{B-1}{B}\) である。層 \(l\) における値の平均数は、層 \(l+1\) に置ける値の平均数の \(B\) 倍であることは容易に分かる。層 \(l\) の値は層 \(l' \gt l\) の値を持つ境界で分割されるため、層 \(l\) のノードには平均して \(B-1\) 個の値が格納され、非葉層では \(B\) 個の子ノードが存在する。ノードがこれらの平均値よりもはるかに多くの値と子ノードを持つ確率は指数的に減少するため、ノードサイズを任意の高い確率で制限できる。

木の深さは項目を割り当てることのできる最大レベルである。層 1 に項目が存在する確率は \(np_l\) に制限され (ここで \(n\) は木の要素数)、これは \(l\) の増加とともに指数的に減少する。したがって木の深さは \(\log_B n\) に定数 \(c\) を加えた値に制限でき、その確率は \(c\) の増加と共に指数的に減少する。

木の深さは約 \(\log_B n\) であり、ノードは高い確率で一定数の項目を持つため、木は適切に平衡した構造を持ち、読み取り、書き込み、削除は \(O(\log_B n)\) の計算量で実装できると結論づけられる。

D. データセット比較の効率性

2 つの異なるノードに格納された 2 つのマークル検索木の比較は効率的である。ノード \(n_1\) 上の \(f\) と \(n_2\) 上の \(g\) を比較する場合、ノード \(n_1\) と \(n_2\) は \(O(d \log_B n)\) 個のメッセージのみを交換する必要がある。ここで \(d\)=\(|\{x \mid\) \(f(x)\) \(\ne\) \(g(x)\}|\)、\(n=\max(|f|,|g|)\) である。\(\mathbb{K}\) と \(\mathbb{V}\) の要素が一定サイズであると仮定すると、交換されるメッセージの平均サイズは \(B\) に比例する。

内部木ノードの平均出次数は \(B\) の値を変更することで制御できる。\(B\) の値を大きくすると、より多くのノードを含むノードととなり、ピア間で交換する際により多くの帯域幅を必要とするが、木は浅くなるため葉にいたるノードの完全なセットを取得するためのネットワークラウンドトリップ数が少なくなる。我々の実験では \(B=16\) に固定している。

E. CRDT としてのマークル検索木

\(\mathbb{V}\) が \(\forall x\) において \(\bot \sqcup_{\mathbb{V}} x = x \sqcup_\mathbb{V} \bot = x\) となるような結合操作 \(\sqcup_\mathbb{V}\) を持つ CRDT である場合、マークル検索木は \(\sqcup_\mathbb{V}\): \((f \sqcup g)(x)\) = \(f(x) \sqcup_\mathbb{V} g(x)\) の点対点適用によって定義される \(\mathbb{K}\to\mathbb{V}\) 上の CRDT を実装する。

CRDT が取る状態の列は、セクション II-A で説明したように、\(\sqcup\) に対して単調であることが想定される。状態 \(x\) から状態 \(x'\) への遷移は \(x' = x \sqcup o\) の形式でなければならない。マークル検索木の場合、これは許可される操作の集合を、各個のキーに対して単調なシーケンスにつながる操作のみに制限することを意味する。したがって、put および delete 操作を直接使用してはならず、代わりに更新は \({\tt update}(f,k,v)\) = \({\tt put}(f,k,{\tt get}(f,k)\sqcup v)\) の形式を使用する必要がある。

\(\mathbb{V}\) を適切に選択することで様々な CRDT を得ることができる。例えば \(\mathbb{V}=\{\bot,\top\}\) が項目が存在するかどうかを示すブール値である場合、\(\mathbb{K}\) 上で定義される成長専用集合を得る。\(\mathbb{V}\) がバージョン番号を持つ last-write-wins レジスタである場合、last-write-wins 調整を持つ Key-Value ストアが得られる。既存の CRDT 型はいずれも値型 \(\mathbb{V}\) として使用でき、異なる項目を効率的に検出するマップ CRDT 構成を実現する。

IV. 大規模オープンネットワークにおける CRDT

我々が提示したマークル検索木は、集合 CRDT またはマップ CRDT に対して、特に効率的なペアワイズ分散調整手順 (pair-wise distributed reconciliation procedure) を実装するために使用できる。この手順により、2 つのノードは自発的な交換に基づいて、他のノードの状態を事前に知る必要なく一意の状態に収束することができる。この手順を単純なゴシップベースのアルゴリズムと組み合わせることで、高いチャーン率 (high churn rate) を持つオープンネットワークにおける効率的な更新配信を可能にする。

A. 状態ベース CRDT のゴシップベース調整

我々の手法は MST を用いずに ALGORITHM 1 の基本形式に示される状態ベース CRDT の単純な分散状態更新手法に基づいている。ALGORITHM 1 はリアクティブゴシップ戦略を採用している。ノードが \(x_0\) から \(x_1\) へ状態遷移を伴う操作を行う場合 (ここで \(x_1 = x_0 \sqcup o\)、それは \(x_1\) をいくつかのランダムピアにゴシップする。ノードが状態 \(x'_0\) にあるときに状態 \(x_1\) を受信すると、\(x'_0 \sqcup x_1 = x'_1\) への遷移を行い、\(x'_1 \ne x'_0\) の場合、今度は \(x'_1\) をいくつかのランダムピアにゴシップする。ランダムピアノ選択は、ネットワークからランダムに選ばれたノードの ID を取得できるピアサンプリングサービス [14] を前提としている。

ALGORITHM 1 はリアクティブ push 専用交換を実装する。pull または push/pull 戦略を用いる他の方法も可能であり、チャネルを周期的なコンポーネントで拡張して従来のアンチエントロピープロトコルを実現することもできる。

ALGORITHM 1: 基本的なステートベース CRDT

B. マークル検索木を使用した大規模 CRDT の実装

ALGORITHM 1 を使用して集合や Key-Value ストアなどの大規模マップ型 CRDT を実装する場合、状態全体を交換するような単純な実装はすぐに扱いにくくなる。このような場合、MST を用いることで、ノード間の複数回のラウンドトリップをコストにするだけで、ネットワーク帯域幅の使用量を大幅に削減できる。ALGORITHM 2 は、ローカル操作をブロックすることなくバックグラウンドでこれを実現する方法を示している。マージに必要なリモート情報がすべて取得されるまで (12 行目) この状態に対して get 操作や update 操作を実行し続けることができる。このアルゴリズムでは、マージしたいリモート MST のセットがバッファに保持され (4, 14, 18 行目)、欠落しているすべてのブロックがリモートピアに要求される (13 行目)。すべてのブロックがローカルで利用可能になると、ネットワーク通信成しにマージ操作が実行され (16 行目) ローカル MST が更新される。

ALGORITHM 2: マークル検索木付きのステート CRDT

C. 因果一貫性

ALGORITHM 1 と ALGORITHM 2 は次の意味で因果一貫性を実装する: ノードが状態 \(x\) から読み取りを行った後、\(x\) から \(x' = x \sqcup o\) への遷移を生じる操作を行った場合、put 操作の因果過去 (causal past) は \(x\) に含まれていると記述でき、put を観測する他のすべてのノードは自身の因果過去 \(x\) (\(x'\) は \(x\) を含むため) または \(\sqcup\) に従って \(x\) の後継を観測する。このアルゴリズムの結果として得られる特性は、マージ \(\sqcup\) によって定義されるすべての CRDT に適用可能であり、マークル検索木はこれを CRDT のマップに自然に拡張する。これは因果ブロードキャスト [6][26] で要求されるように、ネットワークトポロジーにいかなる条件も付けずに行われる。これはすべてのゴシップイベントで完全な状態マージが行われるという事実から生じる。

因果一貫性が不要で、結果整合性で十分な場合、

D. A Note on Crashes

E. Extension to Distributed MSTs

V. APPLICATION: A CAUSALLY-CONSISTENT DISTRIBUTED EVENT STORE

A. Scuttlebutt anti-entropy

B. Merkle Search Tree anti-entropy

VI. EXPERIMENTAL EVALUATION

A. Methodology

B. A Metric for Event Dissemination

C. Results

VII. CONCLUSION AND OUTLOOK

A. Adaptive Algorithms

B. Merkle DAGs as Persistent Data Structures

C. Other Applications of Merkle Search Trees

ACKNOWLEDGEMENTS

This work has been partially supported by the French ANR projects DESCARTES n. ANR-16-CE40-0023, and PAMELA n. ANR-16-CE23-0016.

References

  1. N. Bronson, Z. Amsden, G. Cabrera, P. Chakka, P. Dimov, H. Ding, J. Ferris, A. Giardullo, S. Kulkarni, H. Li, M. Marchukov, D. Petrov, L. Puzar, Y. J. Song, and V. Venkataramani, “TAO: Facebook’s Distributed Data Store for the Social Graph,” 2013.
  2. W. Vogels, “Eventually Consistent,” Queue, vol. 6, Oct. 2008.
  3. M. Shapiro, N. Preguic ¸a, C. Baquero, and M. Zawirski, “ConflictFree Replicated Data Types,” in Stabilization, Safety, and Security of Distributed Systems, Springer Berlin Heidelberg, 2011.
  4. P. S. Almeida, A. Shoker, and C. Baquero, “Efficient state-based crdts by delta-mutation,” arXiv:1410.2803 [cs], 2014.
  5. A. van der Linde, J. Leitão, and N. Preguiça, “\(\delta\)-crdts: Making \(\delta\)-crdts delta-based,” PaPoC ’16, p. 12:1–12:4, ACM, 2016.
  6. B. Nédelec, P. Molli, and A. Mostéfaoui, “Breaking the Scalability Barrier of Causal Broadcast for Large and Dynamic Systems,” arXiv:1805.05201 [cs], May 2018.
  7. R. J. T. Goncalves, P. S. Almeida, C. Baquero, and V. Fonte, “DottedDB: Anti-Entropy without Merkle Trees, Deletes without Tombstones,” in SRDS ’17, 2017.
  8. R. C. Merkle, “A digital signature based on a conventional encryption function,” 1987.
  9. G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels, “Dynamo: Amazon’s Highly Available Key-value Store,” p. 16, 2007.
  10. R. van Renesse, D. Dumitriu, V. Gough, and C. Thomas, “Efficient Reconciliation and Flow Control for Anti-entropy Protocols,” LADIS ’08, ACM, 2008.
  11. A. Fox and E. A. Brewer, “Harvest, yield, and scalable tolerant systems,” pp. 174–178, 1999.
  12. S. Gilbert and N. Lynch, “Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-tolerant Web Services,” SIGACT News, 2002.
  13. A. Demers, D. Greene, C. Houser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry, “Epidemic algorithms for replicated database maintenance,” 1987.
  14. M. Jelasity, S. Voulgaris, R. Guerraoui, A.-M. Kermarrec, and M. van Steen, “Gossip-based peer sampling,” ACM Trans. Comput. Syst., 2007.
  15. A. Kermarrec, L. Massoulie, and A. J. Ganesh, “Probabilistic reliable dissemination in large-scale systems,” IEEE Transactions on Parallel and Distributed Systems, vol. 14, pp. 248–258, Mar. 2003.
  16. P. Euster, R. Guerraoui, A.-M. Kermarrec, and L. Maussoulie, “From epidemics to distributed computing,” IEEE Computer, 2004.
  17. Y. Zhang, A. Rajimwale, A. C. Arpaci-Dusseau, and R. H. ArpaciDusseau, “End-to-end data integrity for file systems: A zfs case study.,” in FAST, pp. 29–42, 2010.
  18. J. Benet, “Ipfs-content addressed, versioned, p2p file system,” arXiv preprint arXiv:1407.3561, 2014.
  19. R. Tamassia and N. Triandopoulos, “Efficient Content Authentication in Peer-to-Peer Networks,” in Applied Cryptography and Network Security, Springer Berlin Heidelberg, 2007.
  20. S. A. Crosby and D. S. Wallach, “Super-Efficient Aggregating HistoryIndependent Persistent Authenticated Dictionaries,” in ESORICS, 2009.
  21. R. Bayer and E. M. McCreight, “Organization and maintenance of large ordered indexes,” ACM, 1970.
  22. B. H. Bloom, “Space/time trade-offs in hash coding with allowable errors,” Commun. ACM, vol. 13, no. 7, pp. 422–426, 1970.
  23. J. Byers, J. Considine, and M. Mitzenmacher, “Fast approximate reconciliation of set differences,” p. 17, 2002.
  24. Y. Minsky, A. Trachtenberg, and R. Zippel, “Set reconciliation with nearly optimal communication complexity,” IEEE Transactions on Information Theory, vol. 49, p. 2213–2218, Sep 2003.
  25. L. Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System,” Commun. ACM, vol. 21, pp. 558–565, July 1978.
  26. R. Friedman and S. Manor, “Causal Ordering in Deterministic Overlay Networks,” Tech. Rep. CS Technion report CS-2004-04, 2004.
  27. J. R. Driscoll, N. Sarnak, D. D. Sleator, and R. E. Tarjan, “Making Data Structures Persistent,” STOC ’86, (New York, NY, USA), ACM, 1986.
  28. M. Shapiro, A comprehensive study of Convergent and Commutative Replicated Data Types, p. 1–5. Springer New York, 2011.
  29. N. Preguica, J. M. Marques, M. Shapiro, and M. Letia, “A Commutative Replicated Data Type for Cooperative Editing,” in 29th IEEE International Conference on Distributed Computing Systems, 2009.
  30. B. Nédelec, P. Molli, A. Mostefaoui, and E. Desmontils, “LSEQ: An Adaptive Structure for Sequences in Distributed Collaborative Editing,” DocEng ’13, ACM, 2013.
  31. T. Schütt, F. Schintke, and A. Reinefeld, “Scalaris: reliable transactional p2p key/value store,” in ERLANG ’08, p. 41, ACM Press, 2008.

翻訳抄

従来の CRDT 技術は因果ブロードキャストプリミティブやベクタークロックに依存しているが、これらは大規模なオープンネットワークでは効率的に実装することが難しい。状態を Merkle Search Tree (MST) として符号化することで、純粋な状態ベース CRDT を効率的に実装できることを提案する 2019 年の論文。

  1. Alex Auvolat, François Taïani. Merkle Search Trees: Efficient State-Based CRDTs in Open Networks. SRDS 2019 - 38th IEEE International Symposium on Reliable Distributed Systems, Oct 2019, Lyon, France. pp.1-10, ff10.1109/SRDS.2019.00032ff. ffhal-02303490f