Redis 对过期数据的处理方法

robj *lookupKeyReadWithFlags(redisDb *db, robj *key, int flags) {
robj *val;

if (expireIfNeeded(db,key) == 1) {
/* Key expired. If we are in the context of a master, expireIfNeeded()
* returns 0 only when the key does not exist at all, so it’s safe
* to return NULL ASAP. */
if (server.masterhost == NULL) {
server.stat_keyspace_misses++;
notifyKeyspaceEvent(NOTIFY_KEY_MISS, “keymiss”, key, db->id);
return NULL;
}

/* However if we are in the context of a slave, expireIfNeeded() will
* not really try to expire the key, it only returns information
* about the “logical” status of the key: key expiring is up to the
* master in order to have a consistent view of master’s data set.
*
* However, if the command caller is not the master, and as additional
* safety measure, the command invoked is a read-only command, we can
* safely return NULL here, and provide a more consistent behavior
* to clients accessign expired values in a read-only fashion, that
* will say the key as non existing.
*
* Notably this covers GETs when slaves are used to scale reads. */
if (server.current_client &&
server.current_client != server.master &&
server.current_client->cmd &&
server.current_client->cmd->flags & CMD_READONLY)
{
server.stat_keyspace_misses++;
notifyKeyspaceEvent(NOTIFY_KEY_MISS, “keymiss”, key, db->id);
return NULL;
}
}
val = lookupKey(db,key,flags);
if (val == NULL) {
server.stat_keyspace_misses++;
notifyKeyspaceEvent(NOTIFY_KEY_MISS, “keymiss”, key, db->id);
}
else
server.stat_keyspace_hits++;
return val;
}

~~ B ~~ B ~~ B ~~ B ~~ B ~~ B ~~ B ~~ B ~~ B ~~ B ~~ B ~~ B〜|

~~~~~~~~~~ C ~~~~~~~~ C ~~~~~~~~~ C ~~~~~~ |

~~~~~ D ~~~~~~~~~ D ~~~~~~~ D ~~~~~~~~ D |

在上图中，按照LRU机制删除的话删除的顺序应该是C->A->B->D 其实这并不是我们想要的，因为B被访问的频率是最高的，而D被访问的频率比较低，所以我们更想让B保留，把D删除，所以我们接下来看另一种策略 LFU

**LFU（leastFrequently used 最不经常使用）**

如果一个数据在最近一段时间内很少被访问到，那么可以认为在将来他被访问到的概率也很小。所以，当空间满时，最小频率访问的数据最先被淘汰

Redis使用redisObject中的24bit lru字段来存储lfu字段， 这24bit被分为两部分：

1:高16位用来记录访问时间(单位为分钟)

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

16 bits 8 bits

+—————-+——–+

Last decr time | LOG_C |

但是counter 8bit很容易就溢出了，技巧是用一个逻辑计数器，给予概率的对数计数器，而不是一个普通的递增计数器
“`
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.0/((counter – LFU_INIT_VAL)*server.lfu_log_factor+1);
“`
其中LFU_INIT_VAL为5，其实简单说就是，越大的数，递增的概率越低
严格按照LFU算法，时间越久的key，counter越有可能越大，被剔除的可能性就越小。counter只增长不衰减就无法区分热点key。为了解决这个问题，redis提供了衰减因子server.lfu_decay_time,其单位为分钟，计算方法也很简单，如果一个key长时间没有访问那么他的计数器counter就要减少，减少的值由衰减因子来控制