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

Предыстория

Думал сделать в базе данных таблицу, в которой будут храниться все известные 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-адреса посетителя сайта с данными в базе данных и получить подсеть и владельца.
  • Вопрос задан
  • 178 просмотров
Пригласить эксперта
Ответы на вопрос 4
rozhnev
@rozhnev
Fullstack programmer, DBA, медленно, дорого
В PostgreSQL есть специальный тип данных для хранения адресов и набор функций для работы с ними
Ответ написан
Комментировать
wataru
@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 миллиарда айпишников в отдельные записи - вообще не работающая идея.
Ответ написан
Комментировать
VoidVolker
@VoidVolker
Dark side eye. А у нас печеньки! А у вас?
Если стоит задача именно максимально быстрого поиска, то вот тут я уже отвечал на похожий вопрос: Как ускорить поиск элементов из статичного 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 Мб.
Ответ написан
Vapaamies
@Vapaamies
Разработчик будущей ОС для ПК размером 250 МБ
Вне зависимости от используемой СУБД IP-адреса надо хранить как числа, а начальный и конечный IP преобразовать в связку IP+подсеть, типа 192.168.100.128/25, как делает PostgreSQL. И, видимо, сделать функциональный индекс какой-нибудь, чтобы было проще искать. Если СУБД их поддерживает. Всю обвязку придется писать самостоятельно. Встроенный в СУБД тип и соответствующие функции сильно упрощают дело.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы