我们如何与 Meta (Facebook) 合作创建 Shadow Cache

通过 Meta (Facebook)、普林斯顿大学和 Alluxio 之间的合作，我们开发了“Shadow Cache”——一个轻量级的 Alluxio 组件，用于跟踪工作集大小和无限缓存命中率。影子缓存可以动态跟踪过去窗口的工作集大小，由一系列布隆过滤器实现。影子缓存部署在 Meta (Facebook) Presto 中，并被用于了解系统瓶颈并帮助制定路由设计决策。

动机和背景

在 Meta (Facebook)，Presto 是一个分布式实时查询引擎，使用 SQL 语言作为接口对 PB 级数据执行快速、交互式查询。它支持标准 ANSI SQL，包括查询、聚合、JOIN 和窗口函数。

Alluxio 是数据编排平台，作为支持 Presto 和其他各种数据分析应用程序和用例的关键技术。 Alluxio 创建了一个虚拟数据层，可以联合来自任何文件系统或对象存储的数据，提供跨存储系统的统一命名空间，并使用具有快速数据访问的行业标准接口为应用程序提供数据。

要提高 Presto 的性能，了解缓存大小和缓存命中率的影响至关重要。 Presto 需要从 Alluxio 获知某些缓存信息，以确定在缓存存储受限的情况下，扩大缓存大小是否有助于提高缓存命中率和性能。此信息还有助于优化缓存算法。我们还想优化路由算法以获得更好的平衡和效率。因此，如何更好地跟踪和管理 Alluxio 缓存数据是 presto 优化决策的关键。

Presto 方面需要解决两个关键问题：

1.如何为每个租户设置缓存大小？

2. 潜在的缓存命中率提升是多少？

我们提出了“Shadow Cache”，这是一个轻量级的 Alluxio 组件，用于跟踪工作集大小和缓存命中率。

为了回答第一个问题，Shadow Cache 会告诉管理员在过去 24 小时内缓存收到了多少非重复字节，以估计未来的缓存需求。对于第二个问题，Shadow Cache 会告诉管理员，如果缓存可以保留过去 24 小时内的所有请求，有多少请求命中缓存，即未命中的请求是从未出现的请求，因此最大命中率为可以计算缓存。

这个轻量级的 Alluxio 组件，Shadow Cache，可以提供关于缓存工作集的见解，以及如果有无限的缓存空间，缓存命中率会是什么样子。为了监控集群的缓存状态，我们定义了以下关键指标。

• C1：某个时间点的真实Cache使用情况
• C2：时间窗口中的影子缓存工作集（1天/1周）
• H1：真实缓存命中率
• H2：暗影缓存命中率

挑战

虽然我们试图为 Alluxio 的缓存提供上述指标，但我们遇到了一些挑战。

低内存和 CPU 开销

Shadow Cache 是一个轻量级组件，用于跟踪缓存工作集的大小。很难跟踪内存有限的“无限”工作集。 Shadow Cache 还必须具有较低的 CPU 开销，因为它会在处理每个查询时缓存数据。否则，用户请求将被长时间阻塞。

准确性

Shadow Cache 还必须保证准确性。在 Presto 中，Shadow Cache 测量集群的缓存状态，如果估计的限制缓存命中率太低，Presto 可能会错误地判断该作业是缓存不友好的。相比之下，如果预估的 limit 缓存命中率过高，Presto 可能认为此时扩展集群的缓存会显着提升整体性能。

动态更新

Presto 和其他现代数据应用程序主要用于发现当前或未来趋势。因此，Shadow Cache 也应该实时丢弃过时的项目。否则，很可能会给决策带来噪声干扰。滑动窗口是存储最新项目最常用的方法之一，但创建滑动窗口模型的数据结构并不容易。当窗口滑动时，我们需要实时删除刚刚移出的项目。重要的是尽快找到需要删除的项目并将其删除。

解决方案

鉴于高精度和低开销这两个要求，我们立即想到了布隆过滤器，它在各种分布式数据库中得到了普及。 Shadow Cache 根据 Bloom 过滤器估计工作集大小和限制命中率。以下是布隆过滤器如何解决这三个挑战。

布隆过滤器：开销和准确性挑战的解决方案

布隆过滤器是一种节省空间的概率数据结构成员测试。布隆过滤器是一个以位为单位全零初始化的数组，每个对象仅用几个位表示，显着节省空间开销并提供高效的查询。布隆过滤器可以确定一个项目是否存在。如果 Bloom 过滤器返回它不存在，则该项目不得存在。请注意，可能会出现误报，但不会出现误报。

布隆过滤器有 k 个哈希函数。要添加元素，请应用每个散列函数并将位设置为 1。要查询元素，请应用每个散列函数并对位进行与运算。当 k 个位置上的所有位都为 1 时，认为该项存在。否则，该项目被认为不存在。

布隆过滤器链：动态更新的解决方案

布隆过滤器可以提供低开销和高精度，那么我们可以直接将它们应用于Shadow Cache吗？

我们遇到的第一个问题是布隆过滤器不支持删除。这是因为我们只关心用户应用的工作集随时间变化的大小，而Shadow Cache 需要这样做。 Shadow Cache 通过将多个过滤器链接在一起来创建一个布隆过滤器链来实现这一点。

以下是如何使用布隆过滤器链实时更新工作集的负载大小。

查询：如上图所示，Shadow Cache 是一个由多个 Bloom filter 组成的链。在跟踪用户在过去 24 小时内的工作集大小时，我们可以将 24 小时分为四个时段。一个布隆过滤器跟踪影子缓存中的每个周期，每个布隆过滤器跟踪一个周期。 Shadow Cache 使用所有现有的布隆过滤器或为查询创建一个新的布隆过滤器，如下图所示。

实时更新：为了保持数据的实时性，我们需要Shadow Cache在时间窗口滑动时丢弃已经过时的数据。布隆过滤器值必须随着时间 t 不断更新，并且已经在时间窗口之外的布隆过滤器项必须被删除。由于我们组合了多个布隆过滤器，因此很容易在布隆过滤器的最后确定过期项目的位置，如下图所示。每次新周期开始时，我们从链中删除最旧的过滤器，并添加一个新的全空过滤器来记录最新数据。

工作集大小：由于布隆过滤器将一个项目映射到多个位，因此仅根据位数为 1 来判断工作集大小会引入不可接受的错误，因为一个位可能代表多个项目，一个项目可以分散在多个位中。因此，我们采用由Swamidass & Baldi (2007)推导出的公式。我们利用以下等式的近似值来测量工作集的大小。

其中 n* 是过滤器中项目数的估计值，m 是过滤器的长度（大小），k 是散列函数的数量，X 是设置为 1 的位数。

Infinite Size Hit Ratio： Shadow Cache 在提供了工作集大小指标后，还需要提供无限大小的命中率。我们可以将 Bloom 过滤器用作具有无限空间的缓存，因为它们可以用很少的内存使用跟踪大量数据。命中布隆过滤器的用户请求数等于无限缓存中的命中数，称为命中。 “用户请求”的总数表示为 queryNum。 QueryNum 是“用户请求”的总数，所以命中率等于 hit/queryNum。

使用影子缓存确定 Presto 集群缓存状态

完成布隆过滤器链后，我们可以快速学习之前定义的指标H1、H2、C1、C2。下一步，Presto 可以通过比较它们之间的大小关系来判断集群的缓存状态，如下图所示。

当H2低时，表示即使缓存空间无限，也无法达到该集群中应用的缓存命中率。这意味着此应用程序对缓存不友好。当 H2 高 H1 低且 C2 > C1 时，表明集群缓存空间分配不足，如果扩大缓存容量，可以进一步提高命中率。当H2高且H1高且C2 < C1时，集群缓存过度分配，资源被浪费。如果 H2 > H1 和 C2 > C1 和 C2 > C1，则集群状态良好，这意味着不需要扩展缓存。

执行

Shadow Cache 的 Bloom 过滤器实现基于 Guava BloomFilter 库，并支持基于用户定义的内存开销预算和影子缓存窗口的特定过滤器配置。目前，Shadow Cache 支持以#pages 和#byte 表示工作集大小，分别表示工作集包含多少页和多少特定字节。对于命中率计算，Shadow Cache 支持无限大小的字节命中率和对象命中率。

下面是配置。

#过去的窗口定义工作集

alluxio.user.client.cache.shadow.window=**24h**

#用于跟踪的布隆过滤器的总内存开销

alluxio.user.client.cache.shadow.memory.overhead=**125MB**

#用于跟踪的布隆过滤器的数量。每个跟踪一段窗口

alluxio.user.client.cache.shadow.bloomfilter.num=**4**

试验结果

我们测试了 Shadow Cache，发现只有 125MB 的空间，Shadow Cache 可以跟踪 27TB 的工作集，错误率只有 3%。此外，使用 HyperLogLog 可以进一步降低错误率，但如果使用 HyperLogLog，将不支持无限大小的命中率估计。

Presto 路由优化

为了提高性能，Presto 需要一种方法来及时调整集群，如果它从 Shadow Cache 中学习到特定的集群状态。我们下一步是描述当前的 Presto 路由算法，然后在引入 Shadow Cache 之后提供路由优化的几个选项。

Presto 路由

Presto 将不同的表存储在不同的集群中，通过表名跨集群共享缓存。因此，访问同一张表的查询总是会去同一个目标集群以最大化其缓存。如果不这样做，集群缓存将充满各种不同的表。下面是路由算法的示意图。

如上图所示，表1到表4的表名不同，因此被分配到不同的簇中。向table1请求数据时，路由算法将请求发送到cluster1，向table3请求数据时，路由算法将请求发送到cluster3。

路由优化选项

集群请求的响应时间是确定集群是否正常工作的简单方法。当集群响应缓慢或响应时间过长时，我们假设集群有问题。使用Shadow Cache，如上所述，结合H1、H2、C1、C2，我们可以快速确定集群是否由于缓存压力而出现性能下降。

Presto 为这种性能不佳的集群提出了以下三个路由优化选项。当然，每个选项都有其权衡。

• 选项 1：当主集群繁忙时，为这些查询指定一个启用缓存的指定辅助集群。但是，这种方法需要在每个集群上存储额外的表缓存。
• 选项 2：两个集群都被视为服务请求的主集群，并在两个集群中执行负载平衡。但是，此选项将使缓存磁盘空间使用量成倍增加。
• 选项3：构建从表到集群的Map，使CPU利用率更加均匀。但是，它可能会使缓存存储分布不均匀，并且需要额外的缓存空间。

概括

跟踪和估计缓存中工作集大小的挑战是巨大的，因此我们使用 Bloom 过滤器开发了一个轻量级的 Alluxio 组件 Shadow Cache。因为我们只对工作集的最新状态感兴趣，所以有必要使用时间窗口模型来消除过时的项目。为此，Shadow Cache 将时间窗口分为四段。每个段都使用不同的布隆过滤器进行跟踪。创建一个新的布隆过滤器来跟踪最新数据，替换每个消除中最早的数据。最后，当需要提供工作集大小时，我们使用Swamidass & Baldi (2007)提出的基础估计公式。

总的来说，Shadow Cache 为 Presto 提供了四个方便的指标：H1、H2、C1、C2，其中 H1 和 C1 分别代表真正的缓存命中率和使用率，而 H2 和 C2 代表缓存的限制命中率和大小用户在一段时间内的工作集。 Presto 可以根据以上四个指标快速判断缓存容量与应用性能之间的关系，并优化路由算法以获得更好的平衡和效率。

链接

• 代码合并
• 这篇文章的中文版

关于作者

Ke Wang是 Meta (Facebook) 的一名软件工程师，专注于 Presto 团队的低延迟查询。

宋振宇是博士。普林斯顿大学计算机科学系的候选人，研究机器学习以提高 CDN 的缓存效率。