【原理】Redis 热点 Key 自动发现机制和客户端缓存方案

2024-11-01
北京
本文字数：5215 字
阅读完需：约 17 分钟

作者：京东物流京东物流

本文详细讲解下 Redis 热点 key 发现机制+客户端缓存的原理。

一、redis4.0 之基于 LFU 的热点 key 发现机制

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

Redis 中的 LFU 思路

Least Frequently Used——简称 LFU，意为最不经常使用，是 redis4.0 新增的一类内存逐出策略，

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

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

1.1、LFU 算法介绍

在 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 时，其被分为两部分：

1.高 16 位用来记录访问时间（单位为分钟）

2.低 8 位用来记录访问频率，简称 counter

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

复制代码

1.1.1、counter：基于概率的对数计数器

这里读者可能会有疑问，8 bits 最大值也就是 255，只用 8 位来记录访问频率够用吗？对于 counter，redis 用了一个 trick 的手段，counter 并不是一个简单的线性计数器，而是用基于概率的对数计数器来实现，算法如下：

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

复制代码

 #define LFU_INIT_VAL 5server.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)

复制代码

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

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 越灵敏.可见counter增长与访问次数呈现对数增长的趋势，随着访问次数越来越大，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 百万的访问频率。

1.1.2、新生 key 策略

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

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

复制代码

counter会被初始化为LFU_INIT_VAL，默认 5。

1.1.3、counter 的衰减因子

从上一小节的 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 的最近降低时间ldt与低 8 bits 的计数器counter，然后根据配置的lfu_decay_time计算应该降低多少。

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

/* 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，然后计算与ldt的差值now-ldt。当ldt > now时，默认为过了一个周期(16 bits，最大 65535)，取值65535-ldt+now。

然后用差值与配置lfu_decay_time相除，LFUTimeElapsed(ldt) / server.lfu_decay_time，已过去 n 个lfu_decay_time，则将counter减少 n，counter - num_periods。

1.1.4、LFU 配置

Redis4.0 之后为maxmemory_policy淘汰策略添加了两个LFU模式：

•volatile-lfu：对有过期时间的 key 采用LFU淘汰算法

•allkeys-lfu：对全部 key 采用LFU淘汰算法

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

lfu-log-factor 10lfu-decay-time1

复制代码

lfu-log-factor可以调整计数器counter的增长速度，lfu-log-factor越大，counter增长的越慢。

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

1.热点 key 发现

介绍完 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;}

复制代码

二、redis6.0 客户端缓存方案

1.1 client cache 的问题

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

1.2 redis 6.0 的解决方式

1.2.1 整体思想

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

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

1.2.2 默认模式

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 的映射关系。因为键对象的指针就是内存地址，也就是长整型数据。客户端缓存的相关操作就是对该数据的增删改查：

•优点：只对 Client 发送其访问过的被修改的数据

•缺点：Server 端需要额外存储较大的数据量。

1.2.3 广播模式

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

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

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

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

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

•优点：服务端记录信息比较少

•缺点：client 会收到自己未访问过的 key 的失效通知。

1.2.4 RESP3 协议

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

三、参考

1.https://redis.io/docs/manual/client-side-caching/

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/c15752c372b12223a775dc471】。文章转载请联系作者。

京东科技开发者

关注

拥抱技术，与开发者携手创造未来！ 2018-11-20 加入

我们将持续为人工智能、大数据、云计算、物联网等相关领域的开发者，提供技术干货、行业技术内容、技术落地实践等文章内容。京东云开发者社区官方网站【https://developer.jdcloud.com/】，欢迎大家来玩

发布

暂无评论

创作场景

【原理】Redis 热点 Key 自动发现机制和客户端缓存方案

一、redis4.0 之基于 LFU 的热点 key 发现机制

Redis 中的 LFU 思路

1.1、LFU 算法介绍

1.1.1、counter：基于概率的对数计数器

1.1.2、新生 key 策略

1.1.3、counter 的衰减因子

1.1.4、LFU 配置

二、redis6.0 客户端缓存方案

1.1 client cache 的问题

1.2 redis 6.0 的解决方式

1.2.1 整体思想

1.2.2 默认模式

1.2.3 广播模式

1.2.4 RESP3 协议

三、参考

京东科技开发者

评论