Understanding Redis GEOADD and GEORADIUS: Source‑Code Analysis and Algorithm Details

Redis 3.2 introduced a geo module that leverages geohash encoding and ordered sets (zset) to provide location‑based functionality. The module offers six commands: GEOADD, GEOPOS, GEODIST, GEOHASH, GEORADIUS, and GEORADIUSBYMEMBER, which together enable adding, querying, and managing geographic data.

GEOADD

The command syntax is:

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

It validates arguments, converts latitude/longitude to a 52‑bit geohash score, and stores the member in a sorted set using the internal zadd command.

/* GEOADD key long lat name [long2 lat2 name2 ... longN latN nameN] */
void geoaddCommand(client *c) {
    // argument validation
    if ((c->argc - 2) % 3 != 0) {
        addReplyError(c, "syntax error. Try GEOADD key [x1] [y1] [name1] ...");
        return;
    }
    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]);
    for (int i = 0; i < elements; i++) {
        double xy[2];
        if (extractLongLatOrReply(c, (c->argv+2)+(i*3), xy) == C_ERR) {
            for (int j = 0; j < argc; j++) if (argv[j]) decrRefCount(argv[j]);
            zfree(argv);
            return;
        }
        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];
        argv[2 + i*2] = score;
        argv[3 + i*2] = val;
        incrRefCount(val);
    }
    replaceClientCommandVector(c, argc, argv);
    zaddCommand(c);
}

The command ultimately stores each member with its geohash‑derived score in the sorted set, enabling fast range queries.

GEORADIUS

The command syntax is:

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

It returns all members within the specified radius around the given point, optionally including distances, coordinates, or raw geohash values.

void georadiusGeneric(client *c, int flags) {
    robj *key = c->argv[1];
    robj *storekey = NULL;
    int stoRedis = 0; // 0 for STORE, 1 for STOREDIST
    // lookup the sorted set
    robj *zobj = lookupKeyReadOrReply(c, key, shared.null[c->resp]);
    if (zobj == NULL || checkType(c, zobj, OBJ_ZSET)) return;
    // parse center point and radius
    double xy[2] = {0};
    if (flags & RADIUS_COORDS) { /* parse longitude/latitude */ }
    double radius_meters = 0, conversion = 1;
    if ((radius_meters = extractDistanceOrReply(c, c->argv + base_args - 2, &conversion)) < 0) return;
    // optional flags handling (WITHDIST, WITHHASH, WITHCOORD, SORT, COUNT, STORE)
    // compute geohash area covering the circle
    GeoHashRadius georadius = geohashGetAreasByRadiusWGS84(xy[0], xy[1], radius_meters);
    // search the 9 neighboring geohash boxes
    geoArray *ga = geoArrayCreate();
    membersOfAllNeighbors(zobj, georadius, xy[0], xy[1], radius_meters, ga);
    if (ga->used == 0 && storekey == NULL) { addReplyNull(c); geoArrayFree(ga); return; }
    // build and send reply (omitted for brevity)
    geoArrayFree(ga);
}

The core steps are: calculate the bounding box of the search radius, determine the appropriate geohash precision, generate a 3×3 grid (nine‑box) covering the area, and then query the sorted set for members whose scores fall within each box, finally filtering by exact distance.

Algorithm Summary

Extract and validate command arguments.

Convert latitude/longitude to a 52‑bit geohash score (for GEOADD) or compute the geohash grid covering the search radius (for GEORADIUS).

Use the sorted‑set’s skip‑list to locate the first element in each geohash range (O(log M) per box) and iterate to collect candidates.

Decode each candidate’s geohash, compute the spherical distance, and keep those within the radius.

The overall time complexity of a GEORADIUS query is O(N + log M), where N is the number of candidates in the nine‑box area and M is the total number of elements in the sorted set.

Author

Wan Mi, senior development engineer at Ele.me, experienced in iOS, Go, Java, and currently focusing on big‑data development.