Database Reference
In-Depth Information
Unfortunately, other than “don't do that” there is no easy solution to that
particular problem.
Consensus in an Unreliable World
In addition to unreliable network connections and poorly synchronized
clocks, there is the possibility that the processes themselves might contain
faults that cause them to generate incorrect results at times. In some
academic work on the subject, these processes may even be actively
malicious, though many real-world systems do not consider this scenario.
In the face of all the things that can go wrong, the distributed state
maintainedacrossmachinesshouldbeconsistent.Themostfamous(though
not the first) algorithm for doing this, known as Paxos, was first published
in the late 1980s.
In the Paxos algorithm, a process that wants to mutate the shared state
first submits a proposal to the cluster. This proposal is identified by a
monotonically increasing integer, which must be larger than any identifier
previously used by the Proposer.
The proposal is then transmitted to a quorum of other processes, called the
Acceptors. If a given Acceptor receives a message identifier smaller than
the largest it has seen from the proposer, it simply discards the proposal as
being stale (alternatively, it can explicitly deny the request to the Proposer).
If the message seen by the Acceptor is the largest it has ever seen from
the Proposer, it updates the largest identifier seen for the Proposer. At the
same time, it returns the previous identifier and the associated value it
had received from that Proposer. This is called the promise phase because
the Acceptor has now promised not to deny all requests with an identifier
smaller than the new value.
After the Proposer has received enough positive responses from the promise
phase, it may consider its request to mutate the state to be accepted. The
Proposer then sends the actual change to the Acceptors, who then propagate
the information to other nodes in the cluster, which are called Learners.
This process also identifies the Proposer whose proposal has been accepted
as the Leader of the cluster. In practice, this is often used to implement
Leader Election for a cluster of servers (for example, a clustered database
application).
