前言介绍
业务中存在访问热点是在所难免的，redis 也会遇到这个问题，然而如何发现热点 key 一直困扰着许多用户，redis4.0 为我们带来了许多新特性，其中便包括基于 LFU 的热点 key 发现机制。
Least Frequently Used
Least Frequently Used——简称 LFU，意为最不经常使用，是 redis4.0 新增的一类内存逐出策略，从 LFU 的字面意思我们很容易联想到 key 的访问频率，但是 4.0 最初版本仅用来做内存逐出，对于访问频率并没有很好的记录，那么经过一番改造，redis 于 4.0.3 版本开始正式支持基于 LFU 的热点 key 发现机制。
LFU 算法介绍
Redis 中每个对象都有 24 bits 空间来记录 LRU/LFU 信息：
typedef struct redisObject { 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 时，其被分为两部分：
counter：基于概率的对数计数器
8 bits 最大值也就是 255，只用 8 位来记录访问频率够用吗？
对于 counter，redis 用了一个 trick 的手段，counter 并不是一个简单的线性计数器，而是用基于概率的对数计数器来实现，算法如下：
uint8_t LFULogIncr(uint8_t counter) { if (counter == 255) return 255; double r = (double)rand()/RAND_MAX; double baseval = counter - LFU_INIT_VAL; if (baseval < 0) baseval = 0; double p = 1.0/(baseval*server.lfu_log_factor+1); if (r < p) counter++; return counter; }
复制代码
对应的概率分布计算公式为：
1/((counter-LFU_INIT_VAL)*server.lfu_log_factor+1)
复制代码
其中 LFU_INIT_VAL 为 5，我们看下概率分布图会有一个更直观的认识，以默认 server.lfu_log_factor=10 为例：
从上图可以看到，counter 越大，其增加的概率越小，8 bits 也足够记录很高的访问频率，下表是不同概率因子 server.lfu_log_factor 与访问频率 counter 的对应关系：
也就是说，默认 server.lfu_log_factor 为 10 的情况下，8 bits 的 counter 可以表示 1 百万的访问频率。
counter 的衰减因子
counter 增长函数 LFULogIncr 中我们可以看到，随着 key 的访问量增长，counter 最终都会收敛为 255，这就带来一个问题，如果 counter 只增长不衰减就无法区分热点 key。
为了解决这个问题，redis 提供了衰减因子 server.lfu_decay_time，其单位为分钟，计算方法也很简单，如果一个 key 长时间没有访问那么它的计数器 counter 就要减少，减少的值由衰减因子来控制：
unsigned long LFUDecrAndReturn(robj *o) { unsigned long ldt = o->lru >> 8; unsigned long counter = o->lru & 255; unsigned long 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。
概率因子和衰减因子均可配置，推荐使用 redis 的默认值即可：
lfu-log-factor 10lfu-decay-time 1
复制代码
热点 key 发现
介绍完 LFU 算法，接下来就是我们关心的热点 key 发现机制。
其核心就是在每次对 key 进行读写访问时，更新 LFU 的 24 bits 域代表的访问时间和 counter，这样每个 key 就可以获得正确的 LFU 值：
void updateLFU(robj *val) { unsigned long counter = LFUDecrAndReturn(val); counter = LFULogIncr(counter); val->lru = (LFUGetTimeInMinutes()<<8) | counter;}
复制代码
那么用户如何获取访问频率呢？redis 提供了 OBJECT FREQ 子命令来获取 LFU 信息，但是要注意需要先把内存逐出策略设置为 allkeys-lfu 或者 volatile-lfu，否则会返回错误：
127.0.0.1:6379> config get maxmemory-policy1) "maxmemory-policy"2) "noeviction"127.0.0.1:6379> object freq counter:000000006889(error) ERR An LFU maxmemory policy is not selected, access frequency not tracked. Please note that when switching between policies at runtime LRU and LFU data will take some time to adjust.
127.0.0.1:6379> config set maxmemory-policy allkeys-lfuOK127.0.0.1:6379> object freq counter:000000006889(integer) 3
复制代码
底层算法：使用 scan 命令遍历所有 key，再通过 OBJECT FREQ 获取访问频率并排序，即可得到热点 key。
redis 4.0.3 同时也提供了 redis-cli 的热点 key 发现功能，执行 redis-cli 时加上--hotkeys 选项即可，示例如下：
$./redis-cli --hotkeys
# Scanning the entire keyspace to find hot keys as well as# average sizes per key type. You can use -i 0.1 to sleep 0.1 sec# per 100 SCAN commands (not usually needed).
[00.00%] Hot key 'counter:000000000002' found so far with counter 87[00.00%] Hot key 'key:000000000001' found so far with counter 254[00.00%] Hot key 'mylist' found so far with counter 107[00.00%] Hot key 'key:000000000000' found so far with counter 254[45.45%] Hot key 'counter:000000000001' found so far with counter 87[45.45%] Hot key 'key:000000000002' found so far with counter 254[45.45%] Hot key 'myset' found so far with counter 64[45.45%] Hot key 'counter:000000000000' found so far with counter 93
-------- summary -------
Sampled 22 keys in the keyspace!hot key found with counter: 254 keyname: key:000000000001hot key found with counter: 254 keyname: key:000000000000hot key found with counter: 254 keyname: key:000000000002hot key found with counter: 107 keyname: mylisthot key found with counter: 93 keyname: counter:000000000000hot key found with counter: 87 keyname: counter:000000000002hot key found with counter: 87 keyname: counter:000000000001hot key found with counter: 64 keyname: myset
复制代码
可以看到，排在前几位的即是热点 key。
Scan 操作的介绍
熟悉 Redis 的人都知道，它是单线程的。因此在使用一些时间复杂度为 O(N)的命令时要非常谨慎。可能一不小心就会阻塞进程，导致 Redis 出现卡顿。
有时，我们需要针对符合条件的一部分命令进行操作，比如删除以 test_开头的 key。那么怎么获取到这些 key 呢？在 Redis2.8 版本之前，我们可以使用 keys 命令按照正则匹配得到我们需要的 key。但是这个命令有两个缺点：
没有 limit，我们只能一次性获取所有符合条件的 key，如果结果有上百万条，那么等待你的就是“无穷无尽”的字符串输出。
keys 命令是遍历算法，时间复杂度是 O(N)。如我们刚才所说，这个命令非常容易导致 Redis 服务卡顿。因此，我们要尽量避免在生产环境使用该命令。
在满足需求和存在造成 Redis 卡顿之间究竟要如何选择呢？面对这个两难的抉择，Redis 在 2.8 版本给我们提供了解决办法——scan 命令。
Scan 操作的优势
相比于 keys 命令，scan 命令有两个比较明显的优势：
这两个优势就帮助我们解决了上面的难题，不过 scan 命令也并不是完美的，它返回的结果有可能重复，因此需要客户端去重。scan 命令
总结有下面几个特征：
返回的结果可能会有重复，需要客户端去重复，这点非常重要;
遍历的过程中如果有数据修改，改动后的数据能不能遍历到是不确定的;
单次返回的结果是空的并不意味着遍历结束，而要看返回的游标值是否为零;
scan 命令使用示例
// 第一个参数指定游标，第二个参数指定匹配模式，第三个参数指定返回数据的条数// 注意: count 参数是限定服务器单次遍历的字典槽位数量，而不是限制返回 key 的数量
127.0.0.1:6379> scan 0 match key99* count 10001) "13976"2) 1) "key9911" 2) "key9974" 3) "key9994" 4) "key9910" 5) "key9907" 6) "key9989" 7) "key9971" 8) "key99" 9) "key9966" 10) "key992" 11) "key9903" 12) "key9905"127.0.0.1:6379> scan 13976 match key99* count 10001) "1996"2) 1) "key9982" 2) "key9997" 3) "key9963" 4) "key996" 5) "key9912" 6) "key9999" 7) "key9921" 8) "key994" 9) "key9956" 10) "key9919"127.0.0.1:6379> scan 1996 match key99* count 10001) "12594"2) 1) "key9939" 2) "key9941" 3) "key9967" 4) "key9938" 5) "key9906" 6) "key999" 7) "key9909" 8) "key9933" 9) "key9992"......127.0.0.1:6379> scan 11687 match key99* count 10001) "0"2) 1) "key9969" 2) "key998" 3) "key9986" 4) "key9968" 5) "key9965" 6) "key9990" 7) "key9915" 8) "key9928" 9) "key9908" 10) "key9929" 11) "key9944"...
复制代码
主要从底层的结构和源码的角度来讨论 scan 是如何工作的。
Redis 的结构
Redis 使用了 Hash 表作为底层实现，原因不外乎高效且实现简单。说到 Hash 表，很多 Java 程序员第一反应就是 HashMap。没错，Redis 底层 key 的存储结构就是类似于 HashMap 那样数组+链表的结构。其中第一维的数组大小为 2n(n>=0)。每次扩容数组长度扩大一倍。
scan 命令就是对这个一维数组进行遍历。每次返回的游标值也都是这个数组的索引。limit 参数表示遍历多少个数组的元素，将这些元素下挂接的符合条件的结果都返回。因为每个元素下挂接的链表大小不同，所以每次返回的结果数量也就不同。
SCAN 的遍历顺序
关于 scan 命令的遍历顺序，我们可以用一个小栗子来具体看一下。
127.0.0.1:6379> keys *1) "db_number"2) "key1"3) "myKey"127.0.0.1:6379> scan 0 MATCH * COUNT 11) "2"2) 1) "db_number"127.0.0.1:6379> scan 2 MATCH * COUNT 11) "1"2) 1) "myKey"127.0.0.1:6379> scan 1 MATCH * COUNT 11) "3"2) 1) "key1"127.0.0.1:6379> scan 3 MATCH * COUNT 11) "0"2) (empty list or set)
复制代码
我们的 Redis 中有 3 个 key，我们每次只遍历一个一维数组中的元素。如上所示，SCAN 命令的遍历顺序是
这个顺序看起来有些奇怪。我们把它转换成二进制就好理解一些了。
00->10->01->11
我们发现每次这个序列是高位加 1 的。普通二进制的加法，是从右往左相加、进位。而这个序列是从左往右相加、进位的。这一点我们在 redis 的源码中也得到印证。
在 dict.c 文件的 dictScan 函数中对游标进行了如下处理
v = rev(v);v++;v = rev(v);
复制代码
意思是，将游标倒置，加一后，再倒置，也就是我们所说的“高位加 1”的操作。
这里大家可能会有疑问了，为什么要使用这样的顺序进行遍历，而不是用正常的 0、1、2……这样的顺序呢，这是因为需要考虑遍历时发生字典扩容与缩容的情况（不得不佩服开发者考虑问题的全面性）。
我们来看一下在 SCAN 遍历过程中，发生扩容时，遍历会如何进行。加入我们原始的数组有 4 个元素，也就是索引有两位，这时需要把它扩充成 3 位，并进行 rehash。
原来挂接在 xx 下的所有元素被分配到 0xx 和 1xx 下。在上图中，当我们即将遍历 10 时，dict 进行了 rehash，这时，scan 命令会从 010 开始遍历，而 000 和 100（原 00 下挂接的元素）不会再被重复遍历。
再来看看缩容的情况。假设 dict 从 3 位缩容到 2 位，当即将遍历 110 时，dict 发生了缩容，这时 scan 会遍历 10。这时 010 下挂接的元素会被重复遍历，但 010 之前的元素都不会被重复遍历了。所以，缩容时还是可能会有些重复元素出现的。
Redis 的 rehash
rehash 是一个比较复杂的过程，为了不阻塞 Redis 的进程，它采用了一种渐进式的 rehash 的机制。
/* 字典 */typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 // 当 rehash 不在进行时，值为 -1 int rehashidx; /* rehashing not in progress if rehashidx == -1 */ // 目前正在运行的安全迭代器的数量 int iterators; /* number of iterators currently running */} dict;
复制代码
在 Redis 的字典结构中，有两个 hash 表，一个新表，一个旧表。在 rehash 的过程中，redis 将旧表中的元素逐步迁移到新表中，接下来我们看一下 dict 的 rehash 操作的源码。
/* Performs N steps of incremental rehashing. Returns 1 if there are still * keys to move from the old to the new hash table, otherwise 0 is returned. * * Note that a rehashing step consists in moving a bucket (that may have more * than one key as we use chaining) from the old to the new hash table, however * since part of the hash table may be composed of empty spaces, it is not * guaranteed that this function will rehash even a single bucket, since it * will visit at max N*10 empty buckets in total, otherwise the amount of * work it does would be unbound and the function may block for a long time. */int dictRehash(dict *d, int n) { int empty_visits = n*10; /* Max number of empty buckets to visit. */ if (!dictIsRehashing(d)) return 0;
while(n-- && d->ht[0].used != 0) { dictEntry *de, *nextde;
/* Note that rehashidx can't overflow as we are sure there are more * elements because ht[0].used != 0 */ assert(d->ht[0].size > (unsigned long)d->rehashidx); while(d->ht[0].table[d->rehashidx] == NULL) { d->rehashidx++; if (--empty_visits == 0) return 1; } de = d->ht[0].table[d->rehashidx]; /* Move all the keys in this bucket from the old to the new hash HT */ while(de) { uint64_t h;
nextde = de->next; /* Get the index in the new hash table */ h = dictHashKey(d, de->key) & d->ht[1].sizemask; de->next = d->ht[1].table[h]; d->ht[1].table[h] = de; d->ht[0].used--; d->ht[1].used++; de = nextde; } d->ht[0].table[d->rehashidx] = NULL; d->rehashidx++; }
/* Check if we already rehashed the whole table... */ if (d->ht[0].used == 0) { zfree(d->ht[0].table); d->ht[0] = d->ht[1]; _dictReset(&d->ht[1]); d->rehashidx = -1; return 0; }
/* More to rehash... */ return 1;}
复制代码
通过注释我们就能了解到，rehash 的过程是以 bucket 为基本单位进行迁移的。所谓的 bucket 其实就是我们前面所提到的一维数组的元素。每次迁移一个列表。
首先判断一下是否在进行 rehash，如果是，则继续进行；否则直接返回。
接着就是分 n 步开始进行渐进式 rehash。同时还判断是否还有剩余元素，以保证安全性。
在进行 rehash 之前，首先判断要迁移的 bucket 是否越界。
然后跳过空的 bucket，这里有一个 empty_visits 变量，表示最大可访问的空 bucket 的数量，这一变量主要是为了保证不过多的阻塞 Redis。
接下来就是元素的迁移，将当前 bucket 的全部元素进行 rehash，并且更新两张表中元素的数量。
每次迁移完一个 bucket，需要将旧表中的 bucket 指向 NULL。
最后判断一下是否全部迁移完成，如果是，则收回空间，重置 rehash 索引，否则告诉调用方，仍有数据未迁移。
由于 Redis 使用的是渐进式 rehash 机制，因此，scan 命令在需要同时扫描新表和旧表，将结果返回客户端。
评论