Стратегия наилучшей практики, ограничивающая текущий интерфейс Redis + Lua

Автор оригинала: David Wong.

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

Существует два популярных алгоритма ограничения тока: алгоритм дырявого ковша и алгоритм токенового ковша.

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

Реализация алгоритма дырявого ведра относительно проста. Вода (запрос) сначала поступает в ведро, а затем ведро вытекает с определенной скоростью (интерфейс имеет скорость отклика). Когда вода проходит через большое количество (частота доступа превышает установленный порог), системная служба отклонит запрос. Принудительно ограничьте количество запросов, к которым система обращается в единицу времени. Принципиальная схема алгоритма дырявого ведра выглядит следующим образом: В алгоритме дырявого ведра есть две ключевые переменные: размер ведра и скорость оттока воды, которые вместе определяют максимальное количество запросов, которые система может получить за единицу времени. Потому что размер ковша и скорость оттока являются фиксированными параметрами в алгоритме дырявого ковша. Не может заставить поток ворваться в порт, недостаточная эффективность для потока с характеристиками разрыва, что вы имеете в виду? Позже мы будем использовать PHP для реализации демо-версии с дырявым ведром и подробно объясним результаты тестирования. Исходный адрес GitHub: демонстрация алгоритма drop bucket

2.2 алгоритм сбора токенов

Ведро токенов и дырявое ведро используют противоположный алгоритм, который легче понять. С течением времени система добавит токен в корзину в соответствии с константой 1/QPS (если интервал времени составляет 1 мс). (представьте, что есть кран, непрерывно добавляющий воду, в отличие от утечки воды). Если ведро заполнено, оно не будет добавлено. Когда поступит запрос, он попытается получить токен из корзины. Если он не сможет получить токен, он заблокирует или откажет в обслуживании. Он получит токен в следующий раз, когда появится токен. Алгоритм корзины токенов показан на следующем рисунке: Преимущество корзины токенов очевидно. Мы можем изменить скорость ограничения запроса, увеличив скорость размещения токенов в корзине. Корзина токенов обычно регулярно добавляет токен в корзину (например, каждые 10 мс). Мы будем использовать язык go для реализации демо-версии корзины токенов. Для достижения совместимости с распределенными параллельными сценариями мы улучшим демонстрационную версию корзины токенов. При добавлении токенов мы используем альтернативный алгоритм: когда поступит запрос, мы рассчитаем количество токенов, которые должны быть помещены в корзину в режиме реального времени, в соответствии со скоростью ввода токена в корзину. Исходный адрес GitHub: демонстрация алгоритма сбора токенов

2.3 описание примера

Функция нашей реализации моделирования заключается в ограничении частоты доступа к интерфейсу в компании. В примере интерфейс списка сотрудников/пользователь/список организации 1 в компании может быть доступен 100 раз извне в течение 1 секунды.

3.1 PHP реализация алгоритма дырявого ведра

В redis установите ограничение интерфейса для доступа к 100 раз хэшу в течение 1 секунды:

 hmset org1/user/list expire 1 limitReq 100

Мы используем predis для подключения redis для работы. Интерфейс моделирования относительно прост. Мы получаем только два параметра: org и pathinfo. Связанными методами в классе ratelimit являются:

php
/**
 *Description: leakage barrel current limiting
 * User: guozhaoran<[email protected]>
 * Date: 2019-06-13
 */

class RateLimit
{
    Private $conn = null; // redis connection
    Private $org = '; // company ID
    Private $pathinfo = '; // interface path information

    /**
     * RateLimit constructor.
     * @param $org
     * @param $pathInfo
     * @param $expire
     * @param $limitReq
     */
    public function __construct($org, $pathInfo)
    {
        $this->conn = $this->getRedisConn();
        $this->org = $org;
        $this->pathInfo = $pathInfo;
    }
    //... the getluascript method is omitted here
    /**
     *Get redis connection
     * @return \Predis\Client
     */
    private function getRedisConn()
    {
        require_once('vendor/autoload.php');
        $conn = new Predis\Client(['host' => '127.0.0.1',
            'port' => 6379,]);
        return $conn;
    }
    //... the isactionallowed method is omitted here
}

Далее давайте рассмотрим дизайн сценария lua:

/**
     *Get Lua script
     * @return string
     */
    private function getLuaScript()
    {
        $luaScript = << tonumber(ARGV[2]) then
return 0
end

return 1
LUA_SCRIPT;

        return $luaScript;
    }

Сценарий Lua может быть упакован на сервер redis для выполнения, поскольку сервер redis на сервере redis по умолчанию имеет встроенный анализатор Lua версии 2.6. Взаимодействие между клиентом redis PHP и сценарием Lua в основном передает два ключа и argv, где ключи-это значение ключа, соответствующее операции в redis (в примере ключи [1] – это org1/пользователь/список), а argv-параметр атрибута, который необходимо задать. В скрипте Lua индекс таблицы автоматически увеличивается с 1. Выполнение команды redis в сценарии Lua может обеспечить атомарность (поскольку redis является однопоточным), поэтому он также может обеспечить согласованность чтения и записи хэша в состоянии параллельной гонки. Команда сначала вызывает incr, чтобы задать количество организаций/пользователей/списков. Структуры данных списка, набора, хэша и набора в redis являются структурами данных контейнеров. Они разделяют следующие два общих правила:

• 1. Создать, если не существует: если контейнер не существует, создайте его и выполните операцию снова. Например, в incr org/user/list, если организация/пользователь/список не существует, это эквивалентно установке для организации/пользователя/списка значения 1, поэтому приведенный выше сценарий Lua использует expire для установки времени истечения срока действия Организации/пользователя/списка, когда время равно 1
• 2. Удалить, если элементов нет: если в контейнере нет элементов, немедленно удалите контейнер и освободите память. Например, после того, как lpop оперирует списком, если в списке нет содержимого элемента, то списка не существует

Логика, приведенная ниже, очень ясна, то есть, чтобы увидеть, превышает ли совокупное количество вызовов интерфейса предельное значение (предельная частота определяется по argv [2]). Если он превышает лимит, верните 0, в противном случае верните 1

Далее мы можем увидеть, как метод isactionallowed определяет, следует ли ограничивать текущий:

/**
     *Judge whether the interface restricts access
     * @return bool
     */
    public function isActionAllowed()
    {
        $pathInfo = $this->org . $this->pathInfo;
        $config = $this->conn->hgetall($pathInfo);
        //There are no restrictions on interfaces in the configuration
        if (!$config) return true;

        $pathInfoLimitKey = $this->org . '-' . $this->pathInfo;
        try {
            $ret = $this->conn->evalsha(sha1($this->getLuaScript()), 1, $pathInfoLimitKey, $config['expire'], $config['limitReq']);
        } catch (Exception $e) {
            $ret = $this->conn->eval($this->getLuaScript(), 1, $pathInfoLimitKey, $config['expire'], $config['limitReq']);
        }

        return boolval($ret);
    }

Predis использует evalsha для упаковки сценария Lua и отправки его на сервер для выполнения. Первым параметром evalsha является сценарий Lua после кодирования SHA1. Сервер Redis может кэшировать сценарий Lua в виде ключа: значение, где ключ-это содержимое сценария lua после SHA1, поэтому, когда сценарий Lua относительно велик, клиентам нужно только отправить значение после SHA1 на сервер redis, уменьшая размер каждой команды в байтах. Если evalsha сообщает об ошибке, ее можно изменить на функцию eval, поскольку при первом получении сервером redis сценария Lua он, возможно, не был кэширован. Лучше использовать try… Поймать… Для совместимости. Вторым параметром evalsha является количество ключей. Вот один из них, $pathinfolimitkey. Следующие два-это значения конфигурации, взятые из redis, указывающие, что $pathinfolimitkey разрешено использовать 100 раз за 1 секунду. Если частота $pathinfolimitkey не настроена, по умолчанию она не ограничена.

Выше приведено все содержание класса ratelimit. Идея проста. Давайте взглянем на файл с записью. Это тоже просто. Он должен получать параметры, а затем записывать информацию о том, ограничен ли интерфейс статистикой.файл журнала журнала.

[email protected]>
 * Date: 2019-06-16
 */
require_once('./RateLimit.php');
ini_set('display_errors', true);

$org = $_GET['org'];
$pathInfo = $_GET['path_info'];

$result = (new RateLimit($org, $pathInfo))->isActionAllowed();

$handler = fopen('./stat.log', 'a') or die('can not open file!');
if ($result) {
    fwrite($handler, 'request success!' . PHP_EOL);
} else {
    fwrite($handler, 'request failed!' . PHP_EOL);
}
fclose($handler);

Мы используем инструмент AB для проверки информации об интерфейсе. Ограничение программы позволяет выполнять 100 обращений за 1 секунду. Мы открываем 10 клиентов и запрашиваем 110 раз одновременно. Теоретически, первые 100 раз являются успешными, а последние десять раз-неудачными. Команда такова:

ab -n 110 -c 10 http://localhost/demo/rateLimit/index.php\?org\=org1\&path_info\=/user/list

Информация журнала в stat.log такая же, как мы ожидали, что указывает на то, что настройка частоты нашего интерфейса достигла ожидаемого эффекта:

... // 96 lines are omitted here
request success!
request success!
request success!
request success!
request failed!
request failed!
request failed!
request failed!
request failed!
request failed!
request failed!
request failed!
request failed!
request failed!

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

3.2 перейдите к реализации алгоритма корзины токенов

Прежде всего, мы не учитываем условия гонки и используем язык go для реализации версии V1 корзины токенов, чтобы испытать ее алгоритм. Мы создаем новый модуль туннеля и определяем структуру, которая содержит необходимые атрибуты корзины токенов:

package funnel

import (
    "math"
    "time"
)

type Funnel struct {
    Capacity Int64 // token bucket capacity
    Leakingrate float64 // token bucket pipeline rate: number of tokens added to token bucket per millisecond
    Remainingcapacity Int64 // token bucket space remaining
    Lastleakingtime Int64 // last pipeline (put token) time: millisecond timestamp

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

//Update the status of token bucket when there is a request, mainly including the remaining space of token bucket and the time stamp of taking token
func (rateLimit *Funnel) updateFunnelStatus() {
    nowTs := time.Now().UnixNano() / int64(time.Millisecond)
    //How long has it been since the token was last taken
    timeDiff := nowTs - rateLimit.LastLeakingTime
    //Calculate how many tokens need to be added to token bucket according to time difference and pipeline rate
    needAddSpace := int64(math.Floor(rateLimit.LeakingRate * float64(timeDiff)))
    //No token needs to be added
    if needAddSpace < 1 {
        return
    }
    rateLimit.RemainingCapacity += needAddSpace
    //The added token cannot be larger than the remaining space of token bucket
    if rateLimit.RemainingCapacity > rateLimit.Capacity {
        rateLimit.RemainingCapacity = rateLimit.Capacity
    }
    //Update last token bucket pipeline (add token) timestamp
    rateLimit.LastLeakingTime = nowTs
}

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

//Judge whether the interface is restricted
func (rateLimit *Funnel) IsActionAllowed() bool {
    //Update token bucket status
    rateLimit.updateFunnelStatus()
    if rateLimit.RemainingCapacity < 1 {
        return false
    }
    rateLimit.RemainingCapacity = rateLimit.RemainingCapacity - 1
    return true
}

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

hmset org2/user/list Capacity 100 LeakingRate 0.1 RemainingCapacity 0 LastLeakingTime 1560789716896

Мы устанавливаем емкость корзины токенов интерфейса (/пользователя/списка) компании II (org 2) на 100 и помещаем токен каждые 10 мс (метод расчета 100/1000). Мы храним поля содержимого объекта воронки в хэш-структуре. Когда мы вычисляем, следует ли ограничивать ток, нам нужно взять значения из хэш-структуры, выполнить операции в памяти, а затем выполнить обратное заполнение в хэш-структуру. Особенно для естественных и параллельных программ, таких как язык go, мы не можем гарантировать атомизацию всего процесса (вот почему мы используем сценарий Lua, потому что, если мы используем, если программа реализована, она должна быть заблокирована. Как только он будет заблокирован, он может выйти из строя. Если это не удастся, вы можете только повторить попытку или отказаться. Повторная попытка приведет к снижению производительности, отказ повлияет на пользовательский интерфейс, а сложность кода значительно возрастет. Мы все равно выберем сценарий Lua для версии 2: конкретный процесс исследования выглядит следующим образом:

Добавьте одну вещь: red is 4.0 предоставляет модуль ограничения тока, ячейку redis. Модуль также использует алгоритм воронки и предоставляет команду ограничения атомарного тока. Механизм повторных попыток очень прост, и вы можете изучить его, если вам интересно. Мы все еще используем решение Lua + redis здесь, с меньшим количеством глупостей. Код версии V2 выглядит следующим образом:

const luaScript = `
--Interface current limiting
--Last? Leaving? Time milliseconds of last access time
--Retaining_capacity the number of available request tokens in the current token bucket
--Capacity token bucket capacity
--Rate at which token bucket is being added

--Persistent and master-slave replication of data change commands in a transactional manner (supported by redis4.0)
redis.replicate_commands()

--Get configuration information of token bucket
local rate_limit_info = redis.call("HGETALL", KEYS[1])

--Get current timestamp
local timestamp = redis.call("TIME")
local now = math.floor((timestamp[1] * 1000000 + timestamp[2]) / 1000)

If rate ﹣ limit ﹣ info = = nil then -- if the current limit configuration is not set, the token will be obtained by default
    return now * 10 + 1
end

local capacity = tonumber(rate_limit_info[2])
local leaking_rate = tonumber(rate_limit_info[4])
local remaining_capacity = tonumber(rate_limit_info[6])
local last_leaking_time = tonumber(rate_limit_info[8])

--Calculate the number of tokens to be replenished, update the number of tokens and replenishment timestamp
local supply_token = math.floor((now - last_leaking_time) * leaking_rate)
if (supply_token > 0) then
   last_leaking_time = now
   remaining_capacity = supply_token + remaining_capacity
   if remaining_capacity > capacity then
      remaining_capacity = capacity
   end
end

Local result = 0 -- whether the returned result can get the token, no by default

--Calculate whether the request can get the token
if (remaining_capacity > 0) then
    remaining_capacity = remaining_capacity - 1
    result = 1
end

--Update token bucket configuration information
redis.call("HMSET", KEYS[1], "RemainingCapacity", remaining_capacity, "LastLeakingTime", last_leaking_time)

return now * 10 + result
`

Наш скрипт возвращает целое число типа Int64. Последний бит 0 или 1 указывает, следует ли ограничивать ток интерфейса. Цифра впереди указывает на отметку времени в миллисекунду. В будущем это будет занесено в журнал для статистики измерения давления. Когда программа запущена, я получаю текущую метку времени, вызывая команду redis time. Есть две причины:

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

Как и прежде, вы можете запросить по умолчанию, не устанавливая конфигурацию регулирования. Затем в соответствии с меткой времени для предоставления токена вычислите, можно ли получить токен, а затем обновите статус токена. Идея та же, что и в версии V1, и читатель может прочитать ее сам. Чтобы было ясно, команда повторяется. Репликация команд() в начале сценария связана с тем, что более низкая версия redis не поддерживает как чтение, так и запись в redis, поэтому таким образом обеспечивается совместимость версий, но решение является наиболее совершенным. Далее давайте рассмотрим код логики go:

func main() {
    http.HandleFunc("/user/list", handleReq)
    http.ListenAndServe(":8082", nil)
}

//Initialize redis connection pool
func newPool() *redis.Pool {
    return &redis.Pool{
        MaxIdle:   80,
        MaxActive: 12000, // max number of connections
        Dial: func() (redis.Conn, error) {
            c, err := redis.Dial("tcp", ":6379")
            if err != nil {
                panic(err.Error())
            }
            return c, err
        },
    }
}

//Write log
func writeLog(msg string, logPath string) {
    fd, _ := os.OpenFile(logPath, os.O_RDWR|os.O_CREATE|os.O_APPEND, 0644)
    defer fd.Close()
    content := strings.Join([]string{msg, "\r\n"}, "")
    buf := []byte(content)
    fd.Write(buf)
}

//Process the request function and write the response result information to the log according to the request
func handleReq(w http.ResponseWriter, r *http.Request) {
    //Get URL information
    pathInfo := r.URL.Path
    //Get the company information delivered by get ORG
    orgInfo, ok := r.URL.Query()["org"]
    if !ok || len(orgInfo) < 1 {
        fmt.Println("Param org is missing!")
    }

    //Calling Lua script atomicity for interface current limiting statistics
    conn := newPool().Get()
    key := orgInfo[0] + pathInfo
    lua := redis.NewScript(1, luaScript)
    reply, err := redis.Int64(lua.Do(conn, key))
    if err != nil {
        fmt.Println(err)
        return
    }
    //Is the interface restricted
    isLimit := bool(reply % 10 == 1)
    reqTime := int64(math.Floor(float64(reply) / 10))
    //Write the statistics to the log
    if !isLimit {
        successLog := strconv.FormatInt(reqTime, 10) + " request failed!"
        writeLog(successLog, "./stat.log")
        return
    }

    failedLog := strconv.FormatInt(reqTime, 10) + " request success!"
    writeLog(failedLog, "./stat.log")
}

Сценарий прослушивает локальный порт 8082 и использует правительственную структуру redis для работы с redis. Мы инициализируем пул соединений redis для получения соединений из пула соединений для работы. Мы анализируем следующий код:

lua := redis.NewScript(1, luaScript)
    reply, err := redis.Int64(lua.Do(conn, key))

Первый параметр в newscript представляет количество ключей для работы с красноватым цветом, что аналогично второму параметру evalsha в predis. Затем для выполнения сценария используется метод do, возвращаемое значение обрабатывается redis.int64, а затем выполняется операция для определения того, разрешен ли доступ к интерфейсу, а затем время доступа и результат записываются в статистику.файл журнала журнала. Логика очень проста. Мы в основном смотрим на результаты испытаний под давлением, запускаем код и используем ПРИВЕДЕННУЮ ВЫШЕ команду испытания под давлением для выполнения:

 ab -n 110 -c 10 http://127.0.0.1:8082/user/list\?org\=org2

Тогда мы можем быть удивлены, проанализировав статистику.журнал журнал журнал:

1561263349294 request success! // log line 1
... // omit 95 lines
1561263349387 request success!
1561263349388 request success!
1561263349398 request success!
1561263349396 request success!
1561263349404 request success!
1561263349407 request success!
1561263349406 request success!
1561263349406 request success!
1561263349407 request success!
1561263349406 request success!
1561263349406 request success!
1561263349405 request success!
1561263349406 request success!
1561263349406 request success!
1561263349406 request success!

Да, все прошло успешно. Почему? Из статистики мы видим, что для выполнения этих 100 запросов потребовалось 110 миллисекунд. В процессе выполнения программы токен добавляется в корзину токенов каждые 10 мс, всего добавляется 11 токенов, таким образом, 110 запросов получили токены. Можно видеть, что ведро токенов подходит для ограничения потока при большом потоке, что может обеспечить равномерное распределение потока в соответствии со временем и избежать централизованного пакетного доступа к потоку.

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