4 ms·

Individual unique IDs and /changes lists all the IDs that might have changed. One good thing about IMAP is that there's a fair bit of data which is immutable,

Individual unique IDs and /changes lists all the IDs that might have changed. One good thing about IMAP is that there's a fair bit of data which is immutable, and JMAP retains that - emails with the same ID must have the same content, so there's a limited amount of metadata that you need to resync. I wrote something about how you fix UID clashes in a split brain while staying within the IMAP data model many years ago... https://lists.andrew.cmu.edu/pipermail/cyrus-devel/2010-July/001500.html https://lists.andrew.cmu.edu/pipermail/cyrus-devel/2010-July...

jorangreef 7y ago
> /changes lists all the IDs that might have changed. How does it do this in a distributed setting? When clients might be connecting to multiple servers with different states?
- brongondwana 7y ago
  Well, it depends on how you architect your system - you can embed whatever you like in your state. I'd probably do something cheap and nasty like embed a modseq counter for each of the different servers into the state string, and if any of them went backwards I'd reject the /changes with a cannotCalculateChanges error. I mean, you can do other things - but at the point where you're switching between multiple masters in a split brain from your client, all bets are off - so you're going to need to fall back resyncing any mutable data.
  - jorangreef 7y ago
    > but at the point where you're switching between multiple masters in a split brain from your client, all bets are off CRDTs handle split brain fine. They eventually converge. You just don't want your clients flapping in the meantime by resyncing tons of data. That's where a distributed sync algorithm would help keep things working in the interim.
jorangreef 7y ago
> I wrote something about how you fix UID clashes in a split brain while staying within the IMAP data model many years ago... Thanks for this. It was a good read and promoting UIDs instead of bumping UIDVALIDITY is a great idea. Surely, it would be even better if IMAP had support for distributed Merkle Tree synchronization, so that clients can sync with different server replicas without the server replicas having to coordinate or promote UIDs at all in the first place? I don't know of any algorithm other than a Merkle Tree that will do this correctly and simply and efficiently in a distributed setting?
- brongondwana 7y ago
  That would be a pretty massive change to the entire data model of IMAP. It's never going to happen[tm]. IMAP4rev2 is much more conservative than that. https://datatracker.ietf.org/doc/draft-ietf-extra-imap4rev2/ https://datatracker.ietf.org/doc/draft-ietf-extra-imap4rev2/ Merkle tree would is great for full history - I built something like that with digital signing for tracking clinical data over 15 years ago that would have been fine for email as well - but it's way over-expensive for email. Which leads back to the key design principle I try to use when working on protocols, which is something like "make the weird edge cases sand and possible, but don't optimise them!" You don't want to build the Merkle tree complexity into a client and have all the servers be completely independent, because it makes the protocol a pain to use for the simple case. (What we use for IMAP replication in Cyrus is much dumber than all this - it uses a per-message CRC and XORs them together for the whole mailbox to create the sync_crc value. If those don't match, it does a resync. Fixes up split brain just fine while being cheap and dumb for the common case.
  - jorangreef 7y ago
    > Merkle tree would is great for full history - [...] but it's way over-expensive for email. Does JMAP then not support syncing full history efficiently as a key design priority? > That would be a pretty massive change to the entire data model of IMAP. It's never going to happen[tm]. Sure, and that's why I had hoped JMAP would, especially in a distributed master setting, since this was something IMAP overlooked. I guess it's because JMAP still needs to be backwards-compatible with the strict consistency master-slave restriction of IMAP? > What we use for IMAP replication in Cyrus is much dumber than all this - it uses a per-message CRC and XORs them together for the whole mailbox to create the sync_crc value. If those don't match, it does a resync. Fixes up split brain just fine while being cheap and dumb for the common case. You're implementing the first layer of an incremental Merkle tree right there. How many bits are those CRCs just out of interest?

jorangreef 7y ago

> /changes lists all the IDs that might have changed. How does it do this in a distributed setting? When clients might be connecting to multiple servers with different states?

brongondwana 7y ago
Well, it depends on how you architect your system - you can embed whatever you like in your state. I'd probably do something cheap and nasty like embed a modseq counter for each of the different servers into the state string, and if any of them went backwards I'd reject the /changes with a cannotCalculateChanges error. I mean, you can do other things - but at the point where you're switching between multiple masters in a split brain from your client, all bets are off - so you're going to need to fall back resyncing any mutable data.
- jorangreef 7y ago
  > but at the point where you're switching between multiple masters in a split brain from your client, all bets are off CRDTs handle split brain fine. They eventually converge. You just don't want your clients flapping in the meantime by resyncing tons of data. That's where a distributed sync algorithm would help keep things working in the interim.

jorangreef 7y ago

> I wrote something about how you fix UID clashes in a split brain while staying within the IMAP data model many years ago... Thanks for this. It was a good read and promoting UIDs instead of bumping UIDVALIDITY is a great idea. Surely, it would be even better if IMAP had support for distributed Merkle Tree synchronization, so that clients can sync with different server replicas without the server replicas having to coordinate or promote UIDs at all in the first place? I don't know of any algorithm other than a Merkle Tree that will do this correctly and simply and efficiently in a distributed setting?

brongondwana 7y ago
That would be a pretty massive change to the entire data model of IMAP. It's never going to happen[tm]. IMAP4rev2 is much more conservative than that. https://datatracker.ietf.org/doc/draft-ietf-extra-imap4rev2/ https://datatracker.ietf.org/doc/draft-ietf-extra-imap4rev2/ Merkle tree would is great for full history - I built something like that with digital signing for tracking clinical data over 15 years ago that would have been fine for email as well - but it's way over-expensive for email. Which leads back to the key design principle I try to use when working on protocols, which is something like "make the weird edge cases sand and possible, but don't optimise them!" You don't want to build the Merkle tree complexity into a client and have all the servers be completely independent, because it makes the protocol a pain to use for the simple case. (What we use for IMAP replication in Cyrus is much dumber than all this - it uses a per-message CRC and XORs them together for the whole mailbox to create the sync_crc value. If those don't match, it does a resync. Fixes up split brain just fine while being cheap and dumb for the common case.
- jorangreef 7y ago
  > Merkle tree would is great for full history - [...] but it's way over-expensive for email. Does JMAP then not support syncing full history efficiently as a key design priority? > That would be a pretty massive change to the entire data model of IMAP. It's never going to happen[tm]. Sure, and that's why I had hoped JMAP would, especially in a distributed master setting, since this was something IMAP overlooked. I guess it's because JMAP still needs to be backwards-compatible with the strict consistency master-slave restriction of IMAP? > What we use for IMAP replication in Cyrus is much dumber than all this - it uses a per-message CRC and XORs them together for the whole mailbox to create the sync_crc value. If those don't match, it does a resync. Fixes up split brain just fine while being cheap and dumb for the common case. You're implementing the first layer of an incremental Merkle tree right there. How many bits are those CRCs just out of interest?