Abandonnez ElasticSearch, GitHub construit un moteur de recherche à partir de zéro ! Comment rechercher dans l'entrepôt de 200 millions de codes ?

En décembre 2021, GitHub a publié un aperçu technologique et mené une optimisation complète pour résoudre le problème de « rien ne peut être trouvé » dans la recherche de code GitHub.

En novembre de l'année dernière, lors de la conférence des développeurs de l'univers GitHub, le responsable a publié la version bêta publique, qui résout principalement les problèmes des développeurs pour trouver, lire et naviguer dans le code.

Lors de la conférence, quelqu'un a posé une question importante : Quel est le principe derrière l'amélioration de « Code Search » ?

Récemment, GitHub a publié un blog expliquant en détail les principes techniques et l'architecture système derrière le nouveau modèle.

Créez un moteur de recherche GitHub à partir de zéro

Pour faire simple, derrière le nouveau moteur de recherche se cache une roue réécrite par des chercheurs dans Rust, spécifiquement optimisée pour la recherche de code, nommée Blackbird.

À première vue, créer un moteur de recherche à partir de zéro peut sembler une décision déroutante : Pourquoi repartir de zéro ? N’existe-t-il pas déjà de nombreuses solutions open source ? Pourquoi gaspiller encore plus d’énergie pour construire une nouvelle chose ?

En fait, GitHub a essayé d'utiliser les solutions existantes pour résoudre le problème de recherche, mais malheureusement, les produits utilisés pour la recherche de texte générale sont difficiles à adapter à la recherche de « code ». Parce que la vitesse d'indexation est trop lente, l'expérience utilisateur est mauvaise, le nombre de serveurs requis est important et les coûts de fonctionnement sont trop élevés.

Bien qu'il existe de nouveaux projets open source spécifiquement adaptés à la recherche de code, ils ne sont toujours pas adaptés à une base de code aussi grande que GitHub.

Sur la base des observations ci-dessus, les développeurs de GitHub ont fixé trois objectifs et conclusions principaux :

1. Les utilisateurs peuvent vivre une nouvelle expérience pendant le processus de recherche en posant des questions de code. naviguer et lire du code pour obtenir des réponses.

2. Il existe de nombreuses différences entre la recherche de code et la recherche de texte générale.

Les développeurs écrivent du code pour qu'il soit compris par les machines, de sorte que le processus de recherche de code doit tirer parti de la structure et de la corrélation du code ; et les utilisateurs peuvent rechercher des signes de ponctuation (par exemple, des points, des crochets ouverts et d'autres opérateurs dans le code ); ne racinez pas les mots dans votre code ; ne supprimez pas les mots vides de la requête et n'utilisez pas d'expressions régulières pour effectuer la recherche ;

3. L'échelle de GitHub présente un défi unique.

L'ancienne version du moteur de recherche utilisait Elasticsearch. Lors de son premier déploiement, il fallait plusieurs mois pour indexer tout le code sur GitHub (il y avait environ 8 millions de référentiels de code à l'époque), mais maintenant le référentiel de code. Le nombre a dépassé les 200 millions, et ces codes ne sont pas statiques : les développeurs les soumettent constamment et le code change constamment, ce qui est très difficile pour créer un moteur de recherche.

Actuellement en version bêta, les utilisateurs peuvent effectuer des recherches dans environ 45 millions de bases de codes contenant 115 To de code et 15,5 milliards de documents.

Pour résumer, les choses toutes faites ne peuvent pas répondre aux besoins, alors construisez-en une à partir de zéro.

Essayez Grep ?

Lors de la recherche, un outil couramment utilisé est "grep". En saisissant une expression, vous pouvez faire correspondre le texte, alors pourquoi ne pas simplement utiliser grep pour résoudre le problème de recherche par force brute ?

Pour répondre à cette question, vous pouvez d'abord calculer combien de temps il faut pour faire correspondre 115 To de code avec ripgrep.

Sur une machine dotée d'un processeur Intel à 8 cœurs, ripgrep peut exécuter une requête d'expression régulière sur un fichier de 13 Go mis en cache en mémoire en 2,769 secondes (~0,6 Go/sec/cœur).

Après un simple calcul, nous pouvons constater que cette méthode n'est pas réalisable pour les données massives actuelles : en supposant que le programme de recherche de code s'exécute sur un cluster de 32 serveurs, chaque machine possède 64 cœurs, même si les 115 To de code sont mis dans la mémoire, et tout fonctionne correctement. Il faut environ 96 secondes pour que 2 048 cœurs de processeur exécutent "une" requête, et il ne peut y en avoir qu'une. Les autres utilisateurs doivent faire la queue, ce qui signifie qu'elle ne peut être utilisée que si le QPS est. 0.01.grep

Donc la force brute ne fonctionnera pas, nous ne pouvons donc que créer un index en premier.

Indice de recherche (index de recherche)

Ce n'est qu'après que les informations pertinentes sont pré-calculées sous la forme d'un index que le moteur de recherche peut répondre rapidement lors d'une interrogation. En termes simples, l'index est un mappage clé-valeur. l'index inversé (index inversé), la clé est un mot-clé et la valeur est la liste ordonnée des ID de document dans laquelle le mot apparaît.

Dans la tâche de recherche de code, les chercheurs ont utilisé un type spécial d'index inversé, à savoir l'index ngram.

Un ngramme est une séquence de caractères de longueur n. Par exemple, n = 3 (trigames) signifie que la longueur maximale de la clé ne peut être que de 3. Pour les clés plus longues, elle doit être coupée en fonction de la longueur de 3, comme les limites. Il est divisé en lim, imi, mit et its

Lors d'une recherche, les résultats de la requête de plusieurs clés sont combinés et la liste des documents dans lesquels la chaîne apparaît est obtenue après fusion

La question suivante est de savoir comment le rendre relativement raisonnable. Terminer la construction de l'index dans les délais requis.

Les chercheurs ont observé que Git utilise le hachage adressé au contenu, et qu'il y a en fait beaucoup de contenu en double sur GitHub, les chercheurs ont donc proposé les deux méthodes suivantes pour créer des index.

1. shard by Git blob object ID fournit un bon moyen de répartir uniformément les documents entre les fragments et d'éviter la duplication tout en étant capable d'augmenter le nombre de fragments à tout moment selon les besoins.

2. Modélisez l'index sous forme d'arbre et utilisez le codage différentiel (codage delta) pour réduire le nombre d'explorations et optimiser les métadonnées dans l'index, où les métadonnées incluent la liste des emplacements où le document apparaît ( quel chemin, branche et référentiels) et des informations sur ces objets (nom du référentiel, propriétaire, visibilité, etc.). Pour certains référentiels populaires, la quantité de métadonnées peut être assez importante.

GitHub a également conçu un système pour maintenir la cohérence des résultats de la requête avec le code soumis.

Si un utilisateur effectue une recherche dans la base de code pendant qu'un membre de l'équipe envoie du code, les documents nouvellement validés ne doivent pas être inclus dans les résultats de la recherche jusqu'à ce que le système ait entièrement traité ces documents. Blackbird fait de la cohérence des requêtes de validation un élément essentiel de. sa conception.

Blackbird

Ce qui suit est le schéma d'architecture du moteur de recherche Blackbird.

Tout d'abord, Kafka fournira des événements pour spécifier le contenu de l'index, puis il y aura un grand nombre de programmes d'exploration pour interagir avec Git, y compris un service qui extrait à nouveau les symboles du code ; Utilisez Kafka pour indexer chaque fragment et obtenir le document cible.

Bien que le système ne réponde qu'à des événements tels que "git push" pour récupérer les modifications et événements similaires, un travail supplémentaire est nécessaire pour ingérer toutes les bases de code pour la première fois.

Une caractéristique clé de ce système est l'optimisation de l'ordre d'ingestion initial pour tirer pleinement parti de l'encodage incrémentiel.

GitHub utilise une nouvelle structure de données probabiliste pour représenter la similarité des bases de code, et l'ordre d'ingestion est calculé à partir d'un parcours séquentiel horizontal d'un arbre couvrant minimum du graphe de similarité de la base de code.

Sur la base de l'ordre d'ingestion optimisé, le processus de construction de l'arborescence delta consiste à différencier chaque base de code de sa base de code parent. Cela signifie également que le système n'a besoin d'explorer que les blobs uniques à la base de code actuelle. inclut Récupérez le contenu du blob depuis Git, analysez-le pour extraire des symboles et créez des documents qui seront utilisés comme entrée dans l'index.

Publiez ensuite ces fichiers dans un autre sujet Kafka, où les données sont également partitionnées entre les fragments. Chaque fragment utilise une partition Kafka dans le sujet.

L'utilisation de Kafka peut découpler l'indexation et l'exploration, et le tri des messages dans Kafka peut également rendre les résultats des requêtes cohérents.

Les fragments de l'indexeur trouvent ensuite ces documents et construisent l'index : tokenisation du contenu, des symboles et des chemins pour construire des index ngram et d'autres indices utiles (langue, propriétaire, base de code, etc.) et vidage des résultats sur le disque.

Enfin, compactez les fragments et réduisez le plus petit index en un index plus grand, afin que la requête soit plus efficace et que le déplacement soit plus facile.

Cycle de vie des requêtes

Avec l'index, le suivi des requêtes à travers le système devient simple. Chaque requête est une expression régulière, qui peut être écrite sous la forme "/arguments?/ org:rails lang:Ruby", c'est-à-dire trouver. un code écrit en langage Ruby par l'organisation Rails.

Il existe également un service entre GitHub.com et shards, qui se charge de coordonner la réception des requêtes des utilisateurs, de disperser les requêtes vers chaque hôte du cluster de recherche, et enfin d'utiliser Redis pour gérer le disque espace (quotas) et mettre en cache certaines données de contrôle d'accès.

Le frontend accepte une requête utilisateur et la transmet à Blackbird, qui analyse ensuite la requête dans un arbre de syntaxe abstraite, la réécrit dans un ID de langage canonique et marque les autorisations et les portées sur des clauses supplémentaires.

L'étape suivante consistera à envoyer n requêtes simultanées : une à chaque fragment du cluster de recherche. La stratégie de partitionnement définie dans le système consiste à envoyer des requêtes de requête à chaque fragment du cluster.

Ensuite, effectuez quelques transformations sur la requête sur chaque fragment individuel pour retrouver les informations dans l'index.

Enfin, regroupez les résultats renvoyés par tous les fragments, réorganisez par score, filtrez (vérifiez à nouveau les autorisations) et renvoyez le top 100, puis le front-end de GitHub.com effectue la coloration syntaxique, la coloration des termes. , et la pagination. Enfin, nous pouvons présenter les résultats à la page.

En utilisation réelle, le temps de réponse p99 d'un seul fragment est d'environ 100 ms. Cependant, pour des raisons telles que l'agrégation des réponses, la vérification des autorisations et la coloration syntaxique, le temps de réponse total est plus long.

Une requête occupe un cœur de processeur pendant 100 millisecondes sur le serveur d'index, donc la limite supérieure d'un hôte à 64 cœurs est d'environ 640 requêtes par seconde. Par rapport à la méthode grep (0,01 QPS), cette méthode peut être considérée comme assez rapide.

Résumé

Après avoir présenté l'architecture complète du système, vous pouvez réexaminer l'ampleur du problème.

Le pipeline d'ingestion de GitHub peut publier environ 120 000 documents par seconde, il faudra donc environ 36 heures pour traiter les 15,5 milliards de documents. Cependant, l'indexation delta peut réduire le nombre de documents à explorer de plus de 50 %, ce qui permet l'ensemble du processus pour réindexer l'ensemble du corpus en 18 heures environ.

Certaines avancées ont été réalisées en termes d'échelle d'index. Le volume de contenu initial était de 115 To. Après avoir supprimé le contenu en double et utilisé l'indexation incrémentielle, la quantité de contenu a été réduite à environ 28 To.

Et l'index lui-même ne fait que 25 To, ce qui inclut non seulement tous les index (y compris les ngrams), mais également des copies compressées de tout le contenu unique, ce qui signifie également que la taille totale de l'index, y compris le contenu, ne représente qu'environ un quart de l'original. taille des données un !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!