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

京东云开发者
• 阅读 55

作者:京东物流 京东物流

本文详细讲解下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 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)

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)

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

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



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

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



1.1.2、新生key策略

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

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 10
lfu-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热点Key自动发现机制和客户端缓存方案

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



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

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



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

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

1.2.3 广播模式

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

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



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



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

这种监测带有前缀的 key 的广播模式,和我们对 key 的命名规范非常匹配。我们在实际应用时,会给同一业务下的 key 设置相同的业务名前缀,所以,我们就可以非常方便地使用广播模式。 【原理】Redis热点Key自动发现机制和客户端缓存方案



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

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

1.2.4 RESP3协议

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

三、参考

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

点赞
收藏
评论区
推荐文章
Stella981 Stella981
3年前
Redis cluster eval的使用
对于eval有一个很大的约束在集群模式下,即lua所用到的key必须在该节点上因此可以借助solt来发送到指定的key存在的节点上 因此需要redisclient正确处理key方法1:  通过client显示指定key 发送到对应的节点上,lua代码不参与redis缓存每次发送到redis的lua代码都是新的因为把用到的东西都
Stella981 Stella981
3年前
Redis 热点key
压测报redis热点问题热点问题概述产生原因热点问题产生的原因大致有以下两种:用户消费的数据远大于生产的数据(热卖商品、热点新闻、热点评论、明星直播)。在日常工作生活中一些突发的的事件,例如:双十一期间某些热门商品的降价促销,当这其中的某一件商品被数万次点
Stella981 Stella981
3年前
Redis4.0新特性(二)
Redis4.0新增了非常实用的lazyfree特性,从根本上解决BigKey(主要指定元素较多集合类型Key)删除的风险。笔者在redis运维中也遇过几次BigKey删除带来可用性和性能故障。本文分为以下几节说明redislazyfree:lazyfree的定义我们为什么需要lazyfreelazyfr
Stella981 Stella981
3年前
Redis的7个应用场景
一:缓存——热数据热点数据(经常会被查询,但是不经常被修改或者删除的数据),首选是使用redis缓存,毕竟强大到冒泡的QPS和极强的稳定性不是所有类似工具都有的,而且相比于memcached还提供了丰富的数据类型可以使用,另外,内存中的数据也提供了AOF和RDB等持久化机制可以选择,要冷、热的还是忽冷忽热的都可选。结合具体应用需要注意一下:很
Easter79 Easter79
3年前
TiDB 4.0 为解决热点问题做了哪些改进?
作者:李坤热点问题概述一直以来,TiDB的数据访问热点问题,是用户比较关注的问题。为什么这个问题如此突出呢?这其实是“分布式”带来的结构效应。单机数据库由于只有一个节点,是不存在热点问题的(因为性能的上限就是单机的处理能力),而分布式数据库集群存在多个节点,在达到存储扩展、读写能力扩展的目的上,我们希望大量的读写压力能够平摊在每个节点
Stella981 Stella981
3年前
Redis 缓存问题及解决方案
【相关概念】缓存击穿:指的是一些热点数据过期,由于热点数据存在并发量大的特性,所以短时间内对数据库的造成很大的冲击,导致系统瘫痪。常见于例如微博系统中明星结婚或出轨时微博瘫痪的情况。缓存雪崩:指的是大量数据或全部数据集中过期失效的情况,这种情况是由于大量数据设置了相同的过期时间而导致的。【使用缓存的流程】
一种基于Nginx的热点数据调度处理方法
基于Nginx的热点数据调度处理,热点节点数据负载均衡处理,减少热点节点压力,提高处理和访问效率;每一个节点的nginx服务接收大量的访问,但是每个节点处理请求都有一个峰值,当请求数达到峰值时,后续请求的处理效率就会有一定的下降,为了保证请求能及时处理,热点节点会触发请求调度策略,转发请求到非热点节点进行处理,若无非热点节点,则触发分布式节点策略,备机节点会启动Nginx服务处理,并接收热点节点转发过来的请求,从而提升访问及处理效率。
浅谈Redis - 热点key问题 | 京东云技术团队
热key问题就是突然有几十万的请求去访问redis上的某个特定key,那么这样会造成流量过于集中,达到物理网卡上限,从而导致这台redis服务器直接宕机。
浅析Redis大Key | 京东云技术团队
一、背景在京东到家购物车系统中,用户基于门店能够对商品进行加车操作。用户与门店商品使用Redis的Hash类型存储,如下代码块所示。不知细心的你有没有发现,如果单门店加车商品过多,或者门店过多时,此Key就会越来越大,从而影响线上业务。userPin:st
京东云开发者 京东云开发者
1个月前
ChatGPT背后的AI背景、技术门道和商业应用(万字长文,建议收藏)
作者:京东科技李俊兵各位看官好,我是球神(江湖代号)。自去年11月30日ChatGPT问世以来,迅速爆火出圈。起初我依然以为这是和当年Transformer,Bert一样的“热点”模型,但是当一篇篇文章/报告不断推送到我的眼前,我后知后觉地发现这次真的不一