Как стать автором
Обновить

Комментарии 12

Я вот так и не понял где это может пригодиться и почему вам не хватает 64бит счетчиков?
Предположим считаем события появляющиеся со скоростью 3ГГц в течении 100 лет => log2(3e9*100*365*24*60*60)=63.04 бита
И потом что мешает оценить допустимые значения счетчика и выделить нужное количество бит с запасом? И фалг переполнения добавить если уж совсем педантичным быть.
Дело в том, что различных типов событий, которые мы хотим считать, очень много. И под каждый тип нужен свой счётчик. Поэтому в итоге с помощью подобных хитростей можно добиться существенной экономии памяти.

Пример: хотим посчитать количество пакетов, приходящих от каждого ipv4-адреса. Если использовать 64-битные счётчики, то потребуется 2^32 * 8 = 32 GiB. Если же 8-битные счётчики Морриса, то всего 4 GiB, а столько уже можно выделить на любом сервере и даже в маршрутизаторе.

Ещё пример: хотим сделать то же самое с ipv6. Там уже 2^128 адресов, и под каждый из них счётчик не завести. Но можно, например, использовать какой-нибудь sketch-based подход типа en.wikipedia.org/wiki/Count%E2%80%93min_sketch (разбиваем все адреса на подмножества, на каждое по счётчику). Ясно, что будет какая-то ошибка, но довольно очевидно, что чем больше счётчиков (мельче подмножества), тем она меньше.
Там уже 2^128 адресов, и под каждый из них счётчик не завести
А под каждый и не надо, в реальности же их гораздо меньше, для 2^128 вам даже однобитовые счетчики не помогут, во всей галактике столько памяти нет ). Более того, не обязательно выделять сразу 4(5,6,7...) байт на каждый счетчик. Если там 0 или редко возникающие события, то на какое-то время хватит 1 байта, дальше расширяем (если старший бит 1). Потребуется конечно некоторая «дефрагментация» такой структуры в процессе работы, но зато не надо будет вероятность каждый раз считать.
для 2^128 вам даже однобитовые счетчики не помогут, во всей галактике столько памяти нет

Ещё раз суть примера: да, адресов очень много, и нет возможности под каждый выделить память. Поэтому приходится прибегать к помощь алгоритмов, лишь оценивающих точные значения. Например, алгоритмы, дробящие все адреса на подмножества (скетчи), или алгоритмы, хранящие счётчики лишь для «интенсивных» адресов (e.g. en.wikipedia.org/wiki/Misra%E2%80%93Gries_summary). Но факт остаётся фактом: чем больше счётчиков мы сможем cодержать единовременно, тем точнее будут наши оценки (намеренно забываю про точность самих счётчиков — естественно есть некий trade-off).
дальше расширяем

Если я правильно понимаю, Вы предлагаете динамически выделять память под каждый счётчик. Мне совершенно непонятно, как такое организовать, тем более эффективно. Было бы интересно понять идею. Вот допустим у нас есть большой выделенный кусок памяти «под счётчики». Как Вы предлагаете им распорядиться? По описанию я представил такую картинку: первый бит под один адрес, следующие 3 под другой и т.д… А что делать, если битность счётчика посередине нужно увеличить? Как двигать хвос? И под длины счётчиков тоже, наверное, нужно память выделить.
зато не надо будет вероятность каждый раз считать

Звучит так, как будто Вы хотите явно считать 2^{-k} (и работать с даблами). Нет же! Мы считаем 2^k (битовый сдвиг) и смотрим на rand()%(2^k). Работает довольно быстро.
Да суть примера понятна, выше головы не прыгнешь, что-то придется или урезать или выделять по необходимости.
Есть какое-то интуитивное ощущение, что и со счетчиками так же, нельзя сжать информацию выше определенного предела, с допустимыми потерями или без таковых. А уж способ сжатия, тут возможны варианты, вероятностный счетчик, какие-то таблицы со счетчиками разной размерности для каналов с разной частотой инкремента, динамическое выделение памяти под счетчики, компрессия в rar массива памяти со счетчиками etc.

от rand() и % тоже несложно избавиться ;)

Хм. Странное желание учитывать все ip4 адреса, но не точно. Что мешает учитывать не все но простым счетчиком?
Например сбалансированное бинарное дерево ipv4 адресов 64битными счетчиками в 4Gb сможет однозначно вместить на 214M уникальных адресов. (134M если ipv6)

Задачи всё-таки немного разные, но главное что "пакеты" считать им нужно на нагруженных 10G интерфейсаx.
Соответственно, дерево не подходит, ибо уловные переходы при поиске и перебалансировка.

Да для 10G бинарное дерево не пойдёт.
Но можно сделать таблицу на 2^26 по 7 u64 счетчики и по 7 6bit остатка ip адреса.
То можно хранить 7*2^26 = 469M ipv4 адресов с 64бит счетчиками и займёт это 3.9Gb
Вместо ip можно использовать ip*c1 что бы раскидать адреса (где c1 mod 8 = 5 или 3).

Хотя соглашусь, в данной ситуации (все ipv4 в 4Gb) счетчики Мориса проще, быстрее и больше входит, но с потерей точности. Но если железо 10G и хочется все ipv4 то 32Gb не такая уж и великая проблема.

Как именно у "куратора" не знаю, но на всякий для полноты картины:


В подобных случаях/задачах важно экономить memory bandwidth.
Например, если вы читаете/пишете одну кэш-линию для одного счетчика-на-пакет, то примерно успеваете, а если две то уже никак.
Поэтому, какие-либо варианты хеш-таблиц часто не подходят.


С другой стороны, "моррисоны", "скетчи" и т.п. можно реализовать через примитивную арифметику и табличные функции. А сами счетчики держать в не-кэшируемой памяти, заранее посчитав достаточность полосы для худшего случая.
Короче, в результате можно посчитать/доказать, что ваш софт полностью обработает корректно весь/любой трафик через входящие N×10G (но отдельная тема чтобы эти N×10G рационально приземлить на другие numa-ноды и т.д.).

Спасибо за Ваш интерес к статье!
Да, Вы правы. Экономия памяти — критически важная задача в нашем случае. Делать это можно по-разному. Мы экспериментируем с различными алгоритмами и счётчиками, в них использующимися. Счётчики Морриса — это одно из направлений, и, на мой взгляд, мы получили довольно интересные результаты (например, уменьшение ошибки при введении мантиссы), которыми хотелось поделиться.
Строго говоря, экономить нужно не пропускную способность памяти (ее как раз хватает с запасом), а задержку на доступ к памяти. Действительно, всего два промаха в кэш в среднем — и мы проиграли по задержке, уже не получится обрабатывать поток на line rate. И да, мы пробуем разные типы счетчиков и разные подходы к их организации, но рассматриваем только то, что «можно реализовать через примитивную арифметику и табличные функции», причем эти таблицы должны быть реально маленькими — с запасом помещаться в кэш.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий