关于go:Ristretto-简介-一个高性能-GO-缓存

这个博客登上了 Golang subreddit 的顶部，并且在 Hacker News 的 trending 上排在前十位。肯定要在那里参加探讨，并通过给咱们一个 star，表白对咱们的喜爱。

通过六个月的研发，咱们骄傲的发表 缓存 Ristretto：一个高性能、并发、可设置内存下限的 Go 缓存 的初始版本。他是抗争用、扩展性好、提供稳固的高命中率。

前言

这所有都始于 Dgraph 中须要一个可设置内存下限的、并发的 Go 缓存。咱们四处寻找解决方案，然而没有找到一个适合的。而后咱们尝试应用分片 map，通过分片驱赶来开释内存，这导致了咱们的内存问题。而后咱们从新利用了 Groupcache 的 LRU, 用互斥锁保障线程平安。应用了一年之后，咱们留神到缓存存在重大的争用问题。一个 commit 删除了该缓存，使咱们的查问提早显著改善了 5-10 倍。实质上，咱们的缓存正在减慢咱们的速度!

咱们得出的论断是，Go 中的并发缓存库曾经坏了，必须修复。在三月, 咱们写了一篇对于 Go 中的缓存状态, 提到数据库和零碎须要一个智能的、可设置内存下限的缓存的问题，它能够扩大到 Go 程序所处的多线程环境。特地的，咱们将这些设置为缓存的要求：

1. 并发的；
2. 缓存命中率高；
3. Memory-bounded (限度为可配置的最大内存使用量)；
4. 随着核数和协程数量的减少而扩大；
5. 在非随机 key 拜访 (例如 Zipf) 散布下很好的扩大；

公布了博客文章之后，咱们组建了一个团队来解决其中提到的挑战，并创立了一个值得与非 Go 语言缓存实现进行比拟的 Go 缓存库。特地的，Caffeine 这是一个基于 Java 8 的高性能、近乎最优的缓存库。许多基于 Java 8 的数据库都在应用它, 比方 Cassandra，HBase，和 Neo4j。这里有一篇对于 Caffeine 设计的文章。

Ristretto: Better Half of Espresso

从那以后咱们浏览了文献, 宽泛的测试了实现，并探讨了在写一个缓存库时须要思考的每一个变量。明天，咱们骄傲的发表他曾经筹备好供更宽泛的 Go 社区应用和试验。

在咱们开始解说 Ristretto 的设计之前, 这有一个代码片段展现了如何应用它：

func main() {
cache, err := ristretto.NewCache(&ristretto.Config{
NumCounters: 1e7,     // key 跟踪频率为（10M）MaxCost:     1 << 30, // 缓存的最大老本 (1GB)。BufferItems: 64,      // 每个 Get buffer 的 key 数。})
if err != nil {panic(err)
}

cache.Set("key", "value", 1) // set a value
// 期待值通过 buffer
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 存储.

缓存的外围是一个 hash map 和对于进入和进来的规定。如果 hash map 体现不佳，那么整个缓存将受到影响。与 Java 不同, Go 没有无锁的并发 hashmap。相同，Go 的线程平安是必须通过显式获取互斥锁来达到。

咱们尝试了多种实现形式（应用 Ristretto 中的 store 接口），发现 sync.Map 在读取密集型工作负载方面体现良好，但在写入工作负载方面体现不佳。思考没有 thread-local 存储，咱们发现应用分片的互斥锁包装的 Go map 具备最佳的整体性能。 特地是，咱们抉择应用 256 个分片，以确保即便在 64 核服务器上也能体现良好。

应用基于分片的办法，咱们还须要找到一种疾速办法来计算 key 应该进入哪个分片。这个要求和对 key 太长耗费太多内存的担心，导致咱们对 key 应用 uint64，而不是存储整个 key。理由是咱们须要在多个中央应用 key 的哈希值，并且在入口处执行一次容许咱们重用该哈希值，防止任何更多的计算。

为了生成疾速 hash，咱们从 Go Runtime 借用了 runtime.memhash 该函数应用汇编代码疾速生成哈希。请留神，这个 hash 有一个随机化器，每当过程启动时都会初始化，这意味着雷同的 key 不会在下一次过程运行时生成雷同的哈希。然而，这对于非长久缓存来说没问题。在咱们的试验, 咱们发现它能够在 10ns 内散列 64 字节的 key。

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 应该进入的分片。_这个的确引入了 key 抵触的机会，这是咱们打算稍后解决的事件。_

并发和抗争用

实现高命中率须要治理无关缓存中，存在的内容以及缓存中应该存在的内容的元数据。当跨 goroutine 均衡缓存的性能和可扩展性时，这变得十分艰难。
侥幸的是，有一篇名为 BP-Wrapper 的论文写了一个零碎框架，能够使任何替换算法简直无锁争用。本文介绍了两种缓解争用的办法：预取和批处理。咱们只应用批处理。

批处理的工作形式与您设想的差不多。咱们不是为每个元数据变动获取互斥锁，而是期待 ring buffer 填满，而后再获取互斥锁并解决变动。如论文中所述，这大大降低了争用，而且开销很小。

咱们将此办法用于缓存的所有 Gets 和 Sets。

Gets

当然，所有对缓存的 Get 操作都会立刻失去服务。艰难的局部是捕捉 Get，因而咱们能够跟踪 key 拜访。在 LRU 缓存中，通常将 key 放在链表的头部。在咱们基于 LFU 的缓存中，咱们须要减少一个 item 的命中计数器。这两个操作都须要对缓存全局构造进行线程平安拜访。BP-Wrapper 倡议应用批处理来解决命中计数器增量，但问题是咱们如何在不获取另一个锁的状况下实现此批处理过程。

这听起来像是 Go chan 的完满用例，事实的确如此。可怜的是，chan 的吞吐量性能阻止了咱们应用它们。相同，咱们设计了一种奇妙的办法应用 sync.Pool 来实现条带化的有损 ring buffers，这些缓冲区具备杰出的性能并且简直没有数据失落。

存储在 pool 中的任何 item 都可能随时主动删除，不另行通知。_这引入了一个级别的有损行为。_ Pool 中的每个 item 实际上都是一批 key。当批次填满时，它会被推送到一个 chan。chan 大小成心放弃较小，以防止耗费太多 CPU 周期来解决它。如果 chan 已满，则抛弃该批次。_这引入了二级有损行为。_ 一个 goroutine 从外部 chan 中获取这批数据并解决这些 key，更新它们的命中计数器。

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

一旦 buffer 填满，push 到 chan:
  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、携带互斥锁等）的性能都好，次要是因为 thread-local 存储的外部应用，_这是 Go 用户无奈从公共 API 取得的货色。_

Sets

Set buffer 的要求与 Get 略有不同。在 Gets 中，咱们缓冲 key，只有在 buffer 填满后才解决它们。在 Sets 中，咱们心愿尽快解决 key。因而，咱们应用一个 chan 来捕捉 Set，如果 chan 已满则将它们丢掉以防止争用。几个后盾 goroutine 从 chan 中筛选 set 并解决 set。

与 Gets 一样，此办法旨在优化抗争用性。然而，有一些注意事项，如下所述。

select {case c.setBuf <- &item{key: hash, val: val, cost: cost}:
    return true
default:
    // 抛弃 set 操作并防止阻塞
    c.stats.Add(dropSets, hash, 1)
    return false
}

注意事项

Ristretto 中的 Set 进入 buffer 排队，控制权返回给调用者，而后将 buffer 利用于缓存。这有两个副作用：

1. 无奈保障会利用 Set 操作 它能够立刻删除以防止争用，也能够稍后被策略回绝。
2. 即便利用了 Set，在调用返回给用户后也可能须要几毫秒。用数据库术语来说，它是一个 最终的一致性 模型。

然而，如果缓存中已存在密钥，则 Set 将立刻更新该密钥。这是为了防止缓存的 key 保留过期的值。

抗争用

Ristretto 针对抗争用进行了优化。这在高并发负载下体现十分好，正如咱们将在上面的吞吐量基准测试中看到的那样。然而，它会失落一些元数据以换取更好的吞吐量性能。

乏味的是，因为密钥拜访散布的性质，信息失落不会影响咱们的命中率性能。如果咱们的确失落了元数据，它通常会平均失落，而密钥拜访散布依然是不平均的。因而，咱们依然实现了高命中率，并且命中率降落很小，如下图所示。

可设置内存下限

Key 老本

无限大的缓存实际上是不可能的。 缓存的大小必须有界。许多缓存库会将缓存大小视为元素的数量。咱们发现这种办法 _很童稚_。当然，它实用于值大小雷同的工作负载。然而，大多数工作负载具备可变大小的值。一个值可能须要几个字节，另一个可能须要几千字节，还有一个须要几兆字节。将它们视为具备雷同的内存老本是不事实的。

在 Ristretto 中, 咱们将老本附加到每个 key-value 用户能够在调用 Set 时指定该老本是多少。咱们将此老本计入缓存的 MaxCost。当缓存满负荷运行时，一个 重 的 item 可能会取代许多 轻 的 item。这种机制很好，因为它实用于所有不同的工作负载，包含每个 key-value 老本为 1 的奢侈办法。

通过 TinyLFU 的准入策略

”咱们应该让什么进入缓存？“

显然，咱们的指标是让比以后 item 更 “有价值” 的新 item 进入。然而，如果您思考跟踪相干 item 的与 “价值” 问题无关的信息所需的开销（提早和内存），这将成为一个挑战。

只管这是一个有据可查的进步命中率的策略，但大多数 Go 缓存库基本没有准入策略。事实上，许多 LRU 驱赶实现都假设最新的密钥是最有价值的。

此外，大多数 Go 缓存库应用纯 LRU 或 LRU 的近似值作为它们的驱赶策略。只管 LRU 近似的品质很高，但某些工作负载更适宜 LFU 逐出策略。咱们在应用各种跟踪的基准测试中发现了这种状况。

对于咱们的准入政策，咱们看了一篇引人入胜的新论文名为 TinyLFU: 一个高效的缓存准入策略 在十分高的档次上，TinyLFU 提供了三种办法：

• Increment(key uint64)
• Estimate(key uint64) int (referred as ɛ)
• Reset

该论文对其进行了最好的解释，但 TinyLFU 是一种与逐出无关的准入策略，旨在以极少的内存开销进步命中率。次要思维是 只有当新 item 的估计值高于被驱赶 item 的估计值时，才容许新 item 进入。咱们应用 Count-Min 在 Ristretto 中实现了 TinyLFU。它应用 4 位计数器来估算 item (ɛ) 的拜访频率。每个 key 的这种小老本，使咱们可能跟踪比应用一般的频率 map，更大的全局 key 空间里的样本。

TinyLFU 还通过 重置 性能保护 key 拜访的早先度。每 N 个 key 递增后，计数器减半。因而，一个很久没有呈现的 key，其计数器将被重置为零；为最近呈现的 key 铺平道路。

通过采样 LFU 的驱赶策略

当缓存达到容量时，每个传入的 key 都应替换缓存中存在的一个或多个 key。不仅如此，传入 key 的 ε 应该高于被驱赶 key 的 ε。为了找到一个 ε 低的 key，咱们应用 Go map 迭代提供的天然随机性来抉择 key 样本并循环，在它们之上找到具备最低 ε 的 key。

而后咱们将这个 key 的 ɛ 与传入的 key 进行比拟。如果传入的 key 具备更高的 ε，则该 key 将被逐出（_驱赶策略_）。否则，传入的 key 将被回绝（_准入策略_）。反复此机制，直到传入 key 的老本能够放入缓存中。因而，一个传入的 key 可能取代一个以上的 key。_留神，传入 key 的老本在抉择驱赶 key 时不起作用。_

应用这种办法，在各种工作负载下，命中率与准确 LFU 策略的误差在 1% 以内。 这意味着咱们在同一个包中取得了准入策略、激进内存应用和较低争用的益处。

// 准入和驱赶算法的片段
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)
}

DoorKeeper

在咱们将新 key 放入 TinyLFU 之前，Ristretto 应用布隆过滤器首先查看该 key 是否曾被见过。只有当该 key 曾经存在于布隆过滤器中时，它才会被插入到 TinyLFU 中。这是为了防止 TinyLFU 被那些不被屡次看到的长尾 key 所 _净化_。

在计算一个 key 的 ε 时，如果 item 蕴含在 bloom filter 中，它的频率预计就是 TinyLFU 的 Estimate 加一。在 TinyLFU重置 期间，布隆过滤器也被革除。

Metrics

尽管是可选的，但理解缓存的行为形式是很重要的。咱们心愿确保跟踪与缓存相干的指标不仅是可能的，而且这样做的开销足够低，能够关上并放弃。

除了命中和未命中，Ristretto 还追踪一些指标，如增加、更新和逐出的 key 及其老本，set 操作被抛弃或回绝，以及 get 操作抛弃或保留的次数。所有这些数字有助于理解各种工作负载下的缓存行为，并且为了进一步优化铺平道路。

咱们最后为这些应用原子计数器。然而，开销是微小的。咱们把起因放大到 False Sharing。思考多核零碎，其中不同的原子计数器 (每个 8 字节) 位于对立 cache line（通常为 64 字节）。任何更新扭转计数器，都会导致其余计数器被标记 _有效_。这会强制为持有该缓存的所有其余外围从新加载缓存，从而在 cache line 上产生写入争用。

为了实现可扩展性，咱们确保每个原子计数器齐全占据一个残缺的 cache line。所以，每个核在不同的 cache line 上工作。Ristretto 通过为每个 metric 调配 256 个 uint64 来应用它，在每个流动的 uint64 之间留下 9 个未应用的 uint 64。为了防止额定的计算，重用 key hash 值去决定要减少哪个 uint64。

Add:
valp := p.all[t]
// 通过在两个将递增的原子计数器之间填充至多 64 字节的空间来防止 false sharing。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 并求和，以获取最新的数字。应用这种办法，metrics 跟踪只对缓存性能增加 10% 左右的开销。

Benchmarks

当初你理解了 Ristretto 中存在的各种各样的机制，让咱们看看与其余风行的 Go 缓存相比的命中率和吞吐量 benchmark。

命中率

命中率是应用 Damian Gryski 的 cachetest 和咱们本人的 benchmarking 套件测量的. 两个程序的命中率数字雷同，但咱们增加了读取某些 trace 格局 (特地是 LIRS and ARC)以及 CSV 输入的性能，以便于绘制图表。如果你想编写本人的 benchmark 或者增加一种 trace 格局，请查看 sim 包。

为了更好地理解改良空间，咱们增加了一个实践上最佳的缓存实现, 它应用将来的常识来驱赶在其的整个生命周期内命中次数起码的. 留神这是一个能预感将来的 LFU 驱赶策略，其余能预感将来的策略可能用 LRU。依据工作负载，LFU 或 LRU 可能更适宜，但咱们发现能预感将来的 LFU 对于与 Ristretto 的 Sampled LFU 进行比拟很有用。

查找

这个 trace 被形容为“由大型商业搜索引擎发动的磁盘读取拜访，以响应各种网络搜寻申请”

数据库

这个 trace 被形容为“在一个商业数据库上，一个商业网站正运行一个 ERP 利用，一个数据库服务运行在下面“

循环

这个 trace 演示了循环拜访模式。咱们不能在此和后续的 benchmark 中包含 Fastcache、Freecache 或 Bigcache 实现，因为它们具备会影响后果的最低容量要求。一些跟踪文件很小并且须要小容量来进行性能测量。

CODASYL

这个 trace 被形容为”在一小时内援用 CODASYL 数据库。“请留神与这里的其余库相比 Ristretto 的性能受到影响。这是因为 LFU 逐出策略不适宜此工作负载。

吞吐量

吞吐量是应用与上一篇博文雷同程序测量的，该程序会生成大量 key，并依据设置的工作负载在 Get 和 Set 的 goroutine 之间交替。

所有吞吐量基准测试均在具备 16gb RAM 的英特尔酷睿 i7-8700K (3.7GHz) 上运行。

混合: 25% Writes, 75% Reads

读取: 100% Reads

写入: 100% Writes

将来的改良

正如您可能曾经在 CODASYL benchmark 中留神到的那样，Ristretto 的性能在 LRU 沉重的工作负载中受到影响. 然而，对于大多数工作负载，咱们的 Sampled LFU 策略体现相当好。这个问题就变成了“咱们怎么能两败俱伤”

在一篇名为 Adaptive Software Cache Management 的论文 , 探讨了这个确切的问题. 这个根本思维是在主缓存片段之前搁置一个 LRU 窗口，并且应用爬山（hill-climbing）技术自适应地调整该窗口的大小以最大化命中率。Caffeine 曾经通过这个看到了重大的后果。咱们置信 Ristretto 未来也能从中收益。

特别感谢

咱们诚挚的感激 Ben Manes。他的常识深度和专一,、自私的分享是咱们获得任何提高的重要隐衷，咱们很荣幸能与他就缓存的所有方面进行对话。没有他的领导、反对和咱们外部 Slack 频道 99.9% 的可用性，Ristretto 是不可能的。

咱们还要感激 Damian Gryski 在对 Ristretto 进行基准测试和编写参考 TinyLFU 实现方面提供的帮忙。

论断

咱们的指标是让缓存库与 Caffeine 竞争。尽管没有齐全实现, 但咱们的确通过应用其他人能够学习的一些新技术，发明了比目前 Go 世界中大多数其他人 更好 的货色。
在 Dgraph 中应用此缓存的一些初步试验看起来很有心愿。并且咱们心愿将 Ristretto 整合到 Dgraph 和 Badger 在接下来的几个月里. 肯定要查看它，兴许能够应用 Ristretto 来放慢您的工作负载。