20 февраля 2012 в 12:48

Плоский GeoIP или диапазон в одной колонке из песочницы

В опубликованной накануне (февраль, 2012) статье озаглавленной «Определение страны по IP: тестируем скорость алгоритмов» сравнивались реализации на уровне БД и нативной реализации. Мы же предлагаем рассмотреть ещё более оптимальный и простой алгоритм, который может быть реализован как в БД, так и в нативном варианте – плоские диапазоны.

Имплементация или алгоритм?


Нисколько не умаляя нативного варианта, давайте попробуем сравнивать не имплементации, а именно алгоритмы. Текущий алгоритм использует две колонки в варианте с БД и также границы диапазонов в нативном. А что если мы будем, хранить не диапазоны, а только их начальные точки? Аналогичная идея в комментах к статье уже высказана: «…Все хранить не надо, только концы диапазонов …». Ведь в этом случае поиск у нас явно ускоряется в два раза – нам надо найти только начало диапазона, в который входит значение. Тем, кто заметит, что существуют пустые диапазоны, мы ответим, что и их можно хранить: начало пустоты и значение, которое её символизирует.

Простые диапазоны или вложенные?


На рассмотренной в предыдущем примере, простом на наш взгляд, была использована GeoLite Country, у которой диапазоны не пересекаются и нет проблемы вложенных диапазонов. В более сложном случае, таком, как например российский IpGeoBase, диапазоны нещадно пересекаются и уже простыми запросами вида needle between start and end мы не обойдёмся. Но на помощь нам как раз приходит урощение алгоритма поиска!

Концепция плоских диапазонов


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

Что это такое?
  • Три колонки: start, end, value
  • Две колонки: start, value
Как пустые диапазоны учитываются?
  • Никак – в простом диапазоне их не требуется учитывать, так как в случае запроса на пустой диапазон вернётся ноль записей.
  • Хранится начало пустого диапазона в колонке start и некое обозначение пустоты в колонке value – это может быть NULL, но и может быть 0, в том случае, если мы используем составной первичный ключ на start и value.
Насколько больше записей в итоге получается?
  • В простом случае, типа GeoLiteCountry – 160222.
    В сложном, типа IpGeoBase – 39449.
    В сложном и старом типа IpGeoBase предыдущего формата, где много идущих подряд диапазонов (например, от ноября 2011 года) – 148666.
  • GeoLiteCountry – 161619. Увеличение менее, чем на 1%.
    IpGeoBase – 46047. Увеличение всего на 16%.
    IpGeoBase предыдущего формата – 31156. Уменьшение на целых 80%!
Как по нему искать?
  • В простом случае: needle between start and end limit 1.
    В сложном, когда у нас имеются вложенности уже надо подключать дополнительную колонку diff, которая в составном индексе будет использована и в итоге получается ужас типа: needle between start and end order by end, diff limit 1.
  • Любой из случаев будет простой: neddle >= start order by start desc limit 1.
Что приходится делать БД или любому другому провадеру поиска?
  • Сначала сходить в одном направлении, а потом удостовериться, что с другого направления всё хорошо. Т.е. в общем случае сделать два движения.
  • Всегда идти в одном направлении.
Как его получить?
  • Он уже у нас имеется – любая загрузка из файла с диапазонами geoip.
  • Взять таблицу с тремя колонками и с помощью особой уличной магии преобразовать её в таблицу с тремя колонками. См. Приложение 1.

Заключение


Вы конечно спросите – а как нам преобразовать данные в плоский вид и насколько объёмы увеличатся? Отвечаем с конца: объёмы увеличатся примерно в два раза, а SQL преобразования мы ниже выложим с комментами (см. Приложение 1).
PS: Скорее всего при применении концепции плоских диапазонов в нативном варианте всё будет ещё более космически мгновенно. Просьба к тем, кто может проверить – проверить это утверждение.
PS2: Также что-то мне подсказывает, что в эру более активного IPv6, если к тому времени не будет распространены HUGEINT`ы, также весьма пригодятся плоские диапазоны, если хранение будет в виде CHAR`а.

Приложение 1. Создание плоских диапазонов на примере MySQL


Взято с github.com/garex/geoip-flat-range, а именно с github.com/garex/geoip-flat-range/blob/master/01-create-flat-range-mysql.sql

-- Create intermediate table with 3 columns
-- Change this to your columns and/or table
drop table if exists t3;
create table t3
select
    range_start f, range_end t, country_code v
    from countries_ips
;
alter table t3 add primary key (f,t,v);

-- Create target table with 2 columns and fill it with all distinct ranges borders
drop table if exists t2;
create table t2
select distinct border as f, (select max(v) from t3) as v from (
    select f-1 as border from t3
    union select f from t3
    union select t from t3
    union select t+1 from t3
) inn
order by f;
-- Here we just reset value column as it was filled by max value to have auto created column with needed type
update t2 set v = null;

-- We can add PK here, as all our range borders are unique
alter table t2 add primary key(f);

-- Adding diff column, that will help us to order ranges during main update
alter table t3 add column diff int(10) unsigned, add unique index dif_f(diff, f);
update t3 set diff = t-f;

-- Create helper table, that will help to smooth main update
drop table if exists t3diff;
create table t3diff
select distinct diff from t3 order by diff;

-- Here are our MAIN update
update t3diff, t2, t3 set t2.v = t3.v where t3.diff = t3diff.diff and t2.f between t3.f and t3.t;

-- We dont' need 'em anymore
drop table if exists t3;
drop table if exists t3diff;

-- We should remove records, that points to the same value and is one after another
alter table t2 drop primary key;
alter table t2 add column row_number int(10) unsigned not null auto_increment primary key;
alter table t2 add column next_row_number int(10) unsigned not null;
update t2 set next_row_number = row_number + 1;
alter table t2 add unique index next_row_number_v (next_row_number, v);

delete t2.* from t2, (
    select cur.row_number from t2 as cur
    join t2 prev on cur.row_number = prev.next_row_number and cur.v = prev.v    
) as inn
where t2.row_number = inn.row_number;

-- Also we dont' need first record
delete from t2 where row_number = 1;

-- Removing extra columns, that will not help us anymore
-- And also adding primary key on key and value to just always use index instead of table
alter table t2
    drop column row_number,
    drop column next_row_number,
    drop primary key,
    drop index next_row_number_v,
    add primary key (f, v)
;

-- ... And renaming target table to more human readable form
-- Change table`s/columns` names/definitions to your tables/columns
drop table if exists countries_ips_flat;
alter table t2
    rename to countries_ips_flat,
    change column f range_start int(20) unsigned not null default 0 first,
    change column v country_code varchar(2) not null default '' after range_start;

-- Comparing records count and check, that's all is ok
select
    (select count(*) from countries_ips) as default_range_records,
    (select count(*) from countries_ips_flat) as flat_range_records;
Александр @garex
карма
14,5
рейтинг 0,0
Разработчик
Похожие публикации
Самое читаемое Разработка

Комментарии (19)

  • +1
    Спасиб за статью. На самом деле SxGeo именно так и работает, потому у него и база очень компактная. Но кроме того там были еще некоторые оптимизации, чтобы хранить начало диапазона не в 4, а в 3 байтах, плюс дополнительный индекс. Ну это думаю уже в отдельной статье распишу детали.
    • 0
      Значит у нас уже есть клевая штука, которая любую базу может сконвертнуть в формат, с которого уже в нативный в два счёта? :)

      Btw, последняя версия только на гитхабе — здесь так, для общего представления.
      • 0
        Нет, я не видел особого смысла делать лишнее преобразование в базе, поэтому конвертилка работает с таблицей в которой обычные диапазоны. Планирую еще сделать чтобы можно было конвертить сразу из CSV, без предварительного загона данных в MySQL.
  • 0
    наверное будет не в тему, но некторые БД имеют geo индекс — например mongodb www.mongodb.org/display/DOCS/Geospatial+Indexing
    • +5
      Верно, абсолютно не в тему.
  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Товарищ phpdude, этот подход как раз и был опробован и создан под необходимостью работы с городами — см. ipgeobase российскую.

      Если найдете серьезный баг или невозможность им пользоваться — скину 50 рублей на Ваш сотовый.

      2 karellen: Это то очевидно. Ускорение идёт в процессе поиска, а не в дальнейших оптимизациях. А если у нас сайт, где юзеров много и они заходят на 1-2-3 страницы, то быстрый поиск крайне выгоден. Конечно лучше всего нативный.
      • НЛО прилетело и опубликовало эту надпись здесь
        • –1
          Да это так — мелочь, а приятно :)
  • +1
    При скольких тысячах хитов в секунду стоит вообще об этом беспокоиться, страшно подумать. Всегда ведь можно 1 раз посчитать для пользователя город по любому алгоритму, а потом записать его и хэш от IP в куку. Потом читать из куки, и, если хэш изменился, пересчитывать город. Это на 99.999% снизит объем обращений к геобазе. Разве нет?
  • 0
    Жду повсеместного внедрения ipv6, наверное статей такого рода будет становиться всё больше с его распространением :)
  • 0
    Вот я как раз нечто подобное реализовал в open-source проекте IpLoc. Там берётся база GeoLiteCity c maxmind.com, приводится к оптимальному виду, и потом при помощи двух простых запросов по IP адресу получаются Страна + Город + координаты провайдера. На дешёвеньком хостинге такая штука находит нужный адрес за 1-3мс.
    • 0
      Ой, я что-то не до конца вчитался, у вас тут как-то совсем всё навёрнуто… Я исходил из того, что если отсортировать все диапазоны по ip_start, и далее забить на ip_end, а просто искать нужный диапозон запросом вида: SELECT locationId as id FROM '. $this->ipMasksTable. ' WHERE startIp < "'. sprintf('%u', ip2long($ip)). '" ORDER BY startIp DESC LIMIT 1, то с 99% процентной вероятностью результат будет правильным.
      • 0
        Смысл в том, что если у вас есть диапазон 2 в который вложен диапазон 1 как-то так:

        1 2 3 4 5 6 7 8
        2 2 2 2 1 1 2 2

        то при попытке получить 7 или 8 ваш алгоритм отработает с ошибкой.
        • 0
          Ага, а такое вообще возможно разве?)))
          • 0
            оказалось, что возможно и не такое 8)
            • –1
              Ну вот насколько я понял, вероятность таких накладок стремится к 1%, и решил этой погрешность просто пренебречь %)
  • 0
    Можете пояснить назначение колонки diff и принцип работы запроса, в котором она используется?
    • 0
      Она нужна в промежуточном трех-колоночном варианте, который пытается соптимизоваться.

      Было 3 колонки:
      from to value
      1 100 a
      10 50 b
      10 90 c
      20 33 d
      20 50 e

      Мы делаем запрос с условием вида:
      … where $ip between from and to order by from desc, to limit 1

      В СУБД, в которых можно создать индекс вида ICoolIndex (from desc, to, value) — эта колонка не нужна.

      В MySQL обычном это пока не очень — все д.б. ASC упорядочено.

      Поэтому это такой workaround:
      from to diff value
      20 33 13 d
      20 50 30 e
      10 50 40 b
      10 90 80 c
      1 100 99 a

      diff ASC == from DESC:
      … where $ip between from and to order by diff, to limit 1

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.