Skip to content
notes.vinhnq.com

Search

System DesignSenior19 min read

A liveness system: from a Redis sorted set to a timing wheel and the LMAX Disruptor

Review 14 cards
On this page

An underrated system design question: detect that a device is “dead” when it stops sending heartbeats. This post goes from the requirements to the data structure (Redis sorted set, timing wheel), then to splitting work across threads and the Disruptor queue. Afterwards you’ll be able to analyse a data structure against the real load of a problem, not just its big-O. The same problem seen from the architecture side (Kafka partitions, preventing false alarms when consumers lag, deduplicated alerts): Case study: a liveness system for 1 million IoT devices.

1. How to analyse a data structure

Key idea: ask five questions: what it’s for, what a point read and a range read cost, what writes cost, how much memory it takes and whether it’s contiguous or scattered, and what its limits are.

Question Example with a Redis ZSET
Use case leaderboards, timers, time-ordered queues
Point read ZSCORE O(1)
Range read ZRANGE ... BYSCORE O(log n + m)
Write (insert/update/remove) ZADD/ZREM O(log n)
Memory skiplist + hash, scattered on the heap, tens of bytes per member
Limits one key lives on one node, can’t be split across a cluster

You don’t need to memorise every structure. Keep a cheat sheet and learn the one you need in depth when you need it. Once you understand how it’s implemented, you can work out its limits yourself.

Big-O is only one axis. An O(1) operation over the network (≈0.5 ms) is thousands of times slower than an O(log n) one in RAM (≈100 ns). A contiguous array is far friendlier to the CPU cache than a scattered linked list, even though both are O(n).

Cheat sheet: data structures that keep showing up in system design
Structure Used for Limit to remember
Consistent hashing spreading keys over nodes, adding/removing a node moves only ~1/n of keys needs virtual nodes for an even spread
Geohash nearby search (shared prefix = close together) points near a cell edge may have different prefixes, check the 8 neighbours
Token bucket / leaky bucket rate limiting token bucket allows bursts, leaky bucket smooths the rate
Bloom filter answering “definitely not here” to skip an expensive lookup false positives, no deletes (plain version)
Trie autocomplete memory hungry, usually stores top-k at each node
Rsync (rolling checksum) file sync, sending only the changed parts the weak checksum must be confirmed by a strong one
Raft distributed consensus (etcd, KRaft) needs a majority alive
Merkle tree finding where replicas diverge tree must be rebuilt when lots of data changes
HyperLogLog approximate count of distinct items, 12 KB ~0.81% error
Inverted index full-text search updates are expensive, usually batched
Hierarchical timing wheels schedulers, timeouts, heartbeats precision is one tick
Lossy counting / Count-min sketch heavy hitters, approximate frequencies estimates only, count-min always over-counts
Operational transformation collaborative editing complex, many systems moved to CRDTs
Frugal streaming approximate median and percentiles over a stream approximate only

I wrote in detail about ZSET and HyperLogLog in Redis and Bloom filters against cache penetration.

2. The liveness problem

Key idea: 1 million IoT devices send a heartbeat every 3 seconds. Any device silent for longer than its timeout (configured per device type) is reported as “disconnected”; a small alert delay is acceptable.

Functional requirements:

  • No heartbeat within the timeout means an alert that the device is disconnected.
  • The timeout is configured per device type (street lamps 30 seconds, traffic sensors 10 seconds…).

Non-functional requirements: scalable, and a small delay between expiry and alert is fine (say ≤ 1 second).

Quick estimate:

  • Heartbeats: 10⁶ / 3 seconds ≈ 333K per second. Each one is a “reset timer” operation.
  • Live timers at once: 10⁶. About 64 bytes each (id, expiry, pointers) → ~64 MB, fits in one machine’s RAM.
  • Expiries: normally close to zero; when a cell tower loses power, 100K devices may expire in the same second.

Three questions drive the design: how cheap is a timer reset, how cheap is finding expired timers (and how often you scan), and how you handle a big wave of expiries.

3. Option 1: Redis sorted set

Key idea: one ZSET per device type, member = device_id, score = expiry time. A heartbeat is a ZADD that overwrites the score; a periodic job fetches and removes members whose score is below now.

# heartbeat: overwrite the score, O(log n)
ZADD timeout:street_lamp <now + 30000> lamp-42

# every second: fetch and remove expired timers, O(log n + m)
ZRANGE timeout:street_lamp -inf <now> BYSCORE LIMIT 0 1000
ZREM timeout:street_lamp lamp-17 lamp-99 ...
  • ZADD on an existing member just updates its score, so “add the new timer” and “remove the old one” are really one command.
  • ZREMRANGEBYSCORE is also O(log n + m) but only returns the count removed, not the members, so you can’t alert from it. You have to read, then remove.
  • Keying by device type spreads load: each ZSET can live on a different Redis Cluster node.

The variant on the slides (called 1.2): don’t remove the old timer, store device_id → expiry as a string too, and compare against it when scanning to drop stale timers. That adds I/O and can’t be wrapped in one Lua script when the keys land in different cluster slots. It’s also unnecessary: ZADD already overwrites the score.

An atomic fetch-and-remove Lua script, and the real cost
-- KEYS[1] = timeout:street_lamp, ARGV[1] = now, ARGV[2] = limit
local expired = redis.call('ZRANGE', KEYS[1], '-inf', ARGV[1], 'BYSCORE', 'LIMIT', 0, ARGV[2])
if #expired > 0 then
  redis.call('ZREM', KEYS[1], unpack(expired))
end
return expired

Lua runs atomically on one node, so no heartbeat can slip in between. The LIMIT keeps the script from blocking Redis too long during a big wave of expiries (Redis is single-threaded).

Cost: 333K ZADD/second is beyond one Redis node (~100K–200K single commands/second, more with pipelining). You need to split by device type and add a shard suffix (timeout:street_lamp:{0..15}, chosen by hash(device_id) % 16). Every heartbeat is still a network hop from the heartbeat server to Redis.

In return, Redis gives you persistence and replication for free: restarting the service doesn’t lose timers.

4. Option 2: a timing wheel

Key idea: a fixed circular array of buckets; each bucket holds the timers expiring at that tick. Resetting a timer means unlinking it from the old bucket and linking it into a new one, O(1). Each tick scans exactly one bucket.

The parts:

  • Wheel: a fixed-size circular array, for example 60 slots with a 1-second tick (size ~ the timeout).
  • Bucket: each slot is a list of timers (usually doubly linked for O(1) removal).
  • Timer: device_id, slot index, remaining rounds (when the timeout is longer than one turn of the wheel).
  • Map<deviceId, Timer>: find a device’s old timer in O(1).
flowchart LR
  HB[Heartbeat lamp-42] --> M["Map: lamp-42 -> timer (slot 7)"]
  M --> R[Unlink from slot 7]
  R --> A["Link into slot (current + 30) mod 60"]
  T[Tick every second] --> S[Scan only the slot under the hand]
  S --> X{Remaining rounds = 0?}
  X -->|yes| AL[Alert: disconnected]
  X -->|no| D[Decrement rounds]

When a heartbeat arrives: get the timer from the map, unlink it from its old bucket, compute the new slot (current tick + timeout) mod size, link it into the new bucket. All O(1), all in RAM.

What about long timers? A 60-slot, 1-second wheel only covers 60 seconds; a 1-hour timeout needs “remaining rounds”, and every pass of the hand has to look at timers that aren’t due yet. Kafka solves this with hierarchical timing wheels: a seconds wheel, a minutes wheel and an hours wheel stacked together. Far-off timers sit on the coarse wheel and move down to a finer wheel as they get close.

Java code: a minimal timing wheel for heartbeats
final class TimingWheel {
    private final int size;                 // number of slots, e.g. 60
    private final List<Set<String>> buckets;
    private final Map<String, Integer> slotOf = new HashMap<>();
    private final Map<String, Integer> roundsOf = new HashMap<>();
    private int cursor = 0;

    TimingWheel(int size) {
        this.size = size;
        this.buckets = new ArrayList<>(size);
        for (int i = 0; i < size; i++) buckets.add(new HashSet<>());
    }

    // called on the wheel's own thread (a single thread owns this structure)
    void heartbeat(String deviceId, int timeoutTicks) {
        Integer old = slotOf.get(deviceId);
        if (old != null) buckets.get(old).remove(deviceId);  // O(1)
        int slot = (cursor + timeoutTicks) % size;
        buckets.get(slot).add(deviceId);
        slotOf.put(deviceId, slot);
        roundsOf.put(deviceId, timeoutTicks / size);
    }

    // called every tick, returns the devices that expired
    List<String> tick() {
        cursor = (cursor + 1) % size;
        List<String> expired = new ArrayList<>();
        Iterator<String> it = buckets.get(cursor).iterator();
        while (it.hasNext()) {
            String id = it.next();
            int rounds = roundsOf.get(id);
            if (rounds == 0) { it.remove(); slotOf.remove(id); roundsOf.remove(id); expired.add(id); }
            else roundsOf.put(id, rounds - 1);
        }
        return expired;
    }
}

This isn’t thread-safe, on purpose: one thread owns the wheel, and the heartbeat-receiving threads push events to it through a queue. That’s exactly where section 5 goes. HashSet gives O(1) average removal; Netty uses a doubly linked list and cancellation marks to avoid hashing.

5. A big bucket: splitting work across threads

Key idea: when 100K devices expire in one tick, a single thread that both scans and sends alerts falls behind the next tick. Split it: the main thread only scans and pushes expired timers to a queue; several worker threads take them, re-check and send alerts.

The work per expired timer: re-check, record the state, send the alert (a Kafka or HTTP call, which is I/O). The I/O is the slowest part, so it’s worth spreading across threads.

New questions: how does the main thread hand work to the workers, and what if it pushes faster than they can process? The answer is a bounded queue in between.

flowchart LR
  P["Scanner thread (producer)"] --> Q[Queue]
  Q --> W1[Worker 1]
  Q --> W2[Worker 2]
  Q --> W3[Worker 3]

A queue shared between threads has its own problems:

  • Array: fixed size, you must decide what happens when it’s full (block the producer, i.e. backpressure).
  • Linked list: unbounded, so it can eat all memory; nodes are scattered, not CPU-cache friendly.
  • Write contention on head, tail and size: producers and consumers modify them, so you need a lock or CAS.
  • Garbage for the GC: every element is a new object that becomes garbage once processed.

Java’s ArrayBlockingQueue uses one ReentrantLock for both put and take. LinkedBlockingQueue uses two locks but allocates a node on every put. At millions of events per second, locks and GC become the bottleneck.

6. LMAX Disruptor: a lock-free queue between threads

Key idea: the Disruptor is a library for passing messages between threads inside one JVM. It uses a pre-allocated ring buffer, each side keeps its own sequence counter, and it synchronises with CAS and memory barriers instead of locks.

What makes it fast:

  • Ring buffer allocated at startup: producers overwrite the fields of an existing slot instead of creating objects, so almost no garbage.
  • Producers and consumers are decoupled: each consumer has its own sequence, and the producer only reads the slowest consumer’s sequence to know if there’s room. There’s no shared size to fight over.
  • CAS instead of locks: a single producer doesn’t even need CAS; multiple producers claim slots with CAS.
  • Memory barriers (volatile) make sure a consumer sees the data fully written before it sees the new sequence.
  • Batching: a lagging consumer can take everything from its sequence up to the latest one in one go.
  • Tunable: pick a wait strategy (busy spin, yield, blocking) to trade CPU for latency.

Numbers from LMAX’s own docs (three-stage pipeline): mean latency 52 ns versus 32,757 ns for ArrayBlockingQueue; p99 128 ns versus ~2.1 ms. Throughput for one producer and one consumer: ~160 million versus ~21 million operations per second.

Java code: a Disruptor between the scanner and the alerting workers
final class ExpiredSlot { String deviceId; long expiredAt; }   // pre-allocated slot, overwritten

Disruptor<ExpiredSlot> disruptor = new Disruptor<>(
        ExpiredSlot::new,
        1 << 16,                               // 65,536 slots, a power of 2
        Thread.ofPlatform().factory(),
        ProducerType.SINGLE,                   // only the scanner writes
        new BlockingWaitStrategy());           // saves CPU, higher latency than spinning

// 4 workers share the events (each event handled by exactly one worker)
WorkHandler<ExpiredSlot>[] workers = IntStream.range(0, 4)
        .mapToObj(i -> (WorkHandler<ExpiredSlot>) e -> alertService.send(e.deviceId, e.expiredAt))
        .toArray(WorkHandler[]::new);
disruptor.handleEventsWithWorkerPool(workers);
RingBuffer<ExpiredSlot> ring = disruptor.start();

// scanner thread
for (String id : wheel.tick()) {
    ring.publishEvent((slot, seq, dev, ts) -> { slot.deviceId = dev; slot.expiredAt = ts; }, id, now);
}

publishEvent waits when the ring is full: natural backpressure. Disruptor 4 removed WorkerPool; there you use several EventHandlers where handler i only processes events with sequence % n == i, or a BatchEventProcessor.

Two more “mechanical sympathy” details: sequences are padded so each sits on its own 64-byte cache line (avoiding false sharing, where two cores update two different variables that share a cache line and have to fight over it); and the ring buffer is a contiguous array, so CPU prefetching works well.

Foundations worth reading first: race conditions, volatile and deadlocks and ExecutorService.

7. The overall design and how to present it

Key idea: several instances receive heartbeats, and devices are routed by hash(device_id) so each device always lands on the same instance; each instance keeps its own timing wheel, persists last_seen in batches for recovery, and publishes alerts through Kafka.

flowchart LR
  D[1M devices] --> LB[Load balancer, hash by device_id]
  LB --> I1[Instance 1: timing wheel]
  LB --> I2[Instance N: timing wheel]
  I1 --> K[Kafka: device-offline]
  I2 --> K
  I1 -.->|last_seen in batches| S[(Redis / Cassandra)]
  K --> N[Notification, dashboard]

How to run it in an interview (about 45 minutes):

  1. 5 minutes: clarify requirements. Number of devices, heartbeat interval, timeouts, acceptable alert delay, whether timers must survive a restart.
  2. 5 minutes: estimate. 333K heartbeats/second, 1M timers, ~64 MB.
  3. 10 minutes: the simple option first (Redis ZSET), stating its network cost and single-key limit.
  4. 15 minutes: the timing wheel, partitioning by device, recovery after restart, a big wave of expiries and the worker queue.
  5. 5 minutes: failures and operations. An instance dies (devices move, wait one period before alerting), flaky networks (alert after 2–3 missed heartbeats), a metric for alert delay.
  6. 5 minutes: recap the three main decisions and what you’d do with more time.

Remember

  • Can you analyse a data structure with the five questions, and explain why O(1) over the network can be slower than O(log n) in RAM?
  • Can you write the Redis commands for the heartbeat and the scan job, and explain why the read-and-remove must be in Lua?
  • Can you draw a timing wheel, explain the O(1) timer reset and what hierarchical timing wheels add?
  • Do you know when the Disruptor is worth it and when ArrayBlockingQueue is enough?
  • Do you know how to recover timers after a restart and avoid false alarms during a rebalance?

Interview questions

Mid

Design the simplest possible disconnected-device detector with Redis.

One ZSET per device type, member = device_id, score = expiry time; a heartbeat is a ZADD that overwrites it, and a job every second fetches and removes members with score ≤ now in one Lua script.

ZADD is O(log n); fetching expired is O(log n + m). Cap how many you take per scan so you don’t block Redis, and shard the keys once load exceeds one node.

Why not use Redis key TTLs and keyspace notifications to detect expiry?

Because Redis expires keys lazily and by random sampling, so the expired event can arrive noticeably late, and notifications are fire-and-forget pub/sub: a disconnected subscriber loses events.

If you need guarantees, use a structure you can scan (a ZSET) or timers inside your own service.

What is a timing wheel, and why does a timer reset cost only O(1)?

A circular array of buckets, each holding the timers that expire at that tick; a reset looks up the old timer in a map, unlinks it from its bucket and links it into bucket (cursor + timeout) mod size.

Each tick scans only one bucket. The price is that precision is rounded to one tick.

Senior

A timing wheel doesn’t suit long timers. How do you handle them?

Use hierarchical timing wheels: several wheels with different ticks (seconds, minutes, hours); far-off timers sit on a coarse wheel and move down to finer ones as they get close.

Kafka does this for its purgatory. The alternative is counting remaining rounds on one wheel, but every pass of the hand then walks timers that aren’t due.

Is 333K heartbeats per second into a Redis ZSET okay?

Not on one node; you’d have to shard the keys by hash(device_id), and every heartbeat still costs a network round trip.

At this load, an in-memory timing wheel inside the service itself (devices routed by hash) is much cheaper; you just add batched last_seen persistence for recovery.

Why is the LMAX Disruptor faster than ArrayBlockingQueue?

No locks (CAS and memory barriers), a pre-allocated ring buffer so almost no garbage, each side keeps its own sequence so nobody fights over a size field, and consumers read in batches.

Add padding against false sharing and a contiguous, cache-friendly array. The price: fixed size, busy-spinning burns CPU, and it only works inside one JVM.

100K devices expire in the same tick. How does your system react?

The scanner only collects timers and pushes them to a bounded queue; a worker pool sends alerts, batched and grouped by region; when the queue is full the scanner waits (backpressure) instead of blowing up memory.

A big simultaneous wave is usually an infrastructure incident (power or signal loss), so collapse it into one regional alert rather than 100K messages.

The service holding the timing wheel restarts. How do you avoid missing dead devices?

Persist each device’s last_seen to durable storage in batches, reload it on startup and set timers at last_seen + timeout, with a grace period to avoid false alarms from slightly stale data.

Route devices with consistent hashing so that adding or removing an instance only moves a fraction of them.

Useful phrases for interviews

  • “Every heartbeat is really a timer reset, so that’s the hot path I optimise for.”
  • “Big-O isn’t the whole story: an O(1) call over the network is slower than O(log n) in memory.”
  • “I’d start with a Redis sorted set keyed by device type, with the expiry time as the score.”
  • “A timing wheel gives constant-time resets at the cost of one-tick precision.”
  • “For long timeouts I’d stack wheels, the way Kafka’s purgatory does.”
  • “The wheel lives in memory, so I persist last-seen timestamps in batches for recovery.”
  • “A bounded queue between the scanner and the workers gives us backpressure.”
  • “The Disruptor only pays off when the queue itself is the bottleneck.”
  • “A wave of simultaneous expiries usually means an infrastructure incident, so I’d group the alerts.”

Notes based on the System Design course (Ronin Engineer), rewritten in my own words.