LevelDB LRUCache浅谈

LRUCache

LruCache算法就是Least Recently Used，也就是最近最少使用算法。即事先申请一块内存，将数据按照访问顺序进行存储。

一般需要两种结构，一个链表用于存储数据，并表示数据的先后顺序，另外一个结构为hash表，用于找到对应的链表节点。

levelDB LRUCache结构

在levelDB中，对LRUCache的实现做了优化，其优化目标，就是为了在多线程使用中，提高访问LRUCache的速度。

上图所示是LRUCache的结构示意图，在lru_双向链表中，lru_.prev所指向的节点是最新的节点。其中：

_list 数组中维护n个队列，输入的key会hash到不同的队列中；

in_use_ 双向链表，表示正在被线程使用的节点；该链表是无序的；

lru_ 双向链表，表示只被cache使用的节点；该链表是有序的；

那么为什么在LevelDB中要维护两个双向链表呢？ 因为在cache达到上线时，lru_中存储的是线程未使用的节点，所以从后向前清理lru_链表即可。

LevelDB 中最小结构–LRUHandle

struct LRUHandle {
  void* value;
  void (*deleter)(const Slice&, void* value);
  LRUHandle* next_hash;
  LRUHandle* next;
  LRUHandle* prev;
  // 需要的字节大小
  size_t charge;  // TODO(opt): Only allow uint32_t?
  size_t key_length;
  bool in_cache;     // Whether entry is in the cache.
  // 有多少线程正在使用该节点
  uint32_t refs;     // References, including cache reference, if present.
  // 多个LRUCache，hash是key 基于 Hash函数 得到。通过hash的前四位，判断该key放在哪个LRUCache中。
  uint32_t hash;     // Hash of key(); used for fast sharding and comparisons
  char key_data[1];  // Beginning of key

  Slice key() const {
    // next_ is only equal to this if the LRU handle is the list head of an
    // empty list. List heads never have meaningful keys.
    assert(next != this);

    return Slice(key_data, key_length);
  }
};

每个LURHandle中存储着key-value对信息；

// A single shard of sharded cache.
class LRUCache {
 public:
  LRUCache();
  ~LRUCache();

  // Separate from constructor so caller can easily make an array of LRUCache
  void SetCapacity(size_t capacity) { capacity_ = capacity; }

  // Like Cache methods, but with an extra "hash" parameter.
  Cache::Handle* Insert(const Slice& key, uint32_t hash, void* value, size_t charge, void (*deleter)(const Slice& key, void* value));
  Cache::Handle* Lookup(const Slice& key, uint32_t hash);
  void Release(Cache::Handle* handle);
  void Erase(const Slice& key, uint32_t hash);
  void Prune();
  size_t TotalCharge() const {
    MutexLock l(&mutex_);
    return usage_;
  }

 private:
  // 辅助函数：将链节 e 从当前的双向链表中摘除
  void LRU_Remove(LRUHandle* e);
  // 辅助函数：将链节 e 追加到链表头
  void LRU_Append(LRUHandle* list, LRUHandle* e);
  // 辅助函数：判断是否需要将 e 移动到 in_use_ 链表中，并增加 e 的引用计数
  void Ref(LRUHandle* e);
  // 辅助函数：减少 e 的引用计数. 当引用计数为0，销毁 e;当引用计数为1，将 e 移动到 lru_链表
  void Unref(LRUHandle* e);
  bool FinishErase(LRUHandle* e) EXCLUSIVE_LOCKS_REQUIRED(mutex_);

  // Initialized before use. 有多少节点供key-value对使用
  size_t capacity_;
  // 当前已有key-value已经使用了多少字节
  size_t usage_ GUARDED_BY(mutex_);
  
  // mutex_ protects the following state.
  mutable port::Mutex mutex_;

  // lru 双向链表的空表头
  // lru.prev 指向最新的条目，lru.next 指向最老的条目
  // 此链表中所有条目都满足 refs==1 和 in_cache==true
  // 表示所有条目只被缓存引用，而没有客户端在使用
  LRUHandle lru_ GUARDED_BY(mutex_);

  // in-use 双向链表的空表头，节点间没有顺序
  // 保存所有仍然被客户端引用的条目
  // 由于在被客户端引用的同时还被缓存引用，
  // 肯定有 refs >= 2 和 in_cache==true
  LRUHandle in_use_ GUARDED_BY(mutex_);

  HandleTable table_ GUARDED_BY(mutex_);
};

从代码实现中可以看出LRUCache类中维护一个锁成员对象，对LRUCache的所有操作，都会进行加锁和解锁操作，那么在多线程操作的情况下，就会增加很多耗时。

levelDB的对其优化方式为，维护多个LRUCache结构，通过Hash算法，将key均匀分布在不同的LRUCache中，这样多个线程不一定会同时操作同一个Cache，从而达到减少锁等待的发生。

LevelDB中 LRUCache实现的优点

1. 多分片LRUCache机制，避免密集上锁&解锁操作，提高多线程操作LRUCache的效率。
2. 将cache中的节点分为两个双向链表（一个存储使用中节点 in_use_，一个存储未使用节点 lru_），提高存取速度。链表in_use_无需保证节点的先后顺序