コンシステントハッシュ

「どのキーをどのサーバに置くか」を、サーバの増減に強く決める方法を作る。素朴な hash(key) % N は 1 台増減しただけでほぼ全キーの置き場所が変わり、キャッシュが総崩れになる。そこでノードもキーも円環に置き、時計回りで最初のノードに属させると、増減で動くのは担当の弧の分だけ(平均 K/N 個)で済む。1 台を多数の点(仮想ノード)として置けば負荷の偏りもならされる。

この章で作るもの

レプリケーションで「書きはリーダー1点がボトルネック、伸ばすにはシャーディング」と見た。そのシャーディング、すなわちキーをサーバ群に分けて置く仕組みの土台がコンシステントハッシュ。分散キャッシュ(memcached)・分散DB(Cassandra / DynamoDB / Riak)・ロードバランサ(Envoy の ring hash)が使う。

順に見ていく。

hash(key) % N の罠: 一番素朴な割り方。だが N(台数)が1変わると、ほとんどのキーの % N の結果が変わり、ほぼ全キーが引っ越す。キャッシュなら全ミス、DB なら全データ移動
リング: ノードもキーも円環 [0, 2^32) 上に置き、キーは「時計回りで最初に出会うノード」に属す。ノードの増減で動くのは、その担当の弧に載っていたキーだけ
仮想ノード(vnode): ノードが少ないとリング上の弧が不揃いで負荷が偏る。1台を多数の点として散らばせると、担当弧の合計がならされて均等に近づく

素朴な `% N` の何が悪いか

キー k をサーバ nodes[hash(k) % N] に置く。分かりやすいが、N が変わった瞬間に破綻する。hash(k) % 4 と hash(k) % 3 は、ほとんどのキーで違う値になるからだ。

  key    hash%4   hash%3    変わった?
  k1       2        1         ✓ 移動
  k2       0        0           そのまま
  k3       3        0         ✓ 移動
  k4       1        2         ✓ 移動
  …        大半が変わる  →  4→3 でおよそ 3/4 が引っ越す

mod N の再ハッシュ。4台から3台に減らすと、hash%4 と hash%3 が一致するキーはごく一部。大半のキーが別のサーバへ移る。キャッシュなら一斉にミスし、DB なら大移動が起きる

Go 側のテストで実測すると、4→3台で mod 方式は 3000件中およそ 2230件(約 3/4)が動く。台数変更が日常茶飯事(オートスケール・故障・増設)の分散システムで、これは致命的。

リング: 時計回りで最初のノード

発想の転換。割り算をやめて、円環に並べる。ノードもキーも同じハッシュ空間 [0, 2^32) を円環と見なして配置し、キーは「自分の点から時計回りに進んで最初に出会うノード」に属す、と決める。

              A
         k1 ·   · k2
       ·             ·
     C                 B
       ·             ·
         k4 ·   · k3
              (時計回り →)

   C を削除 → C の弧(k4付近)だけが次のノードへ。A,B の担当は不変

ハッシュリング。ノード A/B/C とキーを同じ円環に置く。各キーは時計回りで最初のノードに属す。C を外すと、C が担当していた弧のキーだけが次のノード(時計回りの隣)へ移り、他は一切動かない

担当ノードを求めるのは、リング上でキーの点以上の最小の点を二分探索するだけ。端を超えたら先頭へ回り込む(円環だから):

// Get はキーの担当ノードを返す。円環上でキーの点から時計回りに最初に出会うノード。
// 空リングなら ok=false。
func (r *Ring) Get(key string) (node string, ok bool) {
	if len(r.points) == 0 {
		return "", false
	}
	h := r.hash([]byte(key))
	// h 以上で最小の点を二分探索。無ければ先頭へ回り込む(円環)。
	i := sort.Search(len(r.points), func(i int) bool { return r.points[i] >= h })
	if i == len(r.points) {
		i = 0
	}
	return r.owner[r.points[i]], true
}

ノードを1台足す/外すと、影響を受けるのはその点の隣の弧だけだ。平均すれば全キーの K/N 個しか動かない。mod のように全体を混ぜ直さないのが、コンシステント(一貫した)と呼ばれる理由だ。

動かす

下はリング。外周の色付きの線が仮想ノード(各物理ノードの担当開始点)、内側の点がキーで、時計回りで最初に出会うノードの色に染まる。**「ノードを追加/削除」**すると、動いたキーの数が出る。200件中ほんの一部しか動かない。右の棒は各ノードの担当キー数。

デモコンシステントハッシュ・リング3ノード / vnode 100

vnode 1 vnode 20 vnode 100

A1218件 (41%)

B751件 (25%)

C1031件 (34%)

仮想ノード数を変えると偏りが、ノードを増減すると『動くキーの少なさ』が見える

外周の色付き線 = 仮想ノード(その物理ノードの担当開始点)内側の点 = キー。時計回りで最初に出会うノードの色に染まる

仮想ノード: 偏りをならす

リングには弱点がある。ノードが少ないと、円環上の点の間隔がたまたま不揃いになり、担当弧の長さ=負荷が大きく偏る。デモで「vnode 1」にすると、3台なのに1台へ大きく偏るのが分かる(実測で最大/最小の負荷比が数百倍になることも)。

対策が仮想ノード。1つの物理ノードを、node#0, node#1, … と多数の点としてリングに置く。各ノードの担当は「あちこちに散らばった細かい弧の集まり」になり、合計すると平らにならされる。

  vnode 1(偏る)              vnode 多数(均等)
      A                          A B C A
    ·   ·                      ·         ·
   C     ·      →            C A B     B C
    ·   ·                      ·         ·
      B  (Aの弧が巨大)          B C A B A C

仮想ノードの効果。左は物理ノードそのまま(点3つ)で弧がいびつ。右は各ノードを多数の点として散らすので、担当弧が細かく交互に並び、合計負荷がならされる。vnode を増やすほど均等に近づく

デモの「vnode」を 1 → 20 → 100 と上げると、右の棒グラフが揃っていく。均等さの目安は 1/√(vnode数)。1台あたりの負荷のばらつきはおよそこの割合。vnode 100 なら ~10%、300 なら ~6% のばらつきに縮む。ただし物理ノードが少ないと残りの偏りは大きめで、3台だと vnode 100 でも最大/最小が 1.5 倍前後残る(√の効きが弱い)。ノード数と vnode 数の両方が増えるほど均等に近づく。だから Cassandra などは vnode を多めに取る。

ハッシュ関数の選択も効く。この実装は CRC32 を使う。node#0 のような似た短い文字列でも点がよく散らばるからで、同じ条件で FNV-1a に替えると負荷比が 2 倍超に偏った(groupcache も crc32 を採用)。

レプリケーションとの接続

シャーディングとレプリケーションは組み合わせて使う。あるキーの置き場所を1つ決めたら、その時計回りの隣 R 台にも同じデータを複製すれば、シャードごとに冗長化できる。GetN がそれで、時計回りに重複しない物理ノードを R 個返す:

primary, backups := ring.GetN(key, 3)[0], ring.GetN(key, 3)[1:]
// primary に書き、backups へ複製する(前章の耐久性ポリシーで何台待つかを決める)

Dynamo/Cassandra はまさにこの形だ。「リングで置き場所を決め、隣 R 台へ複製し、quorum で読み書きする」。前章の quorum と、この章のリングが、ここで1つの設計に合流する。

設計の観点: シャード設計の見積もり

「1TB のデータ / 書き 5万 QPS。どう分割する?」。シャーディングの問いには順序で答える:

シャード数: 1ノードが捌ける容量・QPS から割る。1ノード 100GB・1万 QPS なら、容量で10台、QPS で5台 → 多い方の10台。将来の増設を見込んで vnode は多め(100〜)に
リバランスのコスト: ノード追加で動くのは K/N。10→11台なら全体の ~1/11 だけ移動。mod なら大半が動くのでオンライン増設が現実的でない。ここがコンシステントハッシュを選ぶ理由
ホットスポット: 特定キーにアクセスが集中すると、そのシャード1台だけが灼ける。ハッシュは均等化するが単一キーの偏りは消せない。対策はキーの分割(user_id#bucket)や、そのキーだけレプリカ読みに逃がす
レプリケーションと合わせる: GetN で隣 R 台へ複製。故障時は次のノードが担当を引き継ぐ

メリット・デメリットと実例

方式	ノード増減で動くキー	負荷の均等さ	実装の重さ
`hash % N`	ほぼ全部(大半が移動)	均等	最軽量
リング(vnode なし)	K/N のみ	偏りやすい	軽い
リング + vnode	K/N のみ	vnode 数を上げるほど均等	中(点の管理)

裏どり:

Amazon DynamoDB / Dynamo 論文: リング + 仮想ノードで分割し、隣 N 台へ複製、quorum で読み書き。この章の設計の源流
Apache Cassandra: 同じくリング。num_tokens(vnode 数)を設定でき、既定は 16〜256 の範囲
memcached クライアント(ketama): 分散キャッシュのクライアント側でリングを持ち、サーバ増減時のキャッシュ全ミスを防ぐ。コンシステントハッシュの初期の普及例
Envoy / gRPC: ロードバランサの ring_hash ポリシー。同じキーを同じバックエンドへ(セッション固定・キャッシュ局所性)

簡略化したこと

円環は 32bit。実物(Cassandra/Dynamo)は 128bit の広い空間を使う
vnode 数は全ノード一律。実物は容量差に応じて重み付けする(重いノードに多くの点)
データの実移動・再バランスは扱わない(所属の計算だけ)。ホットスポット緩和(bounded loads)も無し
GetN の複製先選定は「時計回りに distinct」まで。ラック/AZ を跨がせる配置制約は無し

参考資料

Karger et al., Consistent Hashing and Random Trees (1997)。原典
DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store (2007)。リング + vnode + quorum の実システム
Kleppmann, Designing Data-Intensive Applications 6章(Partitioning)
実装: distributed/consistenthash

コンシステントハッシュ ​

この章で作るもの ​

素朴な % N の何が悪いか ​

リング: 時計回りで最初のノード ​

動かす ​

仮想ノード: 偏りをならす ​

レプリケーションとの接続 ​

設計の観点: シャード設計の見積もり ​

メリット・デメリットと実例 ​

簡略化したこと ​

参考資料 ​