Re: [Imap-protocol] Efficiently handling sequence numbers
Timo Sirainen <[email protected]>
| Newsgroups | gmane.mail.imap.general |
|---|---|
| Message-ID | <[email protected]> |
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). _______________________________________________ Imap-protocol mailing list [email protected] http://mailman2.u.washington.edu/mailman/listinfo/imap-protocol