Google : d’une recherche aux résultats, en passant par un index de 100 000 To

jinge a écrit :



Ici on ne parle pas de 10k mots mais beaucoup plus dans la mesure où il faut prendre chaque langue + les mots qui n’existent pas/sont pal orthographiés…

Chacun de ces mots renvoie plusieurs centaines de millions de résultats, et croiser c’est bien ces opérations que je trouve hallucinantes.

Qu’il y ait des index ou non, le nombre de résultats fait que la recherche devrait être plus longue (sauf que non " /> )





Voilà comment faire un Google. Ce n’est sans doute pas le fonctionnement de Google mais il y a nécessairement des simililtudes.



Disons qu’il y a un million de mots enregistré par Google. Le serveur sur lequel tu débarques n’a donc besoin que d’un index (appelons-le index d’entrée) de quelques dizaines voire centaines de méga-octets pour connaître pour chaque mot les serveurs qui possèdent les listes de sites contenant ce mot (l’index “mot”). Autrement ce petit index d’entrée suffit à dire quel ordinateur contient les quelques ko ou Mo de l’index “mot” parmi les centaines de milliers de To stockés sur les millions de serveurs.



Jusque là c’est un jeu d’enfants (si on oublie la redondance, la résistance aux pannes, le correction d’erreurs dans la requête, les synonymes, les sens multiples pour un mot, l’identification du sens correct en fonction de tes recherches habituelles, etc). Afficher les pages par pertinence n’est pas beaucoup plus difficile car cela a été fait au préalable : l’index “mot” contient déjà toutes les pages triées par pertinence pour ce mot et si tu souhaites la troisième page il est aisé de récupérer les numéros 30 à 40 sans avoir à lire ce qui précède. Et comme personne les résultats mal notés sont très rarement, chaque serveur pour les indexes “mot” contient 99% de données rarement demandées, on pourra donc garder le 1% important en mémoire..



Maintenant le cas des requêtes à plusieurs mots est plus délicat : pour chaque mot il peut y avoir des millions de pages. Pour chacune il ne nous faut qu’un identifiant de 16 octets (et quelques autres infos pour le tri mais ce n’est que tout à la fin, une fois les dix pages retenues sélectionnées, qu’on requiérera les url). Considérons une requête à deux mots avec un million de résultats chacun. Deux solutions naïves pour comprendre la vraie solution expliquée plus loin :

* Récupérer les millions de page triées par leur identifiant. Le croisement est alors simple (l’affaire de quelques ms) mais on se retrouverait avec de très nombreux résultats à trier et, là, on explose le budget CPU.

* Récupérer les millions de pages triées par note. Le problème est alors inversé, c’est le croisement qui est hors-budget.



En réalité plusieurs éléments de solutions à ça :

* On mélange les deux solutions naïves, ce qui fait qu’il faut deux index “mot” par mot, triés différemment.

* Au lieu de s’embêter à rapatrier des millions de pages, on triche sur le tri. Par exemple on considère que les 100 premières pages sont constituées des 50 premières du premier mot et des 50 suivantes du second mot. Du coup on ne rapatrie que très peu de données et le croisement puis le tri sont un jeu d’enfants. La mémoire, la bande passante réseau, le CPU et le disque dur du serveur “mot” sont épargnés et le résultat est bon pour l’utilisateur, vraisemblablement proche du résultat exact.

* En plus de l’index d’entrée il faut un autre index donnant les mots qui suivent généralement. Ces séquences doivent être traitées comme des mots en eux-mêmes avec leurs propres index “mot”. On enregistre donc un index “mot” pour “hymne à la joie” contenant toutes les pages avec cette séquence de mots. Ainsi on pourra obtenir une meilleure pertinence pour “hymne à la joie” qu’en combinant “hymne” et “joie”.



Et j’en passe et des meilleures, notamment tout l’aspect du tri des résultats finaux en fonction du profil de l’utilisateur.