Eine Tatsache, die ich immer als lustig empfunden habe, ist, dass Google tatsächlich von Bioinformatik betrieben wird ('Kay, ich finde das lustig, weil ich ein Bioinf… Ding bin). Lassen Sie mich erklären.
Die Bioinformatik hatte schon früh die Herausforderung, sehr schnell nach kleinen Texten in gigantischen Strings zu suchen. Für uns ist die „gigantische Saite“ natürlich DNA. Oft keine einzelne DNA, sondern eine Datenbank mit mehreren DNAs verschiedener Arten / Individuen. Die kleinen Texte sind Proteine oder ihr genetisches Gegenstück, ein Gen. Die meisten ersten Arbeiten von Computerbiologen beschränkten sich darauf, Homologien zwischen Genen zu finden. Dies geschieht, um die Funktion neu gefundener Gene festzustellen, indem Ähnlichkeiten mit bereits bekannten Genen festgestellt werden.
Jetzt werden diese DNA-Strings tatsächlich sehr groß und die (verlustbehaftete!) Suche muss äußerst effizient durchgeführt werden. Der größte Teil der modernen Theorie der String-Suche wurde daher im Kontext der Computerbiologie entwickelt.
Vor einiger Zeit war die konventionelle Textsuche jedoch erschöpft. Es war ein neuer Ansatz erforderlich, der es ermöglichte, große Zeichenfolgen in sublinearer Zeit zu durchsuchen, dh ohne jedes einzelne Zeichen zu betrachten. Es wurde festgestellt, dass dies gelöst werden kann, indem die große Zeichenfolge vorverarbeitet und eine spezielle Indexdatenstruktur darüber erstellt wird. Es wurden viele verschiedene solcher Datenstrukturen vorgeschlagen. Jeder hat seine Stärken und Schwächen, aber es gibt eine, die besonders bemerkenswert ist, weil sie eine Suche in konstanter Zeit ermöglicht. In den Größenordnungen, in denen Google tätig ist, ist dies nicht mehr unbedingt der Fall, da der Lastausgleich zwischen Servern, die Vorverarbeitung und einige andere anspruchsvolle Dinge berücksichtigt werden müssen.
Im Wesentlichen ermöglicht der sogenannte Q-Gramm-Index eine Suche in konstanter Zeit. Einziger Nachteil: Die Datenstruktur wird lächerlich groß. Um eine Suche nach Zeichenfolgen mit bis zu q Zeichen (daher der Name) zu ermöglichen, ist im Wesentlichen eine Tabelle erforderlich, die ein Feld für jede mögliche Kombination von q Buchstaben enthält ( dh q S , wobei S die Größe des Alphabets ist sagen wir 36 (= 26 + 10)). Außerdem muss für jede Buchstabenposition in der indizierten Zeichenfolge ein Feld vorhanden sein (oder im Fall von Google für jede Website).
Um die schiere Größe zu mildern, Google wird wahrscheinlich mehrere Indizes verwenden (in der Tat, sie tun , zu bieten Dienstleistungen wie Rechtschreibkorrektur). Die obersten funktionieren nicht auf Zeichenebene, sondern auf Wortebene. Dies reduziert q, aber es macht S unendlich größer, so dass sie Hashing- und Kollisionstabellen verwenden müssen, um mit der unendlichen Anzahl verschiedener Wörter fertig zu werden.
Auf der nächsten Ebene verweisen diese Hash-Wörter auf andere Indexdatenstrukturen, die wiederum Hash-Zeichen auf Websites verweisen.
Kurz gesagt, diese Q- Gramm-Indexdatenstrukturen sind wohl der zentralste Teil des Google-Suchalgorithmus. Leider gibt es keine guten nichttechnischen Dokumente, die erklären, wie q- Gramm-Indizes funktionieren. Die einzige Veröffentlichung, die ich kenne und die eine Beschreibung der Funktionsweise eines solchen Index enthält, ist… leider meine Bachelorarbeit .
Hier sind einige der großartigen Antworten und Hinweise:
quelle
Sie haben gute, verteilte Algorithmen implementiert, die auf einer großen Menge an Hardware ausgeführt werden.
quelle
Eine der wichtigsten Verzögerungen ist, dass Webserver Ihre Anfrage an den Webserver senden und die Antwort zurückgeben. Diese Latenz ist an die Lichtgeschwindigkeit gebunden, die auch Google einhalten muss. Sie haben jedoch Rechenzentren auf der ganzen Welt. Infolgedessen ist der durchschnittliche Abstand zu einem von ihnen geringer. Dies hält die Latenz niedrig. Sicher, die Differenz wird in Millisekunden gemessen, aber es ist wichtig, ob die Antwort innerhalb von 1000 Millisekunden eintreffen muss.
quelle
Jeder weiß, dass es daran liegt, dass sie natürlich Tauben benutzen !
Oh ja, das und Mapreduce.
quelle
Sie haben so ziemlich eine lokale Kopie des Internets, die auf Tausenden von PCs in benutzerdefinierten Dateisystemen zwischengespeichert ist.
quelle
Google stellt die Besten der Besten ein. Einige der klügsten IT-Mitarbeiter arbeiten bei Google. Sie haben praktisch unendlich viel Geld, um auf Hardware und Ingenieure zu werfen.
Sie verwenden hochoptimierte Speichermechanismen für die Aufgaben, die sie ausführen.
Sie haben geografisch lokalisierte Serverfarmen.
quelle
Ein Versuch, eine allgemeine Liste zu erstellen (dies hängt nicht davon ab, ob Sie Zugriff auf die internen Tools von Google haben):
quelle
Auf der Google Research-Homepage finden Sie einige Hinweise zu den Forschungsberichten, die von einigen Google-Mitarbeitern verfasst wurden. Sie sollten mit der Erläuterung des Google-Dateisystems und des Map / Reduce-Algorithmus beginnen , um zu verstehen, was hinter den Google-Seiten vor sich geht.
quelle
Dieser Link ist auch sehr informativ Hinter den Kulissen einer Google-Abfrage
quelle
Hardware.
Viele, viele Hardware. Sie verwenden massive Cluster von Standard-PCs als Serverfarm.
quelle
TraumaPony ist richtig. Tonnenweise Server und intelligente Architektur für Load Balancing / Caching und Voila können Sie Abfragen in weniger als 1 Sekunde ausführen. Es gab viele Artikel im Internet, die die Architektur von Google Services beschrieben. Ich bin sicher, Sie können sie über Google finden :)
quelle
HenryR ist wahrscheinlich richtig.
Map Reduce spielt für die Suche selbst keine Rolle, sondern wird nur zur Indizierung verwendet. Überprüfen Sie dieses Videointerview mit den Erfindern von Map Reduce .
quelle
Ein weiterer Grund scheint zu sein, dass sie den TCP-Slow-Start-Algorithmus betrügen.
http://blog.benstrong.com/2010/11/google-and-microsoft-cheat-on-slow.html
quelle
Und Algorithmen , die diese Hardware-Leistung nutzen können. Wie zum Beispiel mapreduce .
quelle
Wenn Sie an weiteren Details zur Funktionsweise des Google-Clusters interessiert sind, empfehle ich diese Open-Source-Implementierung des HDFS .
Es basiert auf Mapreduce von Google.
quelle
Mehrstufiges Speichern, Verarbeiten und Abrufen von Daten
EFFIZIENTE Verteilung (100 von 1000 Maschinen) der oben genannten Aufgaben
Guter Rahmen zum Speichern der Rohdaten und der verarbeiteten Ergebnisse
Guter Rahmen, um die Ergebnisse abzurufen
Wie genau dies alles gemacht wird, wird durch alle Links zusammengefasst, die Sie in der Fragenübersicht haben
quelle