Tech Learning Daily

mod N 方式が抱える脆さ

コンシステントハッシングは、1997 年に Karger らが発表した論文が、Web キャッシュへのアクセスが特定のサーバーに集中してしまう状態であるホットスポットを分散させる目的で提案した手法だ。キャッシュサーバーを複数台構成にするとき、まず思いつくのは hash(key) % サーバー台数 でどのサーバーが担当するかを決める方式だろう。台数が変わらない限り、この式はキーをほぼ均等にばらまける。

ところがサーバーを1台追加すると、割り算の除数そのものが変わる。ほぼすべてのキーで剰余の値が変わってしまうため、大半のキーが以前とは別のサーバーの担当になる。担当が変わったキーはそのサーバーのキャッシュ上には存在しないので、次に来たリクエストは軒並みキャッシュミスとして DB まで届いてしまう。これが、台数を増やしただけなのにヒット率が急落する理由だ。

リングの上でキーとサーバーを同じ空間に置く

この壊れやすさを解消するのが、サーバー名とキーの両方を同じハッシュ関数にかけ、大きな数直線を輪っか状につないだ円環（ハッシュリング）上の点として配置するコンシステントハッシングだ。キーの担当は「そのキーの位置から時計回りに歩いて最初に見つかったサーバー」と定義する。

ハッシュリング（0〜2^32 の円環、時計回り）
┌───────────────────────────┐
│ S1 ──▶ key ──▶ S2 ──▶ S3  │
└───────────────────────────┘
→ key は次に現れる S2 が担当する
→ 一周すると S1 の手前に戻る

この定義の下では、サーバーを1台取り除いても、影響を受けるのは取り除かれたサーバーが担当していた区間のキーだけで済む。リングの反対側にあるキーは、担当サーバーの位置がそもそも変わらないので、そのまま同じサーバーがヒットし続ける。除数が変わるたびに全体が揺れ動く mod N 方式との違いはここにある。

実サーバーが少ないと生じる偏り、仮想ノードによる解消

サーバーを増やすほど負荷は自動的に均等になっていくように思えるかもしれない。しかし実際のリングでは、各サーバーが置かれる位置はハッシュ関数の出力次第であり、台数が少ないうちは担当区間の長さが大きく偏ることがある。ある1台だけが広い区間を受け持ってしまえば、そのサーバーだけがアクセス集中で重くなる。

この偏りを均すために使われるのが仮想ノード（virtual node）だ。1台の物理サーバーを「サーバー名+連番」のような複数の文字列でハッシュし、リング上の複数の点に割り当てる。担当区間の数が増えるほど、統計的に見た区間の合計長はサーバー間で近づいていく。Memcached 向けの実装である Ketama は、サーバー1台につき 100〜200 個のハッシュ値をリング（continuum）上に置く設計になっている。Cassandra も同様の考え方を num_tokens 設定として持ち、公式ドキュメントは1ノードあたり 8 個の vnode を割り当てる構成で、分散のばらつきをおよそ 10% に抑えられるとしている。

実際に使われている場所と Redis Cluster との違い

Amazon が 2007 年に公開した Dynamo の論文は、キーバリューストアのデータ分散にコンシステントハッシングと仮想ノードを採用し、後続の Cassandra など多くの分散データストアの設計に影響を与えた。ノードが増減しても、影響を受けるのはリング上で隣接する範囲のデータだけだという性質は、この種のシステムが「一部のノード故障時にも全データの再配置をせずに済む」ことの土台になっている。

一方で Redis Cluster は、リングそのものではなく、あらかじめ 16384 個に固定した担当範囲の単位であるハッシュスロットにキーを割り当てる方式を採る。キーの CRC16 値を 16384 で割った余りでスロット番号を決め、各ノードがスロット番号の範囲を1つずつ受け持つ。ノードを追加するときはスロットの範囲そのものをノード間で移動させるため、動くデータの量はスロット単位で見積もれる。同じ「ノード変化時の移動を最小化する」という目的でも、リングと固定スロットでは管理の単位が異なる。