Learn more about Russian war crimes in Ukraine.

How is the Redis sorted set implemented?

Redis provides a data structure called “sorted sets” which are,

... similarly to Redis Sets, non repeating collections of Strings. The difference is that every member of a Sorted Set is associated with a score, that is used in order to take the sorted set ordered, from the smallest to the greatest score. While members are unique, scores may be repeated.

I was curious what data structure Redis sorted sets used, since they allow efficient ordering of the set members on two different orderings: lexicographically, and by associated score.

Looking at the source, we find that there is no fundamentally new data structure; only two old ones: a hash table and a skip list.

ZSETs are ordered sets using two data structures to hold the same elements in order to get O(log(N)) INSERT and REMOVE operations into a sorted data structure. The elements are added to a hash table mapping Redis objects to scores. At the same time the elements are added to a skip list mapping scores to Redis objects (so objects are sorted by scores in this “view”).

In Redis, the keys are strings and the values are integers, but this “sorted set” abstraction can be generalized to any key and value types with orderings. In Haskell, we can implement:

-- Constructors
zempty :: ZSet k v
zadd   :: (Ord k, Ord v) => k -> v -> ZSet k v -> ZSet k v
zrem   :: (Ord k, Ord v) => k      -> ZSet k v -> ZSet k v

-- The two orderings
zrangebylex   :: ZSet k v -> [(k, v)]  -- retrieve ordered by k
zrangebyscore :: ZSet k v -> [(k, v)]  -- retrieve ordered by v

The implementation works by maintaining the ordinary forward map, Map k v, plus a reverse map, Map v (Set k). In Redis, the forward map is a hash table, and the reverse map is a skip list. In Haskell, here’s the implementation:

data ZSet k v = ZSet {
  scores  :: Map k v,
  byScore :: Map v (Set k)
} deriving (Show)

type MultiMap k v = Map.Map k (Set v)

zempty :: ZSet k v
zempty = ZSet Map.empty Map.empty

zadd :: (Ord k, Ord v) => k -> v -> ZSet k v -> ZSet k v
zadd x newScore z = ZSet (Map.insert x newScore (scores z)) newByScore where
  newByScore = Map.alter (Just . maybe (Set.singleton x) (Set.insert x)) newScore oldScoreRemoved
  oldScoreRemoved = maybe (byScore z) (\oldScore -> multiMapDelete oldScore x (byScore z)) (Map.lookup x (scores z))

zrem :: (Ord k, Ord v) => k -> ZSet k v -> ZSet k v
zrem x z = case Map.lookup x (scores z) of
  Nothing -> z
  Just oldScore -> ZSet (Map.delete x (scores z)) (multiMapDelete oldScore x (byScore z))

zrangebylex :: ZSet k v -> [(k, v)]
zrangebylex z = Map.toAscList $ scores z

zrangebyscore :: ZSet k v -> [(k, v)]
zrangebyscore = concatMap flattenScore . Map.toAscList . byScore where
  flattenScore (score, xs) = Prelude.map (\x -> (x, score)) $ Set.toAscList xs

multiMapDelete :: (Ord k, Ord v) => k -> v -> Map k (Set v) -> Map k (Set v)
multiMapDelete k v m = Map.alter f k m where
  f Nothing = Nothing
  f (Just vs) = let vs' = Set.delete v vs
                in if Set.null vs' then Nothing else Just vs'

What can computers do? What are the limits of mathematics? And just how busy can a busy beaver be? This year, I’m writing Busy Beavers, a unique interactive book on computability theory. You and I will take a practical and modern approach to answering these questions — or at least learning why some questions are unanswerable!

It’s only $19, and you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

After months of secret toil, I and Andrew Carr released Everyday Data Science, a unique interactive online course! You’ll make the perfect glass of lemonade using Thompson sampling. You’ll lose weight with differential equations. And you might just qualify for the Olympics with a bit of statistics!

It’s $29, but you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

More by Jim

Tagged #programming. All content copyright James Fisher 2018. This post is not associated with my employer. Found an error? Edit this page.