Raft Visualization(thesecretlivesofdata.com)
thesecretlivesofdata.com
Raft Visualization
http://thesecretlivesofdata.com/raft/
36 comments
Well, just two weeks ago I was searching for a quick intro on how Raft works, because I heard it several times over the years, but never took the time to see how it actually works. I didn't really find something to digest quickly until I saw your page. Great work and thank you!
It really is super handy to see what was being described in the paper! Curiously I posted this about a year ago and it didn't make the front page.
The internet is a fickle place...
The internet is a fickle place...
this was super helpful for me when I was trying to understand the related paxos algorithms, thanks so much for making this!
MIT online trainig has this great YouTube playlist on distributed systems, with one of the lectures being on RAFT [1,2,3]. The entire playlist [4] is probably worth your time, though.
[1] Intro https://www.youtube.com/watch?v=UzzcUS2OHqo
[2] Part I: https://www.youtube.com/watch?v=64Zp3tzNbpE
[3] Part II https://www.youtube.com/watch?v=4r8Mz3MMivY
[4] Playlist for the course: https://www.youtube.com/watch?v=cQP8WApzIQQ&list=PLrw6a1wE39...
[1] Intro https://www.youtube.com/watch?v=UzzcUS2OHqo
[2] Part I: https://www.youtube.com/watch?v=64Zp3tzNbpE
[3] Part II https://www.youtube.com/watch?v=4r8Mz3MMivY
[4] Playlist for the course: https://www.youtube.com/watch?v=cQP8WApzIQQ&list=PLrw6a1wE39...
I don't have any particular use for this right now but the visualization is so good that I actually followed along and get what it's about. Pretty obvious to say but it's super cool and I wish more projects had this kind of quick intro/overview.
Same! Raft is something I've heard about for years and always "wanted to get around to" learn, but this visualization just took care of most of that. Hoping there are other good visualizations like this in the future.
This visualization is very good. But the Raft paper itself is also quite understandable (and I say this as someone without any formal CS background who struggles getting through papers). It's main goal, aside from correctness, was understandability after all.
https://web.stanford.edu/~ouster/cgi-bin/papers/raft-atc14
I'd estimate it took me about 2 hours to get through it, but it felt very satisfying because I walked away saying "yup, I see how this works now". Give it a shot!
https://web.stanford.edu/~ouster/cgi-bin/papers/raft-atc14
I'd estimate it took me about 2 hours to get through it, but it felt very satisfying because I walked away saying "yup, I see how this works now". Give it a shot!
I see from elsewhere in the thread that this was a painstaking/manual effort and leverages D3.
Does anyone know if there are projects/libraries to help build this kind of visualization more generically? I realize that no library could every cover every possible use case, but I'd love some kind of framework that makes it easy to build out this kind of thing.
Reveal [1] is great for a web-based slideshow, but I'd love something that helps explain complex systems, even if that requires me to do some heavy lifting.
[1] https://revealjs.com/
Does anyone know if there are projects/libraries to help build this kind of visualization more generically? I realize that no library could every cover every possible use case, but I'd love some kind of framework that makes it easy to build out this kind of thing.
Reveal [1] is great for a web-based slideshow, but I'd love something that helps explain complex systems, even if that requires me to do some heavy lifting.
[1] https://revealjs.com/
I'd appreciate it if that presentation UI allowed to go back a step.
Pressing the left cursor seems to work.
Edit: sometimes
Edit: sometimes
Yeah, same thought here. That'd definitely be a majorly useful UI improvement. :)
Turns out this was requested about two years ago, and hasn't been responded to by the developers. :(
https://github.com/benbjohnson/thesecretlivesofdata/issues/2...
Looking at the project commit history, although there was a minor commit (changing a URL) in 2020, the newest commit before that was 2014.
Seems like a dead project. Oh well, the idea was good. :)
Turns out this was requested about two years ago, and hasn't been responded to by the developers. :(
https://github.com/benbjohnson/thesecretlivesofdata/issues/2...
Looking at the project commit history, although there was a minor commit (changing a URL) in 2020, the newest commit before that was 2014.
Seems like a dead project. Oh well, the idea was good. :)
What are of the shelve solutions when it comes to actually using these protocols? Implementing these in-house doesn't make sense to me.
`etcd` is probably the canonical off-the-shelf solution. Other implementations are listed here https://raft.github.io/#implementations
Consul[0] and Nomad [1] by HashiCorp both use raft.
[0] https://consul.io
[1] https://nomadproject.io
[0] https://consul.io
[1] https://nomadproject.io
As does RabbitMQ, Docker Swarm, AlertManager (prometheus addon).
If you run any of these systems in production, it is good to have a cursory understanding.
If you run any of these systems in production, it is good to have a cursory understanding.
YugabyteDB https://blog.yugabyte.com/how-does-the-raft-consensus-based-...
And CockroachDB both use raft consensus https://www.cockroachlabs.com/docs/stable/architecture/repli...
And CockroachDB both use raft consensus https://www.cockroachlabs.com/docs/stable/architecture/repli...
If you want a library and not a fully-fledged raft-backed KV daemon/service, there's also dragonboat [1].
[1] - https://github.com/lni/dragonboat
[1] - https://github.com/lni/dragonboat
I can only recommend the 'Distributed systems for fun and profit' book as a follow up to this neat visualisation.
http://book.mixu.net/distsys/
http://book.mixu.net/distsys/
How does Raft handle the scenario where there’s a network split, Client One updates a value on the majority, and then Client Two attempts to read the value from the minority side?
I'll assume by "majority/minority" you mean a network partition where at least half plus one nodes are still able to elect a leader, while the remainder are not.
In vanilla Raft, reads are appended to the Raft log like writes are. This means in order to commit a write, the client and the leader on the "majority" side will update the value as normal. The second client will either be unable to find a leader to contact at all, or if it is connected to an old leader, the leader will not be able to replicate the log entry necessary to service the read from the second client.
There are lease optimizations that rely on bounded clock error that allow for performing reads from the leader without appending entries to the log. Note this relies on the rate at which the clock advances, not the actual time.
There are also optimizations from Paxos research that would allow reading from the followers, but those also require contacting the leader at minimum.
In summary, Client One will succeed and Client Two will fail.
In vanilla Raft, reads are appended to the Raft log like writes are. This means in order to commit a write, the client and the leader on the "majority" side will update the value as normal. The second client will either be unable to find a leader to contact at all, or if it is connected to an old leader, the leader will not be able to replicate the log entry necessary to service the read from the second client.
There are lease optimizations that rely on bounded clock error that allow for performing reads from the leader without appending entries to the log. Note this relies on the rate at which the clock advances, not the actual time.
There are also optimizations from Paxos research that would allow reading from the followers, but those also require contacting the leader at minimum.
In summary, Client One will succeed and Client Two will fail.
Then client two can't read the new value until a least one node of the minority side can connect to the majority. Also client two can't update anything.
I would have killed for this in my advanced distributed systems class in university..
Why RAFT is better? In other words, why do we need a concept of a leader?
Consistent hashing is a routing algorithm, not a consensus algorithm.
https://en.wikipedia.org/wiki/Consistent_hashing
https://en.wikipedia.org/wiki/Consistent_hashing
Barring some very advanced systems a leader is needed to allow for Serializability https://en.wikipedia.org/wiki/Serializability
> Barring some very advanced systems
you mean atomic clocks as in spanner?
you mean atomic clocks as in spanner?
Yeah google's True Time system pretty much is the only one I know of.
https://cloud.google.com/spanner/docs/true-time-external-con...
https://cloud.google.com/spanner/docs/true-time-external-con...
[deleted]
Basically if you want to replicate data across multiple nodes, all of them need to agree on the sequence of data updates. For example if I did [x=6, x=7], then the outcome of those ops is very different if I did it in the opposite order [x=7, x=6]. Easiest way to do this sequencing is to have a unique leader who will impose the unique order. Strict sequencing is not really serializability, but linearizability. For example, Cassandra doesn't by default have the concept of a leader and hence can't provide linearizability. Of course, there is a problem on how you decide who is the leader and what happens if two nodes think they are the leader at the same time. That's where the genius of Multi-Paxos/Raft comes in. You can read more about sequencing here
https://medium.com/swlh/replication-and-linearizability-in-d...
https://medium.com/swlh/replication-and-linearizability-in-d...
Very useful for understanding the protocol including edge cases.
So Raft is single leader but Paxos is leaderless?
Raft should be compared performance-wise to multi-paxos, (which also has a leader)
Yes, just to add:
Raft is essentially Multi-Paxos under the hood, with some overstrict invariants that can impact availability and latency. If you need a consensus algorithm, then it's worth doing a survey of the literature beyond Raft.
Other Multi-Paxos variants are Viewstamped Replication Revisited, which has deterministic leader election for lower latency in the common case and thus no issue of split votes, and which I personally find easier to understand than Raft, also making less demands of the underlying hardware (i.e. VRR can do in-memory leader election, so you're safe in the event of disk failure, corruption, lost writes, and misdirected writes, which Raft does not deal with).
For all these Multi-Paxos variants, you can also look at Flexible Paxos, which is a simple technique for making leader election quorums slightly more expensive (since leader elections are infrequent) in order to make replication quorums much cheaper (since they are the common case critical path). You can use Flexible Paxos to save 20% in the number of hardware nodes for the same common case failure tolerance. Flexible Paxos is a game changer.
Raft is essentially Multi-Paxos under the hood, with some overstrict invariants that can impact availability and latency. If you need a consensus algorithm, then it's worth doing a survey of the literature beyond Raft.
Other Multi-Paxos variants are Viewstamped Replication Revisited, which has deterministic leader election for lower latency in the common case and thus no issue of split votes, and which I personally find easier to understand than Raft, also making less demands of the underlying hardware (i.e. VRR can do in-memory leader election, so you're safe in the event of disk failure, corruption, lost writes, and misdirected writes, which Raft does not deal with).
For all these Multi-Paxos variants, you can also look at Flexible Paxos, which is a simple technique for making leader election quorums slightly more expensive (since leader elections are infrequent) in order to make replication quorums much cheaper (since they are the common case critical path). You can use Flexible Paxos to save 20% in the number of hardware nodes for the same common case failure tolerance. Flexible Paxos is a game changer.
Unfortunately, the visualization project is effectively dead. The Raft visualization involved a lot of painful D3.js coding and effectively writing a JS Raft implementation. In hindsight, a deterministic format would be much easier. I toyed around with learning After Effects in hopes of producing some other visualization videos but I never did finish any.
I'm glad folks are still getting value out of the Raft visualization. The paper is good but it helps to see data move over time to really make it click.