Как максимально быстро найти в диапазоне IP-адресов или подсетях нужный IP-адрес?

Question

[weranda]

Предыстория

Думал сделать в базе данных таблицу, в которой будут храниться все известные IP-адреса в формате [ip, подсеть, asn, владелец]для того, чтобы быстренько искать по ним нужные данные. В сети нашел базу на 400К строк. Но после тестовой обработки около трех процентов этой базы понял, что поддерживать ее в таком состоянии, в котором планировал — сложно будет.

Записи в исходной базе хранятся в формате:

начальный ip диапазона, конечный ip диапазона, asn, владелец диапазона.

Вот так:

5.45.192.0,5.45.208.255,13238,YANDEX LLC
213.180.192.0,213.180.223.255,13238,YANDEX LLC
...
1.179.112.0,1.179.127.255,396982,Google LLC
5.62.21.0,5.62.21.255,396982,Google LLC
...
1.0.0.0,1.0.0.255,13335,"Cloudflare, Inc."
1.1.1.0,1.1.1.255,13335,"Cloudflare, Inc."
...
2.16.20.0,2.16.21.255,12389,PJSC Rostelecom
2.16.53.0,2.16.53.255,12389,PJSC Rostelecom
...

Я взял первые 10К из 400К строк из этой базы, обработал и на выходе получил CSV объемом 10 Гб c почти 200 миллионами IP-адресов в формате [ip, подсеть, asn, владелец]. Провел кое-какие расчеты и понял, что если диапазоны обрабатывать полностью и потом добавлять в базу данных, только формирование выходных данных для базы данных займет 6–8 часов, а добавление в саму базу пару недель (это я по прикидкам при добавлении в базу файла в формате CSV). И это не говоря о конечном объеме базы и времени, затрачиваемом на запрос.

В общем, много времени уйдет на обработку. А с учетом того, что исходный файл базы с диапазонами IP-адресов планировалось обновлять раз в неделю, то этот эксперимент провалился. Есть большая вероятность того, что я что-то не так делаю.

*

Я подумал о том, что есть какая-то возможность быстрее получать данные по нужному IP-адреса из исходной базы прямо по диапазонам. Но я не знаю варианта, при котором не надо будет все эти диапазоны преобразовывать к IP-адресу и потом уже искать нужный IP-адрес по сформированным из диапазонов. И это я уже описал выше — ничего путевого не вышло.

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

Если я что-то не так сформулировал, извиняюсь, так как конкретно в этих сетевых делах/алгоритмах слабо соображаю.

Если кратко, то:

1
Есть CSV-файл в формате или в базе данных эти же данные:

[start_ip],[end_ip],[subnet],[holder]
5.45.192.0,5.45.208.255,13238,YANDEX LLC
1.179.112.0,1.179.127.255,396982,Google LLC
1.0.0.0,1.0.0.255,13335,"Cloudflare, Inc."
2.16.20.0,2.16.21.255,12389,PJSC Rostelecom
...и таких почти 400К

2
Есть IP-адрес посетителя сайта: 1.179.112.15

3
Нужно как-то быстро соотнести IP-адреса посетителя сайта с данными в базе данных и получить подсеть и владельца.

Comments

[asmelnik]

IP адрес -- это 32битное число. (с несколькими зарезервированными диапазонами)
Так что в итоге вы бы получили бы "всего" чуть менее 4 000 000 000 записей :)
Если не хотите связываться со спецтипами полей, переводите адрес сети в 32-битное число, читаете как найти наибольший адрес по адресу+маска.
Делаете 2 колонки: наименьший и наибольший адрес в подсети.
Ну а далее банально -- IP переводите в число и MIN<=NN<=MAX...
Поиск должен получится быстрый... Числовые поля индексируются и сравниваются легко.

[weranda]

asmelnik, Спасибо. Уже так сделал. Пока это самое доступная мне реализация. Может быть, стоит еще с «деревьями» что-то попробовать, как рекомендовали уже, но это чуть позже.

Answer 1

[Slava Rozhnev]

В PostgreSQL есть специальный тип данных для хранения адресов и набор функций для работы с ними

Answer 2

[Wataru]

Вообще, лучшая структура данных для этого - trie. Диапазоны, я уверен, идут так, что там фиксированно сколько-то начальных бит, а все оставшиеся - любые - все попадают в эту подсеть. Более того, все эти коды префиксные - ни один не будет началом другого.

Поэтому вам надо лишь эти префиксы в trie сложить, а в вершине сохранить саму запись. При запросе надо спускаться по битам айпишника в trie, пока не упретесь в лист - вот он и соответсвтует искомому диапазону.

Если хотите использовать существующие БД, то можно сохранить в любой реляционной базе данных начала диапазонов. По запросу IP вам надо найти последнюю стороку не больше его. Буквально

where range_start <= IP order by range_start desc limit 1

.

Смотрите только аккуратно, что сравнивать их надо как битовые строки/32-битные числа, а не просто как строки. Ибо должно выполнятся 127.0.01 > 8.8.8.8. Сравнение как строки же не сработает. Или храните как битовые строки, или преобразуйте в числа, или нулями отбивайте октеты, короче трех символов.

Раскрывать все 4 миллиарда айпишников в отдельные записи - вообще не работающая идея.

Answer 3

[VoidVolker]

Если стоит задача именно максимально быстрого поиска, то вот тут я уже отвечал на похожий вопрос: Как ускорить поиск элементов из статичного string[] по подстроке? и там же есть ссылка на готовый код примера реализации на шарпе. Если кратко: тупо дерево таблиц переходов, на весь диапазон IPv4 - 17 гигабайт памяти и практически мгновенный поиск. Если на списках - то поиск примерно в 1-1000 раз медленнее и значительнее меньше затраты памяти.
Примерно так:

public struct Organization
{
    public UInt64 Asn;
    public string Name;
}

var tree = ArrayTree<Organization>();
var org1 = new Organization() { Asn = 13238, Name = "YANDEX LLC" };
tree.Add(IPAddress.Parse("5.45.192.0").GetAddressBytes(), org1);

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

Измерил расход памяти для 400к записей: 1.6 и 3.6GB для х86 и х64 соответственно для ArrayTree. Для ListTree - 400 Мб.

Comments

[weranda]

17 Гб ОЗУ на запрос? — Это перебор для меня, тем более, что я знаю о шарпе, ровно то, что есть такой язык программирование) Пытался ознакомиться с вашим ответом и комментариями по ссылке, но там что-то на марсианском) С деревьями таблиц познакомлюсь.

[VoidVolker]

weranda Неее, какой еще на запрос? Это ВСЕ дерево. 17 гигов - это на все 4 миллиарда записей. Для 400к записей куда меньше надо памяти. Собственно я уже сделал замер и дополнил ответ. Полтора гига уже более реальное значение. Можно просто сделать стадартный апи, который просто будет просто читать/писать в дерево и его уже использовать под ваши нужды.

[Everything_is_bad]

VoidVolker, так по вопросам ТС уже понятно, что он не способен реализовать хоть какой-то алгоритм, максимум что он может, это воспользоваться готовым решением уровня "подключить стороннюю библиотеку"