Como criamos um parser inspirado no Lucene em Go

Na Mailgun, temos vários sistemas gerando uma enorme quantidade de eventos a cada hora do dia. É um número tão grande que é impossível para uma equipe classificar os resultados do ElasticSearch e esperar resultados consistentes, ou até mesmo manter a sanidade.

Como muitas empresas, ainda precisamos encontrar uma maneira de lidar com todos os dados. Isso cria uma tarefa substancial: criar um sistema que permita aos nossos clientes internos reagir a eventos em tempo real.

Tradicionalmente, as opções para resolver esse problema incluem:

• Inserir os dados em um banco de dados e, em seguida, executar consultas de banco de dados, muitas vezes em um intervalo de tempo fixo
• Soluções map-reduce, como o Hadoop
• Mechanical Turk  
• Filtros em tempo real.

Temos orgulho de fazer muito com muito pouco, então decidimos ver como poderíamos fazer os filtros em tempo real funcionarem para nós. Focamos em construir um sistema que permita essencialmente a qualquer pessoa nas equipes de engenharia e suporte escrever regras que reajam e executem ações em seu nome.

Ao projetar esse sistema, tentamos construir algo que desse a todo mundo as ferramentas para iterar e responder rapidamente a ameaças ao nosso sistema, e que tivesse de estar em conformidade com as seguintes regras:

1. Os usuários devem poder adicionar as próprias regras à vontade
2. A linguagem de domínio específico, doravante chamada de DSL, deve ser o mais simples possível e, de preferência, se parecer com algo que já conhecem.
3. As pessoas devem poder testar as próprias regras nos dados históricos antes de aplicá-las.

Usamos o Kibana internamente, então algo que pudesse ser testado nele para cumprir o ponto número três seria o ideal. Isso nos leva a uma conclusão direta: devemos escrever um parser de DSL inspirado no Lucene! 

A primeira iteração do sistema dependia de expressões regulares e muito parsing de caractere por caractere. Isso resolveu o problema, mas as iterações subsequentes cresceram rapidamente em complexidade. Se você já fez algum grande projeto de parsing de strings, sabe do que estamos falando.

Seguindo em frente, sabíamos que tínhamos de construir algo que pudesse ser iterado rapidamente e que, idealmente, estivesse em conformidade com um padrão conhecido.

Quem de nós já fez cursos universitários de Teoria dos Autômatos e afins provavelmente se lembra das gramáticas no contexto das linguagens de programação. Além disso, é certo que algumas pessoas lendo isso terão muito mais conhecimento do que este humilde autor no assunto, então deixe as explicações mais aprofundadas para o seu mecanismo de busca preferido.

Ainda assim, é útil falar brevemente sobre o que compõe uma gramática e a sua utilidade. Citando a Wikipédia, uma Gramática Formal é “…um conjunto de regras de produção para cadeias de caracteres (strings) em uma linguagem formal. As regras descrevem como formar strings a partir do alfabeto da linguagem que sejam válidas de acordo com a sintaxe da linguagem. Uma gramática não descreve o significado das strings nem o que pode ser feito com elas em qualquer contexto — apenas a sua forma.”

Correndo o risco de simplificar demais, isso nos permite pegar uma string como “Você tem um e-mail!” e dividi-la em tokens que podemos analisar semanticamente. Em outras palavras, se a nossa gramática estiver bem definida, podemos escrever um código adicional para determinar o significado dessa string.

A história e os tipos de gramáticas dariam para preencher muitos livros e, portanto, vão muito além do escopo de um post de blog. Em vez disso, vamos nos concentrar nas gramáticas livres de contexto e, mais especificamente, nas gramáticas de expressão de análise (parsing expression grammars).

Citando a Wikipédia novamente, uma Gramática livre de contexto é “um determinado tipo de gramática formal: um conjunto de regras de produção que descrevem todas as strings possíveis em uma determinada linguagem formal. As regras de produção são simples substituições.”

Dito de outra forma, uma gramática livre de contexto define um grafo que, por sua vez, define como analisar sintaticamente (fazer o parse de) uma linguagem. Conforme mencionado acima, ela não nos diz como entender a linguagem. Também vale a pena mencionar, como veremos abaixo, que o grafo pode ter ciclos, mas acaba terminando.

As gramáticas livres de contexto têm uma espécie de prima na Parsing Expression Grammar, ou PEG. Elas se parecem muito com uma gramática livre de contexto (ou CFG, na sigla em inglês), mas trazem uma distinção muito útil: ao se deparar com uma escolha ambígua, a PEG sempre escolherá a primeira regra de produção definida. Por outro lado, a CFG deixa a escolha ambígua, e por que nos preocuparmos com a ambiguidade se não somos obrigados?

O que isso realmente significa é que é mais fácil criar ferramentas para definir as PEGs. Felizmente, muitas pessoas já fizeram isso por nós.

Depois de algumas pesquisas, escolhemos o Pigeon como base da nossa PEG. O Pigeon segue o mesmo paradigma de muitas ferramentas de Go, gerando um código que é compilado junto com o seu programa.

O seu uso é bastante simples: você define tanto a gramática quanto o código em Go para processar cada uma das regras no mesmo pacote, e simplesmente chama Parse() no parser gerado. O desafio é escrever handlers para cada uma dessas regras. Assim como as gramáticas, o tema da compilação daria para preencher uma biblioteca de livros. Felizmente para nós, escrever um interpretador é menos complexo e o código resultante é suficientemente rápido para as nossas necessidades.

Além disso, a sintaxe procura se alinhar ao máximo com a própria sintaxe do Go, o que facilita na hora de escrever a sua PEG junto com o seu programa em Go utilizando a gramática.

Digamos que você tenha um evento gerado pelo envio de um e-mail, codificado em JSON, com a seguinte aparência:

{
 "event": "sent",
 "subject": "Uma oferta especial só para você!",
 "account": "12345",
}

Há algumas maneiras de analisar esse evento: você pode decidir que se trata de um e-mail inofensivo, ou dizer “Isso pode ser spam, mas não há informações suficientes para decidir”. Esse é um problema muito comum no nosso sistema e sempre exige muitos dados agregados para chegarmos a uma conclusão.

Portanto, vamos escrever uma regra que corresponda ao evento acima:

                                

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

Isso é bem fácil de analisar sintaticamente e, melhor ainda, também pode ser verificado no Kibana!

Agora vamos construir uma PEG muito simples que corresponderia a essa regra. Implementaremos cada regra de produção, uma de cada vez, e explicaremos o que ela faz. Os nomes das regras normalmente seguem o padrão PascalCase e permitem o uso de números e underlines. Cada regra adota a seguinte forma:

                                

                                    RuleName <- 
                                
                            

Note que, na verdade, há vários caracteres válidos para o operador de definição de regra, mas gostamos de <-, pois é fácil de digitar e se parece mais com as gramáticas definidas academicamente.

A primeira regra na gramática é tratada como o ponto de entrada:

                                

                                    Input <- Term !.
                                
                            

A nossa regra Input diz “Corresponder a toda a string de entrada” com !. que significa “Corresponder ao final do arquivo”. Isso passará toda a string de entrada para uma regra chamada Term, com a seguinte aparência:

                                

                                    Term <- Variable AndVar*
                                
                            

Isso passa o fluxo de controle para a regra de produção Variable:

                                

                                    Variable <-  FieldChars+ _ ":" _ Value
                                
                            

Agora está ficando um pouco mais complexo. Primeiro, correspondemos todos os caracteres de forma gananciosa até que a regra FieldChars seja satisfeita. Note o + ali no final. A sintaxe da PEG tem muito em comum com as expressões regulares, então isso quer dizer “Corresponder à regra FieldChars uma ou mais vezes”

                                

                                    FieldChars <- [a-z]
                                
                            

Novamente, se você tem familiaridade com a sintaxe de regex, isso deve ser simples: basta corresponder a qualquer caractere único entre “a” e “z”

Voltando agora a Variable, a próxima parte _ é uma regra que diz “corresponder a qualquer caractere de espaço em branco”. Note que o _ é um identificador totalmente válido para uma regra de produção, e digitar menos geralmente é algo bom.

                                

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

Há algumas coisas a serem observadas aqui:

1. A string “whitespace” é o “nome amigável” e existe para fins de documentação e para a sua sanidade no futuro.
2. Como ocorre com a sintaxe de expressões regulares, isso corresponderá a qualquer forma de espaço em branco, quebras de linha, tabulações ou retornos de carro (carriage-returns).

A próxima parte da regra Variable corresponde à string literal “AND”. Não fica muito mais fácil do que isso.

Em seguida, temos outra regra de espaço em branco e, por fim, a regra Value.

                                

                                    Value <- '"' ValueChars* '"'
                                
                            

Essa regra corresponde à string literal '"' , zero ou mais regras ValueChars e, por último, outras aspas.

O ValueChars tem a seguinte aparência:

                                

                                    How we built a Lucene-inspired parser in Go

                                
                            

Esses ValueChars corresponderão ao alfabeto minúsculo e maiúsculo, a qualquer número, espaços e ao ponto de exclamação.

Por que definimos Value dessa maneira? Porque a regra pode retirar as aspas duplas por nós, para não termos que fazer isso, e também porque somos preguiçosos. No entanto, trata-se de uma mera conveniência que poderíamos ter omitido a favor de incluir a forma da regra Value junto com a definição da regra Variable.

Por fim, o AndVar deve parecer bastante direto neste ponto. Note que ele se remete a Term e implementa o ciclo mencionado anteriormente.

                                

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

A definição completa tem a seguinte aparência.

                                

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

O verdadeiro valor de definir a sua própria gramática vem quando você fornece implementações para as ações das regras. Vejamos a verdadeira definição da 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 !]
                                
                            

Temos muito a analisar aqui, então vamos prosseguir passo a passo.

Na parte superior, temos uma seção de código cercada por chaves. Essa é uma convenção do Pigeon que pega o código incluído literalmente e o injeta na saída final do código gerado. Note que, por conveniência, você pode definir aqui tipos relevantes para a sua gramática, ou pode colocá-los em outro arquivo, pois o Pigeon usará o nome do pacote que você declarar aqui. Tudo o que vier depois disso é a própria definição da gramática.

Neste ponto, você provavelmente deve ter notado que as regras diferem um pouco da forma como as definimos acima. Vamos dar uma olhada em Term.

                                

                                    Term <- variable:Variable rest:AndVar*
                                
                            

Essa é quase a nossa definição anterior de Term, mas agora a tornamos útil. Colocar o prefixo name: numa regra da definição atribui o valor de retorno dessa regra a name e depois passa name para a função definida pela ação da sua regra quando o código for gerado. Todo o código entre as chaves se torna uma função associada a essa regra e é chamado quando ocorre a correspondência com a regra:

                                

                                    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
}
                                
                            

Aqui podemos ver que o Pigeon lida inteiramente com tipos de interfaces vazias (empty interface). É ótimo para a flexibilidade, mas não tão bom para escrever a implementação, pois temos que levá-las em conta.

                                

                                    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
                                
                            

Conforme mencionado anteriormente, podemos ter ciclos em regras. Considerando isso, sabemos que é possível receber um número infinito de Terms mapeados para a variável rest. O Pigeon lida com isso nos entregando um slice de interfaces vazias. Criamos uma interface Node na qual tudo deve sofrer inferência de tipo (type inference) antes que possamos usá-los.

Depois de percorrer toda a lista de variáveis com o operador AND, criamos um AndNode contendo cada um dos Terms. A definição do AndNode pode ser encontrada na seção de código literal definida na parte superior da PEG. Como implementador da interface Node, ele define um método Evaluate (avaliar) que diz que a expressão é avaliada como verdadeira apenas se todos os termos individuais também forem avaliados como verdadeiros.

A esta altura, o restante da definição deve fazer sentido; portanto, vamos passar direto para a execução. A listagem de código a seguir mostra como analisar a nossa regra, como usá-la e alguns exemplos extras para mostrar falhas e tratamentos de erro:

                                

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

Tudo que você precisa fazer é executar:

~> go get github.com/mna/pigeon   ~> pigeon rules.peg > rules.go   ~> go run . Rule 'event:"sent" AND subject:"Uma oferta especial só para você!"' matched: true Rule 'event:"found" AND subject:"Uma oferta especial só para você!"' matched: false Rule 'event:"sent" AND badfield:"Uma oferta especial só para você!"' failed with error 'Field 'badfield' not present in the event'

Parabéns! Agora você criou sua própria linguagem, de utilidade extremamente limitada!

A esta altura, você pode estar pensando:

1. Muitos remetentes não usam assuntos assim?
2. Um mecanismo de regras que corresponda apenas a strings literais é tão útil assim?
3. Este post não poderia ter metade do tamanho?

Ao que responderíamos:

1. Gostaríamos de implementar algum tipo de tratamento para o campo account (conta) conforme definido no evento original. O Mailgun resolve esse problema incluindo uma lógica de negócios na base de código (codebase) para dar suporte à limitação de taxa (rate-limiting) com base em um campo definido. Em outras palavras, podemos dizer: “Se houver correspondência com essa regra, salve a conta e o tempo atual e não execute essa ação nessa conta pelos próximos N minutos.” Obviamente, se não tivéssemos esse tratamento e o remetente em questão enviasse um milhão de e-mails, o suporte seria notificado um milhão de vezes. Isso seria uma ótima maneira de afogar a sua equipe de suporte em barulho e também de sofrer uma emboscada no estacionamento depois do trabalho.
2. Alguém poderia implementar regras para fazer parse de expressões regulares e substrings que seriam muito mais úteis do que uma correspondência explícita de strings. De fato, nós fizemos exatamente isso.
3. Desculpe.

Por fim, você provavelmente notou que não definimos aqui o que a regra faria quando ela realmente correspondesse. Uma solução possível é fazer com que a regra publique num canal do Slack quando for acionada. Essa é uma solução comum aqui no Mailgun, e tem a seguinte aparência:

slack:#channel-name

Esperamos que, a essa altura, a sua cabeça esteja fervilhando de possibilidades. Aqui estão algumas ideias que tivemos:

1. Há muito mais a emular na sintaxe lucene, como instruções NOT e OR, e parênteses.
2. Fornecer uma gramática separada para ações.
3. Implementar uso de templates para injetar valores do evento na ação.
4. Adicionar uma camada de “syntactic sugar” (açúcar sintático) para facilitar a escrita de alguns filtros.
5. Implementar um sistema para contar e reagir a um número específico de ocorrências de eventos ao longo de um período de tempo.
6. Implementar um cache, pois analisar sintaticamente as regras é um pouco custoso.

Há muito mais que você pode fazer, especialmente quando se trata de estruturar o parser de ação. Você poderia acionar outros serviços, notificar clientes, acender e apagar as luzes, e muito mais. Quando se trata de inventar suas próprias ferramentas com base nisso, o céu é o limite.

Então, neste ponto, você deve estar se perguntando: “por que não usaram $SOME_OTHER_TOOL?” 

A resposta é que ainda não precisamos do poder de nenhuma dessas ferramentas nem da complexidade que frequentemente as acompanha. Nossa atual ferramenta de processamento de stream é um único binário simples implantado em um contêiner que simplesmente funciona (Just Works™). Há muito pouco para gerenciar, e ela está lidando muito bem com nosso feed de eventos de altíssimo volume.

1. É fácil de desenvolver
2. Ainda utiliza ferramentas de código aberto (FOSS) prontas para uso
3. Pode ser adaptada exatamente às nossas necessidades
4. A sintaxe da nossa DSL é minúscula, fácil de articular e de raciocinar, forçando todo mundo a escrever as regras quase da mesma maneira. Também torna mais difícil criar efeitos colaterais indesejados

1. Os recursos de linguagem que vão além do que já implementamos representam um salto substancial em complexidade.
2. Atualizar a PEG de origem gerará um novo código, e isso bagunça bastante os diffs do seu código.
3. A simplicidade proposital do Lucene pode dificultar a criação de regras mais complexas.

Podemos acabar decidindo que a $SOME_OTHER_TOOL é mais adequada às nossas necessidades, mas em um futuro previsível, o poder que a nossa DSL do Mailgun oferece é mais do que suficiente.

A esta altura, esperamos ter demonstrado como criar a sua própria DSL pode ser útil. Nossa implementação processa um número enorme de eventos por dia, além de facilitar muito a vida de várias pessoas da nossa equipe (pelo menos é o que dizemos a elas). 

Quanto aos recursos aos quais oferece suporte, estamos apenas começando. Se isso inspirou você a estudar a implementação da sua própria gramática de processamento de streams, conte para nós. Adoraríamos saber mais sobre isso!

Autor: Matthew Dietz Software Developer IV at Sinch Mailgun