Розуміння лімітування запитів та його реалізація.

Цей блог — спосіб, через який я хочу пояснити все, що я навчився про обмеження швидкості (rate limiting). Я зроблю все максимально просто і поясню більшість речей, відповідаючи на основні питання. У блозі надано реалізації кількох алгоритмів з фрагментами коду.

Давайте глибше зануримось у питання "що, чому, де, коли і як" цього цікавого топіка.

Що таке обмеження швидкості?

Обмеження швидкості — це техніка, яка обмежує кількість запитів, які можна надіслати на певну точку доступу (endpoint). Це допомагає захистити ваш API від зловживань. Наприклад, щоб зупинити атаки грубою силою, ви можете обмежити кількість запитів до вашої точки доступу. Обмеження кількості запитів також допомагає уникнути виснаження ресурсів.

Ось кілька прикладів:

• Користувач може написати не більше 2 постів за секунду.
• Ви можете створити не більше 10 акаунтів на день з однієї IP-адреси.

Чому обмеження швидкості потрібне?

Одним із найпоширеніших способів атак в Інтернеті є DoS-атака (Denial of Service). Це спосіб, через який зловмисники намагаються "задушити" сервіс, надсилаючи множину запитів до API. Через це справжні користувачі платформи або застосунку страждають і втрачають доступ до сервісу. Щоб протидіяти таким подіям, впроваджуються обмеження швидкості. Це має багато переваг, деякі з яких:

• Запобігає виснаженню ресурсів через DoS-атаки.
• Зменшує витрати. Обмеження надмірних запитів означає менше серверів і більше ресурсів для API з високим пріоритетом.
• Запобігає перевантаженню серверів. Для зниження навантаження на сервер використовується обмежувач швидкості, який фільтрує надлишкові запити від ботів або через неправомірні дії користувачів.

Де розміщувати обмежувач швидкості?

У клієнт-серверній архітектурі обмежувач швидкості можна реалізувати як на стороні клієнта, так і на стороні сервера, і кожен з варіантів має свої переваги та недоліки.

Реалізація на стороні клієнта: Клієнт — ненадійне місце для впровадження обмеження швидкості, тому що запити клієнта можна легко підробити зловмисниками. Крім того, у нас може бути мало контролю над реалізацією на стороні клієнта.

Реалізація на стороні сервера:

Реалізація на стороні сервера.

Іншим способом реалізації є використання підходу через проміжне програмне забезпечення (middleware). Ми створюємо проміжне програмне забезпечення для обмеження швидкості, яке обмежує запити до наших API. Обмеження швидкості також можна реалізувати на рівні API шлюзу.

Реалізація на основі проміжного програмного забезпечення.

Далі в цьому блозі я реалізую підхід через проміжне програмне забезпечення для впровадження обмежувача швидкості.

Припустимо, наш API дозволяє 2 запити на секунду, а клієнт надсилає 3 запити до сервера протягом секунди. Перші два запити маршрутизуються до API серверів. Однак, проміжне програмне забезпечення для обмеження швидкості обмежує третій запит і повертає статус HTTP 429. Статус HTTP 429 означає, що користувач надіслав надмірну кількість запитів.

Коли використовувати обмежувач швидкості?

Досить неясне питання, на яке почати відповісти. Це хороша практика — впроваджувати контроль за використанням API точок доступу, але в деяких ситуаціях, де потрібно обмеження швидкості, є:

Якщо наші системи вразливі до перевантажень, то має бути належним чином впроваджено обмеження швидкості, адже воно може запобігти перевантаженню серверів і таким чином допомогти контролювати використання ресурсів системи.

Щоб захистити наші системи від ботів, скрейперів і атак на зразок Brute force, DoS та DDoS, ми повинні розглянути впровадження обмеження швидкості.
Це захищає справжніх користувачів, і тому сервіси залишаються функціональними.

Якщо наші системи схильні до різких сплесків трафіку, тоді ми також повинні розглянути використання обмежувача швидкості для точок доступу API, щоб системи не зламалися під час сплесків трафіку.

Існує ще кілька причин для впровадження обмежувача швидкості, і більшість з них залежить від конкретних випадків використання.

Як реалізувати обмежувач швидкості?

Для впровадження обмеження швидкості є кілька керованих рішень, які можна використовувати. Використання API шлюзу, такого як AWS, надає своє власне кероване рішення, але як реалізувати своє власне, ось це я і розгляну в цій частині блогу.

Для впровадження обмеження швидкості існує кілька алгоритмів, які використовуються для цього. Я поясню всі з них, з їхніми перевагами та недоліками, а також реалізую більшість з них через код.

ВАЖЛИВО

Для реалізації я використовую Nodejs, Expressjs, Redis, Docker та Postman. Я створю клас Rate limiter, і цей клас матиме конструктор, який встановлює redis=redisClient. Клас також буде мати реалізації різних алгоритмів через методи. Redis використовується для зберігання лічильників та ідентифікаторів користувачів. Я поясню код через коментарі у фрагментах. Також я реалізую об'єкт правил для відстеження правил реалізації. Його можна зберігати в Redis і отримувати за необхідності, просто для спрощення я реалізував його як об'єкт тут.

Почнемо.

Запустимо Redis інстанс локально через Docker:

docker run -p 6379:6379 -it redis/redis-stack-server:latest

npm init -y

npm i express redis

npm i @types/node @types/express --save-dev

Створимо файл index.js і налаштуємо простий сервер Express з точкою доступу /test для тестування нашого обмеження швидкості.

const express = require('express');  
const redis = require('redis');  
const { rateLimitMiddleware } = require('./middleware');  

const app = express();  

app.get('/test', rateLimitMiddleware, (req, res) => {  
 res.json({  
 msg: 'Hello AMAN',  
 });  
});  

app.listen(3000, () => {  
 console.log('Listening on port 3000');  
});

Створимо файл middleware.js для реалізації обмежувача швидкості.

Це алгоритми, які ми будемо обговорювати.

• Token bucket
• Leaky bucket
• Fixed window counter
• Sliding window log
• Sliding window counter

Token bucket

Алгоритм Token bucket є найефективнішим. Він простий і добре зрозумілий. Це хороший вибір для обмежувачів швидкості, які використовуються в розподілених системах.

Алгоритм Token Bucket.

Алгоритм можна описати наступним чином:

1. Токен додається в відро з фіксованою швидкістю. Припустимо, 1 токен за секунду.

2. Відро має ємність b токенів. Припустимо, 10 токенів.

3. Коли запит зроблений, токен видаляється з відра.

4.
Якщо в відрі немає токенів, повертається статусний код 429.

Реалізація.

const redis = require('redis');  

class RateLimiter {  
 constructor(redisClient) {  
 this.redis = redisClient;  
 }  

 // Алгоритм Token Bucket  
 async tokenBucket(key, rule) {  
 const now = Date.now();  
 const bucketId = `token_bucket:${key}`;  

 let bucket = await this.redis.get(bucketId);  
 bucket = bucket  
 ? JSON.parse(bucket)  
 : {  
 tokens: rule.capacity,  
 lastRefill: now,  
 };  

 const timePassed = now - bucket.lastRefill;  
 const tokensToAdd = Math.floor(timePassed * (rule.refillRate / 1000));  
 bucket.tokens = Math.min(rule.capacity, tokensToAdd + bucket.tokens);  
 bucket.lastRefill = now;  

 if (bucket.tokens >= 1) {  
 bucket.tokens -= 1;  
 await this.redis.set(bucketId, JSON.stringify(bucket));  
 return true;  
 }  
 await this.redis.set(bucketId, JSON.stringify(bucket));  
 return false;  
 }  
}  

const rules = {  
 tokenBucket: {  
 capacity: 2,  
 refillRate: 1,  
 },  
};  

const redisClient = redis.createClient();  

redisClient.on('error', (err) => {  
 console.error('Сталася помилка з клієнтом Redis:', err);  
});  

(async () => {  
 console.log('Here');  
 return await redisClient.connect();  
})();  

const rateLimiter = new RateLimiter(redisClient);  

async function rateLimitMiddleware(req, res, next) {  
 const clientIP = req.ip;  
 const rule = rules.tokenBucket;  

 try {  
 const allowed = await rateLimiter.tokenBucket(clientIP, rule);  
 if (!allowed) {  
 return res.status(429).json({  
 error: 'Забагато запитів',  
 });  
 }  
 next();  
 } catch (error) {  
 next(error);  
 }  
}  

module.exports = {  
 rateLimitMiddleware,  
};

node index.js

Тепер, використовуючи Postman, ми можемо протестувати точку доступу і побачити, що згідно з кодом, якщо ми зробимо більше ніж 2 запити, сервер поверне статусний код 429.

Переваги

• Легко реалізувати
• Ефективне використання пам'яті

Недоліки

• Для цього алгоритму потрібно встановити два параметри: швидкість поповнення та розмір відра

Leaky Bucket

Алгоритм Leaky Bucket схожий на алгоритм Token Bucket. Але замість того, щоб додавати токени в відро, він видаляє токени з відра.

Алгоритм можна описати наступним чином:

1. Відро має ємність b токенів. Припустимо, 10 токенів.

2. Коли запит надходить, ми додаємо 1 токен в відро.

3. Якщо відро заповнене, ми відхиляємо запит і повертаємо статусний код 429.

4. Якщо відро не заповнене, ми дозволяємо запит і забираємо 1 токен з відра.

5. Токени видаляються з фіксованою швидкістю r токенів за секунду.
   Припустимо, 1 токен на секунду.

Реалізація

Додайте цей метод до об'єкта Rate Limiter, який ми створили раніше.

async leakyBucket(key, rule) {  
 const now = Date.now();  
 const bucketKey = `leaky_bucket:${key}`;  

 let bucket = await this.redis.get(bucketKey);  
 bucket = bucket  
 ? JSON.parse(bucket)  
 : {  
 water: 0,  
 lastLeaked: now,  
 };  

 const timePassed = now - bucket.lastLeaked;  
 const leaked = Math.floor(timePassed * (rule.leakRate / 1000));  
 bucket.water = Math.max(0, bucket.water - leaked);  
 bucket.lastLeaked = now;  

 if (bucket.water < rule.capacity) {  
 bucket.water += 1;  
 await this.redis.set(bucketKey, JSON.stringify(bucket));  
 return true;  
 }  

 await this.redis.set(bucketKey, JSON.stringify(bucket));  
 return false;  
 }

Додайте це до об'єкта правил.

leakyBucket: {  
 capacity: 5,  
 leakRate: 1,  
 }

Змініть виклик методу та реалізувати це.

async function rateLimitMiddleware(req, res, next) {  
 const clientIP = req.ip;  
 const rule = rules.leakyBucket;  

 try {  
 const allowed = await rateLimiter.leakyBucket(clientIP, rule);  
 if (!allowed) {  
 return res.status(429).json({  
 error: 'Забагато запитів',  
 });  
 }  
 next();  
 } catch (error) {  
 next(error);  
 }  
}

Тепер протестуйте точку доступу за допомогою Postman.

Переваги

• Ефективне використання пам'яті
• Легко реалізувати
• Запити обробляються з фіксованою швидкістю

Недоліки

• Для цього алгоритму потрібно встановити два параметри: швидкість витоку та розмір відра

Fixed window counter

Алгоритм фіксованого лічильника є найпростіший алгоритм. Проблема алгоритму фіксованого лічильника виникає на межах часового вікна. Наприклад, припустимо, що лічильник порожній на 10:59, і надходить 10 запитів. Ці запити будуть оброблені. О 11:00 приходить ще 10 запитів, які також будуть прийняті, оскільки лічильник порожній. Такий сценарій призводить до порушення ліміту запитів, і ліміт 10 запитів на годину не витримується.

Алгоритм можна описати наступним чином:

1. Часова шкала розділяється на фіксовані часові вікна.
2. Кожне часове вікно має лічильник.
3. Коли приходить запит, лічильник для поточному часового вікна збільшується.

4. Якщо лічильник перевищує ліміт запитів, запит відхиляється.

5. Якщо лічильник менший за ліміт запитів, запит приймається.

Реалізація

async fixedWindowCounter(key, rule) {  
 const windowKey = `fixed_window:${key}:${Math.floor(  
 Date.now() / rule.windowSize  
 )}`;  

 const count = await this.redis.incr(windowKey);  
 if (count === 1) {  
 this.redis.expire(windowKey, Math.ceil(rule.windowSize / 1000));  
 }  

 return count <= rule.maxRequests;  
 }

Додайте вищезазначений метод до класу RateLimiter.

fixedWindow: {  
 windowSize: 60000,  
 maxRequests: 30,  
 }

Додайте це до об'єкта правил.

Тепер змініть виклик методу і протестуйте це за допомогою Postman.

async function rateLimitMiddleware(req, res, next) {  
 const clientIP = req.ip;  
 const rule = rules.fixedWindow;  

 try {  
 const allowed = await rateLimiter.fixedWindow(clientIP, rule);  
 if (!allowed) {  
 return res.status(429).json({  
 error: 'Забагато запитів',  
 });  
 }  
 next();  
 } catch (error) {  
 next(error);  
 }  
}

Переваги

• Ефективне використання пам'яті
• Легко реалізувати
• Нові запити не блокуються старими

Недоліки

• Одноразовий сплеск запитів наприкінці часового вікна може перевищити ліміт запитів

Sliding window log

Алгоритм фіксованого лічильника є хорошим, але має проблему з дозволом сплеску запитів, що проходять на межах вікна. Алгоритм Sliding Window Counter вирішує цю проблему, переміщаючи вікно вперед, коли надходить запит. Це дозволяє здійснювати більш точне лімітування запитів.

Алгоритм можна описати наступним чином:

1. Створити кеш для міток часу.

2.
Коли приходить новий запит, видаляйте всі застарілі мітки часу з кешу. Під застарілими маються на увазі мітки часу, які старші за розмір вікна.

1. Додайте нову мітку часу в кеш.

2. Якщо кількість міток часу в кеші перевищує ліміт, відхиліть запит і поверніть статус код 429.

3. Якщо менше за ліміт, то прийміть запит і поверніть статус код 200.

Реалізація

async slidingWindowLog(key, rule) {  
 const now = Date.now();  
 const windowKey = `sliding_window_log:${key}`;  
 await this.redis.zAdd(windowKey, now, now.toString());  
 await this.redis.zRemRangeByScore(windowKey, '-inf', now - rule.windowSize);  
 const count = await this.redis.zCard(windowKey);  
 this.redis.expire(windowKey, Math.ceil(rule.windowSize / 1000));  
 return count <= rule.maxRequests;  
 }

Додайте це до об'єкта правил.

slidingWindowLog: {  
 windowSize: 60000,  
 maxRequests: 30,  
 }

Тепер змініть виклик методу та протестуйте це за допомогою Postman.

async function rateLimitMiddleware(req, res, next) {  
 const clientIP = req.ip;  
 const rule = rules.slidingWindowLog;  
 try {  
 const allowed = await rateLimiter.slidingWindowLog(clientIP, rule);  
 if (!allowed) {  
 return res.status(429).json({  
 error: 'Забагато запитів',  
 });  
 }  
 next();  
 } catch (error) {  
 next(error);  
 }  
}

Переваги

• Дуже точне лімітування запитів.

Недоліки

• Більш складна реалізація.
• Використання пам'яті зростає лінійно з часом.

Sliding window counter

Останній алгоритм, який ми розглянемо в цій статті, є своєрідним поєднанням алгоритмів фіксованого лічильника та логічного вікна ковзання. За допомогою цього алгоритму можна пом'якшити сплески трафіку та водночас відслідковувати трафік за останні n хвилин.

Алгоритм можна описати наступним чином:

1. Ми маємо вікно розміром N хвилин (у нашому випадку N=1)

2. Протягом перших 10 секунд надходить 5 запитів. [0:00–0:10]

3. У часі [01:15] надходить ще 10 запитів.

4. Максимальна кількість запитів обчислюється за наступною формулою:

Запити в поточному вікні + Запити в попередньому вікні * Процент перекриття поточного та попереднього вікон

1. Результат округлюється до найближчого цілого числа.

Реалізація

async slidingWindowCounter(key, rule) {  
 const now = Date.now();  
 const currentWindow = Math.floor(now / rule.windowSize);  
 const previousWindow = currentWindow - 1;  

 const currentKey = `sliding_window_counter:${key}:${currentWindow}`;  
 const previousKey = `sliding_window_counter:${key}:${previousWindow}`;  

 const currentCount = parseInt((await this.redis.get(currentKey)) || '0');  
 const previousCount = parseInt((await this.redis.get(previousKey)) || '0');  

 const previousWeight =  
 (rule.windowSize - (now % rule.windowSize)) / rule.windowSize;  
 const weightedCount = Math.ceil(  
 previousCount * previousWeight + currentCount  
 );  

 if (weightedCount < rule.maxRequests) {  
 await this.redis.incr(currentKey);  
 this.redis.expire(currentKey, Math.ceil(rule.windowSize / 1000) * 2);  
 return true;  
 }  
 return false;  
 }

Додайте це правило до об'єкта правил.

slidingWindowCounter: {  
 windowSize: 60000,  
 maxRequests: 30,  
 }

Тепер змініть виклик методу і протестуйте це за допомогою Postman.

async function rateLimitMiddleware(req, res, next) {  
 const clientIP = req.ip;  
 const rule = rules.slidingWindowCounter;  
 try {  
 const allowed = await rateLimiter.slidingWindowCounter(clientIP, rule);  
 if (!allowed) {  
 return res.status(429).json({  
 error: 'Забагато запитів',  
 });  
 }  
 next();  
 } catch (error) {  
 next(error);  
 }  
}

Переваги

• Ефективне використання пам'яті
• Сплески пом'якшуються

Недоліки

• Метод ефективний лише тоді, коли вікно для огляду не надто суворе. Він дає приблизну оцінку реальної швидкості, оскільки припускає, що запити в попередньому вікні рівномірно розподілені.

Це все, що стосується цієї теми лімітування запитів.
Більш просунута версія цього може бути реалізована таким чином, щоб правила були змінними, а також, коли запити будуть обмежені, ми зможемо додавати відповідні заголовки для цього.

Цей блог скоро буде оновлено з більш складними темами, які включатимуть просунуті реалізації лімітерів запитів та їх імплементації в розподіленому середовищі.

Джерела

• Лімітування запитів в NGINX — https://www.nginx.com/blog/rate-limiting-nginx/
• Стратегії та техніки лімітування запитів — https://cloud.google.com/architecture/rate-limiting-strategies-techniques
• Що таке лімітування запитів? — https://www.cloudflare.com/learning/bots/what-is-rate-limiting/
• Як ми створили систему лімітування запитів, здатну масштабуватись до мільйонів доменів — https://blog.cloudflare.com/counting-things-a-lot-of-different-things/
• Інтерв'ю з системного дизайну: посібник для інсайдерів
• YouTube (Arpit)

Перекладено з: Understanding rate limiting and its implementation.