Проектирование системы ограничения тока на основе Redis

база данных

В этой статье описываетсяПроектирование системы ограничения тока на основе Redis, в основном речь идет о системе ограничения токаТекущая стратегия ограниченияДизайн этой функции; с точки зрения реализации алгоритм используетведро с жетонамиАлгоритм доступа к Redis с помощью lua-скрипта.

1. Концепция

In computer networks, rate limiting is used to control the rate of traffic sent or received by a network interface controller and is used to prevent DoS attacks

Переведите как я понимаю: ограничение тока для системыВходящий и исходящий трафикпровестиконтроль, чтобы предотвратить большой поток в и из, что приводит кресурсНедостаточно, система нестабильна.

Текущая система ограничения является компонентом управления доступом к ресурсам, управляющим двумя основными функциями:Текущая стратегия ограниченияистратегия автоматического выключателя, Что касается стратегии автоматического выключателя, разные системы имеют разные требования к стратегиям автоматического выключателя.Некоторые системы хотят отклонять напрямую, некоторые системы хотят ждать в очереди, некоторые системы хотят, чтобы услуги были снижены, а некоторые системы будут настраивать свои собственные стратегии автоматического выключателя. , Сложно перечислить по порядку, поэтому эта статья посвящена толькоТекущая стратегия ограничения Эта функция делает детальный дизайн.

противТекущая стратегия ограниченияДля этой функции в текущей системе ограничений есть два основных понятия: ресурсы и стратегии.

  • ресурс: или ограниченные ресурсы, объекты, управляемые потоком, такие как интерфейсы записи, интерфейсы внешних продавцов и интерфейсы чтения при большом трафике

  • Стратегия: Стратегия ограничения тока состоит из алгоритма ограничения тока и настраиваемых параметров.

стратегия автоматического выключателя:Запросы, превышающие пороговое значениеизстратегия обработки, это имя, которое я понимаю, а не основное заявление в отрасли.

2. Алгоритм ограничения тока

  • Ограничить мгновенный параллелизм

  • Ограничьте максимальное количество запросов во временном окне

  • ведро с жетонами

2.1. Ограничьте количество одновременных одновременных операций

определение: Мгновенноепараллелизм, количество одновременных запросов/транзакций, обрабатываемых системой

преимущество: этот алгоритм может достичь эффекта контроля количества параллелизма.

недостаток: Сценарий использования относительно прост и обычно используется для контроля входящего трафика.

реализация псевдокода Java:

AtomicInteger atomic = new AtomicInteger(1)try {        if(atomic.incrementAndGet() > 限流数) {           //熔断逻辑
    } else {        //处理逻辑    } } finally {
    atomic.decrementAndGet();
}скопировать код

2.2. Ограничьте максимальное количество запросов во временном окне

определение: максимальное количество запросов во временном окне, максимальное количество разрешенных запросов в указанном временном диапазоне.

преимущество: этот алгоритм может удовлетворить подавляющее большинство требований к управлению потоком данных, а максимальное количество запросов в секунду может быть напрямую преобразовано через максимальное количество запросов во временном окне (QPS = количество запросов/временное окно).

недостаток: Таким образом, трафик может быть неравномерным, и на небольшой объем трафика во временном окне приходится особенно большая доля.

Реализация кода Lua:

--- 资源唯一标识local key = KEYS[1]--- 时间窗最大并发数local max_window_concurrency = tonumber(ARGV[1])  --- 时间窗local window = tonumber(ARGV[2])   
--- 时间窗内当前并发数local curr_window_concurrency = tonumber(redis.call('get', key) or 0)  if current + 1 > limit then
    return falseelse
    redis.call("INCRBY", key,1)        if window > -1 then
        redis.call("expire", key,window)        end
    return trueendскопировать код

2.3. Ведро токенов

Алгоритм Описание

  • Если средняя скорость отправки, настроенная пользователем, равна r, токен добавляется в корзину каждые 1/r секунды.

  • Предполагается, что в корзине может храниться не более b токенов. Если корзина токенов заполнена, когда токен поступает, токен отбрасывается.

  • Когда трафик входит со скоростью v, токен берется из корзины со скоростью v, трафик, который получает токен, проходит, а трафик, который не получает токен, не проходит, и выполняется логика прерывателя цепи.

Атрибуты

  • В долгосрочной перспективе скорость соответствующего трафика зависит от скорости добавления токена и стабилизируется следующим образом: r

  • Поскольку ведро токенов имеет определенный объем хранилища, оно может выдерживать определенные всплески трафика.

    • M — максимально возможная скорость передачи в байтах/сек: M>r

    • T max = b/(M-r) Время выдерживания максимальной скорости передачи

    • B max = T max * M Трафик, передаваемый в течение времени, обеспечивающего максимальную скорость передачи

преимущество: Трафик относительно плавный и может выдерживать определенные всплески трафика.

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

3. Реализация проекта

3.1. Технический отбор

  • mysql: хранит метаданные, такие как параметры текущей политики ограничения

  • redis+lua: реализация алгоритма ведра токенов

Описание: Поскольку мы позиционируем Redis как: кеш, вычислительный носитель, метаданные хранятся в БД.

3.2 Схема архитектуры

3.3, структура данных

поле описывать
name Уникальный идентификатор корзины токенов
apps Список приложений, которые могут использовать ведро токенов
max_permits Максимальное количество токенов в ведре токенов
rate Скорость, с которой токены добавляются в корзину токенов
created_by основатель
updated_by программа обновления

Реализация текущей системы ограничения основана на Redis, который может не иметь ничего общего с приложением.Однако для того, чтобы выполнять унифицированное управление текущей конфигурацией ограничивающих метаданных, управлять и использовать ее в соответствии с измерением приложения, структурой данных был добавлен.appsЭто поле, если есть проблема, удобнее устранять неполадки.

3.4, реализация кода

3.4.1 Проблемы, возникающие при реализации кода

Ссылаясь на описание алгоритма ведра токенов, общая идея состоит в том, чтобы поместить поток для повторного выполнения в RateLimiter-клиенте, и поток добавляет токены в ведро токенов в соответствии с конфигурацией.Эта реализация имеет следующие недостатки:

  • Необходимо добавить повторяющийся поток для каждой конфигурации корзины токенов.

  • Точность интервала повторения недостаточно точна: потоку необходимо добавлять токен в корзину каждую 1/r секунды, а при r>1000 времени временной интервал выполнения потока вообще нельзя задать (из реализации производительности протестируйте позже, возможно, клиент RateLimiter предполагает скорость запроса QPS> 5000)

3.4.2 Решения

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

Алгоритм Описание

  • На основе приведенного выше алгоритма ведра токенов

  • Измените токен добавления на метод запуска, и токен будет использован для выполнения действия по добавлению токена.

  • При удалении токена рассчитайте количество токенов, которые следует добавить за этот период, рассчитав разницу во времени между последним добавленным токеном и текущим временем, а затем добавьте его в корзину.

    • curr_mill_second = текущее количество миллисекунд

    • last_mill_second = миллисекунды с момента последнего добавления токена

    • r = скорость добавления токенов

    • reserve_permits = (curr_mill_second-last_mill_second)/1000 * r

  • После добавления токена выполните логику извлечения токена.

3.4.3, реализация кода lua

--- 获取令牌--- 返回码--- 0 没有令牌桶配置--- -1 表示取令牌失败，也就是桶里没有令牌--- 1 表示取令牌成功--- @param key 令牌（资源）的唯一标识--- @param permits  请求令牌数量--- @param curr_mill_second 当前毫秒数--- @param context 使用令牌的应用标识local function acquire(key, permits, curr_mill_second, context)
    local rate_limit_info = redis.pcall("HMGET", key, "last_mill_second", "curr_permits", "max_permits", "rate", "apps")        local last_mill_second = rate_limit_info[1]        local curr_permits = tonumber(rate_limit_info[2])        local max_permits = tonumber(rate_limit_info[3])        local rate = rate_limit_info[4]        local apps = rate_limit_info[5]        --- 标识没有配置令牌桶
    if type(apps) == 'boolean' or apps == nil or not contains(apps, context) then
        return 0
    end
    local local_curr_permits = max_permits;        --- 令牌桶刚刚创建，上一次获取令牌的毫秒数为空
    --- 根据和上一次向桶里添加令牌的时间和当前时间差，触发式往桶里添加令牌
    --- 并且更新上一次向桶里添加令牌的时间
    --- 如果向桶里添加的令牌数不足一个，则不更新上一次向桶里添加令牌的时间
    if (type(last_mill_second) ~= 'boolean' and last_mill_second ~= false and last_mill_second ~= nil) then
        local reverse_permits = math.floor(((curr_mill_second - last_mill_second) / 1000) * rate)                local expect_curr_permits = reverse_permits + curr_permits;
        local_curr_permits = math.min(expect_curr_permits, max_permits);                --- 大于0表示不是第一次获取令牌，也没有向桶里添加令牌
        if (reverse_permits > 0) then
            redis.pcall("HSET", key, "last_mill_second", curr_mill_second)             end
    else
        redis.pcall("HSET", key, "last_mill_second", curr_mill_second)       end
    local result = -1
    if (local_curr_permits - permits >= 0) then
        result = 1
        redis.pcall("HSET", key, "curr_permits", local_curr_permits - permits)        else
        redis.pcall("HSET", key, "curr_permits", local_curr_permits)        end
    return resultendскопировать код

Я разместил все детали реализации текущей системы ограничений на github. Адрес gitbub: https://github.com/wukq/rate-limiter. Заинтересованные студенты могут проверить это. Из-за ограниченного опыта и знаний автор, код Если есть ошибки или неточности, прошу обсудить и исправить.

3.4.4 Интерфейс управления

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

  • Управление текущей конфигурацией ограничения по приложению

  • Разным людям назначаются разные разрешения; соответствующий персонал имеет разрешение на просмотр конфигурации, а ответственное лицо имеет разрешение на изменение и удаление конфигурации.

3.5 Тест производительности

настроить:aws-elasticache-redis 2 ядра 4g

Поскольку функция Ratelimiter-client относительно проста, она в основном обесценивает производительность Redis.

  • Однопоточное извлечение токена: количество запросов в секунду клиента Ratelimiter = 250/с

  • 10 потоков берут токены: QPS клиента Ratelimiter = 2000/с

  • 100 потоков берут токены: QPS клиента Ratelimiter = 5000/с

4. Резюме

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

недостаточный:

  • Redis Мы используем одноточечный redis, только master-slave, без кластера высокой доступности redis (можно использовать кластер высокой доступности redis, что принесет новые проблемы)

  • Текущая система ограничения в настоящее время реализована только на уровне приложения, а не на уровне приложения.шлюз интерфейсареализация на

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

Справочник:

1".RedisДизайн и реализация" 2."LuaРуководство по программированию

Справочная статья:

1. официальный сайт Redis

2. стандарт кодирования луа

3. Расскажите об ограничениях по току в системах с высокой степенью параллелизма.

4. Реализация Guava Ratelimiter

5. Вики-запись Token_bucket

    Категории