Real world example of Paxos

Question

Can someone give me a real-world example of how Paxos algorithm is used in a distributed database? I have read many papers on Paxos that explain the algorithm but none of them really explain with an actual example.

A simple example could be a banking application where an account is being modified through multiple sessions (i.e. a deposit at a teller, a debit operation etc..). Is Paxos used to decide which operation happens first? Also, what does one mean by multiple instances of Paxos protocol? How is when is this used? Basically, I am trying to understand all this through a concrete example rather than abstract terms.

Answer 1

For example, we have MapReduce system where master consists of 3 hosts. One is master and others are slaves. The procedure of choosing master uses Paxos algorithm.

Also Chubby of Google Big Table uses Paxos: The Chubby Lock Service for Loosely-Coupled Distributed Systems, Bigtable: A Distributed Storage System for Structured Data

Answer 2

The Clustrix database is a distributed database that uses Paxos in the transaction manager. Paxos is used by the database internals to coordinate messages and maintain transaction atomicity in a distributed system.

• The Coordinator is the node the transaction originated on
• Participants are the nodes that modified the database on behalf of
• the transaction Readers are nodes that executed code on behalf of the transaction but did not modify any state
• Acceptors are the nodes that log the state of the transaction.

The following steps are taken when performing a transaction commit:

1. Coordinator sends a PREPARE message to each Participant.
2. The Participants lock transaction state. They send PREPARED messages back to the Coordinator.
3. Coordinator sends ACCEPT messages to Acceptors.
4. The Acceptors log the membership id, transaction, commit id, and participants. They send ACCEPTED messages back to the Coordinator.
5. Coordinator tells the user the commit succeeded.
6. Coordinator sends COMMIT messages to each Participant and Reader.
7. The Participants and Readers commit the transaction and update transaction state accordingly. They send COMMITTED messages back to the Coordinator.
8. Coordinator removes internal state and is now done.

This is all transparent to the application and is implemented in the database internals. So for your banking application, all the application level would need to do is perform exception handling for deadlock conflicts. The other key to implementing a database at scale is concurrency, which is generally helped via MVCC (Multi-Version concurrency control).