Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 15
Очень круто написано. все сжато и поделу, читать было очень интересно. Про память неожиданность конечно
Секундочку… Мы говорим про ipv4? Их всего-то около 2 миллиардов. Если использовать номер дата-центра (u16) как значение, а ip-адрес как индекс (т.е. буквальное преобразование ipv4->u32), то нам потребуется всего-то 4Гб для хранения таблицы IP->DC. Без всяких блумов. Даже если мы будем наивно использовать весь u32 (включая мультикаст адреса и т.д.), потребуется 8Гб.
Один и тот же IP может быть с разными номерами датацентра.
По идее конкретные адреса можно огрубить до /24, даже /28 уже уменьшает требования по памяти в 16 раз.
Вопрос в том что запарсить ip строку в число, может быть сильно затратнее чем просто хэш посчитать.
Если большинтсво сервис провайдеров самого низкого уровня до клиента будут настраивать файервол по разрешенным собственным source ip, то и проблема спуфинга должна быть минимальной, левый пакеты будут уже на первом хопе отсекаться. На сколько я понимаю основная задача чтобы миллионы IoT чайников не генерировали тысячи левых запросов. А не чтобы тысяча серверов генерировала миллионы запросов, этот случай сильно легче вычислить.
Вопрос в том что запарсить ip строку в число, может быть сильно затратнее чем просто хэш посчитать.
Если большинтсво сервис провайдеров самого низкого уровня до клиента будут настраивать файервол по разрешенным собственным source ip, то и проблема спуфинга должна быть минимальной, левый пакеты будут уже на первом хопе отсекаться. На сколько я понимаю основная задача чтобы миллионы IoT чайников не генерировали тысячи левых запросов. А не чтобы тысяча серверов генерировала миллионы запросов, этот случай сильно легче вычислить.
Я вам больше того скажу, даже 4 Гб не понадобиться.
Решал подобную задачу для 32-битных целых чисел. Там по факту требуется только возвести флаг – 1бит. Итого 0.5GB на вспомогательный массив. Основной же массив ограничен только оперативкой, ну или делать с подкачкой блоками из файла.
Работает быстро.
По самой статье было очень интересно. Особенно в части простоя при загрузке данных в кэш процессора, сам приходил к подобным выводам.
Решал подобную задачу для 32-битных целых чисел. Там по факту требуется только возвести флаг – 1бит. Итого 0.5GB на вспомогательный массив. Основной же массив ограничен только оперативкой, ну или делать с подкачкой блоками из файла.
Работает быстро.
Мой пример на Pascal
// Сортировка подсчётом с удалением повторов
procedure Sort_Counting_Unique(var m: array of longword);
const max = 256 * 256 * 256 * 8;
var
s: array of longword;
i, j, k: longword; // Переменные, играющие роль индексов
offset1, offset2: longword; // Смещения
begin
SetLength(s, max);
FillChar(s[0], max * SizeOf(Longword), 0); // Обнуление вспомогательного массива
for i := 0 to Length(m)-1 do // Заполняем массив подсчётов
begin
offset1 := m[i] shr 5; // Id ячейки в спомогательном массиве
offset2 := 1 shl (m[i] and 31); // Cмещение бита в ячейке
s[offset1] := s[offset1] or offset2; // Сохраняем ячейку с взведённым битом
end;
j := 0;
for i := 0 to max-1 do // Сохраняем отсортированный массив, повторы игнорируются
if s[i] <> 0 then // Пропускаем пустые ячейки для ускорения
for k := 0 to 31 do
if ((s[i] shr k) and 1) > 0 then
begin
m[j] := i * 32 + k;
Inc(j);
end;
FillChar(m[j], (Length(m)-j) * SizeOf(Longword), 0); // Зануляем оставщуюся часть массива очищенного от повторов
SetLength(s, 0);
end;
procedure Sort_Counting_Unique(var m: array of longword);
const max = 256 * 256 * 256 * 8;
var
s: array of longword;
i, j, k: longword; // Переменные, играющие роль индексов
offset1, offset2: longword; // Смещения
begin
SetLength(s, max);
FillChar(s[0], max * SizeOf(Longword), 0); // Обнуление вспомогательного массива
for i := 0 to Length(m)-1 do // Заполняем массив подсчётов
begin
offset1 := m[i] shr 5; // Id ячейки в спомогательном массиве
offset2 := 1 shl (m[i] and 31); // Cмещение бита в ячейке
s[offset1] := s[offset1] or offset2; // Сохраняем ячейку с взведённым битом
end;
j := 0;
for i := 0 to max-1 do // Сохраняем отсортированный массив, повторы игнорируются
if s[i] <> 0 then // Пропускаем пустые ячейки для ускорения
for k := 0 to 31 do
if ((s[i] shr k) and 1) > 0 then
begin
m[j] := i * 32 + k;
Inc(j);
end;
FillChar(m[j], (Length(m)-j) * SizeOf(Longword), 0); // Зануляем оставщуюся часть массива очищенного от повторов
SetLength(s, 0);
end;
По самой статье было очень интересно. Особенно в части простоя при загрузке данных в кэш процессора, сам приходил к подобным выводам.
С учётом того, что мало у какой компании есть больше 256 дата-центров — там вообще можно в байте держать всё это дело — итого в 2 ГБ вполне можно уложиться, ну в 4, если они захотят ВСЕ возможные адреса разметить :)
>Справедливо сказать, что фильтры Блума великолепно себя проявляют, пока помещаются в кэш L3. Но если нет, то они ужасны.
На самом деле в этом утверждении одна большая ошибка. L3 тут будет в случае, если данные все уже в памяти. Что далеко не факт.
У нас спарк успешно использует блум на данных, которые лежат в распределенной FS Hadoop, и в этом случае размер фильтра и L3 уже не играет никакой роли. А точнее, в роли L3 тут скорее всего объем памяти процесса на одной машине, или разумный объем передачи данных фильтра между машинами. В нашем случае это скажем 256 Мегабайт, а самих данных порядка терабайтов. При этом использование фильтра все еще дает экономию по времени обработки примерно в разы.
На самом деле в этом утверждении одна большая ошибка. L3 тут будет в случае, если данные все уже в памяти. Что далеко не факт.
У нас спарк успешно использует блум на данных, которые лежат в распределенной FS Hadoop, и в этом случае размер фильтра и L3 уже не играет никакой роли. А точнее, в роли L3 тут скорее всего объем памяти процесса на одной машине, или разумный объем передачи данных фильтра между машинами. В нашем случае это скажем 256 Мегабайт, а самих данных порядка терабайтов. При этом использование фильтра все еще дает экономию по времени обработки примерно в разы.
Проблему можно было решить, сделав не один блум-фильтр, а много маленьких по, скажем 4КБ. Сначала вычисляете номер блум-фильтра, а далее в нём уже применяете все ваши 8 хэш-функций. Сразу даст прирост в 8 раз при той же точности и объёме памяти.
Проблема со случайным доступом к памяти у фильтра Блума — штука известная и довольно очевидная для тех, кто знает числа, которые должен знать каждый программист.
Замена фильтра Блума на подобную хэш таблицу работает хорошо, но там совсем не нужен linear probing при обработке коллизий. Он легко заменяется на bitwise OR. Проверка наличия строчки в таблице делается через bitwise AND. В этом случае потребление памяти получается практически равно таковому у фильтра Блума, и работает быстрее предложенной таблички, т.к. нет лишних условных переходов/циклов, которые процессору надо предсказывать. Работает еще быстрее.
Замена фильтра Блума на подобную хэш таблицу работает хорошо, но там совсем не нужен linear probing при обработке коллизий. Он легко заменяется на bitwise OR. Проверка наличия строчки в таблице делается через bitwise AND. В этом случае потребление памяти получается практически равно таковому у фильтра Блума, и работает быстрее предложенной таблички, т.к. нет лишних условных переходов/циклов, которые процессору надо предсказывать. Работает еще быстрее.
Если автор хотел напомнить про медлительность случайного доступа к памяти при больших объёмах данных, то ему это удалось. Например, я постоянно об этом забываю.
Если же задача реальная, но одноразовая: «слить все файлы в один, удалить дубликаты и отправить результат в архив», то пусть стандартные процедуры хоть час работают, а автор в это время может Habr почитать.
Но если с полученным файлом ещё надо будет работать, например, статистику собрать, или если такую работу надо выполнять часто, то исходные данные изначально неверно хранятся. Можно предложить для каждого дата-центра завести отдельный двоичный файл (то есть, организовать бор первого уровня), а в каждом файле хранить отсортированные 32-битные IP-адреса.
Если же задача реальная, но одноразовая: «слить все файлы в один, удалить дубликаты и отправить результат в архив», то пусть стандартные процедуры хоть час работают, а автор в это время может Habr почитать.
Но если с полученным файлом ещё надо будет работать, например, статистику собрать, или если такую работу надо выполнять часто, то исходные данные изначально неверно хранятся. Можно предложить для каждого дата-центра завести отдельный двоичный файл (то есть, организовать бор первого уровня), а в каждом файле хранить отсортированные 32-битные IP-адреса.
Проблема случайного доступа не стоит так остро, когда фильтр Блума позволяет позволяет избежать доступа к гораздо более дорогому ресурсу. Например БД, Сетевой вызов. То есть тут важна стоимость альтернативного действия.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Когда фильтр Блума не подходит