早在4月份，我们就宣布了对每个Cloudflare客户的请求速率限制。能够在网络的边缘进行速率限制有许多优点：客户更容易设置和操作，其源服务器不会受到过多流量或第7层攻击的困扰，速率限制的性能和内存成本被转移到边缘，等等。简而言之，速率限制是这样工作的：客户可以定义一个或多个与特定HTTP请求（失败的登录尝试、昂贵的API调用等）匹配的速率限制规则每个符合规则的请求都按客户机IP地址计数一旦该计数器超过阈值，就不允许进一步的请求到达源服务器，而是向客户端返回一个错误页这是一个简单但有效的保护，以防止暴力攻击登录页面和其他类型的滥用流量，如l7dos攻击。使用可能有数百万个域和更多的规则来执行此操作会立即变得更加复杂。本文将介绍我们如何实现一个能够在网络边缘快速准确运行的速率限制器，该限制器能够应对Cloudflare的巨大流量。我们就在本地做吧！由于Cloudflare边缘服务器正在运行NGINX，我们先来看看stock rate limiting模块是如何工作的：http协议{limit_req_zone$binary_remote_addr zone=速率限制区：10m速率=15r/m;...服务器{...位置/api/昂贵的\u端点{limit_req zone=速率限制区；}}}这个模块工作得很好：使用起来相当简单（但是每次更改都需要重新加载配置），而且非常高效。唯一的问题是，如果传入的请求分布在大量的服务器上，这将不再有效。显而易见的选择是使用某种集中的数据存储。感谢NGINX的Lua脚本模块，我们已经广泛地使用它，我们可以使用任何类型的中央数据后端轻松地实现类似的逻辑。但是，另一个问题出现了：如何使之快速高效？条条大路通罗马？不是选播！由于Cloudflare有一个庞大且多样化的网络，将所有计数器报告到单个中心点并不是一个现实的解决方案，因为延迟太高，而且保证中央服务的可用性会带来更多挑战。首先，让我们看看Cloudflare网络中的流量是如何路由的。所有到边缘服务器的流量都是选播流量。这意味着我们在全球范围内为给定的web应用程序、站点或API公布相同的IP地址，流量将自动且一致地路由到最近的实时数据中心。这个属性非常有价值：我们确信，在正常情况下[1]，来自单个IP地址的流量将始终到达同一个PoP。不幸的是，每个新的TCP连接可能会命中PoP中的不同服务器。但我们仍然可以缩小我们的问题：我们实际上可以在每个PoP内部创建一个独立的计数系统。这在很大程度上解决了延迟问题，并大大提高了可用性。存储计数器在Cloudflare，我们的边缘网络中的每台服务器都尽可能独立，以简化管理。不幸的是，对于速率限制，我们发现我们确实需要在许多不同的服务器上共享数据。我们在过去的SSL会话id中也遇到过类似的问题：每个服务器都需要获取关于过去连接的TLS连接数据。为了解决这个问题，我们在每个pop中创建了一个Twemproxy集群：这允许我们在多个服务器上分割memcache[2]数据库。一个一致的哈希算法可以确保在调整集群大小时，只有少数几个键以不同的方式散列。在我们的体系结构中，每台服务器托管一个数据库碎片。因为我们已经有了这个系统的经验，所以我们想利用它来限制利率。算法现在让我们更深入地了解不同的速率限制算法是如何工作的。下一段中我们所说的采样周期是计数器的参考时间单位（对于10个请求/秒的规则，为1秒，对于600个请求/分钟的规则，为1分钟，…）。最简单的实现是简单地增加一个计数器，我们在每个采样周期开始时重置它。这是可行的，但不是非常准确，因为计数器会在固定的时间间隔内被任意重置，允许正常的流量峰值通过速率限制器。对于资源密集型端点来说，这可能是一个问题。另一种解决方案是存储每个请求的时间戳，并统计在上一个采样周期内接收了多少个请求。这是更准确的，但有巨大的处理和内存需求，因为检查计数器的状态需要读取和处理大量数据，尤其是如果您希望在较长时间内（例如每小时5000个请求）进行速率限制。leaky bucket算法允许在获得更好的资源的同时获得更高的精确度（这就是stock NGINX模块正在使用的）。从概念上讲，它的工作原理是在每个请求进来时递增一个计数器。同一个计数器也会根据允许的请求率随时间递减，直到达到零。bucket的容量是您可以接受的"突发"流量（重要的是，合法流量并不总是完全规则的）。如果存储桶已满（尽管已衰减），则进一步的请求将得到缓解。然而，在我们的案例中，这种方法有两个缺点：它有两个参数（平均速率和突发）并不总是很容易调整我们被限制使用memcached协议，并且这个算法需要多个不同的操作，而这些操作是我们无法以原子方式完成的[3]所以情况是唯一可用的操作是GET、SET和INCR（原子增量）。推窗救人CC BY-SA 2.0图像朴素的固定窗口算法实际上没有那么糟糕：我们只需要解决在每个采样周期中完全重置计数器的问题。但实际上，我们不能仅仅使用上一个计数器的信息来推断请求速率的精确近似值吗？假设我在一个API端点上设置了每分钟50个请求的限制。柜台可以这样想：在这种情况下，我在15秒前开始的当前一分钟内执行了18个请求，在前一分钟内完成了42个请求。基于此信息，速率近似计算如下：费率=42*（（60-15）/60）+18=42*0.75+18=49.5个请求下一秒再提出一个请求，速率限制器就会非常生气！此算法假设在前一个采样周期（可以是任何时间跨度）内请求的速率是恒定的，这就是为什么结果只是实际速率的近似值。该算法可以改进，但在实践中证明它足够好：它平滑了固定窗口方法存在的流量峰值问题它非常容易理解和配置：没有平均流量和突发流量，较长的采样周期可以用来达到相同的效果它仍然非常准确，对来自27万个不同来源的4亿个请求的分析显示：0.003%的请求被错误地允许或费率受限实际汇率与近似汇率平均相差6%尽管生成的流量略高于阈值（假阴性），但允许3个信源，实际速率比阈值速率高出不到15%所有缓解的来源均未低于阈值（假阳性）此外，在我们的案例中，它提供了有趣的特性：小内存使用：每个计数器只有两个数字递增一个计数器可以通过发送一个INCR命令来完成计算速率相当简单：一个GET命令[4]和一些非常简单、快速的数学运算因此，我们终于可以实现一个好的计数系统，只需使用几个memcache原语，而不需要太多的争用。但我们对此并不满意：它需要一个memcached查询来获取速率。在Cloudflare，我们看到了一些有史以来最大的L7攻击。我们知道大规模的攻击会像这样摧毁memcached集群。更重要的是，即使在正常情况下，这样的操作也会稍微减慢合法请求的速度。这是不可接受的。这就是为什么增量作业在不减慢请求速度的情况下异步运行的原因。如果请求速率高于阈值，则会存储另一段数据，要求PoP中的所有服务器开始对该客户机应用缓解措施。在请求处理过程中只检查这部分信息。更有趣的是：一旦缓解措施开始，我们就知道它何时结束。这意味着我们可以在服务器内存中缓存这些信息。一旦一个服务器开始减轻一个客户机，它甚至不会运行另一个查询，它可能会看到来自该源的后续请求！最后一个调整使我们能够有效地缓解大型L7攻击，而不会明显地惩罚合法请求。结论尽管是一个年轻的产品，速率限制器已经被许多客户用来控制其源服务器接收请求的速率。速率限制器已经每天处理数十亿个请求，我们最近以每秒40万个请求的速度缓解了攻击，而不会降低合法用户的服务质量。我们刚刚开始探索如何利用这个新工具有效地保护我们的客户。我们正在寻找更高级的优化，并在现有工作的基础上创建新功能。对在网络边缘的数千台服务器上运行的高性能代码感兴趣吗？考虑申请我们的空缺职位！anycast路由更改的内部工作原理不在本文的讨论范围之内，但是我们可以假设，在本例中，它们非常罕见。↩︎Twemproxy也支持Redis，但是我们现有的基础设施是由Twemcache（Memcached fork）支持的↩︎Memcache支持CAS（Compare-And-S