構造的アルゴリズム

論文翻訳: Merkle-CRDTs: Merkle-DAGs meet CRDTs

Takami Torao 2020年の論文 #MerkleCRDT #CRDT #LogicalClock
  • このエントリーをはてなブックマークに追加

Héctor Sanjuán1, Samuli Pöyhtäri2, Pedro Teixeira1, and Ioannis Psaras1,3
1Protocol Labs
2Haja Networks
3University College London

概要

我々は Merkle-DAG を Conflict-Free Replicated Data Types (CRDTs) のトランスポートおよび永続層として研究し、Merkle-CRDT という用語を作り、関連する様々な概念、特性、利点、制限の概要を提供する。ここでは Merkle-DAG が論理クロックとしてどのように機能するかを示し、メッセージング層の保証が弱くレプリカの数が非常に多いシステムにおいて Merkle-CRDT が収束データ型の設計と実装を大幅に簡素化できる可能性を示す。Merkle-CRDT は DHT や PubSub アルゴリズムのようなスケーラビリティの高い分散技術を使用してコンテンツアドレス指定のセキュリティと重複排除の特性を活用することができる。このようなコンテンツ指向システムの例としては、日和見的に接続されるモバイルデバイス、IoT デバイス、または Web ブラウザで実行されるユーザアプリケーション間のピアツーピアコンテンツ交換および同期アプリケーションが挙げられる。

Table of Contents

  1. 概要
  2. I. 導入
  3. II. 背景と関連研究
    1. A. 結果整合性
    2. B. Merkle DAGs
    3. C. 論理クロック
    4. D. Conflict-free Replicated Data Types (CRDTs)
    5. E. 情報中心ネットワークにおける同期プロトコル
    6. F. IPFS: The InterPlanetary File System
  4. III. システムモデルと仮定
    1. A. DAG-Syncer コンポーネント
    2. B. Broadcaster コンポーネント
    3. C. DAG-Syncer および Broadcaster コンポーネントとしての IPFS
  5. IV. Merkle-Clocks
    1. A. 概要
    2. B. 収束する複製データ型としての Merkle-Clocks
    3. C. クロックの中の Merkle: Merkle-Clock の特性
  6. V. Merkle-CRDTs: ペイロード付き Merkle-Clocks
    1. A. オブジェクト単位の因果整合性とギャップ検出
    2. B. Merkle-CRDT の一般的なアンチエントロピー・アルゴリズム
    3. C. 操作ベース Merkle-CRDTs
    4. D. 状態ベース Merkle-CRDTs
  7. VI. Merkle-CRDT の制約と最適化
    1. A. Merkle-CRDT の制約
    2. B. Merkle-CRDT の最適化
  8. VII. 結論
  9. Appendix
  10. References
  11. 翻訳抄

I. 導入

ブロックチェーン技術の登場は、暗号通貨のようなアプリケーションにおいてグローバルに分散され、結果整合性のあるデータ構造を実現するために、Merkle-DAG として知られる暗号指向の非巡回グラフとともにピアツーピアネットワーキングの使用を一般化した。Merkle-DAG はこれらのシステムにおいてトラストレスなピアツーピア環境で簡単かつ効率的に共有できるオブジェクトの因果情報と自己検証の両方を提供するために使用されているコンテンツアドレス型データ構造である。敵対的なシナリオでは、ブロックチェーンに新しいブロックを追加するために一定のルールを維持および適用する必要があるため、通常はコンセンサスアルゴリズムの使用が正当化される。

分散システムにおいて結果整合性を得るための別のアプローチは Conflict-Free Replicated Data Types (CRDTs) [30], [33] を使用することである。CRDT は参加しているレプリカが正しく動作していると分っている非敵対的シナリオで有用である。CRDT はコンセンサスを必要とせず、グローバルでユニークな状態への収束を可能にするデータオブジェクト自体の特性に依存している。CRDT には 2 つの種類がある。レプリカの状態が結合半束 (join-semilattice) を形成しその保証の下でマージされる状態ベースの CRDT1 と、可換演算がブロードキャストされすべてのレプリカがローカル状態に適用する操作ベースの CRDT2である。さらに \(\delta\)-CRDTs は状態ベース CRDT の最適化であり、レプリカによって送信されるペイロードのサイズを削減する。

Merkle-DAG と CRDT はどちらも興味深い特徴を備えている: 前者は分散システムがコンテンツアドレッシング層を利用することでソースの場所に関係なくデータの解決/発見可能性と自己検証を行うことができ、後者は通常複雑で高価なコンセンサスアルゴリズムを使用することなくグローバルな状態の収束を行うことができる。CRDT オブジェクトを Markle-DAG ノード内に埋め込むことにより両世界の最良の特性が得られる。つまり、DAG を論理クロックとして利用できる収束システムを得ることができる。この論理クロックは協調を必要とせずにすべてのレプリカによって提供および構築される。レプリカは配信の保証がないルーズなネットワーク環境でも中断されることなく動作することができる。後述するように、Merkle-CRDT に基づくシステムは、システムがレプリカ間でどのようにデータをアナウンスし発見するかについて完全に不可知であるため、DHT や PubSub メカニズムによって提供されるような様々なアプローチを活用できる。これは従来のコンセンサスアルゴリズム、例えば Raft が特定のメッセージ配信プロトコルに縛られているのとは対照的である。

このアプローチは、レプリカが共通データセット (通常はデータベースの形式) の書き手であるような、完全に分散された非構造的ピアツーピアアプリケーションにおいて非常に有効だとと考えている。例えば、分散された完全な複製ファイルシステム、チャットグループ、パッケージリポジトリのインデックスなどが当てはまる。我々は InterPlanetary File System (IPFS) [14] (セクション II-F 参照) をコンテンツアドレスのピアツーピア分散ファイルシステムおよびコンテンツ配信ネットワークとして使用することで、Merkle-CRDT ベースのシステムがモバイル、ブラウザまたは IoT デバイスで作業する際に非常に一般的な条件である、臨機応変に参加および離脱することができる数千のレプリカのオーダーまで十分にスケールすることを発見した。

InterPlanetary File System はコンテンツアドレッシングされたピアツーピアファイルシステム [14] を提供する。これは任意のフォーマットとペイロードを持つ Merkle-DAG のシームレスな同期をサポートし、PeerPad3 や OrbitDB4 のような CRDT と IPFS を搭載した様々なタイプの分散アプリケーションのための堅牢なビルディングブロックとなっている。

IPFS は (今回使用する Merkle-DAG のような) コンテンツアドレッシングされたデータを扱うための適切な環境を提供するだけではなく、CRDT アプリケーションを分散システムの下位レベルから完全に切り離すこともできる。ネットワーキングトランスポート、検出、およびデータ転送機能はモジュール化されており、個別に交換および調整することができる。このようなシステムを活用することで CRDT 層の設計と最適化が大幅に簡素化され、使用するユースケースにうまく適応できるようになる。

この論文では Merkle-CRDT と呼ばれるものを形式化する。この目的は、Merkle-CRDT の特性、利点、制限の概要を提供することであり、この分野における将来の研究や空間の最適化のための基礎となるものである。例えば Merkle-CRDT は、メッセージ配信が保証されていないネットワーク上の現実的なシステムにおいて、完全な分散 Key-Value ストアを構築することを可能にし、CRDT レイヤーに影響を与えることなくいつでも拡大・縮小できる柔軟なレプリカ集合を構築できる。

この論文の貢献は以下の通りである:

  • 分散システムにおける因果情報を表現するために、Merkle-DAG ベースの論理クロックとして Merkle-Clock を定義する。Merkle-DAG を用いた因果情報の埋め込みは暗号通貨や Git のようなソース管理システムの中核であるが、論理クロックの一種として個別に考慮されることはほとんどない。我々は Version Vector や Vector Clock のような CRDT で伝統的に使用されている他の論理クロックの代わりに Merkle-Clock を使用できることを実証する。我々は Merkle-Clock が CRDT オブジェクトそのものであり、同期やマージが可能であり、異なるレプリカ間での一貫性を正式に証明できることを示す。

  • 我々は、設計によりオブジェクト単位の因果整合性を提供するために DAG-Syncer と Broadcaster を使用し Merkle-Clock の特性を活用した CRDT ペイロードの汎用トランスポートおよび永続化レイヤーとして Merkle-CRDT を定義する。これによりメッセージング層の保証が弱くレプリカ数の多いシステムでも単純な CRDT 型を使用できるようになる。

この論文の目的は、基礎となるトランスポートメカニズムに依存せずすべてのピアが平等である設定においてレプリカ間の最終的な一貫性を達成できることを示すことである。これはつまり、基礎となるピアの発見およびルーティングシステム (DHT, PubSub など) の上にMerkle-CRDT を実装できることを意味している。これは非常に強力な概念であり、新たな一貫性システムの設計に繋がる可能性があると我々は主張する。また Raft などの従来のコンセンサスアルゴリズムとは根本的に異なる。Raft では任意の時点で他のすべてのピアから最新の状態を収集するリーダーピアが必要である。このように要件と設計原理が根本的に異なるため、これらの従来のアプローチに対する評価は提供しない。

この論文の残りの部分は次のように構成されている: セクション II ではまず関連する背景概念と先行技術を紹介することから始める。セクション III ではシステムモデルの特徴を明らかにし、Merkle-CRDT の保存と同期に必要な機能を紹介する。

セクション IV では Merkle-Clock を紹介し、セクション V では前のセクションをもとに Merkle-CRDT を定義する。さまざまな CRDT ペイロード (操作ベース、状態ベース、\(\delta\)-ベースのいずれか) が Merkle-CRDT からどのように恩恵を得るかについて議論する。最後に、セクション VI では Merkle-CRDT の限界と非効率性に付いて説明しそれらを克服する手法を紹介する。

  1. 1収束 CRDTs (Convergent CRDTS) または CvRDTs でも知られる。
  2. 2可換 CRDTs (Commutative CRDTs) または CmRDTs でも知られる。
  3. 3PeerPad はリアルタイムの P2P 共同編集ツールである (https://peerpad.net)。
  4. 4OrbitDB は分散型 Web のためのピアツーピアデータベースである (https://github.com/orbitdb/orbit-db)。

A. 結果整合性

分散システムにおける結果整合性 (EC; Eventual Consistency) とは、システムのレプリカ間が同じ状態でなくても十分な時間があれば、そしておそらくネットワーク分断やダウンタイムなどの不測の事態が解決された後であれば、システム設計によってどれも同じ状態になることを保証する状況を示す。

結果整合性の定義の主な弱点は、共有状態がいつ収束するのか、またはそれまで個々の状態がどの程度乖離することが許されるかについて保証ができないことである5。強い結果整合性 (SEC; Strong Eventual Consistency) は 2 つのレプリカが同じ更新を受け取った場合、それらの状態は同じになるという追加の保証を確立することでこれらの問題に対処する。

コンセンサスアルゴリズム、あるいは本論文にとってより重要な Conflict-Free Replicated Data Types (CRDTs) は分散システムにおいて (強い) 結果整合性を実現する方法である。

B. Merkle DAGs

有向非巡回グラフ (DAG; Directed Acyclic Graphs) は辺に方向があり循環が許されないグラフの一種である。例えば \(A \to B \to C\) のようなリンクリストは DAG の一種であり、\(A\) は \(B\) を参照する。\(B\) は \(A\) の子または子孫であり、ノード \(A\) は \(B\) へのリンクを持っている。逆に \(A\) は \(B\) の親である。DAG 内の他のノードの子ではないノード6をルートノードと呼ぶ。Merkle-DAG は各ノードが識別子を持つ DAG であり、その識別子はノードの内容 (ノードによって運ばれる不透明なペイロードとその子の識別子リスト) を SHA256 のような暗号論的ハッシュ関数を用いてハッシュ化して得られた結果である。これによりいくつかの重要な考慮点が生じる:

  1. Merkle-DAG は葉、つまり子のないノードからしか構築することができない。親は子の後に追加されるが、これはこの識別子が事前に計算されていないとリンクできないためである。

  2. Merkle-DAG の各ノードはそれ自体が (サブ) Merkle-DAG のルートであり、この部分グラフは親の DAG7 に含まれる。

  3. Merkle-DAG のノードは不変である。ノードが変更されるとその識別子が変更され、DAG 内のすべての上位ノードに影響し、本質的に別の DAG が作成される。

Merkle-DAG のようなデータオブジェクトをハッシュ値で識別することはコンテンツアドレッシングと呼ばれる。したがってノード識別子をコンテンツ識別子 (Content Identifier) または CID と名付ける。

例えば先のリンクリストで各ノードのペイロードがその子孫の CID だけであると仮定すると \(A = {\rm Hash}(B)\) \(\to\) \(B = {\rm Hash}(C)\) \(\to\) \(C = {\rm Hash}(\emptyset)\) のようになる。ハッシュ関数の特性により Merkle-DAG を生成する際に循環が存在しないことが保証される8。

Merkle-DAG は自己検証可能で不変な構造である。ノードの CID はそのペイロードの内容およびすべての子孫の内容に一意的にリンクされている。したがって同じ CID を持つ 2 つのノードは全く同じ DAG を一意的に表している。これは IPFS のようなシステムで利用されているように、完全な DAG をコピーすることなく、効率的に Merkle-CRDT を同期するための重要な特性である。

Merkle-DAG は広く使われている。Git [17] のようなソース管理システム [13] はオブジェクトの重複を排除しブランチ間の競合を検出を可能にする方法でリポジトリ履歴を効率的に保存する。Dynamo [19] のような分散データベースではレプリカ間の状態の効率的な比較と調整のために Merkle-Tree が使用されている。Hash Histries [22] では状態を表す Merkle-Tree を参照するためにコンテンツアドレッシングが使用されている。

Merkle-DAG はブロックチェーンの基礎となっているブロックでもあり単一の枝を持つ Markle-DAG として見ることができる。またその最も一般的な用途は暗号通貨である (例えば [3], [1], [18])。Bitcoin [26] のような暗号通貨はチェーン内に埋め込まれた因果情報の恩恵を受けている。つまりチェーン内の深いブロックにおけるトランザクションは常にそれ以前のブロックのトランザクションよりも先に起きる (happened before)。暗号通貨における主な問題の 1 つは、参加するすべてのピアにチェーンの先端/先頭/ルートについて合意させることである。とりわけ、一部のトランザクションには非可換な性質があるため有効なブロックのみが新しいルートになることを強制するコンセンサスメカニズムが必要となる。

これらのシステムの多くに共通する点は Merkle-DAG が因果情報を暗黙のうちに埋め込んでいることである。DAG は特定のトランザクションが別のトランザクションに先行することや、Git のコミットが fast-forward ではなく merge される必要があることを示すことができる。これは我々が Merkle-CRDT で使用する特性の一つであり、この論文では論理クロックとして知られる他の因果関係エンコードメカニズムと対比して明示する。

C. 論理クロック

因果収束システムの設計には、例えばイベントが同時に発生したときに異なるレプリカ間で異なる状態のバージョンを調整することが含まれている。

そのためには 2 つのイベントが実際に同時に発生したかどうか、また同時更新やその他の理由 (1 つのレプリカがより多くの更新を受けたなど) によって 2 つの状態が実際に異なっているかを識別できる必要がある。

本質的にこの問題は異なるイベントが起きた順序を追跡することである。たとえば異なるレプリカでレジスタに複数の値の書き込みがあった場合、レジストリの最終値が最後の書き込みの値になることが期待される。

理想的には、システム内のすべてのイベントを順序付けし9、レジスタへの実際の最後の更新がどれであるかを識別できるようにする必要がある。

イベントにタイムスタンプをつけることで次のような情報を得られる: もしすべてのイベントにタイムスタンプをつけることができれば、どのレプリカもそのイベントの発生順序を認識することができ、その情報を使って最終的な状態を決定することができる。ただし分散システムではすべてのレプリカをグローバル時刻に完全に同期できるわけではないため、タイムスタンプを確実に使用することはできない [27]。"壁時計" (wall clock) も簡単にシミュレートやなりすましが可能で信頼のないピアツーピアシステムでは問題となる。

論理クロック (logical clock) はグローバル時刻に代わるものである。論理クロックは分散システムの異なるアクターが機知のイベント間の因果情報をエンコードする方法を提供する。

基本的な考え方は、すべてのイベントがグローバルに発生した順序は分らないかも知れないが、すべてのレプリカは少なくともそれ自身が発行したイベントの順序を知っていると言うことである。その情報を受信した他のレプリカは、それ以降に自分自身によって発行されたイベントがその後に来ることを認識する。これは本質的に因果履歴 (causal history) として知られているものである。

論理クロックは因果履歴 [12] を表現したものであり、イベント間の部分的な順序づけを提供する。つまり 2 つのイベント \(a\) と \(b\) が与えられたとき、論理クロックは \(a\) が \(b\) の前に起きた (happened before) のか (\(a \to b\))、あるいはその逆か (\(b \to a\))、または \(a\) と \(b\) の両方が同時に起きたか (\(a || b\)) を知ることができるはずである。

論理クロックの実用的な実装には通常、システム内のすべてのイベントに付随して送信されるメタデータが含まれる。論理クロックの最も一般的な形式の一つは Version Vector [28] である。すべてのレプリカは、すべてのレプリカの状態がどのバージョンであるかを追跡するベクトルを保持しブロードキャストする。レプリカが状態に変更を加えるとそのレプリカのバージョンが上がる。レプリカが他のレプリカから状態をマージするとき、ローカルバージョンとイベント共に他のレプリカから提供されたバージョンの間で最も高いバージョンが採用される。したがって Version Vector \(\mathcal{V}^a\), \(\mathcal{V}^b\) を持つ 2 つのイベント \(a\), \(b\) が与えられたとき、ベクトル内の各位置 \(i\) に対して \(\mathcal{V}^a_i \leq \mathcal{V}^b_i\) ならば \(\mathcal{V}^a, \mathcal{V}^b: a \to b\) である。\(a \not\to b\) かつ \(b \not\to a\) の場合、その定義より \(a\) と \(b\) は同時である。

見て分るように、Version Vector は完全な因果履歴を保存する必要がなく、各レプリカの履歴の長さを示す数字を保存するだけなのでコンパクトである。Version Vector はレプリカの数に依存するため、多数のレプリカが存在するシナリオやレプリカの数が安定していないシナリオでうまく機能させるにはさらなる最適化が必要になるかも知れない。

この論文では Merkle-DAG が論理クロックとして機能できることを実証する。これから示すように Merkle-Clock は異なる性質を持つがイベントに関する因果情報は同じである。

D. Conflict-free Replicated Data Types (CRDTs)

CRDT は、状態やそれを更新する操作に特定の特性を要求することで分散システムの異なるレプリカ間で強力な結果整合性を提供するデータ型である。さらに CRDT は単調性 (monotonicity) という特徴も持ち合わせている。データ型に適用される単調性の概念は、更新のたびに状態が膨張 (inflation) し、サイズではなく以前の状態を基準にして状態を拡大するという概念である。これは、状態間には常に順序があることを意味している。単調性は、更新が行われる順序に関係なく、状態のロールバックが不要であることを意味する。

CRDT には状態ベース CRDT と操作ベース CRDT の 2 つの主要なタイプがある。状態ベース CRDT では、システム内のすべての状態 (つまり異なるレプリカおよび異なる瞬間の状態) が単調結合半束 (monotonic join-semilattice) を形成する。つまり任意の 2 つの状態 \(X\) と \(Y\) について、両者を "結合" (joined) (マージまたは合併) (\(\sqcup\)) することができ、その結果は 2 つの状態の最小上限 (LUB; Least-Upper-Bound) に対応する新しい状態となる [30]。言い換えれば、レプリカが状態に加えるすべての変更は膨張でなければならず、2 つの状態 \(X\) と \(Y\) の結合は \(X\) と \(Y\) の両方を含むことができ、それ以上を含まない最小の状態 (つまり LUB) である。したがって結合半束は半順序集合であり、その LUB は半束内のすべての状態を含む最小の状態である。このことは、演算が冪等 (\(X \sqcup Y = X\)) であり、可換 (\(X \sqcup Y = Y \sqcup X\)) であり、結合可能 (\((X \sqcup Y) \sqcup Z = X \sqcup (Y \sqcup Z)\)) であることを意味する。

状態ベース CRDT におけるレプリカは、自身の状態を変更または膨張し、その結果の状態を他のレプリカにブロードキャストする10。状態を受信した他のレプリカはその状態をローカルの状態とマージする。状態の特性により、レプリカが他のレプリカから送信された状態を正しく受信していれば (その逆も同様) 最終的に収束することが保証される。

一方、操作ベース CRDT [30] は状態そのものには何の特性も強制しないが、状態を変更するための操作には (少なくとも同時に発行された別の操作に関しては) 可換でなければならない。レプリカは状態ではなく操作をブロードキャストする。2 つのレプリカで同時に 2 つの操作が発生した場合、他のレプリカがそれを適用する順序は問題ではない。

その結果、例えばネットワーク障害などで操作のブロードキャストがレプリカに到着しなかった場合、そのレプリカはその操作を適用することができず状態は収束しない。したがって状態ベース CRDT とは異なり操作ベース CRDT の結果整合性には最終的にすべての操作を配信する信頼性の高いメッセージング層が必要である [11]。例えば操作が冪等でない場合、メッセージング層は各操作が正確に一度だけ (exactly once) 配信されることを保証する必要があるという追加の制約が必要になるだろう。

操作ベース CRDT の中には因果的な配信を要求するものもある。あるレプリカが操作 \(a\) を \(b\) より先に送信した場合 (\(a \to b\))、\(a\) は常に \(b\) より先に別のレプリカに配信されなければならない。

状態ベース CRDT と操作ベース CRDT の両方におけるこれらの特性と要件によりオブジェクトごとの因果一貫性 (per-object causal consistency) が保証される。つまり状態を更新するとそれらの間の因果関係が維持される。例えば Grow-Only Set (G-Set) では、あるレプリカが要素 \(A\) を追加し、次に要素 \(B\) を追加した場合、他のレプリカは \(B\) がセットの一部だが \(A\) が含まれていないセットを持つことはない11。

前のセクションで説明したように、論理クロックは CRDT タイプを実装するためによく使用される。論理クロックは 2 つの更新が同時に発生しマージが必要なタイミングを識別するのに役に立つ。CRDT は様々なアプリケーションや分散データベースで使用され最適化されており、Basho の Riak [15], [16] は最も代表的な例の 1 つである。

E. 情報中心ネットワークにおける同期プロトコル

前述の Version Vector に似ているが、異なるニーズを満たしたり欠点の一部を解決した複数のタイプの論理クロックが存在する: Vector Clock [21], Bounded Version Vector [8], Dotted Version Vector [29], Tree Clocks [24], Interval Tree Clocks [9] などである。

情報中心ネットワーク (ICN; Information-Centric Networks) [32], [31], [35], [7] の分野では分散データセットの同期に関する最近の研究がある。情報中心アーキテクチャでは、ネットワーク層で直接的なコンテンツ命名とそれに続く (コアネットワークルータによる) ルーティングと転送をコンテンツ名と (場合によっては) 最長接頭辞マッチングに基づいて行うことを提唱している。

ChronoSync [35] は Named-Data Networking アーキテクチャ [34] の機能を利用して異なるデータセット間の状態を同期させている。ChronoSync はデータレイヤーのメカニズムであるが、NDN が構築している階層的で柔軟な命名スキームを利用している。Merkle Tree にヒントを得た ChronoSync は暗号ダイジェストとフィルターを使用してピア間でデータセットを同期する。ChronoSync は基礎となるネットワーク (NDN) の名前ベースの性質を利用し、各ピアに一意の公開接頭辞を割り当てている。この一意の接頭辞はシーケンス番号とネットワーク層の永続的/長寿命の "Interest packets" とともに、他のアプローチがクロックや CRDT で行おうとしていることの大部分を置き換えている。同期機構をネットワーク層で統合することで、よりネイティブな設計が可能になる一方で、一部の機能は必然的に失われる。たとえば ChronoSync は同時 (並行) データ公開に対応できない。RoundSync [32] は同期プロセスをラウンドで分割することでこの問題を部分的に解決している。

VersionSync [31] は ChronoSync [35] の拡張版で、Version Vector を使用してピア間の同期を効率化する。前述の通り Version Vector は単純なメッセージダイジェストよりも不整合の検出において効率的である。しかしこの分野は他の提案と同様に、VectorSync はデータセットの状態を更新するアクティブなメンバーに対処するために "リーダーベースのメンバーシップ管理" を実現する必要がある。

分散データセット同期機能をネットワークのネットワーク層にネイティブに統合することは明らかに先進的な試みであり独自の課題を伴う。Merkle-CRDT によってもたらされる "トランスポートにとらわれない" 状態同期の利点は ChronoSync, RoundSync, VectorSync などのプロトコルに適用でき、パフォーマンスを向上させることができると考えている。一方、Merkle-CRDT ベースの状態同期を名前付きネットワークオブジェクトで直接処理すると、Merkle-CRDT に標準的な ICN の利点がもたらされる。そのため状態同期に対するこれら 2 つの異なるアプローチは補完的なものであると考えられる。

F. IPFS: The InterPlanetary File System

IPFS [14] はコンテンツアドレッシング型の分散ファイルシステムである。分散ハッシュテーブル (DHT; Distributed Hash Table) を使用して特定の Merkle-DAG ノードを提供するレプリカ (またはピア) をアナウンスおよび検出する。これは bitswap と呼ばれるノード交換プロトコルを実装して任意のプロバイダから DAG ノードを取得する。IPFS は P2P ネットワーク用のモジュラーネットワークプロトコルスタックである libp2p [5] 上に構築されており、さらに、主に publish-subscribe モデル [2] に基づいた効率的なブロードキャストメカニズムを提供している。

IPFS はまた任意のノードフォーマットと複数のタイプの CID [6] をサポートする Merkle-DAG を記述するフレームワークである IPLD, InterPlanetary Linked Data Format [4] を使用しており、カスタム DAG ノードの作成と同期が非常に容易になっている。

これらの機能により、IPFS は潜在的に非常に大規模なネットワーク内でコンテンツを検出、ルーティング、アナウンスするために必要なメカニズムを提供するため、Merkle-CRDT を実装するのに適したレイヤーとなっている。これは他のトランスポートメカニズムが Merkle-CRDT を構築するのに適していないということではない。

  1. 5EC はシステムが収束に向けて前進しているときにスタックしないという有効性の保証のみを提供する。
  2. 6本論文を通じて、ネットワークノードの物理的なマシンを指す場合はレプリカ、単一の識別子でアドレス指定されたバンドルコンテンツを指す場合はノードという用語を使用する。
  3. 7Merkle-DAG は Merkle Tree [25] と類似しているが、バランス要件はなく、すべてのノードがペイロードを運ぶことができる。また DAG では複数の枝が再合流することができる。言い換えると、ノードは複数の親を持つことができ、複数の Merkle DAG の一部になることができる。
  4. 8ハッシュ関数は一方向関数である。何らかの脆弱性が発見され悪用されない限り循環を作ることは不可能なほど難しいはずである。
  5. 9これはすべての事象に対して厳密な順序 (total strict order) を確立することを意味する。
  6. 10ここで重要なことは CRDT は単なるデータ型ということである。レプリカ間の CRDT オブジェクトの送信ポリシーは独立している。一部の CRDT は、設計上、他のブロードキャストメカニズムよりも一部のブロードキャストメカニズムに適しており、すべてのレプリカにブロードキャストするのではなく、ランダムなサブセットにのみブロードキャストするといった最適化を容易にできる。
  7. 11これは G-Set の操作ベースの実装では明らかである (操作の因果配信を想定した場合)。G-Set の状態ベースの実装には完全なセットの送信が含まれている。したがって \(B\) を追加するイベントはすでに \(A\) を含むセットである。たとえ \(A\) を追加したイベントが失われたり後から到着したとしても、\(B\) が存在し \(A\) が存在しないセットは存在しない。

III. システムモデルと仮定

我々の Merkle-CRDT アプローチは単純であると同時に、多数のレプリカが存在しメッセージ配信の保証がない (つまり信頼性の低いトランスポート) ピアツーピア分散システムで CRDT の使用を容易にすることを目的としている。

我々は、別々のレプリカ間の通信チャネルを提供する非同期メッセージングレイヤーの存在を仮定している。このチャネルはすべてのレプリカが利用する 2 つの機能、DAG-Syncer と Broadcaster コンポーネントによって管理される (以下に定義)。

我々は、メッセージは削除されたり順序が入れ替わったり、破損したり、複製されたりする可能性があると想定している。システムに参加しているレプリカの数を事前に知っておく必要はない。レプリカは他のレプリカに通知することなく自由に参加したり離脱することができる。ネットワーク分断が発生する可能性があるが、接続が再確立され、レプリカが新しいイベントをブロードキャストすればすぐに解決される。

レプリカはそれぞれの要件やデータタイプに応じて耐久性のあるストレージを持つことができる。Merkle-CRDT を使用すると耐久ストレージを持たない新しいレプリカやクラッシュしたレプリカでも、他のレプリカが少なくとも 1 つ最新のシステム状態にある限り最終的にシステムの完全な状態を再構築することができる。

A. DAG-Syncer コンポーネント

DAG-Syncer は、レプリカが他のレプリカからコンテンツ識別子 (CID) を指定してリモートの Merkle-DAG ノードを取得したり、自身のノードを他のレプリカが利用できるようにするコンポーネントである。ノードには直接の子孫へのリンクが含まれているため、ルートノードの CID を指定すると DAG-Syncer コンポーネントを使用して各ノードの子へのリンクをたどって完全な DAG を取得することができる。したがって DAG-Syncer を以下のように定義することができる:

定義 1. (DAG-Syncer). DAG-Syncer は 2 つのメソッドを持つコンポーネントである:

  • Get(CID): Node
  • Put(Node)

ノードをアナウンスしたり取得するプロトコルがどのように見えるかなど、これ以上の詳細は指定しない。理想的には DAG-Syncer レイヤーはシステムモデルに追加の制約を課すべきではない。我々のアプローチは DAG-Syncer と Merkle-DAG の特性に依存して上記のすべてのネットワーク上の不測の事態を許容する。

B. Broadcaster コンポーネント

Broadcaster はあるレプリカから他のすべてのレプリカに (直接またはリレーを通じて) 任意のデータを配信するコンポーネントである。理想的にはペイロードはシステム内のすべてのレプリカに到達するが、これはすべてのブロードキャストメッセージの要件ではない:

定義 2. (Broadcaster). Broadcaster は 1 つのメソッドを持つコンポーネントである:

  • Broadcast(Data)

C. DAG-Syncer および Broadcaster コンポーネントとしての IPFS

上記のコンポーネントは (セクション II で紹介したように) IPFS を使用して実現できる。IPFS は DAG-Syncer として動作し、その libp2p レイヤーによって提供される PubSub メカニズムの 1 つは Broadcaster コンポーネントのタスクを実行することができる。

このような実装では一般にレプリカ集合の極端なスケーラビリティが可能になる。ネットワーク内のピアは他のすべてのピアと完全に接続されている必要はなく、システムは非常にモジュール化されており、小型デバイスと大規模ストレージサーバの両方に適合できるように構成可能である。設定や実装の選択は様々状況やネットワークトポロジーの下でのシステムパフォーマンスに影響するが、Merkle-CRDT オブジェクトやデータ型には依存しない。

IV. Merkle-Clocks

A. 概要

Merkle-Clock \(\mathscr{M}\) は各ノードがイベントを表す Merkle-DAG である。言い換えれば、システム内にイベントが与えられると我々はそれを表すノードをこの DAG 内で見つけることができ、それを使用して他のイベントと比較できるようになる。

DAG はいくつかの簡単なルールに従って他の DAG (他のレプリカにある DAG) をマージすることで構築される。新しいイベントは新しいルートノード (既存のイベントの親) として追加される。Merkle-Clock はある時点で複数のルートを持つ可能性があることに注意。

例えば \(\mathscr{M}_\alpha\) と \(\mathscr{M}_\beta\) が与えられたとする (\(\alpha\) と \(\beta\) はこれらの DAG における単一のルート CID である12):

  1. \(\alpha=\beta\) の場合、同じ DAG であるためアクションは必要ない。

  2. \(\alpha \in \mathscr{M}_\beta\) の場合、\(\mathscr{M}_\alpha\) の履歴はすでに \(\mathscr{M}_\beta\) の一部であるため \(\mathscr{M}_\beta\) を我々の新しい Clock として保持する。この場合 \(\mathscr{M}_\alpha \lt \mathscr{M}_\beta\) となる。

  3. \(\beta \in \mathscr{M}_\alpha\) の場合、同じ理由で \(\mathscr{M}_\alpha\) を保持する。これを \(\mathscr{M}_\beta \le \mathscr{M}_\alpha\) とする。

  4. それ以外の場合、両方の DAG をそのまま維持し \(\alpha\) と \(\beta\) が参照する 2 つのルートノードを持つことで両方のクロックをマージする。\(\mathscr{M}_\alpha\) と \(\mathscr{M}_\beta\) はより深いノードの一部を共有するかどうかによって完全に不連続になる可能性があることに注意。新しいイベントを記録したい場合、2 つの子 \(\alpha\) と \(\beta\) を持つ新しい子 \(\gamma\) を作成することができる。

ある Merkle-Clock が別の Merkle-Clock に含まれているかどうかを判断することで Merkle-Clock 間に順序の概念を導入していることが既にわかる。同様に以前に発生したイベントは常に後で発生したイベントの子孫となるため各クロックのノード間にも順序の概念がある。さらに、我々は比較方法に従って Merkle-Clock をマージする方法を導入した。結果として得られる Merkle-Clock は常に両方の Merkle-Clock の因果情報が含まれている。これは最終的にすべてのレプリカの Merkle-Clock に格納された因果情報がマージ後に同じ Merkle-Clock に収束することを意味する。

Merkle-Clock が提供する因果順序は同様のルールを使用して Merkle-DAG を構築する際に組み込まれ、通常は非常に直感的なものとして見過ごされている。しかし Merkle-Clock 間の順序を定義する方法を定式化し、Merkle-Clock が同期およびマージされたときに因果情報が維持されることを証明するのは重要である。

B. 収束する複製データ型としての Merkle-Clocks

このセクションでは Merkle-Clock の定義と Merkle-Clock DAG としてのその表現を定式的に説明する。Merkle-Clock DAG は Growing-Set (G-Set) CRDT と見なすことができ、したがって複数のレプリカで収束することを示す。

すべてのシステムイベントの集合を \(\mathscr{S}\) とする:

定義 3. (Merkle-Clock ノード). Merkle-Clock ノード \(n_\alpha\) はイベント \(\mathscr{e} \in \mathscr{S}\) を表すタプル: \[ (\alpha, \mathscr{e}_\alpha, \mathcal{C}_\alpha) \] である。\(\alpha\) はノード CID、\(\mathcal{C}_\alpha\) は \(n_\alpha\) の直接の子孫の CID 集合である。

定義 4. (Merkle-Clock DAG). Merkle-Clock DAG はペア: \[ \langle \mathbb{N}, \leq \rangle \] である。ここで \(\mathbb{N}\) は不変の DAG-ノードの集合であり、\(\mathbb{N}\) 上の半順序 \(\leq\) は次のように定義される: \[ n_\alpha, n_\beta \in \mathbb{N}: n_\alpha \lt n_\beta \Leftrightarrow n_a \mbox{ は $n_\beta$ の子孫である} \]

つまり \(n_\beta\) から \(n_\alpha\) に向かうリンクされたノードの経路が存在する場合 \(n_\alpha \lt n_\beta\) となる。

この関係を維持するために Merkle-Clock DAG は次の実装ルール (Inplementation Rule) IR で構築されなければならない。システム内のすべての新しいイベントは既存の Merkle-Clock DAG (複数可) の新しいルートノードとして表現されなければならない。特に集合 \(\mathcal{C}\) は以前のルート CID が含まれなければならない。

定義 5. (Merkle-Clock). Merkle-Clock (\(\mathscr{M}\)) はイベント \(\mathscr{e}_\alpha \in \mathscr{S}\) が与えられたとき Merkle-Clock DAG \(\mathbb{N}\) からノードを返す関数である: \[ \mathscr{M} : \mathscr{S} \to \mathbb{N} \]

備考. Merkle-Clock は強いクロック条件 [23] を満たす。すべてのノードはその子のイベントよりも後のイベントを表していることがわかる: \[ \forall (\beta, \mathscr{e}_\beta, \mathcal{C}_\beta) \in \mathbb{N}: \forall \alpha \in \mathcal{C}_\beta : \mathscr{e}_\alpha \to \mathscr{e}_\beta \] 各イベントは実装ルールを用いて構築された (部分) DAG のルートであるため、以前の Merkle-Clock 値が後のイベントの子孫であることがすぐにわかる： \[ \mathscr{M}(\mathscr{e}_\alpha) \lt \mathscr{M}(\mathscr{e}_\beta) \Leftrightarrow \mathscr{e}_\alpha \to \mathscr{e}_\beta \]

ここで Merkle-Clock DAG の結合半束をペアとして定義することができる: \[ \langle \mathbb{J}, \subseteq_\mathbb{J} \rangle \] ここで \(\mathbb{J}\) は Merkle-Clock DAG の集合であり、\(\subseteq_\mathbb{J}\) はその集合に対する半順序で次のように定義される。ある \(\mathbb{M}, \mathbb{N} \in \mathbb{J}\) に対して: \[ \mathbb{M} \subset_\mathbb{J} \mathbb{N} \Leftrightarrow \forall m \in \mathbb{M}, \exists n \in \mathbb{N} \ | \ m \lt n \Leftrightarrow \mathbb{M} \subset \mathbb{N} \] \(m \le n\) は \(m\) が \(n\) の子孫であり、したがって同じ DAG に属さなければならないことを意味し、\(\subset_\mathbb{J}\) は単に \(\mathbb{M}\) が \(\mathbb{N}\) の部分集合であることを意味する。

これにより 2 つの Merkle-Clock DAG の Least-Upper-Bound (\(\sqcup_\mathbb{J}\)) を集合の正規和として定義することができる: \[ \mathbb{M} \sqcup_\mathbb{J} \mathbb{N} = \mathbb{M} \cup \mathbb{N} \]

当然のことながら Merkle-Clock 表現は実際には状態ベースの CRDT 形式 [33] の Grow-Only-Set (G-Set) に対応する。集合の要素は不変であり暗号的にリンクされシステム内のイベントを表している。DAG が不連続 (互いに素) である場合、結果の DAG には \(\mathbb{N}\) と \(\mathbb{M}\) の両方のルートが含まれている。これは因果関係のない複数のイベントがあるのと同等である。DAG マージイベントに関する因果情報は、実装ルールに従って新しい一意なルートを作成することで DAG の結合後にオプションで含めることができる。

次のセクションでは Merkle-DAG の特性により通常の状態ベースの G-Set よりも効率的な方法で Merkle-Clock を同期する方法について説明する。

C. クロックの中の Merkle: Merkle-Clock の特性

ここまでレプリカごとに因果情報をエンコードする方法を定義し 2 つのレプリカ Merkle-Clock をマージできることを確認してきた。次に Merkle-DAG の特性によって push ではなく pull アプローチがどのように可能となり、コンテンツアドレッシングと組み合わせてレプリカ間の効率的なクロック同期が可能となり、ネットワークの分断や不測の事態の影響を克服できるかを説明する。レプリカ間の Merkle-Clock を同期する手順を以下に示す。

  1. Merkle-Clock をブロードキャストするには現在のルート CID のみをブロードキャストする必要がある。クロック全体はルートの CID によって明確に識別され必要に応じてそこから完全な DAG をウォークダウンできる。

  2. Merkle-DAG の不変性により、他のすべてのレプリカは迅速に比較を行い、まだ持っていないノードのみを pull/fetch することができる。

  3. Merkle-DAG ノードは CID によって自己検証されるため破損や改ざんの影響を受けない。そのため、信頼できるかどうかにかかわらず、ノードを提供しようとする任意のソースからそれらを fetch (pull) することができる。

  4. 同一ノードは設計により重複が排除される。すべてのイベントに対して一意な表現は 1 つだけ存在できる。

実際にはすべてのレプリカは他のレプリカからデルタ因果履歴をフェッチするだけで、システムのどこかに明示的にデルタを構築する必要はない。以前の履歴を持たない全く新しいレプリカは自動的に完全な履歴をフェッチする13。

Merkle-Clock は通常の CRDT の一部である Version Clock やその他の論理クロックを置き換えることができる。これにはいくつかの注意点がある。

  • Merkle-Clock を使用することで Version Clock の一般的な制限である因果情報とレプリカの数を切り離すことができる。これにより CRDT を実装する際のメッセージサイズを削減できるようになる。最も重要な点として、レプリカがシステムにランダムに参加したり離脱する際にクロックを動作させ続けるという問題を解決することができる。

  • マイナス面として因果情報はイベントごとに増大し、イベント情報を小さなオブジェクトに結合してもレプリカは潜在的に大きな履歴を保存することになる。

  • 因果履歴全体を保持することで、新しいレプリカはシステムのスナップショットを新規参加者に明示的に送信することなく、すぐにイベントを最初から同期することができる。しかし履歴が非常に大きい場合は同期に時間がかかる可能性がある。この点については Merkle-CRDT とともに最適化の可能性を探る予定である。

従来の Version Clock に対する Merkle-Clock の大きな利点はいくつかの種類のネットワーク異常にも対応できることである:

  • 紛失したメッセージ (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 がダウンロードされたコンテンツと一致しないときそれを破棄することができる。

前のセクションで示したように Merkle-Clock はイベントの厳密な半順序を表す。システム内のすべてのイベントを比較し順序付けることができるわけではない。例えばルートが複数ある場合 Merkle-Clock はどのイベントが最初に起きたかを判断できない。

全順序は有用であり [23]、たとえば同時並行するイベントを等しいと考えることで取得できる。同様に、厳密な全順序は同時発生イベントをそのノードの CID で並べたりクロックノードに付与された追加情報に基づいて他の任意のユーザ定義戦略で並べ換えたりすることで構築できる。このようなアプローチはデータレイヤーの競合解決として適格である。

  1. 12この例では一般性を損なわない範囲で、複数のルートではなく 1 つのルートを含む DAG から始めると仮定する。
  2. 13このようにして暗号通貨マイニングに参加するピアは台帳を同期させる。

V. Merkle-CRDTs: ペイロード付き Merkle-Clocks

定義 6. (Merkle-CRDT) Merkle-CRDT はノードが任意の CRDT ペイロードを伝送する Merkle-Clock である。

Merkle-CRDT は先に見た Merkle-Clock の特定をすべて保持している。ただしペイロードが収束するためにはペイロード自身が収束データ型 (CRDT) である必要がある。この利点は Merkle-Clock には順序情報と因果情報がすでに埋め込まれていることである。このような情報は CRDT オブジェクトに埋め込むか (通常は他の論理クロックの形式で)、信頼性の高いメッセージング層かｒ提供される必要がある。

したがって Merkle-CRDT ノードの実装は次のようになる: \[ (\alpha, P, \mathcal{C}) \] ここで \(\alpha\) はコンテンツ識別子、\(P\) は CRDT 特性を持つ非透明なデータオブジェクト、\(\mathcal{C}\) は子の識別子集合である。

A. オブジェクト単位の因果整合性とギャップ検出

Merkle-CRDT の有向リンクの性質は、イベントの順序でシステムの完全な因果履歴をたどることを可能にし、我々のシステムモデルを修正することなく設計によってオブジェクトごとの因果一貫性 (causal consistency) とギャップ検出 (gap detection) を保証するために必要なすべての特性を提供する。

つまり Merkle-CRDT は操作ベースの CRDT を運ぶのに非常に適しており、操作が失われたり無秩序に適用されることがないことを保証することができる14。

Merkle-CRDT で CRDT ペイロードを処理するタスクを容易にするために、次のセクションでは任意の CRDT 埋め込みオブジェクトのオブジェクトごとの因果一貫性を得るために使用できる一般的で単純な (最適化されていない) アンチエントロピーアルゴリズムを示す。

B. Merkle-CRDT の一般的なアンチエントロピー・アルゴリズム

定義 7. (Merkle-CRDT の一般的なアンチエントロピー・アルゴリズム)

現在の Merkle-CRDT DAG として \(\mathscr{M}_\alpha\) と \(\mathscr{M}_\beta\) を持つ Merkle-CRDT を使用する 2 つのレプリカをそれぞれ \(\mathcal{R}^A\) と \(\mathcal{R}^B\) とする。

  1. \(\mathcal{R}^B\) は新しい DAG ノード \((\beta,P,\{\theta\})\) を作成し、それを \(\mathscr{M}_\beta\) となる Merkle-CRDT に新しいルートとして追加することで新しいペイロードを発行する。

  2. \(\mathcal{R}^B\) はシステム内の残りのレプリカに \(\beta\) をブロードキャストする。

  3. \(\mathcal{R}^A\) は \(\beta\) のブロードキャストを受信し完全な \(\mathscr{M}_\beta\) を取得する。これはルート \(\beta\) から開始し、DAG-Syncer コンポーネントを使用して DAG を降下して、\(\mathscr{M}_\alpha\) にないすべてのノードをフェッチし、同時にそれらの CID を CID-集合 \(\mathcal{D}\) に収集することによって行われる。DAG の固有の特性を考えると \(\mathscr{M}_\alpha\) にすでにある CID については部分 DAG 全体をスキップすることができる。

  4. \(\mathcal{D}\) が空の場合はそれ以上のアクションは必要ない。\(\mathcal{R}^A\) はすでに \(\mathscr{M}_\beta\) 内のすべてのペイロードを処理しているはずである。これは \(\mathscr{M}_\beta \subseteq \mathscr{M}_\alpha\) であることを意味する。

  5. \(\mathcal{D}\) が空でない場合、\(\mathcal{D}\) 内の CID を Merkle-Clock が提要する順序でソートする。

    因果関係の配送が我々のシステムで要求されない場合、順序づけを省略することができる。\(\mathcal{D}\) 内の項目の量は、システムの同時実行の量と、2 つの Merkle-CRDT の分岐が許容される時間に依存するが、通常では少ないはずである。

  6. \(mathcal{R}^A\) は \(\mathcal{D}\) の CID に対応するノードに関連付するペイロードを低い方から高い方へ処理する。

  7. \(\alpha \in \mathcal{D}\) の場合、\(\mathscr{M}_\alpha \subseteq \mathscr{M}_\beta\) であり \(\mathscr{M}_\beta\) は \(\mathcal{R}^A\) の新しいローカル Merkle-CRDT となる。

  8. それ以外の場合、\(\mathscr{M}_\alpha \not\subset \mathscr{M}_\beta\), \(\mathscr{M}_\beta \not\subset \mathscr{M}_\alpha\) となる。\(\mathcal{R}^A\) は両方のノードをルートとして保持する。

C. 操作ベース Merkle-CRDTs

定義 8. 操作ベース Merkle-CRDT とは、ノードが操作ベースの CRDT ペイロードに埋め込まれたものである。

操作ベースの Merkle-CRDT は Merkle-CRDT の最も自然な応用である。操作の定義は簡単で可換であるだけで良いため、操作を行った順番に関係なくどのレプリカでも同じ状態になる。ただし、これは状態が収束するためにはすべての操作を受信する必要があることも意味する。信頼性の高いメッセージング層 [11] が収束の前提条件となるが、多数のレプリカ存在する現実のネットワークでは、メッセージが失われないことを保証することは通常不可能である。このため CRDT の実装には、因果ペイロードの追加、バッファリング、リトライ機構などの複雑な回避策が必要となり、単純な CRDT の実装であるはずがかなり複雑なものになってしまうだろう。

Merkle-DAG は、メッセージが常に順番に配信され、検証され、繰り返されたり削除されたりすることのないメッセージングレイヤーのすべての特性を提供する。したがって Merkle-CRDT はこれまで容易に使用できなかったコンテキストで操作ベースの CRDT を使用できるようにする。

これまで見てきたように、Merkle-DAG が埋め込まれているため各レプリカは DAG の欠けている部分のみを必要とし、ルートが分ればそれらをフェッチすることができる。これにはシステムに参加する新しいレプリカも含まれ、すべての操作をフェッチして適用できるようになる。完全なレプリカ集合をを把握しておく必要はなく、効率的なブロードキャストの責任は Broadcaster コンポーネントにある。

D. 状態ベース Merkle-CRDTs

定義 9. 状態ベースの Merkle-CRDT とは、ノードが状態ベースの CRDT ペイロードを埋め込まれたものである。

状態ベースの CRDT はすでにオブジェクトごとの因果一貫性を提供しており、設計により信頼性の低いメッセージ層に対処できるため、各 Merkle-CRDT ノードに完全な状態を埋め込むことは直感に反する。

さらに、最終的な状態は Merkle-CRDT ノード内のすべての状態のマージから得られるが、依然として DAG-Syncer コンポーネントはそれらの状態を保存する必要があり、大きな状態オブジェクトを扱う場合には法外な作業となる。とはいえ、Merkle-CRDT は因果メタデータを添付する必要性を取り除き、レプリカの数から切り離すことができるため、レプリカの数に比べてステートが非常に小さい状態ベースの CRDT にとっては興味深いかも知れない。

さらに興味深いアプローチとして、完全な状態をブロードキャストする代わりにより小さなセクション (デルタ) を送信できる \(\delta\)-CRDT [10] がある。これらのオブジェクトは \(\delta\)-mutation と呼ばれ、毛愚答操作のセマンティクスを変更することなく完全な状態と同じようにダウンストリームでマージすることができる。したがって複数のデルタを結合して \(\delta\)-group として知られるものを形成しブロードキャストのペイロードの効率を向上させることができる。[10] で指摘されているように "完全な状態は \(\delta\)-group の特別な (極端な) ものと見なすことができる"。

しかし \(\delta\)-CRDT の vanilla 形式では、メッセージが失われたときに整合性が無限に遅延し、状態ベースの CRDT オブジェクトごとの因果一貫性特性が失われる。これらの問題は [10] で示されているようにグループ化、ソート、配信の追跡、紛失した差分の再送信を行うアンチエントロピー・アルゴリズムを追加することで対処できるが、\(\delta\)-state-Merkle-CRDT の場合、アンチエントロピー・アルゴリズムおよび元のオブジェクトに付随する因果情報は必要ない。本質的に、このアプローチは \(\delta\)-state Merkle-CRDT を操作ベースの対応物に近づける。

  1. 14Merkle-Clock がイベントの厳密な半順序を提供することは以前に述べた。この場合、オブジェクトに適用される 2 つの非同期操作はクロックによってソート可能である。

VI. Merkle-CRDT の制約と最適化

A. Merkle-CRDT の制約

我々はこれまで従来の CRDT アプローチと比較して Merkle-CRDT が提供する様々な特性を説明することに焦点を絞ってきたが、Merkle-CRDT がもたらす本質的かつ実用的な制約についても強調する必要がある。

a) 増加し続ける DAG サイズ: Merkle-CRDT の最も明白な結果は、CRDT が通常ブロードキャストオブジェクトをマージ、適用、統合および破棄するのに対し、Merkle-CRDT は永久的な Merkle-DAG を構築することである。これまで見てきたようにこれは多くの有利な特性を提供するがいくつかの影響もある。

  • DAG のサイズは許容範囲を超えて大きくなる可能性がある。増加率はイベントの数とペイロードのサイズに依存する。これはブロックチェーンが時間と共に大きなサイズに成長するのとよく似ている15。例えば非バッチ実装では CRDT Key-Value ストアの実装に挿入するたびに新しい DAG ノードが生成される。したがってキーごとに追加の空間を消費することに形、小さなオブジェクトの場合は元のオブジェクト自体よりも大きくなる可能性がある。これは、例えばデータベース内の 1 つのキーを繰り返し更新する場合など、実際の状態がはるかに小さい場合に特に問題となる。場合によっては状態をすべての Merkle-CRDT 操作結果の圧縮として表現できるかも知れないが、これは次のポイントに繋がる。

  • レプリカが Merkle-DAG のみを保存し、そこから完全な状態を再構築できる (つまり空間を制約できる) ことが分っている場合、非常に大きな Merkle-DAG を含むレプリカを開始すると、たとえローカルで取得可能な場合であっても、完全な DAG を再処理する必要があるため非常に時間がかかる可能性がある。そうでなければ結果の状態と Merkle-DAG の両方に冗長な情報が保存されていることになる。

  • ゼロからの Merkle-CRDT 同期は可能であり、新しいレプリカが参加したときにシステムで自然に行われる。しかし Markle-DAG は成長し続けるだけではなく深く薄い傾向もある16。新しいレプリカはブロードキャスト操作からルート CID を学習し、そこから完全な DAG を解決する必要がある。薄さのため複数のブランチを並行してフェッチすることはできない。コールド同期にはスナップショットを送信する時間よりかなり長くかかる可能性があるため、この Merkle-DAG の埋め込み特性はほとんど価値がない。

非常に大きな DAG と遅い同期はシナリオによっては問題ではなく許容可能なトレードオフと見なすことができるが、"ガーベッジコレクション" と DAG 圧縮メカニズムを検討する必要性が強調される。

b) Merkle-Clock ソート: 2 つの Merkle-Clock をマージするには、それらが互いに含まれているかを比較し違いを見つける必要がある。これは DAG が大きく (またはかなり前から) 分岐している場合にコストのかかる操作となる可能性がある。

c) DAG-Syncer レイテンシ: レプリカは DAG-Syncer コンポーネントにオゾンしてメッセージング層との間でノードをフェッチおよび提供する。前述の通り Merkle-CRDT はメッセージの同期に賞されるメカニズム (DHT や PubSub など) に依存しないが、注意深く選択しないかぎりこのメカニズムにより同期遅延を引き起こす可能性がある。アプリケーションの要件によってはこの遅延を許容できる場合もあれば許容できない場合もある。

これらの制限が実際に与える影響はアプリケーションの要件によって異なる。特に Merkle-CRDT の採用を検討する場合、ユーザh i) ノード数と状態サイズ、ii) コールド同期までの時間、iii) 更新伝搬の遅延、iv) 想定するレプリカの総数、v) 想定するレプリカ集合の変更 (参加と離脱)、vi) 想定する同時イベントの量、という観点から Merkle-CRDT が最適なアプローチであるかを検討する必要がある。

B. Merkle-CRDT の最適化

a) 遅延 DAG ノード: レプリカが頻繁に更新を発行するシナリオでは、複数のペイロードをグループ化してからそれらすべてを含む単一ノードを発行することができる。このアプローチがいくつかの利点をもたらすことは明らかだが、これにはトレードオフが伴う。つまり更新がすぐに送信されないため更新の伝搬に時間がかかることになる。

b) 迅速な Merkle-DAG 包含チェック: ローカルレプリカ DAG とリモートレプリカ DAG をマージするには、一方の DAG に他方の DAG が含まれているかをチェックする必要がある。最初の DAG をたどって 2 番目の DAG のルートと一致するノード CID を探すことは可能だが、非効率的である。ローカル DAG の CID を、CID がローカル DAG の一部であるかを素早くチェックできる Key-Value ストアに格納することで作業が大幅に艱難になる17。ローカル DAG で包含チェックを行うためにリモート DAG をたどるとき、そのノードの子の CID をチェックしてローカル DAG の一部であるかを確認することができる。ただし、これは実装がノードのローカルストレージシステムを認識しアクセスできなければならないことを意味する。現在定義されている DAG-Syncer はローカルで利用可能なノードとリモートで利用可能なノードを区別することはできない。ブルームフィルタ、キャッシュ、およびいくつかのデータ構造も効率を向上させることができるが、これらは通常、選択されたストレージバックエンドの一部である。

アプリケーションに課せられる制約を今日できるのであれば、ペイロードに Version Vector を埋め込むことによっても同様の効果を実現できる。ペイロード間の Version Vector の比較は DAG をたどって実行する必要のない包含チェックである。

c) ブロードキャストペイロードの調整: 我々の標準的なアプローチでは新しいルートの CID のみを含めることによってブロードキャストのサイズを削減する。パブリッシングメカニズムは十分に複雑であるため、ペイロードが小さいほど常にメリットが得られる。

ただし一部のシステムでは新しい Merkle-DAG ノードをブロードキャストペイロードの一部として直接送信することが有益な場合もある。オフラインになったレプリカやメッセージの欠落したレプリカは将来の更新を受信して DAG を完成させたときに回復するためこの点では何の影響もない。ペイロードをブロードキャストすると (それが十分に小さいと仮定すれば) システム内の変更の伝播の待ち時間が短縮される可能性が高い。

d) Merkle-DAG のノードサイズの削減: CRDT 自体が必要としない冗長な情報を圧縮および削除することでペイロードのサイズを可能な限り削減することを試みることができる。例えば信頼できるレプリカからのものであることを保証するために CRDT のペイロードに署名する代わりに、ブロードキャストメッセージに署名をすることで Merkle-DAG から署名を省くことができる。

もう一つの選択肢は、ペイロード (またはその一部) を CID にして実際のコンテンツを参照することである。ペイロードが大きい場合、これには Merkle-DAG のサイズを大幅に縮小し DAG フェッチの効率を上げる可能性がある。これはペイロードの一部が同一で重複を排除できる場合や、データの一部に臨機応変にアクセスできる場合に関係する。

e) ノード内の追加ポインタ: 薄い DAG 問題を解決する一つの方法は、新しいノードを発行するときに DAG のより深い部分への参照を定期的に導入することである。この方法は基本的にノードに追加の子ノードを追加することである。これにより DAG の欠落した部分をフェッチする際の並列性が向上しトラバースが大幅に拘束される。追加のリンクの実際の数とそのリンク先はアプリケーションの要件に依存する。

上記の推奨事項は、前述の最適化されて否バージョンに比べて大きな利点をもたらす可能性があるため、いかなる Merkle-CRDT 実装でも考慮されるべきである。どの最適化がどの実装に適合するかは主にアプリケーションに依存する。DAG の圧縮とガーベッジコレクションについては今後の課題に譲るが、直感的には、すべてのレプリカが Merkle-DAG の一部を破棄することは、すべてのレプリカがそれを認識したことを確認する前に行うべきではないことに注意。このためには現在のレプリカ集合に関する知識を持つか外部の信頼できる情報源 (ブロックチェーンなど) を使用する必要がある。これは以前にはなかったシステム制約である。

  1. 15この論文を書いている時点でビットコインは 220GB 異常、イーサリウム (パリティ) は 165GB 以上を使用している。
  2. 16Merkle-DAG は多くの同時イベントがなければ薄くなり、そうでなければ分岐係数が高くなる。どちらの場合もレプリカから新しいイベントが発行されるたびに分岐が集約されるため DAG のウエストは細くなる。
  3. 17インメモリなどの高速な Key-Value ストアは通常高いメモリフットプリントペナルティを支払うことになるが、ディスクバックされたものは遅くなる。

VII. 結論

この論文では、自己検証と効率的な動機特性を備えた因果関係エンコード構造として Merkle-DAG にアプローチした。これにより Merkle-Clock の概念が導入され、Broadcaster コンポーネントでアナウンスされ、DAG-Syncer 機能でフェッチされるとすべてのレプリカで収束する状態ベースの CRDT として説明できることを示した。

我々は次に CRDT ペイロードを持つ Merkle-Clock として Merkle-CRDT を提示した。メッセージング層の保証がほとんどなく、オブジェクト単位の因果一貫性を提供する一方でレプリカ集合は動的で未知な可能性があるような状況で Merkle-CRDT がどのように機能するかを示した。Merkle-CRDT は IPDF エコシステムにおいて、データベースのロギング操作18、分散 P2P データベースである OrbitDB19、そのサーバレスアプリケーションである Orbit20、分散型の共同編集21、およびモバイル写真共有アプリケーション22などで広く使用されている。

Merkle-CRDT は収束するためにコンセンサスが必要な従来のブロックチェーンと、設計によって収束する CRDT 間の組み合わせであり、したがって両方の世界の良い面と悪い面を受け継いでいる。我々はこの研究によりこのテーマに関するさらなる研究のための良い基盤を築くことを望んでいる。

Appendix

Merkle-CRDT は、これまで定式化された居なかったとしても非常に直感的であり Merkle-DAG のよく知られ広く使われている特性に依存している。IPFS エコシステムのいくつかのプロジェクトではすでにそれらを使用しており23、Merkle-DAG にすべての操作ベース CRDT を埋め込んでいる。

  • ipfs-log24 は我々の知る限りここで説明されている Merkle-CRDT の現存する最初のインスタンスである。これは操作ベースの追記専用ログ CRDT (grow-only 集合と同様) を実装している。

  • ipfs-hyperelog25 は Merkle-DAG を構築し複製するユーティリティである。

  • Orbit DB26 は分散ピアツーピアデータベースである。様々なモデルに ipfs-log や他の CRDT を使用する。分散型のサーバレスチャットアプリケーションである Orbit27 の構築に使用されている。

  • Tevere28 は操作ベースの Merkle-CRDT Key-Value ストアである。

  • peer-crdt29 および peer-crdt-ipfs30 はカウンタ、集合、配列、レジスタ、テキスト (およびコンポーザブル CRDT) といった複数の CRDT の汎用的な操作 Merkle-CRDT 実装を提供する。

  • versidag31 は ipfs-log に似たバージョン情報を格納するための競合解決機能を備えたリンクログである。

  • PeerPad32 は peer-crdt と \(\delta\)-CRDT に基づくリアルタイム協調型テキストエディタである。

  • Textile.photos33 は写真用のモバイル分散型デジタルウォレットである。Textile Threads (v1) [20] は中央データベースなしにユーザグループが写真を共有することを可能にし Merkle-CRDT に基づいている。

  • go-ds-crdt34 は \(\delta\)-state Merkle-CRDT を使った Go による Key-Value 分散データストアの実装である。IPFS Cluster35 で使用されている。

  1. 18https://github.com/orbitdb/ipfs-log
  2. 19https://github.com/orbitdb/orbit-db
  3. 20https://github.com/orbitdb/orbit
  4. 21https://github.com/peer-base/peer-pad
  5. 22textile.photos
  6. 23dynamic data and capabilities ワーキンググループは次のトピックで多くの議論を開始している: https://github.com/ipfs/dynamic-data-and-capabilities
  7. 24https://github.com/orbitdb/ipfs-log
  8. 25https://github.com/noffle/ipfs-hyperlog
  9. 26https://github.com/orbitdb/orbit-db
  10. 27https://github.com/orbitdb/orbit
  11. 28https://github.com/ipfs-shipyard/tevere
  12. 29https://github.com/ipfs-shipyard/peer-crdt
  13. 30https://github.com/ipfs-shipyard/peer-crdt-ipfs
  14. 31https://github.com/ipfs/dynamic-data-and-capabilities/issues/50
  15. 32https://github.com/ipfs-shipyard/peer-pad
  16. 33https://www.textile.photos/
  17. 34https://github.com/ipfs/go-ds-crdt
  18. 35https://cluster.ipfs.io

References

  1. DAG Coin. https://dagcoin.org.
  2. GossipSub: A Unstructured, Secure Decentralised PubSub Protocol P2P for Overlays. https://research.protocol.ai/posts/201912-resnetlab-launch/PL-TechRep-gossipsub-v0.1-Dec30.pdf.
  3. IOTA. https://iota.org.
  4. IPLD: The InterPlanetary Linked Data Format. https://ipld.io/.
  5. libp2p: A Modular Network Protocol Stack for P2P Networks. https://libp2p.io/.
  6. Multiformats: Self-describing https://multiformats.io/. values for Future-proofing.
  7. Alexander Afanasyev, Zhenkai Zhu, Yingdi Yu, Lijing Wang, and Lixia Zhang. The story of chronoshare, or how ndn brought distributed secure file sharing back. In IEEE MASS, pages 525–530, 10 2015.
  8. José Bacelar Almeida, Paulo Sérgio Almeida, and Carlos Baquero Moreno. Bounded version vectors. In International Conference on Distributed Computing - ICDCS, volume 3274, pages 102–116, Tokyo, Japan, March 2004. Springer, Springer.
  9. Paulo Sérgio Almeida, Carlos Baquero, and Victor Fonte. Interval tree clocks. In Proceedings of the 12th International Conference on Principles of Distributed Systems, OPODIS ’08, pages 259–274, Berlin, Heidelberg, 2008. Springer-Verlag.
  10. Paulo Sérgio Almeida, Ali Shoker, and Carlos Baquero. Efficient statebased CRDTs by delta-mutation. CoRR, abs/1410.2803, 2014.
  11. Carlos Baquero, Paulo Sérgio Almeida, and Ali Shoker. Making operation-based CRDTs operation-based. In Proceedings of the First Workshop on Principles and Practice of Eventual Consistency, PaPEC ’14, pages 7:1–7:2, New York, NY, USA, 2014. ACM.
  12. Carlos Baquero and Nuno Preguiça. Why logical clocks are easy. ACM Queue, 14, April 2016.
  13. Petr Baudis. Current concepts in version control systems. CoRR, abs/1405.3496, 2014.
  14. Juan Benet. IPFS- content addressed, versioned, P2P file system (draft 3), 2014.
  15. Russell Brown, Sean Cribbs, Christopher Meiklejohn, and Sam Elliott. Riak dt map: A composable, convergent replicated dictionary. In Proceedings of the First Workshop on Principles and Practice of Eventual Consistency, PaPEC ’14, pages 1:1–1:1, New York, NY, USA, 2014. ACM.
  16. Russell Brown, Zeeshan Lakhani, and Paul Place. Big(ger) sets: decomposed delta CRDT sets in riak. CoRR, abs/1605.06424, 2016.
  17. Scott Chacon and Ben Straub. Pro Git. Apress, Berkely, CA, USA, 4th edition, 2018.
  18. Anton Churyumov. Byteball: A decentralized system for storage and transfer of value, 2016.
  19. Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo: Amazon’s highly available key-value store, 2007.
  20. Carson Farmer and Sander Pick. Textile Threads whitepaper... just kidding... a deeper look at the tech behind textile’s Threads protocol, October 2018.
  21. C. J. Fidge. Timestamps in message-passing systems that preserve the partial ordering. Proceedings of the 11th Australian Computer Science Conference, 10(1):56–66, 1988.
  22. Brent ByungHoon Kang, Robert Wilensky, and John Kubiatowicz. The hash history approach for reconciling mutual inconsistency. In Proceedings of the 23rd International Conference on Distributed Computing Systems, ICDCS ’03, pages 670–, Washington, DC, USA, 2003. IEEE Computer Society.
  23. Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558–565, July 1978.
  24. Tobias Landes. Tree clocks: An efficient and entirely dynamic logical time system. In Proceedings of the 25th IASTED International Multi-Conference: Parallel and Distributed Computing and Networks, PDCN’07, pages 375–380, Anaheim, CA, USA, 2007. ACTA Press.
  25. Ralph C. Merkle. A digital signature based on a conventional encryption function. In Carl Pomerance, editor, Advances in Cryptology — CRYPTO ’87, pages 369–378, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg.
  26. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2009.
  27. Geroge Neville-Neil. Time is an illusion. ACM Queue, 13(9), 2016.
  28. D. S. Parker, G. J. Popek, G. Rudisin, A. Stoughton, B. J. Walker, E. Walton, J. M. Chow, D. Edwards, S. Kiser, and C. Kline. Detection of mutual inconsistency in distributed systems. IEEE Trans. Softw. Eng., 9(3):240–247, May 1983.
  29. Nuno M. Preguiça, Carlos Baquero, Paulo Sérgio Almeida, Victor Fonte, and Ricardo Gonçalves. Dotted version vectors: Logical clocks for optimistic replication. CoRR, abs/1011.5808, 2010.
  30. Nuno M. Preguiça, Carlos Baquero, and Marc Shapiro. Conflict-free replicated data types (CRDTs). CoRR, abs/1805.06358, 2018.
  31. Wentao Shang, Alexander Afanasyev, and Lixia Zhang. Vectorsync: Distributed dataset synchronization over named data networking. In Proceedings of the 4th ACM Conference on Information-Centric Networking, ICN ’17, page 192–193, New York, NY, USA, 2017. Association for Computing Machinery.
  32. Wentao Shang, Yingdi Yu, Lijing Wang, Alexander Afanasyev, and Lixia Zhang. A survey of distributed dataset synchronization in Named Data Networking. Technical Report NDN-0053, NDN, May 2017.
  33. Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. A comprehensive study of Convergent and Commutative Replicated Data Types. Research Report RR-7506, Inria– Centre Paris-Rocquencourt ; INRIA, January 2011.
  34. Lixia Zhang, Alexander Afanasyev, Jeffrey Burke, Van Jacobson, kc claffy, Patric Crowley, Christos Papadopoulos, Lan Wang, and Beichuan Zhang. Named Data Networking. ACM Computer Communication Reviews, June 2014.
  35. Zhenkai Zhu and Alexander Afanasyev. Let’s chronosync: Decentralized dataset state synchronization in named data networking. In Proceedings - International Conference on Network Protocols, ICNP, pages 1–10, 10 2013.

翻訳抄

分散システムにおけるデータの同期を効率的に行う、Merkle-DAG と CRDT を組み合わせたデータ構造である Merkle-CRDTs に関する 2020 年の論文。

  1. SANJUAN, Hector, et al. Merkle-crdts: Merkle-dags meet crdts. arXiv preprint arXiv:2004.00107, 2020.