ロードバランサ

実装: resilience/loadbalancer/ / 実行: go test ./resilience/loadbalancer/

同じ役割のサーバを何台も並べたら、来たリクエストをどの台へ振るかを決めることになる。混み具合を見ずに順番へ回すと、重いものが同じ台に集まって1台だけ10倍の負荷になった。全台を見れば偏らないが、振り分け役が複数だと同じ台へ殺到する。無作為な2台だけ見て軽いほうを選ぶと、全台を見たのとほぼ同じところまで平らになる。

この章で作るもの

1台では捌けない負荷は、同じ役割のサーバを何台も並べて分ける。その前に立ってリクエストを振り分けるのがロードバランサになる。仕事は単純に見える。 来たリクエストを、後ろのどれか1台へ渡す。決めるのはそれだけだ。

だが「どれか」の選び方で、暇な台と溢れた台が同時に生まれる。選び方を4つ作って、それぞれ何を見て、何を見ないかを比べる。

先に押さえることが3つある。

見ないと偏る: 混み具合を見ずに順番へ回すと、重いものが集まった台だけ突出する
全部見ると群れる: いちばん空いた台へ送ると、振り分け役が複数のとき全員が同じ台へ殺到する
2台だけ見れば足りる: 無作為な2台の軽いほうを選ぶだけで、全台を見たのとほぼ同じになる

① 順番に回す(ラウンドロビン)

いちばん単純な選び方から。カーソルを1つずつ進めて、台数で割った余りの台へ渡す。 1台目、2台目、3台目、また1台目、と順繰りに回るので、ラウンドロビンと呼ばれる。


// pickRoundRobin は順番に1台ずつ回す。
//
// 台の混み具合は一切見ない。カーソルを1つ進めて、台数で割った余りを返すだけ。
// 状態を見ないので速く、振り分け役が何台居ても同じように動く。
// 代わりに、重いリクエストが特定の台に集まっても気づけない。
func (b *Balancer) pickRoundRobin() int {
	i := b.rr % len(b.backends)
	b.rr++
	return i
}

台の混み具合は一切見ていない。見ないので速いし、覚えておく状態はカーソル1つだけ。振り分け役が何台並んでいても、それぞれが自分のカーソルを進めるだけで動く。

リクエストの重さが全部同じなら、これで完璧になる。20台に2000件を流すと、テストで全台がちょうど100件ずつになることを固定した。割り切れる以上、偏りようがない。

崩れるのは、リクエストの重さがばらついたときだ。10件に1件だけ10倍重いものが混じる筋書きで測った。

	いちばん混んだ台	いちばん空いた台
ラウンドロビン	1,000	100

10倍。理由は単純で、重いリクエストが10件おきに来て、台が20台あるからだ。 10と20の倍数が噛み合って、重いものが毎回きっかり同じ台に落ちる。順番に回すこと自体は公平なのに、来る順に周期があると公平でなくなる。

これが「見ないことの代償」になる。その台がもう溢れていても、順番が来れば渡してしまう。

② 全台を見る(最少接続)と、その落とし穴

見ないから偏るなら、見ればいい。全部の台の処理中の数を数えて、いちばん少ない台へ渡す。最少接続(least connections)と呼ばれる方式になる。


// pickLeastConn は全台を見て、いま処理中の数がいちばん少ない台を選ぶ。
//
// 混み具合を見るので、重さがばらついても偏らない。
// 代わりに毎回すべての台を見ることになり、振り分け役が複数居ると
// 全員が同じ「いちばん空いた台」を選んで殺到する。
func (b *Balancer) pickLeastConn() int {
	best := 0
	for i := 1; i < len(b.backends); i++ {
		if b.backends[i].active < b.backends[best].active {
			best = i
		}
	}
	return best
}

同じ、重さがばらつく筋書きで測ると崩れない。

	いちばん混んだ台	いちばん空いた台
ラウンドロビン	1,000	100
最少接続	196	187

10倍の開きが、1.05倍に収まった。混み具合を見ているのだから当然ではある。テストで、混み具合を見る方式が最大と最小の比を2倍以内に収めることを固定した。

ではこれが答えかというと、そうならない。問題は台数ではなく、振り分け役の数になる。

大きなサービスでは、ロードバランサ自体も何台も並ぶ。各々が独立に「いま最も空いている台」を選ぶと、全員が同じ台を最少だと判断して、一斉にそこへ送る。次の瞬間その台はいちばん混んだ台になる。今度は別の台が最少になり、また全員が殺到する。負荷が台から台へ波のように押し寄せる。群集効果(herd behavior)と呼ばれる形になる。

  時刻 t        b0:8  b1:8  b2:2  b3:9      ← 全員が b2 を最少と判断
  LB×4 が一斉に送る          ↓↓↓↓
  時刻 t+1      b0:8  b1:8  b2:6  b3:9      ← 今度は b2 が混む番

  時刻 t+2      b0:8  b1:8  b2:6  b3:9      ← 全員が b0 か b1 を最少と判断
                 ↓↓↓↓                        …これが繰り返される

最少接続を複数の振り分け役が同時に使うと起きること。全員が同じ「いちばん空いた台」を見て、そこへ一斉に送る

選ぶ主体が1つなら最適に近く、複数だと不安定になる。見ることそのものが悪いのではなく、全員が同じものを見て同じ結論に達するのが悪い。

③ 2台だけ見る(P2C)

そこで折衷案になる。全台は見ない。無作為に2台だけ選んで、そのうち軽いほうへ渡す。選択肢が2つあるので P2C(power of two choices)と呼ばれる。


// pickP2C は無作為に2台だけ選び、そのうち処理中の数が少ないほうを返す。
//
// 全台は見ないので、振り分け役が何台居ても同じ台へ殺到しない。
// それでいて、1台を無作為に選ぶのに比べて偏りがはっきり小さくなる。
// 2台目は「1台目を除いた n-1 台」から引くので、同じ台を2回引かない。
func (b *Balancer) pickP2C() int {
	n := len(b.backends)
	if n == 1 {
		return 0
	}
	i := b.rand.intn(n)
	j := b.rand.intn(n - 1)
	if j >= i {
		j++ // i を除いた n-1 台から選ぶ
	}
	if b.backends[j].active < b.backends[i].active {
		return j
	}
	return i
}

無作為に選ぶので、振り分け役が複数居ても同じ2台を引くとは限らない。だから殺到しない。それでいて混み具合は見ているので、偏りにも強い。

効き目を測った。20台に2000件(平均100件)を流す。

	いちばん混んだ台
無作為に1台選ぶ	111
P2C(無作為な2台の軽いほう)	101
最少接続(全台を見る)	100

無作為に1台選ぶと、平均100に対して最大111まで膨らむ。これは箱にボールを投げると必ず飛び抜けて多い箱が出るのと同じで、避けられない。 2台のうち軽いほうを選ぶだけで、はみ出しが11から1に縮む。全台を見た最少接続の100にほとんど届いている。

理由は確率の性質になる。n台にm件を無作為に1台ずつ投げると、最も混んだ台の負荷は平均 + O(log n / log log n) まで膨らむ。ところが選択肢を2つにして軽いほうを選ぶと、これが O(log log n) まで落ちる。 1000台なら log n はおよそ10、log log n はおよそ3になる。 選択肢を1つから2つに増やすところだけが効いていて、3つ4つに増やしても大して変わらない。

重さがばらつく筋書きでも、最少接続とほぼ同じところに収まった(最大197 / 最小182)。 全台を見ずに、全台を見たのとほぼ同じ結果が出る。これが P2C の全部になる。

④ 同じキーを同じ台へ寄せる(ハッシュと円環)

ここまでは「どの台でもいい」前提だった。だがキャッシュサーバのように、 同じキーは同じ台に当たってほしい場合がある。別の台に行くと、そこにはキャッシュが無い。

「同じ入力から常に同じ数が出る」道具がハッシュ関数になる。ハッシュとHMACで作ったものと同じで、文字列を混ぜて1つの整数にする。値そのものに意味は無いが、同じキーからは何度でも同じ値が出る。だから hash(key) % 台数 で台を決めれば、同じキーは必ず同じ台へ行く。

問題は台数が変わったときだ。余りを取る数が5から6に変われば、 ほとんどのキーで結果がずれる。キャッシュなら大半が一斉に入れ替わり、全部ミスして裏のデータベースを直撃する。

一貫ハッシュはこれを避ける。台とキーを同じ円環の上のハッシュ値として置き、キーから時計回りに最初に出会った台へ渡す。

        0 ─────────────── 2^32
        │                   │
   a ●──┼── k1 ── b ●── k2 ─┼── c ●── k3 ──┐
        │                   │              │  ← 回り込んで a へ
        └───────────────────┘──────────────┘

   f を b と c の間に足すと…

   a ●──── k1 ── b ●── k2 ── f ●── c ●── k3 ──┐
                          ↑ ここに落ちるキーだけ振り先が b から f へ動く
                            k1 も k3 も動かない

円環に台とキーを置き、キーから時計回りで最初に出会った台へ渡す。台を1つ足しても、動くのはその点の手前に落ちるキーだけ


// replicas は 1 台あたりのリング上の仮想ノード数。多いほど分散が均等になる。
const replicas = 64

// hash32 は FNV-1a による 32bit ハッシュ(外部依存を避け自前で書く)。
func hash32(s string) uint32 {
	var h uint32 = 2166136261
	for i := 0; i < len(s); i++ {
		h ^= uint32(s[i])
		h *= 16777619
	}
	return h
}

// buildRing は各台を replicas 個の仮想ノードとしてリング上に配置し、ソートする。
func (b *Balancer) buildRing(rep int) {
	b.ring = b.ring[:0]
	for i, be := range b.backends {
		for v := 0; v < rep; v++ {
			key := be.ID + "#" + itoa(v)
			b.ring = append(b.ring, vnode{hash: hash32(key), backend: i})
		}
	}
	sort.Slice(b.ring, func(x, y int) bool { return b.ring[x].hash < b.ring[y].hash })
}

// pickRing は key のハッシュ以上で最も近い仮想ノードの台を返す(円環なので回り込む)。
func (b *Balancer) pickRing(key string) int {
	if len(b.ring) == 0 {
		return 0
	}
	h := hash32(key)
	// h 以上の最初の点を二分探索。無ければ先頭(円環の回り込み)。
	idx := sort.Search(len(b.ring), func(i int) bool { return b.ring[i].hash >= h })
	if idx == len(b.ring) {
		idx = 0
	}
	return b.ring[idx].backend
}

// itoa は小さな非負整数を文字列にする(strconv を避ける)。
func itoa(n int) string {
	if n == 0 {
		return "0"
	}
	var buf [10]byte
	i := len(buf)
	for n > 0 {
		i--
		buf[i] = byte('0' + n%10)
		n /= 10
	}
	return string(buf[i:])
}

台を1つ足すと、円環の上にその台の点が増える。 振り先が変わるのは、新しい点とその手前の点の間に落ちたキーだけになる。 5台から6台へ増やして、1000個のキーがどれだけ動くか測った。

	動いたキー
割り算(`hash % 台数`)	883 / 1000
円環(一貫ハッシュ)	252 / 1000

割り算は9割近くが動く。円環なら4分の1で済む。テストで、割り算が4分の3以上動くこと、円環が3分の1以下に収まること、そしてその差が3倍以上あることを固定した。

各台を1点でなく複数の点として円環にばらまくのが実用上の勘所になる。 1点だと台ごとの担当区間の広さがばらつき、負荷が不均等になる。この実装では1台あたり64点に散らして均している。

動かす

方式を切り替えて、同じリクエスト列を後ろの台に振ったときの積み上がり方を比べられる。いちばん混んだ台がどこまで高くなるかを見ると、P2C がランダムよりずっと平らで、最少接続に近いことが分かる。

デモロードバランサ最大負荷 11 / 平均 10

ラウンドロビン最少接続P2Cランダム

平均 10

P2C: 2 台だけ無作為に見て軽い方へ。全台を見ないのに最大は 11(平均+1)。ランダムよりずっと平ら、最少接続にも肉薄

120 / 120 件

12 台に 120 リクエスト(平均 10)を振ったときの、各台の積み上がり。方式を切り替えて、いちばん高い棒(最も混んだ台)の高さを比べてほしい。ランダムは平均から大きくはみ出し、 P2C は 2 台を見るだけでほぼ平らになる。最少接続は最も平らだが全台を見る必要があり、複数のロードバランサが並ぶと同じ台への殺到(群集効果)を招く。

設計の観点

見る範囲を、振り分け役の数で決める: 1台なら全台を見ていい。複数並ぶなら、全員が同じ結論に達しない選び方が要る
周期を疑う: 順番に回す方式は、来る順に周期があると崩れる。台数と周期が噛み合うと1台に集中する
一部を見るだけで足りることがある: 2台見れば全台見たのとほぼ同じ。3台目を足す得は小さい
無作為さが群れを防ぐ: 決定的に選ぶと全員が同じ答えを出す。無作為に選べば、同じ答えでも同じ台には集まらない
状態を台に寄せるかで方式が変わる: どの台でもいいなら P2C、同じキーを同じ台へ寄せたいなら円環
落ちた台を外す: どの方式も、生死を見ていなければ落ちた台へ渡し続ける。実物には健康チェックが要る

対照と実例

方式	見る範囲	重さのばらつきに	振り分け役が複数のとき	使いどころ
ラウンドロビン	見ない	弱い(10倍まで開いた)	問題なし	重さが揃っているとき
最少接続	全台	強い	殺到する	振り分け役が1台のとき
P2C	2台	強い	問題なし	大規模・振り分け役が複数
一貫ハッシュ	円環	キー次第	問題なし	同じキーを同じ台へ寄せたいとき

裏どり:

2択で足りるのは証明されている: Mitzenmacher の The Power of Two Choices in Randomized Load Balancing が、最大負荷が O(log n / log log n) から O(log log n) へ落ちることを示している。1つから2つへの1歩だけが大きく、そこから先は小さいというのがこの結果の要点になる
Envoy と gRPC は P2C を使う: どちらも least request の名前で、既定は全台ではなく無作為な2台を見る形になっている。台数が増えるほど全台走査が重くなるうえ、群集効果が出るため
NGINX と HAProxy は最少接続を持つ: least_conn / leastconn として標準にある。振り分け役が1台の構成では今でも妥当な選択になる
一貫ハッシュの原典: Karger らの論文がウェブキャッシュのために提案したもの。memcached の ketama、Amazon Dynamo、Cassandra が同じ考えでデータを台に置いている
仮想ノードの数: ketama は1台あたり160点、Dynamo は台の性能に応じて数を変える。点の数がそのまま重み付けになるので、速い台に多く点を置けば多く受け持たせられる

簡略化したこと

健康チェックなし: 落ちた台を候補から外す仕組みは持たない。実物ではこれが無いと落ちた台へ渡し続ける
重み付けなし: 台ごとの性能差を反映しない。円環なら点の数で表せるが、実装していない
処理中の数は論理的: 実際に並行実行するのではなく、Acquire / Release で数えるだけ
振り分け役は1つ: 群集効果は図と説明で示すだけで、複数の振り分け役を並べて測ってはいない
仮想ノードは固定64点: 実物は台の重みに応じて数を変える
再試行なし: 渡した先が失敗したときに別の台へ振り直す動きは扱わない

参考資料

M. Mitzenmacher, The Power of Two Choices in Randomized Load Balancing — 2択で足りることの一次資料
Envoy: Load Balancers — least request が既定で2台だけ見る話
Consistent Hashing (Karger et al.) — 円環の原典と解説
実装: resilience/loadbalancer

ロードバランサ ​

この章で作るもの ​

① 順番に回す(ラウンドロビン) ​

② 全台を見る(最少接続)と、その落とし穴 ​

③ 2台だけ見る(P2C) ​

④ 同じキーを同じ台へ寄せる(ハッシュと円環) ​

動かす ​

設計の観点 ​

対照と実例 ​

簡略化したこと ​

参考資料 ​