UID Promotion Logic

[Bron Gondwana]

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.