# 分散キャッシュ ## 定義 分散キャッシュ(distributed caching)とは、複数のサーバにわたってインメモリのキャッシュ層を分散配置し、バックエンドのデータベースや永続ストレージへの読み取り負荷を軽減するシステムである。キーに基づいて一貫性ハッシュ法などでサーバを決定し、get/set/delete の単純な操作で大量のデータアクセスをさばく。(Source: [[@2013__NSDI__Scaling Memcache at Facebook]]) 最も広く使われた実装として memcached がある。Facebook はこれを building block として改良し、秒間数十億リクエストを処理する分散キー値ストアを構築した。 ## ルックアサイドキャッシュパターン (Look-aside Cache) 最も一般的なパターン。キャッシュはデータの信頼できる唯一の情報源ではなく、バックエンドDBのルックアップ負荷を軽減するレイヤとして機能する。 - **読み取り**: キャッシュ miss → DB からデータ取得 → キャッシュに挿入 → 返す - **書き込み**: DB 更新 → キャッシュから delete(update ではない) delete を使う理由は**べき等性**である。複数の並行更新が起きたとき、update より delete のほうが安全に古いデータを除去できる。(Source: [[@2013__NSDI__Scaling Memcache at Facebook]]) ## リースメカニズム thundering herd（特定キーへの大量ミス→DB 一斉クエリ）と stale set（並行更新の並べ替えによる古いデータのキャッシュ）を解決するメカニズム。 - キャッシュミス時にサーバは 64 ビットのリーストークンをクライアントに発行 - クライアントはトークンを提示してのみ set できる - delete が来るとトークンは無効化され、その後の set が拒否される - thundering herd 対策として、デフォルトでキーあたり 10 秒に 1 回のみトークンを発行 効果: 特定キーのピーク DB クエリレートを 17 K/s → 1.3 K/s に削減。(Source: [[@2013__NSDI__Scaling Memcache at Facebook]]) ## Gutter プール 障害対応用の小規模サーバ群(クラスタの約 1%)。通常の memcached サーバが応答しない場合のフォールバック先として機能する。キーの再ハッシュよりも安全な理由は、ホットキーを受け取った代替サーバが過負荷になるカスケード障害を防げるため。 効果: 障害時のクライアント可視失敗率を 99% 削減、毎日 10〜25% の失敗をヒットに変換。(Source: [[@2013__NSDI__Scaling Memcache at Facebook]]) ## スケールに伴う課題の変化 | スケール | 主課題 | 解決策 | |---------|--------|--------| | クラスタ内 | レイテンシ・incast 輻輳 | UDP get / スライディングウィンドウ / リース | | リージョン内 | クラスタ間整合性 | mcsqueal / regional pool / cold warmup | | リージョン間 | レプリケーション遅延 | remote marker / ベストエフォート結果整合性 | (Source: [[@2013__NSDI__Scaling Memcache at Facebook]]) ## 横断的知見 - **読み取り圧倒的ワークロードでの整合性コスト**: Facebook memcache は「古いデータを読む確率」をチューニング可能なパラメータとして扱い、完全整合性よりも性能・可用性を優先する。Dynamo や Cassandra が書き込み主体・より強い整合性を志向するのと対照的。(Source: [[@2013__NSDI__Scaling Memcache at Facebook]], [[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]]) - **ステートレスクライアント設計の優位性**: 複雑さをクライアントライブラリ/mcrouter に寄せることで、サーバをシンプル・高性能に保てる。サーバがステートフルになるほど運用の複雑さが増す(論文の結論 (3))。(Source: [[@2013__NSDI__Scaling Memcache at Facebook]]) ## 未解決の問い - memcache のような「弱い整合性」キャッシュ層が整合性を必要とするユースケースに導入されるとき、開発者はどのようにミスを防いでいるか？ - リースメカニズムはどの程度の規模や頻度のワークロードから有効か？small-scale では不要なオーバーヘッドになる閾値はあるか？ - Gutter プールによるフォールバック以外に、memcache サーバ障害時のカスケード防止策として有効なパターンはあるか？ ## 関連 - [[一貫性ハッシュ法]] — memcache クラスタ内でのキー配布に使用 - [[結果整合性]] — memcache のリージョン間整合性モデルの分類 - [[Incast]] — all-to-all 通信によるスイッチ輻輳問題(スライディングウィンドウで緩和) - [[Facebook]] — 本システムを本番展開した組織 - [[インターネットスケールサービス設計]] — より広い文脈 ## 出典 - [[@2013__NSDI__Scaling Memcache at Facebook]]