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
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.
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).
We set a TTL on the entire sorted set. This step is also optional.
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.
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).