サーバーサイドでキャッシュという仕組みは非常に重要です。オリジナルのデータを保存しているDBへの負荷を減らすため、ユーザーへのレスポンスを速くするためなどの理由で使われることが多いと思います。とりあえずキャッシュしておけば早くなるだろう、そう思って雑にキャッシュできそうなデータをRedisに突っ込んでいた時期がありました。
この記事では、キャッシュを扱う上で気をつけなければいけない問題の1つである Cache Stampede について紹介します。

Cache Stampede とは

一般的なアプリケーションサーバーでは、メインのDBにオリジナルのデータを入れておき、更新頻度が低いものやリアルタイム性が求められないものなどをRedisやMemcachedなどのキャッシュストレージにいれるといった構成を取ることが多いと思います。
アプリケーションサーバーの挙動としては、まずキャッシュを取りに行ってヒットしたらその値を返し、ヒットしなければオリジナルのデータベースを取りに行ってキャッシュを更新する、といった感じになるでしょうか。キャッシュの有効期限が切れたり削除された時、キャッシュのデータがアプリケーションサーバーによって更新されることになります。
この仕組みによってキャッシュがあるときはメインのDBへの負荷を減らすことができ、キャッシュを更新したタイミングにだけDBへとアクセスするようにできます。

では、多くのサーバーが参照しているキャッシュを消した(or期限が切れた)場合はどうなるでしょうか。

各アプリケーションサーバーは参照しているキャッシュが無いため、メインのDBへとアクセスし、キャッシュを更新しようとします。1度アプリケーションサーバーのうちどれかがキャッシュを更新してしまえば、そのあとのリクエストはキャッシュを見るようになるので、サーバーの台数や同時リクエスト数があまり多くない場合は問題にならないかもしれません。

しかし、キャッシュが消えてから更新されるまでの間にかなりのリクエストが来た場合、メインのDBへそれらのリクエストが送られてしまいます。アプリケーションサーバーの台数が多かったり1つのアプリケーションサーバーが並列にリクエストを捌いている場合は注意しなければいけません。
本来メインのDBへのアクセスを減らす目的だったキャッシュが役割を果たさなくなり、瞬間的に増えたそのリクエストにDBが耐えきれなかった場合は最悪落ちてしまうかもしれません。

このように、キャッシュが切れたタイミングでオリジナルのサーバーへとリクエストが殺到してしまう現象を Cache Stampede や、キャッシュシステムにおける Thundering Herd 問題 などと呼ばれます。
(注: Thundering Herd 問題はキャッシュに限った問題ではないです)

対策例

Cache Stampede の対策例として、リクエスト元で排他制御を行う方法を紹介します。

リクエスト元がアプリケーションサーバーでかつ並列にリクエストを捌いていた場合、キャッシュが切れたタイミングで1つのサーバーからも複数のリクエストが送られてしまうことになります。これを防ぐため、同じキャッシュに対するオリジナルのサーバーへのリクエストやキャッシュの更新リクエストは1つにしたいです。

例えばGoの場合、 singleflight package を使用することで解決できることがあります。singleflight package を使うことで、関数が並列で呼び出された際に1回だけ処理を行い、その結果を呼び出し側に共有するといったことが簡単に実装できます。

以下が実装例です。実行してみると10回run()関数を呼び出しますが、calledを出力する部分は数回しか呼ばれないことがわかると思います。

package main

import (
    "fmt"
    "log"
    "sync"

    "golang.org/x/sync/singleflight"
)

var group singleflight.Group

func main() {
    var wg sync.WaitGroup
    for i := 0; i < 10; i++ {
        wg.Add(1)
        go func() {
            defer wg.Done()
            run("key")
        }()
    }
    wg.Wait()
}

func run(key string) {
    v, err, shared := group.Do(key, func() (interface{}, error) {
        fmt.Println("called")
        return key, nil
    })
    if err != nil {
        log.Fatal(err)
    }
    fmt.Printf("result: %s, shared: %t\n", v, shared)
}

実行結果例

called
result: key, shared: true
result: key, shared: true
result: key, shared: true
result: key, shared: true
result: key, shared: true
result: key, shared: true
result: key, shared: true
result: key, shared: true
result: key, shared: true
result: key, shared: true

他にも Cache Stampede の対策例として、キャッシュが切れても一定時間はキャッシュを返し続ける Stale While Revalidate や、そもそも同じタイミングでキャッシュが切れないようにするといった対策が考えられます。

まとめ

Cache Stampede を理解し、キャッシュが切れた時に適切にリクエストを捌けるよう対策する

参考

https://en.wikipedia.org/wiki/Cache_stampede
https://en.wikipedia.org/wiki/Thundering_herd_problem
https://labs.cybozu.co.jp/blog/kazuho/archives/2007/09/cache_and_thundering_herd.php
https://techblog.yahoo.co.jp/infrastructure/cache-reducing-origin-request/

この記事を読んで「面白かった」「学びがあった」と思っていただけた方、よろしければ Twitter や facebook、はてなブックマークにてコメントをして頂けると嬉しいです。
また DeNA 公式 Twitter アカウント @DeNAxTech では、 Blog記事だけでなく色々な勉強会での登壇資料も発信してます。こちらもぜひフォローして頂けると嬉しいです。
Follow @DeNAxTech

キャッシュが切れるときに発生する問題について

Cache Stampede とは

対策例

まとめ

参考