Supposons qu'on vous demande dans une interview "Comment implémenteriez-vous Google Search?" Comment répondriez-vous à une telle question? Certaines ressources peuvent expliquer la mise en œuvre de certains éléments de Google (BigTable, MapReduce, PageRank, ...), mais cela ne convient pas à une interview.
Quelle architecture générale utiliseriez-vous et comment expliqueriez-vous cela dans un intervalle de temps de 15 à 30 minutes?
Je commencerais par expliquer comment créer un moteur de recherche capable de gérer environ 100 000 documents, puis de l’étendre en partageant environ 50 millions de documents, puis peut-être un autre saut architectural / technique.
C'est la vue à 20 000 pieds. Ce que j'aimerais, ce sont les détails - comment vous répondriez cela dans une interview. Quelles structures de données utiliseriez-vous? De quels services / machines votre architecture est-elle composée? Quelle serait une latence de requête typique? Qu'en est-il des problèmes de basculement / fractionnement du cerveau? Etc...
la source
Réponses:
Considérez le méta-point: que recherche l'intervieweur?
Une question gigantesque comme celle-là ne vous cherche pas à perdre votre temps à mettre en œuvre un algorithme de type PageRank ou à effectuer une indexation distribuée. Concentrez-vous plutôt sur l’ image complète de ce que cela prendrait. On dirait que vous connaissez déjà toutes les grandes pièces (BigTable, PageRank, Map / Reduce). La question est donc, comment les connectez-vous réellement?
Voici mon coup de poignard.
Phase 1: Infrastructure d'indexation (consacrez 5 minutes à expliquer)
La première phase de mise en œuvre de Google (ou de tout moteur de recherche) consiste à créer un indexeur. Il s’agit du logiciel qui explore le corpus de données et produit les résultats dans une structure de données plus efficace pour la lecture.
Pour implémenter cela, considérons deux parties: un robot et un indexeur.
Le travail du robot d'indexation Web consiste à spider des liens de page Web et à les transférer dans un ensemble. L'étape la plus importante ici consiste à éviter de se faire prendre dans une boucle infinie ou sur un contenu généré à l'infini. Placez chacun de ces liens dans un fichier texte massif (pour le moment).
Deuxièmement, l'indexeur sera exécuté dans le cadre d'un travail de mappage / réduction. (Mappez une fonction sur chaque élément de l'entrée, puis réduisez les résultats en une seule chose.) L'indexeur prend un lien Web unique, récupère le site Web et le convertit en fichier d'index. (Discuté ensuite.) L’étape de réduction consistera simplement à regrouper tous ces fichiers d’index en une seule unité. (Plutôt que des millions de fichiers volants.) Étant donné que les étapes d'indexation peuvent être effectuées en parallèle, vous pouvez alimenter ce travail Mapper / Réduire sur un centre de données de taille arbitraire.
Phase 2: Spécificités des algorithmes d'indexation (consacrez 10 minutes à expliquer)
Une fois que vous avez indiqué comment vous allez traiter les pages Web, la partie suivante explique comment vous pouvez calculer des résultats significatifs. La réponse courte ici est «beaucoup plus de cartes / réductions», mais considérez le genre de choses que vous pouvez faire:
Malheureusement, je ne connais pas suffisamment les moyens d'analyser et de traiter les données pour être extrêmement utile. Mais l'idée générale est de disposer de moyens évolutifs pour analyser vos données .
Phase 3: Résultats des services (consacrez 10 minutes à expliquer)
La phase finale sert réellement les résultats. J'espère que vous avez partagé des informations intéressantes sur la manière d'analyser les données de pages Web, mais la question est de savoir comment l'interroger réellement. De manière anecdotique, 10% des requêtes de recherche Google effectuées chaque jour sont inédites. Cela signifie que vous ne pouvez pas mettre en cache les résultats précédents.
Vous ne pouvez pas avoir une seule "recherche" dans vos index Web, alors que tenteriez-vous? Comment regarderiez-vous les différents index? (Peut-être que la combinaison de résultats - le mot-clé 'stackoverflow' est peut-être apparu très fréquemment dans plusieurs index.)
Aussi, comment vous y prendreriez-vous quand même? Quelles sortes d'approches pouvez-vous utiliser pour lire rapidement des données à partir de quantités énormes d'informations? (N'hésitez pas à nommer ici votre base de données NoSQL préférée et / ou à vous interroger sur la BigTable de Google.) Même si vous disposez d'un index impressionnant et extrêmement précis, vous avez besoin d'un moyen de trouver rapidement des données. (Par exemple, recherchez le numéro de classement de 'stackoverflow.com' dans un fichier de 200 Go.)
Problèmes aléatoires (temps restant)
Une fois que vous avez couvert les "os" de votre moteur de recherche, n'hésitez pas à choisir n'importe quel sujet sur lequel vous êtes particulièrement bien informé.
Il y a évidemment plus de 15 minutes de matériel à discuter ici, mais j'espère que cela suffira pour vous aider à démarrer.
la source
Le post sur Quora a donné l' article original publié par Sergey Brin et Larry Page. Cela semble être une excellente référence pour ce type de question.
la source