【ITニュース解説】Consistent hashing

システムエンジニアとして、多くのデータを扱うシステムを設計する際、データを複数のサーバー（ノードと呼ぶ）に分散させることは非常に重要になる。これにより、ひとつのサーバーへの負荷集中を防ぎ、システムの処理能力を高め、障害に対する耐性も向上させることが可能となる。しかし、この「データをどのサーバーに置くか」という問題は、システムの規模が大きくなるにつれて複雑化する。特に、サーバーの数が増えたり減ったりする状況で、いかに効率的にデータを再配置するかが課題となる。

一般的なデータ分散の方法として、データの識別子（キー）をハッシュ関数で数値に変換し、その数値をサーバーの総数で割った余り（モジュロ演算）を使って、データを割り当てるサーバーを決定する方法がある。例えば、server_index = hash(key) % N のように計算し、Nはサーバーの総数を示す。この方法のメリットはシンプルであることだが、大きな欠点が存在する。もしサーバーの総数Nが1台でも増えたり減ったりすると、モジュロ演算の結果が変わってしまうため、ほとんど全てのデータの割り当て先が変更されてしまうのだ。これは、大量のデータがサーバー間で一斉に移動しなければならないことを意味し、ネットワーク帯域の消費やシステム全体の性能低下を引き起こす。例えば、キャッシュサーバーが一時的に落ちて再起動したり、新しいキャッシュサーバーを追加したりするたびに、キャッシュ内のデータがほとんど無効になり、データベースへの問い合わせが集中してシステム全体がボトルネックに陥る、といった状況が考えられる。このような大規模なデータ移動を避け、システムの柔軟性を保つために「コンシステントハッシュ（Consistent Hashing）」という技術が考案された。

コンシステントハッシュの基本的な考え方は、データのハッシュ空間を円環状にマッピングすることにある。まず、0からある最大値までを連ねた一本の線が、両端でつながれて円を形成するイメージを持つと良い。この円環上に、データ（キー）とサーバー（ノード）の両方を、それぞれ同じハッシュ関数を使ってハッシュ値を計算し、そのハッシュ値が示す位置に配置する。具体的には、サーバーにはIPアドレスやサーバー名などの識別子をハッシュ化して円環上に配置し、データにはそのキーをハッシュ化して円環上に配置する。データの割り当てルールはシンプルで、円環上でデータのハッシュ値から時計回りに進んで最初にぶつかるサーバーに、そのデータを割り当てるというものである。

この円環状の仕組みが、サーバーの増減時に大きなメリットを発揮する。例えば、新しいサーバーがシステムに追加された場合を考えてみよう。新しいサーバーが円環上のどこかの位置に配置されると、その新しいサーバーから反時計回り方向で最初に位置していたサーバーに割り当てられていたデータの一部が、新しいサーバーに割り当てられるようになる。つまり、影響を受けるのは、新しいサーバーが加わったことで「担当範囲が変わった」部分のデータのみであり、他のサーバーに割り当てられているデータは、その割り当て先が変わることがない。同様に、既存のサーバーがシステムから削除された場合も、削除されたサーバーに割り当てられていたデータは、円環上で削除されたサーバーの次に時計回り方向に位置するサーバーに再割り当てされるだけである。ここでも、影響を受けるのは削除されたサーバーが担当していたデータのみであり、全体のデータのうちごく一部が移動するだけで済む。このように、サーバーの増減が発生しても、データ移動の範囲が最小限に抑えられる点が、コンシステントハッシュの最大の強みである。

しかし、このシンプルなコンシステントハッシュにも課題が存在する。もしサーバーの数が少ない場合、円環上にサーバーが均等に配置されない可能性があるのだ。例えば、偶然にもハッシュ値が偏ってしまい、特定のサーバーばかりが集中して配置されたり、逆に特定のサーバーが極端に離れて配置されたりすることが考えられる。この場合、円環上の担当範囲が非常に広くなるサーバーや狭くなるサーバーが生じ、結果として一部のサーバーにデータが集中して負荷が高まったり（ホットスポット）、逆にほとんどデータが割り当てられないサーバーが生じたりして、データの分散が不均一になってしまう。このような偏りをなくし、より均一なデータ分散を実現するために「仮想ノード（Virtual Nodes）」という概念が導入される。仮想ノードとは、一つの物理サーバーに対して、仮想的に複数のノードを割り当てるという考え方である。例えば、一つの物理サーバーを「Server A」とすると、「Server A-1」「Server A-2」「Server A-3」といった複数の仮想ノードが円環上の異なる位置に配置される。これにより、円環上には物理サーバーの数よりもはるかに多くのノードが存在することになり、ノードの密度が高まる。結果として、データのハッシュ値が円環上のどこに位置しても、近くにいずれかの仮想ノードが存在する確率が高まり、データの分散がより均一になる。もし特定の仮想ノードにデータが集中したとしても、その仮想ノードは同じ物理サーバーに属する他の仮想ノードと合わせて全体としてデータを受け持つため、物理サーバーごとの負荷の偏りを平準化できる。仮想ノードの数を適切に設定することで、物理サーバーの増減があっても、データの再配置を最小限に抑えつつ、かつデータが均等に分散される理想的な状態に近づけることが可能になる。

コンシステントハッシュは、分散システムにおいて非常に重要な技術であり、Memcachedのようなキャッシュシステム、CassandraやDynamoDBといった分散データベースなど、多くの大規模システムで実際に利用されている。システムエンジニアにとって、この技術の理解は、スケーラブルで可用性の高いシステムを設計・構築する上で不可欠な知識となる。データの分散と再配置の効率化という課題に対する、洗練された解決策がコンシステントハッシュなのである。