Спасибо за Ваш интерес к статье!
Да, Вы правы. Экономия памяти — критически важная задача в нашем случае. Делать это можно по-разному. Мы экспериментируем с различными алгоритмами и счётчиками, в них использующимися. Счётчики Морриса — это одно из направлений, и, на мой взгляд, мы получили довольно интересные результаты (например, уменьшение ошибки при введении мантиссы), которыми хотелось поделиться.
для 2^128 вам даже однобитовые счетчики не помогут, во всей галактике столько памяти нет
Ещё раз суть примера: да, адресов очень много, и нет возможности под каждый выделить память. Поэтому приходится прибегать к помощь алгоритмов, лишь оценивающих точные значения. Например, алгоритмы, дробящие все адреса на подмножества (скетчи), или алгоритмы, хранящие счётчики лишь для «интенсивных» адресов (e.g. en.wikipedia.org/wiki/Misra%E2%80%93Gries_summary). Но факт остаётся фактом: чем больше счётчиков мы сможем cодержать единовременно, тем точнее будут наши оценки (намеренно забываю про точность самих счётчиков — естественно есть некий trade-off).
дальше расширяем
Если я правильно понимаю, Вы предлагаете динамически выделять память под каждый счётчик. Мне совершенно непонятно, как такое организовать, тем более эффективно. Было бы интересно понять идею. Вот допустим у нас есть большой выделенный кусок памяти «под счётчики». Как Вы предлагаете им распорядиться? По описанию я представил такую картинку: первый бит под один адрес, следующие 3 под другой и т.д… А что делать, если битность счётчика посередине нужно увеличить? Как двигать хвос? И под длины счётчиков тоже, наверное, нужно память выделить.
зато не надо будет вероятность каждый раз считать
Звучит так, как будто Вы хотите явно считать 2^{-k} (и работать с даблами). Нет же! Мы считаем 2^k (битовый сдвиг) и смотрим на rand()%(2^k). Работает довольно быстро.
Дело в том, что различных типов событий, которые мы хотим считать, очень много. И под каждый тип нужен свой счётчик. Поэтому в итоге с помощью подобных хитростей можно добиться существенной экономии памяти.
Пример: хотим посчитать количество пакетов, приходящих от каждого ipv4-адреса. Если использовать 64-битные счётчики, то потребуется 2^32 * 8 = 32 GiB. Если же 8-битные счётчики Морриса, то всего 4 GiB, а столько уже можно выделить на любом сервере и даже в маршрутизаторе.
Ещё пример: хотим сделать то же самое с ipv6. Там уже 2^128 адресов, и под каждый из них счётчик не завести. Но можно, например, использовать какой-нибудь sketch-based подход типа en.wikipedia.org/wiki/Count%E2%80%93min_sketch (разбиваем все адреса на подмножества, на каждое по счётчику). Ясно, что будет какая-то ошибка, но довольно очевидно, что чем больше счётчиков (мельче подмножества), тем она меньше.
Да, Вы правы. Экономия памяти — критически важная задача в нашем случае. Делать это можно по-разному. Мы экспериментируем с различными алгоритмами и счётчиками, в них использующимися. Счётчики Морриса — это одно из направлений, и, на мой взгляд, мы получили довольно интересные результаты (например, уменьшение ошибки при введении мантиссы), которыми хотелось поделиться.
Ещё раз суть примера: да, адресов очень много, и нет возможности под каждый выделить память. Поэтому приходится прибегать к помощь алгоритмов, лишь оценивающих точные значения. Например, алгоритмы, дробящие все адреса на подмножества (скетчи), или алгоритмы, хранящие счётчики лишь для «интенсивных» адресов (e.g. en.wikipedia.org/wiki/Misra%E2%80%93Gries_summary). Но факт остаётся фактом: чем больше счётчиков мы сможем cодержать единовременно, тем точнее будут наши оценки (намеренно забываю про точность самих счётчиков — естественно есть некий trade-off).
Если я правильно понимаю, Вы предлагаете динамически выделять память под каждый счётчик. Мне совершенно непонятно, как такое организовать, тем более эффективно. Было бы интересно понять идею. Вот допустим у нас есть большой выделенный кусок памяти «под счётчики». Как Вы предлагаете им распорядиться? По описанию я представил такую картинку: первый бит под один адрес, следующие 3 под другой и т.д… А что делать, если битность счётчика посередине нужно увеличить? Как двигать хвос? И под длины счётчиков тоже, наверное, нужно память выделить.
Звучит так, как будто Вы хотите явно считать 2^{-k} (и работать с даблами). Нет же! Мы считаем 2^k (битовый сдвиг) и смотрим на rand()%(2^k). Работает довольно быстро.
Пример: хотим посчитать количество пакетов, приходящих от каждого ipv4-адреса. Если использовать 64-битные счётчики, то потребуется 2^32 * 8 = 32 GiB. Если же 8-битные счётчики Морриса, то всего 4 GiB, а столько уже можно выделить на любом сервере и даже в маршрутизаторе.
Ещё пример: хотим сделать то же самое с ipv6. Там уже 2^128 адресов, и под каждый из них счётчик не завести. Но можно, например, использовать какой-нибудь sketch-based подход типа en.wikipedia.org/wiki/Count%E2%80%93min_sketch (разбиваем все адреса на подмножества, на каждое по счётчику). Ясно, что будет какая-то ошибка, но довольно очевидно, что чем больше счётчиков (мельче подмножества), тем она меньше.