Автор оригинала: David Wong.
Многие из разработанных нами систем интерфейсного обслуживания обладают характеристиками, позволяющими противостоять высокому параллелизму и обеспечивать высокую доступность. В действительности, с постоянным увеличением трафика, в условиях ограниченных средств, аппаратных средств и ресурсов, нам необходимо сформулировать эффективные текущие стратегии ограничения и перенаправления для наших системных сервисов для защиты нашей системы.
Алгоритм дырявого ковша и алгоритм токенового ковша являются популярными алгоритмами ограничения тока в отрасли.
2.1 Алгоритмы Дырявого ведра
Алгоритм дырявого ведра относительно прост в реализации. Вода (запрос) сначала поступает в ведро, затем ведро вытекает с определенной скоростью (интерфейс имеет скорость отклика). Когда поток воды слишком велик (частота доступа превышает установленный порог), системная служба отклонит запрос. Принудительные ограничения на количество запросов на доступ к системе в единицу времени. Принципиальная схема алгоритма дырявого ведра выглядит следующим образом: Алгоритм дырявого ковша имеет две ключевые переменные: размер ковша и скорость стока, которые вместе определяют максимальное количество запросов, которые система может получать в единицу времени. Поскольку размер ковша и скорость стока являются фиксированными параметрами в алгоритме дырявого ковша. В чем смысл того, что поток не поступает в порт и не хватает эффективности для трафика с характеристиками пакетов? Позже мы будем использовать PHP для реализации демо-версии с дырявым ведром и подробно объясним результаты тестирования. Исходный адрес GitHub: демонстрация алгоритма дырявого ведра
2.2 Алгоритмы Сбора Токенов
Ведро токенов и Дырявое ведро используют алгоритмы в противоположных направлениях, которые легче понять. Со временем система добавляет токен в корзину с постоянной скоростью 1/QPS (если интервал времени составляет 1 мс). (Представьте, что, вопреки утечке, кран постоянно наполняет ведро.) Если ведро заполнено, оно не будет добавлено. Когда поступит запрос, он попытается взять токен из корзины. Если Токен недоступен, он заблокирует или откажет в обслуживании. Затем он заберет токен в следующий раз, когда появится токен. Алгоритм корзины токенов проиллюстрирован следующим образом: Преимущества корзин токенов очевидны. Мы можем изменить скорость ограничения запросов, увеличив количество токенов, размещенных в корзинах. Корзины токенов обычно добавляют токены в корзины через регулярные промежутки времени (например, добавление токена в корзины каждые 10 мс). Мы будем использовать язык Go для реализации демо-версии корзины токенов. Для достижения совместимости с распределенными параллельными сценариями мы улучшим демонстрационную версию корзины токенов. При добавлении токенов мы используем альтернативный алгоритм: когда поступают запросы, мы вычисляем количество токенов, которые должны быть помещены в корзину в режиме реального времени, в соответствии со скоростью, с которой токен помещается в корзину. Исходный адрес GitHub: демонстрация алгоритма сбора токенов
2.3 Примеры
Функция, которую мы моделируем, заключается в ограничении количества обращений к интерфейсу в рамках компании. Пример состоит в том, чтобы ограничить количество обращений к интерфейсу списка сотрудников/пользователю/списку организаций компании 1 в течение 1 с до 100 внешних обращений.
3.1 PHP алгоритм дырявого ведра
Установка ограничения интерфейса в Redis для доступа к хэшу 100 раз за 1 секунду:
hmset org1/user/list expire 1 limitReq 100
Мы используем Predis для подключения redis для работы. Интерфейс моделирования относительно прост. Мы получаем только два параметра: org и pathInfo. Связанные методы в классе RateLimit следующие:
php /** * Description: Leaky bucket current limiting * User: guozhaoran<[email protected]> * Date: 2019-06-13 */ class RateLimit { Private $conn = null; //redis connection Private $org =';// Corporate Identity 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 isAction Allowed method is omitted here }
Далее давайте рассмотрим дизайн сценария Lua:
/**
* Get the 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. Сценарий Lua выполняет команду Redis для обеспечения атомарности (поскольку Redis однопоточен), поэтому хэш можно последовательно считывать и записывать в условиях одновременной гонки. Команда сначала вызывает incr, чтобы задать количество организаций/пользователей/списков. Четыре структуры данных списка, набора, хэша и набора в Redis являются структурами данных контейнера. Они разделяют следующие два общих правила:
- 1. создайте, если контейнер не существует: Если контейнер не существует, создайте его, а затем действуйте с ним. Например, когда incr org/user/list не существует, это эквивалентно установке org/user/list на 1, поэтому приведенный выше сценарий Lua использует expire для установки времени истечения срока действия org/user/list, когда время равно 1.
- 2. удалить, если элементов нет: Если в контейнере нет элементов, немедленно удалите контейнер и освободите память. Например, после того, как цикл работает со списком, в списке нет содержимого элемента, а затем список не существует.
Логика, приведенная ниже, очень ясна. Это зависит от того, превышает ли совокупное количество вызовов интерфейса предельное значение (предельная частота определяется ARGV [2]). Если ограничение возвращает 0, в противном случае оно возвращает 1.
Далее мы можем увидеть, как метод isActionAllowed определяет, следует ли ограничивать текущий:
/**
* Determine 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… catch… для обработки совместимости. Вторым параметром 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 запросов являются успешными, а последние 10 запросов-неудачными. Порядок таков:
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 раз за 1 секунду. Если в первые 900 миллисекунд совершается только 80 посещений, а в следующие 100 миллисекунд внезапно совершается 50 посещений, то нет никаких сомнений в том, что следующие 30 посещений окажутся неудачными. Однако воронка, простое и грубое решение для ограничения тока, очень подходит для централизованного доступа к трафику, например (всего 1000 посещений в минуту).
3.2 Язык go, Реализующий Алгоритмы Набора Токенов
Прежде всего, не учитывая условия гонки, мы реализуем набор токенов V1 на языке go, чтобы испытать его идею алгоритма. Мы создаем новый модуль воронки, который определяет структуру, содержащую атрибуты, необходимые для корзины токенов:
package funnel
import (
"math"
"time"
)
type Funnel struct {
Capacity int64//Token Bucket Capacity
Leaking Rate float64//Token Bucket Pipeline Rate: Number of tokens added to the token bucket per millisecond
Remaining Capacity int64//Token Bucket Residual Space
LastLeaking Time int64// Last pipelining time (put token) time: millisecond timestampСтруктура воронки поддерживает экспорт, включая емкость корзины токенов, скорость добавления токенов в корзину токенов и оставшееся пространство корзины токенов. Четыре атрибута последнего времени токена. Мы принимаем идею изменения статуса корзины токенов в режиме реального времени при запросе на вход. Методы изменения статуса корзины токенов следующие:
// Update the status of the token bucket when requested, mainly the remaining space of the token bucket and the time stamp of taking Token from the record
func (rateLimit *Funnel) updateFunnelStatus() {
nowTs := time.Now().UnixNano() / int64(time.Millisecond)
// How long has it been since the last token was taken
timeDiff := nowTs - rateLimit.LastLeakingTime
// Calculate how many tokens need to be added to the token bucket based on the time difference and flow rate
needAddSpace := int64(math.Floor(rateLimit.LeakingRate * float64(timeDiff)))
// No tokens need to be added
if needAddSpace < 1 {
return
}
rateLimit.RemainingCapacity += needAddSpace
// The token added should not be larger than the remaining space of the token bucket
if rateLimit.RemainingCapacity > rateLimit.Capacity {
rateLimit.RemainingCapacity = rateLimit.Capacity
}
// Update last token bucket pipelining (add token) timestamp
rateLimit.LastLeakingTime = nowTs
}Чтобы изменить статус корзины токенов, мы используем приемник указателей для определения метода воронки структуры. Основная идея заключается в том, что в соответствии с текущим временем и отметкой времени последнего токена, помещенного в корзину токенов, в сочетании с токеном, который должен помещаться в корзину токенов каждую миллисекунду, должен быть рассчитан токен, добавленный в корзину токенов, и размер самой корзины токенов не может быть превышен после помещения в корзину токенов. Затем достаньте токен и обновите метку времени последнего токена. Чтобы определить, является ли интерфейс ограничивающим ток, необходимо посмотреть, можно ли удалить токен из корзины токенов. Метод заключается в следующем:
// Determine whether the interface is current-limited
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
Мы настраиваем интерфейс (/пользователь/список) компании 2 (org 2) с емкостью корзины токенов 100 и помещаем токен каждые 10 мс (метод расчета 10/1000). Мы храним поле содержимого объекта воронки в хэш-структуре. Нам нужно взять значение из хэш-структуры, выполнить расчет в памяти, а затем заполнить его обратно в хэш-структуру при расчете того, следует ли ограничивать ток. Особенно для естественной параллельной программы, такой как язык go, мы не можем гарантировать атомизацию всего процесса (вот почему мы используем сценарий Lua, потому что если мы используем сценарий Lua. Программы должны быть заблокированы для достижения, после блокировки существует вероятность сбоя блокировки, сбой может быть вызван только повторной попыткой или отказом, повторная попытка приведет к снижению производительности, отказ повлияет на пользовательский интерфейс, сложность кода значительно возрастет. Наша версия V2 по-прежнему будет использовать сценарий Lua для достижения: конкретный процесс исследования заключается в следующем:
| Механизм блокировки для работы одной сервисной пары | Как упоминалось в статье, этот метод может гарантировать сериализацию только на одном узле и имеет низкую производительность. |
| Радиус атомной операции увеличивается | Эта схема используется в модели воронки. Он может работать только с простыми сценариями. Трудно иметь дело со сложными сценариями. |
| Распределенная транзакция Redis | Хотя распределенная транзакция Redis может гарантировать атомарную работу, ее реализация сложна, а сетевые издержки велики, что требует большой сетевой передачи. |
| Redis+Lua | Здесь мы должны преувеличить это решение. Сценарий Lua выполняется в Redis, redis однопоточный, поэтому он может гарантировать последовательную работу. Кроме того: для снижения сетевых накладных расходов, как мы упоминали ранее, командам, завернутым в код Lua, не нужно отправлять несколько запросов команд. Redis может кэшировать сценарии Lua для уменьшения передачи по сети, и другие клиенты также могут использовать кэширование. |
Кроме того, Redis 4.0 предоставляет модуль ограничения тока, называемый Redis-Cell. В этом модуле также используется алгоритм воронки, и предусмотрена команда ограничения тока атомов. Механизм повторных попыток очень прост, поэтому его интересно изучить. Мы все еще используем решение Lua + Redis здесь, чтобы сказать меньше глупостей, код в версии V2:
const luaScript = `
Interface Current Limitation
- last_leaking_time last access time in milliseconds
-- remaining_capacity Number of Request Tokens Available in Current Token Bucket
Capacity Token Bucket Capacity
-- Rate of adding tokens to leaking_rate token bucket
Persistence and master-slave replication of commands with data changes in a transactional manner (Redis 4.0 support)
redis.replicate_commands()
Get configuration information for token buckets
local rate_limit_info = redis.call("HGETALL", KEYS[1])
Get the current timestamp
local timestamp = redis.call("TIME")
local now = math.floor((timestamp[1] * 1000000 + timestamp[2]) / 1000)
If rate_limit_info== nil then -- If no current limiting configuration is set, the token is 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 return result can get the token or not by default
- Calculate whether the request can get a 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 получает текущую метку времени только в секундах, в то время как Redis получает ее.
- Если метка времени передается в качестве параметра вызова сценария (программа go), это будет проблематично, поскольку все еще существует некоторая ошибка времени, когда сценарий передается Lua для выполнения в Redis, что не может гарантировать, что первый полученный запрос будет обработан первым, в то время как получение метки времени в Lua может гарантировать, что запрос и время являются последовательными.
Как и прежде, без настройки текущей конфигурации ограничения, она может быть запрошена по умолчанию. Затем, в соответствии с меткой времени для пополнения токена, рассчитайте, можно ли получить токен, а затем обновите статус токена. Идея та же, что и в версии V1, читатель может прочитать ее сам. Чтобы проиллюстрировать, красный цвет есть. команда replicate_commands () в начале сценария связана с тем, что более низкая версия 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 to the 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)
}
// Processing the request function and writing the response result information to the log according to the request
func handleReq(w http.ResponseWriter, r *http.Request) {
// Getting URL information
pathInfo := r.URL.Path
// Get the company information transmitted by get ORG
orgInfo, ok := r.URL.Query()["org"]
if !ok || len(orgInfo) < 1 {
fmt.Println("Param org is missing!")
}
// Invoking the atomicity of lua script 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 statistics into 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 framework redigo go для работы с redis. Мы инициализируем пул соединений redis и получаем соединение из пула соединений для работы. Мы анализируем следующий код:
lua := redis.NewScript(1, luaScript)
reply, err := redis.Int64(lua.Do(conn, key))Первый параметр в Новом скрипте представляет количество ключей для работы с Redis, аналогично второму параметру в evalsha Predis. Затем скрипт выполняется методом Do, возвращаемое значение обрабатывается redis. Int64, и операция выполняется для определения того, разрешен ли доступ к интерфейсу. Затем время доступа и результаты записываются в состояние. файл журнала журнала. Логика по-прежнему очень проста, мы в основном смотрим на результаты измерения давления, запускаем код, используя команду измерения давления AB для выполнения:
ab -n 110 -c 10 http://127.0.0.1:8082/user/list\?org\=org2
Тогда мы могли бы быть удивлены, проанализировав состояние. журналы регистрации:
1561263349294 request success!//First line log ...//95 lines omitted 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 запросам выдаются токены. Можно видеть, что корзина токенов подходит для ограничения тока при большом потоке, что может обеспечить равномерное распределение потока в соответствии со временем и избежать централизованного доступа к трафику.
До сих пор мы указывали на необходимость ограничения тока, а также на общие средства и процедуры ограничения тока. Я полагаю, что у вас есть предварительное понимание ограничения тока шага. Вот краткое резюме:
| Он подходит для доступа при большом трафике, что может обеспечить равномерное распределение трафика в зависимости от времени и избежать возникновения централизованного взрывоопасного доступа к трафику. | Ведро для токенов |
| Простой и грубый, он хорошо влияет на нижний предел потока большого трафика, особенно для сервиса ограничения запросов в единицу времени, и не может хорошо реагировать на внезапный трафик. | Дырявое ведро |
Оригинал: “https://developpaper.com/redis-lua-interface-current-limitation-best-practice-strategy/”