Edit File: mixfmt.txt
/* ======================================================================== * Copyright 1988-2006 University of Washington * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * * ======================================================================== */ Last update: 18 December 2006 INTRODUCTION This file is the descendant of a design document used to specify the mix format. An attempt is being made to keep this document more or less current with the way the mix format actually works. 1. Mix mailbox naming Mailbox names correspond to directory names; thus mix format mailboxes are "dual-use" (lack both \NoInferiors and \NoSelect). This will satisfy some long-standing requests. 2. Mailbox files A mix format mailbox is a directory with regular files with filenames of: .mixmeta mailbox metadata file .mixindex message index file (message static data) .mixstatus message status file (message dynamic data) .mix######## (where ######### is a <hex8>) secondary message data files. .mix primary message data file (used in experimental versions, supported for compatibility only) 2.1 Metadata, index, and status files The mailbox metadata, index, and status files contain a sequence of CRLF-terminated lines. These files have an update sequence, which is a strictly-ascending sequence value. Any time the file is changed, the update sequence is increased; this allows easy detection of whether the file has been changed by another process. For now, this update sequence is a modseq (see below). 2.1.1 Metadata file The mailbox metadata file is called ".mixmeta". It contains a series of CRLF-terminated lines. The first character of the line is a key that identifies the payload of the line, and the remainder of the line is the payload. Key Payload --- ------- S <hex8> ;; update sequence V <hex8> ;; UIDVALIDITY L <hex8> ;; UIDLAST N <hex8> ;; current new message file K [atom 0*(SP atom)] ;; keyword list All other keys are reserved for future assignment and must be ignored (and may be discarded) by software which does not recognize them. The mailbox metadata file is rewritten as part of new mail delivery (so APPENDUID/COPYUID can work) and when new keywords are added. 2.1.2 Message static index file The mailbox message static index file is called ".mixindex". It contains a series of CRLF-terminated lines. The first character of the line is a key that identifies the payload of the line, and the remainder of the line is the payload. Key Payload --- ------- S <hex8> ;; update sequence : <uid>:<date>:<size>:<file>:<pos>:<isiz>:<hsiz> ;; per-message record The per-message records contain the following data: <uid> = <hex8> ;; message UID <date> = <yyyymmddhhmmss+zzzz> ;; internal date <size> = <hex8> ;; rfc822.size <file> = <hex8> ;; message data file (0 = .mix file) <pos> = <hex8> ;; message position in file <isiz> = <hex8> ;; message internal data size <hsiz> = <hex8> ;; header size (offset to body) All other keys, and subsequent fields in per-message records, are reserved for future assignment and must be ignored (and may be discarded) by software which does not recognize them. The mailbox metadata file is appended by new mail delivery and rewritten by expunge "burping", and otherwise is not altered. 2.1.3 Message dynamic status file The mailbox message dynamic status file is called ".mixstatus". It contains a series of CRLF-terminated lines. The first character of the line is a key that identifies the payload of the line, and the remainder of the line is the payload. Key Payload --- ------- S <hex8> ;; update sequence : <uid>:<uf>:<sf>:<mod>: ;; per-message record The per-message records contain the following data: <uid> = <hex8> ;; message UID <keys> = <hex8> ;; keyword flags <flag> = <hex4> ;; system flags <mod> = <hex8> ;; date/time last modified (modseq) All other keys, and subsequent fields in per-message records, are reserved for future assignment and must be ignored (and may be discarded) by software which does not recognize them. The mailbox dynamic idex file is rewritten by flag changes (or any future change that alters dynamic data) and is re-read when a session sees that the mtime has changed (atime and ctime are not used). The modseq is an unsigned 32-bit date/time, along with a guarantee that this value can not go backwards. It currently corresponds to the time from time(); however, since it is unsigned, it won't run out until the year 2106. In the future, this may be used as a basic for implementing the IMAP CONDSTORE extension. 2.2 Message data files A mix message file is a regular file with filename starting with ".mix" followed by a <hex8> suffix which indicates the file number. It contains a series of CRLF-terminated lines. By special dispensation, the filename ".mix" is used for file number 0, which was used in experimental versions of mix as a "primary" file (this concept no longer exists). A file number is set to the current modseq when it is created. If a copy or append causes the file to exceed the compiled-in file size limit, a new file is started and the metadata is updated accordingly. Preceeding each message is per-message record with the following format: Key Payload --- ------- ;; per-message record : :<code>:<uid>:<date>:<size>: The per-message records contain the following data: <code> = "msg" ;; fixed code <uid> = <hex8> ;; message UID <date> = <yyyymmddhhmmss+zzzz> ;; internal date <size> = <hex8> ;; rfc822.size The message data begins on the next line Subsequent fields are reserved for future assignment and must be ignored. 3. New mail delivery To deliver a new message, it is necessary to share lock the destination metadata file, then get an exclusive lock on the destination index and status files. Once this is done, the new message data is appended to the new message file. The metadata (UIDLAST value), index, and status files are all updated to add the new message. Then all the destination mailbox files are closed. 4. Mailbox pinging The index and status files are share locked. Initially, sequences are remembered as zero, so at open time they are always "altered". The sequence from the index file is checked; if it is altered the index file is read and processed as follows: . If expunge is permitted, then any messages that are not in the index are reported as having been expunged via mm_expunged(). . new messages are announced via mm_exists()/mm_recent(). Next, the sequence from the status file is checked. If it is altered, the status file is read and the status updated for any message which is new or has an altered modseq in the status file. Altered modseq messages are announced via mm_flags(). Then the index and status files are closed. 4. Flag alteration The status file is exclusive locked. The sequence from the status file is checked. If it is altered, the status file is read and the status updated for any message which is new or has an altered modseq in the status file. Altered modseq messages are announced via mm_flags(). The alterations are then applied for all requested messages, updating the modseq for each requestedmessage which changes flags as a result of the alteration (alterations which do not result in a change do not alter the modseq). Then the status file is rewritten with a new sequence, but only if flags of at least one message was changed. Then the status file is closed. 5. Checkpoint and expunge Checkpoint is identical to expunge, however it skips the step of expunging deleted messages. The index and status files are locked exclusive. If expunging, all deleted messages are expunged from the index and announced via mm_expunged(). The message data is notremoved at this time. If a checkpoint was requested, or if any messages were expunged, or if it remembered that a "burp" was needed, then: . the metadata file is locked exclusive. If this fails, remember that a burp is needed. Otherwise perform a burp: . calculate the file byte ranges occupied by expunged messages . for each file needing "burping", open and slide down subsequent file data on top of the expunged messages . update the index and status files Then the index and status files are closed. 5.1 More details on expunging and "burping" Shared expunge presents a problem due to the requirements of the IMAP protocol. You can't "burp" away a message until you are certain that no sharers have a pointer to any longer. Consequently, for the nonce "burping" out expunged data be defered to an exclusive expunge as in mbx format. If shared burping is ever implemented, then care will be needed not to burp data that a session still relies upon. It's easy enough to burp the index files; just create new index files, deleting the old, and require that you look for a new one appearing at mailbox ping time (when it's safe). The data files are a problem, since we intentionally don't want to keep them open and do want to avoid quota problems by overwriting in place. Also, when you burp you have to change the pointers in the index file. Bottom line: shared burping is too hairy right now, so the first version will do exclusive-only burping and not worry about it. If shared burping is really needed, then that routine will need to be rewritten. Shared burping has been a problem for every other IMAP server. Most get it wrong, and cause terrible confusion to clients (including client crashes). 6. Message data file file roll out strategy The current new message file is finalized, and a new one started, when an append or copy is done that would cause the file to grow to larger than a preconfigured size (MIXDATAROLL). A multi-message copy or append is written into its entirety to a single new message file. In the case of multi-copy, the new message file is switched when the sum of the sizes of all messages to be copied would cause the current new message file to exceed MIXDATAROLL. In the case of multi-append, only the first message is considered; this is due to technical limitations. 7. Error detection Mix detects bad data in the metadata, index, and status files; and declares the stream dead. It does not unilaterally reassign UIDVALIDITY the way that the flat file formats do. When mix reads a header from the message file, it also reads the per-message record and verifies that there is a per-message record there. This is a simple test for message file corruption. It doesn't declare the stream dead; it simply issues an error message and returns a zero-length string for the message header. This makes it possible for the user to fix the mailbox simply by deleting and expunging any messages that are in this state. 8. Reconstruct tool [None of this is implemented yet.] The layout of these files is designed to make the reconstruct tool be as simple as possible. Much of the need for the reconstruct tool is eliminated since the mix format has a much more limited scope of writing than the flat file formats; thus there is "less collateral damage." If the metadata file is lost or corrupted, then all keywords are lost; if the mailbox has any keywords used in the .mixstatus file, it'll be necessary to create some placeholder names. Otherwise, a new UIDVALIDITY can be assigned, and a good UIDLAST value calculated by the reconstruct tool. Since this file is very small, it's not likely to be damaged. If the index file is lost or corrupted, it is possible to reconstruct it with no loss by reading all the data files. However, this could cause expunged but not yet burped messages to reappear. If the status file is lost or corrupted, then flags are lost and will revert to a default state of no flags set. Just deleting the corrupted file is good enough. The reconstruct tool can use the per-message record in the message file to locate messages if the recorded sizes and/or messages are corrupt. If that happens, it will need to rebuild the index file (with associated changes to the metadata file to change the UIDVALIDITY). That should probably be a manual operation and not be part of the default operation or auto-reconstruct. 9. Locking strategy The mix format does not use the traditional c-client /tmp file locking. The metadata file is open and locked whenever the mailbox is open. Normally this is a shared lock, but it will be upgraded to exclusive if the mailbox is expunged. As a guard (since there is no true lock-upgrade/downgrade on UNIX), the index exclusive lock must be acquired first before upgrading to exclusive. The index file is shared locked when reading the index, and exclusive locked (and read) when appending new messages to the index or when expunging (note that expunging also requires an exclusive lock on metadata). Normally, the index file is not open or locked. The status file is shared locked when reading status, and exclusive locked (and read) when updating status. Normally, the status file is not open or locked. It isn't necessary to lock any of the data files as long as we only have exclusive burping. 10. Memory usage The mix format returns a file stringstruct, which is the modern c-client behavior. This prevents imapd from growing to enormous sizes due to a godzillagram (how it affects other programs depends upon what they do with the returned stringstruct). 11. Future extensions Cached ENVELOPE, BODYSTRUCTURE. Cyrus does, and this will eliminate most of the reason to access the data files. Possibly cached overviews, ala NNTP, instead? Support for ANNOTATION. 12. RENAME issues Mix currently makes no attempt to address the IMAP RENAME problem. This occurs when a mailbox is deleted, and another mailbox is renamed with that name in place, no attempt is made to reassign UIDVALIDITY for this mailbox and all the inferior mailboxes. This potentially can cause problems for a disconnected-use client that has cached status for the old mailbox which had that name. The RENAME problem is a well known flaw in the IMAP protocol. Few servers correctly handle it (among other things, not only do all the UIDVALIDITY values have to be changed but this has to be done atomically!). It was a mistake to add RENAME into IMAP, but it's much too late to remove it now.