Wie kehrt eine Abfrage in eine riesige Datenbank mit vernachlässigbarer Latenz zurück?

Question

Wenn beispielsweise etwas in Google gesucht wird, kehren die Ergebnisse nahezu intensiv zurück.

Ich verstehe, dass Google Seiten mit Algorithmen usw. sortiert und indiziert, aber ich stelle mir vor, dass es nicht zu Indexierung der Ergebnisse jeder einzelnen Abfrage ist (und die Ergebnisse sind personalisiert, was dies noch reibungsloser macht)?

Wäre die Hardware -Latenz in Googles Hardware nicht riesig? Selbst wenn die Daten in Google alle in TB/S -SSDs gespeichert wurden, stelle ich mir vor, dass die Hardware -Latenz angesichts der schiere Datenmenge, die zu verarbeiten ist, enorm ist.

Hilft MapReduce bei der Lösung dieses Problems?

Bearbeiten: Okay, ich verstehe, dass beliebte Suchvorgänge im Speicher zwischengespeichert werden können. Aber was ist mit unpopulären Suchanfragen? Selbst für die dunkelste Suche, die ich durchgeführt habe, glaube ich nicht, dass die Suche jemals größer als 5 Sekunden ist. Wie ist das möglich?

Answer 1

Ich bin mir nicht sicher, ob es sich um MapReduce handelt, die das Problem löst, aber es wäre sicherlich nicht allein MapReduce, all diese von Ihnen aufgeworfenen Fragen zu lösen. Aber hier sind wichtige Dinge zu berücksichtigen, und das macht es machbar So geringe Latenz zu Abfragen von all diesen TBs von Daten in verschiedenen Maschinen zu haben:

1. Distributed Computing: Durch die Verteilung bedeutet nicht, dass die Indizes einfach in verschiedenen Maschinen verteilt sind, sie werden tatsächlich entlang verschiedener Cluster repliziert, wodurch viele Benutzer unterschiedliche Abfragen mit niedriger Abrufzeit ausführen können (ja, riesige Unternehmen können sich für so viel leisten von Maschinen);
2. Caching: Caches reduzieren die Ausführungszeit enorm, sei es für den Kriechschritt, für das Abrufen von Seiten oder für das Ranking und das Exihibition der Ergebnisse;
3. Viele Optimierung: Alle oben genannten und sehr effizienten Algorithmen/Lösungen können nur dann wirksam sein, wenn die Implementierung ebenfalls effizient ist. Es gibt unzählige (hart codierte) Optimierungen wie Referenzort, Komprimierung, Zwischenspeicherung; Alle von ihnen sind normalerweise für verschiedene Teile der Verarbeitung zutreffend.

In Anbetracht dessen versuchen wir, Ihre Fragen zu beantworten:

Aber ich stelle mir vor, dass es nicht realisierbar ist, dass die Ergebnisse jeder einzelnen möglichen Abfrage indiziert werden,

Ja, es wäre und ist tatsächlich nicht zu tun, um Ergebnisse zu erzielen Jede mögliche Abfrage. Es gibt eine unendliche Anzahl von Begriffen in der Welt (auch wenn Sie davon ausgehen, dass nur ordnungsgemäß geschriebene Begriffe eingegeben werden), und es gibt eine exponentielle Anzahl von Abfragen von diesen n -> inf Bedingungen (2^n). Also, was wird getan? Zwischengespeichert. Aber wenn es so viele Abfragen/Ergebnisse gibt, welche zum Cache? Richtlinien zwischengespeichert. Die häufigsten/populärsten/relevanten Anfragen für die Benutzer sind zwischengespeichert.

Wäre die Hardware -Latenz in Googles Hardware nicht riesig? Auch wenn die Daten in Google alle in TB/S SSDs gespeichert wurden

Mit solchen hoch entwickelten Prozessoren neigen die Menschen heutzutage dazu zu der Meinung, dass jede mögliche Aufgabe, die innerhalb einer Sekunde (oder weniger) abgeschlossen ist und die so viele Daten befasst, von extrem leistungsstarken Prozessoren mit mehreren Kernen und viel Speicher verarbeitet werden muss. Allerdings die einzige Sache Regeln Der Markt ist Geld und die Investoren sind nicht daran interessiert, es zu verschwenden. Also, was wird getan?

Die Präferenz dient tatsächlich darin, viele Maschinen zu haben, die jeweils einfache/zugängliche (in Bezug auf die Kosten-) Prozessoren verwenden, was den Preis für den Aufbau der Vielzahl von Clustern senkt. Und ja, es funktioniert. Der Haupttipp läuft immer auf die Festplatte hinaus, wenn Sie einfache Messungen von betrachten Leistung. Aber sobald es so viele Maschinen gibt, kann man es sich leisten, die Dinge in den Hauptspeicher zu laden, anstatt an Festplatten zu arbeiten.

Speicherkarten sind teuer Für uns, bloße Menschen, aber sie sind sehr billig für Unternehmen, die viele solche Karten gleichzeitig kaufen. Da es nicht kostspielig ist, ist es kein Problem, viel Speicher zu haben, um Indizes zu laden und Caches zur Hand zu halten. Und da es so viele Maschinen gibt, sind keine superschnellen Prozessoren erforderlich, da Sie Fragen an verschiedene Orte lenken können und Cluster von Maschinen haben, die für die Teilnahme verantwortlich sind Spezifische geografische Regionen, was mehr zulässt spezialisiert Daten zwischen Daten und noch bessere Reaktionszeiten.

Hilft MapReduce bei der Lösung dieses Problems?

Obwohl ich nicht der Meinung bin, dass MapReduce in Google eingeschränkte Informationen ist, bin ich nicht zu diesem Punkt gesprochen. Die Implementierung von MapReduce durch Google (was sicherlich sicherlich ist nicht Hadoop) muss viele Optimierungen haben, viele mit den oben diskutierten Aspekten. Die Architektur von MapReduce hilft also wahrscheinlich zu leiten, wie die Berechnungen physikalisch verteilt sind, aber es gibt viele andere Punkte, die in Betracht gezogen werden müssen, um eine solche Geschwindigkeit in der Abfragezeit zu rechtfertigen.

Okay, ich verstehe, dass beliebte Suchanfragen im Gedächtnis zwischengespeichert werden können. Aber was ist mit unpopulären Suchanfragen?

Die folgende Grafik zeigt eine Kurve darüber, wie die Arten von Fragen treten auf. Sie können sehen, dass es drei Hauptarten von Suchanfragen gibt, von denen jede ungefähr 1/3 des Zfrauungsvolumens (Bereich unterhalb der Kurve) enthält. Die Handlung zeigt das Machtgesetz und verstärkt die Tatsache, dass kleinere Fragen am beliebtesten sind. Das zweite Drittel der Abfragen ist immer noch machbar zu verarbeiten, da sie nur wenige Wörter enthalten. Aber der sogenannte Satz obskure Abfragen, die normalerweise aus Fragen der nicht erlangten Benutzer bestehen, sind kein vernachlässigbarer Teil der Abfragen.

Und dort liegt Platz für neuartige Lösungen. Da es nicht nur ein oder zwei Fragen (sondern ein Drittel von ihnen) sind, müssen sie haben relevant Ergebnisse. Wenn Sie etwas eingeben viel zu dunkel Bei einer Google -Suche dauert es nicht länger, eine Liste von Ergebnissen zurückzugeben, wird Ihnen aber höchstwahrscheinlich etwas anzeigen gefolgert Sie möchten sagen. Oder es kann einfach besagt, dass es kein Dokument mit solchen Begriffen gab - oder sogar Ihre Suche auf 32 Wörter reduzieren (die mir hier gerade in einem zufälligen Test passiert sind).

Es gibt Dutzende anwendiger Heuristiken, die entweder einige Wörter ignorieren oder versuchen können, die Abfrage in kleinere zu zerbrechen und am meisten zu sammeln Beliebt Ergebnisse. Und all diese Lösungen können zugeschnitten und an Respekt geändert werden Machbare Wartezeiten von z. B. weniger als eine Sekunde? :D

Answer 2

MapReduce hat nichts mit Echtzeit zu tun. Es handelt sich um ein batchorientiertes Verarbeitungsrahmen, das für einige Offline-Aufgaben wie ETL und Indexgebäude geeignet ist. Google hat jetzt für die meisten Jobs von MapReduce abgelehnt, und selbst das Hadoop -Ökosystem tut dasselbe.

Die Antwort auf eine geringe Latenz besteht im Allgemeinen darin, vorberechtigte Indizes im Speicher zu halten. Alles, was die Festplatte berührt, ist schwer zu machen und zu skalieren. So wie Hadoop-basierte SQL-Motoren mit neuer Generation mögen Impala Erhalten Sie so viel Geschwindigkeit im Vergleich zu MapReduce-basierter Infrastruktur wie Bienenstock, zum Beispiel.

Suchinfrastruktur kann die Ergebnisse jeder einzelnen Abfrage nicht zwischenspeichern. Es kann jedoch sicherlich Intermediate -Ergebnisse oder umfassendere Ergebnisse für Top -Abfragen zwischenspeichern. Mit ein wenig Caching können Sie Ergebnisse für eine bedeutende Minderheit aller Abfragen erzielen.

Die Suche wird auch auf Server aufgeteilt. So kann eine Maschine auf 100 delegieren, um einen Teil des Ergebnisses zu erhalten und sie dann zu kombinieren.

Sie können auch mit einem gewissen Annäherungsgrad davonkommen. Google bildet buchstäblich tausend Seiten Suchergebnisse. Es muss nur die erste Seite über rechts bekommen.

Denken Sie daran, dass Google hat Millionen von Computern rund um den Globus. Ihre Abfragen gehen geografisch in einem Rechenzentrum in Ihrer Nähe und dienen nur Ihrer Geographie. Dies reduziert den größten Teil der Latenz, nämlich das Netzwerk und keine Verarbeitungszeit im Rechenzentrum.

Answer 3

MapReduce wird bei der Suche nicht verwendet. Es wurde vor langer Zeit verwendet, um den Index zu erstellen; Aber es handelt inkrementell statt batchorientiert.

Die Suche in Google funktioniert größtenteils gleich. Es funktioniert bei Lucene und elastischer Suche, mit Ausnahme vieler fein abgestimmter zusätzlicher Gewichtung und Optimierungen. Aber im Herzen werden sie irgendeine Form eines verwenden Umgekehrter Index. Mit anderen Worten, sie tun es nicht Suchen Sie mehrere Terabyte, wenn Sie eine Suchabfrage eingeben (auch wenn sie nicht zwischengespeichert wird). Sie betrachten die tatsächlichen Dokumente wahrscheinlich überhaupt nicht. Sie verwenden jedoch eine Nachschlagetabelle, in der die Dokumente mit Ihrem Abfragebegriff übereinstimmen (mit Stamm, Missschreibungen, Synonymen usw. alle vorverarbeitet). Sie holen wahrscheinlich die ab aufführen Von den Top 10000 -Dokumenten für jedes Wort (10K Ganzzahlen - nur ein paar KB!) Und die besten Übereinstimmungen davon berechnen. Nur wenn es in diesen Listen keine guten Übereinstimmungen gibt, erweitern sie auf die nächsten solchen Blöcke usw.

Abfragen nach allgemeinen Wörtern können leicht zwischengespeichert werden. Und über die Vorverarbeitung können Sie eine Liste der Top 10K -Ergebnisse erstellen und sie dann nach dem Benutzerprofil erneut übertragen. Auch durch eine "exakte" Antwort zu erhalten. Das Betrachten der Top 10K -Ergebnisse ist wahrscheinlich ausreichend. Es gibt keine korrekte Antwort; Und wenn ein besseres Ergebnis irgendwo an Position 10001 vermisst wird, wird oder bemerken es niemand (oder sorgen Sie sich). Es war wahrscheinlich bereits in der Vorverarbeitung eingestuft und hätte es nicht in die Top 10 geschafft, die dem Benutzer am Ende präsentiert werden (oder die Top 3, der Benutzer tatsächlich ansieht)

Seltene Begriffe hingegen sind auch keine große Herausforderung - eine der Listen enthält nur einige passende Dokumente, und Sie können sofort alle anderen verwerfen.

Ich empfehle, diesen Artikel zu lesen:

Die Anatomie einer groß angelegten hypertextuellen Web-Suchmaschine
Sergey Brin und Lawrence Page
Informatikabteilung, Stanford University, Stanford, CA 94305
http://infolab.stanford.edu/~backrub/google.html

Und ja, das sind die Google -Gründer, die dies geschrieben haben. Es ist nicht der neueste Zustand, aber es wird bereits in großem Maßstab funktionieren.