Wed, 31 Jul
groupcache を読む #1

groupcache は Go むけのキャッシュライブラリだ。Brad Fitzpatrick が dl.google.com を C++ から Go に書き換えるときに書いたもので、いまでは Google の他のサービスの一部でも使われているらしい。

groupcache は、名前の末尾に “d” がつかないことからもわかるように、memcached のようなデーモンではない。Go で書かれたアプリケーションに組み込めるライブラリで、インプロセスなキャッシュシステムと、複数の groupcache を連携させるためのネットワーク部分から構成されている。

それでは、OSCON 2013 のスライド45ページ目からのサンプルコードをみながら、実際のコード (リビジョン: 0e1c218) を追ってみよう。

groupcache.NewHTTPPool

groupcache は、複数のホストをまとめて一つのキャッシュプールとして扱うことができる。まず groupcache.NewHTTPPool で groupcache サーバーを起動して、groupcache.HTTPPool#Setで自分以外のホストの場所を設定する。

me := "http://10.0.0.1"
peers := groupcache.NewHTTPPool(me)

// Whenever peers change:
peers.Set("http://10.0.0.1", "http://10.0.0.2", "http://10.0.0.3")

groupcache.NewHTTPPool の実装は http.go にある。このメソッドは groupcache.HTTPPool の初期化と、HTTP サーバーの起動を行う。

// NewHTTPPool initializes an HTTP pool of peers.
// It registers itself as a PeerPicker and as an HTTP handler with the
// http.DefaultServeMux.
// The self argument be a valid base URL that points to the current server,
// for example "http://example.net:8000".
func NewHTTPPool(self string) *HTTPPool {
    if httpPoolMade {
        panic("groupcache: NewHTTPPool must be called only once")
    }
    httpPoolMade = true
    p := &HTTPPool{basePath: defaultBasePath, self: self}
    RegisterPeerPicker(func() PeerPicker { return p })
    http.Handle(defaultBasePath, p)
    return p
}

冒頭の panic 文からもわかるように groupcache.NewHTTPPool は複数回は呼び出せない。ここで返している groupcache.HTTPPool はプロセス全体で共有される。

groupcache.HTTPPool#Set は groupcache.HTTPPool の peers を設定するだけだ。ネットワーク経由でネゴシエーションをしたりはしない。

// Set updates the pool's list of peers.
// Each peer value should be a valid base URL,
// for example "http://example.net:8000".
func (p *HTTPPool) Set(peers ...string) {
    p.mu.Lock()
    defer p.mu.Unlock()
    p.peers = append([]string{}, peers...)
}

さて、http.Handle の第二引数になっているのからもわかるように、groupcache.HTTPPool は http.Handler インターフェースを実装している。groupcache 間の通信の感じをつかむために groupcache.HTTPPool#ServeHTTP をみてみよう。

func (p *HTTPPool) ServeHTTP(w http.ResponseWriter, r *http.Request) {
    // Parse request.
    if !strings.HasPrefix(r.URL.Path, p.basePath) {
        panic("HTTPPool serving unexpected path: " + r.URL.Path)
    }
    parts := strings.SplitN(r.URL.Path[len(p.basePath):], "/", 2)
    if len(parts) != 2 {
        http.Error(w, "bad request", http.StatusBadRequest)
        return
    }
    groupName, err := url.QueryUnescape(parts[0])
    ...
    key, err := url.QueryUnescape(parts[1])
    ...

    // Fetch the value for this group/key.
    group := GetGroup(groupName)
    ...
    var ctx Context
    if p.Context != nil {
        ctx = p.Context(r)
    }
    var value []byte
    err = group.Get(ctx, key, AllocatingByteSliceSink(&value))
    ...

    // Write the value to the response body as a proto message.
    body, err := proto.Marshal(&pb.GetResponse{Value: value})
    ...
    w.Header().Set("Content-Type", "application/x-protobuf")
    w.Write(body)
}

memcached みたいなものを期待していると、かなり拍子抜けするだろう。groupcache のネットワークプロトコルには、HTTP の GET /_groupcache/グループ名/キー名に対してキーの内容を返す get しか存在しない。

groupcache.NewGroup

では set はだれがやってくれるのだろうか? その前に groupcache のグループについて説明しよう。

groupcache では生成方法の同じキーの集まりを「グループ」として定義する。例えば SELECT * FROM customers WHERE id=? でひけるテーブルが MySQL 上にあって、この SQL 文の結果を customer:$id というキーでキャッシュにいれるとする。この場合 customer:1 と customer:23, customer:456 は同じ「グループ」に属することになる。

スライドのサンプルコードでは thumbnail というグループと、その生成方法を定義している。

var thumbNails = groupcache.NewGroup("thumbnail", 64<<20, groupcache.GetterFunc(
    func(ctx groupcache.Context, key string, dest groupcache.Sink) error {
        fileName := key
        dest.SetBytes(generateThumbnail(fileName))
        return nil
    }))

memcached はアプリケーション固有のロジックを一切持たない、独立したキャッシュサーバーだった。一方 groupcache は、アプリケーションのプロセスの中に組み込まれ、グループの定義の際に値の生成方法を教えられる。そのため、ネットワークの外から他人が値を set しなくとも、自分自身でキーに対応する値を生成できるのだ。

というわけで、冒頭の「set はだれがやってくれるのだろうか?」への答えは「groupcache 自身」ということになる。

groupcache.NewGroup の実装は groupcache.go にある。ひたすら初期化するだけなので、とくにひっかかるところもないと思う。

// NewGroup creates a coordinated group-aware Getter from a Getter.
//
// The returned Getter tries (but does not guarantee) to run only one
// Get call at once for a given key across an entire set of peer
// processes. Concurrent callers both in the local process and in
// other processes receive copies of the answer once the original Get
// completes.
//
// The group name must be unique for each getter.
func NewGroup(name string, cacheBytes int64, getter Getter) *Group {
    return newGroup(name, cacheBytes, getter, nil)
}

// If peers is nil, the peerPicker is called via a sync.Once to initialize it.
func newGroup(name string, cacheBytes int64, getter Getter, peers PeerPicker) *Group {
    if getter == nil {
        panic("nil Getter")
    }
    mu.Lock()
    defer mu.Unlock()
    initPeerServerOnce.Do(callInitPeerServer)
    if _, dup := groups[name]; dup {
        panic("duplicate registration of group " + name)
    }
    g := &Group{
        name:       name,
        getter:     getter,
        peers:      peers,
        cacheBytes: cacheBytes,
    }
    if fn := newGroupHook; fn != nil {
        fn(g)
    }
    groups[name] = g
    return g
}

groupcache.Group#Get

グループは作成できたので、そこから値を取得してみよう。

var data []byte
err := thumbNails.Get(ctx, "big-file.jpg",
    groupcache.AllocatingByteSliceSink(&data))

これで big-file.jpg に対応するサムネイルが data から参照できるようになる。

groupcache.Group#Get はまずローカルのキャッシュをさがし、ヒットしなかった場合は、自分自身でキーに対応する値を生成するか、他の groupcache から値をもらうかして、その値を返す。

func (g *Group) Get(ctx Context, key string, dest Sink) error {
    g.peersOnce.Do(g.initPeers)
    g.Stats.Gets.Add(1)
    if dest == nil {
        return errors.New("groupcache: nil dest Sink")
    }
    value, cacheHit := g.lookupCache(key)

    if cacheHit {
        g.Stats.CacheHits.Add(1)
        return setSinkView(dest, value)
    }

    // Optimization to avoid double unmarshalling or copying: keep
    // track of whether the dest was already populated. One caller
    // (if local) will set this; the losers will not. The common
    // case will likely be one caller.
    destPopulated := false
    value, destPopulated, err := g.load(ctx, key, dest)
    if err != nil {
        return err
    }
    if destPopulated {
        return nil
    }
    return setSinkView(dest, value)
}

groupcache.Group#Stats へのアクセスは、get が何回あって、キャッシュヒットが何回あって、といった統計情報の操作なので、基本的には無視していい。

ローカルのキャッシュをさがす groupcache.Group#lookupCache は、2種類のキャッシュをひいて、対応する値が存在していたらそれを返すだけだ。このホストが生成に責任をもつキャッシュが groupcache.Group#mainCache に、他のホストが生成に責任を持っているのだけど、よくリクエストされるので高速化のためにローカルにおいておくキャッシュが groupcache.Group#hotCache に保持されている。

func (g *Group) lookupCache(key string) (value ByteView, ok bool) {
    if g.cacheBytes <= 0 {
        return
    }
    value, ok = g.mainCache.get(key)
    if ok {
        return
    }
    value, ok = g.hotCache.get(key)
    return
}

というわけで、ほとんどの処理は groupcache.Group#load からはじまることになる。

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) {
        g.Stats.LoadsDeduped.Add(1)
        var value ByteView
        var err error
        if peer, ok := g.peers.PickPeer(key); ok {
            value, err = g.getFromPeer(ctx, peer, key)
            if err == nil {
                g.Stats.PeerLoads.Add(1)
                return value, nil
            }
            g.Stats.PeerErrors.Add(1)
            // TODO(bradfitz): log the peer's error? keep
            // log of the past few for /groupcachez?  It's
            // probably boring (normal task movement), so not
            // worth logging I imagine.
        }
        value, err = g.getLocally(ctx, key, dest)
        if err != nil {
            g.Stats.LocalLoadErrs.Add(1)
            return nil, err
        }
        g.Stats.LocalLoads.Add(1)
        destPopulated = true // only one caller of load gets this return value
        g.populateCache(key, value, &g.mainCache)
        return value, nil
    })
    if err == nil {
        value = viewi.(ByteView)
    }
    return
}

groupcache.Group#loadGroup.Do は、あるキーに対する処理がプロセス内で複数はしらないように排他制御を行っている。そのなかでは

groupcache.Group#peers.PeerPicker を呼び出して、そのキーを持っているはずの groupcache をさがす
自分以外のホストが持っているはずのキーなら groupcache.Group#getFromPeer で別ホストから値を取得する
自分が持っているはずのキーなら、まだ生成されていないかキャッシュが消えてしまったということなので、groupcache.Group#getLocally でキーに対応する値を自分で生成する

という処理を行っている。

groupcache.Group#peers.PeerPicker

groupcache.Group#peers は groupcache.Group#Get の冒頭で、gropupcache.Group ごとに一回だけ初期化される。

func (g *Group) initPeers() {
    if g.peers == nil {
        g.peers = getPeers()
    }
}

func (g *Group) Get(ctx Context, key string, dest Sink) error {
    g.peersOnce.Do(g.initPeers)
    ...

groupcache.getPeers は peers.go に定義されている。

// RegisterPeerPicker registers the peer initialization function.
// It is called once, when the first group is created.
func RegisterPeerPicker(fn func() PeerPicker) {
    if portPicker != nil {
        panic("RegisterInitPeers called more than once")
    }
    portPicker = fn
}

func getPeers() PeerPicker {
    if portPicker == nil {
        return NoPeers{}
    }
    pk := portPicker()
    if pk == nil {
        pk = NoPeers{}
    }
    return pk
}

というわけで、groupcache.HTTPPool は groupcache.RegisterPeerPicker を介して、めでたく groupcache.Group#peers から参照できるようになった。

groupcache.HTTPPool#PickPeer はキーを渡すと、そのキーの取得方法を groupcache.ProtoGetter として返す。

func (p *HTTPPool) PickPeer(key string) (ProtoGetter, bool) {
    // TODO: make checksum implementation pluggable
    h := crc32.Checksum([]byte(key), crc32.IEEETable)
    p.mu.Lock()
    defer p.mu.Unlock()
    if len(p.peers) == 0 {
        return nil, false
    }
    if peer := p.peers[int(h)%len(p.peers)]; peer != p.self {
        // TODO: pre-build a slice of *httpGetter when Set()
        // is called to avoid these two allocations.
        return &httpGetter{p.Transport, peer + p.basePath}, true
    }
    return nil, false
}

どの groupcache がどのキーを持つかは、キーのハッシュ値から一意に決まる。自分自身がそのキーの担当の場合、自分自身からの取得方法は groupcache.ProtoGetter にはくるまずに nil を返している。

groupcache.Group#getFromPeer と groupcache.Group#getLocally

groupcache.ProtoGetter が返った場合は、それに対して groupcache.ProtoGetter#Get を呼び出す 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
}

サンプルコードの例だと peer は groupcache.httpGetter 型なので groupcache.httpGetter#Get をみてみよう。

func (h *httpGetter) Get(context Context, in *pb.GetRequest, out *pb.GetResponse) error {
    u := fmt.Sprintf(
        "%v%v/%v",
        h.baseURL,
        url.QueryEscape(in.GetGroup()),
        url.QueryEscape(in.GetKey()),
    )
    req, err := http.NewRequest("GET", u, nil)
    if err != nil {
        return err
    }
    tr := http.DefaultTransport
    if h.transport != nil {
        tr = h.transport(context)
    }
    res, err := tr.RoundTrip(req)
    if err != nil {
        return err
    }
    if res.StatusCode != http.StatusOK {
        return fmt.Errorf("server returned: %v", res.Status)
    }
    defer res.Body.Close()
    // TODO: avoid this garbage.
    b, err := ioutil.ReadAll(res.Body)
    if err != nil {
        return fmt.Errorf("reading response body: %v", err)
    }
    err = proto.Unmarshal(b, out)
    if err != nil {
        return fmt.Errorf("decoding response body: %v", err)
    }
    return nil
}

みての通り、ふつうに HTTP リクエストを送って、レスポンスボディを値としているのがわかる。

groupcache.Group#getLocally は、グループの定義時に設定した groupcache.Group#getter に対して Get を呼ぶだけだ。

func (g *Group) getLocally(ctx Context, key string, dest Sink) (ByteView, error) {
    err := g.getter.Get(ctx, key, dest)
    if err != nil {
        return ByteView{}, err
    }
    return dest.view()
}

ここまでのまとめ

さすがに長くなりすぎたので、いったんまとめよう。

groupcache は Go むけのキャッシュライブラリだ。memcached のような独立したキャッシュサーバーとちがい、アプリケーションの中に組み込まれて使われるので、自分自身でキーに対応する値を生成できる。
groupcache は複数のホストを、まとめてひとつのキャッシュプールとして使うことができる。
公開されている groupcache.HTTPPool では、キーのハッシュ値をホストの数で割るという簡単な方式で、あるキーに対応するホストを一意に決め、別ホストからキーに対応する値を取得する際には HTTP を使う。

次回は README.md に列挙されている特徴の確認と、本番環境への導入にむけての壁、野次馬情報について説明します。

Back