Unlocking Redis Streams: How Radix Tree & Listpack Power Modern MQs

What is Redis Stream?

Redis Stream, introduced in Redis 5.0, is a native data type designed for message‑queue use cases. It adopts Kafka‑style consumer groups, provides persistence and master‑slave replication, and records each client’s read position to guarantee no message loss.

Storage is based on a Radix Tree (compact prefix tree) and listpack structures.

Message IDs are generated automatically and are monotonically increasing.

Consumer groups enable parallel, non‑duplicate consumption of the same stream.

Supports multicast, blocking and non‑blocking reads.

ACK mechanism ensures at‑least‑once delivery.

Configurable MAXLEN trims old entries to control memory usage.

Core concepts and terminology

Each stream is identified by a unique key. The first XADD creates the stream automatically. Consumer Group: a logical group where multiple consumers compete for messages; groups are independent. *pel (Pending Entries List): tracks messages read by a client but not yet ACKed, enabling the ACK mechanism.

Stream internal structure

The C definition lives in stream.h:

typedef struct stream {
    rax *rax;
    uint64_t length;
    streamID last_id;
    streamID first_id;
    streamID max_deleted_entry_id;
    uint64_t entries_added;
    rax *cgroups;
} stream;

typedef struct streamID {
    uint64_t ms;
    uint64_t seq;
} streamID;

*rax

: pointer to a Radix Tree where keys are message IDs and values point to a listpack containing the actual messages. length: total number of entries in the stream. last_id / first_id: IDs of the newest and oldest entries. entries_added: total messages ever added (including deleted ones). *cgroups: Radix Tree mapping consumer‑group names to their metadata.

Consumer group structure

typedef struct streamCG {
    streamID last_id;
    long long entries_read;
    rax *pel;
    rax *consumers;
} streamCG;

last_id

: last ID read but not yet ACKed by the group. *pel: pending entries list (radix tree) storing un‑ACKed messages. *consumers: radix tree of all consumers in the group.

Pending entry (streamNACK)

typedef struct streamNACK {
    mstime_t delivery_time;
    uint64_t delivery_count;
    streamConsumer *consumer;
} streamNACK;

delivery_time

: timestamp of the last delivery attempt. delivery_count: how many times the message was delivered. *consumer: pointer to the consumer that received the message.

Consumer representation (streamConsumer)

typedef struct streamConsumer {
    mstime_t seen_time;
    sds name;
    rax *pel;
} streamConsumer;

seen_time

: last time the consumer was active. name: consumer identifier. *pel: pending entries list specific to this consumer (shares the same streamNACK objects as the group’s *pel).

Inserting messages with XADD

Command syntax: XADD key id field value [field value ...] Example inserting book‑order events into a stream named hotlist:books:

> XADD hotlist:books * payerID 1 amount 69.00 orderID 9
1679218539571-0
> XADD hotlist:books * payerID 1 amount 36.00 orderID 15
1679218572182-0
> XADD hotlist:books * payerID 2 amount 99.00 orderID 88
1679218588426-0
> XADD hotlist:books * payerID 3 amount 68.00 orderID 80
1679218604492-0

The asterisk tells Redis to generate a unique ID composed of a millisecond timestamp and a sequence number, ensuring monotonic ordering and making the stream an append‑only structure.

Radix tree fundamentals

A Radix (or Compact Prefix) Tree stores strings by sharing common prefixes, reducing memory compared to hash tables. Redis uses a compact variant where nodes may store multiple characters.

Radix node definition

typedef struct raxNode {
    uint32_t iskey:1;
    uint32_t isnull:1;
    uint32_t iscompr:1;
    uint32_t size:29;
    unsigned char data[];
} raxNode;

iskey

: 1 if the path to this node forms a complete key. isnull: 1 if the node is empty (no value pointer needed). iscompr: 1 if the node is a compressed node. size: length of the compressed string or number of child pointers. data: actual stored bytes; for leaf nodes it points to a listpack holding the message payload.

Because the radix tree shares prefixes, streams with many sequential IDs consume far less memory than a naïve hash‑table implementation.

Q: Why does Redis use Radix Tree + listpack instead of a hash table for storing stream messages? A: The radix tree shares common prefixes of message IDs, while the listpack stores multiple messages compactly. This combination dramatically reduces memory overhead compared to storing each message ID as a separate hash key.