See discussions, stats, and author profiles for this publication at: [Link]

net/publication/2610686

The Linux Scalability Project

Article · December 1999

Source: CiteSeer

CITATIONS READS
4 432

4 authors, including:

Peter Honeyman Niels Provos

University of Michigan 63 PUBLICATIONS 6,799 CITATIONS
88 PUBLICATIONS 3,120 CITATIONS
SEE PROFILE
SEE PROFILE

All content following this page was uploaded by Peter Honeyman on 23 July 2013.

The user has requested enhancement of the downloaded file.

 CITI Technical Report 99-4

The Linux Scalability Project

Peter Honeyman
Chuck Lever
Stephen Molloy
Niels Provos

linux-scalability@[Link]
[Link]

ABSTRACT

The Linux Scalability Project is adapting Linux for use in enterprise-scale networking
environments. We focus on kernel algorithms and data structures that scale poorly when
presented with thousands or tens of thousands of simultaneous service requests. For ex-
ample, we uncovered a “thundering herd” problem in the accept system call. A few
dozen lines of code corrects this behavior to awaken only one, instead of all, waiting
threads. This small change improves macro-benchmark performance by over 50% on
high-performance hardware.
Other examples include improving poll performance, adding read-ahead support for
sendfile and mmaped files, and identifying areas of significant kernel SMP lock con-
tention. The project is also implementing an open source, reference implementation of
NFSv4, a highly scalable evolution of the popular distributed file system.
Building relationships between academia, industry, and open source communities is a
primary goal of our effort. While our research-oriented, “cathedral” approach is some-
times at odds with the “bazaar” style of software development prevalent in the Linux
community, we find ways to build reputation and influence among Linux kernel develop-
ers and the growing Linux commercial sector.

November 11, 1999

Center for Information Technology Integration

University of Michigan
519 W. William St.
Ann Arbor, MI 48103-4943
 The Linux Scalability Project
Peter Honeyman
Chuck Lever1
Stephen Molloy
Niels Provos

The specific areas in which we are interested are:

Introduction
• Reliability — improving system recovery
The Linux operating system is an open-source mechanisms, backup/restore, and fault-
POSIX-compliant operating system that runs par- tolerance.
ticularly well on commodity Intel-compatible PC
hardware. Linux is not only free, it also happens • Performance — getting the most out of high-
to be very stable, crashing infrequently in a vari- performance systems: fast CPUs, RAID sys-
ety of environments. As such, it is widely de- tems, and high-speed networking such as
ployed as a platform for network services, e.g., ATM and gigabit Ethernet.
mail and web servers. Despite high acclaim and
• Scalability — improving system throughput,
ultra-stability, Linux remains a work in progress:
overload characteristics, relieving architec-
Linux continues to be improved in many ways to
tural constraints, and enhancing administra-
better position it for enterprise service.
tion of large installations.
For peculiar reasons, Linux has focused on the
desktop, paying special attention to hardware • Security — improving resistance to network
compatibility, user interfaces, and application and local attacks, reducing or eliminating the
development. These emphases are critical to Li- risk of buffer overflows, continuous security
nux’ broad acceptance by a worldwide community testing of all bundled applications and utili-
of users, but have little influence on its usability ties.
or appropriateness in an enterprise service envi- • Standards compliance — assuring that net-
ronment. The Linux Scalability Project (LSP) at work implementations are well behaved and
the University of Michigan’s Center for Informa- that useful and common APIs maintain stan-
tion Technology Integration (CITI) is adapting dards compliance (e.g., POSIX).
Linux to meet the needs of enterprise-scale Inter-
net service providers. • Quality assurance — reducing defect rate
(and defect re-introduction).
LSP is specifically interested in finding immediate
and practical improvements to Linux that increase Improving existing features and adding new ones
the performance of commercial enterprise servers, to an operating system to boost application-
such as Sun-Netscape’s iPlanet server suite (a specific performance via independent research is
collection of web, directory, messaging, and secu- an opportunity afforded by Linux’ open source
rity services). To achieve our goals, our strategy distribution. A major challenge for LSP is to find
is to select a handful of areas of potential im- the right ways to work with Linux developers so
provement to the Linux operating system, priori- that our kernel improvements can be easily incor-
tize the areas based on their estimated improve- porated into the baseline Linux source code. In
ment pay-off versus their implementation cost, the following sections, we outline the areas where
then implement the highest priority improve- we have had the most success and those where we
ments. We evaluate each improvement using intend to continue our efforts. In addition to tech-
server and OS benchmarking methodologies that nical milestones, we discuss building collabora-
are as close to standard as possible to allow scien- tive relationships among open source advocates,
tific comparison with other research in this area. and with system and software vendors.

1
Chuck Lever is a Sun-Netscape Alliance employee resident at CITI.

– 1–
Prioritizing our work We want to see our patches applied to the distrib-
uted Linux kernel. Our improvements lose value
To decide which improvements provide the most if they have to be installed or included separately.
benefit, we assess potential improvements in the
following categories. • Coordination efforts
• Measurable throughput, performance, scal- These efforts help build collaborative relation-
ability improvements. ships among research and corporate entities to
forward the mission of our research.
These are the most important gains we hope for.
We can estimate these benefits by using research • Input from industry partner server product
of preexisting literature and simple microbench- teams
marks. We consult with technical staff among our indus-
• Added stability during overload. try partners, such as Netscape’s server product
teams, to itemize, prioritize, and coordinate LSP
While some improvements may provide little, plans and efforts.
none, or even slightly negative performance or
scalability gains, they might offer significant en- • Collaboration with Linux development com-
hancements of system behavior during overload munity
conditions. We cooperate with members of the Linux devel-
• Synergy with other potential improvements. opment community to determine the current state
of Linux, and determine how that work affects
Several potential improvements to Linux can be high-end server performance. We offer develop-
accomplished in different ways. Choosing to im- ment resources for work on scalability and per-
plement one improvement may make others much formance issues.
simpler to implement.
• Estimated resource costs. Network server performance issues
We want to make sure the work we plan is feasi- In this section, we summarize some of the per-
ble for our developers, and can be completed suc- formance and scalability issues we have ad-
cessfully with the resources available to CITI. dressed.
• Estimated complexity. File descriptor scalability
Complexity relates directly to the amount of test- As the number of network users and clients grows,
ing required, for example, and increases the likeli- the number of concurrent open file descriptors on
hood that improvements may introduce new bugs. network servers can easily exhaust system limits.
We are also concerned about introducing im- The number of file descriptors maintained on
provements that require significant changes to servers often grows proportionally with the num-
applications, especially changes that are not ber of concurrent clients served. For example,
backward compatible. IMAP servers need to maintain a socket to con-
• Potential introduction of security or scalabil- nect with each client, and an open file descriptor
ity problems. for each client's mailbox. Until recently, a sys-
tem-wide limit of 1024 file descriptors prevented
While an improvement might be easily imple- such a server from supporting more than about
mented, it also might introduce other problems 500 concurrent users.
that make it unsuitable, such as unstable overload
behavior or unacceptable security exposures. Although the file descriptor limit was extended to
4096 open files, vestigial limits to poll and se-
• Amount of server re-engineering required. lect precluded their use with more than 1000
We favor work that requires few modifications to file descriptors. When calling poll or select
system interfaces. This lets everyone take advan- each process must allocate a fixed size
tage of our changes immediately. wait_table that can be used by the underlying
device drivers to store information about the proc-
• Expectation of acceptance by Linux develop- esses that need to be awakened when an event
ers.

– 2–
occurs. Each device driver adds information to Hints for select and poll
the wait_table via the poll_wait interface.
We extended the interface to allocate more storage A process registers interest in file descriptor
space dynamically for the wait_table if events with the poll system call. The kernel
needed. passes this information to all concerned device
drivers and puts the process to sleep until a rele-
We also encountered a performance problem for vant event occurs. Even though the status of only
applications that use a large number of file de- one file descriptor might have changed, when the
scriptors. In applications with many open file process awakens, poll is forced to examine all
descriptors, the open system call searches a lin- of the selected file descriptors for status changes.
ear list in the form of a single bitmap to find a free
file descriptor. The result is that the time to find It would be useful if the device drivers could tell
an open file descriptor increases linearly with the — hint — each process as to which file descrip-
number of open files. Linux and *BSD memorize tors changed their status. To make this possible,
the last closed file descriptor, which allows a sin- we extended poll to maintain a list of selected
gle open to return quickly. However, when file descriptors and their associated events and
open and close system calls are interleaved, processes. When a relevant event occurs, e.g., an
performance degradation is apparent. interrupt, the driver searches this list to find the
associated process and file descriptor. Poll then
A solution to this problem was suggested by sets the bitmap of changed file descriptors di-
Banga et al. [BM, BDM]: instead of using a single rectly, obviating the need to check each driver
bitmap, a two-bitmap structure is used to maintain individually.
the list of free file descriptors. The first bitmap
points to free entries in the second bitmap, and the Because in general the hinting system requires
second bitmap points to the free file descriptors each device driver to be rewritten, each device
themselves. The graph shown below shows the driver is given the ability to indicate whether it
result of a micro-benchmark that opens 100,000 supports hinting. This way, only the essential
file descriptors and measures the time between drivers — generally speaking, the network devices
closing the first and the nth file descriptors and — need to be modified.
two subsequent calls to open. There is a clear
difference between the single bitmap allocation of Memory management
file descriptors and the two-bitmap allocation. Server applications make heavy use of shared
regions, anonymous maps, and mapped files.
Special features like locking down regions so they
aren't swapped, fast mmap, support for allocating
very large shared regions and memory areas, and
efficient memory allocation are especially useful.
Many modern network servers use multithreading
to take advantage of I/O concurrency and multiple
CPUs. As network services scale to tens of thou-
sands of clients per server, their architecture de-
pends more and more on the ability of the under-
lying operating system to support multithreading
efficiently. This especially true for library rou-
tines that are provided not by the applications'
designers, but by the OS.
An example of a heavily used programming inter-
face that needs to scale well with the number of
threads is the memory allocator, known in UNIX
as malloc. Malloc makes use of several im-
portant system facilities, including mutex locking
and virtual memory page allocation. Thus, ana-
lyzing the performance of malloc in a multi-

– 3–
threaded and multi-CPU environment can provide processes large, pageable virtual memory areas.
important information about potential system inef- Optimizing the allocation of anonymous maps and
ficiency. Finding ways to improve the perform- reducing the overhead of these calls by having
ance of malloc can benefit the performance of malloc ask for larger chunks at a time are two
any sophisticated multithreaded application, such possible ways of helping performance in this area.
as network servers.
Benchmark description
To test malloc’s ability to divide its work effi-
We wrote a simple multithreaded program that
ciently among multiple threads and processors, we
invokes malloc and free in a loop, and timed
wrote a simple benchmark that drives multi-
the results on a dual processor 200Mhz Pentium
threaded loads. In the next subsections, we dis-
Pro with 128Mb of RAM and an Intel i440FX
cuss initial results of the benchmarks and analyze
mainboard. The operating system is Red Hat 5.1,
the results with an eye towards identifying areas
which comes with glibc 2.0.6. We replaced the
of the implementation of malloc and Linux it-
kernel with 2.2.0-pre4. Gettimeofday's reso-
self that can be improved.
lution on this hardware is 2-3 microseconds.
A look at glibc’s malloc During the tests, the machine was at runlevel 5,
but was otherwise quiescent.
Most modern distributions of Linux use glibc ver-
sion 2.0 as their C library. Glibc's implementers To measure the effects of multithreading on heap
have adopted Wolfgang Gloger's ptmalloc accesses, we compare the results of running this
[WG] as the glibc implementation of malloc. program on a single process with the results of
Ptmalloc has many desirable properties, in- two processes running this program on a dual
cluding multiple heaps to reduce heap contention processor, and one process running this test in two
among threads sharing a single C library invoca- threads on a dual processor. This answers several
tion. questions:

Ptmalloc is based on Doug Lea's original im- • How well does thread scheduling compare
plementation of malloc [DL]. Lea's malloc with process scheduling?
has several goals, including improving portability, • How well does more than one thread in a pro-
space and time utilization, and adding tunable cess utilize multiple CPUs?
parameters to control allocation behavior. Lea is
also greatly concerned about software re-use, be- • How well does malloc scale with multiple
cause very often, application developers, frus- threads accessing the same library and heaps?
trated by inappropriate behavior of memory allo-
• How heavyweight are thread mutexes?
cators, often write “yet another” specialized mem-
ory allocation scheme rather than re-use an exist- If a malloc implementation is efficient, we ex-
ing one.2 pect that the two-thread run will work as well as
the two-process run. Typically, we find that a
Gloger's update to Lea's work retains these desir-
poorly performing implementation uses a signifi-
able behaviors, and adds multithreading ability
cant amount of kernel time with a high context
and some nice debugging extensions. Nonethe-
switch count as a result of contention for mutexes
less, because the C library is pre-built on most
protecting the heap and other shared resources.
Linux distributions with debugging extensions and
tunability compiled out, it is necessary to rebuild We are also interested in the behavior of malloc
the C library or pre-load a separate version of and the system on which it's running as we in-
malloc to take advantage of these features. crease the number of threads past the number of
Ptmalloc also makes use of both mmap and physical CPUs present in the system. We con-
sbrk on Linux when allocating arenas. Of jecture that the most efficient way to run heavily
course, these system calls are essentially the same loaded servers is to keep the ratio of busy threads
under the covers, using anonymous maps to offer to physical CPUs as close to 1:1 as possible. We
would like to know the penalty as the ratio in-
creases.
2
One of the authors of this paper encountered this
frustration many, many years ago; see [HB].

– 4–
For each test, the benchmark makes 10 million constant slope of 1/N * M, where N is the number
balanced malloc and free requests. It does of processors (N = 2 in our case) and M is the
this because: number of seconds for a single thread run (23 sec-
onds in our case).
• Increasing the sample size increases the sta-
tistical significance of the average results. Next, we examine the linearity over a much
greater number of threads. This tells us how the
• Short timings are hard to measure precisely, library scales with increasing thread count.
so running the test over a longer time allows
elapsed time measurements with greater pre- The graph shows that the increase in elapsed time
cision. is approximately linear with increasing thread
counts for counts much larger than the number of
• Start-up costs (e.g., library initialization) are configured physical CPUs on the system.
amortized over the huge number of requests.
Specific tests and results
First, we compare the performance of two threads
sharing the same C library with the performance
of two threads using their own separate instances
of the C library. We hope to learn whether shar-
ing a C library (and thus “sharing” the heap)
scales as well as using separate instances of the C
library. On our host, the threaded test did almost
as well as the process test, losing only about 10%
of elapsed time. This indicates that malloc
scales well as the number of threads sharing the
same C library increases.
Next, we examine the behavior of malloc as we
increase the number of working threads past the

Discussion
We are satisfied that the malloc implementation
used in glibc 2.0 effectively handles increasing
numbers of threads with low overhead, even for a
comparatively large number of threads. We found
performance to respond linearly to increased of-
fered load.
In the future, we'd like to examine the multi-
threaded capabilities of a commercial vendor's
malloc implementation, e.g., Solaris 2.6 or So-
laris 7. Initial tests on single and dual processor
Ultra 2s indicate that the Solaris pthread imple-
mentation serializes all of the threads created by
the malloc-test program.
We are also examining the performance relation-
number of physical CPUs in the system. The re- ship between the C library's memory allocator and
sults are summarized in the following graph. OS primitives such as mutexes and sbrk. We
So far, so good: the average elapsed time in- recently removed a global kernel lock from sbrk,
creases linearly with the number of threads, with a allowing greater concurrency in memory-intensive

– 5–
multi-threaded applications. (This patch is incor- designed to provide a consistent workload across
porated in the 2.3.6 kernel.) runs, and to error-check the output of each script
to quickly catch problems.
We would like to study the effects of allocating in
one thread while freeing the same area in another. It became quickly apparent that running S-DET
In addition, we would like to investigate whether with a large number of scripts could reproduce the
memory allocator performance benefits from performance degradation scenario quickly, as il-
knowledge about level-2 cache and main memory lustrated in the following graph, representing per-
characteristics. Page coloring or alignment re- formance of consecutive runs of 128 scripts on
finements could help promote cache-friendly heap Linux 2.2.3.
storage behavior.

Buffer management
This section describes a bug in the buffer cache
that was identified and corrected by LSP staff.
Recent releases of Linux feature the ability to self-
tune system parameters, such as buffer cache size,
according to offered system load. Part of this self-
tuning ability is implemented in a varying parti-
tioning of physical RAM between the traditional-
style buffer cache and the virtual memory system.
However, allowing the buffer cache to grow and
shrink on-demand introduces some interesting
design problems, and, in this case, a significant
bug.
In this section, we describe the bug and how it
was identified. We provide performance meas-
urements to show the significance of the problem.
Finally, we detail the fix as we proposed it and as
it was adopted into the Linux kernel, and report on
the performance improvement.
We observed (using vmstat) that the buffer
Along with several other developers, we noticed cache continues to grow without bounds during
that early releases of Linux 2.2.x were experienc- the benchmark runs. Eventually, the buffer cache
ing a memory leak of some kind under heavy file causes the system to begin flushing pages unnec-
system and VM loads. Symptoms included poor essarily. This pressure on the VM system results
system performance after copying or removing in, among other things, pages being stolen back
large files, sporadic “out of memory” errors, and from the buffer cache. Remarkably, the buffer
performance degradation on long-running jobs. cache doesn't have any aging or replacement pol-
To stress the system and help identify the cause of icy, so any buffer can be stolen, even buffers for
the problem, we used the SPEC S-DET bench- heavily-used data. The system doesn't usually
mark suite [SDM] to generate significant loads on recover from this condition until it is rebooted.
a 4-way Dell PowerEdge 6300-450 with 512M of
RAM and an 18G Ultra2 LVD SCSI hard drive. Other features of this scenario include low CPU
utilization and a large number of blocked proc-
The SPEC S-DET benchmark consists of a script esses. The size of the buffer cache and the size of
that is designed to emulate a software developer the free memory list are continually fluctuating,
by running programs such as cc, nroff, cpio, suggesting a high flow of pages into and out of the
and ed. The software developer workload buffer cache.
stresses many aspects of an operating system, in-
cluding the file and VM subsystems. Multiple After some number of unsuccessful guesses at
concurrent instances of the script can run to what might be the problem, it was noticed that the
simulate reproducible and increasing amounts of rate at which blocks were being read was low
system load. The S-DET benchmark is carefully during benchmark runs with good performance,

– 6–
but increased significantly during poorly per- The following graph shows that performance is
forming runs. This suggested that the buffer flat for each consecutive run of the 128-script
cache was somehow becoming ineffective over benchmark.
time. Linux prioritizes read requests over write
requests, assuming that a read request is usually
more time-critical, so the elevated read rate inter-
feres with disk write bandwidth.
LSP staff and Andrea Arcangeli, a European Li-
nux developer working for SuSE, independently
discovered that buffers were being orphaned.
Many buffers were ending up unlinked from the
hash, so that they would not be found during a
subsequent find_buffer request. Each time a
buffer is orphaned, another buffer is allocated for
the same logical block of data, and another read
operation is requested to pull the same data in
from the disk. This also causes the buffer cache to
grow in size as more and more copies of the same
data blocks appear in the cache.
A review of the source that manages buffers (li-
nux/fs/buffer.c) revealed that the bfor-
get function, used by ext2 when files are trun-
cated or deleted, removes buffers from the hash The corrected version of bforget is contained
table, but then abandons them without recycling in Linux 2.2.5 and later.
them.
In Linux 2.0, refile_buffer was probably Kernel hash table analysis
responsible for ensuring that the buffer was prop- Hash tables are a venerable and well-understood
erly added to the free list. However, rewrites of data structure favored for high-performance appli-
the VM and buffer cache subsystems in Linux cations because of their excellent average search
have since removed that functionality from re- time. The Linux kernel relies on hash tables to
file_buffer. manage pages, buffers, inodes, and other data ob-
jects. Several hash tables in the Linux kernel are
A patch was proposed by LSP and Andrea Arcan-
in performance-critical paths. As hardware size
geli, subsequently modified slightly by Linus
and offered load increases on servers, proper allo-
Torvalds. The revised bforget ensures that a
cation of resources to kernel hash tables becomes
buffer's usage count is zero before inserting it into
important to overall system performance and scal-
the free list. In general, a non-zero usage count
ability.
prevents try_to_free_buffers from re-
leasing pages containing buffers. If buffers with For example, on a small machine with 32M of
non-zero usage counts do appear in the buffer free physical RAM, a page cache hash table with 2048
lists, they are skipped over by buckets is probably enough to hold all the pages
try_to_free_buffers in favor of buffers that could be hashed, in chains of less than three.
that may still have useful data. Having a large However, this hash table couldn't possibly hold all
number of these buffers in the free list can even the pages on a large machine with, say, 512M of
cause a severe system-wide memory shortage. physical RAM and continue to maintain short
chains to keep lookup times quick. This is an
The revised bforget corrects the performance issue for older Linux kernels because these hash
degradation observed in the buggy version. tables are statically allocated in fixed sizes for all
Vmstat confirms that CPU utilization is maxi- hardware types.
mized, few processes are blocked, block read rate
is low, and the buffer cache size expands to a rea- It is important to understand why hash tables are
sonable working set, then remains at a steady size. used in preference to a more sophisticated data

– 7–
structure, such as a tree. Insertion into and dele- using dynamic table sizes determined by hardware
tion from a hash table is O(1) if the hashed objects characteristics, while keeping the simplicity and
are simply maintained in LIFO order in each compute-efficiency of existing hash functions.
bucket. A tree insertion or deletion is O(log(n)).
There are four hash tables we were especially in-
Hash table lookup operations are often O(n/m)
terested in measuring:
(where n is the number of objects in the table and
m is the number of buckets), which is close to • page cache
O(1), especially when the hash function has
spread the hashed objects evenly through the hash • buffer cache
table and there are more hash buckets than objects • inode cache
to be stored. Finally, if we are careful about our
hash table design, we can keep the average lookup • dentry cache
time for both successful and unsuccessful lookups In Linux, the page cache holds data in active use
low — i.e., less than O(log(n)) — by using a large by processes. The buffer cache holds data moving
hash table and a hash function that does a good to and from disk. The inode cache holds VFS
job of distributing the hash key. inodes (file system metadata), and the dentry
Hash tables depend on good average behavior to cache is a tree representing the file system direc-
perform well. This average behavior relies on the tory structure. Our analysis shows that increasing
actual input data more often than we like to admit, the size of these tables significantly improves
especially if simple shift-add hash functions are scalability on large-memory hardware.
used. Therefore, statistical examination of spe- We also studied hash function behavior and com-
cific hash functions, in combination with specific pare the results of benchmarks where we fix the
real world data, can reveal surprising behavior, size of the hash table but vary the hash function.
and can expose opportunities for performance Hash function alternatives include:
improvement.
• Untransformed key.
Our analysis focuses on several aspects of kernel
hash table behavior: • Modulus hashing.
• Statistical “goodness” of hash functions. • Multiplicative hashing.
• Size of hash table relative to the number of • Shift-add hash function.
objects it must store.
• Random table-driven hash function.
• Lookup and insertion efficiency.
• Architecture-specific hash functions.
• Overall system throughput as it changes with
The result of our work is that the page and buffer
hash table parameters.
caches in the Linux 2.3 kernel are now dynami-
• Worst-case behavior, which can expose de- cally sized during system initialization, and the
nial-of-service vulnerabilities. buffer cache hash function has been significantly
enhanced to improve the distribution of buffers in
Our methodology measures standard benchmark
the hash table. The inode and dentry caches are
throughput, as well as statistical behavior of the
undergoing some evolution in the 2.3 kernel and
various hash tables, via instrumentation we added
have yet to be retrofitted with dynamic hash table
to the Linux kernel. We used the SPEC S-DET
allocation.
workload described above to offer fixed load lev-
els to the system as we varied specific parameters
Accept scalability
of each hash table. For each table we are inter-
ested in, we recorded hash table histogram infor- This section explores the effects of a “thundering
mation to measure the number empty buckets, the herd” problem associated with the Linux imple-
percentage of hashed objects contained in small mentation of the POSIX accept system call.
buckets, the largest bucket size, and the bucket We discuss the nature of the problem and how it
size. We are also curious about how hash func- affects the scalability of the Linux kernel. In ad-
tion randomness changes as table sizes change. dition, we identify candidate solutions and consid-
We want to demonstrate the positive effects of erations to keep in mind. Finally, we present a

– 8–
solution and benchmark it, giving a description of sk->data_ready
the benchmark methodology and the results of the bound to sock_def_readable
benchmark. sk->write_space
bound to tcp_write_space
Offered loads on network servers that use TCP/IP
sk->error_report
to communicate with their clients is rapidly in-
creasing. A service may elect to create multiple bound to sock_def_error_report
threads or processes to wait for increasing num- Each of these methods invokes the
bers of concurrent incoming connections. By pre- wake_up_interruptible function. This
creating these multiple threads, a network server means that extra tasks may be unnecessarily
can handle connections and requests at a faster awakened in other sections of the TCP code dur-
rate than with a single thread. ing the processing of other system calls or proto-
In Linux, when multiple threads call accept on col states. In fact, while processing accept,
the same TCP socket, they get put on the same three methods — tcp_write_space,
wait queue, waiting for an incoming connection to sock_def_readable, and
wake them up. In the Linux 2.2.9 kernel (and sock_def_wakeup — are invoked every time,
earlier), when an incoming TCP connection is essentially tripling the thundering herd problem.
accepted, the wake_up_interruptible Because the most frequently invoked socket
function is invoked to awaken waiting threads. methods use wake_up_interruptible, the
This function walks the wait queue and awakens
thundering herd problem extends beyond the ac-
everybody. All but one of the threads, however,
will go back to sleep, waiting for the next connec- cept system call into the rest of the TCP code.
tion. This unnecessary awakening is commonly In reality, it is wasteful for most of these methods
referred to as a “thundering herd” problem and to awaken the entire wait queue. Thus, almost any
creates scalability problems for network server TCP socket operation unnecessarily awakens tasks
applications. and returns them to sleep. This inefficient prac-
tice robs valuable CPU cycles from server appli-
In the remainder of this section, we explore the cations.
effects of the thundering herd problem associated
with the accept system call as implemented in Methodology
the Linux kernel. We then discuss the nature of Our focus is on improving system throughput by
the problem and how it affects the scalability of eliminating unnecessary kernel state CPU activity.
network server applications running on Linux. Two metrics can be used to evaluate our solution.
Finally, we benchmark the solutions and give the The first is the amount of time it takes from the
results and description of the benchmark. All initiation of the TCP connection until all tasks are
benchmarks and patches are against the Linux back on the wait queue. The second is a meas-
2.2.9 kernel. urement of throughput under a high load macro-
benchmark.
Current practice
Guidelines
The socket structure in Linux contains a virtual
operations vector, similar to VFS inodes, that lists Don't break any existing system calls
six methods (referred to as callbacks in some ker-
nel comments). These methods are initially If the changes affect the behavior of any other
pointed at a set of default functions for generic system calls in an unexpected way, then the solu-
sockets. Each socket protocol family (e.g., TCP) tion is unacceptable.
has the option to override these default functions Preserve “wake everybody” behavior for calls that
and point the method to a function specific to the rely on it. Some calls — notably select — rely
protocol family. TCP provides only one of these on the “wake everybody” behavior of
for TCP sockets. The four most commonly used wake_up_interruptible. Without this
socket methods for TCP are: behavior, select does not conform to POSIX
sk->state_change specifications.
bound to sock_def_wakeup Make the solution as simple as possible without
adding too much new code in too many places.

– 9–
The more complicated the solution, the more the same arguments. The only difference is that
likely it is to break something, or have bugs. In an extra flag is sent to __wake_up, indicating
addition, we want to keep the changes local to the “wake one” as opposed to the default “wake all.”
TCP code insofar as possible so other parts of the This way, it's up to the waker whether it wants to
kernel don't have to worry about tripping over the wake one (e.g., to accept a connection) or wake all
changed behavior. (e.g., to tell everyone the socket is closed).
Do not change any familiar/expected interfaces. For this “wake one” solution we examined each of
Do not add extra arguments to existing function the methods used with TCP sockets and decided
calls. which should call wake_up_interruptible
Make the solution general so that it can be used by and which should call
the entire kernel. wake_one_interruptible. Where we
elected to use wake_one_interruptible,
Solutions and the method was the socket default, we created
One proposed solution to this problem was sug- a small function just for TCP to be used instead of
gested by the Linux community after the accept the default. We did this so the changes would
thundering herd problem was brought to their at- affect only the TCP code, and not affect any other
tention. The idea is to add a flag in the kernel's working socket protocols. If at some point later it
task structure and change the handling of wait is decided that wake_one_interruptible
queues in the __wake_up and should be the socket default, then the new TCP
__add_wait_queue_tail functions. First, a specific methods can be eliminated. Based on our
bit in the state variable of the task structure is re- interpretation of how each socket method is used,
we arrived at the following solution:
served for an “exclusive” marking. The accept
system call is then responsible for setting the “ex- sk->state_change
clusive” flag in the task's state variable and calling bound to tcp_wakeup
add_wait_queue_exclusive to add the sk->data_ready
task to the wait queue. bound to tcp_data_ready
sk->write_space
In handling the wait queue, __wake_up walks
bound to tcp_write_space
the wait queue, waking tasks as it goes until it
sk->error_report
runs into its first “exclusive” task. It wakes this
bound to sock_def_error_report
task and then exits, leaving the rest of the queue
waiting. To ensure that all tasks that are not When the LSP patch is applied, all three of the
marked exclusive are awakened, methods used in accept call
add_wait_queue is complemented by wake_one_interruptible instead of
add_wait_queue_exclusive, which adds wake_up_interruptible.
an exclusive task to the end of the wait queue, past
all non-exclusive waiters, to ensure that all “nor- Benchmarks
mal” tasks are considered first. We took two different approaches to benchmark-
The solution developed at CITI stems from the ing the performance impact of the “wake one” and
idea that deciding whether a task should be exclu- “task exclusive” patches. The first is a simple
sive should not occur when the task is put on a micro-benchmark that is easy to set up and quick
wait queue. The process or interrupt that awakens to run. We ran this to get an idea of the “best
tasks on the wait queue is better able to determine case” performance improvement. To see if the
if it wants to awaken one task or all of them. With patch improves performance under high loads, we
these considerations in mind, we added new calls also ran a large-scale macro-benchmark on the
to complement wake_up and patched kernels.
wake_up_interruptible. These new calls Micro-Benchmark
are wake_one and
The micro-benchmark measures the time for wait
wake_one_interruptible. They are #de-
queue activity to settle down after a connection is
fined macros, just like wake_up and made. A server generates a large number of
wake_up_interruptible, and take exactly threads and has each of them accept on the same

– 10–
port. A client program creates a socket and con- static-dynamic content ratio specifically to ham-
nects to the server. We issue a printk from the mer the accept system call and because the
kernel every time a task is put on or removed from benchmark is pre-release, SPEC rules constrain us
the wait queue. After the client “taps” the server, from publishing detailed throughput results.
we examine the output of the printks and iden- However, we are able to report statistically sig-
tify the point where the connection was first ac- nificant throughput improvements.
knowledged (in terms of wait queue activity) and
Running the benchmark establishes n simultane-
when all tasks finally settled back into the wait
ous connections to the web server from the client
queue.
machines. Each connection requests a web page
The results are reported as an estimated elapsed and then dies while new connections are generated
time for the wait queue to settle down after an to take their place. These runs of the benchmark
accept call. The measurements are not exact, as request static pages as that will allow it to create
we did not take any precautions with regard to more TCP/IP connections per second rather than
concurrency control in the printks. Each data consuming excess server cycles by running cgi-
point is measured only once as we need only an scripts. This helps generate a higher stress on
estimate of what it looks like.. The server was accept. The Apache web server starts 1000
running Linux 2.2.9 on a Dell PowerEdge 6300 HTTP daemons and increases the number if it
with four 450 MHz Xeon processors and 512M of deems necessary (which it does occasionally due
RAM. to lingering connections). All of these daemons
accept on the same port.
Macro-Benchmark
Benchmark Results
To set up the test harness for this benchmark, we
purchased four machines for use as clients against The following micro-benchmark result shows the
the web server. The four machines are equipped initial state of the thundering herd problem in un-
with AMD K6-2's running at 400 MHz and a 100 modified 2.2.9 kernels. The problem is evident:
Mbps Ethernet card. The server is a Dell Power- as the number of threads increases, so does the
Edge 6300 with 4 Pentium II Xeon processors and time required to process a call to accept.
a 100Mbps Ethernet card. The clients and the
server are all connected to the server through a
100 Mbps Ethernet switch. All client machines
used in the test harness ran the stock 2.2.9 Linux
kernel. The server runs Red Hat Linux 5.2 with a
stock 2.2.9 kernel as well as our patched 2.2.9
kernel.
We elected to use the Apache web server on the
server host because it's open source and is easily
modified to make this test more useful. Stock
Apache 1.3.6 uses a locking system to prevent
multiple httpd processes from calling accept
on the same port at the same time, which is in-
tended to improve performance and reduce errors
in production web servers. For our purposes, we
want to see how the web-serving machine will
react when multiple httpd processes all call ac-
cept at once. So we modified Apache so that it
doesn't wait to obtain a lock before calling ac-
cept.
To stress test our web server, we used a pre-
release version of SPEC's SpecWeb99 benchmark,
courtesy of Netscape's web server development
team. Because we modified the benchmark's

– 11–
Running the micro-benchmark on a 2.2.9 kernel Discussion
with our patch produces the following graph: We have shown that the thundering herd problem
in accept is indeed a bottleneck in high-load
server performance, and that both the “task exclu-
sive” and “wake one” patches significantly im-
proves the performance of a high-load server. It is
our opinion that the “wake one” patch has two
main advantages over the “task exclusive” ap-
proach.
First, “wake one” does not commit a task to “ex-
clusive” status before it is awakened, obviating
the need to handle special cases to completely
empty the wait-queue. In this regard, the “wake
one” patch can solve any thundering herd prob-
lems locally, while the “task exclusive” method
may require changes in multiple places.
Second, “wake one” is somewhat cleaner and
easier to incorporate into new or existing code.

Read-ahead for mmap and sendfile

To support applications that deliver streaming
The performance improvement is clear: the cost of media such as audio or video efficiently, an oper-
processing a call to accept is constant. We also ating system must be aware of some of the unique
benchmarked the “task exclusive” approach, and characteristics of streaming data:
found similar improvements. • Usually each page of the stream is read once,
The micro-benchmark results show great promise so data caching is unnecessary and wasteful.
in improving Linux performance by addressing • Pages are read sequentially from the begin-
the thundering herd problem in accept. How- ning of the stream to the end, in strict order.
ever, we also elected to examine overall system
performance improvement by running an industry • Streaming data is often larger than a server's
standard macro-benchmark on the modified ker- main memory.
nel. • Delivery of the pages in a stream is often
Macro-Benchmark time-critical.
The results of the macro-benchmark are similarly Mail servers, web servers, and networked data-
encouraging. Running with a stable load between base servers fall in the class of servers that can be
100 and 1500 simultaneous connections to the asked to serve streaming data.
web server, the number of requests serviced per Applications that serve streaming data often use
second increased dramatically with both the mmap to access the data to be streamed. On Li-
“wake one” and “task exclusive” patches. While
nux, the mmap implementation reads a cluster of
the performance impact is not as powerful as that
pages out of any file on 64-kilobyte boundaries,
evidenced in the micro-benchmark, a considerable
but does no prediction about which pages might
gain is evident in the testing. Whether the number
be accessed next. Linux's read implementation
of simultaneous connections is at a low level, or
can read single pages at a time. Speculative read-
reaching the upper bounds of the test, the per-
ahead helps minimize application latency; we are
formance increase due to either patch remains
steady at just over 50%. There is no discernable engineering mmap to share this advantage.
difference between the two patches. Our focus is to provide speculative read-ahead
support in two places that can be of great benefit
to network server applications: in mmap, and in

– 12–
the new sendfile system call. It is obvious Scalable distributed filesystems
from its definition that the sendfile system call
reads data from a file from beginning to end in A related effort of the LSP is the implementation
order, and thus can benefit from nonspeculative of an open source, reference implementation of
the new version of the NFS distributed file sys-
read-ahead. The mmap system call can be used
tem, NFSv4. The NFSv4 protocol standard, under
both for random data access, and for sequential
development in the IETF at this writing, holds
access, thus some speculative heuristics must be
great promise for highly scalable file systems.
used to determine whether to read in small chunks
Notably, NFSv4 provides a mechanism for multi-
or use read-ahead to help improve read latency.
ple requests to be issued in the same remote pro-
Our implementations should not increase the av-
cedure call, which promises to reduce the latency
erage latency overhead of mmap page faults, the
of many compound NFS requests. In addition,
penalty of reading ahead when the data is not NFSv4 includes scalable mechanisms for insuring
used, nor cause significant pollution of the page consistent access to shared data as well as ad-
cache with pages read ahead too far in advance.
vanced security features, based on GSS API
Applications that benefit from read-ahead, such as [GSS].
database servers or specialized web servers, may Our implementation effort is still young, but
also directly exercise rather precise control over interoperability testing at an NFSv4 “bake off” in
data caching in the operating system. On some October, 1999 was very promising. Our NFSv4
POSIX-compliant UNIX systems, the madvise reference implementation will be available in “al-
and mincore system calls provide applications pha” form before the end of 1999; we anticipate a
access to information that was formerly exclu- fully functional, well-tested and -documented ver-
sively in the domain of operating system caching sion in 2000, as the IETF standardization process
algorithms. It is a short jump from teaching mmap moves forward.
to recognize sequential page faults and invoke a
simple read-ahead mechanism, to providing these Current work
POSIX APIs to applications.
Many of the issues discussed above require further
So far, we've been able to implement mmap read- exploration. In addition, we have identified sev-
ahead and madvise in several versions of the eral other challenging problems in Linux. In this
Linux 2.3 kernel. Studying Linux's read-ahead section, we briefly describe some of these issues.
support and mmap implementation has allowed us
to provide the Linux kernel community with a Hybrid poll/interrupt device driver
cleaner implementation of the generic mmap
logic, and this work appears in revisions of the 2.3 We're formulating plans to implement a device
kernel series. Because of recent significant modi- driver that intelligently switches back and forth
fications to this area of the kernel to provide sup- between interrupt mode and polling for work. We
port for large-memory hardware and the new intend to modify a stock gigabit-Ethernet driver
write-through page cache, we've been passing our and create microbenchmarks to measure the im-
modifications to the Linux community at a rather provement.
determined pace. Future work will include:
POSIX RT signals
• Studying the improvement of web serving
using our modified kernels. Traditional methods of managing asynchronous
event notification in UNIX, such as select and
• Studying the behavior of our modified kernels non-blocking I/O, are rapidly approaching, or
with artificially created malicious applica- have passed, their limits of efficiency and useful-
tions. ness in high-performance environments such as
today's network servers. Network server applica-
• Adding read-ahead and network transmission
tion developers, as well as client developers, seek
scheduling to sendfile.
alternatives to traditional paradigms to address
• Adding mincore support. some of the challenges brought on by having to
support orders of magnitude more clients per
server than ever before.

– 13–
In UNIX-like operating systems, I/O-ready and - madvise
completion events are accomplished via signals.
While traditional UNIX signals don't carry a data We're developing a Linux version of the POSIX
payload, new POSIX real-time (RT) signals do. madvise system call and plan to compare its
This payload can indicate, for example, the iden- performance and behavior to the same call on
tity of the file descriptor that just completed. This other systems, e.g., Solaris. This will involve
would obviate an additional poll invocation in developing test applications and microbenchmarks
order for an application to discover which file to measure application behavior while using
descriptor is ready for more I/O. An added bene- madvise, as well as research into how mad-
fit of RT signals is that they can be queued in the vise behaves on other open and closed source
kernel and delivered to an application in order, operating systems.
one at a time, leaving an application free to pick
up the events when it is convenient. Future work
Because the POSIX RT API is fairly new, it is In addition to our current development activities,
unfamiliar to many application developers. There we plan to address a number of critical scalability
is significant apprehension, and even some mis- issues in the Linux kernel. In this section, we
understanding, about its capabilities and limita- discuss some of these plans.
tions. We are studying the few existing applica-
tions that have successfully employed the POSIX Data throughput
RT API and creating a primer or road-map for
mainstream application developers to use as they Service scalability depends on the ability of net-
discover and begin to use POSIX RT signals. We work servers to deliver more and more data at
are also measuring performance improvement, higher and higher rates. Operating system archi-
and analyzing these new applications to see how tecture and implementation can have significant
the new architecture compares to other types of effects on data bandwidth. To improve a server's
server architectures [HPS]. effectiveness, we need to address issues in the
operating system and application that limit the
Socket efficiency amount and rate of data flowing from the server's
disk to the network.
Currently it takes much longer to create sockets
than it does to simply open files. Furthermore, the On some types of network servers, such as mail
memory overhead per socket makes it prohibitive servers, the disk read-write ratio is significantly
to manage thousands and thousands of sockets per skewed towards writes. Metadata updates and
server application. We are investigating ways to data writes are among the most expensive disk
make kernel socket management cheaper in terms and file system operations. Careful analysis of
of CPU and memory resources so that applications these operations is of great benefit.
can open more sockets. This work extends what Memory bandwidth is also important in this re-
we've done on thundering herds and poll. gard. Memory allocation and system memory
management can be optimized to make good use
SMP locking strategy of hardware memory caches. As well, maintain-
During the most recent kernel development cycle, ing I/O data cached in main memory can improve
many areas of the kernel have been freed from the overall server efficiency.
global kernel lock. Consequently, some opera- Network traffic generated by heavily used net-
tions are no longer safe, resulting in new dead- work servers exhibits unique characteristics not
locks or incorrect behavior. In addition, perform- easily reproduced when analyzing server perform-
ance is not consistent because of newly introduced ance. Clients are often situated behind high la-
timing dependent behavior. We are investigating tency network connections, resulting in a high
inter-run performance variance as well as to dis- degree of server packet retransmission. Packet
cover new ways to debug and measure locking retransmission creates unnecessary levels of net-
problems in the kernel. work congestion. Furthermore, servers often
maintain an increasingly large number of concur-
rent connections because most clients are slow to

– 14–
retrieve data, and thus maintain their connection More flexible and efficient system call inter-
for a longer time. faces
Research has suggested ways to improve TCP Under some circumstances, enterprise server
congestion management and startup behavior. products appear to perform better on Windows NT
The good news is that these changes can be im- than on UNIX platforms. Many have conjectured
plemented on the server, benefiting server net- that NT has better system call interfaces for net-
work data throughput without dependencies on work servers than UNIX. A way of improving
client networking software. server performance and scalability is to help the
server application itself make more efficient use
Specific OS issues of the operating system and the resources it pro-
vides.
Lock contention
We can do this by adding improved interfaces, or
Locks are used extensively in server applications,
by making the current interfaces, such as poll,
so the performance of an operating system's lock
more efficient. System interfaces should also
primitives is very important. In addition, support
support 64-bit files and filesystems, as well as
for mutexes that can be shared among processes is
required. very large address spaces and more than a few
gigabytes of physical RAM.
Multi-processor scalability
Improving memory bandwidth
To provide more processing power to a server
application, we can add more CPUs to a server. We plan to implement and measure new versions
First, we must be sure that the operating system of memset and memcpy in the kernel and in the
and the server application can take full advantage C run-time library that can approach hardware
of more than one or two CPUs at a time. memory bandwidth limits. We will also tune
malloc in the kernel and the C run-time library
Network servers are generally I/O bound, but in- to help mitigate latencies in underlying system
creasing the number of CPUs while not directly resource providers, and to help these routines lay-
increasing the I/O bandwidth of a system may out memory in a more hardware cache-friendly
have other benefits, such as increasing the amount way.
of CPU available for handling interrupts and proc-
essing network protocols. The very latest versions Improving TCP bandwidth
of Linux use MP hardware significantly more Several interesting innovations, such as TCP Ve-
efficiently than some earlier versions do. How- gas [BP], can help boost TCP throughput, and
ever, there is still room to improve. reduce latency due to lost packets. We will im-
Asynchronous events and thread dispatching plement and study a new mechanism that connects
recovery processing on one connection to all other
Network servers require an integrated approach to connections between the server and a particular
asynchronous I/O and thread dispatching. Most client. We will also hope to tune and improve
modern server architectures make heavy use of current TCP recovery mechanisms, including
both asynchronous I/O and threads. Asynchro- SACK [MMF], duplicate ACK, slow start, and
nous I/O support helps keep the amount of kernel fast retransmit. Finally, we plan to analyze Li-
resources and number of outstanding read buffers nux's current TCP implementation to check its
to a minimum. Having an asynchronous I/O compliance with TCP standards, e.g., to verify
model that is easy to program and allows reuse of that its congestion behavior is neighborly.
server software among various OS platforms is a
big win. Most importantly, an OS-provided inte- Continuing to extend and benchmark our test
grated asynchronous I/O and event-dispatching harness
facility has been shown by researchers to be criti- To measure our improvements accurately and
cal to the performance and scalability of Internet reproducibly, we will need to extend our test har-
servers. ness to meet the needs of experiments that stress
and benchmark Linux and the various network
server applications.

– 15–
Implementing a caching sendfile Linux device driver support for ATM cards
A Linux implementation of sendfile exists, ATM networking can help increase server
but there may be room for improvement. For ex- throughput over and above FDDI or fast Ethernet
ample, integrating sendfile with the kernel technologies. Therefore, we can explore much
network buffers may improve sendfile per- further the edges of server performance with
formance significantly. There may also be op- ATM. It is not clear, though, how well ATM and
portunities to improve sendfile throughput by other types of high-performance networking are
adjusting the scheduler to process short jobs first supported in the Linux kernel.
[CFH]. Improved interrupt handling
Discovering Linux scalability limits This work will combine SMP enhancements with
Linux may have some unfortunate system limits the addition of a hybrid polling/interrupt-driven
that we will need to discover in order to address interrupt model to the kernel to allow device driv-
them within enterprise server software. Examples ers to handle batches of interrupts rather than one
of such limits might be: interrupt at a time. Such support already exists for
serial devices; we may find that it significantly
• Small process address space size. improves the performance of disk and high-
bandwidth network devices, too.
• Small kernel address space size.
Zero-copy networking
• Inability to page most kernel data structures.
Reducing or eliminating data copy operations that
• Fixed limits on kernel data structure size. result from processing a network packet can help
• 32-bit limits on file system interfaces (like improve application data and request bandwidth
VFS). [MZA]. Mechanisms for improving networking
efficiency include checksum caching, reducing the
This work will attempt to stress various parts of number of data copy operations, and moving data
the Linux kernel to determine where its limits lie. directly from one driver to another without con-
We will also engage in research and communica- text switches (using a mechanism such as IO-Lite
tion with Linux developers to uncover architected [PDZ]). Some of these changes are easy, but
limits, and find ways to relieve the limits. something like IO-Lite would be a significant
High-performance filesystems undertaking.

In the near future, Linux is expected to have a Benchmark methodologies

journaling file system, as well as support for 64- To provide truly useful measurements of perform-
bit files. It is important that the underlying file- ance and scalability, we endeavor to select
system implementations can realistically scale to benchmarking systems that academic researchers
provide these features. Some such areas might and industrial engineers use most often. This
include boosting the ability to create many files in permits comparison and repetition of our work,
the same directory, providing support for swap- increasing its value over time. At the same time,
ping memory-based filesystems, improving the we recognize that no benchmark is able to meas-
efficiency of metadata operations and data writes, ure all types of performance problems, so we use
and supporting very large filesystems via variable other benchmarks as well, usually crafted locally.
block sizes (for use with RAID subsystems).
There are also cases where we need to examine
Optimizing PCI performance on multiple buses directly the effects of certain modifications to
This work will require a server configuration with operating system features. For analyzing OS-
high memory bandwidth and multiple PCI buses. specific modifications, McVoy's microbench-
We will study the interaction between the operat- marks and the Byte Linux Benchmarks are very
ing system and multiple PCI buses, and try some useful. File system benchmarks, such as Bonnie,
improvements based on our analysis. In addition, the Modified Andrew Benchmark, and SPEC’s
we will explore ways of improving the efficiency SDET and KENBUS benchmarks, provide cross-
of SCSI drivers by increasing the capacity of the sections of overall system performance.
device driver to handle overlapped I/O and RAID.

– 16–
We are especially interested in application per- services, the cost of providing infrastructure serv-
formance, so application-specific benchmarks are ices also increases, especially as technologies
typically used to measure our progress. Webstone reach the limit of their scalability. Linux offers
and SPECweb96 appear to be the standard web new hope to many service providers because it
server benchmarks. However, S-client and httperf provides paradigms that escape the conventional
have features that exercise pathological network models of software licensing and technical sup-
behavior, and are often useful in judging net- port.
working improvements.
Building relationships between academia, indus-
For several reasons, we have a strong bias towards try, and open source communities is a primary
web-server benchmarks: goal of our effort. Yet, our approach is character-
istic of academic researchers: we are “cathedral”
• Using freeware web servers and benchmarks people [ESR], “individual wizards or small bands
means LSP and others can remain without of mages working in splendid isolation, with no
nondisclosure agreements while still making beta to be released before its time.” Recognizing
significant contributions. that our academic approach is in many ways at
• Many web server performance issues are odds with the “bazaar” style of software develop-
common to other types of network services . ment prevalent in the Linux community, we are
pressed to reach beyond the technical challenges
• There are numerous web servers and web and establish a mechanism that influences the
server benchmarks available, as well as a design and implementation of Linux in areas
body of research literature describing the where our goals dovetail with those of the Linux
challenges and pitfalls of measuring web core.
server performance.
LSP nurtures its involvement in the Linux devel-
• Hardware. opment community by serving as a source of good
High-speed networking technologies are an inte- ideas and by backing up its faith in and respect for
gral part of our test harness. Currently, switched open source with source code, patches, and de-
fast Ethernet comprises our test harness network. tailed benchmark results. To best serve the Linux
We are preparing to install gigabit Ethernet, and community, LSP is forced to take certain risks.
hope to experiment with ATM. For example, when we undertook our analysis of
malloc, we recognized that the results might not
We have multiprocessor CPU hardware on hand provide LSP opportunities for improvement, as
to implement and test SMP changes. It may be indeed they did not. Yet, our detailed analysis and
advisable to use the more powerful machines to confirmation of a sound implementation have in-
drive server loads on smaller machines in the test herent value to us as researchers and to the
harness to approach server performance limits broader Linux community.
more quickly and repeatably.
Similarly, LSP was able to contribute to address-
Testing and evaluation of large-scale server con- ing the thundering herd issue in accept by
figurations is beyond the scope of this project. helping to identify the existence and severity of
We can go as far as understanding compatibility the problem. Although a patch was suggested and
and Linux-specific performance issues with large- integrated by the Linux core almost immediately,
scale and esoteric configurations, but our expertise we continued to study the problem. Our analysis
is focused on software optimization. We believe serves as a means of documenting the issue for
that our operating system optimizations will bene- current developers and educating future develop-
fit moderate and large-scale server deployments. ers. Furthermore, the LSP-suggested patch has
Moreover, as our work progresses, we will be architectural features not present in the patch that
better positioned later to investigate large-scale was adopted, and we continue to press (lightly) to
server performance issues. see our solution embraced by others.

LSP and the Linux community In other instances, LSP has succeeded in inte-
grating improvements into the formal Linux dis-
As universities and businesses increase their reli- tribution channel by applying focused efforts that
ance on information technology products and address specific performance and scalability

– 17–
 problems. LSP also serves as a focal point for of Relative Addresses,” in Proc. Sum-
industry's and academia's mutual agendas by mer USENIX Conf., Atlanta (June 1986).
forming a coalition of interested parties that bene-
[HPS] J.C. Hu, I. Pyarali, D.C. Schmidt,
fit from the leverage gained by our open source
“Measuring the Impact of Event Dis-
policy. Still young, LSP has established and con-
patching and Concurrency Models on
tinues to grow a strong reputation for its funda-
Web Server Performance Over High-
mental contributions to Linux.
Speed Networks,” in Proc. 2nd IEEE
Global Internet Conference (November
Acknowledgements 1997).
We gratefully acknowledge input and contribu- [MMF] M. Mathis, J. Mahdavi, S. Floyd, A.
tions from many members of the Linux developer Romanow, “TCP Selective Acknowl-
community, especially Andrea Arcangeli, Linus edgment Options,” RFC 2018 (October
Torvalds, and Stephen C. Tweedie. We thank 1996).
Charles Antonelli and Gary Tyson for providing
access to hardware. [MZA] B.J. Murphy, S Zeadally, C.J. Adams,
“An Analysis of Process and Memory
This work was partially supported by the Sun- Models to Support High-Speed Net-
Netscape Alliance, Intel, and Sun Microsystems. working in a UNIX Environment,” in
Proc. USENIX Technical Conference
References (January 1996).
[BDM] G. Banga, P. Drushel, J.C. Mogul, [PDZ] V.S. Pai, P. Druschel, W. Zwaenepoel,
“Better operating system features for “IO-Lite: A Unified I/O Buffering and
faster network servers,” in Proc. Caching System,” in Proc. 3rd Sympo-
SIGMETRICS Workshop on Internet sium on Operating Systems Design and
Server Performance (June 1998). Implementation (February 1999).
[BM] G. Banga, J. C. Mogul, “Scalable ker- [SDM] Standard Performance Evaluation Cor-
nel performance for Internet servers poration, System Development Multi-
under realistic load,” in Proc. of task Benchmark,
USENIX Annual Technical Conference, [Link]
New Orleans (June 1998). m91, (1991).
[BP] L.S. Brakmo, L.L. Peterson, “TCP Ve- [WG] W. Gloger, “Dynamic memory alloca-
gas: End to End Congestion Avoidance tor implementations in Linux system li-
on a Global Internet,” IEEE Journal on braries,”
Selected Areas in Communication 13(8) [Link]
(October 1995). [Link]/~wmglo/malloc-
[CFH] M. Crovella, R. Frangioso, M. Harchol- [Link].
Balter, “Connection Scheduling in Web
Servers,” in Proc. USENIX Conference
on Internet Technologies (October
1999)
[DL] D. Lea, “A Memory Allocator,”
unix/mail, December 1996. See also
[Link]
l/[Link].
[ESR] E.S. Raymond, The Cathedral & the
Bazaar, O’Reilly & Assoc. (October
1999).
[HB] P. Honeyman and S. Bellovin,
“PATHALIAS or The Care and Feeding

– 18–

View publication stats