A qmail system revolves around its queue. The queue is basically a holding area for messages which have been sent (either from the local machine or from a remote machine) but have not reached their final destination (a user's mailbox, another mail server, etc.) yet.
Remember that qmail is made up of several small programs, each of which does its one little piece of the overall job of a mail server. In the case of the queue, there is one set of programs devoted to accepting messages and adding them to the queue, and another set of programs devoted to moving messages from the queue to their next stop (i.e. "delivering" messages.) In the middle of it all is a program called qmail-send, whose job is to manage the queue by scheduling deliveries as quickly as possible.
There are several programs which accept incoming messages and add them to the queue. For example, qmail-smtpd handles the server end of an SMTP connection, accepting messages from other machines on the internet, while qmail-inject accepts messages from a file or a pipe on the local machine.
All of these programs (qmail-smtpd, qmail-qmqpd, qmail-qmtpd, and qmail-inject) call the qmail-queue program to handle the low-level mechanics of adding their messages to the queue.
qmail-queue works by writing the message text (the full headers and body) to a file in the "mess" section of the queue and renaming the file so its name is the same is its own inode number. The envelope information (sender and recipients) is written to a file with the same name (number) in the "todo" section of the queue, and a signal is sent to qmail-send, telling it that a new message has arrived.
Using the inode number as the filename has two
advantages. First, it guarantees that no other message in the queue will
have the same filename, because inode numbers are guaranteed to be
unique with their filesystems.
The second advantage is that because it is a number, the number can be "hashed" to produce a much smaller non-unique number, and the file can be stored in a sub-directory whose name is this smaller number. Storing the files in sub-directories speeds up access to the files through the filesystem- in order to find a certain file within a directory, every filename in the directory has to be checked until the system finds the one you're looking for.
For example, imagine a collection of 10,000 files, and you want to read file number 9876. If all of the files are stored in one directory, you end up having to potentially read up to 10,000 names in order to find the one you want. If the files are split into groups (i.e. all files from 0-99 in one directory, all files from 100-199 in another directory, and so forth) you can apply the same logic to the name you're looking for- you would know that the file "9876" will be in a directory called "98", which means you search up to 100 directory names to find the "98" directory, then search up to 100 filenames to find the "9876" file. It takes a lot less time to search 200 entries than it does to search 10,000 entries.
This process of splitting up the files in a known manner is known as "hashing", and the sub-directories are known as "buckets." With qmail, the hashing algorithm (the function it uses to figure out which bucket should contain a given file) is very simple- it divides the message number by a fixed number, chosen when qmail is compiled, and the remainder of that division is the bucket number.
By default, qmail uses 23 as the bucket count. The qmail hashing algorithm seems to produce a more even distribution of elements within the buckets when the bucket count is a prime number- there is a deep mathematical explanation, but I don't worry about it... if I need to change the bucket count when installing a server, I always use a prime number.
The qmail-send program manages the queue, making sure deliveries are processed as quickly as possible. It works as a loop, doing the following steps over and over:
Classify messages. Remember that when messages are added, qmail-queue sends a signal to qmail-send. When qmail-send receives this signal, it pauses whatever it's doing, sets a flag to show that the signal was received, and picks up again where it left off.
When the main processing loop starts, it looks at this flag. If at least one signal has been received, qmail-send looks at every message with a control file (containing the sender and recipients) in the "todo" directory and uses the recipient domain names to classify each recipient as local or remote. It creates another control file in the "local" or "remote" directory for each recipient. When all recipients for a message have been classified, the "todo" file is deleted.
This process continues until no more messages are found in the "todo" directory.
Schedule deliveries. qmail-send searches the "local" directory, searching for messages which are not already in the process of being delivered, and which are not "on hold" due to a deferral from a previous delivery. When it finds one, it tells qmail-lspawn to attempt delivery of that message, and continues searching. It stops when there are "concurrencylocal" local deliveries in process, or there are no more messages to be delivered.
It then does the same process for the "remote" directory, although the decision whether or not to tell qmail-rspawn to process a given delivery also takes into account the status of the IP address of the remote server- if the IP address is on a "timeout" list, the delivery will not be attempted.
Handle errors. qmail-send checks the status of each outstanding delivery.
For each finished delivery which was successful, the recipient is "checked off". When a message has no recipients whose deliveries have not been done, the message is dropped from the queue (all deliveries are complete, no need to keep the message.)
For "deferred" deliveries (i.e. "soft errors") a log entry is made and the message is placed "on hold" for a time. In the case of a remote delivery, if the delivery failed because a remote machine didn't answer, the remote IP address may be added to the "tcp timeout" list, depending on how many deliveries have been attempted to that IP recently.
For failed deliveries, it generates a bounce message- or if the message whose delivery failed was itself a bounce, then a "doublebounce" is generated... and if the message whose delivery failed was a "doublebounce", the message is dropped from the queue (i.e. a "triplebounce".)
It then sleeps for a short time, and then goes back to the beginning of the loop (classifying messages) again.
The problem with this scenario happens when a very large number of messages are added to the queue in a short period of time. Remember that the classification portion of qmail-send (i.e. the "todo" portion of the program) inspects every newly-arrived message and decides, for each message, whether it's "local" or "remote"- and while it's doing this, no new deliveries are being started.
In a case where too many messages are added at once (which may be anywhere from a few hundred to several thousand, depending on the speed of the CPU, the disk containing the queue, and any in-memory disk caching) this "todo" process takes a long time- so long that most or all of the currently in-process deliveries finish before it's done.
This can also happen in reverse... sometimes if the system is doing a lot of deliveries and they all "hang", waiting for remote servers which don't answer quickly, the delivery-scheduling side will be stuck and the classifying side doesn't run, which can cause a large number of un-classified messages to build up, and then of course when the deliveries finaly finish it takes forever to classify them all, which makes the delivery side sit there and do nothing.
The effect is that qmail-send spends all of its time doing one side of its job, either inspecting and classifying new messages or schedulding deliveries, and the other side of its job doesn't get done in a timely manner. This is known as the "silly qmail syndrome".
The solution to this problem is the EXTTODO patch by André Oppermann. (Note: the link points directly to the original patch file, the patch author never wrote any kind of web page to document the patch.) It solves the problem by breaking qmail-send into two processes.
One process is a new program called qmail-todo, which catches the signals from qmail-queue whenever new messages are added to the queue, and runs a loop whose only job is the same classification functions that qmail-send normally does by itself. As it classifies each message, it creates the same files in the "local" and "remote" directories. When it finishes each message, it sends a message to qmail-send, telling it what the new message number is. When it runs out of new messages to classify, it goes to sleep until another signal arrives from qmail-queue.
The other process is the original qmail-send, with the "todo" processing removed (since qmail-todo is now doing that function) and a new communication channel added for passing messages to and from qmail-todo.
With this scenario, if several thousand messages are added to the queue all at once, qmail-todo becomes very busy classifying messages, and sending message numbers to qmail-send. Because qmail-send doesn't have to do this pre-classifying work anymore, it is able to spend more time concentrating on starting as many deliveries as possible. As each delivery finishes, qmail-send is able to immediately start up another delivery. The problem with qmail not scheduling deliveries disappears entirely.
The EDTTODO patch is included as part of my combined patch file, starting with version 6c. If you would rather use a single combined patch than having to manually apply patches on top of each other and have to manually deal with their typographic incompatibilities, you should at least look at the combined patch and see if it has the features you need for your server.