Pull to refresh

Comments 93

PRIMARY KEY (`ipn1`),
INDEX `ipn2` (`ipn2`)
Я бы на вашем месте снёс свой обзор в черновики и пошёл учить мат. часть про индексы в MySql
Хм, и что не так с индексами хоть бы намекнули. Да и тут вообще-то рассматриваются популярные решения, встречающиеся в инете.
Нормальная структура для использования индекса и запрос должны быть примерно такими:

CREATE TABLE `worldip` (
  `start` int(10) UNSIGNED NOT NULL default '0',
  `end` int(10) UNSIGNED NOT NULL default '0',
  `code` varchar(2) NOT NULL default '',
  PRIMARY KEY (`start`,`end`)
) ENGINE=MyISAM;

SELECT code FROM `worldip` WHERE `start` <= INET_ATON('IP') AND `end` >= INET_ATON('IP') LIMIT 1


Индекс должен быть сдвоенным в общем.
Я в статье не правильно описал проблему, индекс то используется, только можно сказать не полноценно.
И составные индексы тут погоды не делает.
Вот explain для двух вариантов, первый для составного ключа, второй вариант для двух отдельных индексов
id	select_type    table	                   type	possible_keys  key        key_len    ref	rows        Extra
1	SIMPLE	       ip2country_copy  range	PRIMARY		PRIMARY	4	NULL	1648	Using where
1	SIMPLE	       ip2country_copy  range	PRIMARY,idn2	PRIMARY	4	NULL	1579	Using where

Второй вариант даже чуть лучше
А что именно там? Как раз запрос с вложенным SELECT который там советуют для определения страны по IP и участвует в этом тесте. Просто, есть еще два более простых запроса, хотелось наглядно показать насколько они тормозные.
Честно-говоря, не совсем понятно зачем этот sub-select вообще нужен, т.е. зачем усложнять запрос.
Когда два года назад решал эту же задачу на базе MaxMind, то обошелся
просто запросом:
SELECT * FROM ip2country WHERE `ipn1` <= INET_ATON('IP') ORDER BY `ipn1` DESC LIMIT 1

где индекс по полю `ipn1` будет использоваться как для фильтра, так и для сортировки.
Зачем вообще добавлять условие
WHERE `ipn2` >= INET_ATON('IP')
?
Там «дырки» есть в диапазонах, в итоге при попадании IP в «дырку» будет неправильно определена страна.
Теоретически вы правы, но думаю, что такое если и будет случаться, то крайне редко
В таком запросе индекс не будет использоваться.
mysql> EXPLAIN SELECT code FROM `worldip` USE INDEX (PRIMARY)
WHERE `start` <= INET_ATON('8.8.8.8') AND `end` >= INET_ATON('8.8.8.8') LIMIT 1;
+----+-------------+---------+--------+---------------+------+---------+------+------+-------+
| id | select_type | table   | type   | possible_keys | key  | key_len | ref  | rows | Extra |
+----+-------------+---------+--------+---------------+------+---------+------+------+-------+
|  1 | SIMPLE      | worldip | system | PRIMARY       | NULL | NULL    | NULL |    1 |       |
+----+-------------+---------+--------+---------------+------+---------+------+------+-------+
Для такого запроса вторая часть индекса не будет использоваться никогда.

Два разных индекса в этом случае будут удобнее в том смысле, что оптимизатор сможет выбирать.
SELECT code FROM `worldip` WHERE `start` <= INET_ATON('IP') AND `end` >= INET_ATON('IP') LIMIT 1
Индекс должен быть сдвоенным в общем.

Второй сегмент индекса будет задействован в случае, если на первый наложено условие по равенству, а в вашем случае это не так, будет скан диапазона по первому полю от минимальных значений до искомого IP, и чем больше значение INET_ATON('IP'), тем хуже.
структура mysql базы необязательно должна быть такой:
можно хранить 1.1.1.0\24, и запрос тогда будет совсем другим.
Не очень представляю как в таком случае сделать быструю выборку.
Вы не правильно их готовите.
Вы пробуете искать в базе по открытому интервалу, те в начале ищем ВСЕХ левее, потом ВСЕХ правее. Потом пересекаем.
А можно и проще.
Вариант 1 — WHERE ip1<$ip ORDER BY ip1 DESC LIMIT 1.
Потому что нет пересекающихся регионов, есть вложенные.
Это это открытый интервал.
Найдем максимальную ширину IP адреса. те MAX(ip2-ip1). В зависимости от базы это значение разное, но вообще — не более 32к те /16
Вариант 2 — WHERE ip1 between ($ip-$maxWidth) and $ip ORDER BY ip1 DESC LIMIT 1.
Таким образом поиск производиться в закрытом диапазоне.

Также есть вариант когда у нас составной индекс, и можно искать как WHERE (ip1>$1 and ip2<$2) and(ip1<$ip and ip2>$ip) еще более ограничивая вариативность операций в базе.
На самом деле диапазоны бывают и даже по 30 млн. к примеру (28.0.0.0-30.255.255.255 — US)
Да я и не говорил, что не могу такую выборку сделать, я имел ввиду, что она не получится быстрее запроса с вложенным SELECT.

По-поводу составного индекса, выше уже замечали, что нормально работает, если по одному из столбцов стоит равенство, в случае когда у обоих значений стоит больше/меньше, то лучше вообще индекс по одному полю строить.
Добавьте пожалуйста в обзор эту базу:
www.wipmania.com/ru/base/

Там как раз нормально с индексом используется mysql
Там просто объединенный индекс, он работает так же как два индекса отдельных. Я в статье несколько неправильно сформулировал насчет индекса. Сейчас подправлю.
В том то и дело, что работает он не как два отдельных индекса, а эффективнее. Вот и интересно, изменит ли график и на сколько именно такой вариант.
Я проверил, составной индекс в данном случае работает медленнее примерно процентов на 10-15%.
Выше explain привел, который проясняет почему, в составном индексе получается больше строк для перебора.
Ясно, большое спасибо )
И вообще за SxGeo огромное спасибо — очень полезная библиотека.
UFO just landed and posted this here
А если таблицу в MySQL уже отсортированной хранить? Если использовать в MySQL таблицы в памяти?
Если памяти достаточно и буфера настроены так, как полагается — тогда innodb и так будет держать всё в памяти. Сортировка есть в индексах, а вы предлагаете по какому полю её хранить сортированной?
По ipn1, тогда в subquery не потребуется сортировка.
Сортировка не потребуется, если субд будет знать, что сортировка уже есть. А без order by порядок ничем не гарантируется.
Что-то не понял вашу мысль.
Основная идея: чем хранение таблицы в отсортированном состоянии поможет? Какую операцию это упростит?
Очевидно же: уйдёт сортировка по полю в подзапросе.
Не уйдёт — субд не гарантирует порядок в резалтсете без указания сортировки.

Оптимизация, способ хранения данных на диске, кеширование и прочее вполне могут всё испортить.
Вы это сами придумали или в документацию всё-таки посмотрели?
ORDER BY enables you to create the new table with the rows in a specific order. Note that the table does not remain in this order after inserts and deletes. This option is useful primarily when you know that you are mostly to query the rows in a certain order most of the time. By using this option after major changes to the table, you might be able to get higher performance. In some cases, it might make sorting easier for MySQL if the table is in order by the column that you want to order it by later.

dev.mysql.com/doc/refman/5.1/en/alter-table.html
WHERE `ipn1` <= INET_ATON('IP') ORDER BY `ipn1` DESC

Для этого вложенного запроса индекс по `ipn1` разрулит и сортировку.

Что именно вы хотите улучшить, убрав сортировку и добавив указанный выше костыль?
Он «разрулит» сортировку не каким-то магическим образом. Это работа, менее серьёзная, но работа. «Костыль», как вы изволили выразиться, призван избавить MySQL от этой работы. Конечно, у него есть недостатки (описанные в документации выше), поэтому он применяется для данных, которые меняются редко (как списки geoip).

С чем вы пытаетесь поспорить, я не понимаю.
«менее серьёзная, чем сортировка таблицы, но работа»
Отнюдь нет, он НИКАКОЙ работы производить не будет.

`WHERE `ipn1` <= INET_ATON('IP')` — для этого условия мы в дереве находим первый ряд, для которого условие истинно (поиск в B-Tree, LogN)
`ORDER BY `ipn1` DESC` — по индексу мы будем идти от больших к меньших (mysql не поддерживает desc, так что всегда именно так)
`LIMIT 1` — берём первый ряд (тот самый, который мы уже нашли в шаге 1)

никакой дополнительной работы тут нет. Сортировка тут несёт декларативную задачу, просто подсказывая в какую сторону отсчитывать ряды.

С чем я пытаюсь поспорить — с тем, что ваше предложение имеет хоть какую-то практическую пользу
По умолчанию в MySQL нет никакой сортировки. Сортировка будет только тогда, когда мы в запросе напишем ORDER BY.
Прошу прощения, это должен был быть ответ к этому комментарию
По-умолчанию — нет. Можно добиться, чтобы была.
Спасибо, отличный инструмент.

А тоже самое, но уже с точностью до города?
UFO just landed and posted this here
Пока в этом направлении не смотрел. Думаю для начала прикручу поддержку городов, потом глянем на ipv6.
ежу понятно, что древовидные алгоритмы в разы быстрее линейных.
сам как-то писал велосипед по определению города по IP
а алгоритме использовался RBTree с ключом IPmin в котором лежала структура: IPmax, CityId
Тестирование показывало отличные результаты (по Городам RF, BY, UA) но база занимала много памяти
Была идея использовать его в качестве модуля для nginx
к сожалению инвестор решение отверг и я переключился на реализацию других проектов
Автор, скоро уже PHP 6 выйдет, а вы еще в PHP4 стиле пишите. А за обзор спасибо.
К сожалению есть пару старых клиентов, которые никак не обновятся :(
Документацию класса и методов в PHPDoc или смежном формате никто не отменял :)
Как не ухищряйся, а быстрее памяти не прыгнешь, так что все равно в чем хранить и как выбирать.
Самое главное формат хранения адресов.
Я бы предложил свести поиск к
select country from table where table.ip>= '11.22.33.44' order by table.ip limit 1
ну и кластерный индекс по ip, храинть конец диапазона.
ну и ip хранить и сравнивать как число для нормализации
«нормализация» — не в смысле «нормальной модели»
А с PostgreSQL не пробовали тесты проводить? У них есть расширение ip4r, которое достаточно шустро ищет по IP.
С PostgreSQL не работал, потому не пробовал :(
А расскажите, как вы тестировали, тогда я попробую PostgreSQL потестить.
UFO just landed and posted this here
Это Вы про GeoIP? Никто не спорит, что СИ быстрее PHP, но скорее всего SxGeo будет быстрее если его портировать на СИ, алгоритм более быстрый, да и база меньше, т.е. с меньшим объемом данных работать нужно.
Сам не так давно возился с базами геотаргетинга.
Было бы интересно, если бы автор рассказал про свой формат бинарной базы.
Когда я пытался воссоздать бинарную базу GeoIPCity, то смог сделать это по алгоритму с этой страницы Compressing dictionaries with a DAWG.

Ну а про скорость, php — странное решение в вопросах скорости. У того же MaxMind есть C-API и доступ к нему из PHP. Я вот взял питоновскую обёртку вокруг С-API и получил скорость 310 000 запросов в секунду, а ваш тест 50 000.

P.S. Кстати у вас ошибка в sxgeo_bench.php, неправильно указано имя класса
О формате еще напишу, если будет многим интересно. В дальнейшем также думаю выложу скрипт для конвертирования, пока сыроват, и еще в доработке.

Что касается PHP, это просто мой основной язык, потому на нем привычнее. Но думаю потом вполне можно портировать на другие языки, алгоритм довольно простой.

P.S. Спасибо ошибку поправил.
нас (wipmania) много спрашивали базу в бинарном формате, но сделать свой — руки не доходили, можно ли пользовать ваш? Тогда следующие базы выложим дополнительно и в этом виде.
У нас есть база в бинарном виде, но она для модуля geoip из xtables-addons для iptables.
Автору однозначно плюс за то, что поделился создал качественный продукт и поделился им.
Скажите, пожалуйста, а как можно сконвертировать базу от MaxMind, например, в формат вашей базы? В статье не нашёл. Спасибо
Пока, что скрипт конвертилки не выкладываю в открытый доступ, т.к. еще планируется доделать работу с базами для городов, и он в очень девелоперском состоянии, стрёмно выглядит. Если интересно могу сгенерить бинарник по любой другой базе, кидайте в личку.
А вообще планируете выкладывать? Базы то постоянно обновляются. Каждый раз не хотелось бы вас дёргать :)
Да планирую выложить как закончу с городами. В принципе процесс можно автоматизировать, чтобы кроном проверялось обновление и генерился файл.
Вообще в TODO еще над системой обновления поработать, чтобы не нужно было в ручную дергать, в теории файл, должен отлично обновляться по частям.
Стрёмно выглядит — выкладывайте на гитхаб и принимайте пулл-реквесты. Социальное программирование оно такое :-)

(Не иронизирую, на самом деле так и есть — чем раньше продукт в любом состоянии появится на публике — тем раньше получит полезный фидбэк)
нужна версия на С и перекодировщик из других форматов в ваш, иначе в реально высоконагруженом проекте не имеет применения
совершенно некорректно сравнивать БД и специальные программные средства — работающие в памяти
для начала посмотрите как именно работает between в MySQL, в статье как раз показано как делать такое на БД
habrahabr.ru/blogs/mysql/125467/
извинияюсь что ссылка на мой пост — зато на хабр.
А второе засуньте все индексы и таблицы в кэш и посмотрите на скорость — поверьте она вас приятно удивит (10000/sec для MySQL это далеко не предел)
Почему это сравнивать некорректно? Я сравнивал решения, которые часто встречаются в инете и применяют для одной и той же задачи. У меня не стояло задачи добиться максимальной производительности каждого из вариантов.
В таком случае извиняюсь, просто судя по тому, что что в MySQL вы использовали три конструкции для поиска я было решил, что вы ищете наиболее быстрый вариант для работы с БД.
Попробую протестить еще Ваш вариант на днях. Просто у Вас же еще тестирование было внутри MySQL, при тестировании из PHP или другого клиента будет скорость явно ниже.
Из спортивного интереса набросал тест, делающий выборку стран по случайным IP из массива в памяти — получилось около 10000000 IP/sec. Подозреваю, что основное влияние на результаты оказал собственно скрипт тестирования.
На каком языке этот тест был? Железо же тоже отличается.
Delphi 7, Core i3 2120 в одном потоке. Это не php, но раз тестируется скорость — полезно для понимания результатов. Было интересно почему такие маленькие цифры.
Ну это уже видимо издержки скриптовых языков с динамической типизацией, ради интереса попробовал загнать базу полностью в массив, прибавка получилась 20%, но и памяти больше жрёт.
Интересно будет портировать SxGeo, на какой-нибудь компилируемый язык.
Кого сейчас волнует 10 Мб памяти? К тому же скорость никому кроме анализаторов логов не особо нужна.
Ну к примеру, на тестовом серваке, как раз скрипт уперся в ограничения памяти, пришлось поменьше сделать тестовых айпишек, когда я попытался просто загнать базу в массив.
А что будет когда база будет для городов, там уже речь о 2,5-3 млн. диапазонов.
Если я не ошибаюсь, то автор определяет по диапазону ip, а вы по ключу в массиве, что конечно быстрей, но вам придется тогда хранить вообще все ip в этом массиве, что лишено смысла.
Я взял ту же самую базу GeoLite Country. Дают IP — возвращаю страну, город тоже попробовал — там база побольше, немножко медленнее выходит.
Все хранить не надо, только концы диапазонов. Следующий начинается там, где предыдущий закончился. Поиск дихотомией. Можно и пооптимизировать если захочется.
Если оптимизировать и поменять комплятор на понимающий инлайны, будет 150 000 000 IP/sec с одного треда.
И да, мне самому интересно куда столько девать ;)
Понравилась статья, все подробно описано, а главное, т.е. вывод — просто няшка, ничего не навязывается, а хочется сразу взять и даже не тестировать, а уже использовать.
Конечно понятно, что чем больше IP/сек, тем меньше ресурсов сервера используется. Но меня интересует вопрос с другой стороны. Сколько IP/сек может потребоваться огромному сайту (гугл, фэйсбук или что-то такое)? Ведь для каждого пользователя это нужно определить только в редких случаях. Например, при первом входе, на этапе регистрации или при смене его места нахождения (гео-сервисы). Как мне кажется, этот максимум получится не таким и большим, например, 10 000 IP/сек
zapimir, а Вы можете выложить скрипт-конвертер GeoIP->SxGeo? Хочется иметь возможность переодически «освежать» базу, не завися от графика выхода новых версий.
Доделаю расширением формата, чтобы была поддержка городов, после чего выложу скрипт для конвертирования в формат SxGeo. Также планируется выпуск модулей для Apache и nginx.
Порадовала молниеносная скорость даже на SXGEO_FILE.

Теперь о пожеланиях: хотелось бы видеть список стран в виде полного названия, а не только двухбуквенного кода. Вообщем-то, можно добавить файл с определением массива, вроде такого $sxgeoCountries = array('EN' => 'England', 'RU' => 'Russia', 'US' => 'United States'). На этой странице было бы неплохо повесить черные tooltip'ы на флажки: driversworld.us/app/user/profile/?id=1
А что на счёт mod_geoip?

На сайте есть сравнение, если я правильно понял, то разница между PHP и C API колоссальная www.maxmind.com/app/benchmark

И ещё такой момент, у вас используется небольшая GeoIP Country. Работают ли ваши графики так же со 150-мегабайтной базой GeoIPOrg?
Определять то надо не 10000 ip за один запуск. А по 1 ip 10000 раз! А это значит открывать и считывать файл не 1 раз а 10,000. И соответственно совсем другие цифры.
Решение на С держит все в памяти (т.к. работает в фоне). Скрипт же на РНР вынужден считывать каждый раз заново.
Хотя за скрипт в целом большое спасибо!
Тут тестировались алгоритмы, так что пропорции на других языках будут близкими, ничто не мешает мой алгоритм переписать на Си.
Тут так же как с алгоритмами поиска, поиск перебором, будет всегда медленнее бинарного поиска, независимо от языка.
спасибо за минус в карму.
все таки на хабре в основном душевно больные люди с комплексами
С чего это мне минусы Вам ставить, еще и в карму? Не страдаю подобным.
Извините, я редко тут чтото пишу, но именно после комментария к вашему топику карма упала еще на один пункт.

По сабжу — реально не хватает скрипта для перевода MindMax в ваш формат. Уже подумываю о том чтобы переписать ваш алгоритм как РНР-расширение
Скрипт для конвертации будет, как и подробное описание формата. Формат будет открытым и универсальным (универсальным в том плане, что можно свои данные хранить в БД).

Я уже сделал новую версию с поддержкой как стран, так и городов, работает в 4-5 раз быстрее GeoIP.

Сейчас готовлю к запуску сайт (на этой неделе запустим), на котором будет и документация, и свежие базы данных. В том числе будет собственная БД, так как в GeoLite City куча мусора и неточностей.

Так что пока с PHP-расширением лучше подождать.

P.S. Карму плюсанул ;)
Спасибо! Не за карму конечно, а за работу над вашим проектом. Сейчас пишем баннерку, скорее всего в ней придётся использовать ваше решение т.к. нагрузки будут большие.

PS до вчерашнего дня у нас использовались запросы с where ip_min={$ip}
— до прочтения этого топика не задумывался о том какие они на самом деле тормозные)
Only those users with full accounts are able to leave comments. Log in, please.