Как искать IP адрес в списке диапазонов

one · 30.11.2022

ИП адрес 217.5.150.228 входит в этот диапазон:

DevOps сказал(а):
217.5.150.224 - 217.5.150.231

Alexmd · 30.11.2022

правильное решение ниже по теме
https://zennolab.com/discussion/threads/kak-iskat-ip-adres-v-spiske-diapazonov.108305/post-717260

Alexmd · 30.11.2022

DevOps сказал(а):
Nice.
thanks

исправил функцию. перечитал, потом перепроверил и оказалось, что работала неправильно.

BAZAg · 30.11.2022

DevOps сказал(а):
Добрый день форум
Подскажите направление, как поступить в таком вопросе
Есть список диапазонов IP адресов такого вида

194.206.161.47 - 194.206.161.47
213.159.160.0 - 213.159.191.255
194.219.52.224 - 194.219.52.239
217.204.110.64 - 217.204.110.127
217.141.234.232 - 217.141.234.239
62.27.21.0 - 62.27.21.255
212.82.218.48 - 212.82.218.63
212.63.174.183 - 212.63.174.183
217.5.150.224 - 217.5.150.231
Список диапазонов более 3 миллионов строк (IANA IPv4)
Теперь, у меня есть IP адрес и мне нужно найти диапазон в который он входит
Дайте направление и подсказки, спасибо

Берете любую базу данных, например SQLite или MySQL.
Создаете там табличку, которая содержит два столбца start и end
Далее, заполняете эту табличку своими диапазонами, прежде конвертируя IP to INT.

C#:

byte[] ip = System.Net.IPAddress.Parse("170.66.0.0").GetAddressBytes();
Array.Reverse(ip);
var ip_start = BitConverter.ToUInt32(ip, 0); // тут у нас уже число

А далее уже с базы в любой момент дёргаем как-то так:
SELECT * FROM tb WHERE start > 123 AND end < 123 LIMIT 1

Где, 123 - IP который нужно проверить.

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

P.S. Нужно учитывать, что IP может входить в несколько диапазонов.
Вот пример, набросал на шарпе, вижу что несколько вариантов может быть.

C#:

string ip = "212.82.218.49";
string text = @"
194.206.161.47 - 194.206.161.47
213.159.160.0 - 213.159.191.255
194.219.52.224 - 194.219.52.239
217.204.110.64 - 217.204.110.127
217.141.234.232 - 217.141.234.239
62.27.21.0 - 62.27.21.255
212.82.218.48 - 212.82.218.63
212.63.174.183 - 212.63.174.183
217.5.150.224 - 217.5.150.231
";
var list = text.Trim().Split(new[]{Environment.NewLine}, StringSplitOptions.RemoveEmptyEntries).ToList();

return list.Where(line =>{
    var arr = line.Trim().Split(new[] {" - "}, StringSplitOptions.RemoveEmptyEntries);
    var start = BitConverter.ToUInt32(System.Net.IPAddress.Parse(arr.First()).GetAddressBytes().Reverse().ToArray(), 0);
    var end = BitConverter.ToUInt32(System.Net.IPAddress.Parse(arr.Last()).GetAddressBytes().Reverse().ToArray(), 0);
    var data = BitConverter.ToUInt32(System.Net.IPAddress.Parse(ip).GetAddressBytes().Reverse().ToArray(), 0);
    bool check = start>=data && data <= end;
    string log = string.Format("IP:{0} D: {1} CHECK: {2}", ip, line, check);
    if(check) project.SendInfoToLog(log);
    else  project.SendWarningToLog(log);
    return check;
    
}).ToList()
    .DefaultIfEmpty(string.Empty).First();

Ilshakin · 30.11.2022

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

NuGet Gallery | IPAddressRange 4.2.0

This library allows you to parse range of IP address string such as "192.168.0.0/24" and "192.168.0.0/255.255.255.0" and "192.168.0.0-192.168.0.255", and can contains check. This library supports both IPv4 and IPv6.

www.nuget.org

пробуем:

Alexmd · 30.11.2022

@Ilshakin, зачем качать какие-то библиотеки?
Там простая проверка, не требующая таких заморочек. Подойдет и решение от Юрия(@BAZAg), и мое, которое опубликую ниже.
В своем первом сообщении я изначально пошел по неверному пути, поспешил и запутался в цикле, причем дважды, не стал больше исправлять, так как допер до другого способа, который мне больше по душе.

C#:

public static bool isIpRanged(string ip, string start, string end){
            long _ip = long.Parse(string.Join("", ip.Split('.').Select(x=>$"00{x}".Substring($"00{x}".Length-3))));
            long _start = long.Parse(string.Join("", start.Split('.').Select(x=>$"00{x}".Substring($"00{x}".Length-3))));
            long _end = long.Parse(string.Join("", end.Split('.').Select(x=>$"00{x}".Substring($"00{x}".Length-3))));
            return (_ip >= _start && _ip <= _end);
        }

C#:

string ip = "212.82.218.49";
var list = new List<string>(){
    "194.206.161.47 - 194.206.161.47",
    "213.159.160.0 - 213.159.191.255",
    "194.219.52.224 - 194.219.52.239",
    "217.204.110.64 - 217.204.110.127",
    "217.141.234.232 - 217.141.234.239",
    "62.27.21.0 - 62.27.21.255",
    "212.82.218.48 - 212.82.218.63",
    "212.63.174.183 - 212.63.174.183",
    "217.5.150.224 - 217.5.150.231"
};
return list.GroupBy(x=>x.Split(new[]{" - "}, StringSplitOptions.RemoveEmptyEntries)).Where(x =>CC.isIpRanged(ip, x.Key.First(), x.Key.Last())).First().First();

Очень было интересно, почему код Юрия отрабатывает с ошибкой. Ведь, на первый взгляд, там все очень даже. Оказалось, там в проверке больше-меньше неточность

правильное условие: start<=data&&data<=end
И все становится на свои места.

BAZAg · 30.11.2022

Alexmd сказал(а):
правильное условие: start<=data&&data<=end

Допустим start = 10 data = 15 end = 20
Тогда check = true должно быть тогда, когда data >= start и end >= data
Я действительно накосячил с условием (думал правильно, написал не правильно).

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

Ilshakin сказал(а):
немного не так ...
из представленных диапазонов - ip войдет только в один диапазон, проверяем:

Да, может потому, что я там с условием накосячил.

Alexmd · 01.12.2022

CC - класс в общем коде
isIpRanged - метод класса
Если зашла речь об оптимизации, то стоит:
1. сделать его динамическим
2. переводить ip в число только один раз для всего поиска, как верно подметил Юрий.
3. распараллелить поиск
4. ну, и с базой ip тоже что-то сделать... это здесь главное. разбить ее, к примеру, на множество списков по первому октету, например, и искать придется уже не в списке с 3KK строк, а в условных 15К. Можно использовать как бд, так и статические файлы. Не думаю, что подключение к бд будет быстрее считывания не такого уж большого файла в поток.. все это надо проверять. Скорее всего имеет смысл создать предварительно списки с диапазонами, уже переведенными в числа, как также изначально посоветовал Юрий. Вкупе с дроблением большого списка на пару сотен маленьких скорость проверки вырастет не просто в разы, по идее, а может и хватит для Ваших потребностей.
Вообще, оптимизировать надо не преждевременно, а по необходимости, проверяя эффект от того или иного мероприятия. Так и опыта наберешься и не запутаешься.
Думаю, что вполне реально достичь скорости в 10КК проверок в сутки, даже на достаточно слабой машине.
зы. а если загрузить в память все эти списки единоразово и удерживать их там всегда, пока работает программа, то вообще не важно, где их хранить, в списках, в бд или вообще собирать запросами откуда-то, ведь на дистанции это окажется вообще "песчинкой".

Alexmd · 01.12.2022

Раз в сутки собрал, раздробил, перевел в числа, загрузил в память и проверяй себе сколько хочешь. Причем, это тоже можно сделать безшовно. Это что касается чистой проверки.
Останется другое узкое горлышко потом: сохранение и запись результатов в другое место. Это тоже нужно придумать, как оптимизировать. Но, как я и посоветовал выше, проблемы надо решать по мере их поступления.

Ilshakin · 01.12.2022

DevOps сказал(а):
using NetTools; забыли
Без нее будет ругаться на IPAddressRange.Parse
ЗЫ Соррян, не заметил что код заскринен не полностью, а так в целом то что нужно, спасибо
ЗЫ 2 К сожалению решение не подходит, только база RIPE 4M+ строк, а еще есть 4 корневые зоны, проверка 1 ip заняла больше 2 минут, а по проекту проверять нужно около 10М в сутки. Придется думать насчет БД и индексации
Посмотреть вложение 100232

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

набросал код для многопоточной проверки, при следующих условиях:
потоков : 100
кол-во ip: 1 млн
кол-во диапазонов: 9
результат : ~ 1 мин. 40 сек

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

код , на всякий

C#:

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Net;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
using NetTools;

namespace ConsoleApp3
{
    public class Program
    {
        private static void Main(string[] args)
        {
            const int threads = 100; // Кол-во потоков
            const string resultFile = @"C:\Users\Anon\Desktop\result.txt"; // Файл для сохранения результатов
            const string ipFile = @"C:\Users\Anon\Desktop\ip.txt"; // Файл с ip-адресами

            Console.WriteLine("Начинаю многопоточный чек ...");
            Stopwatch timer = Stopwatch.StartNew();

            var results = TextWriter.Synchronized(new StreamWriter(resultFile, false));
            var ipAll = File.ReadAllText(ipFile).Split(new[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries);

            var lst = new List<string> { "194.206.161.47 - 194.206.161.47", "213.159.160.0 - 213.159.191.255",
                                                 "194.219.52.224 - 194.219.52.239", "217.204.110.64 - 217.204.110.127",
                                                 "217.141.234.232 - 217.141.234.239", "62.27.21.0 - 62.27.21.255",
                                                 "212.82.218.48 - 212.82.218.63", "212.63.174.183 - 212.63.174.183",
                                                 "217.5.150.224 - 217.5.150.231"};

            Parallel.ForEach(ipAll, new ParallelOptions { MaxDegreeOfParallelism = threads }, ip => {

                foreach (var s in lst)
                {
                    var range = IPAddressRange.Parse(s);
                    results.WriteLine($"{ip}|[{range}]|{range.Contains(IPAddress.Parse(ip))}");
                    results.Flush();
                }
            });

            timer.Stop();
            Console.WriteLine("Закончил !");
            Console.WriteLine($"Чекнул {ipAll.Count()}ip в [{lst.Count()}] диапазонах за: {timer.Elapsed.TotalSeconds} сек.");
            Console.ReadKey();
        }
    }
}

Alexmd · 01.12.2022

По поводу перевести диапазон в список ip -плохая затея

Не надо переводить все, а диапазоны представить в числовом виде. Тогда функция проверки принадлежности ip диапазону сведется к операции логического сравнения.

Alexmd · 01.12.2022

Я бы не уповал на

потоков : 100

. Этот параметр носит несколько иной характер и не гарантирует работы в 100 потоков, если конечно, ядер не больше 100. Так что при нагрузке, а не разовом запуске фактическое число потоков с большой долей вероятности уменьшится.
Мы говорим о несколько разных вещах. Оптимизировать как таковую функцию нечем, она простая, как пробка. Речь идет о том, чтобы оптимизировать структуру программы, путем изменением подхода и в конечном счете уменьшения итераций на каждом ip, чтобы обойти функцию написанную в любом из трех представленных вариантов и сравнивать просто числа, а не миллиард раз в сутки проделывать напрасно операции по переводу ip в число.. уверен, что под капотом у этого метода из библиотеки что-то вроде кода, представленного уважаемым Юрием.
Буду у компа, постараюсь показать более наглядно.

костяк есть

формат ip проверяйте, который даете на вход функции. Там же белым по черному написано, в чем проблема

Ilshakin · 01.12.2022

DevOps сказал(а):
Епта, кто Вы такой
Спасибо огромное
ЗЫ Неа, не идет
Ладно, попробую разобраться, костяк есть, поковыряю
Посмотреть вложение 100238

скинь свой файлик с ip и диапазон ip в телегу, в подписи

Alexmd · 01.12.2022

@DevOps просто оставьте здесь два списка.
1 с диапазонами, пусть хоть на миллион строк и 1 на миллион ip.
Так каждый желающий сможет на примере данных оценить свой подход.

Alexmd · 01.12.2022

В общем, поигрался я немного. Надеюсь, это поможет. Таким образом, я легко добился скорости в 15К за 20сек = 45К за мин = 2+KK в час == 60+КК в сутки.

Прикрепил код для консольки в студии.
Конечно, этот тест можно назвать синтетическим. В реальности списки будут куда больше, как я понимаю, но всегда можно разгруппировать список диапазонов и далее: по второму, третьему и четвертому октетам. Тем самым еще больше снизив количество проверок ip по диапазонам. Таким образом, я боюсь предположить, что миллион проверок можно будет проводить и вовсе в пределах 1-ой минуты. Надеюсь, мысль ясна. Дальше сами ;-)

Alexmd · 02.12.2022

DevOps сказал(а):
Вот только запустил Студию чтобы все таки создать словарь со сабсписками. Пока сидел думал, решил сюда заглянуть, а тут вуаля - готовое решение
Я в шоке, спасибо
PS В 20 секунд не получается
Ладно, главное есть, допинаюПосмотреть вложение 100280

с потоками экспериментируйте.
вот, на 8 потоках

а вот на 24, как ядер в системе

В случаях, когда запрос выполняет значительный объем работы, не связанной с вычислениями, такой как ввод-вывод файлов, степень параллелизма может быть больше количества ядер на соответствующем компьютере.
Параллелизм следует понять, прежде чем применять. В данном случае чрезмерное увеличение количества потоков будет только тормозить обработку. Рекомендую или не использовать этот параметр или прописывать по умолчанию WithDegreeOfParallelism(Environment.ProcessorCount)

Как искать IP адрес в списке диапазонов

Client

Client

Client

Client

Client

Client

Client

Client

Client

Client

Client

Client

Client

Client

Client

Client

Client

Client

Client

Client

Client

Client

Client

Client

Client

Вложения

Client

Вложения

Client

Client

Кто просматривает тему: (Всего: 2, Пользователи: 0, Гости: 2)