Комментарии 12
Предположим считаем события появляющиеся со скоростью 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). Работает довольно быстро.
Есть какое-то интуитивное ощущение, что и со счетчиками так же, нельзя сжать информацию выше определенного предела, с допустимыми потерями или без таковых. А уж способ сжатия, тут возможны варианты, вероятностный счетчик, какие-то таблицы со счетчиками разной размерности для каналов с разной частотой инкремента, динамическое выделение памяти под счетчики,
от rand()
и %
тоже несложно избавиться ;)
Например сбалансированное бинарное дерево ipv4 адресов 64битными счетчиками в 4Gb сможет однозначно вместить на 214M уникальных адресов. (134M если ipv6)
Задачи всё-таки немного разные, но главное что "пакеты" считать им нужно на нагруженных 10G интерфейсаx.
Соответственно, дерево не подходит, ибо уловные переходы при поиске и перебалансировка.
Но можно сделать таблицу на 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-ноды и т.д.).
Да, Вы правы. Экономия памяти — критически важная задача в нашем случае. Делать это можно по-разному. Мы экспериментируем с различными алгоритмами и счётчиками, в них использующимися. Счётчики Морриса — это одно из направлений, и, на мой взгляд, мы получили довольно интересные результаты (например, уменьшение ошибки при введении мантиссы), которыми хотелось поделиться.
Обзор счётчиков Морриса