Puissance de 10 et calculs au dos d’enveloppe

Mon métier m’amène parfois à faire des calculs concernant les performances d’une solution (algorithme, architecture, persistance, etc.). Pour ce faire il y a quelques ordres de grandeur à avoir en tête afin de connaitre le domaine de performance et donc la scalabilité de la solution. Les logiciels accessibles au grand public rendent d’autant plus critique cette phase d’estimation faite rapidement au dos d’une enveloppe (back of the envelope calculations, technique popularisée par Enrico Fermi).
Voici donc ces ordres de grandeur :

Registre et cache du processeur : 1 à 10 ns

Le processeur travaille extrêmement vite, le principal problème des concepteurs de processeurs à l’heure actuelle est d’éviter à tout prix un cache miss. L’accès au cache L1 prend 1 cycle (soit 1 nanoseconde pour simplifier), une mauvaise prédiction de branchement prend 5 cycles (soit 5 ns), un accès au cache L2 prend 7 ns. Le verrouillage/déverrouillage d’un mutex pour la synchronisation de thread prend 25 ns. On reste dans l’ordre de grandeur de quelques nanosecondes.

Mémoire centrale : 100 ns soit 10² ns

Et hop, on change d’échelle en accédant à la mémoire centrale, mais bon cela reste quand même très très court (100 ns ça fait 0, 000 000 1 s). Le gonflement des RAM serveur s’explique parfaitement. A titre de référence :

• Compresser 1 Ko avec zippy (l’outil de compression LZW interne de Google) prend 3 000 ns (lecture et traitement).
• Envoyer 2 Ko sur un réseau local à 1 Gbps prend 20 000 ns.
• Lire 1 Mo en mémoire prend 250 000 ns.

Disque SSD : 100 μs soit 10⁵ ns

Un disque SSD est effectivement 10 fois à 100 fois plus rapide qu’un disque magnétique. Attention, la latence est effectivement dans ces ordres de grandeurs mais ce n’est pas le cas du débit où la différence est plutôt de l’ordre de 3 à 4 (environ 70 MB/S pour un disque magnétique et 200 MB/s pour un disque SSD). D’ailleurs, comprendre la différence entre débit et latence fait partie des fondamentaux sur laquelle j’écrirai un de ces jours.

Disque magnétique : 10 ms soit 10⁷ ns

L’accès à une donnée sur le disque est 10 000 fois plus coûteuse que sa lecture en mémoire, ça c’est du changement d’échelle ! Ceci explique le fort développement des solutions de cache mémoire distribué (Memcached, Terracota, Gigaspaces et autre Coherence). Le seek time d’un disque magnétique est ainsi d’environ 10 000 000 ns et cela prend environ 20 000 000 ns pour lire 1 Mo de manière séquentielle, soit 20 millisecondes.

Réseau local : 100 μs à 10 ms soit 10⁶ à 10⁸ns

Suivant l’architecture de la solution, il est parfois équivalent en terme de performance de lire la donnée sur un autre serveur que sur le propre disque de la machine (voir les protocoles de communication performant comme Protocol Buffers, toujours chez Google). Un aller/retour dans le même datacenter prend ainsi environ 500 000 ns.

Réseau distant : 0,1 s soit 10⁹ ns

La latence sur un WAN entre deux continents ou dans un même pays sera toujours de l’ordre de 100 ms. C’est pour cela que les datacenters des majors du web (Google, Amazon et autre facebook) sont localisés sur chaque continent. Il est donc utile de savoir que la latence typique d’un échange de données avec un service sur Internet sera d’environ 100 ms.

Mise en application de ces chiffres

Réaliser un logiciel consiste bien souvent à traiter des données : les déplacer, les créer ou les transformer. La revue de conception d’une solution impliquera donc de déterminer le volume des données et comment elles vont se déplacer d’un stockage à un autre (base de données à la mémoire du serveur d’application par exemple). Les éléments suivants et les ordres de grandeur sus-cités permettent ainsi de réaliser ce calcul « à vue de nez » :

• Volume des données active : volume total des données moins les logs, les données archivées, les sauvegardes, etc. Il est important de noter que les données les plus récentes sont souvent les plus consultées.
• Volume d’une requête moyenne : quel volume de données traite une transaction utilisateur typique ? un site avec 100 000 images de petite taille ne se comporte pas de la même manière qu’avec 1 000 vidéos de taille importante.
• Nombre de requêtes : combien de transactions par seconde et d’utilisateurs concurrents le système va devoir gérer ? le dimensionnement se fera sur le pic d’utilisateurs et de transactions afin de conserver des performances acceptables.
• Type de traitement : est ce que les données sont principalement accédées en lecture ou en écriture ? un système transactionnel se comporte différemment d’un système décisionnel.
• Cohérence : a t’on besoin d’une cohérence forte des données ? cela est souvent superflu. Un délai de mise à jour est ainsi acceptable (« Voici la donnée telle qu’elle était à 12H35m48s ») permettant alors la résistance au morcellement et la disponibilité (en application du théorème CAP).
• Regroupement : permet de connaitre les caractéristiques permettant de partitioner (techniques de sharding) les données pour optimisation. Cela peut être un critère géographique, de propriétés des données, etc.

J’ai vécu cette situation il y a quelque temps. Le contexte : mettre à jour les valeurs d’un arbre de données lorsque la valeur d’un noeud change, avec environ 1 000 noeuds d’environ 1 Ko chacun (j’arrondis les chiffres intentionnellement à la puissance de 10 supérieur, en fait les chiffres étaient bien en dessous), soit 1 Mo d’occupation mémoire. Question : vaut il mieux charger la totalité de l’arbre en mémoire ou travailler par fragment avec uniquement les noeuds à mettre à jour ? avec les ordres de grandeur ci-dessus et la complexité supplémentaire en terme de persistance qu’implique la mise à jour d’une partie des noeuds, mon choix a été de charger la totalité de l’arbre à chaque fois. Une requête de 1 Mo optimisée avec la base de données en réseau local prend environ 100 ms (arrondi très supérieur) et le calcul environ 10 ms sur l’ensemble des noeuds. Bref, mon choix a été de simplifier l’algorithme car les performances tiennent largement en terme d’ordre de grandeur.

Conclusion

En résumé, les processeurs sont très rapides et la mémoire et la bande passante sont précieuses. Une bonne conception privilégiera la localisation des données dans la mémoire vive en fonction de leurs volumes. Bien souvent, les composants d’infrastructure feront ce boulot pour nous, sous réserve d’être attentif à la localisation physique de ces composants. Pensez-y lors de votre conception, même (et surtout) si vous faites du Cloud Computing, le nuage ne vous retiendra pas et vous retomberez vite sur terre 🙂

Liens

• La présentation de Jeff Dean, Google Fellow, « Designs, Lessons and Advice from Building Large Distributed System » : retour d’expérience concernant Protocol Buffers, Map Reduce et Big Data avec un exemple d’estimation de performance. Les chiffres sur les pannes typiques pendant un an dans un cluster sont un must.
• Programming Pearls de Jon Bentley, chapitre 7 « The back of the envelope »
• 24 Gigabytes of memory ought to be enough for anybody
• What your computer does while you wait
• Application concrètes de ces faits dans node.js
• UPDATE February 2012 : this post is brilliant as  it gives us the opportunity to literally  « feel » theses scales !