Redis 對(duì)過(guò)期數(shù)據(jù)的處理方法

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機(jī)制刪除的話(huà)刪除的順序應(yīng)該是C->A->B->D 其實(shí)這并不是我們想要的，因?yàn)锽被訪問(wèn)的頻率是最高的，而D被訪問(wèn)的頻率比較低，所以我們更想讓B保留，把D刪除，所以我們接下來(lái)看另一種策略 LFU

**LFU（leastFrequently used 最不經(jīng)常使用）**

如果一個(gè)數(shù)據(jù)在最近一段時(shí)間內(nèi)很少被訪問(wèn)到，那么可以認(rèn)為在將來(lái)他被訪問(wèn)到的概率也很小。所以，當(dāng)空間滿(mǎn)時(shí)，最小頻率訪問(wèn)的數(shù)據(jù)最先被淘汰

Redis使用redisObject中的24bit lru字段來(lái)存儲(chǔ)lfu字段， 這24bit被分為兩部分：

1:高16位用來(lái)記錄訪問(wèn)時(shí)間(單位為分鐘) 

2:低8位用來(lái)記錄訪問(wèn)頻率，簡(jiǎn)稱(chēng)counter

 16 bits  8 bits
 
 +----------------+--------+
 
 Last decr time | LOG_C |

但是counter 8bit很容易就溢出了，技巧是用一個(gè)邏輯計(jì)數(shù)器，給予概率的對(duì)數(shù)計(jì)數(shù)器，而不是一個(gè)普通的遞增計(jì)數(shù)器
```
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;
}
```

對(duì)應(yīng)的概率分布計(jì)算公式為
```
1.0/((counter - LFU_INIT_VAL)*server.lfu_log_factor+1);
```
其中LFU_INIT_VAL為5，其實(shí)簡(jiǎn)單說(shuō)就是，越大的數(shù)，遞增的概率越低
嚴(yán)格按照LFU算法，時(shí)間越久的key，counter越有可能越大，被剔除的可能性就越小。counter只增長(zhǎng)不衰減就無(wú)法區(qū)分熱點(diǎn)key。為了解決這個(gè)問(wèn)題，redis提供了衰減因子server.lfu_decay_time,其單位為分鐘，計(jì)算方法也很簡(jiǎn)單，如果一個(gè)key長(zhǎng)時(shí)間沒(méi)有訪問(wèn)那么他的計(jì)數(shù)器counter就要減少，減少的值由衰減因子來(lái)控制