分散型一貫性ハッシュ

一貫性ハッシュ#

内容来自

極客時間専欄:《分布式技術原理與算法解析》

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 に属します。
データのシャーディングは、データの次元から分割され、データセットを特定の方法で複数のデータサブセットに分割することを指します。異なるデータサブセットは異なるストレージブロックに存在し、これらのストレージブロックは異なるノードに存在することも、同じノードに存在することもあります。