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実装

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

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

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

LFUの実装

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

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

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

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

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

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

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

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

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

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

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

LFUカウントの更新と対数

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

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

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

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

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

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

 # + --------+-------------+-------------+-------------+-------------+-------------+  
 # | 係数 | 100 ヒット | 1000 ヒット | 100K ヒット | 100 万ヒット | 1000 万ヒット |
 # + --------+-------------+-------------+-------------+-------------+-------------+  
 # | 0 | 104 | 255 | 255 | 255 | 255 |
 # + --------+-------------+-------------+-------------+-------------+-------------+  
 # | 1 | 18 | 49 | 255 | 255 | 255 |
 # + --------+-------------+-------------+-------------+-------------+-------------+  
 # | 10 | 10 | 18 | 142 | 255 | 255 |
 # + --------+-------------+-------------+-------------+-------------+-------------+  
 # | 100 | 8 | 11 | 49 | 143 | 255 |
 # + --------+-------------+-------------+-------------+-------------+-------------+

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

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