Как организовать быстрый поиск соответствия IP адреса по списку сетей ?

src_ip,dst_ip, bytes

Не mikrotik accountant случаем парсите?

Я в influxdb загнал подобную структуру и от туда можно вытаскивать запросами по ip.

парсить планирую скриптом

Дерево отрезков

Какими могут быть подходы

Загнать оба файла в одну таблицу в кликхаус.

зачем?

Можно привести строку файла п.2. к записи в которой сеть преобразовать к диапазону целых чисел - 1 поле - число с которого начинается сеть и 2 поле - число которым заканчивается сеть

так наверное лучше. такие отрезки ж не могут пересекаться?

не могут, адресное пространство интернета - это не пересекающиеся блоки разной длины (число IP в блоке).

как его составить?
узел дерева - уникальный октет ip адреса ?

не могут

значит из второго файла делать двоичное(или еще какое) дерево отрезков, а потом последовательно матчить записи из первого по нему. тогда n*log m.

узел дерева - уникальный октет ip адреса ?

нетерминальный узел есть отрезок, охватывающий подчиненные отрезки. терминальный узел - собственно отрезок подсети, или что у тебя там.

Чтобы сразу логи в базу писать и метрики без особых вопросов выбирать.

в принципе понятно, осталось эффективный код написать

в этой БД есть функции проверки вхождения IP в блоки сетей?

Следует учитывать, что адрес может попасть в несколько подсетей, и выбирать обычно следует самую узкую.

в принципе понятно, осталось эффективный код написать

можно и троичное дерево сделать (лево,центр, право). если в узел попал, и он нетерминальный, то сначала ищешь в центральном отрезке, если ты левей - уходишь на левый, правей - на правый

Поделить на сегменты по маске, соответствие AS num получать поиском бинарного 32-битного значения ip&~mask по сегментам бинарным поиском.

Это первый фильтр на файл п.2 - очистить файл (сеть,AS) от мелких блоков, оставить нужно самые крупные блоки от AS ки.

какие у тебя проблемы со скоростью, что конкретно тормозит?

https://stackoverflow.com/questions/66054802/how-to-match-ip-addresses-to-a-subnets-and-get-sum

https://github.com/ClickHouse/ClickHouse/issues/6808

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

все так

в принципе да, в интернете префиксов длиннее чем /24 быть не может для IPv4

https://www.postgresql.org/docs/14/functions-net.html

Trie. Оно же raidix tree. Подумай про IP не как о числе, а как о бинарной строке. Тебе нужно найти все строки (сети с маской), являющиеся подстрокой из твоей строки (ip).

Нужно dst_ip каждой записи первого файла сматчить по сеть/маска записи второго файла и посчитать байты всех сматченных записей.чтобы в итоге получить число байт которое ушло на AS num как организовать быстрый поиск соответствия? пробегать записью первого файла по второму - в лоб так сказать, видится не оптимальным.

Тебе нужно найти прямое произведение всех элементов двух множеств. Ясен хрен у тебя n^2 будет. Если список сетей отсортируешь, то можешь уложиться в n*log(n).

Вот тебе либа на русте, которая позволяет такое сделать: https://docs.rs/treebitmap/0.4.0/treebitmap/

ее как то к сишке или через сишку прикрутить можно?

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

Либо выучи раст. Тут не то чтобы много кода тебе придётся написать:

1. Всосать файл с подсетями и сделать из него вот это дерево.
2. Построчно перебрать IP адреса, сделать поиск по дереву, выдать результат в другой файл.
3. ???
4. PROFIT!

IP хранить как uint32

Сети как 2 числа (границы IP адресов) unit32

Работа с uint32 быстрая, проверка на вхождение (IP >= start_net_IP) && (IP <= end_net_IP)

почему это должно быть в BGP демоне? Скорее ip lookup должен быть в ядре линукс или модуле ipt_netflow или в каком нибудь intel DPDK.

да, есть такое дело

почему это должно быть в BGP демоне?

Потому что BGP демоны хранят такие таблицы. Ты full view откуда взял, по-твоему? В ведре тоже может быть, но не гарантирую.

да. посмотрел исходники демона. есть какой то код с деревьями

Реализацию maxmindDB не смотрел?

Сделай массив на 2^32 элементов.