缓存 - Dask 博客

这项工作由 Continuum Analytics 以及 XDATA Program 支持，作为 Blaze Project 的一部分。

总而言之：缓存在重复性工作负载下能提高性能。传统的 LRU 策略不太适合数据科学。我们提出了一种新的缓存策略。

人类重复做事情

想想你最近处理过的数据集。你从磁盘加载到内存多少次了？你对这些数据重复执行几乎相同的计算多少次了？

探索性数据科学工作负载涉及重复执行非常相似的计算。这些计算共享结构。通过缓存常用结果（或部分结果），我们可以显著加快探索性数据分析的速度。

其他场景下的缓存

Web 社区热爱缓存。基于数据库的 Web 应用几乎总是使用类似 memcached 这样的系统来保护其数据库查询，该系统会划拨一部分内存来缓存频繁和最近的查询。因为人类访问的大多数页面是重复的，这可以将数据库负载降低一个数量级。即使人类访问带有不同输入的页面，这些页面通常也共享许多元素。

有限的缓存资源

如果内存无限大，我们会缓存计算过的所有结果。这样对于非新颖的结果，我们就能立即回忆（取用）它们。可惜我们的内存资源有限，所以我们会驱逐那些似乎不值得保留的缓存结果。

传统上，我们使用诸如“最少最近使用”（Least Recently Used, LRU）这样的策略。此策略会驱逐长时间未被请求的结果。这成本低廉，并且在 Web 和系统应用中效果良好。

LRU 不适合分析工作负载

不幸的是，LRU 不太适合分析工作负载。分析工作负载的计算时间和存储成本分布范围很广。大多数 Web 应用的数据库查询时间大致相同（100ms-1000ms），存储空间也大致相同（1-10kb），但分析计算的计算和存储成本很容易相差许多个数量级（分布范围达到百万或十亿是很常见的）。

考虑对大型 NumPy 数组进行的以下两种常见计算

x.std() # 重计算成本高，存储成本低
x.T # 重计算成本低，存储成本高

在第一种情况，x.std()，在大型数组上可能需要一秒钟（有点耗时），但存储只需几个字节。这个结果的存储成本如此之低，即使不常被请求，我们也乐意将其长时间保留在缓存中。

在第二种情况，x.T，计算成本很低（只是数组的元数据变化），执行只需微秒。然而结果可能需要数 GB 内存来存储。我们不想将其保留在缓存中，即使它被频繁请求也是如此；它会占用其他可能更有用（且更小）结果的空间，而且无论如何我们都可以轻易地重新计算它。

因此，我们希望保留具有以下属性的缓存结果

重计算成本高（按秒计）
存储成本低（按字节计）
经常使用
最近使用

提出的缓存策略

以下是一种 LRU 的替代方案，它满足上述目标。

每次有人访问缓存中的一个条目时，我们都会按照以下值增加该条目对应的分数：

\[\textrm{得分} = \textrm{得分} + \frac{\textrm{计算时间}}{\textrm{字节数}} (1 + \epsilon)^{t}\]

其中 compute time 是初次计算该结果所需的时间，nbytes 是存储结果所需的字节数，epsilon 是一个确定“最近”半衰期的小数，而 t 是每次访问时自动递增的计时器。

这具有反向带宽的单位（秒/字节），通过缓慢增长的指数增长给予新结果更高的重要性，并以大致线性的方式放大频繁请求结果的分数。

我们在堆中维护这些分数，追踪总字节数，并在必要时清除缓存，以将存储成本控制在固定预算内。更新成本为 O(log(k))，其中 k 是缓存中的元素数量。

Cachey

我将此实现为一个名为 cachey 的小型库。这是实验性代码，并且可能会有剧烈的 API 变更（包括重命名）。

核心对象是一个 Cache，它要求提供以下信息

可用于缓存的字节数
重要性的半衰期（减少缓存结果重要性一半所需的访问次数）（默认为 1000）
考虑将结果添加到缓存中的最低成本阈值（默认为 0）

示例

这是一个小例子

>>> from cachey import Cache
>>> c = Cache(available_bytes=1e9)  # 1 GB

>>> c.put('Hello', 'world!', cost=3)

>>> c.get('Hello')
'world!'

更有趣的示例

该缓存包含一个 memoize 装饰器。让我们来 memoize pd.read_csv。

In [1]: import pandas as pd
In [2]: from cachey import Cache

In [3]: c = Cache(1e9)
In [4]: read_csv = c.memoize(pd.read_csv)

In [5]: %time df = read_csv('accounts.csv')
CPU times: user 262 ms, sys: 27.7 ms, total: 290 ms
Wall time: 303 ms

In [6]: %time df = read_csv('accounts.csv')  # second read is free
CPU times: user 77 µs, sys: 16 µs, total: 93 µs
Wall time: 93 µs

In [7]: c.total_bytes / c.available_bytes
Out[7]: 0.096

所以我们创建一个新函数 read_csv，它的行为与 pandas.read_csv 完全一致，不同之处在于它将最近的结果保存在 c 这个缓存中。这个特定的 CSV 文件创建了一个 dataframe，它占用了我们缓存空间的十分之一。我们越频繁地请求这个 CSV 文件，它的分数就会越高，未来保留在缓存中的可能性就越大。如果使用同一缓存的其他 memoized 函数产生了更有价值的结果（重计算成本高，存储成本低）并且缓存空间耗尽，那么这个结果将被驱逐，如果再次请求 read_csv('accounts.csv')，我们将不得不重新计算结果。

Memoize 所有东西

仅仅 memoizing read_csv 并不是非常有趣。pd.read_csv 函数以大约 100 MB/s 的恒定数据带宽运行。cachey 的缓存策略只有在看到所有计算时才能真正发挥作用。例如，我们可能不想保留 read_csv 的结果，因为它们占用大量空间。如果我们发现自己正在进行相同的 groupby 计算，那么我们可能更愿意使用我们的千兆字节缓存空间来存储这些结果，原因有二：

groupby 计算需要很长时间才能完成
groupby 结果在内存中通常非常紧凑

Cachey 与 Dask

我正在逐步将 cachey 集成到 dask 的共享内存调度器中。

Dask 非常适合将 cachey 应用到许多计算中。它可以查看任务图中的每个任务，并考虑将结果包含到缓存中。我们无需明确地 memoize 想要使用的每个函数，dask 可以为我们即时完成这项工作。

此外，dask 能够很好地将我们的计算视为子任务的集合。相似的计算（如均值和方差）通常共享子任务。

未来工作

Cachey 是新的且未经测试，但现在可能有用，特别是通过上面展示的 memoize 方法。它是一个小巧简单的代码库。我很想听听大家是否认为这种缓存策略有价值。

我近期计划考虑以下事项

如何构建缓存层级，以在内存和磁盘之间共享？
如何将 cachey 干净地集成到 dask 中（参见 PR #502），以及如何使 dask 适合缓存（参见 PR #510）？

博客评论由 Disqus 提供支持

缓存 人类总是重复做事情。缓存可以提供帮助。