Redis 實現(xiàn)“附近的人”功能

/* GEOADD key long lat name [long2 lat2 name2 ... longN latN nameN] */
void geoaddCommand(client *c) {
//參數(shù)校驗
  /* 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);
}

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

["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)中心點經(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;
//利用中心點和半徑計算目標(biāo)區(qū)域范圍
  GeoHashRadius georadius =
    geohashGetAreasByRadiusWGS84(xy[0], xy[1], radius_meters);
//對中心點及其周圍8個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);
}

// geohash_helper.c
GeoHashRadius geohashGetAreasByRadiusWGS84(double longitude, double latitude,
                      double radius_meters) {
  return geohashGetAreasByRadius(longitude, latitude, radius_meters);
}
//返回能夠覆蓋目標(biāo)區(qū)域范圍的9個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;
//計算目標(biāo)區(qū)域外接矩形的經(jīng)緯度范圍（目標(biāo)區(qū)域為：以目標(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ū)域中心點緯度和半徑，計算帶查詢的9個搜索框的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個方向上進(jìn)行擴充，確定周圍8個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;
}

// 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中搜索目標(biāo)點
  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時可能出現(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集合中滿足條件的點
  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個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范圍內(nèi)的首個元素（跳表數(shù)據(jù)結(jié)構(gòu)，效率可比擬于二叉查找樹），沒有則返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;
  }
//構(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;
}