28

Could someone give me a list of real use cases of Paxos. That is real problems that require consensus as part of a bigger problem.

Is the following a use case of Paxos?

Suppose there are two clients playing poker against each other on a poker server. The poker server is replicated. My understanding of Paxos is that it could be used to maintain consistency of the inmemory data structures that represent the current hand of poker. That is, ensure that all replicas have the exact same inmemory state of the hand.

But why is Paxos necessary? Suppose a new card needs to be dealt. Each replica running the same code will generate the same card if everything went correct. Why can't the clients just request the latest state from all the replicated servers and choose the card that appears the most. So if one server had an error the client will still get the correct state from just choosing the majority.

user782220
  • 10,677
  • 21
  • 72
  • 135

5 Answers5

16

You assume all the servers are in sync with each other (i.e., have the same state), so when a server needs to select the next card, each of the servers will select the exact same card (assuming your code is deterministic).

However, your servers' state also depends on the the user's actions. For example, if a user decided to raise by 50$ - your server needs to store that info somewhere. Now, suppose that your server replied "ok" to the web-client (I'm assuming a web-based poker game), and then the server crashed. Your other servers might not have the information regarding the 50$ raise, and your system will be inconsistent (in the sense that the client thinks that the 50$ raise was made, while the surviving servers are oblivious of it).

Notice that majority won't help here, since the data is lost. Moreover, suppose that instead of the main server crashing, the main server plus another one got the 50$ raise data. In this case, using majority could even be worse: if you get a response from the two servers with the data, you'll think the 50$ raise was performed. But if one of them fails, then you won't have majority, and you'll think that the raise wasn't performed.

In general, Paxos can be used to replicate a state machine, in a fault tolerant manner. Where "state machine" can be thought of as an algorithm that has some initial state, and it advances the state deterministically according to messages received from the outside (i.e., the web-client).

More properly, Paxos should be considered as a distributed log, you can read more about it here: Understanding Paxos – Part 1

Ezra Hoch
  • 1,752
  • 1
  • 12
  • 7
6

Update 2018:

Mysql High Availability uses paxos: https://mysqlhighavailability.com/the-king-is-dead-long-live-the-king-our-homegrown-paxos-based-consensus/

Real world example:

Cassandra uses Paxos to ensure that clients connected to different cluster nodes can safely perform write operations by adding "IF NOT EXISTS" to write operations. Cassandra has no master node so two conflicting operations can to be issued concurrently at multiple nodes. When using the if-not-exists syntax the paxos algorithm is used order operations between machines to ensure only one succeeds. This can then be used by clients to store authoritative data with an expiration lease. As long as a majority of Cassandra nodes are up it will work. So if you define the replication factor of your keyspace to be 3 then 1 node can fail, of 5 then 2 can fail, etc.

For normal writes Caassandra allows multiple conflicting writes to be accepted by different nodes which may be temporary unable to communicate. In that case doesn't use Paxos so can loose data when two Writes occur at the same time for the same key. There are special data structures built into Cassandra that won't loose data which are insert-only.

Poker and Paxos:

As other answers note poker is turn based and has rules. If you allow one master and many replicas then the master arbitrates the next action. Let's say a user first clicks the "check" button then changes their mind and clicks "fold". Those are conflicting commands only the first should be accepted. The browser should not let them press the second button it will disable it when they pressed the first button. Since money is involved the master server should also enforce the rules and only allow one action per player per turn. The problem comes when the master crashes during the game. Which replica can become master and how do you enforce that only one replica becomes master?

One way to handle choosing a new master is to use an external strong consistently service. We can use Cassandra to create a lease for the master node. The replicas can timeout on the master and attempt to take the lease. As Cassandra is using Paxos it is fault tolerant; you can still read or update the lease even if Cassandra nodes crash.

In the above example the poker master and replicas are eventually consistent. The master can send heartbeats so the replicas know that they are still connected to the master. That is fast as messages flow in one direction. When the master crashes there may be race conditions in replicas trying to be the master. Using Paxos at that point gives you strong consistently on the outcome of which node is now the master. This requires additional messages between nodes to ensure a consensus outcome of a single master.

simbo1905
  • 6,321
  • 5
  • 58
  • 86
5

Real life use cases:

  1. The Chubby lock service for loosely-coupled distributed systems

  2. Apache ZooKeeper

Fakrudeen
  • 5,778
  • 7
  • 44
  • 70
  • 1
    Another real life use case is RavenDB handling electing of a master node, http://ayende.com/blog/4824/raven-situational-awareness – Chris Chilvers Jun 03 '11 at 11:18
  • 3
    These aren't problems or use cases, but Paxos implementations or solutions. – Derek Mahar May 15 '12 at 09:03
  • 15
    Zookeeper doesn't use Paxos, it actually uses Zab [1]. 1. Zab is described in “A simple totally ordered broadcast protocol” by Benjamin Reed and Flavio Junqueira (LADIS ’08: Proceedings of the 2nd Workshop on Large-Scale Dis- tributed Systems and Middleware, pages 1–6, New York, NY, USA, 2008. ACM) – Stanislav Levental Nov 07 '12 at 16:00
  • This answer should be updated with if Zookeeper uses/used Paxos or not. Otherwise looks misleading. – Alex Yursha Jan 30 '18 at 01:40
3

Paxos is used for WAN-based replication of Subversion repositories and high availability of the Hadoop NameNode by the company I work for (WANdisco plc.)

James Creasy
  • 653
  • 1
  • 4
  • 15
0

In the case you describe, you're right, Paxos isn't really necessary: A single central authority can generate a permutation for the deck and distribute it to everyone at the beginning of the hand. In fact, for a poker game in general, where there's a strict turn order and a single active player as in poker, I can't see a sensible situation in which you might need to use Paxos, except perhaps to elect the central authority that shuffles decks.

A better example might be a game with simultaneous moves, such as Jeopardy. Paxos in this situation would allow all the servers to decide together what sequence a series of closely timed events (such as buzzer presses) occurred in, such that all the servers come to the same conclusion.

Nick Johnson
  • 100,655
  • 16
  • 128
  • 198
  • Wait what if I add the extra constraint that the result needs to be archived into some kind of permanent logging system. Lets say the logging system is a SQL database. So the entire hand history needs to be stored into the SQL database and the money for each player needs to be updated in the SQL database as well. How can this logging be done fault tolerant in the case I described without Paxos but just replica servers. It would seem trying to rely on just one of the servers to write to the SQL database would be prone to the one server crashing. – user782220 Jun 03 '11 at 07:37
  • @user782220 If you're using an SQL database, you need to rely on its replication - if any - which may or may not use paxos. If you were building your own system to track transactions, though, and you wanted it to be multi-master, yes, you probably would want to use Paxos. – Nick Johnson Jun 03 '11 at 08:14
  • What do you mean by rely on the replication of SQL database? Isn't relying on the replication of some master SQL database dangerous? Its relying on the master SQL database, of which there is only one, to not become corrupted. Isn't that inherently not fault tolerant. – user782220 Jun 03 '11 at 08:27
  • @user782220 Relying on a pre-built replication solution is a lot less dangerous than inventing your own! Paxos is extremely tough to get right, and building some sort of synchronization layer on top of an existing DB isn't particularly advisable. Whether or not your database is fault-tolerant depends on the DB and what sort of replication it has. – Nick Johnson Jun 03 '11 at 10:09