1. Введение

Мобильный Интернет прочно вошёл во все сферы нашей жизни.

Обычно мы находим предприятия, дома и автомобили через различные приложения. Я, как автор 👨‍💻‍, по привычке задумываюсь над тем, как реализованы эти функции?

Например, чтобы найти спрос на такси в пределах 3 км от окрестностей, наиболее интуитивная идея состоит в том, чтобы найти таблицу в базе данных, чтобы отфильтровать автомобили, которые находятся менее чем в 3 км от пользователя, и вернуть данные в клиент.

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

Ключом к решению этой проблемы является быстрое индексирование данных. При просмотре Redis API я обнаружил, что он может напрямую реализовывать близлежащие функции XXX. Далее будет представлено, как реализовать такие функции с помощью Redis, и глубоко проанализирован принцип реализации, стоящий за этим. .

2 Redis GEO API

2.1 Добавить информацию о географическом местоположении

geo add key longitude latitude member [longitude latitude member ...]

eg:

Добавьте информацию о местонахождении автомобиля № 1 и № 2 в cars:locations.

127.0.0.1:6379> geoadd cars:locations 120.346111 31.556381 1 120.375821 31.560368 2

2.2 Получение информации о географическом местоположении

eg:

Получить информацию о местоположении транспортного средства с номером транспортного средства 1

127.0.0.1:6379> geopos cars:locations 1
1) 1) "120.34611314535140991"
   2) "31.55637987511895659"

2.3 Получить расстояние между двумя географическими точками

eg:

Получить расстояние между транспортным средством № 1 и транспортным средством № 2

127.0.0.1:6379> geodist cars:locations 1 2 km
"2.8504"

2.4 Получить набор географических сведений о местоположении указанного диапазона местоположений

GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC|DESC] [COUNT count]

Принимая заданные широту и долготу в качестве центра, среди элементов положения, содержащихся в ключе возврата, все элементы положения, расстояние от центра которых не превышает заданного максимального расстояния.

eg:

Найти транспортные средства в пределах 5 км от долготы 120,375821 широты 31,556381

127.0.0.1:6379> GEORADIUS cars:locations 120.375821 31.556381 5 km WITHCOORD WITHDIST WITHHASH  ASC COUNT 100
1) 1) "2"
   2) "0.4433"
   3) (integer) 4054421167795118
   4) 1) "120.37582129240036011"
      2) "31.5603669915025975"
2) 1) "1"
   2) "2.8157"
   3) (integer) 4054421060663027
   4) 1) "120.34611314535140991"
      2) "31.55637987511895659"

Диапазоны могут использовать одну из следующих единиц измерения:

m означает, что единицей измерения являются метры.
км указывает, что единицей измерения являются километры.
mi указывает, что единицей измерения являются мили.
ft означает, что единицей измерения являются футы.

Команда возвращает дополнительную информацию, если заданы следующие параметры:

WITHDIST: при возврате элемента position также возвращается расстояние между элементом position и центром. Единица расстояния согласуется с единицей дальности, заданной пользователем.
WITHCOORD : также возвращает долготу и широту элемента position.
WITHHASH : возвращает необработанную отсортированную оценку множества элемента position, закодированную геохэшем, в виде 52-битного целого числа со знаком. Этот параметр в основном используется для низкоуровневых приложений или отладки и на практике малоэффективен. По умолчанию команда возвращает несортированные позиционные элементы. С помощью следующих двух параметров пользователь может указать порядок возвращаемых элементов позиции:
ASC : В соответствии с положением центра верните элемент положения от ближнего к дальнему. DESC : В соответствии с положением центра, вернуть элемент позиции из дальнего в ближний.
По умолчанию команда GEORADIUS возвращает все соответствующие элементы местоположения. Хотя пользователь может использовать параметр COUNT для получения первых N совпадающих элементов, поскольку команде может потребоваться внутренняя обработка всех совпадающих элементов, при поиске в очень большой области даже с использованием параметра COUNT для получения небольшого числа элементов выполнение команды также может быть очень медленным. Но, с другой стороны, использование параметра COUNT для уменьшения количества возвращаемых элементов по-прежнему очень полезно для уменьшения пропускной способности.

2.5 Получить набор географических сведений о местоположении указанного диапазона элементов

GEORADIUSBYMEMBER key member radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC|DESC] [COUNT count]

eg:

Найти транспортные средства в пределах 5 километров от транспортного средства номер 1 ГЕОРА

127.0.0.1:6379> GEORADIUSBYMEMBER cars:locations 2 5 km WITHCOORD WITHDIST WITHHASH  ASC COUNT 100
1) 1) "2"
   2) "0.0000"
   3) (integer) 4054421167795118
   4) 1) "120.37582129240036011"
      2) "31.5603669915025975"
2) 1) "1"
   2) "2.8157"
   3) (integer) 4054421060663027
   4) 1) "120.34611314535140991"
      2) "31.55637987511895659"

Соответствующие необязательные параметры такие же, как в 2.4.

3 Redis GEO реализует близлежащие функции XXX

Изучив Redis GEO API, вы можете обнаружить, что пока вы вызываете клиент Redis

2.4 Получить набор географических сведений о местоположении указанного диапазона местоположений

API может реализовать соответствующие требования. так легко! ! !

4 принципа Redis GEO

4.1 Структура хранения

Redis имеет соответствующие методы кодирования при хранении данных разных типов. Какой метод кодирования используется для хранения Redis GEO?

Просматривая Redis GEO API, я обнаружил, что он не удалил инструкцию, потому что нижний слой должен использоватьzsetбыть реализованным. Мы можем использовать zrem для удаления данных.

Затем попробуйте использовать команду запроса zset для запроса информации GEO, добавленной выше.

127.0.0.1:6379> ZRANGE cars:locations  0 -1 WITHSCORES
1) "1"
2) "4054421060663027"
3) "2"
4) "4054421167795118"

Найдено, что информация о местоположении транспортного средства № 1 — 4054421060663027, информация о местоположении транспортного средства № 2 — 4054421167795118. Давайте рассмотрим инструкции по добавлению участников в zset.

ZADD key score member [[score member] [score member] ...]

На данный момент можно сделать вывод, что процесс добавления информации о широте и долготе в Redis GEO выглядит следующим образом:

ZADD cars:locations 4054421060663027 1

4054421060663027 — закодированное значение широты и долготы. Используя 4054421060663027 в качестве оценки, можно быстро реализовать индекс долготы и широты.

Просмотрите соответствующие документы и обнаружите, что Redis использует геохэш для кодирования информации о широте и долготе.

4.2 Анализ принципа геохеширования

Что касается основных принципов геохеширования, эта статья очень хорошо анализируетАнализ основных принципов GeoHash

Подводя итог,

Как уникально представить кусок космоса на Земле?
Как разрезать землю на куски одинакового размера и поддерживать представления с разной степенью детализации?

Чтобы решить две вышеупомянутые проблемы, нам нужно три шага.

Первый шаг — превратить трехмерную землю в двухмерную;
Второй шаг — преобразовать двумерное в одномерное;
Последним шагом является представление одномерного представления в виде двоичного кода для хранения.

4.2.1 Как изменить 3D на 2D?

Интервал широты земли [-90,90], а интервал долготы [-180,180]. Разверните его, чтобы представить длинный прямоугольник в виде

4.2.2 Как конвертировать 2D в 1D?

С помощью этого метода мы можем преобразовать поверхность земли в плоскость в двумерном пространстве. Затем следующим шагом будет преобразование двумерного изображения в одномерное. Если разрезать двухмерное пространство, можно вырезать много квадратов. Как изобразить этот квадрат? Самый простой способ — перелететь на самолете. Каждый раз, когда точка проходится, она помечается значением, например 00, 01, 10, 11. Увеличение двоичного числа эквивалентно прохождению различных позиций на поверхности.

Когда пространство разделено на четыре блока, порядок кодирования: 00 в нижнем левом углу, 01 в верхнем левом углу, 10 в нижнем правом углу и 11 в верхнем правом углу, что представляет собой кривую, подобную Z.

Как представить различные степени детализации?

Когда мы рекурсивно разбиваем каждый блок на более мелкие подблоки, мы можем определить меньшие пространственные диапазоны (как показано на рисунке 2 выше).Например, последовательность кодирования от 0000 до 1111 является самоподобной (фрактальной), каждый подграфик A также образует Z-кривую, этот тип кривой называется кривой Пеано, заполняющей пространство.

4.2.3 Как представить одно измерение как хранилище двоичного кода

Geohash также имеет несколько форм кодирования, есть две распространенные, base 32 и base 36. будет кодировать двоичные данные, попадающие в сетку, в строку

Хвостик

Проанализировав принцип реализации Redis GEO, было обнаружено, что в его основе лежит геохэш, который используется для кодирования двумерных данных широты и долготы в одномерные данные, а затем индекс B-дерева используется для быстрого найти необходимые данные.

При использовании Redis GEO для реализации вышеуказанных функций, таких как находящиеся поблизости люди, транспортные средства поблизости и предприятия поблизости, вы можете выполнять поиск только по радиусу.

В: Что делать, если требуется найти все предприятия в пределах 5 километров, которые продают кофе?

О: Конечно, мы можем фильтровать все данные, запрашиваемые Reids, на прикладном уровне.

Вопрос: Когда объем данных, возвращаемых Redis, и количество пользовательских запросов относительно велики, он очень сильно потребляет ресурсы памяти.Есть ли лучшее решение? Существуют ли уже лучшие решения в реализации баз данных в отрасли?

A: Имея в виду этот вопрос, я искал соответствующую информацию и обнаружил, что geohash на самом деле является реализацией пространственного индекса MySql и MongoDB, которые мы часто используем, имеют реализации пространственного индекса.

MongoDB

Объектами GeoJSON в монго являются точка, линия, многоугольник, многолинейный сегмент, мультиточка, мультиполигон. Поддержка содержит, пересекает, смежный запрос и одновременно поддерживает запрос с несколькими условиями. (Это кажется очень мощным, и действительно можно изменить решение, и могут быть качественные преимущества.)

MySql

MySql InnoDB добавил поддержку пространственных индексов только в лабораторной версии 5.7.4, и все они реализуют пространственные индексы через R-деревья.

Стоимость обновления MySql очень высока.После понимания принципа геохэша мы можем добавить поле геохэша в таблицу MySql и быстро найти данные с помощью метода двоичного поиска числа B.

В следующем блоге будет обобщена соответствующая практика ручного расчета реализации индекса B-дерева geohash + MySql, а также сопоставлены различия в пространстве хранения и эффективности запросов пространственного индекса, который поставляется с MySql.