Интервьюер: Давай, молодой человек! Пожалуйста, сыграйте в 5 распространенных алгоритмов ограничения тока!

Java
  1. Мгновенный трафик слишком высок, сервис перегружен?
  2. Злоумышленники часто посещают сайт, вызывая простои сервера?
  3. Потребление сообщений слишком быстрое, что приводит к чрезмерной нагрузке на базу данных, снижению производительности или даже к сбою? ......

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

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

01 Фиксированное окно

Фиксированное окно, также известное как фиксированное окно (также известное как алгоритм счетчика, фиксированное окно) алгоритм ограничения тока, является простейшим алгоритмом ограничения тока.Максимальное количество посещений в единицу времени контролируется счетчиком, поддерживаемым в единице время.

Предполагая, что количество запросов в минуту ограничено не более 60, установить счетчик.При поступлении запроса, если счетчик достигает порога, запрос отклоняется, в противном случае счетчик увеличивается на 1, счетчик сбрасывается на 0 каждую минуту. Код реализован следующим образом:

public class CounterRateLimiter extends MyRateLimiter {
    /**
     * 每秒限制请求数
     */
    private final long permitsPerSecond;
    /**
     * 上一个窗口的开始时间
     */
    public long timestamp = System.currentTimeMillis();
    /**
     * 计数器
     */
    private int counter;

    public CounterRateLimiter(long permitsPerSecond) {
        this.permitsPerSecond = permitsPerSecond;
    }

    @Override
    public synchronized boolean tryAcquire() {
        long now = System.currentTimeMillis();
        // 窗口内请求数量小于阈值，更新计数放行，否则拒绝请求
        if (now - timestamp < 1000) {
            if (counter < permitsPerSecond) {
                counter++;
                return true;
            } else {
                return false;
            }
        }
        // 时间窗口过期，重置计数器和时间戳
        counter = 0;
        timestamp = now;
        return true;
    }
}

Самым большим преимуществом стационарных окон является то, чтоЛегко реализовать;а такжеНебольшой объем памяти, нам нужно только сохранить количество во временном окне; это гарантирует, что более свежие запросы обрабатываются без зависания новых запросов по мере накопления старых запросов. Конечно же, передкритическая проблема, когда два окна находятся на стыке, мгновенный расход может быть 2n.

02 Раздвижное окно

Чтобы предотвратить мгновенный трафик, фиксированное окно можно дополнительно разделить на несколько сеток, и каждый раз, когда небольшая сетка перемещается назад, вместо фиксированного размера окна это скользящее окно (Sliding Window).

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

Реализация выглядит следующим образом:

public class SlidingWindowRateLimiter extends MyRateLimiter {
    /**
     * 每分钟限制请求数
     */
    private final long permitsPerMinute;
    /**
     * 计数器, k-为当前窗口的开始时间值秒，value为当前窗口的计数
     */
    private final TreeMap<Long, Integer> counters;

    public SlidingWindowRateLimiter(long permitsPerMinute) {
        this.permitsPerMinute = permitsPerMinute;
        this.counters = new TreeMap<>();
    }

    @Override
    public synchronized boolean tryAcquire() {
        // 获取当前时间的所在的子窗口值； 10s一个窗口
        long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / 10 * 10;
        // 获取当前窗口的请求总量
        int currentWindowCount = getCurrentWindowCount(currentWindowTime);
        if (currentWindowCount >= permitsPerMinute) {
            return false;
        }
        // 计数器 + 1
        counters.merge(currentWindowTime, 1, Integer::sum);
        return true;
    }
    /**
     * 获取当前窗口中的所有请求数（并删除所有无效的子窗口计数器）
     *
     * @param currentWindowTime 当前子窗口时间
     * @return 当前窗口中的计数
     */
    private int getCurrentWindowCount(long currentWindowTime) {
        // 计算出窗口的开始位置时间
        long startTime = currentWindowTime - 50;
        int result = 0;

        // 遍历当前存储的计数器，删除无效的子窗口计数器，并累加当前窗口中的所有计数器之和
        Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Long, Integer> entry = iterator.next();
            if (entry.getKey() < startTime) {
                iterator.remove();
            } else {
                result += entry.getValue();
            }
        }
        return result;
    }
}

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

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

03 Алгоритм дырявого ведра

Как плавнее ограничить ток? Давайте посмотрим на алгоритм «Дырявое ведро». дырявое ведро переполнится, новые входящие запросы будут отброшены.Ограничениеа такжепластикНе хватает двух основных компетенций Algorithm.

Реализация выглядит следующим образом:

public class LeakyBucketRateLimiter extends MyRateLimiter {
    // 桶的容量
    private final int capacity;
    // 漏出速率
    private final int permitsPerSecond;
    // 剩余水量
    private long leftWater;
    // 上次注入时间
    private long timeStamp = System.currentTimeMillis();

    public LeakyBucketRateLimiter(int permitsPerSecond, int capacity) {
        this.capacity = capacity;
        this.permitsPerSecond = permitsPerSecond;
    }

    @Override
    public synchronized boolean tryAcquire() {
        //1. 计算剩余水量
        long now = System.currentTimeMillis();
        long timeGap = (now - timeStamp) / 1000;
        leftWater = Math.max(0, leftWater - timeGap * permitsPerSecond);
        timeStamp = now;
        
        // 如果未满，则放行；否则限流
        if (leftWater < capacity) {
            leftWater += 1;
            return true;
        }
        return false;
    }
}

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

Если вы хотите сливать трафик с постоянной скоростью, это обычно должно быть реализовано с очередью FIFO.Когда tryAcquire возвращает true, запрос будет помещен в очередь, а затем запрос будет взят из очереди с фиксированной частотой для обработки. Пример кода выглядит следующим образом:

@Test
public void testLeakyBucketRateLimiter() throws InterruptedException {
    ScheduledExecutorService scheduledExecutorService = Executors.newSingleThreadScheduledExecutor();
    ExecutorService singleThread = Executors.newSingleThreadExecutor();

    LeakyBucketRateLimiter rateLimiter = new LeakyBucketRateLimiter(20, 20);
    // 存储流量的队列
    Queue<Integer> queue = new LinkedList<>();
    // 模拟请求  不确定速率注水
    singleThread.execute(() -> {
        int count = 0;
        while (true) {
            count++;
            boolean flag = rateLimiter.tryAcquire();
            if (flag) {
                queue.offer(count);
                System.out.println(count + "--------流量被放行--------");
            } else {
                System.out.println(count + "流量被限制");
            }
            try {
                Thread.sleep((long) (Math.random() * 1000));
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    });
  
    // 模拟处理请求 固定速率漏水
    scheduledExecutorService.scheduleAtFixedRate(() -> {
        if (!queue.isEmpty()) {
            System.out.println(queue.poll() + "被处理");
        }
    }, 0, 100, TimeUnit.MILLISECONDS);

    // 保证主线程不会退出
    while (true) {
        Thread.sleep(10000);
    }
}

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

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

04 Ведро жетонов

Как разрешить пакетный трафик при ограничении скорости трафика? Узнайте об алгоритме ведра токенов! Алгоритм ведра токенов отправляет токены в ведро токенов с постоянной скоростью.Когда приходит запрос, пытаемся получить токен из ведра токенов.Только после получения токена можно выпустить токен, иначе он будет отклонен.

Ковш для токенов имеет следующие характеристики:

  1. Выдача токенов с постоянной скоростью, ограничитель скорости потока предполагал V / S, это означает, что токен оплаты для каждого 1 / V SEC

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

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

В алгоритме корзины токенов есть два параметра, на которые стоит обратить внимание, а именно: текущая скорость ограничения v/s и емкость корзины токенов b; скорость представляет собой текущую скорость ограничения текущего ограничителя в целом, а b — это аббревиатура. пакета, Указывает максимальный пакетный трафик, разрешенный текущим ограничителем.

Например, если b=10, при заполнении корзины токенов доступно 10 токенов, и одновременно через текущий ограничитель может проходить 10 запросов (Разрешить некоторую степень разрыва трафика), после того как эти 10 запросов потребляют токены мгновенно, последующий трафик может проходить только через текущий ограничитель со скоростью r.

Реализация выглядит следующим образом:

public class TokenBucketRateLimiter extends MyRateLimiter {
    /**
     * 令牌桶的容量「限流器允许的最大突发流量」
     */
    private final long capacity;
    /**
     * 令牌发放速率
     */
    private final long generatedPerSeconds;
    /**
     * 最后一个令牌发放的时间
     */
    long lastTokenTime = System.currentTimeMillis();
    /**
     * 当前令牌数量
     */
    private long currentTokens;

    public TokenBucketRateLimiter(long generatedPerSeconds, int capacity) {
        this.generatedPerSeconds = generatedPerSeconds;
        this.capacity = capacity;
    }

    /**
     * 尝试获取令牌
     *
     * @return true表示获取到令牌，放行；否则为限流
     */
    @Override
    public synchronized boolean tryAcquire() {
          /**
           * 计算令牌当前数量
           * 请求时间在最后令牌是产生时间相差大于等于额1s（为啥时1s？因为生成令牌的最小时间单位时s），则
           * 1. 重新计算令牌桶中的令牌数
           * 2. 将最后一个令牌发放时间重置为当前时间
           */
        long now = System.currentTimeMillis();
        if (now - lastTokenTime >= 1000) {
            long newPermits = (now - lastTokenTime) / 1000 * generatedPerSeconds;
            currentTokens = Math.min(currentTokens + newPermits, capacity);
            lastTokenTime = now;
        }
        if (currentTokens > 0) {
            currentTokens--;
            return true;
        }
        return false;
    }
}

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

из-заНеопределенность планирования потоков, в сценариях с высоким параллелизмом ошибка таймера очень велика, и сам таймер создаст поток планирования, который такжепроизводительность системыоказать влияние.

05 журнал слайдов

Скользящий лог — относительно «непопулярный», но очень простой в использовании алгоритм ограничения тока. Алгоритм ограничения скорости скользящего журнала должен записывать метку времени запроса, обычно используяотсортированный наборДля хранения мы можем отслеживать все запросы пользователей за определенный период времени в одной упорядоченной коллекции.

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

Реализация выглядит следующим образом:

public class SlidingLogRateLimiter extends MyRateLimiter {
    /**
     * 每分钟限制请求数
     */
    private static final long PERMITS_PER_MINUTE = 60;
    /**
     * 请求日志计数器, k-为请求的时间（秒），value当前时间的请求数量
     */
    private final TreeMap<Long, Integer> requestLogCountMap = new TreeMap<>();

    @Override
    public synchronized boolean tryAcquire() {
        // 最小时间粒度为s
        long currentTimestamp = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC);
        // 获取当前窗口的请求总数
        int currentWindowCount = getCurrentWindowCount(currentTimestamp);
        if (currentWindowCount >= PERMITS_PER_MINUTE) {
            return false;
        }
        // 请求成功，将当前请求日志加入到日志中
        requestLogCountMap.merge(currentTimestamp, 1, Integer::sum);
        return true;
    }

    /**
     * 统计当前时间窗口内的请求数
     *
     * @param currentTime 当前时间
     * @return -
     */
    private int getCurrentWindowCount(long currentTime) {
        // 计算出窗口的开始位置时间
        long startTime = currentTime - 59;
        // 遍历当前存储的计数器，删除无效的子窗口计数器，并累加当前窗口中的所有计数器之和
        return requestLogCountMap.entrySet()
                .stream()
                .filter(entry -> entry.getKey() >= startTime)
                .mapToInt(Map.Entry::getValue)
                .sum();
    }
}

Скользящие логи позволяют избежать всплесков трафика и добиться более точного ограничения тока;Более гибкий и способный поддерживать более сложные стратегии ограничения тока, такие как многоуровневое ограничение тока, не более 100 раз в минуту, не более 300 раз в час, не более 1000 раз в день, нам нужно только сохранить все журналы запросов за последние 24 часа для достижения.

Гибкость не бесплатна, недостатком является то, чтоЗанять место для хранения выше, чем другие алгоритмы ограничения тока.

06 Распределенное ограничение тока

Реализации вышеупомянутых алгоритмов ограничения тока подходят только для ограничения тока одной машины. Хотя цель ограничения тока может быть достигнута путем равномерного назначения квот ограничения тока для каждой машины, из-за таких проблем, как производительность машины, неравномерное распределение трафика и динамические изменения количества вычислений, эффект ограничения тока одной машины в распределенных сценарии всегда неудовлетворительны.

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

Конечно, также возможно ограничить ток от входа трафика верхнего уровня.Прокси-сервис Nginx предоставляет модуль ограничения тока, который также может обеспечить высокую производительность и точное ограничение тока.Нижний уровень - это дырявое ведро. алгоритм.

07 Резюме

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

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

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

  3. Хотите достичь цели ограничения потока, не отключая его и не делая поток более плавным? Рассмотрим алгоритм дырявого ведра! Следует отметить, что алгоритм дырявого ведра обычно настраивается с очередью FIFO для достижения эффекта разрешения текущего ограничения.

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

  4. Ограничение по току и мгновенный трафик на самом деле не противоречат друг другу, в большинстве сценариев вполне допустимы системы кратковременного всплеска трафика. Алгоритм ведра токенов — лучший выбор.Ведро токенов генерирует токены с фиксированной скоростью v и помещает их в ведро с фиксированной емкостью n.Когда приходит запрос, он пытается получить токен из ведра.

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

  5. Как добиться более гибкого многоуровневого ограничения тока? Узнайте об алгоритме ограничения тока скользящего бревна! Журнал здесь представляет собой отметку времени запроса, а гибкое ограничение тока достигается путем подсчета общего количества запросов за указанный период времени.

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

Неважно, черная это кошка или белая кошка, если она умеет ловить мышей, это хорошая кошка. Абсолютной разницы между алгоритмами ограничения тока нет, как выбрать подходящий алгоритм ограничения тока? Может пожелать начать со спектакля,Можно ли превышать порог,стоимость посадки,Плавность потока,Разрешить ли пакетный трафиктак же каксистемный ресурсОграничение размера рассматривается по-разному.

Конечно, на рынке есть и более зрелые современные лимитирующие инструменты и фреймворки. такие как гуглGuavaТекущий ограничивающий компонент, основанный на готовой к использованию реализации Token Bucket в Китае, и инфраструктура управления трафиком с открытым исходным кодом Alibaba для архитектуры распределенных услуг.SentinelБольше позволит вам положить его вниз, он основан на скользящем окне для достижения."Кодовый адрес этой статьи"

После просмотра ставьте лайки и формируйте привычку! На этом все, до встречи в следующий раз!

Категории