12

背景

Echo Nest 有一个速率受限的 API。给定的应用程序（使用 API 密钥在请求中标识）每分钟最多可以进行 120 次 REST 调用。服务响应包括对最后一分钟呼叫总数的估计；重复滥用 API（超过限制）可能会导致 API 密钥被撤销。

当从单台机器（向客户端提供服务的 Web 服务器）上使用时，很容易控制访问 - 服务器完全了解请求的历史并可以正确地自我调节。

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

在这种情况下，最佳解决方案是什么就不太清楚了。总的来说，这个问题似乎是无法确定的——如果超过 120 个客户（都没有以前的历史记录）同时发出初始请求，那么速率将被超过。

但由于这是一个个人项目，预计客户使用是零星的（突发的），而且我的项目从未取得巨大成功，因此预计这不会是一个大问题。一个更可能的问题是，有时少数客户端希望尽快发出许多请求（例如，客户端可能需要在第一次启动时发出数千个请求 - 这是可能的两个客户端大约在同一时间启动，因此它们必须合作共享可用带宽）。

鉴于以上所有情况，什么是适合客户端的算法，以便他们适当地限制速率？ 请注意，有限的合作是可能的，因为 API 返回所有客户端在最后一分钟的请求总数。

当前解决方案

我目前的解决方案（当问题被写出来时——给出了一个更好的方法作为答案）非常简单。每个客户端都有最后一次调用的时间和最后一分钟调用次数的记录，由 API 报告，在该调用上。

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

否则（即，当有更多先前的请求时）客户端计算它需要工作的限制速率（即period = 60 / (120 - number of previous requests)），然后等待直到先前调用和当前时间之间的间隔超过该时间段（以秒为单位；60 秒分钟；每分钟最多 120 个请求）。这有效地限制了速率，因此，如果它单独行动，它不会超过限制。

但是上面有问题。如果您仔细考虑一下，您会发现对于大量请求，单个客户端会振荡并且不会达到最大吞吐量（这部分是因为“初始突发”会突然“落在窗口外”，部分是因为算法没有充分利用其历史）。并且多个客户会在一定程度上合作，但我怀疑它是最优的。

更好的解决方案

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

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

这种方法存在吗？任何人都可以提供实现或参考吗？谁能想到更好的启发式方法？

我想这是某个地方的已知问题。在什么领域？排队论？

我还猜测（参见前面的评论）没有最佳解决方案，并且可能有一些知识/传统/公认的启发式在实践中效果很好。我很想知道什么......目前我正在努力找出已知网络协议中的类似问题（我想如果是这样的话，Perlman 会有一些漂亮的解决方案）。

我也对需要中央服务器来帮助协作的解决方案感兴趣（在较小程度上，以供将来参考，如果该程序变得流行）。

免责声明

这个问题根本不是对 Echo Nest 的批评；他们的服务和使用条件都很棒。但是我越想如何最好地使用它，它就会变得越复杂/有趣......

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

更新

可能是相关论文。

4

3 回答 3

3

以上工作，但非常嘈杂，代码是一团糟。我现在使用一种更简单的方法：

  • 打个电话
  • 从响应中，注意限制和计数

  • 计算

    barrier = now() + 60 / max(1, (limit - count))**greedy
  • 在下一次通话中，等到barrier

这个想法很简单：你应该等待一段时间，这与那一分钟剩下的请求数量成正比。例如，如果 count 是 39，limit 是 40，那么你等待一整分钟。但是如果计数为零，那么您可以很快提出请求。该greedy参数是一个权衡 - 当大于 1 时，“第一次”调用会更快，但您更有可能达到限制并最终等待 60 秒。

它的性能类似于上面的方法，并且更加健壮。当客户端“突发”时特别好，因为上面的方法在尝试估计线性速率时会感到困惑，而这会很高兴地让客户端在需求低时“窃取”一些快速请求。

代码在这里。

于 2013-02-09T16:08:08.157 回答
1

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

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

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

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

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

最后，以上没有强制所有客户端平等共享带宽。因此，我在本地费率估算中增加了 10%。这具有优先高估利率高的客户的利率的效果，这使他们更有可能降低利率。通过这种方式，“贪婪”的客户减少消费的压力略大，从长远来看，这似乎足以保持资源分配的平衡。

重要的见解是：

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

  • 没有客户端知道客户端的总数（除非它是零或一），但所有客户端都运行相同的代码，因此可以相互“信任”。

  • 鉴于上述情况，您无法“准确”计算要使用的汇率，但您可以根据全局汇率进行“恒定”修正（在本例中为 +/- 10% 系数）。

  • 客户端连接频率的调整是针对最后两个连接之间的增量进行的（基于整分钟的平均值进行调整太慢并导致振荡）。

  • 通过对贪婪的客户进行轻微惩罚，可以实现均衡消费。

在（有限的）实验中，这工作得相当好（即使在多个客户端同时启动的最坏情况下）。主要缺点是：（1）它不允许初始“突发”（如果服务器的客户端很少而客户端只有几个请求，这将提高吞吐量）；(2) 系统仍会振荡约一分钟（见下文）；(3) 处理大量客户端（在最坏的情况下，例如如果它们都同时启动）需要更大的增益（例如 20% 的修正而不是 10%），这往往会使系统不太稳定。

阴谋

（测试）服务器报告的“使用”量，与时间（Unix 纪元）绘制。这是针对四个客户端（彩色）的，它们都试图消耗尽可能多的数据。

振荡来自通常的来源 - 修正滞后信号。它们通过 (1) 使用速率的上限（从瞬时值预测长期速率）和 (2) 使用目标频带来衰减。这就是为什么由了解控制理论的人提供的答案将受到赞赏......

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

总之：对于这种方法，这一切都和我预期的差不多。它有点工作，但因为它是一种简单的基于反馈的方法，它只能在有限的参数范围内稳定。我不知道有什么替代方案是可能的。

于 2012-08-28T09:32:41.387 回答
0

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

一般来说，您每分钟收到 120 个请求。有三个标头可以帮助您自我调节 API 消耗：

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

**（请注意“Ratelimit”中的小写“ell”——文档让您认为它应该大写，但实际上它是小写的。）

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

很整洁吧？好吧，恐怕有摩擦...

每分钟 120 个请求确实是一个上限。你不能指望它。该文档指出，该值可能会根据系统负载而波动。在我进行的一些调用中，我看到它低至 40ish，并且在某些情况下看到它低于零（我真的希望这是 echonest API 中的一个错误！）

您可以采取的一种方法是在利用率（使用除以限制）达到某个阈值时减慢速度。但请记住，在下一次调用时，您的下载限制可能已被调整得足够大，以至于“已使用”大于“限制”。

直到某一点为止，这都很好。由于 Echonest 不会以可预测的方式调整限制，因此在实践中很难避免 400 秒。

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

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

于 2013-03-01T20:16:12.973 回答