限制远程请求速率的算法

Question

假设我有一个非常大的请求池，想要发送到远程主机。与任何服务器一样，远程主机的容量也是有限的。所有的消息最终都必须被传递，及时性是可取的，但并不重要。除了监视我发送的请求的响应时间和/或失败率之外，我无法知道远程主机的此容量。

我需要开发一个算法来以最大化吞吐量的速率发送请求，而不会使远程主机崩溃。

最佳输出变量似乎是请求之间的时间间隔，因此请求N在请求N-1之后M纳秒被调度。

我应该如何处理确定最优速率的问题？有没有什么论文可以供我参考呢？或者，有人能想出一些神奇的算法吗？以前有人这么做过吗？

注意:令牌桶也不是我想要的答案。我已经在使用像令牌桶这样的东西了，但我正在寻找一种方法来确定令牌应该添加到桶中的速率。

Answer 1

当我写我的网络爬虫时，我没有想出一个神奇的算法。我们使用了一些启发式方法，虽然肯定不是完美的，但似乎做得相当好。

首先，我们查看了站点的robots.txt文件。如果它有一个爬行延迟的入口，我们将永远不会超过它。

对于其他服务器，我们将保持最后n个请求所需时间的运行平均值(我认为我们确定的值为5)，并且我们将确保发送请求的频率永远不会超过该平均值。我们测量了从发出请求到完成处理响应的时间。

如果服务器超时，该请求的时间将进入运行平均值。

如果我们从服务器得到一个50x，在向该服务器发出另一个请求之前，我们会延迟相当长的时间(5分钟或更长时间)。重复50x的响应会导致我们停止请求，直到有人去查看问题所在。

我们还跟踪了40倍的响应。大量未找到或拒绝访问将导致爬虫程序停止处理某个域，并引发一个标志，以便有人可以查看它。

我们有一个分布式爬虫。没有单独的爬虫会向同一个域发出并发请求，而且我们有一些跨服务器通信，这使得多个服务器向同一个域发出并发请求是不寻常的。

我确信这不会最大化任何特定服务器上的吞吐量，但它确实让较大的站点非常繁忙。对我们来说更重要的是，它阻止了我们(主要是)被许多网站屏蔽。

我们还为许多使用API的站点提供了特殊情况处理。有些人会说他们的请求限制是什么，我们会调整这些网站的设置，这样我们就可以在线路上骑行了。但我们只有几十个。手动配置9000台服务器的请求频率(然后跟上更改)是不现实的。但是，您可以手动配置十几个或两个。