В классе поточных алгоритмов имеется подкласс, решающий задачу поиска тяжелых элементов (heavy hitters). В общем виде эта задача формулируется как «выявление во входящем потоке наиболее часто повторяющихся событий и измерение их интенсивности». В данной публикации сотрудника компании Qrator Labs Артема janatem Шворина предлагается эффективный алгоритм для решения этой задачи.
Введение
Алгоритмы нахождения тяжелых элементов помогают решать задачи, такие как борьба с перегрузкой сети, выявление сетевых аномалий и атак, управление динамической маршрутизацией. Например, известный веб-сервер NGINX позволяет ограничивать интенсивность запросов к определённому ресурсу, и для того, чтобы это делать, интенсивность должна быть измерена количественно.
В этой публикации мы хотим показать читателю ещё один подход к измерению интенсивности потока событий при наличии множества разных (не идентичных) потоков событий. Пусть задано множество типов событий. Требуется оценивать, насколько часто происходит событие данного типа, и обращать внимание на случаи, когда событие одного типа повторяется «слишком часто».
Читать полностью »