コンシステントハッシュ法とは?サーバーを増減しても大惨事にならない仕組み

コンシステントハッシュ法とは何か

コンシステントハッシュ法とは、複数のサーバーにデータを分散して保存する際に、「どのデータをどのサーバーに置くか」を決めるための割り振り方の一種です。分散キャッシュや分散データベースなど、複数台のサーバーでデータを手分けして管理する仕組みで広く使われています。

この手法の最大の特徴は、サーバーの台数が増えたり減ったりしても、再配置が必要になるデータの範囲がごく一部で済むという点です。

単純な「割り算」方式の弱点

コンシステントハッシュ法のメリットを理解するために、まず単純な方法から考えてみます。

サーバーが3台あるとして、各データに番号を振り、「データ番号 ÷ サーバー台数」のあまりでどのサーバーに置くかを決めるとします(これを剰余ハッシュ法と呼びます)。この方法自体はシンプルで分かりやすいのですが、大きな弱点があります。

サーバーを1台追加して4台にした瞬間、「割る数」が3から4に変わります。すると、ほとんどのデータで「あまり」の計算結果が変わってしまい、ほぼ全部のデータについて、担当サーバーの再計算・移動が必要になってしまうのです。サーバーをたった1台増やしただけなのに、システム全体のデータをほぼ丸ごと移動させる大工事になりかねません。

コンシステントハッシュ法の考え方

コンシステントハッシュ法では、サーバーとデータの両方を、大きな「輪(リング)」の上の点として配置する、というイメージで考えます。

1. サーバー自体にもハッシュ値を計算し、輪の上のどこかの位置に配置する
2. データにもハッシュ値を計算し、同じ輪の上のどこかの位置に配置する
3. 各データは、「輪の上を時計回りに進んで、最初に出会ったサーバー」が担当する、というルールにする

この方式であれば、サーバーを1台追加した時に何が起きるかというと、輪の上でその新しいサーバーのすぐ手前に位置していたデータだけが、新しいサーバーの担当に切り替わります。それ以外の大部分のデータは、担当サーバーが変わりません。サーバーの増減が、影響範囲を輪の一部分だけに限定できるというのが、この手法の核心部分です。

実際にはもう一工夫されている

輪の上にサーバーを1点ずつ配置するだけだと、配置の偏りによって、特定のサーバーだけ負担が集中してしまうことがあります。そのため実際の実装では、1台のサーバーを、輪の上の複数の点(仮想ノード)として配置するという工夫が行われることが多いです。これにより、負荷がより均等に分散されやすくなります。

関連するトピック

以前の記事「キャッシュとは」でも触れた通り、キャッシュの仕組みは応答速度の改善に大きく貢献します。コンシステントハッシュ法は、そのキャッシュを複数台のサーバーに分散させる場合に、裏側で使われている考え方の1つです。CDNとはのような、多数のサーバーにコンテンツを配置する仕組みとも関連が深い技術です。

こうして見ると

コンシステントハッシュ法は、「サーバーの台数はいずれ変わるもの」という前提に立ち、変化に強い設計をあらかじめ組み込んでおく、という考え方の一例です。地味な仕組みですが、大規模なサービスがサーバー増減のたびに大惨事にならずに済んでいる背景には、こうした工夫が存在しています。