7 ms·

I find that the core of Paxos (the Synod protocol) is very easy to understand - it is literally just two exchanges of messages! The tricks that you need to add

I find that the core of Paxos (the Synod protocol) is very easy to understand - it is literally just two exchanges of messages! The tricks that you need to add to go from the Synod protocol and get an actual production implementation of the replicated log are another matter, the original paper only hints about some of them. There is e.g. the Paxos Made Live paper (link: https://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/paper2-1.pdf https://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/paper...) that has more on this topic. BTW Paxos also has a leader - this is what makes these protocols efficient. They need only the linear number of messages instead of the quadratic "everybody talks to everybody" design.

vyodaiken 7y ago
>BTW Paxos also has a leader - this is what makes these protocols efficient. That's the funny part of Paxos. Paxos is specifically sold as a multi-proposer protocol. The most subtle and hard to understand part of the protocol is the clever 2 phase proposal election with value inheritance. But it's all pointless because in order to make the system work you need a single coordinator you elect using timeouts or reliable message protocols.
kerkeslager 7y ago
> BTW Paxos also has a leader - this is what makes these protocols efficient. They need only the linear number of messages instead of the quadratic "everybody talks to everybody" design. Okay, but again, this means that the leader is the bottleneck. In that case, I'd want the leader to be on beefier hardware than the other machines, and to not serve up any read requests, so all of its resources are devoted to leading. In order to accommodate this, you'd want to elect leaders from a pool of leaders which have the beefier hardware. And at that point, since you're only talking to the leaders when you write, rather than talk through to the leaders through the extra latency of the followers, just write to the leaders directly. And then at that point this looks suspiciously like the leaders are a sharded database and the followers are caches. Am I missing something?

vyodaiken 7y ago

>BTW Paxos also has a leader - this is what makes these protocols efficient. That's the funny part of Paxos. Paxos is specifically sold as a multi-proposer protocol. The most subtle and hard to understand part of the protocol is the clever 2 phase proposal election with value inheritance. But it's all pointless because in order to make the system work you need a single coordinator you elect using timeouts or reliable message protocols.

kerkeslager 7y ago

> BTW Paxos also has a leader - this is what makes these protocols efficient. They need only the linear number of messages instead of the quadratic "everybody talks to everybody" design. Okay, but again, this means that the leader is the bottleneck. In that case, I'd want the leader to be on beefier hardware than the other machines, and to not serve up any read requests, so all of its resources are devoted to leading. In order to accommodate this, you'd want to elect leaders from a pool of leaders which have the beefier hardware. And at that point, since you're only talking to the leaders when you write, rather than talk through to the leaders through the extra latency of the followers, just write to the leaders directly. And then at that point this looks suspiciously like the leaders are a sharded database and the followers are caches. Am I missing something?