A Redis Recipe for Lists of Recency

October 17, 2019

A nifty recipe for main­tain­ing a list by recen­cy. For exam­ple, a list of recent­ly viewed page ids, main­tained per user.

When insert­ing 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 fetch­ing the list:

ZREVRANGE       rv:<user_id> 0 -1

ZADD

We use Redis sorted sets. ZADD adds an an entry into the sorted set whose value is page_id, and whose score is an epoch time­stamp or some other suf­fi­cient­ly pre­cise and monot­o­n­ic source. If an entry with an exist­ing page_id is added, its score is updat­ed. This has the effect of remov­ing the entry from the list and append­ing it to the front.

ZREMRANGEBYRANK

We then trim the sorted set by some spec­i­fied length. This step is option­al, and can be tweaked to your require­ments. If per­for­mance is a con­cern, this com­mand can also be run prob­a­bilis­ti­cal­ly (flip a coin, trim the set if heads).

EXPIRE

We set a TTL on the entire sorted set. This step is also option­al.

ZREVRANGE

We fetch the entire sorted set in reverse order in the read path. This can be tweaked to have a limit. The ZREMRANGEBYRANK trim­ming can also be done in the read path instead of the write path, although this may con­sume a lot more space if writes are pro­por­tion­ate­ly higher than reads (as it was in my case).


Each series of oper­a­tions is idem­po­tent, which is a prop­er­ty that can be exploit­ed to sim­pli­fy imple­men­ta­tion. Note, how­ev­er, that oper­a­tions are not pair-wise com­mu­ta­tive. An entry with a lower time­stamp will over­ride an entry with a higher time­stamp.

Memory usage

Some back of the enve­lope cal­cu­la­tions:

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

Assum­ing a key format like rv:<9 digit user id> and a page id with 9 char­ac­ters, and extrap­o­lat­ing from the MEMORY USAGE num­bers above, a sorted set with 30 entries occu­pies (69-12) + (30 * 12) + 12 = 429 bytes.

This seems to cor­re­spond with my num­bers in pro­duc­tion so far (μ = 225 bytes).