Недавно у нас было требование к проекту реализовать личное общение с друзьями.
Предполагаемый сценарий заключается в том, что когда два пользователя смотрят друг на друга, они могут легко найти друг друга, встряхивая или используя другие интерактивные методы, чтобы связаться с друзьями.
ключевой момент
Серверная служба быстро сопоставляет людей поблизости на основе местоположения GPS.
строить планы
1. Полный обход
Первый способ, который приходит на ум, — это непосредственное вычисление расстояния пользователя.Если расстояние пользователя находится в требуемом диапазоне, два пользователя достигнут совпадения.
вопрос
Это решение должно проходить через всех пользователей, что требует больших вычислений и низкой эффективности сопоставления.
2. Геохеш
Идея геохэша заключается в преобразовании двумерных значений широты и долготы в одномерные строки.Геохеш имеет следующие три характеристики:
Чем длиннее строка, тем точнее представленный диапазон.
Сходные строки указывают на схожие расстояния. Используя сопоставление префиксов строк, можно запрашивать близлежащие географические местоположения. Таким образом, можно быстро запросить географическое местоположение рядом с определенной координатой.
Строка, рассчитанная геохешем, может быть декодирована в обратном порядке, чтобы получить исходные широту и долготу.
Информация о точности геохэша выглядит следующим образом: чем длиннее строка, тем точнее представленный диапазон.
2.1. Редис GeoHash
Redis обеспечивает поддержку геолокации после версии 3.2. Мы можем легко поддерживать географическое местоположение через Redis и быстро запрашивать географическое местоположение на определенном расстоянии рядом с координатой.
вопрос
В общих сценариях географическое расположение магазина в основном не меняется, и информация также действительна в течение длительного времени. Поэтому более целесообразно поддерживать все географические местоположения через Redis. Но в нашем сценарии спроса поиск друзей — это мгновенный сценарий. Сам запрос на сопоставление пользователя зависит от времени.Если вы напрямую используете GeoHash Redis для сохранения географического местоположения, вам также необходимо учитывать удаление информации, что усложняется.
2.2, Redis Hash+GeoHash
Мы можем напрямую использовать хеш-структуру Redis, чтобы поддерживать соответствие всех пользователей. Поле представляет собой идентификатор пользователя, а значение — информацию, относящуюся к сопоставлению пользователей, включая GeoHash, соответствующий координатам пользователя. затем пройтизадача на времяПолучите всю информацию о пользователе, которая должна быть сопоставлена, в соответствии сgeohashОтсортируйте поля, а затем подсчитайте, находятся ли соседние пользователи на требуемом расстоянии.Если условия соблюдены, совпадение может быть достигнуто.
ключевой момент
Если два пользователя находятся рядом друг с другом, их строки геохэша будут очень похожими.При сортировке по геохешу индексы информации двух пользователей также будут соседними.
3. Р дерево
R-деревоЭто древовидная структура данных, используемая для хранения пространственных данных. В сценариях на вынос R-деревья часто используются для поддержания диапазона доставки продавцов и фильтрации ближайших продавцов для пользователей. R-дерево не применимо в этом требовании.
вопрос
В конце концов, мы приняли решение Redis Hash+GeoHash, и есть другие вопросы, которые необходимо учитывать в процессе внедрения.
1. Большая коллекция пользователей
Разделите полный набор пользователей и сначала создайте корзину по городу пользователя. С большой вероятностью рядом могут появиться только пользователи из одного города. Кроме того, допустимое время запросов на сопоставление пользователей обычно относительно короткое, поэтому размер полного набора должен контролироваться после группирования.
Город, в котором находится пользователь, можно оценить на основе информации GPS или IP-адреса пользователя;
Возможна ситуация, когда два пользователя на окраине города не могут постоянно сопоставляться, вероятность такой ситуации очень мала и может быть проигнорирована;
Пользователь может отменить сопоставление, пока мы выполняем задачу сопоставления. При выполнении операции сопоставления мы получим полный пользовательский набор и удалим соответствующий полный набор данных (черезpipelineспособ достижения атомарности). Таким образом, в этот раз пользователь не сможет отменить совпадение, что упрощает логику. Если последний пользователь не совпадает, соответствующая информация может быть записана обратно в набор пользователей в пакетном режиме.
3. Система координат не унифицирована
В ходе тестирования было обнаружено, что системы координат стороны Android и стороны iOS будут несовместимыми, в данном случае из-за смещения позиции не удалось сопоставить. Система координат может быть унифицирована путем преобразования системы координат.
4. Проблемы с GeoHash
Как показано на рисунке ниже, картинка взята из Интернета. Для точек рядом с краем желтая точка ближе к красной точке, чем черная точка, но поскольку количество префиксов GeoHash черной точки и красной точки больше совпадает, в результате черная точка ближе к красной точке. получается. Общий метод обработки заключается в фильтрации всех точек в окружающих 8 областях, а затем вычислении расстояния для получения результата, соответствующего условиям.
В нашей задаче сопоставления времени GeoHash используется только в качестве эталона для расстояния.Теоретически пользователи в соседних областях также будут находиться в соседних позициях индекса, а затем определять, выполняются ли условия, вычисляя расстояние.
резюме
Мы реализуем сопоставление лицом к лицу через GeoHash. GeoHash преобразует двумерные значения широты и долготы в одномерные строки, а затем мы сортируем одномерные строки, чтобы можно было быстро найти соседнюю информацию о пользователе.