Робота з геолокації в режимі highload

    При розробці ПО часто виникають цікаві завдання. Одна з таких: робота з гео-координатами користувачів. Якщо вашим сервісом користуються мільйони користувачів і запити до РСУБД відбуваються часто, то вибір алгоритму відіграє важливу роль. Про те як оптимально обробляти велику кількість запитів і шукати найближчі гео-позиції розказано під катом.
 
 image
 
 

Завдання пошуку найближчого сусіда

У процесі розробки сервісу push-повідомлень Pushwoosh виникла досить відома задача. Мається багато геозон. Геозон задається географічними координатами. Коли користувач проходить повз одну з таких геозон (наприклад закусочна) йому повинно приходити push-повідомлення («Йоу, заходь до нас і підкріпив з 20% знижкою). Для простоти будемо вважати радіус всіх геозон однаковим. В умовах великої кількості геозон і великої кількості користувачів (у нас їх 500 мільйонів!) , які постійно переміщаються — пошук найближчої геозон повинен здійснюватися максимально швидко. В англомовній літературі це завдання відома як Nearest neighbor search . На перший погляд здається, що щоб вирішити цю задачу потрібно порахувати відстані від користувача до кожної геозон і складність даного алгоритму лінійна O (n), де n — кількість геозон. Але давайте вирішимо це завдання за логарифм O (log n)!
 
 Географічні координати
Почнемо з простого — широти і довготи. Щоб вказати положення точки на поверхні Землі можна скористатися:
 
     
  1. Широтою (latitude) — йде з півночі на південь. 0 — нульовий меридіан (Грінвіч). Змінюється від -90 до +90 градусів.
  2.  
  3. Довготою (longitude) — йде із заходу на схід. 0 — екватор. Змінюється від -180 до +180 градусів.
  4.  
 
Потрібно звернути увагу що x — це довгота, y — широта (Google Maps, Яндекс.Карти і всі інші сервіси вказують довготу першої).
 
Географічні координати можна перевести в просторові — просто точка (x, y, z). Кому цікаво більш детально можна подивитися вікіпедію .
Кількість знаків після коми визначає точність:
                                  
Градуси Дистанція
1 111 km
0.1 11.1 km
0.01 1.11 km
0.001 111 m
0.0001 11.1 m
0.00001 1.11 m
0.000001 11.1 cm
Якщо потрібна точність до одного метра, то слід зберігати 5 знаків після коми.
 
 Geohashing
Нехай у нас є сервіс, яким користуються мільйони людей, і ми хочемо зберігати їх географічні координати. Очевидний підхід в даному випадку завести в таблиці два поля — широта / довгота. Можна використовувати double precision (float8), який займає 8 байт. У підсумку нам буде потрібно 16 байт для зберігання координат одного користувача.
 
Але є й інший підхід, який називається geohashing . Ідея проста. Широта і довгота кодується в число, яке потім кодується в base-32. Карта розбивається на матрицю розміру 4x8 і кожному осередку присвоюється певний символ (alphanumeric).
 image
 
Щоб підвищити точність, кожна клітинка розбивається на більш дрібні, при цьому до коду додаються символи (якщо бути точним цифри, а після відбувається кодування в base-32).
 image
Розбиття можна виробляти до необхідної точності. Такий код унікальний для кожної точки.
 
Детально алгоритм побудови я описувати не буду, про нього можна почитати в вікіпедії . Його ідея схожа на арифметичне кодування . Даний код звернемо. Багато технологій вже мають вбудовані методи для роботи з гео-хешамі, наприклад, MongoDB .
 
Приклад: координати 57.64911,10.40744 будуть закодовані в u4pruydqqvj (11 символів). Якщо потрібна менша точність, то і код буде менше.
 
Особливість даного коду в тому, що ЗВИЧАЙНО довколишні точки мають однаковий префікс. І можна порахувавши різницю між гео-хешамі визначити близькість двох точок. Але на жаль даний алгоритм не точний, це добре видно з попередніх зображень. Осередки з кодами 7 і 8 знаходяться далі один від одного, ніж осередку 2 і 8.
 
Як приклад наведу картинку, де гео-хеш дає невірний результат (geohashdelta — різниця між геохешамі без base32)
 image
 
Якщо точністю в задачі можна знехтувати, то можна створити в таблиці поле geohash, додати по ньому індекс та здійснювати пошук за логарифм.
 
 Повний перебір
Можна написати збережену процедуру
 
create or replace function gc_dist(_lat1 float8, _lon1 float8, _lat2 float8, _lon2 float8) returns float8 as
$$
  DECLARE
   radian CONSTANT float8 := PI()/360;
  BEGIN
   return ACOS(SIN($1*radian) * SIN($3*radian) + COS($1*radian) * COS($3*radian) * COS($4*radian-$2*radian)) * 6371;
  END;
$$ LANGUAGE plpgsql;

 
і використовувати її
 
explain SELECT *, gc_dist(54.838971, 83.106560, lat, lng) AS pdist FROM geozones WHERE applicationid = 3890 ORDER BY pdist ASC LIMIT 10;

 
Але в підсумку буде Seq Scan, що дуже не приємно.
 
Limit  (cost=634.72..634.75 rows=10 width=69)
   ->  Sort  (cost=634.72..639.72 rows=2001 width=69)
         Sort Key: (gc_dist(54.838971::double precision, 83.10656::double precision, (lat)::double precision, (lng)::double precision))
         ->  Seq Scan on geozones  (cost=0.00..591.48 rows=2001 width=69)

 
 K-d tree і R tree
Що робити, коли точністю знехтувати не виходить? Для цього вже є спеціальна структура даних Kd tree . Можна перевести широту і довготу в (x, y, z) побудувати по них дерево та здійснювати пошук по дереву в середньому за логарифм.
 
 PostGIS
 PostGIS — це розширення, яке значно розширює обробку географічних об'єктів в РСУБД PostgreSQL.
 
Для вирішення нашого завдання буде використовувати тривимірну систему координат SRID 4326 (WGS 84 ). Дана система координат визначає координати відносно центру мас Землі, похибка становить менше 2 см.
 
Якщо у вас ubuntu-подібна система, то PostGIS можна встановити з пакету (для PostgreSQL 9.1):
 
 
sudo apt-get install python-software-properties;
sudo apt-add-repository ppa:ubuntugis/ppa;
sudo apt-get update;
sudo apt-get install postgresql-9.1-postgis;

 
І підключити необхідні екстеншени:
 
 
CREATE EXTENSION postgis;
CREATE EXTENSION btree_gist; -- for GIST compound index

За допомогою \ dx можна подивитися всі встановлені екстеншени.
 
Створимо відношення з індексом по полю location
 
CREATE TABLE geozones_test (
    uid SERIAL PRIMARY KEY,
    lat DOUBLE PRECISION NOT NULL CHECK(lat > -90 and lat <= 90),
    lng DOUBLE PRECISION NOT NULL CHECK(lng > -180 and lng <= 180),
    location GEOMETRY(POINT, 4326) NOT NULL -- PostGIS geom field with SRID 4326
);
CREATE INDEX geozones_test_location_idx ON geozones_test USING GIST(location);

 
Після чого для пошуку найближчої геозон можна скористатися наступним запитом
 
SELECT *, ST_Distance(location::geography, 'SRID=4326;POINT(83.106560 54.838971)'::geography)/1000 as dist_km
FROM geozones_test ORDER BY location <-> 'SRID=4326;POINT(83.106560 54.838971)' limit 10;

Тут <-> — Distance operator. Ми порахували дистанцію і знайшли найближчі 10 геозон!
 СТОП скажіть Ви! Адже даний запит повинен переглянути всі записи в таблиці і порахувати відстань до кожної геозон O (n).
 
Давайте подивимося EXPLAIN ANALYZE запиту
 
EXPLAIN ANALYZE
SELECT *, ST_Distance(location::geography, 'SRID=4326;POINT(83.106560 54.838971)'::geography)/1000 as dist_km
FROM geozones_test ORDER BY location <-> 'SRID=4326;POINT(83.106560 54.838971)' limit 10;

 Limit  (cost=0.00..40.36 rows=10 width=227) (actual time=0.236..0.510 rows=10 loops=1)
   ->  Index Scan using geozones_test_location_idx on geozones_test  (cost=0.00..43460.37 rows=10768 width=227) (actual time=0.235..0.506 rows=10 loops=1)
         Order By: (location <-> '0101000020E6100000F4C308E1D1C654406EA5D766636B4B40'::geometry)
Total runtime: 0.579 ms

 
 Index Scan! Де ж магія?
 
А вона знаходиться в GiST індексі.
PostgreSQL підтримує 3 типи індексів:
 
     
  1. B-Tree — використовуються, коли дані можуть бути відсортовані уздовж однієї осі; наприклад, числа, символи, дати. Дані ГІС не можуть бути раціональним способом відсортовані уздовж однієї осі (що більше: (0,0) або (0,1) або (1,0)?), А тому для їх індексування B-Tree не допоможуть. B-Tree працюють з операторами <, <=, =,> =,> та ін
  2.  
  3. Hash — може працювати тільки з порівнянням на рівність. Так само даний індекс НЕ Write-Ahead logging — тоесть з бекапа індекс може і не поднятся.
  4.  
  5. — »перевернуті" індекси, які можуть обробляти значення, що містять більше одного ключа, наприклад, масивів.
  6.  
  7. Індекси GiST (Generalized Search Trees — узагальнені дерева пошуку) — являє собою якусь інфраструктуру, в якій можуть бути реалізовані багато різних стратегій індексування. GiST-індекси поділяють дані на об'єкти по одну сторону (things to one side), пересічні об'єкти (things which overlap), об'єкти всередині (things which are inside) і можуть бути використані для багатьох типів даних, включаючи дані ГІС.
  8.  
 
GiST-індекс реалізований PostGIS підтримує distance operator <-> при пошуку. Також даний індекс може бути складеним!
 
Даний функціонал можна реалізувати і без використання PostGIS, скориставшись індексом btree-gist , але PostGIS надає зручні методи для перекладу широти і довготи в WGS 84.
 
 

Посилання:

[1] Цікаві приклади запитів postgresql.ru.net/postgis/ch04_6.html
[2] Замилування простотою використання boundlessgeo.com/2011/09/indexed-nearest-neighbour-search-in-postgis /
[3] Презентація про те, що даний підхід можна використовувати не тільки для широти / довготи, а й для вулиць та інших цікавих об'єктів www.hagander.net / talks / Find% 20your% 20neighbours.pdf
[4] Презентація розробників KNN GIst-index www.sai.msu.su/ ~ megera/postgres/talks/pgcon-2010-1.pdf
 
P.S.
Postgres version> = 9.1
PostGIS version> = 2.0
  

    
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.