Re: [Imap-protocol] Re: Efficiently handling sequence numbers

On Wed, Nov 14, 2012, at 01:00 AM, Brandon Long wrote:
> On Sun, Nov 11, 2012 at 6:49 AM, Jan Kundrát <[email protected]> wrote:
> > A graphical MUA typically wants to show a simple statistic like X new, Y
> > unread messages. I can get that number through the STATUS command, but what
> > shall I do when receving EXPUNGE for a message whose flags are not known --
> > shall the number of the unread messages be decreased? Shall I invoke an
> > explicit SEARCH NOT SEEN? Shall I just sync the flags in such case? (Note
> > that  I cannot use STATUS on an already opened mailbox.)
> 
> Anyone know what the point of that restriction is?  We've had at least one
> client ask us if it was ok, and it works fine on our implementation
> (though, its the actual state of the folder, not the possibly out of date
> view the client has).

We're careful in Cyrus to return the view that the client has, so that
RECENT counts match up.  This is done by fetching the status data from
the open index struct rather than the statuscache (which we also update
at the same time, but obviously with RECENT zeroed out, since other
connections don't see those messages as RECENT.  It was kind of a pain
to implement, but it's unconfusing to the clients that way)

> So, I guess some of these are pretty dated at this point, but client
> support is much more recent.  CONDSTORE in particular requires another very
> IMAP specific piece of information in the storage layer which made us wait
> on more client support before taking the expensive plunge.  Our lack of
> ESEARCH support is just an embarrassing result of our hand built parser.

Yes, CONDSTORE is a pain to implement.  If/when you do it, make sure to
consider QRESYNC as well.  In particular you will need to keep track of
the lowest MODSEQ for which you still have "tombstones" for expunged UIDs.

In Cyrus we call that "DELETEDMODSEQ".  We use it not only for qresync:

    if (params->modseq >= mailbox->i.deletedmodseq) {
        /* all records are significant */
        /* List only expunged UIDs with MODSEQ > requested */
    [...]
    }
    else {
        [...]
        /* use the sequence to uid mapping provided by the client to
         * skip over any initial matches - see RFC 5162 section 3.1 */
        [...]
        /* for the rest of the mailbox, we're just going to have to assume
         * every record in the requested range which DOESN'T exist has been
         * expunged, so build a complete sequence */
        [...]
        /* include the space past the final record up to last_uid as well */
    }

But also for our replication protocol - where if we have the full historical
data we can use the same logic as qresync to just send changes to the replica.

For replication we also have a thing called 'sync_crc', which is an algorithm
calculated over the entire state of the mailbox at each end.  If that doesn't
match up after a sync, we know something got corrupted and we do a full resync
(similar to FETCH 1:* FLAGS but with all the internal metadata and annotations
and foo) to bring the mailboxes back to a consistent state.

> I'm willing to believe this is only a problem for our ridiculo distributed
> implementation, but I really dislike having O(n) operations like this which
> are just bound to trip at some number of n.  Maybe I should instead post to
> the imap5 list that not having sequence numbers would be a good idea.

Sequence numbers are a win for one particular use case, which seems to be
falling out of favour more and more in real clients.  Mostly the are sorting
by date headers or some other complex algorithm rather than just showing the
last 'n' records in UID order.

O(n) gets to be a problem once N is in the hundreds of thousands, though it's
surprisingly un-bad.  We now have a search command (XCONVMULTISORT) which
reads in the index data from every mailbox, applies the search program to
every message, and finally sorts all the matches.  It caches to disk, so if
you haven't had a modseq change, and you a query with the same search and
sort parameters, the result can be returned again.  This is very useful for
us because said command also supports ranged returns - so you can ask for the
first 30, or the next 30, or 30 messages starting after a particular item.
Caching results makes paging fast.

I was surprised at just how quickly a search like "UNREAD since:yesterday"
works in our interface (dates get parsed before passing them to IMAP), across
all my folders.  I have a good half a million emails, and when I'm in
conversations mode it has to O(n) sweep the whole thing twice, once for the
search and a second time to combine related messages (so there's a hash lookup
on each record too).  It returns in under half a second.

Of course, the index format is only 120 bytes per message, and it's stored on
SSD, but still - O(n) isn't that scary.

Bron.


-- 
  Bron Gondwana
  [email protected]

_______________________________________________
Imap-protocol mailing list
[email protected]
http://mailman2.u.washington.edu/mailman/listinfo/imap-protocol