Le bruit de fond à l'autre bout du fil était un chaos indescriptible.
Quelqu'un hurlait après l'administrateur à en perdre la voix : « Ajoute dix balles sur la machine trois de la zone C ! » Un autre frappait sur son bureau en jurant : « C'est quoi ce bordel ? Tu m'as flashé ! » La cacophonie était entrecoupée d'une litanie de toux et de CLIC de briquets.
Chen Zhuo écarta un peu le combiné de son oreille.
« Attends une seconde. »
Chu Ge hurla de son côté, suivi du grattement d'une chaise qu'on traîne. Le vacarme baissa d'un cran, comme s'il s'était réfugié dans un coin.
« C'est bon, vas-y. J'ai trouvé un stylo. »
Chu Ge coinça le combiné entre son épaule et son oreille, un bâton de sucrerie serré entre les dents. Sa main droite fouilla dans l'enchevêtrement de câbles du clavier jusqu'à en ressortir avec un stylo bille.
Pas de papier sur le bureau. Il jeta un coup d'œil autour de lui, saisit un gobelet de nouilles instantanées déjà mangé, et en arracha le couvercle en carton, taché de quelques gouttes d'huile de piment rouge. Il le retourna.
Le verso était légèrement humide, mais on pouvait encore y écrire.
Chen Zhuo se tenait près de la fenêtre du salon, contemplant la fine couche de givre sur la vitre. Il tendit le doigt et y traça un trait.
« Comment ils ont construit la base de données à la Capitale ? » demanda Chen Zhuo.
« Relationnelle. Une structure en arbre classique. »
Chu Ge croqua son bonbon deux ou trois fois avec force.
« Ils veulent bâtir un réseau social "six degrés de séparation". La logique sous-jacente est simple. Si je suis A et que je connais B, la base crée un lien entre nous. Interroger mes amis, c'est rapide. Interroger les amis de mes amis... ça passe à peu près. »
La voix de Chu Ge était rauque, celle de quelqu'un qui a tiré une nuit blanche.
« Mais dès qu'on essaie d'aller chercher les connexions de troisième ou quatrième degré, si la concurrence dépasse deux cents utilisateurs, la base doit effectuer des jointures imbriquées sans fin. Une table de quelques centaines de milliers d'utilisateurs explose instantanément en dizaines de millions de lignes de données redondantes. »
« Le gars de la Capitale a dit qu'ils venaient de faire un test de charge. Deux cents comptes virtuels ont tous cliqué sur la fonction "Personnes que vous connaissez peut-être" en même temps. Les ventilateurs du seveur se sont mis à tourner comme des pales d'hélicoptère, le CPU a grimpé direct à cent pour cent, et trois secondes plus tard, la base était en interblocage. »
Chu Ge soupira.
« Du coup, c'est l'impasse. Pour que ce soit rapide, il faut précalculer toutes les relations et les stocker en cache. Mais ça demande une quantité massive de mémoire, et ils n'ont pas les moyens de s'offrir autant de serveurs. Si on ne précalcule pas et qu'on interroge en temps réel, la base plante dès que quelques personnes tentent d'y accéder simultanément. »
Après avoir écouté, Chen Zhuo ne répondit pas tout de suite.
Il alla s'asseoir sur le canapé, attrapa une cacahuète dans son coque dans la corbeille à fruits, et l'écrasa doucement dans sa main.
« Vous les informaticiens... vous êtes toujours aussi raides dans votre façon de penser ? »
Chen Zhuo frotta la cacahuète pour enlever sa peau fine, une pointe d'amusement dans la voix.
« Qu'est-ce que tu veux dire ? »
Chu Ge fut un instant décontenancé.
« C'est un problème pur de théorie des graphes. Pourquoi tu tentes de le résoudre comme si tu faisais un recensement ? »
Chen Zhuo jeta la cacahuète dans sa bouche.
« Oublie tes requêtes imbriquées. Imagine tous les utilisateurs comme des points dans un espace de grande dimension. Les relations entre utilisateurs sont les segments qui les relient. »
Chu Ge ne dit rien, la pointe de son stylo en suspens au-dessus du couvercle de gobelet.
« Construis une matrice d'adjacence. »
La voix de Chen Zhuo était posée, comme s'il expliquait un devoir de calcul intégral de première année à quelqu'un dans une salle d'étude universitaire.
« Disons que tu as cent mille utilisateurs. Ça fait une matrice cent mille par cent mille, appelons-la A. Si l'utilisateur i et l'utilisateur j sont amis, la valeur à la position (i, j) dans la matrice est 1. Sinon, c'est 0. »
« Attends une seconde. »
Chu Ge le coupa.
« Cent mille fois cent mille... ça fait dix milliards de données. T'as calculé la mémoire que ça boufferait ? Le serveur exploserait sur le champ. »
« Chu Ge. »
Chen Zhuo pouffa doucement de son côté du fil.
« Dans la vraie vie, t'as cent mille amis ? »
« Non. J'en ai même pas dix. »
Chu Ge répondit honnêtement.
« Aucun être normal n'en a, »
dit Chen Zhuo.
« Donc, quatre-vingt-dix-neuf virgule neuf-neuf pour cent des valeurs de cette matrice sont des zéros. C'est une matrice extrêmement creuse. »
Les doigts de Chu Ge, crispés sur le stylo, se raidirent brutalement.
« En mémoire, t'as pas besoin de stocker ces dix milliards de points. Il te suffit de stocker les coordonnées des uns. »
Chen Zhuo continua.
« C'est un simple mappage de coordonnées. Ensuite, si tu veux trouver les amis de tes amis — tes connexions de second degré — comment tu l'exprimes mathématiquement ? »
L'esprit de Chu Ge s'emballa. Les concepts d'algèbre linéaire qu'il avait appris en première année et à moitié oubliés traversèrent soudain le brouillard de son cerveau comme un éclair.
« La multiplication matricielle, »
lâcha Chu Ge.
« A fois A. A au carré. »
« Exact. »
Chen Zhuo se leva, alla vers la table basse, et se versa un verre d'eau tiède.
« A au carré. Les valeurs non nulles de cette matrice sont tes connexions de second degré. A au cube te donne tes connexions de troisième degré. »
Chu Ge fixait le couvercle de gobelet, son stylo bille traçant machinalement des cercles dessus. Son souffle s'accéléra.
« Mais la charge de calcul pour la multiplication matricielle est énorme, surtout pour les multiplications d'ordre supérieur. Le CPU ne tiendra toujours pas le coup. »
Chu Ge pointa le nœud du problème.
« C'est parce que t'es trop gourmand. Tu veux calculer le réseau social complet de tout le monde d'un seul coup. »
Chen Zhuo but une gorgée, humecta sa gorge.
« Le serveur n'a pas besoin de savoir qui tout le monde connaît. Il doit juste répondre à la requête de l'utilisateur connecté à l'instant T. Donc, t'as pas besoin de faire une multiplication matrice par matrice. »
La voix de Chen Zhuo baissa d'un ton, mais aux oreilles de Chu Ge, elle résonna comme un coup de tonnerre.
« L'utilisateur connecté, ce n'est pas une matrice. C'est un vecteur. »
Chen Zhuo donna la pièce finale de la solution.
« Un vecteur qui vaut 1 à la position de l'utilisateur et 0 partout ailleurs. Tu prends ce vecteur unidimensionnel et tu le multiplies par la matrice creuse. Une multiplication, et tu obtiens un vecteur représentant ses amis directs. Tu reprends ce résultat et tu le multiplies à nouveau par la matrice, et tu as ses amis de second degré. »