GitHub a beaucoup de code à rechercher – plus de 200 millions de référentiels – et indique que la version bêta de novembre dernier d’un moteur de recherche optimisé pour le code source a provoqué une “rafale d’innovations”.
L’ingénieur de GitHub, Timothy Clem, a expliqué que l’entreprise avait du mal à faire fonctionner correctement la technologie existante. “La vérité est que de Solr à Elasticsearch, nous n’avons pas eu beaucoup de chance en utilisant des produits de recherche de texte généraux pour alimenter la recherche de code”, a-t-il déclaré. a dit dans une présentation vidéo de GitHub Universe. “L’expérience utilisateur est médiocre. C’est très, très cher à héberger et c’est lent à indexer.”
Dans un article de blog Lundi, Clem s’est penché sur la technologie utilisée pour parcourir seulement un quart de ces dépôts, un moteur de recherche de code construit à Rust appelé Blackbird.
Blackbird donne actuellement accès à près de 45 millions de référentiels GitHub, qui représentent ensemble 115 To de code et 15,5 milliards de documents. Parcourir autant de lignes de code nécessite quelque chose de plus fort que grep, un outil de ligne de commande courant sur les systèmes de type Unix pour rechercher dans les données textuelles.
En utilisant ripgrep sur un processeur Intel à 8 cœurs pour exécuter une requête d’expression régulière exhaustive sur un fichier de 13 Go en mémoire, a expliqué Clem, prend environ 2,769 secondes, soit 0,6 Go/sec/cœur.
“Nous pouvons voir assez rapidement que cela ne fonctionnera vraiment pas pour la plus grande quantité de données dont nous disposons”, a-t-il déclaré. “La recherche de code s’exécute sur 64 cœurs et 32 clusters de machines. Même si nous parvenons à mettre 115 To de code en mémoire et supposons que nous pouvons parfaitement paralléliser le travail, nous allons saturer 2 048 cœurs de processeur pendant 96 secondes pour répondre à une seule requête ! Seule cette requête peut être exécutée. Tous les autres doivent se mettre en ligne. »
À 0,01 requêtes par seconde, grep n’était pas une option. GitHub a donc chargé une grande partie du travail dans des index de recherche précalculés. Ce sont essentiellement des cartes de paires clé-valeur. Cette approche rend la recherche de caractéristiques de document telles que le langage de programmation ou les séquences de mots moins exigeante en termes de calcul en utilisant une clé numérique plutôt qu’une chaîne de texte.
Même ainsi, ces index sont trop volumineux pour tenir en mémoire, donc GitHub a construit des itérateurs pour chaque index auquel il avait besoin d’accéder. Selon Clem, ceux-ci renvoient paresseusement des ID de documents triés qui représentent le rang du document associé et répondent aux critères de requête.
Pour que l’index de recherche reste gérable, GitHub s’appuie sur le sharding – en divisant les données en plusieurs parties à l’aide du schéma de hachage adressable par le contenu de Git et sur l’encodage delta – en stockant les différences de données (deltas) pour réduire les données et les métadonnées à explorer. Cela fonctionne bien car GitHub a beaucoup de données redondantes (par exemple, des fourches) – ses 115 To de données peuvent être réduites à 25 To grâce à des techniques de déduplication de rasage des données.
Le système résultant fonctionne beaucoup plus rapidement que grep – 640 requêtes par seconde contre 0,01 requêtes par seconde. Et l’indexation se produit à un rythme d’environ 120 000 documents par seconde, de sorte que le traitement de 15,5 milliards de documents prend environ 36 heures, ou 18 pour la réindexation puisque l’indexation delta (modification) réduit le nombre de documents à explorer.
La recherche de code GitHub est actuellement en bêta-test. ®
