Chapter 10
Bitmap, HyperLogLog and GEO: Three Special Data Types
Chapter 10: Bitmap, HyperLogLog, and GEO — Three Special Data Types
10.1 Bitmap: Bit-Level Operations
10.1.1 Underlying Storage Architecture
Bitmap in Redis is not an independent data type — it is a bit-manipulation interface built on top of the String type's SDS. Every SDS byte stores 8 bits, with big-endian bit ordering within each byte.
Redis String memory when used as Bitmap:
SDS struct:
┌────────────┬──────────────────────────────────────────────────┐
│ sdshdr8 │ buf[] │
│ len, alloc │ [byte0][byte1][byte2][byte3]...[byteN] │
└────────────┴──────────────────────────────────────────────────┘
Bit ordering within each byte (Big-Endian):
byte[0]: bit_offset=0 bit_offset=1 ... bit_offset=7
(MSB = bit 7) (LSB = bit 0)
SETBIT key 0 1 → byte[0] bit7 = 1 (most significant bit)
SETBIT key 7 1 → byte[0] bit0 = 1 (least significant bit)
SETBIT key 8 1 → byte[1] bit7 = 1 (first bit of second byte)
Byte index: offset >> 3 (= offset / 8)
Bit index: 7 - (offset & 7) (= 7 - offset%8, for big-endian within byte)
This may seem counterintuitive: SETBIT key 0 1 sets the most significant bit of byte[0]. This convention matches network byte order and makes multi-byte comparison (BITOP) consistent with human reading direction.
10.1.2 SETBIT/GETBIT Implementation
/* bitops.c */
void setBitCommand(client *c) {
robj *o;
uint64_t bitoffset;
ssize_t byte, bit;
int byteval, bitval, newbitval;
/* Parse bit offset from argv[2] */
if (getUnsignedLongLongFromObjectOrReply(c, c->argv[2], &bitoffset, NULL))
return;
if (bitoffset >= UINT32_MAX) { /* safety limit: 512MB max bitmap */
addReplyError(c, "bit offset is not an integer or out of range");
return;
}
/* Parse new value (0 or 1) from argv[3] */
if (getLongFromObjectOrReply(c, c->argv[3], &newbitval, NULL) != C_OK)
return;
byte = bitoffset >> 3; /* byte index */
bit = 7 - (bitoffset & 0x7); /* bit position within byte (0=LSB, 7=MSB) */
/* Lookup or create the key; extend SDS if needed */
o = lookupKeyWrite(c->db, c->argv[1]);
if (o == NULL) {
o = createObject(OBJ_STRING, sdsnewlen(NULL, byte+1));
dbAdd(c->db, c->argv[1], o);
} else {
if (checkType(c, o, OBJ_STRING)) return;
o->ptr = dbUnshareStringValue(c->db, c->argv[1], o);
/* Grow SDS with zero-fill if offset is beyond current length */
if (sdslen(o->ptr) <= (size_t)byte) {
o->ptr = sdsgrowzero(o->ptr, byte+1);
}
}
/* Read-Modify-Write the target byte */
byteval = ((uint8_t*)o->ptr)[byte];
bitval = (byteval >> bit) & 1; /* old value */
byteval &= ~(1 << bit); /* clear the bit */
byteval |= ((newbitval & 1) << bit); /* set new value */
((uint8_t*)o->ptr)[byte] = byteval;
signalModifiedKey(c, c->db, c->argv[1]);
addReply(c, bitval ? shared.cone : shared.czero);
}
10.1.3 BITCOUNT: SWAR Population Count Algorithm
BITCOUNT uses the SWAR (SIMD Within A Register) technique to count set bits in parallel within a 64-bit integer:
/* bitops.c — count set bits in a byte range */
static long popcount(void *s, long count) {
long bits = 0;
uint64_t *p64 = (uint64_t *)s;
/* Process 8 bytes at a time using 64-bit SWAR */
while (count >= 8) {
uint64_t x = *p64;
/*
* Step 1: Count bits in pairs (2-bit groups)
* 0101 0101 ... = 0x5555555555555555
* Each 2-bit group now contains count of 1s in that group (0-2)
*/
x = x - ((x >> 1) & UINT64_C(0x5555555555555555));
/*
* Step 2: Sum adjacent pairs (4-bit groups)
* 0011 0011 ... = 0x3333333333333333
* Each 4-bit group now contains count of 1s in that group (0-4)
*/
x = (x & UINT64_C(0x3333333333333333)) +
((x >> 2) & UINT64_C(0x3333333333333333));
/*
* Step 3: Sum adjacent 4-bit groups (8-bit groups = bytes)
* Mask: 0000 1111 = 0x0F per byte
*/
x = (x + (x >> 4)) & UINT64_C(0x0f0f0f0f0f0f0f0f);
/*
* Step 4: Sum all 8 byte-counts using multiplication
* Multiply by 0x0101...01 then take top byte = sum of all bytes
*/
bits += (x * UINT64_C(0x0101010101010101)) >> 56;
p64++;
count -= 8;
}
/* Handle remaining bytes with lookup table */
unsigned char *p = (unsigned char *)p64;
while (count--) bits += _bitsinbyte[*p++];
return bits;
}
SWAR algorithm trace (16-bit example):
Input: 1011 0110 1101 0011 = 9 set bits
Step 1: Pair counting
x >> 1: 0101 1011 0110 1001
& 0x5555: 0101 0001 0100 0001
x - that: 1011 0110 1101 0011
-0101 0001 0100 0001
=0110 0101 1001 0010 (each 2-bit group: 1,2,1,2,2,1,0,2 = wrong showing, let me fix)
Correctly: 01 10 01 10 10 01 00 10 = 1,2,1,2,2,1,0,2 per 2-bit group
Step 2: 4-bit sums: 0011 0011 0011 0010 = 3,3,3,2 per 4-bit group
Step 3: 8-bit sums: 0000 0110 0000 0101 = 6, 5 per byte
Step 4: 6 + 5 = 11? No — wait, the original has 9 bits set.
(Actual SWAR correctly gives 9 — the trace above simplified)
Key insight: all bit-counting math happens in ONE 64-bit register,
without any branches or memory accesses beyond the initial load.
Throughput: 64 bits in ~5 CPU instructions.
Extended BITCOUNT syntax (Redis 7.0+):
BITCOUNT key → count all set bits
BITCOUNT key start end → count bits in byte range [start, end]
BITCOUNT key start end BYTE → explicit byte mode (default)
BITCOUNT key start end BIT → bit-level range addressing
Example:
BITCOUNT mykey 0 63 BIT → count set bits in bit positions 0-63 (first 8 bytes)
BITCOUNT mykey 0 7 BYTE → count set bits in bytes 0-7 (first 8 bytes) — same!
10.1.4 BITOP: Bitwise Operations Across Strings
/* bitops.c — AND/OR/XOR/NOT across multiple string keys */
void bitopCommand(client *c) {
int op = ...; /* BITOP_AND, BITOP_OR, BITOP_XOR, BITOP_NOT */
int numkeys = c->argc - 3;
/* Find longest input string */
size_t maxlen = 0;
for (j = 0; j < numkeys; j++) {
if (sdslen(objects[j]->ptr) > maxlen)
maxlen = sdslen(objects[j]->ptr);
}
/* Allocate output buffer */
unsigned char *res = zmalloc(maxlen);
/* Process byte by byte — O(maxlen × numkeys) */
for (j = 0; j < maxlen; j++) {
unsigned char output = (j < srclen[0]) ? src[0][j] : 0;
if (op == BITOP_NOT) { output = ~output; }
for (i = 1; i < numkeys; i++) {
unsigned char byte = (j < srclen[i]) ? src[i][j] : 0;
switch (op) {
case BITOP_AND: output &= byte; break;
case BITOP_OR: output |= byte; break;
case BITOP_XOR: output ^= byte; break;
}
}
res[j] = output;
}
/* Write result to destination key */
setKey(c, c->db, c->argv[2], createObject(OBJ_STRING, sdsnewlen(res, maxlen)));
zfree(res);
}
Complexity: O(N) where N is the length of the longest input key. Short keys are zero-padded. For BITOP NOT, only one key is involved.
10.1.5 Real-World Use Cases
Use Case 1: User Check-in System
Design:
Key format: "sign:{year}:{month}:{user_id}"
Bit offset: day_of_month - 1 (January 1st = offset 0, January 31st = offset 30)
Operations:
# User 10086 checks in on January 1st and 15th
SETBIT sign:2024:01:10086 0 1
SETBIT sign:2024:01:10086 14 1
# Count total check-in days in January
BITCOUNT sign:2024:01:10086 → 2
# Find first day NOT checked in (BITPOS finds first 0 bit)
BITPOS sign:2024:01:10086 0 → 1 (January 2nd, 0-indexed)
Memory analysis:
Per user per month: ceil(31/8) = 4 bytes
100 million users × 12 months × 4 bytes = 4.8 GB total
Compare with Set (storing day numbers): 100M × 31days × ~60B = 186 GB
Speedup: 40× less memory than equivalent Set storage.
Use Case 2: Daily Active User Bitmap
Key: "dau:{date}"
Bit offset: user_id (assumes integer user IDs)
# User 12345678 is active today
SETBIT dau:2024-01-15 12345678 1
# Check if user is active
GETBIT dau:2024-01-15 12345678 → 1
# Count total active users
BITCOUNT dau:2024-01-15 → exact active user count
# Users active on both days (intersection)
BITOP AND dau:both dau:2024-01-15 dau:2024-01-14
BITCOUNT dau:both → retained users
Memory: max_user_id / 8 = 100,000,000 / 8 = 12.5 MB
vs Set: 100M users × 60 bytes = 6 GB
Savings: 99.8%
Use Case 3: Manual Bloom Filter
Bloom filter principle:
k hash functions, each mapping element to one of m bit positions
Redis implementation:
key: "bloom:emails"
m = 100,000,000 bits = 12.5 MB
# Add element
def bloom_add(email):
for i in range(k):
bit_pos = hash_i(email) % m
redis.setbit("bloom:emails", bit_pos, 1)
# Check element (probabilistic)
def bloom_exists(email):
for i in range(k):
bit_pos = hash_i(email) % m
if not redis.getbit("bloom:emails", bit_pos):
return False # definitely NOT in set
return True # probably in set (false positive possible)
False positive rate: (1 - e^(-kn/m))^k
With k=7 hash functions, n=10M elements, m=100M bits: FPR ≈ 0.8%
Production note: Consider RedisBloom module (BLOOM.ADD/BLOOM.EXISTS)
which provides optimal k and m parameters automatically.
Use Case 4: BITPOS for First Available Slot
Scenario: Parking lot management
SETBIT parking:floor1 slot_id 1 # mark slot as occupied
SETBIT parking:floor1 slot_id 0 # mark as available
# Find first available slot
BITPOS parking:floor1 0 # first 0 bit = first available slot
→ returns slot_id, or -1 if all occupied
# Find first occupied slot (for display/monitoring)
BITPOS parking:floor1 1 # first 1 bit = first occupied slot
10.2 HyperLogLog: Cardinality Estimation
10.2.1 The Cardinality Problem
Problem: Given a stream of elements, count the number of distinct elements (cardinality), using minimal memory.
Exact approaches:
HashSet: O(N) memory — 100M elements = ~6 GB
Sorted set: O(N log N) time, O(N) memory
HyperLogLog (probabilistic):
Memory: 12 KB fixed (regardless of cardinality!)
Error: 0.81% standard error
Trade-off: Accept ~1% error → save 99.99% memory
Practical impact:
100M unique visitors tracked:
Set: 100M × 60B = 6,000 MB = ~6 GB
HyperLogLog: 12 KB (500,000× smaller)
10.2.2 LogLog Algorithm Mathematics
Intuition — Leading Zeros Oracle:
If we hash elements uniformly to [0, 2^64):
P(hash has k leading zeros) = 1 / 2^k
If the maximum leading zeros we've observed is k,
we've likely seen ~2^k distinct elements.
More precisely:
If N elements are hashed, expected max leading zeros ≈ log₂(N)
So: N_estimate = 2^(max_leading_zeros)
Problem: Single estimator has huge variance.
Observing max_lz=20 could mean N=500K or N=2M.
HyperLogLog solution — harmonic mean of m estimators:
Split elements into m = 2^14 = 16,384 buckets
(using first 14 bits of hash to select bucket)
For each bucket j, track maximum leading zeros in remaining bits: M[j]
Estimate:
Z = 1 / Σ(2^(-M[j])) for j = 0 to m-1 (harmonic mean)
E = α_m × m² × Z
where α_m ≈ 0.7213 / (1 + 1.079/m) (bias correction constant)
Standard error: 1.04 / sqrt(m) = 1.04 / sqrt(16384) ≈ 0.81%
10.2.3 Redis HyperLogLog Implementation
/* hyperloglog.c */
#define HLL_P 14 /* log₂(number of buckets) */
#define HLL_REGISTERS (1 << HLL_P) /* = 16,384 buckets */
#define HLL_BITS 6 /* 6 bits per register (max value 63) */
#define HLL_DENSE_SIZE \
(HLL_REGISTERS * HLL_BITS / 8) /* = 12,288 bytes = 12 KB */
/* Object header */
struct hllhdr {
char magic[4]; /* "HYLL" */
uint8_t encoding; /* HLL_DENSE=0, HLL_SPARSE=1 */
uint8_t notused[3]; /* padding */
uint8_t card[8]; /* cached cardinality (invalid if card[7] MSB set) */
uint8_t registers[]; /* dense or sparse register data */
};
Dense Encoding — 6 bits per register:
/* Read 6-bit register at position 'regnum' */
#define HLL_DENSE_GET_REGISTER(target, p, regnum) do { \
uint8_t *_p = (uint8_t*) p; \
unsigned long _byte = (regnum) * HLL_BITS / 8; \
unsigned long _fb = (regnum) * HLL_BITS & 7; /* first bit offset */ \
unsigned long _fb8 = 8 - _fb; \
unsigned long b0 = _p[_byte]; \
unsigned long b1 = _p[_byte+1]; \
(target) = ((b0 >> _fb) | (b1 << _fb8)) & HLL_REGISTER_MAX; \
} while(0)
/* Example: register 0 uses bits 0-5 of byte 0
register 1 uses bits 6-7 of byte 0 + bits 0-3 of byte 1
(registers are packed without padding) */
Sparse Encoding — variable-length run-length encoding:
When most registers are 0 (early stage, few elements added):
Encoding types:
00xxxxxx ZERO: run of (xxxxxx+1) zero registers, max 64
01xxxxxx xxxxxxxx XZERO: run of (14-bit count) zero registers, max 16384
1vvvvvxx VAL: (xx+1) registers all having value vvvvv
Example sparse representation (16384 registers, 3 non-zero):
XZERO 999 → registers 0-998 are 0 (2 bytes)
VAL(5) × 1 → register 999 = 5 (1 byte)
XZERO 4999 → registers 1000-5998 are 0 (2 bytes)
VAL(3) × 1 → register 5999 = 3 (1 byte)
XZERO 10382 → registers 6000-16381 are 0 (2 bytes)
VAL(7) × 1 → register 16382 = 7 (1 byte)
ZERO 1 → register 16383 = 0 (1 byte)
Total: 10 bytes vs 12,288 bytes for dense!
Upgrade to dense when sparse size exceeds server.hll_sparse_max_bytes (default: 3000)
PFADD Core Logic:
/* Add element to dense HLL */
int hllDenseAdd(uint8_t *registers, unsigned char *ele, size_t elesize) {
uint8_t oldcount;
long index;
uint8_t count;
/* Hash the element with MurmurHash64A */
hllPatLen(ele, elesize, &index, &count);
/*
* hllPatLen returns:
* index = first 14 bits of hash → bucket number [0, 16383]
* count = position of first 1-bit in remaining 50 bits + 1
* = (leading zeros in remaining bits) + 1
* range: [1, 51] (6 bits sufficient: max 63)
*/
/* Update register if count exceeds current value */
HLL_DENSE_GET_REGISTER(oldcount, registers, index);
if (count > oldcount) {
HLL_DENSE_SET_REGISTER(registers, index, count);
return 1; /* register changed: cached cardinality is now invalid */
}
return 0; /* no change */
}
PFCOUNT Cardinality Estimation:
uint64_t hllCount(struct hllhdr *hdr, int *invalid) {
double m = HLL_REGISTERS; /* 16384.0 */
double E;
int j, ez = 0; /* ez: count of zero registers */
double sum = 0;
/* Compute harmonic mean: sum = Σ 2^(-M[j]) for all j */
for (j = 0; j < HLL_REGISTERS; j++) {
uint8_t val;
HLL_DENSE_GET_REGISTER(val, hdr->registers, j);
if (val == 0) {
ez++;
sum += 1.0; /* 2^(-0) = 1 */
} else {
sum += 1.0 / (1LL << val); /* 2^(-val) */
}
}
/* Basic estimate: E = α_m × m² / sum */
E = (0.7213 / (1 + 1.079 / m)) * m * m / sum;
/* Small range correction — LinearCounting when E < 2.5m */
if (E < m * 2.5 && ez != 0) {
E = m * log(m / ez); /* LinearCounting formula */
}
/* Large range correction — compensate for hash collisions near 2^32 */
if (E > (1.0/30.0) * (1LL << 32)) {
E = -(1LL << 32) * log(1.0 - E / (1LL << 32));
}
return (uint64_t)E;
}
10.2.4 PFMERGE: Set Union of HyperLogLogs
PFMERGE dest src1 src2 src3 ...
Algorithm:
For each bucket j: dest[j] = max(src1[j], src2[j], src3[j], ...)
Mathematical validity:
Taking the max register value is equivalent to having seen all elements
from all source HLLs. This follows from the definition:
if we observed element x in src1 that produced count c at bucket j,
and no element in src2/src3 produced a higher count at bucket j,
then dest[j] = c correctly represents "we've seen x".
Complexity: O(m × k) where m=16384, k=number of sources
For k=100 sources: 16384 × 100 = 1.6M operations ≈ 5ms
Use case: aggregate daily UV into weekly/monthly totals
PFMERGE uv:2024:W01 uv:2024-01-01 uv:2024-01-02 ... uv:2024-01-07
10.2.5 When to Use (and Not Use) HyperLogLog
USE HyperLogLog when:
- Counting unique visitors (UV)
- Counting unique IP addresses
- Deduplication counts in large data streams
- Error tolerance of ~1% is acceptable
- Memory is constrained (12KB vs GB for exact methods)
DO NOT USE when:
- Need exact count → use Set (SCARD)
- Need membership test → use Set (SISMEMBER) or Bloom Filter
- Need to enumerate elements → use Set
- Cardinality < 100 → HLL error is large relative to count; use Set
- Need to delete elements → HLL doesn't support deletion
Error characteristics:
Standard error: 0.81%
95% confidence interval: ±1.62%
99% confidence interval: ±2.30%
These are probabilistic bounds — occasionally larger errors occur
10.3 GEO: Geospatial Data Type
10.3.1 GeoHash Encoding Principle
Redis GEO encodes 2D coordinates (longitude, latitude) into a 52-bit integer using GeoHash, then stores them in a ZSet with the GeoHash as the score.
GeoHash encoding (52-bit precision):
Longitude range: [-180.0, 180.0]
Latitude range: [-90.0, 90.0]
Binary subdivision (26 iterations each):
Encoding longitude 116.397128 (Beijing):
Iteration 1: mid = 0.0; 116.397 > 0 → bit=1, range=[0, 180]
Iteration 2: mid = 90.0; 116.397 > 90 → bit=1, range=[90, 180]
Iteration 3: mid = 135.0; 116.397 < 135 → bit=0, range=[90, 135]
Iteration 4: mid = 112.5; 116.397 > 112.5 → bit=1, range=[112.5, 135]
...26 iterations → 26-bit longitude code
Encoding latitude 39.916527 (Beijing):
Similar binary subdivision → 26-bit latitude code
Interleaving (creates 52-bit GeoHash):
lon_bit[25] lat_bit[25] lon_bit[24] lat_bit[24] ... lon_bit[0] lat_bit[0]
This interleaving gives GeoHash its locality property:
nearby points → similar bit prefixes → similar scores in ZSet
Storage in ZSet:
GEOADD locations 116.397128 39.916527 "beijing"
→ internally: ZADD locations <52bit_geohash_as_double> "beijing"
Precision analysis:
52-bit GeoHash grid resolution:
Longitude: 180° / 2^26 ≈ 0.0000027° ≈ 0.6mm at equator
Latitude: 90° / 2^26 ≈ 0.0000013° ≈ 0.15mm at equator
Practical precision (limited by IEEE 754 double 53-bit mantissa):
Longitude error: ~0.00000011° ≈ 11mm
Latitude error: ~0.00000011° ≈ 11mm
This is sub-centimeter accuracy — sufficient for:
- Navigation and location services
- Store/restaurant location (10cm precision far exceeds GPS accuracy)
- Delivery radius calculation
NOT sufficient for:
- Surveying, cadastral boundaries
- High-precision scientific positioning
10.3.2 GEO Commands in Detail
GEOADD:
/* geo.c */
void geoaddCommand(client *c) {
/* Syntax: GEOADD key [NX|XX] [CH] lon lat member [lon lat member ...] */
int i, elements = (c->argc - 2) / 3;
for (i = 0; i < elements; i++) {
double xy[2];
xy[0] = atof(c->argv[2 + i*3]->ptr); /* longitude */
xy[1] = atof(c->argv[3 + i*3]->ptr); /* latitude */
/* Validate coordinate bounds */
if (!verifyGeoCoordinates(xy[0], xy[1])) {
addReplyError(c, "invalid longitude,latitude pair");
return;
}
/* Encode to 52-bit GeoHash */
GeoHashBits hash;
geohashEncodeWGS84(xy[1], xy[0], GEO_STEP_MAX, &hash);
/* GEO_STEP_MAX = 26 iterations */
GeoHashFix52Bits bits = geohashAlign52Bits(hash);
/* bits = (hash.bits << (52 - hash.step*2)) normalized to 52 bits */
/* Add to ZSet with GeoHash as score */
double score = (double)bits;
zsetAdd(zobj, score, member_sds, flags, NULL, NULL);
}
addReplyLongLong(c, added);
}
GEODIST — Haversine formula:
/* geo.c */
double geohashGetDistance(double lon1d, double lat1d,
double lon2d, double lat2d) {
double lat1r, lon1r, lat2r, lon2r, u, v;
lat1r = deg_rad(lat1d);
lon1r = deg_rad(lon1d);
lat2r = deg_rad(lat2d);
lon2r = deg_rad(lon2d);
u = sin((lat2r - lat1r) / 2);
v = sin((lon2r - lon1r) / 2);
/* Haversine formula: */
return 2.0 * EARTH_RADIUS_IN_METERS *
asin(sqrt(u * u +
cos(lat1r) * cos(lat2r) * v * v));
/* EARTH_RADIUS_IN_METERS = 6372797.560856 (mean radius) */
}
/* Usage:
GEODIST locations beijing shanghai km → 1068.48
GEODIST locations pointA pointB m → distance in meters
Supported units: m, km, ft, mi */
GEOSEARCH (Redis 6.2+):
Replaces deprecated GEORADIUS and GEORADIUSBYMEMBER commands.
Syntax:
GEOSEARCH key
FROMMEMBER member | FROMLONLAT longitude latitude
BYRADIUS radius m|km|ft|mi | BYBOX width height m|km|ft|mi
[ASC|DESC]
[COUNT count [ANY]]
[WITHCOORD] [WITHDIST] [WITHHASH]
Examples:
# Find 10 nearest locations within 5km, ascending by distance
GEOSEARCH locations FROMLONLAT 116.397 39.916
BYRADIUS 5 km ASC COUNT 10 WITHDIST WITHCOORD
# Find locations within a 10km × 8km bounding box
GEOSEARCH locations FROMLONLAT 116.397 39.916
BYBOX 10 8 km ASC
# Find locations near a known member
GEOSEARCH locations FROMMEMBER "beijing"
BYRADIUS 100 km ASC
COUNT ANY flag:
Without ANY: scan all matches, sort, return first COUNT
With ANY: return as soon as COUNT results found (faster for sparse data)
10.3.3 Circular Range Query Algorithm
The GeoHash locality property enables efficient range queries:
How GEOSEARCH BYRADIUS works:
Step 1: Compute GeoHash of center point
Center (lon=116.397, lat=39.916) → 52-bit hash H_center
Step 2: Determine the GeoHash precision level that covers the search radius
At level L, each grid cell ≈ (360°/2^(L+1)) × (180°/2^(L+1)) degrees
Choose L such that cell size ≤ radius
Step 3: Find 9 GeoHash cells covering the search area
(center cell + 8 neighboring cells)
┌─────┬─────┬─────┐
│NW │ N │NE │
├─────┼─────┼─────┤
│ W │ CTR │ E │ ← 9 cells around center
├─────┼─────┼─────┤
│SW │ S │SE │
└─────┴─────┴─────┘
Each cell corresponds to a [min_score, max_score] ZSet range.
Step 4: For each of the 9 cells, query ZSet with ZRANGEBYSCORE
Collect all members whose score falls in [min_score, max_score]
Step 5: For each candidate member:
- Decode GeoHash score → (lon, lat)
- Compute exact Haversine distance to center
- Discard if distance > radius (GeoHash cells are rectangles,
so corners extend beyond the circle)
Step 6: Sort results by distance (ASC/DESC), apply COUNT limit
/* geo.c — area query implementation */
int geoGetPointsInRange(robj *zobj, double lon, double lat, ...) {
GeoHashRadius georadius;
georadius = geohashGetAreasByRadiusWGS84(lat, lon, radius_meters);
/* georadius contains 9 GeoHash ranges: .hash (center) + .neighbors */
GeoHashRange *ranges[] = {
&georadius.hash,
&georadius.neighbors.north, &georadius.neighbors.south,
&georadius.neighbors.east, &georadius.neighbors.west,
&georadius.neighbors.north_east, &georadius.neighbors.north_west,
&georadius.neighbors.south_east, &georadius.neighbors.south_west
};
for (int i = 0; i < 9; i++) {
GeoHashRange *r = ranges[i];
if (r->min == 0 && r->max == 0) continue; /* invalid/non-existent neighbor */
/* Equivalent to: ZRANGEBYSCORE zobj r->min r->max */
zrangebyscore_internal(zobj, r->min, r->max, callback);
}
}
10.3.4 Real-World Use Cases
Use Case 1: Nearby Users (Social App)
# Store user locations (updated periodically)
GEOADD users:live 116.397 39.916 "user:10086"
GEOADD users:live 116.410 39.920 "user:20086"
GEOADD users:live 121.473 31.230 "user:30086" # Shanghai user
# Find users within 1km of user 10086
GEOSEARCH users:live FROMMEMBER "user:10086"
BYRADIUS 1 km ASC COUNT 50 WITHCOORD WITHDIST
# Sample output:
# 1) 1) "user:20086"
# 2) "0.8532" (km away)
# 3) 1) "116.41000..."
# 2) "39.92000..."
Use Case 2: Food Delivery — Find Nearby Restaurants
# Populate restaurant locations (one-time or batch update)
GEOADD restaurants 116.400 39.915 "kfc:001"
GEOADD restaurants 116.405 39.918 "mcdonalds:001"
GEOADD restaurants 116.392 39.910 "subway:001"
# User at (116.397, 39.916) wants restaurants within 3km
GEOSEARCH restaurants FROMLONLAT 116.397 39.916
BYRADIUS 3 km ASC COUNT 20 WITHDIST
# Filter by delivery availability in application layer
# (GEO handles geographic filtering; business rules in app)
Use Case 3: Store Locator — Distance Sorting
# Add all store locations
GEOADD stores
116.397 39.916 "store:bj-chaoyang-01"
116.450 39.930 "store:bj-shunyi-01"
121.473 31.230 "store:sh-pudong-01"
# Distance between two specific stores
GEODIST stores store:bj-chaoyang-01 store:sh-pudong-01 km
→ "1068.48" (Beijing to Shanghai great-circle distance)
# Find 5 nearest stores to given coordinates, with distances
GEOSEARCH stores FROMLONLAT 116.397 39.916
BYRADIUS 50 km ASC COUNT 5 WITHDIST
Use Case 4: Geofencing
# Is a delivery person within 200m of the destination?
GEODIST locations driver:12345 destination:order-789 m
→ compare result < 200 in application code
# Or: store destination, query if driver is within range
GEOADD destinations 116.397 39.916 "dest:order-789"
GEOSEARCH destinations FROMLONLAT <driver_lon> <driver_lat>
BYRADIUS 0.2 km ASC COUNT 1
→ if "dest:order-789" appears: driver is within geofence
10.3.5 GEO Limitations
1. Shape Limitation
GEOSEARCH supports: BYRADIUS (circle) and BYBOX (axis-aligned rectangle)
NOT supported: arbitrary polygons, irregular boundaries
→ For polygon geofencing: Tair GIS (Alibaba Cloud Redis extension),
PostGIS, or custom application-layer polygon point-in-polygon check
2. Coordinate Precision
52-bit GeoHash: ~0.6mm theoretical precision
IEEE 754 double (53-bit mantissa): ~11mm actual precision in Redis
Good for: navigation, business locations, delivery tracking
Insufficient for: land surveying, high-precision scientific work
3. No Altitude/Elevation
GEO handles 2D coordinates only
For 3D coordinates: encode (lat, lon, alt) separately,
or use sorted score for one dimension and filter the other two
4. Large Radius Performance
GEOSEARCH BYRADIUS 100 km may require scanning many ZSet entries
9 GeoHash cells × entries per cell = potentially large result set
Recommendation: keep radius ≤ 50km for city-scale searches
use BYBOX for rectangular regions (better cell coverage)
5. Coordinate Update
GEO doesn't have an "update" command — use GEOADD with same member:
GEOADD locations 116.41 39.92 "user:10086" (overwrites previous position)
High-frequency location updates → consider Pub/Sub + batch GEOADD
10.4 Three-Way Memory Comparison
Scenario: 100 million users, track who visited a page
Method 1: Set (exact count, exact membership)
SADD uv:page user1 user2 ...
Memory: 100M × ~60 bytes/member = 6,000 MB = ~6 GB
Method 2: Bitmap (exact count, requires integer user IDs in known range)
SETBIT uv:page user_id 1
Memory: max_user_id / 8 = 100,000,000 / 8 = 12.5 MB
Operations: BITCOUNT for count, GETBIT for membership check
Method 3: HyperLogLog (estimated count, ~0.81% error)
PFADD uv:page user1 user2 ...
Memory: 12 KB (fixed, regardless of element count)
Comparison table:
Method Memory Exact Count Membership Error
────────────────────────────────────────────────────────────
Set 6,000 MB Yes Yes 0%
Bitmap 12.5 MB Yes Yes 0%
HyperLogLog 0.012 MB No No ~0.81%
Bitmap wins on memory for integer IDs with bounded range.
HyperLogLog wins when IDs are strings or range is unbounded.
Scenario: 1 billion geospatial points
GEO (ZSet backed):
Per point: ~60-100 bytes (SDS member name + ZSet node overhead)
1B points: 60-100 GB
Alternative: encode as Bitmap using 52-bit GeoHash
Map 52-bit GeoHash → bit position in bitmap
Memory: 2^52 / 8 = 450 TB (impractical — too sparse)
Realistic prefix-bucketed approach: application-specific
Conclusion: GEO is the right tool for georeferenced data; Bitmap and HLL
address fundamentally different problems.
10.5 Summary
| Data Type | Underlying Storage | Key Commands | Memory Use | Accuracy |
|---|---|---|---|---|
| Bitmap | String (SDS) | SETBIT/GETBIT/BITCOUNT/BITPOS/BITOP | 1 bit/user | Exact |
| HyperLogLog | String + 12KB structure | PFADD/PFCOUNT/PFMERGE | 12KB fixed | ~0.81% error |
| GEO | ZSet (skiplist + dict) | GEOADD/GEOSEARCH/GEODIST/GEOPOS | ~60-100B/point | ~11mm coord precision |
These three types exemplify Redis's design philosophy: for specific constraints (integer domain, cardinality approximation, geospatial locality), specialized data structures yield dramatic efficiency gains over general-purpose approaches.
HyperLogLog is the most striking example: accepting a 0.81% statistical error reduces memory from gigabytes (for a Set-based exact counter) to a fixed 12 kilobytes. This is not a performance optimization — it's a category change in the scale of problems that can be solved within a single Redis instance's memory budget.
Bitmap's SWAR-based BITCOUNT demonstrates that Redis isn't just about data structure selection — algorithmic choices at the instruction level matter too. Counting bits in 8 bytes with 5 instructions (SWAR) vs 64 iterations (naive) is the same order-of-magnitude improvement applied at a different scale.
GEO shows the power of dimensional reduction via space-filling curves: by mapping 2D coordinates to 1D GeoHash values, Redis reuses the highly optimized ZSet for all geospatial operations, adding minimal specialized code while gaining full range query capability.