Programming technology cache writing method (3)

We talked about multi-level cache last time. This chapter introduces in detail how to design the memory cache.

1: Analysis and Design

Suppose there is a project with a certain amount of concurrency, which requires the use of multi-level cache, as follows:

Before actually designing a memory cache, we need to consider issues:

1: Memory Data replacement with Redis improves the data hit rate in memory as much as possible and reduces the pressure on the next level.

2: Memory capacity limit, the number of caches needs to be controlled.

3: Hotspot data updates are different and a single key expiration time needs to be configurable.

4: Good cache expiration deletion strategy.

5: Keep the complexity of the cache data structure as low as possible.

About replacement and hit rate: We use the LRU algorithm because it is simple to implement and the cache key hit rate is also very good.

LRU means: eliminate the data that has been accessed least recently, and the data that is frequently accessed is hot data.

About LRU data structure: Because of key priority promotion and key elimination, a sequential structure is required. I have seen that most implementations adopt a linked list structure, that is: new data is inserted into the head of the linked list, and the data when hit is moved to the head. Adding complexity is O(1) and moving and getting complexity is O(N).

Is there anything less complex? There is Dictionary, whose complexity is O(1) and has the best performance. So how to ensure that the cache priority is improved?

Two: O(1) LRU implementation

We define a LRUCache class and construct the parameter maxKeySize to control the maximum number of caches.

Use ConcurrentDictionary as our cache container and ensure thread safety.

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;
       }
   }

The two self-increasing parameters ageToDiscard and currentAge are defined above. Their function is to mark the newness of each key in the cache list.

The core implementation steps are as follows:

1: Each time a key is added, currentAge is incremented and the currentAge value is assigned to the Age of this cache value. CurrentAge always increases.

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: When adding, if the maximum quantity is exceeded. Check whether there is an ageToDiscard age key in the dictionary. If there is no cyclic auto-increment check, the deletion and addition will be successful.

ageToDiscard+maxSize= currentAge, so that the design can ensure that old data can be eliminated under O(1) instead of using linked list movement.

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);
            }
        }

Expired deletion strategy

In most cases, the LRU algorithm has a high hit rate for hotspot data. However, if a large number of sporadic data accesses occur suddenly, a large amount of cold data will be stored in the memory, which is cache pollution.

will cause LRU to be unable to hit hotspot data, causing the cache system hit rate to drop sharply. Variant algorithms such as LRU-K, 2Q, and MQ can also be used to improve the hit rate.

Expiration configuration

1: We try to avoid cold data resident in memory by setting the maximum expiration time.

2: In most cases, the time requirements of each cache are inconsistent, so the expiration time of a single key is increased.

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

Deletion strategy

1: Regarding key expiration deletion, it is best to use scheduled deletion. This can release the occupied memory as quickly as possible, but obviously, a large number of timers are too much for the 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的实现。