9 ms·

Raft: Understandable Distributed Consensus

161 points by otoolep 12y ago

coreymgilmore 12y ago
Very cool intro website. Is this used in production somewhere already? Would love to hear more of the details about use cases and deployment.
- stonith 12y ago
  Raft? It's used in etcd, consul, serf and probably more.
  - otoolep 12y ago
    I used it to build distributed replication of a SQLite database. Quite good fun. https://github.com/otoolep/rqlite https://github.com/otoolep/rqlite
  - mitchellh 12y ago
    Just a nitpick here with the qualifications that I'm one of the authors of Serf: Serf doesn't use Raft. Serf is masterless and the distributed messaging protocol used is SWIM (a gossip protocol).
    - stonith 12y ago
      Apologies, thanks for the correction.
  - otoolep 12y ago
    InfluxDB too, a time-series database written entirely in Go. http://influxdb.com http://influxdb.com
  - andrewguenther 12y ago
    Username "stonith" commenting on a post about Raft? I laughed out loud. http://en.wikipedia.org/wiki/STONITH http://en.wikipedia.org/wiki/STONITH
Illniyar 12y ago
So this site is using a custom built library called "playback.js": https://github.com/benbjohnson/playback.js https://github.com/benbjohnson/playback.js looks interesting.
- restalis 12y ago
  I accidentally clicked twice on "Continue" and there wasn't any mean to go back to read the missed comment. This slide-show player wants to be clean and simple and ends up with holes in functionality.
  - deleted 12y ago
    [deleted]
  - evrenesat 12y ago
    While this will not help for touch screen devices, left arrow goes back.
  - deleted 12y ago
    [deleted]
thrownaway2424 12y ago
Where's the skip intro button on this horror show?
- thrownaway2424 12y ago
  https://ramcloud.stanford.edu/wiki/download/attachments/11370504/raft.pdf https://ramcloud.stanford.edu/wiki/download/attachments/1137...
stfp 12y ago
Awesome
pandatigox 12y ago
They've written a lot on the subject. For anyone who prefers the arrow key over the 'continue' button, https://speakerdeck.com/search?q=raft https://speakerdeck.com/search?q=raft
- polskibus 12y ago
  The arrrow key works for me (in Chrome at least).
Illniyar 12y ago
If I've understood the presentation correctly, Raft is a master-slave protocol that determines how to choose a master. Considering it basically relies on random chance (I.E. who receives the message first) to elect a master, has basically no real way of resolving a conflict in election (I.E. if two nodes receive the same amount of votes, we do a re-election ad infinitum) and does not address the situation of two nodes having conflicting sets of data (for instance from network partition). Considering all that, this protocol doesn't seem very interesting (from a use-case point of view).
- stonith 12y ago
  For the split vote see https://github.com/goraft/raft/issues/13 https://github.com/goraft/raft/issues/13 The conflicting data under partition is covered I think - the set that doesn't meet quorum won't accept writes and will see it has a lower election term than the other partition when it re-joins. EDIT: From a use vase point of view, it simplifies the construction of CP systems. This has directly led to etcd and consul, which would be many times more complex had their authors had to implement paxos. Both etcd and consul are still young software, but if you take a look at the 'Call me Maybe' series of blog posts it's pretty apparent that there's a massive deficiency in current systems handling of network partitions. http://aphyr.com/posts/281-call-me-maybe-carly-rae-jepsen-and-the-perils-of-network-partitions http://aphyr.com/posts/281-call-me-maybe-carly-rae-jepsen-an...
- deathanatos 12y ago
  > and does not address the situation of two nodes having conflicting sets of data (for instance from network partition). I believe it does address this. Each log entry is either committed or not; an entry can only be committed if it has been replicated to a majority of nodes. Any node that lacks a committed entry cannot be elected master because of the election rules: a node will not vote for another node less complete than itself. Since a committed entry has been replicated to a majority, a node lacking that entry cannot receive a majority of the votes. (Thus the committed log entries will always be the same on all nodes (though some may be behind, and may only have a subset), which is the purpose of the protocol.) > Considering it basically relies on random chance (I.E. who receives the message first) to elect a master, has basically no real way of resolving a conflict in election This is mostly true. The PDF slides I link to below recommend that the election timeout be much greater than the broadcast time, the idea being that things should work out in the long run. Highly recommend the PDF slides here, as they explain it better than I can: https://ramcloud.stanford.edu/~ongaro/userstudy/ https://ramcloud.stanford.edu/~ongaro/userstudy/ — there's also a YouTube talk here: https://www.youtube.com/watch?v=YbZ3zDzDnrw https://www.youtube.com/watch?v=YbZ3zDzDnrw > Considering all that, this protocol doesn't seem very interesting (from a use-case point of view). I'd love to hear of alternatives.
FredericJ 12y ago
It's important to note that this consensus model only works if all nodes are honest.
- deathanatos 12y ago
  Given that nodes are trusted and communicate securely, why would a node be dishonest? (I'm thinking about this in a standard server setting: is your point that you can't use it for distributed peer-to-peer stuff on random user machines?)
  - the_schwarz 12y ago
    A "dishonest" node doesn't necessarily have to be explicitly malicious, it can be simply faulty.
    - elbenshira 12y ago
      Lots of research has gone into this, under the name Byzantine fault tolerance. http://en.wikipedia.org/wiki/Byzantine_fault_tolerance http://en.wikipedia.org/wiki/Byzantine_fault_tolerance
  - kijin 12y ago
    For one thing, you can't use it for cryptocurrency stuff.
- jedunnigan 12y ago
  Yep. It seems to me that homogeneity amongst nodes in a distributed consensus mechanism is of utmost importance; once you implement a hierarchical power structure dishonesty becomes difficult to deal with... especially when "voting" for a "leader" is involved in mapping the node landscape. edit:spelling
deleted 12y ago
[deleted]
regularfry 12y ago
Can't this lose commits? It looks like the message to commit the log entry to the followers happens after the message to the client to say that the commit is confirmed. The client can't actually tell when their commit has been replicated. If the leader dies before sending that confirm to the followers, the client will end up thinking the new leader has a commit which it's going to have to roll back. Is this something the full algorithm handles differently to the way the diagrams would indicate?
- skew 12y ago
  The response to the client is only sent after a majority of followers have the log entry. That's described in the text in the "Protocol Overview", and nicely animated in "Log Replication".
  - regularfry 12y ago
    Yes, they have the log entry, but it can still be rolled back, can't it? Here's how I understand the process: 1. Client sends log entry to leader 2. Leader appends log entry, forwards it to followers 3. Majority of followers confirm 4. Leader commits the log entry 5. Leader confirms the commit to the client 6. Followers commit on the next heartbeat What happens if the leader goes away between 5 and 6? To my eyes, it looks like the followers will time out, elect a new leader, and have to roll back the last log entry.
    - DanWaterworth 12y ago
      If an entry has been replicated to a majority of followers, then the new leader is guaranteed to have that entry and therefore it won't be rolled back.
      - regularfry 12y ago
        How does the new leader know it went to a majority? The only entity which could confirm that is the old leader.
hardwaresofton 12y ago
For those who are encountering distributed systems for the first time, it might also do you some good to look up (or use as search fodder) "Paxos". If you want to dive even deeper "FLP" and "Leslie Lamport" should also open up a can of interesting worms
toolslive 12y ago
Raft itself is very nice, and the paper https://ramcloud.stanford.edu/wiki/download/attachments/11370504/raft.pdf https://ramcloud.stanford.edu/wiki/download/attachments/1137... Does an excellent job in explaining it, but I have some problems with this claim: "A user study with 43 students at two universities shows that Raft is significantly easier to understand than Paxos: after learning both algorithms, 33 of these students were able to answer questions about Raft better than questions about Paxos". Honestly, what I think happened is this: They first explained paxos to the poor students, then asked questions. In a later session explained Raft and asked questions. Can't it be the students started processing the problem of distributed consensus between the sessions so they got a better grasp of the topic? This would mean paxos helped them understand raft better. Anyway I'm nitpicking etc etc.
- sbhat7 12y ago
  From 9.1 section in the paper, > Each student watched one video, took the corresponding quiz, watched the second video, and took the second quiz. About half of the participants did the Paxos portion first and the other half did the Raft portion first in order to account for both individual differences in performance and experience gained from the first portion of the study. We compared participants’ scores on each quiz to deter- mine whether participants showed a better understanding of Raft.
  - toolslive 12y ago
    This seems to be a good strategy but it is difficult to factor out the quality of the explanations. The reason I'm so picky about this claim is that before you know it, you have mythical pseudo-statistical claims like "some programmers are more than 10 times as good as others" that will live a life of their own. CS has way too many of those.
lclarkmichalek 12y ago
In the network partition example, you say that in the smaller partition, changes cannot be commited because they cannot be replicated to the majority of nodes (as the smaller partition is... smaller). How is the partition to know this? The system can't tell the difference between a node leaving the network and a node undergoing a (tempoary) partition. To give an example, say I have n machines in datacenter A, and n*.99 in datacenter B. datacenter A gets destroyed, permanently. Does datacenter B now reject all (EDIT: where reject = not commit) requests until a human comes along to tell it that datacenter A isn't coming back?
- sbhat7 12y ago
  > To give an example, say I have n machines in datacenter A, and n*.99 in datacenter B. datacenter A gets destroyed, permanently. Does datacenter B now reject all (EDIT: where reject = not commit) requests until a human comes along to tell it that datacenter A isn't coming back? Of CAP, you are now choosing CP with Raft. So yes, the system is unavailable until an external agent fixes it. In other words, the system needs to have a majority of nodes online to be "available".
  - lclarkmichalek 12y ago
    What would happen if nodes were to be added to each side of a network partition (unknown to the other side), so that each side believed they had a majority? Or is the "writing" side of the partition determined at partition time, and not changed until they are restored?
    - sbhat7 12y ago
      To add a new node to the network, it * needs to have the same data as the other nodes * needs a round of Raft to notify its presence to other nodes So you can only add new nodes (automatically) when you have a 'live' system. majority = ceil((2n + 1)/2) : so by getting the number of available nodes in the partition, nodes can figure out if they are in the majority or minority cluster. See section 6 in the paper for details of its implementation.
- 12y ago
PeterisP 12y ago
Horrible presentation - the enforced pauses (even hiding the continue button during them!) cause frustration after every single sentence. Why can't I read at a normal pace instead of being interrupted all the time and having to wait while the next sentence is shown? [edit] This behavior would be very suitable if I was making a presentation to an audience with this content - but it's quite contrary to what's needed for the audience to view the content themselves at their own pacing.
- annnnd 12y ago
  Well, I like it - a lot. It would be even nicer if the "Continue" button had a permanent position (and if I could use enter/space/pagedown/... instead of mouse), but I didn't notice that it was hidden between animations. I guess I am slower than you are. :) I am not sure if the concept is valid (some other comments have issue with that), but it was well presented. Good job, OP - keep it up!
  - lambda 12y ago
    You can use the arrow keys to navigate, which is a lot better than clicking "Continue" each time.
    - lobster_johnson 12y ago
      Arrow keys don't help much on a tablet or a phone.
- pjc50 12y ago
  +1 It's infuriatingly slow. This is almost worse than presenting text content as videos.
- smeyer 12y ago
  I only managed to click continue two or three times before I gave up in frustration.
  - 12y ago
grogers 12y ago
Can someone explain to me how Raft differs from Viewstamped Replication? From reading both papers (vr revisited) it looks like Raft just renamed all of VR's nomenclature without changing anything significant. Paxos is fairly different since it only relies on a distinguished leader for guaranteed progress, it "works" without it. Under the hood the mechanism is still similar though, as opposed to something like chain replication.
- Muzzaf 12y ago
  See section 10 of the Raft paper. > VR uses a leaderbased approach with many similarities to Raft. > However, Raft has less mechanism that VR or ZooKeeper because it minimizes the functionality in non-leaders. For example, log entries in Raft flow in only one direction: outward from the leader in AppendEntries RPCs. In VR log entries flow in both directions (leaders can receive log entries during the election process); this results in additional mechanism and complexity > Raft has fewer message types than any other algorithm for consensus-based log replication that we are aware of. For example, we counted the message types VR and ZooKeeper use for basic consensus and membership changes (excluding log compaction and client interaction, as these are nearly independent of the algorithms). VR and ZooKeeper each define 10 different message types, while Raft has only 4 message types (two RPC requests and their responses).
blutoot 12y ago
This maybe a bit off-topic but I fail to understand why the top 2 textbooks on Distributed Computing - Tanenbaum and Coulouris - don't have a dedicated section on Consensus Algorithms. I learned distributed computing from Tanenbaum and can't recall encountering it. Contrary some of the folks here, I found the presentation very cool. But that maybe because I'm a slow learner.
- tigeba 12y ago
  You may want to check out "Reliable and Secure Distributed Programming", it has a few chapters on Consensus.
pepijndevos 12y ago
In the example with 5 nodes and a split, it is my understanding that the two nodes can't elect a leader. While the candidate in the smaller split receives votes from a majority of the split, there is no true majority, so no leader. The cluster is configured with the total number of nodes. What could happen is that an already elected leader continues to think it's the leader for a while while the rest fo the cluster elects a new leader. The split leader will however fail to commit its log, and throw them away once it rejoins. Another important detail that's missing is that node only votes once pere term, and only for a node that has an equal or higher term than itself. It will never vote twice or vote for an outdated node. Changing the configuration is in fact handled in a special way at the end of the raft paper in a way that avoids split-brain. [edit] Oh, the 2-node split was in fact already the leader, so it does exactly what I described. Dur...
rwinn 12y ago
So what happens if a network partition occurs where both sides can elect a new leader?
- pepijndevos 12y ago
  This can't happen. You can't devide a cluster in half and still have a majority. See my other post.
  - rwinn 12y ago
    Ah, ok so all nodes needs to be known beforehand
    - knyt 12y ago
      Yeah, and any changes to the set of nodes (adding or removing a node from the cluster) must be agreed upon by a majority of the existing nodes.
- Muzzaf 12y ago
  At most one side can elect a new leader, since there are an odd number of nodes.
fiatjaf 12y ago
How do you do these animations?
pit 12y ago
Holy cow: social media is a means for distributing consensus.
EGreg 12y ago
Sex.

161 points by otoolep 12y ago

Very cool intro website. Is this used in production somewhere already? Would love to hear more of the details about use cases and deployment.

stonith 12y ago
Raft? It's used in etcd, consul, serf and probably more.
- otoolep 12y ago
  I used it to build distributed replication of a SQLite database. Quite good fun. https://github.com/otoolep/rqlite https://github.com/otoolep/rqlite
- mitchellh 12y ago
  Just a nitpick here with the qualifications that I'm one of the authors of Serf: Serf doesn't use Raft. Serf is masterless and the distributed messaging protocol used is SWIM (a gossip protocol).
  - stonith 12y ago
    Apologies, thanks for the correction.
- otoolep 12y ago
  InfluxDB too, a time-series database written entirely in Go. http://influxdb.com http://influxdb.com
- andrewguenther 12y ago
  Username "stonith" commenting on a post about Raft? I laughed out loud. http://en.wikipedia.org/wiki/STONITH http://en.wikipedia.org/wiki/STONITH

Illniyar 12y ago

So this site is using a custom built library called "playback.js": https://github.com/benbjohnson/playback.js https://github.com/benbjohnson/playback.js looks interesting.

restalis 12y ago
I accidentally clicked twice on "Continue" and there wasn't any mean to go back to read the missed comment. This slide-show player wants to be clean and simple and ends up with holes in functionality.
- deleted 12y ago
  [deleted]
- evrenesat 12y ago
  While this will not help for touch screen devices, left arrow goes back.
- deleted 12y ago
  [deleted]

thrownaway2424 12y ago

Where's the skip intro button on this horror show?

thrownaway2424 12y ago
https://ramcloud.stanford.edu/wiki/download/attachments/11370504/raft.pdf https://ramcloud.stanford.edu/wiki/download/attachments/1137...

stfp 12y ago

Awesome

pandatigox 12y ago

They've written a lot on the subject. For anyone who prefers the arrow key over the 'continue' button, https://speakerdeck.com/search?q=raft https://speakerdeck.com/search?q=raft

polskibus 12y ago
The arrrow key works for me (in Chrome at least).

Illniyar 12y ago

If I've understood the presentation correctly, Raft is a master-slave protocol that determines how to choose a master. Considering it basically relies on random chance (I.E. who receives the message first) to elect a master, has basically no real way of resolving a conflict in election (I.E. if two nodes receive the same amount of votes, we do a re-election ad infinitum) and does not address the situation of two nodes having conflicting sets of data (for instance from network partition). Considering all that, this protocol doesn't seem very interesting (from a use-case point of view).

stonith 12y ago
For the split vote see https://github.com/goraft/raft/issues/13 https://github.com/goraft/raft/issues/13 The conflicting data under partition is covered I think - the set that doesn't meet quorum won't accept writes and will see it has a lower election term than the other partition when it re-joins. EDIT: From a use vase point of view, it simplifies the construction of CP systems. This has directly led to etcd and consul, which would be many times more complex had their authors had to implement paxos. Both etcd and consul are still young software, but if you take a look at the 'Call me Maybe' series of blog posts it's pretty apparent that there's a massive deficiency in current systems handling of network partitions. http://aphyr.com/posts/281-call-me-maybe-carly-rae-jepsen-and-the-perils-of-network-partitions http://aphyr.com/posts/281-call-me-maybe-carly-rae-jepsen-an...
deathanatos 12y ago
> and does not address the situation of two nodes having conflicting sets of data (for instance from network partition). I believe it does address this. Each log entry is either committed or not; an entry can only be committed if it has been replicated to a majority of nodes. Any node that lacks a committed entry cannot be elected master because of the election rules: a node will not vote for another node less complete than itself. Since a committed entry has been replicated to a majority, a node lacking that entry cannot receive a majority of the votes. (Thus the committed log entries will always be the same on all nodes (though some may be behind, and may only have a subset), which is the purpose of the protocol.) > Considering it basically relies on random chance (I.E. who receives the message first) to elect a master, has basically no real way of resolving a conflict in election This is mostly true. The PDF slides I link to below recommend that the election timeout be much greater than the broadcast time, the idea being that things should work out in the long run. Highly recommend the PDF slides here, as they explain it better than I can: https://ramcloud.stanford.edu/~ongaro/userstudy/ https://ramcloud.stanford.edu/~ongaro/userstudy/ — there's also a YouTube talk here: https://www.youtube.com/watch?v=YbZ3zDzDnrw https://www.youtube.com/watch?v=YbZ3zDzDnrw > Considering all that, this protocol doesn't seem very interesting (from a use-case point of view). I'd love to hear of alternatives.

FredericJ 12y ago

It's important to note that this consensus model only works if all nodes are honest.

deathanatos 12y ago
Given that nodes are trusted and communicate securely, why would a node be dishonest? (I'm thinking about this in a standard server setting: is your point that you can't use it for distributed peer-to-peer stuff on random user machines?)
- the_schwarz 12y ago
  A "dishonest" node doesn't necessarily have to be explicitly malicious, it can be simply faulty.
  - elbenshira 12y ago
    Lots of research has gone into this, under the name Byzantine fault tolerance. http://en.wikipedia.org/wiki/Byzantine_fault_tolerance http://en.wikipedia.org/wiki/Byzantine_fault_tolerance
- kijin 12y ago
  For one thing, you can't use it for cryptocurrency stuff.
jedunnigan 12y ago
Yep. It seems to me that homogeneity amongst nodes in a distributed consensus mechanism is of utmost importance; once you implement a hierarchical power structure dishonesty becomes difficult to deal with... especially when "voting" for a "leader" is involved in mapping the node landscape. edit:spelling

deleted 12y ago

[deleted]

regularfry 12y ago

Can't this lose commits? It looks like the message to commit the log entry to the followers happens after the message to the client to say that the commit is confirmed. The client can't actually tell when their commit has been replicated. If the leader dies before sending that confirm to the followers, the client will end up thinking the new leader has a commit which it's going to have to roll back. Is this something the full algorithm handles differently to the way the diagrams would indicate?

skew 12y ago
The response to the client is only sent after a majority of followers have the log entry. That's described in the text in the "Protocol Overview", and nicely animated in "Log Replication".
- regularfry 12y ago
  Yes, they have the log entry, but it can still be rolled back, can't it? Here's how I understand the process: 1. Client sends log entry to leader 2. Leader appends log entry, forwards it to followers 3. Majority of followers confirm 4. Leader commits the log entry 5. Leader confirms the commit to the client 6. Followers commit on the next heartbeat What happens if the leader goes away between 5 and 6? To my eyes, it looks like the followers will time out, elect a new leader, and have to roll back the last log entry.
  - DanWaterworth 12y ago
    If an entry has been replicated to a majority of followers, then the new leader is guaranteed to have that entry and therefore it won't be rolled back.
    - regularfry 12y ago
      How does the new leader know it went to a majority? The only entity which could confirm that is the old leader.

hardwaresofton 12y ago

For those who are encountering distributed systems for the first time, it might also do you some good to look up (or use as search fodder) "Paxos". If you want to dive even deeper "FLP" and "Leslie Lamport" should also open up a can of interesting worms

toolslive 12y ago

Raft itself is very nice, and the paper https://ramcloud.stanford.edu/wiki/download/attachments/11370504/raft.pdf https://ramcloud.stanford.edu/wiki/download/attachments/1137... Does an excellent job in explaining it, but I have some problems with this claim: "A user study with 43 students at two universities shows that Raft is significantly easier to understand than Paxos: after learning both algorithms, 33 of these students were able to answer questions about Raft better than questions about Paxos". Honestly, what I think happened is this: They first explained paxos to the poor students, then asked questions. In a later session explained Raft and asked questions. Can't it be the students started processing the problem of distributed consensus between the sessions so they got a better grasp of the topic? This would mean paxos helped them understand raft better. Anyway I'm nitpicking etc etc.

sbhat7 12y ago
From 9.1 section in the paper, > Each student watched one video, took the corresponding quiz, watched the second video, and took the second quiz. About half of the participants did the Paxos portion first and the other half did the Raft portion first in order to account for both individual differences in performance and experience gained from the first portion of the study. We compared participants’ scores on each quiz to deter- mine whether participants showed a better understanding of Raft.
- toolslive 12y ago
  This seems to be a good strategy but it is difficult to factor out the quality of the explanations. The reason I'm so picky about this claim is that before you know it, you have mythical pseudo-statistical claims like "some programmers are more than 10 times as good as others" that will live a life of their own. CS has way too many of those.

lclarkmichalek 12y ago

In the network partition example, you say that in the smaller partition, changes cannot be commited because they cannot be replicated to the majority of nodes (as the smaller partition is... smaller). How is the partition to know this? The system can't tell the difference between a node leaving the network and a node undergoing a (tempoary) partition. To give an example, say I have n machines in datacenter A, and n*.99 in datacenter B. datacenter A gets destroyed, permanently. Does datacenter B now reject all (EDIT: where reject = not commit) requests until a human comes along to tell it that datacenter A isn't coming back?

sbhat7 12y ago
> To give an example, say I have n machines in datacenter A, and n*.99 in datacenter B. datacenter A gets destroyed, permanently. Does datacenter B now reject all (EDIT: where reject = not commit) requests until a human comes along to tell it that datacenter A isn't coming back? Of CAP, you are now choosing CP with Raft. So yes, the system is unavailable until an external agent fixes it. In other words, the system needs to have a majority of nodes online to be "available".
- lclarkmichalek 12y ago
  What would happen if nodes were to be added to each side of a network partition (unknown to the other side), so that each side believed they had a majority? Or is the "writing" side of the partition determined at partition time, and not changed until they are restored?
  - sbhat7 12y ago
    To add a new node to the network, it * needs to have the same data as the other nodes * needs a round of Raft to notify its presence to other nodes So you can only add new nodes (automatically) when you have a 'live' system. majority = ceil((2n + 1)/2) : so by getting the number of available nodes in the partition, nodes can figure out if they are in the majority or minority cluster. See section 6 in the paper for details of its implementation.
12y ago

PeterisP 12y ago

Horrible presentation - the enforced pauses (even hiding the continue button during them!) cause frustration after every single sentence. Why can't I read at a normal pace instead of being interrupted all the time and having to wait while the next sentence is shown? [edit] This behavior would be very suitable if I was making a presentation to an audience with this content - but it's quite contrary to what's needed for the audience to view the content themselves at their own pacing.

annnnd 12y ago
Well, I like it - a lot. It would be even nicer if the "Continue" button had a permanent position (and if I could use enter/space/pagedown/... instead of mouse), but I didn't notice that it was hidden between animations. I guess I am slower than you are. :) I am not sure if the concept is valid (some other comments have issue with that), but it was well presented. Good job, OP - keep it up!
- lambda 12y ago
  You can use the arrow keys to navigate, which is a lot better than clicking "Continue" each time.
  - lobster_johnson 12y ago
    Arrow keys don't help much on a tablet or a phone.
pjc50 12y ago
+1 It's infuriatingly slow. This is almost worse than presenting text content as videos.
smeyer 12y ago
I only managed to click continue two or three times before I gave up in frustration.
- 12y ago

grogers 12y ago

Can someone explain to me how Raft differs from Viewstamped Replication? From reading both papers (vr revisited) it looks like Raft just renamed all of VR's nomenclature without changing anything significant. Paxos is fairly different since it only relies on a distinguished leader for guaranteed progress, it "works" without it. Under the hood the mechanism is still similar though, as opposed to something like chain replication.

Muzzaf 12y ago
See section 10 of the Raft paper. > VR uses a leaderbased approach with many similarities to Raft. > However, Raft has less mechanism that VR or ZooKeeper because it minimizes the functionality in non-leaders. For example, log entries in Raft flow in only one direction: outward from the leader in AppendEntries RPCs. In VR log entries flow in both directions (leaders can receive log entries during the election process); this results in additional mechanism and complexity > Raft has fewer message types than any other algorithm for consensus-based log replication that we are aware of. For example, we counted the message types VR and ZooKeeper use for basic consensus and membership changes (excluding log compaction and client interaction, as these are nearly independent of the algorithms). VR and ZooKeeper each define 10 different message types, while Raft has only 4 message types (two RPC requests and their responses).

blutoot 12y ago

This maybe a bit off-topic but I fail to understand why the top 2 textbooks on Distributed Computing - Tanenbaum and Coulouris - don't have a dedicated section on Consensus Algorithms. I learned distributed computing from Tanenbaum and can't recall encountering it. Contrary some of the folks here, I found the presentation very cool. But that maybe because I'm a slow learner.

tigeba 12y ago
You may want to check out "Reliable and Secure Distributed Programming", it has a few chapters on Consensus.

pepijndevos 12y ago

In the example with 5 nodes and a split, it is my understanding that the two nodes can't elect a leader. While the candidate in the smaller split receives votes from a majority of the split, there is no true majority, so no leader. The cluster is configured with the total number of nodes. What could happen is that an already elected leader continues to think it's the leader for a while while the rest fo the cluster elects a new leader. The split leader will however fail to commit its log, and throw them away once it rejoins. Another important detail that's missing is that node only votes once pere term, and only for a node that has an equal or higher term than itself. It will never vote twice or vote for an outdated node. Changing the configuration is in fact handled in a special way at the end of the raft paper in a way that avoids split-brain. [edit] Oh, the 2-node split was in fact already the leader, so it does exactly what I described. Dur...

rwinn 12y ago

So what happens if a network partition occurs where both sides can elect a new leader?

pepijndevos 12y ago
This can't happen. You can't devide a cluster in half and still have a majority. See my other post.
- rwinn 12y ago
  Ah, ok so all nodes needs to be known beforehand
  - knyt 12y ago
    Yeah, and any changes to the set of nodes (adding or removing a node from the cluster) must be agreed upon by a majority of the existing nodes.
Muzzaf 12y ago
At most one side can elect a new leader, since there are an odd number of nodes.

fiatjaf 12y ago

How do you do these animations?

pit 12y ago

Holy cow: social media is a means for distributing consensus.

EGreg 12y ago

Sex.