Redis的LRU算法文章描述了LRU存在以下缺陷。
~~~~~~~ a~~~~~~~~~~~~~~~~~~ a~~ |
~~b~~ b~~ B~~ B~~ B~~ B~~ B~~ B~~ B~~ B~~ B~~ |
~~~~~~~~~~~~~~~~~~c~~~~~|
~~~~~~d~~~~~~~~~~~~~~~~ d |
将数据d误认为是将来最有可能被访问的数据。
Redis作者试图改进LRU算法，但Redis的LRU算法受制于随机采样数maxmemory_samples，在maxmemory_samples等于10的情况下是理想的LRU算法也就是说，LRU算法本身变得更加困难。
因此，将思路回归原点，淘汰算法的本意是保存将来最有可能被访问的数据，而LRU算法只是预测最近被访问的数据将来最有可能被访问的数据。 我们可以改变想法，采用最近最大似然(lfu )算法。 这意味着，最频繁访问的数据将来最有可能被访问。 在上述情况下，可以根据访问频率决定预约的优先级。 BAC=D。
Redis中LFU的思考
LFU算法可以为每个key维护一个计数器。 每次访问key时，计数器都会增大。 计数器越大，访问就越频繁，这几乎是一样的。
上述简单算法有两个问题。
LRU算法维护双向链表，可以方便地将被访问的节点移动到链表的开头，但LFU无法做到。 节点按计数器严格排序，添加节点或更新节点位置时，时间复杂度可能会达到o(n )。
只是简单地增加计数器的方法并不完美。 访问模式频繁变化。 在一段时间内频繁访问的key在一段时间后可能很少被访问。 仅仅增加计数器并不能显示出这一趋势。
第一个问题得到很好的解决，可以借鉴LRU实现的经验，维持废除key的pool。 第二个问题的解决方案是记录key上次访问的时间，然后随着时间的推移计数器下降。
Redis对象的结构如下：
typedef struct redisObject { (
无符号类型：4；
未编码：4；
unsigned lru:LRU_BITS；/* lr utime (relativetogloballru _ clock ) or
* lf udata (least significant8bits frequency
* andmostsignificant 16 bits access time (.* /
int refcount；
void *ptr；
} robj；
在LRU算法中，24位的LRU用于记录LRU时间，LFU也可以使用此字段，但分为16位和8位使用。
16位8位
----------------
Last decr time | LOG_C |
----------------
高度16 bits用于记录最近计数器下降的时间ldt。 单位为分钟，低8 bits记录计数器值counter。
配置LFU
从Redis4.0开始，maxmemory_policy的销毁策略中添加了两个LFU模式。
volatile-LFU :对有有效期的key采用lfu丢弃算法
allkeys-LFU :对所有key采用lfu淘汰算法
有两种配置可以调整LFU算法。
lfu-log-factor 10
lfu-decay-time 1
lfu-log-factor可以调整计数器counter的生长速度，lfu-log-factor越大，计数器的生长速度越慢。
lfu-decay-time是以分钟为单位的数值，可以调整柜台的减少速度
源代码实现
robj*lookupkey(redisdb*db，robj *key，int flags ) )
DICTentry*de=DICTfind(DB-DICT，key-ptr )；
if(de ) (
robj*val=dictgetval(de；
/* updatetheaccesstimefortheageingalgorithm。
* Don't do it if we have a saving child，as this will trigger
* a copy on write madness. */
if(server.RDB_child_PID==-1
se
rver.aof_child_pid == -1 &&!(flags & LOOKUP_NOTOUCH))
{
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
updateLFU(val);
} else {
val->lru = LRU_CLOCK();
}
}
return val;
} else {
return NULL;
}
}
当采用LFU策略时，updateLFU更新lru：
/* Update LFU when an object is accessed.
* Firstly, decrement the counter if the decrement time is reached.
* Then logarithmically increment the counter, and update the access time. */
void updateLFU(robj *val) {
unsigned long counter = LFUDecrAndReturn(val);
counter = LFULogIncr(counter);
val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}
降低LFUDecrAndReturn
首先，LFUDecrAndReturn对counter进行减少操作：
/* If the object decrement time is reached decrement the LFU counter but
* do not update LFU fields of the object, we update the access time
* and counter in an explicit way when the object is really accessed.
* And we will times halve the counter according to the times of
* elapsed time than server.lfu_decay_time.
* Return the object frequency counter.
*
* This function is used in order to scan the dataset for the best object
* to fit: as we check for the candidate, we incrementally decrement the
* counter of the scanned objects if needed. */
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;
}
函数首先取得高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. */
unsigned long LFUGetTimeInMinutes(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. */
unsigned long LFUTimeElapsed(unsigned long ldt) {
unsigned long now = LFUGetTimeInMinutes();
if (now >= ldt) return now-ldt;
return 65535-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。
增长LFULogIncr
增长函数LFULogIncr如下：
/* Logarithmically increment a counter. The greater is the current counter value
* the less likely is that it gets really implemented. Saturate it at 255. */
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;
}
counter并不是简单的访问一次就+1，而是采用了一个0-1之间的p因子控制增长。counter最大值为255。取一个0-1之间的随机数r与p比较，当r
+--------+------------+------------+------------+------------+------------+
| 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 |
+--------+------------+------------+------------+------------+------------+
可见counter增长与访问次数呈现对数增长的趋势，随着访问次数越来越大，counter增长的越来越慢。
新生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。
pool
pool算法就与LRU算法一致了：
if (server.maxmemory_policy & (MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_LFU) ||
server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL)
计算idle时有所不同：
} else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
/* When we use an LRU policy, we sort the keys by idle time
* so that we expire keys starting from greater idle time.
* However when the policy is an LFU one, we have a frequency
* estimation, and we want to evict keys with lower frequency
* first. So inside the pool we put objects using the inverted
* frequency subtracting the actual frequency to the maximum
* frequency of 255. */
idle = 255-LFUDecrAndReturn(o);
使用了255-LFUDecrAndReturn(o)当做排序的依据。
参考链接