Posted by bert hubert
Sun, 04 Feb 2007 12:14:00 GMT
Ok, I’m going to lecture a bit, a bad habit of mine. The summary is that an important enhancement of the Linux kernel has been proposed, but in order to understand the significance of this enhancement, you need a lot of theory, which follows below.
I use the word “computer” sometimes when I properly mean “the operating system”. This exposes a problem of this post, I’m trying to explain something deeply theoretical to a general audience. Perhaps it didn’t work. See for yourself.
Doing many things at once
People generally tend not to be very good at doing many thing at once, and surprisingly, computers are not much different in this respect.
First about human beings. We can do one thing at a time, reasonably well. There are people that claim they can multi-task, but if you look into it, that generally means doing one thing that is really simple, while simultaneously talking on the phone.
This is exemplified by how we answer a second phone call, ie, by saying “The other line is ringing, I’ll call you back”, or conversely, telling the other line they’ll have to wait.
We emphatically don’t try to have two conversations at once, and even if we had two mouths, we still wouldn’t attempt it.
Let’s take a look at a web server, the program that makes web pages available to internet browsers. The basic steps are:
- Wait for new connections from the internet
- Once a new connection is in, read from it which page it wants to see (for example, ‘GET http://blog.netherlabs.nl/ HTTP/1.1’).
- Find that page in the computer
- Send it to the web browser that connected to us
- Go to 1.
Compare this to answering a phone call, step 1 is the part where you wait for the phone to ring, and answering it when it does. Step 2 is hearing what the caller wants, step 3 is figuring out the answer to the query, 4 is sharing that answer.
This all seems natural to us, as it is the way we think. And programmers, contrary to what people think, are human beings, too.
Where this simple process breaks down is that, much like a regular phone call, we can only serve a new web page once the old one is done sending.
And here is where things get interesting - although we people have a hard time doing multiple things at once, we can give the problem to the computer.
What is the easiest way of doing so? Well, if we want to increase the capacity of a telephone service we do so.. by adding people. So on the programming side of things, we do the same thing, only virtually: we order the computer (or more exactly, the operating system) to split itself in two!
The new list of steps now becomes:
- Wait for new connections from the internet
- Once a new connection is in, split the computer in two.
- One half of the computer goes back to step 1, the other half continues this list
- (2) Read from it which page it wants to see (for example, ‘GET http://blog.netherlabs.nl/ HTTP/1.1’).
- (2) Find that page
- (2) Send it to the web browser
- (2) Done - remove this “half” of the computer
I’ve prefixed the things the second computer does with ”(2)” . This looks like the best of both worlds. We can “serve” many web pages at the same time, and we didn’t need to do complicated things. In other words, we could continue thinking like human beings, and use our intuition, by thinking of the analogies with answering phone calls.
So, are we done now? Sadly no. What basically has happened is that we have invoked a piece of magic: let’s split the computer in two. That is all fine, but somebody has to do the splitting. This job is farmed out to the CPU (the processor) and the operating system (Windows, Linux etc), and they have to deal with making sure it appears the computer can do two things at the same time.
Because the truth is.. people can’t do it, and neither can computers. They fake it.
This faking comes at a cost, incurred both while splitting the computer (“forking”), and by making the computer juggle all its separate parts. Finally, it turns out that practically speaking, you can divide a computer up into only a limited number of parts before the charade falls down.
Busy websites have tens of millions of visitors, we’d need to be able to split the computer into at least that many parts, while in practice the limit lies at perhaps 100,000 slices, if not less.
Now what
Several solutions to this problem have been invented. Some involve not quite splitting up the entire computer and making split parts share more of the resources (like for example, memory). This is called ‘threading’. Perhaps this could be compared with not hiring more people to answer the telephone, but instead giving the people you have more heads, so as to save money.
In the end, all these solutions run into a brick wall: it is hard to maintain the illusion that the computer can do multiple things at the same time, AND have it actually do a million things at the same time.
So in the end, we have to bite the bullet, and just make sure the program itself can handle many many things at once, without needing the magic of pretending the computer can do it for us.
“Asynchronous programming”
This is where things get hard, and this is to be expected, as it was our basic premise that people can’t do multiple things at the same time, and what’s worse, they have a hard time even thinking about what it would be like.
The new algorithm looks like this:
- Instruct the computer to tell us when “something has happened”
- Figure out what happened:
- If there is a new connection, instruct the computer that from now on, it should tell us if new data arrived on that connection
- If something has happened to one of those connections we’ve told the computer about, read the data sent to us on that connection. Then find the information requested on that connection, and instruct the computer to tell us when there is “room” to send that data
- If the computer told us there was “room”, send the data that was previously requested on that connection. If we are done sending all the data, tell the computer to disconnect, and no longer inform us of the state of the connection.
- Go back to 1.
If this feels complicated, you’d be right. However, this is how all very high performance computer applications work, because the “faking” described above doesn’t really “scale” to tens of thousands of connections.
How does this translate to the telephone situation? It would be like we have lots of small answering machines, that lots of callers can talk to at the same time. Whenever someone has finished a question, the operator would listen to that answering machine, and leave the answer on the machine, and go on to the next machine that has a finished message.
From this description, it is clear it would not work faster that way if you’d try it for real. However, in many countries, if you call a directory service to find a telephone number, you’ll get half of this. Your call is answered by a real human being, who asks you questions to figure out which phone number you are looking for. But once it has been found, the operator presses a button, and the result of your query is sent to a computer, which then reads it to you, allowing the operator to already start answering a new call. Rather smart.
Something in between
If the previous bit was hard to understand, I make no apologies, this is just how complicated things are in the world of computing. However, we programmers also hate to deal with complicated things, so we try to avoid stuff like this.
People have invented many ways of allowing programmers to think ‘linearly’, as if only a single thing is happening at the same time, without having to split the entire computer.
One way of doing this is having a facade that makes things go linearly, until the program has to wait for something (a new connection, “room” to send data etc), and then switch over to processing another connection. Once that connection has to wait for something, chances are that what our earlier ‘wait’ was waiting for has happened, and that program can continue.
This truly offers us the best of both worlds: we can program as if only a single thing is happening at the same time, something we are used to, but the moment the computer has to wait for something, we are switched automatically to another part of the program, that is also written as if it is the only thing happening at the same time.
Actually making this happen is pretty hard however, because traditional computer programming environments don’t clearly separate actions that could lead to “waiting” from actions that should happen instantly.
A prime example of the first kind of action is “waiting for a new connection” - this might in theory take forever, especially if your website is really unpopular.
Things that should happen instantly include for example asking the computer what time it thinks it is.
Traditional operating systems can be instructed to be mindful of new incoming connections, and not keep the program waiting for them. This is what we described in the complicated “if X happened, if Y happened” scenario above.
They can also do the same for reading from the network and writing to the network, both things that might take time. This means you can ask the operating system ‘let me know when I can read so I don’t have to wait for it, and I can process other connections in the meantime’.
Furthermore, there are some limited tricks to do the same for reading a file. The problem is that back in the 1970s when most operating system theory was being invented, disks were considered so fast, nobody thought it possible you’d ever need to meaningfully wait for one. Of course disks weren’t faster back then, but computers were slower, and massively so. So by comparison, disks were really fast.
The upshot is that in most operating systems, disk reads are grouped with “stuff that should happen instantly”, whereas every computer user by now has experienced this is emphatically not the case.
Modern operating systems offer only a limited solution to this problem, called ‘asynchronous input/output’, which allows one to more or less tell the computer to notify us when it has read a certain piece of data from disk.
However, it doesn’t offer the same facility for doing a lot of other things that might take time, like finding the file in the first place, or opening it. Things that in the real world take a lot of time.
So, we can’t truly enjoy the best of both worlds as sketched above, which would mean the programmer could write simple programs, which would be switched every time his program has to wait for something.
Enter ‘Generic AIO’
Zach Brown, who is employed by Oracle to work on Linux, has now dreamed up something that appears to never have been done before: everything can now be considered something that “might take time”.
This means that you can ask Linux to find a certain file for you, and immediately allows you to process other connections that need attention. Once the operating system has found the file for you, it is available for you without waiting.
Although almost every advance in operating system design has at one point been researched already, this approach appears to be rather revolutionary.
It has ignited vigorous discussion within the Linux community about the feasibility of this approach, and if it truly is the dreamt of “best of both worlds”, but to this author, it surely looks like a breakthrough.
Especially since it unites the worlds of “waiting on a read/write from the network” with “waiting for a file to be read from disk”.
Time will tell if “Generic AIO” will become part of Linux. In the meantime, you can read more about it on LWN.
Posted in Linux, Netherlabs, Life | 2 comments
Posted by bert hubert
Fri, 12 Jan 2007 21:16:00 GMT
The workings of the Internet are described, or even proscribed, by the so called ‘Requests For Comments’, or RFCs. These are the laws of the internet.
Today the IETF DNS Extensions working group accepted an “Internet-Draft” Remco van Mook and I have been working on. And the cool bit is that over time, many such accepted “Internet-Drafts” turn into RFCs!
Read about it what our draft does
here
and here.
The actual Internet-Draft can be found over at the IETF, or over here as pretty HTML.
In short, this RFC documents and standardises some of the stuff DJBDNS and PowerDNS have been doing to make the DNS a safer place.
Besides the fact that it is important to update the DNS standards to reflect this practice, it is also rather a cool thought to actually be writing an RFC, especially one that has the magic stanzas “Standards Track” and “Updates 1035” in it.
So we are well pleased! Over the coming months we’ll have to tune the draft so it confirms with the consensus of the DNSEXT working group, and hopefull somewhere around March, it will head towards the IESG, after which an actual RFC should be issued.
Exciting!
Posted in Linux, PowerDNS, Netherlabs, Life | 10 comments
Posted by bert hubert
Mon, 01 Jan 2007 15:58:00 GMT
I wish everybody a very good 2007! For PowerDNS, it certainly has been a very good year.
In some (large) places, the Recursor now commands a 40% market share, while the authoritative server is also expanding its user base around the world, with multi-million domain deployments now no longer as newsworthy as they once were.
The Chaos Computer Club held its annual congress last week, and they chose the PowerDNS Recursor to provide the DNS service to go with their 10 gigabit connection. I’m pleased to report that the PowerDNS process was fired up only once, and that it held steady for the entire congress, with no complaints. This would usually not be that strange, but the CCC clientèle are among the most critical internet users to be found on the planet.
Many thanks to Stefan Schmidt and other CCC admins for their vote of confidence!
Rails
I’m working on understanding ‘Ruby on Rails’, which will probably end up as a HOWTO aimed at seasoned programmers. The internet abounds with “you won’t believe how easy Ruby on Rails is” demonstrations, but the hard truth is that below the surface, a lot of magic is happening. The kind of magic the discerning programmer wants to grasp so as to make the most of it.
A very small start to this HOWTO can be found here.
It may also allow experience programmers to teach themselves Ruby in less time than it would take them to read a 750 page book.
Posted in Linux, PowerDNS, Netherlabs, Life | 7 comments
Posted by bert hubert
Thu, 14 Dec 2006 21:21:00 GMT
After PowerDNS 3.1.4 turned out to be boringly stable, fixing all reported crashes, I decided it was time to do the massive speedup I’d been promising people for some time.
With some help from my friends over at #offtopic2, I was able to use the TSC register of my CPU to measure down to the nanosecond how much time things were taking within PowerDNS. Previously I’d concentrated on profiling macro performance, but nanosecond resolution allows one to study fully how much time is spent within each function.
Using this technique, it became apparent we take a whopping 60 microseconds to answer even the most basic of questions. We make up for this by being pretty fast at complicated questions. But 60 microseconds mean we are limited to about 15000 questions/second, max.
First I started shaving microseconds. It turns out snprintf is truly slow, taking up to 5 microseconds for some strings. Additionally, we wasted a lot of time on needlessly copying std::strings.
The unsurpassed Boost::Multi_Index container has a spectacular feature, called ‘compatible keys’, which means we can lookup answers using a question key that is a bare piece of memory instead of a proper std::string. This again saved a few microseconds.
Put together, this brought down the 60 usec to perhaps 40, which is nice, but not stunning.
But the big savings only came when I did the only thing that actually makes code fast: do less.
So - when encoding the answer to a question, we no longer do the whole “DNS label compression”-routine, as we know the “label” of the answer to a question can always be encoded as the fixed bytes 0xc00c - we don’t need to calculate it.
Going beyond that, when generating a simple answer, don’t generate an answer packet, but simply tack on the answer to the original question, and update the ‘answer count’.
Also, if we see we have an ‘instant answer’ available for a question, don’t bother to launch a whole ‘MThread’ to generate it, but return synchronously.
The upshot of all this is that we can now answer most questions in… 4 microseconds, down from 60. 15-fold speedups are rather rare usually.
We didn’t speedup everything that much though, only the majority of queries. However, even the uncached queries will benefit from the microsecond shaving performed earlier, and run around twice as fast.
I can’t wait to do a live benchmark on all this. I’m estimating we should now be able to do over 50000 “real” queries/second on a 3GHz P4, which would put us an order of magnitude above the open source competition, and even beat, by a large factor, the numbers I hear quoted for commercial alternatives. These are hard to compare as their numbers are under NDA.
It might not even be easy to generate that much testing data..
Will keep you posted!
Posted in Linux, PowerDNS, Netherlabs | 1 comment
Posted by bert hubert
Thu, 12 Oct 2006 19:55:00 GMT
Many thanks to my brother who read my previous post and promptly offered to procure new disks for me, they are now in production. Thanks Jaap!
C & C++
One of the things that is easy to forget about C++ is that, while not (really) a superset of C, it does offer the ability to call C functions from C++, and makes some pretty strong statements about the abilty to exchange data between the two languages.
C++ does not come with a set of ‘foundation classes’, and while the “standard template library” is strong on data structures, and algorithms to manipulate them, nothing is offered in the way of network communications infrastructure.
Many attempts have been made to rectify this situation, but these tend to be somewhat heavy handed, or overly complex.
Enter the ComboAddress. This C++ union is laid out in memory just like the venerable struct sockaddr_in, and through its second member, also just like struct sockaddr_in6.
The upshot is that we have a C++ union with interesting methods, that allows us to specify destination addresses, either IPv4 or IPv6, with ease, but that can also be passed to the standard Berkeley C socket functions!
These functions promptly forget they are passed a C++ union, and interpret their argument as a struct sockaddr family member.
For example:
int sock = socket(AF_INET, SOCK_STREAM, 0);
ComboAddress ca("127.0.0.1", 6666);
if (connect(sock, ca) < 0)
unixDie("connecting to server");
‘unixDie()’ is a simple function that uses strerror to throw a runtime_error with a descriptive error message.
If you are really paying attention, you might have noticed that the ‘connection’ function above is not a real C function, and you would be right. It is a very thin wrapper that saves some typing:
inline int connect(int fd, const ComboAddress& remote)
{
return connect(fd, (struct sockaddr*) &remote, remote.getSocklen());
}
Another example:
int fd = accept(sock, &ca);
if(fd >= 0)
cout << "Connection from " << ca <<endl;
The tiny bit of code that makes up the ComboAddress can be found in the PowerDNS Recursor source code. I find that it nicely bridges the vast power of the Berkeley sockets API, while taking a lot of the tedium out of calling the host of functions needed to convert between printable IP addresses, port numbers, and the actual stuff the sockets API expects.
And this is all possible because a bunch of guys with serious ‘Unix beards’ decided that C and C++ should remain family members. Thanks!
Posted in Linux, PowerDNS, Netherlabs | 7 comments
Posted by bert hubert
Fri, 06 Oct 2006 22:52:00 GMT
Well, I reported previously that the server that powers this blog fell 9 feet, and appeared to have survived? Since that event, one of the disks reported odd errors every once in a while, but those appeared to point to a bad cable. I replaced it, but no joy, problems remained.
So tonight I decide to back up that disk completely, and take it out of use. And lo, during the backup it decides to pack up! It made a noise like a passing moped, and ceased to work. Backup was almost entirely done.
I restored the backup to another computer and mounted it via NFS (over wifi no less!), and things (including this blog) are back in production again. I’ll have to buy new disks ASAP though.
PowerDNS RIPE presentation
RIPE was lots of fun, although my presentation did not go as well as I’d hoped. I’ve been distracted by grave medical problems in my family, which mean that I spend a lot of my time in the hospital. It might’ve been better to not do the presentation. Some people did tell me they enjoyed it though. Oh well.
For the first time, I’ve had the pleasure of answering a question from a webcam viewer! RIPE offers the great service that remote attendants can ask questions over IRC or Jabber, and a RIPE employee will then relay the question. A tremendous service!
Lunch at RIPE was fantastic, and it was very nice to meet many friends again. All in all a good day.
Posted in Linux, PowerDNS, Life | 7 comments
Posted by bert hubert
Sun, 01 Oct 2006 12:47:00 GMT
Quick post to say that at RIPE 53, I’ll be presenting about the PowerDNS Recursor and specifically its implementation of my Internet-Draft (“Draft RFC”).
More details in this post.
If you are at RIPE, come and say hello, or have an excellent Krasnapolski lunch with me!
Long standing bugs
Over the past few weeks some very long standing “low level irritation” PowerDNS bugs have been fixed. One of the things you learn during the maturation of software projects is that things are good once you start to get reports of obscure bugs, as this means that the big problems are out of the way!
Predictably, the bugs were related to the handling of rare errors, which also reinforces my belief that error handling of rare bugs tends to be very buggy, as these paths rarely get exercised, and when they do, people often don’t even notice the problem is more in the handling than in the error.
Don’t try to be too smart when dealing with errors!
Posted in Linux, PowerDNS, Netherlabs | 8 comments
Posted by bert hubert
Thu, 21 Sep 2006 21:16:00 GMT
Quick update on some small things.
PowerDNS
I managed to release PowerDNS Recursor 3.1.3 which must rank as one of the most succesful releases of PowerDNS ever, as I have had zero feedback, despite a large number of downloads. Most big deployments have switched over. There is still a very small trickle of odd crashes though, but they are so rare it is hard to pin it down to anything.
Wireless
Our new house has a lot going for it, except wiring possibilities. It might be possible to improve this, but right now I want nothing but the best and I’m not prepared to soil my house with badly laid cables. So it has to be wireless, which for fixed computers mostly means USB. After some searching and experimenting, I can report that zd1211 derived devices work really well using the Linux zd1211rw driver. Wireless reception depends a lot on RF conditions, having a USB receiver on a cable means you can move it around for the best reception.
The nice thing about the ZD1211 derived devices (I have two 3Com OfficeConnect adaptors) is that the authors of the driver are very approachable and work well with (and are in fact part of) the Linux kernel community. Unlike some.
New house
It still rocks, although we haven’t had much time to empty the last boxes and buy furniture that matches the quality of the house. Sadly, we are spending a lot of time in the hospital and taking care of related things.
Posted in Linux, PowerDNS, Netherlabs, Life | 9 comments
Posted by bert hubert
Fri, 08 Sep 2006 13:36:00 GMT
Programming is a lot of things. One of them is writing good error messages. We tend to think that errors are rare and this should of course be so. However, sometimes they are not, and in that case, good reporting is vital to quickly resolve the problem.
So, even though we should make sure errors do not happen, if they do, our error messages should be top notch.
About error messages
Purpose
For operators, they are vital aids in configuring software
For system adminstrators, they show which external problems need to be resolved (disk full, network down, etc).
Should a program crash, the authors often only have error messages as clues to why this happened. Many crashes are preceded by errors that are reported. A good error can help generate a bug fix.
Taxonomy of error messages
- Configuration problems, for example, looking for a file in directory A while it resides in directory B;
- Unavailable resources (disk full, out of memory), connectivity problems;
- Should Never Happen.
Configuration problems
These commonly occur while software is being installed and setup. Good error reporting is of utmost importance here, as it serves two purposes:
- Educating the operator about how the program functions;
- Explaining what needs to be fixed.
Ad 1, an error like “Can’t start frobnicator because the discombulator is not running” teaches the operator that a frobnicator needs a discombulator. This knowledge can of course also be gleened from the documentation, but in this case, repetition is a good thing.
Compare this error to “Can’t start process: Connection refused”, for example, and think about how helpful that is.
Ad 2, a report like “Can’t connect to product database using connection string ‘dbuser=john, dbname=changeme’: No such database” immediately tells the operator what he needs to know.
Unavailable resources
These typically occur while a program is already running and installed, but are nonetheless important. Do not log ‘Disk full’, but report ‘Disk full writing to ….’ so the operator knows which disk filled up. If a server could not be reached, log the IP address and possibly the name of the server. Any discrepancy between the two may point out a DNS configuration error.
Out of memory is typically very hard to deal with, except when something really odd was going on. A typical example is trying to allocate a ridiculous amount of memory because of an earlier error, in which case logging what memory was being allocated for might help debug the problem. It typically will not help the user of a program.
Should never happen
These are errors of the program itself. Programmers quite often test for impossible conditions, especially if they sense these might conceivably happen one day. An example might be a module that can only connect to IPv4 servers that gets confronted by an IPv6 socket, which in turn leads calls to determine the IPv4 remote address to fail.
It is tempting to be quite rude in these messages, or say stuff like “should never happen!!”, but resist these urges. One day a ‘should not happen’ error is going to be a vital debugging clue. These errors are rare, but it pays to go, well, the extra few yards to perhaps report “unexpected address family accepting connection!”.
Guidelines
An error message should contain:
- Who is reporting the error (which subsystem, which program, which module)
- The action that failed
- The subject of the action (a directory, a server, a port number, an IP address)
- As good an indication of the actual error as possible.
- Optional - what the program is doing about it
An excellent error message is:
Webserver can't serve page, error opening file '/var/www/index.html': Permission denied, reporting HTTP 404 error
Ad 1, it is tempting to include filenames, function names, and line numbers here. OpenSSL does this a lot, for example. However, almost none of your intended audience will be able to extract useful information from the fact that the error occurred on line 123 of ‘multiplexer.c’. Make sure the module means something to the operator. It may be as simple as the name of your program.
Ad 2, this helps the operator determine if this error might be the explanation of observed problems. An error like “Webserver failed to increase TCP buffer size, continuing with default” can immediately be ruled out as an explanation for why people can’t log in to their mail.
Ad 3, an error like “Can’t open file” on its own can mean many things. One of which might be that it is not reading the configuration file you think it is, and trying to open your index.html in ‘/usr/local/www’, and not in ‘/var/www’ like you thought you configured.
Ad 4, self explanatory. Take the trouble to convert error codes into strings. Many programmers may know what ‘errno = 111’ means ‘Connection refused’, but don’t count on your users knowing this.
Ad 5, this is a fine counterpoint to item 4. “Giving a 404” is very clear for any operator of a web server. Not all errors need a followup, so reporting what the program is doing about the error is not mandatory.
Conclusion
Good error messages can save your users many days of problems. And, suprisingly, you might yourself gain even more time - how well do you know the internals of your program after a few months?
So please please, both as a user and a progammer, I ask you, spend time on error messages!
Posted in Linux, PowerDNS, Netherlabs | 12 comments
Posted by bert hubert
Mon, 14 Aug 2006 16:46:00 GMT
As previously noted, Sun is making a SunFire T2000 server available permanently for PowerDNS development, which should be good for all PowerDNS users, and probably for Sun as well. With a big PowerDNS user we are currently investigating an interaction between PowerDNS, Solaris and its Completion Ports, which may turn out not to be a PowerDNS bug. So everybody wins.
The server is arriving tomorrow at the PowerDNS offices, we hope to have it up and running shortly.
Ok, some more spiffy ‘before and after’ graphs, this time from a Solaris 10 user:
The lower graph lists the number of queries per 5 minutes. In the lowest graph, it can be seen that just before and after the maintenance period (the white bit around Mon), the number of processed queries went up substantially.
The upper graph is a plot of the load average of the server in question, which can be seen to drop visibly after this period. It is probably best to concentrate on Friday vs Wednesday. Friday, which is non-PowerDNS, did 200kqueries in 5 minutes in peak, at a load of 1.75 at peak.
The next Wednesday, we see a peak of 300kqueries in five minutes, with a load of 0.6 at peak.
If we combine these numbers, we see the efficiency (queries divided by cpu load) go up by a factor of 4. It should be noted that this is a dual CPU machine, which explains why the load can exceed 1 when running a single name server.
Thanks to Jan Gyselinck for these graphs.
Posted in Linux, PowerDNS, Netherlabs | no comments
