One of the most elegant software designs I've seen is that of Dan Bernstein's
Maildir. Maildir is a way of storing email messages common to Unix platforms.
It's the successor to an earlier format called MBox. These two formats differ
in a very big way. To better understand the driving factors behind Maildir it's
important to know the flaws that it's trying to address. The flaw in MBox, it
turns out, is baked into its design and cannot be fixed without throwing out the
design and starting fresh; which is exactly what Dan did with Maildir.
The MBox format keeps all messages in a single text file in the user's home
directory, or anywhere for that matter. Each message is delimited by a From
line, that is, a line that starts with from:. As you can imagine, this design
makes is easy to count the number of messages in the file by counting the number
of from lines. Another benefit of this format is that since messagse are
appended on to the end of the file all of the messages are in chronological
order. These benefits, are not without their drawbacks.
Since MBox stores everything in a single file that file needs to be locked
anytime a process wants to write to it. That means that message delivery agents
(MDAs) need to lock the file while accepting mail for a user limiting the total
number of messages that can be accepted for a user at a given time to one.
Locking isn't the only problem that occurs when you store lots of information in
a single file. When a message user agent (MUA) wants to remove a message from
the middle of the file it has to rewrite the entire file without the message
that the user wants to delete. Along the same lines, in order to get a listing
of the messages in the mailbox the MUA must scan the entire file from the first
byte to the last -- apparently listing and deleting messages were not considered
a common use case. Another problem, albeit one that only reveals itself in
extreme cases, is that if a mailbox gets extremely large it could potentially
run up against the operating system's file size limitations. Lastly, the file
format is extremely fragile -- an errant From: line coult corrupt the mailbox
and render the mailbox unreadable to MUAs. When designing systems it's
important to balance speed, efficiency, robustness, and simplicity; MBox seems
to be designed for simplicity at the expense of others.
Clearly the bar is set fairly low for other mailbox formats. Luckily, Maildir
wasn't designed as an incremental improvement over MBox, it was designed to
maximize speed, efficiency, and simplicity; and it did so in an amazingly
elegant and robust way.
Enter Maildir
Maildir, as the name implies stores its data in a directory structure. This is a
crutial difference between Maildir and MBox. Maildir, unlike MBox purports to
be a lock-free system -- the mailbox can be read and written to at the same
time. Under high load this is a really good feature to have. The most
interesting piece is that Maildir maintains its lock-free design even when the
mailbox is stored on a remote system and mounted using NFS (network file
system).
Not only is the system lock-free it also doesn't fall victim to the other
problems faced by MBox; receiving and deleting messages are O(1) operations --
meaning that they take a constant amount of time to complete, instead of an
amount of time proportional to the amount of messages in the mailbox. Another
advantage to storing the mailbox as a directory is that the number of messages
can be found by counting the number of files in the mailbox directories -- the
MUA doesn't need to open the files at all unless it wants to get information
from them.
So how does it work? Maildir is a fairly simple system which has the nice side
effect of making it robust. A Maildir mailbox is a directory that contains 3
subdirectories to store messages: tmp, new, and cur. Messages that are
being delivered are placed into tmp while they are being received. Once
messages have been received they are moved to new before being read. After a
user reads a new message it's moved into cur.
So far this seems like a fairly simple system; but what are the files that
contain the messages called? Each message is given a unique name. The unique
name is made up of a combination of machine and process dependent information
such as the host name, current time, PID of the MDA delivering the message, etc.
By concatenating a few of these together a globally unique name can be created;
in the event that a collision occurs Maildir specifies that the MDA wait at
least one second before trying again. This timeout is meant only to ensure that
enough time has elapsed that the data used to create another unique name will be
different.
That's effectively all there is to the mailbox format. Certainly it's simple,
but how is it elegant or robust? To get a handle on that it's important to
have an understanding of the properties of the Unix file system.
Unix File Systems 101
When most people think of a file on their computer they percieve a one-to-one
mapping between file names and data; that is, a file and its data are
synonyms. Under Unix this isn't the case. Unix treats file names and data as
two separate things. What you might think of as the data in the file is
actually known to the operating system as a unique number called an inode.
Files are simply references to an inode. When you create a new file the file
system allocates a new inode and associates the data you're saving with it. The
name you specified for the file references the inode. When you delete the file
you're deleting the reference to the inode. When the file system sees that
there are no longer any references to the inode it knows that the space being
used by that inode can be reclaimed.
Since multiple names can reference the same inode you can save disk space and
headaches by having multiple names for the same inode. The process for creating
a new name for an inode is called linking and there are two APIs (application
programming interfaces) exposed by POSIX (the portable operating system
interface [for unix]) that manage links: link and unlink. As you can gather
from the name link creates a new name while unlink removes a name.
Linking and unlinking inodes is an atomic operation -- an operation that occurs
instantly without the possibility of being interupted part way through. When a
new link for a file is created the file is completely accessible, there's no
delay while the data is copied on the disk. Simply put linking amounts to adding
some accounting information in the file system but doesn't need to shuffle data
around on the disk. This property of atomicity can be used by any application
that requires that readers have a consistent view of the world.
Another feature of the Unix file system, and file systems in general is that the
metadata -- the data about the files -- is stored separately from the file data.
The stat information includes, but is not limited to: creation, modification and
access times as well as size and ownership information. Having this information
at the file system level means that it's relatively inexpensive to load
information about a file or directory. Loading information about a file is
called stating a file based on the name of the POSIX function stat. Since
this information is standard information stored by the file system and isn't
buried within a data file access to this data doesn't require specialized APIs
-- the ones exposed by the OS are sufficient.
How Maildir Exploits the Unix File System
The features of the Unix file system mentioned previously are exploited very
well by the design of Maildir. In order to ensure currency Maildir stores mail
that is being received in a temporary directory, tmp. This ensures that
readers of the mailbox, who read messages from the new and cur directories
will not see messages that have not been completely received. Once a message is
completely received it is linked over to the new directory. At the moment
that the file system is updated with the new link to the file in new, all
readers of the mailbox can see the message -- and the message they see is the
full message, not a partially written one. In a similar vein, the stat
information makes is very easy to get the size and received date of each message
without having to parse the message file.
These benefits are extremely tangible, especially when considered in concert
with the notion that a user's mailbox is generally located on a remote machine
mounted using a Networked File System (NFS). Accessing files over a network is
an order of magnitude slower than accessing files that are local to a particular
machine; however the networked file system is presented to the system as any
other file system -- neatly abstracted away behind the standard POSIX calls.
From a user's perspective an NFS doesn't look any different than any other file
system, it's just slower. But since Maildir is optimized to use the POSIX calls
for many common operations, the whole experience is greatly improved.
Consider the case where an MUA wants to get a listing of the number of messages
and sort them by date. An MUA that uses MBox would need to first lock the
mailbox file, then read and parse its entire contents before it could provide
the listing. For large mailboxes this is an expensive operation -- and an order
of magnitude more expensive when the mailbox is on a remote machine. The MUA
using Maildir would need to simply stat the file system. The data returned
doesn't need to be parsed since its already in a standard POSIX structure. To
get email specific information from each message such as subject, sender, etc
Maildir helps by reducing the amount of I/O that needs to be performed. An MUA
can simply read the first few lines of any message it's interested in to parse
the headers. Contract this with MBox where it must read the entire mailbox file
since the only way to know that you've reached the last message is when you hit
the end of the file.
An Example -- How MTAs Accept Mail for Maildir Mailboxes
As mentioned previously the Maildir directory consists of at least 3
subdirectories: tmp, new, and cur. When writing new mail to a Maildir
mailbox the tmp and new directories are used.
When a new message arrives, the system constructs a (possibly) unique identifier
for the message. The MTA then checks tmp directory for a file with the same
name. If a file with that name exists the MTA waits for 1 second and constructs
a new unique identifier and tries again until it finds a unique identifer that
doesn't clash with an existing file. The 1 second delay allows enough time for
any time-related information used in the unique identifier to change.
The MTA then writes the message data to the uniquely named file in the tmp
diectory. When the file has been completely recieved a new link is created to
the message file in the new directory. The file is then unlinked from the
tmp directory leaving a single link to the file in new.
Conclusion
The design of Maildir leverages the facilities provided by POSIX to produce an
elegant solution that is simple, efficient and robust. Its clever use of the
Unix file system and associated POSIX APIs demonstrates that it's possible to
design a robust and scalable inter-process communication (IPC) mechanism using
nothing but these facilites. In general, Maildir is a great example of what can
be accomplished by having an understanding of the pieces of technology that a
system is built on.
