memcachedが最初に導入されたとき、通常はバックエンドのWebサーバーに併置され、予備のRAMとCPUサイクルを使用していました。高速でありながらCPU使用量を抑えることが重要でした。そうでないと、改善しようとしているアプリケーションのパフォーマンスに影響を与えるからです。

時が経つにつれて、デプロイメントスタイルは変化しました。より多くのRAMを搭載した専用ノードが少なくなり、CPUに余裕があることが多くなりました。さらに、Webリクエストは一度に数十から数百のオブジェクトを取得する可能性があり、リクエストの遅延が全体的な影響を大きくしています。

この記事では、キャッシュスペースを浪費する期限切れアイテムの数を減らす取り組み、一般的なLRUの改善、および遅延の一貫性に焦点を当てています。

元の実装

1.4.x以前では、memcachedのLRUは標準的な双方向連結リストです。先頭と末尾があります。新しいアイテムは先頭に挿入され、削除は末尾からポップされます。アイテムにアクセスすると、その位置からリンクが解除され、LRUの先頭（「バンプ」と呼ぶ）に再度リンクされます。

データを積極的にメンテナンスするバックグラウンドスレッドはありませんでした。アイテムが期限切れになった場合、再度アクセスされるまでメモリに残っていました。期限切れのアイテムを検索すると、メモリが解放され、クライアントにMISSが返されます。

期限切れアイテムが削除されるのは、以下のときのみです

• 意図的に削除された場合
• SET経由で上書きされた場合
• 期限切れになり、GET、ADDなどを介して再アクセスされた場合。
• 削除が必要な場合、実際の末尾を削除するのではなく、末尾付近のいくつかのアイテムを見て、再利用する期限切れのアイテムを探します。

初期に行われた重要な最適化として、アイテムは60秒ごとに1回のみバンプされるというものがあります。頻繁にアクセスされるアイテムは、過度のミューテックスロックと変更を回避します。

ホットアイテムが常にLRU内で「バンプ」しない場合でも、一度に数百のアイテムを取得すると、それらの少なくともいくつか（または、ユーザーが休憩から戻ってきた場合はすべて）がバンプされる可能性があります。これにより、ミューテックスの競合、遅延のばらつき、およびサーバーでの過剰なCPU使用量が発生する可能性があります。

マルチスレッドスケーラビリティは、LRUのロックによって大きく制限されます。元のLRUでは、8つのワーカースレッドを超えてスケーリングするのは困難でした。非常に読み取り負荷の高いワークロードは、最適化が行われると、48コアまでほぼ線形にスケーリングしました。

私たちは、新しいアルゴリズムを見つけるために最小限のアプローチを取りました。コードの変更は比較的小さく、下位互換性があり、テストと検証が容易である必要があります。エンドユーザーは、さまざまな未知の負荷パターンを持っているため、より一般的なアプローチが必要です。

セグメント化されたLRU

最初の改善点：2Q、セグメント化されたLRUの設計、およびOpenBSDのファイルシステムバッファキャッシュからの命名の影響を受けた変更されたLRUを構築しました。

LRUは、4つのサブLRUに分割されます。各サブLRUには、独自のミューテックスロックがあります。これらはすべて、「LRUメンテナー」と呼ばれる単一のバックグラウンドスレッドによって管理されます。詳細を以下に示します。

各アイテムには、アクティビティレベルを示す2つのビットフラグがあります。

• FETCHED：アイテムがリクエストされたことがある場合に設定
• ACTIVE：アイテムが2回目にアクセスされた場合に設定。アイテムがバンプまたは移動されると削除されます。

HOTは、アイテムが強い時間的局所性または非常に短いTTL（Time-To-Live）を示す可能性が高いため、試用キューとして機能します。その結果、アイテムはHOT内でバンプされることはありません。アイテムがキューの末尾に到達すると、アイテムがactive（3）の場合はWARMに、非アクティブの場合はCOLD（5）に移動されます。

WARMは、古い投稿を読んでいるWebクローラーのようなスキャンワークロードのバッファとして機能します。2回ヒットしないアイテムはWARMに入ることができません。WARMアイテムは、ロックの競合を減らしながら、TTLを長く生き残る可能性が高くなります。末尾のアイテムがactiveの場合、先頭に戻します（4）。それ以外の場合は、非アクティブなアイテムをCOLDに移動します（7）。

COLDには、最もアクティブでないアイテムが含まれています。非アクティブなアイテムは、HOT（5）およびWARM（7）からCOLDに流れます。メモリがいっぱいになると、COLDの末尾からアイテムが削除されます。アイテムがactiveになると、WARMに非同期で移動されるようにキューに入れられます（6）。COLDへのバーストまたは大量のヒットの場合、バンプキューがオーバーフローする可能性があり、アイテムは非アクティブなままになります。過負荷シナリオでは、COLDからのバンプは、ワーカースレッドをブロックするのではなく、確率的になります。

TEMPは、非常に短いTTL（通常は数秒）（2）を持つ新しいアイテムのキューとして機能します。TEMP内のアイテムはバンプされず、他のLRUに流れることもないため、CPUとロックの競合を節約できます。現在、デフォルトでは有効になっていません。

HOTおよびWARM LRUは、主に使用メモリの割合によってサイズが制限されますが、COLDおよびTEMPは無制限です。HOTとWARMには、COLDの末尾の経過時間に対する相対的な2番目の末尾経過時間制限があります。これにより、非常にアイドルなアイテムが不必要にアクティブなキューに残り続けるのを防ぎます。

LRUメンテナースレッド

これらはすべて、LRUメンテナバックグラウンドスレッドによってまとめられています。これには簡単な仕事があります。

• すべてのサブLRUを反復処理し、末尾のアイテムを覗き見ます。
• 各サブLRUがその制限を尊重していることを確認し、必要に応じてアイテムを移動します。
• 期限切れになった末尾のアイテムを再利用します。
• COLD LRUからの非同期バンプを処理します。

これには、特定のスラブクラスのSETの継続的な過負荷により、削除するCOLDアイテムがなくなる可能性があるという注意点があります。この場合、SETは「直接再利用」モードに入り、ワーカースレッドはHOTおよびWARMからアイテムを押し出す間ブロックされます。

概要

メモリ効率に加えて、セグメント化されたLRUは、パフォーマンスにいくつかの大きな影響を与えます。

1. アイテムは、直接取得したときにバンプされることはありません。一度に500個のキーをすべて取得でき、LRUロックを待つ必要はありません。
2. アイテムは非同期的にバンプされます。setまたはfetchトラフィックの短時間のバーストは、HOTまたはWARMの一時的な不均衡を引き起こします。
3. 追加のミューテックスは、書き込み操作のスケーリングに役立ちます。
4. アイテムごとのメタデータサイズは増加しません。

これらのシステムの効率は、ワークロードによって異なります。60秒のTTLを持つ多くのアイテムを、86400（1D）TTLを持つアイテムと混在させて挿入すると、60秒のアイテムは、取得されるか末尾にドロップするまでメモリを浪費します。その間、システムは残り寿命が数時間のアイテムを削除します。

これは、依然として非常に効果的なキャッシュです。LRUであるため、TTLが長い頻繁にリクエストされるアイテムは先頭に留まる可能性が高く、TTLを自由に使い果たすことができます。

LRUクローラー

この実装には、依然としていくつかの未解決の問題があります

キャッシュのサイズ設定は困難です。RAMが多すぎますか？少なすぎますか？途中で浪費されているため、判断が難しいです。アクセスパターンが一貫しないアイテム（つまり、ユーザーが昼食や睡眠に行く）は、過度のミスを引き起こす可能性があります。より大きな（マルチキロバイト）の期限切れアイテムは、数百のより小さなアイテムのためのスペースを作ったり、それらをより長く保存したりできるようにします。

これらの問題を解決すると、キャッシュ内のアイテムを非同期でウォークスルーするためのメカニズムであるLRUクローラーが導入されます。期限切れのアイテムを再利用でき、キャッシュ全体またはそのサブセットを調べることができます。

クローラーは、すべてのスラブクラスの各サブLRUの末尾に特別なクローラーアイテムを挿入する単一のバックグラウンドスレッドです。次に、各クローラーアイテムを最下部から最上部へ、LRUを逆方向に同時に移動します。クローラーは、通過する各アイテムを調べて、期限切れかどうかを確認し、期限切れの場合は再利用します。

クラス1のHOTで1つのアイテム、クラス1のWARMで1つのアイテムなどを確認します。クラス5に10個のアイテムがあり、クラス1に100万個のアイテムがある場合、クラス5のスキャンはすぐに完了し、クラス1の完了に長い時間がかかります。

TTLの残りのヒストグラムは、各サブLRUをスキャンするときに作成されます。次に、ヒストグラムを使用して、各LRUを再スキャンする積極性を決定します。たとえば、クラス1に0 TTLのアイテムが100万個ある場合、クラス1は1時間に最大1回スキャンされます。クラス5に100000個のアイテムがあり、その1％が5分以内に期限切れになる場合、5分後に再実行するようにスケジュールされます。必要に応じて、数秒ごとに再スキャンできます。

スケジューリングは強力です。上位のスラブクラスは、自然に、より多くのスペースを占有するアイテムの数が少なくなります。大きなアイテムを非常に迅速にスキャンおよび再スキャンして、デッドメモリの比率を低く保つことができます。クラス1のスキャンに10分かかる場合でも、クラス50を何度も何度もスキャンできます。

セグメント化されたLRUと組み合わせると、LRUクローラーは「HOT」をスキャンする価値がないことを学習する可能性がありますが、WARMとCOLDは有益な結果をもたらします。またはその逆の場合：HOTにTTLの低いアイテムが多数ある場合、クローラーは比較的大きなCOLDのスキャンを回避しながら、HOTをクリーンに保つことができます。これにより、単一のスラブクラス内でも、スキャン作業量を減らすことができます。

ハッシュテーブルを先頭から後ろに向かってウォークスルーしてこれを達成しようとした場合。TTLの残りが10秒の1MBのアイテムは、ハッシュテーブル内のすべてのアイテムが一度調べられるまで、再度確認されることはありません。

概要

このセカンダリプロセスは、TTL付きのデータを管理するLRUの残りの非効率性のほとんどをカバーします。純粋なLRUには、穴や期限切れアイテムの概念がなく、ファイルシステムバッファプールは、同様のサイズ（たとえば、8kチャンク）でデータを保持することがよくあります。

バックグラウンドプロセスを使用して、最も効果的な場所に自己集中しながら、デッドデータを選択することで、デッドメモリのほぼすべてを再利用できます。キャッシュが実際にどれだけのメモリを消費しているかを測定するのがはるかに簡単になりました。

LRUクローラーの上に他の機能を構築することも可能です。

lru_crawler metadump <classid,classid|all>
example output:
key=foo exp=1539196410 la=1539196351 cas=3 fetch=no cls=1 size=64

このコマンドは、クラスIDのリストまたは「all」のいずれかを受け取り、キャッシュ内のすべてのアイテムに関するキーとメタデータ情報を非同期的に出力します。

Memcachedのチューニング

LRUコードには、実行中のインスタンスで変更できるいくつかのオプションがあります。

lru [tune|mode|temp_ttl] [option list]

• “mode” flat|segmented: セグメント化されたLRUから従来のLRUモードに実行中に切り替えたり、元に戻したりすることができます。HOTまたはWARM内のアイテムはCOLDに非同期的に排出され、COLDがメインのLRUになります。

• “tune”: 引数として “percent hot”, “percent warm”, “max hot age factor”, “max warm age factor” を受け取ります。これにより、HOTまたはWARMキューを大きくしたり小さくしたりして、ヒット率を動的に実験できます。

lru tune 10 25 0.1 2.0

この例では、HOTはメモリの10％、またはCOLDの末尾経過時間の10％の末尾経過時間に制限されています。WARMはメモリの25％、またはCOLDの末尾経過時間の200％に制限されています。LRUメンテナーは、必要に応じて新しい制限に合わせるためにアイテムを移動します。

• “temp_ttl” ttl: -1に設定して無効にするか、0より大きくして実行時にTEMP LRUの使用を有効にします。指定したTTLよりも短いTTLで入力されたオブジェクトは、TEMPに直接移動し、期限切れになるか、別の方法で削除されるまでそこに残ります。

これらはすべて、コマンドライン起動オプションで調整可能です。最新の起動オプションについては、'-h'コマンドを使用してください。

ソースのdoc/protocol.txtには、ライブチューニングに関する最新の詳細が記載されています。また、このコードに関連する新しい統計カウンターの説明も含まれており、ほとんどが「stats items」出力に表示されます。

結論

この記事では、メモリ効率に影響を与え、memcached 1.5.0でデフォルトで有効になった2つの改善点を紹介しました。

ソフトウェアコミュニティには、多くの新しく興味深いアイデアがあり、私たちは実験を続けます。一般的なワークプロファイル用の高速キー/値キャッシュを作成するには、トレードオフを慎重に評価する必要があります。これらの機能の実装作業には、合わせて数週間かかりましたが、本番環境でのテストにより、長年にわたって小さな変更が加えられました。

バックグラウンドスレッドで限定的なCPUを使用することで、memcachedのメモリ効率を大幅に向上させると同時に、レイテンシプロファイルも改善できることを示しました。