Ich bin mir nicht sicher, ob MapReduce das Problem löst, aber es wäre sicherlich nicht MapReduce allein, um all diese Fragen zu lösen, die Sie aufgeworfen haben. Hier sind jedoch wichtige Dinge zu beachten, die es möglich machen, bei Abfragen von all diesen TBs von Daten auf verschiedenen Computern eine so geringe Latenz zu haben:
- Verteiltes Rechnen: Verteilt zu sein bedeutet nicht, dass die Indizes einfach auf verschiedenen Computern verteilt werden. Sie werden tatsächlich entlang verschiedener Cluster repliziert, was es vielen Benutzern ermöglicht, unterschiedliche Abfragen mit geringer Abrufzeit durchzuführen (ja, große Unternehmen können sich das leisten von Maschinen);
- Caching: Caches reduzieren die Ausführungszeit erheblich, sei es für den Crawling-Schritt, für das Abrufen von Seiten oder für das Ranking und die Ausstellung von Ergebnissen.
- Viele Optimierungen: Alle oben genannten und sehr effizienten Algorithmen / Lösungen können nur dann effektiv sein, wenn die Implementierung auch effizient ist. Es gibt unzählige (fest codierte) Optimierungen, z. B. Referenzort, Komprimierung, Caching. Alle von ihnen sind normalerweise auf verschiedene Teile der Verarbeitung anwendbar.
In Anbetracht dessen versuchen wir, Ihre Fragen zu beantworten:
Ich halte es jedoch für unmöglich, die Ergebnisse jeder einzelnen möglichen Abfrage zu indizieren
Ja, es wäre und tatsächlich unmöglich, Ergebnisse für jede einzelne mögliche Abfrage zu haben . Es gibt unendlich viele Begriffe auf der Welt (selbst wenn Sie davon ausgehen, dass nur richtig geschriebene Begriffe eingegeben werden), und es gibt eine exponentielle Anzahl von Abfragen aus diesen n -> infBegriffen ( 2^n). Was wird also gemacht? Caching. Aber wenn es so viele Abfragen / Ergebnisse gibt, welche müssen zwischengespeichert werden? Caching-Richtlinien. Die häufigsten / beliebtesten / für den Benutzer relevanten Abfragen sind die zwischengespeicherten.
Wäre die Hardwarelatenz in Googles Hardware nicht riesig? Auch wenn die Daten in Google alle in TB / s-SSDs gespeichert waren
Heutzutage denken die Leute bei solch hoch entwickelten Prozessoren, dass jede mögliche Aufgabe, die innerhalb einer Sekunde (oder weniger) erledigt werden muss und die so viele Daten verarbeitet, von extrem leistungsstarken Prozessoren mit mehreren Kernen und viel Speicher verarbeitet werden muss. Allerdings ist die eine Sache herrschenden ist Markt Geld, und die Investoren sind in verschwenden sie nicht interessiert. Was wird also gemacht?
Die Präferenz besteht 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 der vorhandenen Cluster senkt. Und ja, es funktioniert. Der Hauptengpass läuft immer auf die Festplatte hinaus, wenn Sie einfache Leistungsmessungen in Betracht ziehen . Aber wenn es so viele Maschinen gibt, kann man es sich leisten, Dinge in den Hauptspeicher zu laden, anstatt auf Festplatten zu arbeiten.
Speicherkarten sind für uns, bloße Menschen, teuer , aber für Unternehmen, die viele solcher Karten gleichzeitig kaufen, sehr billig. Da es nicht teuer ist, ist es kein Problem, bei Bedarf über viel Speicher zu verfügen, um Indizes zu laden und Caches zur Hand zu haben. Und da es so viele Maschinen gibt, sind keine superschnellen Prozessoren erforderlich, da Sie Anfragen an verschiedene Orte richten können und Gruppen von Maschinen für die Bearbeitung bestimmter geografischer Regionen zuständig sind , was ein spezialisierteres Daten-Caching und eine noch bessere Reaktion ermöglicht mal.
Hilft MapReduce bei der Lösung dieses Problems?
Obwohl ich nicht denke, dass die Verwendung oder Nichtverwendung von MapReduce Informationen in Google einschränkt, bin ich mit diesem Punkt nicht vertraut. Die Implementierung von MapReduce durch Google (was sicherlich nicht Hadoop ist) muss jedoch viele Optimierungen aufweisen, von denen viele die oben diskutierten Aspekte betreffen. Die Architektur von MapReduce hilft wahrscheinlich dabei, die physische Verteilung der Berechnungen zu bestimmen. Es sind jedoch noch viele andere Punkte zu berücksichtigen, um eine solche Geschwindigkeit bei der Abfragezeit zu rechtfertigen.
Okay, ich verstehe, dass beliebte Suchanfragen im Speicher zwischengespeichert werden können. Aber was ist mit unpopulären Suchanfragen?
Die folgende Grafik zeigt eine Kurve, wie die Arten von Abfragen auftreten. Sie können sehen, dass es drei Hauptarten von Suchvorgängen gibt, von denen jede ungefähr 1/3 des Abfragevolumens enthält (Bereich unter der Kurve). Die Handlung zeigt das Potenzgesetz und verstärkt die Tatsache, dass kleinere Abfragen am beliebtesten sind. Das zweite Drittel der Abfragen kann noch bearbeitet werden, da sie nur wenige Wörter enthalten. Die Menge der sogenannten obskuren Abfragen , die normalerweise aus nicht erfahrenen Benutzerabfragen bestehen, ist jedoch kein vernachlässigbarer Teil der Abfragen.
Und es gibt Raum für neuartige Lösungen. Da es sich nicht nur um eine oder zwei Abfragen handelt (sondern um ein Drittel davon), müssen sie relevante Ergebnisse haben. Wenn Sie in einer Google-Suche etwas viel zu Dunkles eingeben, dauert es nicht länger, eine Ergebnisliste zurückzugeben, sondern zeigt Ihnen höchstwahrscheinlich etwas an, auf das Sie schließen möchten. Oder es kann einfach angegeben werden, dass es kein Dokument mit solchen Begriffen gab - oder sogar Ihre Suche auf 32 Wörter reduzieren (was mir gerade in einem zufälligen Test hier passiert ist).
Es gibt Dutzende anwendbarer Heuristiken, die entweder darin bestehen, einige Wörter zu ignorieren oder zu versuchen, die Abfrage in kleinere zu unterteilen und die beliebtesten Ergebnisse zu erzielen . Und all diese Lösungen können so angepasst und optimiert werden, dass mögliche Wartezeiten von beispielsweise weniger als einer Sekunde eingehalten werden. : D.
MapReduce hat nichts mit Echtzeit zu tun. Es ist ein stapelorientiertes Verarbeitungsframework, das für einige Offline-Aufgaben wie ETL und Indexerstellung geeignet ist. Google hat MapReduce für die meisten Jobs inzwischen verlassen, und sogar das Hadoop-Ökosystem tut dies auch.
Die Antwort auf eine geringe Latenz besteht im Allgemeinen darin, vorberechnete Indizes im Speicher zu halten. Alles, was die Festplatte berührt, ist schwer schnell und skalierbar zu machen. Auf diese Weise erhalten Hadoop-basierte SQL-Engines der neueren Generation wie Impala im Vergleich zu MapReduce-basierten Infrastrukturen wie beispielsweise Hive so viel Geschwindigkeit .
Die Suchinfrastruktur kann die Ergebnisse jeder einzelnen Abfrage nicht zwischenspeichern. Aber es kann sicher Zwischenergebnisse oder vollständigere Ergebnisse für Top-Abfragen zwischenspeichern. Mit ein wenig Caching können Sie Ergebnisse für eine signifikante Minderheit aller Abfragen bereitstellen.
Die Suche ist auch auf mehrere Server verteilt. Eine Maschine kann also an 100 delegieren, um jeweils einen Teil des Ergebnisses zu erhalten und diese dann zu kombinieren.
Sie können auch mit einer gewissen Annäherung davonkommen. Google bildet nicht buchstäblich tausend Seiten mit Suchergebnissen. es muss nur die erste Seite ungefähr richtig machen.
Denken Sie daran, dass Google weltweit über Millionen von Computern verfügt . Ihre Anfragen werden an ein Rechenzentrum in Ihrer Nähe gesendet, das nur Ihrer geografischen Region dient. Dies reduziert den größten Teil der Latenz, die das Netzwerk und nicht die Verarbeitungszeit im Rechenzentrum ist.
quelle
MapReduce wird bei der Suche nicht verwendet. Es wurde vor langer Zeit verwendet, um den Index zu erstellen; Es handelt sich jedoch um ein Framework für die Stapelverarbeitung, und der größte Teil des Webs ändert sich nicht ständig. Daher sind die neueren Architekturen alle inkrementell und nicht stapelorientiert.
Die Suche in Google funktioniert weitgehend genauso wie in Lucene und Elastic Search, mit Ausnahme vieler fein abgestimmter zusätzlicher Gewichtungen und Optimierungen. Aber im Kern werden sie eine Form eines invertierten Index verwenden . Mit anderen Worten, sie durchsuchen nicht mehrere Terabyte, wenn Sie eine Suchabfrage eingeben (auch wenn diese nicht zwischengespeichert ist). Sie sehen sich wahrscheinlich überhaupt nicht die tatsächlichen Dokumente an. Sie verwenden jedoch eine Nachschlagetabelle, in der aufgelistet ist, welche Dokumente zu Ihrem Abfragebegriff passen (mit Vorverarbeitung, Rechtschreibfehlern, Synonymen usw.). Sie rufen wahrscheinlich die Liste der 10000 besten Dokumente für jedes Wort ab (10.000 Ganzzahlen - nur ein paar KB!) Und berechnen daraus die besten Übereinstimmungen. Nur wenn diese Listen keine guten Übereinstimmungen enthalten, werden sie auf die nächsten derartigen Blöcke usw. erweitert.
Abfragen für gebräuchliche Wörter können einfach zwischengespeichert werden. Über die Vorverarbeitung können Sie eine Liste der Top-10k-Ergebnisse erstellen und diese dann entsprechend dem Benutzerprofil neu bewerten. Es gibt auch nichts zu gewinnen, wenn man eine "genaue" Antwort berechnet. Ein Blick auf die Top-10k-Ergebnisse ist wahrscheinlich genug. es gibt keine richtige Antwort; und wenn irgendwo auf Position 10001 ein besseres Ergebnis verfehlt wird, wird es niemand wissen oder bemerken (oder sich darum kümmern). Es wurde wahrscheinlich bereits in der Vorverarbeitung herabgestuft und hätte es nicht in die Top 10 geschafft, die dem Benutzer am Ende präsentiert werden (oder in die Top 3, die der Benutzer tatsächlich betrachtet).
Seltene Begriffe sind dagegen auch keine große Herausforderung - eine der Listen enthält nur wenige übereinstimmende Dokumente, und Sie können alle anderen sofort verwerfen.
Ich empfehle diesen Artikel zu lesen:
Und ja, das sind die Google-Gründer, die das geschrieben haben. Es ist nicht der neueste Stand, aber es wird bereits in ziemlich großem Maßstab funktionieren.
quelle