4 ms·

The semantics of Raft has a "simple" (compared to the harder to understand Paxos) forward motion of events that is supposed to guarantee that you won't get into

The semantics of Raft has a "simple" (compared to the harder to understand Paxos) forward motion of events that is supposed to guarantee that you won't get into weird states regardless of if any particular node(s) goes down (I think it can surive (N/2)-1 dead machines in a cluster of N). Raft is based on having a leader decide what the next COMMIT is going to be, so B could never have X and Y at the same time (they could both be queued but other mechanisms could reject them). Also data is not considered committed until more than half the cluster has acknowledged it (at which point the leader will know it and handle going forward), leader election also works in a similar way iirc. As others mentioned, the visualization on https://raft.github.io/ https://raft.github.io/ is really good (You can affect it to create commits and control downtime of machines)

hinkley 6y ago
It’s 1/2 + 1 isn’t it? So if the leader goes down at the exact moment of quorum, you you can still get quorum again. That would mean in 3 servers you need 2.5 aka 3 machines to commit a change. Then 4/5, 5/7, 6/9, 7/11. And I think it’s a wash anyway, because as the servers go up the fraction you need for quorum goes down, but the odds of falling behind or failing outright go up too. Not to mention the time during which 1/n machines are down due to an upgrade gets longer and longer the more machines you have, increasing the chances of double fault.
- simtel20 6y ago
  > It’s 1/2 + 1 isn’t it? The parent post is talking about the number that can go down while maintaining quorum, and you're talking about the number that need to remain up to maintain quorum. So you're both correct. However: > That would mean in 3 servers you need 2.5 aka 3 machines to commit a change. That seems wrong. You need N//2 +1 where "//" is floor division, so in a 3 node cluster, you need 3//2 +1, or 1+1 or 2 nodes to commit a change.
  - hinkley 6y ago
    I think I see the problem. 'Simple majority' is based on the number of the machines that the leader knows about. You can only change the membership by issuing a write. Write quorum and leadership quorum are two different things, and if I've got it right, they can diverge after a partition. I'm also thinking of double faults, because the point of Raft is to get past single fault tolerance. [edit: shortened] After a permanent fault (broken hardware) in a cluster of 5, the replacement quorum member can't vote for writes until it has caught up. It can vote for leaders, but it can't nominate itself. Catching up leaves a window for additional faults. It's always 3/5 for writes and elections, the difference is that the ratio of original machines that have to confirm a write can go to 100% of survivors, instead of the 3/4 of reachable machines. Meaning network jitter and packet loss, slows down writes until it recovers, and an additional partition can block writes altogether, even with 3/5 surviving the partition.
- teraflop 6y ago
  > It’s 1/2 + 1 isn’t it? > That would mean in 3 servers you need 2.5 aka 3 machines to commit a change. Then 4/5, 5/7, 6/9, 7/11. No, the requirement isn't 1/2 + 1. Any strict majority of the cluster is enough to elect a leader. So you need 2/3, or 3/4, or 3/5, and so on. > Not to mention the time during which 1/n machines are down due to an upgrade gets longer and longer the more machines you have, increasing the chances of double fault. Generally, this is not the case. If individual machine failures are random and equally probable, and if each machine is down on average less than 50% of the time, then adding more machines makes things better, not worse. (This is a basic property of the binomial distribution.) Of course, if you have a single point of failure somewhere -- e.g. a network switch -- this assumption can be violated, but that's true regardless of how many machines you have.
  - hinkley 6y ago
    If the leader is down (the scenario you clipped out in your response) you need a strict majority with an even number of machines.
    - hinkley 6y ago
      This is right for the wrong reason. See follow-up down-thread.

hinkley 6y ago

It’s 1/2 + 1 isn’t it? So if the leader goes down at the exact moment of quorum, you you can still get quorum again. That would mean in 3 servers you need 2.5 aka 3 machines to commit a change. Then 4/5, 5/7, 6/9, 7/11. And I think it’s a wash anyway, because as the servers go up the fraction you need for quorum goes down, but the odds of falling behind or failing outright go up too. Not to mention the time during which 1/n machines are down due to an upgrade gets longer and longer the more machines you have, increasing the chances of double fault.

simtel20 6y ago
> It’s 1/2 + 1 isn’t it? The parent post is talking about the number that can go down while maintaining quorum, and you're talking about the number that need to remain up to maintain quorum. So you're both correct. However: > That would mean in 3 servers you need 2.5 aka 3 machines to commit a change. That seems wrong. You need N//2 +1 where "//" is floor division, so in a 3 node cluster, you need 3//2 +1, or 1+1 or 2 nodes to commit a change.
- hinkley 6y ago
  I think I see the problem. 'Simple majority' is based on the number of the machines that the leader knows about. You can only change the membership by issuing a write. Write quorum and leadership quorum are two different things, and if I've got it right, they can diverge after a partition. I'm also thinking of double faults, because the point of Raft is to get past single fault tolerance. [edit: shortened] After a permanent fault (broken hardware) in a cluster of 5, the replacement quorum member can't vote for writes until it has caught up. It can vote for leaders, but it can't nominate itself. Catching up leaves a window for additional faults. It's always 3/5 for writes and elections, the difference is that the ratio of original machines that have to confirm a write can go to 100% of survivors, instead of the 3/4 of reachable machines. Meaning network jitter and packet loss, slows down writes until it recovers, and an additional partition can block writes altogether, even with 3/5 surviving the partition.
teraflop 6y ago
> It’s 1/2 + 1 isn’t it? > That would mean in 3 servers you need 2.5 aka 3 machines to commit a change. Then 4/5, 5/7, 6/9, 7/11. No, the requirement isn't 1/2 + 1. Any strict majority of the cluster is enough to elect a leader. So you need 2/3, or 3/4, or 3/5, and so on. > Not to mention the time during which 1/n machines are down due to an upgrade gets longer and longer the more machines you have, increasing the chances of double fault. Generally, this is not the case. If individual machine failures are random and equally probable, and if each machine is down on average less than 50% of the time, then adding more machines makes things better, not worse. (This is a basic property of the binomial distribution.) Of course, if you have a single point of failure somewhere -- e.g. a network switch -- this assumption can be violated, but that's true regardless of how many machines you have.
- hinkley 6y ago
  If the leader is down (the scenario you clipped out in your response) you need a strict majority with an even number of machines.
  - hinkley 6y ago
    This is right for the wrong reason. See follow-up down-thread.