Мне понадобилось ограничение скорости. Я написал вариант на 3 строки: счётчик и начало текущего окна. На ревью прозвучали слова про проблему границы, я перешёл на токен-бакет, все покивали, правка уехала. При этом я не смог бы сказать, сколько пропускает любой из двух. Поэтому собрал их все и подал на каждый 4 формы трафика.
Лимит везде один: 100 запросов за 60 секунд. Меряю я не то, сколько запросов прошло всего, а худшие 60 секунд в потоке пропущенных, потому что именно это число придётся пережить сервису за ограничителем.
Известный изъян настоящий. Положи 100 запросов в последнюю секунду одного окна и 100 в первую секунду следующего. Счётчик пропустит все 200, потому что с его точки зрения это 2 разных окна по 100. Шестьдесят секунд, лежащие на границе, содержат двойную норму.
Ещё ему нужен противник, который знает, где граница. На ровном потоке вдвое выше лимита тот же счётчик не превышает 100 никогда.
Тот, на который я перешёл
Токен-бакет, настроенный очевидным способом, то есть с ёмкостью, равной лимиту, пропускает 199 за окно на простом ровном переливе. Ни противника, ни расчёта времени, просто клиент шлёт быстрее, чем ему положено.
Арифметика перестаёт быть тонкой, как только число оказывается перед глазами. Ведро входит в окно полным. Эта ёмкость тратится сразу. Доливается оно ровно на лимит за окно. Долитое тратится по мере поступления. Ёмкость плюс долив это то, что окно способно выплатить. Поставь ёмкость равной лимиту: ответ будет двойным.
Уменьшение ведра это чинит. Ёмкость 10 держит худшее окно на 109 на всех формах, которые я подавал.
Чем уменьшение оплачено
Четвёртая форма трафика это клиент, который молчит 9 минут, а потом шлёт 300 запросов подряд. Пропустить из них 100 должен любой ограничитель: клиент всё это время был ниже лимита и просит ровно окно работы.
Окно-счётчик пропускает 100. Журнал отметок пропускает 100. Ведро размером с лимит пропускает 100. Ведро, которое я ужал до 10, пропускает 10 и отбивает 90 запросов, на которые клиент имел право.
Вот и весь размен в одной строке таблицы. Большое ведро щедро к тихому клиенту. Оно же пропускает переливающегося вдвое. Маленькое ведро держит черту и наказывает ровно того вежливого, кто ничего не накопил.
Тот, который не течёт
Журнал отметок пропускает ровно 100 на всех 4 формах. Это то, что он обещает: он хранит отметки времени и считает, что происходило в последние 60 секунд на самом деле.
Он же хранит до 100 отметок на клиента. По 8 байт это 800 байт против 16, которых хватает счётчику с началом окна. Счёту токенов со временем долива хватает тех же 16. То есть в 50 раз больше памяти на клиента плюс проход по началу списка на каждом запросе. Это и есть цена ограничителя, у которого нет формы трафика, где он худший в таблице.
Чего я не проверял
Всего этого на нескольких машинах, а нужно мне было именно там. 3 узла со счётчиком каждый это 3 окна и тройная протечка. Лечится либо общим хранилищем на горячем пути, либо делением лимита на 3, которое при неровном трафике выбрасывает две трети разрешённого. Ничего из этого я не мерил. Ещё я дал каждому ограничителю идеальные часы, а журнал отметок ровно настолько точен, насколько точны поданные ему отметки.
Узкое утверждение в том, что выбор идёт не между сломанным ограничителем и правильным. Каждый из дешёвых оказывается худшим на какой-то форме трафика. Какая форма достанется, то и решит, какой изъян ты купил.