Redis 源碼剖析之 GEO——Redis 是如何高效檢索地理位置的？
作者：xindoo
來源：SegmentFault 思否社區(qū)
Redis GEO 用做存儲地理位置信息，并對存儲的信息進行操作。通過geo相關(guān)的命令，可以很容易在redis中存儲和使用經(jīng)緯度坐標信息。Redis中提供的Geo命令有如下幾個：
geoadd：添加經(jīng)緯度坐標和對應(yīng)地理位置名稱。 geopos：獲取地理位置的經(jīng)緯度坐標。 geodist：計算兩個地理位置的距離。 georadius：根據(jù)用戶給定的經(jīng)緯度坐標來獲取指定范圍內(nèi)的地理位置集合。 georadiusbymember：根據(jù)儲存在位置集合里面的某個地點獲取指定范圍內(nèi)的地理位置集合。 geohash：計算一個或者多個經(jīng)緯度坐標點的geohash值。
geohash
116.404844,39.912279，通過12位geohash編碼后就變成了wx4g0cg3vknd，它究竟是如何實現(xiàn)的？其實原理非常簡單，就是二分，整個編碼過程可以分為如下幾步。1. 轉(zhuǎn)二進制
比如還是北京市中心的經(jīng)緯度坐標
116.404844,39.912279，我們先對116.404844做編碼，得到其二進制為:11010010110001101101
39.912279編碼得到二進制為：10111000110000111001
2. 經(jīng)緯度二進制合并
1101101110000200111100000001111011010011
3. 將合并后的二進制做base32編碼
geohash的用途及問題
geohash有個需要注意的問題。geohash是將二維的坐標點做了線下編碼(如下圖)，有時候可能會給人一個誤解就是如果兩個geohash之間二進制的差異越小，這兩個區(qū)間距離就越近，這完全是錯誤的，比如如下圖0111和1000，這倆區(qū)間二進制只差0001但實際物理距離比較遠。
如果上圖還不明顯的話，我從Wikipedia上拿到一張圖，虛線是線性索引的路徑，被虛線鏈接的兩個塊geohash值是非常相近的，如下圖的(7,3)和(0,4)，geohash值會非常相近，但實際物理距離非常遠，這就是geohash的突變現(xiàn)象，這也導(dǎo)致了不能直接根據(jù)geohash的值來直接判定兩個區(qū)域的距離大小。
但在實際使用geohash過程中，時常會遇到跨域搜索的情況，比如我要在上圖(3,3)這個區(qū)間內(nèi)某個點上搜索距它1個距離單位的所有其他點集，這個點集有可能橫跨(3,3)加上它周圍8個鄰域的9個區(qū)間，突變的問題會導(dǎo)致這9個區(qū)間的geohash不是線性跳轉(zhuǎn)的，但也不是沒法計算，實際上可以通過特殊的位運算可以很輕易計算出某個geohash的8個鄰域，具體可參考redis源碼中src/geohash.c中g(shù)eohashNeighbors()的具體實現(xiàn)，geohashNeighbors使用了geohash_move_x和geohash_move_y兩個函數(shù)實現(xiàn)了geohash左右和上下的移動，這樣可以很容易組合出8個鄰域的geohash值了。
static void geohash_move_x(GeoHashBits *hash, int8_t d) {
if (d == 0)
return;
uint64_t x = hash->bits & 0xaaaaaaaaaaaaaaaaULL;
uint64_t y = hash->bits & 0x5555555555555555ULL;
uint64_t zz = 0x5555555555555555ULL >> (64 - hash->step * 2);
if (d > 0) {
x = x + (zz + 1);
} else {
x = x | zz;
x = x - (zz + 1);
}
x &= (0xaaaaaaaaaaaaaaaaULL >> (64 - hash->step * 2));
hash->bits = (x | y);
}
static void geohash_move_y(GeoHashBits *hash, int8_t d) {
if (d == 0)
return;
uint64_t x = hash->bits & 0xaaaaaaaaaaaaaaaaULL;
uint64_t y = hash->bits & 0x5555555555555555ULL;
uint64_t zz = 0xaaaaaaaaaaaaaaaaULL >> (64 - hash->step * 2);
if (d > 0) {
y = y + (zz + 1);
} else {
y = y | zz;
y = y - (zz + 1);
}
y &= (0x5555555555555555ULL >> (64 - hash->step * 2));
hash->bits = (x | y);
}
Geo in redis
首先，可能大家最好奇的是geohash在redis中是怎么存儲的，從geoadd命令的實現(xiàn)可以一窺端倪。
/* GEOADD key [CH] [NX|XX] long lat name [long2 lat2 name2 ... longN latN nameN] */
void geoaddCommand(client *c) {
int xx = 0, nx = 0, longidx = 2;
int i;
/* 解析可選參數(shù) */
while (longidx < c->argc) {
char *opt = c->argv[longidx]->ptr;
if (!strcasecmp(opt,"nx")) nx = 1;
else if (!strcasecmp(opt,"xx")) xx = 1;
else if (!strcasecmp(opt,"ch")) {}
else break;
longidx++;
}
if ((c->argc - longidx) % 3 || (xx && nx)) {
/* 解析所有的經(jīng)緯度值和member，并對其個數(shù)做校驗 */
addReplyErrorObject(c,shared.syntaxerr);
return;
}
/* 構(gòu)建zadd的參數(shù)數(shù)組 */
int elements = (c->argc - longidx) / 3;
int argc = longidx+elements*2; /* ZADD key [CH] [NX|XX] score ele ... */
robj **argv = zcalloc(argc*sizeof(robj*));
argv[0] = createRawStringObject("zadd",4);
for (i = 1; i < longidx; i++) {
argv[i] = c->argv[i];
incrRefCount(argv[i]);
}
/* 以3個參數(shù)為一組，將所有的經(jīng)緯度和member信息從參數(shù)列表里解析出來，并放到zadd的參數(shù)數(shù)組中 */
for (i = 0; i < elements; i++) {
double xy[2];
if (extractLongLatOrReply(c, (c->argv+longidx)+(i*3),xy) == C_ERR) {
for (i = 0; i < argc; i++)
if (argv[i]) decrRefCount(argv[i]);
zfree(argv);
return;
}
/* 將經(jīng)緯度坐標轉(zhuǎn)化成score信息 */
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[longidx + i * 3 + 2];
argv[longidx+i*2] = score;
argv[longidx+1+i*2] = val;
incrRefCount(val);
}
/* 轉(zhuǎn)化成zadd命令所需要的參數(shù)格式*/
replaceClientCommandVector(c,argc,argv);
zaddCommand(c);
}
void georadiusGeneric(client *c, int srcKeyIndex, int flags) {
robj *storekey = NULL;
int storedist = 0; /* 0 for STORE, 1 for STOREDIST. */
/* 根據(jù)key找找到對應(yīng)的zojb */
robj *zobj = NULL;
if ((zobj = lookupKeyReadOrReply(c, c->argv[srcKeyIndex], shared.emptyarray)) == NULL ||
checkType(c, zobj, OBJ_ZSET)) {
return;
}
/* 解析請求中的經(jīng)緯度值 */
int base_args;
GeoShape shape = {0};
if (flags & RADIUS_COORDS) {
/*
* 各種必選參數(shù)的解析，省略細節(jié)代碼，主要是解析坐標點信息和半徑
*/
}
/* 解析所有的可選參數(shù). */
int withdist = 0, withhash = 0, withcoords = 0;
int frommember = 0, fromloc = 0, byradius = 0, bybox = 0;
int sort = SORT_NONE;
int any = 0; /* any=1 means a limited search, stop as soon as enough results were found. */
long long count = 0; /* Max number of results to return. 0 means unlimited. */
if (c->argc > base_args) {
/*
* 各種可選參數(shù)的解析，省略細節(jié)代碼
*/
}
/* Get all neighbor geohash boxes for our radius search
* 獲取到要查找范圍內(nèi)所有的9個geo鄰域 */
GeoHashRadius georadius = geohashCalculateAreasByShapeWGS84(&shape);
/* 創(chuàng)建geoArray存儲結(jié)果列表 */
geoArray *ga = geoArrayCreate();
/* 掃描9個區(qū)域中是否有滿足條的點，有就放到geoArray中 */
membersOfAllNeighbors(zobj, georadius, &shape, ga, any ? count : 0);
/* 如果沒有匹配結(jié)果，返回空對象 */
if (ga->used == 0 && storekey == NULL) {
addReply(c,shared.emptyarray);
geoArrayFree(ga);
return;
}
long result_length = ga->used;
long returned_items = (count == 0 || result_length < count) ?
result_length : count;
long option_length = 0;
/*
* 后續(xù)一些參數(shù)邏輯，比如處理排序，存儲……
*/
// 釋放geoArray占用的空間
geoArrayFree(ga);
}
解析請求參數(shù)。 計算目標坐標所在的geohash和8個鄰居。 在zset中查找這9個區(qū)域中滿足距離限制的所有點集。 處理排序等后續(xù)邏輯。 清理臨時存儲空間。
結(jié)語
評論
圖片
表情