TOC 2022 Paper 论文阅读笔记整理
问题
现代键值存储、对象存储、互联网代理缓存和内容交付网络(CDN)通常管理不同大小的对象,例如,Blob、不同长度的视频文件、不同分辨率的图像和小文件。在这种工作负载中,大小感知缓存策略的性能优于忽略大小的算法。但现有的大小感知算法往往过于复杂且计算成本高昂。
现有方法局限性
现有的处理可变大小对象的缓存策略有一些缺陷:
-
用对象的序列化字节数组表示,将它们划分为大小相等的块或块,类似于操作系统管理内存和文件的方式。但会导致空间利用率低,或记录开销高,或序列化反序列化开销高。
-
将缓存划分为多个块,其中每个板块用于大小相似的对象,并且独立于其他块进行管理。但会导致次优的缓存利用率,因为对象的流行程度各不相同,没有单一的最佳静态块分区。
-
GDSF策略[14]在命中率和字节命中率方面都非常有效,但计算开销过高。其他方法AdaptSize [11]、LHD [6]和最近的 LRB [44],也受限于计算开销高。
本文方法
本文扩展了流行的(忽略大小的)W-TinyLFU缓存策略,来处理可变大小的项目。
原始W-TinyLFU缓存策略:
本文主要修改了3个方面:
-
新项目可能比Window Cache大,这时新项目跳过Window Cache,立即提交给TinyLFU过滤器,以确定它是否可以进入Main Cache。
-
需要考虑多个潜在的Window受害者,他们的总大小足以为新项目腾出空间。本文使用的原型中,在每个缓存区域中,使用优先级队列跟踪LRU,并且给定缓存区域的受害者是相应队列中的最后一个项目。
-
在TinyLFU中,针对Main受害者测试Window受害者。可能有多个Window受害者,每个Window受害者都与(一个或多个)Main受害者进行比较。比较方法如图6。
修改后的W-TinyLFU缓存策略:
实验表明,与AdaptSize、LHD、LRB和GDSF等最先进的大小感知算法相比,本文的算法有更好的命中率和字节命中率。运行时比较表明,与最佳替代方案相比,本文的实现速度快了3倍,即CPU开销低得多。
总结
针对不同大小的对象,如何使用统一的低开销缓存策略进行管理。本文扩展了忽略大小的W-TinyLFU缓存策略,来处理可变大小的项目。修改了3个部分:(1)新对象可能比Window Cache大,则直接提交给TinyLFU过滤器,以确定它是否可以进入Main Cache。(2)需要考虑多个潜在的Window受害者,他们的总大小足以为新对象腾出空间。(3)在TinyLFU中,可能有多个Window受害者,每个Window受害者都与总和大于其大小的(一个或多个)Main受害者进行比较。