分散型一致性ハッシュ

一貫性ハッシュ#

内容来自

極客時間のコラム: 《分布式技術原理與算法解析》

5 分で理解する一貫性ハッシュアルゴリズム

データ分布設計原則#

分散データストレージシステムにおいて、ストレージソリューションの選定時には、通常データの均一性、データの安定性、ノードの異種性の 3 つの次元を考慮します。
データの均一性の次元から考えると、主に 2 つの側面があります：

異なるストレージノードに保存されるデータはできるだけ均衡を保ち、特定のノードまたはいくつかのノードに過度の負担がかからないようにし、他のノードにはほとんどデータがない状態を避ける必要があります。
また、ユーザーのアクセスも均衡を保つ必要があり、特定のノードまたはいくつかのノードへのアクセスが非常に多く、他のノードには誰も訪れない状況を避ける必要があります。

データの安定性の次元から考えると、ストレージノードに障害が発生し、削除または拡張が必要な場合、データは分布ルールに従って得られた結果ができるだけ安定している必要があり、大規模なデータ移動が発生しないようにする必要があります。

ノードの異種性の次元から考えると、異なるストレージノードのハードウェア構成には大きな差があり、性能の差も大きくなりますが、データ量やユーザーアクセス量はほぼ同じであるため、これは本質的に不均衡です。したがって、良いデータ分布アルゴリズムはノードの異種性を考慮する必要があります。

一貫性ハッシュ#

一貫性ハッシュとは、ストレージノードとデータを首尾一貫したハッシュリングにマッピングすることを指します。ストレージノードは IP アドレスに基づいてハッシュ化され（2 回のハッシュに相当）、データは通常、時計回りの方向で自分の所属するストレージノードを特定するために探します。つまり、データがリング上の位置にマッピングされているところから始まり、時計回りの方向で最初に見つかるストレージノードを見つけます。現在、Cassandraは一貫性ハッシュ方式を使用しています。

一貫性ハッシュアルゴリズムを使用した場合、ハッシュテーブルのスロット数（サイズ）の変更は平均して K/n 個のキーワードを再マッピングするだけで済みます。ここで K はキーワードの数、n はスロットの数です。しかし、従来のハッシュテーブルでは、スロットを追加または削除する際にはほぼすべてのキーワードを再マッピングする必要があります。たとえば、Node2 ノードがダウンした場合、影響を受けるのは前のデータだけ（元のデータは時計回りの次のサーバーノード Node3 に保存されます）であり、他のデータには影響を与えません。

この方法は安定性を向上させましたが、それに伴う均一性の問題も明らかです。ノードが退出すると、そのノードの後継ノードはそのノードのすべての負荷を引き受ける必要があり、後継ノードが耐えられない場合、ノード障害が発生し、後継ノードの後継ノードも同様の問題に直面します。Google は 2017 年に負荷制限付きの一貫性ハッシュアルゴリズムを提案し、この問題に対していくつかの最適化を行いました。

負荷制限付きの一貫性ハッシュ#

負荷制限付きの一貫性ハッシュ方式の核心原理は、各ストレージノードにストレージ上限値を設定し、ストレージノードの追加または削除によるデータの不均一性を制御することです。データが一貫性ハッシュアルゴリズムに従って対応するストレージノードを見つける際、そのストレージノードがストレージ上限に達しているかどうかを最初に判断します。上限に達している場合は、そのストレージノードの時計回りの方向にあるノードを探してストレージを行う必要があります。

このアルゴリズムの詳細については、“Consistent Hashing with Bounded Loads”という論文を参照してください。

負荷制限付きの一貫性ハッシュ方式は、同種のノードやノードの規模が変化するシナリオに適しています。現在、Google Cloud Pub/Sub や HAProxy でこの方法が実装されており、Google や Vimeo などの企業の負荷分散プロジェクトに応用されています。

仮想ノードを持つ一貫性ハッシュ#

一貫性ハッシュと負荷制限付きの一貫性ハッシュは、ノードの異種性の問題を考慮していません。ストレージノードの性能が異なる場合、データ分布の方法がこれらの方法に従っていると、実際にはデータの均一分布が達成されていません。

仮想ノードを持つ一貫性ハッシュ方式の核心思想は、各ノードの性能に基づいて、各ノードに異なる数の仮想ノードを割り当て、これらの仮想ノードをハッシュリングにマッピングし、その後、一貫性ハッシュアルゴリズムに従ってデータのマッピングとストレージを行うことです。

仮想ノードを持つ一貫性ハッシュ方式は、異種ノードやノードの規模が変化するシナリオに適しています。現在、Memcached キャッシュシステムがこの方法を実装しています。

まとめと拡張#

いくつかのハッシュアルゴリズムのまとめ#

データのシャーディングとデータのパーティショニングの違いは？#

データのパーティショニングは、データストレージブロックの次元から分割され、異なるパーティションは物理的に異なるノードに属します。たとえば、現在 2 つのノード Node1 と Node2、2 つのデータパーティション Partition1 と Partition2 があり、Partition1 は Node1 に、Partition2 は Node2 に属します。
データのシャーディングは、データの次元から分割され、データセットを特定の方法で複数のデータサブセットに分割することを指します。異なるデータサブセットは異なるストレージブロックに存在し、これらのストレージブロックは異なるノード上に存在することも、同じノード上に存在することもあります。