Здравствуйте, Буравчик, Вы писали:
Б>На лету (без таймера) так: Б>- для каждого пользователя храним время для 100 последних запросов этого пользователя (например, в виде queue) Б>- при поступлении запроса добавляем его в конец очереди и удаляем самый старый запрос (самый первый) Б>- вычисляем разницу по времени между этими запросами и сравниваем ее с одной минутой — определили робот, или нет Б>- обновляем количество текущих роботов
Способ хороший и практичный для похожих задач, но к конкретно на вопрос "каково текущее число пользователей, которые за последнюю минуту сделали более 100 запросов" он не позволит ответить.
Так как декремент общего счётчика завязан на внешние действия. И он не будет происходить, если внешних действий не будет.
Например, пусть есть полностью пустая система. В момент X приходит 1000 пользователей и задаёт за 1 секунду по 1000 запросов каждый. Мы их радостно записываем в роботы и увеличиваем счётчик до 1000. Потом пользователи перестают задавать запросы. Через минуту счётчик должен опустится, так как больше запросов нет вообще ни от кого. Но он этого не произойдёт, так как без таймера не будет сгенерировано событие, которое приведёт к пересчёту статуса пользователя.
То есть через такой алгоритм хорошо реализуется счётчик числа пользователей, которые хотя бы раз были записаны в роботы. Но не счётчик, который позволяет пользователю терять атрибут "робот".
Впрочем, если это практическая задача, то последнее свойство обычно не доставляет неудобств — можно и не разбанивать забанненного робота в тот же момент, когда он перестал спамить запросами
Я бы решал задачу так:
для каждого пользователя заводим пару чисел счетчик запросов (усредненный) и последнее время обновления. Для нулевых счетчиков вообще не держим данные в базе.
при приходе запроса считаем, что все предыдущие запросы приходили равномерно в течение минуты, поэтому вычитаем из существующего значения число пропорциональное разнице времени последнего обращения и текущего времени. Пример, счетчик 10, время до предыдущего обращения 1 секунда — новое значение счетчика 10 — (1/60)*10 + 1 (поправили счетчик с учетом времени отсутствия запросов и прибавили текущий запрос). Если интервал был больше минуты — обнуляем счетчик и прибавляем 1 (текущий запрос). Время последнего обращения устанавливаем текущее.
Итого, для каждого пользователя храним только два числа — счетчик и время последнего обновления (или ничего, если счетчик нулевой).
По сути примерно тот же token bucket, только токены добавляем не по таймеру, а когда приходит очередной запрос (точнее храним сколько токенов израсходовано, причем округленно, а не точно). Для подобных задач типа ограничения количества запросов точности алгоритма вполне достаточно.
Здравствуйте, watchmaker, Вы писали:
W>Например, пусть есть полностью пустая система. В момент X приходит 1000 пользователей и задаёт за 1 секунду по 1000 запросов каждый. Мы их радостно записываем в роботы и увеличиваем счётчик до 1000. Потом пользователи перестают задавать запросы. Через минуту счётчик должен опустится, так как больше запросов нет вообще ни от кого. Но он этого не произойдёт, так как без таймера не будет сгенерировано событие, которое приведёт к пересчёту статуса пользователя.
Замечание интересное и верное, но в данном случае — спорное.
Если пользователь уже проявил себя как робот и не делает новых запросов, то он все еще робот.
Здравствуйте, n0dwis, Вы писали:
N>На собеседовании попалась задача, основной смысл такой: N>
N>Нужно написать сервис, который будет считать текущее количество наших пользователей, являющихся роботами. Роботом считается пользователь, который делает более 100 запросов в минуту.
N>"В лоб" я её решил. Т.е. просто накапливать запросы, вместе со временем их поступления и по таймеру очищать старые. Но, по-видимому, предполагался другой подход — анализ сразу на лету. Но не могу понять, каким образом отбрасывать старые данные? Не знаю даже, в каком направлении искать.
N>Подскажите, хоть к какому разделу относятся такого типа задачи.
берем любую базу ключ-значение с инкрементом (Redis)
берем любой брокер очередей (Kafka/Rabbit) для апдейта значений последовательно, без гонок
инкремент через очередь, GET — многопоточный
2 переменные
1я хранит текущее время первого запроса с протуханием 60 секунд (при запросе просто обновляет ttl)
2я хранит количество запросов и протухает за 60 секунд
дальше математика
количество запросов делим на количество секунд, умножаем на 60 (остальная логика не важна, так как если пройдет минута, мы сбросим переменные)
ключ-значение решает вопрос с многопоточным чтением
брокер очередей пишет в один поток
т.е. на выходе у вас будет среднее число запросов за период времени (по ttl — 1 минута)
за минуту очередь всегда разойдется, либо протухнут переменные
при запросе просто if(COUNT/(NOW — V1)) > N => BAN
Здравствуйте, n0dwis, Вы писали:
N>На собеседовании попалась задача, основной смысл такой: N>
N>Нужно написать сервис, который будет считать текущее количество наших пользователей, являющихся роботами. Роботом считается пользователь, который делает более 100 запросов в минуту.
N>"В лоб" я её решил. Т.е. просто накапливать запросы, вместе со временем их поступления и по таймеру очищать старые. Но, по-видимому, предполагался другой подход — анализ сразу на лету. Но не могу понять, каким образом отбрасывать старые данные? Не знаю даже, в каком направлении искать.
N>Подскажите, хоть к какому разделу относятся такого типа задачи.
