パクシやいかだの代わりにCRDTのようなものを使用するのはいつ良い考えですか？
質問する
10029 次
7 に答える
35
CRDTのようなものを使用できる場合は、そうしてください。はるかに優れたパフォーマンスが得られるはずです。また、オフラインで作業して後でマージするなどの興味深いユースケースも可能になります。ただし、CRDTが機能するように設計できるとは限りません。その場合、paxosはあなたのために難しい問題を解決することができます。
ただし、paxosを使用することにした場合でも、通常は、paxosアルゴリズムを介して直接実行される作業量を制限する必要があります。代わりに、パフォーマンス上の理由から、マスターの選択などの必要な操作のためにpaxosを予約し、複製されたマスターセットアップにほとんどの決定を処理させる必要があります。（高スループット環境では、マスターは特定のシャードに対する責任を特定の子に委任するようなことを行う可能性があります。これは相互に複製されます。マスターをボトルネックにしないでください...）
とは言うものの、実際にそれを行うよりも、パクシの魔法の杖を振ると主張する方がはるかに簡単です。その観点から、 http：//static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/archive/chubby-osdi06.pdfは、現実の世界が抱える困難についての興味深い説明であることがわかります。paxosの実装が発生する可能性があります。
于 2012-06-29T00:13:04.477 に答える
15
于 2013-11-12T13:19:51.497 に答える
9
CRDTとPaxosには異なる目標があり、異なるシナリオで使用されます。それらには、プログラマーが並行性/レプリケーションに対処するのに役立つという共通点があります。CRDTは、同時更新が発生することを前提としたデータ型です。Paxosは、それらに全順序を適用することによって、それらが実行しないことを強制するプロトコルです。 これをもっと詳しく見てみましょう。
2つの異なる場所で複製された複製セットがあるとしましょう。
Paxosを使用すると、セットへの書き込みがすべてのレプリカによって同じ順序で実行されることが保証されます。より一般的には、セットの状態がどのように変化するかについて、すべてのレプリカが同意することを保証します。
たとえば、user1がreplica1でupdate1を実行し、同時にuser2がupdate2を実行し、replica2でelement2を追加する場合、Paxosはレプリカにそれらの更新の特定の順序に同意させるか、場合によっては1つを選択することに同意します。 2つの更新のうち、2番目の更新を破棄します。これは、使用方法と達成したい内容によって異なります。たとえば、Paxosの結果がupdate1がupdate2の前に来る場合、すべてのレプリカはその順序でセットを更新します。結果として、これらの更新と同時にセットを読み取るユーザーは、（どのレプリカで）読み取るかに関係なく、セットの次の状態のみを監視できます（最初にセットが空であると想定）。
{} （空集合）
{element1}
{element1、element2}
さらに、これらの状態はこの順序でのみ表示されます。つまり、セットの状態が{element1、element2}（すべてのレプリカで）になると、それ以降の読み取りでは{}または{element1}は返されません。
良い面：このセットは、複製されないセットと同等であるため、簡単に推論できます。
マイナス面：使用不可：レプリカが相互に通信できない場合（ネットワークパーティション）、合意がないため、セットを更新できません。低パフォーマンス、高遅延：契約では、クライアントに応答する前にレプリカを同期する必要があります。これにより、レプリカ間のレイテンシーに比例したレイテンシーが発生します。
CRDTの保証は弱くなります。CRDTセットは、シーケンシャルなシングルコピーセットと同等ではありません。レプリカの更新方法について合意または全順序がないことを前提としています。
CRDTは、セットの両方のレプリカが同じ更新を確認した場合（それらが表示される順序に関係なく）、同じ状態を示すことを保証します。レプリカは収束します。
2人のユーザーが同時に更新を実行する例では、セットの操作を注文するためにPaxosを実行しないシステム（これは、たとえば、最終的または因果整合性の下で発生します）は、replica2がelement2を追加している間にreplica1がelement1を追加できるようにします
したがって、replica1の状態は次のようになります。{element1}
そして、replica2の状態は次のようになります：{element2}
この時点で、レプリカは分岐します。後で、レプリカが同期すると、更新が交換され、最終的に次の状態が表示されます。
Replica1の状態は次のようになります：{element1、element2}
Replica2の状態は次のようになります：{element2、element1}
この時点で、レプリカは収束しています。
これらの更新と同時にセットを読み取るユーザーは、読み取る場所（どのレプリカ）に応じて、セットの次の状態を観察できます（最初にセットが空であると想定）。
{} （空集合）
{element1}（replica1から読み取った場合）
{element2}（replica2から読み取った場合）
{element1、element2}
{element2、element1}
マイナス面：このセットは、シーケンシャルセットでは発生しなかった状態を示しているため、推論するのが困難です。この例では、セットへの2つの同時追加の場合のみを観察しました。これは簡単です。同時追加と削除はより複雑ですさまざまな問題を持つ多くのデータ型があります。
良い面：高可用性：レプリカが相互に通信できない場合（ネットワークパーティション）、セットを更新できます。レプリカは、接続し直したときに同期されます。高性能、低遅延：レプリカは、クライアントに応答した後、すぐにクライアントに応答し、バックグラウンドで同期します。
于 2016-10-12T10:55:45.930 に答える
4
CRDTTreedocの例には欠陥があります。2つのシステムが同じキーで同時に挿入する場合、各ノードには明確化機能が必要です。
これが発生した後、システムが別の同一のキーを挿入する必要があるが、曖昧さ回避の順序を制御する必要があるため、システムが同一のキーを持ち、曖昧さを解消するエントリの間に挿入することはできなくなります。曖昧さ回避剤は密集していないため、これが常に可能であるとは限りません。曖昧さ回避がさらに別のツリーである場合、1つの問題を解決しますが、さらに深いところにある別の競合解決メカニズムが必要になります...など。
この言及されていない問題に加えて、メタデータを整理するために2フェーズコミットを実行する必要があるという事実により、CRDTはまだ進行中の作業であると私は思います。
于 2014-05-12T13:13:51.147 に答える
2
私たちが持っている複数のメトリックがあります：
- スループット（CRDTまたはPaxosに関係なく、すべての要求が最終的にすべてのレプリカに複製されるため、CRDTとPaxosは同じです）。
- レイテンシー（CRDTは少数のレプリカに書き込むため、Paxosよりも優れています）。
- 信頼性（CRDTは、状態が失われる可能性のある少数のレプリカ（多数派よりも少ない）に書き込むため、Paxosよりも弱いです）。
- 一貫性（CRDTは同期ポイントなしで同時書き込みを許可するため（基本的に重複するレプリカがない）、Paxosよりも弱いですが、Paxos書き込みでは、シリアル化を行うために常に重複するレプリカが必要です）。
私の提案は、レプリカが互いに遠くない場合（たとえば、データセンター内）にPaxosを使用し、ネットワークのパーティション分割が通常の場合（たとえば、切断されたモバイル）にCRDTを使用することです。
于 2014-06-19T09:35:39.233 に答える
1
@btillyによる応答へのコメント：
このトピックの質問は、一貫性のさまざまなモデル、つまりデザインパターンに関連しています。
- CRDTは、アルゴリズムの結果整合性ファミリに関連しています。
- PAXOSファミリーのアルゴリズムは、強一貫性/線形性（クライアントからサーバーへの同期）に関連しています。
- RAFTは、アルゴリズムと一貫性の点でPAXOSと同等ですが、実装が簡単であると考えられています。
CRDTとPaxosは非常に異なるものであり、アーキテクチャ要件に基づいて使用法を決定する必要があります。それを処理する最良の方法は、それらのアルゴリズムが正常に適用されたユースケースを確認することだと思います。
使用パターン：
CRDTは、クライアント（つまり、モバイルデバイス）とサーバー間のデータ同期、リアルタイムの共同編集、dist-db実装での値の同期、および結果整合性が良好なその他すべての場合に使用できます。
PAXOSは主に、システムインフラストラクチャをサポートする独自のシステム（つまりChubby）で使用されるか、BigTable、Datastore、Spinnaker、Spannerなどの分散データベースシステムで同期を実装するために使用されます。
RAFTは、ETCD、領事、...などのOSSインフラストラクチャプロジェクトでより人気があります。
（CockroachDBとTiDBが何に基づいているか覚えていない）
BFTもありますが、使用量は少なくなります。
ps PAXOS！=ZooKeeper。ZooKeeperは、ZABと呼ばれる異なるアルゴリズムを使用し、複製された状態マシンではありませんが、単一のライターとリラックスした読み取りモデルを備えた複製されたスナップショットマシンです。GoogleのChubbyはPaxosをベースにしていますが、独自仕様です。
pssPAXOSがここ数年どのように進化しているかは興味深いです。過去20年間で、エッジケース、クォーラムサイズ、およびクラスターの再構成のさまざまな最適化を処理する多くのバリアントが発明されました。
于 2018-06-18T08:20:53.957 に答える
-2
それが適切であるときはいつでも。ただし、PaxOSは、スループットが通常CRDTと同じであるため、それほど悪くはありません。信頼性がはるかに高いことは言うまでもありません（CRDTは状態を失う可能性があります）。また、レイテンシは、過半数を必要とするだけなので、それほど悪くはありません。レプリカのすべてではなく返信します。
于 2014-02-24T03:40:30.383 に答える