> [!abstract] 概要(原文 abstract の日本語訳) > Memcached は広く知られたシンプルなインメモリキャッシュソリューションである。本論文では、Facebook が memcached を building block として活用し、世界最大のソーシャルネットワークを支える分散キー値ストアを構築・スケールさせる方法を述べる。我々のシステムは秒間数十億のリクエストを処理し、数兆のアイテムを保持することで、世界中の 10 億以上のユーザに豊かな体験を提供する。 ## 論文情報 - **タイトル**: Scaling Memcache at Facebook - **著者**: Rajesh Nishtala, Hans Fugal, Steven Grimm, Marc Kwiatkowski, Herman Lee, Harry C. Li, Ryan McElroy, Mike Paleczny, Daniel Peek, Paul Saab, David Stafford, Tony Tung, Venkateshwaran Venkataramani（全員 Facebook Inc.） - **媒体**: 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI '13) - **発表年**: 2013 - **ページ**: 385–398 - **PDF**: https://www.usenix.org/system/files/conference/nsdi13/nsdi13-final170_update.pdf ## 概要 Facebook が memcached（オープンソースのインメモリハッシュテーブル）を基盤に構築した分散キー値ストアの設計と運用を詳述する。単一クラスタから複数のフロントエンドクラスタ(リージョン)、さらに地理的に分散した複数リージョンへとスケールアップする過程で現れる課題と、各スケールに応じた設計判断を体系的に報告する。本論文の 4 つの主要貢献は、(1) アーキテクチャの変遷の記述、(2) memcached へのパフォーマンス・メモリ効率改善の追加、(3) 大規模運用を支える仕組みの提示、(4) 本番ワークロードの特性化である。 ## 問題設定 - **読み書き非対称性**: ユーザはコンテンツの消費量が生成量の桁違いに多い。大量の読み取りに対して MySQL を直接叩くことは過負荷につながる。 - **ファンアウト**: 1 回のページリクエストで平均 521 個の個別アイテムを memcache から取得する(p95: 1,740 アイテム)。 - **多対多通信**: 全ウェブサーバが短時間で全 memcached サーバと通信する all-to-all パターンが生じ、incast 輻輳やホットスポットを引き起こす。 - **一貫性の難しさ**: 複数フロントエンドクラスタ間・複数リージョン間でのキャッシュ整合性の維持が主要技術課題となる。 ## 提案手法 ### ルックアサイドキャッシュ (Look-aside Cache) memcache をデマンドフィル型のルックアサイドキャッシュとして使う。 **図1: look-aside cache の読み書きパス** ![[_attachments/nsdi13-final170_update/fig01-look-aside-cache.png]] (Figure 1. 読み取りパス: ウェブサーバが memcache に get(k) → キャッシュミス時は DB に SELECT → memcache に set(k,v)。書き込みパス: DB に UPDATE → memcache に delete(k)。削除はべき等なため update ではなく delete を選択。Source: Figure 1, p. 385.) - 読み取り: キャッシュヒット → memcache からデータを返す。キャッシュミス → DB から取得して memcache に保存。 - 書き込み: DB に SQL 文を発行 → memcache から古いデータを削除。更新(update)でなく削除(delete)を使う理由はべき等性の確保。 - memcache はデータの信頼できる唯一の情報源ではなく、キャッシュデータを退避させてよい。 ### アーキテクチャの 3 スケール構造 **図2: 全体アーキテクチャ(マスターリージョンとスレーブリージョン)** ![[_attachments/nsdi13-final170_update/fig02-overall-architecture.png]] (Figure 2. リージョンはフロントエンドクラスタ(複数の Web Server + Memcache 群)とストレージクラスタ(MySQL)で構成。マスターリージョンからスレーブリージョンへストレージレプリケーションが行われる。Source: Figure 2, p. 386.) 1. **クラスタ内**: レイテンシとロードの削減 2. **リージョン内**: 複数フロントエンドクラスタ間のレプリケーション 3. **リージョン間**: 地理分散時の整合性 ### クラスタ内: レイテンシとロード削減 **並列リクエストとバッチ処理**: データ依存関係を有向非巡回グラフ(DAG)として表現し、独立して取得できるアイテムを一括 get。1 リクエストあたり平均 24 キー(p95: 95 キー)をバッチ取得する。 **UDP/TCP の使い分け**: get リクエストには UDP を使う。各スレッドが mcrouter を経由せず直接 memcached サーバと通信できるため、接続確立のオーバーヘッドがない。UDP は単一 get で TCP 比 20% 低レイテンシを達成する(Figure 3)。set/delete 等の状態変更は TCP 経由で mcrouter を通す。ピーク時に 0.25% の get リクエストが破棄されるが、クライアントはこれをキャッシュミスとして扱う。 **Incast 制御**: スライディングウィンドウ機構で同時リクエスト数を制限する。ウィンドウサイズが小さすぎると逐次処理が増加し、大きすぎると incast 輻輳で memcache エラーが増えて永続ストレージへのフォールバックが多発する(Figure 4)。 **リースメカニズム**: stale set（並行更新の並べ替えで古い値がキャッシュされる問題）と thundering herd（特定キーへの大量読み書きで無効化直後の再取得要求が集中する問題）を解決する。 - memcached インスタンスはキャッシュミスしたクライアントにリーストークン(64 ビット)を発行する。 - クライアントはトークンを提示してキャッシュに値をセットする。delete リクエストがあればトークンを無効化するため、並行書き込みを調停できる。 - thundering herd 対策として、デフォルトでキーごとに 10 秒に 1 回しかトークンを返さない。10 秒以内の 2 回目以降のリクエストは「少し待て」と通知され、最初のクライアントがキャッシュをセットするまで待機する。 - 効果: 特定のサンダリングハード耐性の低いキー群のピーク DB クエリレートを 17K/s → 1.3K/s に削減。 **Memcache プール**: アクセスパターン・メモリフットプリント・QoS 要件が異なるワークロードを分離するため、クラスタの memcached サーバを複数プールに分割する。デフォルトプール(wildcard)のほか、アプリ専用(app)、高頻度アクセス用レプリケーションプール、低頻度・大型データ用リージョナルプールなどを設ける。 **プール内レプリケーション**: 全データセットが 1〜2 サーバに収まり、かつリクエストレートが単一サーバの処理能力を超える場合に採用。クライアントは IP アドレスに基づいてレプリカを選択する。シャーディングより有効な理由: 100 キーをまとめて取得するワークロードでは、2 台に分割しても各サーバへの負荷は変わらないが、2 台にレプリカを持てば各サーバへの負荷を半減できる。 **Gutter プール**: 障害対応用の専用サーバ群(クラスタの約 1%)。memcached サーバが応答しないとき、クライアントは Gutter プールへリクエストを再送し、そこでもミスなら DB から取得して Gutter に挿入する。Gutter のエントリは短期間で期限切れにする。通常のキー再ハッシュ方式よりも安全な理由: ホットキーを受け取るサーバが過負荷になるカスケード障害を防げる。実績: 障害率 99% 削減、毎日 10〜25% の障害をヒットに変換。memcached サーバが完全停止した場合、4 分以内に Gutter ヒット率が 35% を超え、50% に近づく。 ### リージョン内: レプリケーション **mcsqueal による DB コミットログ駆動の無効化**: **図6: 無効化パイプライン(mcsqueal)** ![[_attachments/nsdi13-final170_update/fig06-invalidation-pipeline.png]] (Figure 6. Storage Server 上の MySQL Commit Log を mcsqueal デーモンが監視し、削除すべきキーを抽出。mcrouter にバッチ送信したのち、各フロントエンドクラスタの対象 memcached サーバに配送される。Source: Figure 6, p. 390.) - ウェブサーバが直接全フロントエンドクラスタに無効化を送るより安全。SQL 文に無効化キーを埋め込み、DB のコミットログ経由で mcsqueal が読み出す。誤配送があってもリプレイ可能。 - mcsqueal は削除をバッチにまとめて mcrouter に送る。これにより削除/パケット比が中央値で 18 倍改善。 - 4% の削除のみが実際のキャッシュデータの無効化につながる(残りはすでにキャッシュにないか)。 **リージョナルプール**: 複数フロントエンドクラスタで共有するメモリプール。大きく低頻度のアイテムを各クラスタに複製するのは非効率なため、1 リージョンに 1 コピーだけ保持する。 **Cold Cluster Warmup**: 新規クラスタや保守後クラスタは空キャッシュ状態のため、既存 warm クラスタからデータを取得させることで数日→数時間でウォームアップできる。整合性のため cold クラスタへの delete に 2 秒の hold-off を設ける。 ### リージョン間: 整合性 マスターリージョンに書き込み可能な DB を置き、他リージョンは読み取り専用レプリカ。MySQL レプリケーションで最新化する。**ベストエフォートの結果整合性**を提供しつつ、パフォーマンスと可用性を最優先にする。 **リモートマーカー機構**: 非マスターリージョンからの書き込み後にレプリケーション遅延中にレプリカの古い値がキャッシュされないよう、リモートマーカー(remote marker, rk)をリージョナルプールに置く。rk の存在はそのキーのデータが古い可能性を示し、クエリをマスターリージョンに向ける。 ### シングルサーバ改善 **細粒度ロック**: グローバルロック → ファイングレインドロックにより、ピーク get レートが hit で 600K/s → 1.8M/s、miss で 2.7M/s → 4.5M/s に向上。 **図7: memcached バージョン別 multiget ヒット・ミス性能** ![[_attachments/nsdi13-final170_update/fig07-multiget-performance.png]] (Figure 7. Facebook の fine-grained locking 版(Facebook-μlocks)が hit レートを約 3 倍にしている。なお現在のオープンソース 1.4.10 もより粗いロック戦略を独立して実装しており改善が見られる。Source: Figure 7, p. 393.) **適応型スラブアロケータ**: 定期的にスラブクラス間のメモリを再割り当てし、現在のワークロードに最適化する。ロックせず最近使われたアイテムの経過時間でバランスを取る方式。 **一時アイテムキャッシュ (Transient Item Cache)**: 短命キーを秒単位の循環バッファに入れ、期限切れ時点で能動的に退避する。長命キーは従来の LRU 遅延退避。効果: 短命キーファミリーの memcache プール使用率が 6% → 0.3% に削減。 **System V 共有メモリを用いたゼロダウンタイムアップグレード**: キャッシュデータと主要データ構造を共有メモリに置くことで、ソフトウェアアップグレード中もキャッシュを生かし続ける。 ## 新規性 memcached は元来単一マシンのインメモリハッシュテーブル。本論文はそれを 10 億ユーザ規模の分散キー値ストアに変換した**工学的進化の全記録**として唯一無二の価値を持つ。特に: - ルックアサイドキャッシュパターンとリース機構の組み合わせによる thundering herd 解決 - mcsqueal を介したコミットログ駆動の安全な無効化(ウェブサーバ直接無効化より堅牢) - Gutter プールによる failure isolation - Cold Cluster Warmup による迅速なキャパシティ投入 Dynamo[12] や Cassandra[1] が書き込み主体ワークロードや強い整合性を志向するのと対照的に、本システムは**読み取り圧倒的・ベストエフォート整合性**で設計され、性能と可用性を最優先にしている点が差別化要因。 ## 実験設定 - **環境**: 本番環境の Facebook インフラ。具体的なハードウェアは Open Compute Project 参照[4]。 - **テスト用構成(§6)**: Intel Xeon X5650 (2.67 GHz, 12 コア+12 ハイパースレッド)、Intel 82574L GbE NIC、12 GB RAM。クライアント 15 台 → 単一 memcached サーバ(24 スレッド)、ギガビットイーサネット同一ラック構成、2 分間の持続負荷測定。 - **ワークロード**: Facebook の読み取り主体ワークロード。Atikoglu et al. [8] でより詳細な分析あり。 ## 実験結果 ### レイテンシ - 本番 7 日間の中央値リクエストレイテンシ: **333 μs**(p75: 475 μs, p95: 1.135 ms) - アイドルウェブサーバからのエンドツーエンド中央値: 178 μs(p75: 219 μs, p95: 374 μs) - UDP は TCP(mcrouter 経由)比で約 20% レイテンシが低い(Figure 3) ### スループット (細粒度ロック後) - hit レート: **1.8M items/s**(改善前 600K/s の 3 倍) - miss レート: **4.5M items/s**(改善前 2.7M/s) - UDP は single get で TCP 比 13% 上回り、10-key multiget で 8% 上回る ### ファンアウト **図9: distinct memcached サーバ数の累積分布** ![[_attachments/nsdi13-final170_update/fig09-fanout-distribution.png]] (Figure 9. 全リクエストの 56% は 20 台未満との接続にとどまるが、高負荷ページは大半が 100 台以上にアクセスし、数百台に達することも珍しくない。Source: Figure 9, p. 395.) - 全ページリクエストの 56% が 20 台未満の memcached サーバに接続 - データ集中型の人気ページでは 100 台以上、数百台にアクセスすることも ### プール統計(7 日間平均) | プール | ミス率 | get/s | set/s | delete/s | |--------|--------|-------|-------|---------| | wildcard | 1.76% | 262 K | 8.26 K | 21.2 K | | app | 7.85% | 96.5 K | 11.9 K | 6.28 K | | replicated | 0.053% | 710 K | 1.75 K | 3.22 K | | regional | 6.35% | 9.1 K | 0.79 K | 35.9 K | (Table 2. replicated プールは最低ミス率(0.053%)と最高 get レートを達成。Source: Table 2, p. 395.) ### 無効化レイテンシ **図11: 削除パイプラインのレイテンシ(30 日間)** ![[_attachments/nsdi13-final170_update/fig11-delete-pipeline-latency.png]] (Figure 11. マスターリージョン内では 1 秒以内に 4 ナイン(99.99%)の信頼性、1 時間後に 5 ナイン。レプリカリージョン間では 1 秒以内が 3 ナイン、10 分後に 4 ナイン。Source: Figure 11, p. 396.) - マスターリージョン内: 1 秒以内に 4 ナインの信頼性、1 時間後に 5 ナイン - レプリカリージョン間: 1 秒以内が 3 ナイン、10 分後に 4 ナイン - 数秒後でも無効化が届かない主な原因は最初の試みの失敗→再試行で解決 ## 考察 ### 優位性の根拠 1. **ステートレスなクライアント設計**: 複雑なロジックをサーバでなくクライアント(ライブラリ or mcrouter)に持つことで、memcached サーバをシンプルかつ高性能に保ちつつ機能追加を容易にする。 2. **リース + Gutter の組み合わせ**: それぞれ独立した問題(thundering herd vs. サーバ障害時カスケード)を解決し、バックエンド DBへの突発的負荷を二重に遮断する。 3. **mcsqueal によるコミットログ駆動**: ウェブサーバ直接無効化より信頼性が高く、誤配送時のリプレイが容易。 ### 限界と課題 - キャッシュのセマンティクスが複雑で正確な記述が難しい(concurrent modification の場合に remote marker が消える可能性など)。 - ベストエフォート整合性のため、ごく稀に古いデータが読まれる状況を許容している。 - コールドクラスタウォームアップの 2 秒 hold-off では理論的にはまだ整合性問題が残る。 - プールの分割・リージョナル移行の判断は現在も手動のヒューリスティクスに依存。 ## 強み - Facebook 本番環境での実測値が豊富で、設計判断の根拠が定量的に示されている。 - 工学的制約(エンジニアリングリソース、ライブシステムの継続的製品開発)との現実的なトレードオフが明示されている。 - クラスタ→リージョン→リージョン間という段階的スケールと課題の変遷が整理されており、再現性と応用性が高い。 ## 弱点・課題 - 強い整合性を必要とするユースケースには向かない(同論文中でも TAO[37] は別システムと紹介)。 - キャッシュのセマンティクスが精確に定義しにくく、開発者・運用者の理解が難しい。 - 部分的な設計判断(例: 2 秒 hold-off の根拠)は経験則ベース。 ## 関連 - **wiki 内**: [[分散キャッシュ]] / [[一貫性ハッシュ法]] / [[Incast]] / [[結果整合性]] / [[Facebook]] / [[Rajesh Nishtala]] - **既存論文との関係**: [[structures/AIOps - Fault Localization - MOC|AIOps - Fault Localization - MOC]] には無関係だが、[[structures/Systems for ML - MOC|Systems for ML]] の基盤インフラ文脈で参照可。 - **後続研究**: TAO[37]（グラフデータモデル特化キャッシュ）、mcrouter の OSS 公開、Twitter の twemproxy も類似アプローチ。