LSM-Tree - LevelDb之LRU缓存
引言
LRU缓存在各种开源组件中都有应用的场景，经常用于做冷热数据和淘汰策略，应用LRU次要有三点。
- 第一点是实现非常简单。
- 第二点是代码量自身也不错。
- 最初波及数据结构十分经典。
LevelDB对于LRU缓存实现算是比拟经典的案例，这一节来介绍它是如何应用LRU实现缓存的。
LeetCode 中有一道相应LRU缓存算法的题目，感兴趣能够做一做：
lru-cache
实践
依据wiki的LRU缓存构造介绍，能够理解到缓存的根本淘汰策略过程，比方上面这张图的节点淘汰过程：
读取的程序为 A B C D E D F，缓存大小为 4，括号内的数字示意排序，数字越小越靠后，示意 Least recently.
依据箭头的读取程序，读取到E的时候，发现缓存曾经满了，这时会淘汰最早的一个A(0)。
接下来持续读取并且更新排序，倒数第二次中发现D是最大的，而B是最小的，当读取F退出缓存之后，发现缓存曾经是满的，此时发现绝对于A之后插入的数值B拜访次数最小，于是进行淘汰并且替换。
依据起码实用准则LRU 的实现须要两个数据结构：
- HashTable（哈希表）: 用于实现O(1)的查找。
- List: 存储
Least recently排序，用于旧数据的淘汰。
LevelDB实现
这里间接看LevelDB是如何利用这个数据结构的。
LevelDB的LRUCache设计有4个数据结构，是顺次递进的关系，别离是：
- LRUHandle（LRU节点，也就是LRUNode）
- HandleTable（哈希表）
- LRUCache（要害，缓存接口标准和实现）
- ShardedLRUCache（用于进步并发效率）
整个LevelDB 的数据结构组成如下：
上面是相干接口定义：
// 插入一个键值对（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;依据LevelDB接口定义，能够整顿出缓存解决了如下的需要：
- 多线程反对
- 性能需求
- 数据条目标生命周期治理
cache.cc
在cache.cc中根本蕴含了LevelDB对于LRU缓存实现的所有代码。
HandleTable - 哈希表
HandleTable 和 HashTable 其实就是名字的区别，外部比拟要害的几个属性如下。
private:// The table consists of an array of buckets where each bucket is// a linked list of cache entries that hash into the bucket.// 第一个length_ 保留了桶的个数uint32_t length_;// 保护在整个hash表中一共寄存了多少个元素uint32_t elems_;// 二维指针，每一个指针指向一个桶的表头地位LRUHandle** list_;为了晋升查找效率，一个桶外面尽可能只有一个元素，在上面的插入代码中应用了二级指针的形式解决，然而实际上并不算非常复杂，插入的时候会找到前驱节点，并且操作的是前驱节点中的 next_hash 指针：
// 首先读取 `next_hash`，找到下一个链节，将其链到待插入节点后边，而后批改前驱节点 `next_hash` 指向。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). // 因为每个缓存条目都相当大，咱们的指标是一个小的均匀链表长度（<= 1）。 Resize(); } } return old;}另外当整个hash表中元素的个数超过 hash表桶的的个数的时候，会调用Resize函数并且把整个桶的个数增加一倍，同时将现有的元素搬迁到适合的桶的前面。
留神这个resize的操作来自一篇[[Dynamic-sized NonBlocking Hash table]]的文章，作者参照此论文的叙述设计了整个哈希表，其中最为要害的局部就是resize的局部，对于这部分内容将独自通过一篇文章进行剖析。
如果想要理解具体到算法实践，那么必然须要理解下面提到的论文：
文档下载：p242-liu.pdf
/* 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; }};这种相似汇合提前扩容的形式，联合良好的hash函数以及之前作者提到的元素长度管制为间接一倍扩容，最终这种优化之后的查找的效率能够认为为O（1）。
这里开展说一下FindPointer定位路由的办法，能够看到这里通过缓存节点的hash值和位操作疾速找到对应二级指针节点，也就是找到最终的桶，同时因为链表外部没有排序，这里通过全链表遍历的形式找到节点。
除此之外还有一个细节是下面的插入应用的是前驱接节点的 next_hash，这里查找返回这个对象也是适合的。
最终的节点查找过程如下：
- 如果节点的 hash 或者 key 匹配上，则返回该节点的双重指针（前驱节点的 next_hash 指针的指针）。
- 否则返回该链表的最初一个节点的双重指针（边界状况，如果是空链表，最初一个节点便是桶头）。
// 返回一个指向 slot 的指针，该指针指向一个缓存条目// 匹配键/哈希。 如果没有这样的缓存条目，则返回一个// 指向对应链表中尾随槽的指针。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;}删除操作会批改 next_hash 的指向，和新增的基本操作相似，这里不多介绍了。
在删除时只需将该 next_hash 改为待删除节点后继节点地址，而后返回待删除节点即可。
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; }小结
整个哈希表的内容发现次要的难点在了解二级指针的保护上，在这个几个办法当中副作用最大的函数是Resize办法，此办法在运行的时候会锁住整个哈希表并且其余线程必须期待重新分配哈希表完结，尽管一个桶尽量指向一个节点，然而如果哈希调配不平均仍然会有性能影响。
另外须要留神尽管须要阻塞，然而整个锁的最小粒度是桶，大部分状况下其余线程读取其余的桶并没有影响。
再次强调，为解决问题并发读写的哈希表，在这里，提到一种渐进式的迁徙办法：Dynamic-sized NonBlocking Hash table，能够将迁徙工夫进行均摊，有点相似于 Go GC 的演变。
"Dynamic-Sized Nonblocking Hash Tables", by Yujie Liu, Kunlong Zhang, and Michael Spear. ACM Symposium on Principles of Distributed Computing, Jul 2014.=
依据理论知识能够晓得，LRU缓存的淘汰策略通常会把最早拜访的数据移除缓存，然而显然通过哈希表是无奈实现这个操作的，所以咱们须要从缓存节点看到设计。
LRUCache - LRU缓存
LRU缓存的大抵构造如下：
和少数的LRU缓存一样，2个链表的含意是保障冷热拆散的模式，外部保护哈希表。
- lru_：冷链表，如果援用计数归0移除“冷宫”。
- in_use_：热链表，通过援用计数通常从冷链表退出到热链表。
LRUHandle lru_; // lru_ 是冷链表，属于冷宫， LRUHandle in_use_; // in_use_ 属于热链表，热数据在此链表 HandleTable table_; // 哈希表局部曾经讲过LRUCache中将之前剖析过的导出接口 Cache 所蕴含的函数省略后，LRUCache 类简化如下：
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 // 示意所有条目只被缓存援用，而没有客户端在应用 // 作者正文 // LRU 列表的虚构头。 // lru.prev 是最新条目，lru.next 是最旧条目。 // 条目有 refs==1 和 in_cache==t LRUHandle lru_ GUARDED_BY(mutex_); // in-use 双向链表的空表头 // 保留所有依然被客户端援用的条目 // 因为在被客户端援用的同时还被缓存援用， // 必定有 refs >= 2 和 in_cache==true. // 作者正文： // 应用中列表的虚构头。 // 条目正在被客户端应用，并且 refs >= 2 并且 in_cache==true。 LRUHandle in_use_ GUARDED_BY(mutex_); // 所有条目标哈希表索引 HandleTable table_ GUARDED_BY(mutex_);};冷热链表通过上面的办法进行保护：
- Ref： 示意函数要应用该cache，如果对应元素位于冷链表，须要将它从冷链表溢出链入到热链表。
- Unref：和
Ref相同，示意客户不再拜访该元素，须要将援用计数-1，再比方彻底没人用了，援用计数为0就能够删除这个元素了，如果援用计数为1，则能够将元素打入冷宫放入到冷链表。
void LRUCache::Ref(LRUHandle* e) { if (e->refs == 1 && e->in_cache) { // If on lru_ list, move to in_use_ list. LRU_Remove(e); // 打入热链表 LRU_Append(&in_use_, e); } e->refs++; } void LRUCache::Unref(LRUHandle* e) { assert(e->refs > 0); e->refs--; if (e->refs == 0) { // Deallocate. // 解除调配 assert(!e->in_cache); (*e->deleter)(e->key(), e->value); free(e); } else if (e->in_cache && e->refs == 1) { // No longer in use; move to lru_ list. // 不再应用； 挪动到 冷链表。 LRU_Remove(e); LRU_Append(&lru_, e); } }LRU 增加和删除节点比较简单，和个别的链表操作相似：
void LRUCache::LRU_Append(LRUHandle* list, LRUHandle* e) { // 通过在 *list 之前插入来创立“e”最新条目 // Make "e" newest entry by inserting just before *list e->next = list; e->prev = list->prev; e->prev->next = e; e->next->prev = e; } void LRUCache::LRU_Remove(LRUHandle* e) { e->next->prev = e->prev; e->prev->next = e->next; }因为是缓存，所以有容量的限度，如果超过容量就必须要从冷链表当中剔除拜访起码的元素。
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; // for the returned handle. 返回的句柄 std::memcpy(e->key_data, key.data(), key.size()); if (capacity_ > 0) { e->refs++; // for the cache's reference. e->in_cache = true; //链入热链表 LRU_Append(&in_use_, e); //应用的容量减少 usage_ += charge; // 如果是更新的话，须要回收老的元素 FinishErase(table_.Insert(e)); } else { // don't cache. (capacity_==0 is supported and turns off caching.) // capacity_==0 时示意敞开缓存，不进行任何缓存 // next is read by key() in an assert, so it must be initialized // next 由断言中的 key() 读取，因而必须对其进行初始化 e->next = nullptr; } 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);}这里须要关注上面的代码：
if (capacity_ > 0) { e->refs++; // for the cache's reference. e->in_cache = true; //链入热链表 LRU_Append(&in_use_, e); //应用的容量减少 usage_ += charge; // 如果是更新的话，须要回收老的元素 FinishErase(table_.Insert(e)); } else { // don't cache. (capacity_==0 is supported and turns off caching.) // 不要缓存。 （容量_==0 受反对并敞开缓存。） // next is read by key() in an assert, so it must be initialized // next 由断言中的 key() 读取，因而必须对其进行初始化 e->next = nullptr; }在外部的代码须要留神FinishErase(table_.Insert(e));办法，这部分代码须要联合之前介绍的哈希表（HandleTable）的LRUHandle* Insert(LRUHandle* h)办法，，在外部如果发现同一个key值的元素曾经存在，HandleTable的Insert函数会将旧的元素返回。
因而LRU的Insert函数外部隐含了更新的操作，会将新的Node退出到Cache中，而老的元素会调用FinishErase函数来决定是移入冷宫还是彻底删除。
// If e != nullptr, finish removing *e from the cache; it has already been removed from the hash table. Return whether e != nullptr.// 如果e != nullptr，从缓存中删除*e；示意它曾经被从哈希表中删除。同时返回e是否 !=nullptr。bool LRUCache::FinishErase(LRUHandle* e) { if (e != nullptr) { assert(e->in_cache); LRU_Remove(e); e->in_cache = false; usage_ -= e->charge; // 状态扭转 Unref(e); } return e != nullptr;}扩大：Mysql的内存缓存页也是应用冷热拆散的形式进行保护和解决，目标使均衡可用页和缓存命中，然而咱们都晓得8.0缓存间接删掉了，起因是现今稍大的OLTP业务对于缓存的命中率非常低。
小结
LevelDB当中到LRU缓存实现有以下特点：
- 应用冷热拆散链表保护数据，冷热数据之间的数据不存在交加：被客户端援用的
in-use链表，和不被任何客户端援用的lru_链表。 - 双向链表的设计，同时其中一端应用空链表作为边界判断。表头的
prev指针指向最新的条目，next指针指向最老的条目，最终造成了双向环形链表。 - 应用
usage_示意缓存以后已用量，用capacity_示意该缓存总量。 - 形象出了几个基本操作：
LRU_Remove、LRU_Append、Ref、Unref作为辅助函数进行复用。 - 每个
LRUCache由一把锁mutex_守护。
LRUHandle - LRU节点
LRU节点 通过状态判断切换是否存在缓存当中，如果援用计数为0，则通过erased办法被移除哈希以及LRU的链表。
上面是具体的示意图：
LRUHandle 其实就是缓存节点LRUNode，LevelDB的Cache治理，通过作者的正文能够理解到，整个缓存节点保护有2个双向链表和一个哈希表，哈希表不须要过多介绍。
哈希的经典问题就是哈希碰撞，而应用链表节点解决哈希节点的问题是经典的形式，LevelDB也不例外，不过他要比传统的设计形式要简单一点。
// 机翻自作者的正文，对于了解作者设计比拟要害，翻得个别。倡议比照原文多读几遍// LRU缓存实现//// 缓存条目有一个“in_cache”布尔值，批示缓存是否有// 对条目标援用。如果没有传递给其“删除器”的条目是通过 Erase()，// 通过 Insert() 时， 插入具备反复键的元素，或在缓存销毁时。//// 缓存在缓存中保留两个我的项目的链表。中的所有我的项目// 缓存在一个列表或另一个列表中，并且永远不会同时存在。仍被援用的我的项目// 由客户端但从缓存中删除的不在列表中。名单是：// - in-use: 蕴含客户端以后援用的我的项目，没有// 特定程序。 （这个列表用于不变查看。如果咱们// 删除查看，否则该列表中的元素可能是// 保留为断开连接的单例列表。）// - LRU：蕴含客户端以后未援用的我的项目，按 LRU 程序// 元素通过 Ref() 和 Unref() 办法在这些列表之间挪动，// 当他们检测到缓存中的元素获取或失落它的惟一// 内部参考。// 一个 Entry 是一个可变长度的堆调配构造。 条目保留在按拜访工夫排序的循环双向链表中。// LRU cache implementation//// Cache entries have an "in_cache" boolean indicating whether the cache has a// reference on the entry. The only ways that this can become false without the// entry being passed to its "deleter" are via Erase(), via Insert() when// an element with a duplicate key is inserted, or on destruction of the cache.//// The cache keeps two linked lists of items in the cache. All items in the// cache are in one list or the other, and never both. Items still referenced// by clients but erased from the cache are in neither list. The lists are:// - in-use: contains the items currently referenced by clients, in no// particular order. (This list is used for invariant checking. If we// removed the check, elements that would otherwise be on this list could be// left as disconnected singleton lists.)// - LRU: contains the items not currently referenced by clients, in LRU order// Elements are moved between these lists by the Ref() and Unref() methods,// when they detect an element in the cache acquiring or losing its only// external reference.// 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; 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]; // 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. // 仅当 LRU 句柄是空列表的列表头时，next 才等于此值。此时列表头永远不会有有意义的键。 assert(next != this); return Slice(key_data, key_length);}ShardedLRUCache
该类继承Cache接口，并且和所有的LRUCache一样都会加锁，然而不同的是ShardedLRUCache能够定义多个LRUCache别离解决不同的hash取模之后的缓存解决。
class ShardedLRUCache : public Cache { private: LRUCache shard_[kNumShards]; port::Mutex id_mutex_; uint64_t last_id_; static inline uint32_t HashSlice(const Slice& s) { return Hash(s.data(), s.size(), 0); } static uint32_t Shard(uint32_t hash) { return hash >> (32 - kNumShardBits); } public: explicit ShardedLRUCache(size_t capacity) : last_id_(0) { const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards; for (int s = 0; s < kNumShards; s++) { shard_[s].SetCapacity(per_shard); } } ~ShardedLRUCache() override {} Handle* Insert(const Slice& key, void* value, size_t charge, void (*deleter)(const Slice& key, void* value)) override { const uint32_t hash = HashSlice(key); return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter); } Handle* Lookup(const Slice& key) override { const uint32_t hash = HashSlice(key); return shard_[Shard(hash)].Lookup(key, hash); } void Release(Handle* handle) override { LRUHandle* h = reinterpret_cast<LRUHandle*>(handle); shard_[Shard(h->hash)].Release(handle); } void Erase(const Slice& key) override { const uint32_t hash = HashSlice(key); shard_[Shard(hash)].Erase(key, hash); } void* Value(Handle* handle) override { return reinterpret_cast<LRUHandle*>(handle)->value; } // 全局惟一自增ID uint64_t NewId() override { MutexLock l(&id_mutex_); return ++(last_id_); } void Prune() override { for (int s = 0; s < kNumShards; s++) { shard_[s].Prune(); } } size_t TotalCharge() const override { size_t total = 0; for (int s = 0; s < kNumShards; s++) { total += shard_[s].TotalCharge(); } return total; }};ShardedLRUCache 外部有16个LRUCache，查找key的时候，先计算属于哪一个LRUCache，而后在相应的LRUCache中上锁查找，这种策略并不少见，然而外围的代码并不在这一部分，所以放到了最初进行介绍。
16个LRUCache，Shard 办法利用 key 哈希值的前 kNumShardBits = 4 个 bit 作为分片路由，最终能够反对 kNumShards = 1 << kNumShardBits 16 个分片，这也是16个分片
static uint32_t Shard(uint32_t hash) { return hash >> (32 - kNumShardBits); }因为 LRUCache 和 ShardedLRUCache 都实现了 Cache 接口，因而 ShardedLRUCache 只需将所有 Cache 接口操作路由到对应 Shard 即可，总体来说 ShardedLRUCache 没有太多逻辑，这里不再赘述。
总结
整个LevelDB的LRU缓存实现，除了在起名的中央有点非主流之外，根本合乎LRU的设计思维。
整个LevelDB的外围是哈希表和哈希函数，反对并发读写的哈希表以及resize函数外围局部都是值得斟酌。
对于哈希表的优化实际上自呈现开始就始终在优化，LevelDB上的实现是一个不错的参考。
写在最初
LevelDB比拟重要的组件根本介绍实现，LevelDB的LRU缓存也能够看做是教科书个别的实现。