引言
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; }
LSM-Tree - LevelDb之LRU缓存(二)https://developer.aliyun.com/article/1395014