Name: FOSDEM 2016: Why we choose the Raft consesus algorithm
Uploaded: 2016-10-08T18:36:41.000Z
Duration: 19 min 25 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

Next speaker is Robert and he will talk about how using the RAFT consenous algorithm helped him a lot

At the starts I would like to introduce myself. I'm Robert Wojciechowski, I work for Skylable, which is making a distributed storage system.

I'm wondering how many of you are system administrators here...

Yeah... I can see a lot of you are, so probably you faced an issue of having lots of...

Maybe not lots of but couple of servers with a lot of free space on them.

And you were wondering what to do with that space.

I started thinking about this situation at once and I thought that I could built my own distributed storage cluster.

Because why not? I have a lot of free space. I could make some good use of it.

And I could also have cluster which will be S3 compatible.

That would give me some additional freedom of usage.

My goals were to build a cluster which would be first of all free for me and I would not have to spent lots of time on maintaining this.

I asked you how many of you are system administrators and I'm not.

And for me ease of use is one of the most important goals because I really wanted to...

To just setup the configuration and to be able to store my data there.

One of the requirements was to be fault tolerant. I used to store my backups on those servers.

And I really wanted them to be distributed on my behalf.

And they would be replicated so my data should be safe there.

After looking at some possible solutions there were couple of them... but I've got interested in Skylable SX distributed storage

Which is GPL licenced solution for the people like me.

And it is also... It also supports S3 compatibility with LibreS3 layer.

And this solution seems to me very nice because I was reading a little bit about it and it stand out that this supports couple of nice features like...

...block level deduplication which would be... well I was thinking that it would be nice for me to have this deduplication because I store a lots of data

Which can usually be deduplicated, so why shall I spend a lot of time on sending data which is already there.

Besides the deduplication it is of course scalable which means that you can easily add or remove nodes to the cluster...

...on your demand and you don't have to disable it, turn it off or anything else.

And it is also a multiplatform solution which you can easily install on any UNIX based systems.

Well... I had a scalability but there was I would really  appreciate...

The software supported data replication and distribution of the blocks so they are equally distributed between nodes of the cluster.

And already software supported administrator tools  from the Command Line interface.

Which allowed me to... disable nodes which I would now that they are failed.

This routine needs to be done by an admin which is called a set-faulty function.

And it enables you to inform the cluster that some of the data may not be available. So when you have enough replicas of your blocks...

And you know that one of the nodes or more of them are dead basically, because some power outage or something...

You can inform the life nodes that the data should not be send to them and retrieved from those nodes.

As I said there was missing feature of automatic failover...

The cluster was able to deal with failed nodes only when I told him to do it.

I started thinking what could be done to improve this software and to make it aware of automatic failover.

What was needed for me was the ability for the cluster members - the nodes to detect the situation of failure.

In order to detect the situation of faulire I needed some leader node which would perform the operations I previously had to do from the CLI interface as an admin.

The leader node should do this task on my behalf... also the leader node should be the one which would be respected as making a decision.

All the alive nodes, all the rest of the nodes should followed this decision made by  this leader node.

So the... conclusion was that I definitely needed a consensus algorithm.

The software was at that state that it did not supported that...

Well the consensus algorithm is basically designed to handle the exact situations I had.

When you have failure condition, when you need some internal decision to be made automatically...

You definitely need a consensus algorithm.

So I started looking at possibilities and basically I...

...started looking at two of them which were the most commonly returned from possible algorithms.

The first was PAXOS, which is probably the one of the most known algorithms.

It is a provent work... let say... very complicated algorithm to implement. There are many of implementations of it.

But it turns out that many of them also has to be somehow adjusted to the working environment...

Well... there was existing some software that I could probably use but also I didn't want to include too much to the existing software.

But I started also looking at the RAFT algorithm, and RAFT algorithm was basically designed to be easier version of PAXOS... easier to implement.

So why not taking a look at this specification when it told that it is easy.

And it turn out that I should be able to do it... why not to try?

I started reading and now I'm going to tell you a little basics on how does it work and what stuff I needed from it...

So first thing I needed was the leader election.

As I said in the beginning the software itself did not has a concept of master and slave nodes or leader and follower as you call them.

So... this is the first situation I had to face...

Basically every node... each node is equal to each other. They have follower role which means that all they should obey the leader node commands...

At least one of them will at some point... just time out.

The time out, which is called election time out is a time after which some nodes should start thinking that something is wrong...

When the node times out, it starts a routine called - election basically

When the election starts, the node which timed out changes it's role as a candidate. When node is a candidate...

It starts sending request vote queries. Request vote queries are just simple... queries that contains the ID of the sender...

...which can be saved on the follower nodes, which means that when a follower nodes receives a request vote query...

...It save the number or ID of the node which send the request vote query.

So that is pretty simple and... that mark is needed for the nodes to avoid voting for other nodes.

So when there are couple of voting nodes in the cluster...

Follower nodes can only vote for one at a time and it is also... a part of the algorithm that candidate note votes for itself so...

...In one election candidate node receives at least one vote.

And the final state of this voting is that... candidate received 3 votes.

3 votes are more then half of the nodes in the cluster.

In this simple case there are 3 clusters so it had to get 2 votes out of 3... so the situation is simple.

Node number 2 becomes a variable leader now.

When it becomes a leader it has to immediately send heartbeat queries.

Heartbeat queries are just the simple ping like queries which are meant to reset time outs on the follower nodes.

Effectively stopping them of being timed out... then while the node is sending heartbeat queries to all the nodes...