В чем заключается формальная ошибка корзины токенов и можно ли ее откалибровать?

Question

Я ищу способ регулирования скорости определенного события.У меня жесткое ограничение на количество событий в секунду, но я могу допустить некоторое количество ошибок.Реализация должна использовать как можно меньше памяти.В настоящее время мы сохраняем очередь меток времени, которая всегда точна, но было бы неплохо устранить объем памяти.

Алгоритм сегмента памяти токенов кажется подходящим, но он только гарантирует среднюю скорость.Это может нарушать лимит в зависимости от того, когда происходят события относительно точек пополнения токена.

Как сформулировать ошибку корзины токенов?Можно ли его откалибровать?

Answer 1

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

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

event_time = start_time + event_counter / rate

После каждого события увеличивайтеevent_counter и спать до тех пор, пока не наступит event_time следующего события (sleep(event_time - current_time) или аналогичное).

В моем втором предложении вам также потребуется сохранить длительность задержки, поэтому у вас будет трисохраняемые значения.

После каждого события спите до тех пор, пока не наступит задержка, и переходите к следующему событию.Также после каждого события (или просто если counter % n == 0 сделать это только после n событий) вы обновляете задержку: используя текущее время, время начала и счетчик, вы вычисляете текущую среднюю скорость;если оно слишком высокое, вы увеличиваете задержку;если оно слишком мало, вы уменьшаете задержку;в противном случае вы оставляете задержку без изменений.

Это автоматически определит среднюю задержку, необходимую для вашего типа события и скорости.Однако, если ваши события сильно различаются по продолжительности, у вас будут проблемы с плавностью.В худшем случае (с определенным изменением длительности) вы можете даже получить резонансные эффекты периодического увеличения и уменьшения задержек.