How Redis GEOADD & GEORADIUS Power Nearby-User Searches: Deep Code Dive

Preface: For location‑based “nearby people” scenarios, various databases can use spatial indexes, but Redis uses an ordered set (zset) with geohash to achieve high efficiency. This article analyzes the algorithm from source code and derives query time complexity.

To provide a complete “nearby people” service, basic CRUD operations are needed; the article focuses on the query part.

Commands

Since Redis 3.2, the Geo module provides six commands:

GEOADD : Add a location object (latitude, longitude, name) to a key.

GEOPOS: Return positions of given members.

GEODIST: Return distance between two members.

GEOHASH: Return geohash representation of members.

GEORADIUS : Return members within a radius from a given point.

GEORADIUSBYMEMBER: Return members within a radius from a given member.

Combining GEOADD and GEORADIUS implements “add” and “query”. GEORADIUSBYMEMBER is essentially GEOPOS + GEORADIUS.

Redis Geo only includes add and query; deletion can be done with ZREM.

GEOADD

Usage

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

It adds the given location object to the specified key. When many objects are stored, sharding by multiple keys can be used.

Return value: ( integer ) N, where N is the number of successfully inserted members.

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, convert lat/lon to 52‑bit geohash, build ZADD vector, call ZADD
    ...
}

The implementation stores each location as a member of a sorted set, using a 52‑bit geohash as the score.

double precision provides 52 bits; geohash encoded in base‑32 yields about 0.42 m error.

Algorithm Summary

1. Validate and extract parameters. 2. Convert latitude/longitude to a 52‑bit geohash score. 3. Call ZADD to store the member and 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 members within the given radius from the specified point. Optional flags modify the output.

WITHDIST: also return distance.

WITHCOORD: also return coordinates.

WITHHASH: also return raw geohash score.

ASC/DESC: sort by distance.

COUNT: limit number of results.

STORE / STOREDIST: store results in a key.

Because STORE and STOREDIST make the command a write operation, they are routed to the master instance, which may increase load; read‑only variants GEORADIUS_RO and GEORADIUSBYMEMBER_RO were added in later versions.

Source Code Analysis

void georadiusGeneric(client *c, int flags) {
    // lookup key, verify type
    // determine center point (coordinates or member)
    // compute radius in meters and conversion factor
    // parse optional arguments (WITHDIST, WITHHASH, WITHCOORD, SORT, COUNT, STORE)
    // compute geohash area covering the radius
    // search the nine neighboring geohash boxes
    // collect members whose distance is within radius
    // return or store results
}

The core steps are:

Extract and validate parameters.

Calculate the bounding box and appropriate geohash precision, producing a nine‑cell grid.

Iterate over each cell, retrieve members whose geohash scores fall within the cell’s range, and filter by exact spherical distance.

Key helper functions: geohashGetAreasByRadiusWGS84 – computes the nine‑cell grid. membersOfAllNeighbors – scans each cell’s sorted‑set range. geoGetPointsInRange – uses the skip‑list of the ZSET to find members in the score range. geoAppendIfWithinRadius – decodes geohash, calculates distance, and adds qualifying members to the result array.

Algorithm Summary

GEORADIUS first determines the optimal geohash precision to cover the search radius, then searches the nine neighboring geohash boxes, finally filtering candidates by exact distance.

Complexity Analysis

Ignoring optional parameters, the time complexity is O(N + log M), where N is the number of elements inside the radius and M is the number of elements examined in the nine‑cell grid. Because Redis stores data in memory, the operation is highly efficient.