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

Question

[Виталий]

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


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

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

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

Comments

[Олег Гамега]

а вы пробовали postgresql geolocation ?

[Виталий]

Я использую MySQL

Answer 1

[Mrrl]

Может быть, вычислять расстояние только до пользователей, которые находятся в этом или смежных квадратах? Можно ограничиться 4 квадратами - расположенными вокруг вершины, ближайшей к пользователю.

Answer 2

[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}) рассчитывались заранее для каждого объекта перед внесением в БД.

Comments

[Виталий]

скорость вычисления повысилась на 30% (и это программным способом, не через базу)

[DigitalSmile]

Виталий: вобщем-то неплохой результат, мне кажется. Спасибо за замер.

Answer 3

[Ai Lab]

можно в базе хранить кроме "настоящих" координат "приблизительные", с погрешностью скажем в 1 градус, то есть отсеять всю дробную часть. Далее из базы делать выборку только тех пользователей у которых координата lat-1<lat<lat+1 и для второй координаты аналогичное условие, полученную выборку можно уже честно отсеивать по точному расстоянию.

Answer 4

[Сергей]

Найти ближайшую точку в системе координат?

Comments

[Виталий]

Этот вариант не подходит из-за того что придется выполнять полный перебор таблицы (у меня в таблице больше 10 миллионов пользователей)

[Сергей]

Где полный перебор?

Answer 5

[Вячеслав]

Думаю, правильно будет использовать расширение к базе данных для работы с геоданными. Для MySQL ничего подходящего не знаю, для Postgresql есть PostGIS, с помощью которого вашу задачу можно будет очень легко решить. Если возможности полностью перейти на Postgresql нет, то можно, например, вынести туда хранение текущих координат пользователей и поиск по ним.

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