Какой самый быстрый алгоритм (способ) искать ipv4 адреса в таблицах. Чтобы вопрос был более понятен — скажем "проблема" по аналогии с контреком — надо найти к какому соединению относится пакет. Как?
Разница с контреком толко в том, что надо искать только адресс. Не надо искать ни пару адресов ни порты.

Подробности для оценки маштаба.

Всего размер таблицы — 10 миллионов.
Соотношение поисковых запросов к запросам обновления — 1 к 10 — 10 поисковых на один удаления/добавления.

Здравствуйте, imh0, Вы писали:

I>Какой самый быстрый алгоритм (способ) искать ipv4 адреса в таблицах. Чтобы вопрос был более понятен — скажем "проблема" по аналогии с контреком — надо найти к какому соединению относится пакет. Как?
I>Разница с контреком толко в том, что надо искать только адресс. Не надо искать ни пару адресов ни порты.

I>Подробности для оценки маштаба.

I>Всего размер таблицы — 10 миллионов.
I>Соотношение поисковых запросов к запросам обновления — 1 к 10 — 10 поисковых на один удаления/добавления.

Выскажу такое соображение: самый быстрый алгоритм, каким бы он ни был с программной точки зрения, должен быть заточен под физический носитель. Скажем, если хранилище на механическом диске, то нужно физическое партицирование, чтобы минимизировать движение считывающей головки.

Здравствуйте, gyraboo, Вы писали:

G>Выскажу такое соображение: самый быстрый алгоритм, каким бы он ни был с программной точки зрения, должен быть заточен под физический носитель. Скажем, если хранилище на механическом диске, то нужно физическое партицирование, чтобы минимизировать движение считывающей головки.

Все это в памяти естественно.

Здравствуйте, imh0, Вы писали:

G>>Выскажу такое соображение: самый быстрый алгоритм, каким бы он ни был с программной точки зрения, должен быть заточен под физический носитель. Скажем, если хранилище на механическом диске, то нужно физическое партицирование, чтобы минимизировать движение считывающей головки.

I>Все это в памяти естественно.

Ну тогда, раз это v4, то наверное самый быстрый способ — это прямая адресация по четырехмерному массиву? Типа ip[][][][]?
Хотя тут будут издержки на парсинг ip и вычленение 4 чисел, поэтому для ускорения работы ещё нужно минимизировать парсинг, и может как-то адресовать напрямую по строке ip.

Здравствуйте, gyraboo, Вы писали:

G>Ну тогда, раз это v4, то наверное самый быстрый способ — это прямая адресация по четырехмерному массиву? Типа ip[][][][]?

Так-то да ) Но —

255*255*255*255*8/(1024*1024*1024) = 31.5029220656 Гигабайт.

Здравствуйте, imh0, Вы писали:

G>>Ну тогда, раз это v4, то наверное самый быстрый способ — это прямая адресация по четырехмерному массиву? Типа ip[][][][]?

I>Так-то да ) Но —

I>255*255*255*255*8/(1024*1024*1024) = 31.5029220656 Гигабайт.

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

Здравствуйте, 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 млн записей вероятностей коллизий будет мала

Здравствуйте, Буравчик, Вы писали:

I>>255*255*255*255*8/(1024*1024*1024) = 31.5029220656 Гигабайт.

Б>Для адреса x.y.z.t можно сделать таблицу ip[t][z][y] (в обратном порядке)
Б>Она будет занимать в 200 раз меньше, т.е. примерно 150-200 Мб
Б>При хранении 10 млн записей вероятностей коллизий будет мала

Для ещё большего снижения коллизий нужно набор селективных признаков брать не от балды, а на основе анализа конкретного набора хранимых ip-адресов.

Здравствуйте, gyraboo, Вы писали:

G>Ну тогда еще вариант — адресовать по наиболее селективным значениям ip-адресов, т.е. по значениям, которые снижают кол-во записей после применения такого фильтра, а после применения селективных фильтров остается бакет размера, который соответствует заданным пределам ОЗУ. Сами селективные значения твоя программа высчитывает во втором потоке на основе первичного набора ip-адресов, а потом периодически пересчитывает селективные признаки и ребалансирует хэш-структуру, когда добавилось достаточное кол-во новых ip-адресов и замечена деградация скорости поиска.
G>Мысль тут такая, что селективные признаки нужно выстраивать на основе конкретного набора ip-адресов, и ребалансировать на основе измененных данных. Если их заранее их выстроить, вслепую, или по каким-то своим эвристикам — это будет неоптимально для скорости.
G>В качестве структуры для этого можно наверное использовать обычный хэш-мап, просто ключ по конкретному искомому ip-адресу надо высчитывать на основе этих селективных признаков.

Не очень понял, если честно, расскажи более просто.
И кроме того, число запросов в секунду которые надо отрабатывать примерно 18-20 миллинов с секунду. Это я про второй поток.

Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, 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-адреса наверняка неравномерно будут распределенны, да и вообще мне кажется, что при таком соотношении возможных к хранимым как раз коллизий будет много?

Здравствуйте, 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-адресов.

Здравствуйте, gyraboo, Вы писали:

G>Ну смотри, фундаментальный подход к оптимизации и ускорению поиска — это нахождение и использование селективных признаков.
G>Видно, что в этом наборе наиболее часто меняются 2-й и 3-й номера. Значит они являются селективными признаками

Теперь понял. То есть ты предлагаешь переодически переотимизировать таблицу.

https://ieeexplore.ieee.org/document/1557298
https://storm.cis.fordham.edu/~zhang/cs5835/slides/modularHash.pdf

G>Но учитывая что у разных классов ip-адресов, даже в ipv4, некоторые биты в номерах зарезервированы или имеют стандартные значения, это также поможет сократить размер структуры для хранения, т.е. вычислять ключ для хэш-мапы можно с учетом и этих битов.

https://ipset.netfilter.org/libipset.man.html

То есть, ты предлагаешь использовать хеши. Тут как раз и проблема. Надо быстрее. (

I>>255*255*255*255*8/(1024*1024*1024) = 31.5029220656 Гигабайт.
Ну и что? Просто зарезервировать регион такого размера, а комитить страницы по мере получения сегфолтов

Здравствуйте, ononim, Вы писали:

I>>>255*255*255*255*8/(1024*1024*1024) = 31.5029220656 Гигабайт.
O>Ну и что? Просто зарезервировать регион такого размера, а комитить страницы по мере получения сегфолтов

Согласен — память не ресурс!!!111 ))

I>>>>255*255*255*255*8/(1024*1024*1024) = 31.5029220656 Гигабайт.
O>>Ну и что? Просто зарезервировать регион такого размера, а комитить страницы по мере получения сегфолтов
I>Согласен — память не ресурс!!!111 ))
Не память — не ресурс, а использование аппаратного механизма виртуальной памяти для организации sparse-array. Зарезервированные страницы виртуальной памяти почти не занимают. Разумеется надо будет реализоваь и логику для декоммита не нужных страниц.

Здравствуйте, imh0, Вы писали:

I>То есть, ты предлагаешь использовать хеши. Тут как раз и проблема. Надо быстрее. (

Не просто хэш, а хэш с ключом, основанным на селективных признаках, вычисленных для конкретного набора ip-адресов. Это как раз и есть "быстрее", чем просто хэш-таблица на основе ключа "от балды".
Если ты не хочешь адресовать массив прямо по ip-адресу, то ты в любом случае приходишь к использования хэш-функции, будет ли она в виде готовой хэш-мапы, или ты руками реализуешь свою, но это будет хэш-функция.

Можно конечно ещё сделать какой-нибудь кэш, типа кешировать самые горячие ip-адреса, перенося их из хэш-мапы в более быструю структуру, которая адресует их напрямую (без применения хеш-функции) или с минимальной хэш-функцией. Если в этой быстрой структуре с прямой адресацией ip-адрес не найден, тогда алгоритм поиска лезет в более медленную хэш-мапу.

Здравствуйте, ononim, Вы писали:

O>Не память — не ресурс, а использование аппаратного механизма виртуальной памяти для организации sparse-array. Зарезервированные страницы виртуальной памяти почти не занимают. Разумеется надо будет реализоваь и логику для декоммита не нужных страниц.

В целом как идея, подходит. Спасибо. Но пока вижу явную угрозу вырождения как раз при равномерном распределени. То есть в каждой странице по одному адресу и привет. Но как сама идея хорошая.

I>В целом как идея, подходит. Спасибо. Но пока вижу явную угрозу вырождения как раз при равномерном распределени. То есть в каждой странице по одному адресу и привет. Но как сама идея хорошая.
ну зависит от того какая информация хранится per-adress. Если там пара байт то не эффективно будет конечно при рандомных распределениях. А если распределение адресов не совсем рандомное (скажем, подсети) или информации per-adress много то может и норм будет.
Как бонус — можно будет легко допилить до работы с mapped file, чтоб данные автоматом сохранялись, но правда я не уверен что все оси предоставят надежные механизмы для декомита страниц отображенных в файл.