A Redis Recipe for Lists of Recency

A nifty recipe for maintaining a list by recency. For example, a list of recently viewed page ids, maintained per user.

When inserting a new entry:

# rv stands for "recently viewed"

ZADD            rv:<user_id> <epoch_timestamp> <page_id>
ZREMRANGEBYRANK rv:<user_id> 0 -<length + 1>
EXPIRE          rv:<user_id> <ttl>

When fetching the list:

ZREVRANGE       rv:<user_id> 0 -1

ZADD

We use Redis sorted sets. ZADD adds an entry into the sorted set whose value is page_id, and whose score is an epoch timestamp or some other sufficiently precise and monotonic source. If an entry with an existing page_id is added, its score is updated. This has the effect of removing the entry from the list and appending it to the front.

ZREMRANGEBYRANK

We then trim the sorted set by some specified length. This step is optional, and can be tweaked to your requirements. If performance is a concern, this command can also be run probabilistically (flip a coin, trim the set if heads).

EXPIRE

We set a TTL on the entire sorted set. This step is also optional.

ZREVRANGE

We fetch the entire sorted set in reverse order in the read path. This can be tweaked to have a limit. The ZREMRANGEBYRANK trimming can also be done in the read path instead of the write path, although this may consume a lot more space if writes are proportionately higher than reads (as it was in my case).

Each series of operations is idempotent, which is a property that can be exploited to simplify implementation. Note, however, that operations are not pair-wise commutative. An entry with a lower timestamp will override an entry with a higher timestamp.

#Memory usage

Some back of the envelope calculations:

127.0.0.1:6379> zadd test 1569230000 123123123
(integer) 1
127.0.0.1:6379> memory usage test
(integer) 69
127.0.0.1:6379> zadd test 1569230001 234234234
(integer) 1
127.0.0.1:6379> memory usage test
(integer) 81
127.0.0.1:6379> zadd mem 1569230002 345345345
(integer) 1
127.0.0.1:6379> memory usage mem
(integer) 93

Assuming a key format like rv:<9 digit user id> and a page id with 9 characters, and extrapolating from the MEMORY USAGE numbers above, a sorted set with 30 entries occupies (69-12) + (30 * 12) + 12 = 429 bytes.

This seems to correspond with my numbers in production so far (μ = 225 bytes).