4 ms·

I know nothing of consensus algorithms and distributed systems so bear with me please. > rqlite uses Raft to achieve consensus across all the instances of the

I know nothing of consensus algorithms and distributed systems so bear with me please. > rqlite uses Raft to achieve consensus across all the instances of the SQLite databases, ensuring that every change made to the system is made to a quorum of SQLite databases, or none at all. What I understood from this sentence is that, if we have three instances, rqlite will make sure that every change is written to at least two. But what if two changes are written to two different pairs of instances? Then the three instances will have three different versions of the data. For example, change X is written to instances A and B, and change Y is written to B and C. Now A has X, B has X and Y, and C has Y only. How do you decide who is right?

jasonjayr 6y ago
IIRC, a monatomic counter is involved. The odd one out will realize it's behind the highest sequence number and discard it's updates to resync with the majority consensus. Edit: http://thesecretlivesofdata.com/raft/ http://thesecretlivesofdata.com/raft/ if you have some time seems to be a good step by step explanation on how it works in detail.
- adsharma 6y ago
  The visual is indeed cool. I also thought it'd be nice to use a chat like interface to learn raft. Alice: /set a 1 Alice: /set b 2 Bob: /status Etc https://github.com/adsharma/zre_raft https://github.com/adsharma/zre_raft https://github.com/adsharma/raft https://github.com/adsharma/raft Bug reports welcome
edoceo 6y ago
Raft consensus: https://raft.github.io/ https://raft.github.io/ Surprisingly easy to understand, and a cool viaual.
teraflop 6y ago
In brief: at any point in time, one of the replicas is a "leader" which controls the order in which operations are committed. The changes occur in a defined sequence, and other replicas may lag behind the leader, but cannot be inconsistent with it. Your example can't happen, because if (for instance) A is the leader, then C will not apply change Y without contacting the leader, which will tell it to apply X first. If you want more details about how this handles all the edge cases -- for instance, what happens if the leader crashes -- the Raft paper is quite accessible: https://raft.github.io/raft.pdf https://raft.github.io/raft.pdf
- hinkley 6y ago
  TL;DR: Raft updates are serialized (as in sequential).
whizzter 6y ago
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.

jasonjayr 6y ago

IIRC, a monatomic counter is involved. The odd one out will realize it's behind the highest sequence number and discard it's updates to resync with the majority consensus. Edit: http://thesecretlivesofdata.com/raft/ http://thesecretlivesofdata.com/raft/ if you have some time seems to be a good step by step explanation on how it works in detail.

adsharma 6y ago
The visual is indeed cool. I also thought it'd be nice to use a chat like interface to learn raft. Alice: /set a 1 Alice: /set b 2 Bob: /status Etc https://github.com/adsharma/zre_raft https://github.com/adsharma/zre_raft https://github.com/adsharma/raft https://github.com/adsharma/raft Bug reports welcome

edoceo 6y ago

Raft consensus: https://raft.github.io/ https://raft.github.io/ Surprisingly easy to understand, and a cool viaual.

teraflop 6y ago

In brief: at any point in time, one of the replicas is a "leader" which controls the order in which operations are committed. The changes occur in a defined sequence, and other replicas may lag behind the leader, but cannot be inconsistent with it. Your example can't happen, because if (for instance) A is the leader, then C will not apply change Y without contacting the leader, which will tell it to apply X first. If you want more details about how this handles all the edge cases -- for instance, what happens if the leader crashes -- the Raft paper is quite accessible: https://raft.github.io/raft.pdf https://raft.github.io/raft.pdf

hinkley 6y ago
TL;DR: Raft updates are serialized (as in sequential).

whizzter 6y ago

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.