Re: [Imap-protocol] Efficiently handling sequence numbers

On Fri, Nov 9, 2012 at 1:53 PM, Timo Sirainen <[email protected]> wrote:

> On 9.11.2012, at 23.45, Brandon Long wrote:
>
> > On Fri, Nov 9, 2012 at 1:37 PM, Timo Sirainen <[email protected]> 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

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