Trois qualités attendues

• Fiabilité : fonctionner correctement même quand quelque chose va mal
• Scalabilité : un moyen raisonnable de faire face à plus de charge
• Maintenabilité : d’autres que vous peuvent le comprendre et le réparer

Opérationnel ou analytique ?

Pourquoi l’analytique stocke en colonnes

• Une table de 100 colonnes ; la requête n’en lit que 2
• Stockage par lignes : on lit les 100 colonnes de chaque ligne
• Stockage par colonnes : on ne lit que les 2 utiles
• Bonus : une colonne se compresse très bien

Latence et débit

• Latence : le temps d’une opération, en millisecondes
• Débit : le nombre d’opérations par seconde

La moyenne ment

999 requêtes à 10 ms, une à 5 secondes :

$$\text{moyenne} = \frac{999 \times 10 + 1 \times 5000}{1000} \approx 15 \text{ ms}$$

Le tableau de bord est vert. Un utilisateur sur mille attend 5 secondes.

Les percentiles

• p50 (médiane) : la moitié des requêtes sont plus rapides
• p95 : 1 requête sur 20 est plus lente
• p99 : 1 sur 100
• p99,9 : 1 sur 1000, celle que regardent les grandes plateformes

def percentile(valeurs, p):
    """p entre 0 et 100. Renvoie le percentile p de la liste."""
    triees = sorted(valeurs)
    if not triees:
        return None
    indice = int(round((p / 100.0) * (len(triees) - 1)))
    return triees[indice]

Le parallélisme multiplie les lenteurs

Une page appelle 20 services et attend qu’ils aient tous répondu.

Chacun est lent 1 fois sur 100. La page est lente avec la probabilité :

$$1 - 0{,}99^{20} \approx 18\,\%$$

Plusieurs copies de la même donnée

1. Disponibilité : une machine tombe, une autre a la donnée
2. Lectures : dix copies servent dix fois plus de lectures
3. Proximité : une copie près de chaque utilisateur

Le modèle leader / suiveurs

• Le leader reçoit toutes les écritures
• Les suiveurs reçoivent son journal et l’appliquent
• Les lectures peuvent aller n’importe où

Le retard de réplication

Vous publiez un commentaire (écriture → leader). Vous rechargez la page (lecture → un suiveur en retard). Votre commentaire a disparu.

Si le leader tombe

Il faut en élire un autre : le basculement (failover).

• Comment être sûr qu’il est mort, et pas seulement lent ?
• Quel suiveur choisir ? Le plus à jour, mais comment le savoir ?
• Que faire des écritures pas encore transmises ? En général : perdues

Deux leaders à la fois

Trois machines : A (leader), B, C.

1. Le réseau qui relie A aux deux autres est coupé. A fonctionne toujours.
2. B et C ne reçoivent plus de signe de vie de A. Ils élisent B.
3. A n’a rien remarqué : il accepte toujours des écritures.
4. B, nouveau leader, accepte lui aussi des écritures, de l’autre côté.

Pourquoi c’est si grave

• Ce n’est pas une donnée perdue : c’est une donnée incohérente
• Le système a fait deux promesses incompatibles
• Aucun des deux historiques n’est « le bon »
• Cela ne se répare qu’à la main, après coup

Solution 1 : la majorité

Un leader n’agit que s’il est soutenu par plus de la moitié des machines.

• Une coupure crée deux groupes : au plus un a la majorité
• B et C : 2 sur 3, majorité : ils élisent B
• A : 1 sur 3, pas de majorité : il cesse d’écrire

Pourquoi des grappes impaires

Solution 2 : le numéro de mandat

• Chaque élection donne un numéro strictement plus grand (term, époque)
• Chaque écriture porte le numéro de son leader
• On refuse toute écriture d’un numéro plus petit que le plus grand vu

Solutions 3 et 4

Le bail (lease) : le leader ne l’est que 10 secondes, et doit renouveler son bail auprès de la majorité. Isolé, il s’arrête de lui-même. Suppose des horloges à peu près fiables : on le combine avec le mandat.

Abattre l’ancien leader : lui couper l’alimentation à distance avant de promouvoir le nouveau. Nom volontairement brutal : STONITH, Shoot The Other Node In The Head.

En pratique

On ne réécrit pas cela à la main : on le délègue.

• ZooKeeper, etcd : 3 ou 5 machines, un algorithme de consensus (Raft, Paxos, Zab) = majorité + mandat
• Les autres logiciels leur demandent « qui est le leader ? »
• HDFS : ZooKeeper désigne le NameNode actif
• Kafka : KRaft, sa propre version de Raft

Découper la donnée

• Réplication : la même donnée à plusieurs endroits
• Partitionnement (sharding) : des données différentes à des endroits différents

Par plage de clés

• A à F sur la machine 0, G à M sur la machine 1, …
• Avantage : « tous les clients en D » sur une seule machine
• Inconvénient : déséquilibre

Par hachage

$$\texttt{machine} = \texttt{hash(cle)} \bmod N$$

import hashlib

def partition(cle, nb_partitions):
    empreinte = hashlib.md5(cle.encode("utf-8")).hexdigest()
    return int(empreinte, 16) % nb_partitions

Ajouter une machine

10 000 clés, on passe de 10 à 11 machines (exercice 5.3, mesuré) :

Le point chaud reste possible

Même avec un hachage parfait, une clé très demandée sature une machine : le compte d’une célébrité.

Le signe de vie (heartbeat)

import time

INTERVALLE = 2.0        # un signal attendu toutes les 2 s
TOLERANCE  = 6.0        # mort si silence pendant 6 s

derniers_signaux = {}   # machine -> instant du dernier signal

def signal_recu(machine):
    derniers_signaux[machine] = time.perf_counter()

def machines_mortes():
    maintenant = time.perf_counter()
    return [m for m, t in derniers_signaux.items()
            if maintenant - t > TOLERANCE]

Le dilemme du délai

Exercice 5.4, mesuré : tolérance 3 s → 7 à 8 fausses alertes par minute ; 15 s → 0.

Impossible à coup sûr

Pourquoi elles survivent

• Listées dans les années 1990 chez Sun (Peter Deutsch, puis James Gosling)
• Ce sont les hypothèses que votre code fait sans le dire
• Sur 127.0.0.1, elles sont presque vraies : rien ne se perd, tout répond en 0,1 ms, rien ne change

Les idées fausses 1 à 4

Les idées fausses 5 à 8

À retenir

Deux horloges, deux usages

La réponse avant la question

• Le maître envoie une requête à 00,010 s à sa montre
• Le travailleur, qui retarde de 30 ms, répond à 00,005 s à la sienne
• On fusionne les journaux et on trie : la réponse précède la question

Les trois lettres

Une donnée répliquée sur plusieurs machines.

• C, Consistency, cohérence : toute lecture voit la dernière écriture, comme s’il n’y avait qu’une seule copie
• A, Availability, disponibilité : toute machine en marche répond, par une vraie réponse
• P, Partition tolerance : le système continue quand le réseau se coupe en groupes isolés

Le dilemme, sur un exemple

Le stock est sur deux machines, Paris et Lyon. Il reste un livre. Le lien Paris–Lyon est coupé.

Un client lyonnais veut l’acheter. Lyon ne peut pas savoir si Paris vient de le vendre.

« Deux sur trois » est trompeur

• On ne choisit pas d’avoir des coupures : elles arrivent
• Renoncer à P n’a pas de sens sur plusieurs machines

Qui choisit quoi ?

On choisit selon le coût d’une erreur.

• CP quand une réponse fausse coûte plus cher qu’un refus : solde bancaire, dernier exemplaire, siège de train, élection d’un leader. ZooKeeper, etcd : c’est la majorité vue plus haut.
• AP quand une réponse un peu périmée est acceptable : panier, compteur de « j’aime », fil d’actualité, DNS. Cassandra, DynamoDB.

HDFS : le système de fichiers de Hadoop

• Les fichiers sont découpés en blocs de 128 Mo : partitionnement
• Chaque bloc est copié 3 fois, sur des machines et des armoires différentes : réplication
• Un fichier de 1 Go = 8 blocs = 24 copies réparties

NameNode et DataNodes

• DataNodes : les nombreuses machines qui stockent les blocs. Elles ne connaissent pas les fichiers
• NameNode : une machine unique qui tient l’annuaire : quels fichiers, quels blocs, où sont les copies. Il ne stocke aucune donnée

HDFS et les pannes

• Chaque DataNode envoie un signe de vie toutes les 3 s
• Sans nouvelle pendant environ 10 minutes : déclaré mort, ses blocs sont recopiés ailleurs

Kafka : le journal distribué

• Des producteurs écrivent des messages, des consommateurs les lisent à leur rythme ; les messages restent stockés
• Un topic : un flux nommé de messages (commandes, clics)
• Chaque topic est découpé en partitions, sur plusieurs serveurs (brokers)
• Partition d’un message = hash(cle) % N. L’ordre n’est garanti qu’à l’intérieur d’une partition

Kafka : réplication et ISR

• Chaque partition a un leader et des suiveurs, souvent 3 copies
• ISR, In-Sync Replicas : les copies à jour avec le leader
• Un message peut n’être confirmé qu’une fois reçu par toute l’ISR
• Si le leader tombe, le nouveau est choisi dans l’ISR

Bien choisir une clé de partitionnement

Le champ qui décide sur quelle machine va chaque donnée. Très difficile à changer après coup.

1. Beaucoup de valeurs, bien plus que de partitions
2. Une charge répartie : aucune valeur ne domine
3. Ce qui se lit ensemble reste ensemble (et garde son ordre)

Bonnes et mauvaises clés

Les exercices

• 5.1 — Percentiles. Un serveur qui hoquette 2 % du temps : la moyenne ment, le p99 dit vrai, une page sur trois est lente.
• 5.2 — Équilibrage. Hachage contre première lettre, sur un vrai livre.
• 5.3 — Ajouter une machine. 90 % de clés déplacées, ou 10 %.
• 5.4 — Détecteur de pannes. Compter les fausses alertes selon le délai.
• 5.5 — Diagnostiquer. Quatre symptômes, quatre mécanismes.
• 5.6 — Majorité et CAP. Sur papier : grappes, mandats, choix CP ou AP.

Ce qu’il faut retenir

• On mesure en percentiles, jamais en moyenne
• Répliquer = même donnée ; partitionner = données différentes
• Split brain : on l’empêche par la majorité et le mandat
• hashlib, jamais hash() ; hash % N déplace presque tout
• « Mort » ou « lent » : indiscernable. Le délai est un compromis
• Huit idées fausses : vraies en local, fausses en réseau
• time.time() pour dater, perf_counter() pour chronométrer
• CAP : pendant une coupure, cohérence ou disponibilité
• HDFS : blocs × 3, NameNode = annuaire. Kafka : partitions, ISR