leveldb中的哈希表

发布于 2022-04-11  405 次阅读


关于本文

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的幂倍增的。
  • 出于性能考虑,在旧链中从头遍历,在新链中头插。因此如果两个同链键值对迁移后依然同链,它们的前后顺序会被颠倒。

长安城里的一切已经结束,一切都在无可挽回地走向庸俗。