LRU是常见的缓存淘汰策略,用于分布式系统的缓存、页表置换等场景。然而,经典的哈希链表实现事实上并不是很好的实现策略。
本文将从内存页、CPU缓存、分布式缓存等几个方面介绍它们所使用的LRU算法实现。
目录
时间戳排序
为每个缓存赋予时间戳,在访问时更新时间戳,使用优先队列按照时间戳排序,淘汰最小时间戳的缓存。这种算法时空的开销都很大。
哈希链表
哈希链表的关键在于,使用哈希映射链表节点,而不是用链表串联哈希入口。这是因为哈希扩容后原本的哈希映射全部打乱。
在查询时,我们简单地将链表节点从链表中删除,然后插入头节点即可,这样链表的尾结点必然是最早访问的缓存。看上去,不管是淘汰还是查询都是O(1)。
问题在于,插入头结点具备scalability么? 哈希链表最大的问题在于,将所有的读访问转换为对同一临界区的写访问,在多核下是完全没有可拓展性的!
绝对的LRU并不适合工程实践,一般工业界使用LRU的近似算法。思路在于: 我们并不一定要淘汰最早访问的缓存,只要淘汰相对最早访问的缓存即可。
Clock(NRU)
如同时钟一般,Clock将物理页环形存储,并在物理页维护reference bit(不能使用access bit,因为MMU对应虚拟页),时钟的柄作为入口,当没有空物理页时,从柄开始查询。
某些优化会考虑物理页是否发生修改dirty bit,如果没有修改的话是可以不用刷回磁盘的,因此最适合淘汰。
显然,clock算法在读取时并不会导致竞争,只会修改本地的reference bit。
此外,clock算法还有一系列的变种,参考https://en.wikipedia.org/wiki/Page_replacement_algorithm#cite_note-9
工作集(Working Set)
工作集的意思是,进程在时间段(t - x, t)内使用的内存页集合,也有可能是(t,t+x)所访问的页集合,因此应该将它们尽可能保存在内存中。工作集的实现依赖于OS提供Page Aging的支持。
工作集时钟中断固定间隔发生,处理函数扫描内存页
若Age大于设置的x,则不在工作集,可以被淘汰。
工作集模型本身并不是页面置换算法,但是可以辅助页面置换算法作为淘汰的额外条件,例如WSclock算法就是基于Clock算法和Working Set算法而实现的。
2Q(Two Queue)
BlueStore的缓存策略,基于FIFO+LRU双队列实现,个人感觉不如Linux巧妙,这里的插入是实时+单向的。
FIFO链表
LRU链表
感觉还是没法解决头结点竞争的问题,不知道最后用了啥优化。
Linux 双链表LRU
linux的想法是,一个链表存储活跃的页,另一个链表存储不活跃的页,通过active bit区分。插入表头的过程是惰性的,推迟到了淘汰时进行,因此避免了之前所说的并发读高度竞争。
转自兰新宇大佬
当我们想要从链表中移除页时(对inactive是进行淘汰,对active是补充inactive)
从链表末尾开始依次检测
活跃链表
不活跃链表
但是,虽然惰性的插入已经减少了很多插入表头,但是插入表头依然是竞争。因此Linux用了lru cache进行了batching,一次性处理多个插入表头以减少锁的获取。
同样地,因为采用了惰性,这种算法显然不是绝对的LRU,具体参照这篇文章
对于硬件级别的缓存而言,每个缓存行的block数目固定且规模有限,因此不需要复杂机制也能判断,直接运用bit即可。硬件有很多LRU的近似实现。
Tree-PLRU
利用二叉树来确定LRU的位置,0表示左,1表示右。
在访问缓存的过程中,路径上的flag设置和查找方向相反(例如如果向左查找,那么设置成1)。
当miss时,二叉树根据flag查找到的block会被淘汰。
MRU(mostly)
实际上淘汰的是NRU, 每个block具备一个bit,访问block时该bit置0,其他block置1。当miss时,第一个bit为1的block会被淘汰。
QLRU(quad age)
MRU变种,每个block具备两个bit,代表年龄,初始为1, 0为LRU,3为MRU。当miss时,bit最小的block会被淘汰。Intel在PPT表示,给予初始时middle age能够有效帮助prefetch,使得新增加的数据不会立刻被淘汰。不过这货找不到论文,具体状态机没搞懂。
Redis 采样式 LRU
实现位于evict.c中,通过近似算法来淘汰相对不经常使用的元素,其实就是之前时间戳排序的弱化版,淘汰的是采样部分的LRU。
void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {
int j, k, count;
dictEntry *samples[server.maxmemory_samples];
count = dictGetSomeKeys(sampledict,samples,server.maxmemory_samples);
}
在dictGetSomeKeys中,随机挑选某个位置开始收集连续count个元素,如果均为空,那么再次随机挑选。这里复杂的地方在于Rehashing过程中会存在两张表,但是这和Redis机制太耦合,和LRU本身倒没啥关系。
维持一个全局的LRU时钟作为时间戳,如果刷新速度比服务器要求的刷新速度快,就用服务器缓冲的LRU,否则用实时的。
unsigned int getLRUClock(void) {
return (mstime()/LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX;
}
unsigned int LRU_CLOCK(void) {
unsigned int lruclock;
if (1000/server.hz <= LRU_CLOCK_RESOLUTION) {
lruclock = server.lruclock;
} else {
lruclock = getLRUClock();
}
return lruclock;
}
然后idle的时间就是当前时钟与上次访问时钟的差值
unsigned long long estimateObjectIdleTime(robj *o) {
unsigned long long lruclock = LRU_CLOCK();
if (lruclock >= o->lru) {
return (lruclock - o->lru) * LRU_CLOCK_RESOLUTION;
} else {
return (lruclock + (LRU_CLOCK_MAX - o->lru)) *
LRU_CLOCK_RESOLUTION;
}
}
这里的优化在于eviction pool记忆之前LRU的幸存者,其实和数据流的Top-K算法比较类似。pool按照idle升序排列,通过插入排序来维护。如果满了,则把idle最小的给删除。
只有比幸存者最小idle更大的元素才可能加入eviction pool,淘汰的时候复用eviction pool中被淘汰的entry以减少分配开销。
/* Try to reuse the cached SDS string allocated in the pool entry,
* because allocating and deallocating this object is costly
* (according to the profiler, not my fantasy. Remember:
* premature optimizbla bla bla bla. */
int klen = sdslen(key);
if (klen > EVPOOL_CACHED_SDS_SIZE) {
pool[k].key = sdsdup(key);
} else {
memcpy(pool[k].cached,key,klen+1);
sdssetlen(pool[k].cached,klen);
pool[k].key = pool[k].cached;
}
pool[k].idle = idle;
pool[k].dbid = dbid;
Memcache分段式LRU
memcache采用分段的方式,没有将整体实现为哈希链表,而是每次以Slab为单位进行LRU,这样一来头结点的竞争就被均摊到了每个Slab上。淘汰的是局部的LRU,而不是全局的LRU。
static void do_item_link_q(item *it) { /* item is the new head */
item **head, **tail;
assert((it->it_flags & ITEM_SLABBED) == 0);
head = &heads[it->slabs_clsid];
tail = &tails[it->slabs_clsid];
assert(it != *head);
assert((*head && *tail) || (*head == 0 && *tail == 0));
it->prev = 0;
it->next = *head;
if (it->next) it->next->prev = it;
*head = it;
if (*tail == 0) *tail = it;
sizes[it->slabs_clsid]++;
#ifdef EXTSTORE
if (it->it_flags & ITEM_HDR) {
sizes_bytes[it->slabs_clsid] += (ITEM_ntotal(it) - it->nbytes) + sizeof(item_hdr);
} else {
sizes_bytes[it->slabs_clsid] += ITEM_ntotal(it);
}
#else
sizes_bytes[it->slabs_clsid] += ITEM_ntotal(it);
#endif
return;
}
分为四种状态,每个item具有两个bit,fetched和active,即访问1次和访问2次
https://memcached.org/blog/modern-lru/
Hot - active则到WARM表头,inactive则到COLD表头(类比JVM的eden区)
Warm - active则到WARM表头,inactive则到COLD表头(类比JVM的survivor区)
Cold - active则异步到WARM表头,否则淘汰
Temp - 极小存活周期的缓存,过期直接淘汰
当Hot和Warm的长度超出限制之后,Warm和Hot开始进行末位淘汰。
当Slab内存满了的时候,Cold开始进行末位淘汰