天天看點

RocksDB LRUCache

目錄

LRUHandle

LRUCache

LRUCacheShard

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

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

RocksDB LRUCache

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連結清單管理的記憶體之間的關系:

RocksDB LRUCache

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連結清單的結構應該是這樣的:

RocksDB LRUCache

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

RocksDB LRUCache

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

RocksDB LRUCache