Ten Thousand Connections, One Thread, and One Thing It Still Cannot Do

Last timeThe State Called Blocked

A request can be told to answer not yet rather than block. That alone is not enough, and the piece that makes it work is the kernel telling you which requests are ready.

Answering not yet

The previous lesson ended with a thread that completes a hundred and

twenty-five requests a second while computing almost nothing. The thread is not

slow. It is asleep for ninety-nine per cent of its life, and the sleep is the

problem.

The first piece of the fix is small. A descriptor can be marked non-blocking,

and after that, a request on it never puts the process to sleep. If there is

data, you get data. If there is not, you get an immediate, specific answer

meaning there is nothing right now, which is not an error and has to be handled

as a normal case.

That changes what you own. Before, the kernel decided when your thread ran

again, and the decision was correct but out of your hands. Now the thread keeps

the processor and the question of what to do next is yours. The honest way to

describe this is not that waiting has been removed. It has been moved into your

program, where you can wait for many things at once instead of one.

FIG 1What can actually be made non-blocking

	can be marked non-blocki	reports readiness useful	stops the thread regardl
reading a socket	1	1	0
writing a socket	1	1	0
reading a pipe	1	1	0
reading an ordinary file	0	0	1
a page fault on your own	0	0	1
resolving a host name	0	0	1
computing something	0	0	1

The first three rows are what the pattern was designed for and they work exactly as advertised. The last four are where people get hurt. The first marked row is the famous one: marking an ordinary file non-blocking is accepted and then has almost no effect, because the kernel will still fetch the data synchronously, so a file read in an event loop stalls every connection on it. The second marked row is the one that surprises people, since looking up a host name is a network operation that nonetheless blocks in the ordinary library, and a single slow lookup freezes a server that handles ten thousand sockets without breaking a sweat.

Why asking everything fails

Given non-blocking requests, the obvious program is a loop: go round every

connection, try to read each one, handle whatever came back, repeat.

It does not work, and the reason is the second lesson. Every one of those

attempts is a crossing, costing a few hundred nanoseconds whether or not there

was anything there. The cost of a pass is proportional to the number of

connections you are watching, and the useful work in a pass is proportional to

how many of them actually had data, which at any instant is a small fraction.

FIG 2The cost of one pass over everything you are watching

: the time one full pass costs, before any work is done
: how many connections you are watching
: the cost of one crossing, a few hundred nanoseconds

There is no term in this for how many connections had data, which is the whole complaint. Ten thousand idle connections cost exactly as much to check as ten thousand busy ones, so a mostly idle server spends its processor discovering that nothing has happened, and the discovery has to be repeated as fast as possible to keep latency low. This is the shape of a design that gets worse as it gets more popular.

FIG 3Microseconds spent per pass, with four connections actually ready

ask every connection in turnone notification, four ready

The straight line is the loop and the flat line is the alternative. At a handful of connections there is nothing to choose between them, which is why this never shows up in a small test. At two hundred the loop costs fifty times as much per pass, and the line keeps going: at ten thousand it is five milliseconds per pass, so the server can do no more than two hundred passes a second no matter how fast the machine is. The flat line does not move at all, because it depends on the four, not the ten thousand.

Let the kernel tell you

The fix is to stop asking. Register the whole set of things you care about

once, in the kernel, where it is kept across calls. Then make a single request

that blocks until at least one of them is ready, and returns the ones that are.

That one change moves the cost from the size of the watched set to the size of

the ready set. The kernel is not scanning either: when a packet arrives, the

interrupt handler already knows which connection it belongs to, so it can put

that connection straight onto a ready list. Your notification request just

collects the list.

The lesson stops here

1 more paragraph to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents