Geben Sie ElasticSearch auf, GitHub baut eine Suchmaschine von Grund auf! Wie durchsucht man das 200-Millionen-Code-Warehouse?

Im Dezember 2021 veröffentlichte GitHub eine Technologievorschau und führte eine umfassende Optimierung durch, um das Problem „Es kann nichts gefunden werden“ in der GitHub-Codesuche anzugehen.

Im November letzten Jahres veröffentlichte der Beamte auf der GitHub Universe Developer Conference die öffentliche Betaversion, die hauptsächlich die Probleme von Entwicklern löst, Code zu finden, zu lesen und zu navigieren.

Auf der Konferenz stellte jemand eine wichtige Frage: Was ist das Prinzip hinter der Verbesserung der „Codesuche“?

Kürzlich hat GitHub einen Blog veröffentlicht, in dem die technischen Prinzipien und die Systemarchitektur hinter dem neuen Modell ausführlich erläutert werden.

Erstellen Sie eine GitHub-Suchmaschine von Grund auf

Um es einfach auszudrücken: Hinter der neuen Suchmaschine steckt ein von Forschern in Rust neu geschriebenes Rad, das speziell für die Codesuche optimiert wurde und den Codenamen Blackbird trägt.

Auf den ersten Blick mag der Aufbau einer Suchmaschine von Grund auf wie eine rätselhafte Entscheidung erscheinen:

Warum bei Null anfangen? Gibt es nicht bereits viele Open-Source-Lösungen? Warum noch mehr Energie verschwenden, um etwas Neues zu bauen?

Tatsächlich hat GitHub versucht, bestehende Lösungen zu nutzen, um das Suchproblem zu lösen, aber leider lassen sich Produkte, die für die allgemeine Textsuche verwendet werden, nur schwer an die „Code“-Suche anpassen. Da die Indizierungsgeschwindigkeit zu langsam ist, ist die Benutzererfahrung schlecht, die Anzahl der erforderlichen Server groß und die Betriebskosten zu hoch.

Obwohl es einige neuere Open-Source-Projekte gibt, die speziell auf die Codesuche zugeschnitten sind, sind sie immer noch nicht für eine so große Codebasis wie GitHub geeignet.

Basierend auf den oben genannten Beobachtungen haben sich GitHub-Entwickler drei Hauptziele und Schlussfolgerungen gesetzt:

1. Benutzer können während des Suchvorgangs eine neue Erfahrung machen, indem sie durch Suchen, Durchsuchen usw. iterieren. Navigieren und Code lesen, um Antworten zu erhalten.

2. Es gibt viele Unterschiede zwischen der Codesuche und der allgemeinen Textsuche.

Entwickler schreiben Code, der von Maschinen verstanden werden soll, daher sollte der Codesuchprozess die Struktur und Korrelation des Codes nutzen und Benutzer können nach Satzzeichen (z. B. Punkten, offenen Klammern und anderen Operatoren) suchen den Code); entfernen Sie keine Stoppwörter aus der Abfrage und verwenden Sie keine regulären Ausdrücke.

3. Die Größe von GitHub stellt eine einzigartige Herausforderung dar.

Die alte Version der Suchmaschine verwendete Elasticsearch. Bei der ersten Bereitstellung dauerte es mehrere Monate, bis der gesamte Code auf GitHub indiziert war (damals gab es etwa 8 Millionen Code-Repositorys), jetzt jedoch das Code-Repository Die Zahl hat 200 Millionen überschritten, und diese Codes sind nicht statisch: Entwickler reichen ständig ein, und der Code ändert sich ständig, was für den Aufbau einer Suchmaschine eine große Herausforderung darstellt.

Derzeit in der Betaphase können Benutzer etwa 45 Millionen Codebasen mit 115 TB Code und 15,5 Milliarden Dokumenten durchsuchen.

Zusammenfassend lässt sich sagen, dass fertige Dinge den Bedarf nicht decken können, also machen Sie etwas von Grund auf neu.

Grep ausprobieren?

Bei der Suche ist „grep“ ein häufig verwendetes Werkzeug. Durch die Eingabe eines Ausdrucks können Sie den Text abgleichen. Warum also nicht einfach grep verwenden, um das Suchproblem mit roher Gewalt zu lösen?

Um diese Frage zu beantworten, können Sie zunächst berechnen, wie lange es dauert, 115 TB Code mit Ripgrep abzugleichen.

Auf einem Computer mit einer 8-Core-Intel-CPU kann ripgrep eine reguläre Ausdrucksabfrage für eine 13-GB-Datei im Speicher in 2,769 Sekunden (~0,6 GB/Sek./Kern) ausführen.

Nach einer einfachen Berechnung können wir feststellen, dass diese Methode für die aktuellen Massendaten nicht durchführbar ist: Unter der Annahme, dass das Codesuchprogramm auf einem Cluster von 32 Servern ausgeführt wird, verfügt jeder Computer über 64 Kerne, selbst wenn alle 115 TB Code darin gesteckt sind Der Speicher ist leer, und alles läuft reibungslos. Es dauert etwa 96 Sekunden, um „eine“ Abfrage auszuführen, und es kann nur eine in der Warteschlange stehen, was bedeutet, dass sie nur verwendet werden kann, wenn der QPS beträgt . grep

Brute Force funktioniert also nicht, Sie können also nur zuerst einen Index erstellen.

Suchindex (Suchindex)

Erst nachdem die relevanten Informationen in Form eines Indexes vorberechnet wurden, kann die Suchmaschine bei der Abfrage schnell reagieren der invertierte Index (invertierter Index), der Schlüssel ist ein Schlüsselwort und der Wert ist die geordnete Liste der Dokument-IDs, in denen das Wort vorkommt.

Bei der Codesuchaufgabe verwendeten die Forscher einen speziellen Typ eines invertierten Index, nämlich den Ngram-Index.

Ein ngram ist eine Zeichenfolge der Länge n. Beispielsweise bedeutet n = 3 (Trigame), dass die maximale Länge des Schlüssels nur 3 betragen kann. Bei längeren Schlüsseln muss er entsprechend der Länge von gekürzt werden 3, wie z. B. Limits. Es ist in lim, imi, mit und its unterteilt. Bei der Suche werden die Abfrageergebnisse mehrerer Schlüssel kombiniert und nach dem Zusammenführen wird die Liste der Dokumente erhalten, in denen die Zeichenfolge angezeigt wird

Die nächste Frage ist, wie man es relativ vernünftig gestalten kann. Schließen Sie die Indexerstellung innerhalb der erforderlichen Zeit ab.

Forscher stellten fest, dass Git inhaltsadressiertes Hashing verwendet und es tatsächlich ziemlich viele doppelte Inhalte auf GitHub gibt. Daher schlugen die Forscher die folgenden zwei Methoden zum Erstellen von Indizes vor.

1. Shard nach Git-Blob-Objekt-ID bietet eine gute Möglichkeit, Dokumente gleichmäßig auf Shards zu verteilen und Duplikate zu vermeiden, während die Anzahl der Shards jederzeit nach Bedarf erweitert werden kann.

2. Modellieren Sie den Index als Baum und verwenden Sie Differenzkodierung (Delta-Kodierung), um die Anzahl der Crawls zu reduzieren und die Metadaten im Index zu optimieren, wobei die Metadaten die Liste der Speicherorte enthalten, an denen das Dokument angezeigt wird ( welcher Pfad, Zweig und Repositorys) und Informationen zu diesen Objekten (Repository-Name, Besitzer, Sichtbarkeit usw.). Bei einigen beliebten Repositories kann die Menge an Metadaten recht groß sein.

GitHub hat außerdem ein System entwickelt, um die Abfrageergebnisse mit dem übermittelten Code konsistent zu halten.

Wenn ein Benutzer die Codebasis durchsucht, während ein Teammitglied Code pusht, sollten die neu festgeschriebenen Dokumente nicht in die Suchergebnisse aufgenommen werden, bis das System diese Dokumente vollständig verarbeitet hat. Blackbird macht die Festschreibungsabfragekonsistenz zu einem Kernbestandteil Design.

Blackbird

Das Folgende ist das Architekturdiagramm der Blackbird-Suchmaschine.

Zuerst stellt Kafka Ereignisse zur Verfügung, um den Inhalt des Index zu spezifizieren, und dann wird es eine große Anzahl von Crawler-Programmen geben, die mit Git interagieren, einschließlich eines Dienstes, der erneut Symbole aus dem Code extrahiert Verwenden Sie Kafka, um jeden Shard zu indizieren und das Zieldokument abzurufen.

Obwohl das System nur auf Ereignisse wie „Git Push“ reagiert, um Änderungen und ähnliche Ereignisse abzurufen, ist einige zusätzliche Arbeit erforderlich, um alle Codebasen zum ersten Mal aufzunehmen.

Ein Hauptmerkmal dieses Systems ist die Optimierung der anfänglichen Aufnahmereihenfolge, um die Vorteile der inkrementellen Kodierung voll auszunutzen.

GitHub verwendet eine neue probabilistische Datenstruktur, um die Ähnlichkeit von Codebasen darzustellen, und die Reihenfolge der Aufnahme wird aus einer horizontalen sequentiellen Durchquerung eines minimalen Spannbaums des Codebasis-Ähnlichkeitsdiagramms berechnet.

Basierend auf der optimierten Aufnahmereihenfolge besteht der Konstruktionsprozess des Deltabaums darin, jede Codebasis von ihrer übergeordneten Codebasis zu unterscheiden. Dies bedeutet auch, dass das System nur Blobs crawlen muss, die für die aktuelle Codebasis eindeutig sind Enthält: Holen Sie sich den Blob-Inhalt von Git, analysieren Sie ihn, um Symbole zu extrahieren, und erstellen Sie ein Dokument, das als Eingabe für den Index verwendet wird.

Veröffentlichen Sie diese Dateien dann in einem anderen Kafka-Thema, in dem auch die Daten zwischen Shards aufgeteilt werden. Jeder Shard verwendet eine Kafka-Partition im Thema.

Durch die Verwendung von Kafka können Indizierung und Crawling entkoppelt werden, und das Sortieren von Nachrichten in Kafka kann auch zu konsistenten Abfrageergebnissen führen.

Die Indexer-Shards finden dann diese Dokumente und erstellen den Index: Sie tokenisieren Inhalte, Symbole und Pfade, um Ngram-Indizes und andere nützliche Indizes (Sprache, Eigentümer, Codebasis usw.) zu erstellen, und schreiben die Ergebnisse auf die Festplatte.

Komprimieren Sie abschließend die Shards und reduzieren Sie den kleineren Index in einen größeren Index, damit die Abfrage effizienter und die Bewegung einfacher ist.

Abfragelebenszyklus

Mit dem Index wird die Verfolgung von Abfragen durch das System einfacher. Jede Abfrage ist ein regulärer Ausdruck, der als „/arguments?/org:rails lang:Ruby“ geschrieben werden kann ein von der Rails-Organisation in Ruby-Sprache geschriebener Code.

Es gibt auch einen Dienst zwischen GitHub.com und Shards, der dafür verantwortlich ist, den Empfang von Benutzeranfragen zu koordinieren, die Anfragen an jeden Host im Suchcluster zu verteilen und schließlich Redis zum Verwalten der Festplatte zu verwenden Speicherplatz (Kontingente) und einige Zugriffskontrolldaten zwischenspeichern.

Das Frontend akzeptiert eine Benutzeranfrage und leitet sie an Blackbird weiter, der die Anfrage dann in einen abstrakten Syntaxbaum analysiert, sie in eine kanonische Sprach-ID umschreibt und Berechtigungen und Bereiche für zusätzliche Klauseln markiert.

Der nächste Schritt besteht darin, n gleichzeitige Anfragen zu senden: eine an jeden Shard im Suchcluster. Die im System festgelegte Sharding-Strategie besteht darin, Abfrageanfragen an jeden Shard im Cluster zu senden.

Führen Sie dann einige Transformationen der Abfrage für jeden einzelnen Shard durch, um die Informationen im Index zu finden.

Abschließend werden die von allen Shards zurückgegebenen Ergebnisse aggregiert, nach Punktzahl neu geordnet, gefiltert (Berechtigungen erneut prüfen) und zu den Top 100 zurückgekehrt, und dann führt das Frontend von GitHub.com eine Syntaxhervorhebung durch , Begriffshervorhebung und Paginierung. Schließlich können wir die Ergebnisse auf der Seite präsentieren.

Bei der tatsächlichen Verwendung beträgt die p99-Antwortzeit eines einzelnen Shards etwa 100 ms. Aus Gründen wie der Aggregation von Antworten, der Überprüfung von Berechtigungen und der Syntaxhervorhebung ist die Gesamtantwortzeit jedoch länger.

Eine Abfrage belegt einen CPU-Kern für 100 Millisekunden auf dem Indexserver, sodass die Obergrenze eines 64-Kern-Hosts bei etwa 640 Abfragen pro Sekunde liegt. Im Vergleich zur grep-Methode (0,01 QPS) kann man sagen, dass diese Methode recht schnell ist.

Zusammenfassung

Nachdem Sie die vollständige Systemarchitektur vorgestellt haben, können Sie das Ausmaß des Problems noch einmal untersuchen.

Die Ingest-Pipeline von GitHub kann etwa 120.000 Dokumente pro Sekunde veröffentlichen, sodass die Verarbeitung aller 15,5 Milliarden Dokumente etwa 36 Stunden dauern wird. Allerdings kann die Delta-Indizierung die Anzahl der Dokumente, die gecrawlt werden müssen, um mehr als 50 % reduzieren Der gesamte Prozess zur Neuindizierung des gesamten Korpus dauert etwa 18 Stunden.

In Bezug auf die Indexskala wurden einige Durchbrüche erzielt. Das anfängliche Inhaltsvolumen betrug 115 TB. Nach dem Löschen doppelter Inhalte und der Verwendung einer inkrementellen Indizierung wurde die Inhaltsmenge auf etwa 28 TB reduziert.

Und der Index selbst ist nur 25 TB groß, was nicht nur alle Indizes (einschließlich Ngrams) umfasst, sondern auch komprimierte Kopien aller eindeutigen Inhalte, was auch bedeutet, dass die gesamte Indexgröße einschließlich Inhalt nur etwa ein Viertel des Originals beträgt Datengröße eins!

Das obige ist der detaillierte Inhalt vonGeben Sie ElasticSearch auf, GitHub baut eine Suchmaschine von Grund auf! Wie durchsucht man das 200-Millionen-Code-Warehouse?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!