Shapelez Aug 1 2017 at 11:07

Измерение интенсивности входящего потока событий в модели распада

12 min

6.5K

Qrator Labs corporate blogAlgorithms*C*Mathematics*

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

Введение

Алгоритмы нахождения тяжелых элементов помогают решать задачи, такие как борьба с перегрузкой сети, выявление сетевых аномалий и атак, управление динамической маршрутизацией. Например, известный веб-сервер NGINX позволяет ограничивать интенсивность запросов к определённому ресурсу, и для того, чтобы это делать, интенсивность должна быть измерена количественно.

В этой публикации мы хотим показать читателю ещё один подход к измерению интенсивности потока событий при наличии множества разных (не идентичных) потоков событий. Пусть задано множество типов событий. Требуется оценивать, насколько часто происходит событие данного типа, и обращать внимание на случаи, когда событие одного типа повторяется «слишком часто».

Важной характеристикой данного инструмента является его высокая эффективность, чтобы он не стал узким местом во всей системе анализа и фильтрации трафика. Речь в этом случае идет о том, чтобы обрабатывать одно событие за несколько десятков тактов центрального процессора современных компьютеров.

Помимо собственно измерения интенсивности требуется выделять типы событий, которые случаются наиболее часто. Их интенсивность нужно измерять более точно, в то время как редкие типы событий большой роли не играют, и оценивать их интенсивность не обязательно с высокой точностью.

В работе представлен разработанный нами алгоритм Decay-based count, основанный на модели распада радиоактивного вещества (см. раздел «Модель распада»), с высокой эффективностью решающий задачу поиска тяжелых элементов.

Задача поиска тяжелых элементов

Классификация задач

В описываемом классе задач можно выделить следующие подклассы:

Threshold- $inline$ . Требуется выделить потоки, имеющую большую интенсивность чем заданная доля $inline$ интенсивности всего входящего трафика.
Top- $inline$ . Требуется выделить заданное количество $inline$ самых интенсивных потоков.
Выделение потоков, интенсивность которых превышает некоторое заданное абсолютное значение.

Предлагаемый алгоритм относится к последнему из перечисленных подклассов.

Целевая архитектура

В зависимости от платформы, на которой предполагается запускать данный поточный алгоритм, имеется набор аппаратных ограничений. Иногда требуется встраивать нужную функциональность в сетевое оборудование (свитч, коммутатор и т. п.). Предлагаемый алгоритм предполагается использовать на универсальном процессоре, но при некоторых значениях параметров допускает встраивание в сетевое оборудование.

Параметры задачи

Абсолютное значение интенсивности потока, которое считается «опасным». Задачей алгоритма является выявление потоков, интенсивность которых превышает заданный порог.
Размер ключа — идентификатора, по которому определяется тип события. В данной реализации, как и во многих других алгоритмах, требуется хранить значения ключей в таблице, поэтому размер ключа влияет на затраты памяти.
Способ вычисления оценки интенсивности одного потока по временам прихода однотипных событий. По сути это алгоритмическое определение того, что такое интенсивность потока. В этом случае вычисляется экспоненциальное скользящее среднее, которое имеет единственный параметр — характерное время $\tau$ , в течение которого учитывается вес события после его прихода.

Точность решения

Оценкой качества алгоритма может быть относительная или абсолютная погрешность в оценке интенсивности потоков. Также используют $(\varepsilon,\delta)$ -аппроксимацию в качестве оценки точности: если с вероятностью $1-\delta$ погрешность составляет не более $\varepsilon$ , то говорят, что алгоритм имеет характеристику точности $(\varepsilon, \delta)$ .
Если ошибка имеет качественный, а не количественный характер, как, например, включение или невключение данного потока в список самых интенсивных в задаче top- $inline$ , то для оценки берутся вероятности ложноположительного и ложноотрицательного срабатывания.

Накладные расходы

Как правило, основной характеристикой алгоритма является максимальная интенсивность входящего потока, которую он способен обработать. То есть важно лишь время обработки одного события. Однако на практике влияют и другие аппаратные ограничения, такие как размер памяти, используемой для хранения накопленной информации о потоке. Особенно жесткие аппаратные ограничения имеют место при встраивании функционала в сетевое оборудование. Но и на обычных компьютерах наличие большого количества оперативной памяти DRAM помогает далеко не всегда, поскольку доступ в DRAM может занимать неприемлемо много времени. Для того чтобы достичь требуемой производительности, приходится идти на компромисс с точностью измерения и ограничивать размер используемой памяти, чтобы она помещалась в кэш процессора. В данной реализации при осмысленных значениях параметров таблица помещается в L2 кэш процессора. В результате удалось добиться того, чтобы время обработки одного события составляло несколько десятков тактов процессора.

Методы оценки интенсивности потока

Для оценки интенсивности повторений событий заданного типа требуется посчитать количество событий в течение некоторого времени. Для этого нужно фиксировать время наступления события и каким-то образом сохранять его. Обычно для этой цели используют счетчик, который инкрементируется при наступлении соответствующего события. Тогда интенсивность оценивается как отношение значения счетчика к интервалу времени, в течение которого проводится измерение. Более аккуратные способы измерения актуального значения интенсивности используют различные варианты скользящего среднего. Например, экспоненциальное скользящее среднее (exponential moving average, EMA) — разновидность взвешенного скользящего среднего с экспоненциально убывающими весами.

В работе предлагается новый метод вычисления EMA. Здесь используется модель экспоненциального распада, которая описывает такое физическое явление как радиоактивный распад. Эта модель имеет ряд преимуществ по сравнению с традиционным подходом. Во-первых, представление данных оказывается более экономичным по памяти. Во-вторых, модель распада допускает эффективную по скорости реализацию операции обновления счетчика — она требует небольшое количество целочисленных арифметических операций и одно кэшируемое обращение к памяти.

Методы учета множества потоков

В задаче поиска тяжелых элементов проблемой является не только высокая интенсивность входного трафика, но и большое количество различных потоков (типов событий), за которыми приходится следить. Наивная реализация предполагает заведение отдельного счетчика на каждый поток, что приводит к значительному расходу памяти. При этом есть опасность не только в исчерпании всей доступной памяти, но в существенной замедлении скорости работы из-за промахов в кэш. Поэтому, как правило, отказываются от точного решения задачи поиска тяжелых элементов, выбрасывая часть накопленной информации о потоках. Известно множество методов ограничения объема используемой памяти и уменьшения времени обработки события, некоторые из которых приведены ниже:

Packet sampling
Space saving algorithm
HashParallel
HashPipe
Count-min sketch

Формализация задачи

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

Последовательность однотипных событий задается в виде множества элементарных событий $\{event_k\}_{k\in I}$ , где индекс $inline$ пробегает конечный или бесконечный дискретный интервал $I\subset\mathbb{Z}$ .

В простейшем случае событие определяется только временем его наступления: $inline$ , причем события упорядочены во времени: $t_{k_1} < t_{k_2}$ для $inline$ . В большинстве реализаций систем учета событий время считается дискретной величиной: $t_k\in\mathbb{Z}$ , однако для теоретических рассуждений бывает удобно обобщить и считать время непрерывным: $t_k\in\mathbb{R}$ .

Основной вопрос, на который должны отвечать системы учета событий, — это оценка интенсивности потока. Интенсивность может быть строго формализована для равномерного потока событий. Равномерный поток $\{t_k\}$ определяется следующим образом:

$t_k = \varphi+pk,\quad k\in\mathbb{Z},$

где $inline$ , $\varphi\in[0,p)$ — параметры потока — период и фаза, соответственно. То есть события наступают через равные промежутки времени. Тогда интенсивность такого потока, по определению, выражается как $inline$ .

Для неравномерных потоков формальное определение интенсивности $r=r(\{t_k\})$ может отличаться в зависимости от постановки задачи. Модель распада остается работоспособной и полезной и в этом случае, однако оценка качества вычисления истинной интенсивности дана ниже только для случая равномерных потоков.

В некоторых моделях требуется дополнительно учитывать некоторую характеристику события, например, его вес $inline$ — величина вклада данного события в измеряемую интенсивность. Тогда событие определяется не только временем его наступления, но и весом: $inline$ .

В типичных реализациях систем учета событий заводится счетчик $inline$ , который некоторым образом накапливает информацию о потоке событий, и в любой момент времени по его текущему значению можно получить оценку интенсивности потока $\hat{r}=\hat{r}(s)$ , такую что $r\approx\hat{r}$ . Обновление счетчика происходит по приходу очередного события $inline$ :

$s \leftarrow update(s, event_k),$

где $inline$ — некоторая функция, которая определяется реализацией. Ниже приведено несколько примеров с вариантами реализации функции $inline$ :

Простой подсчет количества событий: $inline$ ;
Подсчет количества событий с учетом веса: $inline$ ;
Вычисление экспоненциального скользящее среднего (EMA) с параметром $\beta$ . Здесь счетчик $inline$ хранит две величины: собственно значение EMA и время последнего обновления.
$update_{EMA}((v, t), event_k) = (v', t'),$
где $v'=\beta + (1-\beta)^{t_k-t}\cdot v,\quad t'=t_k$ .

В некоторых задачах требуется различать потоки событий. Пусть имеется множество различных типов событий, занумерованных индексом $i=1,\dots N$ , и требуется учитывать отдельно потоки сообщений каждого типа. Тогда событие описывается как $inline$ (или, с учетом веса события, $inline$ ), где $inline$ — тип события. Множество индексов $inline$ , относящихся к данному типу события $inline$ обозначим $I_i = \{k\mid i_k = i\}$ .

Модель распада

Модель распада описывается следующим образом:

$v(t) = v_0 e^{-\lambda t},$

где $inline$ — «количество вещества» в нулевой момент времени, $inline$ — количество в момент времени $inline$ , $\lambda$ — параметр модели (так называемая постоянная распада). Название данной модели отражает тот факт, что она описывает физическое явление радиоактивного распада.

Дополнительно введем следующие обозначения:

$\tau = 1/\lambda,\quad\alpha = e^{\lambda}.$

В нашем случае в качестве параметра модели вместо $\lambda$ удобнее использовать $\tau$ , поскольку $\tau$ будет иметь размерность времени и неформально может определяться как характерный интервал времени, в течение которого собирается история событий.

Будем по определению считать, что каждому типу события соответствует величина $inline$ , имеющая физический смысл «количества вещества» и зависящая от времени, которая при наступлении события скачком увеличивается на единицу, а в остальное время уменьшается по приведенному выше экспоненциальному закону.

На рис. 1 показано, как меняется со временем значение $inline$ для равномерных потоков с разной интенсивностью и для неравномерного потока.

Рисунок 1: Значение $inline$ для разных потоков

Величина $inline$ не хранится явно в памяти, но может быть вычислена в любой момент. Хранится же значение $inline$ , такое что в момент времени $t_{now}$ величина $inline$ выражается следующим образом:

$v=\alpha^{s-t_{now}}.$

Данное представление соответствует модели распада.

Вычисление счетчика в модели распада эквивалентно вычислению экспоненциального
скользящего среднего с точностью до нормирующего множителя (константы). Важной особенностью данного представления является то, что единственное значение, хранимое в счетчике, заменяет собой пару (время последнего события, накопленная величина), которую хранят при традиционном подходе.

Обновление счетчика

Нетривиальной операцией является обновление значения счетчика $inline$ при наступлении очередного события. В этом случае требуется заменить $inline$ на новое значение $inline$ , которое определяется из следующего равенства:

$\alpha^{s'-t_{now}} = \alpha^{s-t_{now}} + 1.$

Здесь слева стоит значение $inline$ сразу после наступления события, а справа — значение $inline$ непосредственно до события, увеличенное на вклад события (равный единице). Ниже будут предложены эффективные способы вычисления результата обновления.

В терминах функции $inline$ из определения операция обновления выражается так:

$update_1(s, event_k) = t_k + \log_\alpha(1 + \alpha^{s-t_k}).$

Здесь время исполнения операции $t_{now}$ совпадает со временем $inline$ прихода сообщения.

Определение интенсивности

Пусть имеется равномерный поток событий интенсивности $inline$ , то есть события наступают с периодом $inline$ . Равномерный поток задается согласно определению.

Если измерение производится сразу после наступления очередного события, то есть $t_{now}=t_n$ для некоторого $inline$ , то накопленное в течение длительного времени значение счетчика $inline$ будет выражаться следующим рядом:

$\alpha^{s-t_{now}} = \sum_{k=-\infty}^n\alpha^{t_k-t_{now}}=\sum_{k=0}^\infty \alpha^{-kp},$

откуда

$\alpha^{-\Delta s} + \alpha^{-p} = 1,$

где $\Delta s = s-t_{now}$ — относительное значение счетчика.

В более общем случае момент измерения может оказаться между событиями:
$t_{now}=t_n+\psi$ , $\psi\in[0,p)$ . В этом случае значение счетчика будет отличаться в меньшую сторону на величину $\psi$ :

$\alpha^{-(\Delta s+\psi)} + \alpha^{-p} = 1.$

Задача измерения интенсивности заключается в том, чтобы по значению счетчика оценить интенсивность. В предположении, что поток равномерный, можно получить оценки истинной интенсивности равномерного потока сверху и снизу, подставляя в предыдущее уравнение крайние значения $\psi=0$ и $\psi=p$ :

$r^-\le r < r^+,$

где

$\begin{align}r^+&=r^+(\Delta s)=\frac1{\log_\alpha(1+\alpha^{-\Delta s})}\\r^-&=r^-(\Delta s)= \left\{\begin{array}{ll}\frac1{-\log_\alpha(1-\alpha^{-\Delta s})}&\mbox{при }\Delta s>0\\ 0&\mbox{иначе}\end{array}\right.\end{align}$

Обе оценки $inline$ и $inline$ монотонно зависят от значения счетчика $inline$ (см. рис. 2), поэтому, например, сравнение текущего значения счетчика с пороговым значением не требует дополнительных вычислений.

Рисунок 2: График функций $inline$ и $inline$ для $\tau=15$

В модели распада интенсивность произвольных (не обязательно равномерных) потоков по определению задается приведёнными выше оценками $inline$ и $inline$ . Причем, если измерение происходит сразу после обработки события, то интенсивность считается в точности равной нижней оценке.

Границы применимости модели распада

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

Во-первых, если время наступления событий измеряется как дискретная величина, то период потока не может быть меньшим единицы. То есть интенсивность потока не должна превышать $r_{max}=1$ . Отсюда следует ограничение на относительное значение счетчика $\Delta s = s-t_{now}$ — оно не должно превышать значения $\sigma_{max}$ , которое определяется из формулы:

$r^-(\sigma_{max}) = r_{max}.$

Величина $\sigma_{max}$ оценивается следующим образом:

$\sigma_{max}=\tau\ln\tau+\omega(\tau),$

где $0\le\omega(\tau)\le1/2$ .

Во-вторых, оценка интенсивности слабых (малоинтенсивных) потоков затруднена: при малых относительных значениях счетчика $\Delta s$ точность верхней и нижней оценки $inline$ и $inline$ ухудшается, а при отрицательных значениях $\Delta s$ нижняя оценка интенсивности вырождается в нуль.

Также есть ограничение на время работы реализаций модели распада, связанное с переполнением счетчиков. Поскольку значение счетчика не может убежать от $t_{now}$ более, чем на $\sigma_{max}$ , время работы системы фактически определяется разрядностью счетчика и длительностью одного такта. Если для хранения счетчика используется 64-разрядный регистр, то он не переполнится в течение 100 лет. Но в реализациях с малоразрядными регистрами должен быть предусмотрен механизм сброса счетчиков.

Алгоритмы учета множества потоков

Особенности модели распада

Особенностью использования EMA в качестве значения счетчика является то, что при прекращении потока событий накопленное значение быстро (экспоненциально по времени) деградирует и становится неотличимым от нуля. В модели распада этот факт используется для автоматического сброса счетчика: хотя значение счетчика $inline$ будет всё время возрастать с приходом событий, через некоторое время после прекращения потока событий величину $v=\alpha^{s-t_{now}}$ можно будет считать равной нулю, не меняя явно значения счетчика. Время $T_{vanish}$ , за которое любое накопленное ранее значение распадается до условного нуля, зависит от параметра $\tau$ и требуемой точности. Оно выражается как $T_{vanish}=T_{min}+\sigma_{max}$ , где $T_{min}$ — время распада значения, накопленного в результате единичного события. В разделе «Табличная реализация» дано точное выражение $T_{min}$ , но здесь достаточно иметь в виду следующий факт: $T_{vanish} = O(\tau\ln\tau)$ при фиксированной точности.

Отсюда следует оценка сверху на размер хранилища счетчиков при учете множества потоков для случая, когда информация вообще не будет теряться — достаточно иметь $T_{vanish}\cdot r_{max}$ ячеек. Есть множество применений задачи поиска тяжелых элементов, где не требуется больших значений $\tau$ , и всё хранилище помещается оперативную память или даже в кэш процессора L3 или L2. В этом случае обеспечивается малое время доступа к хранилищу, так что задача становится выполнимой при высоких значениях интенсивности входного потока.

Для реализации хранилища годится хэш-таблица, где ключом является тип события. При этом пустыми считаются ячейки, у которых значение счетчика $inline$ удовлетворяет условию $s-t_{now} \le T_{min}$ .

Численная реализация Decay-based count

Операция обновления значения

Введем следующее обозначение:

$\rho_\tau(x) = \tau\ln(1+e^{x/\tau}) = \log_{\alpha}(1+\alpha^x).$

Тогда операция обновления выражается следующим образом:

$s' = t_{now} + \rho_\tau(s-t_{now}).$

Таким образом, задача сводится к эффективному вычислению приближения функции $\rho_\tau$ . Время удобно представлять целым числом, например, измерять его в тактах процессора, так что требуется построить целочисленное отображение ${R:\mathbb{Z}\to\mathbb{Z}}$ , такое, что:

$R_\tau(T) \approx \rho_\tau(T)\quad\mbox{для }T\in\mathbb{Z}.$

Для данной задачи точность важна не относительная, а абсолютная, поскольку со значениями времени используются в основном аддитивные операции. Очевидно, что из-за целочисленности представления времени погрешность меньше 0.5 такта недостижима.
Кроме того, операция измерения текущего времени, как правило, дает некоторую погрешность. Например, если есть способ измерения времени с точностью в 10 тактов, то достаточно потребовать, чтобы $R_\tau$ давало приближение примерно такой же точности: $\left|R_\tau(T) - \rho_\tau(T)\right| \le 10.$

Можно предложить несколько разных способов вычисления $R_\tau$ разной сложности и степени эффективности.

Вычисление $R_\tau$ : FPU

Проще всего использовать арифметику с плавающей точкой и непосредственно вычислять $\rho_\tau$ по определению. Время выполнения этой операции составляет около 100 тактов процессора, что довольно много по сравнению предлагаемым ниже методом.

Вычисление $R_\tau$ : табличная реализация

Идея табличной реализации состоит в том, чтобы сохранить предвычисленные значения функции в таблице.

Во-первых, используя тождество

$\rho_\tau(-x) = -x + \rho_\tau(x),$

достаточно строить $R_\tau(T)$ только для $T\le0$ .

Во-вторых, поскольку

$\rho_\tau(x)\to 0 \mbox{ при } x\to-\infty,$

существует $T_{min}>0$ , такое что $R_\tau(T)=0$ при $T\le-T_{min}$ . Где $T_{min}$ можно найти из следующих соображений:

$T_{min}=\lceil t_{min}\rceil,\quad \rho_\tau(t_{min})=1/2,$

откуда
$T_{min}=\lceil-\log_\alpha(\alpha^{1/2}-1)\rceil=\lceil-\tau\ln(e^{1/{2\tau}}-1)\rceil.$

Таким образом, достаточно определить $R_\tau(T)$ для ${T_{min}<T\le0}$ .

График функции $\rho_\tau(x)$ представлен на рис. 3. Особенность этой функции такова, что с изменением параметра $\tau$ будет происходить одинаковое масштабирование по обеим осям.

Рисунок 3: График функции $\rho_\tau(x)$

Очевидная реализация $R_\tau$ состоит в построении таблицы из $T_{min}$ ячеек, где будут храниться предвычисленные значения. Поскольку все значения функции на данном интервале находятся в промежутке между 0 и $\rho_\tau(0)=\tau\ln2$ , итоговый размер таблицы составляет $T_{min}\log_2(\tau\ln2)$ бит.

Алгоритм обновления значения выглядит следующим образом:

$\begin{align} t_{now}& \leftarrow getTime()\\ \delta & \leftarrow \min\{|s-t_{now}|, T_{min}\}\\ \delta' &\leftarrow R(-\delta)\\ s' &\leftarrow \delta' + \max\{s, t_{now}\} \end{align}$

Абсолютная точность этого метода составляет 1/2, поскольку он дает наилучшее целочисленное приближение вещественнозначной функции.

Результаты измерения эффективности

Сравнивались между собой следующие три реализации экспоненциального скользящего среднего:
1. наивная реализация EMA;
2. модель распада через FPU (то есть с вызовом функций exp() и log() математической библиотеки);
3. модель распада табличным методом.

Исходный код теста на си: pastebin.com/N1Xg9dud.

Время выполнения одного вызова функции update() при $\tau=100000$ (в этом случае таблица для вычисления $R_\tau$ помещается в кэш L1) в реализациях 1, 2 и 3 составляет 100, 125, 11 тактов процессора, соответственно.

Использование экспоненциального скользящего среднего — удобный способ подсчёта событий и оценки интенсивности. Однако данная операция вычислительно затратна, что сильно ограничивает возможности её применения. Наша реализация алгоритма на основе модели распада, во-первых, красива, а во-вторых, более эффективна, нежели наивная реализация вычисления ЕМА. Эффективность обеспечивается за счет двух факторов: табличное вычисление трансцендентной функции и более экономное по памяти представление счетчика.

Благодарности

Данная публикация подготовлена нами в пробном режиме в рамках проекта по освещению механизмов работы сети фильтрации Qrator. Спасибо Антону Орлову, Артему Гавриченкову, Евгению Наградову и Никите nikitadanilov Данилову за обсуждения и идеи.

Tags:

Hubs:

Измерение интенсивности входящего потока событий в модели распада

Введение