如何做百度的网站如何做游戏推广

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受害者进行比较。