高效利用具有速率限制的API（Echo Nest）与分布式客户端

Question

背景

Echo Nest有一个限速API。使用API密钥识别的应用程序可以每分钟最多进行120个REST调用。服务响应包括上一分钟内所做调用的总数估计；滥用API（超过限制）可能导致API密钥被吊销。

当从单个机器（为客户提供服务的Web服务器）使用时，很容易控制访问-服务器完全了解请求历史记录并可以正确地进行调节。

但是，我正在开发一个程序，其中分布式、独立的客户端并行发出请求。

在这种情况下，什么是最佳解决方案就不太清楚了。而且通常问题看起来是不可解的-如果超过120个没有先前历史记录的客户端同时发出初始请求，那么速率将超过限制。

由于这是一个个人项目，客户端使用预计会间歇性地发生（爆发式），而且我的项目从未取得过巨大的成功，因此这不被认为是一个巨大的问题。更可能的问题是，在较短的时间内有少量客户端希望尽可能快地发出大量请求（例如，当客户端第一次启动时，可能需要异常地发出数千个请求 - 可能会有两个客户端在同一时间启动，因此它们必须合作共享可用带宽）。

鉴于上述所有情况，对于客户端来说，哪些适当的算法可以使其适当地限制速率？请注意，由于API返回了“所有”客户端在最后一分钟内的请求总数，因此有限的合作是可能的。

当前解决方案

我的当前解决方案（在撰写本文时 - 一个更好的方法已经给出作为答案）非常简单。每个客户端都记录了上次调用的时间以及在该调用中由API报告的最近一分钟内所做的调用数量。

如果调用数量小于60（限制的一半），则客户端不进行限流。这允许快速突发小数量的请求。

否则（即存在更多先前的请求时），客户端会计算其需要工作的限制速率（即period = 60 / (120 - 先前请求数量)），然后等待前一次调用和当前时间之间的间隔超过该期间（以秒为单位；每分钟60秒；每分钟最多120个请求）。这有效地限制了速率，以便如果它是单独操作的，它不会超出限制。

但上述方法存在问题。仔细思考后，您会发现对于大量请求，单个客户端会振荡并且无法达到最大吞吐量（部分原因是由于“初始爆发”突然“超出窗口”，部分原因是算法未充分利用其历史记录）。多个客户端将在一定程度上合作，但我怀疑这不是最优解决方案。

更好的解决方案：

我可以想象一个更好的解决方案，它使用客户端的完整本地历史记录，并使用隐马尔可夫模型来模拟其他客户端。因此，每个客户端都将使用API报告来模拟其他（未知的）客户端，并相应地调整其速率。

我还可以想象一种算法，适用于单个客户端，它从小突发无限行为逐渐过渡到适用于许多请求的最佳限制行为，而不会引入振荡。

这样的方法存在吗？有人可以提供实现或参考文献吗？有人能想到更好的启发式算法吗？

我想这在某个领域是一个已知的问题。在哪个领域？排队理论？

我还猜测（请参见早期评论）没有最优解，可能有一些传统/被接受的启发式算法，在实践中效果很好。我很想知道...目前我正在努力在已知的网络协议中识别类似的问题（如果是这样，我想Perlman会有一些美妙的解决方案）。

我也对需要中央服务器来帮助协作的解决方案感兴趣（在未来，如果程序变得流行，这点程度上的兴趣）。

免责声明

这个问题并不是要批评Echo Nest；他们的服务和使用条件非常好。但是，我越想如何最好地使用它，它就变得越复杂/有趣...

此外，每个客户端都有一个本地缓存用于避免重复调用。

更新 可能相关的论文。

- andrew cooke

---

响应是否也告诉您当前分钟剩余的秒数，还是您也需要猜测？[编辑：实际上，我的问题对服务器的速率限制做出了可能不正确的假设。限制是在1分钟内120个请求，然后是一个新的1分钟时间段，还是在任何60秒的时间窗口内限制120个请求？] - Steve Jessop

虽然不是完全清楚，但我进行了一些简单的测试，我认为响应数字是最近60秒内请求的数量。换句话说，它似乎是一个滑动窗口。因此没有“当前分钟”。但我猜它实际上是在两者之间实现的（例如，他们将请求分组到5秒钟的容器中，并使用它来近似滑动窗口）。 - andrew cooke

好的，我假设使用滑动窗口。我不会声称这背后有任何特定的理论，但在每个请求之后，看一下API响应报告的当前使用情况，减去该客户端在过去60秒内发出的任何请求。这告诉您所有其他客户端的总使用情况，因此相应地规划该客户端的使用情况。然后您有两个选择：（1）使用所有可用配额，冒着让其他客户端饥饿的风险（尤其是在此客户端爆发期间进入的新客户端），或者（2）保持持续使用量小于120，并留出空间供新客户端启动。 - Steve Jessop

如果您有一个中央服务器来协助协作，那么您可以使用它在多个客户端之间“公平”地分配配额。基本模型可以是客户端请求允许进行 N 次请求，并在接下来的 t 秒内获得允许进行 K <= N 次请求。然后，如果需要，服务器可以根据客户端想要进行的请求数量和请求原因对客户端进行优先处理。 - Steve Jessop

当然，但你究竟如何做到这一点呢？例如，您不希望仅消耗所有剩余的使用量，因为这将不留任何给新客户。那么，您如何估计其他客户正在使用什么？也许您应该使用随时间变化的平均值？您可以编写一些复杂的代码，假设一个非常特定的模型，但我敢打赌，当其他客户不遵循该模型时，它会不稳定。所以我的直觉是有一种更健壮的启发式方法...（可能已经为某人所知）。但大多数速率限制都是基于服务器的。 - andrew cooke

Answer 1

以上方法虽然可行，但是太过繁琐，代码也很混乱。现在我正在采用一种更简单的方法：

• Make a call
• From the response, note the limit and count

• Calculate

  barrier = now() + 60 / max(1, (limit - count))**greedy
  

• On the next call, wait until barrier

这个想法非常简单：你应该等待与每分钟剩余请求数量成比例的一段时间。例如，如果计数为39，限制为40，则需要等待整整一分钟。但是，如果计数为零，则可以很快地发出请求。参数“greedy”是一个权衡因素-当大于1时，“第一次”调用会更快，但是您更有可能达到限制并等待60秒。

这种方法的性能类似于上面的方法，但是更加健壮。当客户端“突发”时，尤其是在需求低的情况下，这种方法特别好，因为上述方法试图估计线性速率时会感到困惑，而这种方法会让客户端在需求低时“窃取”一些快速请求。

代码可以在这里找到。

- andrew cooke

---

你考虑过令牌桶算法吗？(http://en.wikipedia.org/wiki/Token_bucket) 我在处理突发客户端请求时使用它，但在你的情况下，跨多个客户端进行协调会使实现更加具有挑战性。 - sw1nn

Answer 2

经过一些实验，似乎最重要的是尽可能准确地估计当前连接速率的上限。

每个客户端可以使用时间戳队列跟踪自己（本地）的连接速率。每次连接都会向队列中添加一个时间戳，并且超过一分钟的时间戳将被丢弃。然后从第一个和最后一个时间戳以及条目数（减一）中找到“长期”（一分钟以上）平均速率。从最后两个请求的时间可以找到“短期”（瞬时）速率。上限是这两个值中的最大值。

每个客户端还可以估计外部（其他客户端）的连接速率。从服务器报告的过去一分钟内“已使用”的连接数（通过上述队列中的本地连接进行校正）可以找到“长期”速率。从上一个请求以来的“已使用”数字（减去本地连接的一个），按时间差缩放可以估算出“短期”速率。同样，使用这两个值中的最大值作为上限。

每个客户端计算这两个速率（本地和外部），然后将它们相加以估计连接服务器的总速率上限。该值与目标速率带进行比较，目前设置为最大值的80%到90%之间（每分钟0.8到0.9 * 120）。

根据估计速率和目标速率之间的差异，每个客户端修改自己的连接速率。这是通过取先前的增量（上次连接和上上次连接之间的时间）并将其缩放1.1倍（如果速率超过目标）或0.9倍（如果速率低于目标）来完成的。然后，客户端拒绝建立新连接，直到经过缩放的增量已经过去（如果请求了新连接，则通过睡眠来实现）。

最后，以上内容并未强制所有客户端平均共享带宽。因此，我将本地速率估计值增加了10％。这会导致高速率客户端的速率被优先高估，从而使他们更有可能减少其速率。通过这种方式，“贪婪”客户端具有稍微更强的压力来减少消耗，从而在长期内保持资源分配的平衡。

重要的见解如下：

• 通过采用“长期”和“短期”估计值的最大值，系统在启动额外客户端时是保守的（更稳定）。

• 除非客户端数量为零或一，否则没有客户端知道总客户端数量，但所有客户端都运行相同的代码，因此可以“信任”彼此。

• 基于上述情况，您无法进行“精确”的计算以确定使用什么速率，但可以根据全局速率进行“恒定”的修正（在本例中，+/- 10％因子）。

• 客户端连接频率的调整是针对最后两个连接之间的差异进行的（基于整个分钟的平均值进行调整过于缓慢且会导致振荡）。

• 通过轻微惩罚贪婪的客户端，可以实现平衡的消耗。

在（有限的）实验中，这个方法表现得相当不错（即使是在多个客户端同时启动的最坏情况下）。主要缺点是：（1）它不允许初始“突发”（如果服务器只有少数客户端并且客户端只有少量请求，则可以提高吞吐量）；（2）系统仍然会在大约一分钟内振荡（见下文）；（3）处理更多的客户端（在最坏的情况下，例如它们都同时启动）需要更大的增益（例如20％的校正而不是10％），这往往会使系统不稳定。

测试服务器报告的“已使用”量，根据时间（Unix纪元）绘制。这是针对四个客户端（彩色）尝试尽可能消耗数据的情况。

振荡来自通常的源头-修正滞后信号。通过（1）使用速率的上限（从瞬时值预测长期速率）和（2）使用目标带来抑制它们。这就是为什么需要有一个理解控制理论的人提供答案的原因...

我不清楚分别估计本地和外部速率是否重要（如果其中一个的短期速率很高，而另一个的长期速率很高，则可能有所帮助），但我怀疑去除它不会改善事情。

总之：对于这种方法，这几乎都是我预期的。它有点起作用，但因为它是一种简单的反馈式方法，所以只在有限的参数范围内稳定。我不知道可能有什么替代方案。

- andrew cooke

Answer 3

既然您正在使用Echonest API，为什么不利用每个API调用返回的速率限制标头呢？

通常情况下，您每分钟可以获得120个请求。有三个标头可以帮助您自我调节API消耗：

X-Ratelimit-Used
X-Ratelimit-Remaining
X-Ratelimit-Limit

**（注意'Ratelimit'中的小写字母'l'--文档让你觉得它应该是大写字母，但实际上它是小写字母。）

这些计数考虑了使用您的API密钥的其他进程所做的调用。

相当不错，不是吗？但是，我很遗憾有一个问题...

每分钟120个请求确实是一个上限。您不能指望它。文档指出该值可以根据系统负载波动。我在某些调用中看到过它低至约40，有时甚至低于零（我真希望那是echonest API中的错误！）

您可以采取的一种方法是，一旦利用率（已使用除以限制）达到一定阈值，就减缓速度。 但是请记住，在下一次调用中，您的限制可能已经调整下载足够大，以致“已使用”大于“限制”。

在某种程度上，这很有效。由于Echonest没有以可预测的方式调整限制，因此很难在实践中避免400。

以下是我发现有用的一些链接：

http://blog.echonest.com/post/15242456852/managing-your-api-rate-limit http://developer.echonest.com/docs/v4/#rate-limits

- Gary Dusbabek

---

我所提供的两个回答都使用了这些信息。问题在于当有多个未通信的客户端时，如何最好地使用它。因为如果一个客户端仅仅读取直到配额用尽，它可能会使其他客户端饿死。 - andrew cooke