2

From the spanner paper, it says that

"To support replication, each spanserver implements a single Paxos state machine on top of each tablet. (An early Spanner incarnation supported multiple Paxos state machines per tablet, which allowed for more flexible replication configurations. The complexity of that design led us to abandon it.)"

so can anyone explain what dose the single paxos state machine mean? and what does the multiple paxos stathe machines mean?

I guess the multiple Paxos state machine per tablet is that there is multiple independent single Paxos state machne in a single tablet, then the leader and followers in a single tablet can replicate data in parallel, since these single paxos state machines are independent.

is it right? If I misunderstanding something, please correct me. Thank you.

Maxim
  • 4,075
  • 1
  • 14
  • 23
baotiao
  • 775
  • 6
  • 20
  • I think this other SO [case](https://stackoverflow.com/questions/26589137/why-is-multi-paxos-called-multi-paxos) does perfectly explain the difference between Paxos state machine and multi-paxos. I don't think it meant parallel replication, but just the use of former agreement on sequential table data replication. – Ggrimaldo May 31 '18 at 07:42
  • 1
    @Ggrimaldo I don't agree with you. that is not the difference between paxos and multi-paxos. And, again, we always implement multi-paxos in industry. And multi-paxos is more widely used and easier implement. so I think the multi paxos state machine meant multi multi-paxos group. – baotiao Jun 01 '18 at 07:14

1 Answers1

0

what dose the single paxos state machine mean?

By "Paxos state machine" the paper's authors mean a replicated state machine (RSM) based on the Paxos consensus algorithm.

The idea of an RSM was introduced in this paper and is explained in this Wikipedia article. In short, the idea is to build a replicated log of (deterministic) state machine operations and execute those operations on each replica in the same order, which will necessarily lead to the same state on each replica.

Paxos, which is covered well in this paper and explained in this Wikipedia article, can be used to create that replicated log.

A single vs multiple Paxos state machines means literally that - a single or multiple Paxos-based RSMs. (Note it's not about basic Paxos vs Multi-Paxos, that's something else). Think of it almost like a single vs multiple databases.

What is the practical difference? It's unclear from the paper. The paper only says that multiple RSMs "allowed for more flexible replication configurations." One possibility is that the multiple RSMs allowed for some form of sharding. On multi-tenant architectures it is common to have multiple RSMs replicas per server, one for each entity (e.g. for each database). Another possibility is that it allowed them to overcome some performance bottleneck. There are probably other possibilities as well.

Avi
  • 1,231
  • 10
  • 23