Блог

Главная - Вопросы по программированию - Алгоритм / структура данных для регулирования запросов

Алгоритм / структура данных для регулирования запросов

#algorithm #data-structures #throttling

#алгоритм #структуры данных #регулирование

Вопрос:

У меня есть интерфейс запроса, который вызывается много раз в секунду и выглядит примерно так:

 def do_something(timestamp_in_ms)

Я ищу способ выполнить простое регулирование запросов, которое гарантирует, что обрабатываются только первые N запросов за секунду, а остальные отбрасываются. В идеале это должно выполняться для каждого временного интервала, который длится секунду (например 00:00:00.123-00:00:01.123) вместо того, чтобы использовать только тактовые секунды (например, 00:00:00-00:00:01).

Дополнительная проблема заключается в том, что do_something это вызывается чрезвычайно часто, поэтому регулирование должно быть эффективным.

Ответ №1:

Вы могли бы использовать очередь, которая содержит временные метки предыдущих N-1 запросов и сравнивает временную метку нового запроса-кандидата с временной меткой самого раннего запроса в очереди.

  • если разница составляет более одной секунды, запрос-кандидат выполняется, а его временная метка добавляется в очередь;
  • если разница составляет менее одной секунды, запрос-кандидат отбрасывается.

Всякий раз, когда в очередь добавляется новая временная метка, самая старая временная метка выбрасывается.

Ресурсы:

Комментарии:

1. Я бы предположил, что концептуально очередь здесь должна быть реализована как кольцевой буфер?

2. @ZizhengTai Я не думаю, что это действительно имеет значение. Вы можете использовать любую реализацию очереди. Если вам нравятся кольцевые буферы, вы можете использовать кольцевой буфер. В Python уже есть классы queue.Queue , и queue.SimpleQueue поэтому я предлагаю использовать один из них, если вы специально не хотите получить возможность обучения для реализации своих собственных.