Можно ли сделать быстрый поиск по карте с 1 млн маркеров (MongoDb) и кластеризацией?
Доброго времени. Есть база (MongoDb) с 1 млн точек для карты. У клиента есть карта на которой отображаются эти маркеры. На сервер прилетают границы просматриваемой области клиента + зум.
1. Нужно эти данные кластеризовать на сервере
2. Нужно это делать максимально быстро
Уже долгое время пытаюсь придумать что с этим можно сделать и пока нет ответа.
Для понимания примерной картины:
1. Размеры
база данных в 1 млн, она еженедельно наполняется по 20-30к новыми данными, т.е. в теории через год-два, она может достигать 2-3 млн.
2. Пользователи
На сайте каждый час находится 200-600 пользователей которые обращаются к карте при каждом перемещении.
3. Скорость
В идеале обойтись вообще без фильтрации данных по типу A < B < C, что бы запрос просто целенаправелнно доставал нужную область карты. Было бы круто достичь 0.005с на запрос (если это реально).
Пишу вопрос потому что пробую различные варианты, и это займет много времени, может кто сталкивался с подобным и огородит от граблей и кучи потраченного времени.
Что пробовал:
1. Пробовал реализовать QuadTree, но я так понимаю он хорошо работает только если все держать в памяти, иначе я не придумал как QuadTree реализовать для MongoDb. Он отрабатывает за 0.005с, но нужно держать в памяти всю коллекцию маркеров.
2. Пробовал каждому маркеру присваивать QuadKey. Т.е. делить карту на квадранты, на 4 части, и так до 23 уровня глубины, QuadKey относился к своему тайлу на карте, и по идее если сделать поиск по QuadKey + группировка, получается отличная кластеризация, но запрос идет 0.8с на большом зуме тип 14-17, и 1-2с на маленьком, когда много объектов попадают под область видимости. Пробовал по разному с ним играться, искать подстроки в QuadKey, преобразовывать QuadKey в uint и делать запросы типа A < B < C. Но это все сводилось к 0.8с до 3с. Все это с учетом индексации в монге.
3. Пробовал делать 2d индекс в монге по положению маркеров, и делать поиск через $geoWithin, но такой запрос отрабатывает за 0.8-0.9с.
Карта работает на веб-сокетах, было бы круто не выгружать клиенту мегабайты данных, по этому нужна кластеризация.
В реализации 3-ех описанных примерах я мог совершить ошибку и возможно можно достичь более высокой скорости.
Сами вопросы:
Может кто-то сталкивался с подобной задачей и знает как лучше всего кластеризовать маркеры? Какой алгоритм более эффективен?
Каким образом реализовать поиск по 1млн маркеров, что бы это занимало как можно меньше времени?
Имеет смысл тут делать кэш?
Может кто знает как работают на стороне сервера сервисы типа яндекс.карт, гугл.карт?
Может есть готовые решения для C#?
Буду благодарен за любую ссылку, личный опыт или полезную информацию
Не нужны эти кластеры никому. Пользователю важно само наличие, да или нет. И даже сотню маркеров на экране человек не способен адекватно воспринять, зачем ему эти ваши миллионы.
freeExec, Так мне же не нужно отображать 1 млн маркеров. Я о том что 1 млн лежит в базе, и нужно делать быстрый поиск по этим данным что бы возвращать клиенту 100-200 маркеров
Почти все гео-поисковые системы для хранения геометрии используют либо quad-tree либо R-tree. К чему здесь Mongo - вообще непонятно. Это бд другого типа. Для документов.
Бери деревья и используй. Мало памяти - ну решай это быстрыми дисками или просто покупай больше узлов для параллельных поисков.
То есть quad-tree работает без использования баз? Т.е. все точки хранит постоянно в памяти? Просто думал что quad-tree работает в сочетании с базами, и у яндекса есть статейка где они пишут - используйте пространственные базы (перечисления + MongoDb).
Stanislav Martynov, слушай. Я не сказал что 100% данных надо держать в памяти. Это unreal. Но в топике мало информации о структуре ответа пользователю. Я бы пошел от этого.
Для хранения информации о географических объектах целесообразно использовать пространственные базы данных. Для многих СУБД существуют расширения, позволяющие организовывать доступ к пространственным объектам. Например, для MySQL — это SPATIAL, для PostgreSQL — PostGIS. Также пространственные индексы поддерживают и другие стандартные базы данных, например, Oracle, MongoDB
А это нормальная практика хранить такие объемы в оперативке? Я всеми руками за Redis, если это будет оправдано. Просто какие статьи не читаю, везде пишут про хранение подобных объемов в базе и поиск по ней
Stanislav Martynov, Нормальная. В общем то даже стремятся размещать всю базу в оперативной системе, проблема то в общем в том что они зачастую сильно больше 300 гигов. Так что кэш в 10 -20 гигов это нормально, тем более что он не сразу наполняется а по мере запросов
Попробуйте PostGIS для хранения данных. В ней эти алгоритмы уже реализованы и данные получаются при помощи обычных SQL запросов.
Для скорости пробуйте построить таблицу соответствий между входными параметрами и искомой областью. Скажем, определить longitude, latitude и тогда можно быстро доставать нужную область. С кэшированием координат часто запрашиваемых областей еще более ускорится.
Средний
