Monday, October 28, 2013

Web Servers and the Zen of Non-blocking I/O

This post started as a short introduction to the first one in a mini-series of head-to-head comparisons of three non-blocking I/O web servers. And then things got out of control. Being as it is, I convinced myself that a bit more elaborate introduction is in order. Now comes the hard part, to convince everyone else.

Web servers
Web servers are complicated machines, both hardware and software-wise. The illustration below shows block diagram of a typical web server based on LAMP (Linux Apache MySQL/MariaDB) Perl/PHP/Python) bundle (or stack as some prefer to say).

LAMP bundle web server

Told' ya it was complicated, didn't I? And this is just a block diagram. There are variants of this stack, such as WAMP (Windows Apache MySQL/MariaDB) Perl/PHP/Python). By the way, these bundles are really easy to install. Companies like TurnKey Linux offer a number of software appliances based on Linux in number of formats, including the virtual machine ready ones. All you have to do is download and start VM. That is exactly what hosting companies do. Except that they, presumably, package their own bundles.
Luckily for us, we are going to concentrate only on the little box on the left with the title “Web server”. There are two types of web server software. The one on the picture, Apache, is so called user-mode web server, meaning that it runs in user-space like any other application. The other type is known as in-kernel (or kernel-mode) web server, and the representative is Microsoft IIS. The in-kernel web server software is on a first-name basis with the computer hardware and that supposedly makes it faster than user-space counterparts. The downside is that they are tied to single operating system and can not work on any other. On the other hand, user-space web server software has to compete for the hardware resources with all the other running applications (processes), and that is why they sometimes can be slower. The good thing is that they are operating-system-free, like in LAMP and WAMP.
Still, not all web servers are made equal. Some are built for speed and others for features. But, what interests us here is how they handle I/O.

Blocking and non-Blocking I/O
There is a lot of theory behind handling I/O operations. It involves queueing theory, and it has a lot to do with stochastic processes for which you need to study Markov chains. And that is just the beginning. Not to mention that the whole shebang in most cases is just a model (read: approximation), and since this is a blog and not an online university, we'll revert to analogy.
OK, you are very hungry and looking for a place to eat. In this unhappy hour you are facing two possibilities: fast-food restaurant to your left and a full service restaurant to your right. If you choose to enter the fast-food restaurant, doesn't really matter if it's Windows, Apple or Linux chain, you will see a number of cash registers and a queue in front of each. If you are disrespectful to Murphy's laws, you'll even stop and thinker which queue to join, which would be a great mistake (both theoretically and practically). At the head of each queue there is a customer that is being served at the moment you entered the restaurant, and the next customer in each line can not order until the previous one is finished with his/hers. In case someone in the queue has a large family, you will wait forever for your bite (or Mega Byte). This is blocking I/O.
It is obvious that waiting time here is very susceptible to the number of requests (customers). Also, the system can not prioritize between someone who wants to order just one item and someone else who is ordering full tray. Adding resources (cash registers in our example), is an obvious remedy to the situation. The problem is that it's costly, and a balance has to be made between rush (peak) hour and the off-hour. No one likes to see his expensive assets being idle most of the day and working their normal capacity during peak hours. Preferred situation for the owner is that the system is at nominal capacity most of the day, and in overdrive at rush hour, even at the risk of losing few customers. Technology and economy hand in hand, as always. On the other hand, Windows and Apple chains of restaurants opted for maximizing customer experience by providing abundant resources. We all know on whose expense.
Waiting in the queue made you even more hungry, so you switched to the restaurant across the street. In there, you click, sorry point your finger, at the menu entry, especially in a French restaurant (hoping you did not order something inedible). The waiter takes your order to kitchen and it gets prepared there. In the kitchen, orders are being processed in parallel (more or less), so that orders, no matter how big or small, do not wait for previous others to be finished. This is non-blocking I/O.
The concept of non-blocking I/O allows you to introduce various scheduling policies for performance fine-tuning and enhancement (it applies to restaurant as well as web server). The article on queueing theory lists some of them:
Processor sharing
Service capacity is shared equally between customers.

Customers with high priority are served first. Priority queues can be of two types, non-preemptive (where a job in service cannot be interrupted) and preemptive (where a job in service can be interrupted by a higher priority job). No work is lost in either model.

Shortest job first
The next job to be served is the one with the smallest size

Preemptive shortest job first
The next job to be served is the one with the original smallest size

Shortest remaining processing time
The next job to serve is the one with the smallest remaining processing requirement.
Of course, adding resources also helps here. In addition, operating system could be optimized (up to a point) for better cooperation with queueing mechanism for further improvements.

C10K Problem
Some think that the C10K is so last decade, and are targeting C10M problem already. The C10k refers to the problem of optimizing network sockets to handle ten thousand connections at the same time. Relatively few web servers address this problem and, according to this article on Wikipedia, node.js is one of them., a library for node.js, is written to help address this specific problem. But, since this topic is not the focus of this post, I shall return to it in some future one.

From the illustration above, we can see that there are three layers that affect the performance of a web server from the prospective of handling I/O operations. These are: hardware, operating system and application software.
Hardware is not a bottleneck anymore. 64 bit CPUs in gigahertz region, very fast RAM in gigabytes and discs in terabytes o or petabytes. No, we have to look elsewhere for performance improvements.
Operating systems, or more precisely, server operating systems are sort of a problem in respect to handling I/O. In use today are general purpose server operating systems. Even worse, they are general purpose operating systems slightly modified to operate as servers. Unix, for instance, was originally designed to act as a control system for a telephone network. Not for handling data, telephone network took care of that. Another thing, what we are forgetting is that server in the beginning meant file server. Novel NetWare was file server. Actually, Netware was the file server. It was not built as a software layer on top of general purpose OS, but a special purpose OS without time sharing. NetWare had its own file system NWFS. What it did not have was preemption, virtual memory and, heaven forbid, graphical user interface. While we are at it, one of the biggest mysteries of the trade is why certain server OS from certain very large software company has graphical user interface. Even bigger mystery is why the same large software company decided, in the version 2012 of the said server, to introduce the option to switch it off! Performance issues? Welcome back to NetWare. A bit simplified version goes like this: Novel NetWare had one process which used round-robin scheduling to serve files to its users. If you wanted a file from server, the scheduler placed you in the list along with others. Then NetWare would pitch file chunks to users, as a poker dealer does to players at a poker table. Once you received the whole file, you were out of the list. Using this technique and few others, like scheduling policies similar to the ones mentioned before, NetWare outperformed competition's file servers of the time by 5:1 or even 10:1. In the meantime, general purpose operating systems improved, and hardware accelerated to the extent where OS inefficiency is largely compensated by hardware speed. Still, NetWare concept is hard to beat.
What is so wrong with general purpose OS dubbing as file and/or web server? Preemptive multitasking provides every user the feeling that his program is the only one running on the computer. This is done by forcing (preempting) processes to share hardware resources. For their own good, of course. The outcome is that below the surface of this cyber-democracy rages a battle for every CPU cycle and every block of data. As a result we can have resource starvation which can leave our web server software at the wrong end of the stick. Users of such servers, on the other hand, have completely unfounded impression that processes that handle networking and I/O should be given advantage. Web servers resemble a patient whose psychiatrist said to him: “You have a very strong ego, but it has no foundation in reality”.

And how exactly are we enlightened by this development? Obviously, general-purpose preemptive-multitasking operating systems with thin layer of web server software can have serious problems handling large number of I/O requests. But, it is hard to believe that some new cooperative-multitasking operating system will appear as a reincarnation of beloved Novel NetWare, and put our harts and minds at ease. So, what can we do about it? As always, if you want a thing done well, do it yourself. Write your own web server that takes the I/O handling load off the operating system. In the next few post we'll take a look at software platforms which enable you to do just that.