Gubernator微服务的云原生分布式速率限制

今天，Mailgun 很高兴能够开源高性能的分布式限速微服务 –Gubernator。Gubernator 会做什么？

Gubernator 在整个集群中平均分配速率限制请求，这意味着您可以通过简单地添加更多节点来扩展系统。
Gubernator 不依赖于 Memcache 或 Redis 之类的外部缓存，因此不存在与相关服务的部署同步。这使得在 kubernetes 或 nomad 等编排系统中动态增加或缩小群集。
Gubernator 不会在磁盘上保持任何状态，客户端会根据每个请求将其配置传递给它。
Gubernator 提供对其 API 的 GRPC 和 HTTP 访问。
可以作为需要速率限制的服务的辅助工具运行，也可以作为单独的服务运行。
可用作库，以实现特定于域的速率限制服务。
支持用于极高吞吐量环境的可选最终一致的速率限制分配。

现在，我们确信您对我们为什么决定开源 Gubernator 仍有很多疑问。因此，在深入探讨 Gubernator 的工作方式之前，让我们先回答其中几个问题。您要问的最大的问题可能是 …

在评估 Redis 时，考虑到下面几点：

即使使用 pipelining，使用基本 Redis 速率限制实现也将导致额外的网络往返。
我们可以使用 https://redis.io/commands/eval 并编写一个 LUA 脚本来减少往返行程，但我们需要为所实现的每种算法维护该脚本。
每个单独的请求将导致至少两次往返 Redis。再加上至少 1 次往返于我们的微服务，这意味着每个请求至少 2 次往返于我们的服务。

Redis 的最佳解决方案是编写一个实现速率限制算法的 LUA 脚本。然后将该脚本存储在 Redis 服务器上，并针对每个速率限制请求调用该脚本。在这种情况下，大部分工作都是由 Redis 完成的，而我们的微服务基本上是访问 Redis 的代理。在这种情况下，我们有两个选择：

将 Gubernator 创建为可访问 Redis 的速率限制库。每个需要速率限制的服务都将使用该库。
消除 Redis，并在具有速率限制的微服务中使用瘦 GRPC 客户端实现分发，缓存和限制算法。

为什么是微服务 ?

Mailgun 是一家使用 python 和 golang 的多语言公司，构成了我们大多数代码库。如果我们选择将速率限制实现为库，则需要最少 python 和 golang 版本。在内部使用同一库的 python 和 golang 版本之前，我们已经走了这条路线。根据我们的经验，跨服务的共享库具有以下缺点。

库的 bug 和功能更新最多只能对依赖项进行更新。最糟糕的是，它要求以所有受支持的语言对使用该库的所有服务进行修改。
开发人员很少要使用两种语言维护或编写新功能。通常，这会导致库的一个版本比其他版本具有更多功能或得到更好的维护。

随着我们生态系统中微服务和语言的数量持续增长，这些问题变得越来越严重。相比之下，可以轻松为需要访问 Gubernator 的每种语言创建和维护 GRPC 和 HTTP 库。

对于微服务，可以在不中断相关服务的情况下添加错误更新和新功能。只要不允许对 API 进行重大更改，相关服务就可以选择新功能，而无需更新所有相关服务。

Gubernator 作为微服务的杀手级功能是，它为进入系统的许多请求创建了一个同步点。彼此之间在几微秒之内收到的请求可以进行优化和协调，从而减少服务在高负载下使用的总带宽和往返延迟。在单个主机上运行的所有服务都具有在各自进程中运行的同一个库，这些服务不具有此功能。

Gubernator 无状态，因为它不需要磁盘空间即可操作。从来没有配置或缓存数据同步到磁盘，这是因为对 Gubernator 的每个请求都包含速率限制的配置。

起初，您可能认为这对每个请求来说都是不必要的开销。但是，实际上，速率限制配置仅由 4 个 64 位整数组成。该配置由“限制”，“持续时间”，“算法”和“行为”组成（有关其工作原理的详细信息，请参见下文）。正是由于这种简单的配置，Gubernator 可以用于提供客户可以使用的多种速率限制用例。其中一些用例是：

Ingress limiting – 基于 HTTP 的典型 402 太多请求类型限制
Traffic Shedding – 当您的 API 处于错误状态时，仅拒绝新的或未经身份验证的请求
Egress limiting – 用数百万条消息轰炸外部 SMTP 服务器不是 No Bueno
Queue Processing – 知道何时可以立即处理请求，或应按接收顺序将其排队和处理
API Capacity Management – 对全局 API 系统可以处理的请求总数设置全局限制。拒绝或排队请求破坏了系统的正常运行能力

除了上述用例之外，无配置设计对微服务设计和部署也有重要意义：

部署时无配置同步。部署使用 Gubernator 的服务时，没有速率限制配置需要预先部署到 Gubernator。
使用 Gubernator 的服务拥有其问题空间的速率限制域模型。这样可以将特定领域的知识排除在 Gubernator 之外，因此 Gubernator 可以专注于其最擅长的工作 - 速率限制！

除了这些问题之外，让我们从整个工作原理开始，全面讨论 Gubernator。

Gubernator 设计为对等体的分布式群集运行，该对等体利用所有当前活动速率限制的内存中缓存，因为这样就不会将任何数据同步到磁盘。由于大多数基于网络的速率限制持续时间仅保留几秒钟，因此在重新启动或计划的停机时间期间丢失内存高速缓存并不是什么大问题。对于 Gubernator，我们选择性能而不是准确性，因为在高速缓存丢失的情况下，一小部分流量在短时间内（通常是几秒钟）过度请求是可以接受的。

当向 Gubernator 发出速率限制请求时，该请求将被加密，并应用一致的哈希算法来确定哪个对等方将成为速率限制请求的所有者。为速率限制选择单个所有者，可以使计数的原子增量非常快，并且避免了在对等群集之间一致地分配计数时所涉及的复杂性和延迟。

尽管简单高效，但是由于单个协调器可能负责成千上万个请求，而速率限制，因此该设计可能会受到大量请求的影响。

为了解决这个问题，客户端可以请求“Behaviour = BATCHING”，该行为允许对等方在指定窗口（默认值为 500 微秒）内接收多个请求，并将请求分批处理为单个对等方请求，从而减少通过有线方式进行请求的总数。

为了确保集群中的每个对等方准确地为速率限制密钥计算正确的哈希值，必须以及时且一致的方式将集群中的对等方列表分配给集群中的每个对等方。当前，Gubernator 支持使用 etcd 或 kubernetes 端点 API 来发现 Gubernator 对等体。

当客户端或服务向 Gubernator 发出请求时，客户端将为每个请求提供速率限制配置。然后，将速率限制配置与当前速率限制状态一起存储在速率限制所有者的本地缓存中。速率限制及其存储在本地缓存中的配置仅在速率限制配置的指定持续时间内存在。

持续时间到期后，如果在持续时间内未再次请求速率限制，则将其从缓存中删除。随后对相同名称和 unique_key 对的请求将在缓存中重新创建配置和速率限制，并且该循环将重复。另一方面，具有不同配置的后续请求将覆盖先前的配置，并立即应用新的配置。

通过 GRPC 发送的速率限制请求示例可能如下所示：

     rate_limits:
    # Scopes the request to a specific rate limit 
  - name: requests_per_sec
    # A unique_key that identifies this rate limit request
    unique_key: account_id=123|source_ip=172.0.0.1
    # The number of hits we are requesting
    hits: 1
    # The total number of requests allowed for this rate limit
    limit: 100
    # The duration of the rate limit in milliseconds
    duration: 1000
    # The algorithm used to calculate the rate limit  
    # 0 = Token Bucket
    # 1 = Leaky Bucket
    algorithm: 0
    # The behavior of the rate limit in gubernator.
    # 0 = BATCHING (Enables batching of requests to peers)
    # 1 = NO_BATCHING (Disables batching)
    # 2 = GLOBAL (Enable global caching for this rate limit)
    behavior: 0

一个示例响应为：

rate_limits:
      # The status of the rate limit.  OK = 0, OVER_LIMIT = 1
    - status: 0,
      # The current configured limit
      limit: 10,
      # The number of requests remaining
      remaining: 7,
      # A unix timestamp in milliseconds of when the rate limit will reset,
      #  or if OVER_LIMIT is set it is the time at which the rate limit
      # will no longer return OVER_LIMIT.
      reset_time: 1551309219226,
      # Additional metadata about the request the client might find useful
      metadata:
        # This is the name of the node that owns this request
        "owner": "api-n03.staging.us-east-1.mailgun.org:9041"

由于 Gubernator 速率限制是由集群中的单个对等方散列和处理的，因此，适用于数据中心中每个请求的速率限制将导致单个对等方对整个数据中心的速率限制请求进行处理。

例如，考虑一个速率限制，其名称为 name = requests_per_datacenter，而 unique_id = us-east-1。现在想象一下，对于每个进入 us-east- 1 数据中心的 HTTP 请求，都以该速率限制向 Gubernator 发送了一个请求。这可能是成千上万，甚至每秒可能有数百万个请求，这些请求全部由集群中的单个对等方散列和处理。由于存在潜在的扩展问题，因此 Gubernator 引入了一种称为 GLOBAL 的可配置行为。

当将速率限制配置为 behavior = GLOBAL 时，从客户端收到的速率限制请求将不会转发到拥有对等方。相反，它将从接收请求的对等方处理的内部缓存中进行应答。达到速率限制的匹配将由接收对等方批处理，并异步发送到所属对等方，在此对匹配进行总计并计算 OVER_LIMIT。然后，拥有对等方的责任是使用速率限制的当前状态更新群集中的每个对等方，以使对等方内部缓存定期从所有者那里以最新速率限制状态进行更新。

由于匹配数是批量处理的，并且异步转发给所有者，因此对客户端的即时响应将不包括最准确的剩余计数。仅在对所有者对等方的异步调用完成并且拥有对等方有时间更新集群中的所有对等方之后，该计数才会更新。结果，使用 GLOBAL 可以扩大规模，但要以保持一致性为代价。如果群集足够大，则使用 GLOBAL 可以增加每个速率限制请求的流量。GLOBAL 仅应用于与传统非 GLOBAL 行为无法很好扩展的极高速度限制。

在生产环境中，对于我们的 API 的每个请求，我们都会向 Gubernator 发送 2 个限速请求，以进行限速评估；一个用于对 HTTP 请求进行评分，另一个用于对用户在特定持续时间内也可以发送电子邮件的收件人数量进行评分。在这种设置下，一个超过 2,000 个的 Gubernator 节点字段每秒请求一次，并且大多数批处理响应在 1 毫秒内返回。

由于我们许多面向公众的 API 都是使用 python 编写的，因此我们在单个节点上运行了许多 python 解释器实例。这些 python 实例会将请求本地转发到 Gubernator 实例，然后再将其批处理并将请求转发到拥有的节点。

Gubernator 允许用户选择非分批行为，这将进一步减少客户端速率限制请求的延迟。但是，由于吞吐量要求，我们的生产环境使用 Behaviour = BATCHING 和默认的 500 微秒窗口。在生产中，我们观察到 API 使用高峰期间的批量为 1,000。流量需求不一样的其他用户可能会禁用批量处理，并会降低等待时间，但会降低吞吐量。

如果您使用的是 Golang，则可以将 Gubernator 用作库。如果您希望在自己的公司特定模型之上实施限流服务，这将很有用。我们在 Mailgun 的内部进行此操作，并提供了一个我们创造性地称为 ratelimits 的服务，该服务跟踪每个帐户所施加的限制。这样，您可以利用 Gubernator 的功能和速度，但仍可以分层业务逻辑，并将特定于域的问题集成到您的限速服务中。

使用库时，您的服务将成为集群的完整成员，与独立的 Gubernator 服务器一样，将参与相同的一致哈希和缓存。您所需要做的就是提供 GRPC 服务器实例，并告诉 Gubernator 集群中的对等节点位于何处。

将 Gubernator 用作通用限速服务使我们能够依赖微服务体系结构，而不会损害服务独立性和通用限速解决方案所需的重复工作。我们希望通过将该项目开源，其他人可以合作并从我们在这里开始的工作中受益。

PS: 本文属于翻译，原文

Gubernator微服务的云原生分布式速率限制

Features

为什么不使用 Redis?

为什么 Gubernator 是无状态 ?

Gubernator 工作原理

Gubernator 操作

GLOBAL 行为

GLOBAL 行为的副作用

Gubernator 性能

Gubernator 作为库使用

结论