Wie würden Sie die Google-Suche implementieren? [geschlossen]

44

Angenommen, Sie wurden in einem Interview gefragt, wie Sie die Google-Suche implementieren würden. Wie würden Sie eine solche Frage beantworten? Es gibt möglicherweise Ressourcen, die erklären, wie einige Teile in Google implementiert sind (BigTable, MapReduce, PageRank, ...), aber das passt nicht genau in ein Interview.

Welche Gesamtarchitektur würden Sie verwenden und wie würden Sie dies in einer Zeitspanne von 15 bis 30 Minuten erklären?

Ich würde damit beginnen, zu erklären, wie eine Suchmaschine erstellt wird, die ~ 100.000 Dokumente verarbeitet, und diese dann über Sharding auf etwa 50 Millionen Dokumente erweitern, um dann vielleicht einen weiteren architektonischen / technischen Sprung zu machen.

Dies ist die 20.000 Fuß Ansicht. Was ich möchte, sind die Details - wie würden Sie das in einem Interview beantworten? Welche Datenstrukturen würden Sie verwenden? Aus welchen Diensten / Maschinen besteht Ihre Architektur? Was wäre eine typische Abfrageverzögerung? Was ist mit Failover- / Split-Brain-Problemen? Usw...

ripper234
quelle
1
Das ist eine ziemliche Interviewfrage. Wie viele Details suchten sie?
Paddy
1
Eigentlich ist das eine Frage, die ich vor einiger Zeit bei einigen Interviews gestellt habe. Das Schöne ist, dass die Menge an Details, die Sie angeben, wirklich von Ihnen abhängt und die Zeit, die Ihr Interviewer dafür aufwenden möchte.
Ripper234
2
"Karte verkleinern! Nächste Frage bitte." "Wir werden dich anrufen."
2
gute frage aber welche art könntest du stundenlang beantworten. Vielleicht würde ich mit einem Flash-Laufwerk in Google einbrechen
Ich denke, das ist eine gute Frage, obwohl ich es ziemlich überwältigend finden würde. Ich habe erst kürzlich darüber nachgedacht, wie man einen Algorithmus zum "Wichten" von Artikeln auf einer Nachrichtenseite erstellt (theoretisch nur, um mich unter der Dusche zu beschäftigen :), und ich gebe zu, dass ich selbst diese Idee als ziemlich schwierig empfinde /Komplex.

Antworten:

45

Betrachten Sie den Meta-Punkt: Was sucht der Interviewer?

Bei einer solchen Mammutfrage müssen Sie Ihre Zeit nicht damit verschwenden, einen PageRank-Algorithmus zu implementieren oder eine verteilte Indizierung durchzuführen. Konzentrieren Sie sich stattdessen auf das Gesamtbild dessen, was erforderlich ist. Es hört sich so an, als ob Sie bereits alle großen Teile kennen (BigTable, PageRank, Map / Reduce). Die Frage ist also, wie Sie sie tatsächlich miteinander verbinden.

Hier ist mein Stich.

Phase 1: Infrastruktur indizieren (5 Minuten erklären)

Die erste Phase der Implementierung von Google (oder einer Suchmaschine) besteht darin, einen Indexer zu erstellen. Dies ist die Software, die den Datenbestand crawlt und die Ergebnisse in einer Datenstruktur erzeugt, die das Lesen effizienter macht.

Um dies zu implementieren, betrachten Sie zwei Teile: einen Crawler und einen Indexer.

Der Webcrawler hat die Aufgabe, Webseiten-Links zu spinnen und sie in einer Gruppe abzulegen. Der wichtigste Schritt dabei ist, dass Sie nicht in einer Endlosschleife oder in unendlich generierten Inhalten hängen bleiben. Platzieren Sie jeden dieser Links (vorerst) in einer massiven Textdatei.

Zweitens wird der Indexer als Teil eines Map / Reduce-Jobs ausgeführt. (Ordnen Sie jedem Element in der Eingabe eine Funktion zu und reduzieren Sie dann die Ergebnisse in ein einzelnes "Ding".) Der Indexer erstellt einen einzelnen Weblink, ruft die Website ab und konvertiert sie in eine Indexdatei. (Wird als nächstes besprochen.) Der Verkleinerungsschritt wird einfach darin bestehen, alle diese Indexdateien zu einer einzigen Einheit zusammenzufassen. (Statt Millionen loser Dateien.) Da die Indizierungsschritte parallel ausgeführt werden können, können Sie diesen Map / Reduce-Auftrag in einem beliebig großen Rechenzentrum ausführen.

Phase 2: Besonderheiten der Indexierungsalgorithmen (10 Minuten Erklären)

Nachdem Sie festgelegt haben, wie Sie Webseiten verarbeiten, wird im nächsten Teil erläutert, wie Sie aussagekräftige Ergebnisse berechnen können. Die kurze Antwort hier lautet "viel mehr Karten / Verkleinerung", aber überlegen Sie, was Sie alles tun können:

  • Zählen Sie für jede Website die Anzahl der eingehenden Links. (Stärker verlinkte Seiten sollten "besser" sein.)
  • Überprüfen Sie für jede Website, wie der Link dargestellt wurde. (Links in einem <h1> oder <b> sollten wichtiger sein als solche, die in einem <h3> vergraben sind.)
  • Überprüfen Sie für jede Website die Anzahl der ausgehenden Links. (Niemand mag Spammer.)
  • Sehen Sie sich für jede Website die Arten der verwendeten Wörter an. Zum Beispiel bedeuten "Hash" und "Tabelle" wahrscheinlich, dass die Website mit der Informatik verwandt ist. "Hash" und "Brownies" auf der anderen Seite würden bedeuten, dass es sich bei der Site um etwas ganz anderes handelte.

Leider weiß ich nicht genug über die Art und Weise, wie ich die Daten analysieren und verarbeiten kann, um super hilfreich zu sein. Die Grundidee sind skalierbare Möglichkeiten zur Analyse Ihrer Daten .

Phase 3: Ergebnisse bereitstellen (10 Minuten Erklären)

Die letzte Phase dient tatsächlich den Ergebnissen. Hoffentlich haben Sie einige interessante Einblicke in die Analyse von Webseitendaten erhalten, aber die Frage ist, wie Sie diese tatsächlich abfragen. Täglich wurden 10% der Suchanfragen von Google noch nie zuvor gesehen. Dies bedeutet, dass Sie vorherige Ergebnisse nicht zwischenspeichern können.

Sie können nicht eine einzige Suche in Ihren Web-Indizes durchführen. Was würden Sie also versuchen? Wie würden Sie über verschiedene Indizes schauen? (Vielleicht Ergebnisse kombinieren - vielleicht tauchte das Schlüsselwort "stackoverflow" in mehreren Indizes auf.)

Und wie würden Sie es trotzdem nachschlagen? Welche Arten von Ansätzen können Sie verwenden , um Daten aus der Lektüre massiven schnell Mengen an Informationen? (Geben Sie hier einen Namen für Ihre bevorzugte NoSQL-Datenbank ein und / oder werfen Sie einen Blick auf Googles BigTable.) Auch wenn Sie einen hervorragenden Index haben, der sehr genau ist, müssen Sie schnell nach Daten suchen können. (Finden Sie beispielsweise die Rangnummer für "stackoverflow.com" in einer 200-GB-Datei.)

Zufällige Probleme (verbleibende Zeit)

Wenn Sie die "Knochen" Ihrer Suchmaschine verdeckt haben, können Sie sich zu jedem einzelnen Thema äußern, mit dem Sie sich besonders gut auskennen.

  • Performance des Website-Frontends
  • Verwalten des Rechenzentrums für Ihre Map / Reduce-Aufträge
  • A / B-Tests für Suchmaschinenverbesserungen
  • Integration früherer Suchvolumina / Trends in die Indexierung. (ZB wird erwartet, dass die Frontend-Serverlasten um 9-5 ansteigen und in der frühen Früh absterben.)

Offensichtlich gibt es hier mehr als 15 Minuten Material zu besprechen, aber hoffentlich ist es genug, um Ihnen den Einstieg zu erleichtern.

Chris Smith
quelle
1
Dies ist eine großartige Antwort, aber ich bin der Meinung, dass die Skalierungsprobleme bei der Erstellung von Google nicht behoben werden. Ich denke, der schwierigere Teil liegt in der Bereitstellung von Ergebnissen als Teil Ihrer Antwort. Ich habe eine Idee, wie man so etwas baut, aber ich bin daran interessiert, andere zu hören.
Ripper234
Ich habe dies auf Quora gefragt - ich denke, es kann das Publikum haben, um diese Frage zu beantworten. quora.com/…
ripper234
Schau dir meine Antwort an.
Ripper234
19

Der Beitrag auf Quora ergab den Originalartikel von Sergey Brin und Larry Page. Es scheint eine hervorragende Referenz für diese Art von Frage zu sein.

Google Architecture

ripper234
quelle