Facebookの論文に学ぶ結果整合性を持つキャッシュパターン
概要
Facebook(meta)のキャッシュ活用に関する有名なケーススタディ論文
Scaling Memcache at Facebook(2013)
に書かれているKVデータベースを利用したキャッシュの運用方法について学んだのでメモします。
この手法は、多くの一般的Webサービスで使える定石的な手法に個人的に思うのですが、日本語であまり解説記事を読んだことがないので記載します[1]。
用語の整理
キャシュパターンは read
に関するものとwrite
に関するものの2つあります。この記事では
-
read
read-through
look aside
-
write
write-through
-
demand-fill
というパターンが関係します
demand-fill/look aside cache
基本:参照している論文では
read:: look aside
write:demand-fill
というパターンを採用しています。具体的な手順は以下のとおりです。
- write(書き込み)
-
UPDATE/INSERT
:リレーショナルDB
にデータ(ユニークキー:K
,値:V
)を書き込む -
DELETE
:キャッシュDB
(memcached/redisなど)の該当するキー(K
)のデータを削除する
- read(読み込み)
- キャッシュDBにおいて(キー
K
)にデータがヒットする場合
1.GET
: そのままヒットしたデータを返す - キャッシュDBにおいて(キー
K
)のデータが存在しない
1.SELECT
:リレーショナルDB
からデータ(V
)取得
2.SET
: キャッシュDBにデータ(キーK
, 値V
)を登録する
- キャッシュDBにおいて(キー
この手法を 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
を逆の順番でやったらどうなるか?
キャッシュDB
に値をSET
しないのか(write-through/look aside
ではだめか?)
Q:なぜ値のUPDATE時にA:以下のようなシナリオでキャッシュとRDBの矛盾が生じ、次のwriteまでその矛盾が永続化して結果整合性が破綻する恐れがあります。
以下、2つのトランザクションT1(write)とT2(write)が存在するものとする
2つとも同じキー(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
に対して冪等な操作のため、どのような順番で何回やっても結果が変わらないという利点があります。
UPDATE/INSERT
と DELETE
を逆の順番でやったらどうなるか?
Q:write時に A:以下のようなシナリオでキャッシュとRDBの矛盾が生じ、次のwriteまでその矛盾が永続化して結果整合性が破綻する恐れがあります。
以下、2つのトランザクションT1(write)とT2(read)が存在するものとする
2つとも同じキー(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)が存在するものとします
2つとも同じキー(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勝ちでかつデータの整合性は結果整合で十分、という場合が多いのではないでしょうか。
キャッシュパターンをを上手く使い分けハイパフォーマンスなサービスを作っていきたいですね!
Discussion