分散ストレージシステムのデータ分散アルゴリズムを簡単に見てみましょう。

序文

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

[[283891]]

文章

（I）指標

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

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

これら 2 つの目標はある程度矛盾していることがわかります。ストレージ ノードが追加または削除される場合、安定性を維持するためにデータの移動と再配布を最小限に抑える必要がありますが、これは必然的に負荷の不均衡につながります。同様に、極端な均一性の追求も、より多くのデータ移行につながります。

したがって、私たちは、適切な均一性と安定性を実現するために、これら 2 つの極端な点の間の点を見つけたいと考えています。上記の 2 つの基本目標に加えて、データ分散アルゴリズムの長所と短所を判断するために、プロジェクトでは次の側面を考慮する必要があります。

• パフォーマンスのスケーラビリティ: これは主に、ストレージ ノードの規模に対するアルゴリズムの時間的複雑さを考慮します。システム全体のスケーラビリティを確保するため、データ分散アルゴリズムでは、クラスター サイズの増加後に実行時間が大幅に増加しないようにする必要があります。
• ノードの異種性を考慮する: 実際のプロジェクトでは、異なるストレージ ノード間でパフォーマンスや容量に大きな違いが生じる可能性があります。優れたデータ分散アルゴリズムは、この異質性に対処し、重み付けされたデータの均一性を提供できる必要があります。
• 障害ドメインを分離する: データの可用性を高めるには、データ分散アルゴリズムで各キーのストレージ ノードのセットを検出する必要があります。これらのノードは、データのミラー コピー、または消去コードに類似したコピー方法を提供する場合があります。データ分散アルゴリズムは、異なるコンピュータ ルーム、異なるラック、異なるスイッチ、異なるマシンなど、これらのレプリカの障害ドメインを分離するように努める必要があります。

（II）進化

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

1. ハッシュ

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

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

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

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

一貫性ハッシュには、ノードの変更が不均一になるという問題があります。 2017 年に、Google はこの不均一性の程度を制御するために Consistent Hashing with Bounded Loads を提案しました。簡単に言うと、このアルゴリズムはハッシュ リング上の各ノードに平均負荷の 1 + e 倍の負荷制限を与え、この 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 アルゴリズムは、本質的には、次の側面を最適化しようとするシャードベースのデータ分散方法です。

• シャード マッピング情報量: 中央ディレクトリ サービスとストレージ ノードおよびクライアント間で大量のシャード マッピング情報を交換しないようにします。代わりに、ストレージ ノードまたはクライアントは、小規模で安定したクラスター ノード トポロジと特定のルールに基づいて、シャード マッピングを自ら計算します。
• 完全な障害ドメイン分割: 階層的な障害ドメイン制御をサポートし、構成に応じて同じシャードの異なるコピーを異なるレベルの障害ドメインに分割します。

クライアントまたはストレージ ノードは、キー、ストレージ ノードのトポロジ、および割り当てアルゴリズムを使用して、シャードの場所を個別に計算し、対応するシャードとレプリカを担当するストレージの場所のセットを取得します。

図は位置決めプロセスを示しており、最終的に 1 行下の 3 つのキャビネット (cab21、cab23、cab24) の下の 3 つのストレージ ノードが選択されます。

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

（III）応用事例

最も一般的な分散ストレージ システムでは、シャーディングに似たデータ分散および配置方法が使用されます。

• Cassandra/Dynamo: シャーディングとゴシップ プロトコルを使用してピア ノード間の通信を行います。
• Redis クラスター: キー空間をスロットに分割し、通信には Gossip プロトコルも使用します。
• Zeppelin: データをパーティションに分割し、Meta クラスターを通じて中央ディレクトリ サービスを提供します。
• Bigtable: データをタブレットに分割します。これは変数シャードに似ています。 Tablet Server はシャードをカットすることができ、最終的なシャード情報は Chubby に記録されます。
• Ceph: CRUSH メソッドを使用して、中央クラスター モニターがクラスター トポロジの変更を提供および維持します。