TL;DR : Il y a quatre ans, j'ai quitté Google avec l'idée d'un nouvel outil de surveillance des serveurs. L'idée était de regrouper des fonctions habituellement isolées en un seul service. et analyse des journaux, collecte de métriques, et tableaux de bord. L'un des principes est que le service doit être véritablement vite, offrant aux développeurs une expérience simple, interactive et agréable. Cela nécessite de traiter des ensembles de données de plusieurs gigaoctets en quelques fractions de seconde tout en respectant le budget. Les outils de gestion des logs existants sont souvent lents et peu pratiques, nous avons donc été confrontés à un défi de taille : concevoir intelligemment un outil pour offrir aux utilisateurs une nouvelle expérience.
Cet article décrit comment chez Scalyr nous avons résolu ce problème en appliquant des méthodes anciennes, une approche par force brute, en éliminant les couches inutiles et en évitant les structures de données complexes. Vous pouvez appliquer ces leçons à vos propres problèmes d’ingénierie.
Le pouvoir de la vieille école
L'analyse des journaux commence généralement par une recherche : recherchez tous les messages qui correspondent à un certain modèle. Dans Scalyr, il s'agit de dizaines ou de centaines de gigaoctets de journaux provenant de nombreux serveurs. En règle générale, les approches modernes impliquent la construction d'une structure de données complexe optimisée pour la recherche. J'ai certainement vu cela sur Google, où ils sont plutôt bons dans ce genre de choses. Mais nous avons opté pour une approche beaucoup plus grossière : l’analyse linéaire des journaux. Et cela a fonctionné : nous fournissons une interface de recherche beaucoup plus rapide que celle de nos concurrents (voir l'animation à la fin).
L’idée clé était que les processeurs modernes sont en effet très rapides pour des opérations simples et directes. Il est facile de manquer cela dans les systèmes multicouches complexes qui reposent sur la vitesse d’E/S et les opérations réseau, et de tels systèmes sont très courants aujourd’hui. Nous avons donc développé une conception qui minimise les couches et les excès de débris. Avec plusieurs processeurs et serveurs en parallèle, la vitesse de recherche atteint 1 To par seconde.
Points clés à retenir de cet article :
- La recherche par force brute est une approche viable pour résoudre des problèmes réels à grande échelle.
- La force brute est une technique de conception, pas une solution sans travail. Comme toute technique, elle est mieux adaptée à certains problèmes que d’autres, et peut être mal ou bien mise en œuvre.
- La force brute est particulièrement efficace pour atteindre stable productivité.
- Une utilisation efficace de la force brute nécessite d’optimiser le code et d’appliquer suffisamment de ressources au bon moment. Il convient si vos serveurs sont soumis à une forte charge de non-utilisateur et que les opérations des utilisateurs restent une priorité.
- Les performances dépendent de la conception de l’ensemble du système, et pas seulement de l’algorithme de la boucle interne.
(Cet article décrit la recherche de données en mémoire. Dans la plupart des cas, lorsqu'un utilisateur effectue une recherche de journaux, les serveurs Scalyr les ont déjà mis en cache. L'article suivant abordera la recherche de journaux non mis en cache. Les mêmes principes s'appliquent : code efficace, force brute avec de grandes ressources de calcul).
Méthode de force brute
Traditionnellement, un vaste ensemble de données est recherché à l’aide d’un index de mots clés. Lorsqu'il est appliqué aux journaux du serveur, cela signifie rechercher chaque mot unique dans le journal. Pour chaque mot, vous devez dresser une liste de toutes les inclusions. Cela permet de trouver facilement tous les messages contenant ce mot, par exemple « erreur », « Firefox » ou « transaction_16851951 » - il suffit de regarder dans l'index.
J'ai utilisé cette approche chez Google et cela a bien fonctionné. Mais dans Scalyr, nous recherchons les journaux octet par octet.
Pourquoi? D’un point de vue algorithmique abstrait, les index de mots-clés sont bien plus efficaces que les recherches par force brute. Cependant, nous ne vendons pas d’algorithmes, nous vendons de la performance. Et la performance n’est pas seulement une question d’algorithmes, mais aussi d’ingénierie système. Il faut tout considérer : volume de données, type de recherche, contexte matériel et logiciel disponible. Nous avons décidé que pour notre problème particulier, quelque chose comme « grep » était mieux adapté qu'un index.
Les index sont excellents, mais ils ont des limites. Un mot est facile à trouver. Mais rechercher des messages contenant plusieurs mots, tels que « googlebot » et « 404 », est beaucoup plus difficile. La recherche d'une expression telle que « exception non détectée » nécessite un index plus volumineux qui enregistre non seulement tous les messages contenant ce mot, mais également l'emplacement spécifique du mot.
La vraie difficulté vient quand on ne cherche pas les mots. Supposons que vous souhaitiez connaître la quantité de trafic provenant des robots. La première pensée est de rechercher dans les journaux le mot « bot ». C’est ainsi que vous retrouverez certains bots : Googlebot, Bingbot et bien d’autres. Mais ici, « bot » n'est pas un mot, mais une partie de celui-ci. Si nous recherchons « bot » dans l’index, nous ne trouverons aucun article contenant le mot « Googlebot ». Si vous vérifiez chaque mot de l'index, puis parcourez l'index pour les mots-clés trouvés, la recherche ralentira considérablement. En conséquence, certains programmes de journalisation n'autorisent pas les recherches par mots partiels ou (au mieux) autorisent une syntaxe spéciale avec des performances inférieures. Nous voulons éviter cela.
Un autre problème est la ponctuation. Voulez-vous retrouver toutes les demandes de 50.168.29.7? Qu'en est-il des journaux de débogage contenant [error]? Les indices ignorent généralement la ponctuation.
Enfin, les ingénieurs aiment les outils puissants, et parfois un problème ne peut être résolu qu'avec une expression régulière. L'index de mots-clés n'est pas très adapté pour cela.
De plus, les indices complexe. Chaque message doit être ajouté à plusieurs listes de mots clés. Ces listes doivent être conservées à tout moment dans un format facilement consultable. Les requêtes contenant des phrases, des fragments de mots ou des expressions régulières doivent être traduites en opérations multi-listes, et les résultats analysés et combinés pour produire un ensemble de résultats. Dans le contexte d’un service multi-tenant à grande échelle, cette complexité crée des problèmes de performances qui ne sont pas visibles lors de l’analyse des algorithmes.
Les index de mots-clés prennent également beaucoup de place et le stockage représente un coût majeur dans un système de gestion de journaux.
En revanche, chaque recherche peut consommer beaucoup de puissance de calcul. Nos utilisateurs apprécient les recherches rapides pour des requêtes uniques, mais ces requêtes sont relativement rares. Pour les requêtes de recherche typiques, par exemple pour un tableau de bord, nous utilisons des techniques spéciales (nous les décrirons dans le prochain article). Les autres demandes sont suffisamment rares pour que vous deviez rarement en traiter plusieurs à la fois. Mais cela ne veut pas dire que nos serveurs ne sont pas occupés : ils sont occupés au travail de réception, d'analyse et de compression de nouveaux messages, d'évaluation des alertes, de compression des anciennes données, etc. Ainsi, nous disposons d'une offre assez importante de processeurs pouvant être utilisés pour exécuter des requêtes.
La force brute fonctionne si vous avez un problème de brute (et beaucoup de force)
La force brute fonctionne mieux sur des problèmes simples avec de petites boucles internes. Souvent, vous pouvez optimiser la boucle interne pour fonctionner à des vitesses très élevées. Si le code est complexe, il est beaucoup plus difficile de l’optimiser.
Notre code de recherche comportait à l’origine une boucle interne assez grande. Nous stockons les messages sur des pages en 4K ; chaque page contient des messages (en UTF-8) et des métadonnées pour chaque message. Les métadonnées sont une structure qui code la longueur de la valeur, l'ID du message interne et d'autres champs. Le cycle de recherche ressemblait à ceci :
Il s'agit d'une version simplifiée du code actuel. Mais même ici, plusieurs placements d'objets, copies de données et appels de fonctions sont visibles. La JVM est assez efficace pour optimiser les appels de fonctions et allouer des objets éphémères, donc ce code a mieux fonctionné que nous le méritions. Lors des tests, les clients l'ont utilisé avec beaucoup de succès. Mais finalement, nous sommes passés au niveau supérieur.
(Vous vous demandez peut-être pourquoi nous stockons les messages dans ce format avec des pages 4K, du texte et des métadonnées, plutôt que de travailler directement avec les journaux. Il existe de nombreuses raisons, qui se résument au fait qu'en interne, le moteur Scalyr ressemble plus à une base de données distribuée qu'à une système de fichiers. La recherche de texte est souvent combinée avec des filtres de style SGBD dans les marges après l'analyse des journaux. Nous pouvons rechercher simultanément plusieurs milliers de journaux à la fois, et les simples fichiers texte ne conviennent pas à notre gestion de données transactionnelles, répliquées et distribuées).
Au départ, il semblait qu'un tel code n'était pas très adapté à l'optimisation par force brute. "Un vrai travail" dans String.indexOf() n'a même pas dominé le profil du processeur. Autrement dit, l’optimisation de cette méthode à elle seule n’apporterait pas d’effet significatif.
Il se trouve que nous stockons les métadonnées au début de chaque page et que le texte de tous les messages en UTF-8 est compressé à l'autre extrémité. Profitant de cela, nous avons réécrit la boucle pour rechercher toute la page d'un coup :
Cette version fonctionne directement sur la vue raw byte[] et recherche tous les messages en même temps sur toute la page 4K.
C'est beaucoup plus facile à optimiser pour la méthode de la force brute. La boucle de recherche interne est appelée simultanément pour l’ensemble de la page 4K, plutôt que séparément sur chaque publication. Il n'y a pas de copie de données, pas d'attribution d'objets. Et les opérations de métadonnées plus complexes ne sont appelées que lorsque le résultat est positif, et non pour chaque message. De cette façon, nous avons éliminé une tonne de frais généraux et le reste de la charge est concentré dans une petite boucle de recherche interne, bien adaptée à une optimisation ultérieure.
Notre algorithme de recherche actuel est basé sur . Il est similaire à l'algorithme de Boyer-Moore, sautant approximativement la longueur de la chaîne de recherche à chaque étape. La principale différence est qu'il vérifie deux octets à la fois pour minimiser les fausses correspondances.
Notre implémentation nécessite la création d'une table de recherche de 64 Ko pour chaque recherche, mais ce n'est rien comparé aux gigaoctets de données dans lesquels nous recherchons. La boucle interne traite plusieurs gigaoctets par seconde sur un seul cœur. En pratique, les performances stables sont d'environ 1,25 Go par seconde sur chaque cœur, et des améliorations sont possibles. Il est possible d'éliminer une partie de la surcharge en dehors de la boucle interne, et nous prévoyons d'expérimenter une boucle interne en C au lieu de Java.
Nous utilisons la force
Nous avons discuté du fait que la recherche de journaux peut être implémentée « grossièrement », mais de quel « pouvoir » disposons-nous ? Beaucoup.
1 noyau: Lorsqu'il est utilisé correctement, un seul cœur d'un processeur moderne est assez puissant en soi.
8 cœurs: Nous fonctionnons actuellement sur des serveurs SSD Amazon hi1.4xlarge et i2.4xlarge, chacun doté de 8 cœurs (16 threads). Comme mentionné ci-dessus, ces cœurs sont généralement occupés par des opérations en arrière-plan. Lorsque l'utilisateur effectue une recherche, les opérations en arrière-plan sont suspendues, libérant ainsi les 8 cœurs pour la recherche. La recherche se termine généralement en une fraction de seconde, après quoi le travail en arrière-plan reprend (le programme de limitation garantit que le barrage de requêtes de recherche n'interfère pas avec un travail en arrière-plan important).
16 cœurs: pour plus de fiabilité, nous organisons les serveurs en groupes maître/esclave. Chaque maître dispose d'un serveur SSD et d'un serveur EBS sous ses ordres. Si le serveur principal tombe en panne, le serveur SSD prend immédiatement sa place. Presque tout le temps, maître et esclave fonctionnent correctement, de sorte que chaque bloc de données peut être recherché sur deux serveurs différents (le serveur esclave EBS a un processeur faible, nous n'en tenons donc pas compte). Nous répartissons la tâche entre eux, de sorte que nous disposions d'un total de 16 cœurs disponibles.
De nombreux noyaux: Dans un avenir proche, nous répartirons les données sur les serveurs de manière à ce qu'ils participent tous au traitement de chaque requête non triviale. Chaque noyau fonctionnera. [Note: nous avons mis en œuvre le plan et augmenté la vitesse de recherche à 1 To/s, voir note en fin d'article].
La simplicité garantit la fiabilité
Un autre avantage de la méthode par force brute est ses performances assez constantes. En règle générale, la recherche n'est pas très sensible aux détails du problème et à l'ensemble de données (je suppose que c'est pourquoi on l'appelle « grossière »).
L'index de mots clés produit parfois des résultats incroyablement rapides, et d'autres fois non. Supposons que vous disposiez de 50 Go de journaux dans lesquels le terme « client_5987235982 » apparaît exactement trois fois. Une recherche de ce terme compte trois emplacements directement à partir de l'index et se terminera instantanément. Mais les recherches complexes avec des caractères génériques peuvent analyser des milliers de mots-clés et prendre beaucoup de temps.
D’un autre côté, les recherches par force brute s’effectuent plus ou moins à la même vitesse pour n’importe quelle requête. La recherche de mots longs est meilleure, mais même la recherche d'un seul caractère est assez rapide.
La simplicité de la méthode par force brute fait que ses performances sont proches de son maximum théorique. Il existe moins d'options pour les surcharges de disque inattendues, les conflits de verrouillage, la poursuite de pointeur et des milliers d'autres raisons d'échec. Je viens de regarder les requêtes faites par les utilisateurs de Scalyr la semaine dernière sur notre serveur le plus occupé. Il y a eu 14 000 demandes. Exactement huit d’entre eux ont pris plus d’une seconde ; 99 % terminé en 111 millisecondes (si vous n'avez pas utilisé d'outils d'analyse de journaux, faites-moi confiance : c'est rapide).
Des performances stables et fiables sont importantes pour faciliter l’utilisation du service. S'il est périodiquement en retard, les utilisateurs le percevront comme peu fiable et hésiteront à l'utiliser.
La recherche de journaux en action
Voici une courte animation qui montre la recherche Scalyr en action. Nous avons un compte de démonstration sur lequel nous importons chaque événement dans chaque référentiel Github public. Dans cette démo, j'examine l'équivalent d'une semaine de données : environ 600 Mo de journaux bruts.
La vidéo a été enregistrée en direct, sans préparation particulière, sur mon bureau (à environ 5000 kilomètres du serveur). Les performances que vous verrez sont en grande partie dues à , ainsi qu'un backend rapide et fiable. Chaque fois qu'il y a une pause sans indicateur de « chargement », c'est moi qui fais une pause pour que vous puissiez lire sur quoi je m'apprête à appuyer.
En conclusion
Lors du traitement de grandes quantités de données, il est important de choisir un bon algorithme, mais « bon » ne signifie pas « sophistiqué ». Pensez à la façon dont votre code fonctionnera dans la pratique. L’analyse théorique des algorithmes laisse de côté certains facteurs qui peuvent s’avérer d’une grande importance dans le monde réel. Les algorithmes plus simples sont plus faciles à optimiser et plus stables dans les situations extrêmes.
Pensez également au contexte dans lequel le code sera exécuté. Dans notre cas, nous avons besoin de serveurs suffisamment puissants pour gérer les tâches en arrière-plan. Les utilisateurs lancent des recherches relativement rarement, nous pouvons donc emprunter un groupe entier de serveurs pour la courte période nécessaire pour effectuer chaque recherche.
En utilisant une méthode de force brute, nous avons mis en œuvre une recherche rapide, fiable et flexible dans un ensemble de journaux. Nous espérons que ces idées seront utiles pour vos projets.
Modifier: Le titre et le texte sont passés de « Recherche à 20 Go par seconde » à « Recherche à 1 To par seconde » pour refléter l'augmentation des performances au cours des dernières années. Cette augmentation de vitesse est principalement due aux changements dans le type et le nombre de serveurs EC2 que nous mettons en place aujourd'hui pour servir notre clientèle croissante. Des changements seront bientôt apportés qui apporteront une nouvelle amélioration considérable à l'efficacité opérationnelle, et nous avons hâte de les partager.
Source: habr.com