[Dovecot] Replication plans

[Troy Benjegerdes]

My first reaction is that I've already got replication by running
dovecot on AFS ;)

But that's currently not *really* replicated. The real question I guess
is why not use a cluster/distributed/san filesystem like AFS, GFS,
Lustre, GPFS to handle the actual data, and specify that replication
only works for maildir or other single file per message mailbox formats.

This puts about half the replication problem on the filesystem, and I
would hope keeps the dovecot code a lot simpler. The hard part for
dovecot is understanding the locking semantics of various filesystems,
and doing locking in a way that doesn't totally trash performance.

I also tend to have imap clients open on multiple machines, so the
assumption that a user's mailbox will only be accessed from 1 IP is
probably a bad one.

I'd suggest that multi-master replication be implemented on a
per-mailbox basis, so that for any mailbox, the first dovecot instance
that gets a connection for that mailbox checks with a 'dovelock' process
that can either backend to a shared filesystem, or implement it's own
tcp-based lock manager. It would then get a master lock on that mailbox.
If a second dovecot gets a connection to a mailbox with a master lock,
it would act as a proxy and redirect all writes to the master. In the
case of a shared filesystem, all reads can still come from the straight
from the local filesystem. In the case of AFS, this might hit the
directory lookups kind of hard, but I think would still be a big win
because of local cacheing of all the maildir files, which for the most
part are read-only.

In the event that a master crashes or stops responding, the dovelock
process would need a mechanism to revoke a master lock.. this might
require some filesystem-specific glue to make sure that once a lock is
revoked the dovecot process that had it's lock revoked can't write to
the filesystem anymore. I can think of at least one way to do this with
AFS by having the AFS server invalidate authentication tokens for the
process/server that the lock was revoked from.

Once the lock is revoked, the remaining process can grab it and go on
happily with life. Once the dead/crashed process comes back, it just has
to have it's filesystem go out and update to the latest files.

I like the idea of dovecot having a built-in proxy/redirect ability so a
cluster can be done with plain old round-robin DNS. I also think that in
most cases, if there's a dead server in the round-robin DNS pool, most
clients will retry automatically, or the user will get an error, click
okay, and try again. Having designated proxy or redirectors in the
middle just makes things complicated and hard to debug.

On Thu, May 17, 2007 at 04:45:21PM +0300, Timo Sirainen wrote:
> Several companies have been interested in getting replication support
> for Dovecot. It looks like I could begin implementing it in a few months
> after some other changes. So here's how I'm planning on doing it:
> 
> What needs to be replicated:
> 
>  - Saving new mails (IMAP, deliver)
>  - Copying existing mails
>  - Expunges
>  - Flag and keyword changes
>  - Mailbox creations, deletions and renames
>  - Subscription list
>  - IMAP extension changes, such as ACLs
> 
> I'll first talk about only master/slave configuration. Later then
> master/multi-slave and multi-master.
> 
> Comments?
> 
> Basic design
> ------------
> 
> Since the whole point of master-slave replication would be to get a
> reliable service, I'll want to make the replication as reliable as
> possible. It would be easier to implement much simpler master-slave
> replication, but in error conditions that would almost guarantee that
> some messages get lost. I want to avoid that.
> 
> Both slave and master would be running a dovecot-replication process.
> They would talk to each others via TCP connection. Master would be
> feeding changes (transactions) to slave, and slave would keep replying
> how far it's committed the changes. So there would be an increasing
> sequence number sent with each transaction.
> 
> Master keeps all the changes in memory until slave has replied that it
> has committed the changes. If the memory buffer gets too large (1MB?)
> because the slave is handling the input too slowly or because it's
> completely dead, the master starts writing the buffer to a file. Once
> the slave is again responding the changes are read from the file and
> finally the file gets deleted.
> 
> If the file gets too large (10MB?) it's deleted and slave will require a
> resync. Master always keeps track of "user/mailbox -> last transaction
> sequence" in memory. When the slave comes back up and tells the master
> its last committed sequence, this allows the master to resync only those
> mailboxes that had changed. If this mapping doesn't exist (master was
> restarted), all the users' mailboxes need to be resynced.
> 
> The resyncing will also have to deal with new mailboxes, ACL changes and
> such. I'm not completely sure yet how the resyncing will work. Probably
> the only important thing here is that it would be good if it would
> resolve any message UID conflicts (even though they shouldn't happen,
> see below) by comparing either the messages' MD5 contents, or with
> maildir it would be enough to just compare the maildir filename.
> 
> It's possible that the slave doesn't die completely but only some
> transactions fail. This shouldn't normally happen, so the easiest way to
> handle it would be to try a full resync, and if that still fails stop
> the whole slave. Another way would be to just mark that one user or
> mailbox as dirty and try to resync it once in a while.
> 
> imap, pop3 and deliver would connect to dovecot-replication either using
> UNIX sockets or POSIX message queue. Queue could be faster, but sockets
> would allow better security checks. Or I suppose it would be possible to
> send some kind of a small authentication token in each message with
> queues. The communication protocol would be binary and the existing
> dovecot.index.log format would be used as much as possible (making it
> simple for slave to append changes to mailboxes' dovecot.index.log).
> 
> dovecot-replication process would need read/write access to all users'
> mailboxes. So either it would run as root or it would need to have at
> least group-permission rights to all mailboxes. A bit more complex
> solution would be to use multiple processes each running with their own
> UIDs, but I think I won't implement this yet.
> 
> The replication would require support for shared mailboxes. That way the
> mailboxes could be accessed using the configured shared namespaces, for
> example "shared/<username>/INBOX". (LMTP server could be implemented in
> a similar way BTW)
> 
> Configuration
> -------------
> 
> I'm not yet sure how this should work. The simplest possibility would be
> just to configure a single slave and everything would be replicated
> there.
> 
> But it should be possible to split users into multiple slaves (still one
> slave/user). The most configurable way to do this would be to have
> userdb return the slave host. Hmm. Actually that could work pretty well
> if the userdb returned slave's name and each slave would have a separate
> socket/queue where dovecot-replication listens in. I'm not sure if they
> could all still be handled by a single dovecot-replication process or if
> there should be a separate one for each of them. The configuration would
> then be something like:
> 
> # slave for usernames beginning with letters A..K
> replication users_a_k {
>   host = slave1.example.com
>   # other options?
> }
> # L..Z and others
> replication users_l_z_rest {
>   host = slave2.example.com
> }
> 
> Saving
> ------
> 
> This is the most important thing to get right, and also the most complex
> one. Besides replicating mails that are being saved via Dovecot, I think
> also externally saved mails should be replicated when they're first
> seen. This is somewhat related to doing an initial sync to a slave.
> 
> The biggest problem with saving is how to robustly handle master
> crashes. If you're just pushing changes from master to slave and the
> master dies, it's entirely possible that some of the new messages that
> were already saved in master didn't get through to slave. So when you
> switch to using slave, those messages are gone. The biggest problem with
> this is that when saving new mails, they'll be assigned UIDs that were
> already used by the original master. If a locally caching client had
> already seen the UID from the original master, it'll think the message
> is the original one instead of the new one. So the newly added message
> pretty much gets lost, and if the user could expunge the message
> (thinking it's the original one) without ever even seeing it.
> 
> This UID conflict could be avoided by making the master tell slave
> whenever it's saving new mails. The latency between master-slave
> communication could be avoided with a bit of a trick:
> 
>   - When beginning to save/copy a mail, tell slave to increase UID
> counter by one. Slave replies with the new highest-seen-UID counter.
>   - UID allocation is done after all the mails are saved/copied within a
> transaction. At this stage wait until slave has replied that it has
> reserved UIDs at least as high as we're currently allocating (other
> processes could have caused it to get even higher).
>   - If save/copy is aborted, tell the slave to decrease the UID counter
> by the number of aborted messages.
>   - UID counter desync shouldn't happen, but if it does handle that also
> somehow.
> 
> Then the UID allocation latency depends on how long it takes to write
> the message, and where the message comes from. With IMAP APPEND there's
> probably no wait required, unless the APPEND command and the whole
> message arrives in one IP packet. With deliver and copying it might have
> to wait a while.
> 
> So the UID allocation should work with minimal possible latency. It
> could use a separate TCP connection to slave and maybe a separate high
> priority process in the slave that would handle only UID allocations.
> 
> The above will make sure that conflicting UIDs aren't used, but it
> doesn't make sure that messages themselves aren't lost. If the master's
> hard disk failed completely and it can't be resynced anymore, the
> messages saved there are lost. This could be avoided by making the
> saving wait until the message is saved to slave:
> 
>   - save mail to disk, and at the same time also send it to slave
>   - allocate UID(s) and tell to slave what they were, wait for "mail
> saved" reply from slave before committing the messages to mailbox
> permanently
> 
> This would however add more latency than the simpler UID allocation
> counter. I don't know if it should be optional which way is used.
> Perhaps I'll implement the full save-sync first and if it seems too slow
> then I'll implement optionally the UID allocation counter.
> 
> Save messages from imap/deliver would contain at least:
> 
> 1. user name (unless using UNIX sockets, then it's already known)
> 2. mailbox name
> 3. UIDVALIDITY
> 4a) UID
> 4b) global UID, filename, offset and size of the message
> 
> 4a) would be used with the UID allocation counter behavior. The message
> would be sent after the message was saved and UIDs were allocated.
> 
> 4b) would be used with the wait-slave-to-save behavior. The message
> would be sent immediately whenever new data was received for the
> message, so possibly multiple times for each message. The last block
> would then contain size=0. After saving all the mails in a transaction,
> there would be a separate "allocate UIDs x..y for global UIDs a, b, c,
> d, etc." message which the slave then replies and master forwards the
> reply to imap/deliver.
> 
> If the slave is down, or if a timeout (a few seconds?) occurs while
> waiting for the reply from slave, imap/deliver could just go on saving
> the message. If this is done it's possible that if the master also dies
> soon, there will be UID conflicts. But since this should be a rare error
> condition, it's unlikely that the master will die soon after a
> misbehaving slave.
> 
> Copying
> -------
> 
> Copying has similar UID conflict problems than saving. The main
> difference is that there's no need to transfer message contents, which
> makes it faster to handle copies reliably.
> 
> Copying could be handled with the UID allocation counter way described
> above. Since the message already exists in the server, there's no way
> that the message gets lost. So it would be possible to allow master and
> slave to go into desync, because the user would still find the message
> from the original mailbox.
> 
> Move operation is done with "copy + mark \deleted + expunge"
> combination. This could be problematic if the master had managed to do
> all that before slave saw the COPY at all. Since the message isn't yet
> copied to the new mailbox in slave, clients wouldn't see it there, but
> locally caching clients might not see the message in the original
> mailbox either because they had already received EXPUNGE notification
> for it. So this should be avoided in some way.
> 
> Perhaps it would be better to just treat copies the same way as saves:
> Require a notification from slave before replying to client with OK
> message. Alternatively the wait could be done at EXPUNGE command, as
> described below.
> 
> Expunges
> --------
> 
> Losing expunge transactions wouldn't be too bad, because the worst that
> can happen is that the user needs to expunge the message again. Except
> that having an expunged message suddenly appear again in the middle of
> the mailbox violates IMAP protocol. I don't know if/how that will break
> clients.
> 
> Solution here would again be that before EXPUNGE notifications are sent
> to client we'll wait for reply from slave that it had also processed the
> expunge.
> 
> Flag and keyword changes
> ------------------------
> 
> Most likely doesn't matter if some of them are lost. If someone really
> cares about them, it would be possible to again do the slave-waiting for
> either all the changes or just when some specific flags/keywords change.
> 
> Other changes
> -------------
> 
> Mailbox creations, deletions, renames and subscription changes could all
> be handled in a similiar way to flag/keyword changes.
> 
> Handling changes implemented by IMAP extensions such as ACL is another
> thing. It's probably not worth the trouble to implement a special
> replication handler for each plugin. These changes most likely will
> happen somewhat rarely though, so they could be implemented by sending
> the whole IMAP command to slave and have it execute the command using a
> regular imap process. The commands could be marked with some
> "replication" flag so Dovecot knows that they need to be sent to slave.
> 
> Although instead of executing a new imap process for each user (probably
> each command), it could be possible to use one imap process and just
> change the mailbox name in the command. So instead of eg. "setacl
> mailbox (whatever)" the IMAP process would execute "setacl
> shared/username/mailbox (whatever)". That would require telling Dovecot
> what parameter contains the mailbox name. Should be pretty easy to
> implement, unless some IMAP extensions want multiple mailbox names or
> the position isn't static. I can't think of any such extensions right
> now though.
> 
> Master/multi-slave
> ------------------
> 
> Once the master/slave is working, support for multiple slaves could be
> added. The main thing to be done here is to have the slaves select which
> one of them is the new master, and then they'll have to sync the
> mailboxes with each others, because each of them might have seen some
> messages that others hadn't. This is assuming that save/etc. operations
> that are waiting for a reply from slave would wait for only one reply
> from the first slave that happens to respond. The number of slave
> replies to wait for could be also configurable, in case you're worried
> of a simultaneous master+slave crash.
> 
> Multi-master
> ------------
> 
> After master/multi-slave is working, we're nearly ready for a full
> multi-master operation. The master farm will need global locking.
> Perhaps there is a usable existing implementation which could be used.
> In any case there needs to be a way to keeps track of what master owns
> what locks.
> 
> The easiest way to implement multi-master is to assume that a single
> user isn't normally accessed from different servers at the same time.
> This wouldn't be a requirement, but it would make the performance
> better. For most users you could handle this by making sure that load
> balancer transfers all connections from the same IP to the same server.
> Or you could use a Dovecot proxy that transfers the connections.
> 
> So, once the user is accessed only from one server, the operation
> becomes pretty much like master/multi-slave. You'll just need to be able
> to dynamically change the current master server for the user. This can
> be done by grabbing a global per-user lock before modifying the mailbox.
> The lock wouldn't have to be released immediately though. If no other
> server needs the lock, there's no point in locking/unlocking constantly.
> Instead the lock server could request the current lock owner to release
> the lock whenever another server wants it.



-- 
--------------------------------------------------------------------------
Troy Benjegerdes                'da hozer'                hozer at hozed.org  

Somone asked me why I work on this free (http://www.fsf.org/philosophy/)
software stuff and not get a real job. Charles Shultz had the best answer:

"Why do musicians compose symphonies and poets write poems? They do it
because life wouldn't have any meaning for them if they didn't. That's why
I draw cartoons. It's my life." -- Charles Shultz