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

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