<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="author" content="Rob Siemborski" />
<title>Mailbox File Formats</title>
</head>
<body>
<h1>Mailbox File Formats</h1>
<h2>Intro</h2>
<p>This documentation refers to the "version 12" cyrus index format
and associated mailbox files.</p>
<p>No external tools should make use of this information. The only
supported method of access to the mail store is through the standard
interfaces: IMAP, POP, NNTP, LMTP, etc.</p>
<p>A cyrus mailbox is a directory in the filesystem. It contains the
following files:</p>
<ul>
<li> zero or more message files </li>
<li> the <tt>cyrus.header</tt> metadata file </li>
<li> the <tt>cyrus.index</tt> metadata file </li>
<li> the <tt>cyrus.cache</tt> metadata file </li>
<li> zero or one <tt>cyrus.squat</tt> search indexes </li>
<li> zero or more subdirectories </li>
</ul>
<p>With "split metadata" configuration, the mailbox may actually be
split between multiple disks, with the files being in the same
relative directory on the meta disk. See the <tt>imapd.conf</tt> option
<tt>metapartition_files</tt> for more information</p>
<h2>Message Files</h2>
<p>The message files are named by their UID, followed by a ".", so UID 423
would be named "<tt>423.</tt>". They are stored in wire-format: lines
are terminated by CRLF and binary data is not allowed.</p>
<h2><tt>cyrus.header</tt></h2>
<p>This file contains mailbox-wide information that does not change
often. Its format:</p>
<pre>
<Mailbox Header Magic String>
<Quota Root>\t<Mailbox Unique ID String>\n
<Space-separated list of user flags>\n
<Mailbox ACL>\n
</pre>
<p>The Mailbox Unique ID String is used for non-owner per-user \Seen
flags so they remain with the mailbox during renames, and also by the
replication subsystem to detect mailbox renames.</p>
<p>The ACL is a copy of the value stored in mailboxes.db, and isn't
actually used.</p>
<h3>Locking Considerations</h3>
<p>The <tt>cyrus.index</tt> file must be locked in exclusive mode
while making changes to the <tt>cyrus.header</tt> file to ensure
consistency. All changes are made by rewriting the entire file
and renaming the new version into place.</p>
<h2><tt>cyrus.cache</tt></h2>
<p>The <tt>cyrus.cache</tt> file is a pure cache of information that's
also present in the message files. It exists to make ENVELOPE and
specific header fetches more efficient, as well as to assist with
searches and sorts.</p>
<p>If a <tt>cyrus.cache</tt> file is missing or corrupted, it can be
re-generated by running a <tt>reconstruct</tt> on the mailbox.</p>
<p>The format is 10 individual records each prefixed with a 32 bit length
value in network byte order. The offset of each message's cache record
is stored in the <tt>cyrus.index</tt> file (documented below). The
records in a cyrus.cache file are of variable length, depending on the
contents of the associated message.</p>
<p>The first 4 bytes of the cyrus.cache file are a "generation number"
which must match the first 4 bytes of the associated cyrus.index file.
In the past this was used to track consistency between the files, but
the name locking scheme and per-record CRC check in cyrus 2.4 and
above means this is just a backup consistency check rather than an
essential format feature.</p>
<pre>
+------------------------------------------------------------------------+
|Gen # (32bits)|Size 1 (32bits)|Data 1 |
+------------------------------------------------------------------------+
| |Size 2 (32bits)|Data 2 |Size 3 (32bits)| Data 3 |
+------------------------------------------------------------------------+
| ..... |
+------------------------------------------------------------------------+
</pre>
<p>While there are occasional changes to the cache format, this
information is NOT stored in the cyrus.cache file. Instead, there
is a "cache_version" field in the cyrus.index record, so multiple
different versions of cache data may exist in the same cache file.</p>
<p>
The order of fields per record in the cache file is as follows:
(keep in mind that they are all preceeded by a 4 byte network byte order
size).</p>
<dl>
<dt>Envelope Response</dt>
<dd> Raw IMAP response for a request for the envelope.</dd>
<dt>Bodystructure Response</dt>
<dd> Raw IMAP response for a request for the bodystructure.</dd>
<dt>Body Response</dt>
<dd> Raw IMAP response for an (old style) request for the body.</dd>
<dt>Binary Bodystructure</dt>
<dd><p>
Offsets into the message file to pull out various body parts. Because
of the nature of MIME parts, this is somewhat recursive.</p>
<p>
This looks like the following (starting the octet following the cache
field size). All of the fields are bit32s.</p>
<pre>
[
[Number of message parts+1 for the rfc822 header if present]
[
[Offset in the message file of the header of this part]
[Size (octets) of the header of this part]
[Offset in the message file of the content of this part]
[Size (octets) of the content of this part]
[Encoding Type of this part]
]
(repeat for each part as well as once for the headers)
[zero *or* number of sub-parts in the case of a multipart.
if nonzero, this is a recursion into the top structure]
(repeat for each part)
]
</pre>
<p>
Note if this is not a message/rfc822, than the values for the sizes
of the part 0 are -1 (to indicate that it doesn't exist). Sub-parts are
not possible for a part 0, so they aren't included when finding recursive
entries.
</p>
<p>
The offset and size info for both the mime header and content part are
useful in order to do fast indexing on the appropriate parts of the
message file when a client does a FETCH request for BODY[HEADER],
or BODY[2.MIME].
</p>
<p>
Note that the top level RFC822 headers are a treated as a
separate part from their body text ("0" or "HEADER").
</p>
<p>
In the case of a multipart/alternative, the content size & offset
refers to the size of the entire mime part.
</p>
<p>
A very simple message (with a single text/plain part) would therefore
look like:
</p>
<pre>
[[2][rfc822 header][text/plain body part info][0]]
</pre>
<p>
A simple multipart/alternative message might look like:
</p>
<pre>
[[3][rfc822 header][text/plain message part info]
[second message part info][0][0]]
</pre>
<p>
A message with an attachment that has two subparts:
</p>
<pre>
[[3][rfc822 header info][rfc822 first body part info][attachment info][0][
[3][NIL header info][sub part 1 info][sub part 2 info][0][0]]]
</pre>
<p>
A message with an attached message/rfc822 message with the following
total structure:
</p>
<pre>
message/rfc822
0 headers; content-type: multipart/mixed
1 text/plain
2 message/rfc822
0 headers; content-type: multipart/alternative
1 text/plain
2 text/html
</pre>
<pre>
[[3][rfc822 header part 0][text/plain part 1][overall attachment info][0][
[3][rfc822 header part 2.0][text/plain part 2.1][text/html part 2.2]
[0][0]]]
</pre>
</dd>
<dt>Cache Header</dt>
<dd>
<p>
Any cached header fields. The exact set of fields here depends on the
cache record version - there is a function in <tt>imap/mailbox.c</tt>
to determine if a named header would be cached based on the version.
These are in the same format they would appear in the message file:
</p>
<pre>
HeaderName: headerdata\r\n
</pre>
<p>
Examples include: References, In-Reply-To, etc.
</p>
</dd>
<dt>From</dt>
<dd> The from header.</dd>
<dt>To</dt>
<dd> The to header.</dd>
<dt>Cc</dt>
<dd> The CC header.</dd>
<dt>Bcc</dt>
<dd> The BCC header.</dd>
<dt>Subject</dt>
<dd> The Subject header.</dd>
</dl>
<h3>Locking Considerations</h3>
<p>The <tt>cyrus.index</tt> file must be locked in exclusive mode while
making changes to the <tt>cyrus.cache</tt> file to ensure consistency.
All new cache records are created by reading the current end-of-file
offset, appending the new cache record, and storing that start offset
into the associated cyrus.index record.</p>
<h2><tt>cyrus.index</tt></h2>
<p>The cyrus.index file is NOT just a cache - it stores information not
present in the message file!</p>
<p>The cyrus.index file consists of a fixed width header, followed by
fixed width records. In the past, it would be rewritten on every expunge,
but since Cyrus 2.4 the expunged records remain in the cyrus.index file
for a configurable time to support QRESYNC and more efficient delayed
expunge.</p>
<p>The cyrus.index file is the "heart" of the mailbox format - containing
checksums (CRC32) of everything else, and the most frequently updated
fields. All fields are stored in network byte order and aligned on 4
byte boundaries. Due to some 64 bit values being stored, the header
and individual records are aligned on 8 byte boundaries.</p>
<p>
The overall format looks sort of like this:</p>
<pre>
cyrus.index:
+----------------+
| Mailbox Header |
+----------------+
| Msg: Num 1 |
+----------------+
| Msg: Num 2 |
+----------------+
| ... |
+----------------+
</pre>
<p> The basic idea being that there is one header, and then all the
message records are evenly spaced throughout the file. All of the
message records are at well-known offsets, making any part of the file
accessable at roughly equal speed.</p>
<h3>Locking Considerations</h3>
<p> <tt>cyrus.index</tt> files can not be repacked (i.e. records
can not change UID for a particular offset, and the file can't be
rewritten or deleted) unless there's an exclusive namelock held
for the mailbox name. This is to avoid race conditions and simplify
the use of mailboxes. Whenever a mailbox is opened, the caller
holds a shared namelock on the mailbox name for the duration of
the "mailbox object"'s existence.</p>
<p> All reads of a <tt>cyrus.index</tt> file must be done with a
lock held, and all writes must be done with an exclusive lock held.
This ensures CRC32 checksums of individual headers and records are
always consistent. There are no direct "offset" reads done any more,
instead the mailbox API provides a way to read an entire cyrus.index
header or cyrus.index record into a struct, performing consistency
checks. Writes are also done with a complete record struct.</p>
<h3>Detail of <tt>cyrus.index</tt> header</h3>
<p>The index header contains the following information, in order:</p>
<dl>
<dt>
Generation Number (4 bytes)</dt>
<dd>A number that is basically the "revision number" of the mailbox. It must
match between the cache and index files. This is to ensure that if we
fail to sync both the cache and index files and a crash happens (so that
only one is synced), we do not provide bad data to the user. This is
also backed by having indiviual cache checksums on each record.</dd>
<dt>Format (4 bytes)</dt>
<dd>Basically obsolete (indicates netnews or regular).</dd>
<dt>Minor Version (4 bytes)</dt>
<dd>Indicates the version number of the index file. This can be used
for on-the-fly upgrades of the index and cache files.</dd>
<dt>Start Offset (4 bytes)</dt>
<dd> Size of index header.</dd>
<dt>Record Size (4 bytes)</dt>
<dd> Size of an index record.</dd>
<dt>Num Records (4 bytes)</dt>
<dd> How many records are in this index (including records for expunged
records. See below for "Exists" which has moved from pre-version 12
files.</dd>
<dt>Last Appenddate (4 bytes)</dt>
<dd> (time_t) of the last time a message was appended</dd>
<dt>Last UID (4 bytes)</dt>
<dd> Highest UID of all messages in the mailbox (UIDNEXT - 1).</dd>
<dt>Quota Mailbox Used (8 bytes)</dt>
<dd> Total amount of storage used by all of the messages in the mailbox.
Platforms that don't support 64-bit integers only use the last 4 bytes.</dd>
<dt>POP3 Last Login (4 bytes)</dt>
<dd> (time_t) of the last pop3 login to this INBOX, used to enforce
the "poptimeout" <tt>imapd.conf</tt> option.</dd>
<dt>UIDvalidity (4 bytes)</dt>
<dd>The UID validitiy of this mailbox. Cyrus currently uses the
<tt>time()</tt> when this mailbox was created.</dd>
<dt>Deleted, Answered, and Flagged (4 bytes each)</dt>
<dd> Counts of how many messages have each flag.</dd>
<dt>Mailbox Options (4 bytes)</dt>
<dd> Bitmask of mailbox options, consisting of any combination of the
following:
<dl>
<dt>POP3_NEW_UIDL</dt>
<dd> Flag signalling that we're using
"<em>uidvalidity</em>.<em>uid</em>" instead of just "<em>uid</em>" for
the output of the POP3 UIDL command.</dd>
<dt>IMAP_SHAREDSEEN</dt>
<dd> Flag signalling that we're supporting a shared \Seen flag
on the mailbox.</dd>
<dt>IMAP_DUPDELIVER</dt>
<dd> Flag signalling that we're allowing duplicate delivery of
messages to the mailbox, overriding system-wide duplicate suppression.</dd>
<dt>MAILBOX_NEEDS_REPACK</dt>
<dd> Flag signalling that the mailbox is due to be repacked. During
mailbox_close() every process will attempt to take an exclusive namelock
on the mailbox and repack.</dd>
<dt>MAILBOX_DELETED</dt>
<dd> Flag signalling that the mailbox is deleted. This can be set with
a shared namelock, and indicates to all other users of the mailbox that
they need to close it and attempt cleanup. The last process to close
the mailbox will perform the final cleanup under an exclusive namelock,
giving the other processes a chance to finish their current operation
first without files disappearing from under them!
</dd>
</dl>
</dd>
<dt>Leaked Cache (4 bytes)</dt>
<dd> Number of leaked records in the cache file.</dd>
<dt>Highest ModSeq (8 bytes)</dt>
<dd> Highest Modification Sequence of all the messages in the
mailbox (CONDSTORE).</dd>
<dt>Deleted ModSeq (8 bytes)</dt>
<dd> Lowest Modification Sequence before which expunged message data
may have been purged from the mailbox and forgotten
(CONDSTORE/QRESYNC support).</dd>
<dt>Exists (4 bytes)</dt>
<dd> See NumRecords above. This is the count of non-expunged records
in the mailbox and corresponds to the IMAP status item "EXISTS".</dd>
<dt>First Expunged (4 bytes)</dt>
<dd> lowest modified time of an expunged message in this mailbox (or
zero if there are no expunged messages) - used to determine if the
mailbox needs repacking.</dd>
<dt>Last Repack Time (4 bytes)</dt>
<dd> a timestamp for the last repack, to ensure repacks aren't done
too close together if expunges were closely spaced</dd>
<dt>Header File CRC (4 bytes)</dt>
<dd> CRC32 value of the bytes in the <tt>cyrus.header</tt> file for
this mailbox. Must be rewritten whenever the cyrus.header file is
changed (see locking considerations above - this is why the
cyrus.index must be exclusively locked!)</dd>
<dt>Sync CRC (4 bytes)</dt>
<dd> An XOR of the CRC32 of a specially generated value for each of
the non-expunged records in this mailbox. This is a cached value
which allows the replication subsystem to quickly determine that
all non-expunged records in a mailbox are in sync and detect
possible "split brain" scenarios with low bandwidth use.</dd>
<dt>Recent UID (4 bytes)</dt>
<dd> The highest UID last time an IMAP client logged in as the mailbox
owner (or anybody if SHAREDSEEN is enabled) selected this mailbox.
Used to generate the \Recent flags in IMAP</dd>
<dt>Recent Time (4 bytes)</dt>
<dd> Used for consistency with the seen_db code, but probably not
actually necessary. Oh well</dd>
<dt>Header CRC (4 bytes)</dt>
<dd> Must always be the LAST record of the header. This is the CRC32
of the actual bytes on disk (network order format) for the rest of the
cyrus.index. By keeping it last, it can be easily calculated with
the following snippet of code:
<tt>crc = crc32_map(buf, OFFSET_HEADER_CRC);</tt> - i.e. crc32 from
the start of the buffer to just before this field.</dd>
</dl>
<p>
There are also spare fields in the index header, to allow for future
expansion without forcing an upgrade of the file, and to round up
to be divisible by 8 bytes.</p>
<h3>Detail of <tt>cyrus.index</tt> records</h3>
<p>These records start immediately following the <tt>cyrus.index</tt>
header, and are all fixed size. They are in-order by uid of the
message.</p>
<dl>
<dt>UID (4 bytes)</dt>
<dd> UID of the message</dd>
<dt>INTERNALDATE (4 bytes)</dt>
<dd>INTERNALDATE of the message (where possible, this matches the
creation and modification times of the file on disk to help
reconstruct in the event of data loss)</dd>
<dt>SENTDATE (4 bytes)</dt>
<dd> Contents of the Date: header chomped to day resolution with timezone stripped.</dd>
<dt>SIZE (4 bytes)</dt>
<dd> Size of the whole message (in octets)</dd>
<dt>HEADER SIZE (4 bytes)</dt>
<dd> Size of the message header (in octets)</dd>
<dt>GMTIME (4 bytes)</dt>
<dd> Contents of the Date: header at 1 second resolution and converted to GMT (for sort)</dd>
<dt>CACHE_OFFSET (4 bytes)</dt>
<dd>Offset into the <tt>cyrus.cache</tt> file for the beginning of this message's
cache entry.</dd>
<dt>LAST UPDATED (4 bytes)</dt>
<dd>(time_t) of the last time this record was changed</dd>
<dt>SYSTEM FLAGS (4 bytes)</dt>
<dd> Bitmask showing which system flags are set/unset</dd>
<dt>USER FLAGS (MAX_USER_FLAGS / 32 bytes)</dt>
<dd> Bitmask showing which user flags are set/unset (bits correspond to
positions in the cyrus.header flag list, i.e.
(1<<0) == the flag name</dd>
<dt>CONTENT_LINES (4 bytes)</dt>
<dd> Number of text lines contained in the message content (body).</dd>
<dt>CACHE_VERSION (4 bytes)</dt>
<dd>Indicates the version number of the cache record for the message
(determines which headers are cached, see list in mailbox.c).</dd>
<dt>GUID (MESSAGE_GUID_SIZE bytes)</dt>
<dd>Globally Unique IDentifier of the message (used by replication
engine). This is the sha1 value of the bytes as stored on disk.</dd>
<dt>MODSEQ (8 bytes)</dt>
<dd>Modification Sequence of the message (CONDSTORE).</dd>
<dt>CACHE_CRC (4 bytes)</dt>
<dd>This is the CRC32 of all the bytes of the cache record (all
10 fields) as stored on disk. Again, calculated over the exact
bytes stored in the <tt>cyrus.cache</tt> file.</dd>
<dt>RECORD_CRC (4 bytes)</dt>
<dd>Like the header CRC - this is the CRC32 of all the bytes in on-disk
order that exist in this record. Records are always rewritten as the
entire record, including the updated CRC, so it's always consistent if
you have a lock on the <tt>cyrus.index</tt> file, because writers will
wait until they get an exclusive lock to make modifications.</dd>
</dl>
<h2>Notes</h2>
<ul>
<li> Expunge is super quick now - it's just a flag update!</li>
<li> Append is relatively fast (it only adds to the end of both the
cache and index files and modifies the index header)</li>
<li> Message unlinks always happen during the "close" phase - which
may be noticed when you select another mailbox, but otherwise
are delayed from the actual action. With delayed expunge,
the unlinks are pushed off to cyr_expire which is a background
task, and will never be noticed by the user.</li>
<li> Message delivery is something like this:
<ol>
<li> write/sync message file</li>
<li> write/sync new <tt>cyrus.cache</tt> record</li>
<li> write/sync new <tt>cyrus.index</tt> record</li>
<li> calculate, write, sync new <tt>cyrus.index</tt> header</li>
<li> acknowledge message delivery</li>
</ol>
<p>The message isn't delivered until the new index header is written. In
case of a crash before the new index header is written, any previous
writes will be overwritten on the next delivery (and will not be
noticed by the readers).</p>
<p>Note that certain power failure situations (power failure in the
middle of a disk sector write) could cause a mailbox to need
reconstruction (possibly even losing some flag state). These failure
modes are not possible in the "Hardware RAID disk model" (which we
will describe somewhere else when we get around to it).</p>
</li>
</ul>
<h2>Future considerations</h2>
<ul>
<li> Cache all header fields? (or all up to Xk?) This could greatly improve
speeds of clients that just ask for everything, but also increases the
expense of rewriting the cache file (as well as the size it takes
on disk).</li>
<li> Reformat cache file to use a (size)(size)(size)(size)(data)(data)(data)
format. This makes accesses anywhere in the cache file equally fast,
as opposed to having to iterate through all the entires for a given
message to get to the last one. Note that either way is still O(1)
so maybe it doesn't matter much.</li>
<li> It would be useful to store a uniqueid -> mailbox name index, so that
we could fix arbitron again.</li>
</ul>
</body>
</html>
