> 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

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.

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

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.

> 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

[2] https://imapwiki.org/ImapTest/ServerStatus

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

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

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.

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

The cost of deletions is heavy, and I wouldn't have done it this way, but note that where it really matters is if you have to do this repeatedly in a loop. But you don't have to do it repeatedly -- you can just delete a ton of messages at once, at the same cost as deleting a single once. As long as user perceptions go, the network latency is probably going to dominate shifting down even a million integers (< 2 ms on my machine), which I suspect most people don't even have.

> 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

That does explain why indexes can get corrupted and need to be cleared out, and why load balancing IMAP can get tricky.

Dovecot puts those index files in the maildir too, so one can read those directly if wanted.

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.

Yea, I think you basically do need one of these: https://en.wikipedia.org/wiki/Order_statistic_tree

They're somewhat obscure though.