LINUX.ORG.RU

Можно ли подобрать параметры по входным данным и алгоритму, без прогона симулятора

 


0

1

Доброго времени суток.

Хотя речь пойдёт об nginx, тема скорее имеет отношение к алгоритмам и программированияю. Есть лог nginx, нужно подобрать ограничения, чтобы отрезать ботов.

Ограничение числа запросов за единицу времени в nginx задаётся через 2 синтетические величины, rate и burst

excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000;

if (excess < 0) {
excess = 0;
}
[...]
if ((ngx_uint_t) excess > limit->burst) {
return NGX_BUSY;
}

Приблизительно можно считать, что rate ограничивает частоту поступления запросов, burst - позволяет пропускать пики запросов.

Например, пусть rate=5, burst=100. nginx пропустит запросы пользователя, который одновременно прислал 80 запросов, потом успокоился на 2 минуты. Но ограничит бота, который шлёт запросы с частотой 6 запросов в секунду ( хотя и не сразу, а примерно через 80 секунд с момента запуска бота ). Т.е. даётся некоторый запас burst, при превышении - жёстко режем по rate

У меня есть лог. Пусть для простоты имеем одного клиента. В логе время каждого обращения, в unixtime ( опять же для простоты )

unixtime1
unixtime2
unixtime3
...
unixtimeN

Вижу, что параметры можно подбирать - написать симулятор ( вход - rate, burst, лог ; выход - блокированные запросы ) и подбирать burst и rate. А хотелось бы не брутфорсить, а вычислять эти значения. Можно ли из лога вычислить достаточные burst и rate?

update В итоге написал пару скриптов. Комментарии внутри. Для понимания нужен средний скил Perl

★★★★★

Последнее исправление: router (всего исправлений: 2)

Построить график распределения вероятности для rate и burst по логам, по нему посмотреть.

goingUp ★★★★★
()

Второе что приходит в голову. Если фиксировать rate, то burst вычислить можно. Прогнать алгоритм симулятора с заданным rate, и когда excess превысил burst, увеличиваем burst на ту же величину.

Остаётся вопрос, как же подобрать хоть какое-то оценочное значение rate.

router ★★★★★
() автор топика
Ответ на: комментарий от router

В памяти и производительности я почти не ограничен. Можно честно считать число запросов x за интервал t ( через очередь, в perl буду использовать массив ). Взять достаточно большой интервал t и взять за rate максимум числа запросов на этом интервале max(x)/t

Это уже выглядит неплохо

router ★★★★★
() автор топика
Ответ на: комментарий от router

График типа такого http://ru.wikipedia.org/wiki/Нормальное_распределение
По оси х rate, площадь под графиком - сколько % пользователей лежат в этом диапазоне rate (по сути вероятность того, что случайно выбраный пользователь попадет в диапазон). У тебя вряд ли будет нормальное распределение, статья просто пример графика.

goingUp ★★★★★
()
Последнее исправление: goingUp (всего исправлений: 1)

Можно ли из лога вычислить достаточные burst и rate?

Можно вычислить такие, которые заблокируют определённые запросы, а остальные пропустят. Проблема в том что анализатор понятия не имеет, какие запросы нужно блокировать, кто бот, кто нет.

Можно взять достаточно репрезентативный лог, пометить (вручную?) ботов, и попробовать посчитать такие burst и rate, чтобы не повлияло на легитимных пользователей и забанило наибольшее количество ботских запросов

disarmer ★★★
()
Ответ на: комментарий от disarmer

Проблема в том что анализатор понятия не имеет, какие запросы нужно блокировать, кто бот, кто нет.

Разумеется. Это я могу определить, но не скрипт.

Можно взять достаточно репрезентативный лог, пометить (вручную?) ботов, и попробовать посчитать такие burst и rate, чтобы не повлияло на легитимных пользователей и забанило наибольшее количество ботских запросов

Вопрос был именно в том, КАК посчитать ;)

router ★★★★★
() автор топика
Ответ на: комментарий от goingUp

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

Но не могу увидеть, как же это можно в принципе использовать для подбора burst и rate одного клиента.

router ★★★★★
() автор топика
Ответ на: комментарий от router

Вопрос был именно в том, КАК посчитать ;)

Это как уравнение с двумя переменными, тут бесконечное множество решений. Так что либо подобрать вручную, либо задать одну(например rate) и по ней посчитать максимальный легитимный burst

disarmer ★★★
()
Ответ на: комментарий от router

Остаётся вопрос, как же подобрать хоть какое-то оценочное значение rate.

Бинарным поиском по ответу :)

vzzo ★★★
()

https://yadi.sk/d/ZmcOt2V6WT8Nf

# при поиске burst и rate
# из всего лога nginx нас интрересует только ip и время. Причём время желательно в unixtime, чтобы не терять время на конвертацию
# этот скрипт работает как фильтр.
# на входе - лог nginx
# на выходе - упрощённый лог nginx, в котором строки имеют вид "ip unixtime"
# cat access.log | ./simplify_nginx_log.pl > simple.log

https://yadi.sk/d/qgLIRbzpWT8NT

# по логу nginx подбираем параметры для модуля ngx_http_limit_req_module
# 1. сначала -m calc_rate -d '1;10;60;300;3600' считаем минимальный rate для интервалов 1 с, 10 с, 1 мин, 5 мин, 1 ч ( это лишь пример, интервалы можно взять другие )
# 2. потом -m calc_burst -d '1;10;50;100' считаем максимальный burst для rate = 1, 10, 50, 100 ( исходя из результатов п.1 )
# 3. потом -m simulate -d '1;10;1;100;10:10;10:100' пытаемся подобрать rate и burst так, чтобы и rate, и burst были поменьше, но клиенты не пострадали
# или - чтобы как можно меньше клиентов пострадало

################################################################################
# mode = calc_rate
# вычислим максимальное чило запросов за интервал $interval
# поделив его на $interval, получим частоту
# полученное значение частоты можно считать нижней границей
################################################################################


################################################################################
# mode = calc_burst
# для каждого данного rate вычислим минимальный burst
# при котором ни однин запрос не будет отброшен
# полученное значение можно считать верхней оценкой burst
################################################################################


################################################################################
# mode = simulate
# для каждой данной пары rate:burst прогоним симуляцию чтобы посчитать
# какое количество ( и процент ) запросов ( для каждого ip отдельно ) будет отброшено
################################################################################

router ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.