# Plan
# Pourquoi raft
# Comment ça fonctionne
# Avantages/Inconvénient
=============================================================================
### Pourquoi raft ?

La plupart des algorithmes à consensus sont basés sur **Paxos** mais c'est un algo **compliqué** et **difficilement implémentables** par des développeurs.
Raft développé comme successeur du **Paxos**.

Raft :
- Pensé pour être facilement **compréhensible**
- Pensé pour être **intuitif** afin de **faciliter son implémentation**.

Contrairement à Paxos, Raft scinde les gros problèmes en petit problèmes plus simple à résoudre

## Comment ça fonctionne?
### Noeuds

2 types de système multi-noeud :
* Symétrique : chaque noeud peut répondre
* Asymmetric : Seuls les noeuds élus

Raft, asymétrique.

Chaque noeud du serveur possède 3 états :

- Leader
- Candidat
- Follower

Leader -> Répond au client, les autres se synchronisent avec.

Candidat -> Possibilité de demander aux autres noeuds de se faire élire en tant que Leader.

Follower -> Ne répond que au leader ou aux candidats, si des requêtes clientes lui arrivent, elles sont transmises au leader.

## Système de temps

L'algorithme divise le temps en plusieurs **mandats**. Chaque mandat est identifié par un numéro qui augmente à chaque nouvelle élection, on appelle ça **term number**

Le term number est **maintenu par chaque noeuds** et les noeuds passent leurs term number grâce aux **communications**.

Il est possible qu'un mandat commence et se termine sans élire de leader, quand le vote n'obtient pas la majorité. on appelle ça **split vote**.

Les nodes mettent à jour leurs term number si elles reçoivent un term number plus élevé.
Ils changent également leurs états en fonction du term number (Si Leader reçoit un term number plus élevé, il passe en follower)

Les requêtes possédant un term number inférieur sont automatiquement rejetées.

## Communications

Raft utilise deux types de communications

- **RequestVotes** : envoyés par les noeuds Candidats pour recueillir des votes.

- **AppendEntries** envoyés par le noeud Leader pour mettre à jour les commandes des autres noeuds. Sert aussi de ping pour vérifier si le noeud est encore up ou down.

## Election du leader

Une nouvelle élection a lieu quand un noeud Follower attend depuis trop longtemps un ping du noeud Leader. (timeout)

Le noeud Follower, passe en état candidat, vote pour lui même et envoie des messages de types RequestVotes pour recueillir des votes.

L'élection peut aboutir en 3 cas :
- Le candidat reçoit la majorité des votes, il devient leader et commence à envoyer des pings.
- Le candidat ne reçoit pas la majorité et le mandat se termine sans Leader. Le candidat retourne à l'état Follower.
- Le term number du candidat qui envoie les requêtes est inférieur à un autre candidat, ses requêtes sont rejetées.

### Les timeouts sont aléatoires
Afin d'éviter le phénomène de **split vote**, Raft utilise des durées de timeout aléatoires entre les serveurs.

A chaque élection, chaque noeud pioche un timeout aléatoire entre 150-300ms.

Cela permet de n'avoir qu'un seul noeud en timeout et lui laisse le temps de récupérer les votes des autres noeuds avant qu'un second passe en timeout.

## Log Replication

Les requêtes clientes sont effectuées sur le noeud Leader, stockées sous forme de logs,puis le leader va répliquer ces logs aux noeuds Followers.

Format d'un log :
- Commande cliente
- Numéro d'index
- Term number

Lorsqu'il reçoit une requête, le leader transmet le log jusqu'à confirmation de la copie par les followers.

Le leader après avoir reçu les confirmations, confirme que la réplication est terminée dans son journal de log, exécute la commande et répond au client.
Les requêtes sont exécutées dans l'ordre de réception.

Pour éviter les incohérences entre les journaux de logs (crash du Leader), le noeud Leader force les Followers à se synchroniser avec son journal.

Il match le dernier index en commun entre son journal et celui des followers, et écrase les index plus grands(si il en existe) avec les nouvelles requêtes du leader.

## Safety
à voir si on en parle

## Cluster membership and Joint Consensus

Le changement d'autorité est suceptible de rendre le cluster vulnérable, donc Raft passe par un état intermédiaire "Joint Consensus" avant de confirmer le changement.

Cela permet de rendre le cluster disponible aux requêtes clientes pendant qu'il change de leader.

## Avantages de raft

Raft a été **prouvé sûr**, aussi **efficace** que les autres algorithmes et beaucoup plus **simple de compréhension**.

Raft est tolérant aux pannes car il continue de fonctionner tant que la majorité des noeuds sont fonctionnels

Raft utilise des mécanismes d'élection simple et rapide en garantissant l'élection d'un leader en maximum 2 termes et il est équitable car tous les noeuds peuvent devenir leader.

Il est utilisé par **beaucoup d'entreprises**(MongoDB, HashiCorp) et il existe plusieurs implémentations de Raft en **open-source**.