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...
quelle
Antworten:
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:
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.
Offensichtlich gibt es hier mehr als 15 Minuten Material zu besprechen, aber hoffentlich ist es genug, um Ihnen den Einstieg zu erleichtern.
quelle
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.
quelle