Redis GEO 用做存儲(chǔ)地理位置信息，并對(duì)存儲(chǔ)的信息進(jìn)行操作。通過(guò)geo相關(guān)的命令，可以很容易在redis中存儲(chǔ)和使用經(jīng)緯度坐標(biāo)信息。Redis中提供的Geo命令有如下幾個(gè)：

• geoadd：添加經(jīng)緯度坐標(biāo)和對(duì)應(yīng)地理位置名稱。
• geopos：獲取地理位置的經(jīng)緯度坐標(biāo)。
• geodist：計(jì)算兩個(gè)地理位置的距離。
• georadius：根據(jù)用戶給定的經(jīng)緯度坐標(biāo)來(lái)獲取指定范圍內(nèi)的地理位置集合。
• georadiusbymember：根據(jù)儲(chǔ)存在位置集合里面的某個(gè)地點(diǎn)獲取指定范圍內(nèi)的地理位置集合。
• geohash：計(jì)算一個(gè)或者多個(gè)經(jīng)緯度坐標(biāo)點(diǎn)的geohash值。

要理解Redis的GEO相關(guān)的命令是如何實(shí)現(xiàn)了，就得先理解geohash的原理，本質(zhì)上這些命令就是對(duì)geohash數(shù)據(jù)的封裝而已。

geohash

geohash是2008年Gustavo Niemeye發(fā)明用來(lái)編碼經(jīng)緯度信息的一種編碼方式，比如北京市中心的經(jīng)緯度坐標(biāo)是116.404844,39.912279，通過(guò)12位geohash編碼后就變成了wx4g0cg3vknd，它究竟是如何實(shí)現(xiàn)的？其實(shí)原理非常簡(jiǎn)單，就是二分，整個(gè)編碼過(guò)程可以分為如下幾步。

1. 轉(zhuǎn)二進(jìn)制

上過(guò)初中地理的我們都知道，地球上如何一個(gè)點(diǎn)就可以標(biāo)識(shí)為某個(gè)經(jīng)緯度坐標(biāo)，經(jīng)度的取值范圍是東經(jīng)0-180度和西經(jīng)0-180度，維度的取值范圍是北緯0到90和南緯0-90度。去掉東西南北，可以分別認(rèn)為經(jīng)度和維度的取值范圍為[-180,180]和[-90,90]。

我們先來(lái)看經(jīng)度，[-180,180]可以簡(jiǎn)單分成兩個(gè)部分[-180,0]和[0,180]，對(duì)于給定的一個(gè)具體值，我們用一個(gè)bit來(lái)標(biāo)識(shí)是在[-180,0]還是[0,180]區(qū)間里。然后我們可以對(duì)這兩個(gè)子區(qū)間繼續(xù)細(xì)分，用更多的bit來(lái)標(biāo)識(shí)是這個(gè)值是在哪個(gè)子區(qū)間里。就好比用二分查找，記錄下每次查找的路徑，往左就是0往右是1，查找完后我們就會(huì)得到一個(gè)0101的串，這個(gè)串就可以用來(lái)標(biāo)識(shí)這個(gè)經(jīng)度值。

同理維度也是一樣，只不過(guò)他的取值返回變成了[-90,90]而已。通過(guò)這兩種方式編碼完成后，任意經(jīng)緯度我們都可以得到兩個(gè)由0和1組成的串。
比如還是北京市中心的經(jīng)緯度坐標(biāo) 116.404844,39.912279，我們先對(duì)116.404844做編碼，得到其二進(jìn)制為:

11010010110001101101

然后我們對(duì)維度39.912279編碼得到二進(jìn)制為：

10111000110000111001

2. 經(jīng)緯度二進(jìn)制合并

接下來(lái)我們只需要將上述二進(jìn)制交錯(cuò)合并成一個(gè)即可，這里注意經(jīng)度占偶數(shù)位，緯度占奇數(shù)位，得到最終的二進(jìn)制。

1101101110000200111100000001111011010011

3. 將合并后的二進(jìn)制做base32編碼

最后我們將合并后的二進(jìn)制做base32編碼，將連續(xù)5位轉(zhuǎn)化為一個(gè)0-31的十進(jìn)制數(shù)，然后用對(duì)應(yīng)的字符代替，將所有二進(jìn)制位處理完后我們就完成了base32編碼。編碼表如下：

最終得到geohash值wx4g0cg3vknd。

geohash是將空間不斷的二分，然后將二分的路徑轉(zhuǎn)化為base32編碼，最后保存下來(lái)，從原理可以看出，geohash表示的是一個(gè)區(qū)間，而不是一個(gè)點(diǎn)，geohash值越長(zhǎng)，這個(gè)區(qū)間就越小，標(biāo)識(shí)的位置也就越精確，下圖是維基百科中不同長(zhǎng)度geohash下的經(jīng)緯度誤差（lat:維度，lng:經(jīng)度）

geohash的用途及問(wèn)題

geohash成功的將一個(gè)二維信息編碼成了一個(gè)一維信息，這樣編碼我覺(jué)得有兩個(gè)好處：1. 編碼后數(shù)據(jù)長(zhǎng)度變短，利于節(jié)省存儲(chǔ)。2. 利于使用前綴檢索。我們來(lái)詳細(xì)說(shuō)下第二點(diǎn)。

從上文中g(shù)eohash的實(shí)現(xiàn)來(lái)看，只要兩個(gè)坐標(biāo)點(diǎn)的geohash有共同的前綴，你們我們就可以肯定這兩個(gè)點(diǎn)在同一個(gè)區(qū)域內(nèi) (區(qū)域大小取決于共同前綴的長(zhǎng)度)。這種特性給我們帶來(lái)的好處就是，我們可以把所有坐標(biāo)點(diǎn)按geohash做增序索引，然后查找的時(shí)候按前綴篩選，大幅提升檢索的性能。

舉個(gè)例子，假設(shè)我要找北京國(guó)貿(mào)附近3公里內(nèi)的餐館，已知國(guó)貿(mào)的geohash是wx4g41，那我也很輕易就可以計(jì)算出來(lái)我需要掃描哪些區(qū)域內(nèi)的點(diǎn)。但有個(gè)點(diǎn)需要注意，上文我已經(jīng)提到過(guò)，geohash值實(shí)際上是代表一個(gè)區(qū)域，而不是一個(gè)點(diǎn)，找到一批候選點(diǎn)之后還需要遍歷一次計(jì)算下精確距離。

geohash有個(gè)需要注意的問(wèn)題。geohash是將二維的坐標(biāo)點(diǎn)做了線下編碼(如下圖)，有時(shí)候可能會(huì)給人一個(gè)誤解就是如果兩個(gè)geohash之間二進(jìn)制的差異越小，這兩個(gè)區(qū)間距離就越近，這完全是錯(cuò)誤的，比如如下圖0111和1000，這倆區(qū)間二進(jìn)制只差0001但實(shí)際物理距離比較遠(yuǎn)。

如果上圖還不明顯的話，我從Wikipedia上拿到一張圖，虛線是線性索引的路徑，被虛線鏈接的兩個(gè)塊geohash值是非常相近的，如下圖的(7,3)和(0,4)，geohash值會(huì)非常相近，但實(shí)際物理距離非常遠(yuǎn)，這就是geohash的突變現(xiàn)象，這也導(dǎo)致了不能直接根據(jù)geohash的值來(lái)直接判定兩個(gè)區(qū)域的距離大小。

但在實(shí)際使用geohash過(guò)程中，時(shí)常會(huì)遇到跨域搜索的情況，比如我要在上圖(3,3)這個(gè)區(qū)間內(nèi)某個(gè)點(diǎn)上搜索距它1個(gè)距離單位的所有其他點(diǎn)集，這個(gè)點(diǎn)集有可能橫跨(3,3)加上它周圍8個(gè)鄰域的9個(gè)區(qū)間，突變的問(wèn)題會(huì)導(dǎo)致這9個(gè)區(qū)間的geohash不是線性跳轉(zhuǎn)的，但也不是沒(méi)法計(jì)算，實(shí)際上可以通過(guò)特殊的位運(yùn)算可以很輕易計(jì)算出某個(gè)geohash的8個(gè)鄰域，具體可參考redis源碼中src/geohash.c中g(shù)eohashNeighbors()的具體實(shí)現(xiàn)，geohashNeighbors使用了geohash_move_x和geohash_move_y兩個(gè)函數(shù)實(shí)現(xiàn)了geohash左右和上下的移動(dòng)，這樣可以很容易組合出8個(gè)鄰域的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的實(shí)現(xiàn)，其實(shí)看到這里，你基本上已經(jīng)理解了redis中的geohash的實(shí)現(xiàn)了。本質(zhì)上redis中的geo就是對(duì)geohash的封裝，具體geohash相關(guān)的代碼就不給大家列了(可自行查閱)，就給大家介紹下redis geo里的大體流程。
首先，可能大家最好奇的是geohash在redis中是怎么存儲(chǔ)的，從geoadd命令的實(shí)現(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，并對(duì)其個(gè)數(shù)做校驗(yàn) */
            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個(gè)參數(shù)為一組，將所有的經(jīng)緯度和member信息從參數(shù)列表里解析出來(lái)，并放到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)緯度坐標(biāo)轉(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);
}

原來(lái)geo的存儲(chǔ)只是zset包了一層殼(是不是有點(diǎn)小失望)，關(guān)于zset的具體實(shí)現(xiàn)可以參考我之前寫的文章redis中skiplist的實(shí)現(xiàn)。

我們?cè)賮?lái)詳細(xì)看下georadius的大體執(zhí)行流程(代碼偏長(zhǎng)，故刪除大量細(xì)節(jié)代碼)。

void georadiusGeneric(client *c, int srcKeyIndex, int flags) {
    robj *storekey = NULL;
    int storedist = 0; /* 0 for STORE, 1 for STOREDIST. */

    /* 根據(jù)key找找到對(duì)應(yīng)的zojb */
    robj *zobj = NULL;
    if ((zobj = lookupKeyReadOrReply(c, c->argv[srcKeyIndex], shared.emptyarray)) == NULL ||
        checkType(c, zobj, OBJ_ZSET)) {
        return;
    }

    /* 解析請(qǐng)求中的經(jīng)緯度值 */
    int base_args;
    GeoShape shape = {0};
    if (flags & RADIUS_COORDS) {
    /*
     * 各種必選參數(shù)的解析，省略細(xì)節(jié)代碼，主要是解析坐標(biāo)點(diǎn)信息和半徑   
     */ 
    }

    /* 解析所有的可選參數(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ù)的解析，省略細(xì)節(jié)代碼   
     */ 
    }
    
    /* Get all neighbor geohash boxes for our radius search
     * 獲取到要查找范圍內(nèi)所有的9個(gè)geo鄰域 */
    GeoHashRadius georadius = geohashCalculateAreasByShapeWGS84(&shape);

    /* 創(chuàng)建geoArray存儲(chǔ)結(jié)果列表 */
    geoArray *ga = geoArrayCreate();
    /* 掃描9個(gè)區(qū)域中是否有滿足條的點(diǎn)，有就放到geoArray中 */
    membersOfAllNeighbors(zobj, georadius, &shape, ga, any ? count : 0);

    /* 如果沒(méi)有匹配結(jié)果，返回空對(duì)象 */
    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ù)邏輯，比如處理排序，存儲(chǔ)……
     */
    // 釋放geoArray占用的空間 
    geoArrayFree(ga);
}

上述代碼刪減了大量細(xì)節(jié)，有興趣的同學(xué)可以自行查閱。不過(guò)可以看出georadius的整體流程非常清晰。

解析請(qǐng)求參數(shù)。計(jì)算目標(biāo)坐標(biāo)所在的geohash和8個(gè)鄰居。在zset中查找這9個(gè)區(qū)域中滿足距離限制的所有點(diǎn)集。處理排序等后續(xù)邏輯。清理臨時(shí)存儲(chǔ)空間。

結(jié)語(yǔ)

由于文章篇幅有限，而且著重講解了geohash的實(shí)現(xiàn)，并未展開(kāi)講解redis中g(shù)eo相關(guān)的各種細(xì)節(jié)，如讀者有興趣可以詳細(xì)閱讀redis中的src/geo.c了解各類細(xì)節(jié)。

參考資料

wikipedia geohash

Geohash算法原理及實(shí)現(xiàn)

本文是Redis源碼剖析系列博文，同時(shí)也有與之對(duì)應(yīng)的Redis中文注釋版，有想深入學(xué)習(xí)Redis的同學(xué)，歡迎star和關(guān)注。
Redis中文注解版?zhèn)}庫(kù)：https://github.com/xindoo/Redis
Redis源碼剖析專欄：https://zxs.io/s/1h

以上就是Redis是如何高效檢索地理位置的詳細(xì)內(nèi)容，更多關(guān)于Redis檢索地理位置的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論