Определение страны по IP: оптимизация

[young]

Определение страны по IP: оптимизация

Задача: получить страну по IP потратив минимум времени и ресурсов.

Текущее решение: есть упорядоченный список диапазонов IP:

ip_from int
ip_to int
country_id int

список диапазонов упорядочен, диапазоны между собой не пересекаются, всего их 70 000. Диапазон содержит от 1 до нескольких миллионов IP.

запрос select country_id from TBL where ip_from < A and ip_to > A limit 1 выполняется в среднем 0,02 секунды, что есть очень долго.

никакие индексы не помогают (пробовал хеш-индексы по ip_from / 2^24, просто индекс по ip_from, составной индекс) и прочие другие

из идей разве что составить таблицу соответствия

ip (int) primary key
country_id (int)

на 3 миллиона и делать выборку по primary key.

либо как-то на php прикручивать двоичный поиск.

других идей нет.

Ваши идеи?

 

[rotoZOOM]

Сложность надеюсь не в том, КАК осуществлять двоичный поиск (это просто и количество итераций будет приблизительно 16 на запрос), а в том, что при каждом запросе необходимо будет подгружать всю таблицу интервалов в память (а это 12 байт на запись минимум, таким образом 840 К). Если запустить процесс как демон, который бы висел и принимал запросы от программ клиентов, то проблема была бы решена.

 

[hermit_refined]

а
[SQL]SELECT country_id, ip_from FROM tbl WHERE ip_to > a ORDER BY ip_to LIMIT 1[/SQL]при индексе (обычном) по ip_to ?

никакие индексы не помогают

а они используются?

 

[young]

hermit_refined
О! в твоем вариант работает супер

но есть одно но - IP может не входить ни в один из диапазонов

а если к твоему запросу дописать условие and ip_from < A возвращаются прежние тормоза

прийдется уже на стороне php проверять вошел ли он в диапазон, и если нет - значит unknown country

-~{}~ 11.01.07 21:05:

но в целом, такой вариант устраивает.
thnx!

 

[grigori]

Автор оригинала: young
прийдется уже на стороне php проверять вошел ли он в диапазон, и если нет - значит unknown country

Можно и
[sql]
SELECT country_id, ip_from,
if(ip_from<a,1,0) as in_range
FROM tbl
WHERE ip_to > a
ORDER BY ip_to
LIMIT 1
[/sql]

 

[Wicked]

hermit_refined
а почему такой эффект?

 

[Term2]

А как ты собрал эти диапазоны IP по странам?

 

[young]

Term2

они есть в публичном доступе
поищи по ip2country в google
точной ссылки не помню

 

[vovanium]

Вообще использование для этих целей MySQL не эффективно. Самый эффективный алгоритм который я видел, это алгоритм собственной разработки Пока на стадии беты с рабочим названием Sypex Geo.
Я уже тут как то выкладывал описание.
В общих чертах это алгоритм на чистом php использует базу в виде бинарного файла собственного формата.
- Скорость работы при пакетной обработке на моем компе достигает 10 000 IP в секунду (без кэширования базы в памяти), для сравнения алгоритм GeoIP показывал в 5 раз меньше производительность, а MySQL вообще 20-30 IP в сек.
- Размер базы на основе GeoLite Country всего ~320 КБ (что в 2 раза меньше бинарной базы самого GeoIP)

Т.е. MySQL в чистую проигрывает специально заточенным решениям, что и не удивительно.

Скачать версию для тестирования можно здесь
http://sypex.net/files/SypexGeo.rar

 

[clevel]

неожиданный конец архива....
перезалей, плз... инетресно посмотреть на решение...

 

[vovanium]

clevel
поправил

 

[magic]

> Ваши идеи?

Maxmind Geo Country Binary Format (100 000 req/sec)

Платно: http://www.maxmind.com/app/country
Бесплатно: http://www.maxmind.com/app/geoip_country

 

[Wicked]

vovanium
можешь описать, что из себя представляет файл с данными, и каким образом происходит поиск? По сорцам понять довольно сложно.

 

[vovanium]

magic

Maxmind Geo Country Binary Format (100 000 req/sec)

Это только в случае если GeoIP работает, как демон причем СИ-шная версия.
А реально чисто php'шная версия GeoIP проигрывает моему варианту в 5 раз, т.е. сам алгоритм у них медленнее Это легко проверить.
Wicked
Извини, описывать особо не буду, так как на базе этого алгоритма будет распространяться аналог GeoIP.
Как и в случае с GeoIP будет бесплатная версия, обновляющаяся 3 раза в месяц, и платная версия с частотой обновления несколько раз в неделю. Пока что в комплекте база на основе февральского GeoLite Country, чтобы сравнение и тестирование было более корректным, в дальнейшем будет своя база.
Насчет алгоритма скажу лишь, что в данном случае поиск по отсортированному списку оказался быстрее поиска по бинарному дереву, которое используется в GeoIP.

 

[MiksIr]

Попробуйте поискать про Patricia tree.

 

[Wicked]

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

 

[phprus]

Wicked
Реализацию хештаблици можно посмотреть в http://risearch.org/rus/risearch_php/index.html, правда не знаю на сколько она качественная. Кроме этого я видел псевдокод (код на perl) выложенный Silent вот сдесь: http://phpclub.ru/talk/showthread_old.php?s=&threadid=25325

А вот ссылку на реализацию какого-то дерева я гдето видел на этом форума и вроде бы ее даже вы оставляли но сейчас я ее найти не смог.

vovanium
А реализация вашего алгоритма на С или С++ будет?

 

[Wicked]

Реализацию хештаблици можно посмотреть в http://risearch.org/rus/risearch_php/index.html, правда не знаю на сколько она качественная.

к сожалению, не очень. Хотя, за годик-другой может чего и изменилось.

 

[StUV]

А реализация вашего алгоритма на С или С++ будет

имея исходники на пхп ничто не мешает сделать это самостоятельно

 

[phprus]

StUV
Ничего кроме лени

vovanium
Нашел баг. Ваша библиотека определяет несуществующие адреса как адреса из страны с кодом NA (Namibia) а все из-за того, что в нулевом элементе массива $this->num2cc написано NA (на сколько я понимаю нулевой элемент - это код несуществующей страны) После замены его на пустую строку все стало работать как надо.

Wicked
А какие у вас критерии качественной реализации?