Posted on by & filed under Content - Highlights and Reviews, Programming & Development.

A guest post by Josiah Carlson who has worked for Google, and then later for Adly, where he first learned about and began using Redis for content-targeting advertising and Twitter analytics platforms. Josiah is the author of Redis in Action by Manning Publications.

Every week someone on the Redis mailing list has a new and interesting problem to solve, and, for someone who loves to solve problems, the list has been a continuous source of entertainment. This week’s problem comes courtesy of Aleš Kafka, who asked about expiring groups of keys simultaneously. In this post, I’ll cover what was asked and two ways of solving the problem. As we progress, I will be providing source code in Python and Lua (you can look at all of the code all at once here).

On the mailing list, Aleš asked whether there was a method for having a group of keys expire at the same time and to having that expiration delayed as necessary. With each user logged into his site, there are a few different types of data stored in Redis; perhaps a list or two, a SET, and a HASH, but he didn’t want to have to manually call EXPIRE on all of the different keys whenever he needs to update the expiration time for a user’s data.

The solution that doesn’t count

In the problem description, you have just read about one possible method—calling EXPIRE on all of the keys related to a given user. While that will work, it may require making several times, as many EXPIRE calls as data update calls for any given update. To be specific, say that a user has 10 keys of data related to them; even updating 1 piece of data in one of those keys would require 10 EXPIRE calls to defer expiration of all of the keys. The code for doing this in Python can be seen below (there is some Python trickery going on; you’ll have to visit to see what is going on with the KeyDiscoveryPipeline base class).

As mentioned earlier, because this requires calling EXPIRE on all known keys related to the user, this can be slow even when only a small amount of data is being updated. Because this is wasteful, we’re not even going to count it as one of the three solutions. Really, we need a method where when updating n pieces of data in Redis for a user; there are at most 2n + 1 calls to handle data updates and expiration.

Our first solution

This first solution comes right from Aleš himself—create a SET that includes all of the known keys associated with a given user, and modify the EXPIRE and underlying DEL functionality within Redis to be able to flag and recognize when one of these special SETs have expired.

By doing this, and with a little work on the way expiration is performed, any update to a user’s data would require updating the data, adding the key to the SET for that user, and calling an updated “EXPIRE <key> <timeout> <flag>” (where the flag would say “this SET contains other keys that should be removed”). That gets us the 2n+1 calls we were looking for, but requires modifying Redis’ source code and maintaining a fork of Redis. While updating Redis itself might not be too bad, maintaining a fork of Redis can be a pain (I’ve done it before). That said, building it on the Python side isn’t too bad, which you can see below.

As mentioned before, not only do we need to use client-side code similar to the above, but we’d need to modify Redis itself. We can do better.

Using Lua

With the release of Redis 2.6, Redis has supported Lua scripting from within Redis itself. We can use this functionality along with a slightly altered version of our previous solution to remove the need to alter Redis.

When updating any data, we again add the key for the updated data to a SET that is named based on the user’s id. After updating all of the data for any group of updates, we also add the user id to a ZSET as a member, with the score being the current Unix timestamp. This can be seen below.

To expire data, we merely need to write a Lua script to look at the ZSET for any user that hasn’t been seen within our cutoff, fetch the keys with a quick call to SMEMBERS, then delete all the keys and remove the entry from the ZSET. The Lua script can loop over this or just return whether any work had been done so the caller can make another call. This latter version can be seen below.


This addresses all of our earlier concerns about updating data and expiration, offering the desired at-most 2n+1 calls for n data updates. But the drawback with this method is that if you have to update the ZSET with every data update, and your expiration ZSET is large, you might end up in a situation where the O(log(n)) update time for the ZSET is too much. There is a bonus answer to reduce the number of ZSET updates in the source code available at from Aleš.

See below for some Redis resources from Safari Books Online.

Read these titles on Safari Books Online

Not a subscriber? Sign up for a free trial.

Redis in Action introduces Redis and walks you through examples that demonstrate how to use it effectively. You’ll begin by getting Redis set up properly and then exploring the key-value model. Then, you’ll dive into real use cases including simple caching, distributed ad targeting, and more. You’ll learn how to scale Redis from small jobs to massive datasets. Experienced developers will appreciate chapters on clustering and internal scripting to make Redis easier to use.
Redis Cookbook will provide developers with problem and solutions in our useful cookbook style. This is an example-driven book.
Instant Redis Optimization How-to will show you how to make the most of Redis. Using real-world examples of Redis as a caching and queuing service, you will learn how to install and calibrate Redis to optimize memory usage, read and write speed, as well as bulk writes and transactions. If you want to use Redis for its blazing fast capabilities, then this book is for you.

About the author

josiah Josiah Carlson has worked for Google, and then later for Adly, where he first learned about and began using Redis for content-targeting advertising and Twitter analytics platforms, before being a regular participant on the Redis mailing list, where he answers hundreds of questions about using and configuring Redis. Josiah is the author of Redis in Action by Manning Publications.

Tags: Aleš Kafka, expiring groups of keys, keys, Lua, Python, Redis, Redis in Action,

Comments are closed.