From 8 GB to 24 MB: Scaling Real‑Time DAU to 200 M Users with Redis HyperLogLog

1. Business Background

The system must provide real‑time, multi‑dimensional, windowed DAU statistics for a dashboard used by operations, experiment, and product teams. Four core requirements are:

Real‑time : events arriving via Kafka must be reflected on the board within seconds.

Multi‑dimensional : dimensions include experiment, channel, country, app version, and device type.

Arbitrary time windows : need counts for the last 5 minutes, 1 hour, 24 hours, and 7 days.

Cost‑controlled : cannot keep adding Redis memory indefinitely.

Typical traffic numbers:

Peak write QPS: ~400 k

Daily active users: ~200 M

Number of dimension combinations: ~2 000

Peak read QPS: ~15 k

P99 query latency target: <20 ms

2. First‑Generation Design – Redis Set

Each dimension had its own Redis Set. The write path was simple:

key = dau:set:20260805:exp_42:channel_appstore:country_us
value = Set<userId>

Advantages:

Exact result – SCARD returns the true unique count.

Low development cost – straightforward logic and debugging.

Problems that emerged with scale:

Memory grows linearly with cardinality (O(N)). A single dimension with 4 M users already consumes >32 MB, and Redis Set overhead (hash buckets, object headers, pointers, fragmentation) makes the real usage much higher.

Hot dimensions (e.g., main channel, default country) concentrate 30‑50 % of traffic, causing CPU spikes, network amplification, slow queries, and replica lag.

Windowed queries require merging many sets (e.g., SUNIONSTORE + SCARD) which is both CPU‑ and memory‑intensive.

Scaling cost is linear – doubling traffic roughly doubles memory.

3. Alternative Solutions and Why HyperLogLog Wins

A quick comparison of candidate approaches:

Solution   Accuracy   Space   Suitable for 64‑bit IDs   Suitable for windowed queries   Verdict
-----------------------------------------------------------------------------------------------
Redis Set   Exact      O(N)    Yes                     General                         Precise but costly
Bitmap     Exact      O(MaxUserId)   No (needs dense IDs)   General                         Not fit for Snowflake IDs
DB COUNT(DISTINCT) Exact   High    Yes                     Offline only                    Too slow for real‑time
HyperLogLog Approx   O(1)    Yes                     Yes                             Best trade‑off

Bitmap was rejected because user IDs are 64‑bit Snowflake values, making the bitmap size (>25 MB per dimension) prohibitive and still suffering from hot‑key issues.

HyperLogLog (HLL) provides a constant‑size sketch (≈12 KB) with a typical error of 0.81 % (p = 14, m = 2¹⁴ registers). It stores only register states, not the raw IDs, giving O(1) space regardless of cardinality.

3.1 HLL Core Idea

Hash each userId to a uniform 64‑bit value. The number of leading zero bits in the hash indicates how rare the value is. By keeping the maximum zero‑run length per bucket, the algorithm can infer the total cardinality.

3.2 Bucketed Estimation

Hash userId with a 64‑bit hash (e.g., MurmurHash3).

Use the first p bits as the bucket index.

Count leading zeros in the remaining bits.

Each bucket records its maximum zero‑run length.

Combine bucket values with a harmonic‑mean estimator and bias correction.

Redis implements HLL with p = 14, yielding 16 384 buckets and the 12 KB size.

3.3 Limitations

Only answers “how many distinct users” – cannot list users or compute set intersections.

Small cardinalities have higher relative error; long‑tail dimensions should be evaluated before using HLL.

Accuracy depends on a good, uniform hash function.

4. Redesign Goals

Core daily HLL storage < 50 MB.

Support 400 k write QPS.

P99 read latency < 20 ms.

Minute, hour, and day granularity windows.

2000+ dimensions with graceful degradation on failures.

Retain an offline exact calibration pipeline.

5. New Architecture – Stream → Local Aggregate → Redis HLL → Offline Calibration

Data flow:

Client or server emits events → Kafka topic user-event.

Stats consumer pod parses dimensions, validates payload.

1‑second local aggregation groups userId by dimension + granularity.

Aggregated batches are flushed to Redis Cluster using PFADD with a TTL.

Query API normalises the requested window, selects the coarsest suitable granularity, merges keys with PFMERGE (if needed), and returns PFCOUNT.

Flink/offline jobs periodically read raw events, build exact daily tables in Hive/ClickHouse, and compare against HLL estimates for calibration.

5.1 Key Design

hll:dau:min:202608051230:{exp42|ios|us|appstore}
hll:dau:hour:2026080512:{exp42|ios|us|appstore}
hll:dau:day:20260805:{exp42|ios|us|appstore}

The hash tag {exp42|ios|us} forces minute, hour, and day keys of the same dimension onto the same Redis slot, enabling PFMERGE without cross‑slot errors.

5.2 Memory Accounting

Day‑level: 2 000 × 12 KB ≈ 24 MB.

Hour‑level (7 days): 2 000 × 24 × 7 × 12 KB ≈ 3.8 GB.

Minute‑level (2 hours): 2 000 × 120 × 12 KB ≈ 2.8 GB.

Only the day‑level is kept permanently; minute and hour keys have short TTLs (2 h and 7 d respectively) to bound total memory.

6. Implementation Details

6.1 Module Layout (Spring Boot + Lettuce)

com.example.stats
├── api
│   └── StatQueryController.java
├── application
│   ├── EventConsumeService.java
│   ├── LocalAggregateFlushService.java
│   ├── DauQueryService.java
│   └── QueryWindowPlanner.java
├── domain
│   ├── model/UserEvent.java
│   └── model/TimeGranularity.java
├── infrastructure
│   ├── kafka/UserEventListener.java
│   ├── redis/HllRedisRepository.java
│   └── redis/RedisKeyBuilder.java
└── config
    ├── RedisConfig.java
    ├── KafkaConsumerConfig.java
    └── StatsProperties.java

6.2 EventConsumeService – Validation & Local Bucketing

public void accept(UserEvent event) {
    Set<ConstraintViolation<UserEvent>> violations = validator.validate(event);
    if (!violations.isEmpty()) {
        throw new IllegalArgumentException("invalid user event");
    }
    Map<TimeGranularity, String> keys = new EnumMap<>(TimeGranularity.class);
    for (TimeGranularity g : TimeGranularity.values()) {
        keys.put(g, keyBuilder.build(g, event.getEventTimeMillis(), event.dimensionTag()));
    }
    String uid = String.valueOf(event.getUserId());
    ConcurrentMap<String, Set<String>> buckets = localBucketsRef.get();
    keys.values().forEach(k -> buckets.computeIfAbsent(k, __ -> ConcurrentHashMap.newKeySet()).add(uid));
}

public ConcurrentMap<String, Set<String>> snapshotAndReset() {
    return localBucketsRef.getAndSet(new ConcurrentHashMap<>());
}

Local aggregation deduplicates within a 1‑second window, reducing duplicate PFADD calls and smoothing write spikes.

6.3 Flush Service – Batch Write & TTL

@Scheduled(fixedDelay = 1000L)
public void flush() {
    ConcurrentMap<String, Set<String>> snapshot = eventConsumeService.snapshotAndReset();
    for (Map.Entry<String, Set<String>> e : snapshot.entrySet()) {
        Duration ttl = resolveTtl(e.getKey());
        try {
            repository.pfadd(e.getKey(), e.getValue().stream().toList(), ttl);
        } catch (Exception ex) {
            log.error("flush hll failed, key={}", e.getKey(), ex);
        }
    }
}

private Duration resolveTtl(String key) {
    if (key.startsWith("hll:dau:min:")) return Duration.ofHours(2);
    if (key.startsWith("hll:dau:hour:")) return Duration.ofDays(7);
    return Duration.ofDays(90);
}

6.4 Kafka Listener – Manual Ack

@KafkaListener(topics = "${stats.kafka.topic}", concurrency = "${stats.kafka.concurrency:20}")
public void onMessage(ConsumerRecord<String, UserEvent> record, Acknowledgment ack) {
    try {
        eventConsumeService.accept(record.value());
        ack.acknowledge();
    } catch (Exception ex) {
        log.error("consume user event failed, partition={}, offset={}", record.partition(), record.offset(), ex);
        throw ex;
    }
}

Manual offset commit guarantees no silent data loss on write failures.

6.5 Query Service & Window Planner

public long query(String dimensionTag, Instant start, Instant end) {
    QueryPlan plan = planner.plan(start, end);
    List<String> keys = plan.points().stream()
        .map(p -> keyBuilder.build(p.granularity(), p.epochMillis(), dimensionTag))
        .toList();
    return repository.mergeAndCount(keys, Duration.ofSeconds(30));
}

The planner maps the requested interval to the coarsest granularity that still satisfies the window (e.g., recent 15 min → minute granularity, recent 6 h → hour granularity). This dramatically reduces the number of keys merged per request.

7. High‑Concurrency Design

Kafka partitioning : use dimensionTag as the message key so events of the same dimension land on the same partition, reducing out‑of‑order processing.

Consumer‑side peak‑shaving : batch poll and 1‑second local aggregation.

Separate Redis connection pools for writes and reads to avoid read‑spike starvation of write commands.

Query cache : hot dashboard windows are cached locally for 1‑3 seconds, avoiding repeated PFMERGE operations.

Hot‑dimension handling : dedicated metrics, optional separate Kafka topics, and isolated consumer groups.

8. Failure‑Tolerant Design

HLL provides idempotent PFADD, but business‑level idempotency (e.g., duplicate dimension parsing) must still be handled.

Write failures are logged, retried via a back‑off queue, and the consumer pauses offset commits to avoid silent loss.

Degradation strategy: return cached results, fall back to offline exact tables, rate‑limit non‑core dimensions, and display a “data delayed” banner.

Recovery flow: after Redis recovers, the consumer resumes, replays the accumulated Kafka backlog, and duplicate PFADD calls are harmless.

9. Observability & Alerting

Four layers of metrics:

Ingress : Kafka consume rate, lag, retry count, invalid‑message count.

Write : PFADD QPS, command latency, flush success rate, bucket count per second.

Query : QPS, P50/P95/P99 latency, number of merged keys per request, cache hit ratio.

Result : HLL vs offline true‑value error rate, hot‑dimension Top‑N, key counts per granularity, Redis slot memory distribution.

Alerting combines resource thresholds (Kafka lag, Redis PFADD P99 latency, hot‑slot command spikes) with data‑quality checks (HLL error exceeding a configurable bound).

10. Common Misconceptions

HLL does not magically solve all memory problems – you still need sensible TTLs and granularity choices.

The 0.81 % error is a statistical expectation; small‑cardinality dimensions can exhibit higher relative error.

HLL complements, not replaces, offline exact pipelines; it cannot provide per‑user detail or set intersections.

Redis Cluster handles capacity but does not eliminate hot‑key skew; application‑level sharding and cache strategies are still required.

11. Evolution Path for Growing Dimensions

If the number of dimensions expands from 2 000 to 10 000, three practical routes are suggested:

Layered dimension governance : keep minute/hour granularity only for core and high‑frequency dimensions; long‑tail dimensions retain only day‑level keys.

Hybrid exact‑approx architecture : route a few critical dimensions through a Flink stateful job that writes exact counts to Redis String or an OLAP store, while the rest stay in HLL.

Domain‑based cluster splitting : separate Redis clusters per business domain (content, e‑commerce, experiments) and add a routing layer in the query service.

12. Takeaways

Accepting a bounded approximation unlocks engineering certainty (memory, CPU, latency).

Memory optimisation is a system‑level problem: time‑window design, TTL strategy, hot‑key mitigation, and merge planning all matter.

Good architecture isolates concerns – Kafka for decoupling, local aggregation for write‑shaping, HLL for scalable distinct counting, and offline calibration for accuracy guarantees.

For teams facing similar high‑throughput, multi‑dimensional UV/DAU challenges, the described HyperLogLog‑centric pipeline offers a proven, production‑grade blueprint. If your workload is still modest (few dimensions, low QPS, zero tolerance for error), a precise Set‑based solution may remain the simpler choice.