高性能本地缓存Ristretto(二)——过期策略

ristretto提供了SetWithTTL()方法，支持创建key的同时，并设置一个过期时间。
ristretto 利用嵌套的map结构，并结合巧妙的存储方式，实现了对每一个key的过期时间的管理。并能在时间到期后，尽快的删除过期的key，以节省资源开销。

过期时间的存储结构

ristretto采用嵌套的map结构记录key以及对应的过期时间，如下所示：

type shardedMap struct {
	...
	expiryMap    *expirationMap  // expirationMap 是全局共享的
	...
}

type expirationMap struct {
	...
	buckets map[int64]bucket    //  buckets的value也是map
}

type bucket map[uint64]uint64    // bucket 本质上是一个map结构

对于以上结构buckets的key是时间戳。bucket中的key和 value则 分别存储是keyHash和conflictHash值（对于这两个值如何得到的，请参考上一篇文章高性能本地缓存Ristretto(一)——存储策略）。这么干说可能有点懵逼，举个例子，画个图可能更形象。

假如有 key = “ZHH” value= “ZhaoHaihang” 需要缓存，并且要设置过期时间为5秒。通过keyToHash（）对key做hash得到keyHash= “666" 和 conflictHash=“888”，并且现在的时间戳为1000。则最终该结构会以如下图的方式存储：

其中，1005为key = “ZHH” value= “ZhaoHaihang” 这条数据的过期时间戳。1005对应的value为bucket2，因此bucket2中的key、value分别为666，888

过期时间的存储策略

仔细考虑可以发现，上面的存储方式可能还有些可优化的地方。我们真的需要将key按每一秒划分bucket吗？如果按每5秒 划分为一个bucket是不是也行呢？

比如，在10秒钟内，每一秒存了1个key。时间戳分别为1000 - 1010，key分别为A-J，每个key的过期时间为5s，则key与之对应的过期时间戳为：

体现在内存中存储结构就变成了如下图所示：

图中，对每一个时间戳除5取整，得到buckets中的key，然后将keyHash 和conflictHash 分别作为bucket的key和value。

具体流程

对大概的存储方式有一定了解后，再结合代码看具体的流程就非常容易了，同时对于key如何过期的就能了解的更清楚。

接下来将以写缓存为例，详细梳理，key的过期时间的存储方式，和删除过期key的方法。

存储key过期时间的流程

1. 调用SetWithTTL()函数，在写缓存的同时为key设置一个过期时间。以秒为单位。
   
   图中，参数ttl即为过期时间。并在内部调用setInternal()

2. setInternal()函数中，对通过ttl 计算key的过期时间戳，并记录在Item中，最终进入setBuf

3. 另外一个协程执行processItems()，从setBuf中取Item，根据不同的操作类型，执行不同的操作。

4. Set() 中会在增加一条key的过期时间的数据。
   

5. add() 先通过 storeBucket() 计算该时间戳应该是哪个bucket，之后将key 和 confict写入bucket就行了。
   
   storeBucket()中，就是通过将时间戳除5得到一个数值的。
   

如何删除过期了的key

已经知道了怎么存储过期时间，现在来看看过期的key是怎么被删除的吧。

1. 首先回到processItems()函数，里面有个定时器，会定时的执行CleanUp() 函数。

该定时器是在初始化的时候就设置好的：

可以发现，定时周期为 bucketDurationSecs / 2，还记得bucketDurationSecs 是多少吗？没错！是5，因此定时周期为2s，即每2秒就会执行一次清理任务。

2. Cleanup() 通过简单的封装，继续执行cleanup().
   
3. 在cleanup() 中，执行最终的删除操作。

cleanupBucket() 返回的是storageBucket() -1 ，即5秒前过期的key，这样就不会误删还没有过期的key。

至此，删除过期key的流程就执行完了。

现在，终于可以明白，为什么要以5秒为一个单位记录key，如果以每一秒，那删除操作的频率会很高，这显然是大可不必的。

链接

高性能本地缓存Ristretto(一)——存储策略