How Redis Implements High‑Performance ‘Nearby People’ Search with GEOADD & GEORADIUS

Preface

Targeting the "nearby people" location‑service scenario, many solutions use spatial indexes of PG, MySQL, or MongoDB, while Redis leverages its ordered set (zset) together with geohash encoding to achieve high‑efficiency spatial search. This article parses the algorithm from the source code and derives the query time complexity.

Operation Commands

Since Redis 3.2, the Geo module provides six commands:

GEOADD: add a location object (longitude, latitude, name) to a key;

GEOPOS: return the longitude and latitude of given members;

GEODIST: return the distance between two members;

GEOHASH: return the geohash representation of one or more members;

GEORADIUS: return all members within a given radius of a center point;

GEORADIUSBYMEMBER: same as GEORADIUS but uses an existing member as the center.

Combining GEOADD and GEORADIUS implements the basic "add" and "query" functions of a "nearby people" service. Deletion can be done with ZREM because Redis stores locations in a zset.

Redis Geo operations only include add and query; there is no dedicated delete command.

The source file geo.c implements GEOADD, GEORADIUS, and GEORADIUSBYMEMBER (the other three commands are auxiliary).

GEOADD

Usage

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

The command adds the given location objects to the specified key. When the number of objects is large, sharding by multiple keys (e.g., one key per province) can be used to avoid oversized single sets.

Successful insertion returns:

(integer) N

Source Code Analysis

/* 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] [x2] [y2] [name2] ... ");
        return;
    }
    // extract arguments
    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]);
    // iterate arguments and convert
    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;
        }
        // encode geohash
        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);
    }
    // call ZADD to store the converted objects
    replaceClientCommandVector(c, argc, argv);
    zaddCommand(c);
}

The analysis shows Redis stores location objects in a sorted set where each element’s score is a 52‑bit geohash value.

double precision provides 52 bits; a 52‑bit geohash (base‑32) can store a 10‑character hash, corresponding to a grid of about 0.6 m. The theoretical error is roughly 0.424 m.

Algorithm Summary

GEOADD performs:

Argument extraction and validation;

Convert latitude/longitude to a 52‑bit geohash (score);

Call ZADD to store the member with its score.

GEORADIUS

Usage

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

Returns all members whose distance from the center does not exceed the given radius. Optional flags control additional output, sorting, limiting, and storing results.

WITHDIST: also return the distance;

WITHCOORD: also return longitude and latitude;

WITHHASH: return the raw 52‑bit geohash score;

ASC|DESC: sort by distance;

COUNT: limit the number of returned members;

STORE: store the resulting locations in a key;

STOREDIST: store the distances in a key.

Because STORE and STOREDIST make the command a write operation, Redis 3.2.10 and 4.0 introduced read‑only variants GEORADIUS_RO and GEORADIUSBYMEMBER_RO.

Example return values:

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

[["member1", distance1, [lon1, lat1]], ["member2", distance2, [lon2, lat2]]]

Source Code Analysis

void georadiusGeneric(client *c, int flags) {
    robj *key = c->argv[1];
    robj *storekey = NULL;
    int stoRedist = 0; /* 0 for STORE, 1 for STOREDIST */
    // lookup the sorted set
    robj *zobj = NULL;
    if ((zobj = lookupKeyReadOrReply(c, key, shared.null[c->resp])) == NULL ||
        checkType(c, zobj, OBJ_ZSET)) {
        return;
    }
    // parse center point
    int base_args;
    double xy[2] = {0};
    if (flags & RADIUS_COORDS) {
        // extract longitude and latitude
    }
    // extract radius
    double radius_meters = 0, conversion = 1;
    if ((radius_meters = extractDistanceOrReply(c, c->argv + base_args - 2, &conversion)) < 0) {
        return;
    }
    // optional flags
    int withdist = 0, withhash = 0, withcoords = 0;
    int sort = SORT_NONE;
    long long count = 0;
    if (c->argc > base_args) {
        // parse options
    }
    // STORE compatibility check
    if (storekey && (withdist || withhash || withcoords)) {
        addReplyError(c, "STORE option in GEORADIUS is not compatible with WITHDIST, WITHHASH and WITHCOORDS options");
        return;
    }
    // default sort when COUNT is set
    if (count != 0 && sort == SORT_NONE) sort = SORT_ASC;
    // compute geohash boxes covering the circle
    GeoHashRadius georadius = geohashGetAreasByRadiusWGS84(xy[0], xy[1], radius_meters);
    // search the nine neighboring 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 circle and determine the highest‑resolution geohash level that fully covers it.

Generate a nine‑grid (center plus eight neighbors) of geohash boxes.

For each box, compute the minimum and maximum geohash scores and perform a ZSET range query to retrieve candidate members.

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

Because geohash values in a box form a continuous range, the range query on the skip‑list of the sorted set runs in O(log M) where M is the number of boxes; the distance checks add O(N) where N is the number of candidates in the nine boxes. Overall complexity is O(N + log M). Combined with Redis’s in‑memory storage, the operation is highly efficient.

Algorithm Summary

GEORADIUS performs:

Argument parsing and validation;

Compute the geohash grid covering the search circle;

Iterate the nine grids, retrieve members via ZSET range scans;

Filter by exact spherical distance.

The left image shows the search center (green circle) and the red points that satisfy the radius condition. The right image illustrates the hierarchy of geohash cells: higher levels correspond to smaller cells, and the nine‑grid avoids boundary issues.