algorithm - 限制请求的算法/数据结构

Question

我有一个每秒调用多次的请求接口，大致如下所示：

def do_something(timestamp_in_ms)

我正在寻找一种方法来进行简单的请求限制，以确保只处理一秒钟内的前 N ​​个请求，其余的被丢弃。理想情况下，这应该适用于每个持续一秒的时间间隔（例如 00:00:00.123-00:00:01.123），而不仅仅是时钟秒数（例如 00:00:00-00:00:01）。

另一个问题是do_something调用非常频繁，因此限制必须是高性能的。

标签： algorithmdata-structuresthrottling

Answer 1

您可以使用一个包含先前 N-1 个请求的时间戳的队列，并将新候选请求的时间戳与队列中最早请求的时间戳进行比较。

• 如果相差超过一秒，则执行候选请求并将其时间戳添加到队列中；
• 如果差值小于一秒，则抛出候选请求。

每当一个新的时间戳添加到队列中时，最旧的时间戳就会被丢弃。

资源：

• 维基百科上的队列
• 模块上的 Python 文档queue