→ SORT in Redis

20 October 2009

Now that Hurl is open source I thought I'd talk a bit about one of my favorite open source projects: Redis.

In Hurl we keep track of all the hurls you make, then show them to you on the "your hurls" page:

Your Hurls

One of the more fun features is the re-ordering of your Hurls. If I click on the Twitter URL then hit 'Send,' I can re-issue the request and see the new response. The next time I visit the "your hurls" page, the Twitter URL will have moved to the top of my list:

Your Hurls

This is probably pretty trivial in a SQL database, but Hurl uses Redis - a key/value database. How do we do this kind of sorting?

First let's talk about the three key/value types involved.

Hurls

A Hurl (in Redis) is a JSON object describing an HTTP request. Its key is the SHA1 of its value. This is convenient because it means we won't store duplicate values - we use Redis' SETNX command to only save the value if its key doesn't already exist - and probably won't get collisions.

Let's look at one of my Hurls:

$ redis-cli get da0838427e5fef02921ca2346f59480da2e9e5d9
{
    "auth": "none",
    "id": "da0838427e5fef02921ca2346f59480da2e9e5d9",
    "method": "GET",
    "url": "http://github.com/api/v2/json/user/show/defunkt"
}

Notice we store the id with the object. We simply compute the SHA before saving then stick it in the object - this is real handy for generating links and whatnot later on, after pulling the object from the db.

Your Hurls

Each user has a SET of SHAs which correspond to Hurls she has made. For example, here's mine (I'm user #59):

$ redis-cli smembers Hurl::User:v1:59:hurls
1. da0838427e5fef02921ca2346f59480da2e9e5d9
2. eebb1e7782d0eefb5e4a82c6ee6a3779497a8d14
3. 0efea52740ebf7c388884461bda6b4a4198c4fa2
4. 59de6e57bda2a07505987a8fa40317a535e769e3

If you and I both query "google.com," we'll both share a SHA in our Hurls list. And that's okay.

Recently Visited Hurls

Each time you make a Hurl request we store the timestamp. This is important for the sorting.

The timestamp is stored as a basic key/value pair. Here's one of mine:

$ redis-cli get Hurl::User:v1:59:hurls:da0838427e5fef02921ca2346f59480da2e9e5d9
1256015372

Simple Unix epoch format. The next time I hit "send" on that Hurl the timestamp will be updated.

Sorting

Now that we have all those pieces in place, sorting is cake. You can see the sort call we use in lines 53-57 of user.rb. Here's an expanded version of it:

hurls = redis.sort "Hurl::User:v1:59:hurls",
  :by    => "Hurl::User:v1:59:hurls:*",
  :get   => "*",
  :order => 'DESC',
  :limit => { :start => 0, :limit => 100 }

We're telling Redis to grab each member of SET Hurl::User:v1:59:hurls then find the corresponding timestamp value at key Hurl::User:v1:59:hurls:* (where * is replaced with the sha) then order the SET by those timestamps. Once it has the ordered list of shas, use each one as a key (again replacing the * with the sha) and return the values. Descending, first 100.

What we end up with is a sorted list of Hurl objects. Beautiful!

Here it is in Ruby pseudocode:

shas = {}

# Find each sha and its timestamp
redis.smembers("Hurl::User:v1:59:hurls").each do |sha|
 shas[sha] = redis.get("Hurl::User:v1:59:hurls:#{sha}")
end

# Sort the shas by their timestamp
shas.sort_by! { |sha, timestamp| -timestamp }

# Return a list of all the Hurls
hurls = shas.map do |sha, timestamp|
  redis.get(sha)
end

That's a wrap

I had a big "a-ha" moment when I finally figured out Redis' SORT. Not because it's complicated, nor because it uses concepts that were entirely new to me, nor because it's fast. No, the a-ha moment was when I realized how damned simple it was.

And not only is Redis' SORT simple - it made my app simpler, too. Just check out the first commit where we introduced SORT. We were able to cut out my complicated, hacky implementation using Redis' LIST type and replace it with something elegant.

Why do I think the SORT implementation in Hurl is elegant? Because it's calling into Redis, using existing features, and not re-implementing features (poorly) in app-land.

Always a win.