Redis是如何實(shí)現(xiàn) “附近的人”功能的？

(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作為分值 & 提取對象名稱
????????/* 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è)置有序集合的對象元素名稱和分值
????????argv[2+i*2] = score;
????????argv[3+i*2] = val;
????????incrRefCount(val);
????}

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

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

[
??["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. */

//根據(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);

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

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主要是針對極地的情況對精度進(jìn)行了一些調(diào)整（緯度越高，位數(shù)越小）
????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ò)充，確定周圍8個(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;
}

//在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中滿足條件的對象
????????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)，效率可比擬于二叉查找樹），沒有則返0
????????if?((ln = zslFirstInRange(zsl, &range)) ==?NULL) {
????????????/* Nothing exists starting at our min. No results. */
????????????return?0;
????????}

??//從首個(gè)元素開始遍歷集合
????????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];

//解碼錯誤, 返回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;
}