На собеседовании попалась задача, основной смысл такой:
Нужно написать сервис, который будет считать текущее количество наших пользователей, являющихся роботами. Роботом считается пользователь, который делает более 100 запросов в минуту.
"В лоб" я её решил. Т.е. просто накапливать запросы, вместе со временем их поступления и по таймеру очищать старые. Но, по-видимому, предполагался другой подход — анализ сразу на лету. Но не могу понять, каким образом отбрасывать старые данные? Не знаю даже, в каком направлении искать.
Подскажите, хоть к какому разделу относятся такого типа задачи.
Здравствуйте, n0dwis, Вы писали:
N>Подскажите, хоть к какому разделу относятся такого типа задачи.
Никак эта задача не решается без аккумулирования данных. Хоть в прямом виде, хоть в агрегированном. Относятся они к разделу "догадайся, о чём думает шибко мнящий о себе интервьюер". Дать бы им всем в лоб.
Здравствуйте, n0dwis, Вы писали:
N>"В лоб" я её решил. Т.е. просто накапливать запросы, вместе со временем их поступления и по таймеру очищать старые. Но, по-видимому, предполагался другой подход — анализ сразу на лету. Но не могу понять, каким образом отбрасывать старые данные? Не знаю даже, в каком направлении искать.
На лету (без таймера) так:
— для каждого пользователя храним время для 100 последних запросов этого пользователя (например, в виде queue)
— при поступлении запроса добавляем его в конец очереди и удаляем самый старый запрос (самый первый)
— вычисляем разницу по времени между этими запросами и сравниваем ее с одной минутой — определили робот, или нет
— обновляем количество текущих роботов
N>Подскажите, хоть к какому разделу относятся такого типа задачи.
хз, но придумалось примерно так:
1. заводим циклический буфер (размера 60 — на каждую секунду из ближайшего прошлого) со списками пользователей, выполнивших запрос
2. при поступлении запроса, добавляем пользователя в список головного элемента циклического буфера и плюсуем ему единичку в таблицу "количество запросов за последнюю минуту"
3. (отбрасываем старые данные) каждую секунду берем последний элемент циклического буфера со списком пользователей, выполнивших запрос минуту назад, и у каждого в этом списке минусуем единичку в таблице и сдвигаем циклических буфер
итого, у нас есть табличка со списком всех пользователей и количеством их запросов за последнюю минуту, надо просто отфильтровать из нее роботов.
это тоже самое что ты придумал?
В общем-то, все предложения — более-менее вариации моего решения.
Ещё была мысль — при поступлении запроса увеличить для каждого пользователя счётчик, а для уменьшения — заводить таймер на 1 минуту. Но, по-моему, слишком сложно для такой задачи — потоков же будет очень много, а пользы — почти нет. Только что не хранить список.
Здравствуйте, n0dwis, Вы писали:
N>Подскажите, хоть к какому разделу относятся такого типа задачи.
Если нужно считать RPS точно, то это алгоритмы из разряда moving average, обычно exponential moving average потому что считать дискретные события в непрерывном пространстве это всегда весело. Но твоя задача это перефразированная задача ограничения частоты запросов (requests throttling). Для нее считать вообще не нужно. Классический алгоритм называется token bucket. Допустим мы хотим ограничить пользователя 100 запросами в секунду. Для каждого пользователя выделяем мешок определенного размера под фишки. Каждую секунду бросаем в этот мешок 100 фишек. Если мешок полон, фишки, которые не влезли, отбрасываются. Когда пользователь делает запрос, вынимаем одну фишку из мешка. Если мешок пустой, отбрасываем запрос.
Здравствуйте, Miroff, Вы писали:
M>Классический алгоритм называется token bucket. Допустим мы хотим ограничить пользователя 100 запросами в секунду. Для каждого пользователя выделяем мешок определенного размера под фишки. Каждую секунду бросаем в этот мешок 100 фишек. Если мешок полон, фишки, которые не влезли, отбрасываются. Когда пользователь делает запрос, вынимаем одну фишку из мешка. Если мешок пустой, отбрасываем запрос.
Окно получается не скользящее? Грубо говоря в 0.5с пришло 60 запросов, в 1.3с пришло 60 запросов, но на 1с мы обновили бакет и робота у нас выявилось, так?
Здравствуйте, Miroff, Вы писали:
M>Если нужно считать RPS точно, то это алгоритмы из разряда moving average, обычно exponential moving average потому что считать дискретные события в непрерывном пространстве это всегда весело. Но твоя задача это перефразированная задача ограничения частоты запросов (requests throttling). Для нее считать вообще не нужно. Классический алгоритм называется token bucket. Допустим мы хотим ограничить пользователя 100 запросами в секунду. Для каждого пользователя выделяем мешок определенного размера под фишки. Каждую секунду бросаем в этот мешок 100 фишек. Если мешок полон, фишки, которые не влезли, отбрасываются. Когда пользователь делает запрос, вынимаем одну фишку из мешка. Если мешок пустой, отбрасываем запрос.
Здравствуйте, n0dwis, Вы писали:
N>На собеседовании попалась задача, основной смысл такой: N>
N>Нужно написать сервис, который будет считать текущее количество наших пользователей, являющихся роботами. Роботом считается пользователь, который делает более 100 запросов в минуту.
N>"В лоб" я её решил. Т.е. просто накапливать запросы, вместе со временем их поступления и по таймеру очищать старые. Но, по-видимому, предполагался другой подход — анализ сразу на лету. Но не могу понять, каким образом отбрасывать старые данные? Не знаю даже, в каком направлении искать.
N>Подскажите, хоть к какому разделу относятся такого типа задачи.
А зачем хранить данные, что под старыми данными имеется в виду? Счетчик и время первого обращения?
Для каждого пользователя -- новая сессия -- заводите счетчик и время. С каждым запросом увеличиваете счетчик, при этом
можно посмотреть и на время. Если разница меньше минуты и счетчик > 100, то робот. Сами данные потоком на сервер -- запрос\ответ.
Т.е. накапливать запросы не вижу смысла. Либо можно таймер на новую сессию вещать, но данный подход, кмк, не очень.
Лишние сущности и расход ресуров.
С>Никак эта задача не решается без аккумулирования данных. Хоть в прямом виде, хоть в агрегированном. Относятся они к разделу "догадайся, о чём думает шибко мнящий о себе интервьюер". Дать бы им всем в лоб.
В таких задачах расчет на то, что интервьюируемый будет задавать вопросы, а не кинется сразу делать.
Здравствуйте, Kernan, Вы писали:
K>Окно получается не скользящее? Грубо говоря в 0.5с пришло 60 запросов, в 1.3с пришло 60 запросов, но на 1с мы обновили бакет и робота у нас выявилось, так?
Верно. Это всегда компромисс между производительностью и точностью.
Здравствуйте, Sharov, Вы писали:
S>Если разница меньше минуты
Если разница между минуты с чем? С первым запросом? Или с последним? Но ведь это в любом случае неправильно. Не факт, что робот в первую же минуту отправит 100 запросов. И не факт, что пользователь не умудрится в какую-то минуту отправить 100 запросов, количество которых потом снизится.
Нужно ведь считать от текущего момента, а не в каждую конкретную секунду. Ну, я так задачу понимаю.
Здравствуйте, n0dwis, Вы писали:
N>Если разница между минуты с чем? С первым запросом? Или с последним? Но ведь это в любом случае неправильно. Не факт, что робот в первую же минуту отправит 100 запросов. И не факт, что пользователь не умудрится в какую-то минуту отправить 100 запросов, количество которых потом снизится. N>Нужно ведь считать от текущего момента, а не в каждую конкретную секунду. Ну, я так задачу понимаю.
Виноват, не так понял условие. Думал что в первую минуту отправит 100. Тогда может и вправду от таймера плясать,
как решение в лоб. Может опять неправ, но навскидку запускать таймер для каждой сессии и каждую минуту сбрасывать
счетчик: если больше 100 -- робот, иначе -- нет. Хотя и это не сработает, если, например было 10 запросов с 1 по 20 сек,
замет с 20 по 59 сек нагенерил еще 80,и в первые 10 сек сл. минуты еще 30, т.е. меньше чем за минуту больше 100 запросов.
Таймер это не отработает. Действительно нужно скользящее окно (или что-то вроде) запускать. Другой вопрос, когда имеет смысл это делать?
Т.е. действительнонужна какая-то очередь\массив индекс-время, и смотреть соотв. интервалы.
Прикольная задачка.
Здравствуйте, Miroff, Вы писали:
M>Верно. Это всегда компромисс между производительностью и точностью.
А вот ещё вопрос есть, что если у нас 1 млн клиентов? Придётся по таймеру обновлять весь миллион? Это не не совсем производительно. Как можно улучшить?
Здравствуйте, Sharov, Вы писали: S>В таких задачах расчет на то, что интервьюируемый будет задавать вопросы, а не кинется сразу делать.
Только если он не решал подобную проблему сам.
Здравствуйте, Kernan, Вы писали:
K>Здравствуйте, Miroff, Вы писали:
M>>Верно. Это всегда компромисс между производительностью и точностью. K>А вот ещё вопрос есть, что если у нас 1 млн клиентов? Придётся по таймеру обновлять весь миллион? Это не не совсем производительно. Как можно улучшить?
Достаточно немного изменить решение — не брать фишки из мешка при каждом входящем запросе, а наоборот класть их в мешок. Когда в мешке окажется 100 фишек, новые запросы от пользователя не обрабатываются (до очистки мешка).
Мы не обязаны хранить пустые мешки пользоватей (от которых нет запросов в данный интервал). Поэтому можем очистить все мешки пользователей разом, уничтожив все мешки, т.е. очистив словарь "пользователь->мешок" (создав новый пустой словарь).
Здравствуйте, Kernan, Вы писали:
K>Здравствуйте, Miroff, Вы писали:
M>>Верно. Это всегда компромисс между производительностью и точностью. K>А вот ещё вопрос есть, что если у нас 1 млн клиентов? Придётся по таймеру обновлять весь миллион? Это не не совсем производительно. Как можно улучшить?
