一貫性ハッシュアルゴリズムと分散ストレージへの応用

OStorageの責任者であるLi Mingyu氏は、同社のエンタープライズレベルのオブジェクトストレージ製品であるOStorage-EOSの監視インターフェースのスクリーンショットである「友達の輪」を何気なく投稿し、200TBを超えるクラスターがユーザーによって急速に92％以上使用されたことに対する感動を表現した。

「部外者は興奮を観察、部内者は出入り口を観察。」分散ストレージに取り組んでいる同僚がこれを見て、こう言いました。「ストレージ使用率は 93% 近くまで達しており、まだデータが書き込まれています。これは、OStorage-EOS のデータ分散が非常に均一であることを示しています。」そうでない場合、データの分散が十分に均一でない場合、他のノードまたはディスクにはまだ十分なスペースがあるが、特定のディスクまたは特定のノードがいっぱいになっている可能性があります。データがまだ書き込まれている場合は、問題が発生します。

[[222254]]

では、OStorage-EOS 分散オブジェクト ストレージはどのようにしてディスク間でデータを均等に分散するのでしょうか? 「コンシステント・ハッシュ」と呼ばれるアルゴリズムが使用され、コンシステント・ハッシュをベースに、重み、レプリカ、キャビネット認識、地域認識などのメカニズムを追加して改良が行われたことが判明しました。

コンシステント・ハッシュ・アルゴリズムは分散システムの分野でも古典的なアルゴリズムであり、多くの場所で使用されています。一緒に見てみましょう:

ハッシュ関数

一貫性ハッシュについて詳しく説明する前に、まず基本的なハッシュについて説明し、ハッシュ関数を使用してオブジェクトが保存されている場所を決定する方法の例を示します。

まず、データを見つけるための比較的簡単な方法を見てみましょう。 MD5 アルゴリズムを使用してオブジェクトの論理的な場所のハッシュ値を取得し、それを使用可能なディスクの数で割って余りを取得します。 ***残りの値をドライブ ID にマップします。

たとえば、オブジェクトの保存場所は /accountA/container1/objectX で、データの保存には 4 つのディスクが使用され、これをディスク 0 からディスク 3 と呼びます。ここでは、まず MD5 値を計算します。

 md5 -s /アカウントA/コンテナ1/オブジェクトX
 MD5 ( "/アカウント/コンテナ/オブジェクト" ) =
 f9db0f833f1545be2e40f387d6c271de

次に、ハッシュ値 (16 進数値) をディスクの数で割り、余り (モジュロ) を算出します。上記の 16 進数値は次のように 10 進数値に変換されます。

332115198597019796159838990710599741918

モジュロ関数は、ほとんどのプログラミング言語で % 演算子を使用して表されます。

332115198597019796159838990710599741918 % 4 = 2

余りが 2 なので、オブジェクトはディスク 2 に保存されます。

このアルゴリズムの最大の欠点は、計算結果が除数、つまりディスクの数に依存することです。ディスクが追加または削除されるたびに (除数が変化すると)、同じオブジェクトが異なる剰余を取得し、異なるディスクにマップされる可能性があります。これを説明するために、次の表は、ディスクが追加されたときにどのディスクがオブジェクトの新しい保存場所になるかを示しています。

ほとんどの場合、新しいディスクが追加されるたびに、オブジェクトを新しいディスクに移動する必要があることに注意してください。これは 1 つのオブジェクトの場合のみです。この動作が一般化されると、ノードまたはディスクを追加または削除するときに、クラスター内のほぼすべてのデータを移動する必要があります。クラスターはこれらの移行を実行するために多大なリソースを費やす必要があり、これにより大きなネットワーク負荷が発生し、データが読み取り不能になります。

一貫性ハッシュアルゴリズム

一貫性ハッシュを使用すると、クラスターにディスクやノードを追加または削除するときに移動する必要があるオブジェクトの数を減らすことができます。一貫性ハッシュは、各値を直接ディスクにマッピングするのではなく、すべての可能なハッシュ値をリングとしてモデル化することによって機能します。一貫性ハッシュ アルゴリズムは、オブジェクトのハッシュを計算するだけでなく、デバイスのハッシュも計算します。ハッシュ値は、ディスクの IP アドレス、ドライブ文字などに基づいて計算されます。図に示すように、各ディスクはハッシュ リング内のポイントにマップされます。

オブジェクトを保存する必要がある場合、まずオブジェクトのハッシュ値が計算され、次に図の「オブジェクトのハッシュ」の位置に示すようにリング上に配置されます。システムは、リング上の次のディスクのハッシュを時計回りに検索し、そのディスクを見つけて、このディスクを使用してデータを保存します。上の図からわかるように、オブジェクトはディスク 4 に保存されます。このアルゴリズムに従って、ハッシュ リング上の特定の間隔のハッシュ値がディスクにマッピングされます。図に示すように、異なる間隔とそれに対応するディスクを表すために異なる色を使用します。オブジェクトのハッシュ値が青い間隔内に収まる場合、そのオブジェクトはディスク 1 に保存されます。

このようなハッシュ リングでは、ディスク 5 などの新しいディスクを追加すると、図のピンク色の部分はディスク 4 に属しなくなります。これは、この部分のデータがすべて新しいディスク 5 に属するようになるためです。したがって、ディスク 4 上のオブジェクトはディスク 5 に移動されますが、他のデータは影響を受けません。

このソリューションを使用すると、ディスクまたはノードを追加するときに少量のデータの移動のみが必要になります。これは、大量のデータを移動する必要があるデータ保存場所を決定するためにハッシュ値の計算とモジュロ除算に依存する以前の最も基本的なソリューションよりもはるかに優れています。

実際のアプリケーションで使用される一貫性のあるハッシュ アルゴリズムでは、実際の各ディスクまたはノードはリング上の複数のタグに対応します。これらのタグは、一部の文献では「仮想ノード」とも呼ばれます。実際のアプリケーションでは、ディスクは多数のタグ/仮想ノードに対応し、各ディスクも数百のタグに対応します。複数のタグは、各ディスクの対応するリングのハッシュ値の範囲が、大きな領域からいくつかの小さな領域に分割されることを意味します。これには2つの効果があります。 1 つは、新しく追加されたディスクが複数のディスクからオブジェクト データを移行する可能性があるため、データ移行の負担がさらに軽減されることです。もう 1 つの効果は、全体的なデータ分布がより均一になることです。

上記はコンシステントハッシュの基本原則です。 OStorage-EOS は、一貫性のあるハッシュ アルゴリズムに基づいてデータの均一な分散を実現し、レプリカ、重み、キャビネット認識、地域認識などのメカニズムを導入することでこれを改善し、エンタープライズ レベルのユーザーのニーズを満たします。