Go реализует различные ограничения тока

Go
Go реализует различные ограничения тока

предисловие

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

Ограничение

限流Цель состоит в том, чтобы защитить систему, ограничивая скорость запросов на одновременный доступ или ограничивая скорость запросов в пределах временного окна.После достижения ограничения скорости она может отказать в обслуживании, поставить в очередь или ждать и перейти на более раннюю версию. Защитите систему, ограничив скорость одновременных (или в течение определенного временного окна) запросов.По достижении лимита скорости она откажет в обслуживании (направит на страницу с ошибкой или сообщит, что ресурс больше не доступен), ждите в очереди (например, seckill, комментарий, размещение заказа), понижение рейтинга (возвращает итоговые данные или данные по умолчанию).

Как показано на рисунке:

自己魔改出来的漫画

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

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

X-RateLimit-Limit: 60         //每秒60次请求
X-RateLimit-Remaining: 22     //当前还剩下多少次
X-RateLimit-Reset: 1612184024 //限制重置时间

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

Вообще говоря, общие методы обработки для ограничения тока:

  • прилавок
  • раздвижное окно
  • дырявое ведро
  • ведро с жетонами

прилавок

Счетчик является одним из простейших алгоритмов ограничения тока, и его принцип таков:在一段时间间隔内，对请求进行计数，与阀值进行比较判断是否需要限流，一旦到了时间临界点，将计数器清零。

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

  1. В программе можно задать переменнуюcount, когда придет запрос, я посчитаю это число +1, записывая время запроса.
  2. Судите, когда придет следующий запросcountПревышает ли значение счетчика установленную частоту, и находятся ли текущее время запроса и время первого запроса в пределах1в течение нескольких минут.
  3. если в1В течение нескольких минут и с превышением установленной частоты это доказывает, что запросов слишком много, и последующие запросы будут отклонены.
  4. Если интервал между запросом и первым запросом больше, чем период счета, иcountЕсли значение все еще находится в пределах текущего предела, сбросьтеcount.

Код:

package main

import (
    "log"
    "sync"
    "time"
)

type Counter struct {
    rate  int           //计数周期内最多允许的请求数
    begin time.Time     //计数开始时间
    cycle time.Duration //计数周期
    count int           //计数周期内累计收到的请求数
    lock  sync.Mutex
}

func (l *Counter) Allow() bool {
    l.lock.Lock()
    defer l.lock.Unlock()

    if l.count == l.rate-1 {
        now := time.Now()
        if now.Sub(l.begin) >= l.cycle {
            //速度允许范围内， 重置计数器
            l.Reset(now)
            return true
        } else {
            return false
        }
    } else {
        //没有达到速率限制，计数加1
        l.count++
        return true
    }
}

func (l *Counter) Set(r int, cycle time.Duration) {
    l.rate = r
    l.begin = time.Now()
    l.cycle = cycle
    l.count = 0
}

func (l *Counter) Reset(t time.Time) {
    l.begin = t
    l.count = 0
}

func main() {
    var wg sync.WaitGroup
    var lr Counter
    lr.Set(3, time.Second) // 1s内最多请求3次
    for i := 0; i < 10; i++ {
        wg.Add(1)
        log.Println("创建请求:", i)
        go func(i int) {
          if lr.Allow() {
              log.Println("响应请求:", i)
          }
          wg.Done()
        }(i)

        time.Sleep(200 * time.Millisecond)
    }
    wg.Wait()
}

OutPut:

2021/02/01 21:16:12 创建请求: 0
2021/02/01 21:16:12 响应请求: 0
2021/02/01 21:16:12 创建请求: 1
2021/02/01 21:16:12 响应请求: 1
2021/02/01 21:16:12 创建请求: 2
2021/02/01 21:16:13 创建请求: 3
2021/02/01 21:16:13 创建请求: 4
2021/02/01 21:16:13 创建请求: 5
2021/02/01 21:16:13 响应请求: 5
2021/02/01 21:16:13 创建请求: 6
2021/02/01 21:16:13 响应请求: 6
2021/02/01 21:16:13 创建请求: 7
2021/02/01 21:16:13 响应请求: 7
2021/02/01 21:16:14 创建请求: 8
2021/02/01 21:16:14 创建请求: 9

Вы можете видеть, что мы установили каждый200msСоздайте запрос, значительно выше1секунд макс3Лимит каждого запроса, после запуска выясняется, что число равно2、3、4、8、9Запрос отбрасывается, указывая на то, что текущий лимит выполнен успешно.

Затем возникает проблема, если есть требование к интерфейсу/queryРазрешено максимум 200 посещений в минуту, при условии, что пользователь отправляет 200 запросов в последние несколько миллисекунд 59-й секунды, когда 59-я секунда закончилась.CounterОчищенный, он отправляет еще 200 запросов в следующую секунду. Тогда этот пользователь отправляет в 2 раза больше запросов за 1 секунду, что соответствует нашей логике проектирования.Это также является конструктивным недостатком метода счетчика.Система может выдержать большое количество запросов от злоумышленников или даже сломать систему. система.

Как показано ниже:

计数图解

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

раздвижное окно

滑动窗口Это критическая точка дефекта существования счетчика, т.н.滑动窗口（Sliding window）является методом управления потоком, этот термин появляется вTCPв соглашении.滑动窗口Разделите фиксированный временной интервал и перемещайтесь по прошествии времени, подсчитайте фиксированное количество подвижных сеток и определите пороговое значение.

Как показано на рисунке:

图解1

На приведенном выше рисунке мы используем красную пунктирную линию для обозначения временного окна (一分钟), каждый раз, когда окно имеет6сетки, каждая сетка10секунды. каждый раз10Второе временное окно перемещается на одну позицию вправо, и вы можете видеть направление красной стрелки. На каждую сетку настраиваем отдельный счетчикCounter, если запрос0:45Побывали тогда поставим счетчик пятой сетки+1(это0:40~0:50), при оценке ограничения по току необходимо сложить отсчеты всех сеток и сравнить их с заданной частотой.

Так как же скользящее окно решает проблему, с которой мы столкнулись выше? Взгляните на картинку ниже:

图解2

когда пользователь0:59отправлено за секунды200 запросы будут фиксироваться счетчиком в шестой сетке+200, временное окно перемещается на одну секунду вправо в следующую секунду, а счетчик уже зафиксировал данные, отправленные пользователем.200Запрос, поэтому, если он будет отправлен снова, будет активирован текущий лимит, а новый запрос будет отклонен.

По сути, счетчик представляет собой скользящее окно, но сетка всего одна, поэтому для более точного ограничения тока нам нужно всего лишь разделить большее количество сеток, а для большей точности мы не знаем, сколько сеток нужно разделить. задавать.格子的数量影响着滑动窗口算法的精度，依然有时间片的概念，无法根本解决临界点问题.

Сливная бочка

漏桶算法（Leaky Bucket）, принцип - негерметичное ведро с фиксированной емкостью, и капли воды вытекают с фиксированной скоростью. Любой, кто пользовался краном, знает, что когда кран включается и выключается, вода будет стекать вниз и капать в ведро, а негерметичное ведро — это отверстие под ведром, через которое вода вытекает. Если кран открыт слишком сильно, расход воды будет слишком большим, что может привести к переполнению ведра.

Как показано на рисунке:

漏 桶

Ведро фиксированной вместимости, в которое поступает вода и вытекает вода. Для поступающей воды мы не можем предсказать, сколько воды будет поступать, и мы не можем предсказать, как быстро вода будет течь. А вот для уходящей воды это ведро может зафиксировать скорость, с которой уходит вода(处理速度), чтобы добиться流量整形а также流量控制Эффект.

Код:

type LeakyBucket struct {
    rate       float64 //固定每秒出水速率
    capacity   float64 //桶的容量
    water      float64 //桶中当前水量
    lastLeakMs int64   //桶上次漏水时间戳 ms

    lock sync.Mutex
}

func (l *LeakyBucket) Allow() bool {
    l.lock.Lock()
    defer l.lock.Unlock()

    now := time.Now().UnixNano() / 1e6
    eclipse := float64((now - l.lastLeakMs)) * l.rate / 1000 //先执行漏水
    l.water = l.water - eclipse                              //计算剩余水量
    l.water = math.Max(0, l.water)                           //桶干了
    l.lastLeakMs = now
    if (l.water + 1) < l.capacity {
        // 尝试加水,并且水还未满
        l.water++
        return true
    } else {
        // 水满，拒绝加水
        return false
    }
}

func (l *LeakyBucket) Set(r, c float64) {
    l.rate = r
    l.capacity = c
    l.water = 0
    l.lastLeakMs = time.Now().UnixNano() / 1e6
}

Алгоритм дырявого ведра имеет следующие характеристики:

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

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

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

Алгоритм ведра токенов（Token Bucket）формирование сетевого трафика（Traffic Shaping）и ограничение скорости（Rate Limiting）один из самых популярных алгоритмов. Как правило, алгоритм корзины маркеров используется для управления объемом данных, отправляемых в сеть, и для разрешения отправки пакетов данных.

令牌桶算法

У нас есть фиксированное ведро, в котором хранятся токены（token）. Ведро вначале пустое, система нажимает фиксированное время（rate）Добавляйте токены в ведро до тех пор, пока количество токенов в ведре не будет заполнено, а избыточные запросы будут отброшены. Когда приходит запрос, удалить токен из корзины, отклонить запрос или заблокировать, если корзина пуста.

Код реализации:

type TokenBucket struct {
    rate         int64 //固定的token放入速率, r/s
    capacity     int64 //桶的容量
    tokens       int64 //桶中当前token数量
    lastTokenSec int64 //桶上次放token的时间戳 s

    lock sync.Mutex
}

func (l *TokenBucket) Allow() bool {
    l.lock.Lock()
    defer l.lock.Unlock()

    now := time.Now().Unix()
    l.tokens = l.tokens + (now-l.lastTokenSec)*l.rate // 先添加令牌
    if l.tokens > l.capacity {
        l.tokens = l.capacity
    }
    l.lastTokenSec = now
    if l.tokens > 0 {
        // 还有令牌，领取令牌
        l.tokens--
        return true
    } else {
        // 没有令牌,则拒绝
        return false
    }
}

func (l *TokenBucket) Set(r, c int64) {
    l.rate = r
    l.capacity = c
    l.tokens = 0
    l.lastTokenSec = time.Now().Unix()
}

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

  • Токены помещаются в корзину токенов по фиксированной ставке.
  • Максимальное хранение в ведрахBтокены, когда ведро заполнено, вновь добавленные токены отбрасываются или отклоняются
  • Если в ведре недостаточно токеновN, токен не будет удален, а запрос будет отрегулирован (отброшен или заблокирован в ожидании)

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

Резюме

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

Категории