Introducing Ristretto: A High-Performance Go Cache

一切始于 Dgraph 需要内存可控的并发 Go 缓存。我们四处寻找也未曾发现一个好的解决方案。后来，我们尝试使用分片 map，它具有分片驱逐功能来释放内存，但导致出现内存问题。然后，我们重新利用 Groupcache 的 LRU，使用互斥锁来确保线程安全。大约一年后，我们注意到缓存遇到严重的争用。删除该缓存的操作使查询延迟大大提高了 5 到 10 倍。本质上，缓存拖慢了速度！

我们得出的结论是，Go 中的并发缓存缺失，我们必须自己实现一个。 3 月，我们写了关于 State of Caching in Go 的文章，提到数据库和系统需要智能且内存可控的缓存的问题，其中该缓存可以在 golang 这样的多线程环境中扩展。特别地，我们认为缓存应该满足：

1. 高并发
2. 高命中率
3. 内存可控（可配置的最大内存使用限制）
4. 随着核心和 goroutine 数量的增加，可以很好地扩展
5. 在非随机 key 访问分布（例如 Zipf）下可以很好地扩展。

发布博客文章后，我们成立了一个团队来解决其中提到的挑战，并创建了一个值得与非 Go 实现的缓存进行比较的 Go 缓存库。尤其是基于 Java 8 的 Caffeine，它是一个高性能，几乎是最佳的缓存库。它被许多基于 Java 的数据库使用，例如 Cassandra，HBase 和 Neo4j。有一篇关于 Caffeine 设计的 文章 。

从那以后，我们阅读了文献^{1, 2, 3}，实现也进行了广泛测试，并讨论了编写缓存库时要考虑的每个变量。今天，我们很自豪地宣布，它已经准备好供 Go 社区更广泛的使用和试验。

在我们开始解释 Ristretto 的设计之前，这里是一个代码片段，展示了如何使用它：

func main() {
    cache, err := ristretto.NewCache(&ristretto.Config{
        NumCounters: 1e7,     // Num keys to track frequency of (10M).
        MaxCost:     1 << 30, // Maximum cost of cache (1GB).
        BufferItems: 64,      // Number of keys per Get buffer.
    })
    if err != nil {
        panic(err)
    }

    cache.Set("key", "value", 1) // set a value
    // wait for value to pass through buffers
    time.Sleep(10 * time.Millisecond)

    value, found := cache.Get("key")
    if !found {
        panic("missing value")
    }
    fmt.Println(value)
    cache.Del("key")
}

Ristretto 建立在三个指导原则上：

1. 快速访问
2. 高并发和抗竞争性
3. 内存可控。

在此博客文章中，我们将讨论这三个原则以及如何在 Ristretto 中实现它们。

尽管我们喜欢 Go 及其在功能方面的坚定立场，但 Go 的某些设计决策阻止了我们挤出想要的所有性能。最值得注意的是 Go 的并发模型。由于对 CSP 的关注，大多数其他形式的原子操作都被忽略了。这使得难以实现在缓存库中有用的无锁结构。例如，Go 不提供线程本地存储。

缓存的核心是 hash map，其中包含有关进出的规则。如果 hash map 执行不佳，则整个缓存将受到影响。与 Java 不同，Go 没有无锁并发的 hash map。相反，Go 中的线程安全是通过显式获取互斥锁来实现的。

我们尝试了多种实现方式（使用 Ristretto 中的 store 接口），发现 sync.Map 对于读取繁重的工作负载表现良好，但对于写入工作负载则表现不佳。考虑到没有线程本地存储，我们发现分片（shared）互斥包装的 Go map 具有最佳的整体性能。特别是，我们选择使用 256 个分片（shared）以确保即使在 64 核服务器上也能很好地执行。

使用基于分片（shared）的方法，我们还需要找到一种快速的方法来计算 key 应放入哪个分片（shared）。这种要求以及对长 key 消耗过多内存的担忧，导致我们将 uint64 代表 key，而不是存储整个 key。这样做的理由是，我们需要在多个位置进行 key 的散列，在入口处执行一次散列即可使我们重新使用该散列，从而避免了任何其他计算。

为了生成快速哈希，我们从 Go Runtime 借用了 runtime.memhash 。此函数使用汇编代码快速生成哈希。请注意，哈希具有一个随机化器，该随机化器会在进程启动时进行初始化，这意味着相同的 key 在下一次进程运行时不会生成相同的哈希。但是，对于非永久性缓存来说，这没关系。在我们的实验中，我们发现它可以在 10ns 内散列 64 字节 key。

然后，我们不仅使用此哈希作为存储的 key，而且还弄清楚了 key 应放入的分片（shared）。这确实会带来 key 碰撞的机会，这是我们计划在以后处理的事情。

要实现高命中率，需要管理元数据，元数据和缓存中存在的内容以及缓存中应存在的内容有关。跨 goroutines 使得平衡缓存的性能和可伸缩性变得非常困难。幸运的是，有一篇名为 BP-Wrapper 的论文，它描述了一个系统框架，该框架使得任何替换算法几乎都可以无争用地锁定。论文介绍了两种缓解争用的方法：预取（prefetching） 和批处理(batching)。我们仅使用批处理。

批处理正是我们所需要的。与其为每个元数据改变获取互斥锁，不如在获取互斥锁并处理突变之前等待环形缓冲区填满。如该论文所述，这几乎没有开销，从而大大降低了竞争。

我们将此方法用于所有获取（Gets） 和设置（Sets） 缓存。

Ristretto 针对竞争性进行了优化。在繁重的并发负载下，这确实表现良好，我们将在下面的吞吐量基准中看到。但是，它将损失一些元数据以换取更好的吞吐量性能。

有趣的是，由于 key 访问分布的性质，信息丢失不会损害命中率。如果我们确实丢失了元数据，当 key 访问分布不统一是，命中率也会统一丢失（If we do lose metadata, it is generally lost uniformly while the key access distribution remains non-uniform. ）（译注：什么意思）。因此，如下图所示，我们仍然可以实现较高的命中率，并且命中率下降很小。

在我们将新 key 放入 TinyLFU 中之前，Ristretto 首先使用布隆过滤器（bloom filter）检查该 key 是否之前已被查看过。仅当 key 在布隆过滤器中已经存在时，才将其插入 TinyLFU。这是为了避免长时间不被看到的长尾 key 污染 TinyLFU。（译注：缓存穿透）

计算 key 的估值（ɛ） 时，如果该条目包含在布隆过滤器中，则其频率估值为 TinyLFU 的估值加 1。在重置 TinyLFU 的过程中，也会清除 Bloom 过滤器。

尽管是可选的，但了解缓存的行为方式是重要的。我们希望确保不仅可以实现与缓存相关的跟踪指标，而且这样做的开销也足够低，可以打开和保持打开状态。

除了命中和遗漏之外，Ristretto 还跟踪其他指标，例如 key 及其添加，更新和收回的成本，sets 丢失或拒绝以及 gets 丢失或保留的成本。所有这些数字有助于了解各种工作负载上的缓存行为，并为进一步优化铺平道路。

我们最初使用原子计数器。但开销很大。我们将原因归结为False Sharign 。考虑一个多核系统，其中不同的原子计数器（每个 8 字节）位于同一高速缓存行（通常为 64 字节）中。对这些计数器之一进行的任何更新都会导致其他计数器被标记为无效。这将强制为拥有该高速缓存的所有其他核心重新加载高速缓存，从而在高速缓存行上创建写争用。

为了实现可伸缩性，我们确保每个原子计数器完全占用完整的缓存行。因此，每个内核都在不同的缓存行上工作。 Ristretto 通过为每个度量分配 256 个 uint64 来使用此功能，在每个活动 uint64 之间保留 9 个未使用的 uint64。为了避免额外的计算，重新使用 key 哈希值以确定要增加的 uint64。

Add:
    valp := p.all[t]
    // Avoid false sharing by padding at least 64 bytes of space between two
    // atomic counters which would be incremented.
    idx := (hash % 25) * 10
    atomic.AddUint64(valp[idx], delta)

Read:
    valp := p.all[t]
    var total uint64
    for i := range valp {
        total += atomic.LoadUint64(valp[i])
    }
    return total

读取度量标准时，将读取并汇总所有 uint64，以获取最新数值。使用这种方法，指标跟踪仅会增加大约 10％的缓存性能开销。

既然您了解了 Ristretto 中存在的各种机制，那么让我们看一下与其他流行的 Go 缓存相比的命中率和吞吐量基准。

您可能已经在 CODASYL 基准测试中注意到，Ristretto 的性能在 LRU 繁重的工作负载中受到影响。但是，对于大多数工作负载而言，我们的 LFU 采样策略表现都很好。问题变成了“我们如何才能兼得两全”？

在名为“自适应软件缓存管理”的论文 中，探讨了这个确切的问题。基本思想是在主缓存段之前放置一个 LRU“窗口”，并使用爬山技术（hill-climbing）自适应地调整窗口大小，以使命中率最大化。Caffeine 已经取得了很好的效果。我们相信 Ristretto 将来也会从中受益。

我们衷心感谢本·马内斯。他的知识渊博和专心，无私的分享是我们取得任何进展的重要因素，我们很荣幸与他就缓存的所有内容进行了多次对话。如果没有他在我们内部 Slack 频道中的指导、支持和 99.9% availabilit，Ristretto 就是不可能的。

我们还要感谢 Damian Gryski 对 Ristretto 进行的基准测试和编写 TinyLFU 实现参考的帮助。

我们的目标是构建与 Caffeine 具有竞争力的缓存库。尽管还不够完善，但通过使用一些新技术，我们确实创造了明显比 Go 世界中大多数缓存更好的东西，其他人可以从中学习。

在 Dgraph 中使用此缓存的一些初步实验看起来很有希望。我们希望在接下来的几个月中将 Ristretto 集成到 Dgraph 和 Badger 中。请检查一下，也许可以使用 Ristretto 来加快工作量！