ebuckets

A bucketed, time-ordered structure for storing TTL entries. The backbone of Redis's expiration store.

Source layout

File	Role
src/ebuckets.c	Implementation (~104 KB).
src/ebuckets.h	Public API and types.

Why bucketing

Expiration is a "find me everything with expire <= now" problem. Three classic approaches:

• Per-key sorted set / heap. O(log N) insert/delete, O(log N) per pop. Memory-heavy because each entry needs heap pointers.
• Hash table + cron sample. O(1) operations but no fast way to find expired entries; the cron has to sample.
• Bucketing by time range. O(1) insert into the right bucket; O(items in bucket) sweep when the bucket's time has passed.

Redis uses the third option. Buckets correspond to time ranges (powers of 2 milliseconds). Each bucket is a small list/dict of keys whose expiration falls within the range. When the bucket's latest time is past now, every entry in it is expired and ready to be deleted; the active-expiration cron scans buckets in time order.

Bucket layout

The structure is hierarchical: top-level buckets cover wide ranges; each bucket holds a sub-rax (or a small flat list) of entries within the range. The boundaries are powers of two from millisecond resolution upward. A configurable EB_BUCKET_KEY_PRECISION parameter trades absolute precision for cheaper bucket boundaries.

graph TD
    Root[ebuckets root rax] --> B1[bucket: ms 0-1023]
    Root --> B2[bucket: ms 1024-2047]
    Root --> B3[bucket: ms 2048-3071]
    B1 --> E11[item: foo expire=999]
    B1 --> E12[item: bar expire=1015]
    B2 --> E21[item: baz expire=1500]

When now is 1100, bucket B1 is fully past its range and can be drained — every entry is definitely expired. Bucket B2 is partially past its range; entries with expire ≤ now are evicted, others stay.

API

typedef struct ebuckets ebuckets;        /* opaque */
typedef struct EBucketsType {
    uint64_t (*getExpireMeta)(const eItem item);
    /* ... callbacks for sizing, freeing, callbacks ... */
} EBucketsType;

ebuckets *ebCreate(EBucketsType *type);
int  ebAdd(ebuckets *eb, const eItem item, uint64_t expire);
int  ebRemove(ebuckets *eb, const eItem item);
int  ebExpire(ebuckets *eb, uint64_t now, ebExpireCallback cb, void *cbctx);
size_t ebSize(const ebuckets *eb);

ebExpire is the main entry point. It walks buckets in time order, calls the user-supplied callback for each expired item (which deletes the key from the keyspace and emits the keyspace notification), and stops when it has spent its time budget or hit a non-expired item.

The EBucketsType lets the same ebuckets implementation back different kinds of expiring objects — full keys (the dataset's expiration store), hash fields (per-field TTL), and module-defined types.

Use in Redis

Use site	Source
Per-DB key expiration	src/estore.c wraps an ebuckets per redisDb.
Per-hash field expiration	src/keymeta.c + src/t_hash.c use ebuckets to track per-field TTLs efficiently.
Module-defined expiration	Modules can register their own expiration callbacks via the API.

Active expiration

activeExpireCycle (in src/expire.c) calls ebExpire with a time budget derived from active-expire-effort. The callback handles each expired entry — for a key, it deletes the key, emits the expired notification, and propagates a DEL to AOF/replicas. For a hash field, it deletes the field and updates the per-key minimum TTL.

Embedded tests

There is a self-test in #ifdef REDIS_TEST that adds a large number of entries with random TTLs and verifies that ebExpire produces them in time order and respects boundaries.

Related pages

• Expiration — the user-facing semantics.
• Memory management — eviction / lazy free interplay.