Concurrent Servers Part 5 - Redis case study

This is part 5 in a series of posts on writing concurrent network servers. After discussing techniques for constructing concurrent servers in parts 1-4, this time we're going to do a case study of an existing production-quality server - Redis.

Redis logo

Redis is a fascinating project and I've been following it with interest for a while now. One of the things I admire most about Redis is the clarity of its C source code. It also happens to be a great example of a high-performance concurrent in-memory database server, so the opportunity to use it as a case study for this series was too good to ignore.

Let's see how the ideas discussed in parts 1-4 apply to a real-world application.

All posts in the series:

Event-handling library

One of Redis's main claims to fame around the time of its original release in 2009 was its speed - the sheer number of concurrent client connections the server could handle. It was especially notable that Redis did this all in a single thread, without any complex locking and synchronization schemes on the data stored in memory.

This feat was achieved by Redis's own implementation of an event-driven library which is wrapping the fastest event loop available on a system (epoll for Linux, kqueue for BSD and so on). This library is called ae. ae makes it possible to write a fast server as long as none of the internals are blocking, which Redis goes to great lengths to guarantee [1].

What mainly interests us here is ae's support of file events - registering callbacks to be invoked when file descriptors (like network sockets) have something interesting pending. Like libuv, ae supports multiple event loops and - having read parts 3 and 4 in this series - the signature of aeCreateFileEvent shouldn't be surprising:

int aeCreateFileEvent(aeEventLoop *eventLoop, int fd, int mask,
                      aeFileProc *proc, void *clientData);

It registers a callback (proc) for new file events on fd, with the given event loop. When using epoll, it will call epoll_ctl to add an event on the file descriptor (either EPOLLIN, EPOLLOUT or both, depending on the mask parameter). ae's aeProcessEvents is the "run the event loop and dispatch callbacks" function, and it calls epoll_wait under the hood.

Handling client requests

Let's trace through the Redis server code to see how ae is used to register callbacks for client events. initServer starts it by registering a callback for read events on the socket(s) being listened to, by calling aeCreateFileEvent with the callback acceptTcpHandler. This callback is invoked when new client connections are available. It calls accept [2] and then acceptCommonHandler, which in turn calls createClient to initialize the data structures required to track a new client connection.

createClient's job is to start listening for data coming in from the client. It sets the socket to non-blocking mode (a key ingredient in an asynchronous event loop) and registers another file event callback with aeCreateFileEvent - for read events - readQueryFromClient. This function will be invoked by the event loop every time the client sends some data.

readQueryFromClient does just what we'd expect - parses the client's command and acts on it by querying and/or manipulating data and sending a reply back. Since the client socket is non-blocking, this function has to be able to handle EAGAIN, as well as partial data; data read from the client is accumulated in a client-specific buffer, and the full query may be split across multiple invocations of the callback.

Sending data back to clients

In the previous paragraph I said that readQueryFromClient ends up sending replies back to clients. This is logically true, because readQueryFromClient prepares the reply to be sent, but it doesn't actually do the physical sending - since there's no guarantee the client socket is ready for writing/sending data. We have to use the event loop machinery for that.

The way Redis does this is by registering a beforeSleep function to be called every time the event loop is about to go sleeping waiting for sockets to become available for reading/writing. One of the things beforeSleep does is call handleClientsWithPendingWrites. This function tries to send all available replies immediately by calling writeToClient; if some of the sockets are unavailable, it registers an event-loop callback to invoke sendReplyToClient when the socket is ready. This can be seen as a kind of optimization - if the socket is immediately ready for sending (which often is the case for TCP sockets), there's no need to register the event - just send the data. Since sockets are non-blocking, this never actually blocks the loop.

Why does Redis roll its own event library?

In part 4 we've discussed building asynchronous concurrent servers using libuv. It's interesting to ponder the fact that Redis doesn't use libuv, or any similar event library, and instead implements its own - ae, including wrappers for epoll, kqueue and select. In fact, antirez (Redis's creator) answered precisely this question in a blog post in 2011. The gist of his answer: ae is ~770 lines of code he intimately understands; libuv is huge, without providing additional functionality Redis needs.

Today, ae has grown to ~1300 lines, which is still trivial compared to libuv's 26K (this is without Windows, test, samples, docs). libuv is a far more general library, which makes it more complex and more difficult to adapt to the particular needs of another project; ae, on the other hand, was designed for Redis, co-evolved with Redis and contains only what Redis needs.

This is another great example of the dependencies in software projects formula I mentioned in a post earlier this year:

The benefit of dependencies is inversely proportional to the amount of effort spent on a software project.

antirez referred to this, to some extent, in his post. He mentioned that dependencies that provide a lot of added value ("foundational" dependencies in my post) make more sense (jemalloc and Lua are his examples) than dependencies like libuv, whose functionality is fairly easy to implement for the particular needs of Redis.

Multi-threading in Redis

For the vast majority of its history, Redis has been a purely single-threaded affair. Some people find this surprising, but it makes total sense with a bit of thought. Redis is inherently network-bound - as long as the database size is reasonable, for any given client request, much more time is spent waiting on the network than inside Redis's data structures.

These days, however, things are not quite that simple. There are several new capabilities in Redis that use threads:

  1. "Lazy" freeing of memory.
  2. Writing a persistence journal with fsync calls in a background thread.
  3. Running user-defined modules that need to perform a long-running operation.

For the first two features, Redis uses its own simple bio library (the acronym stands for "Background I/O"). The library is hard-coded for Redis's needs and can't be used outside it - it runs a pre-set number of threads, one per background job type Redis needs.

For the third feature, Redis modules could define new Redis commands, and thus are held to the same standards as regular Redis commands, including not blocking the main thread. If a custom Redis command defined in a module wants to perform a long-running operation, it has to spin up a thread to run it in the background. src/modules/helloblock.c in the Redis tree provides an example.

With these features, Redis combines an event loop with threading to get both speed in the common case and flexibility in the general case, similarly to the work queue discussion in part 4 of this series.

[1]A core aspect of Redis is its being an in-memory database; therefore, queries should never take too long to execute. There are all kinds of complications, however. In case of partitioning, a server may end up routing the request to another instance; in this case async I/O is used to avoid blocking other clients.
[2]Through anetAccept; anet is Redis's wrapper for TCP socket code.

Book review: "Programming in Haskell" by Graham Hutton (2nd ed.)

It's hard not to run into Graham Hutton's work when reading about functional programming, so reading a book on Haskell written by him sounded like a good opportunity to learn from a real expert. It turned out to be a good choice - this is definitely the best Haskell book I read so far.

The author's deep understanding of functional programming concepts and Haskell shines through the writing on many occasions. He carefully sets up explanations and examples that build one on top of another, and manages to explain some of the thorniest ideas of Haskell (applicatives and monads, I'm looking at you) very clearly; most importantly, the why of things is often explained, along with some important historical background that sheds some light on the design choices made by the language.

There's even space in this book for a few extended programming examples and exercises, both of which are very important for a programming book. Some of the exercises come with solutions in an appendix - a truly impressive information density for a ~250 page book.

My favorite chapter is Monadic Parsers; parser combinators is a very interesting topic, and I went through several resources that tried to explain it in Haskell. The treatment in this book is much better than anything I read before (it even inspired a blog post to document my understanding).

On the flip side, the last two chapters - on automatically proving programs correct, as well as deriving correct programs from definitions - were puzzling. Felt too academic and somewhat out of place in a book teaching a programming language. I suppose that when you write a book, it's your prerogative to include some of the research topics you're excited about and pitch them to a more general audience :-)

It's hard to resist comparing this book to Learn You a Haskell (LYAH), which is based on the false premise that complete beginners want or need to learn Haskell (IMHO they don't). I would guess that most folks coming to Haskell have some programming experience in other languages and are looking to expand their horizons and get some functional and static typing enlightment. Programming in Haskell is exactly the book these programmers need to read.

Deciphering Haskell's applicative and monadic parsers

This post follows the construction of parsers described in Graham Hutton's "Programming in Haskell" (2nd edition). It's my attempt to work through chapter 13 in this book and understand the details of applicative and monadic combination of parsers presented therein.

Basic definitions for the Parser type

A parser parameterized on some type a is:

newtype Parser a = P (String -> [(a,String)])

It's a function taking a String and returning a list of (a,String) pairs, where a is a value of the parameterized type and String is (by convention) the unparsed remainder of the input. The returned list is potentially empty, which signals a failure in parsing [1]. It might have made more sense to define Parser as a type alias for the function, but types can't be made into instances of typeclasses; therefore, we use netwype with a dummy constructor named P.

With this Parser type, the act of actually parsing a string is expressed with the following helper function. It's not strictly necessary, but it helps make code cleaner by hiding P from users of the parser.

parse :: Parser a -> String -> [(a,String)]
parse (P p) inp = p inp

The most basic parsing primitive plucks off the first character from a given string:

item :: Parser Char
item = P (\inp -> case inp of
                    []      -> []
                    (x:xs)  -> [(x,xs)])

Here's how it works in practice:

> parse item "foo"
> parse item "f"
> parse item ""

Parser as a Functor

We'll start by making Parser an instance of Functor:

instance Functor Parser where
  -- fmap :: (a -> b) -> Parser a -> Parser b
  fmap g p = P (\inp -> case parse p inp of
                          []        -> []
                          [(v,out)] -> [(g v,out)])

With fmap we can create a new parser from an existing parser, with a function applied to the parser's output. For example:

> parse (fmap toUpper item) "foo"
> parse (fmap toUpper item) ""

Let's check that the functor laws work for this definition. The first law:

fmap id = id

Is fairly obvious when we substitute id for g in the definition of fmap. We get:

fmap id p = P (\inp -> case parse p inp of
                        []        -> []
                        [(v,out)] -> [(id v,out)])

Which takes the parse result of p and passes it through without modification. In other words, it's equivalent to p itself, and hence the first law holds.

Verifying the second law:

fmap (g . h) = fmap g . fmap h

... is similarly straightforward and is left as an exercise to the reader.

While it's not obvious why a Functor instance for Parser is useful in its own right, it's actually required to make Parser into an Applicative, and also when combining parsers using applicative style.

Parser as an Applicative

Consider parsing conditional expressions in a fictional language:

if <expr> then <expr> else <expr>

To parse such expressions we'd like to say:

  • Parse the token if
  • Parse an <expr>
  • Parse the token then
  • Parse an <expr>
  • Parse the token else
  • Parse an <expr>
  • If all of this was successful, combine all the parsed expressions into some sort of result, like an AST node.

Such sequences, along with alternation (an expression is either this or that) are two of the critical basic blocks of constructing non-trivial parsers. Let's see a popular way to accomplish this in Haskell (for a complete example demonstrating how to construct a parser for this particular conditional expression, see the last section in this post).

Parser combinators is a popular technique for constructing complex parsers from simpler parsers, by means of higher-order functions. In Haskell, one of the ways in which parsers can be elegantly combined is using applicative style. Here's the Applicative instance for Parser.

instance Applicative Parser where
  -- pure :: a -> Parser a
  pure v = P (\inp -> [(v,inp)])

  -- <*> :: Parser (a -> b) -> Parser a -> Parser b
  pg <*> px = P (\inp -> case parse pg inp of
                            []        -> []
                            [(g,out)] -> parse (fmap g px) out)

Recall how we created a parser that applied toUpper to its result using fmap? We can now do the same in applicative style:

> parse (pure toUpper <*> item) "foo"

Let's see why this works. While not too exciting on its own, this application of a single-argument function is a good segue to more complicated use cases.

Looking at the Applicative instance, pure toUpper translates to P (\inp -> [(toUpper,inp)] - a parser that passes its input through unchanged, returning toUpper as a result. Now, substituting item into the definition of <*> we get:

pg <*> item = P (\inp -> case parse pg inp of
                            []        -> []
                            [(g,out)] -> parse (fmap g item) out)

... pg is (pure toUpper), the parsing of which always succeeds, returning

pg <*> item = P (\inp -> parse (fmap toUpper item) inp)

In other words, this is exactly the example we had for Functor by fmap-ing toUpper onto item.

The more interesting case is applying functions with multiple parameters. Here's how we define a parser that parses three items from the input, dropping the middle result:

dropMiddle :: Parser (Char,Char)
dropMiddle =
  pure selector <*> item <*> item <*> item
  where selector x y z = (x,z)

Following the application of nested <*> operators is tricky because it builds a run-time chain of functions referring to other functions. This chain is only collapsed when the parser is used to actually parse some input, so it is necessary to keep a lot of context "on the fly". To better understand how this works, we can break the definition of dropMiddle into parts as follows (since <*> is left-associative):

dropMiddle =
  ((pure selector <*> item) <*> item) <*> item
  where selector x y z = (x,z)

Applying the first <*>:

pg <*> item = P (\inp -> case parse pg inp of
                            []        -> []
                            [(g,out)] -> parse (fmap g item) out)

... pg is (pure selector), the parsing of which always succeeds, returning

pg <*> item = P (\inp -> parse (fmap selector item) inp)  --= app1

Let's call this parser app1 and apply the second <*> in the sequence.

app1 <*> item = P (\inp -> case parse app1 inp of
                            []        -> []
                            [(g,out)] -> parse (fmap g item) out)  --= app2

We'll call this app2 and move on. Similarly, applying the third <*> in the sequence produces:

app2 <*> item = P (\inp -> case parse app2 inp of
                            []        -> []
                            [(g,out)] -> parse (fmap g item) out)

This is dropMiddle. It's a chain of parsers expressed as a compbination of higher-order functions (closures, actually).

To see how this combined parser actually parses input, let's trace through the execution of:

> parse dropMiddle "pumpkin"

dropMiddle is app2 <*> item, so we have:

-- parse dropMiddle

parse P (\inp -> case parse app2 inp of
                   []         -> []
                   [(g,out)]  -> parse (fmap g item) out)

.. substituting "pumpkin" into inp

case parse app2 "pumpkin" of
 []         -> []
 [(g,out)]  -> parse (fmap g item) out

Now parse app2 "pumpkin" is going to be invoked; app2 is app1 <*> item:

-- parse app2

case parse app1 "pumpkin" of
 []         -> []
 [(g,out)]  -> parse (fmap g item) out

Similarly, we get to parse app1 "pumpkin":

-- parse app1

parse (fmap selector item) "pumpkin"

.. following the definition of fmap

parse P (\inp -> case parse item inp of
                  []        -> []
                  [(v,out)] -> [(selector v,out)])

.. Since (parse item "pumpkin") returns [('p',"umpkin")], we get:

[(selector 'p',"umpkin")]

Now going back to parse app2, knowing what parse app1 "pumpkin" returns:

parse (fmap (selector 'p') item) "umpkin"

.. following the definition of fmap

parse P (\inp -> case parse item inp of
                  []        -> []
                  [(v,out)] -> [(selector 'p' v,out)])

[(selector 'p' 'u',"mpkin")]

Finally, dropMiddle:

app2 <*> item = P (\inp -> case parse app2 inp of
                            []        -> []
                            [(g,out)] -> parse (fmap g item) out)

.. Since (parse app2 "pumpkin") returns [(selector 'p' 'u',"mpkin")]

parse (fmap (selector 'p' "u") item) "mpkin"

.. If we follow the definition of fmap again, we'll get:

[(selector 'p' 'u' 'm',"pkin")]

This is the final result of applying dropMiddle to "pumpkin", and when selector is invoked we get [(('p','m'),"pkin")], as expected.

Parser as a Monad

Parsers can also be expressed and combined using monadic style. Here's the Monad instance for Parser:

instance Monad Parser where
  -- return :: a -> Parser a
  return = pure

  -- (>>=) :: Parser a -> (a -> Parser b) -> Parser b
  p >>= f = P (\inp -> case parse p inp of
                          []        -> []
                          [(v,out)] -> parse (f v) out)

Let's take the simple example of applying toUpper to item again, this time using monadic operators:

> parse (item >>= (\x -> return $ toUpper x)) "foo"

Substituting in the definition of >>=:

item >>= (\x -> return $ toUpper x) =
  P (\inp -> case parse item inp of
                []        -> []
                [(v,out)] -> parse (return $ toUpper v) out)

... if item succeeds, this is a parser that will always succeed with
    the upper-cased result of item

When writing in monadic style, however, we won't typically be using the >>= operator explicitly; instead, we'll use the do notation. Recall that in the general multi-parameter case, this:

m1 >>= \x1 ->
  m2 >>= \x2 ->
      mn >>= \xn -> f x1 x2 ... xn

Is equivalent to this:

do x1 <- m1
   x2 <- m2
   xn <- mn
   f x1 x2 ... xn

So we can also rewrite our example as:

> parse (do x <- item; return $ toUpper x) "foo"

The do notation starts looking much more attractive for multiple parameters, however. Here's dropMiddle in monadic style written directly [2]:

dropMiddleM :: Parser (Char,Char)
dropMiddleM = item >>= \x ->
                item >>= \_ ->
                  item >>= \z -> return (x,z)

And now rewritten using do:

dropMiddleM' :: Parser (Char,Char)
dropMiddleM' =
  do  x <- item
      z <- item
      return (x,z)

Let's do a detailed breakdown of what's happening here to better understand the monadic sequencing mechanics. I'll be using the direct style (dropMiddleM) to unravel the applications of >>=:

item >>= \x ->
  item >>= \_ ->
    item >>= \z -> return (x,z)

.. applying the first >>=, calling the right-hand side rhsX

P (\inp -> case parse item inp of
              []        -> []
              [(v,out)] -> parse (rhsX v) out)

.. the result of parsing the first item is passed in as the argument to rhsX,
   which then returns the next application of >>=; As usual, we acknowledge
   the error propagation and ignore it for simplicity.

P (\inp -> case parse item inp of
              []        -> []
              [(v,out)] -> parse (rhsY v) out)

... and similarly for rhsZ; the final result is invoking "parse return (x,z)"
    where x is the result of parsing the first item and z the result of
    parsing the third.

A complete example

As a complete example, I've expanded the parser grammar found in the book to support conditional expressions. The full example is available TODO. Recall that wa want to parse expressions of the form:

if <expr> then <expr> else <expr>

This is the monadic parser [3]:

ifexpr :: Parser Int
ifexpr = do symbol "if"
            cond <- expr
            symbol "then"
            thenExpr <- expr
            symbol "else"
            elseExpr <- expr
            return (if cond == 0 then elseExpr else thenExpr)

And this is the equivalent applicative version (<$> is just an infix synonym for fmap):

ifexpr' :: Parser Int
ifexpr' =
  selector <$> symbol "if" <*> expr
           <*> symbol "then" <*> expr
           <*> symbol "else" <*> expr
  where selector _ cond _ t _ e = if cond == 0 then e else t

Which one is better? It's really a matter of personal taste. Since both the monadic and applicative styles deal in Parsers, they can be freely mixed and combined.

[1]Failures could also be signaled by using Maybe, but a list lets us express multiple results (for example a string that can be parsed in multiple ways). We're not going to be using multiple results in this article, but it's good to keep this option open.
[2]We could also use the monadic operator >> for statements that don't create a new assignment, but using >>= everywhere for consistency makes it a bit easier to understand.
[3]The return value of this parser is Int, because it evaluates the parsed expression on the fly - this technique is called Syntax Directed Translation in the Dragon book. Note also that the conditional clauses are evaluated eagerly, which is valid only when no side effects are present.