Comment Google peut-il être si rapide?

Quelles sont les technologies et les décisions de programmation qui permettent à Google de répondre si rapidement à une requête?

Chaque fois que je recherche quelque chose (l'une des plusieurs fois par jour), je suis toujours étonné de voir comment ils servent les résultats en près ou en moins d'une seconde. Quel type de configuration et d'algorithmes pourraient-ils avoir en place pour y parvenir?

Note latérale: C'est un peu écrasant de penser que même si je devais mettre une application de bureau et l'utiliser sur ma machine, ce ne serait probablement pas deux fois moins rapide que Google. Continuez à apprendre, dis-je.

Voici quelques-unes des bonnes réponses et des conseils fournis:

• Plateforme Google
• Réduire la carte
• Algorithmes soigneusement conçus
• Matériel - fermes de cluster et grand nombre d'ordinateurs bon marché
• Mise en cache et équilibrage de charge
• Système de fichiers Google

La latence est détruite par les accès au disque. Il est donc raisonnable de croire que toutes les données utilisées pour répondre aux requêtes sont conservées en mémoire. Cela implique des milliers de serveurs, chacun répliquant l'un des nombreux fragments. Par conséquent, il est peu probable que le chemin critique de la recherche atteigne l'une de leurs technologies de systèmes distribués phares GFS, MapReduce ou BigTable. Ceux-ci seront utilisés pour traiter les résultats des robots d'exploration, grossièrement.

La chose pratique à propos de la recherche est qu'il n'est pas nécessaire d'avoir des résultats fortement cohérents ou des données complètement à jour, de sorte que Google n'est pas empêché de répondre à une requête car un résultat de recherche plus à jour est devenu disponible.

Une architecture possible est donc assez simple: les serveurs frontaux traitent la requête, la normalisent (éventuellement en supprimant les mots vides, etc.) puis la distribuent à n'importe quel sous-ensemble de répliques qui possède cette partie de l'espace de requête (une architecture alternative consiste à diviser le données par pages Web, de sorte qu'un de chaque jeu de réplicas doit être contacté pour chaque requête). De très nombreuses répliques sont probablement interrogées et les réponses les plus rapides l'emportent. Chaque réplica a un index mappant des requêtes (ou des termes de requête individuels) vers des documents qu'ils peuvent utiliser pour rechercher très rapidement des résultats en mémoire. Si des résultats différents proviennent de sources différentes, le serveur frontal peut les classer au fur et à mesure qu'il crache le html.

Notez que c'est probablement très différent de ce que Google fait réellement - ils auront conçu la vie de ce système afin qu'il puisse y avoir plus de caches dans des zones étranges, des index étranges et une sorte de schéma d'équilibrage de charge funky parmi d'autres différences possibles .

C'est un peu trop pour le mettre en une seule réponse. http://en.wikipedia.org/wiki/Google_platform

Un fait que j'ai toujours trouvé drôle, c'est que Google est en fait géré par la bioinformatique («ok, je trouve ça drôle parce que je suis un bioinf… truc). Laisse-moi expliquer.

La bioinformatique a dès le début eu le défi de rechercher très rapidement de petits textes dans des chaînes gigantesques. Pour nous, la «corde gigantesque» est bien sûr de l'ADN. Souvent, pas un ADN unique mais une base de données de plusieurs ADN de différentes espèces / individus. Les petits textes sont des protéines ou leur homologue génétique, un gène. La plupart des premiers travaux des biologistes computationnels se sont limités à trouver des homologies entre les gènes. Ceci est fait pour établir la fonction des gènes nouvellement trouvés en notant des similitudes avec des gènes déjà connus.

Maintenant, ces chaînes d'ADN deviennent vraiment très volumineuses et la recherche (avec perte!) Doit être effectuée de manière extrêmement efficace. La plupart de la théorie moderne de la recherche de chaînes a donc été développée dans le contexte de la biologie computationnelle.

Cependant, il y a assez longtemps, la recherche de texte conventionnelle était épuisée. Une nouvelle approche était nécessaire qui permettait de rechercher de grandes chaînes dans le temps sous-linéaire, c'est-à-dire sans regarder chaque caractère. On a découvert que cela pouvait être résolu en prétraitant la grande chaîne et en construisant une structure de données d'index spéciale dessus. De nombreuses structures de données de ce type ont été proposées. Chacun a ses forces et ses faiblesses mais il y en a un qui est particulièrement remarquable car il permet une recherche en temps constant. Maintenant, dans les ordres de grandeur dans lesquels Google opère, ce n'est plus strictement vrai car l'équilibrage de charge entre les serveurs, le prétraitement et d'autres éléments sophistiqués doivent être pris en compte.

Mais en substance, le soi-disant index q-gram permet une recherche en temps constant. Le seul inconvénient: la structure des données devient ridiculement grande. Essentiellement, pour permettre une recherche de chaînes avec jusqu'à q caractères (d'où le nom), il faut une table qui a un champ pour chaque combinaison possible de q lettres (c'est-à-dire q ^S , où S est la taille de l'alphabet , disons 36 (= 26 + 10)). De plus, il doit y avoir un champ pour chaque position de lettre dans la chaîne qui a été indexée (ou dans le cas de google, pour chaque site Web).

Pour atténuer la taille, Google utilisera probablement plusieurs indices (en fait, ils le font , pour offrir des services tels que la correction orthographique). Les plus hauts ne fonctionneront pas au niveau des caractères mais au niveau des mots. Cela réduit q mais cela rend S infiniment plus grand, ils devront donc utiliser des tables de hachage et de collision pour faire face au nombre infini de mots différents.

Au niveau suivant, ces mots hachés pointeront vers d'autres structures de données d'index qui, à leur tour, hacheront des caractères pointant vers des sites Web.

Pour faire court, ces structures de données d'index q -gram sont sans doute la partie la plus centrale de l'algorithme de recherche de Google. Malheureusement, il n'y a pas de bons articles non techniques expliquant le fonctionnement des indices q- gramme. La seule publication que je connaisse qui contienne une description du fonctionnement d'un tel index est… hélas, ma thèse de licence .

Voici quelques-unes des bonnes réponses et des conseils fournis:

• Plateforme Google
• Réduire la carte
• Algorithmes soigneusement conçus
• Matériel - fermes de cluster et grand nombre d'ordinateurs bon marché
• Mise en cache et équilibrage de charge
• Système de fichiers Google

Ils ont mis en œuvre de bons algorithmes distribués fonctionnant sur une grande quantité de matériel.

L'un des retards les plus importants est que les serveurs Web acheminent votre requête vers le serveur Web et la réponse. Cette latence est liée à la vitesse de la lumière, à laquelle même Google doit obéir. Cependant, ils ont des centres de données partout dans le monde. En conséquence, la distance moyenne à l'un d'eux est inférieure. Cela réduit la latence. Bien sûr, la différence est mesurée en millisecondes, mais il est important que la réponse arrive dans les 1000 millisecondes.

Tout le monde sait que c'est parce qu'ils utilisent des pigeons , bien sûr!

Oh ouais, ça et Mapreduce.

Ils ont à peu près une copie locale d'Internet en cache sur des milliers de PC sur des systèmes de fichiers personnalisés.

Google embauche le meilleur des meilleurs. Certaines des personnes les plus intelligentes de l'informatique travaillent chez google. Ils ont pratiquement une somme infinie à consacrer au matériel et aux ingénieurs.

Ils utilisent des mécanismes de stockage hautement optimisés pour les tâches qu'ils exécutent.

Ils ont des fermes de serveurs géographiquement localisées.

Une tentative de liste généralisée (qui ne dépend pas de votre accès aux outils internes de Google):

1. Mettre en parallèle les demandes (par exemple, diviser une seule demande en ensembles plus petits)
2. Async (rendre autant asynchrone que possible, par exemple ne bloquera pas la demande de l'utilisateur)
3. Mémoire / cache (les E / S disque sont lentes, conservez autant que possible en mémoire)
4. Pré-calcul (faites autant de travail que possible à l'avance, n'attendez pas qu'un utilisateur demande des données / traitement)
5. Prenez soin de votre HTML frontal (voir Yslow et ses amis)

Vous pouvez trouver sur la page d'accueil de Google Research des conseils sur les documents de recherche rédigés par certains des gars de Google. Vous devriez commencer par l'explication du système de fichiers google et de l' algorithme map / reduction pour essayer de comprendre ce qui se passe derrière les pages google.

Ce lien est également très instructif Dans les coulisses d'une requête Google

Matériel.

Beaucoup de matériel. Ils utilisent des grappes massives de PC de base comme leur ferme de serveurs.

TraumaPony a raison. Des tonnes de serveurs et une architecture intelligente pour l'équilibrage de charge / la mise en cache et voilà, vous pouvez exécuter une requête en moins d'une seconde. Il y avait beaucoup d'articles sur le net décrivant l'architecture des services Google. Je suis sûr que vous pouvez les trouver via Google :)

HenryR a probablement raison.

Map Reduce ne joue pas de rôle pour la recherche elle-même, mais n'est utilisé que pour l'indexation. Regardez cette interview vidéo avec les inventeurs de Map Reduce .

Une raison supplémentaire semble être qu'ils trichent sur l'algorithme de démarrage lent TCP.

http://blog.benstrong.com/2010/11/google-and-microsoft-cheat-on-slow.html

Et des algorithmes qui peuvent exploiter cette puissance matérielle. Comme mapreduce par exemple.

Si vous souhaitez plus de détails sur le fonctionnement du cluster Google, je vous suggère cette implémentation open source de leur HDFS .

Il est basé sur Mapreduce par google.

1. Stockage, traitement et récupération de données en plusieurs étapes

2. Distribution efficace (100 sur 1000 de machines) des tâches ci-dessus

3. Bon cadre pour stocker les données brutes et les résultats traités

4. Bon cadre pour récupérer les résultats

Comment exactement tout cela est fait est résumé par tous les liens que vous avez dans le résumé de la question