Dynamo

Cassandraは、一貫性のあるハッシュと呼ばれる特殊な形式のハッシュを使用して、ストレージノード全体にデータをパーティショニングします。単純なデータハッシュでは、通常、キーのハッシュをバケット数で割った余りを取ることで、キーをバケットに割り当てます。たとえば、単純なハッシュを使用してデータを100個のノードに分散したい場合は、すべてのノードを0から100の間のバケットに割り当て、入力キーの100を割った余りをハッシュし、関連付けられたバケットにデータを保存します。ただし、この単純なスキームでは、単一のノードを追加すると、ほぼすべてのマッピングが無効になる可能性があります。

代わりにCassandraは、すべてのノードを連続ハッシュリング上の一致以上のトークンにマッピングし、キーをリングにハッシュして、Chordアルゴリズムと同様に、リングを一方向に「歩く」ことで所有権を定義します。一貫性のあるハッシュと単純なデータハッシュの主な違いは、ハッシュするノード（バケット）の数が変化した場合、一貫性のあるハッシュはキーのほんの一部を移動するだけでよいということです。

たとえば、均等に配置されたトークンを持つ8つのノードのクラスタがあり、レプリケーションファクタ（RF）が3の場合、キーの所有ノードを見つけるには、まずそのキーをハッシュしてトークンを生成し（これはキーのハッシュにすぎません）、次にリングを時計回りに「歩いて」3つの異なるノードに遭遇するまで続けます。その時点で、そのキーのすべてのレプリカが見つかったことになります。このgRF = 3の8つのノードのクラスタの例は、次のように視覚化できます。

Dynamoのようなシステムでは、キーの範囲（トークン範囲とも呼ばれる）が同じ物理ノードのセットにマッピングされることがわかります。この例では、トークン1を除外してトークン2を含むトークン範囲に該当するすべてのキー（grange（t1、t2]）は、ノード2、3、4に保存されます。

単純な単一トークンの一貫性のあるハッシュは、データを分散させるための多くの物理ノードがある場合はうまく機能しますが、均等に配置されたトークンと少数の物理ノードでは、インクリメンタルスケーリング（容量のわずかなノードの追加）は、リングのバランスを保つことができる新しいノードのトークン選択がないため、困難です。Cassandraは、トークンの不均衡がリクエスト負荷の不均一につながるため、トークンの不均衡を回避しようとします。たとえば、前の例では、不均衡を引き起こすことなく9番目のトークンを追加する方法はありません。代わりに、既存の範囲の中点に8トークンを挿入する必要があります。

Dynamo論文では、この不均衡問題を解決するために「仮想ノード」を使用することを推奨しています。仮想ノードは、トークンリング内の複数のトークンを各物理ノードに割り当てることで問題を解決します。単一の物理ノードがリング内で複数の位置を取れるようにすることで、小規模なクラスタをより大きく見せることができ、したがって単一の物理ノードを追加した場合でも、さらに多くのノードを追加したように見せることができます。つまり、単一のノードを追加した場合でも、より多くのリングネイバーからより小さなデータを取得できます。

Cassandraは、これらの概念を処理するためにいくつかの用語を紹介します。

トークンからエンドポイントへのマッピングにより、Cassandraがどのリング位置がどの物理エンドポイントにマッピングされるかを追跡するトークンマップが発生します。たとえば、次の図では、すべてのノードに2つのトークンを割り当てることで、4つの物理ノードのみを使用して8つのノードのクラスタを表すことができます。

物理ノードごとの複数のトークンには、次の利点があります。

ただし、複数のトークンにはデメリットもあります。

Cassandra 2.xでは、利用可能なトークン割り当てアルゴリズムはランダムなトークンを選択するものであり、バランスを保つためにはノードあたりのデフォルトのトークン数を256と非常に高くする必要がありました。これにより、多くの物理エンドポイントが結合され、可用性のリスクが増加しました。そのため、3.x +では、リングが最適にバランスされるように、より少ない数の物理ノードあたりのトークンでトークンをインテリジェントに選択する新しい決定論的なトークンアロケータが追加されました。

Cassandraはプラグ可能なレプリケーション戦略をサポートしており、特定のトークン範囲のレプリカとして機能する物理ノードを決定します。データのすべてのキースペースには、独自のレプリケーション戦略があります。すべての本番環境デプロイメントではNetworkTopologyStrategyを使用する必要があり、SimpleStrategyレプリケーション戦略は、クラスターのデータセンターレイアウトをまだ知らないテストクラスターでのみ役立ちます。

Cassandraは、データの最終的な整合性を保証するために、ミューテーションタイムスタンプバージョン管理を使用します。具体的には、システムに入るすべてのミューテーションは、クライアントクロックから、またはクライアント提供のタイムスタンプがない場合は、コーディネーターノードのクロックから提供されたタイムスタンプを使用します。更新は、後書き優先の競合解決ルールに従って解決されます。Cassandraの正確さはこれらのクロックに依存するため、NTPなどの適切な時間同期プロセスが実行されていることを確認してください。

Cassandraは、CQLパーティション内のすべての行のすべての列に個別のミューテーションタイムスタンプを適用します。行はプライマリキーによって一意であることが保証されており、行内の各列は、後書き優先の競合解決に従って同時ミューテーションを解決します。これは、パーティション内の異なるプライマリキーへの更新が、実際には競合なしで解決できることを意味します。さらに、マップやセットなどのCQLコレクションタイプは、この同じ競合のないメカニズムを使用します。つまり、マップとセットへの同時更新も解決されることが保証されます。

Cassandraは、整合性レベルを通じて、整合性と可用性の間の操作ごとのトレードオフをサポートしています。Cassandraの整合性レベルは、オペレーターが読み取り（R）および書き込み（W）に参加する必要があるノード数をレプリケーションファクター（N）よりも大きく構成できるDynamoのR + W > N整合性メカニズムのバージョンです。Cassandraでは、代わりに、オペレーターがレプリケーションファクターを知らなくてもRとWの動作を選択できる一般的な整合性レベルのメニューから選択します。一般に、書き込み整合性レベルとのクォーラム交差を保証するのに十分なノードが読み取り整合性レベルに含まれている場合、書き込みは後続の読み取りに表示されます。

次の整合性レベルを利用できます

書き込み操作は、整合性レベルに関係なく、常にすべてのレプリカに送信されます。整合性レベルは、コーディネーターがクライアントに応答するまでに待機する応答数を制御するだけです。

読み取り操作の場合、コーディネーターは通常、整合性レベルを満たすのに十分なレプリカにのみ読み取りコマンドを発行します。この例外の1つは、元のレプリカが指定された時間内に応答しなかった場合に、投機的な再試行が余分なレプリカに冗長な読み取り要求を発行する可能性がある場合です。

ゴシップは、Cassandraがエンドポイントメンバーシップやノード間ネットワークプロトコルのバージョンなどの基本的なクラスタブートストラップ情報を伝播する方法です。Cassandraのゴシップシステムでは、ノードは自分自身に関するだけでなく、自分が知っている他のノードに関する状態情報も交換します。この情報は、(世代、バージョン)タプルのベクトルクロックでバージョン管理されます。ここで、世代は単調なタイムスタンプであり、バージョンはほぼ毎秒増分する論理クロックです。これらの論理クロックを使用すると、Cassandraゴシップはゴシップメッセージに提示された論理クロックを調べるだけで、古いバージョンのクラスタ状態を無視できます。

Cassandraクラスタ内のすべてのノードは、ゴシップタスクを独立して定期的に実行します。毎秒、クラスタ内のすべてのノードが

オペレーターが最初にCassandraクラスタをブートストラップするとき、特定のノードをシードノードとして指定します。どのノードもシードノードになる可能性があり、シードノードと非シードノードの唯一の違いは、シードノードが他のシードノードを確認せずにリングにブートストラップできることです。さらに、クラスタがブートストラップされると、上記のステップ4により、シードノードはゴシップのホットスポットになります。

非シードノードがクラスタにブートストラップするために少なくとも1つのシードノードに接続できる必要があるため、複数のシードノードを含めるのが一般的です。多くの場合、ラックまたはデータセンターごとに1つです。シードノードは、既存の既製のサービスディスカバリメカニズムを使用して選択されることがよくあります。

現在、ゴシップはトークンメタデータとスキーマバージョン情報も伝播します。この情報は、データ移動とスキーマプルをスケジュールするためのコントロールプレーンを形成します。たとえば、ノードがゴシップ状態のスキーマバージョンの不一致を検出した場合、他のノードとのスキーマ同期タスクをスケジュールします。トークン情報がゴシップを介して伝播されるため、どのエンドポイントがどのデータを所有しているかをノードに教えるためのコントロールプレーンでもあります。

ゴシップはリングメンバーシップの基礎を形成しますが、障害検出器は最終的にノードがUPであるかDOWNであるかについての決定を行います。Cassandraのすべてのノードは、Phi Accrual Failure Detectorのバリアントを実行しており、各ノードはピアノードが利用可能かどうかを常に独立して決定しています。この決定は、主に受信したハートビート状態に基づいています。たとえば、ノードが一定時間、ノードからの増加するハートビートを確認しない場合、障害検出器はそのノードを「有罪」と判断します。その時点で、Cassandraは読み取りのルーティングを停止します（書き込みは通常ヒントに書き込まれます）。ノードが再びハートビートを開始すると、Cassandraは連絡を取り、接続しようとします。通信チャネルを開くことができれば、そのノードを利用可能としてマークします。

Cassandraは、オペレーターからのデコミッション操作、またはreplace_address_first_bootオプションでブートストラップする新しいノードを介して明示的な指示がない限り、ゴシップ状態からノードを削除することはありません。この選択は、データが不必要に再バランスすることなく、Cassandraノードが一時的に失敗することを許可するために意図的です。これは、トークン範囲の複数のレプリカが同時に移動する同時範囲移動を防ぐのにも役立ちます。これは、単調整合性に違反する可能性があり、データ損失を引き起こす可能性さえあります。

Cassandraは、Dynamoと同様に、SQLリレーショナルデータベース管理システム（RDBMS）で一般的なクロスパーティショントランザクションを提供しないことを選択します。これにより、プログラマーにシンプルで読みやすく、書きやすいAPIが提供され、複数のノードにまたがるマルチパーティショントランザクションは実装が非常に難しく、通常は非常にレイテンシが高いため、Cassandraは水平方向にスケールするのが容易になります。

代わりに、Cassandraは、単一パーティション操作に対して、高速で一貫性があり、任意のスケールでのレイテンシを提供することを選択し、プライマリキーフィルターに基づいてパーティション全体またはパーティションのサブセットのみの取得を可能にします。さらに、Cassandraは軽量トランザクションCQL APIを介して単一パーティションの比較およびスワップ機能をサポートします。

Cassandraは、Dynamoとは少し異なり、「単純なキーと値」ストアよりも洗練されていますが、SQLリレーショナルデータモデルよりも大幅に複雑でないストレージインターフェースを選択しています。Cassandraは、ワイドカラムストアインターフェースを提供します。このインターフェースでは、データのパーティションに複数の行が含まれ、各行には個別に型指定された柔軟な列セットが含まれています。すべての行は、パーティションキーと1つ以上のクラスタリングキーによって一意に識別され、すべての行は必要に応じて多数の列を持つことができます。

これにより、ユーザーは新しい要件が発生したときに、既存のデータセットに新しい列を柔軟に追加できます。スキーマの変更には、メタデータの変更のみが関与し、ライブワークロードと完全に並行して実行されます。したがって、ユーザーは、クエリのパフォーマンスが低下しないことを確信しながら、既存のCassandraデータベースに列を安全に追加できます。