自适应软件缓存管理
译自：Adaptive Software Cache Management
简介由于负载的多样性，很难开发一个能够适用于各种负载的软件缓存管理策略。在本论文中，我们调研了一种用于软件缓存管理框架的自适应机制，通过调节参数来调节负载的最常(访问) vs 最近(访问)的缓存比例。最终目标是通过自动调节参数来获得最佳性能(而无需人工介入)。我们针对该问题研究了两种方案：爬山解决方案和基于指示器的解决方案。在爬山解决方案中，通过不断配置系统来获得最佳配置。在指示器方案中，我们评估了最常(访问) vs 最近(访问)对系统的影响，并根据单一变量调节参数。
我们将这些自适应机制用于最新的两个软件管理框架中，并对在大量不同特性的负载下的框架和自适应机制进行了评估。通过这些工作来衍生出一个与参数无关的软件缓存策略，并在所有测试的负载中保持竞争力。
本文提供了两种缓存自适应策略:爬山方案和指示器方案。通过比较发现基于W-TinyLFYU的自适应缓存框架可以很好地工作于多种负载之下。
后续有时间研究一下文中给出的自适应实现方式。
1 概述缓存是一种通过维护相对较小的(临近的)高速内存块中的数据来解决系统突发性能的技术。这里我们主要关心软件缓存，即由中间件、操作系统、文件系统、存储系统和数据库等软件系统维护的缓存(而非由硬件实现的缓存，如CPU的L1、L2和L3缓存)。重复访问存在于缓存中的数据的行为，称为缓存命中，其远快于从实际存储中获取数据。其他访问则称为缓存缺失。缓存管理策略的主要工作是确定哪些元素可以放在缓存中，猜测哪些元素可以获得最高的命中率，即缓存命中率和整体访问数的比率。这类框架通常会尝试在负载中确定某些模式来获得最高命中率。
最近(访问)和最常(访问)是软件缓存管理策略经常使用的两种方式。最近(访问)认为，最近访问的元素很可能在不久的将来被重复访问。相比之下，最常(访问)认为，最常访问的元素很可能在不久的将来被重复访问。由于大多数负载元素的流行度都会随着时间变化，通常会使用如滑动窗口[17]或指数退避[13,19]来测量使用频率。
从经验上看，不同的负载展示了不同程度的最近(访问) vs 最常(访问)，这也是为什么很难去设计一个单一的"最佳"缓存管理款框架。因此系统设计者面临的并非一项简单的任务，需要了解负载的特性，然后为这些负载调研出一个可以提供最高命中率的缓存管理策略。而且，一些缓存管理策略具有可调节的参数，这要求系统设计者了解如何去配置这些参数。更糟糕的是，当设计一个新系统时，有可能无法事先知道未来运行的负载，这样设计者就无法判断应该选择哪种缓存管理策略。另外，在一般的缓存库中，为了无需让用户处理设置参数，会将这些参数设置为默认值，以为大多数负载提供最佳结果。但对于其他系统负载，这类设置可能会大大偏离最佳结果。
总之，自适应软件缓存管理策略需要在尽可能多的负载上获得富有竞争力的命中率。我们将聚焦在探索软件存储的自适应性机制。
价值在本论文中，我们为软件缓存管理框架确定了两种自适应机制，这两种机制都暴露了影响命中率的调参。第一种基于爬山方式[26]来调节缓存管理参数。特别地，我们会定期在某个方向上调整参数，使之在偏最近(访问)的负载 vs 偏最常(访问)的负载下更好地工作。在一段时间后，使用最近获得的命中率与上一次的命中率进比较。如果命中率获得了显著提升，则在相同方向上继续调参，否则在相反方向上调参，以此往复。爬山方案最大的优势是可以在不引入任何元数据的情况下实现。然而，它可能会陷入局部最大值的风险，且永远不会停止振荡。
另一种方式是基于指标的方案。这里，我们会定期计算负载的最常(访问) vs 最近(访问)的评估结果，并调节相应的参数。这种方式需要一些元数据来计算上述评估结果，并快速收敛。
我们将这两种方法引入最近出现的FRD[25]和W-TinyLFU [13]1框架中。这两个框架都将整个缓存区域划分为两个子缓存，一个用于保存"最近进入的元素"，另一个用于保存"常用的元素"。两个框架都将两个子缓存的比例作为一个可调节的参数，但在选择哪个元素进入哪个子缓存上有所差异。在W-TinyLFU中，取决于一个通过节省空间的sketch [11]实现的准入过滤器，其频率老化机制作为自适应的另一个潜在区域。
这里，我们使用上面提到的爬山和指示器方法来为在线负载探索动态调节FRD和W-TinyLFU的参数的方式。特别是调节FRD和W-TinyLFU的两个子缓存的相对大小。对于W-TinyLFU，我们还处理了其sketch准入过滤器的过期参数。