HomeBlogRedis client

Writing a Redis client library for Node.js

I'm playing with Node.js lately.  Node is an asynchronous environment that allow you to use JavaScript on the server.  The asynchronous nature makes it a bit different from other programming environments, and I'll describe in this article how I'm using some obvious features of the language (closures and exceptions) to accomplish something not-quite-trivial.  In short, I've written a Redis client library and a WebSocket library (and yes, I know these things exist already, but I suffer from the NIH syndrome).

JavaScript has exceptions, and JavaScript has closures—combining them you can get “restarts”.  It's not the same as Lisp's condition/restarts system, in that once it throws an exception a function can not return anymore.

In order to make use of this technique you have to write your code in “continuation-passing style” and avoid iterative loops.  While this might seem too complicated, it's easier and more natural than it sounds (and it's almost a requirement in environments such as NodeJS).

[ If you're only interested in the Redis code, scroll here ]

Throw a function!

Since you can throw any kind of object in JavaScript, and since functions are objects, it begs the question: couldn't we throw a function?  Of course we can.  Here's a silly example:

function foo() {
    var test = "Something";
    throw function() {
        return test;
    };
};

try {
    foo();
} catch(ex) {
    if (ex instanceof Function) {
        alert(ex()); // displays "Something"
    } else {
        throw ex;
    }
}

While the above example doesn't do anything interesting, it shows that you can throw a closure that captures the context where the “error” happened.  That inner function that we threw can tell the variable value is "Something", even though the outer function has already aborted with an exception (thus the call stack is unwound).

Via the exception system we can abruptly interrupt a complex computation, and still save means to resume it later.  And that's what I meant by “restarts”.

Continuation-passing style

The above technique is not too useful unless you write your code in CPS.  In this style a function never returns—instead it calls another function (named “continuation”) with the return value.  For example:

// classic style
function sum(a, b) {
    return a + b;
}
alert(sum(10, 20));

// CPS
function sum(a, b, cont) {
    cont(a + b);
}
sum(10, 20, function(result){
    alert(result);
});

CPS is a bit harder to follow and it can result in a lot of nesting in your program.  But it's essential for example in programming user interface, or asynchronous servers (node.js).

Tail call optimization

Closely related to CPS is a technique named “tail call optimization”.  Unfortunately JavaScript doesn't have it and it looks like it won't have it anytime soon.  (I was Googling to see if there are any plans to implement it in V8, but the good V8 folks found a lame (valid, but still lame) excuse not to.)

What it means and why is it important?  Since in CPS a function never returns, the stack can only grow and grow.  However, it is important to notice that in the above example, the very last thing that happens in function sum() is to call the continuation.  After cont() returns, the control is passed back to sum(), even though it has nothing else to do.  This is what happens, currently.

If we would have TCO, the compiler would realize that it makes no sense to return to sum(), and instead of allocating a new stack frame for cont() it will simply replace the currently running stack of sum(), and thus cont() will return directly to the calling program instead of uselessly going back through sum().

This is an important speed improvement, but even more importantly it avoids a stack overflow.  However, as you will see, we can get around this JS limitation by using exceptions.

Here is an example of a recursive function that sums 1 + 2 + ... + n.

function sum(n) {
    if (n == 0)
        return 0;
    return n + sum(n - 1);
};

alert(sum(100));   // works: 5050
alert(sum(3000));  // error: too much recursion

Again, should JavaScript have TCO, the last line would work just fine.  But it doesn't, so it fails with a stack overflow exception.  The number is quite small also.

Update: as I re-read this, I realize that the previous paragraph is incorrect—if nothing else, this shows how easy it is to confuse things in the absence of Lispy syntax; in Lisp I wouldn't have mistaken it because it would look like this: (+ n (sum (- n 1))), which makes it obvious that the sum() call isn't in tail position.

So even with TCO, the last line above would still exhaust the stack—because there is something that happens after sum(n-1) returns, and that is adding the current value of n to the result.  To make use of TCO you really have to rewrite it in CPS, and that's what we do below anyway.

Let's now transform this into continuation-passing style:

function sum(n, cont) {
    if (n == 0) {
        cont(0);
    } else {
        sum(n - 1, function(result){
            cont(n + result);
        });
    }
}

sum(100, function(result){   // works, 5050
    alert(result);
});
sum(3000, function(result){  // again, stack overflow
    alert(result);
});

No free lunch yet.  So far I only managed to obfuscate the code.  It's hard to follow what it does unless you understand closures.  At the first step, cont() refers to the function that calls alert(result); at the second step, cont() refers to sum() which is being passed the function that calls alert(result); and so on.  When we get to n = 0, cont() will have a memory of all previous invocations and contains all the logic to complete the computation and call the original function (alert).

I agree that this method doesn't make sense for such a simple example, but bear with me.  Let's now apply the “throw-a-function” technique in order to counterbalance the missing tail call optimization.  We will use a helper function, “cps_call”:

function cps_call(func) {
    while (true) {
        try {
            func();
            break;
        } catch(ex) {
            if (ex instanceof Function) {
                func = ex;
            } else {
                throw ex;
            }
        }
    }
}

It's easy to follow what it does: it calls the given function in a try/catch block, and checks if the exception that was thrown is a function.  If so, it proceeds to call that function in the same fashion (this is why everything is embedded in a while(true) block).  Now we will rewrite our sum() function like this:

function sum(n, cont) {
    if (n == 0) throw function() {
        cont(0);
    };
    else throw function() {
        sum(n - 1, function(result){
            throw function() {
                cont(n + result);
            };
        });
    };
}

cps_call(function(){
    // and what do you know, this time it works!
    // the result is 4501500
    sum(3000, function(result){
        alert(result);
    });
});

Why does it work this time?  Because instead of recursing, we throw continuations.  The exception clears the stack, but we are able to go back and continue the work by saving and re-calling the “current continuation” (CC).

Note that we've chosen to call the CC right away, but we could as well store it somewhere and call it later!

Unreadable code?

Of course, the code looks awful already.  But I think the technique is important.  Before going further, let's redefine the API in a way that would make the code look better.  We will start by building around cps_call():

function Continuation(func, args) {
    this.func = func;
    this.args = args;
};

// this is useful since “arguments” isn't a real array
var SLICE = Array.prototype.slice;

function NOW(func) {
    throw new Continuation(func, SLICE.call(arguments, 1));
};

function cps_call(func) {
    // cc stands for "current continuation"
    var cc = new Continuation(func, []);
    while (true) {
        try {
            cc.func.apply(null, cc.args);
            break;
        } catch(ex) {
            if (ex instanceof Continuation) {
                cc = ex;
            } else {
                throw ex;
            }
        }
    }
};

The implementation of cps_call shouldn't scare you; you write it once and put it somewhere.  What matters is the API that you use.  That should be clean and simple.

The above implements the same idea, but introducing some new API that allows us to write the sum() function like this:

function sum(n, cont) {
    if (n == 0) NOW(cont, 0);
    NOW(sum, n - 1, function(result){
        NOW(cont, n + result);
    });
}

A lot better, isn't it?  It's almost as good as the original recursive implementation.

How's all this useful?

In order to learn some Node internals and do something useful, I decided to write a Redis client library (also because I wasn't happy with any of the existing ones).

In Node, the networking API is asynchronous.  This means that you request something from a server, but you don't get the response right away.  In fact the same happens in any environment, but the classic API is to block the calling application until data arrives.  In Node you simply don't have this API and need to work in continuation-passing style.

What's complicating the Redis problem is that, even though the protocol is extremely simple, it's tricky to read asynchronously because in order to read a full answer you have to parse it.  It would be cool if you could read a full answer and parse it later, but you can't because you don't know in advance how many bytes to read.  The parser has to examine the data as it is coming, but has to stop when (for whatever reason, such as a network bottleneck) no more data is coming, but also it has to be able to resume later.

The classic solution for this, I guess, is to write a state machine.  Your parser would be an object, presumably, that would store the complete state in properties so that the next time you get a block of bytes from Redis it can continue.

State machines aren't fun!  It's quite difficult to keep track of everything manually.  Besides, it seems very difficult to implement a recursive state machine and in this particular case it's important because the Redis protocol is recursive! (and this is where other implementations that I tested fail).

A proper Redis parser

The Redis protocol defines a few response types, based on the first character seen:

  • - (a dash) starts an error line
  • + (plus) starts a single line string reply
  • : (colon) starts a single integer number reply
  • $N (dollar followed by a number) starts a BULK reply; the “string” has N bytes
  • *X (asterisk followed by a number) starts a MULTIBULK reply, which is an array of X replies.

If it weren't for the MULTIBULK type, things would have been much easier.  A MULTIBULK reply is an array, but what other Redis clients seem to assume is that it's always an array of strings (to be honest, the protocol spec isn't clear about this either).  However I found that there are situations where you can get errors, or integers too in this array (in transactions!)—so the best way to implement the MULTIBULK parser is to recursively call the Redis parser.

The code is pretty big to paste it here, but I attached my Redis implementation.  Distributed under the BSD license.  Drop me a line if you find it useful.

The source is pretty well commented.  The actual parsing code, which is implemented using the techniques that I described above, is defined by the RedisParser function (look around line 200).  It's small and elegant, compared to what I've seen out there.

Sample usage:

var client = new redis.Client({ host: ..., port: ... });
client.cmd("INCR", [ "a" ], function(result) {
    if (client.isError(result)) {
        handle_error(result.toString());
    } else {
        alert("Result: " + result);
    }
});

client.withTransaction(function(){
    client.cmd("INCR", [ "seq" ]);
    client.cmd("INCR", [ "seq" ]);
    client.cmd("INCR", [ "seq" ], function(result) {
        // result is seq incremented 3 times.
    });
});

(if you know of other Redis client for Node that properly supports transactions, please let me know :-p).

      Comments

      • By: peepo.comJul 10 (17:06) 2010RE: Writing a Redis client library for Node.js §

        An excellent introduction, adding to my limited knowledge and experience of closure.
        Could you add some links to other writing on this topic?
        had you experience of nodejs with xml databases?

      • By: iniminoJul 10 (21:00) 2010Not quite tail recursive... §

        Nice post, I would be interested to see a follow-up post comparing the same library written as a state machine, in terms of code size and performance.

        Under Tail Call Optimization, you write, "Again, should JavaScript have TCO, the last line would work just fine.  But it doesn't, so it fails with a stack overflow exception."

        The last line of your sum() is "return n + sum(n - 1);".

        This is not tail recursive and would not work even with TCO.  You could write:

        function sum(n){
          return go(n,0)
          function go(n,c){
            if (n == 0) return c
            return go( n-1, c+n )}}

      • By: Matt ToddJul 11 (07:26) 2010RE: Writing a Redis client library for Node.js §

        Excellent! Now is it available on GitHub and/or npm? I'd like to give it a whirl!

        Also, do you plan on adding some command niceties? Like:

        client.incr('seq')

        instead of:

        client.cmd("INCR", [ "seq" ])

      • By: nalplyJul 11 (14:55) 2010RE: Writing a Redis client library for Node.js §

        Isn't cps_call() a trampoline? Trampolines repeatedly call functions and are used in Scheme to implement continuations in C.

        • By: mishooJul 11 (15:46) 2010RE[2]: Writing a Redis client library for Node.js §

          I didn't know this term. :.  Just found it on Wikipedia and indeed, one of the usages refer to the same technique.

        • By: nalplyJul 18 (10:08) 2010Even more trampoline approaches? §

          Your work inspired me to experiment with continuations in Javascript. I am thinking about a code-walker for automatic transforms to CPS. I found that there are more approaches to avoid stack overflow typical of CPS:

          1. Return thunks in NOW(): do not throw but return a function which will apply the continuation: the thunk. In this case CPS needs return in front of NOW(), like this: if (n == 0) return NOW(cont, 0). The trampoline repeatedly applies the thunks in an iterative loop and avoids nested calls, similar to this: while (thunk) { thunk = thunk() }. This works, because the continuations are chained from thunk to thunk. This is the traditional use case of the trampoline, and this also works in C (with function pointers): http://home.pipeline.com/~hbaker1/CheneyMTA.… (read 2nd paragraph of the section "Introduction").

          2. Catch the stack overflow: Each continuation is saved in the trampoline before being called directly and when stack overflow occurs, the saved continuation is restarted again. This trick also works (with some assembly) in C and is used by Chicken Scheme.

          3. Use setTimeout(continuation, 0) instead. Node.js even has a very efficient variant of it: nextTick().

          4. Do the evil trick (like throwing functions or using setTimeout() :-) only every few hundred times. The other times just call the continuations directly. No harm in using up a part of the stack!

      • By: RobertAug 19 (21:55) 2010RE: Writing a Redis client library for Node.js §

        That's a VERY interesting post and technique.

        I currently use redis-node-client in a project I'm working on.
        I found that using 'step' (http://github.com/creationix/step) made the code a billion times more readable than without.

        I've subscribed to your blog and I'm looking forward to reading future posts :)

      • By: Dave HermanFeb 03 (02:12) 2011RE: Writing a Redis client library for Node.js §

        The ECMAScript committee has just agreed to make proper tail calls a priority for the next version of the language! That means that (after opting in to the new language version), you'd be able to write in CPS till the cows come home. Or till your script times out. ;)

        More information here: http://blog.mozilla.com/dherman/2011/01/30/p…

      Page info
      Created:
      2010/07/10 12:15
      Modified:
      2010/07/11 01:22
      Author:
      Mihai Bazon
      Comments:
      11
      Tags:
      javascript, lexical closures, node.js, programming, redis, v8
      See also