漫谈 LevelDB 数据结构（三）：LRU 缓存（ LRUCache）

// 插入一个键值对（key，value）到缓存（cache）中，
// 并从缓存总容量中减去该键值对所占额度（charge） 
// 
// 返回指向该键值对的句柄（handle），调用者在用完句柄后，
// 需要调用 this->Release(handle) 进行释放
//
// 在键值对不再被使用时，键值对会被传入的 deleter 参数
// 释放
virtual Handle* Insert(const Slice& key, void* value, size_t charge,
                       void (*deleter)(const Slice& key, void* value)) = 0;

// 如果缓存中没有相应键（key），则返回 nullptr
//
// 否则返回指向对应键值对的句柄（Handle）。调用者用完句柄后，
// 要记得调用 this->Release(handle) 进行释放
virtual Handle* Lookup(const Slice& key) = 0;

// 释放 Insert/Lookup 函数返回的句柄
// 要求：该句柄没有被释放过，即不能多次释放
// 要求：该句柄必须是同一个实例返回的
virtual void Release(Handle* handle) = 0;

// 获取句柄中的值，类型为 void*（表示任意用户自定义类型）
// 要求：该句柄没有被释放
// 要求：该句柄必须由同一实例所返回
virtual void* Value(Handle* handle) = 0;

// 如果缓存中包含给定键所指向的条目，则删除之。
// 需要注意的是，只有在所有持有该条目句柄都释放时，该条目所占空间才会真正被释放
virtual void Erase(const Slice& key) = 0;

// 返回一个自增的数值 id。当一个缓存实例由多个客户端共享时，
// 为了避免多个客户端的键冲突，每个客户端可能想获取一个独有
// 的 id，并将其作为键的前缀。类似于给每个客户端一个单独的命名空间。
virtual uint64_t NewId() = 0;

// 驱逐全部没有被使用的数据条目
// 内存吃紧型的应用可能想利用此接口定期释放内存。
// 基类中的 Prune 默认实现为空，但强烈建议所有子类自行实现。
// 将来的版本可能会增加一个默认实现。
virtual void Prune() {}

// 返回当前缓存中所有数据条目所占容量总和的一个预估
virtual size_t TotalCharge() const = 0;

LRUHandle** ptr = &list_[hash & (length_ - 1)];

struct LRUHandle {
  void* value;
  void (*deleter)(const Slice&, void* value); // 释放 key,value 空间的用户回调
  LRUHandle* next_hash;  // 用于 hashtable 中链表处理冲突
  LRUHandle* next;       // 用于双向链表中维护 LRU 顺序
  LRUHandle* prev;
  size_t charge;     // TODO(opt): Only allow uint32_t?
  size_t key_length;
  bool in_cache;     // 该 handle 是否在 cache table 中
  uint32_t refs;     // 该 handle 被引用的次数
  uint32_t hash;     // key 的 hash 值，用于确定分片和快速比较
  char key_data[1];  // 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);
  }
};

LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
  LRUHandle** ptr = &list_[hash & (length_ - 1)];
  while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {
    ptr = &(*ptr)->next_hash;
  }
  return ptr;
}

LRUHandle* Remove(const Slice& key, uint32_t hash) {
  LRUHandle** ptr = FindPointer(key, hash);
  LRUHandle* result = *ptr;
  if (result != nullptr) {
    *ptr = result->next_hash;
    --elems_;
  }
  return result;
}

class LRUCache {
 public:
  LRUCache();
  ~LRUCache();

  // 从构造函数分离出此参数的设置方法，可以让调用者在使用时进行灵活的调整
  void SetCapacity(size_t capacity) { capacity_ = capacity; }

 private:
  // 辅助函数：将链节 e 从双向链表中摘除
  void LRU_Remove(LRUHandle* e);
  // 辅助函数：将链节 e 追加到链表头
  void LRU_Append(LRUHandle* list, LRUHandle* e);
  // 辅助函数：增加链节 e 的引用
  void Ref(LRUHandle* e);
  // 辅助函数：减少链节 e 的引用
  void Unref(LRUHandle* e);
  // 辅助函数：从缓存中删除单个链节 e
  bool FinishErase(LRUHandle* e) EXCLUSIVE_LOCKS_REQUIRED(mutex_);

  // 在使用 LRUCache 前必须先初始化此值
  size_t capacity_;

  // mutex_ 用以保证此后的字段的线程安全
  mutable port::Mutex mutex_;
  size_t usage_ GUARDED_BY(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_);
};

Cache::Handle* LRUCache::Insert(const Slice& key, uint32_t hash, void* value,
                                size_t charge,
                                void (*deleter)(const Slice& key,
                                                void* value)) {
  MutexLock l(&mutex_);

  // 构建数据条目句柄
  LRUHandle* e =
      reinterpret_cast<LRUHandle*>(malloc(sizeof(LRUHandle) - 1 + key.size()));
  e->value = value;
  e->deleter = deleter;
  e->charge = charge;
  e->key_length = key.size();
  e->hash = hash;
  e->in_cache = false;
  e->refs = 1;  // 客户端引用
  std::memcpy(e->key_data, key.data(), key.size());

  if (capacity_ > 0) {
    e->refs++;  // 缓存本身引用
    e->in_cache = true;
    LRU_Append(&in_use_, e);
    usage_ += charge;

    FinishErase(table_.Insert(e)); // 如果是替换，要删除原来数据
  } else {  // capacity_==0 时表示关闭缓存，不进行任何缓存
    // next 会在 key() 函数中被 assert 测试，因此要初始化一下
    e->next = nullptr;
  }

  // 当超数据条目超出容量时，根据 LRU 策略将不被客户端引用的数据条目驱逐出内存
  while (usage_ > capacity_ && lru_.next != &lru_) {
    LRUHandle* old = lru_.next;
    assert(old->refs == 1);
    bool erased = FinishErase(table_.Remove(old->key(), old->hash));
    if (!erased) {  // to avoid unused variable when compiled NDEBUG
      assert(erased);
    }
  }

  return reinterpret_cast<Cache::Handle*>(e);
}

static uint32_t Shard(uint32_t hash) { return hash >> (32 - kNumShardBits); }