Какой самый быстрый алгоритм (способ) искать ipv4 адреса в таблицах. Чтобы вопрос был более понятен — скажем "проблема" по аналогии с контреком — надо найти к какому соединению относится пакет. Как?
Разница с контреком толко в том, что надо искать только адресс. Не надо искать ни пару адресов ни порты.
Подробности для оценки маштаба.
Всего размер таблицы — 10 миллионов.
Соотношение поисковых запросов к запросам обновления — 1 к 10 — 10 поисковых на один удаления/добавления.
Здравствуйте, imh0, Вы писали:
I>Какой самый быстрый алгоритм (способ) искать ipv4 адреса в таблицах. Чтобы вопрос был более понятен — скажем "проблема" по аналогии с контреком — надо найти к какому соединению относится пакет. Как? I>Разница с контреком толко в том, что надо искать только адресс. Не надо искать ни пару адресов ни порты.
I>Подробности для оценки маштаба.
I>Всего размер таблицы — 10 миллионов. I>Соотношение поисковых запросов к запросам обновления — 1 к 10 — 10 поисковых на один удаления/добавления.
Выскажу такое соображение: самый быстрый алгоритм, каким бы он ни был с программной точки зрения, должен быть заточен под физический носитель. Скажем, если хранилище на механическом диске, то нужно физическое партицирование, чтобы минимизировать движение считывающей головки.
Re[2]: Быстрый lookup по гиганским ip таблицам. Как?
Здравствуйте, gyraboo, Вы писали:
G>Выскажу такое соображение: самый быстрый алгоритм, каким бы он ни был с программной точки зрения, должен быть заточен под физический носитель. Скажем, если хранилище на механическом диске, то нужно физическое партицирование, чтобы минимизировать движение считывающей головки.
Все это в памяти естественно.
Re[3]: Быстрый lookup по гиганским ip таблицам. Как?
Здравствуйте, imh0, Вы писали:
G>>Выскажу такое соображение: самый быстрый алгоритм, каким бы он ни был с программной точки зрения, должен быть заточен под физический носитель. Скажем, если хранилище на механическом диске, то нужно физическое партицирование, чтобы минимизировать движение считывающей головки.
I>Все это в памяти естественно.
Ну тогда, раз это v4, то наверное самый быстрый способ — это прямая адресация по четырехмерному массиву? Типа ip[][][][]?
Хотя тут будут издержки на парсинг ip и вычленение 4 чисел, поэтому для ускорения работы ещё нужно минимизировать парсинг, и может как-то адресовать напрямую по строке ip.
Здравствуйте, gyraboo, Вы писали:
G>Ну тогда, раз это v4, то наверное самый быстрый способ — это прямая адресация по четырехмерному массиву? Типа ip[][][][]?
Здравствуйте, imh0, Вы писали:
G>>Ну тогда, раз это v4, то наверное самый быстрый способ — это прямая адресация по четырехмерному массиву? Типа ip[][][][]?
I>Так-то да ) Но —
I>255*255*255*255*8/(1024*1024*1024) = 31.5029220656 Гигабайт.
Ну а все другие способы будут менее быстрыми, т.к. они уже будут включать доп.такты процессора на преобразования, хеширование, поиск по бакетам, перебалансировку деревьев и т.д.
Re[6]: Быстрый lookup по гиганским ip таблицам. Как?
Здравствуйте, gyraboo, Вы писали:
G>Ну а все другие способы будут менее быстрыми, т.к. они уже будут включать доп.такты процессора на преобразования, хеширование, поиск по бакетам, перебалансировку деревьев и т.д.
Ну как сказать — Если учитывать итоговую производительность, то затраты на загрузку/выгрузку страниц скорее всего окажуться выше, чем "на преобразования, хеширование, поиск по бакетам, перебалансировку деревьев и т.д."
Не говоря уже о том, что свопа может и не быть вообще. Тогда все вообще работать не будет. )
Здравствуйте, imh0, Вы писали:
G>>Ну а все другие способы будут менее быстрыми, т.к. они уже будут включать доп.такты процессора на преобразования, хеширование, поиск по бакетам, перебалансировку деревьев и т.д.
I>Ну как сказать — Если учитывать итоговую производительность, то затраты на загрузку/выгрузку страниц скорее всего окажуться выше, чем "на преобразования, хеширование, поиск по бакетам, перебалансировку деревьев и т.д."
I>Не говоря уже о том, что свопа может и не быть вообще. Тогда все вообще работать не будет. )
Ну тогда еще вариант — адресовать по наиболее селективным значениям ip-адресов, т.е. по значениям, которые снижают кол-во записей после применения такого фильтра, а после применения селективных фильтров остается бакет размера, который соответствует заданным пределам ОЗУ. Сами селективные значения твоя программа высчитывает во втором потоке на основе первичного набора ip-адресов, а потом периодически пересчитывает селективные признаки и ребалансирует хэш-структуру, когда добавилось достаточное кол-во новых ip-адресов и замечена деградация скорости поиска.
Мысль тут такая, что селективные признаки нужно выстраивать на основе конкретного набора ip-адресов, и ребалансировать на основе измененных данных. Если их заранее их выстроить, вслепую, или по каким-то своим эвристикам — это будет неоптимально для скорости.
В качестве структуры для этого можно наверное использовать обычный хэш-мап, просто ключ по конкретному искомому ip-адресу надо высчитывать на основе этих селективных признаков.
Здравствуйте, imh0, Вы писали:
I>255*255*255*255*8/(1024*1024*1024) = 31.5029220656 Гигабайт.
Для адреса x.y.z.t можно сделать таблицу ip[t][z][y] (в обратном порядке)
Она будет занимать в 200 раз меньше, т.е. примерно 150-200 Мб
При хранении 10 млн записей вероятностей коллизий будет мала
Best regards, Буравчик
Re[6]: Быстрый lookup по гиганским ip таблицам. Как?
Здравствуйте, Буравчик, Вы писали:
I>>255*255*255*255*8/(1024*1024*1024) = 31.5029220656 Гигабайт.
Б>Для адреса x.y.z.t можно сделать таблицу ip[t][z][y] (в обратном порядке) Б>Она будет занимать в 200 раз меньше, т.е. примерно 150-200 Мб Б>При хранении 10 млн записей вероятностей коллизий будет мала
Для ещё большего снижения коллизий нужно набор селективных признаков брать не от балды, а на основе анализа конкретного набора хранимых ip-адресов.
Re[8]: Быстрый lookup по гиганским ip таблицам. Как?
Здравствуйте, gyraboo, Вы писали:
G>Ну тогда еще вариант — адресовать по наиболее селективным значениям ip-адресов, т.е. по значениям, которые снижают кол-во записей после применения такого фильтра, а после применения селективных фильтров остается бакет размера, который соответствует заданным пределам ОЗУ. Сами селективные значения твоя программа высчитывает во втором потоке на основе первичного набора ip-адресов, а потом периодически пересчитывает селективные признаки и ребалансирует хэш-структуру, когда добавилось достаточное кол-во новых ip-адресов и замечена деградация скорости поиска. G>Мысль тут такая, что селективные признаки нужно выстраивать на основе конкретного набора ip-адресов, и ребалансировать на основе измененных данных. Если их заранее их выстроить, вслепую, или по каким-то своим эвристикам — это будет неоптимально для скорости. G>В качестве структуры для этого можно наверное использовать обычный хэш-мап, просто ключ по конкретному искомому ip-адресу надо высчитывать на основе этих селективных признаков.
Не очень понял, если честно, расскажи более просто.
И кроме того, число запросов в секунду которые надо отрабатывать примерно 18-20 миллинов с секунду. Это я про второй поток.
Re[6]: Быстрый lookup по гиганским ip таблицам. Как?
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, imh0, Вы писали:
I>>255*255*255*255*8/(1024*1024*1024) = 31.5029220656 Гигабайт.
Б>Для адреса x.y.z.t можно сделать таблицу ip[t][z][y] (в обратном порядке) Б>Она будет занимать в 200 раз меньше, т.е. примерно 150-200 Мб
Не понимаю почему 200 мб?
Б>При хранении 10 млн записей вероятностей коллизий будет мала
Почему мала? IP-адреса наверняка неравномерно будут распределенны, да и вообще мне кажется, что при таком соотношении возможных к хранимым как раз коллизий будет много?
Re[9]: Быстрый lookup по гиганским ip таблицам. Как?
Здравствуйте, imh0, Вы писали:
G>>Ну тогда еще вариант — адресовать по наиболее селективным значениям ip-адресов, т.е. по значениям, которые снижают кол-во записей после применения такого фильтра, а после применения селективных фильтров остается бакет размера, который соответствует заданным пределам ОЗУ. Сами селективные значения твоя программа высчитывает во втором потоке на основе первичного набора ip-адресов, а потом периодически пересчитывает селективные признаки и ребалансирует хэш-структуру, когда добавилось достаточное кол-во новых ip-адресов и замечена деградация скорости поиска. G>>Мысль тут такая, что селективные признаки нужно выстраивать на основе конкретного набора ip-адресов, и ребалансировать на основе измененных данных. Если их заранее их выстроить, вслепую, или по каким-то своим эвристикам — это будет неоптимально для скорости. G>>В качестве структуры для этого можно наверное использовать обычный хэш-мап, просто ключ по конкретному искомому ip-адресу надо высчитывать на основе этих селективных признаков.
I>Не очень понял, если честно, расскажи более просто. I>И кроме того, число запросов в секунду которые надо отрабатывать примерно 18-20 миллинов с секунду. Это я про второй поток.
Ну смотри, фундаментальный подход к оптимизации и ускорению поиска — это нахождение и использование селективных признаков.
Например, у тебя в базе хранятся 4 адреса:
1.1.1.1
1.2.1.1
1.3.1.1
1.2.2.1
Видно, что в этом наборе наиболее часто меняются 2-й и 3-й номера. Значит они являются селективными признаками, т.е. если сначала фильтровать по ним, то оставшиеся выборки будут меньше, чем например фильтрация по 1-му или 4-му номеру, и поиск по ним будет быстрее.
Значит, можно взять классическую структуру данных хэш-мэп, и сделать ключ по 2-му и 3-му номерам:
HashMap<IpKey, IpInfo> ipMap = new HashMap();
где IpKey это класс:
class IpKey {
private byte number2; // второй номер ip-адреса
private byte number3; // третий номер ip-адреса
}
IpInfo — класс с информацией по нужному ip
Но учитывая что у разных классов ip-адресов, даже в ipv4, некоторые биты в номерах зарезервированы или имеют стандартные значения, это также поможет сократить размер структуры для хранения, т.е. вычислять ключ для хэш-мапы можно с учетом и этих битов.
Чтобы определить, каким именно будет IpKey и какие признаки являются достаточно селективными чтобы включать в ключ, нужно анализировать конкретный массив твоих ip-адресов.
Re[10]: Быстрый lookup по гиганским ip таблицам. Как?
Здравствуйте, gyraboo, Вы писали:
G>Ну смотри, фундаментальный подход к оптимизации и ускорению поиска — это нахождение и использование селективных признаков. G>Видно, что в этом наборе наиболее часто меняются 2-й и 3-й номера. Значит они являются селективными признаками
Теперь понял. То есть ты предлагаешь переодически переотимизировать таблицу.
I>>255*255*255*255*8/(1024*1024*1024) = 31.5029220656 Гигабайт.
Ну и что? Просто зарезервировать регион такого размера, а комитить страницы по мере получения сегфолтов
Как много веселых ребят, и все делают велосипед...
Re[7]: Быстрый lookup по гиганским ip таблицам. Как?
Здравствуйте, ononim, Вы писали:
I>>>255*255*255*255*8/(1024*1024*1024) = 31.5029220656 Гигабайт. O>Ну и что? Просто зарезервировать регион такого размера, а комитить страницы по мере получения сегфолтов
Согласен — память не ресурс!!!111 ))
Re[8]: Быстрый lookup по гиганским ip таблицам. Как?
I>>>>255*255*255*255*8/(1024*1024*1024) = 31.5029220656 Гигабайт. O>>Ну и что? Просто зарезервировать регион такого размера, а комитить страницы по мере получения сегфолтов I>Согласен — память не ресурс!!!111 ))
Не память — не ресурс, а использование аппаратного механизма виртуальной памяти для организации sparse-array. Зарезервированные страницы виртуальной памяти почти не занимают. Разумеется надо будет реализоваь и логику для декоммита не нужных страниц.
Как много веселых ребят, и все делают велосипед...
Re[11]: Быстрый lookup по гиганским ip таблицам. Как?
Здравствуйте, imh0, Вы писали:
I>То есть, ты предлагаешь использовать хеши. Тут как раз и проблема. Надо быстрее. (
Не просто хэш, а хэш с ключом, основанным на селективных признаках, вычисленных для конкретного набора ip-адресов. Это как раз и есть "быстрее", чем просто хэш-таблица на основе ключа "от балды".
Если ты не хочешь адресовать массив прямо по ip-адресу, то ты в любом случае приходишь к использования хэш-функции, будет ли она в виде готовой хэш-мапы, или ты руками реализуешь свою, но это будет хэш-функция.
Можно конечно ещё сделать какой-нибудь кэш, типа кешировать самые горячие ip-адреса, перенося их из хэш-мапы в более быструю структуру, которая адресует их напрямую (без применения хеш-функции) или с минимальной хэш-функцией. Если в этой быстрой структуре с прямой адресацией ip-адрес не найден, тогда алгоритм поиска лезет в более медленную хэш-мапу.
Здравствуйте, ononim, Вы писали:
O>Не память — не ресурс, а использование аппаратного механизма виртуальной памяти для организации sparse-array. Зарезервированные страницы виртуальной памяти почти не занимают. Разумеется надо будет реализоваь и логику для декоммита не нужных страниц.
В целом как идея, подходит. Спасибо. Но пока вижу явную угрозу вырождения как раз при равномерном распределени. То есть в каждой странице по одному адресу и привет. Но как сама идея хорошая.
Re[10]: Быстрый lookup по гиганским ip таблицам. Как?
I>В целом как идея, подходит. Спасибо. Но пока вижу явную угрозу вырождения как раз при равномерном распределени. То есть в каждой странице по одному адресу и привет. Но как сама идея хорошая.
ну зависит от того какая информация хранится per-adress. Если там пара байт то не эффективно будет конечно при рандомных распределениях. А если распределение адресов не совсем рандомное (скажем, подсети) или информации per-adress много то может и норм будет.
Как бонус — можно будет легко допилить до работы с mapped file, чтоб данные автоматом сохранялись, но правда я не уверен что все оси предоставят надежные механизмы для декомита страниц отображенных в файл.
Как много веселых ребят, и все делают велосипед...
Re[11]: Быстрый lookup по гиганским ip таблицам. Как?
Здравствуйте, ononim, Вы писали:
O>Как бонус — можно будет легко допилить до работы с mapped file, чтоб данные автоматом сохранялись, но правда я не уверен что все оси предоставят надежные механизмы для декомита страниц отображенных в файл.
Это работает. Да. Там только надо лимиты поднимать.
Здравствуйте, gyraboo, Вы писали:
I>>То есть, ты предлагаешь использовать хеши. Тут как раз и проблема. Надо быстрее. (
G>Не просто хэш, а хэш с ключом, основанным на селективных признаках, вычисленных для конкретного набора ip-адресов. Это как раз и есть "быстрее", чем просто хэш-таблица на основе ключа "от балды".
Вспомнил еще у хеша есть проблема — расширение/сокращение таблицы очень долгое. Запросы сыпятся а мы таблицу расширям. То есть помимо 18-20 миллинов запросв в сек, требуется еще и стабильное, предсказуемое и гарантированное время реакции.
Re[13]: Быстрый lookup по гиганским ip таблицам. Как?
Здравствуйте, imh0, Вы писали:
I>>>То есть, ты предлагаешь использовать хеши. Тут как раз и проблема. Надо быстрее. (
G>>Не просто хэш, а хэш с ключом, основанным на селективных признаках, вычисленных для конкретного набора ip-адресов. Это как раз и есть "быстрее", чем просто хэш-таблица на основе ключа "от балды".
I>Вспомнил еще у хеша есть проблема — расширение/сокращение таблицы очень долгое. Запросы сыпятся а мы таблицу расширям. То есть помимо 18-20 миллинов запросв в сек, требуется еще и стабильное, предсказуемое и гарантированное время реакции.
Ну так есть же lock-free rehashing структуры.
И ещё один фактор ускорения поиска — это использовать многопоточность и задействовать все ядра процессора.
И ещё вариант — если есть современная видюха, её параллельную архитектуру тоже можно круто задействовать, как для хранения так и для поиска.
Здравствуйте, imh0, Вы писали:
I>Какой самый быстрый алгоритм (способ) искать ipv4 адреса в таблицах. Чтобы вопрос был более понятен — скажем "проблема" по аналогии с контреком — надо найти к какому соединению относится пакет. Как? I>Разница с контреком толко в том, что надо искать только адресс. Не надо искать ни пару адресов ни порты.
I>Подробности для оценки маштаба.
I>Всего размер таблицы — 10 миллионов. I>Соотношение поисковых запросов к запросам обновления — 1 к 10 — 10 поисковых на один удаления/добавления.
Обычная hash таблица внутри узлов сбалансированное дерево для устранение коллизий.
int hash_table[number_of_buckets];
tree_nodes nodes[nodes_limit];
emptry_tree_root=-1;
tree_root=hash_table[ backet(key) ];
tree_{insert,delete,find}(tree_root,key,...)
ps: Обычное RB или AVL дерево укладывается в 2 указателя +1,2бит (которые при желании можно в указатели затолкать, т.к. там есть неиспользуемые биты)
Re[13]: Быстрый lookup по гиганским ip таблицам. Как?
Здравствуйте, imh0, Вы писали:
G>>Не просто хэш, а хэш с ключом, основанным на селективных признаках, вычисленных для конкретного набора ip-адресов. Это как раз и есть "быстрее", чем просто хэш-таблица на основе ключа "от балды".
I>Вспомнил еще у хеша есть проблема — расширение/сокращение таблицы очень долгое. Запросы сыпятся а мы таблицу расширям. То есть помимо 18-20 миллинов запросв в сек, требуется еще и стабильное, предсказуемое и гарантированное время реакции.
Dinkumware STL hashmap, Microsoft STL hashmap имеют фиксированное время на каждую операцию. Они одновременно держат до двух таблиц и на каждую операцию добавления могут сделать перемещение до двух ключей в новую таблицу; что-то похожее есть и на сжатии.
В крайнем случае можно реализовать такое и самому, метод банален.
Здравствуйте, imh0, Вы писали:
I>Всего размер таблицы — 10 миллионов. I>Соотношение поисковых запросов к запросам обновления — 1 к 10 — 10 поисковых на один удаления/добавления.
Быстро это сколько в граммах? 10 миллионов записей это не много.
PostgreSQL поддерживает IP как поле данных и работает очень шустро при правильной настройке. Я 10+ лет назад сохранял данные о сессиях со скоростью 100-200К вставок в секунду.
