Here's a little something that I think deserves a message of its own, and I'll try to keep this brief so you all read it (you have been reading all my long rambling diatribes, right? They're very insightful...)
UPFRONT ASSUMPTIONS: setting the field: ======================================= A message is uniquely identified in IMAP by three properties. 1) Folder Name 2) UIDVALIDITY 3) UID If these three are unchanged, we are asserting that the message is unchanged. Indeed, any value lower than NEXTUID as delivered via IMAP must never have changed since it was first allocated. This has been further extended with: 4) MODSEQ If the modseq is unchanged, we are asserting that the metadata (flags, etc) of the message is also unchanged. There is another invarient - namely that a message that has once been expunged can never be unexpunged. Further - if you have replication, then this property must hold between your replicas. Any fact given by one server must hold true if you connect to the other server at some later time. CASES WHERE THESE ASSUMPTIONS BREAK DOWN: ========================================= reconstruct: 1.1 a message file is found on disk without a corresponding index record 1.2 an index record is corrupted (CRC failure) unexpunge: 2.1 an expunged record is unexpunged replication: 3.1 a message has been delivered on the replica which is not present on the master 3.2 the same UID is present at both ends but with different content 3.3 tricky case: changes have been made at both ends to flags and modseq. This breaks assumption (4) above. STRATEGIES FOR RECOVERY: ======================== You need to break one of the invarients in all cases. Now, changing the folder name is clearly insane, so drop that. Changing the UIDVALIDITY has some merit - just bump the UIDVALIDITY every time you get an incompatible change on any message. This has two significant downsides: 1) it doesn't handle case 3.2 above. You're still out of sync with the replica 2) most IMAP clients will re-fetch every single message in a large mailbox, even though only one message has a problem. So for all cases except 3.3 we're left with changing the UID. This solves everything except case 3.3, which doesn't need it. You can solve 3.3 by choosing a "winner", copying the metadata to the other side and bumping the modseq at both sides to be higher than the maximum modseq previously present. Remember, the case in the past doesn't matter so long as the present matches and has a higher modseq. There's always a legal transition to that point. The only real downside of the UID bumping technique is that the sort order will change for clients that sort purely on UID - but most clients will sort by INTERNALDATE or SENTDATE or even one of the other interesting fields. They will be unchanged. It's similar to an archive folder into which messages were not copied in chronological order. THE UID UPGRADE APPROACH: ========================= Let's address each case individually: reconstruct: 1.1 a message file is found on disk without a corresponding index record => a) message_parse_file() to create a cache record and fill in all the derived index fields. b) stat.st_mtime for internaldate (we "touch" the file to the internaldate when we deliver it, hopefully it's still sane) c) rename the file to mailbox->i.last_uid + 1 and append the record. 1.2 an index record is corrupted (CRC failure) => this is actually identical to the above case. The corrupted record can either be overwritten with a valid record that's marked as UNLINKED, but otherwise follow along above. unexpunge: 2.1 an expunged record is unexpunged => in this case we actually have a viable index record, so copy the old record, unset the EXPUNGED bit (and possibly the \Deleted flag as well), then (c) as above: rename the file and append the record as mailbox->i.last_uid + 1 replication: 3.1 a message has been delivered on the replica which is not present on the master => two sub cases: 3.1.1) UID is greater than master->i.last_uid. => just copy the message to the master with and append with its current UID. Replica copy remains unchanged. 3.1.2 UID is less than master->i.last_uid. => this will be handled below in 3.2 3.2 the same UID is present at both ends but with different content => 3.1.2 above is a special case where the file doesn't actually exist any more on the master, but it obviously did at some point because later UIDs have been allocated. Either way, we need to renumber the replica record. Two cases: 3.2.1) message still exists on the master. => follow the unexpunge process for BOTH the replica and master records. Create two new appends, one for each message, with the flags and content of the old record. This involves copying back from the server - both the body and the flags - and creating a new record. Then both the master and replica copies of the OLD UID are expunged. 3.2.2) message no longer on the master => just the same, but no copy of the master record, since it's already been expunged. 3.3 tricky case: changes have been made at both ends to flags and modseq. This breaks assumption (4) above. => if the modseq or last_modified on the replica is higher, copy the flags back. Otherwise, don't. Bump the MODSEQ on the record up to highestmodseq+1 and save. Next sync will apply the changes to the other end, and we'll be back in agreement. SUMMARY: ======== UID promotion is a totally IMAP-protocol complient method to repair issues while never letting client caches reflect a no-longer-true view of the server state. All transitions are legal IMAP. It also minimises client resynchronisation cost. Only UIDs which the client could legitimately believe are already expunged or have different content are changed, and only those messages need to be re-copied by clients which perform agressive caching. By keeping UIDVALIDITY intact, impact on clients is minimised. This protocol also correctly handles recovery from split brain scenarios, possibly including more than one replica. It can also be applied to IMAP <=> IMAP synchronisation and even cached proxying in a pinch - though it benefits greatly from being able to choose the UID you want to store a new message with. Via IMAP you could wind up doing a lot of speculative append and expunge cycles on both ends to get the UIDs to match again if things went split-brain. =============== And that wasn't as short as I'd hoped. My apologies. Thanks for reading. Any questions, please ask while it's fresh in my brain! This protocol has been implemented in unexpunge and replication for cyrus-future, soon hopefully to become Cyrus 2.4. I'm working on making it happen in reconstruct now as well, hence my other question recently :) Regards, Bron.