プログラミング技術のキャッシュ書き込み方式(3)

前回はマルチレベルキャッシュについて説明しましたが、この章ではメモリキャッシュの設計方法を詳しく紹介します。

1: 分析と設計

次のように、マルチレベル キャッシュの使用を必要とする一定量の同時実行性を持つプロジェクトがあるとします。

実際にメモリ キャッシュを設計する前に、次のことを考慮する必要があります。問題:

1: Redis によるメモリ データの置換により、メモリ内のデータ ヒット率が可能な限り向上し、次のレベルでのプレッシャーが軽減されます。

2: メモリ容量の制限、キャッシュの数を制御する必要があります。

3: ホットスポット データの更新は異なり、単一キーの有効期限を構成できる必要があります。

4: 優れたキャッシュ有効期限削除戦略。

5: キャッシュ データ構造の複雑さを可能な限り低く保ちます。

置換とヒット率について:実装が簡単で、キャッシュキーのヒット率も非常に優れているため、LRUアルゴリズムを使用します。

LRU とは、最も最近アクセスされていないデータを削除し、頻繁にアクセスされるデータをホット データとします。

LRU データ構造について: キーの優先順位の昇格とキーの削除のため、シーケンシャルな構造が必要です。ほとんどの実装では、リンク リストの先頭に新しいデータが挿入され、ヒットしたデータが先頭に移動するというリンク リスト構造が採用されていることがわかりました。 複雑さを追加するのは O(1)、移動して複雑さを取得するのは O(N) です。

もっと複雑でないものはありますか? Dictionary があり、その複雑さは O(1) で最高のパフォーマンスを持っています。 では、キャッシュの優先順位を確実に向上させるにはどうすればよいでしょうか?

2: O(1) LRU 実装

LRUCache クラスを定義し、キャッシュの最大数を制御するパラメータ maxKeySize を構築します。

キャッシュ コンテナとして ConcurrentDictionary を使用し、スレッドの安全性を確保します。

public class LRUCache<TValue> : IEnumerable<KeyValuePair<string, TValue>>
   {
       private long ageToDiscard = 0;  //淘汰的年龄起点
       private long currentAge = 0;        //当前缓存最新年龄
       private int maxSize = 0;          //缓存最大容量
       private readonly ConcurrentDictionary<string, TrackValue> cache;
       public LRUCache(int maxKeySize)
       {
           cache = new ConcurrentDictionary<string, TrackValue>();
           maxSize = maxKeySize;
       }
   }

2 つの自己増加パラメーター ageToDiscard と currentAge は、キャッシュ リスト内の各キーの新しさをマークするために定義されています。

コアの実装手順は次のとおりです:

1: キーが追加されるたびに、currentAge が増分され、currentAge 値がこのキャッシュ値の Age に割り当てられます。

public void Add(string key, TValue value)
       {
           Adjust(key);
           var result = new TrackValue(this, value);
           cache.AddOrUpdate(key, result, (k, o) => result);
       }
       public class TrackValue
       {
           public readonly TValue Value;
           public long Age;
           public TrackValue(LRUCache<TValue> lv, TValue tv)
           {
               Age = Interlocked.Increment(ref lv.currentAge);
               Value = tv;
           }
       }

2:追加する際、最大数量を超えた場合。辞書に ageToDiscard 年齢キーがあるかどうかを確認します。巡回自動インクリメント チェックがない場合、削除と追加は成功します。

ageToDiscard+maxSize= currentAge なので、リンク リストの移動を使用する代わりに、O(1) で古いデータを確実に削除できるように設計されています。

public void Adjust(string key)
        {
            while (cache.Count >= maxSize)
            {
                long ageToDelete = Interlocked.Increment(ref ageToDiscard);
                var toDiscard =
                      cache.FirstOrDefault(p => p.Value.Age == ageToDelete);
                if (toDiscard.Key == null)
                    continue;
                TrackValue old;
                cache.TryRemove(toDiscard.Key, out old);
            }
        }

期限切れの削除戦略

ほとんどの場合、LRU アルゴリズムはホットスポット データに対して高いヒット率を示します。 しかし、突発的に大量のデータアクセスが突然発生すると、大量のコールドデータがメモリに格納され、キャッシュ汚染が発生します。

により、LRU がホットスポット データにヒットできなくなり、キャッシュ システムのヒット率が急激に低下します。 LRU-K、2Q、MQ などのバリアント アルゴリズムを使用してヒット率を向上させることもできます。

有効期限設定

1: 最大有効期限を設定することで、メモリ内にコールド データが常駐することを回避しようとします。

2: ほとんどの場合、各キャッシュの時間要件が一貫していないため、単一キーの有効期限が長くなります。

private TimeSpan maxTime;
public LRUCache(int maxKeySize,TimeSpan maxExpireTime){}
 
 //TrackValue增加创建时间和过期时间
public readonly DateTime CreateTime;
public readonly TimeSpan ExpireTime;

削除戦略

1: キーの有効期限の削除に関しては、スケジュールされた削除を使用するのが最善です。 これにより、占有されているメモリをできるだけ早く解放できますが、明らかに多数のタイマーは CPU にとって多すぎます。

2：所以我们采用惰性删除、在获取key的时检查是否过期，过期直接删除。

public Tuple<TrackValue, bool> CheckExpire(string key)
        {
            TrackValue result;
            if (cache.TryGetValue(key, out result))
            {
                var age = DateTime.Now.Subtract(result.CreateTime);
                if (age >= maxTime || age >= result.ExpireTime)
                {
                    TrackValue old;
                    cache.TryRemove(key, out old);
                    return Tuple.Create(default(TrackValue), false);
                }
            }
            return Tuple.Create(result, true);
        }

3：惰性删除虽然性能最好，对于冷数据来说，还是没解决缓存污染问题。 所以我们还需定期清理。

比如：开个线程，5分钟去遍历检查key一次。这个策略根据实际场景可配置。

public void Inspection()
        {
            foreach (var item in this)
            {
                CheckExpire(item.Key);
            }
        }

惰性删除+定期删除基本能满足我们需求了。

总结

如果继续完善下去，就是内存数据库的雏形，类似redis。

比如：增加删除key的通知，增加更多数据类型。 本篇也是参考了redis、Orleans的实现。