silverhawk90
@silverhawk90
Серверный Java Developer

Как правильно вычислять географические расстояния в высоконагруженных сервисах?

Есть сервис с пользователями и их местоположением. Допустим мне нужно получить всех пользователей в радиусе 500м от текущего пользователя.
И есть проблема, которая возникает при появлении большого количества пользователей. Для того что бы мне получить список пользователей в радиусе 500м мне нужно выполнить такие шаги: получить из БД всех пользователей, потом вычислить расстояние от текущего пользователя (тот который запросил этот список) до каждого пользователя, отфильтровать всех тех кто дальше чем 500м и вернуть оставшихся. От сюда вывод время которое нужно потратить на вычисления расстояния будет расти в арифметической прогрессии.
Я провел небольшое исследование (рост времени вычисления в зависимости от количества пользователей от 1 000 до 1 000 000, с шагом в 10 000).

1e7f818e9a214592ae93b83d3883e0a4.png
И как видно из графика 358 мс это достаточно много, учитывая то что все они могут одновременно это запрашивать.

Может это можно решить другим способом (функция вычисления расстояния наименьшая до не могу)?

Была идея сделать так: разбить всю поверхность Земли на квадраты. Потом определить в каком квадрате находится текущий пользователь и вычислять расстояние только до тех пользователей которые находятся только в этом квадрате.
Но тут возникает другая проблема: а если пользователи находятся в разных но смежных квадратах рядом с границей этих квадратов, то они уже не будут видеть друг друга?
  • Вопрос задан
  • 423 просмотра
Решения вопроса 1
Mrrl
@Mrrl
Заводчик кардиганов
Может быть, вычислять расстояние только до пользователей, которые находятся в этом или смежных квадратах? Можно ограничиться 4 квадратами - расположенными вокруг вершины, ближайшей к пользователю.
Ответ написан
Пригласить эксперта
Ответы на вопрос 4
DigitalSmile
@DigitalSmile
http://brainstorage.me/digitalsmile
Высоконагруженные проекты это всегда компромисс между скоростью и целостностью данных. Поэтому нужно сначала решить, является ли критичной для бизнес-логики ситуация когда несколько пользователей друг друга не увидят или нет. Ответив на этот вопрос можно сделать либо более надженое либо более быстрое решение.

Мы на проекте вынесли логику определения попадания в зону на базу, но честно говоря не тестировали по скорости. Если у Вас будет время и Вы используете MySql, было бы интересно узнать, насколько быстро работает это вычисление.

ACOS(SIN(#{userLat})*e.SIN_LATITUDE + COS(#{userLat})*e.COS_LATITUDE*COS(#{userLong} - e.RADIANS_LONGITUDE)) * 6371000 <= #{targetRadius}

SIN_LATITUDE = SIN(RADIANS(#{latitude})) , COS_LATITUDE = COS(RADIANS(#{latitude})), RADIANS_LONGITUDE = RADIANS(#{longitude}) рассчитывались заранее для каждого объекта перед внесением в БД.
Ответ написан
vpuhoff
@vpuhoff
Программист в свободное от работы время
можно в базе хранить кроме "настоящих" координат "приблизительные", с погрешностью скажем в 1 градус, то есть отсеять всю дробную часть. Далее из базы делать выборку только тех пользователей у которых координата lat-1<lat<lat+1 и для второй координаты аналогичное условие, полученную выборку можно уже честно отсеивать по точному расстоянию.
Ответ написан
Думаю, правильно будет использовать расширение к базе данных для работы с геоданными. Для MySQL ничего подходящего не знаю, для Postgresql есть PostGIS, с помощью которого вашу задачу можно будет очень легко решить. Если возможности полностью перейти на Postgresql нет, то можно, например, вынести туда хранение текущих координат пользователей и поиск по ним.

У меня в одном из проектов основная база - это MySQL, а PostGIS как дополнительная для работы с картой.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы