Не так давно для создания сервиса (да и «в загашник» положить модуль) потребовалось придумать способ как быстро из sql базы делать выборки точек расположенных на карте.
Кода будет мало, что бы не отвлекать от понимания системы в целом.
ТЗ
И так, на «входе» имеет базу из 2 млн точек (пока лишь тестовую, так как реальная еще мала), карта гугла (или яндекса, не принципиально) у каждой точки есть координаты. Пользователь должен перемещаться по карте, видеть все точки, сервер не должен быть размером в пол стойки с учетом «желаемой» посещаемости в до 200 человек в секунду.
Идеи?
Точек много. Очень много. Варианты с проверками на вхождение точки в границы карты не подходит ( вроде (x1< x < x2) and (y1 < y <y2) ), так как такой запрос делался за 20-50мс и приходилось делать его при каждом перемещении карты + объем передаваемых данных шел на десятки килобайт (а с учетом того, что к точке может быть добавлен «балун» с текстовой информацией, то и мегабайты). Кэширование запросов фактически не имеет смысла в виду низкой эффективности.
В ходе поиска решений пришли к следующим пунктам:
1. работать с картой тайлами (квадрат, блок)
2. хранить в базе у точки qtree тайлов
3. при перемещении по карте без изменения масштаба загружать только точки с «новых» тайлов
Для понимания qtree en.wikipedia.org/wiki/Quadtree
Для понимания что из этого получится koti.mbnet.fi/ojalesa/quadtree/quadtree_intro.htm
Строка с «деревом» для каждой точке в базе выглядит как 01320232312222100231210323203 (число цифр равно максимальному уровню масштабирования).
Фактически оно означает, что если карту мира поделить на 4 части 2х2, то точка находится в 1 блоке (нумерация с нуля и «главный блок» с номером 0 мы упустили для упрощения), если этот блок поделить еще раз на 2х2, то она будет в 3 блоке и так далее. С каждым уровнем масштабирования мы должны смотреть «глубже» в наше «дерево».
В чем прелесть хранения данных в данном виде?
Прелесть в том, что зная координаты тайла и масштаб мы получаем qtree вида 132023231, а что бы найти все точки входящие в данную область на карте при данном уровне масштаба надо сделать запрос с условием point_qtree LIKE '132023231%' (ищем вхождение подстроки в строке с первого символа). При этом поле point_qtree мы должны не забыть проиндексировать, что скорость выборок поднимет на максимальный уровень. SQL построит qtree дерево, что максимально упростит ему задачу по выборке.
Ура. Выборка точек стала занимать во много раз меньше времени.
Займемся картой
При перемещениях по карте мы должны сделать ряд вещей:
- определить какие тайлы мы видим
- определить для каких тайлов мы уже точки подгрузили
Для определения видимых тайлов в любом API карт можно запросить координаты окна карты и уровень масштабирования. И исходя из этих данный получить тайл верхнелевого края и нижнеправого и перечислить все другие находящиеся между ними.
У нас получится массив вида 012, 013, 021, 020.
Сохраним его в переменную, которую обзовем oldTile.
При каждом перемещении по карте вычисляем все тайлы и сравниваем с текущим массивом oldTile, при этом у нас должен получится массив newTile в котором будут перечислены все тайлы, которых еще нет в oldTile. Далее мы должны послать ajax запрос серверу на выборку точек для каждого тайла (можно в запросе отправить массив новых тайлов, но цель разбиения на отдельные запросы я поясню далее), допустим вида /point/012, добавить новые точки на карту (не очищая старые). Далее делаем простое oldTile= oldTile+ oldTile.
При изменении масштаба карты нам придется очистить oldTile( и точки на карте, один из вариантов. Второй вариант: не чистить точки, но нужно тогда массив oldTile тоже не очищать, а пересчитать, например из 01 мы должны получить 010, 011, 012, 013). И после этого «по плану» вычислить видимые тайлы карты и т.д.
Что нам дает данный способ:
- запрашиваем только новые точки из новых отображаемых мест на карте
- получаем хорошую возможность ответ сервера сваливать с мемкэш и, настроив Nginx на работу с ним, получать точки в тайлах уже из него (вот по этому мы остановились на нескольких запросах к конкретному тайлу, а не делаем выборки «оптом).
- снижаем число запросов к серверу бд
- уменьшаем объем трафика
Как следующий этап оптимизации системы:
1. При добавлении новой точки в базу принудительно обновлять к мемкэше все массивы всей ветки дерева. Тем самым мы можем добиться того, что запросы далее nginx+memcache не уйдут и данные всегда будут актуальными что позволит перейти от мемкэша к редис и не бояться «холодных стартов».
Автор: psman
