在 Go 中编写一个包含数百万条目的非常快速的缓存服务

最近，我们团队的任务是编写一个非常快速的缓存服务。目标非常明确，但可以通过多种方式实现。最后，我们决定尝试一些新的东西并在Go中实现该服务。我们已经描述了我们是如何做到的，以及从中获得了什么价值。

目录：

  1. 要求
  2. 为什么是Go？
  3. 缓存
    1. 并发
    2. 驱逐
    3. 省略垃圾收集器
    4. BigCache
  4. HTTP 服务器
  5. JSON反序列化
  6. 最终结果
  7. 概括

要求

根据要求，我们的服务应该：

  • 使用 HTTP 协议处理请求
  • 处理 10k rps（写入 5k，读取 5k）
  • 缓存条目至少 10 分钟
  • 响应时间（在没有花费在网络上的时间的情况下测量）低于
    • 5ms – 平均值
    • 第 99.9 个百分位数为 10 毫秒
    • 第 99.999 个百分位数为 400 毫秒
  • 处理包含 JSON 消息的 POST 请求，其中每条消息：
    • 包含一个条目及其 ID
    • 不大于 500 字节
  • 在通过 POST 请求添加条目后立即通过 GET 请求检索条目并返回 int（一致性）

简单来说，我们的任务是编写一个带有过期和 REST 接口的快速字典。

为什么是Go？

我们公司的大多数微服务都是用 Java 或其他基于 JVM 的语言编写的，有些是用 Python 编写的。我们也有一个用 PHP 编写的单一的遗留平台，但除非必须，否则我们不会触及它。我们已经知道这些技术，但我们愿意探索一种新的技术。我们的任务可以用任何语言实现，因此我们决定用 Go 编写它。

在一家大公司和不断增长的用户社区的支持下，Go 已经推出了一段时间。它被宣传为一种编译的、并发的、命令式的、结构化的编程语言。它还具有托管内存，因此看起来比 C/C++ 更安全、更易于使用。我们对用 Go 编写的工具有很好的经验，并决定在这里使用它。我们在 Go 中有一个开源项目，现在我们想知道 Go 是如何处理大流量的。我们相信整个项目只需不到 100 行代码，而且速度足以满足我们的要求，仅仅因为 Go。

缓存

为了满足要求，缓存本身需要：

  • 即使有数百万个条目也非常快
  • 提供并发访问
  • 在预定的时间后驱逐条目

考虑到第一点，我们决定放弃Redis、Memcached或Couchbase等外部缓存，主要是因为网络上需要额外的时间。因此，我们专注于内存缓存。在 Go 中已经有这种类型的缓存，即LRU 组 cache、 go-cache、ttlcache、freecache。只有 freecache 满足了我们的需求。接下来的子章节揭示了为什么我们决定推出自己的产品，并描述上述特性是如何实现的。

并发

我们的服务会同时接收许多请求，因此我们需要提供对缓存的并发访问。实现这一点的简单方法是将sync.RWMutex放在缓存访问函数前面，以确保一次只有一个 goroutine 可以修改它。然而，其他也想对其进行修改的goroutine将被阻止，使其成为瓶颈。为了消除这个问题，可以应用分片。分片背后的想法很简单。创建了 N 个分片的数组，每个分片都包含自己的带有锁的缓存实例。当需要缓存具有唯一键的项目时，首先由函数hash(key) % N选择它的分片. 在获得缓存锁并写入缓存之后。项目读取是模拟的。当分片的数量相对较高并且散列函数返回正确分布的唯一键数字时，可以将锁争用降到几乎为零。这就是我们决定在缓存中使用分片的原因。

驱逐

从缓存中逐出元素的最简单方法是将其与FIFO队列一起使用。当一个条目被添加到缓存中时，会发生两个额外的操作：

  1. 在队列末尾添加一个包含键和创建时间戳的条目。
  2. 从队列中读取最旧的元素。它的创建时间戳与当前时间进行比较。当它晚于驱逐时间时，队列中的元素连同其在缓存中的相应条目一起被删除。

由于已获得锁，因此在写入缓存期间执行驱逐。

省略垃圾收集器

在 Go 中，如果你有一个映射，垃圾收集器 (GC) 将在标记和扫描阶段接触该映射的每个项目。当map足够大（包含数百万个对象）时，这可能会对应用程序性能产生巨大影响。

我们对我们的服务进行了一些测试，其中我们向缓存提供了数百万个条目，然后我们开始向一些不相关的 REST 端点发送请求，这些端点只进行静态 JSON 序列化（它根本没有触及缓存）。对于空缓存，此端点对于 10k rps 的最大响应延迟为 10 毫秒。当缓存被填满时，它在第 99 个百分位有超过一秒的延迟。指标表明堆中有超过 4000 万个对象，GC 标记和扫描阶段耗时超过 4 秒。测试表明，如果我们想满足与响应时间相关的要求，我们需要跳过缓存条目的 GC。我们怎么能这样做？嗯，有三个选择。

GC 仅限于堆，所以第一个是堆外。有一个项目可以帮助解决这个问题，称为offheap。它提供自定义函数Malloc()和Free()管理堆外的内存。但是，需要实现依赖于这些功能的缓存。

第二种方法是使用freecache。Freecache 通过减少指针数量来实现零 GC 开销的 map。它将键和值保存在环形缓冲区中，并使用索引切片来查找条目。

第三种为缓存条目省略 GC 的方法与 Go 版本 1.5 ( issue-9477 ) 中的优化有关。这种优化表明，如果您在键和值中使用没有指针的映射，那么 GC 将忽略它的内容。这是一种留在堆上并为映射中的条目省略 GC 的方法。然而，这并不是最终的解决方案，因为基本上 Go 中的一切都是建立在指针之上的：结构体、切片，甚至是固定数组。只有 int 或 bool 等基元不接触指针。那么我们可以用map[int]int做什么呢？由于我们已经生成了散列键以便从缓存中选择正确的分片（在并发中描述），我们将重用它们作为我们的map[int]int. 但是类型int的值呢? 我们可以保留哪些信息像int？我们可以保留条目的偏移量。另一个问题是这些条目可以保存在哪里以便再次省略 GC？可以分配大量字节，并且可以将条目序列化为字节并保存在其中。在这方面， 来自map[int]int的值可以指向一个偏移量，其中条目在建议的数组中具有其开始的位置。并且由于 FIFO 队列用于保存条目并控制它们的驱逐（在Eviction中描述），它可以被重建并基于一个巨大的字节数组，该映射中的值也将指向该数组。

在所有呈现的场景中，都需要输入（反）序列化。最终，我们决定尝试第三种解决方案，因为我们很好奇它是否可以工作，并且我们已经拥有了大多数元素——散列键（在分片选择阶段计算）和条目队列。

BigCache

为了满足本章开头提出的要求，我们实现了自己的缓存并将其命名为 BigCache。BigCache 提供分片、驱逐，并且它省略了缓存条目的 GC。因此，即使对于大量条目，它也是非常快速的缓存。

Freecache 是 Go 中唯一提供这种功能的可用内存缓存之一。Bigcache 是它的另一种解决方案，并以不同的方式减少 GC 开销，因此我们决定与它共享：bigcache。有关 freecache 和 bigcache 之间比较的更多信息可以在github上找到。

HTTP 服务器

内存分析器向我们展示了在请求处理期间分配了一些对象。我们知道 HTTP 处理程序将成为我们系统的热点。我们的 API 非常简单。我们只接受 POST 和 GET 从缓存上传和下载元素。我们有效地仅支持一个 URL 模板，因此不需要功能齐全的路由器。我们通过剪切前 7 个字母从 URL 中提取了 ID，它对我们来说很好用。

当我们开始开发时，Go 1.6 是在 RC 中。我们减少请求处理时间的第一个努力是更新到最新的 RC 版本。在我们的案例中，性能几乎相同。我们开始寻找更高效的东西，我们找到了 fasthttp。它是一个提供零分配 HTTP 服务器的库。根据文档，在综合测试中，它往往比标准 HTTP 处理程序快 10 倍。在我们的测试中，结果证明它只快了 1.5 倍，但仍然更好！

fasthttp 通过减少 HTTP Go 包完成的工作来实现其性能。例如：

  • 它将请求生命周期限制为实际处理的时间
  • 标头被延迟解析（我们真的不需要标头）

不幸的是，fasthttp 并不是标准 http 的真正替代品。它不支持路由或 HTTP/2，并声称不能支持所有 HTTP 边缘情况。它适用于具有简单 API 的小型项目，因此对于普通（非超高性能）项目，我们将坚持使用默认 HTTP。

fasthttp 与 nethttp

JSON反序列化

在分析我们的应用程序时，我们发现该程序在 JSON 反序列化上花费了大量时间。内存分析器还报告说，json.Marshal.处理了大量数据。这并不让我们感到惊讶。对于 10k rps，每个请求 350 字节可能是任何应用程序的重要负载。尽管如此，我们的目标是速度，所以我们对其进行了调查。

我们听说 Go JSON 序列化器没有其他语言那么快。大多数基准测试都是在 2013 年完成的，所以在 1.3 版本之前。当我们看到issue-5683声称 Go 比 Python 慢 3 倍并且 邮件列表说它比 Python simplejson慢 5 倍时，我们开始寻找更好的解决方案。

如果您需要速度，JSON over HTTP 绝对不是最佳选择。不幸的是，我们所有的服务都使用 JSON 相互通信，因此合并一个新协议超出了这项任务的范围（但我们正在考虑使用avro，就像我们为Kafka所做的那样）。我们决定坚持使用 JSON。快速搜索为我们提供了一个名为ffjson的解决方案。

ffjson 文档声称它比标准json.Unmarshal快 2-3 倍，并且使用更少的内存来做到这一点。

json 16154 纳秒/操作 1875 年 B / 作品 37 分配/操作
ffjson 8417 纳秒/运算 1555 B / 操作 31 分配/操作

我们的测试证实 ffjson 比内置解组器快近 2 倍并且执行的分配更少。怎么可能做到这一点？

首先，为了从 ffjson 的所有特性中受益，我们需要为我们的结构生成一个解组器。生成的代码实际上是一个解析器，它扫描字节并用数据填充对象。如果您看一下JSON 语法，您会发现它非常简单。ffjson 利用准确了解结构的优势，仅解析结构中指定的字段，并在发生错误时快速失败。标准封送拆收器使用昂贵的反射调用在运行时获取结构定义。另一个优化是减少不必要的错误检查。json.Unmarshal执行更少的分配和跳过反射调用会更快失败。

json（无效的 json） 1027 纳秒/运算 384 B / 作品 9个分配/操作
ffjson（无效的 json） 2598 纳秒/运算 528 B / 操作 13 个分配/操作

更多关于 ffjson 如何工作的信息可以在这里找到。基准可在此处获得

最终结果

最后，我们将应用程序的最长请求时间从超过 2.5 秒加快到不到 250 毫秒。这些时间只发生在我们的用例中。我们相信，对于更多的写入或更长的驱逐周期，访问标准缓存可能需要更多时间，但使用 bigcache 或 freecache 可以保持在毫秒级别，因为消除了长时间 GC 暂停的根源。

下图比较了我们服务优化前后的响应时间。在测试期间，我们发送了 10k rps，其中 5k 用于写入，另外 5k 用于读取。驱逐时间设置为 10 分钟。测试时间为 35 分钟。

优化前后的响应时间

最终结果是孤立的，设置与上述相同。

最终结果

概括

如果您不需要高性能，请坚持使用标准库。它们保证得到维护，并且具有向后兼容性，因此升级 Go 版本应该是顺利的。

我们用 Go 编写的缓存服务终于满足了我们的要求。我们大部分时间都在弄清楚 GC 暂停会对应用程序的响应能力产生巨大影响，因为它控制着数百万个对象。幸运的是，像bigcache或freecache这样的缓存解决了这个问题。