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就要减少，减少的值由衰减因子来控制