Dynamo: Amazon’s Highly Available Key-value Store

# Bonjour à tous,
vous pouvez également contribuer à ce pad : https://hackmd.io/JiYCXUWhTmSsL6WoIN3gFg?edit

[Lien de l'article ici !](https://moodle.imt-atlantique.fr/pluginfile.php/55770/mod_resource/content/4/amazon-dynamo-sosp2007.pdf)
* [sur ACM](https://dl.acm.org/doi/abs/10.1145/1323293.1294281)
* [sur google scholar](https://scholar.google.com/scholar?hl=fr&as_sdt=0%2C5&q=Dynamo%3A+Amazon%E2%80%99s+Highly+Available+Key-value+Store&btnG=)

**Nous aimerions avoir une prise de notes partagée !**
Vous pouvez consulter ce document en mode visualisation (l'oeil dans le menu), en mode édition (le crayon)

2 séances prévues - d'étude d'article
* une lecture préalable d'article scientifique
* une analyse approfondie

# Qui participe ?

* Jean-Marie Gilliot
* Antoine Beugnard
* Sylvain Thong
* Noé Loisil
* Ben Mustapha Riadh
* Tchadel Icard
* Charly Martin Avila
* Liam COURSODON
* Thibaud Couchet
* Zahdi Mohcine
* ZHU Xinlei
* Zhan NING
* ZHONG Junzhang

# Comment l'avez vous lu ?

* NotebookLM/ChatGPT : résumé, poser des questions
* Lecture longue - linéaire
* Lecture de l'abstract, l'intro, et finir par la conclusion pour avoir une idée générale.

# Pourquoi cet article mérite-t-il d'être lu ?

* Article de référence
* Amazon

# Qu'en avons-nous retenu ?

* Très grande disponibilité (99.9995%) plutôt que la cohérence
* Beaucoup de justifications avec des exemples concrèts de cas d'utilisateurs
* Approche quantitative

# Quel est l’objectif de l’article ?

* Prouver que notre solution est pérenne/solide, apte à être déployée en production

# Quelle est la motivation de l'article ?

* Acheter AWS ! $$$
* Attirer les ingénieurs/chercheurs brillants

# Structure de l'article

1) Abstract (Résumé)
2) Introduction
3) Contexte/background
a) Besoins utilisateurs
b) Propriétés ACID
c) Qualité de service
3) Related work (solutions existantes/l'état de l'art)
4) Architecture (éléments de solution)
5) Implémentation (mise en oeuvre)
6) Expériences and lessons learned (limites)
7) Conclusion

# Solution générale proposée
* Dynamo - base de données clé-valeur
* Anneau
* Passage à l'échelle
* Réplication (tolérance aux fautes)
* Performance (réponse rapide)
* Disponibilité
* Gestion des versions

# Algorithmes identifiés

* Consistent hashing
* Gossip
* Vector clocks
* Sloppy quorum

# Présentations...
* 4.1 à 4.3 : Junzhang, Charly Martin Avila, Zhan Ning, Liam
* 4.4 & 4.5 : Sylvain, Mohcine, Riadh, Xinlei (il n'y a plus de place tant pis pour vous)
* 4.6 à 4.9 : Tchadel Icard, Thibaud Couchet, Yongshun JIAO, Noé Loisil

en 15 minutes : présenter la partie en reliant avec les éléments de validation

# Notes présentation 1

## 4.1 Interface
- get(key)
- put(key, context, value)

## 4.2 Consistent hashing
- Chaque noeud est responsable des noeuds qui le précèdent
- La répartition de charge n'est pas uniforme
- Noeuds virtuels pour mieux répartir la charge et ne pas avoir à redistribuer toutes les clés : faciliter l'ajout des noeuds

## 4.3 Réplication
Deux enjeux :
- Haute disponibilité
- Haute durabilité

Utilisation d'une liste de préférence qui stocke la liste des noeuds sur lesquels répliquer les données afin de pouvoir récupérer celle-ci en cas de panne : elle est de taille N

Trois variables tunnables :
- N : Cohérence
- R : Performance
- W : Disponibilité

# Notes présentation 2
Euh ?
ah ouais d'accord super sympa les gens

# Notes présentation 3

## 4.6 Gestion des erreurs/pannes temporaires
Une propriété assurant le quorum telle que R+W>N n'est pas résistante à d'éventuelles pannes de certains noeuds ou de problèmes réseaux.
Deux idées :
- sloppy quorum : priorité aux noeuds vivants
- hinted handoff : ??

## 4.7 Gestion des pannes permanentes
Le hinted handoff est pertinent dans le cas de noeud qui sont indisponibles temporairement mais celle-ci pose problème si des noeuds tombent en panne de manière permanente.
Deux solutions :
- Protocole anti-entropie
- Utilisation d'arbres de Merkle (parents qui contiennent les condensés de leurs enfants, les feuilles contiennent les condensés des valeurs des clés individuels)
==> Racines identiques = pas de problème de synchronisation
==> Racines différentes : identification des branches divergentes, échange des clés spécifiques pour synchronisation

## 4.8.1 Ring membership
- Possibilité d'ajouter/retirer des noeuds
- Propagation des changements par protocole gossip
- ???

## 4.8.2 External discovery
Le protocole gossip peut créer temporairement des partitions logiques dans l'anneau dynamo
==> seed nodes pour valider et synchroniser les infos

## 4.8.3 Détection de pannes
Détecter effectivement les noeuds permet d'éviter des tentatives de communication inutiles et de ne pas rester bloqué sur une éventuelle interruption de service
==> Détection locale ==> Pas besoin d'une vision globale

## 4.8 Validation
Résultats :
- Haute disponibilité (99,9995%)
- Cohérence à terme
- Scalabilité et flexiblité opérationnelle

## 4.9 Ajout/Suppression d'un noeud de stockage
- Il faut répondre à de multiples critères lors de l'ajout des noeuds : garantir une distribution équitable de données après ajout et rejet, simplicité de cette opération, confirmation de la complétude de l'opération.

je vais pas écrire tout seul hein :angry: R+W > N?