私は分散システムの初心者であり、CRDT の概念について洞察を得ようとしています。私はそれが3つの表記法を持っていることを認識しています:
Conflict-free Replicated Data Type
Convergent Replicated Data Type
Commutative Replicated Data Type
分散システムで CRDT を使用する例を教えてください。よろしくお願いします。
7570 次
3 に答える
33
CRDT は、Marc Shapiro の作品に触発されています。分散コンピューティングでは、競合のない複製データ型 (略して CRDT) は、強力な結果整合性 (SEC) と単調性 (ロールバックの不在) を実現するために使用される、特別に設計されたデータ構造の一種です。SEC を確保するには、操作ベースの CRDT と状態ベースの CRDT という 2 つの代替ルートがあります。
異なるレプリカの CRDT は互いに分岐する可能性がありますが、最終的にそれらを安全にマージして、最終的に一貫した値を提供できます。つまり、CRDT には、冪等、交換可能、結合可能なマージ メソッドがあります。
一方が他方をエミュレートできるため、2 つの選択肢は同等ですが、操作ベースの CRDT では、通信ミドルウェアからの追加の保証が必要です。CRDT は、ネットワーク内の複数のコンピューター間でデータを複製するために使用され、リモート同期を必要とせずに更新を実行します。これにより、従来の結果整合性テクノロジを使用するシステムではマージ競合が発生しますが、CRDT は競合が数学的に不可能になるように設計されています。CAP 定理の制約の下で、これらは、利用可能な/パーティション トレラント (AP) 設定に対して最も強力な一貫性保証を提供します。
それらが使用されるいくつかの例
Riak は CRDT の最も人気のあるオープン ソース ライブラリであり、Bet365 と League of Legends で使用されています。以下は、Riak をサポートする便利なリンクです。
1- Bet365 (Erlang と Riak を使用) http://www.erlang-factory.com/static/upload/media/1434558446558020erlanguserconference2015bet365michaelowen.pdf
2- League of Legends は、ゲーム内チャット システムに Riak CRDT 実装を使用しています (これは、750 万の同時ユーザーと 1 秒あたり 11,000 メッセージを処理します)。
3- LWW タイムスタンプ セットをサポートする SoundCloud によって実装された Roshi: -ブログ投稿: https://developers.soundcloud.com/blog/roshi-a-crdt-system-for-timestamped-events
于 2016-03-15T13:16:38.573 に答える
13
CRDT は Math を使用して、コンセンサスや関連するレイテンシー/非可用性について心配することなく、分散クラスター全体で一貫性を確保します。
CRDT がいつでも取ることができる値のセットは、最小上限関数 (LUB) を持つ POSET (部分的に順序付けられたセット) である半格子 (具体的には結合半格子) のカテゴリに分類されます。
簡単に言えば、POSET は、すべてが比較できるわけではないアイテムのコレクションです。たとえば、ペアの配列:は <ですが{(2,4), (4, 5), (2, 1), (6, 3)}、比較することはできません(1 つの要素が大きく、もう 1 つの要素が小さいため)。さて、半格子は与えられた 2 つの対から、たとえ 2 つを比較できなくても、両方より大きい要素 (LUB) を見つけることができる POSET です。(2,4)(4,5)(6,3)
もう 1 つの条件は、このデータ型への更新が増加する必要があることです。CRDT の状態は単調に増加し、クライアントは状態のロールバックを観察しません。
この優れた記事では、上記で使用した配列を例として使用しています。これらの値を維持する CRDT の場合、2 つのレプリカが と の間(4,5)でコンセンサスを達成しようとしている場合、コンセンサスとして(6,3)LUB = を選択し、(6,5)両方のレプリカをそれに割り当てることができます。値が増加しているため、これは落ち着くのに適した値です。
CRDT がレプリカ間で相互に同期を維持する方法は 2 つあります。定期的に状態を転送する方法 (収束レプリケート データ型) と、取得した更新 (デルタ) を転送する方法 (可換レプリケート データ型) です。前者はより多くの帯域幅を必要とします。
SoundCloud のRoshiは良い例です (ただし、開発中ではないようです)。タイムスタンプに関連付けられたデータを保存します。タイムスタンプは明らかに増加します。a=b means b=aタイムスタンプが保存されているものよりも小さいか等しい更新は破棄されます。これにより、冪等性 (反復書き込みは問題ありません) と交換性 (順不同の書き込みは問題ありません) が保証されます。update2 の後に update1)
read-repair書き込みはすべてのクラスターに送信され、特定のノードが速度低下や分割などの問題のために応答しない場合、値が確実に収束するように を介して後で追いつくことが期待されます。収束は、前述のように 2 つのプロトコルを介して達成でき、状態または更新を他のレプリカに伝達します。老師は前者だと思います。の一部としてread-repair、レプリカは状態を交換し、データが半格子特性に準拠しているため、収束します。
PS。CRDT を使用するシステムは結果整合性があります。つまり、CAP 定理で AP (高可用性と分割耐性) を採用しています。
于 2017-10-12T01:02:43.567 に答える
3
頭字語のこれら 3 つの展開はすべて、基本的に同じことを意味します。
異なるシーケンスで適用された同じ操作が同じ結果を生成 (収束) する場合、CRDT は収束します。つまり、操作は交換可能です。これは交換可能な RDT です。操作を異なる順序で適用しても同じ結果が得られる理由は、操作に競合がないためです。
したがって、CRDT は、3 つの展開のどれを使用しても同じことを意味しますが、個人的には "Convergent" の方が好きです。
于 2015-12-10T02:21:10.207 に答える