《redis深度历险》十-LRU\LFU

LFU VS LRU

LFU:least frequntly used,按最近的访问频率淘汰,比LRU更加精准的表示了一个key的被访问热度。

redis对象的热度

redis的所有对象头结构中都有一个24bit的字段,用来记录对象的热度。

typedef struct redisObject {
	unsigned type:4; // 对象类型如 zset,set,hash等
	unsigned encoding:4 // 对象编码如ziplist,intset,skiplist等
	unsigned lru:24; // 对象的热度
	int refcount; // 引用计数
	void *ptr // 对象的body
}robj

LRU

Least Recently Used

在 LRU 模式下, lru 字段存储的是 Redis 时钟 server.lruclocko Redis 时钟是一个24bit 的整数,默认是 Unix 时间戳对 2^24 取模的结果,大约 97 天清零一次 。当某个 key被访问一次,它的对象头结构的 lru字段值就会被更新为 server.lruclock。

如果 server.lruclock 没有折返(对 2^24 取模〉,它就是一直递增的,这意昧着对 象的 lru字段不会超过 server.lruclock的值。下方左图

如果超过了,说明 server.lruclock折返了。 通过这个逻辑就可以精准计算出对象多长时间没有被访问一一即“对象的空闲时间”。( 下方右图有些问题,lru不可能超过max的,小于等于max)

《redis深度历险》十-LRU\LFU

LFU

在LFU模式下,lru字段用来存储两个值,分别是ldt(last decrement time)16bit和logc(logistic counter)8bit

loge 是 8 个 bit,用来存储访问频次,因为 8 个 bit 能表示的最大整数值为 255,存储频次肯定远远不够,所以这 8 个 bit 存储的是频次的对数值,并且这个 值还会随时间衰减,如果它的值比较小,那么就很容易被回收。为了确保新创建的 对象不被回收,新对象的这 8 个 bit 会被初始化为一个大于零的值 LFU_INIT_VAL(默认是=5) 。

ldt 是 16 个 bit,用来存储上一次 loge 的更新时间。因为只有 16 个 bit,所以 精度不可能很高。它取的是分钟时间戳对 i6 进行取模,大约每隔 45 天就会折返。 下呈现了折返前后空闲时间的不同计算规则。同 LRU 模式一样,我们也可以 使用这个逻辑计算出对象的空闲时间,只不过精度是分钟级别的。图中的 server.unixtime 是当前 Redis 记录的系统时间戳,和 server.lruclock 一样,它也是每毫秒 更新一次。

《redis深度历险》十-LRU\LFU

ldt不是在对象被访问时更新的,而是在redis的淘汰逻辑进行时更新的,每次淘汰都是采用随机策略, 随机挑选若干个 key,更新这个 key 的“热度”,淘汰掉“热度”最低的 key。因为 Redis 采用的是随机算法,如果 key 比较多的话,那么 ldt 更新得可能会比较慢。不 过既然它是分钟级别的精度,也没有必要更新得过于频繁。

ldt 更新的同时也会一同衰减 loge 的值。衰减也有特定的算法。

总而言之,就是通过logc和ldt相互结合,可以获得某个键的使用频率。

缓存时间戳

redis每一次获取系统时 间戳都是一次系统调用, 系统调用相对来说是比较费时间的,作为单线程的Redis承 受不起,所以它需要对时间进行缓存,获取时间都是从缓存中直接拿。

惰性删除

共享机制

127.0.0.1:6379> sadd heat wade bosh james
(integer) 3
127.0.0.1:6379> sadd cavs irving love james
(integer) 3
127.0.0.1:6379> sunionstore players heat cavs
(integer) 5
127.0.0.1:6379> smembers players
1) "wade"
2) "bosh"
3) "james"
4) "love"
5) "irving"

新的集合包含了旧集合的所有元素,里面有一个trick,底层的字符串对象被共享了。

《redis深度历险》十-LRU\LFU

为什么对象共享是懒惰删除的最大障碍呢,因为懒惰删除相当于彻底砍掉某个树枝,将它扔到异步删除队列里去,这里是彻底删除,如果底层的对象是被共享的,就不是彻底删除,下图就不是彻底删除。

《redis深度历险》十-LRU\LFU

为了支持懒惰删除,就必须实现无共享设计。

异步删除的实现

主线程将删除任务传递给异步线程,他是通过一个普通的双向链表实现的,因为链表需要支持多线程并发操作,所以需要有锁来保护。

执行懒惰删除时, Redis 将删除操作的相关参数封装成一个 bio_job 结构,然后 追加到链表尾部。异步线程通过遍历链表摘取 job 元素来挨个执行异步任务 。

队列安全

前面提到任务队列是个不安全的双向链表 , 需要使用锁来保护它。当主线程 将任务追加到队列之前需要给它加锁,追加完毕后,再释放锁,还需要唤醒异步线 程一一 如果其在休眠的话。

异步线程需要对任务队列进行轮询处理,依次从链表表头摘取元素逐个处理 。 摘取元素的时候也需要加锁,摘出来之后再解锁。如果一个元素都没有,它需要等待, 直到主线程来唤醒它继续工作。

上一篇:高频笔试题 设计LRU 缓存


下一篇:计算机系统原理:cache容量计算