mailing list archives

I'm drawing a blank on how to efficiently handle sequence numbers without
O(n) operations (where n is the number of messages in a folder).

You can store the uids for a folder on disk in sorted order, but because
every connection has its own "view" of that data, and the view itself is
only allowed to change for a connection at specific points, it seems like
the connection needs a copy of that uidlist.

Now, its possible you can maintain an in-memory "diff" between the view and
the actual state.  Or maybe you're using a data store where you can
maintain access to the view based on timestamp.  And then you also keep a
log of changes so you know what to send to the client at a sync checkpoint.
 Even then, there aren't many efficient ways to answer the question of
"give me the 500th entry in that table".  If you store the table as fixed
size records, sure, but then you have to rewrite the whole table, or use
some sort of fixed blocks so you can update only from change to end, but I
don't see what data storage you're using to do that and keep multiple
versions.  Plus, this is starting to sound like using some serious data
storage beyond what I usually see in software like this.

So, what do people use?  IMAP allows 4B messages per folder, right?  Even
in a fairly compact format, that's a lot of data to be either re-writing
constantly or loading completely and caching in memory.

I guess an on-disk b+ tree could be modified to keep counts of each
sub-tree in a node, and then you'd just need to re-write all the nodes up
the list,  is that a widely supported feature of such data structures?

Or am I missing something else obvious?

Brandon
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman13.u.washington.edu/pipermail/imap-protocol/attachments/20121109/7ca2546f/attachment.html>

On 9.11.2012, at 23.15, Brandon Long wrote:

> I'm drawing a blank on how to efficiently handle sequence numbers without O(n) operations (where n is the number of messages in a folder).

I don't think it's a real concern. A long time ago I wrote some kind of a binary tree based algorithm to do expunges in O(log n), but eventually I just realized it's way too much trouble (and I'm pretty sure it had some O(n) operations hidden in there at some intervals). Small fixed size records (especially a simple uids[] array) works just fine for probably up to tens of millions of mails, and just about no one has that many mails in one mailbox.

Dovecot nowadays doesn't rewrite the whole index to disk every time you delete a mail. It appends "uid 123 expunged" to a log file and updates the index in memory (memmove()ing data around). Then once in a while it recreates the index. Works nicely. I've wondered about making this two arrays though, so that you'd have the uids[] array and other_fixed_data[] array and expunge would only need to move data in the uids[] array, but I don't know if that really is a good idea. Probably not.

Also large mailboxes could be split to "old mails" and "new mails" indexes. If you have a huge mailbox, it's very unlikely that any old messages get expunged. Then you only need to append to the old index and rewrite the small new index.

On Fri, Nov 9, 2012 at 1:37 PM, Timo Sirainen <tss@iki.fi> wrote:

> On 9.11.2012, at 23.15, Brandon Long wrote:
>
> > I'm drawing a blank on how to efficiently handle sequence numbers
> without O(n) operations (where n is the number of messages in a folder).
>
> I don't think it's a real concern. A long time ago I wrote some kind of a
> binary tree based algorithm to do expunges in O(log n), but eventually I
> just realized it's way too much trouble (and I'm pretty sure it had some
> O(n) operations hidden in there at some intervals). Small fixed size
> records (especially a simple uids[] array) works just fine for probably up
> to tens of millions of mails, and just about no one has that many mails in
> one mailbox.
>
> Dovecot nowadays doesn't rewrite the whole index to disk every time you
> delete a mail. It appends "uid 123 expunged" to a log file and updates the
> index in memory (memmove()ing data around). Then once in a while it
> recreates the index. Works nicely. I've wondered about making this two
> arrays though, so that you'd have the uids[] array and other_fixed_data[]
> array and expunge would only need to move data in the uids[] array, but I
> don't know if that really is a good idea. Probably not.
>
> Also large mailboxes could be split to "old mails" and "new mails"
> indexes. If you have a huge mailbox, it's very unlikely that any old
> messages get expunged. Then you only need to append to the old index and
> rewrite the small new index.
>
> So, do you load the full sequence into memory on SELECT?

Brandon
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman13.u.washington.edu/pipermail/imap-protocol/attachments/20121109/a83cfa61/attachment.html>

On 9.11.2012, at 23.45, Brandon Long wrote:

> On Fri, Nov 9, 2012 at 1:37 PM, Timo Sirainen <tss@iki.fi> wrote:
> On 9.11.2012, at 23.15, Brandon Long wrote:
> 
> > I'm drawing a blank on how to efficiently handle sequence numbers without O(n) operations (where n is the number of messages in a folder).
> 
> I don't think it's a real concern. A long time ago I wrote some kind of a binary tree based algorithm to do expunges in O(log n), but eventually I just realized it's way too much trouble (and I'm pretty sure it had some O(n) operations hidden in there at some intervals). Small fixed size records (especially a simple uids[] array) works just fine for probably up to tens of millions of mails, and just about no one has that many mails in one mailbox.
> 
> Dovecot nowadays doesn't rewrite the whole index to disk every time you delete a mail. It appends "uid 123 expunged" to a log file and updates the index in memory (memmove()ing data around). Then once in a while it recreates the index. Works nicely. I've wondered about making this two arrays though, so that you'd have the uids[] array and other_fixed_data[] array and expunge would only need to move data in the uids[] array, but I don't know if that really is a good idea. Probably not.
> 
> Also large mailboxes could be split to "old mails" and "new mails" indexes. If you have a huge mailbox, it's very unlikely that any old messages get expunged. Then you only need to append to the old index and rewrite the small new index.
> 
> So, do you load the full sequence into memory on SELECT?

Yes, first read/mmap the index snapshot into memory and then apply any expunges and other changes to it from the log. It could be optimized so that all the expunges are done in one O(n) scan of the index instead of multiple separate of memmove()s, but it hasn't been a real problem so far. I don't have the old/new index separation yet, but I think that would be a good idea to add when the mailbox size grows past maybe 100k messages (or maybe even sooner).

On Fri, Nov 9, 2012 at 1:53 PM, Timo Sirainen <tss@iki.fi> wrote:

> On 9.11.2012, at 23.45, Brandon Long wrote:
>
> > On Fri, Nov 9, 2012 at 1:37 PM, Timo Sirainen <tss@iki.fi> wrote:
> > On 9.11.2012, at 23.15, Brandon Long wrote:
> >
> > > I'm drawing a blank on how to efficiently handle sequence numbers
> without O(n) operations (where n is the number of messages in a folder).
> >
> > I don't think it's a real concern. A long time ago I wrote some kind of
> a binary tree based algorithm to do expunges in O(log n), but eventually I
> just realized it's way too much trouble (and I'm pretty sure it had some
> O(n) operations hidden in there at some intervals). Small fixed size
> records (especially a simple uids[] array) works just fine for probably up
> to tens of millions of mails, and just about no one has that many mails in
> one mailbox.
> >
> > Dovecot nowadays doesn't rewrite the whole index to disk every time you
> delete a mail. It appends "uid 123 expunged" to a log file and updates the
> index in memory (memmove()ing data around). Then once in a while it
> recreates the index. Works nicely. I've wondered about making this two
> arrays though, so that you'd have the uids[] array and other_fixed_data[]
> array and expunge would only need to move data in the uids[] array, but I
> don't know if that really is a good idea. Probably not.
> >
> > Also large mailboxes could be split to "old mails" and "new mails"
> indexes. If you have a huge mailbox, it's very unlikely that any old
> messages get expunged. Then you only need to append to the old index and
> rewrite the small new index.
> >
> > So, do you load the full sequence into memory on SELECT?
>
> Yes, first read/mmap the index snapshot into memory and then apply any
> expunges and other changes to it from the log. It could be optimized so
> that all the expunges are done in one O(n) scan of the index instead of
> multiple separate of memmove()s, but it hasn't been a real problem so far.
> I don't have the old/new index separation yet, but I think that would be a
> good idea to add when the mailbox size grows past maybe 100k messages (or
> maybe even sooner).
>
>
Ah, ok.  If only loading the data was as simple as an mmap for us ;)  At
this point, I think the data only moves through 5 separate servers on 4
machines, usually in the same data center though.  That, and of course we
don't use UIDs as our primary message-id, so we're looking at 32 bits for
the uid and 64 bits for the message-id, so 96 bits minimum per message,
which means a 10M message folder is loading 120MB, probably another 30MB of
overhead in protocol buffers (not really meant for millions of entries).

Brandon
My other computer is a datacenter
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman13.u.washington.edu/pipermail/imap-protocol/attachments/20121109/aa6eb548/attachment.html>

On 10.11.2012, at 0.05, Brandon Long wrote:

> > So, do you load the full sequence into memory on SELECT?
> 
> Yes, first read/mmap the index snapshot into memory and then apply any expunges and other changes to it from the log. It could be optimized so that all the expunges are done in one O(n) scan of the index instead of multiple separate of memmove()s, but it hasn't been a real problem so far. I don't have the old/new index separation yet, but I think that would be a good idea to add when the mailbox size grows past maybe 100k messages (or maybe even sooner).
> 
> 
> Ah, ok.  If only loading the data was as simple as an mmap for us ;)  At this point, I think the data only moves through 5 separate servers on 4 machines, usually in the same data center though.  That, and of course we don't use UIDs as our primary message-id, so we're looking at 32 bits for the uid and 64 bits for the message-id, so 96 bits minimum per message, which means a 10M message folder is loading 120MB, probably another 30MB of overhead in protocol buffers (not really meant for millions of entries).

Sure, Dovecot has also similar extra metadata, more or less depending on the mailbox format. Keep the user typically assigned to the same backend server and you need to fetch the 120MB only once (or somewhat rarely). Send the data back in smaller diffs to avoid constantly re-uploading the whole 120MB file when it changes. I've been working on an object storage optimized backend for Dovecot these last few months. I think it could work well for GMail as well ;)

Anyway, like I mentioned several times already :), I think the most important optimization for huge mailboxes is the separation of old/new data. You most likely don't need to even download/read the old data normally. (Although many IMAP clients fetch 1:* flags after SELECT, but even if IMAP server had no problems with that, the IMAP client would probably be unusably slow so that's not a real problem.)

On Friday, 9 November 2012 23:16:19 CEST, Timo Sirainen wrote:
> (Although many IMAP clients fetch 1:* flags after SELECT, but 
> even if IMAP server had no problems with that, the IMAP client 
> would probably be unusably slow so that's not a real problem.)

In Trojita, I always want to establish a fully synchronized view to a mailbox, which means either CONDSTORE or QRESYNC or a blind 1:* FLAGS fetch upon connecting to a mailbox, yes. At first, this looks like an ugly inefficiency, but I believe that it's more or less the only reasonable way.

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.)

It's true that one can probably come up with a pretty good heuristic like "on mailboxes >10k messages, it's unlikely to ever see expunges from the beginning, so let's load the flags only on demand" and defer to a full sync upon detecting a race. However, because there are extensions (CONDSTORE, QRESYNC) which make this synchronization painless and extremely efficient, I haven't decided to invest my time in optimizing Trojita for interaction with the legacy servers who don't implement these optimizations.

Some of these servers don't even support ESEARCH for an efficient compression of the UID ranges which are needed in any client wishing to maintain its own offline cache (for essentially the same reason -- you want to remove data from the cache upon seeing an EXPUNGE, but in order to do that, you have to know the UID of the message which was expunged or come up with creative ways of finding out that infromation on demand, which is far from trivial -- you could for example ask for the UID of just two messages, the one before the message being expunged and the second one right after it, but then you have to deal with network disconnects in some complicated way, and you would still have to solve this for expunges which have happened while offline, between your reconnects).

In short, yep, there are ample opportunities for clients to make the interoperability "better", but I somehow don't believe that clients should be responsible for this -- there are extensions designed to make this problem go away, and the two most widely deployed open source IMAP servers have implemented them for quite some time. It's a sad reality that many proprietary IMAP server vendors don't bother with ESEARCH, CONDSTORE and QRESYNC.

With kind regards,
Jan

On Sun, Nov 11, 2012 at 6:49 AM, Jan Kundr?t <jkt@flaska.net> wrote:

> On Friday, 9 November 2012 23:16:19 CEST, Timo Sirainen wrote:
>
>> (Although many IMAP clients fetch 1:* flags after SELECT, but even if
>> IMAP server had no problems with that, the IMAP client would probably be
>> unusably slow so that's not a real problem.)
>>
>
> In Trojita, I always want to establish a fully synchronized view to a
> mailbox, which means either CONDSTORE or QRESYNC or a blind 1:* FLAGS fetch
> upon connecting to a mailbox, yes. At first, this looks like an ugly
> inefficiency, but I believe that it's more or less the only reasonable way.
>

Probably depends on which flags you care about, but the SEARCH method is
certainly less data transfered if you only care about certain flags.  I
estimated that a 100k folder will take around 6MB of data to do the FETCH
1:* (UID FLAGS) response.  Obviously, ESEARCH is even more efficient.


> 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).

Obviously an ESEARCH (RETURN COUNT) NOT SEEN would work here, but may not
be as optimized (note to self, optimize this case).


> It's true that one can probably come up with a pretty good heuristic like
> "on mailboxes >10k messages, it's unlikely to ever see expunges from the
> beginning, so let's load the flags only on demand" and defer to a full sync
> upon detecting a race. However, because there are extensions (CONDSTORE,
> QRESYNC) which make this synchronization painless and extremely efficient,
> I haven't decided to invest my time in optimizing Trojita for interaction
> with the legacy servers who don't implement these optimizations.
>
> Some of these servers don't even support ESEARCH for an efficient
> compression of the UID ranges which are needed in any client wishing to
> maintain its own offline cache (for essentially the same reason -- you want
> to remove data from the cache upon seeing an EXPUNGE, but in order to do
> that, you have to know the UID of the message which was expunged or come up
> with creative ways of finding out that infromation on demand, which is far
> from trivial -- you could for example ask for the UID of just two messages,
> the one before the message being expunged and the second one right after
> it, but then you have to deal with network disconnects in some complicated
> way, and you would still have to solve this for expunges which have
> happened while offline, between your reconnects).
>
> In short, yep, there are ample opportunities for clients to make the
> interoperability "better", but I somehow don't believe that clients should
> be responsible for this -- there are extensions designed to make this
> problem go away, and the two most widely deployed open source IMAP servers
> have implemented them for quite some time. It's a sad reality that many
> proprietary IMAP server vendors don't bother with ESEARCH, CONDSTORE and
> QRESYNC.
>

ESEARCH - 11/2006
CONDSTORE 6/2006
QRESYNC 3/2008

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.

Anyways, these all help with the client synchronization, but don't really
help with the server having to load this information (Well, the client as
well) even if it doesn't sync down to the client.

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.

Brandon
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman13.u.washington.edu/pipermail/imap-protocol/attachments/20121113/8e48c70d/attachment.html>

On 11/14/2012 01:00 AM, Brandon Long wrote:
> Anyone know what the point of that restriction is?

It broke a server, mrc's perhaps, which used a locking scheme where 
select locks a mailbox and status does too, and the two locks conflict 
even though they are owned by the same process.

Arnt
(back from the dead, sorry about the prolonged silence)

On Wed, Nov 14, 2012, at 01:00 AM, Brandon Long wrote:
> On Sun, Nov 11, 2012 at 6:49 AM, Jan Kundr?t <jkt@flaska.net> 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
  brong@fastmail.fm

On Wed, Nov 14, 2012, at 09:56 AM, Arnt Gulbrandsen wrote:
> On 11/14/2012 01:00 AM, Brandon Long wrote:
> > Anyone know what the point of that restriction is?
> 
> It broke a server, mrc's perhaps, which used a locking scheme where 
> select locks a mailbox and status does too, and the two locks conflict 
> even though they are owned by the same process.

Yeah, that happens in Cyrus too.  So we check if there's a selected
mailbox and if it has the same name as the one being asked for a
status response, and if so we call index_status() on the index state
rather than statuscache_status() with the mailbox name.

Still, IMAP is already a crazy-stateful protocol, so what's one
more piece of state for every client track of on every connection
and never get wrong...

Bron.
-- 
  Bron Gondwana
  brong@fastmail.fm