Partitionnement et réplication des données

Les trois chapitres précédents ont supposé les données accessibles, sans se demander où elles se trouvent. Cette question devient centrale dès que le volume dépasse ce qu'un disque contient, et sa réponse conditionne tout le reste : la façon dont un calcul se découpe, la vitesse à laquelle il lit, et ce qui se passe quand une machine s'arrête.

Trois façons de brancher du disque

La distinction qui compte n'est pas la marque du boîtier mais le niveau auquel le partage a lieu.

Ces trois modes partagent une limite : ils reposent sur un équipement, et cet équipement a une taille maximale, un prix qui croît plus vite que sa capacité, et une panne possible qui arrête tout ce qui en dépend.

Grossir, ou se multiplier

Le choix n'est pas une question de goût, mais de plafond et de prix. La mise à l'échelle verticale ne demande aucun changement au logiciel, et c'est son immense avantage. Elle rencontre deux murs : un plafond physique, puisque la plus grosse machine du marché existe, et un prix qui croît plus vite que la capacité, un serveur deux fois plus puissant coûtant nettement plus du double.

La mise à l'échelle horizontale n'a pas de plafond et emploie du matériel bon marché. Elle exige en revanche que le logiciel sache répartir, ce qui est exactement le sujet du chapitre précédent, et elle rend les pannes ordinaires : sur mille machines, il en tombe une chaque semaine.

La virtualisation se superpose souvent à cela sans la remplacer. Elle découpe une machine physique en plusieurs machines virtuelles, ce qui permet de mutualiser du matériel sous-employé, d'isoler des environnements et de déplacer une machine virtuelle d'un hôte à l'autre.

Le système de fichiers distribué

La séparation entre le catalogue et les données explique presque tout le comportement de ces systèmes. La lecture d'un fichier se déroule ainsi :

Le catalogue ne rend que des adresses. Les données, elles, passent directement du nœud qui les détient au client, sans jamais transiter par lui : c'est cette séparation qui permet à un seul service de cataloguer des pétaoctets sans en devenir le goulot d'étranglement. Les blocs suivants se lisent en même temps, sur d'autres nœuds.

Le débit vient du nombre de nœuds, pas de la vitesse d'un disque. Un disque lit à environ 200 mégaoctets par seconde. Cent nœuds lisant chacun un bloc différent au même moment délivrent 20 gigaoctets par seconde.

C'est la raison d'être de la découpe en blocs qui compte le plus : elle permet bien de ranger un fichier plus gros qu'aucun disque, mais elle sert surtout à le lire en parallèle. Un fichier stocké en un seul morceau sur un seul nœud n'irait pas plus vite que ce nœud.

Cela explique aussi pourquoi ces systèmes détestent les petits fichiers : chacun coûte deux entrées au catalogue et une ouverture à la lecture, sans rien ajouter au parallélisme. Leur prix se chiffre un peu plus bas.

Le prix des petits fichiers

Le catalogue garde toute l'arborescence en mémoire vive, pour répondre sans lire de disque : une entrée par fichier, une entrée par bloc, chacune de l'ordre de 150 octets. Ce chiffre est la règle d'usage des exploitants de HDFS, le système de fichiers distribué de l'écosystème Hadoop, et il se lit comme un ordre de grandeur, pas comme une mesure. Les emplacements des trois copies tiennent dans l'entrée du bloc : la réplication ne multiplie pas les entrées.

Dix téraoctets rangés en mille fichiers de 10 gigaoctets occupent 79 blocs par fichier, 78 pleins et un dernier de 16 mégaoctets : 79 000 entrées de blocs et 1 000 entrées de fichiers, soit 80 000 entrées et 12 mégaoctets de mémoire. Les mêmes dix téraoctets en fichiers de 100 kilo-octets font $10^{8}$ fichiers. Chacun tient dans un seul bloc, qui n'occupe sur le disque que ses 100 kilo-octets, mais qui compte pour une entrée en plus de celle du fichier : au moins $2 \times 10^{8}$ entrées, soit 30 gigaoctets de mémoire pour le seul catalogue. Les disques portent les mêmes 30 téraoctets avec trois copies ; la mémoire du catalogue a été multipliée par 2 500.

Le second coût est le temps. Ouvrir un fichier demande une question au catalogue, une connexion au nœud qui détient le bloc et un positionnement sur le disque : de l'ordre de 5 à 10 millisecondes, quelle que soit la taille du fichier. Un disque rapide, qui lit à 500 mégaoctets par seconde, lit un bloc de 128 mégaoctets en 256 millisecondes. Les mêmes 128 mégaoctets en 1 280 fichiers de 100 kilo-octets demandent 1 280 ouvertures : 6,4 secondes à 5 millisecondes l'une, 12,8 secondes à 10, avant même de lire. L'ouverture coûte alors vingt-cinq à cinquante fois la lecture, et ce coût ne dépend pas du débit : plus le disque est rapide, plus il pèse.

Le remède ne demande aucun matériel : regrouper les petits fichiers avant de les déposer, en archives ou en fichiers en colonnes de la taille d'un bloc ou plus. La place sur les disques ne change pas ; le catalogue et le temps d'ouverture retrouvent ceux des gros fichiers.

Qui va où : répartir par plages ou par hachage

Un système de fichiers distribué laisse son catalogue retenir l'emplacement de chaque bloc. Une base répartie range des lignes, bien trop nombreuses pour qu'un catalogue retienne l'emplacement de chacune : l'emplacement se calcule à partir de la clé, et il suffit de connaître la règle pour savoir où lire. C'est le partitionnement des données entre machines, et deux règles dominent.

Par plages : chaque machine reçoit un intervalle de clés consécutives, dont les bornes sont connues de tous. Une lecture qui parcourt un intervalle ne touche qu'une machine, ou quelques-unes.

Par hachage : l'empreinte de la clé, ramenée au nombre de machines, désigne la machine. Les clés se dispersent, et une lecture par intervalle doit interroger tout le monde.

Rangées par horodatage, les 18 000 écritures de la minute tombent sur la même machine, et les trois autres attendent : c'est un point chaud, le déséquilibre du chapitre précédent appliqué au stockage. Rangées par empreinte du capteur, elles se répartissent à peu près également, mais relire la minute oblige à interroger les quatre machines. Les lectures par capteur suivent la règle inverse : la journée d'un capteur tient sur une seule machine par hachage, et se disperse sur les quatre plages par horodatage. Aucune règle n'est meilleure dans l'absolu : la clé de répartition se choisit d'après les écritures et les lectures réellement faites, et le chapitre sur les familles NoSQL y revient avec les séries chronologiques.

Le hachage par modulo a un second défaut, qui se voit le jour où le cluster grandit. Passer de quatre à cinq machines change le reste de la division pour presque toutes les empreintes, et presque toutes les données doivent changer de machine. Le hachage cohérent l'évite : machines et clés sont placées sur un même cercle d'empreintes, chaque machine en plusieurs points, et chaque clé va à la machine du premier point qui la suit sur le cercle. Une machine ajoutée ne prend que les clés qui précèdent ses propres points.

Avec le modulo, l'ajout d'une cinquième machine déplace ici 228 clés sur 300, et la plupart d'entre elles passent d'une ancienne machine à une autre ancienne : presque tout le cluster se recopie pour gagner une machine. Avec le hachage cohérent, 60 clés bougent, environ une sur cinq, et toutes vont vers la nouvelle machine, ce qui est le minimum pour lui donner sa part.

Combien de copies, et pourquoi trois

Répliquer coûte : trois copies occupent trois fois la place. Le nombre de copies n'est donc pas un réglage de confort, mais un arbitrage qui se calcule.

Le système n'attend pas qu'une copie manque pour agir. Chaque nœud donne des nouvelles au catalogue toutes les trois secondes ; celui qui se tait une dizaine de minutes est déclaré mort, et chacun de ses blocs est recopié ailleurs à partir des copies restantes. Perdre un bloc demande donc que toutes ses copies disparaissent avant d'avoir été refaites, pendant une réparation de quelques minutes à quelques heures, et non au cours de la même année. Une machine seulement injoignable ne perd rien : ses blocs sont indisponibles un moment. Dans le calcul qui suit, p est la probabilité qu'une copie disparaisse pendant cette fenêtre.

De deux à trois copies, la perte attendue est divisée par $1/p$, soit par cent quand $p$ vaut 1 % et par dix quand il vaut 10 %, pour une place multipliée par 1,5. Le même calcul donnerait encore ce facteur de trois à quatre copies : il dit ce que chaque copie achète, pas où s'arrêter. Ce qui distingue trois de deux, c'est la marge pendant une réparation. Avec deux copies, un disque tombé laisse ses blocs sur une seule copie le temps de les refaire, et une deuxième panne à ce moment les perd ; avec trois, il en reste deux. Au-delà, ce sont les pannes corrélées qui dominent, et une copie de plus sur le même matériel ne les évite pas.

Répliquer n'est pas la seule technique.

Le codage à effacement tolère plus en occupant moins, et coûte du calcul. Un schéma 6+3 supporte la perte de trois fragments sur neuf en n'occupant qu'une fois et demie la taille des données, là où la réplication triple supporte deux pertes en occupant trois fois.

La contrepartie est le calcul : reconstituer un fragment perdu exige de lire les six autres et de refaire l'algèbre, alors qu'une réplication n'exige que de recopier. La lecture d'un fragment manquant devient donc coûteuse.

En pratique, les données récentes et souvent lues restent répliquées, et les données anciennes et rarement lues passent au codage à effacement. C'est le même arbitrage que partout : la place contre le temps.

Le stockage dans le cloud

Le cloud propose trois formes de stockage, qui correspondent aux trois niveaux vus plus haut.

Les couches d'une architecture de données

Les composants vus jusqu'ici s'organisent presque toujours de la même façon, quel que soit l'outillage retenu.

Cinq couches, et une règle par couche. Collecte. Les données entrent, par lots ou en continu, depuis des sources hétérogènes. Règle : ne rien transformer ici, sinon l'erreur de transformation devient irrattrapable.

Stockage brut. Les données sont conservées telles qu'arrivées, dans un espace peu structuré. Règle : garder l'original, toujours, parce qu'aucun besoin futur n'est connu aujourd'hui.

Traitement. Nettoyage, croisement, agrégation, avec les motifs des chapitres précédents. Règle : rendre chaque traitement rejouable à l'identique.

Stockage exploitable. Les données mises en forme pour l'usage, modélisées pour l'analyse. Règle : modéliser selon les questions posées, sujet du chapitre sur l'entrepôt.

Restitution. Requêtes, indicateurs, visualisations. Règle : la couche visible ne doit contenir aucun calcul métier que les couches précédentes ne sachent reproduire.

Deux mots reviennent pour désigner ces stockages, et ils ne sont pas interchangeables. Le data lake, ou lac de données, commence au stockage brut : tout y entre, sans schéma imposé, et le sens est donné à la lecture. Organisé en zones, il conserve aussi ce que produit le traitement : la zone brute est le stockage brut, la zone raffinée garde les données nettoyées, la zone exploitable les données mises en forme pour l'usage. Chaque zone s'ajoute aux précédentes sans les remplacer, puisque la règle du stockage brut est de garder l'original. L'entrepôt est un stockage exploitable dont le schéma est décidé avant l'écriture : ce qui n'y rentre pas n'y entre pas. Le chapitre sur l'entrepôt et le lac traite l'un et l'autre.

Mettre en pratique

La durabilité d'un stockage réparti n'est pas une impression, c'est un produit de probabilités. Et son prix n'est pas une impression non plus.

L'écart entre les deux dernières réponses est l'argument entier du codage à effacement : il double presque la capacité utile pour une durabilité comparable. Son prix est ailleurs, dans le calcul qu'exige la reconstruction d'un fragment perdu, qui mobilise plusieurs machines là où une copie se recopie sans rien calculer.