Quand une donnée devient grosse
Ce que ce chapitre apporte
- Distinguer les trois murs que rencontre un traitement de données : la mémoire, le stockage, le débit.
- Mesurer le coût réel d'une opération plutôt que le supposer.
- Reconnaître le passage d'un coût linéaire à un coût qui ne l'est plus.
- Repérer l'accident de conception qui transforme un traitement d'une seconde en un traitement d'une heure.
- Interpréter les cinq V, et dire ce qu'ils décrivent bien et ce qu'ils n'orientent pas.
Il n'existe aucun seuil en gigaoctets. Une donnée devient grosse le jour où une opération qui marchait cesse de marcher, et ce jour-là dépend de l'opération bien plus que du volume. Trois murs différents attendent, à trois endroits différents, et chacun appelle un remède qui ne soigne pas les deux autres. Les confondre fait acheter des machines pour un problème d'algorithme.
Un fichier de trois gigaoctets se lit sans difficulté sur un ordinateur portable si l'on se contente d'en compter les lignes. Le même fichier fait tomber la même machine si l'on veut trier son contenu. Rien n'a changé dans les données : ce qui a changé, c'est ce qu'on leur demande.
C'est pourquoi la question « à partir de quelle taille parle-t-on de grandes données ? » n'a pas de réponse, et pourquoi il faut la remplacer par une autre : quelle opération, sur quelle machine, cesse de tenir ses promesses, et pourquoi. Ce chapitre pose cette question et donne de quoi y répondre par la mesure plutôt que par l'intuition.
Trois murs, trois remèdes
La mémoire vive. Le traitement charge tout en mémoire, et la mémoire est pleine. Le programme s'arrête net, ou se met à échanger avec le disque et devient mille fois plus lent. Remède : ne plus tout charger, donc traiter en flux.
Le stockage. Les données ne tiennent plus sur un disque, ou plus sur une machine. Remède : les répartir sur plusieurs machines, ce qui pose aussitôt la question de savoir lesquelles vont où.
Le débit. Les données arrivent plus vite qu'on ne les traite. Le retard s'accumule, et rien ne le rattrapera puisque le flux ne s'arrête pas. Remède : traiter en parallèle, ou traiter moins.
Ces trois murs sont indépendants. Un capteur qui produit cent mesures par seconde ne posera jamais de problème de stockage, et posera un problème de débit dès que le traitement de chaque mesure dépassera dix millisecondes. Un historique de dix ans tient sur un disque de bureau et fait exploser la mémoire au premier tri.
Le mur de la mémoire prévient : le programme s'arrête avec une erreur claire. Le mur du débit prévient aussi : la file d'attente grandit sous les yeux de tout le monde.
Le troisième cas ne prévient pas. Un traitement dont le coût croît plus vite que les données continue de fonctionner, de plus en plus lentement, sans jamais rien signaler. Il passe les essais sur un échantillon, il passe la recette sur un jeu réduit, et il tombe le jour où le volume réel arrive. C'est le sujet de la deuxième moitié de ce chapitre.
Mesurer plutôt que supposer
Une liste de un million d'entiers en Python, cela pèse combien, et cela coûte combien à parcourir ? La réponse ne s'estime pas : elle se mesure.
Deux enseignements, et le second compte plus que le premier.
Le poids réel dépasse largement ce que sys.getsizeof annonce, parce que la liste ne contient pas les nombres mais des références vers eux. Un million d'entiers Python occupe une trentaine de mégaoctets, là où le même million d'entiers dans un tableau numpy en occuperait huit. Le facteur quatre n'est pas anecdotique quand la mémoire est la contrainte qui saute.
Surtout, le temps de la somme croît comme le nombre de valeurs. Dix fois plus de données, dix fois plus de temps. C'est la propriété la plus précieuse qu'un traitement puisse avoir, et le chapitre suivant est consacré à la préserver.
Un traitement a un coût linéaire quand doubler la quantité de données double le temps de traitement, sans plus. On l'écrit O(n).
C'est la limite au-delà de laquelle un traitement cesse de passer à l'échelle : à coût linéaire, un volume mille fois plus grand demande mille fois plus de temps, ce qui est déjà beaucoup mais reste prévisible et se répartit sur plusieurs machines. Au-delà, la répartition elle-même ne suffit plus.
Où le coût cesse d'être linéaire
Compter, sommer et chercher un maximum coûtent linéaire. Trier ne le fait pas, et la différence se voit dès que les tailles grandissent.
Le rapport d'un palier au suivant tourne autour de deux pour le tri, et le dépasse un peu. C'est la signature de n log n : plus cher que linéaire, mais de très peu, et parfaitement utilisable jusqu'à des volumes considérables. La somme, elle, double franchement.
Le code retient le meilleur de plusieurs essais et non leur moyenne. Une mesure peut être ralentie par n'importe quoi d'extérieur au programme, jamais accélérée : le minimum est donc l'estimation la moins polluée du coût réel. Sans cette précaution, les rapports observés sautent d'un palier à l'autre et ne veulent plus rien dire.
Nul besoin de savoir démontrer une complexité pour la reconnaître. Doubler la taille et regarder le rapport des temps suffit :
- rapport 2 : coût linéaire, tout va bien ;
- rapport un peu plus de 2 : n log n, c'est le tri, c'est acceptable ;
- rapport 4 : coût quadratique, et le traitement ne passera pas à l'échelle ;
- rapport 8 : coût cubique, il faut changer d'algorithme, pas de machine.
Cette mesure prend quelques minutes et évite des semaines d'optimisation au mauvais endroit.
L'accident qui multiplie tout par mille
Le tri est cher et se voit. L'accident qui suit ne se voit pas, et il est de très loin la première cause de traitements qui ne finissent pas.
Les deux boucles sont écrites de la même façon, produisent le même résultat, et diffèrent d'un mot : list contre set. Le rapport de temps se compte en centaines, et le bloc l'affiche : c'est très exactement le nombre de comparaisons évitées à chaque test d'appartenance.
x in liste parcourt la liste jusqu'à trouver, donc coûte proportionnellement à sa longueur. Placé dans une boucle sur les données, il transforme un traitement linéaire en traitement quadratique.
Sur un échantillon de mille lignes contre une référence de mille lignes, cela fait un million de comparaisons : personne ne remarque rien. Sur un million de lignes contre un million de lignes, cela fait mille milliards de comparaisons, et le traitement ne finira pas.
x in ensemble et x in dictionnaire répondent en temps constant, quelle que soit la taille. La correction tient en un mot, encore faut-il savoir le chercher.
Le même piège se déguise sous d'autres formes. Concaténer dans une boucle avec chaine = chaine + morceau recopie toute la chaîne à chaque tour. Insérer en tête d'une liste avec insert(0, x) décale tout le contenu. Rechercher une correspondance entre deux fichiers avec deux boucles imbriquées revient au même calcul que le in ci-dessus, en plus visible.
Un traitement quadratique est déjà faux sur mille lignes : il fait un million d'opérations là où mille auraient suffi. Simplement, un million d'opérations prend quelques millisecondes et personne ne s'en aperçoit.
Les grandes données ne créent donc pas les problèmes de conception. Elles les rendent visibles, et souvent au pire moment. C'est une raison suffisante pour mesurer les coûts avant que le volume n'arrive.
Le débit, un mur d'une autre nature
Les deux premières sections traitent d'un jeu de données posé quelque part, qu'on a le temps de traiter. Beaucoup de situations ne ressemblent pas à cela : les données arrivent, en continu, et ne s'arrêtent pas.
Ce mur-là se calcule sans machine. Un traitement qui demande dix millisecondes par mesure absorbe cent mesures par seconde, pas une de plus. Si le capteur en produit cent vingt, le retard grandit de vingt mesures par seconde, soit un million deux cent mille mesures de retard au bout d'une journée. Aucune optimisation ne rattrape un retard qui grandit : il faut soit descendre sous le seuil, soit traiter en parallèle, soit accepter de ne pas tout traiter.
Le débit soutenable d'un traitement est le nombre d'éléments qu'il absorbe par unité de temps sans accumuler de retard. Il vaut l'inverse du temps de traitement d'un élément, multiplié par le nombre de traitements menés en parallèle.
Un système est stable tant que le débit d'arrivée reste sous le débit soutenable. Au-dessus, la file d'attente croît sans limite, et le système est déjà en panne même si rien ne l'indique encore.
L'intuition courante veut qu'un pic de charge se résorbe une fois passé. C'est vrai d'un pic, faux d'un dépassement durable.
Tant que le débit d'arrivée dépasse le débit soutenable, ne serait-ce que de quelques pour cent, la file grandit linéairement et sans fin. Les seules issues sont d'augmenter le débit soutenable, de réduire le débit d'arrivée, ou de jeter des données de façon assumée plutôt que subie.
Les cinq V, et ce qu'ils valent
Le domaine s'est doté d'un vocabulaire commode, souvent présenté comme une définition. Il mérite d'être connu, et il mérite d'être relativisé.
On lit couramment que les grandes données se caractérisent par plusieurs V : le volume, la vélocité, c'est-à-dire le débit, la variété des formats et des sources, la véracité de données dont la qualité n'est pas garantie, et parfois la valeur qu'on espère en tirer.
Cette liste décrit bien le paysage. Elle ne dit rien de ce qu'il faut faire, pour une raison simple : elle range les difficultés par leur apparence et non par leur remède. Le volume et le débit appellent des solutions opposées, la variété relève de la modélisation et non de l'infrastructure, et la véracité est un problème de préparation des données, traité dans le parcours d'intelligence artificielle.
Devant un traitement dont on craint qu'il ne passe pas à l'échelle, trois questions valent mieux que cinq mots :
- Qu'est-ce qui sature en premier quand le volume est multiplié par dix : la mémoire, le disque, le processeur, le réseau ?
- Le coût est-il linéaire ? Doubler les données double-t-il le temps, ou davantage ?
- Le traitement peut-il se faire en une seule lecture, ou faut-il tout garder ?
La troisième question est celle du chapitre suivant, et elle décide de presque tout.
Exercices type
Exercice 1 : un fichier de journalisation contient 400 millions de lignes, chacune pesant environ 120 octets. Un traitement doit compter les lignes contenant le mot ERREUR. La machine dispose de 16 gigaoctets de mémoire vive. Quel mur risque de sauter, et lequel ne sautera pas ?
Afficher la solution
Le fichier pèse environ 48 gigaoctets, donc il ne tient pas en mémoire. Le mur de la mémoire saute si, et seulement si, le traitement charge tout, ce qu'une lecture ligne par ligne évite complètement : compter des lignes ne demande de retenir qu'un compteur.
Le mur du stockage ne saute pas : 48 gigaoctets tiennent sur n'importe quel disque contemporain.
Le coût reste linéaire, et le temps sera dominé par la lecture du disque et non par le calcul. C'est un cas de grandes données au sens du volume, et pourtant une simple boucle le traite sur une seule machine.
Exercice 2 : un traitement met 40 secondes sur 100 000 lignes et 160 secondes sur 200 000 lignes. Combien de temps prendra-t-il sur 10 millions de lignes ?
Afficher la solution
Doubler les données quadruple le temps : le coût est quadratique.
Passer de 200 000 à 10 millions multiplie la taille par 50, donc le temps par 2 500. Cela fait 160 × 2 500 = 400 000 secondes, soit un peu plus de quatre jours et demi.
La conclusion n'est pas qu'il faut une machine 2 500 fois plus rapide : c'est qu'il faut trouver le in dans la boucle. Un traitement linéaire équivalent prendrait 160 × 50 = 8 000 secondes, soit un peu plus de deux heures, sur la même machine.
Exercice 3 : un capteur émet 500 mesures par seconde. Le traitement d'une mesure prend 4 millisecondes. Le système tient-il ? Et si le traitement passe à 1,8 milliseconde ?
Afficher la solution
À 4 millisecondes par mesure, le débit soutenable vaut 250 mesures par seconde. L'arrivée en apporte 500 : le retard grandit de 250 mesures par seconde, soit 21,6 millions de mesures par jour. Le système ne tient pas, et aucune patience ne le rattrapera.
À 1,8 milliseconde, le débit soutenable monte à 555 mesures par seconde. Le système tient, avec une marge de 10 %. Cette marge est faible : le moindre pic la consomme, et il faudra soit la surveiller, soit paralléliser sur deux traitements pour doubler le débit soutenable.
Exercice 4 : deux propositions pour accélérer un traitement quadratique de 4 heures. La première double le nombre de machines. La seconde remplace une recherche dans une liste par une recherche dans un dictionnaire. Laquelle choisir ?
Afficher la solution
La seconde, sans hésiter, et l'écart n'est pas de degré mais de nature.
Doubler les machines divise le temps par deux au mieux, donc ramène quatre heures à deux heures, et coûte deux fois plus cher indéfiniment.
Passer d'un coût quadratique à un coût linéaire divise le temps par le nombre d'éléments de la référence. Sur un million d'éléments, le facteur est de l'ordre du million, et il ne coûte rien.
La règle générale tient en une phrase : acheter des machines pour un problème d'algorithme revient à payer pour ne pas corriger le code.
1.Un fichier de 50 Go doit être compté ligne par ligne sur une machine de 16 Go de mémoire. Que se passe-t-il ?
2.Un traitement passe de 10 s à 40 s quand les données doublent. Son coût est…
3.Remplacer x in liste par x in ensemble dans une boucle…
4.Les données arrivent à 500 par seconde, le débit soutenable est de 480. Que faire ?
5.Quel est le principal défaut de la description par les cinq V ?
6.Sur mille lignes, un traitement quadratique…
La méthode
- Nommer le mur avant de chercher une solution : mémoire, stockage ou débit.
- Mesurer, ne pas estimer : chronométrer sur deux tailles suffit à connaître le coût.
- Doubler les données et lire le rapport des temps : 2, un peu plus de 2, ou 4.
- Chercher les recherches : tout
insur une liste, tout parcours imbriqué, toute concaténation dans une boucle. - Corriger l'algorithme avant d'ajouter des machines, l'un est gratuit et l'autre ne l'est pas.
- Calculer le débit soutenable dès que les données arrivent en continu, et le comparer au débit d'arrivée.
- Se demander ce que le traitement doit retenir, question qui décide de tout le reste.
Synthèse
- Aucun seuil en gigaoctets ne définit une grande donnée : c'est l'opération qui cesse de tenir, pas le volume.
- Trois murs indépendants : la mémoire, le stockage, le débit, avec trois remèdes distincts.
- Le mur de la mémoire et celui du débit préviennent. Un coût non linéaire ne prévient pas.
- Un coût linéaire est la limite au-delà de laquelle répartir sur plusieurs machines ne suffit plus.
- Doubler les données et lire le rapport des temps donne le coût : 2, un peu plus de 2, ou 4.
- L'accident le plus fréquent est une recherche dans une liste placée dans une boucle, qui rend le traitement quadratique sans rien signaler.
- Le volume ne crée pas les défauts de conception, il les révèle, souvent au pire moment.
- Un dépassement du débit soutenable, même de quelques pour cent, fait croître la file sans limite.
- Les cinq V décrivent le paysage et n'orientent aucune décision : trois questions font mieux.
- La question qui commande tout le reste : ce traitement peut-il se faire en une seule lecture ?