大規模分散ストレージ分散プルーニングシステム

分散ファイルシステムの保存対象は主に非構造化データですが、実際のアプリケーションでは、構造化データや半構造化データの保存ニーズが多くあります。分散キー値システムは、私たちがよく知っている分散データベース システムとは異なるストレージ アプリケーションです。単純な関係を持つ半構造化データを保存するために使用されます。

分散キー値システムでは、半構造化データは、<キー、値、タイムスタンプ> キーと値のペアで構成されるオブジェクトにカプセル化されます。キーは一意の識別子です。値は属性値であり、テキスト、画像、空など任意の型にすることができます。タイムスタンプは、データの複数のバージョンをサポートできるタイムスタンプです。分散キー値システムは、キーと値のペアで保存されます。その構造は固定されていません。各タプルには異なるフィールドを含めることができ、必要に応じてキーと値のペアを追加できます。そのため、固定された構造に限定されず、適用範囲が広く、拡張性に優れています。

[[207789]]

分散キー値システムは、単一の <キー、値、タイムスタンプ> キー値ペアの追加、削除、クエリ、および変更をサポートします。 PC サーバー クラスター上で実行でき、オンデマンドのクラスター拡張を実現して大規模データを処理できます。また、データのバックアップを通じてフォールト トレランスを確保し、データ分割の複雑さとコストを回避します。

一般に、ストレージ データ構造の観点から見ると、分散キー値システムは従来のハッシュ テーブルに似ています。違いは、分散キー値システムでは、クラスター内の複数のストレージ ノードへのデータの分散をサポートしていることです。分散キー値システムでは、データ バックアップの数を構成し、データのすべてのコピーを異なるノードに保存できます。異常によりノードが正常にサービスを提供できなくなった場合、残りのノードが引き続きサービスを提供します。

次に、業界で主流となっている分散型キーバリューシステムのアーキテクチャモデルを見てみましょう。

アマゾンダイナモ

Dynamo は、AWS 上の最も基本的な分散ストレージ アプリケーションの 1 つであり、AWS が最初にリリースしたクラウド サービスの 1 つです。これは AWS の S3 上に構築されており、分散型ノードベースの P2P アプローチを採用しています。このモデルを採用しているもう一つのサービスは、Facebook が立ち上げた Cassandra です。

1. データ配信

Dynamo は、改良された一貫性のあるハッシュ アルゴリズムを使用します。各物理ノードには、パフォーマンスの違いに基づいて複数のトークンが割り当てられ、各トークンは「仮想ノード」に対応します。すべてのノードは、ゴシップ プロトコルを通じて、一定の間隔 (たとえば 1 秒) で他のノードから通信するノードを選択します。接続が成功すると、両者は保存されているクラスター情報を交換します。

ゴシップ プロトコルは、P2P システム内の自律ノードによって使用され、クラスターのノード ステータスや負荷状態など、クラスター全体の理解を調整します。シード ノードが存在するため、新しいノードが参加するのは比較的簡単です。新しいノードが参加すると、まずシード ノードとクラスター情報を交換して、クラスター全体を理解します。

2. 一貫性と複製

一般的に言えば、マシン K+i がクラッシュしてから永久に故障したと判断されるまでの時間はそれほど長くなく、累積された書き込み操作もそれほど多くはありません。 Merkle ツリーを使用すると、マシンのデータ ファイルをすばやく同期できます。 Dynamo は競合を解決するためにベクトル ロック テクノロジを導入します。この戦略は、クラスター内のノード間のクロック同期アルゴリズムに依存しますが、精度を完全に保証することはできません。 Dynamo は結果整合性のみを保証します。複数のノード間の更新順序が一貫していない場合、クライアントは期待どおりの結果を読み取れない可能性があります。

3. フォールトトレランス

コアメカニズムは、データ転送+マークルツリー同期+読み取り修復です。

Dynamo は、データの読み取りと書き込みに、弱いクォーラム (Sloppy クォーラム) と呼ばれるメカニズムを使用します。これには、W、R、および N という 3 つのパラメーターが含まれます。W は、書き込み操作を正常に実行するために書き込む必要があるコピーの最小数を表し、R は、読み取り操作を正常に実行するためにサーバーがユーザーに返す必要があるコピーの最小数を表し、N は各データ ストアのコピー数です。ダイナモにはR+W〉Nが必要です。この要件を満たすことで、ユーザーはデータを読み取るときに常に最新バージョンのデータを取得できるようになります。

一時的な障害の場合、ノードに問題が発生すると、ノードの値が「同じグループ」内の次の正常なノードに送信され、障害が発生したノードの場所がこのデータ コピーのメタデータに記録され、データの返却が容易になります。その後、このノード上の一時スペースにデータが保存され、処理されます。同時に、ノードは障害が発生したノードも監視します。障害が発生したノードが再び使用可能になると、保存されていた最新のデータがそのノードに戻され、ノード自身が開いた一時領域のデータは削除されます。

永続的な障害が発生した場合、Dynamo はデータの同期をチェックして維持する必要があります。 Dynamo は、データの同期を確実にするために、アンチエントロピー プロトコルと呼ばれる方法を使用します。データ同期検出中に送信する必要があるデータの量を削減し、検出プロセスを高速化するために、Dynamo は Merkle ハッシュ ツリー テクノロジを使用します。各仮想ノードは 3 つの Merkle ツリーを保存します。つまり、キー値間隔ごとに Merkle ツリーが確立されます。 Dynamo の Merkle ハッシュ ツリーのリーフ ノードには、各データ パーティション内のすべてのデータに対応するハッシュ値が格納され、親ノードはそのすべての子ノードのハッシュ値です。

4. 負荷分散

改良された一貫性のあるハッシュ+仮想ノードモードを採用します。

従来の一貫性ハッシュ アルゴリズムでは、サービス ノードはハッシュ リング上のポイントに 1 対 1 で対応します。ここで問題となるのは、各ノードの負荷が最終的に不均一になり、調整できないことです。 Dynamo では、サービス ノードがハッシュ リング上に複数の仮想ノードを持つことができるため、各サービス ノードの負荷が均等に分散されます。また、特定のノードの負荷が高すぎることが判明した場合、そのノードに割り当てる仮想ノードの数を減らすことでサービスノードの負荷を軽減し、自動負荷分散を実現できます。

5. 読み書きのプロセス

分散型モデルのため、同時実行性を制御するにはより複雑なモデルが必要になります。 Dynamo は、並行処理のために Gossip と組み合わせた Paxos プロトコルを使用します。具体的な処理モードを図1に示します。

図1 Dynamoの書き込みと読み取りのプロセス

Dynamo は分散ノードを備えた P2P 設計を採用しており、システムのスケーラビリティが向上しますが、一貫性の問題も発生し、上位レベルのアプリケーションに影響を及ぼします。一貫性の問題により、異常な状況でのテストがより困難になります。 Dynamo は最も基本的な結果整合性のみを保証するため、複数のクライアントが同時に操作する場合の操作結果を予測することは困難であり、一貫性のない時間ウィンドウを予測することも困難であり、テスト ケースの設計に影響します。

分散型モデルによって生じる複雑さと不確実性。現在、主流の分散システムには一般的に中央ノードがあり、設計を簡素化できます。さらに、中央ノードは少量のメタデータのみを保持するため、通常はパフォーマンスのボトルネックにはなりません。

タオバオタイル

Tair は、Alibaba が立ち上げた、高性能、分散型、スケーラブル、高信頼性のキー/値構造ストレージ システムです。小さなファイルの保存に特別に最適化されており、シンプルで使いやすいインターフェース（Map に類似）を提供します。

1. 全体的なアーキテクチャ

分散システムである Tair は、中央制御ノードと複数のサービス ノードで構成されます。 Config Server は制御ポイントであり、単一のポイントです。現在、信頼性を確保するために 1 つのマスターと 1 つのバックアップが使用されています。すべてのデータ サーバーのステータスは同じです。

図2 Tairシステムのアーキテクチャ

2. データ配信

Tair はデータの主キーに基づいてハッシュ値を計算し、それを Q バケットに分散します。 Dynamo 論文の実験的結論によると、Q の値はクラスター内の物理マシンの数よりもはるかに大きくする必要があります。たとえば、Q の値は 102400 です。

3. フォールトトレランス

バックアップ コピーの場合は、直接移行します。プライマリ コピーの場合は、最初に切り替えてから移行します。

4. データ移行

マシンの追加や負荷の不均衡により、バケットの移行が発生する可能性があります。移行プロセス中は、外部サービスが保証される必要があります。移行が発生すると、データ サーバー A がバケット 1、2、3 をデータ サーバー B に移行するとします。移行が完了する前は、クライアントのルーティング テーブルは変更されず、1、2、3 へのクライアントのアクセス要求はすべて A にルーティングされます。ここで、1 は移行を開始しておらず、2 は移行中であり、3 は移行を完了していると仮定します。バケット 1 へのアクセスが行われると、A は直接サービスを提供します。バケット 3 へのアクセスが行われると、A はリクエストを B に転送し、B の応答をユーザーに返します。バケット 2 へのアクセスがあった場合、A はリクエストを処理し、バケット 2 に対する変更であれば変更ログが記録されます。バケット 2 が移行されると、変更ログが B に送信され、これらの変更操作が B に適用されます。A と B 間のデータが完全に一致するまで、移行は実際には完了しません。

5. 構成サーバー

クライアントはルーティング テーブルをキャッシュします。ほとんどの場合、クライアントは構成サーバー (Config Server) にアクセスする必要はなく、Config Server のダウンタイムはクライアントの通常のアクセスに影響を与えません。データ サーバーは、クライアントのバージョン番号が古すぎることを検出した場合、クライアントに Config サーバーにアクセスして新しいルーティング テーブルを取得するように通知します。クライアントがアクセスしたときにデータ サーバーに到達できない場合 (データ サーバーがダウンしている可能性があります)、クライアントは積極的に構成サーバーにアクセスして新しいルーティング テーブルを取得します。

6. データサーバー

Tair ストレージ エンジンには抽象化レイヤーがあります。ストレージ エンジンに必要なインターフェイスが満たされている限り、Tair の基盤となるストレージ エンジンは簡単に置き換えることができます。

Tair の主な目的は分散キャッシュです。永続ストレージは比較的遅れて開始されたため、実装の詳細には不十分な点がいくつかあります。たとえば、Tair 永続ストレージは信頼性を向上させるためにレプリケーション テクノロジを使用しますが、このレプリケーションは非同期です。したがって、データ サーバーに障害が発生すると、顧客は一定期間最新のデータを読み取ることができなくなったり、最新の変更データが失われたりする可能性があります。