Redis 對過期數(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機制刪除的話刪除的順序應該是C->A->B->D 其實這并不是我們想要的，因為B被訪問的頻率是最高的，而D被訪問的頻率比較低，所以我們更想讓B保留，把D刪除，所以我們接下來看另一種策略 LFU

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

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

Redis使用redisObject中的24bit lru字段來存儲lfu字段， 這24bit被分為兩部分：

1:高16位用來記錄訪問時間(單位為分鐘) 

2:低8位用來記錄訪問頻率，簡稱counter

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

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

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