Створення Sliding Window Rate Limiter у Redis
Наша квота YouTube API двічі за минулий квартал вичерпувалася ще до 9:00 ранку. Через це наші стрічки трендів у половині регіонів залишалися застарілими.
Проблема полягала не у зростанні трафіку. Проблема була в нашому rate limiter.
Ми використовували лічильник із фіксованим вікном (fixed-window counter). Це дозволяло двом масивним сплескам API-викликів проходити, якщо вони припадали саме на межу вікна. Для глобального конвеєра з 8 регіонів таке перекриття меж траплялося часто. Це перетворювало нашу жорстку щоденну квоту на «витік бюджету».
Я замінив фіксоване вікно на sliding window log (журнал ковзного вікна), використовуючи Redis sorted sets.
Ось як це працює:
- Використовуйте
ZADD, щоб записати запит із часовою міткою. - Використовуйте
ZREMRANGEBYSCORE, щоб видалити старі записи поза межами вікна. - Використовуйте
ZCARD, щоб точно підрахувати, скільки запитів залишилося у вікні. - Використовуйте
PEXPIRE, щоб автоматично очищувати неактивні ключі.
Цей метод є точним. Тут немає меж, які можна перетнути.
Я реалізував це за допомогою Lua-скрипта в Redis. Це гарантує, що весь процес перевірки та запису є атомарним. Якщо виконувати ці кроки в коді додатка, стан гонитви (race conditions) дозволить пройти зайвим запитам.
Ключові технічні рішення для продакшену:
- Використовуйте
Redis TIME: не використовуйте часові мітки з ваших серверів додатків. Розсинхронізація годинників (clock skew) між серверами порушує точність вікна. - Зважені витрати: не всі API-виклики однакові. Один пошуковий запит може коштувати 100 одиниць, тоді як список відео — лише 1. Мій скрипт обробляє це, вставляючи кілька елементів за один виклик.
- Точний
Retry-After: дивлячись на найстаріший запис у sorted set, система точно обчислює, коли звільниться ліміт. - Логіка відмовостійкості: я використовую
EVALSHAіз резервним варіантомEVAL. Якщо кеш скриптів Redis очиститься під час перезапуску, додаток коректно це обробить.
Компромісом є пам'ять. Кожен запит займає близько 100 байтів. Для щоденної квоти у 10 000 одиниць це лише близько 1 МБ пам'яті. Для більшості випадків використання така точність варта витрат.
З моменту впровадження цієї зміни наша квота жодного разу не була вичерпана. Наші завдання завершуються коректно, замість того, щоб отримувати помилки 403.
Якщо ваш rate limiter скидається в рівну годину, у вас немає ліміту. У вас є лазівка.