Dans la première partie de ce billet, vous avez pu découvrir comment Babbar opère le crawl, récupère les liens, et calcule les métriques (que nous vous décrirons dans un prochain billet). C’est-à-dire que vous savez tout ou presque du fonctionnement de la partie “compute” de Babbar.
Voyons maintenant comment Babbar peut vous donner efficacement accès à toutes les informations qui vous intéresse…
Pour que vous puissiez avoir accès à ces données, il y a bien entendu une partie « serving » qui nécessite quelques traitements supplémentaires côté base de données et pas mal d’acrobaties entre les clusters pour être efficace. Mais le traitement le plus crucial, et que nous avons beaucoup travaillé, c’est la compression.
Pour vous donner un ordre d’idée, on va se baser sur le chiffre de 10 milliards de pages, qui a l’avantage d’être rond et frappant. Quand Babbar crawle 10 milliards de pages, l’outil récupère environ 200 milliards de liens externes. Et en pratique il y aura environ le double de liens internes, que l’outil va stocker différemment (encore un sujet pour un autre jour ;)).
Un lien externe, c’est au minimum deux urls, plus les infos de métriques, l’ancre, la date, etc. Une url en moyenne fera autour de 90 caractères. Quand nous avons fait les calculs, nous nous sommes vite rendu compte que d’un point de vue coût opérationnel (disques et RAM), cela ne serait pas raisonnable.
L’une de nos premières tâches a donc été d’écrire une solution algorithmique efficace pour compresser les URLs de manière rapide et efficace. En gros ce premier niveau de compression permet de manipuler tout au long de la chaine de traitement des structures d’URLs déjà parsées qui font environ un tiers de la taille d’origine. Et c’est sans compter évidemment sur la deuxième passe de compression qui est faite par la base de données, en bénéficiant à fond des répétitions.
Enfin, impossible de finir cet article sans évoquer la compression des vecteurs sémantiques dont nous sommes très fiers.
De base, un vecteur fait environ 1 ko et est très difficile à compresser. Le problème c’est que pour calculer la métrique sémantique (la fameuse semantic value de Babbar), il faut impérativement transmettre ce vecteur dans chaque lien sortant (rappelez-vous, 200 milliards de liens et 1ko par lien).
C’est évidemment totalement hors de question d’un point de vue opérationnel. Il a donc fallu que nous trouvions une solution pour compresser ce vecteur. Il y a des solutions connues comme la Product Quantization, ou encore la Scalar Quantization. Nous les avons essayé, ainsi que des représentations des vecteurs via des mots. Ces dernières étaient d’ailleurs extrêmement efficaces mais bien trop gourmande en temps de calcul.
Après beaucoup d’essais, nous avons trouvé une solution très efficace, basée sur la quantization scalaire mais avec quelques astuces liées à la forme des vecteurs manipulés. Bref, dans les liens, un vecteur est compressé en 24 octets (au lieu de 1 ko !), et malgré cela il conserve encore 70% des caractéristiques du vecteur d’origine (pour les spécialistes, 70% correspond au Recall@100 d’un nearest neighbour fait avec ces vecteurs).
C’est avec tout cela qu’on arrive en moyenne à un stockage de moins de 4 ko par page crawlée, et ce malgré le surcoût de 30% lié à la base de données (RocksDB est basée sur une LSM, qui est extrêmement efficace mais entraîne un petit surcoût en stockage, heureusement plus que compensé par la possibilité de compresser les blocs de données).
Voilà, vous savez maintenant comment on crawle, analyse et stocke des dizaines de milliards de pages web. Pour voir la bête en action, direction https://t.co/h9nLVXk3YV pour vous inscrire à la beta privée !