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

O>Как бонус — можно будет легко допилить до работы с mapped file, чтоб данные автоматом сохранялись, но правда я не уверен что все оси предоставят надежные механизмы для декомита страниц отображенных в файл.

Это работает. Да. Там только надо лимиты поднимать.

Да просто отсортируй эти адреса и ищи делением пополам. Если ещё быстрей нужно — поставь фильтр Блума впереди.

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

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

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

Вспомнил еще у хеша есть проблема — расширение/сокращение таблицы очень долгое. Запросы сыпятся а мы таблицу расширям. То есть помимо 18-20 миллинов запросв в сек, требуется еще и стабильное, предсказуемое и гарантированное время реакции.

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

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

По "trie tree for ip address" много чего гуглится вроде бы.
Совсем не уверен, что это то, что вам надо, но вдргу поможет.