Old --- Currently dsync is designed so that there's one "brain" and two workers. The workers can be local or remote, but they are accessed via the same API. The brain gets some state from both workers, figures out what to do to get them to sync and then tells the workers to do that. This isn't too bad of a design, but it could be better. New overview ------------ The redesign's idea is to get rid of the brain. The sync is split into two parts, run by both sides: 1. Gather our current replication state and tell the other side what it is. Both sides need to know its own state and the remote's state to be able to figure out the replication state. Both sides should come to the same conclusion of the state. 2. Based on remote's known state, tell it what had changed since. 3. Apply the changes that remote sent to us. Remember this replication state and give it an ID (the state itself could be the ID, but it might be annoyingly large). The first part can be highly optimized after initial sync using the saved replication state IDs. If nothing has changed, ideally dsync only needs to read the mailbox list index (mailbox_list_index=yes), which is fast. Replication state ----------------- Some of the important things about state: - IMAP requires messages to have an _ascending_ 32bit unique ID number. A new message is given UID=UIDNEXT, and UIDNEXT is increased by one. - IMAP has 64bit modification sequences (modseq) that increase after anything changes, such as message is saved/expunged or flags are changed. Each mailbox has a HIGHESTMODSEQ value, which is stored in mailbox list index. - Dovecot assigns mailboxes 128bit GUID - Dovecot assigns messages a GUID and if it's not a 128bit GUID (e.g. maildir filename is a GUID) then in some situations it gets 128bit SHA1 of the GUID. - Dovecot keeps track of which messages are expunged, how message flags changed (e.g. UID 123 added \Seen flag and remove \Flagged flag, not simply that the current result is \Seen) - Dovecot keeps track of which mailboxes were deleted, renamed, subscribed, unsubscribed and the timestamp when it happened. - \Noselect mailboxes are more like "directories". They can't be opened until they're actually created, and they don't have a GUID, but they are visible to clients. Their creation, creation and deletes are logged using 128bit SHA1 of their name (this probably changes, because currently dsync uses a separate dovecot.mailbox.log for this, but in future mailbox list indexes should have all of this information without forcing 128bit IDs). So overall what needs to be synced: - New messages, expunges, flag changes. Preferably modseqs would also be equal after sync, since QRESYNC enabled clients rely on them. - Resolving IMAP UID conflicts. If client has seen a message with UID X, then any messages with UID <= X must not change and new messages must not be added with such UIDs. It must also be assumed that the client may log into any of the dsynced servers. So when dsync notices that the servers have a different message (GUID) in UID X, then all of the messages with UID >= X must be reassigned to have UID that is higher than any assigned UID in either server (i.e. max(server1.next_uid, server2.next_uid)). - Expunges from the middle of the mailbox can be detected easily and expunged on both sides. Expunges from the end of mailbox are more difficult, because you need to know if the other side had added a new message or if this side had expunged a message. You need to look at the mailbox log to find out the GUID of the expunged message to determine this. - Flag changes. It should be done by applying changes, rather than replacing all flags. So if one side added \Seen and other side added \Replied, the result should be that both of the flags exist. Handle flag removals similarly. This requires looking into mailbox log to find the changes. I'm not entirely sure if this is worth it, current dsync doens't do this. In any case it needs fallback code to handle when the flag changes no longer exist in the log. - Mailbox creations, renames, deletions, subscription changes are handled in somewhat similar way. - In future there are more things to sync (mail/mailbox metadata, ACLs, shared vs. private flags), but these same basics could be applied to them as well. Idea for new dsync ------------------ I'm only focusing on syncing message data. Syncing mailbox creations, renames, etc. of course need to be handled in some way, but that will be relatively easy and doesn't need to work as well anyway, since it changes so rarely. The replication state can be saved by remembering for each mailbox GUID: - highest common highestmodseq - highest common uidnext On the next sync you'll just need to find all changes that happened after the last common highestmodseq, because you know that everything else was already synced the last time. The highestmodseq is normally enough, but since dovecot.index.log doesn't grow infinitely, dsync needs to also be able to fallback to a slightly less optimal sync if it can't know exactly what changed since the highestmodseq. The highest common uidnext is required in this case to determine which messages are new. It may also be help a bit even if all changes are known. So the idea is that after the initial state finding dsync should know exactly what changes to send to remote. The remote dsync should know exactly what to send to us. This allows two new features that current dsync doesn't support: - dsyncing data via USB sticks! :) For example you want to dsync mails to your laptop and then go sailing around the world. You dsync the servers before you leave home. Then you do your changes while sailing and reach some harbour. You plug the USB stick into your laptop, which writes any changes it did there. You find an internet cafe, plug the USB stick there and upload the changes to remote dsync, which also gives you back its own changes that you move to your latop via USB stick. And this continues. - dsync changes = optimally stored incremental backups. Add some tools to easily recover from a full backup + dsync incremental backups. So I'm thinking the new dsync in a little bit the same way as a functional language: If you have - import(mailbox, change_data) -> (new_mailbox, known_replication_state) - export(mailbox, known_replication_state) -> change_data it should be irrelevant in which order the import/export is done. The resulting mailbox in local and remote servers should be identical. Sometimes it can be a little difficult to figure out what to do if both local and remote had changed something after the last sync (mainly for flag changes and for UID order). In such case: - order the change operations by timestamps (e.g. message saved-timestamp) - if timestamps aren't available or they are identical, order by modseq - if modseqs are identical, order by the session ID string, which can never be identical if there are any changes Current dsync also isn't very happy when changes happen during the dsync itself. It can at least duplicate some mails. The new dsync should be able to handle this so that while after the first dsync the mailboxes won't be identical, they will be after the second dsync. So the mailbox states won't become confused just because other changes happened during it. And if dsync can handle any random mailbox changes happening during its run, it should also be able to handle many dsync all trying to dsync the same mailbox at the same time, right? Current dsync pretty much requires locking, but locking is bad. Most of the dsync run is done without locks. Current Dovecot API doesn't let you lock the mailbox in any way. I'm not sure if this is necessary to change for the dsync to handle simultaneous (other dsync) changes without duplicating or breaking anything, or if it's enough to change the API to make some things optional, such as "save message with UID=123 GUID=xyz, but don't do that if exactly that message already exists". There are already a few similar functions: - mailbox_save_set_uid() assigns UID for the newly saved message, but if UIDNEXT is already higher then it will be assigned some other higher UID. - mail_update_modseq() assigns modseq for an existing message, but only if it's higher than the current modseq. - mail_update_flags() can add/remove specific flags without changing others