💸

Facebookの論文に学ぶ結果整合性を持つキャッシュパターン

に公開
Redis
DynamoDB
DB
キャッシュ
Memcached
tech

概要

Facebook(meta)のキャッシュ活用に関する有名なケーススタディ論文
Scaling Memcache at Facebook(2013)
https://www.usenix.org/system/files/conference/nsdi13/nsdi13-final170_update.pdf
に書かれているKVデータベースを利用したキャッシュの運用方法について学んだのでメモします。

この手法は、多くの一般的Webサービスで使える定石的な手法に個人的に思うのですが、日本語であまり解説記事を読んだことがないので記載します[1]。

用語の整理

キャシュパターンは readに関するものとwriteに関するものの２つあります。この記事では

  • read
    • read-through
    • look aside
  • write
    • write-through
    • demand-fill
      というパターンが関係します

基本:demand-fill/look aside cache

参照している論文では
read:: look aside
write:demand-fill
というパターンを採用しています。具体的な手順は以下のとおりです。

  • write(書き込み)
  1. UPDATE/INSERT : リレーショナルDBにデータ(ユニークキー：K,値:V)を書き込む
  2. DELETE : キャッシュDB(memcached/redisなど)の該当するキー(K)のデータを削除する
  • read(読み込み)
    • キャッシュDBにおいて(キーK)にデータがヒットする場合
      1.GET : そのままヒットしたデータを返す
    • キャッシュDBにおいて(キーK)のデータが存在しない
      1.SELECT : リレーショナルDBからデータ(V)取得
      2.SET : キャッシュDBにデータ(キー K, 値 V)を登録する

この手法を demand-fill/look aside cacheと呼ぶらしいです。
ですが、シナリオによってはこのやり方だと不整合を永続化する恐れがあります。
そのため leaseというトークンを使用した改良版が存在します(後述)

なぜ demand-fill/look aside cacheなのか

leaseを活用した改良版に入る前に demand-fill/look aside cache の特徴を質疑応答を通じて理解したいと思います。

Q1. read-throughとlook asideの違い
Q2. なぜ値のUPDATE時にキャッシュDBに値をSETしないのか write-throughとの比較
Q3. write時に UPDATE/INSERT と DELETE を逆の順番でやったらどうなるか？

Q:なぜ値のUPDATE時にキャッシュDBに値をSETしないのか(write-through/look asideではだめか？)

A:以下のようなシナリオでキャッシュとRDBの矛盾が生じ、次のwriteまでその矛盾が永続化して結果整合性が破綻する恐れがあります。
以下、2つのトランザクションT1(write)とT2(write)が存在するものとする
２つとも同じキー(K)のデータを書き込もうとしています

  • T1(w):INSERT/UPDATE(K, V1)
  • T2(w):INSERT/UPDATE(K, V2)
  • T2(w):SET(K, V2)
  • T1(W):SET(K, V1)
    (次のWRITEまでキャッシュはV1 RDBは V2 という形で矛盾が生じてしまう)

一方 DELETE はKに対して冪等な操作のため、どのような順番で何回やっても結果が変わらないという利点があります。

Q:write時に UPDATE/INSERT と DELETE を逆の順番でやったらどうなるか？

A:以下のようなシナリオでキャッシュとRDBの矛盾が生じ、次のwriteまでその矛盾が永続化して結果整合性が破綻する恐れがあります。
以下、2つのトランザクションT1(write)とT2(read)が存在するものとする
２つとも同じキー(K)のデータを読んだり書いたりする

  • T1(w):DELETE(K)
  • T2(r):Vold = GET(K) -> キャッシュミス
  • T2(r):Vold = SELECT(K)
  • T2(r):SET(K, Vold)
  • T1(w):INSERT/UPDATE(K, Vnew)
    (次のWRITEまでキャッシュはVold RDBは Vnew という形で矛盾が生じてしまう)

Q:read through と look asideの違い

A:キャッシュミス時にFreshなデータを取得する責務がキャッシュDBにあるか、アプリケーションのコードにあるかの違い

  • read-through -> キャッシュDBにある
  • look aside -> アプリケーション側にある

read-through に対応するにはキャッシュDBのライブラリやキャッシュDB本体がネイティブで対応している必要がある 例:Redis
今回の議論ではこの違いは重要ではない

改良版:demand-fill/look aside cache(with lease)

単純なdemand-fill/look aside cacheでキャッシュとオリジンの不整合が起きるケースについて考えてみます。
以下、2つのトランザクションT1(read)とT2(write)が存在するものとします
２つとも同じキー(K)のデータを読み書きしようとしています

  • T1(r):V1 = GET(K) -> キャッシュミス
  • T1(r):V1 = SELECT(K)
  • T2(w):UPDATE/INSERT(K, V2)
  • T2(w):DELETE(K)
  • T1(r):SET(K, V1)
    このようにして不整合が生じます

そのため、新しい概念としてトークン lease を導入します。
このトークン leaseの特徴としては

  • キャッシュミスごとにユニークな値を発行し、キャッシュDBとクライアントが保持する
  • DELETE時に無効化する
  • SET時にクライアントから送信されてきた値とキャッシュDBが保持している値を照合し、一致しない場合値の更新が失敗する

やってみましょう

  • T1(r):V1, L0 = GET(K) -> キャッシュミス
  • T1(r):V1 = SELECT(K)
  • T2(w):UPDATE/INSERT(K, V2)
  • T2(w):DELETE(K) -> L0を無効化する
  • T1(r):SET(K, L0, V1) -> 失敗!

このようにして結果整合性が保たれることがわかります。
T1はSETに失敗したあと特になにかする必要はありません
単純に無視すれば整合性が保たれます

一方、T2のDELETEが遅れた場合どうなるでしょうか？

  • T1(r):V1, L0 = GET(K) -> キャッシュミス
  • T1(r):V1 = SELECT(K)
  • T2(w):UPDATE/INSERT(K, V2)
  • T1(r):SET(K, L0, V1)

↕このタイミングでは整合性が一時的に失われます

  • T2(w):DELETE(K) -> L0を無効化する

↓ここから整合性が復活します

このように一瞬整合性が保たれなくなりますが、すぐに解消します

またread-read競合時には leaseの値はユニークなので最後にキャッシュミスしたトランザクションのみがキャッシュの値を更新することができます

leaseをトランザクションを特定するための認証トークンとして利用していることがわかります

更に改良 Thundering herd problem への対応

例えばコンサートのチケット争奪戦のように、特定のキー Kに短時間で大量アクセスがある場合を考えてみましょう。Kの値を更新した瞬間にDELETE(K)がおこなわれ、RDBヘ大量アクセスがそのまま流れ込み、場合によってはRDBがダウンし障害などを引き起こす問題があります。(Thundering herd problem [3] )
Thundering herd problemは、今どきのサーバレスデータベースを高速にスケールさせることで解決できるかもしれません。しかし、スケールさせて処理するクエリはすべて同じクエリであるという点に注意を払うべきでしょう。つまり計算資源やお金が無駄になるということです。

この問題は lease の仕様に以下を追加ことで解決できます

  • Kに対してlease がすでに存在した場合、GETに失敗する -> クライアント側は、GETに失敗したら一定時間後再リクエストする
  • lease に生存期間(ttl)を設ける
  • SET時にleaseを無効化する

leaseをマルチスレッドプログラミングにおけるセマフォのように使っていることがわかります。
キャッシュ切れ/データ更新時にクライアントサイドで「待ち」が発生することになりますが、DBがダウンするのがいいか個々のユーザが数秒間待つのがいいかどちらがいいのかという話になるかと思われます。
一方、位置情報サービスなどで個人の位置情報を数秒おきに更新するなど、同じデータを頻繁に更新するようなユースケースの場合、ユーザの待ち時間が問題になってくることは考えられます。

Thundering herd problem問題への対応については、必ずしも必須ではなくメリットデメリットがあるので、実際にそのような問題が発生しうる環境かどうかを判断して対応するかしないかを決めることが可能です。

結論

このキャッシュパターンでは、Facebookのようなread勝ちの環境下でキャッシュとオリジンの結果整合性を保ちつつ、高いパフォーマンスを引き出すことに成功しています。
一方で、write勝ちの環境下では別のキャッシュパターンを採用したほうがいいかもしれません。
多くのWebサービスでは、在庫の入出庫や、売上の記録などクリティカルなデータを除けばread勝ちでかつデータの整合性は結果整合で十分、という場合が多いのではないでしょうか。
キャッシュパターンをを上手く使い分けハイパフォーマンスなサービスを作っていきたいですね！

脚注

  1. ちなみに筆者はこの手法についてすでに辞めてしまった会社の元上司に勉強会で教えてもらいました ↩︎

  2. インターネット初のワーム　モリスワームの作者、Yコンビネータの共同設立者でもある ↩︎

  3. Thundering:電撃 herd:（牛などの）群れ 牛などの家畜の群れが突然なだれ込んでくる様子を想像してください。リクエスト雪崩問題とでも訳せそう ↩︎

Discussion