問題の説明
平均的な負荷の高いサイトを想像してください。 通常、そのようなサイトでは、キャッシュレイヤーがバックエンドとDBの間に配置されます。 訪問者の数が増えると、複数のユーザーが「腐った」キャッシュに同時に出くわす可能性が高くなります。 これが発生すると、バックエンドとDBの負荷が増加し、リクエストの処理時間が長くなり、同様の状況が発生する可能性が高くなります。 以下にそのような正のフィードバックシステムを示します。
小さな赤いこぶは、複数のキャッシュ更新に対する「鈍化」要求です。 この記事では、
PHP /
APCバンドル（
patch attached ）の例を使用して問題を解決する方法の1つを説明しますが、理論的基礎はあらゆる言語およびキャッシングシステムに適用できます。
問題を解決するためのオプション
問題を解決するには、いくつかのアプローチがあります。 以下に提案する方法は単なる回避策です。 正しいアプローチであるIMHOは、ビジーロックを使用することです。これにより、キャッシュを更新できるプロセスは1つだけになり、残りは古いデータになります。 ただし、この解決策は十分に簡単なものではなく、ほとんどの場合（要求が均一に分散されている場合）、説明されている回避策は十分すぎるはずです。
また、私の場合、キャッシュ自体のレベルでREDを実装することが決定されましたが、アプリケーションコード内のクラス/ラッパーでも同じことが実装できます。 この方法が選ばれたのは、PHPコードに登るのが面倒だからです。
赤
RED 、別名
random early detection 、
random early discardまたは
random early dropは、ルーターおよびシェーパーで見られるキュー管理のアルゴリズムです。 その物理的な意味はほぼ次のとおりです。キューがいっぱいになってすべてをドロップする必要がある場合（テールドロップ）待機する代わりに、特定のしきい値が入力され、その後、何らかの確率でパケットをドロップし始めます。確率自体は、バッファー内の空き領域に直接比例します。 したがって、
Random Early Drop 。
このケースでは、キャッシュエントリの有効期間に特定のしきい値（
drop_threshold ）を
drop_thresholdます。その後、特定の確率
p cache miss発行して
cache miss読み取り要求を開始し、アプリケーションに最新バージョンのデータをキャッシュさせます。 したがって、競合するキャッシュ更新の数を
p逆に減らします。
マテリエル
数学はここで3番目のクラスのレベルにあるため、画像と式を与えてください。
免責事項
PHP知りません。 私は田舎者としてCで書いています。
APCパッチ
コードは、本番用ではなくPoCのように記述されています。
75%の値は天井から取られました。 実際の状態では、
drop_thresholdを設定で
drop_threshold必要があります。
インデックス：apc_cache.c
================================================== ==================
--- apc_cache.c （リビジョン320057 ）
+++ apc_cache.c （作業コピー）
@@- 705、6 + 705、13 @@
volatile apc_cache_entry_t *値= NULL;
符号なしlong h;
+ / * APC-REDパッチ* /
+ const int drop_threshold = 75 ;
+符号なし整数の確率= 0 ;
+ int red_cf = 0 ;
+ショートドロップ= 0 ;
+ / * APC-REDパッチの終わり* /
+
if （ apc_cache_busy （ cache ） ）
{
/ *キャッシュのクリーンアップが進行中* /
@@-720、8 + 727、25 @@
while （ * slot ） {
if （ （ h == （ * slot ） -> key.h ） &&
！memcmp （ （ * slot ） -> key.data.user.identifier、strkey、keylen ） ） {
+ / * APC-REDパッチ* /
+ if （ （ * slot ） -> value-> data.user.ttl ） {
+ red_cf = （ t- （ * slot ） -> creation_time ） * 100 /
+ （ * slot ） -> value-> data.user.ttl;
+ if （ red_cf> = 100 ） {
+ドロップ= 1 ;
+ }
+ else if （ red_cf <= drop_threshold ） {
+ドロップ= 0 ;
+ }
+ else {
+確率= （ red_cf-drop_threshold ） * 100 / （ 100 -drop_threshold ） ;
+ドロップ= （ arc4random （ ） ％ 100 ） <確率？ 1-0 ;
+ }
+ }
+ / * APC-REDパッチの終わり* /
+
/ *このエントリがハードTTLで期限切れになっていないことを確認してください* /
-if （ （ * slot ） -> value-> data.user.ttl && （ time_t ） （ （ * slot ） -> creation_time + （ * slot ） -> value-> data.user.ttl ） <t ） {
+ if （（ （ （ * slot ） -> value-> data.user.ttl && （ time_t ） （ （ * slot ） -> creation_time + （ * slot ） -> value-> data.user.ttl ） <t ） | |ドロップ） {
#if （ USE_READ_LOCKS == 0 ）
/ *書き込みロックがある場合、これは単にメモリに優しい最適化です
*これをすぐにdeleted_listに移動することもできます。 それ以外の場合は挿入
ハブに到達する前にこのパッチがいくつのパーサーを通過したかを考えると、おそらく適用されないので、ここに要点へのリンクを残した方が良いでしょう：
patch-apc_red.patch美しいの反射
また、RCUサポートをAPCコードに追加する価値があります（たとえば、
liburcuを
使用 ）。これは、高負荷でもrwlockを実行するのがそれほど難しくないためです（ところで、
比較的最近 APCに追加されました）。 APC自体は、長い間PHPに組み込む価値がありました。
また、
drop_thresholdを適応的に設定する方法について考えることができます。これは、phpbbがすべてのグローバル設定を格納し、すべてのリクエストに対してすべてのユーザーによってプルされる
board_configようなグローバル構造では、しきい値を50％に設定するのが理にかなっています。 、「機能」を無効にして、しきい値を100％に設定する価値があります。 このトピックについて考える場合、たとえば、
Adaptive / Active RED（ARED）などのネットワークアナログの方向を見ることができます。
また、キャッシュの
劣化とそれに対抗する問題については、Andrei Smirnov（
smira ）によるHighload 2008の古い、しかしまだ関連性のあるレポートを読むことができます：
Web、キャッシング、memcached