определение географии по ip в счётчике

[lorien]

определение географии по ip в счётчике

Пишу счётчик. Иноформация собирается в сырой лог, потом парсится N-ыми кусками. При парсинге требуется определять географию по ip-адресу.

Как это лучше сделать? Скрипт будет постоянно висеть в памяти, так что я думаю, чтобы базу не мучать, надо бы это всё дело загрузить в память.

Как можно организовать хранение диапазонов с целью наибыстрейшего поиска в них?

Пока на ум приходит только такое:
Массив с числовыми индексами, каждый элемент которого является массивом вида(начало диапазона, конец диапазона, ID страны)
Элементы глобального массива упорядочены по возрастанию начала диапазона каждого подмассива....
Я имею в виду:

$ranges = array(
'0' => array(0,23,3),
'1'=> array(25,333,13),
'2'=> array(334,2323,9)
);

Затем берём ip-адрес и смотрим в какой половинке массива он находицца, потом берём половинку половинки и т.д.

У кого-нить есть предложения, замечания?

 

[Tor]

в каком виде у тебя база по регионам?

 

[Necromant]

$zone =  '82.148.254.0/24';
$ip_check = '82.148.254.122';

list($ip, $mask) = explode('/' , $zone);
$ip = ip2int($ip);
$ip_check = ip2int($ip_check);
if ($ip>>(32-$mask)==($ip_check>>(32-$mask))) {
   echo 'ok';
} else {
   echo 'false';
}

 

[lorien]

2Tor: у меня диапазонам адресов сопоставлен id страны, а разве можно ещё как-либо хранить эту информацию?

2Necromant: Что ты хотел сказать этим кодом? Кстати, диапазоны стран, как я понимаю, не обязаны быть выравнены по четвёртому байту.

 

[Tor]

у меня диапазонам адресов сопоставлен id страны

и что, поиск по этой базе много времени отнимает?

 

[lorien]

Пока юзаю такую функцию. Только, кажется, это дело ещё дольше чем с бД работает... Буду разбираться....

	function get_id_country( $ip, $ip_proxy ) {
		if ( empty($this->geo_cache) ) {
			$this->LoadGeoCache();
		}
		$ip_proxy and $ip = $ip_proxy;
		
		$min = 0; $max = sizeof($this->geo_cache)-1;
		
		$count = 0;
		while ( true ) {
			$idx = floor(( $max + $min ) / 2);
			
			if (
				$this->geo_cache[$idx]['start'] <= $ip and
				$this->geo_cache[$idx]['end'] >= $ip
			) {
				return $this->geo_cache[$idx]['id_country'];
			}
			
			if ( $this->geo_cache[$idx]['end'] <= $ip ) {
				$min = $idx+1;
			} else {
				$max = $idx-1;
			}
			if ( $min > $max ) {
				return 0;
			}
		}
		return 0;
	}

 

[Necromant]

А , кто сказал , что имеено по 4 ?
где ты ето увидел ?
'82.148.254.0/24 никто не мешает , 82.148.254.0/13
если таблица , с предварительно сформироваными границами , по типу
zone | start | end

где, все множество IP , принаджещих зоне лежит между start | end

 

[Steamroller]

lorien, надо юзать какую-то готовую библиотеку. Для работы с такими данными используются Radix Trees.
При не очень большой нагрузке - можно в принципе обычную базу, в таблицу - столбцы с ид страны, началом диапазона, концом диапазона, индексом по началу диапазона, соответственно брать что-то типа where ip>=start_ip and ip<=end_ip order by start_ip desc, end_ip desc limit 1;.

-~{}~ 05.10.05 19:33:

Блин, наврал с запросом, так он тормозить будет, в общем главное - такую таблицу сделать, затем последовательно двумя селектами к ней.

 

[lorien]

У меня почему-то получается, что если делать селект на каждый ip к БД, то это работает быстрее, чем бинарный поиск каждого ip по массиву, который в памяти лежит.

Неужели я настолько кривую функцию написал? :-(
Код функции я уже привёл, а массив весит около 74070 * 9 = 600 кило

SteamrollerЗачем два запроса и зачем там у тебя ORDER BY?

Как-то скудно в поисковиках про эти radix trees. Ещё, как я понял, их patricia tree называют. Почему поиск по patricia tree, быстрее простого бинарного поиска по списку диапазонов я тоже не понял.
Если у кого есть хорошая ссылка, ткните, плиз.

 

[Tor]

а не легче не мучаться с диапазонами,а занести КАЖДЫЙ адресс в базу данных
ну побить для облегчения поиска на 8(16,32,...) баз (по первым битам)
скрипт, который обновляет базу, будет не шустрым
зато поиск (при хорошей машинке, да с правильным объемом памяти) будет летать

 

[lorien]

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

Сам запрос к БД довольно элементарный, так что если дифференцировать диапазоны на отдельные адреса и разнести всё это дело по базам, то быстродействие вряд ли станет много больше, чем в случае простого "SELECT id FROM .. WHERE ip BETWEEN start AND end"

 

[Tor]

если держать всю таблицу адресов в памяти, то поиск по ней в таком случае должен быть быстрее, чем обращение к БД

БД тоже может быть вся в памяти

 

[Steamroller]

У меня почему-то получается, что если делать селект на каждый ip к БД, то это работает быстрее, чем бинарный поиск каждого ip по массиву, который в памяти лежит.

Неужели я настолько кривую функцию написал? :-(

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

Зачем два запроса и зачем там у тебя ORDER BY?

Смысл в том, что обычно на реальных базах соответствия ip-country существуют вложенные диапазоны, и для ip надо находить минимальный диапазон.
Если в твоей базе нету такого - то и не нужно ни двух селектов, ни order by.

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

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

 

[lorien]

Ок, почитаю про Б-деревья.
Кстати, после того как я залил скрипт на сервер ситуация коренным образом поменялась. Работа с БД стала намного медленнее (т.к. рабочий mysql-сервер нагружен ещё другими задачами, зато бинарный поиск стал быстро работать)
Вся фишка, как я понял, в том, что на сервере стоит зенд оптимайзер, на локальной машине - нет.

upd: от БД в памяти(type=memory), как я понял, толку нету т.к. тормозит не поиск по БД, а само обращение к ней.