Redis Top-K tracks frequent items with bounded counting space

Finding the most frequent items becomes expensive when an exact solution remembers every identity that appears. A long tail of rarely seen values consumes storage even though those values will never lead the ranking. The Top-K capability presented for Redis keeps a smaller counting structure and a retained candidate list, accepting approximation in exchange for bounded counting space.

The 2 July introduction describes an implementation based on HeavyKeeper. Its purpose differs from storing an exact score for every member of a sorted set. The application asks which items occur most frequently in a stream, and the data structure concentrates its memory on identifying those items.

I like Redis's specialized data structures because they let an application state what it needs from stored data. This addition makes the accuracy requirement part of that choice. A frequency detector used to identify candidates has different obligations from an exact ranking used to settle a score.

Small flows lose counters more readily

The HeavyKeeper research presented at USENIX ATC 2018 describes counting with exponential decay. Its motivation is finding large network flows under tight memory constraints. Small flows are removed through decay while large flows receive more protection, allowing the structure to concentrate on frequent identities.

The RedisBloom 2.0 command reference exposes the corresponding parameters. Width sets the number of counters in each array, and depth sets the number of arrays. The decay value controls the probability of reducing a counter in an occupied bucket, with the probability raised to the counter's value.

For a decay value below one, that exponent makes reduction less likely as the count grows. Collisions therefore have a different effect on a weakly represented item than on a strongly represented one. This is the mechanism behind favoring frequent items. It does not require allocating an independent permanent counter to every distinct input.

The application chooses K separately from the counting-array dimensions. K determines the number of retained top items, while width and depth govern the supporting counting structure. Increasing the desired result size and increasing the evidence available to identify that result are related decisions, but they are not the same parameter.

The command interface reports displacement

The versioned documentation gives this initialization shape:

TOPK.RESERVE frequent 50 2000 7 0.925
TOPK.ADD frequent alpha beta alpha
TOPK.QUERY frequent alpha beta
TOPK.LIST frequent

The reserve command creates a structure for up to fifty retained items with the stated array dimensions and decay setting. Adding observations updates its state. Querying asks whether particular items belong to the retained Top-K list, and listing returns the current retained candidates.

TOPK.ADD also returns an expelled item when an insertion changes the list. Otherwise its corresponding result is nil. This makes a membership change available in the same request that processes the new observation. An application need not compare two complete snapshots merely to detect that a candidate was displaced.

That return value should still be interpreted as a change in this approximate structure. It does not prove that a mathematically exact ranking changed at that instant. The distinction matters if an application turns candidate changes into notifications or further investigation. The result identifies an event in the maintained candidate list.

Estimated counts have narrower meaning

The reference documents TOPK.COUNT as returning a count that can be lower than the real count. That differs from assuming every frequency estimator has an overestimate bias. Applications have to use the semantics of this structure rather than transfer expectations from another sketch.

Membership and count also answer different questions. A retained item is a candidate in the current Top-K result. Its reported count is information obtained from the approximate counting mechanism. Neither operation reconstructs every occurrence of every identity in the original stream.

I regard that as a useful fit for narrowing a large stream to a smaller set of identities worth inspecting. An application needing exact totals for all members has a different data requirement. Keeping the original observations or an exact counter system would preserve information this structure deliberately does not retain in full.

Frequency is different from an arbitrary score

The introduction compares Top-K with a sorted-set approach that increments members as observations arrive. That comparison concerns frequency tracking. It should not imply that any leaderboard with arbitrary scoring rules can replace its exact scores with a stream-frequency sketch.

A score may decrease, represent an external total or reflect rules unrelated to occurrence count. The documented Top-K operations add observations and estimate their frequencies. Selecting the structure therefore requires matching the meaning of an input event to the meaning of the desired ranking.

The module's bounded counting arrays make the storage decision explicit before ingestion. The retained candidate list supplies identities, and the add-command results identify displacement as observations arrive. Those operations give a frequency-oriented application a defined interface for maintaining and inspecting a small candidate set while avoiding an exact counter for every identity in the input.