В статье расскажу про задачу и её решение, связанную с организацией лимитов для выполнения различных операций и http запросов. Изначально задача звучала как создание распределенного решения, библиотека или микросервис на основе хранилища в redis, который бы мог обеспечить достаточный уровень отказоустойчивости и наблюдаемости. Функциональные и не функциональные требования были обычными для подобной задачи и казалось, что можно обойтись стандартным готовым решением, но не тут то было.

Основная проблема

Было точно ясно, что целевым хранилищем должен быть отказоустойчивый Redis Sentinel (Valkey Sentinel). Из всех алгоритмов наиболее подходящим был sliding window. Готовые решения покрывали 99% требований и хорошо справлялись с задачей одного лимита, но одного лимита было недостаточно.

Представим, что у нас есть действие аутентификации auth.createToken который мы хотим ограничить в 20 запросов в минуту. При этом мы бы не хотели, чтобы все 20 запросов проходили в первые секунды, это создает проблемы для безопасности системы, поэтому нам нужен еще один лимит в 5 запросов за 3 секунды.

Будем последовательно вызывать сперва лимит на 60 секунд, потом на 3 секунды. Что произойдет в случае достижения лимитов и продолжения вызова резервирования?

Проблема оказалось в том, что мы теряем лимиты в периоде минуты, так делать нельзя, попробуем поменять вызовы местами

То что нужно, но что если мы достигнем лимита в периоде 60 секунд, а 3х секундный период станет доступен?

Теперь мы можем столкнуться с проблемой, что минутный лимит уже доступен, но 3х секундный лимит блокирует вызов. С одной стороны это не такая уж и проблема, с другой стороны второй лимит может быть не таким коротким и мы потеряем драгоценные вызовы.

Решение

Для долгих и больших лимитов, у каждого это свой параметр в зависимости от нагрузки, лучше использовать другие хранилища и логику работы самого лимита. В моем случае лимит был максимум 600 операций за 10 минут. Но при этом был набор лимитов для одной операции, от одного до пяти. Все эти лимиты нужно проверять транзакционно.

Конфигурация лимитов стала выглядеть так:

limits:
  - name: "auth.createToken"
    config:
      - limit: 20
        period: 60
      - limit: 5
        period: 3
  - name: "service.actionName"
    config:
      - limit: 600
        period: 600
      - limit: 30
        period: 20

Количество конфигураций для одного лимита не ограничено. Нужно четко понимать как распределять лимиты, чтобы один ограничивал действия другого так, чтобы другой был все еще полезен. Например, если у нас есть лимит 600 запросов за 600 секунд, то лимит 10 запросов за 10 секунд будет полностью закрывать первый, мы точно не выйдем за его пределы. Отношение числа запросов к периоду должно только увеличиваться по мере уменьшения периода.

В нашем случае правило соблюдается, ведь отношение лимита к периоду только увеличивается. Таким образом лимит с периодом в 60 секунд будет иметь смысл.

Следующим вызовом стало то, что после блокировки нужно четко понимать какой именно лимит стал причиной отказа. Еще хочется понимать, в какой именно момент будет освобожден каждый из лимитов, нужно максимум статистики. В результате получился следующий lua скрипт для redis:

-- KEYS[1] - ключ сортированного набора для хранения таймстемпов.
-- ARGV[1] - текущий временной штамп в секундах.
-- ARGV[2] - максимальный период для удаления устаревших значений в секундах. Например, 60 для примера ниже.
-- ARGV[3] - сериализованный в JSON массив окон с лимитами в секундах. Например, '[{"limit": 60, "period": 60}, {"limit": 5, "period": 1}]'.

-- Создаем переменные на основе входных параметров.
local current_time = tonumber(ARGV[1])
local max_period = tonumber(ARGV[2])
local limits = cjson.decode(ARGV[3])

-- Период в секундах, для которого не удается резервировать токен.
local failed_period = 0

-- Удаляем таймстемпы, вышедшие за пределы максимального окна.
redis.call('ZREMRANGEBYSCORE', KEYS[1], "-inf", current_time - max_period)

-- Пытаемся найти период, в котором резервирование невозможно.
for i, limit in ipairs(limits) do
	-- Получаем количество таймстемпов в текущем окне
    local count = redis.call('ZCOUNT', KEYS[1], current_time - limit["period"], "+inf")
	
	-- Если количество таймстемпов превышает лимит, то резервирование невозможно.
	if count >= limit["limit"] then
		failed_period = limit["period"]
		break
	end
end

-- Добавляем текущий таймстемп, если запрос разрешен.
if failed_period == 0 then
    -- Score может быть одинаковым, но member должен быть уникальным.
    redis.call('ZADD', KEYS[1], current_time, tostring(current_time) .. tostring(math.random(1000000, 9999999)))
	-- Указываем время жизни ключа сортированного набора.
	redis.call('EXPIRE', KEYS[1], max_period + 10) -- +10 секунд буфер.
end

-- Собираем статистику по лимитам.
local stats = {}
for i, limit in ipairs(limits) do
	-- Время, с которого начинается проверка на возможность резервирования для текущего лимита.
	local from_timestamp = current_time - limit["period"]

    -- Получаем количество таймстемпов в текущем окне.
    local count = redis.call('ZCOUNT', KEYS[1], from_timestamp, "+inf")

	-- Получаем время сброса лимита на основе первого таймстемпа в текущем окне.
	local reset_time = 0
	local first_time_stamp = redis.call('ZRANGEBYSCORE', KEYS[1], from_timestamp, "+inf", 'WITHSCORES', 'LIMIT', '0', '1')[2]
	if first_time_stamp ~= nil then
		reset_time = first_time_stamp + limit["period"]
	end

    -- Добавляем статистику по текущему лимиту
    table.insert(stats, {
		period = tonumber(limit["period"]), -- Период в секундах.
		limit = tonumber(limit["limit"]), -- Допустимое количество запросов в период.
		remaining = tonumber(limit["limit"] - count), -- Оставшееся количество запросов.
		reset_time = tonumber(reset_time), -- Время до следующего возможного запроса (сброса лимита).
		failure = limit["period"] == failed_period, -- Флаг блокировки по лимиту.
	})
end

-- Возвращаем флаг успешности и статистику по лимитам
return {failed_period == 0, cjson.encode(stats)}

В хранилище будет использован Sorted sets, подробная документация по которому есть на официальном сайте https://valkey.io/topics/sorted-sets/. Сортированный набор - это коллекция уникальных участников (members), отсортированных по соответствующей оценке (score). Когда более одного member имеет одинаковую оценку, members сортируются лексикографически, но нам это не особо важно. В нашем скрипте score является текущий unix timestamp (секунды), раз оценка может повторяться, то нет никаких проблем с тем, что в одну секунду прилетит сразу два резервирования лимита. Для уникальности member мы добавляем к текущему времени случайное число от 1_000_000 до 9_999_999.

Алгоритм работы

Представим, что у нас есть конфигурация как auth.createToken. Напомню, что это 20 резервирований за 60 секунд и 5 резервирований за 3 секунды. Мы выполнили 16 попыток резерва за 6 секунд в разное время, визуально это бы выглядело так:

Плюсы и минусы

Существуют другие виды алгоритмов, которые могут быть значительно более удобные в плане хранения данных, скорости работы и понятности, со своими минусами.

В нашем случае нет сложных вычислений и необходимости в хранении устаревших периодов. Есть только один ключ для одного правила. Есть крайне высокая точность в предоставлении доступа к резервированию. Возможность безболезненно менять конфигурацию на ходу. Конфигурация легко читаема и может содержать большое количество правил. Много полезной информации на выходе, можно сразу понять в чем причина блокировки и как скоро можно будет снова начать вызывать методы.

Из минусов большой объем данных в redis, хорошо что оперативная память стоит не так дорого.

Пример кода на golang. https://gist.github.com/yaBliznyk/8b66f3de4ea3c138c9d24f36f02d6a20