大家好，我是讯享网，很高兴认识大家。



 <p> 

讯享网

业务中存在访问热点是在所难免的，然而如何发现热点key一直困扰着许多用户，redis4.0为我们带来了许多新特性，其中便包括基于LFU的热点key发现机制。

从LFU的字面意思我们很容易联想到key的访问频率，但是4.0最初版本仅用来做内存逐出，对于访问频率并没有很好的记录，那么经过一番改造，redis于4.0.3版本开始正式支持基于LFU的热点key发现机制。 它也是基于局部性原理：如果一个数据在最近一段时间内使用次数最少，那么在将来一段时间内被使用的可能性也很小

在 算法中，可以为每个key维护一个计数器。每次key被访问的时候，计数器增大。计数器越大，可以约等于访问越频繁。

在redis中每个对象都有24 bits空间来记录LRU/LFU信息：

讯享网typedefstructredisObject {     unsigned type:4;     unsigned encoding:4;     unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or                             * LFU data (least significant 8 bits frequency                             * and most significant 16 bits access time). */     int refcount;     void *ptr; } robj;

当这24 bits用作LFU时，其被分为两部分：

           16 bits         8 bits       +------------------+--------+       + Last access time | LOG_C  |       +------------------+--------+

讯享网void updateLFU(robj *val) {     unsigned long counter = LFUDecrAndReturn(val);     //counter增长函数     counter = LFULogIncr(counter);     val->lru = (LFUGetTimeInMinutes()<<8) | counter; }

 #define LFU_INIT_VAL 5 server.lfu_log_factor = CONFIG_DEFAULT_LFU_LOG_FACTOR; //server.c  概率因子 #define CONFIG_DEFAULT_LFU_LOG_FACTOR 10  //server.h //counter增长函数 uint8_t LFULogIncr(uint8_t counter) { //如果已经到最大值255，返回255 ，8位的最大值       if (counter == 255) return 255;   //取一随机小数（0-1）       double r = (double)rand()/RAND_MAX; //新加入的key初始counter设置为LFU_INIT_VAL,为5.不设置为0的原因是防止直接被逐出。       double baseval = counter - LFU_INIT_VAL;       if (baseval < 0) baseval = 0;       double p = 1.0/(baseval*server.lfu_log_factor+1); //可以看到,counter越大,则p越小，随机值r小于p的概率就越小。换言之,counter增加起来会越来越缓慢       if (r < p) counter++;       return counter;//counter 访问频率   }

对应的概率分布计算公式为：

讯享网1/((counter-LFU_INIT_VAL)*server.lfu_log_factor+1)

并不是简单的访问一次就+1，而是采用了一个0-1之间的p因子控制增长。 最大值为255。取一个0-1之间的随机数r与p比较，当 时，才增加 控制产出的策略。p取决于当前 值与 因子， 值与 因子越大，p越小， 的概率也越小， 增长的概率也就越小。

LRU本质上是一个概率计数器，称为morris counter.随着访问次数的增加,counter的增加会越来越缓慢。如下是访问次数与counter值之间的关系

+--------+------------+------------+------------+------------+------------+ | factor | 100 hits   | 1000 hits  | 100K hits  | 1M hits    | 10M hits   |+--------+------------+------------+------------+------------+------------+ | 0      | 104        | 255        | 255        | 255        | 255        |+--------+------------+------------+------------+------------+------------+ | 1      | 18         | 49         | 255        | 255        | 255        |+--------+------------+------------+------------+------------+------------+ | 10     | 10         | 18         | 142        | 255        | 255        |+--------+------------+------------+------------+------------+------------+ | 100    | 8          | 11         | 49         | 143        | 255        |+--------+------------+------------+------------+------------+------------+

factor即server.lfu_log_facotr配置值，默认为10.可以看到,一个key访问一千万次以后counter值才会到达255.factor值越小, counter越灵敏.可见 增长与访问次数呈现对数增长的趋势，随着访问次数越来越大， 增长的越来越慢。

其中LFU_INIT_VAL为5，我们看下概率分布图会有一个更直观的认识，以默认server.lfu_log_factor=10为例：

1/((counter-5)*10+1)



从上图可以看到，counter越大，其增加的概率越小，8 bits也足够记录很高的访问频率，

也就是说，默认server.lfu_log_factor为10的情况下，8 bits的counter可以表示1百万的访问频率。

另外一个问题是，当创建新对象的时候，对象的 如果为0，很容易就会被淘汰掉，还需要为新生key设置一个初始 ， :

讯享网robj *createObject(int type, void *ptr) {     robj *o = zmalloc(sizeof(*o));     o->type = type;     o->encoding = OBJ_ENCODING_RAW;     o->ptr = ptr;     o->refcount = 1;     /* Set the LRU to the current lruclock (minutes resolution), or      * alternatively the LFU counter. */     if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {         o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;     } else {         o->lru = LRU_CLOCK();     }     return o; }

会被初始化为 ，默认5。

从上一小节的counter增长函数LFULogIncr中我们可以看到，随着key的访问量增长，counter最终都会收敛为255，这就带来一个问题，如果counter只增长不衰减就无法区分热点key。

为了解决这个问题，redis提供了衰减因子server.lfu_decay_time，其单位为分钟，计算方法也很简单，如果一个key长时间没有访问那么它的计数器counter就要减少，减少的值由衰减因子来控制：

unsigned long LFUDecrAndReturn(robj *o) {     //lru字段右移8位，得到前面16位的分钟时间戳     unsignedlong ldt = o->lru >> 8; //lru字段与255进行&运算（255代表8位的最大值），得到8位当前counter值     unsignedlong counter = o->lru & 255; //总的没访问的分钟时间/配置值，得到每分钟没访问衰减多，默认每经过一分钟counter衰减1     unsignedlong num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;     if (num_periods)      //计算衰减后的值         counter = (num_periods > counter) ? 0 : counter - num_periods;     return counter; }

默认为1的情况下也就是N分钟内没有访问，counter就要减N。

函数首先取得高16 bits的最近降低时间 与低8 bits的计数器 ，然后根据配置的 计算应该降低多少。

用来计算当前时间与 的差值：

讯享网/* Return the current time in minutes, just taking the least significant * 16 bits. The returned time is suitable to be stored as LDT (last decrement * time) for the LFU implementation. */unsignedlongLFUGetTimeInMinutes(void) {     return (server.unixtime/60) & 65535; } /* Given an object last access time, compute the minimum number of minutes * that elapsed since the last access. Handle overflow (ldt greater than * the current 16 bits minutes time) considering the time as wrapping * exactly once. */unsignedlongLFUTimeElapsed(unsignedlong ldt) {     unsignedlong now = LFUGetTimeInMinutes();     if (now >= ldt) return now-ldt;     return65535-ldt+now; }

具体是当前时间转化成分钟数后取低16 bits，然后计算与 的差值 。当 时，默认为过了一个周期(16 bits，最大65535)，取值 。

然后用差值与配置 相除， ，已过去n个 ，则将 减少n， 。

4.0之后为 淘汰策略添加了两个 模式：

还有2个配置可以调整 算法：

lfu-log-factor 10 lfu-decay-time1

可以调整计数器 的增长速度， 越大， 增长的越慢。

是一个以分钟为单位的数值，可以调整 的减少速度

介绍完LFU算法，接下来就是我们关心的热点key发现机制。

其核心就是在每次对key进行读写访问时，更新LFU的24 bits域代表的访问时间和counter，这样每个key就可以获得正确的LFU值：

讯享网void updateLFU(robj*val) { //首先计算是否需要将counter衰减     unsigned long counter = LFUDecrAndReturn(val); //根据上述返回的counter计算新的counter     counter = LFULogIncr(counter); //robj中的lru字段只有24bits,lfu复用该字段。高16位存储一个分钟数级别的时间戳，低8位存储访问计数     val->lru = (LFUGetTimeInMinutes()<<8) | counter; }

client cache的问题是缓存应该何时失效，更确切的说是如何保持与远端数据的一致性。 为client cache设置过期时间是一个选择，但时间设置多久是一个问题。太长会有时效性问题，太短缓存的效果会打折扣。

redis在服务端记录访问的连接和相关的key， 当key有变化时，通知相应的连接(应用)。 , 进而实现client cache与redis的一致。



redis对客户端缓存的支持方式被称为 ，分为两种模式：默认模式，广播模式。

Server 端记录每个Client访问的Key，当发生变更时，向client推送数据过期消息。

当tracking开启时， Redis会「记住」每个客户端请求的 key，当 key的值发现变化时会发送失效信息给客户端 (invalidation message)。失效信息可以通过 RESP3协议发送给请求的客户端，或者转发给一个不同的连接 (支持 RESP2 + Pub/Sub) 的客户端。

Server 端将 Client 访问的 key以及该 key 对应的客户端 ID 列表信息存储在全局唯一的表（TrackingTable），当表满了，回移除最老的记录，同时触发该记录已过期的通知给客户端。

每个 Redis 客户端又有一个唯一的数字 ID，TrackingTable 存储着每一个 Client ID，当连接断开后，清除该 ID 对应的记录。

TrackingTable 表中记录的 Key 信息不考虑是哪个 database 的，虽然访问的是 db1 的 key，db2 同名 key 修改时会客户端收到过期提示，但这样做会减少系统的复杂性，以及表的存储数据量。

Redis 用TrackingTable存储键的指针和客户端 ID 的映射关系。因为键对象的指针就是内存地址，也就是长整型数据。客户端缓存的相关操作就是对该数据的增删改查：



客户端订阅key前缀的广播(空串表示订阅所有失效广播)，服务端记录key前缀与client的对应关系。当相匹配的key发生变化时，通知client。

当广播模式 (broadcasting) 开启时，服务器不会记住给定客户端访问了哪些键，因此这种模式在服务器端根本不消耗任何内存。

在这个模式下，服务端会给客户端广播所有 key 的失效情况，如果 key 被频繁修改，服务端会发送大量的失效广播消息，这就会消耗大量的网络带宽资源。

所以，在实际应用中，我们设置让客户端注册只跟踪指定前缀的 key，当注册跟踪的 key 前缀匹配被修改，服务端就会把失效消息广播给所有关注这个 key前缀的客户端。

这种监测带有前缀的 key 的广播模式，和我们对 key 的命名规范非常匹配。我们在实际应用时，会给同一业务下的 key 设置相同的业务名前缀，所以，我们就可以非常方便地使用广播模式。





redis6.0开始使用新的协议RESP3。该协议增加了很多数据类型。