Comment nous avons créé un analyseur inspiré de Lucene en Go

Chez Mailgun, nous avons de nombreux systèmes qui génèrent une tonne d’événements à chaque heure de la journée. C’est un nombre si important qu’il est impossible pour une équipe de trier les résultats ElasticSearch et d’espérer obtenir des résultats cohérents, ou même de garder toute sa tête.

Comme beaucoup d’entreprises, nous devons tout de même trouver un moyen de gérer toutes ces données. Cela représente une tâche considérable : créer un système qui permet à nos clients internes de réagir aux événements en temps réel.

Généralement, les options pour résoudre un tel problème incluent :

• L’intégration des données dans une base de données, puis l’exécution de requêtes, souvent à intervalles réguliers
• Les solutions MapReduce comme Hadoop
• Mechanical Turk  
• Les filtres en temps réel.

Nous sommes fiers de faire beaucoup avec très peu, nous avons donc cherché à voir comment les filtres en temps réel pouvaient fonctionner pour nous. Nous nous sommes concentrés sur la création d’un système permettant à n’importe quel membre des équipes d’ingénierie et de support d’écrire des règles qui réagissent et exécutent des actions en leur nom.

Lors de la conception de ce système, nous avons essayé de créer quelque chose qui donnerait à chacun les outils nécessaires pour itérer rapidement et répondre aux menaces pesant sur notre système, tout en devant se conformer aux règles suivantes :

1. Les utilisateurs doivent pouvoir ajouter leurs propres règles à volonté
2. Le langage dédié, ci-après appelé DSL, doit être aussi simple que possible et ressembler idéalement à quelque chose qu’ils connaissent déjà.
3. Les membres de l’équipe doivent pouvoir tester leurs règles sur les données historiques avant de les appliquer.

Nous utilisons Kibana en interne, donc quelque chose qui pourrait être testé avec cet outil pour remplir le point numéro 3 était idéal. Cela nous a conduits à une conclusion évidente : nous devions écrire un analyseur DSL inspiré de Lucene ! 

La première itération du système s’appuyait sur des expressions régulières et beaucoup d’analyses caractère par caractère. Cela faisait l’affaire, mais les itérations suivantes ont rapidement gagné en complexité. Si vous avez déjà travaillé sur un vaste projet d’analyse de chaînes de caractères, vous voyez ce que nous voulons dire.

Pour aller plus loin, nous savions que nous devions créer quelque chose qui pourrait être itéré rapidement, et idéalement, conforme à une norme connue.

Ceux d’entre nous qui ont suivi des cours universitaires sur la théorie des automates ou similaires se souviennent probablement des grammaires dans le contexte des langages de programmation. Par ailleurs, il est certain que certains lecteurs auront bien plus d’expertise que votre humble auteur en la matière. Pour toute explication approfondie, nous vous renvoyons donc à votre moteur de recherche préféré.

Il est tout de même utile de parler brièvement de ce qui constitue une grammaire et de la raison pour laquelle elles sont utiles. Pour citer Wikipédia, une Grammaire formelle est « …un ensemble de règles de production pour les chaînes de caractères dans un langage formel. Les règles décrivent comment former des chaînes à partir de l’alphabet du langage qui sont valides selon la syntaxe de ce langage. Une grammaire ne décrit pas le sens des chaînes ni ce que l’on peut en faire dans un contexte donné, mais seulement leur forme. »

Au risque de simplifier à l’extrême, cela nous permet de prendre une chaîne de caractères comme « Vous avez un email ! » et de la décomposer en jetons que nous pouvons analyser sémantiquement. En d’autres termes, si notre grammaire est bien définie, nous pouvons alors procéder à un codage supplémentaire pour déterminer le sens de cette chaîne.

L’histoire et les types de grammaires pourraient remplir des tonnes de livres et dépassent donc largement le cadre d’un article de blog. Nous allons plutôt nous concentrer sur les grammaires non contextuelles (ou algébriques) et plus spécifiquement, sur les grammaires d’expression d’analyse (PEG).

Pour citer à nouveau Wikipédia, une Grammaire non contextuelle est « un certain type de grammaire formelle : un ensemble de règles de production qui décrivent toutes les chaînes de caractères possibles dans un langage formel donné. Les règles de production sont de simples remplacements. »

Autrement dit, une grammaire non contextuelle définit un graphe qui, à son tour, définit comment analyser un langage. Comme mentionné ci-dessus, cela ne nous dit pas comment comprendre le langage. Il convient également de mentionner, comme nous le verrons ci-dessous, que le graphe peut comporter des cycles, mais qu’il finit par s’arrêter.

Les grammaires non contextuelles ont en quelque sorte une cousine avec la Grammaire d’expression d’analyse, ou PEG. Elles ressemblent beaucoup à une grammaire non contextuelle (CFG), mais avec une distinction très utile : lorsqu’elle est confrontée à un choix ambigu, la PEG choisira toujours la première règle de production définie. La CFG, en revanche, laisse le choix ambigu, et pourquoi s’embêter avec l’ambiguïté quand ce n’est pas nécessaire ?

Ce que cela signifie vraiment, c’est qu’il est plus facile d’écrire des outils pour définir des PEG. Heureusement, de nombreuses personnes l’ont déjà fait pour nous.

Après quelques recherches, nous avons opté pour Pigeon comme base pour notre PEG. Pigeon suit le même paradigme que de nombreux outils Go en générant un code qui se compile en même temps que votre programme.

Son utilisation est assez simple : vous définissez à la fois la grammaire et le code Go pour gérer chacune des règles dans le même package, et vous appelez simplement Parse() sur l’analyseur généré. Le défi consiste à écrire des gestionnaires pour chacune de ces règles. Tout comme les grammaires, le sujet de la compilation pourrait remplir une bibliothèque entière de livres. Heureusement pour nous, écrire un interpréteur est moins complexe, et le code résultant est suffisamment rapide pour nos besoins.

De plus, la syntaxe tente de s’aligner étroitement sur la syntaxe Go elle-même, ce qui facilite l’écriture de votre PEG en parallèle de votre programme Go utilisant la grammaire.

Imaginons que vous ayez un événement généré par l’envoi d’un email, encodé en JSON, qui ressemble à ceci :

{
 "event": "sent",
 "subject": "A special offer just for you!",
 "account": "12345",
}

Il y a plusieurs façons de considérer cet événement : vous pourriez décider qu’il s’agit d’un email inoffensif, ou vous pourriez vous dire « Il pourrait s’agir de spam, mais il n’y a pas assez d’informations pour trancher ». Il s’agit d’un problème très courant dans notre système, qui nécessite toujours un grand nombre de données agrégées pour parvenir à une conclusion.

Écrivons donc une règle qui correspondra à l’événement ci-dessus :

                                

                                    event:"sent" AND subject:"A special offer just for you!"
                                
                            

C’est assez facile à analyser et, mieux encore, cela peut aussi être vérifié dans Kibana !

Voyons maintenant comment construire une PEG très simple qui correspondrait à cette règle. Nous allons implémenter chaque règle de production une par une et expliquer son fonctionnement. Les noms des règles suivent généralement le PascalCase et autorisent également les chiffres et les tirets du bas (underscores). Chaque règle prend la forme suivante :

                                

                                    RuleName <- 
                                
                            

Notez qu’il existe en fait plusieurs caractères autorisés pour l’opérateur de définition de règle, mais nous préférons <- car il est facile à taper et ressemble davantage aux grammaires telles qu'elles sont définies de manière académique.

La première règle de la grammaire est traitée comme le point d’entrée :

                                

                                    Input <- Term !.
                                
                            

Notre règle Input dit « Faire correspondre toute la chaîne d’entrée » avec !. ce qui signifie « Faire correspondre la fin du fichier ». Cela transmettra l’ensemble de la chaîne d’entrée à une règle nommée Term qui ressemble à ceci :

                                

                                    Term <- Variable AndVar*
                                
                            

Cela transmet le flux de contrôle à la règle de production de la variable :

                                

                                    Variable <-  FieldChars+ _ ":" _ Value
                                
                            

Maintenant, cela devient un peu plus complexe. Tout d’abord, nous faisons correspondre de manière gourmande tous les caractères jusqu’à ce que la règle FieldChars soit satisfaite. Notez le + présent à la fin. La syntaxe PEG a beaucoup en commun avec les expressions régulières, cela signifie donc « Faire correspondre la règle FieldChars une ou plusieurs fois »

                                

                                    FieldChars <- [a-z]
                                
                            

Là encore, si vous connaissez la syntaxe regex, cela devrait être très clair : il suffit de faire correspondre un seul caractère compris entre « a » et « z »

Revenons maintenant à la variable, la partie suivante _ est une règle signifiant « faire correspondre n’importe quel caractère d’espacement ». Notez que _ est un identifiant tout à fait valide pour une règle de production, et avoir moins à taper est généralement une bonne chose.

                                

                                    _ "whitespace" <- [ \n\t\r]*
                                
                            

Il y a deux ou trois choses à noter ici :

1. La chaîne de caractères « whitespace » est le « nom convivial » et existe à des fins de documentation et pour votre santé mentale future.
2. Comme pour la syntaxe des expressions régulières, cela correspondra à toute forme d’espace blanc, de saut de ligne, de tabulation ou de retour chariot.

La partie suivante de la règle de la variable correspond à la chaîne littérale « AND ». Difficile de faire plus simple.

Ensuite, nous avons une autre règle d’espacement, et enfin la règle Value.

                                

                                    Value <- '"' ValueChars* '"'
                                
                            

Cette règle correspond à la chaîne littérale '"', à zéro ou plusieurs règles ValueChars, et enfin à un autre guillemet.

ValueChars ressemble à ce qui suit :

                                

                                    How we built a Lucene-inspired parser in Go

                                
                            

Ces ValueChars correspondront aux lettres minuscules et majuscules de l’alphabet, à n’importe quel chiffre, aux espaces et au point d’exclamation.

Pourquoi avoir défini Value de cette façon ? Parce que la règle peut supprimer les guillemets doubles pour nous afin que nous n’ayons pas à le faire, et puis nous sommes paresseux. Il ne s’agit toutefois que d’une commodité que nous aurions pu omettre au profit de l’inclusion de la forme de la règle Value avec la définition de la règle de la variable.

Enfin, AndVar devrait vous paraître assez simple à ce stade. Notez qu’il fait référence à Term et implémente le cycle susmentionné.

                                

                                    ValueChars <- [a-zA-Z0-9 !]
                                
                            

La définition complète ressemble à ce qui suit.

                                

                                    Input <- Term !.
Term <- Variable AndVar*
AndVar <- _ "AND" _ Term
Variable <- FieldChars+ _ ":" _ Value
_ "whitespace" <- [ \n\t\r]*
Value <- '"' ValueChars '"'
FieldChars <- [a-z]
ValueChars <- [a-zA-Z0-9 !]
                                
                            

La véritable valeur de la définition de votre propre grammaire apparaît lorsque vous fournissez des implémentations pour les actions des règles. Examinons la véritable définition PEG :

                                

                                    {
 package main

 import (
   "strings"
 )

 type Node interface {
   Evaluate(input Event) (bool, error)
 }

 type Term struct {
   node Node
 }

 func (t *Term) Evaluate(input Event) (bool, error) {
   return t.node.Evaluate(input)
 }

 type AndNode struct {
   Nodes []Node
 }

 func (n *AndNode) Evaluate(input Event) (bool, error) {
   for _, node := range n.Nodes {
     matched, err := node.Evaluate(input)
     if err != nil {
       return false, err
     }
     if !matched {
       return false, nil
     }
   }
   return true, nil
 }

 type Variable struct {
   Field string
   Value string
 }

 func (v *Variable) Evaluate(input Event) (bool, error) {
   fieldVal, ok := input[v.Field]
   if !ok {
     return false, fmt.Errorf("Field '%s' not present in the event", v.Field)
   }

   return fieldVal == v.Value, nil
 }

 func toString(label interface{}) string {
   var sb strings.Builder
   value := label.([]interface{})
   for _, i := range(value) {
     if i == nil {
       continue
     }
     switch b := i.(type) {
     case []byte:
       sb.WriteByte(b[0])
     case []interface{}:
       s := toString(i)
       sb.WriteString(s)
     default:
       fmt.Printf("She's dead, Jim %T %+v\n", i, i)
     }
   }
   return sb.String()
 }
}

Input <- Term !.

Term <- variable:Variable rest:AndVar* {
 andVars := rest.([]interface{})
 variables := make([]Node, 0, len(andVars))
 variables = append(variables, variable.(Node))
 for _, r := range(andVars) {
      variables = append(variables, r.(Node))
   }
   return &AndNode{Nodes: variables}, nil
}

AndVar <- _ "AND" _ rightSide:Term {
   return rightSide, nil
}
​
Variable <- field:FieldChars+ _ ":" _ value:Value {
   return &Variable{Field: toString(field), Value: toString(value)}, nil
}

Value <- '"' value:ValueChars* '"' {
   return value, nil
}

_ "whitespace" <- [ \n\t\r]*
FieldChars <- [a-z]
ValueChars <- [a-zA-Z0-9 !]
                                
                            

Il y a beaucoup à analyser ici, procédons étape par étape.

En haut, nous avons une section de code entourée d’accolades. Il s’agit d’une convention de Pigeon qui prend le code inclus textuellement et l’injecte dans la sortie de code générée finale. Notez que vous pouvez définir ici les types pertinents pour votre grammaire par commodité, ou les placer dans un autre fichier, car Pigeon utilisera le nom du package que vous déclarez ici. Tout ce qui suit correspond à la définition de la grammaire elle-même.

À ce stade, vous avez probablement remarqué que les règles diffèrent un peu de la façon dont nous les avons définies plus haut. Jetons un œil à Term.

                                

                                    Term <- variable:Variable rest:AndVar*
                                
                            

C’est presque la même définition de Term que précédemment, mais nous l’avons maintenant rendue utile. Le préfixage d’une règle dans la définition par name : attribue la valeur de retour de cette règle à ce nom, puis transmet name à la fonction définie par l’action de votre règle lors de la génération du code. L’intégralité du code entre les accolades devient une fonction associée à cette règle et est appelée lorsque la règle est satisfaite :

                                

                                    func (c *current) onTerm1(variable, rest interface{}) (interface{}, error) {
 andVars := rest.([]interface{})
 variables := make([]Node, 0, len(andVars))
 variables = append(variables, variable.(Node))
 for _, r := range andVars {
   variables = append(variables, r.(Node))
 }
 return &AndNode{Nodes: variables}, nil
}
                                
                            

Ici, nous pouvons voir que Pigeon traite entièrement avec des types d’interface vides. C’est excellent pour la flexibilité, mais moins pratique pour l’écriture de l’implémentation car nous devons en tenir compte.

                                

                                    andVars := rest.([]interface{})
variables := make([]Node, 0, len(andVars))
variables = append(variables, variable.(Node))
for _, r := range andVars {
 variables = append(variables, r.(Node))
}
return &AndNode{Nodes: variables}, nil
                                
                            

Comme mentionné précédemment, nous pouvons avoir des cycles dans les règles. Compte tenu de cela, nous savons qu’il est possible de recevoir un nombre infini de Termes mappés à la variable rest. Pigeon gère cela en nous donnant une tranche d’interfaces vides. Nous avons créé une interface Node dans laquelle tout doit être inféré avant de pouvoir les utiliser.

Après avoir parcouru toute la liste des variables AND, nous créons un AndNode contenant chacun des termes. La définition du AndNode se trouve dans la section littérale du code définie en haut de la PEG. En tant qu’implémentation de l’interface Node, elle définit une méthode Evaluate qui indique que l’expression est évaluée à vrai uniquement si tous les termes individuels le sont également.

À ce stade, le reste de la définition devrait être compréhensible, passons donc à l’exécution de l’ensemble. Le listing de code suivant montre l’analyse de notre règle, son utilisation, ainsi que quelques exemples supplémentaires pour illustrer les échecs et la gestion des erreurs :

                                

                                    package main

import (
 "fmt"
)

type Event map[string]string

func Match(rule string, event Event) (bool, error) {
 // Parse is generated by pigeon in this package
 tree, err := Parse("parsing", []byte(rule))
 if err != nil {
   return false, err
 }

 // Yes, this is a bit ugly. It's a consequence of pigeon dealing in interface slices
 iface, ok := tree.([]interface{})
 if !ok {
   return false, fmt.Errorf("Internal Error")
 }

 ast, ok := iface[0].(Node)
 if !ok {
   return false, fmt.Errorf("Internal Error")
 }

 // ast is the tree generated by our supplementary Go defined by the production rules
 return ast.Evaluate(event)
}

func main() {
  rules := []string{
   "event:\"sent\" AND subject:\"A special offer just for you!\"",
   "event:\"found\" AND subject:\"A special offer just for you!\"",
   "event:\"sent\" AND badfield:\"A special offer just for you!\"",
  }

  event := map[string]string{
    "event":   "sent",
    "subject": "A special offer just for you!",
    "account": "12345",
  }

  for _, rule := range rules {
    matched, err := Match(rule, Event(event))
    if err != nil {
      fmt.Printf("Rule '%s' failed with error '%s'\n", rule, err.Error())
    } else {
      fmt.Printf("Rule '%s' matched: %t\n", rule, matched)
    }
  }
}
                                
                            

Il vous suffit d’exécuter :

~> go get github.com/mna/pigeon   ~> pigeon rules.peg > rules.go   ~> go run . Rule 'event:"sent" AND subject:"A special offer just for you!"' matched: true Rule 'event:"found" AND subject:"A special offer just for you!"' matched: false Rule 'event:"sent" AND badfield:"A special offer just for you!"' failed with error 'Field 'badfield' not present in the event'

Félicitations ! Vous avez maintenant écrit votre propre langage à l’utilité extrêmement limitée !

À ce stade, vous vous dites peut-être :

1. Beaucoup d’expéditeurs n’utilisent-ils pas des objets de ce genre ?
2. Un moteur de règles qui ne fait correspondre que des chaînes littérales est-il vraiment si utile ?
3. Cet article n’aurait-il pas pu être deux fois plus court ?

Ce à quoi nous répondrions :

1. Nous voudrions implémenter une sorte de traitement pour le champ account tel que défini dans l’événement d’origine. Mailgun résout ce problème en incluant une logique métier dans la base de code pour prendre en charge la limitation de débit basée sur un champ défini. En d’autres termes, nous pouvons dire : « Si cette règle correspond, enregistrez le compte et l’heure actuelle et n’effectuez pas cette action pour ce compte pendant les N prochaines minutes. » Évidemment, si nous n’avions pas cette gestion et que l’expéditeur en question envoyait un million d’emails, le support serait notifié un million de fois. Ce serait un excellent moyen de noyer votre équipe de support sous le bruit et de vous faire agresser sur le parking après le travail.
2. On pourrait implémenter des règles pour analyser des expressions régulières et des sous-chaînes qui seraient bien plus utiles qu’une correspondance de chaîne explicite. C’est d’ailleurs exactement ce que nous avons fait.
3. Désolé.

Enfin, vous avez probablement remarqué que nous n’avons pas défini ce que la règle ferait ici lorsqu’elle correspond effectivement. L’une des solutions possibles est de faire en sorte que la règle publie sur un canal Slack lorsqu’elle est déclenchée. Il s’agit d’une solution courante ici chez Mailgun, et elle se présente comme suit :

slack:#channel-name

À ce stade, nous espérons que votre esprit foisonne de possibilités. Voici quelques réflexions que nous avons eues :

1. Il y a bien plus à émuler dans la syntaxe Lucene, comme les opérateurs NOT et OR, ou les parenthèses.
2. Fournir une grammaire séparée pour les actions.
3. Implémenter la création de modèles pour injecter des valeurs de l’événement dans l’action.
4. Ajouter du sucre syntaxique pour faciliter l’écriture de certains filtres.
5. Implémenter un système pour compter et réagir à un nombre spécifique d’occurrences d’événements sur une période donnée.
6. Implémenter un cache, car l’analyse des règles est quelque peu coûteuse.

Il y a beaucoup d’autres choses que vous pouvez faire, en particulier lorsqu’il s’agit d’étoffer l’analyseur d’actions. Vous pourriez appeler d’autres services, notifier des clients, allumer ou éteindre les lumières, et bien plus encore. Lorsqu’il s’agit d’inventer vos propres outils sur cette base, il n’y a pas de limites.

À ce stade, vous vous demandez peut-être : « Pourquoi n’ont-ils pas utilisé $SOME_OTHER_TOOL ? » 

La réponse est que nous n’avons pas encore besoin de la puissance de ces outils, ni de la complexité qui accompagne souvent leur exploitation. Notre outil actuel de traitement de flux est un simple binaire unique déployé dans un conteneur, qui fonctionne tout simplement (Just Works™). Il y a très peu de choses à gérer et il suit facilement notre flux d’événements à très haut volume.

1. C’est facile à développer
2. Il utilise toujours des outils open source et prêts à l’emploi
3. Il peut être adapté exactement à nos besoins
4. La syntaxe de notre DSL est minuscule, facile à articuler et à comprendre, et elle oblige tout le monde à écrire les règles à peu près de la même manière. Elle rend également plus difficile la création d’effets secondaires indésirables

1. Les fonctionnalités du langage qui vont au-delà de ce que nous avons déjà implémenté représentent un saut substantiel en matière de complexité.
2. La mise à jour de la PEG source générera un nouveau code, et cela perturbe vraiment vos diffs de code.
3. La simplicité délibérée de Lucene peut rendre difficile l’écriture de règles plus complexes.

Nous finirons peut-être par décider que $SOME_OTHER_TOOL est plus adapté à nos besoins, mais dans un avenir prévisible, la puissance que notre DSL Mailgun apporte est plus que suffisante.

À ce stade, nous espérons avoir démontré en quoi l’écriture de votre propre DSL peut s’avérer utile. Notre implémentation traite un nombre considérable d’événements par jour tout en facilitant grandement la vie de nombreux membres de notre équipe (du moins, c’est ce que nous leur disons). 

Quant aux fonctionnalités qu’il prend en charge, nous ne faisons que commencer. Si cela vous a inspiré et que vous souhaitez implémenter votre propre grammaire de traitement de flux, n’hésitez pas à nous le faire savoir. Nous serions ravis d’en entendre parler !

Auteur·trice: Matthew Dietz Software Developer IV at Sinch Mailgun