об авторе
Ван Ми, старший инженер-разработчик Ele.me. iOS, Go, Java — все задействовано. В настоящее время занимается разработкой больших данных. Любит кататься и лазить по горам.
Предисловие: Для сценария приложения «близких людей» в сфере услуг определения местоположения обычно для реализации используются пространственные индексы различных БД, таких как PG, MySQL и MongoDB. Redis применил другой подход в сочетании с упорядоченной очередью zset и кодированием геохэша для реализации функции пространственного поиска и чрезвычайно высокой операционной эффективности. В этой статье будет проанализирован принцип его алгоритма с точки зрения исходного кода и рассчитана временная сложность запроса.
Чтобы обеспечить полноценный сервис «люди поблизости», самое основное — реализовать функции «добавить», «удалить» и «проверить». Отдельно будет представлено следующее, в котором будет проанализирована функция запроса.
Команда операции
Начиная с Redis 3.2, Redis основан наgeohashа такжеотсортированный наборПредоставляются функции, связанные с геолокацией. Модуль Redis Geo содержит следующие 6 команд:
- GEOADD: добавить заданный объект местоположения (широта, долгота, имя) к указанному ключу;
- GEOPOS: возвращает местоположение (долготу и широту) всех заданных объектов местоположения из ключа;
- ГЕОРАСП: возвращает расстояние между двумя заданными местоположениями;
- GEOHASH: возвращает представление Geohash одного или нескольких объектов местоположения;
- GEORADIUS: С заданной широтой и долготой в качестве центра вернуть все объекты положения в целевом наборе, расстояние от центра которых не превышает заданное максимальное расстояние;
- GEORADIUSBYMEMBER: центрирует заданный объект местоположения и возвращает все объекты местоположения в пределах заданного максимального расстояния от него.
Среди них комбинированное использование GEOADD и GEORADIUS позволяет реализовать основные функции «добавления» и «проверки» в «людях рядом». Чтобы реализовать функцию «Люди поблизости» в WeChat, вы можете напрямую использовать команду GEORADIUSBYMEMBER. «Заданный объект местоположения» — это сам пользователь, а искомый объект — другие пользователи. Однако, по сути, GEORADIUSBYMEMBER = GEOPOS + GEORADIUS, то есть сначала найти местоположение пользователя, а затем использовать местоположение для поиска других близлежащих объектов пользователя, удовлетворяющих условию взаимного расстояния местоположения.
Далее будут проанализированы команды GEOADD и GEORADIUS с точки зрения исходного кода и проанализированы принципы их алгоритмов.
Геооперации Redis включают только операции «добавить» и «проверить», специальной команды «удалить» нет. Главным образом потому, что Redis внутри использует упорядоченный набор (zset) для сохранения объектов местоположения, которые можно удалить с помощью zrem.
В комментариях к файлу исходного кода Redis geo.c указано лишь, что файл является файлом реализации GEOADD, GEORADIUS и GEORADIUSBYMEMBER (на самом деле реализованы и три другие команды). Остальные три команды видны со стороны как вспомогательные команды.
GEOADD
Как пользоваться
GEOADD key longitude latitude member [longitude latitude member ...]
Добавляет заданный объект местоположения (широта, долгота, имя) к указанному ключу.
Среди них ключ — это имя коллекции, а член — это объект, соответствующий широте и долготе. В практических приложениях, когда количество объектов, которые нужно сохранить, слишком велико, можно выполнить сегментирование коллекции объектов в замаскированной форме, установив несколько ключей (например, сохраняя один ключ на ключ), чтобы избежать чрезмерного количества отдельных коллекций.
Возвращаемое значение после успешной вставки:
(integer) N
где N — количество успешных вставок.
Анализ исходного кода
/* GEOADD key long lat name [long2 lat2 name2 ... longN latN nameN] */
void geoaddCommand(client *c) {
//参数校验
/* Check arguments number for sanity. */
if ((c->argc - 2) % 3 != 0) {
/* Need an odd number of arguments if we got this far... */
addReplyError(c, "syntax error. Try GEOADD key [x1] [y1] [name1] "
"[x2] [y2] [name2] ... ");
return;
}
//参数提取Redis
int elements = (c->argc - 2) / 3;
int argc = 2+elements*2; /* ZADD key score ele ... */
robj **argv = zcalloc(argc*sizeof(robj*));
argv[0] = createRawStringObject("zadd",4);
argv[1] = c->argv[1]; /* key */
incrRefCount(argv[1]);
//参数遍历+转换
/* Create the argument vector to call ZADD in order to add all
* the score,value pairs to the requested zset, where score is actually
* an encoded version of lat,long. */
int i;
for (i = 0; i < elements; i++) {
double xy[2];
//提取经纬度
if (extractLongLatOrReply(c, (c->argv+2)+(i*3),xy) == C_ERR) {
for (i = 0; i < argc; i++)
if (argv[i]) decrRefCount(argv[i]);
zfree(argv);
return;
}
//将经纬度转换为52位的geohash作为分值 & 提取对象名称
/* Turn the coordinates into the score of the element. */
GeoHashBits hash;
geohashEncodeWGS84(xy[0], xy[1], GEO_STEP_MAX, &hash);
GeoHashFix52Bits bits = geohashAlign52Bits(hash);
robj *score = createObject(OBJ_STRING, sdsfromlonglong(bits));
robj *val = c->argv[2 + i * 3 + 2];
//设置有序集合的对象元素名称和分值
argv[2+i*2] = score;
argv[3+i*2] = val;
incrRefCount(val);
}
//调用zadd命令，存储转化好的对象
/* Finally call ZADD that will do the work for us. */
replaceClientCommandVector(c,argc,argv);
zaddCommand(c);
}
Из анализа исходного кода видно, что Redis использует упорядоченный набор (zset) для хранения объектов местоположения. Каждый элемент в упорядоченном наборе представляет собой объект с местоположением. Значение оценки элемента представляет собой 52-битное значение геохэша, соответствующее на его долготу и широту.
Точность типа double составляет 52 бита;
Geohash закодирован в base32, и 52 бита могут хранить до 10-битных значений geohash, соответствующих сетке с размером географической области 0,6 * 0,6 метра. Другими словами, позиция, преобразованная Redis geo, теоретически будет иметь ошибку около 0,3 * 1,414 = 0,424 метра.
Краткое описание алгоритма
Кратко опишите, что делает команда GEOADD:
1. Извлечение и проверка параметров;
2. Преобразовать введенные широту и долготу в 52-битное значение геохэша (счет);
3. Вызовите команду ZADD, чтобы сохранить элемент и соответствующий ему счет в ключе set.
GEORADIUS
Как пользоваться
GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC|DESC] [COUNT count] [STORE key] [STORedisT key]
С центром на заданной широте и долготе возвращает все объекты местоположения в целевой коллекции, которые находятся в пределах заданного максимального расстояния от центра.
Единицы диапазона: м | км | футы | мили --> метры | километры | футы | мили
Дополнительные параметры:
- WITHDIST: при возврате объекта положения также возвращается расстояние между объектом положения и центром. Единица измерения расстояния соответствует единице дальности, заданной пользователем.
- WITHCOORD: возвращает долготу и широту объекта местоположения.
- WITHHASH: возвращает необработанный упорядоченный набор оценок объекта местоположения, закодированный с помощью геохэша, в виде 52-битного целого числа со знаком. Этот параметр в основном используется для низкоуровневых приложений или отладки и на практике малоэффективен.
- ASC|DESC: Возвращает элементы объекта положения от ближнего к дальнему | Возвращает элементы объекта положения от дальнего к ближнему.
- COUNT count: выберите первые N совпадающих элементов объекта position. (возвращает все элементы, если они не установлены)
- Клавиша STORE: сохранить информацию о географическом местоположении возвращенного результата в указанную клавишу.
- Клавиша STORedisT: сохраните расстояние между возвращаемым результатом и центральной точкой для указанной клавиши.
Из-за наличия опций STORE и STORedisT команды GEORADIUS и GEORADIUSBYMEMBER будут технически помечены как команды записи, так что можно будет запрашивать (записывать) только первичный экземпляр.Когда число запросов в секунду слишком велико, легко вызвать чрезмерное давление чтения и записи на основной экземпляр. Чтобы решить эту проблему, в Redis 3.2.10 и Redis 4.0.0 были добавлены две команды только для чтения, GEORADIUS_RO и GEORADIUSBYMEMBER_RO соответственно.
Однако в реальной разработке автор обнаружил, что в пакете javaRedis.clients.jedis.params.geoКласс параметров GeoRadiusParam для GeoRadiusParam не содержит двух опций параметров, STORE и STORedisT.При вызове georadius действительно запрашивается только основной экземпляр или это инкапсуляция только для чтения. Заинтересованные друзья могут изучить его самостоятельно.
Возвращаемое значение после успешного запроса:
Без квалификации WITH возвращает список элементов, например:
["member1","member2","member3"]
С квалификацией WITH каждый элемент в списке элементов также является вложенным списком, например:
[
["member1", distance1, [longitude1, latitude1]]
["member2", distance2, [longitude2, latitude2]]
]
Анализ исходного кода
Этот исходный код длинный, если вы не можете его прочитать, вы можете напрямую прочитать комментарии на китайском языке или сразу перейти к сводному разделу.
/* GEORADIUS key x y radius unit [WITHDIST] [WITHHASH] [WITHCOORD] [ASC|DESC]
* [COUNT count] [STORE key] [STORedisT key]
* GEORADIUSBYMEMBER key member radius unit ... options ... */
void georadiusGeneric(client *c, int flags) {
robj *key = c->argv[1];
robj *storekey = NULL;
int stoRedist = 0; /* 0 for STORE, 1 for STORedisT. */
//根据key获取有序集合
robj *zobj = NULL;
if ((zobj = lookupKeyReadOrReply(c, key, shared.null[c->resp])) == NULL ||
checkType(c, zobj, OBJ_ZSET)) {
return;
}
//根据用户输入（经纬度/member）确认中心点经纬度
int base_args;
double xy[2] = { 0 };
if (flags & RADIUS_COORDS) {
……
}
//获取查询范围距离
double radius_meters = 0, conversion = 1;
if ((radius_meters = extractDistanceOrReply(c, c->argv + base_args - 2,
&conversion)) < 0) {
return;
}
//获取可选参数 （withdist、withhash、withcoords、sort、count）
int withdist = 0, withhash = 0, withcoords = 0;
int sort = SORT_NONE;
long long count = 0;
if (c->argc > base_args) {
... ...
}
//获取 STORE 和 STORedisT 参数
if (storekey && (withdist || withhash || withcoords)) {
addReplyError(c,
"STORE option in GEORADIUS is not compatible with "
"WITHDIST, WITHHASH and WITHCOORDS options");
return;
}
//设定排序
if (count != 0 && sort == SORT_NONE) sort = SORT_ASC;
//利用中心点和半径计算目标区域范围
GeoHashRadius georadius =
geohashGetAreasByRadiusWGS84(xy[0], xy[1], radius_meters);
//对中心点及其周围8个geohash网格区域进行查找，找出范围内元素对象
geoArray *ga = geoArrayCreate();
membersOfAllNeighbors(zobj, georadius, xy[0], xy[1], radius_meters, ga);
//未匹配返空
/* If no matching results, the user gets an empty reply. */
if (ga->used == 0 && storekey == NULL) {
addReplyNull(c);
geoArrayFree(ga);
return;
}
//一些返回值的设定和返回
……
geoArrayFree(ga);
}
В приведенном выше коде есть два основных шага: один — «вычислить диапазон центральной точки», а другой — «найти центральную точку и окружающие ее 8 областей сетки геохеширования». соответствуетgeohashGetAreasByRadiusWGS84а такжеmembersOfAllNeighborsдве функции. Давайте посмотрим на это по очереди:
- Вычислить диапазон центральной точки:
// geohash_helper.c
GeoHashRadius geohashGetAreasByRadiusWGS84(double longitude, double latitude,
double radius_meters) {
return geohashGetAreasByRadius(longitude, latitude, radius_meters);
}
//返回能够覆盖目标区域范围的9个geohashBox
GeoHashRadius geohashGetAreasByRadius(double longitude, double latitude, double radius_meters) {
//一些参数设置
GeoHashRange long_range, lat_range;
GeoHashRadius radius;
GeoHashBits hash;
GeoHashNeighbors neighbors;
GeoHashArea area;
double min_lon, max_lon, min_lat, max_lat;
double bounds[4];
int steps;
//计算目标区域外接矩形的经纬度范围（目标区域为：以目标经纬度为中心，半径为指定距离的圆）
geohashBoundingBox(longitude, latitude, radius_meters, bounds);
min_lon = bounds[0];
min_lat = bounds[1];
max_lon = bounds[2];
max_lat = bounds[3];
//根据目标区域中心点纬度和半径，计算带查询的9个搜索框的geohash精度（位）
//这里用到latitude主要是针对极地的情况对精度进行了一些调整（纬度越高，位数越小）
steps = geohashEstimateStepsByRadius(radius_meters,latitude);
//设置经纬度最大最小值：-180<=longitude<=180, -85<=latitude<=85
geohashGetCoordRange(&long_range,&lat_range);
//将待查经纬度按指定精度（steps）编码成geohash值
geohashEncode(&long_range,&lat_range,longitude,latitude,steps,&hash);
//将geohash值在8个方向上进行扩充，确定周围8个Box（neighbors）
geohashNeighbors(&hash,&neighbors);
//根据hash值确定area经纬度范围
geohashDecode(long_range,lat_range,hash,&area);
//一些特殊情况处理
……
//构建并返回结果
radius.hash = hash;
radius.neighbors = neighbors;
radius.area = area;
return radius;
}
- Найдите центральную точку и окружающие ее 8 областей сетки геохеширования:
// geo.c
//在9个hashBox中获取想要的元素
int membersOfAllNeighbors(robj *zobj, GeoHashRadius n, double lon, double lat, double radius, geoArray *ga) {
GeoHashBits neighbors[9];
unsigned int i, count = 0, last_processed = 0;
int debugmsg = 0;
//获取9个搜索hashBox
neighbors[0] = n.hash;
……
neighbors[8] = n.neighbors.south_west;
//在每个hashBox中搜索目标点
for (i = 0; i < sizeof(neighbors) / sizeof(*neighbors); i++) {
if (HASHISZERO(neighbors[i])) {
if (debugmsg) D("neighbors[%d] is zero",i);
continue;
}
//剔除可能的重复hashBox (搜索半径>5000KM时可能出现)
if (last_processed &&
neighbors[i].bits == neighbors[last_processed].bits &&
neighbors[i].step == neighbors[last_processed].step)
{
continue;
}
//搜索hashBox中满足条件的对象
count += membersOfGeoHashBox(zobj, neighbors[i], ga, lon, lat, radius);
last_processed = i;
}
return count;
}
int membersOfGeoHashBox(robj *zobj, GeoHashBits hash, geoArray *ga, double lon, double lat, double radius) {
//获取hashBox内的最大、最小geohash值（52位）
GeoHashFix52Bits min, max;
scoresOfGeoHashBox(hash,&min,&max);
//根据最大、最小geohash值筛选zobj集合中满足条件的点
return geoGetPointsInRange(zobj, min, max, lon, lat, radius, ga);
}
int geoGetPointsInRange(robj *zobj, double min, double max, double lon, double lat, double radius, geoArray *ga) {
//搜索Range的参数边界设置（即9个hashBox其中一个的边界范围）
zrangespec range = { .min = min, .max = max, .minex = 0, .maxex = 1 };
size_t origincount = ga->used;
sds member;
//搜索集合zobj可能有ZIPLIST和SKIPLIST两种编码方式，这里以SKIPLIST为例，逻辑是一样的
if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
……
} else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
zset *zs = zobj->ptr;
zskiplist *zsl = zs->zsl;
zskiplistNode *ln;
//获取在hashBox范围内的首个元素（跳表数据结构，效率可比拟于二叉查找树），没有则返0
if ((ln = zslFirstInRange(zsl, &range)) == NULL) {
/* Nothing exists starting at our min. No results. */
return 0;
}
//从首个元素开始遍历集合
while (ln) {
sds ele = ln->ele;
//遍历元素超出range范围则break
/* Abort when the node is no longer in range. */
if (!zslValueLteMax(ln->score, &range))
break;
//元素校验（计算元素与中心点的距离）
ele = sdsdup(ele);
if (geoAppendIfWithinRadius(ga,lon,lat,radius,ln->score,ele)
== C_ERR) sdsfree(ele);
ln = ln->level[0].forward;
}
}
return ga->used - origincount;
}
int geoAppendIfWithinRadius(geoArray *ga, double lon, double lat, double radius, double score, sds member) {
double distance, xy[2];
//解码错误, 返回error
if (!decodeGeohash(score,xy)) return C_ERR; /* Can't decode. */
//最终距离校验(计算球面距离distance看是否小于radius)
if (!geohashGetDistanceIfInRadiusWGS84(lon,lat, xy[0], xy[1],
radius, &distance))
{
return C_ERR;
}
//构建并返回满足条件的元素
geoPoint *gp = geoArrayAppend(ga);
gp->longitude = xy[0];
gp->latitude = xy[1];
gp->dist = distance;
gp->member = member;
gp->score = score;
return C_OK;
}
Краткое описание алгоритма
Помимо множества необязательных параметров, кратко опишите, как команда GEORADIUS использует геохэш для получения объекта целевого местоположения:
1. Извлечение и проверка параметров;
2. Используйте центральную точку и введенный радиус, чтобы вычислить площадь для проверки. Этот параметр диапазона включает в себя самый высокий уровень сетки геохэша (точность), который соответствует условиям, и соответствующее положение сетки из девяти квадратов, которое может покрыть целевую область; (подробности будут даны позже)
3. Пройдите по сетке Jiugong и выберите объект положения в соответствии с полем диапазона каждой сетки геохеширования. Далее узнаем объект, расстояние от центральной точки которого меньше входного радиуса, и возвращаем его.
Прямое описание понять непросто, поэтому кратко продемонстрируем алгоритм на следующих двух рисунках:
Пусть центр левого изображения будет центром поиска, зеленая круглая область — целевой областью, все точки — объектами положения, подлежащими поиску, а красные точки — объектами положения, удовлетворяющими условиям.
При фактическом поиске уровень сетки геохэша (то есть уровень размера сетки на правом изображении) сначала вычисляется в соответствии с радиусом поиска и положением сетки из девяти квадратов (то есть информацией о положении красного сетка из девяти квадратов); затем отфильтровываются точки в сетке из девяти квадратов (синяя точка и расстояние между красной точкой) и центральная точка, и, наконец, точки (красные точки) в пределах диапазона расстояний.
Анализ алгоритмов
Зачем использовать эту стратегию алгоритма для запроса, или в чем преимущества этой стратегии, давайте проанализируем и объясним в форме вопроса и ответа.
-
Зачем искать самый высокий уровень сетки геохеширования, который удовлетворяет условию? Зачем использовать Jiugongge?
На самом деле это задача, которая по сути является предварительным просмотром всех объектов-элементов. В многослойной сетке геохеширования каждая низкоуровневая сетка геохеширования формируется путем сращивания 4 сеток более высокого уровня (как показано на рисунке).
Другими словами, чем выше уровень сетки геохеширования, тем меньше охватываемая географическая область. Когда мы вычисляем сетку из девяти квадратов (сетку) самого высокого уровня, которая может покрыть целевую область на основе входного радиуса и положения центральной точки, элементы за пределами девяти квадратов отсеиваются. Основная причина использования сетки из девяти квадратов вместо одиночной — избежать граничных условий и максимально сузить область запроса. Представьте, что вы принимаете 0 широты и долготы в качестве центра, даже если вы проверите диапазон в 1 метр, если одна сетка покрывает всю площадь земли. Расширение круга во всех восьми направлениях может эффективно избежать этой проблемы.
-
Как выбрать объект элемента по ограничивающей рамке сетки геохеш? Насколько это эффективно?
Во-первых, значения геохеша в каждой сетке геохэша непрерывны и имеют фиксированный диапазон. Так что просто узнайте положение объекта в диапазоне в отсортированном наборе. Ниже приведен упорядоченный наборпропустить столструктура данных:
Он имеет эффективность запроса, аналогичную бинарному дереву поиска, а средняя временная сложность операции составляет O (log (N)). А все элементы внизу расположены по порядку в виде связанного списка. Поэтому при запросе вам нужно только найти первое значение в сетке целевого геохэша в коллекции, а затем последовательно сравнивать его, не выполняя многократный поиск. Сетку из девяти квадратов нельзя проверить вместе, и причина обхода по одному заключается в том, что значения геохэша, соответствующие каждой сетке сетки из девяти квадратов, не являются непрерывными. Только если он непрерывный, эффективность запроса будет высокой, иначе потребуется много дистанционных операций.
Таким образом, мы проанализировали подробный процесс «добавления (GEOADD)» и «проверки (GEORADIUS)» в модуле Redis Geo с точки зрения исходного кода. И можно рассчитать, что функция GEORADIUS для поиска ближайших людей в Redis, временная сложность: O (N + log (M)). Среди них N — количество элементов положения в сетке из девяти квадратов (расстояние должно быть рассчитано), M — количество заданных сеток уровней, а log(M) — временная сложность нахождения первого элемента каждой сетка в структуре таблицы пропуска (этот процесс обычно занимает 9 секунд). В сочетании с характеристиками хранилища на основе памяти самого Redis, он имеет очень высокую эффективность работы в процессе фактического использования.
Reference
Справочник по командам Redis
geohash
Список пропусков структуры данных ZSET в Redis
Недостаточно читать блоги?
Вы можете отсканировать QR-код, добавив группового помощника, присоединиться к группе общения, обсудить технические вопросы, связанные с ведением блога, и больше взаимодействовать с блогерами.
По вопросам перепечатки блога, офлайн-мероприятий и сотрудничества обращайтесь по адресуyidong.zheng@ele.meобщаться