I don't think anyone uses dbox currently, so the whole format could still be redesigned. So I was thinking about doing two major changes:

1. Rely on index files a lot more. The flags are already stored in index files, so there's no need to waste I/O updating them to dbox files all the time. They could still be updated (if indexes get deleted, the flags aren't all gone), but less often.

2. Require fcntl() locking. Currently dbox uses dotlocks which is slow.

Cydir could be a good alternative also once index file code is made a bit more robust. Perhaps I could implement single instance attachments for cydir too..

Locking

The current dbox "index" file would be gone. It's pretty useless. Replace it with a whole new index file. Or perhaps it should be called "locks" file or something.

The locks file would contain records: <file id> <lock timestamp> <status>. So something like:

<header> 1 4645a60f 0 2 00000000 N 3 00000000 D

That would mean that the first file is locked by some process, either for appending or expunging. The 2nd and 3rd files aren't locked. New messages can't be appended to 2nd file anymore. 3rd file is already deleted and this record needs to be removed when rewriting the file.

Locking a dbox file for either appends or expunges is done like:

1. See if timestamp is zero

• If not, see if it's older than .. let's say a day or so .. a) Yes: Continue to 2. b) No: Assume the file is locked

2. Do fcntl() byte range lock over the record line in the locks file.

• If it failed, the record is locked

3. Write the timestamp.
4. Compare stat() and fstat() inodes to see if the file was rebuilt

• If yes, reopen the file and goto 1

5. File is now locked. Do the append/expunge.
6. Write timestamp to zero.
7. Unlock the byte range.

If a file is locked, append will try another file and expunge will mark the message as expunged instead of actually expunging it yet.

Note that the locks file is read without locking. This is safe because data is never moved within the file, and it doesn't matter if the timestamp isn't read correctly always. The timestamp check is only an optimization. Actually I'm not sure if it would be better not to have the timestamp at all.

Deleted records will stay in the file until the file is rebuilt. If a deleted record is noticed in the file, the process tries to lock the whole locks file. If it succeeds, it proceeds with writing the non-deleted records to a temporary file and rename()ing it over the locks file.

Appending

1. Find the first file in the locks file that has appendable=0

• If no such file was found, go to "create a new file" logic as described below

2. Lock the file record
3. Verify from the file's headers that this file can actually be appended to

• If messages have been expunged from a dbox file, it can't be safely appended to anymore.
• Other reasons include eg. configurable max. file size and daily rotations

4. Write the mail
5. Lock locks file's header
6. Get the UID from "next uid" field and update it
7. Unlock the header
8. Unlock the file record
9. Update index file

Create a new file logic:

1. Create a temporary file
2. Write the messages there
3. Lock locks file's header (including fstat() / stat() rebuild check)
4. See what the latest file ID is in the file
5. rename() temp fail to msg.
6. Lock locks file for the range of the to-be-written record below
7. Write the new record to locks file
8. Go to step 6 in the original append logic

Syncing / expunging

If locks file's header's "next uid" doesn't match the one currently in index file, the appending crashed between steps 6 and 9. Find the new message(s) and append them to index file.

If the locks file is completely gone , rebuild it by going through all the msg.* files in the directory.

If "expunge counter" (see below) doesn't match in locks file's header vs. index file header, go through all the msg.* files to see if a message exists in multiple files. If found, remove the duplicates.

Typically neither of the above happens, so the only thing to do here is to write changes from index file to dbox files. This may mean flag changes once in a while, but most importantly expunges will always be synced.

Initially figure out what files require expunging. Try to create a single lock range that includes all of them. If there are non-zero lock timestamps in that range, create multiple ranges.

If a file couldn't be locked, the expunge is done by updating expunge-flag in the file. This can be done without locking (see below for flag updates).

If a file was successfully locked, the expunging is done by:

1. Update "expunge offset" in file header to the offset of the first expunged message. If expunge offset is non-zero, the file is treated as non-appendable. Also when rebuilding and finding the same message from multiple files, this field is used to figure out which file should be truncated.

2. Copy the rest of the non-expunged messages to a new temporary file and add the file to locks file using the "Create a new file" logic described for appends. Instead of updating "next uid" field, update "expunge counter" field.

3. ftruncate() the old file.

4. Update "expunge counter" in index file.

Sync locking

If there is one big "sync lock", then flags can be updated in any file with relying only on that lock. Some files may be locked, but they're locked for appends so flag updates (and other record updates as well) are safe.

It would be interesting to make it work without that sync lock though, so that multiple processes could be syncing dbox at the same time. But there probably isn't much point. If the sync is locked, there's no real requirement to do the syncing at all then, it's just left to be done later.

If multiple processes were syncing at the same time, the only problem would come from flag updates. Either the files would have to be locked for flag updates (with waiting locks, bad bad), or it would need to be able to handle the situation when a flag was written just when another process expunged messages from the file and truncated it. That could be done by checking (one way or another) after the flag write if a truncation had happened, and if so do the truncation again.

Preventing out of sync disconnects

Reading messages from dbox files requires no locking, so it's possible that while one session is reading a message another session goes and expunges the message by truncating the file. The only way to handle this situation is to disconnect the client.

Also even if the message wasn't in the middle of being read, this kind of a out-of-sync could happen if a session hasn't synced itself yet (no NOOP/IDLE/etc. for a while) and tries to begin reading an expunged message.

These could be avoided if the expunging process knew that there are other processes that still know about the message, so it could just mark the message as expunged instead of actually doing it.

I think this could be done with yet another file that tracks what messages are expunged. The file would contain "dovecot.index.log file sequence + offset" records. Whenever message(s) are expunged, a new seq +offset is written containing the position in the log file for that transaction.

All the processes accessing the mailbox would then read lock the file from eof to infinity. The lock is updated whenever mailbox is synced (and being careful not to have race conditions there).

So syncing process would then try if it can write lock the file from "last real expunge" log position to end of file. If not, then using some binary search find the position how far it can be locked. If it managed to update the write lock position at least some, the messages up to that far in the transaction log can be expunged safely.

One problem with this is that the file needs to be rotated once in a while so that it won't grow infinitely. This can be done only if the write lock can include the whole file (including infinity). And that can be done only if there's a single process having the mailbox open, which may never happen with shared mailboxes.

I think I'll leave this feature to be implemented later. It's extra overhead that's probably rarely useful.

Single instance attachments

I'll change the dbox messages to have variable sized headers. The header could then contain information such as "at offset 5000 insert 11241242 bytes from file AB123427852".

Fast copying

Would be nice if copying a message from one mailbox to another wouldn't require actually reading+writing the whole message contents. But I can't really figure out how to implement this without requiring that there is only a single dbox storage which contains the mails for all the mailboxes, and the mailboxes themselves are just Dovecot's index files containing pointers to the dbox storage.

The problem with having everything in one storage is that if the index files are broken, the messages can't be placed into correct mailboxes anymore.

Although one possibility would be treat mailboxes a bit similarly than keywords. So that when a message is copied to another mailbox, the message in dbox file is updated to contain information that it exists in such and such mailboxes. Hmm. Perhaps that would be good enough, yes.