Warum ist Codesuche so schwierig?
(blog.val.town)- Die Suche von Val Town basiert derzeit auf einer Postgres-ILIKE-Teilstringsuche, hat daher kaum Ranking und ist auch bei Abfragen mit mehreren Wörtern schwach, weshalb es viele Wünsche nach Verbesserungen gibt
- Regeln der Natural-Language-Suche wie Stopword-Entfernung, Stemming und Lemmatisierung können bei Code Variablennamen, Funktionsnamen und Tokengrenzen zerstören
- Die Postgres-Full Text Search könnte die Infrastruktur einfach halten, hatte in früheren Projekten aber Skalierungsprobleme, und auch Val Town testet die Grenzen eines Single-Node-Postgres aus
- Die sanft eingeführte v2-Suche nutzt eine auf pg_trgrm basierende Trigramm-Suche, doch anders als bei der RegEx-Suche ist es schwierig, das Ranking für freie Abfragen auf das gewünschte Niveau zu bringen
- Alternativen wie Elasticsearch, Meilisearch, Zoekt und ParadeDB gibt es, doch separate Infrastruktur, Betriebsaufwand und die Frage nach Hosting-Support bleiben Einschränkungen bei der Auswahl
Wo Val Towns Suche an ihre Grenzen stößt
- Die Suche von Val Town verwendet derzeit ILIKE von Postgres
- Wenn ein Suchbegriff im Code enthalten ist, erscheint das Ergebnis per Teilstringsuche
- Es gibt kaum Ranking, und Abfragen mit mehreren Wörtern werden nicht ordentlich unterstützt
- Eine bessere Suche ist bei Val Town eines der am häufigsten gewünschten Features
- An Verbesserungen wird gearbeitet, aber bisher wurde noch keine Lösung gefunden, die den Anforderungen entspricht
- Bisher haben sich folgende Rahmenbedingungen gezeigt
- Gängige Suchlösungen sind für natürliche Sprache ausgelegt
- Große Unternehmen, die Codesuche brauchen, investieren viel Zeit und Geld in eigene Suchsysteme
- Val Town hat bereits viele Daten und braucht daher eine Lösung, die gut skaliert
- Wenn statt Datenbank-Skalierung ein separater Suchdienst genutzt wird, sind Abwägungen bei Infrastruktur und Komplexität entscheidend
Warum Regeln der Natural-Language-Suche nicht zu Code passen
- Übliche Konfigurationen für Full Text Search (FTS) bringen standardmäßig Algorithmen für natürliche Sprachen wie Englisch mit
- Stopword-Entfernung: Entfernt vor der Indexierung sehr häufige Wörter wie „the“ oder „it“
- Stemming: Wandelt „running“ in „run“ um, damit es auch bei einer Suche nach „runs“ gefunden werden kann
- Lemmatisierung: Kann Synonyme durch gebräuchlichere Wörter ersetzen, sodass eine Suche nach „excellent“ auch Dokumente mit „great“ findet
- Werden dieselben Regeln auf Code angewendet, verschiebt sich die Bedeutung
- In TypeScript ist
thekein Stopword, sondern kann ein gültiger Variablenname sein, nach dem man suchen möchte - Wortgrenzen in Code unterscheiden sich von denen in natürlicher Sprache
- Selbst wenn man Stemming auf Funktionsnamen anwendet, sind sinnvolle Ergebnisse kaum zu erwarten
- In TypeScript ist
- Postgres
to_tsvector('english', ...)verändert den Originaltext bei der Indexierung natürlicher Sätze erheblichI am writing this example sentencewird etwa zu'exampl':5 'sentenc':6 'write':3
- Bei Code tritt das Tokenisierungsproblem noch deutlicher hervor
function stringifyNumber(a: number): string { return a.toString() }wird etwa zu'a.tostring':7 'function':1 'number':4 'return':6 'string':5 'stringifynumb':2indexiert- Wörter wie
functionbleiben erhalten, abera.toString()wird nicht in zwei Tokens getrennt, weil.standardmäßig keine Wortgrenze ist
Vor- und Nachteile der Postgres Full Text Search
- Postgres bietet die Erweiterung Full Text Search, und auch Val Towns Hosting-Anbieter Render unterstützt sie
- Val Town hat Postgres bisher intensiv genutzt, und Postgres gilt als gut dokumentierte Technologie mit gutem Hosting-Support
- Für ein kleines Team ist es wichtig, die Infrastruktur möglichst einfach zu halten, daher ist es attraktiv, bei Postgres zu bleiben, wenn sich das Problem damit lösen lässt
- Frühere Projekte mit FTS hatten allerdings Probleme bei Performance und Skalierung
- Observable ist letztlich zu Elasticsearch gewechselt
- Val Town hat viele vals und testet die Grenzen eines Single-Node-Postgres-Clusters aus
- Erfolgreiche Beispiele für den Einsatz von FTS bei Codesuche sind schwer zu finden, daher bleibt es eher eine Rückfalloption als die erste Wahl
Experimente mit der v2-Suche auf Basis von pg_trgrm
- Der von Val Town sanft eingeführte v2-Suchalgorithmus basiert auf
pg_trgrmvon Postgrespg_trgrmimplementiert in Postgres eine Trigramm-Suche
- Für Codesuche gibt es bereits erfolgreiche Beispiele für Trigramme
- Ein Artikel von Russ Cox aus dem Jahr 2012 beschreibt, wie Google Code Search Trigramm-Indizes und eine spezielle RegEx-Implementierung nutzte
- Auch GitHubs neues Codesuchsystem verwendet Trigramm-Suche
- Sourcegraph verfügt über ein von Google übernommenes trigrammbasiertes Suchwerkzeug
- Val Towns Postgres-
pg_trgrm-Ansatz ist stark von Stephen Gutekansts Artikel über die Indexierung lokaler Repositories mit Postgres beeinflusst - Die Implementierung verwendet auf der Spalte mit dem Suchtext einen GIN-Index mit
gin_trgm_ops pg_trgrmist eine gute Lösung für RegEx-Suche, passt aber weniger gut zu freieren Abfragen, wie sie bei Val Town meist vorkommen- Für das Suchranking wird word_similarity verwendet
- Es ist sehr schwierig, den Algorithmus auf ein halbwegs sinnvolles Ranking zu justieren
Optionen bei Suchmaschinen und operative Abwägungen
- Zu den geprüften Kandidaten gehören sowohl eigenständige Suchdienste als auch Postgres-Erweiterungen
- Meilisearch: eigenständig, Rust, 41k Stars
- Typesense: eigenständig, C++, 17k Stars
- Zoekt: eigenständig, Go, 406 Stars
- ParadeDB: Postgres-Erweiterung, Rust, 3.2k Stars
- Sonic: eigenständig, Rust, 19.4k Stars
- Es gibt zwar code-spezifische Werkzeuge, die meisten davon sind jedoch nicht öffentlich
- Die GitHub-Suche ist hervorragend, aber das Ergebnis eines dedizierten Teams mit echtem Zeitbudget
- Der von Sourcegraph gepflegte Zoekt-Fork ist interessant, aber sehr nischig und würde eine große neue Infrastrukturinvestition erfordern
- Elasticsearch könnte sich am Ende als unvermeidliche Lösung herausstellen
- Es bietet keine code-spezifische Verarbeitung, lässt sich aber nahezu unbegrenzt anpassen
- Belastend sind das Erlernen von Java-Memory-Tuning, die Einführung des ersten persistenten Disk-Storage in der Anwendung und die Pflege einer zusätzlichen Quelle der Wahrheit für Daten
- Mit Elasticsearch Cloud ließe sich der Wartungsaufwand möglicherweise senken
- Meilisearch wirkt als Alternative zu Elasticsearch vielversprechend
- Attraktiv ist die Rust-Basis
- In den eigenen Vergleichstexten scheint eher die Latenz als die Skalierbarkeit betont zu werden; ob die Infrastrukturlast wirklich geringer ist, bleibt unklar
- ParadeDB arbeitet ähnlich wie Elasticsearch, ist aber attraktiv, weil es „einfach Postgres“ ist
- Auf Render ist diese Erweiterung derzeit allerdings noch nicht verfügbar
Die Last kleiner Teams bei der Wahl von Suchinfrastruktur
- Codesuche ist schwieriger als englische Textsuche
- Kleine Teams haben ein starkes Interesse daran, die Infrastruktur einfach zu halten, die Einrichtung der Entwicklungsumgebung leicht zu machen und die Daten an einem Ort zu behalten
- Val Town möchte sich nicht vorschnell an eine Option binden, die laufende Pflege erfordert
- Dass mittelgroße und große Unternehmen nicht nur einen Such-„Service“, sondern ein ganzes Such-„Team“ haben, hat seinen Grund
1 Kommentare
Hacker-News-Kommentare
Ich bin bei Sourcegraph, und für große Größenordnungen braucht man das natürlich, aber wenn man Produktsuche nach Code zum ersten Mal einbaut, sollte man nicht von Anfang an mit einem Index starten, sondern On-the-fly-Suche empfehlen, bis man an Grenzen stößt
Wenn man nur die ersten N Ergebnisse finden muss, kann man den Ergebnisbuffer füllen, ohne alles bis zum Ende zu durchsuchen, daher trägt das überraschend lange. Ich würde mich auch gerne mit Leuten austauschen, die so etwas bauen, auch mit den Leuten von Val Town.
Sourcegraph hat früher die Wartung von Zoekt übernommen, und Livegrep sowie Hound waren in vielerlei Hinsicht mit der Größenordnung, die wir indexieren wollten, überfordert. Nachdem wir von einer alten, knarzenden OpenGrok-Installation zu Zoekt gewechselt sind, war der Unterschied sowohl bei der Indexierungsleistung als auch bei Suchleistung und Nutzbarkeit groß. Sourcegraph baut auf die von Zoekt bereitgestellte Codesuche noch deutlich ausgefeiltere Funktionen auf.
Zum Beispiel dachte ich bei GritQL(https://github.com/getgrit/gritql) immer, dass es für die Geschwindigkeit irgendwann einen Index brauchen würde, aber bisher hält es sich komplett mit On-the-fly-Suche erstaunlich gut.
Ohne Cache ist es viel einfacher, die Korrektheit aufrechtzuerhalten.
Dinge, die in den L2-Cache passen, laufen wirklich extrem schnell.
Codesuche ist wirklich schwierig, und eine gute Codesuchplattform macht das Leben viel einfacher
Wenn ich Google verlassen würde, wäre mir die interne Codesuche vermutlich das, was ich am meisten vermissen würde. Sie ist so gut in alle Arbeitsabläufe integriert – blaze-Ziele finden, guice-Bindings und so weiter –, dass ich mir kaum vorstellen kann, ohne sie zu arbeiten. Jedes Mal, wenn ich die GitHub-Suche benutze, merke ich ihren Wert noch stärker; nicht weil die GitHub-Suche schlecht wäre, sondern weil es grundsätzlich viel schwieriger ist, eine allgemeine Codesuchplattform zu bauen.
Ich nutze es derzeit persönlich nicht, aber es ist hervorragend und dürfte die meisten Anforderungen erfüllen. https://github.com/livegrep/livegrep
Es wäre schön, wenn man direkt im Suchfeld den Provider oder die Verwendungsstellen finden könnte.
Grundlegende Techniken der Codesuche werden Junior-Entwicklern nicht ausdrücklich gut beigebracht, scheinen aber eine Kernkompetenz zu sein, die man früh lernen sollte
Der empfohlene Ablauf ist, zuerst die überall verfügbare Suche wie Ctrl+F zu beherrschen und dann zu ripgrep(https://github.com/BurntSushi/ripgrep) überzugehen. Das ist weniger optional als vielmehr ein wirklich großartiges und leicht zu entdeckendes Werkzeug, und dass man dafür ein Terminal offen haben muss, ist für Einsteiger sogar eher gut. Wenn möglich, sollte man auch einen leistungsfähigen Kommandozeilen-Editor lernen; früher hätte ich Emacs empfohlen, heute empfehle ich die Standardversion von vim, die fast überall installiert ist. Denn damit kann man im selben Fenster grep ausführen und bearbeiten. Danach kann man sich mit
grep -r,grep -ri,grep -rilauch die Verhaltensweisen des alten grep aneignen, die ripgrep standardmäßig bietet, und schließlich, wenn man an die Grenzen von ripgrep stößt, zu einem echten spezialisierten, indexbasierten Codesuchwerkzeug wechseln.git grepbeim Durchsuchen von Git-Repositories außer der Geschwindigkeit hat.Ich bin überrascht, dass hound(https://github.com/hound-search/hound) nicht erwähnt wurde
Ich dachte, es sei eines der führenden Open-Source-Lösungen in diesem Bereich. Ich habe die Wikimedia-Instanz(https://codesearch.wmcloud.org/search/) genutzt und bin insgesamt zufrieden.
https://codesearch.wmcloud.org/search/?q=test&files=&exclude... braucht bei mir 13 Sekunden, um eine 55-MB-JSON-Antwort zu erzeugen, und dann noch ein paar Sekunden, um sie wieder ins DOM zu rendern. Für die Zoekt-JSON-API, die in neogrok verwendet wird, musste es unbedingt eine saubere Begrenzung der Suchantwortgröße geben, und genau das musste sichergestellt werden: https://github.com/sourcegraph/zoekt/pull/615
Hier liegt der Grund, warum Menschen, die IDEs und Entwicklerwerkzeuge bauen, seit Langem der Ansicht sind, dass man für eine wirklich gute Codesuche eine Compiler-Plattform öffnen muss.
Denn ein großer Teil der nötigen Arbeit besteht letztlich darin, die internen Repräsentationen zu rekonstruieren, die der Compiler verwendet. Gute Codesuche ist auch die Grundlage für Refactoring-Unterstützung, Autovervollständigung und viele übliche IDE-Funktionen. Natürlich ist das leichter gesagt als getan, weshalb bei Compiler-Entwicklern Werkzeuge oft nachrangig behandelt wurden; auch JetBrains hat diesen Fehler in der frühen Kotlin-Zeit gemacht und korrigiert ihn mit Kotlin 2.0 teilweise, um Dinge wie inkrementelle Kompilierung leichter zu unterstützen. Auch die Rust-Community kam vor einigen Jahren bei einer großen Anstrengung zur Verbesserung der IDE-Freundlichkeit zur gleichen Einsicht. IBM hat das früher in Eclipse richtig gut umgesetzt, und seitdem wurde das kaum eingeholt. IntelliJ war um zwei bis drei Größenordnungen langsamer, also der Unterschied zwischen Sekunden und Millisekunden. Eclipse hatte einen extrem schnellen inkrementellen Compiler für Java, der selbst bei einigen Syntaxfehlern noch Teile kompilieren konnte, und die Code-Repräsentation der IDE war an diesen Compiler angebunden. Wenn man durch einen Tippfehler einen Teil des Codes kaputtgemacht hat, wurden die betroffenen Dateien im gesamten Codebestand sofort mit roten Wellenlinien markiert, und nach dem Korrigieren des Tippfehlers verschwanden sie ohne Verzögerung wieder. Dafür braucht man ein Mapping zwischen Dateien und Syntaxbäumen, und Eclipse konnte das, weil es an den inkrementellen Compiler angebunden war. IntelliJ konnte das nicht; stattdessen täuscht es vor einem Rebuild aktiv über gültige/ungültige Zustände hinweg und zeigt viele falsche Fehler an, wenn der interne Zustand nicht mehr zum Stand auf der Festplatte passt. Beim Ausführen gibt es dann manchmal einige Sekunden Kompilierungsverzögerung, und erst dann merkt man, dass der Zustand, den die IDE als lauffähig angezeigt hatte, falsch war. In Eclipse war all das sofort und eindeutig, weil Compiler und interner Zustand geteilt wurden. Es hatte viele Schwächen und lästige Bugs, aber diese Funktion vermisst man
https://willspeak.me/2021/11/24/red-green-syntax-trees-an-ov...
https://ericlippert.com/2012/06/08/red-green-trees/
Ich habe Werkzeuge mit dem Roslyn SDK gebaut, und das war wirklich hervorragend
Das ist für viele Menschen der Hauptgrund, nicht auf eine andere IDE umzusteigen
GitHub hat das früher anscheinend so „repariert“, dass
a.toString()in zwei Tokens zerlegt wurde, und das war ziemlich lästig.GitHub verbessert zwar IDE-artige Funktionen wie das Finden von Verwendungen, aber es ist noch nicht perfekt, sodass man manchmal eine Textsuche wie
"foo.bar()"machen möchte, um übersehene Verwendungen zu finden. Wegen dieses Stemming-Verhaltens werden dann aber auch alle Stellen gefunden, an denen foo und bar getrennt erwähnt werden, wodurch die Ergebnisse unnötig aufblähenIch verstehe nicht, warum Zoekt so oberflächlich abgetan wird.
Es wurde genau für diesen Zweck gebaut und bringt auch keine größere neue Infrastruktur-Last mit sich als andere Optionen. Der Server ist ein einzelnes Binary, der Indexer ebenfalls ein einzelnes Binary; viel einfacher geht es kaum. Ich sehe keinen Grund, vor Zoekt mehr Respekt zu haben als vor Elasticsearch
Einer der interessantesten Ansätze zur Codesuche, die ich in letzter Zeit gesehen habe, ist septum: https://github.com/pyjarrett/septum
Der schwierigste Teil beim Bau einer wirklich guten Codesuche ist meiner Ansicht nach, die richtige Menge an umgebendem Kontext zu liefern, und septum ist ein Werkzeug, das dieses Problem auf Dateiebene angeht. Ebenfalls überraschend unerwähnt blieb stack-graphs(https://github.com/github/stack-graphs), das versucht, Symbolbeziehungen über den gesamten Codebestand hinweg inkrementell aufzulösen. Es treibt GitHubs präzise dateiübergreifende Indizierung an und ist auch konzeptionell überzeugend, aber ich hatte Schwierigkeiten, die Open-Source-Version zum Laufen zu bringen
Oracle hat die Views USER/ALL/DBA_SOURCE, und dort erscheint aller in die Datenbank geladene PL/SQL(SQL/PSM)-Code.
Wenn er nicht absichtlich verschleiert wurde, ist alles im Klartext sichtbar. Es gibt die Spalten Eigentümer, Objektname, LINE[NUMBER] und TEXT[VARCHAR2(4000)], und man kann auf den gespeicherten Quellcode
LIKEoderregexp_like()anwenden. Ich frage mich, ob EnterpriseDB das innerhalb von Postgres implementiert hat oder ob es als Erweiterung bereitgestellt wird. Da SQL/PSM größtenteils ohnehin aus Oracle stammt, wäre das eine sehr naheliegende Funktion. https://en.wikipedia.org/wiki/SQL/PSMEs hieß, „die GitHub-Suche ist großartig“ — aber ist sie das wirklich?
In den meisten Fällen wirkt sie auf mich fast nutzlos, und es ist deutlich effizienter, einfach zu klonen und ripgrep zu verwenden. Vielleicht ist weniger die eigentliche Suche das Problem als vielmehr die schreckliche UX