Linux and the Enterprise

In "Windows NT vs. UNIX: Is One Substantially Better?" (December 1998), I included a sidebar titled "Linux and the Enterprise." This sidebar discussed the Linux kernel's shortcomings, including the lack of kernel-mode threads and the use of non-reentrant kernel code that affects Linux's ability to scale on multiprocessor systems. The Linux community's response to the sidebar has been vociferous, and most of the email I received contains two assertions: Linux does have kernel threads, and Linux 2.2 will remove multiprocessor scalability limitations. Although these assertions are true to a certain extent, significant problems with kernel threads and multiprocessor scalability in Linux 2.2 will prevent it from competing head to head with NT and Linux's UNIX cousins for enterprise applications. In this article, I'll describe several key areas in which Linux lacks maturity. I'll also discuss some powerful features that other OSs, including UNIX variants and NT, have adopted to improve scalability.

Let me state clearly at the outset that I don't intend to bash Linux in this article, nor do I intend to proclaim NT's superiority to Linux. I base the information I present on a thorough study of Linux 2.2, including its source code. I hope that by revealing these problems, I will encourage Linux developers to focus on making Linux ready for the enterprise. I also want to dispel some of the hype that many Linux users have uncritically accepted, which has given them the false impression that Linux is ready for enterprise prime time.

What Does "Enterprise-Ready" Mean?
Before an OS can compete in the enterprise, it must deliver performance levels on network server applications that rival or exceed the levels that other OSs achieve. Examples of network server applications include Web servers, database servers, and mail servers. OS and hardware vendors typically use results from industry-standard benchmarks such as Transaction Processing Council (TPC)-C, TPC-D, and Standard Performance Evaluation Corporation (SPEC) SpecWeb to measure proprietary OSs or hardware against other vendors' products. Vendors spend millions of dollars on benchmark laboratories in which they tune, tweak, and otherwise push state-of-the-art hardware and software technology to the limit. Enterprise customers, in search of a computing infrastructure that provides maximum capacity, often turn to benchmark results for guidance, and OS and hardware vendors holding benchmark leads take great pride in being king of the hill at any given time.

Thus, competing in the enterprise means removing every performance impediment possible. Overlooking even the smallest drag will create an opening that a competitor can drive through to obtain a valuable lead on a benchmark. What complicates the science of engineering an OS for the enterprise is that an OS might have subtle design or implementation problems that don't adversely affect performance in casual desktop or workgroup environments. Yet these problems can keep the OS from achieving competitive results in an enterprise-class benchmarking environment. A typical enterprise-application benchmarking environment includes dozens of powerful multiprocessor computers sending requests as fast as they can over gigabit Ethernet to an 8-way server with 4GB of memory and hundreds of gigabytes of disk space.

Efficient Request Processing
Network server applications typically communicate with clients via TCP or UDP. The server application has either a published or well-known port address on which it waits for incoming client requests. When the server establishes a connection with a client or receives a client request, the server must then process the request. When the server application is a Web server, the Web server has to parse the HTTP information in the request and send requested file data back to the client. A database server application must parse the client's database query and obtain the desired information from the database.

For a network server application to scale, the application must use multiple kernel-mode threads to process client requests simultaneously on a multiprocessor's CPUs. The obvious way to make a server application take advantage of multiple threads is to program the application to create a large pool of threads when it initializes. A thread from the pool will process each incoming request or series of requests issued over the same client connection, so that each client request has a dedicated thread. This approach is easy to implement but suffers from several drawbacks. First, the server must know at the time it initializes what kind of client load it will be subject to, so that it can create the appropriate number of threads. Another drawback is that large numbers of threads (an enterprise environment can produce thousands of simultaneous client requests) can drain server resources significantly. Sometimes, resources might not be adequate to create all the threads the application wants to create. Furthermore, many threads actively processing requests force the server to divide CPU time among the threads. Managing the threads will consume precious processor time, and switching between competing threads introduces significant overhead.

Because a one-thread-to-one-client-request model is inefficient in enterprise environments, server applications must be able to specify a small number of threads in order to divide among themselves the processing for a large number of client requests. Where this client-multiplexing capability is present, no one-to-one correspondence between a thread and a client request occurs. Neither does a one-to-one correspondence between a client request and a thread occur—one thread might share a client request's processing with several other threads. Several OS requirements are necessary for a client-multiplexing server design to be feasible. The first requirement is that a thread must be able to simultaneously wait for multiple events: the arrival of a new client request on a new client connection, and a new client request occurring on an existing client connection. For example, a Web server will keep multiple browser connections open and active while accepting new browser connections as multiple users access a Web site the server manages. Connections between a browser and the server can stay open for several seconds while large files transmit over a connection, or while the browser requests multiple files over the connection.

The second requirement is that the threads must be able to issue asynchronous I/O requests. Asynchronous I/O is an OS-provided feature whereby a thread can initiate I/O and perform other work while the I/O is in progress—the thread can check the I/O result at a later time. For example, if a server thread wants to asynchronously read a file for a client request, the thread can start the read operation and wait for other client requests while the read is in progress. When the read completes, the system notifies a thread (not necessarily the thread that began the read operation) so that the thread can check the I/O's status (i.e., success or failure) and whether the I/O is complete.

Without asynchronous I/O, a thread initiating an I/O operation must wait while the operation takes place. This synchronous I/O causes multiple-client-per-thread server designs to perform poorly. Because such server designs designate limited thread pools, taking threads out of commission to perform I/O can lead to a situation in which no threads are available to accept new client requests or connections. In such a case, a multiprocessor's CPUs might remain idle while client requests sit backlogged. Worse, the server might never have a chance to service client requests, because the client might stop waiting for the server. Figure 1 contrasts asynchronous and synchronous I/O.

Linux and Request Processing
Unfortunately, Linux 2.2 doesn't satisfy either client-multiplexing server-design requirement: Linux 2.2 cannot efficiently wait for multiple events, and it doesn't support asynchronous I/O. Let's look more closely at each of these concerns.

Linux provides only one general API to server applications that want to wait on multiple requests—the select API. Select is a UNIX system call that has been present in every UNIX release since the OS's initial development. Select is one of the OS interface functions that has become part of the POSIX standard for UNIX API compatibility. One reason that the Linux select implementation is not an acceptable function for waiting on multiple events is that the system uses select to notify all threads that are waiting on the same event whenever the event occurs (e.g., the arrival of a request from a new client). Notifying multiple threads in this way degrades server performance: Only one thread can handle the new request or connection, and the other notified threads must return to a state of waiting. In addition, synchronization causes overhead as the threads agree among themselves which one will service the request. Other secondary overhead results when the OS divides CPU time among the threads it has needlessly notified. This kind of limitation forces a network server application to designate only one thread to wait for new incoming client requests. This thread can either process the new request itself, waking up another thread to take over the role of waiting for new requests, or the original thread can hand the request off to a waiting thread. Both alternatives add overhead, because every time a new client request arrives, the waiting thread receives notification and must then notify another thread.

If Linux provided some additional application support, the OS could wake up only one thread. For example, an application could specify that even though multiple threads are waiting for a particular event to occur, the application wants only one of the threads to receive notification for each occurrence of the event. NT provides such support for its waiting functions (NT server applications do not typically use select, although NT implements the select call for compatibility with the POSIX standard) to allow multiple threads to efficiently wait for incoming client requests.

Select suffers another serious problem: It doesn't scale. A Linux application can use select to wait for up to 1024 client connections or request endpoints. However, when an application receives notification of an event, the select call must determine which event occurred, before reporting the event to the application. Select uses a linear search to determine the first triggered event in the set the application is waiting for. In a linear search, select checks events sequentially until it arrives at the event responsible for the notification. Furthermore, the network server application must go through a similar search to determine which event select reports. As the number of events a thread waits for grows, so does the overhead of these two searches. The resulting CPU cost can significantly degrade a server's performance in an enterprise environment.

NT incorporates a unique feature known as completion ports to avoid the overhead of searching. A completion port represents a group of events. To wait on multiple events, a server associates the events with a completion port and waits for the completion port event. No hard upper limit exists on the number of events a server can associate with a completion port, and the server application need not search for which event occurred—when the server receives notification of a completion port event, the server also receives information about which event occurred. Similarly, the kernel doesn't perform searches, because the kernel knows which events the system associates with specific completion ports. Completion ports simplify the design and implementation of highly scalable server applications, and most enterprise-class NT network server applications use completion ports.