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

Введение


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

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

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

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

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

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


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


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

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

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

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


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

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


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

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


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

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


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

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


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

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

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


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

  • Packet sampling
  • Space saving algorithm
  • HashParallel
  • HashPipe
  • Count-min sketch

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


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

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

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

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

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


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

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

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

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

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


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

  • Простой подсчет количества событий: $update_1(s, event_k)=s+1$;
  • Подсчет количества событий с учетом веса: $update_c(s, event_k)=s+c_k$;
  • Вычисление экспоненциального скользящее среднего (EMA) с параметром $\beta$. Здесь счетчик $s=(v,t)$ хранит две величины: собственно значение 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$, и требуется учитывать отдельно потоки сообщений каждого типа. Тогда событие описывается как $event_k = (t_k, i_k)$ (или, с учетом веса события, $event_k = (t_k, i_k, c_k)$), где $i_k$ — тип события. Множество индексов $k$, относящихся к данному типу события $i$ обозначим $I_i = \{k\mid i_k = i\}$.

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


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

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


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

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

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


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

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

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



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

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

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


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

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

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


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

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


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

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

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


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

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


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

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

$\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}$


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



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

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

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


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

Во-первых, если время наступления событий измеряется как дискретная величина, то период потока не может быть меньшим единицы. То есть интенсивность потока не должна превышать $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$ точность верхней и нижней оценки $r^+$ и $r^-$ ухудшается, а при отрицательных значениях $\Delta s$ нижняя оценка интенсивности вырождается в нуль.

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

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


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


Особенностью использования EMA в качестве значения счетчика является то, что при прекращении потока событий накопленное значение быстро (экспоненциально по времени) деградирует и становится неотличимым от нуля. В модели распада этот факт используется для автоматического сброса счетчика: хотя значение счетчика $s$ будет всё время возрастать с приходом событий, через некоторое время после прекращения потока событий величину $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. В этом случае обеспечивается малое время доступа к хранилищу, так что задача становится выполнимой при высоких значениях интенсивности входного потока.

Для реализации хранилища годится хэш-таблица, где ключом является тип события. При этом пустыми считаются ячейки, у которых значение счетчика $s$ удовлетворяет условию $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 Данилову за обсуждения и идеи.
Поделиться с друзьями
-->

Комментарии (3)


  1. pavelodintsov
    01.08.2017 22:03
    #10338958
    +2

    Спасибо за отличную статью и за хорошую лицензию на код примеров :) Утянул к себе на GitHub, чтобы не потерялось и чтобы можно было удобно форкать.

    Очень ждем продолжения статьи для обобщения метода на случай неравномерного потока событий!


    1. janatem
      01.08.2017 23:39
      #10339080
      +2

      О, я открыл для себя gist.


  1. openbsod
    02.08.2017 00:47
    #10339128
    +1

    Спасибо. Интересная, отличная статья.