3 ms·

I think this overstates the instability of strong leader-based consensus algorithms, or at least over-generalizes Raft's instability to apply to all consensus a

by freels 10y ago

I think this overstates the instability of strong leader-based consensus algorithms, or at least over-generalizes Raft's instability to apply to all consensus algorithms with a stronger leader. In Raft, it's possible for multiple nodes to prevent leader election progress by being overly aggressive when requesting votes. It is also possible for a follower to knock out a perfectly healthy leader by being too quick time out the leader and start a new term. Both of these limitations stem from the simplicity of Raft's leader election algorithm. To compensate, most Raft implementations I've seen have more conservative follower timeouts that extend the time to detect leader failure and elect a new one. It's possible for a more optimized algorithm to get sub-second latencies for detecting and re-electing a leader, even in a latent (e.g. geo-distributed) environment. In other words, well within the commit window for the replica set based on network hop latencies. Also, while the latency for individual writes in single-decree paxos can be closer to strong leader protocols, it is non-trivial to achieve the same level of throughput that is possible in Raft et al when writing to an ordered log, as you cannot start a paxos instance for a new log entry until all prior instances have been resolved. Raft can just add new values in the next append call (or just spam out appends for new messages w/o waiting for the replies for previous ones). IME, I'd say both single-decree paxos and raft are probably equivalent in terms of understandability, but raft is a better base on which to build a fast high-throughput consensus protocol.

rystsov 10y ago
> cannot start a paxos instance for a new log entry until all prior instances have been resolved It's wrong. In Grydka (Single-decree Paxos) all the keys are independent so it's possible to update them at the same time without blocking. Grydka's throughput is comparable to Etcd on the same type of machines (4720 vs 5227 rps) and I never optimized for it (my goal was to fit 500 lines) so it's also wrong that it's "non-trivial to achieve the same level of throughput" - I did it by accident. So I don't understand why Raft is a better base to build a fast high-throughput consensus protocol.
- freels 10y ago
  This is true, but comes at the cost of not being able to preserve linearity across arbitrary keys, and you are still limited by the throughput on updates to a single key.
  - rystsov 10y ago
    Assuming linearity is atomic multi-key updates: 1. There are tasks which don't require atomic multi-key updates 2. Atomic multi-key updates can be implemented on the client side (see RAMP, Percolator transactions or the Saga pattern) 3. Once the data overgrow the size of one machine you need to shard the log and at this time you're in the same situation
    - freels 10y ago
      Fair enough, though at that point, you're layering on additional complexity and getting further away from the goal of simplicity. (And to point 3, while this is true, using a log means this problem can be dealt with a lot later, and there are solutions that don't involve giving up linearizability, such as a dedicated set of log replicas apart from data partitions, or implementing something like Calvin.) My main point was that the deficiencies of strong-leader-based consensus protocols are overstated, and despite a (minor IMO) level of additional starting complexity, a raft-like protocol is going to be quite a bit simpler than a paxos-based protocol of equivalent capability.

by freels 10y ago

rystsov 10y ago

> cannot start a paxos instance for a new log entry until all prior instances have been resolved It's wrong. In Grydka (Single-decree Paxos) all the keys are independent so it's possible to update them at the same time without blocking. Grydka's throughput is comparable to Etcd on the same type of machines (4720 vs 5227 rps) and I never optimized for it (my goal was to fit 500 lines) so it's also wrong that it's "non-trivial to achieve the same level of throughput" - I did it by accident. So I don't understand why Raft is a better base to build a fast high-throughput consensus protocol.

freels 10y ago
This is true, but comes at the cost of not being able to preserve linearity across arbitrary keys, and you are still limited by the throughput on updates to a single key.
- rystsov 10y ago
  Assuming linearity is atomic multi-key updates: 1. There are tasks which don't require atomic multi-key updates 2. Atomic multi-key updates can be implemented on the client side (see RAMP, Percolator transactions or the Saga pattern) 3. Once the data overgrow the size of one machine you need to shard the log and at this time you're in the same situation
  - freels 10y ago
    Fair enough, though at that point, you're layering on additional complexity and getting further away from the goal of simplicity. (And to point 3, while this is true, using a log means this problem can be dealt with a lot later, and there are solutions that don't involve giving up linearizability, such as a dedicated set of log replicas apart from data partitions, or implementing something like Calvin.) My main point was that the deficiencies of strong-leader-based consensus protocols are overstated, and despite a (minor IMO) level of additional starting complexity, a raft-like protocol is going to be quite a bit simpler than a paxos-based protocol of equivalent capability.