Алгоритмы rate limiting
Вопрос
Какие алгоритмы ограничения частоты запросов вы знаете и чем они отличаются?
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Fixed window: просто, но всплеск на границе окон
Sliding window log: точно, но хранит метки всех запросов
Sliding window counter: приближение по двум окнам, дёшево
Token bucket: средняя скорость плюс разрешённый всплеск
Leaky bucket: ровный выходной поток
Что могут спросить следом
- Как сделать rate limiter распределённым?
- Что вернуть клиенту при превышении?
Разбор
Fixed window: счётчик на минуту, сбрасывается в начале минуты. Просто, но на границе окон клиент может прислать двойную норму. Sliding window log хранит время каждого запроса и считает за последние 60 секунд: точно, но дорого по памяти. Sliding window counter берёт текущее и предыдущее окно с весом, это почти точно и дёшево. Token bucket: ведро ёмкостью N пополняется со скоростью r, запрос забирает токен, поэтому разрешены всплески до N при средней скорости r. Leaky bucket выпускает запросы ровным потоком, сглаживая всплески. При превышении отдаю 429 с Retry-After. В распределённой системе счётчики в Redis, обновление атомарное через Lua.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.