QRESYNC (was: Re: [POLL] Development guidance)

[Bron Gondwana]

On Mon, Nov 05, 2007 at 07:10:08PM -0500, Ken Murchison wrote:
> Bron Gondwana wrote:
> >On Mon, Nov 05, 2007 at 04:58:59PM +0000, David Carter wrote:
> >>On Fri, 2 Nov 2007, Ken Murchison wrote:
> >>
> >>>I'm getting ready to implement the QRESYNC extension for the upcoming
> >>>LEMONADE interop.

Yeah - I have some questions about that.

> >>>1. Leverage delayed expunge which already stores state for
> >>>expunged messages in cyrus.expunge (up until the records are
> >>>purged by cyr_expire).

Now that expunged messages stay in cyrus.index up until they actually
get cleaned up, which is pretty easy - though still a copy.

> >I think that unexpunge should actually be the same as "COPY" where the
> >source is the "deleted" record.  This updating UIDvalidity is just rude,
> >especially if you're only unexpunging a couple of messages from a much
> >bigger mailbox.
> 
> I think I agree.  We have to change the UID of the unexpunged
> message to UIDNEXT, and rename() the message file accordingly.

Which is what I'll be doing when I get to reworking unexpunge shortly :)


OK - my question.  I have two basic implementation choices:

1) add a "removed_modseq" field to the cyrus.index header.  This contains
   the highest modseq of any record which has been actively REMOVED from
   the file by a cyr_expire run.  If "changedsince" is higher than this
   field, then you can just use the information from the modseqs on the
   expunged records.

   If changedsince is older however, you need to assume that a record
   could have been removed from ANY gap, and return all UID gaps in the
   entire file (at least: that are in the requested range(s)).

2) add a "gap_modseq" field to each cyrus.index record.  This is the highest
   modseq of any record that previously existed in the gap between this
   record and the next record.  Obviously, need one in the header as well to
   cover the gap before the first record.


PROS and CONS:
--------------

1) Pro:
  * less space use - just 8 bytes in the header, no increase in record size.
  * simple to calculate - only updated by cyr_expire

1) Con:
  * Two codepaths required - one for the common case and another for fallback
  * Higher bandwidth use in the "stale client" case.
  * Require delayed delete to be enabled

2) Pro:
  * Don't need delayed delete - could even remove the expunged cyrus.index
    records immediately and it would still work.
  * Only one codepath 
  * guaranteed low bandwidth - no re-telling of facts no matter how long 
    between connections.
  
2) Con:
   * Uses 8 bytes per message for the gap_modseq record
   * Extra bookkeeping - need to update a different record when removing an
     expired record.
   * Replication implications - cyr_expire and replication is already going
     to be tricky - but probably means arbitrary bumping of modseq on the
     previous record to guarantee it replicates.  More spurious modseq bumps.


There are things I like about both solutions.  I'm certainly putting a lot of
thought into making all the index integrity and verification stuff replication
safe - i.e. you can do a cyr_expire (at least the bit that unlinks the message
files) at one end without requiring immediate replication of the unlink to
the other end.  This is vital, because otherwise a cyr_expire run would cause
replicaion slowdowns, and the non-expire tasks would be delayed in their
replication!  Particularly if the master had faster disk-IO.

Does anybody have strong opinions one way or the other?  I've played with
both ideas, and they're both viable.  I suspect the deciding factor will be
the likelyhood that clients sync after the expire interval, or alternatively
the number of sites that will want QRESYNC to work efficiently without having
delayed delete.

One nice thing about the new format is that I've separated unlinking the
spool file (message body) from the removal of the cyrus.index record.  So you
can still get the bulk of the disk saving immediately by unlinking, without
losing the qresync data.  Of course - you can't unexpunge any more :)

Bron.