[Dovecot] Replication plans

[Timo Sirainen]

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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : http://dovecot.org/pipermail/dovecot/attachments/20070517/1af90f1a/attachment.pgp