4 ms·

IMAP was an okay protocol for its time, but in my experience it's basically mindbogglingly bad by current standards. The root of the reason why is the whole con

by Felz 7y ago

IMAP was an okay protocol for its time, but in my experience it's basically mindbogglingly bad by current standards. The root of the reason why is the whole concept of "message sequence numbers", which as far as I know are extremely difficult to implement in a scalable and performant way. Basically, all messages in a mailbox are numbered from 1 to N, and you can reference a message by number, and when a message is deleted all message numbers above it shift down by one. But since this could confuse clients that are sending inflight requests, you can't start translating from the new shifted-down-by-one numbers until you've told your clients about it, which could take a theoretically unbounded amount of time. One implementation of this I've seen is to get a list of every UID in a mailbox at time of selection, and then update that as clients are informed of new or deleted mail. Needless to say, that's a bit problematic with short-lived or multiple connections. So if your mailbox gets too big, too bad. This ends up complicating the client: probably influencing rules 1, 3, part of 5, and 8 listed here. (1) You can't have concurrent mailbox access because it might mess up MSNs reified to disk, (3) you can't have connections live too long because they passively eat up RAM with queued updates and a stored MSN list, (5) there are perfectly good UIDs to reference messages with that you have to learn alongside message sequence numbers, and (8) because opening a new session can be heavy.

pjc50 7y ago
It was bad even 20 years ago, I remember a discussion when we were trying to implement something coining the phrase "University of Washington brain damage". It seems to have been extremely tightly tied to the UW-IMAP implementations. The need for a better protocol is why JMAP exists: https://jmap.io/spec-core.html https://jmap.io/spec-core.html Although I see their point about non-REST, I think there's still a case for having a REST flavour available even if it may not be the most efficient. I wonder if anyone's tried mail delivery over git repo yet.
- hyperrail 7y ago
  > University of Washington brain damage This phrase made me laugh, because UW imapd was largely written by Mark Crispin, who invented the IMAP protocol! It seems that in about 2007, Crispin forked UW IMAP to create his own IMAP server, "Panda IMAP" [1], which at least one website claims to be "fully compliant" with the IMAP RFCs while UW IMAP is not. [2] [1] https://github.com/jonabbey/panda-imap https://github.com/jonabbey/panda-imap [2] https://imapwiki.org/ImapTest/ServerStatus https://imapwiki.org/ImapTest/ServerStatus
- Boulth 7y ago
  > Although I see their point about non-REST, I think there's still a case for having a REST flavour available even if it may not be the most efficient. I was pretty disappointed when I found out how ugly are JMAP requests. I'd also like to see REST variant as messages and their parts should be easily mappable to resources. Too bad SMTP was not also included in JMAP. ActivityPub comes really close to SMTP over HTTP/JSON in my opinion.
throw0101a 7y ago
> Basically, all messages in a mailbox are numbered from 1 to N, and you can reference a message by number, and when a message is deleted all message numbers above it shift down by one. There is no reason technical why this shifting has to happen. If there are ten messages on session creation, and message UID 3 is deleted, you then have UIDs 1-2,4-10. If the server wishes to shift messages over it can, but it must bump UIDVALIDITY, which tells clients that there is a 'new generation' of UIDs for the given folder. But as long as the server's index of UID-to-message is not lost, there's no reason why renumbering has to occur. It's no different than having an AUTO_INCREMENT int column in MySQL: you just keep going up without bothering to fill in any 'holes'. That said, folders and messages can now be assigned UUIDs: * https://tools.ietf.org/html/rfc8474 https://tools.ietf.org/html/rfc8474
- jcranmer 7y ago
  GP is talking about message sequence numbers, not UIDs. Message sequence numbers are literally from 1 to N, and should you delete (expunge) a message, the sequence number of everything subsequent is decremented by 1 to keep 1 to N. It is pretty much impossible to write a modern mail client relying on message sequence numbers, since there are too many ways the bookkeeping go wrong; so everyone uses UIDs (or UUIDs) nowadays wherever possible.
sergiosgc 7y ago
> Basically, all messages in a mailbox are numbered from 1 to N, and you can reference a message by number, and when a message is deleted all message numbers above it shift down by one. But since this could confuse clients that are sending inflight requests, you can't start translating from the new shifted-down-by-one numbers until you've told your clients about it, which could take a theoretically unbounded amount of time. Message ids are monotonically increasing, but not necessarily consecutive. You may need to renumber when you hit the 32-bit ceiling, but that is much less frequent than what you describe. Worst case scenario, you can disconnect unresponsive clients when renumbering, clients behave well on disconnects. This invalidates your conclusions. > (1) You can't have concurrent mailbox access because it might mess up MSNs reified to disk You can. Renumbering is not frequent. > (3) you can't have connections live too long because they passively eat up RAM with queued updates and a stored MSN list My dovecot IMAP processes use an average of 5MB reserved memory, of which 4MB is shared memory, so a server with 100GB memory can hold close to 100k connections. > (8) because opening a new session can be heavy. Monitoring tells me that on loaded production servers, session open + select + list + logout occurs comfortably in less than 100ms. That's not heavy. Dovecot starts to fail on mailboxes with about a million messages. It's a limit I can live with. Users have learned to archive messages by date.
- fanf2 7y ago
  IMAP has two ways of numbering messages. It is important to be clear whether you are discussing message sequence numbers (which are dense, and compacted on EXPUNGE) or unique IDs (which are not compacted). GP was complaining about MSNs, your reply is about UIDs.
- Felz 7y ago
  As fanf2 said, MSNs != UIDs. Also, I didn't mean to imply that MSNs are an insurmountable limitation for performance, they just complicate things a lot. I'm not familiar with Dovecot's code or very good at reading C, but I think part of how they handle it is here: https://github.com/dovecot/core/blob/81b5b188c478ec36bea8bda8fcad1e5f32ac612b/src/lib-index/mail-index-private.h https://github.com/dovecot/core/blob/81b5b188c478ec36bea8bda... Basically, building a mail index for UID<->MSN translation that can serialize to disk, which would explain how it doesn't necessarily need absurd amounts of RAM and can select fast, probably at heavy cost when EXPUNGeing old messages. I'm sure there were worse implementations that did just maintain it all in RAM way back in the day, and still some that do (like the one I ran into).
ball_of_lint 7y ago
This sounds like exactly the situation where you would want to use a persistent tree. For a log(n) overhead, you can keep the ordering of all the messages in your mailbox at any given point in time. Then you don't need to inform clients unless a new message is added that they might want to reference. Otherwise you just keep track of the state that client is operating on and use the old state to let you apply their actions to the new state.
- Felz 7y ago
  Yea, I think you basically do need one of these: https://en.wikipedia.org/wiki/Order_statistic_tree https://en.wikipedia.org/wiki/Order_statistic_tree They're somewhat obscure though.

by Felz 7y ago

pjc50 7y ago

It was bad even 20 years ago, I remember a discussion when we were trying to implement something coining the phrase "University of Washington brain damage". It seems to have been extremely tightly tied to the UW-IMAP implementations. The need for a better protocol is why JMAP exists: https://jmap.io/spec-core.html https://jmap.io/spec-core.html Although I see their point about non-REST, I think there's still a case for having a REST flavour available even if it may not be the most efficient. I wonder if anyone's tried mail delivery over git repo yet.

hyperrail 7y ago
> University of Washington brain damage This phrase made me laugh, because UW imapd was largely written by Mark Crispin, who invented the IMAP protocol! It seems that in about 2007, Crispin forked UW IMAP to create his own IMAP server, "Panda IMAP" [1], which at least one website claims to be "fully compliant" with the IMAP RFCs while UW IMAP is not. [2] [1] https://github.com/jonabbey/panda-imap https://github.com/jonabbey/panda-imap [2] https://imapwiki.org/ImapTest/ServerStatus https://imapwiki.org/ImapTest/ServerStatus
Boulth 7y ago
> Although I see their point about non-REST, I think there's still a case for having a REST flavour available even if it may not be the most efficient. I was pretty disappointed when I found out how ugly are JMAP requests. I'd also like to see REST variant as messages and their parts should be easily mappable to resources. Too bad SMTP was not also included in JMAP. ActivityPub comes really close to SMTP over HTTP/JSON in my opinion.

throw0101a 7y ago

> Basically, all messages in a mailbox are numbered from 1 to N, and you can reference a message by number, and when a message is deleted all message numbers above it shift down by one. There is no reason technical why this shifting has to happen. If there are ten messages on session creation, and message UID 3 is deleted, you then have UIDs 1-2,4-10. If the server wishes to shift messages over it can, but it must bump UIDVALIDITY, which tells clients that there is a 'new generation' of UIDs for the given folder. But as long as the server's index of UID-to-message is not lost, there's no reason why renumbering has to occur. It's no different than having an AUTO_INCREMENT int column in MySQL: you just keep going up without bothering to fill in any 'holes'. That said, folders and messages can now be assigned UUIDs: * https://tools.ietf.org/html/rfc8474 https://tools.ietf.org/html/rfc8474

jcranmer 7y ago
GP is talking about message sequence numbers, not UIDs. Message sequence numbers are literally from 1 to N, and should you delete (expunge) a message, the sequence number of everything subsequent is decremented by 1 to keep 1 to N. It is pretty much impossible to write a modern mail client relying on message sequence numbers, since there are too many ways the bookkeeping go wrong; so everyone uses UIDs (or UUIDs) nowadays wherever possible.

sergiosgc 7y ago

> Basically, all messages in a mailbox are numbered from 1 to N, and you can reference a message by number, and when a message is deleted all message numbers above it shift down by one. But since this could confuse clients that are sending inflight requests, you can't start translating from the new shifted-down-by-one numbers until you've told your clients about it, which could take a theoretically unbounded amount of time. Message ids are monotonically increasing, but not necessarily consecutive. You may need to renumber when you hit the 32-bit ceiling, but that is much less frequent than what you describe. Worst case scenario, you can disconnect unresponsive clients when renumbering, clients behave well on disconnects. This invalidates your conclusions. > (1) You can't have concurrent mailbox access because it might mess up MSNs reified to disk You can. Renumbering is not frequent. > (3) you can't have connections live too long because they passively eat up RAM with queued updates and a stored MSN list My dovecot IMAP processes use an average of 5MB reserved memory, of which 4MB is shared memory, so a server with 100GB memory can hold close to 100k connections. > (8) because opening a new session can be heavy. Monitoring tells me that on loaded production servers, session open + select + list + logout occurs comfortably in less than 100ms. That's not heavy. Dovecot starts to fail on mailboxes with about a million messages. It's a limit I can live with. Users have learned to archive messages by date.

fanf2 7y ago
IMAP has two ways of numbering messages. It is important to be clear whether you are discussing message sequence numbers (which are dense, and compacted on EXPUNGE) or unique IDs (which are not compacted). GP was complaining about MSNs, your reply is about UIDs.
Felz 7y ago
As fanf2 said, MSNs != UIDs. Also, I didn't mean to imply that MSNs are an insurmountable limitation for performance, they just complicate things a lot. I'm not familiar with Dovecot's code or very good at reading C, but I think part of how they handle it is here: https://github.com/dovecot/core/blob/81b5b188c478ec36bea8bda8fcad1e5f32ac612b/src/lib-index/mail-index-private.h https://github.com/dovecot/core/blob/81b5b188c478ec36bea8bda... Basically, building a mail index for UID<->MSN translation that can serialize to disk, which would explain how it doesn't necessarily need absurd amounts of RAM and can select fast, probably at heavy cost when EXPUNGeing old messages. I'm sure there were worse implementations that did just maintain it all in RAM way back in the day, and still some that do (like the one I ran into).

ball_of_lint 7y ago

This sounds like exactly the situation where you would want to use a persistent tree. For a log(n) overhead, you can keep the ordering of all the messages in your mailbox at any given point in time. Then you don't need to inform clients unless a new message is added that they might want to reference. Otherwise you just keep track of the state that client is operating on and use the old state to let you apply their actions to the new state.

Felz 7y ago
Yea, I think you basically do need one of these: https://en.wikipedia.org/wiki/Order_statistic_tree https://en.wikipedia.org/wiki/Order_statistic_tree They're somewhat obscure though.