Мы рады представить вашему вниманию заметку, написанную инженером Qrator Labs Дмитрием @dimak24Камальдиновым. Если вы хотите быть частью нашей команды Core и заниматься подобными задачами - пишите нам наhr@qrator.net.
1 Введение
При реализации потоковых алгоритмов часто возникает задача подсчёта каких-то событий: приход пакета, установка соединения; при этом доступная память может стать узким местом: обычный -битный счётчик позволяет учесть не более событий. Одним из способов обработки большего диапазона значений, используя то же количество памяти, является вероятностный подсчёт. В этой статье будет предложен обзор известного алгоритма Морриса, а также некоторых его обобщений.
Другой способ уменьшить количество бит, необходимое для хранения значения счётчика, использование распада. Об этом подходе мы рассказываемздесь, а также собираемся в ближайшее время опубликовать ещё одну заметку по теме.
Мы начнём с разбора простейшего алгоритма вероятностного подсчёта, выделим его недостатки (раздел 2). Затем (раздел 3) опишем алгоритм, впервые преложенный Робертом Моррисом в 1978 году, укажем его важнейшие свойства и приемущества. Для большинства нетривиальных формул и утверждений в тексте присутствуют наши доказательства интересующийся читатель сможет найти их под спойлером. В трёх последующих разделах мы изложим полезные расширения классического алгоритма: вы узнаете, что общего у счётчиков Морриса и экспоненциального распада, как можно уменьшить ошибку, пожертвовав максимальным значением, и как эффективно обрабатывать взвешенные события.
2 Вероятностный подсчёт, проблемы тривиального подхода
Основная идея вероятностного подсчёта учёт очередного события с некоторой вероятностью. Рассмотрим сначала пример с постоянной вероятностью обновления:
Где черезобозначено значение счётчика после-ой попытки обновления. Несложно понять, чтозадаёт количество успехов среди независимых испытаний Бернулли. Иначе говоря,имеетбиномиальное распределение:
В качестве оценки числа событий естественно использовать . Ясно, что такая оценка несмещённая: .
Описанный подход имеет несколько недостатков: во-первых, он позволяет учесть лишь в раз больше событий по сравнению с простым инкрементальным счётчиком, чем заметно уступает счётчикам Морриса, как мы увидим далее. Во-вторых, относительная ошибка оценки велика при маленьких . Например, при она вообще равна 100%. Оценить относительную ошибку можно с помощью коэффициента вариации:
3 Счётчики Морриса
Счётчик Морриса обновляется с вероятностью, зависящей от текущего значения: первое обновление происходит с вероятностью 1, следующее с вероятностью 1/2, потом 1/4 и т.д.:
Как по значению счётчика оценить, сколько было событий? Обновление счётчика с на происходит в среднем за итераций, отсюда оценка числа событий:
Важнейшими свойствами этой оценки являются
-
её несмещённость, то есть значение оценки после вероятностных обновлений в среднем равно ,
В самом начале значение счётчика равно 0: , тогда , а значит . Итого .
-
а также независимость её относительной ошибки от .
Сначала посчитаем дисперсию . Согласно известной формуле, . Мы уже знаем, что . Осталось получить . Заметим, что
Таким образом, остаётся узнать, чему равно .
Итого
Таким образом, относительная ошибка оценки числа событий при использовании счётчика Морриса ограничена, примерно постоянна и почти не зависит от .
Оценить вероятность больших отклонений от среднего можно с помощью неравенства Чебышёва:
-
отметим здесь также, что покрываемый диапазон количества событий при использовании бит памяти будет . Иначе говоря, для учёта событий достаточно бит памяти!
4 Взвешенные обновления
Счётчики Морриса можно использовать для подсчёта взвешенных событий: например, для суммирования размеров приходящих пакетов. Простейший способ обновление счётчика <вес события> раз приводит к линейной по весу сложности обновления.
Заметим, что в каждый момент времени мы знаем, как распределено количество неудач до ближайшего изменения счётчика, этогеометрическое рапределение:
Учитывая этот факт, мы можем ускорить алгоритм, сразу пропуская все подряд идущие неудачные попытки обновления:
5 Распад
Часто возникает потребность учитывать самые новые события с большим весом. Например, при поиске интенсивных ключей в потоке интереснее понять, какой ключ интенсивен прямо сейчас, а не имеет высокую среднюю интенсивность за счёт своего бурного прошлого. Встатьемы рассказывали о распадных счётчиках, спроектированных специально для решения этой задачи. Другой предпосылкой для некоего распада является то, что несмотря на суперэкономное использование памяти, когда-то и счётчик Морриса переполнится. Оказывается, счётчики Морриса тоже могут распадаться, причём очень похожим на EMA способом, но гораздо эффективнее.
Идея очень проста: будем периодически вычитать из счётчика. Напомним, что значение оценивает количество событий как . Соответственно, после вычитания оценка станет . Иначе говоря, вычитание уменьшает оценку в раза! Мы можем добиться распада ровно в раза, обновив с вероятностью счётчик сразу после вычитания :
6 Мантисса и экспонента
Рассмотрим следующее обобщение счётчика Морриса: вероятность обновления уменьшается враза не на каждое успешное обновление, а на каждые. Возможной реализацией такого подхода будет разделение битов счётчика на две части:экспоненту, отвечающую за вероятность, имантиссу, считающую количество успешных обновлений при текущей вероятности (чем-то похоже на представлениечисел с плавающей точкой).
Рис. 2: разбиение битов счётчика на мантиссу (M=5 бит) и экспоненту (E=3 бит)Введём обозначения для мантиссы и экспоненты:
Теперь правило обновления и оценка числа событий записывается так:
Например, на рисунке 2 значение счётчика , мантисса и экспонента равны и соответственно. А значит число событий оценивается как .
При таком разбиении биты экспоненты будут отвечать за покрываемый диапазон количества событий, а биты мантиссы за точность оценки (далее мы поясним подробнее, что это значит). Наилучшее распределение битов счётчика зависит от задачи; мы предлагаем отдавать как можно больше мантиссе, но чтобы экспоненциальных битов хватало для покрытия интересующего диапазона значений.
Описанный вариант счётчиков Морриса обладает следующими свойствами:
-
покрываемый диапазон значений равен
Покрываемый диапазон получить несложно, подставив в формулу для максимальные возможные значения и :
-
новая оценка также несмещённая: ;
Аналогично доказательству утверждения для обычных счётчиков Морриса посчитаем условное мат.~ожидание . Причём сделаем это отдельно для (вероятность обновления изменится в случае успеха) и .
В обоих случаях
-
коэффициент вариации (и относительная ошибка) становятся ещё меньше! Мы не знаем его точное значение, но имеется такая оценка (сравните её с аналогичной для классического счётчика Морриса):
Алгоритмы взвешенных обновлений и распада тоже немного изменятся.
Аналогично подходу, описанному в разделе 4, чтобы эффективно выполнить взвешенное обновление, нужно понять, через сколько попыток обновления вероятность изменится. При отсутствии мантиссы вероятность меняется после каждого успешного обновления, теперь же после каждых. А значит нам нужно распределение количества испытаний Бернулли (искомое число событий), среди которых ровноуспешных. Такое распределение называетсяотрицательным биномиальным.
Замечание.Существует несколько определений отрицательного биномиального распределения. Будем придерживаться написанного в русскоязычной википедии, где сказано, что это распределение задаёт не общее число событий, а число неудач. Тогда чтобы получить число событий, нужно к случайной величине добавить количество успехов:
Чтобы не генерировать отрицательное биномиальное распределение, можно загрубить алгоритм, всегда выбирая среднее этого распределения:
Чтобы выполнить распад, будем вычитать из экспоненциальной части (иначе говоря, из значения счётчика). Тогда
Заметим, что при (а именно этот случай изучается в этом разделе) . Поэтому исправить оценку можно, вероятностно увеличив счётчик на :
7 Заключение
Счётчики Морриса это очень круто! Пользуйтесь!
Последний раздел не содержит полезных на практике результатов, но...
8 Обобщённые вероятностные счётчики
В общем виде правило обновления счётчика определяется функцией вероятности :
В случае счётчиков Морриса . При изучении вероятностных счётчиков мы попробовали взять линейную функцию вероятности: ( некоторая константа, максимальное значение счётчика). Это привело к некоторым интересным результатам, которые будут кратко изложены в этом разделе.
Прежде чем представить эти результаты, напомним о двух математических сущностях. Полный однородный симметрический многочленстепениотпеременных это сумма всех возможных одночленов степениот этих переменных с коэффициентами:
Другая конструкция, которая нам понадобится, число Стирлинга второго рода. Один из способов определить это число комбинаторный: число Стирлинга второго рода количество разбиений -элементного множества на непустых подмножеств. Числа Стирлинга связаны с полными симметрическим многочленами:
С помощью можно записать в общем виде вероятность того, что после попыток обновления значение счётчика равно :
Эту формулу легко доказать по индукции, но также она несложно следует из простых комбинаторных рассуждений: фактически в ней записано, что для того, чтобы получить значение , нужны успешных обновлений: с до , с до и т.д., за это отвечает множитель , и неудачных, которые разбиваются на групп: неудачных обновлений с до , с до и т.д., что выражено .
Наконец, при использовании линейной функции вероятности вероятность принимает вид
Это и есть анонсированный выше интересный результат. Мы заметили число Стирлинга в значении вероятности достаточно случайно и до сих пор не знаем, можно ли обосновать его присутствие комбинаторынми рассуждениями (опираясь, на его комбинаторное определение). Другой вопрос можно красиво записать аналогичную вероятность для счётчиков Морриса.
Математическое ожидание и дисперсия(доказательства опускаем, но их несложно получить, используя формулу дляи свойства чисел Стирлинга).
Оценить число событий можно по методу моментов:
или аналогично счётчикам Морриса, учитывая, что :
Список литературы
[1] Morris, R.Counting large numbers of events in small registersCommunications of the ACM, 1978 21(10), 840-842.
[2]http://gregorygundersen.com/blog/2019/11/11/morris-algorithm/хороший обзор счётчиков Морриса на английском языке
[3]http://personeltest.ru/aways/habr.com/ru/company/qrator/blog/334354/ наша статья про EMA-счётчики
[4]http://personeltest.ru/aways/habr.com/ru/post/208268/ сторонний материал про счётчики Морриса