Haraka, Node

How an Event Loop works

Getting into coding in Node.js came very naturally to me. Prior to this I had written a fair bit of Danga::Socket in Perl and various solutions on top of it. What that meant is that coding in Node came naturally to me – Danga::Socket is an Event Loop for Perl, so I understood the internals and how everything hung together in an Event Loop. But it’s not that way for a large number of people coming to Node from other languages.

So let’s start with the basics of how an event loop works.

I’m going to start with simple timers – in Node/Javascript this is the concept of setTimeout() and setInterval(). These simply run code at a later time, a number of milliseconds in the future.

If the current time in milliseconds since the epoch is 1000 (yes I know that’s nowhere near what it really is), and we ask for a setTimeout() to run in 25ms time, that means the fire time for that event is 1025. We can loop over and over, checking if that fire_time <= current_time, and fire events that have past.

So the basics of our event loop become the following code:

while (1) {
    // run all setTimeout() code that has past the current time
    _run_timers();
}

This would loop forever, running timers that are due to fire. However a weakness would be that it is what we call a “busy loop” – it burns 100% CPU if there are no timers to fire. To improve this, we make _run_timers() return the timeout until the next timeout has to fire:

while (1) {
    var next_timeout = _run_timers();
    ms_sleep(next_timeout);
}

Consider here that ms_sleep() just puts the process to sleep until the next timeout is due to fire (in C we would use “usleep()”).

Two important things become obvious out of this:

  1. Timers aren’t time-accurate – they may run slightly late (though never early).
  2. Blocking the event loop is bad because other timers don’t get to run

Now we need a data structure that can keep our timers. For this we can use use an array of Timer objects:

var Timers = []; // list of current Timers

// our Timer object constructor
function Timer (fire_time, cb) {
    this.fire_time = fire_time; // in epoch-ms
    this.callback = cb;
}

We are assuming that the Timers array is in the order that events will fire. Now we can implement _run_timers() as follows:

function _run_timers () {
    var now = Date.now();

    while (Timers.length > 0 && Timers[0].fire_time <= now) {
        var to_run = Timers.shift();
        if (to_run->callback) to_run->callback();
    }

    if (Timers.length === 0) return -1;

    return (Timers[0].fire_time - now);
}

If we assume that the current time (now) is 1000, and the Timers array contains entries with fire_now values of: [980, 985, 995, 1005, 1010] – the end result is we run the first three callbacks, Timers is left containing [1005, 1010], and we return 5 from our function. We sleep for 5 milliseconds and call _run_timers() again.

Now all we have to do is implement setTimeout() so it keeps that array in order. Here’s a copy of the implementation in Danga::Socket converted to Javascript:

function setTimeout (cb, ms) {
    var fire_time = ms + Date.now();

    var timer = new Timer (fire_time, cb);

    // Optimise for the case where a timer fires after
    // all current timers
    if (Timers.length === 0 || fire_time >= Timers[Timers.length - 1].fire_time) {
        Timers.push(timer);
        return timer;
    }

    // Otherwise find where we insert linearly:
    for (var i = 0; i < Timers.length; i++) {
        if (Timers[i].fire_time > fire_time) {
            Timers.splice(i, 0, timer);
            return timer;
        }
    }

    throw "Should never get here"
}

So now we have everything that we need to implement an event loop in Javascript, at least only implementing timers. Implementing setInterval() is as simple as:

function setInterval (cb, ms) {
    var _f = function () {
        cb();
        setTimeout(_f, ms);
    };
    setTimeout(_f, ms);
}

And we can cancel timers by clearing their .callback entry (they will remain in the array, but that’s not a big deal for this example).

Lets expand on this to deal with how Node provides us with events on sockets and files. We can mostly assume that aside from Timers we are only dealing with File Descriptors (FDs). This is a misnomer, so don’t focus on the name – they are part of the unix concept of “Everything is a file” and abstract away many different systems in a modern Unix, not just files. Let’s now add to our global objects a mapping of FDs to “things” which can handle events on our file descriptors:

var FDMap = {};

Every time Node opens a file, or creates a server, or gets a connection on a server, all these things create new FDs, and must be added to that mapping table:

function _seen_new_fd (fd) {
  FDMap[fd] = new FDHandler(fd);
}

So now what? How do we know when there are these “events” on file descriptors? Well luckily the Kernel (be it Linux, BSD/OSX, Solaris or Windows) has ways of letting us know something happened. Let’s focus on one of those methods as Node hides all the gritty details for us anyway. In Linux we use something called “epoll”. What epoll does is allows us to setup a structure which monitors those file descriptors and notifies us of events on them. The key events are “read” and “write” but there are others too.

Now we can change our original event loop to look like this:

for (var fd in FDMap) {
    add_to_epoll_set(fd);
}

while (1) {
  var timeout = _run_timers(); // remember this from above?
  var events = epoll_wait(Epoll, 1000, timeout);
  for (var i = 0; i < events.length; i++) {
    var event = events[i];
    // event is an array of [fd, state]
    var fd_handler = FDMap[event[0]];
    var state = event[1];
    if (state & EPOLLIN)  fd_handler.do_read();
    if (state & EPOLLOUT) fd_handler.do_write();
  }
}

I will skip over further implementation details, but this is the basics of an epoll-based event loop, with a LOT of error checking removed for clarity purposes.

  • First we run the timers and get the timeout
  • Then we call epoll_wait() passing in the timeout returned from _run_timers
  • Then we process the events returned, which map to file descriptors
  • Then we loop back and do it all again

OK so how does this all relate to your HTTP server written in Express? We’re a million miles abstracted from that.

At the low level your HTTP server is just a socket that is listening on a port (usually 80 for http, or 443 for https). In Unix terms a socket is represented by an FD, so is part of the descriptor map (FDMap) above.

When a connection comes in from the internet, it tells the kernel, to tell epoll_wait, that a “read” event fired on that FD.

When we get that “read” event, node accepts the connection and passes it to your Javascript program. But it does more than that too – an accepted connection gives you another FD – one that represents that particular connection. And as we said earlier – every FD that node sees gets added to the FDMap, and to the event loop (epoll). Node keeps track of all these FDs for you.

So when we get data sent to us over that connection, it fires the “read” event on it. In HTTP terms this means that we probably have something like:

GET /path/to/resource HTTP/1.1
Host: app.hubdoc.com
Connection: close

Now most users of Node will be using some sort of HTTP layer – which will parse this data automatically. If you were using Node’s “Net” library you would have to do it yourself.

After parsing the HTTP commands, Express then translates that into a Route using a lookup table, and the rest is up to your application.

What about writing?

Writing data in this system is a little more confusing, because the “write” event isn’t really telling you that you SHOULD write, just that there’s space left in the kernel buffers so that you CAN write. More importantly, your application never cares about “write” events because Node handles it all internally. Once you understand that it gets a bit more simple. There’s multiple levels of buffering occurring – Node has to buffer data that your application has tried to write that didn’t get to the kernel, and send it when the epoll system tells it that it can.

In summary this was a VERY high level overview of how event loops work, but skipping over a LOT of the details of error checking, edge cases, and the reality of how things really work low down. But it should give the average Node programmer a better idea of how things work, why blocking the event loop is bad, and how setTimeout works (and thus why setTimeout isn’t “accurate” time-wise).

For more detail I recommend reading the source code to Danga::Socket: http://cpansearch.perl.org/src/BRADFITZ/Danga-Socket-1.61/lib/Danga/Socket.pm – it’s simple to read even for Perl, and the key functions are at the top of the file. It performs well and scales to hundreds of thousands of concurrent connections – I should know – I’ve pushed it that far personally.

Feel free to leave me questions or comments. I’d love to know if you found this useful.

Standard

2 thoughts on “How an Event Loop works

  1. Pingback: Learning Node.JS: News, Videos and Tutorials « Hanger Designs || Web development & Design By Owain Llewellyn

  2. Pingback: Express: Links, News And Resources (3) | Angel "Java" Lopez on Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s