Fly

温故而知新

首页 归档 标签 关于

Ristretto -- 高性能Go Cache

2021-12-20 17 min read

前言

故事开始于我们的Github项目Dgraph 中需要一个内存受限、支持并发的 Go 缓存库。我们四处寻找但没有找到一个很好的解决方案。随后我们尝试使用基于分片的HashMap，通过每个分片独立的淘汰策略来释放内存，这引发了一些内存问题。然后我们启用了 Groupcache 的LRU，它使用互斥锁来保证线程安全。使用一年后，我们注意到这个缓存库的锁冲突情况比较严重。有一次，我们提了Commit从代码中去掉这个缓存，结果令查询性能提高了5-10倍。也就是说**，我们的缓存反而拖累了我们！**

我们得出结论，在Go的生态中，支持并发操作的缓存不完整的，需要被尽快补充完整。三月，我们写了关于Go 缓存状态的文章，提到了数据库和系统需要一个智能的、内存受限的缓存，该缓存可以扩展到 Go 程序所处的多线程环境。我们给这个缓存库提出了如下的要求：

  1. 支持并发操作
  2. 高缓存命中率
  3. 内存受限（限制为配置文件中指定的最大内存使用量）
  4. 随着CPU核心数和Goroutine数的增加，具有很好的扩展性
  5. 在非随机Key访问分布下（例如 Zipf）下，具有很好的扩展性

发布博文后，我们组建了一个团队来解决其中提到的挑战，并创建了一个值得与非 Go 缓存实现进行比较的 Go 缓存。值得一提的是Caffeine，它是一个基于 Java 8 的高性能、近乎最优的缓存库。许多基于 Java 的数据库都在使用它，例如 Cassandra、HBase 和 Neo4j。关于Caffeine的设计文章可以查看这里。

Ristretto：更好的浓缩咖啡

从那以后，我们阅读文献、广泛测试了各种Cache实现，并讨论了在编写缓存库时需要考虑的方方面面。今天，我们自豪地宣布，它已经准备好被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 不提供线程本地存储（Thread-Local）。

从本质上讲，Cache就是简单的HashMap，同时包含一些关于数据准入和淘汰的规则。如果HashMap性能表现不佳，那么整个Cache都会受到影响。与 Java 不同，Go 没有ConcurrentHashMap这种东西（大意是分段加锁，降低锁冲突）。相反，Go 中的线程安全是通过显式的获取互斥锁来实现的。

我们尝试了多种实现，发现sync.Map在频繁的Read操作负载下表现良好，但在Write操作负载时表现不佳。考虑到没有Thread-Local 存储， 我们发现分片且带有互斥锁的 Go Map 具有最佳的整体性能。 我们选择使用 256 个分片以确保即使在 64 核服务器上也可以获得很好的表现。

要想使用这种基于分片的方式，我们还需要找到一种方法快速计算Hash应该进入哪个分片。这样的需求，以及担心Long Key（比较大的Key值）会消耗过多内存，我们决定对Key使用uint64代替，而不是存储整个Key。基本原理是在入口处对Key执行一次Hash计算，这个Hash值允许在后面的多处使用，避免更多计算。

为了快速生成Hash，我们从 Go Runtime借用了runtime.memhash。 该函数使用汇编代码快速生成哈希。它在进程启动时会初始化一个随机数发生器，这意味着相同的Key可能在下一次进程启动时生成不同的Hash值。不过这对于非持久性缓存来说是没问题的。在我们的实验中，我们发现它可以在 10ns 内散列 64 字节的密钥。

BenchmarkMemHash-32 200000000	 8.88 ns/op
BenchmarkFarm-32    100000000	 17.9 ns/op
BenchmarkSip-32      30000000	 41.1 ns/op
BenchmarkFnv-32      20000000	 70.6 ns/op

我们不仅将这个Hash用作存储的Key，而且还用于确定Key应该进入的分片。这带来了Hash冲突的可能，在接下来的文章中我们会讲解如何解决它。

支持并发和抗争用

实现高命中率需要管理一些元数据，这些元数据用来表示Cache中当前存在哪些数据，以及Cache中应该存在哪些数据。支持多Goroutine的Cache中，平衡缓存的性能和可扩展性变得非常困难。幸运的是，有一篇名为BP-Wrapper的论文写了一个系统框架，使任何替换算法几乎无锁争用。该论文描述了两种缓解争用的方法：预取和 批处理 。我们只使用批处理。

批处理的工作方式和你想象的非常相似。 它不是为每次的元数据变化获取互斥锁，而是先等待RingBuffer填满，再去获取互斥锁处理元数据的变化。 正如论文中所述，这大大降低了锁冲突，而且开销很小。

我们在所有的Get操作和更新到缓存中的Set操作上使用了这种思想。

Get请求

当然，所有Get请求都会立即得到响应（不需要等待缓冲区填满）。我们只是用来统计Get操作的次数，因此必须追踪对Key的访问。在 LRU 缓存中，通常将Key放置在链表的头部。在基于 LFU 的缓存中，我们需要增加Key的命中计数器。这两个操作都需要对Cache的全局结构进行访问，而且必须是线程安全的。BP-Wrapper建议使用批处理来处理Key的命中计数器，但问题是我们如何在不获取另一个锁的情况下实现这个批处理过程。

这听起来像是 Go Channel的完美应用，确实如此。不幸的是，通道的吞吐量性能太低阻碍了我们的使用。 我们设计使用sync.Pool实现来条带化的，但有损环形缓冲区 ，该缓冲区具有出色的性能且数据丢失很少。

存储在Pool中的任何数据可能会随时自动删除，而没有任何通知。这个操作导致了一级有损行为*。* Pool 中的每一项实际上都是一批Key。当批次填满时，它会被推送到一个Channel。Channel大小故意保持较小，以避免消耗太多 CPU 周期来处理它。如果通道已满，则丢弃该批次。  这引入了二级有损行为。 一个 Goroutine 从Channel中获取并处理这批Key，更新它们的命中计数器。

AddToLossyBuffer(key):
  stripe := b.pool.Get().(*ringStripe)
  stripe.Push(key)
  b.pool.Put(stripe)

Once buffer fills up, push to channel:
  select {
  case p.itemsCh <- keys:
      p.stats.Add(keepGets, keys[0], uint64(len(keys)))
      return true
  default:
      p.stats.Add(dropGets, keys[0], uint64(len(keys)))
      return false
  }

p.itemCh processing:
  func (p *tinyLFU) Push(keys []uint64) {
    for _, key := range keys {
      p.Increment(key)
    }
  }

使用sync.Pool优于其他任何东西（slice、striped mutexes等）, 由于是Thread-Local存储的内部使用，所以会有这么大的性能优势。这些东西不能作为公共 API 提供给 Go 用户。

Set操作

Set 缓冲区的要求与 Get 略有不同。在 Gets 中，我们只缓冲Key，只有在缓冲区填满后才处理它们。在 Sets 中，我们希望尽快处理这些Key。 因此，我们使用一个通道来捕获 Sets，如果通道已满，则丢弃它们上以避免争用。 几个后台 Goroutines 从Channel中取回并且处理Set操作。

这种方法与 Gets 一样，旨在优化抗争用。但是，有一些注意事项，如下所述。

select {
case c.setBuf <- &item{key: hash, val: val, cost: cost}:
    return true
default:
    // drop the set and avoid blocking
    c.stats.Add(dropSets, hash, 1)
    return false
}

注意事项

Ristretto中的Set操作排队进入Buffer，控制权返回给调用者，然后Buffer被应用到缓存中。这有两个副作用：

  1. 一次Set操作不保证一定会为apply。 可能立即放弃以避免争用，也可以稍后被策略拒绝。
  2. 即使Apply了 Set操作，调用返回给用户后也可能需要几毫秒的时间。在数据库术语中，它是一种最终一致性 模型。

但是，如果缓存中已经存在该Key，则 Set 将立即更新Key。这是为了避免缓存的Key保存过时的值。

降低锁冲突

Ristretto 针对降低锁冲突进行了优化。 这在高并发负载下表现非常好，我们将在下面的吞吐量Benchmark中看到。但是，它会丢失一些元数据以换取更好的吞吐量性能。

有趣的是，由于Hash访问分布的性质，信息丢失并不会影响我们的命中率性能。如果我们确实丢失了元数据，它通常会均匀丢失，而密钥访问分布仍然不均匀。因此，我们仍然实现了高命中率，并且命中率下降很小，如下图所示。

Ristretto 命中率下降

内存受限

Key的成本

不可能存在无限大的缓存*。* 缓存必须有大小限制。许多缓存库将缓存大小视为元素的数量。我们发现这种方法是不成熟的 。当然，它适用于值大小相同的负载。但是，大多数情况下负载值的大小并不确定。一个值占用的空间可能是Bytes、KB或者MB。将他们视为消耗相同的内存成本是不合理的。

在Ristretto 中，我们为每个键值附加一个成本的概念。 用户可以在调用 Set 时指定成本是多少。我们根据缓存的MaxCost配置项计算此成本。当Cache满负荷运行时，一个占用内存大的数据可能会取代许多占用内存少的数据。这是一种很好的机制，因为它适用于不同的工作负载，包括每个Key-Value成本为 1 的简单方法。

TinyLFU 准入策略

“应该让什么样的数据进入Cache？”

这个答案应该有准入策略给出。显而易见的是，我们想要实现的目标是，新数据的进入比旧数据更 “有价值” 。然而，如何跟踪与 “价值” 问题相关的这些数据信息所需的开销（延迟和内存），这将成为一个挑战。

虽然准入策略可以提高Cache命中率，但大多数 Go 缓存库根本没有提供准入策略。许多 LRU 淘汰策略的实现假设最新的Key是最有价值的。

此外，大多数 Go 缓存库使用纯 LRU 或 LRU 的变种作为其淘汰策略。尽管 LRU算法的情况不错，但某些工作负载更适合 LFU 淘汰策略。我们使用各种各样的追踪手段在基准测试中证实了这一点。

对于我们的准入策略，我们阅读了**TinyLFU 的**这篇引人入胜的新论文 ：一种高效的缓存准入策略。TinyLFU 提供了三个方法：

  • Incremenmt
  • Estimate(key uint64) int（简称ɛ）
  • Reset

该论文做了很好的解释，但 TinyLFU 是一种与淘汰策略无关的策略，旨在以很少的内存开销提高命中率。主要思想是 仅在新数据的估计值高于被淘汰数据的估计值时才让其进入。 我们 使用Count-Min Sketch在Ristretto 中实现了 TinyLFU 。它使用 4 位计数器来估算项目的访问频率 (ɛ)。每个键的这种小成本使我们能够跟踪全局键空间的更大样本，这比使用普通键到频率映射可能实现的要大得多。

TinyLFU 还通过Reset函数维护Key访问的新近度。在 N 个Key递增后，计数器减半。因此，一段时间未看到的Key会将其计数器重置为零；为最近看到的Key铺平了道路。

Simpled LFU 淘汰策略

当缓存达到容量时，每个传入的Key都可能替换缓存中存在的一个或多个键。不仅如此， 传入key的ɛ应该高于被驱逐的key的ɛ。 为了找到具有低 ɛ 的键，我们使用Go Map迭代器提供的自然 随机性来选择Key样本并循环它们以找到具有最低 ɛ 的键。

然后我们将这个Kye的 ɛ 与传入的Key进行比较。如果传入的密钥具有更高的 ɛ，则该Key将被淘汰（ 淘汰策略 ）。否则，传入的Key将被拒绝（ 准入策略 ）。重复此机制，直到传入Key的成本可以放入缓存中。因此，单个传入Key可能会取代多个Key。请注意，传入Key的成本不会影响选择淘汰Key的因素。

使用这种方法，对于各种工作负载，命中率在准确 LFU 策略的 1% 以内。 这意味着我们在同一个小包中获得了准入策略、保守的内存使用和更低的争用的好处。

// Snippet from the Admission and Eviction Algorithm
incHits := p.admit.Estimate(key)
for ; room < 0; room = p.evict.roomLeft(cost) {
    sample = p.evict.fillSample(sample)
    minKey, minHits, minId := uint64(0), int64(math.MaxInt64), 0
    for i, pair := range sample {
        if hits := p.admit.Estimate(pair.key); hits < minHits {
            minKey, minHits, minId = pair.key, hits, i
        }
    }
    if incHits < minHits {
        p.stats.Add(rejectSets, key, 1)
        return victims, false
    }
    p.evict.del(minKey)
    sample[minId] = sample[len(sample)-1]
    sample = sample[:len(sample)-1]
    victims = append(victims, minKey)
}

守门员

在我们在 TinyLFU 中放置新Key之前，Ristretto使用布隆过滤器首先检查该密钥之前是否被看到过。只有当密钥已经存在于布隆过滤器中时，它才会被插入到 TinyLFU 中。这是为了避免使用不 多次出现的长尾键污染TinyLFU。

在计算一个键的ɛ时，如果该项目包含在布隆过滤器中，则其频率估计为来自 TinyLFU 的估计值加一。在ResetTinyLFU期间 ，布隆过滤器也被清除。

指标

这是一个可选的配置项，但对于了解缓存的行为方式很重要。我们希望确保与缓存相关的跟踪指标不仅是可能的，而且这样做的开销足够低，可以打开和保持。

除了命中和未命中之外，Ristretto 还跟踪诸如Key及其Cost被添加、更新和淘汰、Set操作被丢弃或拒绝以及被丢弃或保留等指标。所有这些数字都有助于了解各种工作负载上的缓存行为，并为进一步优化铺平道路。

我们最初为这些使用原子计数器。但是，开销很大。我们将原因定位到False Sharing。在一个多核系统只不过，其中不同的原子计数器（每个 8 字节）位于同一Cache line（通常为 64 字节）中。对这些计数器之一进行的任何更新都会导致其他计数器被标记为 invalid 。这会强制为所有其他持有该缓存的内核重新加载缓存，从而在缓存行上产生写入争用。

为了实现可扩展性，我们确保每个原子计数器完全占用一个完整的Cache line。 因此，每个内核都在不同的缓存行上工作。Ristretto 通过为每个Metrics分配 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

读取metric时，读取所有的uint64s并求和得到最新的数字。使用这种方法，指标跟踪只会为缓存性能增加大约 10% 的开销。

Powered by CHEN RSS