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