Replication and synchronization

Replication and synchronization happen to be something about which I
know a teensy weensy little bit. :-) So I'll toss in my 2 cents'
worth.

The easiest thing to implement is the current proposal: one writable
master, and many read-only slaves. Anything that allows writes at
multiple locations is fraught with difficulty. There are a number of
well-known solutions, but all of them have drawbacks, and most require
some complexity.

Multiple-write replication schemes fall into two broad categories:
conservative and optimistic. Briefly, conservative approaches seek to
ensure that there will never be "conflicting" writes (what Nicolas
Fischer called "collisions"). The master/slave method mentioned above
falls into the conservative category. Another popular and relatively
simple conservative approach is the "voting" scheme. Before writing
any record, the writer first contacts a majority of other replicas,
and sets locks on the record. Then it does the write and releases the
locks, propagating the new record as part of the lock-release
message. Clearly, only one writer can lock any record at any time.
Furthermore, if a writer has an out-of-date copy of the record, he can
find out as part of setting the lock.

The disadvantage of this and most other conservative approaches is
that they require a majority of the replicas to be online at any given
time. The voting scheme can be modified slightly by assigning weights
to replicas; a more reliable replica will get a heavier weight, and to
lock you only need to get a majority of the weights.

The one-writable-master scheme can also be modified so that instead of
doing writes directly at the master, a slave first locks the record at
the master, then updates it locally and sends the updated version to
the master. If it chooses, the master can then notify all other
slaves of the new value. This approach is handy if it's important
that all slaves be kept up to date. Many multiprocessor computers use
a form of this approach to keep their caches consistent between
processors.

There are also overhead issues with locking schemes. The number of
messages exchanged can be excessive in some circumstances.

In optimistic approaches, by contrast, every replica accepts writes
without considering the possibility of conflicts. At some later date,
replicas "gossip" with each other to tell each other about updates.
As long as there's no conflict, everything is fine. Otherwise, some
sort of conflict-resolution scheme must be invoked. An early paper
on the idea was titled "Apologizing vs. Asking Permission", which is a
nice summary of the difference between the two methods.

Optimistic approaches can work very well when conflicts are rare. I
suspect that they would be rare in MusicBrainz once it was past the
initial stage of populating the database. However, implementing an
optimistic approach is probably more difficult than doing a
pessimistic one, especially when you consider the work of resolving
conflicts.

I've only touched the surface of a complex subject here, but I hope my
comments will help to serve as a starting point for further
discussion.
--
Geoff Kuenning geoff at cs.hmc.edu http://www.cs.hmc.edu/~geoff/

Software, like bridges, should be elegant and visually pleasing as
well as functional. Ugly constructs, designs, and languages should be
avoided like the plague.