Определение вхождения IP адреса в диапазон

16 Фев
2012

Введение

После прочтения статьи «Определение страны по IP: тестируем скорость алгоритмов» хотелось бы добавить ещё один интересный способ нахождения вхождения в диапазон IP адресов.

Способ заключается в том, что бы представлять диапазон как отрезок с концами [(-1, ip_range_begin), (1, ip_range_end)] и искать точку (0, ip_address) на данном отрезке.

Структура БД

Структура тестовой таблицы для хранения диапазонов IP:

	CREATE TABLE `country_ip` (
	 `ID` int(11) NOT NULL AUTO_INCREMENT,
	 `IPv4_beg` bigint(11) NOT NULL,
	 `IPv4_end` bigint(11) NOT NULL,
	 `IPv4_GeoRange` linestring NOT NULL,
	 `Country_ID` SMALLINT(4) NOT NULL,
	 PRIMARY KEY (`ID`),
	 SPATIAL KEY `sk_range` (`IPv4_GeoRange`),
	 INDEX `IPv4_beg` (`IPv4_beg`),
	 INDEX `IPv4_end` (`IPv4_end`)
	) ENGINE=MyISAM DEFAULT CHARSET=utf8 PACK_KEYS=0
	


Где IPv4_beg это начало диапазона, IPv4_end конец диапазона, IPv4_GeoRange отрезок и Country_ID это идентификатор страны.

По колонке IPv4_GeoRange нужно создать пространственный индекс SPATIAL KEY `sk_range` (`IPv4_GeoRange`). Данная возможность доступна только для MyISAM.

Данные


Для тестирования использовался всё тот же GeoLite Country.

Для импорта использовался небольшой PHP скрипт:

	<?php

	$options = getopt('f:');

	if (empty($options['f'])) {
	    die(getUsage());
	}

	$filename = $options['f'];

	if (!file_exists($filename) || !is_readable($filename)) {
	    die("Cannot open input file '$filename'.");
	}

	$fp = fopen($filename, 'r');

	$countries = array(
	    'A1' => 1236, 'A2' => 1191, 'AD' => 1189, 'AE' => 1023, 'AF' => 1058, 'AG' => 1176, 'AI' => 1203, 'AL' => 1081,
	    'AM' => 1070, 'AN' => 1190, 'AO' => 1109, 'AP' => 1245, 'AQ' => 1201, 'AR' => 1051, 'AS' => 1227, 'AT' => 1019,
	    'AU' => 1001, 'AW' => 1202, 'AX' => 1188, 'AZ' => 1096, 'BA' => 1093, 'BB' => 1162, 'BD' => 1053, 'BE' => 1022,
	    'BF' => 1148, 'BG' => 1078, 'BH' => 1131, 'BI' => 1173, 'BJ' => 1153, 'BM' => 1037, 'BN' => 1143, 'BO' => 1040,
	    'BR' => 1099, 'BS' => 1047, 'BT' => 1174, 'BV' => 1228, 'BW' => 1192, 'BY' => 1085, 'BZ' => 1091, 'CA' => 1035,
	    'CC' => 1229, 'CD' => 1141, 'CF' => 1170, 'CG' => 1144, 'CH' => 1067, 'CI' => 1128, 'CK' => 1218, 'CL' => 1049,
	    'CM' => 1129, 'CN' => 1002, 'CO' => 1103, 'CR' => 1122, 'CU' => 1197, 'CV' => 1172, 'CX' => 1215, 'CY' => 1082,
	    'CZ' => 1026, 'DE' => 1014, 'DJ' => 1175, 'DK' => 1031, 'DM' => 1052, 'DO' => 1114, 'DZ' => 1105, 'EC' => 1112,
	    'EE' => 1084, 'EG' => 1104, 'EH' => 1214, 'ER' => 1168, 'ES' => 1018, 'ET' => 1124, 'EU' => 1013, 'FI' => 1068,
	    'FJ' => 1059, 'FK' => 1230, 'FM' => 1213, 'FO' => 1180, 'FR' => 1012, 'GA' => 1142, 'GB' => 1020, 'GD' => 1205,
	    'GE' => 1095, 'GF' => 1231, 'GG' => 1183, 'GH' => 1133, 'GI' => 1181, 'GL' => 1182, 'GM' => 1177, 'GN' => 1161,
	    'GP' => 1232, 'GQ' => 1138, 'GR' => 1017, 'GS' => 1233, 'GT' => 1117, 'GU' => 1234, 'GW' => 1235, 'GY' => 1169,
	    'HK' => 1008, 'HN' => 1137, 'HR' => 1092, 'HT' => 1152, 'HU' => 1083, 'ID' => 1043, 'IE' => 1069, 'IL' => 1024,
	    'IM' => 1185, 'IN' => 1005, 'IO' => 1216, 'IQ' => 1087, 'IR' => 1032, 'IS' => 1080, 'IT' => 1016, 'JE' => 1097,
	    'JM' => 1139, 'JO' => 1126, 'JP' => 1003, 'KE' => 1123, 'KG' => 1088, 'KH' => 1055, 'KI' => 1219, 'KM' => 1195,
	    'KN' => 1204, 'KP' => 1242, 'KR' => 1007, 'KW' => 1107, 'KY' => 1198, 'KZ' => 1028, 'LA' => 1241, 'LB' => 1119,
	    'LC' => 1048, 'LI' => 1073, 'LK' => 1115, 'LR' => 1178, 'LS' => 1155, 'LT' => 1090, 'LU' => 1075, 'LV' => 1086,
	    'LY' => 1110, 'MA' => 1108, 'MC' => 1186, 'MD' => 1079, 'ME' => 1163, 'MF' => 1244, 'MG' => 1149, 'MH' => 1200,
	    'MK' => 1066, 'ML' => 1147, 'MM' => 1121, 'MN' => 1060, 'MO' => 1056, 'MP' => 1238, 'MQ' => 1223, 'MR' => 1164,
	    'MS' => 1206, 'MT' => 1150, 'MU' => 1146, 'MV' => 1057, 'MW' => 1160, 'MX' => 1036, 'MY' => 1006, 'MZ' => 1193,
	    'NA' => 1145, 'NC' => 1050, 'NE' => 1157, 'NF' => 1225, 'NG' => 1076, 'NI' => 1154, 'NL' => 1021, 'NO' => 1033,
	    'NP' => 1044, 'NR' => 1248, 'NU' => 1220, 'NZ' => 1041, 'OM' => 1113, 'PA' => 1125, 'PE' => 1106, 'PF' => 1209,
	    'PG' => 1045, 'PH' => 1010, 'PK' => 1046, 'PL' => 1062, 'PM' => 1243, 'PN' => 1226, 'PR' => 1038, 'PS' => 1077,
	    'PT' => 1029, 'PW' => 1239, 'PY' => 1134, 'QA' => 1074, 'RE' => 1196, 'RO' => 1063, 'RS' => 1120, 'RU' => 1027,
	    'RW' => 1156, 'SA' => 1030, 'SB' => 1210, 'SC' => 1179, 'SD' => 1111, 'SE' => 1015, 'SG' => 1042, 'SH' => 1212,
	    'SI' => 1071, 'SJ' => 1100, 'SK' => 1065, 'SL' => 1171, 'SM' => 1098, 'SN' => 1140, 'SO' => 1194, 'SR' => 1165,
	    'ST' => 1247, 'SV' => 1130, 'SY' => 1072, 'SZ' => 1166, 'TC' => 1207, 'TD' => 1151, 'TF' => 1222, 'TG' => 1167,
	    'TH' => 1004, 'TJ' => 1158, 'TK' => 1054, 'TL' => 1246, 'TM' => 1187, 'TN' => 1116, 'TO' => 1221, 'TR' => 1064,
	    'TT' => 1132, 'TV' => 1208, 'TW' => 1009, 'TZ' => 1127, 'UA' => 1025, 'UG' => 1135, 'UM' => 1237, 'US' => 1034,
	    'UY' => 1118, 'UZ' => 1094, 'VA' => 1184, 'VC' => 1240, 'VE' => 1102, 'VG' => 1199, 'VI' => 1039, 'VN' => 1011,
	    'VU' => 1211, 'WF' => 1061, 'WS' => 1217, 'YE' => 1089, 'YT' => 1224, 'ZA' => 1101, 'ZM' => 1136, 'ZW' => 1159
	);

	$db = new PDO(
	    'mysql:dbname=test;host=localhost',
	    'root',
	    'nea2KMRF',
	    array(
	        PDO::ATTR_ERRMODE => PDO::ERRMODE_EXCEPTION
	    )
	);

	$db->query('TRUNCATE TABLE `country_ip`');

	$insertStmt = $db->prepare(
	    'INSERT INTO `country_ip` (`IPv4_beg`, `IPv4_end`, `IPv4_GeoRange`, `Country_ID`)
	     VALUES (?, ?, LineString(Point(-1, `IPv4_beg`), Point(1, `IPv4_end`)), ?)'
	);

	while ($line = fgetcsv($fp)) {
	    if (!empty($countries[$line[4]])) {
	        try {
	            $insertStmt->execute(array(
	                sprintf('%u', ip2long($line[0])),
	                sprintf('%u', ip2long($line[1])),
	                $countries[$line[4]]
	            ));
	        } catch (PDOException $e) {
	            echo $e->getMessage() . PHP_EOL;
	            continue;
	        }
	    }
	}

	function getUsage()
	{
	    echo 'Usage:' . PHP_EOL . 'php ' . __FILE__ . ' -f=filename.csv' . PHP_EOL
	        . "\t" . ' -f ' . "\t" . ' - Input filename.' . PHP_EOL;
	}
	


Тестирование


Запрос с использованием пространственного индекса:
 mysql> explain SELECT SQL_NO_CACHE `Country_ID` FROM `country_ip` WHERE MBRContains(`IPv4_GeoRange`, Point(0, INET_ATON('8.8.8.8')));
+----+-------------+------------+-------+---------------+----------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+------------+-------+---------------+----------+---------+------+------+-------------+
| 1 | SIMPLE | country_ip | range | sk_range | sk_range | 34 | NULL | 1 | Using where |
+----+-------------+------------+-------+---------------+----------+---------+------+------+-------------+
1 row in set (0.00 sec)


Запрос c использованием простого индекса:
 mysql> explain SELECT SQL_NO_CACHE *, INET_ATON('8.8.8.8') FROM `country_ip` WHERE IPv4_beg <= INET_ATON('8.8.8.8') AND IPv4_end >= INET_ATON('8.8.8.8');
+----+-------------+------------+-------+-------------------+----------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+------------+-------+-------------------+----------+---------+------+------+-------------+
| 1 | SIMPLE | country_ip | range | IPv4_beg,IPv4_end | IPv4_beg | 8 | NULL | 271 | Using where |
+----+-------------+------------+-------+-------------------+----------+---------+------+------+-------------+
1 row in set (0.00 sec)


Тест делится на два типа теста:
  1. Кол-во запросов в течении 10 секунд с одним и тем же IP адресом.
  2. Время, потраченное на выполнение 1000 запросов с случайными IP адресами.


Во всех тестах кэш отключен (SQL_NO_CACHE).

Результаты тестирования:
 Started test (10 seconds, single ip) for spatial index.
Result: 4532 queries/sec. Hits:45323

Started test (10 seconds, single ip) for simple index.
Result: 613.9 queries/sec. Hits:6139

Started test (1000 random IPs) for spatial index.
Result: 4296 queries/sec. Hits:804

Started test (1000 random IPs) for simple index.
Result: 25 queries/sec. Hits:804


Код для тестирования:
	<?php

	$testIP    = '8.8.8.8';
	$testTime  = 10;
	$testArray = array();

	for ($i = 0; $i < 1000; $i++) {
	    $testArray[] = mt_rand(1,255) . '.' . mt_rand(0,255) . '.' . mt_rand(0,255) . '.' . mt_rand(0,255);
	}

	$db = new PDO(
	    'mysql:dbname=test;host=localhost',
	    'root',
	    'nea2KMRF',
	    array(
	        PDO::ATTR_ERRMODE => PDO::ERRMODE_EXCEPTION
	    )
	);

	$spatialQueryStmt = $db->prepare(
	    'SELECT `Country_ID` FROM `country_ip` WHERE MBRContains(`IPv4_GeoRange`, Point(0, INET_ATON(?)))'
	);

	$simpleQueryStmt = $db->prepare(
	    'SELECT `Country_ID` FROM `country_ip` WHERE IPv4_beg <= INET_ATON(?) AND IPv4_end >= INET_ATON(?)'
	);

	$endTime = time() + $testTime;
	$counter = 0;
	$hits    = 0;

	echo 'Started test (' . $testTime . ' seconds, single ip) for spatial index.' . PHP_EOL;

	while ($endTime >= time()) {
	    $spatialQueryStmt->execute(array($testIP));
	    if ($spatialQueryStmt->fetchColumn()) {
	        $hits++;
	    }
	    $counter++;
	}

	echo 'Result: ' . intval($counter / $testTime) . ' queries/sec.' . ' Hits:' . $hits . PHP_EOL;

	echo PHP_EOL;

	$endTime = time() + $testTime;
	$counter = 0;
	$hits    = 0;

	echo 'Started test (' . $testTime . ' seconds, single ip) for simple index.' . PHP_EOL;

	while ($endTime >= time()) {
	    $simpleQueryStmt->execute(array($testIP, $testIP));
	    if ($simpleQueryStmt->fetchColumn()) {
	        $hits++;
	    }
	    $counter++;
	}

	echo 'Result: ' . ($counter / $testTime) . ' queries/sec.' . ' Hits:' . $hits . PHP_EOL;

	echo PHP_EOL;

	$hits    = 0;

	echo 'Started test (' . sizeof($testArray) . ' random IPs) for spatial index.' . PHP_EOL;

	$startTime = time() + microtime();
	foreach ($testArray as $ip) {
	    $spatialQueryStmt->execute(array($ip));
	    if ($spatialQueryStmt->fetchColumn()) {
	        $hits++;
	    }
	}
	$endTime = time() + microtime();

	echo 'Result: ' . intval(sizeof($testArray) / ($endTime - $startTime)) . ' queries/sec.' . ' Hits:' . $hits . PHP_EOL;

	echo PHP_EOL;

	$hits    = 0;

	echo 'Started test (' . sizeof($testArray) . ' random IPs) for simple index.' . PHP_EOL;

	$startTime = time() + microtime();
	foreach ($testArray as $ip) {
	    $simpleQueryStmt->execute(array($ip, $ip));
	    if ($simpleQueryStmt->fetchColumn()) {
	        $hits++;
	    }
	}
	$endTime = time() + microtime();

	echo 'Result: ' . intval(sizeof($testArray) / ($endTime - $startTime)) . ' queries/sec.' . ' Hits:' . $hits . PHP_EOL;
	
По материалам Хабрахабр.



загрузка...

Комментарии:

Наверх