Redis のソースコードを読んで、キャッシュ除去アルゴリズム W-TinyLFU を学びましょう

Redis のソースコードを読んで、キャッシュ除去アルゴリズム W-TinyLFU を学びましょう

[[433812]]

この記事は董澤潤氏が執筆したWeChat公開アカウント「董澤潤の技術ノート」から転載したものです。この記事を転載する場合は、Dong Zerun の Technical Notes 公開アカウントにご連絡ください。

すべての IT 実務者はキャッシュに触れたことがあり、その基本的な動作原理を理解している必要があります。業界では、「キャッシュは、問題があるところならどこにでも適用できる万能薬である」という有名な格言があります。では彼の本質とは何でしょうか?

上の図は、CPU からその下のハードディスクまで、さまざまなレベルのさまざまなモジュールの実行速度を示しています。上位レベルにもう 1 層のキャッシュを追加すると、下位レベルの速度が遅いという問題を解決できます。ここでの速度が遅いとは、IO が遅いことと、CPU が中間結果をキャッシュするために繰り返し計算することの 2 つの点を指します。

しかし、キャッシュのコスト制約により、キャッシュ サイズは一般的に固定されているため、データを削除する必要があり、キャッシュの一貫性、故障、雪崩、汚染など、一連の他の問題が発生します。この記事では、Redis のソース コードを読んで、主流の削除アルゴリズムを学習します。

LeetCode 146 LRU[1]問題がなかったら、誰も手作業でキャッシュを書くことはないと思います。単純な実装はエンジニアリングの実践とはかけ離れています。真に製品化可能なキャッシュライブラリは、細部のテストです。

Redis キャッシュ削除設定

一般的に、redis をストレージとして使用することは推奨されていません。キャッシュとして使用し、max-memory を設定することのみが許可されています。メモリ使用量が最大値に達すると、redis-server はさまざまな設定に従ってキーの削除を開始します。Redis はバージョン 4.0 から LFU[2] (Least frequently used) を導入しました。4.0 より前は、Least Recently Used (LRU) がデフォルトで使用されていました。

  • volatile-lru は、期限切れのキーに対してのみ lru 削除を実行します。
  • allkeys-lruはすべてのキーに対してlru除去を実行します
  • volatile-lfu は、期限切れのキーに対してのみ lfu 削除を実行します。
  • allkeys-lfuはすべてのキーに対してlfu除去を実行します
  • 揮発性ランダムは有効期限が切れるものだけをランダムに排除する
  • allkeys-random すべてのキーがランダムに削除されます
  • volatile-ttlは、ttl有効期限が最も短いキーを削除します。
  • noevictionは何もしません。メモリがいっぱいの場合、システムは書き込みできません。

デフォルトのポリシーは noeviction で、これは削除しないことを意味します。ディスクがいっぱいになると、システムはディスクに書き込むことができません。LFU 関連に設定することをお勧めします。 LRU は最近使用されていないキーを優先し、コールド データを処理できません。たとえば、ホット キーが短期間アクセスされない場合、一度しか使用されていないコールド データによってフラッシュされ、実際の使用状況を反映できません。

LFUは上記の状況を回避できますが、単純なLFU実装ではバーストトラフィックに対処できず、履歴ホットキーを削除できません。そのため、Redis LFU実装はW-TinyLFU[3]に似ています。ここで、Wはウィンドウを表し、つまり、一定の時間ウィンドウの後に頻度が半分になります。半分にならなければ、キャッシュはキャッシュではなく履歴データの統計になります。

上で述べたように、バースト トラフィックにはどのように対処すればよいでしょうか。その答えは、新しくアクセスされたキーに初期周波数値を与えて、初期値が 0 であるため周波数が更新されないようにすることです。

LRU実装

  1. intプロセスコマンド(redisClient *c) {
  2.     ......
  3.     /* maxmemory ディレクティブを処理します。
  4.      *
  5.      *まず、  無料 可能であればメモリ（揮発性メモリがある場合）
  6.      *データセット内のキー） 。
  7.      *エラーが返されます。 * /
  8.     if (server.maxmemory) {
  9.  int retval = freeMemoryIfNeeded();
  10.         if ((c->cmd->flags & REDIS_CMD_DENYOOM) && retval == REDIS_ERR) {
  11.             フラグトランザクション(c);
  12.             返信を追加します(c、shared.oomerr);
  13.  REDIS_OKを返します。
  14.         }
  15.     }
  16.     ......
  17.  }

クライアント コマンドが処理されるたびに、freeMemoryIfNeeded が呼び出され、一部のキーを削除する必要があるかどうかが確認されます。Redis によって使用される実際のメモリが上限に達すると、メモリの削除が開始されます。ただし、Redis は非常に賢いので、すべてのキーに対して LRU キューを作成するわけではありません。代わりに、maxmemory_samples パラメータに従ってサンプリングします。システムのデフォルトは 5 つのキーです。

上記は非常に典型的なグラフです。キーが 10 個に達すると、効果は理論的な LRU アルゴリズムに近づきますが、CPU 消費量が高くなるため、システムのデフォルト値で十分です。

LFUの実装

  1. robj *lookupKey(redisDb *db, robj *キー, intフラグ) {
  2.     dictEntry *de = dictFind(db->dict, key- >ptr);
  3.     もし（で）{
  4.         robj *val = dictGetVal(de); 
  5.  
  6.         /*アクセス時間を更新する 老化アルゴリズム用。
  7.          * 救世主の子供がいる場合は、これをしないでください。  
  8.          * コピーオンライトの狂気。*/
  9.         if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
  10.             if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
  11.                 LFUを更新します(val);
  12.             }それ以外{
  13.                 val->lru = LRU_CLOCK();
  14.             }
  15.         }
  16. 戻り値:
  17.     }それ以外{
  18.         NULL を返します。
  19.     }
  20.  }

lookupKey がキーにアクセスすると、LRU が更新されます。Redis 4.0 以降では、LFU アルゴリズムが徐々に導入されています。LRU フィールドは再利用されるため、24 ビットしか使用できません。

  1.  * 24 ビットを2 つのフィールドに分割します。
  2.  *
  3.  * 16ビット 8ビット
  4. * + ----------------+--------+  
  5.  * +最終減算時刻| LOG_C |
  6.  * + ----------------+--------+  

カウンターの下位 8 ビットは頻度をカウントするために使用され、値の範囲は 0 から 255 です。ただし、対数をとった後、大きなアクセス頻度を表すことができます。

ldt (最終減分時間) の上位 16 ビットは、最後のアクセス分のタイムスタンプを表し、カウンター値を減少させるために使用されます。カウンターが減少しない場合は、LFU ではなく、履歴キー アクセス数の統計になります。

  1. 符号なしlong LFUTimeElapsed(符号なしlong ldt) {
  2.     符号なし long は現在 = LFUGetTimeInMinutes() です。
  3.     (now >= ldt) の場合はnow-ldtを返します。
  4.  65535-ldt+nowを返します。
  5.  }

ldtは16ビットのカウントのみを使用し、最大値は65535であるため、巻き戻しが発生することに注意してください。

LFU 既存のカウントを取得する

  1.  *必要に応じてスキャンされたオブジェクトのカウンター。 */
  2. 符号なしlong LFUDecrAndReturn(robj *o) {
  3.     符号なしロングldt = o->lru >> 8;
  4.     符号なしロングカウンター = o->lru & 255;
  5.     符号なしlong num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
  6.     if (期間数)
  7.         counter = (num_periods > counter) ? 0 : counter - num_periods;
  8. 返品カウンター;
  9.  }

num_periodsは計算された減衰回数を表し、lfu_decay_timeは減衰係数を表します。デフォルト値は1です。lfu_decay_timeが1より大きい場合、減衰率は非常に遅くなります。

返される最終カウント値は減衰後の値であり、0になることもある。

LFUカウントの更新と対数

  1. /* カウンタを対数的に増加します。現在のカウンタ値が大きいほど
  2.  *実際に実装される可能性は低くなります。255 で飽和させます。 * /
  3.  uint8_t LFULogIncr(uint8_t カウンター) {
  4.     if (counter == 255) 255を返します。
  5. ダブルr = (ダブル)rand()/RAND_MAX;
  6. ダブルベースバル = カウンター - LFU_INIT_VAL;
  7.     baseval < 0 の場合、baseval = 0;
  8. ダブルp = 1.0 /（ベース値*サーバー.lfu_log_factor + 1）;
  9.     r < pの場合counter++;
  10. 返品カウンター;
  11.  }

カウントが 255 を超える場合は、カウントせずに直接戻ります。 LFU_INIT_VALは初期値で、デフォルトは5です。

初期値を減算した後、baseval が 0 未満の場合、有効期限が近づいていることを意味するため、カウンター値を増やす可能性が高くなります。

  1. ダブルp = 1.0 /（ベース値*サーバー.lfu_log_factor + 1）;

この確率アルゴリズムでは、lfu_log_factor は対数の底であり、デフォルト値は 10 です。カウンター値が小さい場合、自己増加の確率は大きくなります。カウンターが大きい場合、何もしない傾向があります。

カウンター値の範囲は 0 ～ 255 で、十分なアクセス頻度を表すことができます。

  1.  # + --------+-------------+-------------+-------------+-------------+-------------+  
  2.  # | 係数 | 100 ヒット | 1000 ヒット | 100K ヒット | 100 万ヒット | 1000 万ヒット |
  3.  # + --------+-------------+-------------+-------------+-------------+-------------+  
  4.  # | 0 | 104 | 255 | 255 | 255 | 255 |
  5.  # + --------+-------------+-------------+-------------+-------------+-------------+  
  6.  # | 1 | 18 | 49 | 255 | 255 | 255 |
  7.  # + --------+-------------+-------------+-------------+-------------+-------------+  
  8.  # | 10 | 10 | 18 | 142 | 255 | 255 |
  9.  # + --------+-------------+-------------+-------------+-------------+-------------+  
  10.  # | 100 | 8 | 11 | 49 | 143 | 255 |
  11.  # + --------+-------------+-------------+-------------+-------------+-------------+  

この機能に基づいて、redis-cli --hotkeys コマンドを使用して、最近の期間のシステム内のホットキーを表示できます。これは非常に実用的です。この機能は旧バージョンでは利用できないため、手動で統計を行う必要があります。

  1.  $ redis-cli --hotkeys  
  2.  # キースペース全体をスキャンしてホットキーと 
  3.  #キータイプごとの平均サイズ。-i 0.1 を使用すると0.1 秒スリープできます
  4. # 100 回の SCAN コマンドあたり (通常は必要ありません)。
  5.  ......
  6.  [47.62%] ホットキー  'key17' がカウンター 6で見つかりました
  7. [57.14%] ホットキー  'key43' がカウンター 7で見つかりました
  8. [57.14%] ホットキー  'key14' がカウンター 6で見つかりました
  9. [85.71%] ホットキー  'key42' がカウンター 7で見つかりました
  10. [85.71%] ホットキー  'key45' がカウンター 8で見つかりました
  11. [95.24%] ホットキー  'key50' がカウンター 7で見つかりました
  12.  
  13.  -  -  -  -  まとめ  -  -  - -   
  14.  
  15. キースペースで105 個のキーをサンプリングしました。
  16. カウンター: 7で見つかったホットキー、キー名: key40
  17. カウンター: 7で見つかったホットキー キー名: key42
  18. カウンター: 7で見つかったホットキー、キー名: key50

キャッシュインジケーターについて

上で説明した Redis LFU 実装は集中型キャッシュです。また、多くのプロセス用のローカル キャッシュもあります。キャッシュ実装の品質をどのように評価するか？指標は多数あり、詳細がより重要

スループット: QPS はよく言及されます。ベンチマーク バケット実装のハッシュマップの複雑さは O(1) です。キャッシュの複雑さはより高く、ロックの競合にも対処する必要があります。つまり、キャッシュ ライブラリ実装の効率はより高くなります。

キャッシュヒット率: スループットだけでは不十分です。キャッシュヒット率も非常に重要です。ヒット率が高ければ高いほど、キャッシュ導入の効果は大きくなります。

高度な機能: キャッシュ メトリック統計、キャッシュの内訳の処理方法など。

<<:  AIは採用に何をもたらすのでしょうか?

>>:  コビオニクス、針を使わずにワクチンを投与する新しいロボットを開発

ブログ    
ブログ    
ブログ    

推薦する

プラグアンドプレイ、トレーニング不要：ケンブリッジ大学、テンセントAIラボなどがトレーニング不要のクロスモーダルテキスト生成フレームワークを提案

1. はじめにこの論文では、新しい MAGIC (iMAge-guided text Generat...

機械学習を使用して Airbnb のリスティングの価格を予測する

[[202603]]ギリシャ、エーゲ海、イメロヴィグリの Airbnb の美しい景色導入データ プロ...

...

AI アバターが CES に登場! Samsung の Neon チャットボットは学習、進化、記憶が可能です!

サムスンの待望のスマートヒューマンプロジェクト「Neon」が、ついにCES 2020でデビューしまし...

感染症の流行に直面して、AIがいかに有用であるかを実感した

インターネット時代では、テクノロジーの発展により、私たちの生活で利用できる手段が大幅に強化されました...

ビジネスプロセス管理を使用してマイクロサービス、人、ロボットを調整する方法

DevOps チームがプロセスの自動化を計画している場合は、ビジネス プロセス管理 (BPM) エン...

...

...

2000年以降の大学生が伝染病と戦うロボットを設計

「私たちのロボット戦車は防疫ロボットに転用できるだろうか？」疫病流行の期間中、山東科技大学の学生たち...

1行のコードで大規模モデルのパフォーマンスが10%向上、開発者は無料でランチを楽しめる

大規模なモデルを微調整するための「無料ランチ」ができました。たった 1 行のコードで、パフォーマンス...

人工知能に置き換えられる可能性が最も高い職業トップ10。今年の転職ではこの罠に陥らないように！

[[220405]]今の時代、就職市場は戦場です。人工知能とロボットの発達は職場に衝撃を与えた。従...

教師なし機械学習の基本ガイド

[51CTO.com クイック翻訳] 教師なし機械学習と人工知能は、組織のビジネス成長に役立つことは...

LEACHプロトコルのアルゴリズムと特徴

LEACH プロトコルについてはあまり知られていないかもしれません。このプロトコルの説明は、低電力適...

AIに関する誤解

企業は意思決定を強化し、消費者体験を向上させるために、幅広いアプリケーションで人工知能を活用すること...

グラフィカル分散コンセンサスアルゴリズム

本日の記事では、グラフを使用して分散一貫性の実装原則を深く研究し、理解します。まず、自己を見つめ直す...