Cómo creamos un parser inspirado en Lucene en Go

En Mailgun tenemos numerosos sistemas que generan muchísimos eventos cada hora del día. Es un número tan grande que resulta imposible para un equipo humano clasificar los resultados de ElasticSearch y esperar resultados coherentes o mantener la cordura.

Como muchas empresas, seguimos necesitando encontrar una manera de lidiar con todos los datos. Esto supone una tarea considerable: crear un sistema que permita a nuestros clientes internos reaccionar a los eventos en tiempo real.

Tradicionalmente, las opciones para resolver este tipo de problema incluyen:

• Introducir los datos en una base de datos y luego ejecutar consultas, a menudo en un intervalo de tiempo fijo
• Soluciones MapReduce como Hadoop
• Mechanical Turk  
• Filtros en tiempo real.

Nos enorgullece hacer mucho con muy poco, así que nos propusimos descubrir cómo hacer que los filtros en tiempo real nos sirvieran. Nos centramos en construir un sistema que permita básicamente a cualquier persona de los equipos de ingeniería y asistencia escribir reglas que reaccionen y realicen acciones en su nombre.

Al diseñar este sistema, intentamos crear algo que diera a todo el mundo las herramientas para iterar rápidamente y responder a las amenazas de nuestro sistema, y que cumpliera con las siguientes reglas:

1. Los usuarios deberían poder añadir sus propias reglas a voluntad
2. El lenguaje de dominio específico (en adelante, DSL) debería ser lo más sencillo posible e idealmente parecerse a algo que ya conocen.
3. La gente debería poder probar sus reglas con datos históricos antes de aplicarlas.

A nivel interno usamos Kibana, así que lo ideal era algo que pudiera probarse con él para cumplir el punto número 3. Esto nos lleva a una conclusión sencilla: ¡deberíamos escribir un parser de DSL inspirado en Lucene! 

La primera iteración del sistema se basó en expresiones regulares y mucho análisis carácter por carácter. Cumplía su función, pero las iteraciones posteriores aumentaron rápidamente en complejidad. Si alguna vez has hecho un proyecto grande de análisis de cadenas (strings), sabes a qué nos referimos.

De cara al futuro, sabíamos que teníamos que crear algo sobre lo que se pudiera iterar rápidamente y, a ser posible, que se ajustara a un estándar conocido.

Quienes hemos hecho cursos universitarios de teoría de autómatas y similares, probablemente recordemos las gramáticas en el contexto de los lenguajes de programación. Además, es un hecho que parte del público tendrá mucha más experiencia en esta materia que quien escribe estas líneas, por lo que cualquier explicación en profundidad deberá consultarse en tu motor de búsqueda de confianza.

Sigue siendo útil hablar brevemente sobre qué compone una gramática y por qué son útiles. Citando a Wikipedia, una gramática formal es “…un conjunto de reglas de producción de cadenas (strings) en un lenguaje formal. Las reglas describen cómo formar cadenas a partir del alfabeto del lenguaje que sean válidas según su sintaxis. Una gramática no describe el significado de las cadenas ni lo que se puede hacer con ellas en un contexto determinado; solo su forma”.

A riesgo de simplificar demasiado, nos permite tomar una cadena como “¡Tienes un email!” y desglosarla en tokens que podemos analizar semánticamente. En otras palabras, si nuestra gramática está bien definida, podemos escribir código adicional para determinar el significado de esa cadena.

La historia y los tipos de gramáticas pueden llenar montones de libros, por lo que van mucho más allá del alcance de un artículo de blog. En su lugar, nos centraremos en las gramáticas libres de contexto y, más específicamente, en las gramáticas de expresiones de análisis sintáctico.

Citando de nuevo a Wikipedia, una gramática libre de contexto es “un determinado tipo de gramática formal: un conjunto de reglas de producción que describen todas las cadenas posibles en un lenguaje formal dado. Las reglas de producción son simples reemplazos”.

Dicho de otra forma, una gramática libre de contexto define un grafo que a su vez define cómo analizar sintácticamente un lenguaje. Como hemos mencionado antes, no nos dice cómo entender el lenguaje. También cabe mencionar, como veremos más adelante, que el grafo puede tener ciclos, pero acaba terminando.

Las gramáticas libres de contexto tienen una especie de prima en la gramática de expresiones de análisis sintáctico, o PEG (por sus siglas en inglés). Se parecen mucho a una gramática libre de contexto, o CFG, pero incluyen una distinción muy útil: ante una opción ambigua, la PEG siempre elegirá la primera regla de producción definida. En cambio, la CFG deja la opción ambigua, y ¿por qué lidiar con la ambigüedad cuando no tenemos que hacerlo?

Lo que esto significa realmente es que resulta más fácil escribir herramientas para definir las PEG. Por suerte, mucha gente ya lo ha hecho por nosotros.

Tras un poco de investigación, nos decidimos por Pigeon como la base de nuestra PEG. Pigeon sigue el mismo paradigma que muchas herramientas de Go al generar código que se compila junto con tu programa.

Su uso es bastante fácil: defines tanto la gramática como el código de Go para manejar cada una de las reglas en el mismo paquete, y simplemente llamas a Parse() en el parser generado. El desafío consiste en escribir controladores para cada una de esas reglas. Al igual que las gramáticas, el tema de la compilación podría llenar una biblioteca entera de libros. Por suerte para nosotros, escribir un intérprete es menos complejo y el código resultante es lo bastante rápido para nuestras necesidades.

Además, la sintaxis intenta alinearse estrechamente con la propia sintaxis de Go, lo que lo hace más fácil a la hora de escribir tu PEG junto a tu programa de Go que utilice la gramática.

Supongamos que tienes un evento generado al enviar un email, codificado en JSON, parecido al siguiente:

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

Hay un par de maneras de ver este evento: podrías decidir que se trata de un email inofensivo, o podrías decir “Esto podría ser spam, pero no hay suficiente información para decidirlo”. Este es un problema muy común en nuestro sistema, y siempre requiere muchísimos datos agregados para llegar a una conclusión.

Así pues, vamos a escribir una regla que coincida con el evento anterior:

                                

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

Es bastante fácil de analizar, y lo que es mejor, ¡también se puede comprobar en Kibana!

Ahora vamos a repasar la construcción de una PEG muy sencilla que coincidiría con esta regla. Implementaremos cada regla de producción de una en una y explicaremos qué hace. Los nombres de las reglas normalmente siguen PascalCase , además de permitir números y guiones bajos. Cada regla adopta la forma:

                                

                                    RuleName <- 
                                
                            

Ten en cuenta que, en realidad, hay varios caracteres legales para el operador de definición de reglas, pero nos gusta <- porque es fácil de escribir y se parece más a las gramáticas tal y como se definen académicamente.

La primera regla de la gramática se trata como el punto de entrada:

                                

                                    Input <- Term !.
                                
                            

Nuestra regla Input dice “Haz que coincida toda la cadena de entrada” con !. que significa “Haz que coincida con el final del archivo”. Esto pasará la cadena de entrada completa a una regla llamada Term que tiene el siguiente aspecto:

                                

                                    Term <- Variable AndVar*
                                
                            

Esto pasa el flujo de control a la regla de producción Variable:

                                

                                    Variable <-  FieldChars+ _ ":" _ Value
                                
                            

Ahora la cosa se vuelve un poco más compleja. Primero, hacemos coincidir de forma codiciosa todos los caracteres hasta que se cumpla la regla FieldChars. Fíjate en el + del final. La sintaxis PEG comparte mucho con las expresiones regulares, así que esto dice “Haz que la regla FieldChars coincida una o más veces”.

                                

                                    FieldChars <- [a-z]
                                
                            

De nuevo, si estás familiarizado con la sintaxis regex esto debería ser sencillo: simplemente haz coincidir cualquier carácter individual entre “a” y “z”.

Volviendo a Variable, la siguiente parte _ es una regla que dice “haz que coincida con cualquier carácter de espacio en blanco”. Ten en cuenta que _ es un identificador completamente válido para una regla de producción, y escribir menos suele ser algo bueno.

                                

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

Aquí hay un par de cosas a tener en cuenta:

1. La cadena “whitespace” es el “nombre descriptivo” y existe para fines de documentación y para tu futura salud mental.
2. Al igual que con la sintaxis de expresiones regulares, esto coincidirá con cualquier forma de espacio en blanco, saltos de línea, tabulaciones o retornos de carro.

La siguiente parte de la regla Variable coincide con el literal de cadena “AND”. No puede ser más fácil que eso.

A continuación, tenemos otra regla de espacio en blanco, y finalmente la regla Value.

                                

                                    Value <- '"' ValueChars* '"'
                                
                            

Esta regla coincide con el literal de cadena '"', con cero o más reglas ValueChars y, por último, con otra comilla.

ValueChars tiene el siguiente aspecto:

                                

                                    How we built a Lucene-inspired parser in Go

                                
                            

Estos ValueChars coincidirán con el alfabeto en minúsculas y mayúsculas, cualquier número, espacios y el signo de exclamación.

¿Por qué definimos Value de esta manera? Porque la regla puede quitarnos las comillas dobles para que no tengamos que hacerlo nosotros, y además porque somos algo vagos. Sin embargo, es simplemente una comodidad que podríamos haber omitido en favor de incluir la forma de la regla de Value con la definición de la regla Variable.

Finalmente, AndVar debería parecer bastante sencillo llegados a este punto. Observa que hace referencia a Term e implementa el ciclo mencionado anteriormente.

                                

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

La definición completa tiene el siguiente aspecto.

                                

                                    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 !]
                                
                            

El valor real de definir tu propia gramática surge cuando proporcionas implementaciones para las acciones de las reglas. Veamos la definición real de 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 !]
                                
                            

Hay mucho que asimilar aquí, así que vamos a ir paso a paso.

En la parte superior, tenemos una sección de código rodeada de llaves. Esta es una convención de Pigeon que toma el código adjunto tal cual y lo inyecta en la salida final del código generado. Ten en cuenta que puedes definir tipos relevantes para tu gramática aquí por conveniencia, o puedes ponerlos en otro archivo, ya que Pigeon usará el nombre del paquete que declares aquí. Todo lo que va después es la definición de la propia gramática.

Llegados a este punto, probablemente te habrás dado cuenta de que las reglas difieren un poco de cómo las definimos arriba. Echemos un vistazo a Term.

                                

                                    Term <- variable:Variable rest:AndVar*
                                
                            

Esta es casi nuestra definición de Term de antes, pero ahora la hemos hecho útil. Anteponer a una regla en la definición name: asigna el valor de retorno de esa regla a name y luego pasa name a la función definida por la acción de tu regla cuando se genera el código. Todo el código entre las llaves se convierte en una función asociada a esa regla y se llama cuando se cumple la regla:

                                

                                    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
}
                                
                            

Aquí podemos ver que Pigeon trabaja enteramente con tipos de interfaz vacíos. Es genial para la flexibilidad, pero no tanto para escribir la implementación, ya que tenemos que tenerlos en cuenta.

                                

                                    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
                                
                            

Como hemos mencionado anteriormente, podemos tener ciclos en las reglas. Teniendo esto en cuenta, sabemos que es posible recibir un número infinito de Terms mapeados a la variable rest. Pigeon lidia con esto entregándonos un slice de interfaces vacías. Hemos creado una interfaz Node hacia la cual todo debe inferirse por tipo antes de que podamos usarlo.

Tras recorrer toda la lista de variables con el operador AND, creamos un AndNode que contiene cada uno de los Terms. La definición del AndNode se puede encontrar en la sección del literal de código definida en la parte superior del PEG. Como implementador de la interfaz Node, define un método Evaluate que establece que la expresión se evalúa como verdadera (true) solo si todos los términos individuales también se evalúan como verdaderos.

En este punto, el resto de la definición debería cobrar sentido, así que vamos a pasar a su ejecución. El siguiente listado de código muestra el análisis de nuestra regla, su uso y un par de ejemplos adicionales para mostrar fallos y la gestión de errores:

                                

                                    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)
    }
  }
}
                                
                            

Solo tienes que ejecutar:

~> 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'

¡Enhorabuena! ¡Acabas de escribir tu propio lenguaje de utilidad extremadamente limitada!

Llegados a este punto tal vez te estés preguntando:

1. ¿No hay muchos remitentes que usan asuntos así?
2. ¿Es tan útil un motor de reglas que solo hace coincidir literales de cadenas?
3. ¿No podría haber sido la mitad de largo este artículo?

A lo que responderíamos:

1. Nos gustaría implementar algún tipo de manejo para la cuenta (account) tal y como se define en el evento original. Mailgun resuelve este problema incluyendo lógica de negocio en el código para ofrecer asistencia a la limitación de peticiones basada en un campo definido. En otras palabras, podemos decir “Si esta regla se cumple, guarda la cuenta y la hora actual y no realices esta acción con esta cuenta durante los próximos N minutos”. Obviamente, si no tuviéramos esta gestión y el remitente en cuestión enviara un millón de emails, el servicio de asistencia recibiría un millón de notificaciones. Esa sería una forma estupenda de ahogar a tu equipo de asistencia en el ruido y también de que te asalten en el aparcamiento al salir del trabajo.
2. Se podrían implementar reglas para analizar sintácticamente expresiones regulares y subcadenas que resultarían mucho más útiles que una coincidencia explícita de cadenas. De hecho, hemos hecho exactamente eso.
3. Lo siento.

Por último, es probable que te hayas dado cuenta de que no definimos lo que haría la regla aquí cuando sí coincide. Una posible solución es hacer que la regla se publique en un canal de Slack cuando salte el disparador. Esta es una solución común aquí en Mailgun, y tiene el siguiente aspecto:

slack:#channel-name

Con suerte, en este punto, tu cabeza estará dándole vueltas a todas las posibilidades. Estas son algunas de las ideas que hemos tenido:

1. Hay mucho más que emular en la sintaxis de Lucene, como las declaraciones NOT y OR, y los paréntesis.
2. Proporcionar una gramática independiente para las acciones.
3. Implementar el uso de plantillas para inyectar valores del evento en la acción.
4. Añadir azúcar sintáctico para facilitar la redacción de algunos filtros.
5. Implementar un sistema para contar y reaccionar ante un número específico de apariciones de eventos a lo largo de un período de tiempo.
6. Implementar una memoria caché porque analizar las reglas resulta un poco costoso.

Hay un montón de cosas más que puedes hacer, sobre todo en lo que respecta a desarrollar el parser de acciones. Podrías llamar a otros servicios, avisar a los clientes, encender y apagar las luces, y mucho más. A la hora de inventar tus propias herramientas basándote en esto, el cielo es el límite.

Llegados a este punto, tal vez te preguntes: “¿Por qué no usaron $SOME_OTHER_TOOL?” 

La respuesta es porque todavía no necesitamos la potencia de ninguna de esas herramientas ni la complejidad que a menudo conlleva operarlas. Nuestra actual herramienta de procesamiento de flujos es un único y sencillo binario desplegado en un contenedor que simplemente funciona (Just Works™). Hay muy poco que gestionar, y sigue fácilmente el ritmo de nuestro flujo de eventos de altísimo volumen.

1. Es fácil de desarrollar
2. Sigue utilizando herramientas de código abierto (FOSS) y comerciales estándar
3. Se puede adaptar exactamente a nuestras necesidades
4. La sintaxis de nuestro DSL es muy pequeña, fácil de articular y de razonar, y obliga a todo el mundo a escribir las reglas más o menos de la misma forma. También hace que sea más difícil crear efectos secundarios no deseados

1. Las características del lenguaje que van más allá de lo que ya hemos implementado representan un salto sustancial en complejidad.
2. Actualizar el código fuente del PEG generará nuevo código, y realmente ensucia los diffs de tu código.
3. La simplicidad deliberada de Lucene puede dificultar la redacción de reglas más complejas.

Con el tiempo, puede que decidamos que $SOME_OTHER_TOOL es más adecuada para nuestras necesidades, pero a corto o medio plazo, la potencia que aporta nuestro DSL de Mailgun es más que suficiente.

Llegados a este punto, esperamos haber demostrado cómo escribir tu propio DSL podría resultar útil. Nuestra implementación procesa una enorme cantidad de eventos al día mientras que facilita mucho la vida a muchos integrantes de nuestro equipo (o al menos eso es lo que les decimos). 

En cuanto a las características a las que da asistencia, solo acabamos de empezar. Si esto te ha inspirado para estudiar la implementación de tu propia gramática de procesamiento de flujos, avísanos. ¡Nos encantaría saberlo!

Autor: Matthew Dietz Software Developer IV at Sinch Mailgun