Mesurer les limites : mémoire, disque et débit

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 peut faire tomber la même machine si l'on veut trier son contenu en le chargeant d'un bloc. Rien n'a changé dans les données : ce qui a changé, c'est ce qu'on leur demande, et la façon de le demander, puisqu'un tri par morceaux, comme celui de la commande sort, en vient à bout avec quelques mégaoctets.

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

Le volume seul ne dit rien, la contrainte qui saute dit tout. 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 qui le charge tout entier.

Les tailles s'écrivent ici, comme dans tout le parcours, avec les préfixes du Système international : un kilooctet (ko) vaut mille octets, un mégaoctet (Mo) un million, un gigaoctet (Go) un milliard, un téraoctet (To) mille milliards. Les multiples de 1 024 portent d'autres noms, le kibioctet (Kio), le mébioctet (Mio) et le gibioctet (Gio), et ne servent que là où le binaire compte vraiment, comme la capacité d'une mémoire vive : une barrette de 16 Gio contient 17,2 milliards d'octets. L'écart, 2,4 % au kilo et 7,4 % au giga, ne change aucun ordre de grandeur, mais il suffit à fausser un calcul qui mélange les deux.

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. Dans la page, où Python tourne en 32 bits, un million d'entiers occupe une vingtaine de mégaoctets : quatre pour les références, seize pour les objets. Un Python 64 bits ordinaire en compte trente-six. Un tableau numpy range le même million dans quatre mégaoctets ici, huit ailleurs : le rapport de quatre à cinq 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. Deux fois plus de données, deux fois plus de temps, aux aléas de la mesure près. C'est la propriété la plus précieuse qu'un traitement puisse avoir, et le chapitre suivant est consacré à la préserver.

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, ne dure ici que de quelques dixièmes de milliseconde à une ou deux millisecondes : l'horloge de la page, qui ne distingue pas mieux que le dixième de milliseconde, départage mal des durées si courtes, et ses rapports sautent d'une exécution à l'autre. Le bloc précédent, sur des listes dix fois plus longues, l'a montrée linéaire.

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.

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, voire en milliers selon la machine. Il reste pourtant bien en dessous du nombre de comparaisons évitées, plus de seize mille par test en moyenne : une recherche dans un ensemble coûte le calcul d'une empreinte, qui vaut à lui seul plusieurs comparaisons. L'écart, lui, grandit avec la taille de la référence, et c'est tout le danger.

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.

Le volume ne crée pas le problème, il le révèle. Un traitement quadratique rend le bon résultat sur mille lignes, mais 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 1 728 000 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.

Sous le débit soutenable, la file ne grandit plus sans fin, mais elle ne reste pas vide pour autant. Le calcul qui précède suppose des arrivées régulières et des traitements de durée fixe. Un serveur d'ingestion, qui reçoit les lots de journaux d'un parc de machines, ne voit rien de tel : les lots arrivent quand les machines les envoient, par grappes et par creux, et leur traitement dure plus ou moins longtemps selon leur taille. Chaque grappe forme une file que le creux suivant doit résorber, et plus le serveur est chargé, plus les creux se raréfient.

Le modèle de la figure, nommé M/M/1, tient en deux formules. Le temps moyen qu'un lot passe dans le système, attente et traitement compris, vaut $W = \frac{1}{\mu - \lambda}$, et le nombre moyen de lots présents $L = \frac{\lambda}{\mu - \lambda}$, où $\lambda$ est le débit d'arrivée et $\mu$ le débit soutenable. Tout se joue au dénominateur : l'attente dépend moins de la charge que de l'écart qui reste avant la saturation, et cet écart fond à l'approche du seuil. À 50 % de charge, un lot passe dans le système deux fois la durée moyenne de son traitement ; à 90 %, dix fois ; à 99 %, cent fois.

Un serveur ne se dimensionne jamais à 100 % de son débit. La marge se déduit de l'attente acceptable, et non d'un pourcentage fixé d'avance. Avec des lots de 50 millisecondes et un séjour d'au plus 250 millisecondes, le serveur ne doit pas dépasser 80 % de charge. Au-delà, il tient sur le papier et fait attendre en pratique ; à 100 %, son attente moyenne n'a plus de limite.

Le chapitre Files d'attente et dimensionnement du parcours de sciences appliquées établit ces formules, et montre ce que changent la régularité des traitements et une file commune à plusieurs serveurs.

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 chapitre sur la préparation du parcours d'intelligence artificielle.

Mettre en pratique

Les trois murs ne se devinent pas, ils se chiffrent, et le chiffre se pose avant d'écrire la première ligne de traitement.

La dernière réponse est celle qui surprend. Moins de deux millions de lignes suffisent à faire basculer un traitement quadratique d'une seconde à une heure, et deux millions de lignes n'ont rien d'un gros volume. Le mur n'est pas dans la taille des données, il est dans la forme de l'algorithme.