Fri, 02 Aug
groupcache を読む #2

groupcache を読む #1 では、外側から groupcache の処理の流れを外側から追ってみた。これで大体、どこに何があるかのあたりがついたので、今回は Comparison to memcached にある memcached に無い機能について、どこで実装されているかを追ってみよう。

Thundering Herd 対策

memcached のような独立したキャッシュサーバーでは、キャッシュが無い場合の処理が、以下のようにだぶってしまうことがある。

  1. クライアント c1 が、キー k1 を get するが存在しなかった。
  2. クライアント c1 は、キー k1 に対応する値を (たとえば MySQL などに問い合わせて) 作りはじめる。
  3. クライアント c2 も、キー k1 を get するが、まだ c1 が作っている最中なので、存在しなかった。
  4. クライアント c2 も、キー k1 に対応する値を作りはじめる。
  5. クライアント c1 が、キー k1 に対応する値を作り終わり set する。
  6. クライアント c2 が、キー k1 に対応する値を作り終わり set する。

k1 が沢山のクライアントから get されるような人気のあるキーだと、キーが消えた瞬間に沢山のクライアントで同じ処理が走ってしまう。

groupcache の場合、c1 が k1 を get してそれが存在しない (groupcache.Group#lookupCache が失敗した) 場合には、k1 が存在しないと伝えるかわりに k1 の生成処理が実行される。作っている最中に c2 が k1 をリクエストした場合には、そのまま c2 を待たせるようになっている。

この排他制御は groupcache.Group#load で呼んでいる groupcache.Group#loadGroup が行っている。

// load loads key either by invoking the getter locally or by sending it to another machine.
func (g *Group) load(ctx Context, key string, dest Sink) (value ByteView, destPopulated bool, err error) {
	g.Stats.Loads.Add(1)
	viewi, err := g.loadGroup.Do(key, func() (interface{}, error) {

groupcache.group#loadGroup は singleflight.Group 型で、キーごとの sync.WaitGroup の map と、その map への一連の操作をアトミックに行うための sync.Mutex を持っている。

// call is an in-flight or completed Do call
type call struct {
	wg  sync.WaitGroup
	val interface{}
	err error
}

// Group represents a class of work and forms a namespace in which
// units of work can be executed with duplicate suppression.
type Group struct {
	mu sync.Mutex       // protects m
	m  map[string]*call // lazily initialized
}

ホットなキーの分散

ホットなキーの分散は、Thundering Herd 対策にくらべるとだいぶ簡単だ。groupcache ではキーのハッシュ値をもとに、キーに対応するホストを一意に決めている。逆にいうと、ホストはあるキーに対して、自分が値を生成するべきか、他のホストから値をとってくるべきかを知っている。

しかし、他のホストから値をとった際にも、ランダムで値を自分の手元に置いておく。この実装は groupcache.Group#getFromPeer にある。

func (g *Group) getFromPeer(ctx Context, peer ProtoGetter, key string) (ByteView, error) {
	req := &pb.GetRequest{
		Group: &g.name,
		Key:   &key,
	}
	res := &pb.GetResponse{}
	err := peer.Get(ctx, req, res)
	if err != nil {
		return ByteView{}, err
	}
	value := ByteView{b: res.Value}
	// TODO(bradfitz): use res.MinuteQps or something smart to
	// conditionally populate hotCache.  For now just do it some
	// percentage of the time.
	if rand.Intn(10) == 0 {
		g.populateCache(key, value, &g.hotCache)
	}
	return value, nil
}

プロダクション環境での運用と野次馬情報

groupcache では groupcache.Group#Stats に統計情報 (キャッシュがどのくらいヒットしたか、など) をいれているけど、http.go には、この統計情報を露出させるエンドポイントがない。groupcache をプロダクション環境に導入する場合は、まずここを変更して /_groupcache_meta/グループ名/Stats あたりから GET できるようにするといいと思う。

groupcache は Google のなかでの運用実績があるといわれている。でも、こういうところをみると、http.go で提供されている HTTP まわりは、Google 社内では使われていないのかもと思う。

スライド にも groupcache.HTTPPool が出てくるところで

This peer interface is pluggable. (e.g. inside Google it’s automatic.)

と書かれている。

また、http.go では Content-Type: application/x-protobuf でレスポンスを返しているけど、Protocol Buffers には公開されていない RPC 実装がある。

Protocol Buffers: Leaky RPC の Kenton Varda のコメント 曰く:

The Protocol Buffer RPC support is, in fact, used for practically all inter-machine communication at Google. We were unable to make our RPC system part of this release, but we have one, and it works on top of exactly the RPC stubs that are in this release. We certainly are not going to remove this support. We rely on it.

というわけで groupcache も、Google の中では HTTP + Content-Type: application/x-protobuf ではなくて、Protocol Buffers RPC をしゃべるのが自然じゃないかと思う。

まとめ

groupcache について、README.md でふれられている機能の実装と、HTTP インターフェースのちょっと足りないところについて説明しました。

  • get されたキーに対応する値がない場合は、その値に対する他の get をブロックさせながら、値を生成するので Thundering Herd 問題はおこらない。とはいえ、その値の生成がすごく遅い場合は、当然こまる。
  • groupcache が他の groupcache から値をとってきた場合、一定の確率でランダムにそれをローカルにコピーする。これで人気のあるキーを持ったホストへのアクセスの集中を防いでいる。
  • 現状、外部から統計情報をとることができないので、プロダクション環境に投入する場合は、すこし手を加えたほうがよいと思う。

memcached を知っていると「キーに対応する値を返す」のような memcached の機能、「キーのハッシュ値を計算してとりにいくクライアントをきめる」のような memcached クライアントの機能、そして「キーに対応する値がなかったので、なんとかして生成する」みたいなアプリケーションの機能がいっしょくたになっているので、ちょっと混乱しますね。

Back