Eh bien, je ne sais pas si c'est MapReduce qui résout le problème, mais ce ne serait sûrement pas MapReduce seul pour résoudre toutes ces questions que vous avez soulevées. Mais voici choses importantes à prendre en compte, et que le rendre possible d'avoir un tel faible temps d' attente sur les requêtes de toutes ces données dans téraoctets de machines différentes:
- informatique distribuée: en étant distribué ne signifie pas que les index sont simplement distribués sur différentes machines, ils sont en fait répliqués sur différents clusters, ce qui permet à de nombreux utilisateurs d'effectuer différentes requêtes avec un temps de récupération faible (oui, les grandes entreprises peuvent se permettre autant de machines);
- mise en cache: les caches réduisent considérablement le temps d'exécution, que ce soit pour l'étape d'exploration, pour la récupération des pages, ou pour le classement et l'exhibition des résultats;
- beaucoup de réglages: tous les algorithmes / solutions ci-dessus et très efficaces ne peuvent être efficaces que si la mise en œuvre est également efficace. Il existe des tonnes d'optimisations (codées en dur), telles que la localité de référence, la compression, la mise en cache; tous sont généralement applicables à différentes parties du traitement.
Compte tenu de cela, essayons de répondre à vos questions:
mais j'imagine qu'il est impossible pour les résultats de chaque requête possible d'être indexés
Oui, ce serait le cas, et il est en fait impossible d'obtenir des résultats pour chaque requête possible . Il existe un nombre infini de termes dans le monde (même si vous supposez que seuls les termes correctement orthographiés seront saisis), et il existe un nombre exponentiel de requêtes à partir de ces n -> inftermes ( 2^n). Alors que fait-on? Mise en cache. Mais s'il y a tant de requêtes / résultats, lesquels mettre en cache? Stratégies de mise en cache. Les requêtes les plus fréquentes / populaires / pertinentes pour l'utilisateur sont celles mises en cache.
la latence matérielle du matériel de Google ne serait-elle pas énorme? Même si les données de Google étaient toutes stockées dans des SSD TB / s
De nos jours, avec de tels processeurs hautement développés, les gens ont tendance à penser que toutes les tâches possibles qui doivent se terminer en une seconde (ou moins), et qui traitent tant de données, doivent être traitées par des processeurs extrêmement puissants avec plusieurs cœurs et beaucoup de mémoire. Cependant, la seule chose qui domine le marché est l'argent, et les investisseurs ne sont pas intéressés à le gaspiller. Alors que fait-on?
La préférence est en fait d'avoir beaucoup de machines, chacune utilisant des processeurs simples / accessibles (en termes de coût), ce qui réduit le prix de la constitution de la multitude de clusters. Et oui, ça marche. Le principal goulot d'étranglement se résume toujours au disque, si vous envisagez de simples mesures de performances . Mais une fois qu'il y a tant de machines, on peut se permettre de charger des choses dans la mémoire principale, au lieu de travailler sur des disques durs.
Les cartes mémoire sont chères pour nous, simples êtres humains, mais elles sont très bon marché pour les entreprises qui achètent beaucoup de ces cartes à la fois. Puisqu'il n'est pas coûteux, disposer de suffisamment de mémoire pour charger les index et garder les caches à portée de main n'est pas un problème. Et comme il y a tellement de machines, il n'y a pas besoin de processeurs ultra rapides, car vous pouvez diriger les requêtes vers différents endroits et avoir des grappes de machines chargées d'assister à des régions géographiques spécifiques , ce qui permet une mise en cache des données plus spécialisée et une réponse encore meilleure fois.
MapReduce aide-t-il à résoudre ce problème?
Bien que je ne pense pas que l'utilisation ou non de MapReduce soit une information restreinte dans Google, je ne suis pas au courant de ce point. Cependant, l'implémentation de MapReduce par Google (qui n'est certainement pas Hadoop) doit avoir beaucoup d'optimisations, dont beaucoup impliquent les aspects discutés ci-dessus. Ainsi, l'architecture de MapReduce aide probablement à guider la façon dont les calculs sont physiquement distribués, mais il existe de nombreux autres points à considérer pour justifier une telle vitesse dans le temps d'interrogation.
D'accord, je comprends donc que les recherches populaires peuvent être mises en cache en mémoire. Mais qu'en est-il des recherches impopulaires?
Le graphique ci-dessous présente une courbe de la façon dont les types de requêtes se produisent. Vous pouvez voir qu'il existe trois principaux types de recherches, chacune d'entre elles détenant environ 1/3 du volume des requêtes (zone sous la courbe). L'intrigue montre la loi de puissance et renforce le fait que les requêtes plus petites sont les plus populaires. Le deuxième tiers des requêtes est toujours réalisable, car elles contiennent peu de mots. Mais l'ensemble des requêtes dites obscures , qui consistent généralement en des requêtes d'utilisateurs non expérimentés, ne sont pas une partie négligeable des requêtes.
Et il y a de la place pour de nouvelles solutions. Comme ce ne sont pas seulement une ou deux requêtes (mais un tiers d'entre elles), elles doivent avoir des résultats pertinents . Si vous saisissez quelque chose de beaucoup trop obscur dans une recherche Google, cela ne prendra pas plus de temps pour renvoyer une liste de résultats, mais vous montrera très probablement quelque chose qu'il a déduit que vous aimeriez dire. Ou il peut simplement indiquer qu'il n'y avait aucun document avec de tels termes - ou même réduire votre recherche à 32 mots (ce qui m'est arrivé dans un test aléatoire ici).
Il existe des dizaines d'heuristiques applicables, qui peuvent être soit d'ignorer certains mots, soit d'essayer de diviser la requête en plus petits et de rassembler les résultats les plus populaires . Et toutes ces solutions peuvent être adaptées et modifiées pour respecter des temps d'attente réalisables , disons, moins d'une seconde? :RÉ
MapReduce n'a rien à voir avec quoi que ce soit en temps réel. Il s'agit d'un cadre de traitement orienté par lots adapté à certaines tâches hors ligne, comme ETL et la construction d'index. Google a abandonné MapReduce pour la plupart des emplois maintenant, et même l'écosystème Hadoop fait de même.
La réponse à une faible latence est généralement de conserver des indices précalculés en mémoire. Tout ce qui touche le disque est difficile à réaliser rapidement et à faire évoluer. C'est ainsi que les moteurs SQL de nouvelle génération basés sur Hadoop comme Impala obtiennent autant de vitesse par rapport à une infrastructure basée sur MapReduce comme Hive , par exemple.
L'infrastructure de recherche ne peut pas mettre en cache les résultats de chaque requête. Mais il peut certainement mettre en cache des résultats intermédiaires ou des résultats plus complets pour les requêtes les plus fréquentes. Avec un peu de mise en cache, vous pouvez fournir des résultats pour une minorité significative de toutes les requêtes.
La recherche est également répartie sur plusieurs serveurs. Une machine peut donc déléguer à 100 pour obtenir chacun une partie du résultat, puis les combiner.
Vous pouvez également vous en sortir avec un certain degré d'approximation. Google ne forme pas littéralement un millier de pages de résultats de recherche; il suffit d'avoir la première page à peu près correcte.
N'oubliez pas que Google possède des millions d'ordinateurs dans le monde. Vos requêtes sont acheminées vers un centre de données géographiquement proche de vous et qui ne sert que votre géographie. Cela réduit la majeure partie de la latence, qui est le réseau et non le temps de traitement dans le centre de données.
la source
MapReduce n'est pas utilisé dans la recherche. Il a été utilisé il y a longtemps pour construire l'index; mais c'est un framework de traitement par lots, et la plupart du Web ne change pas tout le temps, donc les nouvelles architectures sont toutes incrémentielles au lieu d'être orientées par lots.
La recherche dans Google fonctionnera en grande partie de la même manière que dans Lucene et Elastic Search, à l'exception de nombreuses optimisations et pondérations supplémentaires. Mais au fond, ils utiliseront une certaine forme d' index inversé . En d'autres termes, ils ne recherchent pas plusieurs téraoctets lorsque vous entrez une requête de recherche (même lorsqu'elle n'est pas mise en cache). Ils ne regardent probablement pas du tout les documents réels. Mais ils utilisent une table de recherche qui répertorie les documents qui correspondent à votre terme de requête (avec la racine, les fautes d'orthographe, les synonymes, etc. tous prétraités). Ils récupèrent probablement la liste des 10000 premiers documents pour chaque mot (10 000 entiers - juste quelques ko!) Et calculent les meilleures correspondances à partir de cela. Seulement s'il n'y a pas de bonnes correspondances dans ces listes, elles s'étendent aux blocs suivants, etc.
Les requêtes de mots courants peuvent être facilement mises en cache; et via le prétraitement, vous pouvez créer une liste des 10 premiers résultats, puis les reclassifier en fonction du profil utilisateur. Il n'y a rien à gagner à calculer une réponse "exacte" aussi. Regarder les 10 premiers résultats est probablement suffisant; il n'y a pas de bonne réponse; et si un meilleur résultat quelque part à la position 10001 est manqué, personne ne le saura ou ne le remarquera (ou ne s'en souciera). Il était probablement déjà classé dans le prétraitement et ne serait pas entré dans le top 10 qui est présenté à l'utilisateur à la fin (ou dans le top 3, l'utilisateur regarde réellement)
Les termes rares, en revanche, ne posent pas non plus de problème - l'une des listes ne contient que quelques documents correspondants et vous pouvez immédiatement en supprimer tous les autres.
Je recommande de lire cet article:
Et oui, ce sont les fondateurs de Google qui ont écrit cela. Ce n'est pas le dernier état, mais cela fonctionnera déjà à une assez grande échelle.
la source