在 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。

缓存

为了满足要求,缓存本身需要:

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

考虑到第一点,我们决定放弃RedisMemcachedCouchbase等外部缓存,主要是因为网络上需要额外的时间。因此,我们专注于内存缓存。在 Go 中已经有这种类型的缓存,即LRU 组 cachego-cachettlcachefreecache只有 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()管理堆外的内存。但是,需要实现依赖于这些功能的缓存。

第二种方法是使用freecacheFreecache 通过减少指针数量来实现零 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 暂停会对应用程序的响应能力产生巨大影响,因为它控制着数百万个对象。幸运的是,像bigcachefreecache这样的缓存解决了这个问题。