Special Data Types: Bitmaps, HyperLogLog, Geospatial and Probabilistic Structures (Bloom, Cuckoo, Top-K)

Version note: The examples in this post were run with Redis 8.10.3 (redis:8), Valkey 9.1.3, .NET 10 and StackExchange.Redis 3.4.35.

Guess First

In post 05 we kept the daily unique visitors of Bookstore, the online bookstore used as the shared example across this site's series, in one set per day: 20,000 visits a day from a pool of 50,000 customers, 16,429 members and about 622 KB for one day's set. Let's write the same data, with the same random seed, into three structures at once: a set, a bitmap holding one bit per customer number, and a HyperLogLog (HLL):

int[] customerIds = [.. Enumerable.Range(0, 20_000).Select(_ => random.Next(1, 50_001))];
await db.SetAddAsync($"bookstore:visitors:{day}", [.. customerIds.Select(id => (RedisValue)id)]);  // SADD
await db.HyperLogLogAddAsync($"bookstore:visitors:hll:{day}", [.. customerIds.Select(id => (RedisValue)id)]); // PFADD
IBatch batch = db.CreateBatch();
Task[] bits = [.. customerIds.Select(id => batch.StringSetBitAsync($"bookstore:active:{day}", id, true))]; // SETBIT
batch.Execute();
await Task.WhenAll(bits);

How many bytes do the bitmap and the HLL need for one day? Which one counts exactly and which one approximately? In post 05 the unique visitors of the seven days came out as 46,925 with SUNIONCARD; what do the other two say?

dotnet run --project src/Bookstore.RedisLab -- unique-visitors

one day (20261108):
  set     16,429 visitors    636,423 bytes
  bitmap  16,429 visitors     12,332 bytes
  hll     16,473 visitors     14,386 bytes
7 days:
  SUNIONCARD           46,925
  BITOP OR + BITCOUNT  46,925
  PFCOUNT (7 keys)     47,131  error 0.44 %
  every day: BITOP AND + BITCOUNT 20, SINTERCARD 20

The bitmap gave the same exact result with about a fiftieth of the set's memory; the HLL counted 44 too many and was off by 0.44 % for the week. Look closely and you will recognize 47,131: SUNIONCARD … APPROX in post 05 returned exactly this number, because that option uses HyperLogLog internally too. This post covers structures that save memory by giving up some exactness or by using the shape of the data: bitmaps and BITFIELD, HyperLogLog, Geo for the nearest warehouse, Bloom, Cuckoo, Count-Min Sketch, Top-K and t-digest, which became part of the core in Redis 8, and finally the new Array type of 8.8.

Bitmaps: One Bit per Customer

Redis has no separate bitmap type; a bitmap is a string that is read and written at the bit level. SETBIT key offset 1 sets the bit at that offset to 1 and grows the string up to that offset if needed:

127.0.0.1:6379> SETBIT bookstore:active:20261114 7 1
(integer) 0
127.0.0.1:6379> SETBIT bookstore:active:20261114 42 1
(integer) 0
127.0.0.1:6379> GETBIT bookstore:active:20261114 42
(integer) 1
127.0.0.1:6379> GETBIT bookstore:active:20261114 43
(integer) 0
127.0.0.1:6379> BITCOUNT bookstore:active:20261114
(integer) 2
127.0.0.1:6379> BITPOS bookstore:active:20261114 1
(integer) 7
127.0.0.1:6379> STRLEN bookstore:active:20261114
(integer) 6
127.0.0.1:6379> SETBIT bookstore:active:20261114 100000000 1
(integer) 0
127.0.0.1:6379> STRLEN bookstore:active:20261114
(integer) 12500001
127.0.0.1:6379> MEMORY USAGE bookstore:active:20261114
(integer) 14680108

Customers 7 and 42 visited today; BITCOUNT counts the bits set to 1 and BITPOS finds the position of the first one. The return value of SETBIT is the old value of the bit: 0 means the customer is visiting for the first time today, like the return value of SADD in post 05. For bit 42 the string grew to 6 bytes. Then a customer with number 100,000,000 visited, and the string jumped to 12.5 million bytes at once, 14 MB with the memory Redis allocated. All of the bitmap's advantage depends on the numbers being dense: with numbers from 1 to 50,000 a day takes 12 KB; with the same number of customers but scattered, large numbers it takes megabytes. If your identities are GUIDs or large, sparse numbers, do not use a bitmap, or map the identity to a dense sequence number first.

The real strength is in operations across days. BITOP OR combines the bitmaps of seven days into "visited at least once this week", BITOP AND into "visited every day"; in Guess First both gave exactly the same results as the sets (46,925 and 20). The cost of BITOP grows with the length of the bitmaps, not with the number of members; keep that in mind for sparse, long bitmaps. In Bookstore.Api every visit is now written to three places; we keep the set from post 05 for comparison:

// One visit, three structures: exact set (05), bitmap per customer id and HyperLogLog (07)
app.MapPost("/visits", async (VisitRequest request, IConnectionMultiplexer redis, TimeProvider clock) =>
{
    IDatabase db = redis.GetDatabase();
    DateOnly day = DateOnly.FromDateTime(clock.GetUtcNow().UtcDateTime);
    RedisKey set = RedisKeys.DailyVisitors(day), bitmap = RedisKeys.ActiveCustomers(day), hll = RedisKeys.DailyVisitorsHll(day);

    Task<bool> added = db.SetAddAsync(set, request.CustomerId);                     // SADD
    Task<bool> wasActive = db.StringSetBitAsync(bitmap, request.CustomerId, true);   // SETBIT: returns the old bit
    Task<bool> hllChanged = db.HyperLogLogAddAsync(hll, request.CustomerId);         // PFADD
    Task[] ttl = [.. new[] { set, bitmap, hll }.Select(k => db.KeyExpireAsync(k, Retention, ExpireWhen.HasNoExpiry))];
    await Task.WhenAll([added, wasActive, hllChanged, .. ttl]);
    return Results.Ok(new { firstVisitToday = added.Result, wasActiveBefore = wasActive.Result });
});

curl -X POST http://localhost:5080/visits -H "Content-Type: application/json" -d '{"customerId":7}'
{"firstVisitToday":true,"wasActiveBefore":false}
curl -X POST http://localhost:5080/visits -H "Content-Type: application/json" -d '{"customerId":7}'
{"firstVisitToday":false,"wasActiveBefore":true}
curl -X POST http://localhost:5080/visits -H "Content-Type: application/json" -d '{"customerId":42}'
{"firstVisitToday":true,"wasActiveBefore":false}
curl http://localhost:5080/visits/2026-11-14/active
{"day":"2026-11-14","activeCustomers":2}

All three keys get an 8-day TTL, only on the first write with EXPIRE … NX, as in post 05.

BITFIELD: Small Counters in One Key

BITFIELD lets you use a string as an array of integers of whatever width you choose. To keep the 1-to-5 star distribution of every book at Bookstore, a single 20-byte string is enough instead of five separate keys or a hash:

127.0.0.1:6379> BITFIELD bookstore:book:9780441013593:ratings INCRBY u32 #4 1 INCRBY u32 #4 1 INCRBY u32 #2 1
1) (integer) 1
2) (integer) 2
3) (integer) 1
127.0.0.1:6379> BITFIELD bookstore:book:9780441013593:ratings GET u32 #0 GET u32 #1 GET u32 #2 GET u32 #3 GET u32 #4
1) (integer) 0
2) (integer) 0
3) (integer) 1
4) (integer) 0
5) (integer) 2
127.0.0.1:6379> STRLEN bookstore:book:9780441013593:ratings
(integer) 20

u32 is a 32-bit unsigned integer and #4 is "the fourth u32", the field starting at bit 128. Dune (9780441013593) got two 5-star ratings and one 3-star rating. Several operations in one command run atomically, and with OVERFLOW WRAP|SAT|FAIL you choose what happens when a counter overflows. Over a million books the memory difference against a hash is significant, but readability suffers: the code has to know which offset is which star.

HyperLogLog: Unique Counting in 12 KB

HyperLogLog is an algorithm that answers "how many distinct elements have I seen?" approximately, without storing the elements. It looks at each element's hash and updates an array of small counters (registers); the element itself is not kept anywhere, so it cannot answer "did customer 7 visit?". According to the Redis docs, an HLL in Redis uses at most 12 KB and has a standard error of 0.81 %. The measurement shows two different numbers: the HLL itself (STRLEN) is 12,304 bytes, the 12 KB from the docs plus a 16-byte header; MEMORY USAGE shows 14,386 bytes, because the memory allocator (jemalloc) serves 12,304 bytes from a larger size class. An HLL that has seen few elements is much smaller in the sparse encoding: the STRLEN of an HLL with 3 elements is 27 bytes. The switch from sparse to dense is governed by hll-sparse-max-bytes (3000).

To see the effect of scale, I wrote 100, 10,000 and 1,000,000 distinct customers into the three structures:

dotnet run --project src/Bookstore.RedisLab -- unique-scale

      100 customers  set          240 B   bitmap        50 B   hll    480 B  estimate       100 (+0.00 %)
   10,000 customers  set      350,056 B   bitmap     1,317 B   hll 14,370 B  estimate     9,988 (-0.12 %)
1,000,000 customers  set   32,277,596 B   bitmap   131,111 B   hll 14,372 B  estimate 1,009,972 (+1.00 %)

The set grows with the number of customers and reaches 31 MB at a million; the HLL is constant after 10,000. At a million the error is 1.00 %, slightly above the 0.81 % in the docs. That is not a contradiction: 0.81 % is the standard error, and a single measurement can deviate more than that; most estimates stay within ±1.6 % (two standard errors). Note that the bitmap also does well in this table: the numbers start at 1 and are dense, so a million customers take 128 KB and the result is exact. If your identities have that shape, consider a bitmap first; if not, or if you count something other than customers (search terms, IP addresses, page paths), use an HLL.

There are two ways to count over several HLLs: PFCOUNT k1 k2 … k7 computes the union temporarily and counts it, PFMERGE dest k1 … k7 writes the union to a key. Bookstore.Api's weekly endpoint now returns both numbers:

// Unique visitors over the last 7 days: exact with SUNIONCARD (Redis 8.10+), estimated with PFCOUNT
Task<long> exact = db.SetCombineLengthAsync(SetOperation.Union, [.. days.Select(RedisKeys.DailyVisitors)]);
Task<long> estimated = db.HyperLogLogLengthAsync([.. days.Select(RedisKeys.DailyVisitorsHll)]); // PFCOUNT k1 ... k7
await Task.WhenAll(exact, estimated);

curl http://localhost:5080/visits/weekly
{"from":"2026-11-08","to":"2026-11-14","uniqueVisitors":2,"estimatedUniqueVisitors":2}

For small numbers the HLL is exact; the difference only shows up in the thousands. Approximate counting has a price as well: you cannot remove an element from an HLL, and you cannot ask "was this customer counted?".

Geo: the Nearest Warehouse

Bookstore has three warehouses (the coordinates are illustrative). Finding the warehouse nearest to the delivery address is the first step of a shipping time estimate:

127.0.0.1:6379> GEOADD bookstore:warehouses 28.9784 41.0082 istanbul 32.8597 39.9334 ankara 27.1428 38.4237 izmir
(integer) 3
127.0.0.1:6379> GEOSEARCH bookstore:warehouses FROMLONLAT 29.0610 40.1885 BYRADIUS 400 km ASC WITHDIST COUNT 2
1) 1) "istanbul"
   2) "91.4387"
2) 1) "izmir"
   2) "256.4705"
127.0.0.1:6379> GEOSEARCH bookstore:warehouses FROMLONLAT 30.5206 39.7767 BYRADIUS 400 km ASC WITHDIST
1) 1) "istanbul"
   2) "189.2814"
2) 1) "ankara"
   2) "200.4772"
3) 1) "izmir"
   2) "328.0742"
127.0.0.1:6379> GEODIST bookstore:warehouses istanbul ankara km
"349.4544"
127.0.0.1:6379> GEOPOS bookstore:warehouses izmir
1) 1) "27.142799198627472"
   2) "38.42369991211598"
127.0.0.1:6379> TYPE bookstore:warehouses
zset
127.0.0.1:6379> ZSCORE bookstore:warehouses istanbul
"3508663909312994"

Coordinates are written longitude first, then latitude; writing them the other way round is the most common mistake. For an address in Bursa, Istanbul is nearest at 91 km. For an address in Eskisehir the answer is Istanbul (189 km), not Ankara (200 km): Redis computes straight-line distance and knows nothing about roads or shipping routes. The Izmir coordinate changing in the sixth decimal when read back is a hint too. Geo is not a separate type but a sorted set: each point is turned into a 52-bit geohash and stored as the score. That is why TYPE says zset, why every sorted set command from post 06 (ZREM, ZCARD) works here, and why a position is rounded at the scale of centimeters. The endpoint in Bookstore.Api:

// Nearest warehouse to the delivery address: GEOSEARCH ... BYRADIUS ... ASC COUNT 1 WITHDIST
app.MapGet("/warehouses/nearest", async (double lon, double lat, IConnectionMultiplexer redis, double radiusKm = 400) =>
{
    GeoRadiusResult[] found = await redis.GetDatabase().GeoSearchAsync(RedisKeys.Warehouses, lon, lat,
        new GeoSearchCircle(radiusKm, GeoUnit.Kilometers), count: 1, demandClosest: true,
        order: Order.Ascending, options: GeoRadiusOptions.WithDistance);
    return found.Length == 0
        ? Results.NotFound(new { error = $"no warehouse within {radiusKm} km" })
        : Results.Ok(new { warehouse = found[0].Member.ToString(), distanceKm = found[0].Distance });
});

curl "http://localhost:5080/warehouses/nearest?lon=29.0610&lat=40.1885"
{"warehouse":"istanbul","distanceKm":91.4387}
curl -i "http://localhost:5080/warehouses/nearest?lon=43.3832&lat=38.5012"
HTTP/1.1 404 Not Found

{"error":"no warehouse within 400 km"}

demandClosest: true does not add ANY to the command; Redis finds and sorts every point within the radius and returns the nearest. ANY (demandClosest: false) stops as soon as it has found enough points and is faster on large data sets, but the point returned may not be the nearest.

Bloom and Cuckoo Filters

With Redis 8 the probabilistic structures that used to live in the RedisBloom module became part of the core distribution; the redis:8 image needs no extra installation. A Bloom filter says "definitely not in the set" or "probably in the set"; a false "yes" (false positive) is possible, a false "no" is not. At Bookstore the use is clear: requests with ISBNs that are not in the catalog are never found in the cache and go to the database every time. That is the cache penetration problem from "Cache Stampede, Penetration and Avalanche: Three Problems That Break Caches in Production" in the Caching series; the solution side is there, here we look at the numbers on the Redis side. I wrote a million ISBNs into a filter with a 1 % target error and the same ISBNs into a set, then asked about 100,000 ISBNs that are not in the catalog (StackExchange.Redis has no typed API for the BF.* commands, they are sent with ExecuteAsync; typed counterparts are in NRedisStack, which we use in post 11):

await db.ExecuteAsync("BF.RESERVE", filter, 0.01, 1_000_000);
for (long start = 0; start < 1_000_000; start += 10_000)
{
    object[] args = [filter, .. Enumerable.Range(0, 10_000).Select(i => (object)Isbn(start + i))];
    await db.ExecuteAsync("BF.MADD", args);
}

dotnet run --project src/Bookstore.RedisLab -- probabilistic

bloom: 1,000,000 ISBNs in 1,378,616 bytes (set: 39,388,706 bytes), false positives 516 of 100,000 (0.52 %)

The filter is 1.3 MB, the set 37.6 MB. According to the formula in the docs, a 1 % error needs 9.585 bits per element; for a million elements that is 1.2 MB. The 1.38 MB I measured is more, and the false positive rate is half the target: 0.52 %. Both have the same cause, and BF.DEBUG shows it:

127.0.0.1:6379> BF.RESERVE bookstore:catalog:scaling 0.01 1000000
OK
127.0.0.1:6379> BF.DEBUG bookstore:catalog:scaling
1) "size:0"
2) "bytes:1378472 bits:11027776 hashes:8 hashwidth:64 capacity:1000000 size:0 ratio:0.005"
127.0.0.1:6379> BF.RESERVE bookstore:catalog:fixed 0.01 1000000 NONSCALING
OK
127.0.0.1:6379> BF.DEBUG bookstore:catalog:fixed
1) "size:0"
2) "bytes:1198136 bits:9585088 hashes:7 hashwidth:64 capacity:1000000 size:0 ratio:0.01"

In a filter that can grow (the default), Redis builds the first sub-filter with half the requested error (ratio:0.005), so that the total error stays under the target once the errors of sub-filters added after the capacity is exceeded are added in. With NONSCALING the allocated memory matches the formula exactly: 9,585,088 bits. That is why getting the capacity right matters: once it is exceeded, Redis adds another sub-filter (default EXPANSION 2) and every "no" answer now has to check more than one filter; in a NONSCALING filter, the error rate starts to grow instead. If you call BF.ADD without BF.RESERVE, the filter is created with defaults; BF.INFO showed a capacity of 100, so for a large catalog the chain of sub-filters starts right away.

You cannot remove an element from a Bloom filter. If you need removal, there is the Cuckoo filter; for example, for "has this coupon code been used?" when a returned order's coupon has to be reopened:

127.0.0.1:6379> CF.RESERVE bookstore:coupons:used 100000
OK
127.0.0.1:6379> CF.ADD bookstore:coupons:used WELCOME-7F3C
(integer) 1
127.0.0.1:6379> CF.EXISTS bookstore:coupons:used WELCOME-7F3C
(integer) 1
127.0.0.1:6379> CF.DEL bookstore:coupons:used WELCOME-7F3C
(integer) 1
127.0.0.1:6379> CF.EXISTS bookstore:coupons:used WELCOME-7F3C
(integer) 0

According to the docs, Bloom is faster on inserts and Cuckoo on checks. In a Cuckoo filter, delete only an element you really added: deleting an element that was never added but shows as "present" can remove the trace of another element. The real record of coupon use is still in the database; the filter only cuts unnecessary queries.

Count-Min Sketch, Top-K and t-digest

The rest of the same experiment answers three questions. Which search terms are searched most (Top-K)? How many times was a given term searched (Count-Min Sketch)? What is the 95th percentile of order totals (t-digest)? I used 100,000 searches over 17,205 distinct terms and 100,000 order totals:

top-k (estimate / exact):
  dune     21,135 / 21,136
  hobbit    8,742 /  8,754
  tolkien   6,742 /  6,754
  austen    5,672 /  5,684
  orwell    4,973 /  4,982
count-min sketch (estimate / exact): dune 21,140 / 21,136, middlemarch 4,195 / 4,189, q42 13 / 2, never-searched 4 / 0
memory: top-k 2,696 B, cms 56,072 B, distinct terms 17,205
t-digest (estimate / exact): p50 147.60 / 147.81, p95 395.42 / 395.13, p99 600.93 / 601.11, 9,888 bytes

With 2.7 KB, Top-K found the top five terms in the right order; its counts are very close to the truth but slightly low. Count-Min Sketch always overcounts and never undercounts: for popular terms the difference is small (21,140 against 21,136), for rare terms it is large in proportion (13 for q42, which was searched twice), and even a term that was never searched shows 4. So it suits "find the most searched terms", not "count the rare terms". t-digest kept 100,000 totals in 9.9 KB and gave the 95th percentile as 395.42 TL; the exact value is 395.13. Instead of storing and sorting every value for percentiles, t-digest works with an error under one lira even at the tail (p99). All of these are ordinary Redis keys with their own add and query commands; you can give them a TTL and build time windows with daily keys.

Valkey Differences and the New Types

On Valkey 9.1.3 the bitmap, BITFIELD, HyperLogLog and Geo commands behaved the same as on Redis. Probabilistic structures are a different story: on the valkey/valkey:9 image, BF.ADD, CF.RESERVE, TOPK.RESERVE and TDIGEST.CREATE returned ERR unknown command. On Valkey, Bloom filters come with a separate module, valkey-bloom (the Valkey docs call it an official module for 8.0 and later and point Docker users to the valkey-bundle image), which is compatible with the BF.* commands. I could not find a counterpart for Cuckoo, Count-Min Sketch, Top-K or t-digest in the Valkey docs; an application that uses them needs an alternative when moving to Valkey.

Redis 8.8 also brought an Array type: a string array accessed by index that can be sparse. Remember the bitmap pitfall; here is the same large index written to an Array:

127.0.0.1:6379> ARSET bookstore:book:9780441013593:daily-sales 317 12
(integer) 1
127.0.0.1:6379> ARSET bookstore:book:9780441013593:daily-sales 100000000 1
(integer) 1
127.0.0.1:6379> ARGET bookstore:book:9780441013593:daily-sales 317
"12"
127.0.0.1:6379> ARLEN bookstore:book:9780441013593:daily-sales
(integer) 100000001
127.0.0.1:6379> ARCOUNT bookstore:book:9780441013593:daily-sales
(integer) 2
127.0.0.1:6379> MEMORY USAGE bookstore:book:9780441013593:daily-sales
(integer) 33165

The length shows as 100 million, but there are only two filled elements and the key takes 33 KB; the bitmap took 14 MB for the same index. There is also ARRING for a fixed-size ring buffer and AROP for operations such as sums over a range. The type is very new (8.8, May 2026) and not in Valkey (ERR unknown command for ARSET); check client support and the Redis version of your managed service before using it in production. The same distribution also includes the Time Series type (the TS.* commands: timestamped measurements with automatic downsampling rules) and vector sets (VADD, VSIM). Using vector sets as a vector store is the topic of "Choosing a Vector Database: pgvector, SQL Server 2025, Qdrant, Azure AI Search and Elasticsearch" in the RAG series.

In Production

You should be able to state your choice in one sentence: "I need an exact count and identities are dense: bitmap"; "1 % error is fine and identities are arbitrary: HLL"; "knowing absence for certain is enough: Bloom". To estimate memory, run a small test with real data and look at MEMORY USAGE; in this post the theoretical values in the docs (12 KB for an HLL, 9.585 bits per element for Bloom) differed from MEMORY USAGE by 15–20 %, because of the allocator's size classes and the tightened error rate of a growable filter. In a bitmap a single large offset grows the key to megabytes at once, and the server has to allocate that memory during the write; if the offset comes from outside input, put an upper bound on it. In probabilistic structures, capacity and error rate are given at creation and cannot be changed later; if the data turns out larger than you estimated, you have to create a new filter and fill it again. Give daily keys a TTL; even a 12 KB HLL adds up when kept per customer or per page per day.

Common Pitfalls

Using an approximate structure where an exact result is required: billed users, stock and coupon limits are not computed with an HLL or a Bloom filter. In Guess First, the HLL overcounted by 44 people in a single day.

A bitmap with sparse, large identities: a single customer with number 100,000,000 grew the key to 14 MB.

Using Count-Min Sketch to count rare events: a term that was never searched showed 4, a term searched twice showed 13.

Creating a Bloom filter without a capacity: the filter created by BF.ADD has a capacity of 100.

Swapping latitude and longitude in Geo, or taking straight-line distance for delivery distance.

Assuming Redis 8's probabilistic commands or 8.8's Array on Valkey or on an older managed Redis.

A Small Experiment

★☆☆ Merge two days' HLLs with PFMERGE and compare the PFCOUNT of the result with PFCOUNT k1 k2 over both keys. Are they the same?

★★☆ Repeat the unique-scale experiment with customer numbers starting at 1,000,000,000 instead of 1. How does the memory of the set, the bitmap and the HLL change?

★★★ Create a Bloom filter with a capacity of 1,000 and add a million ISBNs. How do the number of sub-filters in BF.INFO, the memory and the false positive rate change? Try the same with NONSCALING: what happens this time?

In the next post we move on to atomicity: why MULTI/EXEC does not roll back, optimistic concurrency with WATCH, Lua scripts and Redis Functions; at Bookstore we will reserve stock in one atomic step and reduce the snapshot build from post 06 to a single step as well.