Первое предложение основной части статьи: Эта статья участвовала в учебном плане выходного дня,Нажмите на ссылку, чтобы просмотреть подробности

введение

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

Алгоритм фиксированного временного окна

Алгоритм фиксированного временного окна также можно назвать простым алгоритмом подсчета. Есть много онлайн, которые выделяют алгоритм подсчета. Но автор считает, что алгоритм подсчета — это идея, а алгоритм фиксированного временного окна — одна из его реализаций.
Включение следующего алгоритма скользящего временного окна также является реализацией алгоритма подсчета. Потому что если счет не привязан ко времени, то теряется суть ограничения тока. превратилось в отказ

преимущество

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

недостаток

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

выполнить

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

controller

	@RequestMapping(value = "/start",method = RequestMethod.GET)
    public Map<String,Object> start(@RequestParam Map<String, Object> paramMap) {
        return testService.startQps(paramMap);
    }

service

@Override
public Map<String, Object> startQps(Map<String, Object> paramMap) {
    //根据前端传递的qps上线
    Integer times = 100;
    if (paramMap.containsKey("times")) {
        times = Integer.valueOf(paramMap.get("times").toString());
    }
    String redisKey = "redisQps";
    RedisAtomicInteger redisAtomicInteger = new RedisAtomicInteger(redisKey, redisTemplate.getConnectionFactory());
    int no = redisAtomicInteger.getAndIncrement();
    //设置时间固定时间窗口长度 1S
    if (no == 0) {
        redisAtomicInteger.expire(1, TimeUnit.SECONDS);
    }
    //判断是否超限  time=2 表示qps=3
    if (no > times) {
        throw new RuntimeException("qps refuse request");
    }
    //返回成功告知
    Map<String, Object> map = new HashMap<>();
    map.put("success", "success");
    return map;
}

результат теста

Ставим qps=3, видим, что первые три доступа нормально после пяти одновременных входящих, а последние два терпят неудачу. Через некоторое время мы получаем доступ одновременно, и к первым трем можно получить доступ в обычном режиме. Указывает следующее временное окно

Алгоритм скользящего временного окна

Из-за недостатка фиксированного временного окна - проблема двойного потока критического значения. Наше скользящее временное окно сгенерировано.
На самом деле это легко понять, то есть для фиксированного временного окна статистика временного окна меняется с исходного фиксированного интервала на более точную единицу.
В нашей демонстрации с фиксированным временным окном выше мы установили единицу времени 1S. Для 1S мы разбили 1S на метки времени.
Фиксированное временное окно — это статистическая единица, которая продолжает двигаться назад во времени. Скользящее временное окно — это то, что мы представляем себе как единицу времени, которая фиксирует время в соответствии с идеей относительности, а наша абстрактная единица времени движется сама по себе. Абстрактная единица времени меньше фактической единицы времени.
Читатели могут взглянуть на анимацию ниже, чтобы понять.

преимущество

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

недостаток

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

выполнить

Скользящее временное окно предназначено для уточнения времени, которого мы достигли выше с помощью redis#setnx. Здесь мы не можем записать через него равномерно. Мы должны добавить меньшие единицы времени в сводку коллекции. Текущий лимит затем рассчитывается на основе общей суммы сбора. Структура данных zsett в Redis соответствует нашим потребностям.
Зачем выбирать zset, потому что zset redis имеет вес в дополнение к значению. будут отсортированы по этому весу. Если мы используем нашу единицу времени и отметку времени в качестве нашего веса, нам нужно только следовать диапазону отметок времени, когда мы получаем статистику.
Поскольку элементы в наборе zset уникальны, наше значение использует генератор идентификаторов, такой как uuid или алгоритм снежинки.

controller

	@RequestMapping(value = "/startList",method = RequestMethod.GET)
    public Map<String,Object> startList(@RequestParam Map<String, Object> paramMap) {
        return testService.startList(paramMap);
    }

service

		String redisKey = "qpsZset";
        Integer times = 100;
        if (paramMap.containsKey("times")) {
            times = Integer.valueOf(paramMap.get("times").toString());
        }
        long currentTimeMillis = System.currentTimeMillis();
        long interMills = inter * 1000L;
        Long count = redisTemplate.opsForZSet().count(redisKey, currentTimeMillis - interMills, currentTimeMillis);
        if (count > times) {
            throw new RuntimeException("qps refuse request");
        }
        redisTemplate.opsForZSet().add(redisKey, UUID.randomUUID().toString(), currentTimeMillis);
        Map<String, Object> map = new HashMap<>();
        map.put("success", "success");
        return map;

результат теста

Тот же параллелизм, что и в окнах с фиксированным временем. Почему критическая ситуация выше? Потому что интервал единицы времени в коде больше, чем фиксированный интервал времени. Приведенная выше демонстрационная единица времени с фиксированным временным окном является наихудшим случаем 1S. Скользящее временное окно должно быть разработано с более короткими интервалами. И я установил его на 10S, и нет плохой ситуации
Здесь объясняются преимущества фиксированного коэффициента скольжения. Если скорректировать поменьше, критических проблем быть не должно, но в итоге критических проблем ему все равно не избежать.

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

Хотя скользящее временное окно может в значительной степени избежать проблемы критического значения, оно все же неизбежно.
Кроме того, у временного алгоритма есть фатальная проблема: он не может столкнуться с внезапным большим объемом трафика, потому что сразу отбрасывает другой дополнительный трафик после достижения лимита.
Для этой задачи мы продолжаем оптимизировать наш текущий алгоритм ограничения. Появился алгоритм дырявого ведра

преимущество

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

недостаток

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

выполнить

controller

@RequestMapping(value = "/startLoutong",method = RequestMethod.GET)
public Map<String,Object> startLoutong(@RequestParam Map<String, Object> paramMap) {
    return testService.startLoutong(paramMap);
}

service

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

@Override
public Map<String, Object> startLoutong(Map<String, Object> paramMap) {
    String redisKey = "qpsList";
    Integer times = 100;
    if (paramMap.containsKey("times")) {
        times = Integer.valueOf(paramMap.get("times").toString());
    }
    Long size = redisTemplate.opsForList().size(redisKey);
    if (size >= times) {
        throw new RuntimeException("qps refuse request");
    }
    Long aLong = redisTemplate.opsForList().rightPush(redisKey, paramMap);
    if (aLong > times) {
        //为了防止并发场景。这里添加完成之后也要验证。  即使这样本段代码在高并发也有问题。此处演示作用
        redisTemplate.opsForList().trim(redisKey, 0, times-1);
        throw new RuntimeException("qps refuse request");
    }
    Map<String, Object> map = new HashMap<>();
    map.put("success", "success");
    return map;
}

последующее потребление

@Component
public class SchedulerTask {

    @Autowired
    RedisTemplate redisTemplate;

    private String redisKey="qpsList";

    @Scheduled(cron="*/1 * * * * ?")
    private void process(){
        //一次性消费两个
        System.out.println("正在消费。。。。。。");
        redisTemplate.opsForList().trim(redisKey, 2, -1);
    }

}

контрольная работа

Мы по-прежнему прокручиваем 50 одновременно для 10 посещений. Мы можем обнаружить, что относительно высокая пропускная способность может быть достигнута только в начале. После того, как вместимость следующей бочки заполнена. В случае, когда скорость дроплетов в нисходящем направлении ниже, чем скорость запросов в восходящем направлении. Доступ может быть получен только с постоянной скоростью в нисходящем направлении.
Его проблемы также были раскрыты. Недостаточное количество «дырявых ведер» для временных окон — это недостатки, но все же недостатки. Полностью избежать проблемы переполнения запросов невозможно.
Переполнение запроса само по себе является катастрофической проблемой. Ни один из алгоритмов в настоящее время не решает эту проблему. просто замедляя проблемы, которые он вызывает

Алгоритм ведра токенов

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


public Map<String, Object> startLingpaitong(Map<String, Object> paramMap) {
        String redisKey = "lingpaitong";
        String token = redisTemplate.opsForList().leftPop(redisKey).toString();
        //正常情况需要验证是否合法，防止篡改
        if (StringUtils.isEmpty(token)) {
            throw new RuntimeException("令牌桶拒绝");
        }
        Map<String, Object> map = new HashMap<>();
        map.put("success", "success");
        return map;
    }


@Scheduled(cron="*/1 * * * * ?")
    private void process(){
        //一次性生产两个
        System.out.println("正在消费。。。。。。");
        for (int i = 0; i < 2; i++) {
            redisTemplate.opsForList().rightPush(redisKey, i);
        }
    }