Нагруженная система (High-load system) - это система, в которой нагрузка (число пользователей, запросов, объём данных или другое) настолько велика, что одного сервера или простой архитектуры уже недостаточно
Нагрузка бывает разной:
Для системы, отвечающей на внешние запросы, выделяют такие характеристики:
Задержка (Latency) - время ответа на один запрос
Так как время ответа обычно не является постоянной величиной (из-за разной маршрутизации, планировании обработки пакетов в промежуточных узлах и так далее), рассматривают задержку как случайную величину. У получившегося распределения рассматривают:
Основные проблемы высоконагруженных систем являются:
Любая система имеет конечную пропускную способность. Если запросов приходит больше, чем она может обработать, деградация становится лавинообразной: растут очереди, растёт задержка, запросы начинают падать по таймауту, клиенты повторяют их (retry), и нагрузка растёт ещё сильнее.
Ограничения нужны, чтобы:
Главная идея состоит в том, отказ в части запросов контролируемо лучше, чем неконтролируемый отказ всей системы
Здесь применяют такие подходы:
Обратное давление (или Back pressure) - механизм, при котором перегруженный потребитель сообщает производителю о том, что нужно замедлить поток запросов
Без механизма “обратного давления” перегрузка превращается в неограниченные очереди, при которых память и задержка растут, из-за чего возникают ошибки нехватки ОЗУ (Out-of-Memory, OOM) и таймауты запросов
Способы реализации:
429 Too Many Requests или 503 Service Unavailable (часто с заголовком Retry-After, где указано предпочтительное время ожидания перед следующим запросом)Ограничение частоты запросов (Rate limit), то есть число запросов за определенный период
Ограничивают число не только всех глобально поступающих запросов, а объединенных по какому-либо признаку, например, с одного IP-адреса, от одного пользователя, для одной конечной точки (endpoint) и так далее
Обычно используется в REST API, обратных прокси и промежуточном ПО. В частности для REST API при превышении лимита возвращают HTTP-код 429 Too Many Requests и заголовок Retry-After
Для ограничения частоты популярны 4 алгоритма:
Время делится на окна - непересекающиеся интервалы по $t$ секунд, в каждом окне ведется подсчет запросов. Если число запросов превысило порог $N$ в этом окне, то следующие запросы отклоняются
Пример реализации фиксированного окна на языке Kotlin:
class FixedWindowLimiter(
private val limit: Int, // N, лимит на окно
private val windowMs: Long // t, длительность окна
) {
private var windowStart = System.currentTimeMillis()
private var count = 0
@Synchronized
fun allow(): Boolean {
val now = System.currentTimeMillis()
// окно закончилось, начинаем новое
if (now - windowStart >= windowMs) {
windowStart = now
count = 0
}
if (count < limit) {
count++
return true
}
return false
}
}
Достоинства такого алгоритма заключаются в том, что он очень прост, не требует много памяти, и легко реализуется в базах данных типа NoSQL (например, в Redis)
Недостаток состоит в том, что на границе переходов окон может произойти всплеск запросов, например, 100 запросов в последнюю секунду первого окна и 100 запросов в первую следующего, из-за чего получится 200 запросов за 2 секунды, тогда как порог - 100 запросов
В такой версии окно зафиксировано относительно текущего момента времени, то есть проверяется, не перешел ли счетчик через порог за последние $t$ секунд
У скользящего окна есть два варианта подсчета запросов за промежуток времени:
Журнал записей, в котором хранятся временные метки всех запросов
При появлении нового запроса проходимся по журналу и удаляем те временные метки, которые не входят в окно, а затем проверяем количество таких записей. Если количество не менее порога, то новый запрос отклоняем
class SlidingWindowLogLimiter(
private val limit: Int,
private val windowMs: Long
) {
private val timestamps = ArrayDeque<Long>()
@Synchronized
fun allow(): Boolean {
val now = System.currentTimeMillis()
// удаляем запросы, вышедшие за пределы окна
while (timestamps.isNotEmpty() && timestamps.first() <= now - windowMs) {
timestamps.removeFirst()
}
if (timestamps.size < limit) {
timestamps.addLast(now)
return true
}
return false
}
}
Можно заметить, что такой вариант имеет сложность $O(N)$ по памяти
Взвешенная оценка - храним счетчики запросов для текущего и предыдущего фиксированных окон. При получении запроса вычисляем оценку запросов взвешенную сумму $A \cdot T + B$, где $B$ - счетчик для текущего окна, $A$ - счетчик для предыдущего, а $T$ - доля предыдущего фиксированного окна, которое пересекается со скользящим окном
В отличие от фиксированного окна алгоритм скользящего окна предоставляет большую равномерность потока
Суть алгоритма: есть “корзина”, которая вмещает $N$ маркеров (или токенов). Каждый запрос забирает некоторое число маркеров, но при этом со временем в корзину добавляется некоторое число маркеров с указанной скоростью $v$. Если в корзине нет свободных маркеров для нового запроса, то он отклоняется
Пример реализации на Kotlin:
class TokenBucket(
private val ratePerSec: Double, // v, скорость пополнения маркеров
private val capacity: Double // N, максимум маркеров в ведре
) {
private var tokens = capacity
private var lastRefillNs = System.nanoTime()
@Synchronized
fun allow(cost: Double = 1.0): Boolean {
refill()
if (tokens >= cost) {
tokens -= cost
return true
}
return false
}
// пополняем ведро пропорционально прошедшему времени
private fun refill() {
val now = System.nanoTime()
val elapsedSec = (now - lastRefillNs) / 1_000_000_000.0
tokens = minOf(capacity, tokens + elapsedSec * ratePerSec)
lastRefillNs = now
}
}
Свойства такого алгоритма:
Суть алгоритма: есть “ведро”, которое заполняется запросами; у этого ведра есть вместимость $N$ - если новый запрос не вмещается в ведро, то он отклоняется. Запросы со временем “утекают” из ведра с фиксированной скоростью $v$
У протекающего ведра есть два варианта реализации:
Протекающее ведро как счетчик (Leaky bucket as a meter) - в этом варианте считается число запросов в ведре. Вместо количества запросов можно использовать маркеры - тогда получится маркерная корзина, но в которой счетчик считает занятые места, а не свободные
Пример реализации:
class LeakyBucket(
private val leakPerSec: Double, // скорость утечки запросов
private val capacity: Double // размер ведра
) {
private var level = 0.0
private var lastLeakNs = System.nanoTime()
@Synchronized
fun allow(): Boolean {
leak()
if (level + 1 <= capacity) {
level += 1
return true
}
return false // ведро переполнено
}
private fun leak() {
val now = System.nanoTime()
val elapsedSec = (now - lastLeakNs) / 1_000_000_000.0
level = maxOf(0.0, level - elapsedSec * leakPerSec)
lastLeakNs = now
}
}
Протекающее ведро как очередь (Leaky Bucket as a Queue) - в этом варианте запросы добавляются в очередь, из которой они уходят со скоростью $v$ и только потом обрабатываются, тем самым сглаживая поток
Свойства такого алгоритма:
В отличие от маркерной корзины протекающее ведро как очередь сглаживает выходной поток запросов