关于本文

leveldb在include/leveldb/cache.h和util/cache.cc中实现了一个LRU缓存，用到的一个重要的数据结构是哈希表。作者并没有使用g++自带的hashtable，而是出于性能和用途考虑自行实现。整个实现不算注释一共只有80行左右，代码风格非常漂亮，本文将详细分析这部分代码。

接口

实现一共分为两个数据结构：

• LRUHandle：表中的键值对，即entry；
• HandleTable：由entry组成的哈希表；

先看LRUHandle，有一些成员变量是用于构造LRUCache的，这里只给出与哈希表有关的部分：

// An entry is a variable length heap-allocated structure.  Entries
// are kept in a circular doubly linked list ordered by access time.
struct LRUHandle {
  void* value;
  LRUHandle* next_hash;
  size_t key_length;
  uint32_t hash;     // Hash of key(); used for fast sharding and comparisons
  char key_data[1];  // Beginning of key

  Slice key() const {
    return Slice(key_data, key_length);
  }
};

这些成员变量有：

• void* value：指向实际value的指针；
• LRUHandle* next_hash：用于构造冲突链，冲突链将在后文介绍；
• size_t key_length：key的长度；
• uint32_t hash：存储key的哈希值，避免重复计算；
• char key_data[1]：存储实际key数据。key_data声明为一个长度为1的char数组，但实际上LRUHandle在使用时会通过malloc动态调整长度，如LRUHandle* e = reinterpret_cast<LRUHandle*>(malloc(sizeof(LRUHandle) - 1 + key.size()))，这样一来实际上有key.size()长度的位置留给LRUHandle结构体最后一个成员，key_data能够存储整个key的数据；

key()方法将key封装成一个Slice类。Slice定义在include/leveldb/slice.h中，本身结构非常简单，由指向数据的指针和数据长度组成。Slice类还定义了很多工具方法，这里只展示哈希表中用到的部分：

class Slice {
 public:
  // Create an empty slice.
  Slice() : data_(""), size_(0) {}

  // Create a slice that refers to d[0,n-1].
  Slice(const char* d, size_t n) : data_(d), size_(n) {}

  // Intentionally copyable.
  Slice(const Slice&) = default;
  Slice& operator=(const Slice&) = default;

  // Return a pointer to the beginning of the referenced data
  const char* data() const { return data_; }

  // Return the length (in bytes) of the referenced data
  size_t size() const { return size_; }

 private:
  const char* data_;
  size_t size_;
};

inline bool operator==(const Slice& x, const Slice& y) {
  return ((x.size() == y.size()) &&
          (memcmp(x.data(), y.data(), x.size()) == 0));
}

inline bool operator!=(const Slice& x, const Slice& y) { return !(x == y); }
}

再来看整个HandleTable提供的接口：

// We provide our own simple hash table since it removes a whole bunch
// of porting hacks and is also faster than some of the built-in hash
// table implementations in some of the compiler/runtime combinations
// we have tested.  E.g., readrandom speeds up by ~5% over the g++
// 4.4.3's builtin hashtable.
class HandleTable {
 public:
  HandleTable() : length_(0), elems_(0), list_(nullptr) { Resize(); }
  ~HandleTable() { delete[] list_; }

  LRUHandle* Lookup(const Slice& key, uint32_t hash);

  LRUHandle* Insert(LRUHandle* h);

  LRUHandle* Remove(const Slice& key, uint32_t hash);

 private:
  // The table consists of an array of buckets where each bucket is
  // a linked list of cache entries that hash into the bucket.
  uint32_t length_;
  uint32_t elems_;
  LRUHandle** list_;

  // Return a pointer to slot that points to a cache entry that
  // matches key/hash.  If there is no such cache entry, return a
  // pointer to the trailing slot in the corresponding linked list.
  LRUHandle** FindPointer(const Slice& key, uint32_t hash);

  void Resize();
};

一共有3个成员变量：

• uint32_t length_：bucket的数量，bucket将在后文叙述；
• uint32_t elems_：存储的键值对的数量；
• LRUHandle** list_：存储键值对的表。类型LRUHandle**可以这样理解：后文会说明每个bucket实际上是一个LRUHandle的链表，以头地址即LRUHandle*类型表示，而整个list_是长度为length_的bucket的数组，因此是LRUHandle**类型；

提供了一些方法：

• Lookup()：根据key及其hash值，返回指向对应LRUHandle的指针；
• Insert()：插入指定LRUHandle，如果key已经存在则会覆盖；
• Remove()：根据key及其hash值，将对应LRUHandle从哈希表中删除；
• FindPointer()：根据key及其hash值，返回指向对应LRUHandle*的指针，注意这里有两个*；
• Resize()：扩容；

存储方式

哈希表常用的冲突处理方法有：开放定址、二次哈希、开链、公共溢出区，leveldb采用了开链法。
开链是将每组冲突的键值对构成一个链表，称为bucket，直译为桶。插入键值对时，根据哈希找到对应的桶链表，然后将键值对插入到链表中。显然随着元素数量的增加，桶的数量必须等比例增加才能维持O(1)查找复杂度，否则将退化为普通链表。其典型结构如图：

理解了这样的结构之后，就可以来研究leveldb的具体实现了。

实现

初始化

构造函数将所有参数设为0，然后调用Resize()，来看一下Resize()中的初始化部分：

  void Resize() {
    uint32_t new_length = 4;
    while (new_length < elems_) {
      new_length *= 2;
    }
    LRUHandle** new_list = new LRUHandle*[new_length];
    memset(new_list, 0, sizeof(new_list[0]) * new_length);
    // something not executed in initialization
    delete[] list_;
    list_ = new_list;
    length_ = new_length;
  }

初始length_设为4，建立了一个长度为length_的数组list_，数组元素是桶（链表）的地址。

FindPointer

最核心的函数，主体只有4行：

  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;
  }

首先根据哈希值，找到list_中对应bucket的位置。这个位置是哈希值模list_长度得到的结果，由于长度始终是2的幂，这里用按位与代替模计算提高性能。回忆前面说list_中的元素是bucket的地址，那么这一步过后ptr指向该元素/该地址，*ptr是bucket地址，**ptr是bucket中的首个LRUHandle。
现在我们找到了key对应的bucket链表，记这个链表的头地址（*ptr）是list_[i]，这个链表是通过LRUHandle中的next_hash链接的，于是我们顺着next_hash一路向下寻找一个包含完全相等的key的键值对，这里有两种情况：

• 这个bucket没有被任何其他键值对使用过，或者这个bucket的链表头的key满足要求，循环直接退出，ptr=&list_[i]；
• 在顺着next_hash寻找的过程中，找到了一个已有的完全相等的key，或者找到了链表尾依然没有找到，这个时候ptr指向找到的上一个节点的next_hash，这个next_hash中存储着满足要求的节点的地址（或nullptr）；

返回的ptr是一个二层指针，它指向满足要求的键值对的地址存储的位置，也就是说*ptr才是这个键值对的地址，**ptr才是这个键值对。这个地址存储的位置可能是list_[i]或前驱节点的next_hash。这和我们熟悉的在链表操作中使用一层指针不太一样，好处在于可以通过ptr直接修改next_hash，在后文中可以体会到这一点。
有了这个核心函数之后其他部分就比较简单了。

Lookup

  LRUHandle* Lookup(const Slice& key, uint32_t hash) {
    return *FindPointer(key, hash);
  }

单纯调用FindPointer，解一层指针得到我们熟悉的一层指针形式。

Insert

  LRUHandle* Insert(LRUHandle* h) {
    LRUHandle** ptr = FindPointer(h->key(), h->hash);
    LRUHandle* old = *ptr;
    h->next_hash = (old == nullptr ? nullptr : old->next_hash);
    *ptr = h;
    if (old == nullptr) {
      ++elems_;
      if (elems_ > length_) {
        // Since each cache entry is fairly large, we aim for a small
        // average linked list length (<= 1).
        Resize();
      }
    }
    return old;
  }

调用FindPointer找到目标位置，插入或替换LRUHandle。如果是插入了新节点而不是替换，则增加elems_，必要时扩容。这里就看到了FindPointer返回二层指针的好处：双向链表替换节点比较直观，但单向链表替换节点需要找到前驱节点，和找目标节点的逻辑存在差异从而不能使用同一个函数。FindPointer的结果指向前驱节点的next_hash，则兼顾了两种逻辑。

Remove

  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;
  }

调用FindPointer找到并移除目标节点，这里和Insert一样，借助FindPointer的二层指针设计，在单向链表中实现优雅的删除。

Resize

  void Resize() {
    uint32_t new_length = 4;
    while (new_length < elems_) {
      new_length *= 2;
    }
    LRUHandle** new_list = new LRUHandle*[new_length];
    memset(new_list, 0, sizeof(new_list[0]) * new_length);
    uint32_t count = 0;
    for (uint32_t i = 0; i < length_; i++) {
      LRUHandle* h = list_[i];
      while (h != nullptr) {
        LRUHandle* next = h->next_hash;
        uint32_t hash = h->hash;
        LRUHandle** ptr = &new_list[hash & (new_length - 1)];
        h->next_hash = *ptr;
        *ptr = h;
        h = next;
        count++;
      }
    }
    assert(elems_ == count);
    delete[] list_;
    list_ = new_list;
    length_ = new_length;
  }

length_每次倍增以维持2的幂，然后将旧list_中的所有键值对迁移到新list_中，这里注意到以下几点：

• 必须遍历所有键值对，而不能一次迁移整个list_。因为length_变化，hash&(length_-1)也可能变化，在新list_中对应的桶编号可能改变。
• 接上一条。原来同链的键值对可能变得不同链，但原来不同链的键值对不可能变得同链，因为length_是以2的幂倍增的。
• 出于性能考虑，在旧链中从头遍历，在新链中头插。因此如果两个同链键值对迁移后依然同链，它们的前后顺序会被颠倒。