RocksDB LRUCache

目錄

LRUHandle

LRUCache

LRUCacheShard

關于LRUCacheShard不同優先級連結清單的實作

整體說來，rocksdb對于LRUCache的實作還是比較簡單的，和我們平時見到的LRUCache基本一緻，核心資料結構包括一個hashtable，用于存放cache所管理的資料，另一個資料結構為一個由雙向循環連結清單實作的LRUList, 用于提供LRU語義。除了LRUCache以外，rocksdb還提供了另外幾種Cache實作，LRUCache在rocksdb的Cache繼承體系如下所示：

LRUHandle

LRUHandle是LRUCache存儲的最基本元素。該對象用于封裝上層調用者傳來的value和key，另外需要注意的是被LRUCache管理的資料都應該在堆上配置設定。LRUHandle的關鍵資料如下:

struct LRUHandle {
  /* 實際的value */
  void* value;
  /* 析構函數 */
  void (*deleter)(const Slice&, void* value);
  /* 用于hashtable，拉鍊法的下一個元素 */
  LRUHandle* next_hash;
  /* 用于LRU連結清單 */
  LRUHandle* next;
  LRUHandle* prev;
  size_t charge;
  size_t key_length;
  uint32_t refs;     // a number of refs to this entry
                     // cache itself is counted as 1

  /*
   * 記錄了該Handle是否在cache中。
   * 該Handle是否為高優先級Handle，由調用者插資料時指定。
   * 是否位于高優先級隊列中，如果該handle為高優先級Handle，則會将其插入LRU連結清單。
   */
  char flags;

  uint32_t hash;     // Hash of key(); used for fast sharding and comparisons

  /* 真正的key資料： key_data[0] -- key_data(key_length) */
  char key_data[1];  // Beginning of key
}
           

LRUHandle共有三種狀态：

• 被外部引用并且在LRUCache的hashtable中, 需要注意的是如果一個Handle被外部引用，那麼rocksdb就不會将該元素放在LRU連結清單中。此時Handle的引用計數應該大于1，并且in_cache == true。
• 沒有被外部引用，此時該Handle會被LRU連結清單管理，在記憶體不足時可以釋放掉。此時Handle的引用計數等于1，并且in_cache == true。
• 被外部引用，但是不在cache中，此時Handle的引用計數大于0，并且in_cache == false。

狀态轉換流程如下:

• 當想LRUCache中插入Handle時，此時Handle的狀态為state1
• 在state1的基礎上，對一個Handle執行Release操作，該Handle的狀态将為state2
• 在state1的基礎上，對一個Handle執行Erase操作，該Handle的狀态将為state3
• 在state2的基礎上，如果caller查到到一個Handle，此時狀态将為state1

另外需要注意的是，對于rocksdb的LRUCache的實作，Handle在hashtable中不一定在LRU連結清單中，但是Handle在LRU連結清單中，一定在hashtable中。

LRUCache

整體上管理LRUCache的類。為了減少鎖沖突，rockdb将一個LRUCache分割成一系列小的LRUCache分片，每一個LRUCache分片用LRUCacheShard對象表示。是以LRUCache類擁有一個LRUCacheShared清單。整體說來LRUCache并沒有對于LRU-Cache管理的核心邏輯，類接口都是一些輔助函數，其類定義如下：

class LRUCache : public ShardedCache {
 public:
  // 構造函數會根據num_shard_bits建立一系列LRUCacheShard對象
  LRUCache(size_t capacity, int num_shard_bits, bool strict_capacity_limit,
           double high_pri_pool_ratio);
  virtual ~LRUCache();
  virtual const char* Name() const override { return "LRUCache"; }
  virtual CacheShard* GetShard(int shard) override;
  virtual const CacheShard* GetShard(int shard) const override;
  virtual void* Value(Handle* handle) override;
  virtual size_t GetCharge(Handle* handle) const override;
  virtual uint32_t GetHash(Handle* handle) const override;
  virtual void DisownData() override;

 private:
  LRUCacheShard* shards_;
};
           

LRUCacheShard

LRUCacheShard代表一個LRU-Cache的分片，該類實作了LRU-Cache的核心語義。首先需要确定一點，LRUCacheShard管理的所有資料都被存放在了一個hashtable中，該類為LRUHandleTable。LRUHandleTable是rocksdb自己實作的hashtable類，其提供的語義與常見的hashtable的語義相同，但是該類具有比系統類庫更好的性能。另外，LRUCacheShard還持有一個雙向循環連結清單，用于實作LRU語義。

一般來說，如果一個資料空間加入到LRUCache後，該資料空間不但被hashtable引用，還會被LRU連結清單引用。但是rocksdb實作的LRUCache語義與常見的LRUCache有一點不同:

• hashtable持有LRUCache所有的資料
• 當一個Handle不被外部引用時，它會被LRU連結清單引用，表示可回收
• 當cache的記憶體不足時，先回收LRU連結清單引用資料的記憶體

下面一張圖展示了hashtable管理的記憶體和LRU連結清單管理的記憶體之間的關系：

LRUCacheShard關鍵類成員如下：

class LRUCacheShard : public CacheShard {
 public:
  LRUCacheShard();
  virtual ~LRUCacheShard();
  
  /* 向LRUCache中插入資料 */
  virtual Status Insert(const Slice& key, uint32_t hash, void* value,
                        size_t charge,
                        void (*deleter)(const Slice& key, void* value),
                        Cache::Handle** handle,
                        Cache::Priority priority) override;
  /* 從LRUCache中查找資料 */                      
  virtual Cache::Handle* Lookup(const Slice& key, uint32_t hash) override;
  /* 解引用一個Handle，視根據記憶體的使用情況和Handle的引用計數而定，該Handle不一定會被在cache中抹除 */
  virtual bool Release(Cache::Handle* handle,
                       bool force_erase = false) override;
  /* 從LRUCache中抹除 */
  virtual void Erase(const Slice& key, uint32_t hash) override;

 private:
  void LRU_Remove(LRUHandle* e);
  void LRU_Insert(LRUHandle* e);
  /* 當高優先級連結清單引用的資料超過一個門檻值時，将高優先級連結清單引用的資料，調整到低優先級連結清單上 */
  void MaintainPoolSize();

  void EvictFromLRU(size_t charge, autovector<LRUHandle*>* deleted);

  /*
   * LRUCahche管理的記憶體上限。
   * 以下幾個關于LRUCache的記憶體相關的資料名額，都僅僅隻包括caller傳入的charge，
   * 不包括LRUCache自身資料結構占用的記憶體
   */
  size_t capacity_; 

  /* 所有駐留在hashtable中的元素所占的記憶體大小 */
  size_t usage_; 

   /* LRUList管理的記憶體大小 */
  size_t lru_usage_;

  /* 高優先級LRU連結清單管理的記憶體大小 */
  size_t high_pri_pool_usage_;

  /* 開啟嚴格模式後，記憶體超限，則報錯 */
  bool strict_capacity_limit_;

  /* 高優先級LRU連結清單能夠管理的記憶體最大大小 */
  double high_pri_pool_capacity_;

  mutable port::Mutex mutex_;

  /* Dummy head of LRU list. */
  LRUHandle lru_;

  /* 低優先連結清單的連結清單頭 */
  LRUHandle* lru_low_pri_;

  LRUHandleTable table_;
};
           

關于LRUCacheShard不同優先級連結清單的實作

上文中提到過，rocksdb的LRUCache是通過一個雙向循環連結清單來實作LRU語義的，該循環連結清單有一個dummy的連結清單頭lru_，連結清單的元素為LRUHandle，LRUHandle為LRUCache管理的最基本的元素，該對象用于封裝上層調用者傳來的value和key。

LRUCache有一個成員變量lru_low_pri_，用于指向低優先級的隊列頭。初始時LRU隊列為空，每次有新元素插入時，對于高優先級元素會将其插入隊列尾部，對于低優先級元素會将其插入低優先級隊列的頭部。比如，我們先插兩個低優先級的元素，再插兩個高優先級的元素，LRU連結清單的結構應該是這樣的：

接着再次插入一個低優先級的元素：

如果LRU隊列設定的高優先級的連結清單長度最多為2，那麼我們再次插入一個高優先級元素後：