Как бы вы сравнили IP-адрес?
Для моего серверного приложения мне нужно проверить, есть ли ip-адрес в нашем черном списке.
Каков наиболее эффективный способ сравнения IP-адресов? Будет ли преобразование IP-адреса в целое число и сравнение их эффективно?
12 ответов
Зависит от того, какой язык вы используете, но IP-адрес обычно хранится в виде 32-разрядного целого числа без знака, по крайней мере, на сетевом уровне, что делает сравнение довольно быстрым. Даже если это не так, если вы не разрабатываете высокопроизводительное приложение с коммутацией пакетов, оно вряд ли будет узким местом в производительности. Избегайте преждевременной оптимизации - разработайте свою программу для тестируемости и масштабируемости, и если у вас есть проблемы с производительностью, вы можете использовать профилировщик, чтобы определить узкие места.
Изменить: чтобы уточнить, адреса IPv4 хранятся в виде 32-разрядных целых чисел плюс маска сети (которая не требуется для сравнения IP-адресов). Если вы используете более новый и в настоящее время более редкий IPv6, то адреса будут иметь длину 128 бит.
32-разрядные целые числа - путь, пока вы не начнете работать с 128-разрядными адресами IPv6.
Вы имеете в виду, если вы должны сравнить его как текстовую строку или преобразовать int в int и сравнить как int?
Это обычно не является узким местом в такого рода поисках. Вы можете просто попробовать реализовать оба метода и посмотреть, какой из них работает быстрее.
Реальная проблема с поиском IP-адреса обычно заключается в создании эффективных запросов, использующих тот факт, что вы имеете дело с IP-адресами, а не просто случайными числами. для достижения этой цели вы можете посмотреть LC Trie и, возможно, эту статью
Очевидно, это должно вас заинтересовать, только если ваш черный список содержит десятки тысяч или миллионы записей. Если в нем всего 10-20 записей, предпочтение следует отдавать линейному поиску, и, действительно, более интересным вопросом является текстовое сравнение с целочисленным сравнением.
static public bool IsEqual(string ToCompare,
string CompareAgainst)
{
return IPAddressToLongBackwards(ToCompare)==IPAddressToLongBackwards(CompareAgainst);
}
static private uint IPAddressToLongBackwards(string IPAddr)
{
System.Net.IPAddress oIP=System.Net.IPAddress.Parse(IPAddr);
byte[] byteIP=oIP.GetAddressBytes();
uint ip=(uint)byteIP[0]<<24;
ip+=(uint)byteIP[1]<<16;
ip+=(uint)byteIP[2]<<8;
ip+=(uint)byteIP[3];
return ip;
}
Если я вас правильно понимаю, это код для сравнения двух IP-адресов. Вы хотите это? В дальнейшем вы можете делать такие вещи, как:
static public bool IsGreater(string ToCompare,
string CompareAgainst)
{
return IPAddressToLongBackwards(ToCompare)>
IPAddressToLongBackwards(CompareAgainst);
}
потому что вы получили адрес байтов.
Да, я обнаружил, что, чтобы быть эффективным, это займет много времени, и, конечно, вы должны индексировать IP-адреса из черного списка в целочисленной форме.
Я сделал это и проверил, использование unsigned int (32-битное) является самым быстрым - я предполагаю, что вы сравниваете это со строковым представлением.
Еще одна вещь, которая может вам помочь, - это создание таблицы, в прошлом у меня было 2 столбца: LowIP и HighIP; таким образом я смог занести в черный список целые диапазоны IP-адресов с одной записью и по-прежнему получать хорошую производительность, проверяя IP-адрес в диапазоне.
Однажды я унаследовал код, в котором кто-то думал, что хранить IP-адреса в виде 4-х int было действительно хорошо, за исключением того, что они проводили все свое время, конвертируя в / из int.
Хранить их как строки в базе данных было намного проще, и для этого требовался только один индекс. Вы будете удивлены, насколько хорошо сервер SQL может индексировать строки, а не 4 столбца целых чисел. Но этот список IP не был предназначен для внесения в черный список. Обход базы данных довольно дорогой.
Если база данных избыточна, сохраните их в словаре в памяти, но это только предположение, поскольку мы не знаем, сколько вам нужно сравнить. Поскольку большинство хеш-кодов являются 32-битными целыми числами, а IPv4-адреса являются 32-битными, сам IP-адрес может быть просто хорошим хеш-кодом.
Но, как отмечают другие, лучшим вариантом может быть снижение нагрузки на ваш сервер и покупка специализированного оборудования. Возможно, вы храните недавно занесенные в черный список IP-адреса в памяти и периодически публикуете новые на маршрутизаторе.
Если вы один из тех, кто пытается создать какое-то программное обеспечение внутри маршрутизатора, то вам нужно найти свою книгу о структурах данных и создать что-то вроде b-дерева.
Используйте такой инструмент, как PeerGuardian, который запрещает входящие TCP/IP-соединения на уровне драйвера для IP-адресов в черном списке. Высокий уровень безопасности, код не требуется (возможно: высокий уровень безопасности, потому что код не требуется).
Radix или PATRICIA Trie - оптимальная структура для этого.
Проверьте источник C для flow-tools: http://www.splintered.net/sw/flow-tools/
Я работал над этим несколько лет назад.
Целочисленные сравнения намного быстрее, чем сравнения строк.
Если вы храните целые числа в отсортированном списке, вы можете найти их быстрее, чем в несортированном списке.
Есть ли у вас проблемы с эффективностью?
Если так, то непременно опубликуйте код (или псевдокод), и мы сможем выбрать труп.
Если нет, то я бы предложил попробовать что-то простое, например, сохранить записи в отсортированном списке и использовать существующие в вашей среде Sort() а также Find(),
Если вы получаете IP-адрес в виде строки, сравнение его со строкой может быть более эффективным, чем преобразование его в целочисленное представление
но я бы профилировал оба решения, чтобы быть уверенным, если несколько миллисекунд (наносекунд!) будут иметь значение для этой операции;-)
Следующий я использовал в JavaScript
function isValidIPv4Range(iPv4Range = '') {
if (IP_V4_RANGE_REGEX.test(iPv4Range)) {
const [fromIp, toIp] = iPv4Range.split('-');
if (!isValidOctets(fromIp) || !isValidOctets(toIp)) {
return false;
}
const convertToNumericWeight = ip => {
const [octet1, octet2, octet3, octet4] = ip.split('.').map(parseInt);
return octet4 + (octet3 * 256) + (octet2 * 256 * 256) + (octet1 * 256 * 256 * 256);
};
return convertToNumericWeight(fromIp) < convertToNumericWeight(toIp);
}
return false;
}