[revision history: 1. Inserted a new step #2 2. Updated descriptions, nothing major. 3. Step #3's previous example was wrong. After seeing the new result, it was easy to solve. Assuming it works :) 4. Step #3 was more difficult than I thought. Implemented it now in code, but this document is out of date. Step #1's algorithm got also simplified with this. ] Problem: How to implement 2-way synchronization of IMAP mailboxes? We'll start with the initial simplified problem of how to merge messages from two mailboxes. The rest is relatively easy. Background: Messages have ascending IMAP UID numbers, and GUID strings. The IMAP UIDs identify messages to IMAP clients (which may cache them based on it), and GUIDs identify what the messages truly are (but IMAP clients don't know about GUIDs). The same GUID may exist multiple times in a mailbox, because messages can be duplicated by copying. The copies should be preserved. When assigning UIDs to messages, they must not be lower than the mailbox's "next-UID" value (which means that any kind of "increase UID by stepping X numbers" scheme doesn't work alone, and in any case isn't preferred as it gets difficult to maintain in large installations). Multiple messages can be saved transactionally, and next-UID gets updated at commit time. An IMAP client may jump between two mailboxes and its internal UID=>mail mapping must match the mailbox's real UID=>mail(=GUID) mapping. The only allowed changes are to delete UIDs and to add new mails with UID >= last next-UID seen by client. ------------------------ Step #1: Now, given two mailboxes with (UID, GUID) pairs and next-UID for each, describe an algorithm that merges the mailboxes, preserving as many UIDs as possible to avoid an IMAP client having to redownload mails. One solution: Example with mailboxes M1 and M2 having UID+GUID pairs e.g. 1A=(UID 1, GUID A): mailbox M1 M2 M1&M2 1A 2B 2B (assignment order: 6A, 2B, 7B, 4C, 5D) 2B 3B => 4C 3C 4C 5D 5D 6A 7B next-UID: 4 6 8 For each mail pair (starting with 1A&2B above) do: 1. If both mails have the same GUID: 1a) If M1.UID = M2.UID, do nothing. 2a) If M1.UID >= M2.next-UID, use M1.UID for M2 as well. 2b) If M2.UID >= M1.next-UID, use M2.UID for M1 as well. 2c) Otherwise, assign UID >= MAX(M1.next-UID, M2.next-UID) to both. Then skip both mails to the next pair. 2. If M1.UID >= M2.next-UID: Copy this message to M2 using M1.UID. Skip to next mail in M1 (but use the current mail in M2 for the next pair). 3. Like 2, but M1/M2 reversed. 4. Select the "lower" message of M1 and M2. This could be primarily based on message's saved-timestamp, but here it suffices to simply do it based on GUID. Assign a new UID >= MAX(M1.next-UID, M2.next-UID) to the lower message and skip it. Finally if there are any pairless messages left in one side: a) For all messages with UID >= other side's next-UID, use their UIDs for the other side as well. b) For the other messages assign new UIDs >= MAX(M1.next-UID, M2.next-UID) ------------------------ Step #2: Mailbox may be changed during dsync, so there may be unexpected mails added during the dsync. This should not break dsync. A little more background to how dsync is going to work: When merging two mailboxes, it gets a "last-common-UID" value. Any messages with UID lower than that don't need to be synced, because they're known to be identical. How this value is found is a solved problem. When dsync asks Dovecot to assign UID X to a message, it only does it if the UID >= next-UID during the transaction commit. For those messages that aren't (or simply don't have any specific UID set), they're assigned a new UID which higher than all of the requested UIDs. So for example if dsync requests messages with GUIDs A and B to be given UIDs 1 and 2, but another session already had saved a message C with UID 1, the result will be a mailbox with (1C, 2B, 3A). So these conflicts can be solved after dsync has committed mails: Find if there are unexpectedly inserted messages. If not, we'de done. If yes, save last-common-UID=-1 and give all the unexpected messages new UIDs. This way they're going to be synced on the next dsync. Example where M2 unexpectedly gets a new mail 6E: mailbox M1 M2 M1 M2 1A 2B 2B 2B (M2 assignment order: 6A, 2B, 7B, 4C, 5D 2B 3B => 4C 4C but 6E already exists, so 6A -> 8A and 3C 4C 5D 5D 6E -> 9E, last-common-uid=5) 5D 6A (6E) 7B 7B 8A 9E next-UID: 4 6 8 10 The second dsync run: mailbox M1 M2 M1&M2 2B 2B 2B (we can skip the known UIDs: 2B, 4C, 5D) 4C 4C => 4C 5D 5D 5D -- -- -- 6A 7B 7B (assignment order: 10A, 7B, 8A, 9E) 7B 8A 8A 9E 9E 10A next-UID: 8 10 11 ------------------------ Step #3: The above solution appears to work (although I didn't do a lot of testing with it), but it requires that both sides figure out their changes and sends them before applying the other side's changes. Otherwise it fails: Lets assume that M1 is as in step#1 example, sends it to M2 which results M2 having the step#1's M1&M2 mailbox. Now M2 sends its changes to M1: mailbox M1 M2 M1 1A 2B 2B (assignment order: 8A, 2B, 4C, 5D, 6A, 7B) 2B 4C => 4C 3C 5D 5D 6A 6A 7B 7B 8A next-UID: 4 8 9 So now M1 has one too many messages. But this should be easy to solve: When reassigning a new UID to an existing message, add it to the GUID's list of reassigned messages. If wee see the same GUID in the other side and its UID is >= our next-uid, use that UID for the message and delete the first half-saved message from the GUID's reassigned messages list. FIXME: what if we see UID < our next-uid? Can that happen, how? ------------------------ Step #4: Allow multiple dsyncs to run in parallel without locking the entire mailboxes for the duration of the whole dsync. And of course the result should be the same as when only one dsync was run. Things that could be possible to add to make it possible: - During transaction commit, soft fail if any unexpected changes occurred during dsync. The new mailbox state could be observed and messages in transaction be reassigned new UIDs or deleted. I'd prefer not to add this feature. - Add conditional saving, for example "if message with same GUID exists with UID >= x then just don't save this message" during commit. - possibly something else that doesn't involve locking Also here it might be necessary to think about what happens when messages are also getting deleted at the same time.