簡(jiǎn)單幾步，實(shí)現(xiàn) Redis 查詢 “附近的人”

程序員的成長(zhǎng)之路

互聯(lián)網(wǎng)/程序員/技術(shù)/資料共享 

來(lái)自：juejin.cn/post/6844903966061363207

前言：針對(duì)“附近的人”這一位置服務(wù)領(lǐng)域的應(yīng)用場(chǎng)景，常見(jiàn)的可使用PG、MySQL和MongoDB等多種DB的空間索引進(jìn)行實(shí)現(xiàn)。而Redis另辟蹊徑，結(jié)合其有序隊(duì)列zset以及geohash編碼，實(shí)現(xiàn)了空間搜索功能，且擁有極高的運(yùn)行效率。

操作命令

• GEOADD: 將給定的位置對(duì)象（緯度、經(jīng)度、名字）添加到指定的key;
• GEOPOS: 從key里面返回所有給定位置對(duì)象的位置（經(jīng)度和緯度）;
• GEODIST: 返回兩個(gè)給定位置之間的距離;
• GEOHASH: 返回一個(gè)或多個(gè)位置對(duì)象的Geohash表示;
• GEORADIUS: 以給定的經(jīng)緯度為中心，返回目標(biāo)集合中與中心的距離不超過(guò)給定最大距離的所有位置對(duì)象;
• GEORADIUSBYMEMBER: 以給定的位置對(duì)象為中心，返回與其距離不超過(guò)給定最大距離的所有位置對(duì)象。

Redis geo操作中只包含了“增”和“查”的操作，并沒(méi)有專(zhuān)門(mén)的“刪除”命令。主要是因?yàn)镽edis內(nèi)部使用有序集合(zset)保存位置對(duì)象，可用zrem進(jìn)行刪除。

在Redis源碼geo.c的文件注釋中，只說(shuō)明了該文件為GEOADD、GEORADIUS和GEORADIUSBYMEMBER的實(shí)現(xiàn)文件（其實(shí)在也實(shí)現(xiàn)了另三個(gè)命令）。從側(cè)面看出其他三個(gè)命令為輔助命令。

GEOADD

使用方式

GEOADD key longitude latitude member [longitude latitude member ...]

(integer) N

源碼分析

/* GEOADD key long lat name [long2 lat2 name2 ... longN latN nameN] */
void geoaddCommand(client *c) {

//參數(shù)校驗(yàn)
    /* 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;
    }

//參數(shù)提取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]);

//參數(shù)遍歷+轉(zhuǎn)換
    /* 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];

    //提取經(jīng)緯度
        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;
        }
    
    //將經(jīng)緯度轉(zhuǎn)換為52位的geohash作為分值 & 提取對(duì)象名稱(chēng)
        /* 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];

    //設(shè)置有序集合的對(duì)象元素名稱(chēng)和分值
        argv[2+i*2] = score;
        argv[3+i*2] = val;
        incrRefCount(val);
    }

//調(diào)用zadd命令，存儲(chǔ)轉(zhuǎn)化好的對(duì)象
    /* Finally call ZADD that will do the work for us. */
    replaceClientCommandVector(c,argc,argv);
    zaddCommand(c);
}

double類(lèi)型精度為52位；
geohash是以base32的方式編碼，52bits最高可存儲(chǔ)10位geohash值，對(duì)應(yīng)地理區(qū)域大小為0.6*0.6米的格子。換句話說(shuō)經(jīng)Redis geo轉(zhuǎn)換過(guò)的位置理論上會(huì)有約0.3*1.414=0.424米的誤差。

算法小結(jié)

GEORADIUS

使用方式

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

• WITHDIST：在返回位置對(duì)象的同時(shí)，將位置對(duì)象與中心之間的距離也一并返回。距離的單位和用戶給定的范圍單位保持一致。
• WITHCOORD：將位置對(duì)象的經(jīng)度和維度也一并返回。
• WITHHASH：以 52 位有符號(hào)整數(shù)的形式，返回位置對(duì)象經(jīng)過(guò)原始 geohash 編碼的有序集合分值。這個(gè)選項(xiàng)主要用于底層應(yīng)用或者調(diào)試，實(shí)際中的作用并不大。
• ASC|DESC：從近到遠(yuǎn)返回位置對(duì)象元素 | 從遠(yuǎn)到近返回位置對(duì)象元素。- COUNT count：選取前N個(gè)匹配位置對(duì)象元素。（不設(shè)置則返回所有元素） - STORE key：將返回結(jié)果的地理位置信息保存到指定key。- STORedisT key：將返回結(jié)果離中心點(diǎn)的距離保存到指定key。

由于 STORE 和 STORedisT 兩個(gè)選項(xiàng)的存在，GEORADIUS 和 GEORADIUSBYMEMBER 命令在技術(shù)上會(huì)被標(biāo)記為寫(xiě)入命令，從而只會(huì)查詢（寫(xiě)入）主實(shí)例，QPS過(guò)高時(shí)容易造成主實(shí)例讀寫(xiě)壓力過(guò)大。

為解決這個(gè)問(wèn)題，在 Redis 3.2.10 和 Redis 4.0.0 中，分別新增了 GEORADIUS_RO 和 GEORADIUSBYMEMBER_RO兩個(gè)只讀命令。

不過(guò)，在實(shí)際開(kāi)發(fā)中筆者發(fā)現(xiàn) 在java package Redis.clients.jedis.params.geo 的 GeoRadiusParam 參數(shù)類(lèi)中并不包含 STORE 和 STORedisT 兩個(gè)參數(shù)選項(xiàng)，在調(diào)用georadius時(shí)是否真的只查詢了主實(shí)例，還是進(jìn)行了只讀封裝。感興趣的朋友可以自己研究下。

["member1","member2","member3"]

[
 ["member1", distance1, [longitude1, latitude1]]
 ["member2", distance2, [longitude2, latitude2]]
]

源碼分析

此段源碼較長(zhǎng)，看不下去的可直接看中文注釋?zhuān)蛑苯犹叫〗Y(jié)部分

/* 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. */

//根據(jù)key獲取有序集合
    robj *zobj = NULL;
    if ((zobj = lookupKeyReadOrReply(c, key, shared.null[c->resp])) == NULL ||
        checkType(c, zobj, OBJ_ZSET)) {
        return;
    }

//根據(jù)用戶輸入（經(jīng)緯度/member）確認(rèn)中心點(diǎn)經(jīng)緯度
    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;
    }

//獲取可選參數(shù) （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 參數(shù)
    if (storekey && (withdist || withhash || withcoords)) {
        addReplyError(c,
            "STORE option in GEORADIUS is not compatible with "
            "WITHDIST, WITHHASH and WITHCOORDS options");
        return;
    }

//設(shè)定排序
    if (count != 0 && sort == SORT_NONE) sort = SORT_ASC;

//利用中心點(diǎn)和半徑計(jì)算目標(biāo)區(qū)域范圍
    GeoHashRadius georadius =
        geohashGetAreasByRadiusWGS84(xy[0], xy[1], radius_meters);

//對(duì)中心點(diǎn)及其周?chē)?個(gè)geohash網(wǎng)格區(qū)域進(jìn)行查找，找出范圍內(nèi)元素對(duì)象
    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;
    }

//一些返回值的設(shè)定和返回
    ……
    geoArrayFree(ga);
}

• 計(jì)算中心點(diǎn)范圍：

GeoHashRadius geohashGetAreasByRadiusWGS84(double longitude, double latitude,
                                           double radius_meters) {
    return geohashGetAreasByRadius(longitude, latitude, radius_meters);
}

//返回能夠覆蓋目標(biāo)區(qū)域范圍的9個(gè)geohashBox
GeoHashRadius geohashGetAreasByRadius(double longitude, double latitude, double radius_meters) {
//一些參數(shù)設(shè)置
    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;

//計(jì)算目標(biāo)區(qū)域外接矩形的經(jīng)緯度范圍（目標(biāo)區(qū)域?yàn)椋阂阅繕?biāo)經(jīng)緯度為中心，半徑為指定距離的圓）
    geohashBoundingBox(longitude, latitude, radius_meters, bounds);
    min_lon = bounds[0];
    min_lat = bounds[1];
    max_lon = bounds[2];
    max_lat = bounds[3];

//根據(jù)目標(biāo)區(qū)域中心點(diǎn)緯度和半徑，計(jì)算帶查詢的9個(gè)搜索框的geohash精度（位）
//這里用到latitude主要是針對(duì)極地的情況對(duì)精度進(jìn)行了一些調(diào)整（緯度越高，位數(shù)越?。?/span>
    steps = geohashEstimateStepsByRadius(radius_meters,latitude);

//設(shè)置經(jīng)緯度最大最小值：-180<=longitude<=180, -85<=latitude<=85
    geohashGetCoordRange(&long_range,&lat_range);
    
//將待查經(jīng)緯度按指定精度（steps）編碼成geohash值
    geohashEncode(&long_range,&lat_range,longitude,latitude,steps,&hash);
    
//將geohash值在8個(gè)方向上進(jìn)行擴(kuò)充，確定周?chē)?個(gè)Box（neighbors）
    geohashNeighbors(&hash,&neighbors);
    
//根據(jù)hash值確定area經(jīng)緯度范圍
    geohashDecode(long_range,lat_range,hash,&area);

//一些特殊情況處理
    ……

//構(gòu)建并返回結(jié)果    
    radius.hash = hash;
    radius.neighbors = neighbors;
    radius.area = area;
    return radius;
}

• 對(duì)中心點(diǎn)及其周?chē)?個(gè)geohash網(wǎng)格區(qū)域進(jìn)行查找:

//在9個(gè)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個(gè)搜索hashBox
    neighbors[0] = n.hash;
    ……
    neighbors[8] = n.neighbors.south_west;

//在每個(gè)hashBox中搜索目標(biāo)點(diǎn)
    for (i = 0; i < sizeof(neighbors) / sizeof(*neighbors); i++) {
        if (HASHISZERO(neighbors[i])) {
            if (debugmsg) D("neighbors[%d] is zero",i);
            continue;
        }

 //剔除可能的重復(fù)hashBox (搜索半徑>5000KM時(shí)可能出現(xiàn))
        if (last_processed &&
            neighbors[i].bits == neighbors[last_processed].bits &&
            neighbors[i].step == neighbors[last_processed].step)
        {
            continue;
        }

 //搜索hashBox中滿足條件的對(duì)象    
        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內(nèi)的最大、最小geohash值（52位）
    GeoHashFix52Bits min, max;
    scoresOfGeoHashBox(hash,&min,&max);

//根據(jù)最大、最小geohash值篩選zobj集合中滿足條件的點(diǎn)
    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的參數(shù)邊界設(shè)置（即9個(gè)hashBox其中一個(gè)的邊界范圍）
    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范圍內(nèi)的首個(gè)元素（跳表數(shù)據(jù)結(jié)構(gòu)，效率可比擬于二叉查找樹(shù)），沒(méi)有則返0
        if ((ln = zslFirstInRange(zsl, &range)) == NULL) {
            /* Nothing exists starting at our min.  No results. */
            return 0;
        }

 //從首個(gè)元素開(kāi)始遍歷集合
        while (ln) {
            sds ele = ln->ele;
  //遍歷元素超出range范圍則break
            /* Abort when the node is no longer in range. */
            if (!zslValueLteMax(ln->score, &range))
                break;
  //元素校驗(yàn)（計(jì)算元素與中心點(diǎn)的距離）
            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];

//解碼錯(cuò)誤, 返回error
    if (!decodeGeohash(score,xy)) return C_ERR; /* Can't decode. */

//最終距離校驗(yàn)(計(jì)算球面距離distance看是否小于radius)
    if (!geohashGetDistanceIfInRadiusWGS84(lon,lat, xy[0], xy[1],
                                           radius, &distance))
    {
        return C_ERR;
    }

//構(gòu)建并返回滿足條件的元素
    geoPoint *gp = geoArrayAppend(ga);
    gp->longitude = xy[0];
    gp->latitude = xy[1];
    gp->dist = distance;
    gp->member = member;
    gp->score = score;
    return C_OK;
}

算法小結(jié)

算法分析

推薦閱讀：

一個(gè)網(wǎng)站部署的完整流程（包教包會(huì)）

巧用 HTTP 協(xié)議，設(shè)計(jì)一個(gè)基 于B/S 架構(gòu)的緩存框架！

互聯(lián)網(wǎng)初中高級(jí)大廠面試題(9個(gè)G)
內(nèi)容包含Java基礎(chǔ)、JavaWeb、MySQL性能優(yōu)化、JVM、鎖、百萬(wàn)并發(fā)、消息隊(duì)列、高性能緩存、反射、Spring全家桶原理、微服務(wù)、Zookeeper......等技術(shù)棧！
?戳閱讀原文領(lǐng)??！                                  朕已閱