Doorman: Global Distributed Client-Side Rate Limiting

Doorman：全局分布式客户端限流

注意：这是原始的Doorman设计文档，删除了对Google内部产品和服务的引用。一些protobuf定义可能已过时，但总体思想没有改变。

介绍

在这里，我要解决的问题是：

一组分布式客户端（其中一些比其他客户端更重要）正在使用具有有限容量的共享资源。这些客户端需要在它们之间共享这个容量，以便实现以下目标：

• 客户端从系统中获取速率限制，然后负责维护这些限制。
• 客户端的组合流量不超过容量。
• 没有容量被闲置。
• 可用的容量在请求者之间公平地分配（对于公平的定义而言）。

背景

在这里，我将谈谈为什么这是一个需要解决的问题。

在YouTube，我们运行各种具有有限容量的内部基础设施，供内部和外部用户使用。为了保护有限的容量，我们使用了服务器端的限流措施。

服务器端限流作为一种防御措施效果良好，但它也存在问题：

1. 发送然后拒绝请求会产生成本。我们已经消耗了网络容量并对请求进行了一些处理。
2. 被拒绝查询的客户端不知道何时再次尝试。解决此问题的行业标准机制是使用指数回退进行重试。这不可避免地意味着某些容量被闲置。
3. 大多数服务器端限流器要求在客户端之间静态分配可用容量（尽管一些限流器允许在客户端超过其限制时共享未使用的容量）。静态预分配可用容量的一个问题是是否每个客户端都能同时使用其最大配额。

显然，不想通过服务器端限流器拒绝查询的客户端应该进行自我限流。

当前的客户端限流策略

在这里，我描述如果想要进行自我限流，人们今天通常会采取哪些机制，以及为什么这些机制不足够。

目前，使用我们基础设施的客户端的作者只有有限的工具可用于进行自我限流。

任务大小调整

在某些情况下，客户端会以无限制的速率向共享服务发送请求（即：以其能够生成的任何速率），我们通过调整客户端作业中的任务数量来限制它们使用服务的聚合速率。显然，这种方法的问题在于，在某些情况下运行N个任务，每个任务可以每秒生成M(i)个请求，可能一天完全没有问题，但在另一天就太多了，这取决于环境条件，例如网络状态和其他用户使用服务的情况。

在安静的日子里，服务可能能够支持N+K个任务，例如因为其他用户没有发送太多的流量，或者由于云计算环境中的随机波动导致ΣM(i)比平常低。当发生这种情况时，通过任务大小调整自我限流的客户端将未使用的容量留在桌子上，客户端无法像其潜在能力那样快速处理数据。然而，在其他日子里，N个任务可能会为服务生成过多的流量，这再次取决于超出配置生产环境的人的控制范围的因素。

局部速率限制

另一种策略是使用局部（任务绑定）速率限制器来限制单个任务可以发送的流量量。N个任务，每个任务被限制为每秒M（i）个请求，最多会生成ΣM（i）个请求。就像前面的例子一样，这个速率可能恰到好处，太保守，或者太激进，这取决于外部情况。这种方法的另一个问题是，如果一个任务正在运行在速率限制下（并且自我限制），而另一个任务还没有达到其限制，则第二个任务中的闲置容量不会分配给第一个任务。

是的，这是正确的。局部速率限制可以有效地限制单个任务生成的流量量，但它不能保证公平性或有效地利用可用容量。如果一个任务正在自我限制而另一个任务还有闲置容量，那么无法将未使用的容量分配给第一个任务。这可能会导致共享资源的利用不足和整体吞吐量降低。

影响

当前可用的限流策略会导致以下一个或多个影响：

• 大多数人在配置任务时过于保守（无论是限制N，还是限制M(i)），这将使得容量未被充分利用，许多作业和流程运行速度比它们实际上可以运行的要慢。在某些情况下，这会对用户产生可见的后果，因为某些流程所需时间比应有的时间长。
• 人们会手动优化N或M(i)以适应系统的典型可用容量。这通常有效，但偶尔他们的限制过于激进，系统将会退化，导致人们收到警报。
• 人们不断调整N和M(i)，以尝试最大化吞吐量。这是很麻烦的，并且经常会出错（导致警报）。

不幸的是：

1. 经验表明，指数级退避是一门失传的艺术（就像拼写一样）。
2. 在某些情况下，重试失败的查询可能会加剧问题。

一个全局分布式客户端限速系统

在这里我提供一个高级别的系统概述。

我提出设计和构建的系统将分配和分发有限的资源或服务容量给希望使用该容量的客户端。该系统对于这种容量代表的内容是不可知的。该系统可用于实现两种类型的速率限制：

1. 限制某些活动的最大频率。例如：将出站 RPC 限制为最大 QPS（每秒查询数）。
2. 只有特定数量的操作处于活动状态。例如：同时只有最大数量的开放 MySQL 事务正在运行。

该系统是合作的。希望使用它的客户端应明确使用此功能来控制执行某些操作的速率或并发操作的数量。

在提出的解决方案中，希望限制其使用共享资源（或服务）的客户端从系统请求并获取单独的容量限制 L。客户端的 L 值取决于：

• 全局总容量：不会提供超过可用容量的容量。
• 此客户端（任务）的单独需求：客户端通常不会获得比其请求更高的限制。
• 全局总需求：根据全局需求，客户端可能会获得低于其请求的限制。执行共享的算法会尽量“公平”地分配可用容量。

客户端的责任是不超过限制 L。系统将在各种语言（Python、C++、Java、Go）中提供模式和库，以允许客户端确定其需求并保持在分配的限制范围内。

系统将定期重新评估容量和限制，并向客户端分配新的限制。

架构概述

在此，我将对系统架构进行高层次的概述。

用于全局分布式客户端限速的系统由以下组件组成：

1. 一个客户端库（C++，Python，Java和Go），该库提供了与限速服务器（下文）通信的功能，并帮助应用程序遵守这些服务器收到的限制。
2. 一组全局分布式限速服务器，用于与客户端通信，接收所有容量请求，分配可用容量，并将容量限制返回给请求客户端。

服务器以层次结构组织：客户端与所谓的叶限速服务器进行通信。叶节点与一组父级服务器通信，在较低级别上聚合和分配容量。父级服务器再与根限速服务器通信，在树的下一级别上执行相同的功能。系统不要求此层次结构，也不要求层次结构深度为三级。层次结构可以是一级（仅根服务器）或深度可以根据生产部署要求而变化。

所提议的三层层次结构将允许以下层次：

1. 每个集群中的叶服务器。
2. 每个区域的父级服务器。
3. 全局的根服务器。

最初的部署可能仅包含根服务器，我可以想象我们不会超出只有叶和根服务器的两层层次结构。

客户端联系其分配的服务器以请求共享资源的限制。服务器响应限制L，该限制在特定时间T之前有效。此限制实际上是容量的租约。如果客户端想要继续使用资源，则需要在当前租约到期之前请求新的（或更改的）限制。鼓励客户在T时间到来之前更新限制。客户端和服务器之间的协议将在即将到来的部分中详细解释。

非根限速服务器基于从较低级别服务器获取的资源容量，使用类似（但不完全相同）于客户端使用的协议分配容量。从较低级别服务器获取容量的机制一直延伸到根服务器，后者从全局配置存储中存储的配置文件获取资源的容量。

注意：如果资源由多个服务器提供，则限速系统不负责规定这些实例之间的负载平衡。应使用现有的负载平衡技术。

根服务器配置

在这里，我将解释根服务器如何知道每个资源的容量以及如何在客户端之间分配它们。

保护的单位是“资源”。资源有一个最大容量，表示为正浮点数。容量的解释由客户端决定，例如可能是每秒查询次数、正在运行的数据库事务数、共享缓存中的项目数量或抽象查询成本。只要客户端和实现资源的服务器达成共识，系统就不需要知道容量的确切含义。

资源的一些示例（以限速系统为例）：

• 与YouTube MySQL主数据库分片相关的Vitess事务池。客户端可以使用这样的资源来限制客户端可以同时有多少个事务正在运行。
• MySQL副本分片。容量可以表示发送到分片的每秒查询数，或者（如果我们实现了查询成本计算系统）每秒查询成本单位的数量。

每个资源都有一个唯一的标识符，客户端在请求容量时使用该标识符。此标识符是人类可读的字符串，对于系统来说是不透明的。现有的标识符（如服务名称和MySQL分片名称）可以重用为资源标识符。

资源配置是一个协议缓冲区。协议缓冲区格式如下：

// NamedParameter encapsulates a name/value pair which is used to
// configure an Algorithm (see below).
message NamedParameter {
  required string name = 1;
  optional string value = 2;
}

message Algorithm {
  enum Kind {
    NO_ALGORITHM = 0;
    STATIC = 1;
    PROPORTIONAL_SHARE = 2;
    FAIR_SHARE = 3;
  }

  required Kind kind = 1;

  // How long should the lease be, in seconds.
  required int64 lease_length = 2;

  // How many seconds should the client wait until refreshing its
  // lease.
  required int64 refresh_interval = 3;

  repeated NamedParameter parameters = 4;

  // By default the learning mode duration is the lease length,
  // however if you want to live dangerously, and assume that
  // clients are living up to their responsibility to contact
  // the server every refresh_interval, you can specify a shorter
  // learning mode here. You can also specify a longer learning
  // mode duration (longer than the lease length), but then you
  // are a muppet (or you do not trust the clients, in which case
  // you need to fix the client implementation).
  optional int64 learning_mode_duration = 5;
}

// ResourceTemplate is used to instantiate the actual configuration
// for a resource based on a match with the identifier_glob glob.
message ResourceTemplate {
  // Glob used to match actual resources.
  required string identifier_glob = 1;

  // Capacity in service units
  required double capacity = 2;

  // Algorithm used to divide capacity between clients.
  required Algorithm algorithm = 3;

  // Capacity to use in "safe" mode.
  // You can set this to a number and then the client will use that number
  // as the capacity in case it cannot refresh its lease.
  // If this field is absent the system returns a dynamic safe capacity in
  // the response, which is the available capacity divided by the number of
  // clients that the server knows about.
  optional double safe_capacity = 4;

  // Description of the resource.
  optional string description = 5;
}

// The resource configuration consists of a list of templates.
message ResourceRepository {
  // List of ResourceTemplates specifying available resources. Order
  // of elements in this list is significant: it will be used to match
  // incoming requests. A template for * should be the last element.
  repeated ResourceTemplate resources = 1;
}

注意：当查找资源的配置条目时，系统将通过仓库进行两次扫描：第一次查找精确匹配，第二次查找正则表达式匹配，以防精确匹配没有结果。

注意：如果系统无法找到匹配请求资源的模板，则会尊重客户端发送的任何请求。将添加监视/警报工具以监视此情况。

资源配置协议缓冲区中的algorithm字段用于指示将用于在客户端之间分配容量的算法。最初将支持若干种算法。param重复字段可用于为算法指定配置参数。有关更多信息，请参阅“算法”一章。

服务器树和发现

本部分介绍速率限制服务器如何分布和被发现。

速率限制服务器被分布在一棵树上。在示例中，我们将使用深度为3的树：叶子节点服务于客户端，父节点服务于一组叶子节点，根节点服务于父节点。这个树的目的是全局分配容量，而不会创建所有客户端都需要访问的全局热点。

在示例中，叶子服务器为一个或多个集群提供服务，而父节点在地理上分布，为两个或多个叶子节点提供服务。

注意：实际部署可能会有不同的设置。例如，在最初的部署中，我们可能只有根服务器。

每个速率限制服务器可以为更高级别的客户端和服务器提供服务。在树的较高级别的速率限制服务器（例如叶子节点）中，他们的客户端总需求将聚合在他们自己的从较低级别服务器请求容量的请求中。在此模型中，客户端为自己请求容量，而服务器代表其所有客户端请求容量。根据配置的容量，根节点将为其客户端分配容量。

服务器树中的每个节点由一个速率限制服务器任务组成，该任务使用主选举机制从中选出一个任务作为该节点的活动服务器。主选举的获胜者将是服务该节点所有容量请求的任务。如果非主任务收到请求，则会回复主节点的地址，以便客户端知道要联系谁。

速率限制服务器将被编写为能够处理来自客户端或上游服务器的至少1,000个QPS的请求。鉴于我稍后将提议每个客户端每8秒联系其叶子服务器一次，这意味着单个速率限制服务器将能够处理大约8,000个客户端。这应该足够应对可预见的未来。如果某一时刻我们的客户端多于这个数，我们可以增加树的深度或改进速率限制服务器以处理更多查询。

根节点有点特殊：它将由不同区域的三个作业组成，这些作业将从三个作业中的所有九个任务中选出一个主节点。

处理集群不可用情况

注意：本章所描述的策略依赖于可用的全局负载均衡基础架构，该基础架构将客户端定向到具有容量的最近可用服务器。

只要树的每个非根级别在不同区域中至少有三个节点，该服务器树就可以抵御维护和其他集群故障：

• 根节点将在不同维护区域中分为三个集群，因此它提供了N+2可用性。
• 当进行排空操作时，已经与节点通信的客户端可以继续与该节点通信。集群被排空的事实并不一定导致该集群中的服务器停止运行。事实上，速率限制服务器的唯一依赖是其用于主节点选举的锁定服务（ZooKeeper，Etcd）单元。只要节点可以与较低级别服务器和锁定服务通信，它就可以运行。（本段不去除谷歌特定技术名称的话可能不太有意义:-)）
• 由于客户端和服务器从较低级别服务器租用容量，因此在离线的集群中拥有的客户端或服务器持有的容量将在租赁到期后自动过期。

客户端操作

在这里，我将描述客户端在请求服务器容量时应如何行事。

客户端标识符

每个客户端都有一个唯一的客户端ID，用于将此客户端与所有其他潜在客户端区分开来。客户端ID可以由计算机的完全限定主机名和一个唯一标识符（如进程标识符或TCP端口号）构成。

租约

速率限制服务器中的核心概念是容量租约：

// Encapsulates a lease on capacity with a start_time and expiry_time in seconds
// since the epoch.
message Lease {
  required int64 expiry_time = 1;
  required int64 refresh_interval = 2;
  required double capacity = 3;
}

一个租约（Lease）的协议缓冲区描述了一个资源上的租约。它包含租约的到期时间（从时代以来的秒数）。租约在到期时间之前有效，但强烈要求客户端每隔“refresh_interval”秒联系限速服务器更新其租约。

客户端状态

每个客户端都维护着它正在使用的所有资源的内部状态，它为这些资源获取的容量以及该容量过期的时间。这个内部状态可以被视为以下类型的协议缓冲区：

// The state a client needs to keep for every resource it wants to talk to.
message ClientResourceState {
  required string resource_id = 1;
  required int32 priority = 2;
  optional Lease has = 3;
  optional double safe_capacity = 4;
  required double wants = 5;
}

// The client state consists of a list of resource states.
message ClientState {
  required string client_id = 1;
  repeated ClientResourceState resource = 2;
}

注：客户端状态的协议缓冲表示是概念性的。客户端实现可能以不同的方式存储此状态，例如加速访问或便于锁定。在即将介绍的速率限制模拟中，使用此协议缓冲器表示客户端状态。

资源状态中的优先级字段表示客户端相对于该资源的优先级。优先级的解释取决于在资源配置中指定的算法。某些算法可能会完全忽略优先级。客户端库创建资源状态条目时会初始设置优先级，但此后只能通过服务器由于执行 GetCapacity RPC 的结果而进行修改。

当租约过期时，客户端应删除容量和租约字段，并表现为无可用容量。

乐观、悲观和安全模式操作

当客户端无法获取或更新容量时，它可以执行三种操作：

1. 在悲观模式下，它可以表现为已授予容量为零，实际上停止使用资源。这显然是最安全的，但如果速率限制系统暂时不可用，可能会停止所有资源使用。这对于离线批处理作业或守护程序是正确的操作，因为它们不与用户交互。
2. 在乐观模式下，它可以表现为已获得其请求的所有容量。这意味着它可以继续使用资源，但是有一个危险，即资源可能会被过度使用。这对于与用户交互以及由其他方式防止过载的资源的在线组件是正确的操作。
3. 在安全模式下，客户端可以使用该资源，直到达到资源的每个客户端安全容量限制为止。安全容量在资源模板中配置，并作为每个容量请求的一部分返回。如果在资源模板中未配置安全容量，则服务器计算动态安全容量（可用容量除以客户端数量）并返回该安全容量以供使用。

注：资源配置中的 safe_capacity 字段定义了服务器希望客户端在无法与速率限制服务器通信时如何行为。但由于该系统是合作性的，客户端不必遵循配置的安全容量，但如果希望成为良好的公民，则应该遵循该容量。

发现服务器

客户端需要找到当前要联系的 Doorman 主服务器。它可以通过两种方式完成：

1. 使用显式 Discovery RPC
2. 只需发送 GetCapacity RPC 并处理响应中的 master_address 字段。

Discovery RPC 是首选机制，但客户端库作者可以使用任何方法。

使用 Discovery RPC

可以将 Discovery RPC 发送到服务器层次结构中给定级别的任何 Doorman 服务器以查找该级别的主服务器

// The request to obtain the master's address.
message DiscoveryRequest {
}

// This message type is used when the server wants to convey the
// address of a master. If the the optional master_address field
// is not there that means that the server we were talking to is
// not the master, and it wants to tell us who the master is, but
// it doesn't know.
message Mastership {
  optional string master_address = 1;
}

// The response containing the master's address.
message DiscoveryResponse {
  required Mastership mastership = 1;
  required bool is_master = 2;
}

回复应该解释如下：

• 如果 is_master 等于 true，则回复 RPC 的服务器是主服务器。主控消息包含主服务器的地址。如果 is_master 为 true，而 master_address 不存在，则会出现语义错误。
• 如果 is_master 等于 false，则主控消息可能包含主服务器的地址。如果没有（可选字段），则服务器不知道主服务器是谁，需要重新尝试发现过程。

请求容量

要从系统中请求容量的客户端首先需要找到最近叶节点的主服务器（参见上面的“发现”部分）。

为了获得资源的容量，客户端向服务器发送一个 GetCapacity RPC。这个 RPC 是一个批量请求，可以请求多个资源的容量。客户端被邀请总是为其内部状态中的所有资源发送 GetCapacity 请求，但可以选择为这些资源的子集请求容量。

GetCapacity 请求以以下协议缓冲区作为其参数（来自“protocol.proto”）：

// Encapsulates the information we need to send to get capacity for a
// single resource.
message ResourceRequest {
  required string resource_id = 1;
  required int64 priority = 2;
  optional Lease has = 3;
  required double wants = 4;
}

// The GetCapacityRequest contains the identifier of the client making
// the request and a list of single resource capacity request protocol
// buffers.
message GetCapacityRequest {
  required string client_id = 1;
  repeated ResourceRequest resource = 2;
}

除了客户端标识符之外，此消息还包含单个资源容量请求的列表。对于新请求，此请求仅包含所请求的新容量（wants），而没有其他可选字段。对于对同一资源的重复请求，单个资源容量请求还包含客户端对该资源拥有的当前容量（has）和当前租赁。

响应是以下类型的协议缓冲区（来自“doorman.proto”）：

// Contains the capacity allocated by the server for a single
// resource.
message ResourceResponse {
  required string resource_id = 1;
  required Lease gets = 2;
  optional double safe_capacity = 4;
}

// The response to a GetCapacity request is a list of protocol buffers
// specifying the capacity for a single resource.
message GetCapacityResponse {
  repeated ResourceResponse response = 1;
  optional Mastership mastership = 2;
}

如前所述，服务器只有在作为主节点时才会返回容量。否则，它将返回主权信息，客户端需要连接到主节点。如果在请求时没有已知的主节点（例如因为正在进行主节点选举），则主权消息中的master_address将为空，客户端应该重试。

客户端需要从GetCapacityResponse中更新其内部状态，并从那时起调节其资源使用量，以不超过新的限制。如果请求中的任何资源在响应中不存在，这意味着资源配置已被修改，不再包含与资源匹配的模板。最终，容量租赁将耗尽。如何处理这种情况在下面的租赁到期部分中描述。

客户端应每“refresh_interval”秒重新发出对资源的GetCapacity请求。如果该调用返回有关新主节点的信息，则客户端应立即向新主节点发送GetCapacity RPC。故障可以忽略，客户端可以在另一个“refresh_interval”秒内重试。

客户端允许在刷新间隔过期之前发送GetCapacity请求。这样做的好理由是：

1. 资源所需的容量发生了显着变化，客户端希望立即更新其容量租约。
2. 客户端希望为新资源获取容量，并决定同时更新其内部状态中其他资源的容量（鼓励这种行为）。

话虽如此，对于给定资源，客户端可能不会发送多个GetCapacity请求，每个请求之间的时间间隔不到五秒。如果在最后一个请求后的五秒内发送了资源的容量请求，则会被静默忽略。该功能保护服务器免受在创建多个资源时客户端初始化期间运行可能昂贵的算法的影响（每个资源都可能导致GetCapacity请求（取决于客户端库的结构））。

租约到期

当容量租约到期时，客户端应更新其内部状态、容量和租赁字段。从此时起，客户端的行为与资源相关的行为取决于客户端是否配置为乐观、悲观或安全模式（见上文节）。

释放资源

如果客户端不再想要与某个资源通信，它可以使用ReleaseCapacity RPC（来自“protocol.proto”）来释放它：

message ReleaseCapacityRequest {
 required string client_id = 1;
 repeated string resource_id = 2;
}

message ReleaseCapacityResponse {
  optional Mastership mastership = 2;
}

如果ReleaseCapacity RPC在错误中结束，客户端可以忽略此错误。如果响应包含有关新主服务器的信息，则客户端无需尝试使用新主服务器重试RPC，因为该新主服务器将不会具有任何有关这些资源的状态（因为速率限制服务器彼此不共享状态）。如果客户端崩溃，则当其所有租约到期时，服务器将自动忘记该客户端。

服务器操作

在其中我描述了服务器在从客户端收到请求时的操作

速率限制服务器充当客户端和更高层次的服务器的服务器，并充当客户端以从低级别服务器获取容量（除根服务器外，它没有下游服务器）。服务器通过标志进行配置，标志包含其需要从其自身获取容量的下一级别服务器的地址。

每个服务器从中央配置服务器加载全局资源配置。

服务器标识符

与客户端一样，每个服务器都有一个服务器标识符。该标识符类似于在客户端操作章节中讨论的客户端标识符，并以相同的方式确定。

主服务器选举

服务器参与与构成节点的其他服务器的主服务器选举。通常情况下，这将是构成节点的作业中的其他任务，但对于根节点，选举是在构成根节点的所有作业（在三个不同的维护区域中）中的任务之间进行的（请参阅本文档中前面的服务器树章节）。

如果服务器输掉选举：

• 其对任何RPC的响应应仅包含主权字段，将客户端重定向到新主服务器。
• 它需要删除整个内部服务器状态。

如果服务器赢得选举：

• 它需要创建一个新的空的内部服务器状态。

服务器状态

服务器保留以下状态：

// This protocol buffer encapsulates the state a server maintains for a client/resource
// combination. Note: This is for actual clients, not for rate limiting servers at
// a higher position in the server tree.
message PerClientResourceState {
  required string client_id = 1;
  required int32 last_request_time = 2;
  required int32 priority = 3;
  optional CapacityLease has = 4;
  required double wants = 5;
}

// This protocol buffer encapsulates the state a server maintains for a single resource
// and a higher level server (a server at a higher level in the server tree that uses
// this server to get capacity on behalf of its clients). The state consists of a list
// of aggregated client needs per priority band.
message PerServerResourceState {
  required string server_id = 1;
  required int32 last_request_time = 2;
  optional CapacityLease has = 3;
  required double outstanding = 4;
  repeated PriorityBandAggregate wants = 5;
}

// This protocol buffer encapsulates the server state for a single resource
message ServerPerResourceState {
  required string resource_id = 1;
  required int32 learning_mode_expiry_time = 2;
  required ResourceTemplate template = 3;
  optional CapacityLease has = 4;
  repeated PerClientResourceState client = 5;
  repeated PerServerResourceState server = 6;
}

// The server state object contains a list of state per resource that the server has
// been asked about.
message ServerState {
  required string server_id = 1;
  required int32 server_level = 2;
  optional int32 election_victory_time = 3;
  repeated ServerPerResourceState resource = 4;
}

"PriorityBandAggregate"看起来像这样：

message PriorityBandAggregate {
  required int32 priority = 1;
  required int32 num_clients = 2;
  required double wants = 3;
}

注意：服务器状态的协议缓冲区表示是概念性的。服务器实现可能以不同的方式存储此状态，例如为了加速访问或简化锁定。

服务器在ServerResourceState中维护的租赁反映了该服务器作为下游服务器的客户端的状态。 PerClientResourceState和PerServerClientResourceState对象中的租赁信息反映了该服务器向这些客户端和服务器分配的信息。

处理GetCapacity RPC

当服务器接收到GetCapacity RPC时，它会针对RPC中的每个单个资源请求执行以下步骤：

步骤1：清理步骤

在清理步骤中，服务器通过其内部状态并删除所有租赁已过期的条目。

注：

• 可以在任何时候执行此清理操作，但现在执行很方便。
• 由于服务器永远不会分配比自己对较低级别服务器获得的能力更长的能力租赁，因此，资源的自己的容量租赁过期意味着从它获得容量的所有客户端和服务器的租赁也已过期。
• 由于所有时间都以秒为单位维护，因此如果当前（秒粒度）时间戳中尚未执行清理，则服务器只需执行清理操作。这提供了一个简单的优化。
• 处于学习模式的资源（请参见下文）不受清理的影响，因为它们可能还没有从下游服务器获得容量。

步骤2：插入步骤

在此步骤中，服务器将请求信息插入其内部状态，除非客户端在5秒内已请求此相同的资源容量，否则不插入状态并且不执行后续步骤。这也意味着响应将不包含此资源的容量。

注意：如果资源不处于学习模式中（请参见下文），则请求带有“has”字段而没有服务器内部状态中的此客户端/资源记录是错误的。在这种情况下，服务器记录一个错误但继续处理请求。

步骤3：确定新容量

如果请求在资源仍处于学习模式时进入（请参见下文），则服务器会要求算法为请求者创建一个新的CapacityLease，其中容量字段设置为与请求中的当前容量（来自“has”字段）相同的值，或如果请求没有当前容量，则为零。

如果资源不再处于学习模式，则服务器在其内部状态上运行所选资源的算法。算法的输出是客户端的新CapacityLease。

有关算法执行的更多信息，请查看下面的“算法”章节。

注意：如果该服务器没有任何资源可用的容量（在ServerPerResourceState对象中，容量和租赁字段都不存在），则它会表现为可用容量为零。这可能是因为该服务器尚未获取该资源的任何容量（例如，因为它最近赢得了主选举并且尚未与下游服务器通信），或者是因为该服务器失去了当前容量的租约。

步骤4：响应步骤

在最后一步，服务器为此资源请求创建了GetCapacity响应协议缓冲区，并将其插入到响应协议缓冲区中。它还更新了客户端的last_request_time字段。

学习模式

服务器不会将其内部状态存储在可持久化介质上，也不会将其复制到选举过程中的备选者中。这意味着当服务器赢得选举时，它拥有一个清洁的内部状态，并且不知道有哪些租赁存在。这也意味着它在重建其内部状态之前无法安全地分配容量。幸运的是，每个客户端和更高级别的服务器（即此服务器的客户端）都必须定期联系此服务器以刷新容量租约，服务器可以利用此功能重建其内部状态。资源的重建内部状态阶段称为“学习模式”。

当资源处于学习模式时，它知道它无法运行其算法来分配容量，另一方面，它也知道当前的资源分配很可能反映了客户端之间的有效容量分配。因此，在学习模式下，服务器只记录客户端提供的信息在其内部状态中，并将相同的容量分配回客户端。如果请求没有“has”字段，这意味着此请求来自新客户端或具有过期容量的客户端。不幸的是，服务器处理这个请求的唯一方法是向此客户端分配零容量。新容量的租约是由为资源选择的算法（通过配置）设置的，通过要求它使用提供的容量创建一个默认租约来实现。

每当服务器在其内部状态中创建新的ServerPerResourceState对象时，它通过向资源的算法询问此资源将要分配的最大租约持续时间来确定该资源的learning_mode_expiry_time。 learning_expiry_time是服务器的election_victory_time加上该最大租赁持续时间。

处理ReleaseCapacity RPC

处理ReleaseCapacity RPC就是从服务器的内部状态中删除请求中有关客户端/资源组合的所有信息，非常简单。

获取服务器的容量

服务器需要为客户端分配每个资源的容量（由算法分配）。服务器对于某个资源拥有的容量反映在服务器内部状态中的ServerPerResourceState对象的“capacity”字段中。

对于根节点中的服务器，资源可用容量是由该资源的资源模板（ResourceTemplate对象的“capacity”字段）确定的。

注意：我们应该在根服务器上分配“正常”的容量租约（包括刷新间隔），因为这使得全局配置中的容量可以通过在配置服务器中更新配置来更改。

非根节点中的服务器需要通过GetServerCapacity RPC向较低级别

message ServerCapacityResourceRequest {
  required string resource_id = 1;
  optional CapacityLease has = 2;
  required double outstanding = 3;
  repeated PriorityBandAggregate wants = 4;
}

message GetServerCapacityRequest {
  required string server_id = 1;
  repeated ServerCapacityResourceRequest resource = 2;
}

服务器需要将其针对某一资源的整个内部状态（包括对单个客户端保留的信息和对使用该服务器获取其自身容量的更高级别服务器保留的信息）压缩成一个 GetServerCapacity 请求。

该请求的响应具有以下格式：

message ServerCapacityResourceResponse {
  required string resource_id = 1;
  required CapacityLease gets = 2;
}

message GetServerCapacityResponse {
  repeated ServerCapacityResourceResponse resource = 1;
  optional Mastership mastership = 2;
}

服务器将容量和租期的信息复制回其内部状态，并在向其客户和高级服务器分配容量时使用该信息。

处理 GetServerCapacity RPC

GetServerCapacity RPC的处理方式与GetCapacity RPC完全相同，尽管算法的运行需要更多的涉及，因为它需要考虑客户端的客户端。

其他

• 可能不用说，但必须小心实现服务器的内部状态的适当锁定，特别是与以下方面有关：
  • 并发处理RPC
  • 更新配置服务器中的配置
• 可能值得考虑的是，将运行算法的部分以轮向方式实现。在这种情况下，几个正在进行的RPC会修改内部服务器状态，然后等待算法的下一轮运行，然后它们会检索结果。这可能会导致整个系统更快地收敛到稳定状态。

算法

在回避如何实际将有限容量分配给客户端的问题时 :-)

在本设计文档的术语中，算法负责处理内部服务器状态，并找出如何将可用容量分配给请求来自该服务器的客户端和更高级别的服务器。该系统可以支持多个算法。每个算法都可以通过命名参数进行参数化，以指导其执行（请参见本文档早期的配置部分）。

算法的主要功能是计算可用容量在请求容量的客户端和更高级别服务器之间的分配。在此基础上，算法具有两个特点，这在学习模式下是必需的：

• 可以根据给定的容量创建租约。
• 可以返回它将分配给资源的最大租约时间。

算法的计算函数以资源标识符和服务器或客户端标识符作为其参数。然后，该函数计算请求容量的客户端或服务器应该获得什么，并为客户端或更高级别的服务器创建新的CapacityLease。

关于此事的一些注释：

• 在创建新租约时，完全有可能请求者无法获得其应得的全部容量，因为此服务器的其他客户端仍具有未过期的租约。在这种情况下，算法应分配它可以给出的最大容量，而不会超过可用容量（考虑所有“has”容量）。
• 如果有足够的可用容量，请求者可能会获得比其要求的更多的容量，由算法自行决定。例如，为了使服务器能够更快地响应新客户端或峰值客户端，可能会有用将更多的容量分配给服务器。
• 算法不应创建持续时间超过该服务器对容量的租赁的新租赁。
• 为了收敛的原因，租约的刷新间隔应该随着我们在树中向上移动

寻找要使用的算法

配置中的每个ResourceTemplate都可以指定用于与此模板匹配的所有资源的算法。如果资源模板不包含算法，则配置将使用（强制）默认算法。

如果服务器无法实例化算法（例如由于未知的算法名称或算法参数中的不可纠正错误），它将为资源实例化“None”算法。此情况将被记录并导出到监控系统，以便生成适当的警报。

常见算法参数

本文档中的每个算法都支持以下参数：

可用算法

最初将实现以下算法：

“无”算法

该算法实际上是没有算法。它简单地为每个请求者分配其所需的容量，甚至忽略了可能超出完全可用容量的可能性。

注意：如果服务器无法实例化资源模板中指定的算法或默认算法，则此为默认算法。

“静态”算法

该算法为每个请求者提供相同的静态配置容量。

“比例共享”算法

从实现代码中可以看出：

// 比例共享（ProportionalShare）为每个客户端分配其所需的容量，除非在超载情况下，每个客户端都至少得到相等的份额（如果它需要的话），
// 并且（如果可能）从请求少于其相等份额的客户端留下的剩余容量中按比例分配到请求更多容量的客户端。

“公平份额”算法

从实现代码中可以看出：

// “公平份额”（FairShare）为每个客户端分配一个“公平”的可用容量份额。公平的定义如下：
// 如果总需求低于总可用容量，则每个人都得到他们想要的容量。
// 但是，如果总需求高于总可用容量，则每个人都保证得到他们的平等份额。
// 任何请求少于其平等份额的客户端留下的容量都会以迭代方式以均等的方式分配给请求更多容量的客户端。有关示例，请参阅文档。

收敛和缺口

在这里，一个重要的系统方面是收敛：系统以多快的速度收敛到一个稳定状态，该状态尽可能地分配了尽可能多的容量，而没有超出最大容量。

下面是第一个模拟场景的图表。在这种情况下：

• 服务器树中只有一个节点（根节点）。
• 有500个容量可分配。
• 有五个客户端。每个最初都想要100个容量，但会随机变化。

如您在图表中看到的，客户端的总请求和总分配容量非常接近，并且客户端的总分配容量不会超过服务器的总分配容量（黄线）。

第七个场景显示了更复杂的树的收敛，具有一个根节点，三个区域，每个区域三个数据中心，每个数据中心五个客户端。这意味着总共有45个客户端。他们最初每个要求14个容量，然后随机波动需求。在运行过程中，会发生一些随机意外事件，例如客户端升峰（增加100个请求容量），服务器故障等等。模拟运行一个小时：

红线显示根节点的总可用容量（500）。掉落发生在模拟服务器崩溃期间。蓝线是分配给客户端的总容量。在全球需求出现重大变化后，系统最多需要2分钟来恢复并分配所有容量。在此模拟中，系统平均分配了所有可用容量的96.6％（在初始启动学习模式之后）。在类似的场景（场景五）中，系统平均分配了可用容量的96.8％，没有随机错误发生。

短缺

从图表中可以看出，系统分配的容量有多次超过了容量限制。我们称这种现象为“短缺”。

短缺的原因是，当一个服务器从下游服务器请求容量时，它可能会得到一个新的容量，该容量小于它当前已经向客户端和上游服务器租用的未归还容量。在这种情况下（这种情况将在单个刷新间隔内得到纠正），该服务器已经分配了比其当前容量更多的容量。当系统运行接近最大容量并且树中某处突然出现容量激增时，就会发生这种情况。在此期间，系统必须重新平衡，而在重新平衡期间，就会发生短缺。

在上述模拟运行中：

• 短缺发生了14次
• 分配的最大容量为530.24（106.05％）
• 平均超容量情况为509.99（102％）

解决短缺的方法意味着以一种会减慢收敛速度的方式改变系统。我们研究了许多方法，但每一种方法对收敛速度都有很大影响。总的来说，我们认为短缺问题并不是非常重要，原因如下：

• 它只在极端情况下发生。
• 对于许多资源，配置的最大容量并不是硬性限制。
• 超过最大容量的量不是非常大。

客户端库

如何让客户端的生活更容易……

速率限制系统的RPC接口非常简单。出于简单性和统一性的原因，我们将开发一个客户端库，向客户端代码公开一个简单的接口，并处理与速率限制系统的协议交互。

API

将公开两种不同的API。一种是针对可用容量代表速率（例如qps）的资源，另一种是针对容量代表计量器（例如最大并发事务数）的资源。

对于速率资源，API（以C++为例）如下：

RateResource resource("resource0");
while (something) {
    resource.Wait()
    // Execute transaction
}

一些注释：

• 多次创建RateResource只会创建一个底层实际资源。引用计数将用于确定何时执行ReleaseCapacity RPC。
• Wait() 方法等待直到我们可以执行下一个查询。查询在秒内不均匀分布，但当该秒的预算用尽时，调用者将被阻止直到新的一秒开始。
• 将添加方法来设置所需的容量。一旦系统在使用中，库将使用Wait()调用的时间和计数来确定此客户端想要/需要的容量。

对于测量资源，API如下所示：

GaugeResource resource("resource1");
while (something) {
    ...
    resource.Mark();
    // Execute transaction
    resource.Release();
    ...
}

while (something) {
    UnderGaugeResource x(&resource);
    // Execute transaction
}

一些评论：

• 将会有一种方法来设置最初所需的容量。Mark()和Release()方法将使用对Mark()和Release()的调用的时间和计数来确定所需的容量...
• 在长时间运行的事务的情况下，存在更高的不足风险（请参见前一章节）。

顶部和底部两半部分

客户端库将由两个层和一个中间数据结构组成。顶半部分由客户端代码调用，而底半部分与速率限制系统通信。客户端状态存在于两层之间的灰色区域，并且由两个部分更新：