RocksDB LRUCache

Catalog

LRUHandle

LRUCache

LRUCacheShard

About LRUCacheShard Implementation of linked lists with different priorities

On the whole ,rocksdb about LRUCache The implementation of is relatively simple , And what we usually see LRUCache Almost the same , The core data structure includes a hashtable, To hold cache Data managed , Another data structure is a two-way circular linked list LRUList, For providing LRU semantics . except LRUCache outside ,rocksdb There are also several other Cache Realization ,LRUCache stay rocksdb Of Cache The inheritance system is as follows ：

LRUHandle

LRUHandle yes LRUCache The most basic element of storage . This object is used to encapsulate value and key, Another thing to pay attention to is being LRUCache All managed data should be allocated on the heap .LRUHandle The key data of are as follows :

struct LRUHandle {
  /*  Actually value */
  void* value;
  /*  Destructor  */
  void (*deleter)(const Slice&, void* value);
  /*  be used for hashtable, The next element of zipper method  */
  LRUHandle* next_hash;
  /*  be used for LRU Linked list  */
  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

  /*
   *  Recorded the time to Handle Whether in cache in .
   *  The Handle Is it high priority Handle, Specified by the caller when inserting data .
   *  Whether it is in the high priority queue , If it's time to handle For high priority Handle, It will be inserted LRU Linked list .
   */
  char flags;

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

  /*  real key data ： key_data[0] -- key_data(key_length) */
  char key_data[1];  // Beginning of key
}

LRUHandle There are three states ：

• Externally referenced and in LRUCache Of hashtable in , It should be noted that if one Handle Externally referenced , that rocksdb This element will not be placed in LRU In the list . here Handle The reference count of should be greater than 1, also in_cache == true.
• Not externally referenced , At this point the Handle Will be LRU Linked list management , When the memory is insufficient, it can be released . here Handle The reference count of is equal to 1, also in_cache == true.
• Externally referenced , But not in cache in , here Handle The reference count of is greater than 0, also in_cache == false.

The state transition process is as follows :

• Think about it LRUCache Insert Handle when , here Handle The status of is state1
• stay state1 On the basis of , To a Handle perform Release operation , The Handle The status of will be state2
• stay state1 On the basis of , To a Handle perform Erase operation , The Handle The status of will be state3
• stay state2 On the basis of , If caller I found one Handle, At this time, the status will be state1

Another thing to note , about rocksdb Of LRUCache The implementation of the ,Handle stay hashtable It is not necessarily in LRU In the list , however Handle stay LRU In the list , It must be hashtable in .

LRUCache

Overall management LRUCache Class . To reduce lock conflicts ,rockdb Will a LRUCache Split into a series of small LRUCache Fragmentation , every last LRUCache For slicing LRUCacheShard Objects represent . therefore LRUCache Class has a LRUCacheShared list . On the whole LRUCache Not for LRU-Cache The core logic of management , Class interfaces are auxiliary functions , Its class is defined as follows ：

class LRUCache : public ShardedCache {
 public:
  //  The constructor will be based on num_shard_bits Create a series of LRUCacheShard object 
  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 Representing one LRU-Cache The fragmentation of , This class implements LRU-Cache The core semantics of . First of all, we need to make sure ,LRUCacheShard All the data managed is stored in one hashtable in , The class for LRUHandleTable.LRUHandleTable yes rocksdb Self realized hashtable class , It provides semantics similar to common hashtable The meaning of is the same , But this class has better performance than the system class library . in addition ,LRUCacheShard It also holds a two-way circular linked list , Used to implement LRU semantics .
Generally speaking , If a data space is added to LRUCache after , This data space is not only hashtable quote , Will be LRU Linked list references . however rocksdb Realized LRUCache Semantics and common LRUCache It's a little different :

• hashtable hold LRUCache All data
• When one Handle When not externally referenced , It will be LRU Linked list references , Indicates recyclable
• When cache When you run out of memory , Recycle first LRU Memory of linked list reference data

The following picture shows hashtable Managed memory and LRU The relationship between memory managed by linked list ：

LRUCacheShard Key class members are as follows ：

class LRUCacheShard : public CacheShard {
 public:
  LRUCacheShard();
  virtual ~LRUCacheShard();
  
  /*  towards LRUCache Insert data  */
  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;
  /*  from LRUCache Find data in  */                      
  virtual Cache::Handle* Lookup(const Slice& key, uint32_t hash) override;
  /*  Dereference a Handle, Depending on the memory usage and Handle Depends on the reference count , The Handle Will not necessarily be in cache Wipe out  */
  virtual bool Release(Cache::Handle* handle,
                       bool force_erase = false) override;
  /*  from LRUCache Wipe out  */
  virtual void Erase(const Slice& key, uint32_t hash) override;

 private:
  void LRU_Remove(LRUHandle* e);
  void LRU_Insert(LRUHandle* e);
  /*  When the data referenced by the high priority linked list exceeds a threshold , The data referenced by the high priority linked list , Adjust to the low priority linked list  */
  void MaintainPoolSize();

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

  /*
   * LRUCahche Maximum memory managed .
   *  The following are about LRUCache Memory related data indicators , It only includes caller Incoming charge,
   *  barring LRUCache Memory occupied by its own data structure 
   */
  size_t capacity_; 

  /*  All reside in hashtable The memory size occupied by the elements in  */
  size_t usage_; 

   /* LRUList Managed memory size  */
  size_t lru_usage_;

  /*  High priority LRU Memory size managed by linked list  */
  size_t high_pri_pool_usage_;

  /*  After starting strict mode , Memory overrun , False report  */
  bool strict_capacity_limit_;

  /*  High priority LRU The maximum memory size that the linked list can manage  */
  double high_pri_pool_capacity_;

  mutable port::Mutex mutex_;

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

  /*  The chain header of the low priority linked list  */
  LRUHandle* lru_low_pri_;

  LRUHandleTable table_;
};

About LRUCacheShard Implementation of linked lists with different priorities

As mentioned above ,rocksdb Of LRUCache It is realized through a two-way circular linked list LRU Semantic , The circular linked list has a dummy The chain head of lru_, The elements of the linked list are LRUHandle,LRUHandle by LRUCache The most basic element of management , This object is used to encapsulate value and key.
LRUCache There is a member variable lru_low_pri_, Used to point to low priority queue headers . At the beginning LRU The queue is empty , Every time a new element is inserted , For high priority elements, they will be inserted at the end of the queue , For low priority elements, they will be inserted into the head of the low priority queue . such as , Let's insert two low priority elements first , Insert two more high priority elements ,LRU The structure of the linked list should be like this ：

Then insert a low priority element again ：

If LRU The maximum length of the high priority linked list set by the queue is 2, Then we insert a high priority element again ：