前言
業務中存在通路熱點是在所難免的，redis也會遇到這個問題，然而如何發現熱點key一直困擾着許多使用者，redis4.0為我們帶來了許多新特性，其中便包括基于LFU的熱點key發現機制。
Least Frequently Used
Least Frequently Used——簡稱LFU，意為最不經常使用，是redis4.0新增的一類記憶體逐出政策，關于記憶體逐出可以參考文章
《Redis資料過期和淘汰政策詳解》。
從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時，其被分為兩部分：
- 高16位用來記錄通路時間（機關為分鐘）
- 低8位用來記錄通路頻率，簡稱counter
16 bits 8 bits
+------------------+--------+
+ Last access time | LOG_C |
+------------------+--------+
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的對應關系：
# +--------+------------+------------+------------+------------+------------+
# | 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 |
# +--------+------------+------------+------------+------------+------------+
也就是說，預設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 10
lfu-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-policy
1) "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-lfu
OK
127.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:000000000001
hot key found with counter: 254 keyname: key:000000000000
hot key found with counter: 254 keyname: key:000000000002
hot key found with counter: 107 keyname: mylist
hot key found with counter: 93 keyname: counter:000000000000
hot key found with counter: 87 keyname: counter:000000000002
hot key found with counter: 87 keyname: counter:000000000001
hot key found with counter: 64 keyname: myset
可以看到，排在前幾位的即是熱點key。
結束
基于4.0的雲redis已正式上線，登陸阿裡雲控制台即可開通：
https://www.aliyun.com/product/kvstore![Redis簡介一(單機版)發展曆程Redis[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)