分散ストレージシステムのデータ分散方法に関する簡単な説明

分散ストレージ システムが直面する主な問題は、大量のデータを異なるストレージ ノードに分散する方法です。上位層インターフェースが KV ストレージ、オブジェクト ストレージ、ブロック ストレージ、または列ストレージのいずれであっても、問題は概ね一貫しています。この記事では、分散ストレージ システムにおけるデータ分散の目標と利用可能なソリューションを紹介し、それらの関係とトレードオフをまとめます。

索引

ここでは、ターゲット データはキーによって識別されるデータ ブロックまたはオブジェクトであると想定します。複数のストレージ ノードを持つクラスターでは、データ分散アルゴリズムによって、指定されたキーごとに 1 つ以上の対応するストレージ ノードを指定する必要があります。データ分散アルゴリズムには、2 つの基本的な目標があります。

[[213691]]

均一性: 異なるストレージ ノードの負荷は均等に分散される必要があります。

一貫性: データ分散アルゴリズムを通じてキーによって取得された分散結果は、ストレージ ノードが変更された場合でも、基本的に毎回安定したままである必要があります。

これら 2 つの目標はある程度矛盾していることがわかります。ストレージ ノードが追加または削除される場合、安定性を維持するために、データの移動と再配布を最小限に抑える必要がありますが、これにより必然的に負荷の不均一が生じます。同じ統一性の追求により、データの移行もさらに進むことになります。したがって、私たちは、適切な均一性と安定性を得るために、これら 2 つの極端な点の間の点を見つけたいと考えています。上記の 2 つの基本目標に加えて、データ分散アルゴリズムの長所と短所を判断するために、プロジェクトでは次の側面を考慮する必要があります。

パフォーマンスのスケーラビリティ。主に、ストレージ ノードの規模に対するアルゴリズムの時間計算量を考慮します。システム全体のスケーラビリティを確保するため、データ分散アルゴリズムは、クラスターの規模が拡大された後に実行時間を大幅に増加させないようにする必要があります。

ノードの異種性を考慮すると、実際のプロジェクトでは、異なるストレージ ノード間でパフォーマンスや容量に大きな違いが生じる可能性があります。優れたデータ分散アルゴリズムは、この異質性に対処し、重み付けされたデータの均一性を提供できる必要があります。

障害ドメインを分離します。データの可用性を高めるには、データ分散アルゴリズムで各キーのストレージ ノードのセットを検出する必要があります。これらのノードは、データのミラー コピー、または消去コードに類似したコピー方法を提供する場合があります。データ分散アルゴリズムは、異なるコンピュータ ルーム、異なるラック、異なるスイッチ、異なるマシンなど、これらのレプリカの障害ドメインを分離するように努める必要があります。

進化

アルゴリズムの評価指標を確認した後、いくつかの可能なソリューションの進化を紹介し、その長所と短所を分析します。ここではキー値が十分に分散されていると仮定します。

1. ハッシュ

シンプルで直感的なアイデアは、ハッシュを使用して直接計算し、キーをハッシュしてからノード数の係数を取得することです。キーが十分に分散されている場合は均一性が達成されますが、ノードが参加または離脱すると、元のノードすべてが影響を受けることがわかります。安定性と呼べるものはありません。

2. 一貫性のあるハッシュ

一貫性のあるハッシュは安定性の問題を非常にうまく解決できます。すべてのストレージ ノードは、最後に接続されたハッシュ リング上に配置できます。ハッシュを計算した後、各キーは時計回り方向に最初に遭遇したストレージ ノードのセットを見つけて保存します。ノードが参加または離脱すると、ハッシュ リング上でそのノードに時計回りに隣接する後続のノードにのみ影響し、そのノードからデータが受信または提供されます。しかし、これによって均一性の問題が生じます。ストレージノードを等間隔に配置できたとしても、ストレージノードの数が変わるとデータの不均一性が発生します。しかし、このような不均一性は、複数存在する可能性があり、実際のエンジニアリングでは許容されません。

3. 負荷制限付き一貫性ハッシュ

一貫性ハッシュには、ノードの変更が不均一になるという問題があります。 2017 年に、Google はこの不均一性の程度を制御するために Consistent Hashing with Bounded Loads を提案しました。簡単に言えば、アルゴリズムはハッシュ リング上の各ノードに平均負荷の 1 + e 倍の負荷制限を与えます。これはカスタマイズ可能です。キーがハッシュ リング上で時計回りに適切なノードを見つけると、このノードの負荷が上限に達したかどうかを判断します。上限に達した場合は、割り当てのために後続のノードを探し続ける必要があります。

上図のように、各バケットの現在の上限が 2 であると仮定すると、赤いボールが順番に訪問されます。 6番の赤いボールが到着すると、時計回りで最初に遭遇したB（3、4）とC（1、5）が上限に達していることが判明し、最終的にバケットAに配置されます。このアルゴリズムの最も魅力的な点は、ノードの変更があった場合、移行する必要があるデータの量は1 / e ^ 2に関連し、ノード数やデータ数とは関係がないことです。つまり、クラスターがスケールアップしても、データ移行の量は大幅に増加しません。さらに、ユーザーは e の値を調整することで、均一性と安定性のトレードオフを制御できます。コンシステント ハッシュ法も、負荷制限付きコンシステント ハッシュ法も、ノードの異質性の問題を解決することはできません。

4. 仮想ノードによる一貫性のあるハッシュ

不均一な負荷と異質性の問題を解決するために、一貫性のあるハッシュに基づいて仮想ノードを導入することができます。つまり、ハッシュ リング上の各ノードは実際のストレージ ノードではなく、仮想ノードです。実際のストレージ ノードは、その異なる重みに応じて 1 つ以上の仮想ノードに対応し、対応する仮想ノードに含まれるすべてのキーはストレージ ノードの責任となります。次の図に示すように、ストレージ ノード A は (1,3]、(4,8]、(10、14] を担当し、ストレージ ノード B は (14,1]、(8,10] を担当します。

このアルゴリズムの問​​題点は、実際のストレージ ノードの追加または終了が複数の仮想ノードの再割り当てに影響し、その結果、多くのノードがデータ移行に参加することにも影響することです。さらに、実際には、仮想ノードが新しい実際のノードに再割り当てされる場合、この部分のデータを走査して新しいノードに送信する必要があります。仮想ノードを分割して割り当てるには、シャーディングという適切な方法が必要です。

5. シャーディング

シャーディングはハッシュ リングを同じサイズのシャードに分割し、これらのシャードを異なるノードに割り当てます。これは、上記の仮想ノードとは根本的に異なることに注意してください。シャードの分割と割り当ては分離されています。ノードが終了すると、そのノードが担当するシャードを時計回りに次のノードにマージする必要はありません。代わりに、シャード全体を任意のノードに全体的により柔軟に引き渡すことができます。実際には、シャードは主にデータの移行とバックアップの最小単位として使用されます。

そして、上記の分離、つまり元のキーとノードのマッピングを 2 つのレイヤーに分割することと同等の分離のために、シャードをストレージ ノードにマッピングするための新しいメカニズムが必要になります。シャードの数はキー空間に比べてすでに少なく、その数は固定されているため、最初により正確に設定することができ、中央ディレクトリ サービスを導入して、ノードの生存に基づいてシャードのマッピング関係を変更し、このマッピング情報をすべてのストレージ ノードとクライアントに通知することができます。

上の図は、当社の分散 KV ストレージ Zeppelin のシャーディング方法を示しています。キー スペースはシャードにハッシュされ、シャードとそのレプリカはレイヤーを通じて最終ストレージ ノード ノード サーバーにマップされます。

6. CRUSHアルゴリズム

CRUSH アルゴリズムは、本質的には、次の側面を最適化しようとするシャード データ分散方法です。

シャード マッピング情報量: 中央ディレクトリ サービスとストレージ ノードおよびクライアントが大量のシャード マッピング情報を交換する必要性を回避します。代わりに、ストレージ ノードまたはクライアントは、小規模で安定したクラスター ノード トポロジと特定のルールに基づいて、シャード マッピングを自ら計算します。

完全な障害ドメイン分割: 階層的な障害ドメイン制御をサポートし、構成に応じて同じシャードの異なるコピーを異なるレベルの障害ドメインに分割します。

クライアントまたはストレージ ノードは、キー、ストレージ ノードのトポロジ、および割り当てアルゴリズムを使用して、シャードの場所を個別に計算し、対応するシャードとレプリカを担当するストレージの場所のセットを取得します。次の図は位置決めプロセスを示しています。最後に、行の下の 3 つのキャビネット cab21、cab23、cab24 の下の 3 つのストレージ ノードが選択されます。

ノードが変更されると、ノード トポロジの変更によって少量のシャード データの移行に影響が及びます。下の図に示すように、新しいノードが追加されるとデータの移行が発生します。適切な分散アルゴリズムにより、適切な負荷分散と安定性を実現できます。

応用

最も一般的なストレージ システムでは、シャーディングに似たデータ分散および配置方法が使用されます。 Dynamo と Cassandra はシャーディングを使用し、ゴシップを通じてピア ノード間で同期します。 Redis Cluster はキー空間をスロットに分割し、ゴシップ通信も使用します。 Zeppelin はデータをパーティションに分割し、メタ クラスターを通じて中央ディレクトリ サービスを提供します。 Bigtable はデータを変数シャードに似たタブレットに分割します。 Tablet Server はシャードをカットすることができ、最終的なシャード情報は Chubby に記録されます。 Ceph は、中央のクラスター モニターによって管理され、クラスター トポロジの変更を提供する CRUSH メソッドを使用します。