Pourquoi la recherche de code est-elle difficile ?

 (blog.val.town)
1 points par GN⁺ 2024-04-12 | 1 commentaires | Partager sur WhatsApp
  • La recherche de Val Town repose sur une recherche par sous-chaîne basée sur ILIKE dans Postgres, avec très peu de classement des résultats, et gère mal les requêtes à plusieurs mots, d’où de nombreuses demandes d’amélioration
  • Les règles de recherche en langage naturel comme la suppression des mots vides, la racinisation et la lemmatisation peuvent casser les noms de variables, les noms de fonctions et les frontières de tokens dans le code
  • La recherche en texte intégral de Postgres permettrait de garder une infrastructure simple, mais des projets précédents ont rencontré des problèmes de montée en charge, et Val Town teste déjà les limites d’un Postgres sur nœud unique
  • La recherche v2, lancée discrètement, utilise une recherche trigramme basée sur pg_trgrm, mais contrairement à la recherche par expression régulière, il est difficile d’obtenir le niveau de classement souhaité pour des requêtes libres
  • Des alternatives comme Elasticsearch, Meilisearch, Zoekt ou ParadeDB existent, mais l’infrastructure séparée, la charge d’exploitation et la disponibilité de l’hébergement restent des contraintes de choix

Là où la recherche de Val Town bloque

  • La recherche de Val Town utilise actuellement ILIKE de Postgres
    • C’est une recherche par sous-chaîne : si le terme recherché apparaît dans le code, il remonte dans les résultats
    • Il n’y a presque pas de classement, et les requêtes à plusieurs mots ne sont pas correctement prises en charge
  • Une meilleure recherche est l’une des fonctionnalités les plus demandées sur Val Town
  • Des améliorations sont en cours, mais aucune solution satisfaisant les exigences n’a encore été trouvée
  • Les contraintes identifiées jusqu’ici sont les suivantes
    • Les solutions de recherche grand public sont conçues pour le langage naturel
    • Les grandes entreprises qui ont besoin de recherche de code investissent beaucoup de temps et d’argent dans leur propre système de recherche
    • Val Town possède déjà beaucoup de données et a besoin d’une solution qui passe bien à l’échelle
    • Utiliser un service de recherche séparé au lieu d’étendre la base de données implique un compromis important en matière d’infrastructure et de complexité

Pourquoi les règles de recherche en langage naturel ne conviennent pas au code

  • Les configurations classiques de recherche en texte intégral (FTS) fournissent par défaut des algorithmes pensés pour des langues naturelles comme l’anglais
    • Suppression des mots vides : des mots très fréquents comme “the” ou “it” sont retirés avant l’indexation
    • Racinisation : “running” devient “run”, ce qui permet aussi de le retrouver avec une recherche sur “runs”
    • Lemmatisation : une recherche sur “excellent” peut aussi retrouver un document contenant “great” en remplaçant des synonymes par un terme plus courant
  • Appliquer ces mêmes règles au code déforme le sens
    • En TypeScript, the n’est pas un mot vide, mais peut être un nom de variable valide que l’on veut rechercher
    • Les frontières entre mots dans le code ne sont pas les mêmes qu’en langage naturel
    • Appliquer une racinisation à des noms de fonctions donne difficilement des résultats pertinents
  • Dans Postgres, to_tsvector('english', ...) transforme fortement le texte original lors de l’indexation de phrases en langage naturel
    • I am writing this example sentence devient par exemple 'exampl':5 'sentenc':6 'write':3
  • Dans le code, les problèmes de tokenisation sont encore plus visibles
    • function stringifyNumber(a: number): string { return a.toString() } est indexé comme 'a.tostring':7 'function':1 'number':4 'return':6 'string':5 'stringifynumb':2
    • Des mots comme function restent tels quels, tandis que a.toString() n’est pas scindé en deux tokens, car . n’est pas une frontière de mot par défaut

Avantages et limites de la recherche en texte intégral de Postgres

  • Postgres propose l’extension Full Text Search, également prise en charge par l’hébergeur de Val Town, Render
  • Val Town s’est beaucoup appuyé sur Postgres jusqu’ici, et Postgres est considéré comme une technologie bien documentée et bien prise en charge par les hébergeurs
  • Pour une petite équipe, il est important de garder l’infrastructure aussi simple que possible, ce qui pousse naturellement à utiliser Postgres si le problème peut être résolu ainsi
  • Mais des projets précédents ayant utilisé FTS ont rencontré des problèmes de performance et de montée en charge
    • Observable a fini par migrer vers Elasticsearch
    • Val Town stocke déjà beaucoup de vals et teste les limites d’un cluster Postgres sur nœud unique
  • Il est difficile de trouver des exemples de réussite avec FTS pour la recherche de code, ce qui en fait davantage une option de secours qu’un premier choix

Expérimentation de la recherche v2 basée sur pg_trgrm

  • L’algorithme de recherche v2, lancé discrètement par Val Town, repose sur pg_trgrm de Postgres
    • pg_trgrm implémente une recherche trigramme dans Postgres
  • Les trigrammes ont déjà fait leurs preuves pour la recherche de code
    • Un billet de Russ Cox datant de 2012 explique que Google Code Search utilisait un index trigramme et une implémentation spéciale des expressions régulières
    • Le nouveau système de recherche de code de GitHub utilise lui aussi une recherche trigramme
    • Sourcegraph dispose d’un outil de recherche basé sur les trigrammes, hérité de l’approche de Google
  • L’approche Postgres pg_trgrm de Val Town s’inspire fortement d’un article de Stephen Gutekanst sur l’indexation de dépôts locaux avec Postgres
  • L’implémentation applique un index GIN avec gin_trgm_ops sur la colonne contenant le texte à rechercher
  • pg_trgrm est une bonne solution pour la recherche par expression régulière, mais convient moins bien aux requêtes plus libres, qui représentent la majorité des recherches sur Val Town
    • Le classement des résultats repose sur word_similarity
    • Il est très difficile d’ajuster l’algorithme pour obtenir un classement raisonnable

Choix de moteurs de recherche et compromis d’exploitation

  • Les options étudiées mêlent services de recherche autonomes et extensions Postgres
    • Meilisearch : autonome, Rust, 41k étoiles
    • Typesense : autonome, C++, 17k étoiles
    • Zoekt : autonome, Go, 406 étoiles
    • ParadeDB : extension Postgres, Rust, 3.2k étoiles
    • Sonic : autonome, Rust, 19.4k étoiles
  • Il existe des outils spécialisés pour le code, mais la plupart sont propriétaires
    • La recherche GitHub est excellente, mais c’est le résultat d’une équipe dédiée et d’un budget réel en temps
  • Le fork de Zoekt maintenu par Sourcegraph est intéressant, mais très de niche et demanderait un gros investissement dans une nouvelle infrastructure
  • Elasticsearch pourrait finir par être la solution inévitable
    • Il n’intègre pas de traitement spécifique au code, mais il est presque infiniment personnalisable
    • Il implique toutefois d’apprendre le réglage mémoire de Java, d’introduire pour la première fois du stockage disque persistant dans l’application, et de gérer une source de vérité supplémentaire pour les données
    • Utiliser Elasticsearch Cloud pourrait réduire la charge de maintenance
  • Meilisearch paraît prometteur comme alternative à Elasticsearch
    • Son implémentation en Rust est attractive
    • Sa communication comparative semble davantage insister sur la latence que sur la montée en charge, et il n’est pas certain qu’il réduise vraiment la charge d’infrastructure
  • ParadeDB fonctionne comme Elasticsearch, mais son côté « simplement Postgres » est séduisant
    • Cependant, cette extension n’est pas encore disponible sur Render

Le poids du choix d’une infrastructure de recherche pour une petite équipe

  • La recherche de code est plus difficile que la recherche en anglais
  • Les petites équipes ont intérêt à garder une infrastructure simple, à faciliter la configuration de l’environnement de développement et à conserver les données au même endroit
  • Val Town ne veut pas se retrouver trop vite lié à une option nécessitant une gestion continue
  • Si les entreprises de taille moyenne ou grande n’ont pas seulement un « service » de recherche, mais aussi une « équipe » de recherche, ce n’est pas pour rien

À lire aussi

1 commentaires

 
GN⁺ 2024-04-12
Avis sur Hacker News

  • Chez Sourcegraph, le passage à l’échelle est évidemment nécessaire, mais si vous intégrez pour la première fois la recherche de code dans un produit, je recommande de ne pas commencer d’emblée par un index, et de privilégier une recherche à la volée jusqu’à atteindre ses limites
    Quand il suffit de trouver les N premiers résultats, on n’a pas besoin de tout parcourir jusqu’au bout pour remplir le tampon de résultats, donc ça tient plus longtemps qu’on ne le pense. Je serais aussi ravi d’échanger avec les personnes qui construisent ce genre de choses, ainsi qu’avec les gens de Val Town

    • Quand la recherche indexée devient nécessaire, Zoekt est la meilleure solution que j’aie trouvée
      Sourcegraph a auparavant pris en charge la maintenance de Zoekt, et Livegrep comme Hound avaient du mal sur plusieurs aspects à l’échelle que nous voulions indexer. Après être passés d’un déploiement OpenGrok ancien et bancal à Zoekt, la différence a été nette, à la fois en performances d’indexation et en performances/utilisabilité de recherche. Sourcegraph ajoute des fonctionnalités bien plus sophistiquées par-dessus la recherche de code fournie par Zoekt
    • J’ai été surpris de voir jusqu’où on peut aller sans index
      Par exemple, j’ai toujours pensé que GritQL (https://github.com/getgrit/gritql) aurait tôt ou tard besoin d’un index pour être rapide, mais jusqu’ici il tient plutôt bien uniquement avec de la recherche à la volée
    • J’applique cette approche à plusieurs problèmes. Je commence par la méthode simple qui garde le moins d’état possible, et je ne change qu’après avoir prouvé qu’il faut privilégier la mémoire pour gagner en vitesse
      Sans cache, il est beaucoup plus simple de garantir que le système reste correct
    • Une fois qu’on dispose d’une charge de travail réelle, à grande échelle et représentative, il devient beaucoup plus facile de choisir la bonne méthode d’indexation
    • Quelqu’un qui construisait une base de données temporelle compressait les blocs disque puis les décompressait en streaming pour les rechercher
      Ce qui tient dans le cache L2 fonctionne vraiment très vite

  • La recherche de code est vraiment difficile, et une bonne plateforme de recherche de code rend la vie beaucoup plus simple
    Si je devais quitter Google, je pense que la recherche de code interne serait ce qui me manquerait le plus. Elle est tellement bien intégrée à tous les workflows — trouver des cibles blaze, des bindings guice, etc. — qu’il m’est difficile d’imaginer travailler sans. Chaque fois que j’utilise la recherche GitHub, j’en mesure encore davantage la valeur ; non pas que la recherche GitHub soit mauvaise, mais parce que construire une plateforme généraliste de recherche de code est intrinsèquement beaucoup plus difficile

    • Si vous partez, vous pouvez utiliser Livegrep, construit à partir du travail de Google sur la recherche de code
      Je ne l’utilise pas personnellement en ce moment, mais il est excellent et devrait couvrir la plupart des besoins. https://github.com/livegrep/livegrep
    • La fonctionnalité de couche de bindings guice est utile, mais l’interface pourrait être améliorée
      Ce serait bien de pouvoir trouver directement depuis la barre de recherche les providers ou les emplacements d’utilisation

  • Les techniques de base de recherche de code ne sont pas souvent enseignées explicitement aux développeurs débutants, mais elles semblent être une compétence essentielle à acquérir tôt
    Le parcours que je recommande consiste à apprendre la recherche disponible partout, comme Ctrl+F, puis à passer à ripgrep (https://github.com/BurntSushi/ripgrep). Ce n’est pas vraiment optionnel : c’est un outil excellent et facile à découvrir, et le fait de devoir garder un terminal ouvert est plutôt bénéfique pour les débutants. Si possible, il est aussi utile d’apprendre un éditeur en ligne de commande puissant ; autrefois j’aurais conseillé Emacs, mais aujourd’hui je recommande la version de base de vim, installée presque partout, car on peut greper et éditer dans la même fenêtre. Ensuite, il faut apprendre avec l’ancien grep les comportements que ripgrep fournit par défaut, comme grep -r, grep -ri, grep -ril, puis enfin, quand on atteint les limites de ripgrep, passer à un véritable outil dédié de recherche de code basé sur un index

    • La fonction de recherche de VSCode utilise aussi ripgrep, c’est donc un bon point de départ
    • GitHub est aussi un excellent outil pour chercher du code à travers des dépôts que l’on n’a pas encore clonés, qu’ils soient publics ou appartenant à une organisation
    • Je me demande quels avantages ripgrep a sur git grep pour chercher dans un dépôt Git, en dehors de la vitesse

  • Je suis surpris que hound (https://github.com/hound-search/hound) ne soit pas mentionné
    Je pensais que c’était l’une des principales solutions open source dans ce domaine. J’utilise l’instance de Wikimedia (https://codesearch.wmcloud.org/search/) et j’en suis globalement satisfait

  • C’est pour cette raison que les personnes qui conçoivent des IDE et des outils de développement estiment depuis longtemps que, pour faire une vraie recherche de code, il faut ouvrir la plateforme du compilateur
    Parce qu’une grande partie du travail nécessaire consiste, au final, à reconstruire les représentations internes utilisées par le compilateur. Une bonne recherche de code est aussi la base de l’aide au refactoring, de l’autocomplétion et des fonctionnalités courantes des IDE. Bien sûr, c’est plus facile à dire qu’à faire : du côté des compilateurs, les outils ont souvent été relégués au second plan, JetBrains a aussi commis cette erreur aux débuts de Kotlin, et corrige en partie le tir avec Kotlin 2.0 pour faciliter la prise en charge de choses comme la compilation incrémentale. La communauté Rust a tiré la même leçon il y a quelques années, lors d’un gros effort pour rendre l’écosystème plus compatible avec les IDE. IBM avait réussi à bien faire cela avec l’ancien Eclipse, et depuis, il n’a pas vraiment été rattrapé. IntelliJ était plus lent de deux à trois ordres de grandeur, ce qui faisait la différence entre des secondes et des millisecondes. Eclipse disposait d’un compilateur incrémental Java très rapide, capable de compiler partiellement même en présence d’erreurs de syntaxe, et la représentation du code dans l’IDE était reliée à ce compilateur. Si l’on introduisait une faute de frappe qui cassait une partie du code, les fichiers problématiques dans toute la base de code étaient immédiatement soulignés en rouge ; une fois la faute corrigée, cela disparaissait sans délai. Cela n’est possible que s’il existe un mapping entre les fichiers et les arbres syntaxiques, et Eclipse y parvenait parce qu’il était relié au compilateur incrémental. IntelliJ n’y arrive pas : avant une reconstruction, il peut activement faire croire qu’un état valide ou invalide est correct, et quand son état interne diverge du disque, il affiche beaucoup de fausses erreurs. Lorsqu’on lance l’exécution, il y a parfois quelques secondes de délai de compilation, et c’est seulement à ce moment-là qu’on découvre que l’état que l’IDE présentait comme exécutable était faux. Dans Eclipse, comme le compilateur et l’état interne étaient partagés, tout cela était immédiat et clair. Il avait beaucoup de défauts et de bugs agaçants, mais cette fonctionnalité me manque

    • Bien sûr, Roslyn de Microsoft, le compilateur .NET, fait exception
      https://willspeak.me/2021/11/24/red-green-syntax-trees-an-ov...
      https://ericlippert.com/2012/06/08/red-green-trees/
      J’ai créé des outils avec le SDK Roslyn, et c’était vraiment très agréable
    • Le compilateur incrémental d’Eclipse pour Java est vraiment impressionnant, mais j’ai fini par passer à IntelliJ, qui s’intègre mieux avec les systèmes de build externes comme Maven et Gradle et prend mieux en charge plusieurs langages
    • Dans Eclipse, c’est toujours instantané et sans ambiguïté
      C’est la principale raison pour laquelle beaucoup de gens ne passent pas à un autre IDE

  • Il me semble que GitHub avait autrefois “corrigé” ça en découpant a.toString() en deux tokens, ce qui était assez pénible
    GitHub renforce bien la recherche des emplacements d’utilisation façon IDE, mais ce n’est pas encore parfait, et il arrive qu’on veuille faire une recherche textuelle du type "foo.bar()" pour trouver des usages manqués. Or, à cause de ce comportement de racinisation, on finit aussi par trouver tous les endroits où foo et bar sont mentionnés séparément, ce qui fait exploser les résultats

  • Je ne comprends pas pourquoi Zoekt est écarté aussi vite
    Il a été conçu précisément pour cet usage, et il n’impose pas une nouvelle charge d’infrastructure plus importante que les autres options. Le serveur est un binaire unique, l’indexeur aussi ; difficile de faire plus simple. Je ne vois pas pourquoi Zoekt ferait plus peur qu’Elasticsearch

  • L’une des approches de recherche de code les plus intéressantes que j’aie vues récemment est septum : https://github.com/pyjarrett/septum
    À mon avis, la partie la plus difficile quand on veut bien faire la recherche de code, c’est de récupérer la bonne quantité de contexte environnant ; septum est un outil qui essaie de résoudre ce problème au niveau du fichier. J’ai aussi été surpris que stack-graphs (https://github.com/github/stack-graphs) ne soit pas mentionné : il vise à résoudre progressivement les relations entre symboles à l’échelle de toute la base de code. Il alimente l’indexation précise inter-fichiers de GitHub et son approche est conceptuellement pertinente, mais j’ai eu du mal à faire fonctionner la version open source

  • Oracle propose les vues USER/ALL/DBA_SOURCE, où apparaît tout le code PL/SQL (SQL/PSM) chargé dans la base de données
    S’il n’a pas été volontairement obfusqué, tout est visible en clair. On y trouve les colonnes propriétaire, nom d’objet, LINE[NUMBER] et TEXT[VARCHAR2(4000)], et l’on peut utiliser LIKE ou regexp_like() sur le code source stocké. Je me demande si EnterpriseDB a implémenté cela dans Postgres, ou si c’est fourni sous forme d’extension. Comme la majeure partie de SQL/PSM vient de toute façon d’Oracle, c’est une fonctionnalité qu’il est naturel d’attendre. https://en.wikipedia.org/wiki/SQL/PSM

  • Il est dit que “la recherche GitHub est excellente”, mais est-ce vraiment le cas ?
    Dans la plupart des cas, elle me semble presque inutilisable, et il est beaucoup plus efficace de cloner puis d’utiliser ripgrep. Le vrai problème est peut-être davantage l’UX catastrophique que la recherche elle-même