W-TinyLFU——设计一个现代的缓存

数据极客 2016-01-26

缓存设计是个基础架构领域里的重要话题,本号之前也有谈论过相关话题,点击原文可以看之前的介绍。


近日,HighScalability网站刊登了一篇文章,由前Google工程师发明的W-TinyLFU——一种现代的缓存。那么,什么缓存设计能够被称作是“现代”的呢?


当数据的访问模式不随时间变化的时候,LFU的策略能够带来最佳的缓存命中率。然而LFU有两个缺点:首先,它需要给每个记录项维护频率信息,每次访问都需要更新,这是个巨大的开销;其次,如果数据访问模式随时间有变,LFU的频率信息无法随之变化,因此早先频繁访问的记录可能会占据缓存,而后期访问较多的记录则无法被命中。因此,大多数的缓存设计都是基于LRU或者其变种来进行的,相比之下,LRU并不需要维护昂贵的缓存记录元信息,同时也能够反应随时间变化的数据访问模式。然而,在许多负载之下,LRU依然需要更多的空间才能做到跟LFU一致的缓存命中率。因此,一个“现代”的缓存,应当能够综合两者的长处。


W-TinyLFU就是这样一个工作,在介绍之前,先来看看TinyLFU,它是W-TinyLFU运转的基础。


TinyLFU维护了近期访问记录的频率信息,作为一个过滤器,当新记录来时,只有满足TinyLFU要求的记录才可以被插入缓存。如前所述,作为现代的缓存,它需要解决两个挑战:一个是如何避免维护频率信息的高开销,另一个是如何反应随时间变化的访问模式。首先来看前者,TinyLFU借助了本号之前介绍过的数据流Sketching技术,Count-Min Sketch显然是解决这个问题的有效手段,它可以用小得多的空间存放频率信息,而保证很低的False Positive Rate。但考虑到第二个问题,就要复杂许多了,因为我们知道,任何Sketching数据结构如果要反应时间变化都是一件困难的事情,在Bloom Filter方面,我们可以有Timing Bloom Filter,但对于CMSketch来说,如何做到Timing CMSketch就不那么容易了。TinyLFU采用了一种基于滑动窗口的时间衰减设计机制,借助于一种简易的reset操作:每次添加一条记录到Sketch的时候,都会给一个计数器上加1,当计数器达到一个尺寸W的时候,把所有记录的Sketch数值都除以2,该reset操作可以起到衰减的作用:


可以证明[1],reset操作带来的频率估计期望不变。


W-TinyLFU主要用来解决一些稀疏的突发访问元素。在一些数目很少但突发访问量很大的场景下,TinyLFU将无法保存这类元素,因为它们无法在给定时间内积累到足够高的频率。因此W-TinyLFU就是结合LFU和LRU,前者用来应对大多数场景,而LRU用来处理突发流量。

HighScalability上的另一种视图:


前端是一个小的LRU,在送到TinyLFU做过滤之后,元素存放到一个大的Segmented LRU缓存里。前端的小LRU叫做Window LRU,它的容量只占据1%的总空间,它的目的就是用来存放短期突发访问记录。存放主要元素的Segmented LRU(SLRU)是一种LRU的改进,主要把在一个时间窗口内命中至少2次的记录和命中1次的单独存放,这样就可以把短期内较频繁的缓存元素区分开来。具体做法上,SLRU包含2个固定尺寸的LRU,一个叫Probation段A1,一个叫Protection段A2。新记录总是插入到A1中,当A1的记录被再次访问,就把它移到A2,当A2满了需要驱逐记录时,会把驱逐记录插入到A1中。W-TinyLFU中,SLRU有80%空间被分配给A2段。




从实验上可以看出,相比其他缓存策略,W-TinyLFU的缓存命中率可以达到最优。


W-TinyLFU的实现在Caffeine项目里[2],除了缓存更新策略之外,另一个设计问题是并发更新,这也是本号上一篇讲述缓存谈论的设计问题。Caffeine采用了类似日志的方式尽可能避免锁的操作:写入操作放到日志里然后异步批处理更新。具体而言,Caffeine利用ringbuffer存放写入数据,待buffer满之后做批量处理,并且为每个线程使用独立的ringbuffer进一步提升性能。


下边是Java类各缓存实现的并发性能对比,差别还是很显著的。



进一步细节论文介绍在[1],[2]和[3]分别是Java和Golang的对应实现,HighScalability的文章在[4],祝玩得开心~


[1] TinyLFU: A Highly Efficient Cache Admission Policy by Gil Einziger, Roy Friedman, Ben Manes

[2] https://github.com/ben-manes/caffeine

[3] https://github.com/dgryski/go-tinylfu

[4] http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html

本站仅按申请收录文章,版权归原作者所有
如若侵权,请联系本站删除
觉得不错,分享给更多人看到

数据极客 微信二维码

数据极客 微信二维码

数据

阅读 78
点赞 5
更新 1月27日 22:55