and*_*oke 11 algorithm networking feedback throttling distributed-computing
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的批评; 他们的服务和使用条件都很棒.但是我越想到如何最好地使用它,它变得越复杂/有趣......
此外,每个客户端都有一个本地缓存,用于避免重复调用.
上面的方法有效，但是噪音很大，而且代码很乱。我现在使用更简单的方法：
计算
barrier = now() + 60 / max(1, (limit - count))**greedy
barrier这个想法非常简单：您应该等待一段时间，该时间与该分钟内剩余的请求数量成正比。例如，如果计数为 39，限制为 40，则您将等待整整一分钟。但如果计数为零，那么您可以很快提出请求。该greedy参数是一种权衡 - 当大于 1 时，“第一次”调用会更快，但您更有可能达到限制并最终等待 60 秒。
这种方法的性能与上面的方法类似，而且更加稳健。当客户“突发”时，它特别好，因为上述方法在尝试估计线性速率时会感到困惑，而这将很高兴地让客户在需求较低时“窃取”一些快速请求。