IT & Engineering
Wie wir einen von Lucene inspirierten Parser in Go entwickelt haben
Bei Mailgun haben wir zahlreiche Systeme, die zu jeder Tagesstunde eine Unmenge an Ereignissen generieren. Diese Zahl ist so groß, dass es für ein Team unmöglich ist, ElasticSearch-Ergebnisse manuell zu durchsuchen und konsistente Resultate zu erwarten – oder dabei nicht den Verstand zu verlieren.
Wie viele Unternehmen müssen auch wir einen Weg finden, mit all diesen Daten umzugehen. Das führt zu einer komplexen Aufgabe: ein System zu entwickeln, mit dem unsere internen Kunden in Echtzeit auf Ereignisse reagieren können.
Traditionell gibt es für dieses Problem folgende Lösungsansätze:
- Daten in eine Datenbank einspeisen und dann Datenbankabfragen ausführen, oft in einem festen Zeitintervall
- Map-Reduce-Lösungen wie Hadoop
- Mechanical Turk
- Echtzeitfilter.
Wir sind stolz darauf, mit sehr wenig sehr viel zu erreichen. Also machten wir uns daran, herauszufinden, wie wir Echtzeitfilter für uns nutzen können. Wir konzentrierten uns auf die Entwicklung eines Systems, das es im Grunde allen im Entwicklungs- und Support-Team ermöglicht, Regeln zu verfassen, die reagieren und in ihrem Namen Aktionen ausführen.
Brainstorming
Beim Design dieses Systems versuchten wir etwas zu entwickeln, das allen das richtige Werkzeug an die Hand gibt, um schnell zu iterieren und auf Bedrohungen für unser System zu reagieren, wobei folgende Regeln gelten sollten:
- Die Nutzer sollten nach Belieben eigene Regeln hinzufügen können
- Die domänenspezifische Sprache, fortan als DSL bezeichnet, sollte so einfach wie möglich sein und idealerweise wie etwas aussehen, das sie bereits kennen.
- Man sollte seine Regeln anhand historischer Daten testen können, bevor sie angewendet werden.
Wir verwenden intern Kibana, daher war etwas ideal, das sich damit testen ließ, um Punkt 3 zu erfüllen. Das führt zu einer einfachen Schlussfolgerung: Wir sollten einen von Lucene inspirierten DSL-Parser schreiben.
Die erste Iteration des Systems stützte sich auf reguläre Ausdrücke und eine Menge zeichenweises Parsen. Es erfüllte seinen Zweck, aber die folgenden Iterationen wurden schnell immer komplexer. Falls Sie jemals ein großes String-Parsing-Projekt durchgeführt haben, wissen Sie, was wir meinen.
Für die Zukunft wussten wir, dass wir etwas entwickeln mussten, worauf sich schnell aufbauen ließ – und das idealerweise einem bekannten Standard entspricht.
Es wird grammatikalisch
Wer im Studium Kurse in Automatentheorie und Ähnlichem belegt hat, erinnert sich wahrscheinlich an Grammatiken im Kontext von Programmiersprachen. Zudem ist davon auszugehen, dass einige aus der Leserschaft bei diesem Thema weitaus mehr Expertise haben als ich als bescheidener Autor. Für tiefergehende Erklärungen verweise ich daher auf die Suchmaschine des Vertrauens.
Trotzdem lohnt es sich, kurz darüber zu sprechen, was eine Grammatik ausmacht und warum sie nützlich ist. Um Wikipedia zu zitieren: eine formale Grammatik ist „…eine Menge von Produktionsregeln für Strings in einer formalen Sprache. Die Regeln beschreiben, wie man aus dem Alphabet der Sprache Strings bildet, die gemäß der Syntax der Sprache gültig sind. Eine Grammatik beschreibt weder die Bedeutung der Strings noch, was mit ihnen in welchem Kontext auch immer getan werden kann – sondern ausschließlich ihre Form.“
Auf die Gefahr hin, es zu stark zu vereinfachen: Sie ermöglicht es uns, einen String wie „You’ve got mail!“ in Tokens zu zerlegen, die wir semantisch analysieren können. Mit anderen Worten: Falls unsere Grammatik gut definiert ist, können wir weiteren Code schreiben, um die Bedeutung dieses Strings zu bestimmen.
Die Geschichte und die Arten von Grammatiken füllen tonnenweise Bücher und sprengen daher den Rahmen eines Blog-Beitrags. Stattdessen konzentrieren wir uns auf kontextfreie Grammatiken und genauer gesagt auf Parsing Expression Grammars.
Kontextfreie Grammatiken und Parsing Expression Grammars
Um noch einmal Wikipedia zu zitieren: eine kontextfreie Grammatik ist „ein bestimmter Typ einer formalen Grammatik: eine Menge von Produktionsregeln, die alle möglichen Strings in einer gegebenen formalen Sprache beschreiben. Produktionsregeln sind einfache Ersetzungen.“
Anders gesagt: Eine kontextfreie Grammatik definiert einen Graphen, der wiederum definiert, wie eine Sprache analysiert (geparst) wird. Wie oben erwähnt, sagt sie uns nicht, wie wir die Sprache verstehen sollen. Es ist auch erwähnenswert – wie wir weiter unten sehen werden –, dass der Graph Zyklen haben kann, aber er terminiert schließlich.
Kontextfreie Grammatiken haben eine Art Verwandten in Form der Parsing Expression Grammar, oder PEG. Sie sehen stark nach einer kontextfreien Grammatik (CFG) aus, bringen aber einen sehr nützlichen Unterschied mit sich: Wenn eine PEG mit einer mehrdeutigen Auswahl konfrontiert wird, wählt sie stets die erste definierte Produktionsregel. Die CFG belässt die Auswahl stattdessen mehrdeutig – und warum sollten wir uns mit Mehrdeutigkeit herumschlagen, wenn wir nicht müssen?
Das bedeutet letztlich, dass es einfacher ist, Tools zur Definition von PEGs zu schreiben. Zum Glück haben das bereits viele Menschen für uns übernommen.
Wir heben ab
Nach einiger Recherche entschieden wir uns für Pigeon als Basis für unsere PEG. Pigeon folgt dem gleichen Paradigma wie viele Go-Tools, indem es Code generiert, der zusammen mit Ihrem Programm kompiliert wird.
Die Nutzung ist recht einfach: Sie definieren sowohl die Grammatik als auch den Go-Code, um jede der Regeln im selben Paket zu handhaben, und rufen einfach Parse() im generierten Parser auf. Die Herausforderung besteht darin, Handler für jede dieser Regeln zu schreiben. Wie bei Grammatiken könnte auch das Thema Kompilierung ganze Bibliotheken füllen. Zum Glück ist das Schreiben eines Interpreters weniger komplex, und der resultierende Code ist für unsere Anforderungen schnell genug.
Außerdem versucht die Syntax, sich eng an die Go-Syntax selbst anzulehnen. Das erleichtert es, Ihre PEG parallel zu Ihrem Go-Programm zu schreiben, das diese Grammatik nutzt.
Wie ein Blatt im Wind
Angenommen, Sie haben ein Ereignis, das durch den Versand einer E-Mail generiert wird, codiert in JSON, und das so aussieht:
{
"event": "sent",
"subject": "A special offer just for you!",
"account": "12345",
}
Es gibt mehrere Möglichkeiten, dieses Ereignis zu betrachten: Sie könnten entscheiden, dass dies eine harmlose E-Mail ist, oder Sie könnten sagen: „Das könnte Spam sein, aber es gibt nicht genug Informationen für eine Entscheidung.“ Dies ist ein sehr häufiges Problem in unserem System und erfordert immer viele aggregierte Daten, um zu einem Schluss zu kommen.
Schreiben wir also eine Regel, die auf das obige Ereignis zutrifft:
event:"sent" AND subject:"A special offer just for you!"
Das lässt sich ziemlich einfach parsen, und besser noch: Es kann auch in Kibana überprüft werden.
Gehen wir nun Schritt für Schritt durch, wie man eine sehr einfache PEG aufbaut, die auf diese Regel zutrifft. Wir implementieren jede Produktionsregel einzeln und erklären, was sie tut. Regelnamen folgen üblicherweise PascalCase und erlauben zudem Zahlen sowie Unterstriche. Jede Regel hat folgendes Format:
RuleName <-
Beachten Sie, dass es eigentlich mehrere gültige Zeichen für den Regeldefinitions-Operator gibt, aber wir verwenden gerne <-, da es leicht einzutippen ist und am ehesten so aussieht wie Grammatiken, die akademisch definiert sind.
Die erste Regel in der Grammatik wird als Einstiegspunkt behandelt:
Input <- Term !.
Unsere Input-Regel besagt mit !.: „Stimme mit dem gesamten Eingabe-String überein“, was „Stimme mit dem Ende der Datei überein“ bedeutet. Dies übergibt den gesamten Eingabe-String an eine Regel namens Term, die wie folgt aussieht:
Term <- Variable AndVar*
Dadurch wird der Kontrollfluss an die Variable-Produktionsregel übergeben:
Variable <- FieldChars+ _ ":" _ Value
Jetzt wird es etwas komplexer. Zuerst gleichen wir alle Zeichen gierig (greedy) ab, bis die FieldChars-Regel erfüllt ist. Beachten Sie das + am Ende. Die PEG-Syntax hat viel mit regulären Ausdrücken gemeinsam. Das hier besagt also: „Stimme einmal oder mehrmals mit der Regel FieldChars überein“.
FieldChars <- [a-z]
Erneut gilt: Falls Sie mit der Regex-Syntax vertraut sind, sollte dies unkompliziert sein: Gleichen Sie einfach ein beliebiges einzelnes Zeichen zwischen „a“ und „z“ ab.
Nun zurück zu Variable. Der nächste Teil _ ist eine Regel, die besagt: „Stimme mit einem beliebigen Leerzeichen (Whitespace) überein“. Beachten Sie, dass _ ein absolut gültiger Bezeichner für eine Produktionsregel ist – und weniger tippen zu müssen, ist normalerweise von Vorteil.
_ "whitespace" <- [ \n\t\r]*
Hier gibt es einige Dinge zu beachten:
- Der String „whitespace“ ist der „anzeigefreundliche Name“ und dient der Dokumentation sowie Ihrem zukünftigen Verstand.
- Wie bei der Syntax regulärer Ausdrücke stimmt dies mit jeder Form von Leerzeichen, Zeilenumbrüchen, Tabs oder Wagenrückläufen überein.
Der nächste Teil der Variable-Regel stimmt mit dem String-Literal „AND“ überein. Viel einfacher geht es nicht.
Als Nächstes haben wir eine weitere Whitespace-Regel und dann schließlich die Value-Regel.
Value <- '"' ValueChars* '"'
Diese Regel stimmt mit dem String-Literal '"', null oder mehr ValueChars-Regeln und schließlich einem weiteren Anführungszeichen überein.
ValueChars sieht folgendermaßen aus:
How we built a Lucene-inspired parser in Go
Diese ValueChars stimmen mit dem Klein- und Großbuchstaben-Alphabet, beliebigen Zahlen, Leerzeichen sowie dem Ausrufezeichen überein.
Warum haben wir Value so definiert? Weil die Regel die doppelten Anführungszeichen für uns entfernen kann, sodass wir es nicht tun müssen – und wir sind natürlich bequem. Das ist jedoch lediglich eine Annehmlichkeit, die wir auch hätten weglassen können, um stattdessen die Regelform von Value in die Definition der Variable-Regel aufzunehmen.
Schließlich sollte AndVar an dieser Stelle ziemlich selbsterklärend sein. Beachten Sie, dass sie auf Term verweist und den bereits erwähnten Zyklus implementiert.
ValueChars <- [a-zA-Z0-9 !]
Die vollständige Definition sieht so aus.
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 !]
Cool, aber was nun?
Der wahre Wert bei der Definition einer eigenen Grammatik zeigt sich erst, wenn Sie Implementierungen für die Aktionen der Regeln bereitstellen. Schauen wir uns die echte PEG-Definition an:
{
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 !]
Hier gibt es einiges zu entschlüsseln, also gehen wir es Schritt für Schritt durch.
Ganz oben haben wir einen Codeblock, der von geschweiften Klammern umschlossen ist. Das ist eine Pigeon-Konvention, die den umschlossenen Code wortwörtlich übernimmt und in die endgültige generierte Code-Ausgabe einfügt. Beachten Sie, dass Sie hier bequem die für Ihre Grammatik relevanten Typen definieren können. Alternativ packen Sie diese in eine andere Datei, da Pigeon den hier deklarierten Paketnamen verwendet. Alles danach ist die Definition der Grammatik selbst.
An dieser Stelle haben Sie wahrscheinlich bemerkt, dass sich die Regeln etwas davon unterscheiden, wie wir sie oben definiert haben. Schauen wir uns Term an.
Term <- variable:Variable rest:AndVar*
Dies ist fast unsere Term-Definition von vorhin, aber nun haben wir sie nützlich gemacht. Stellt man einer Regel in der Definition name: voran, wird der Rückgabewert dieser Regel an name zugewiesen und name wird dann an die Funktion übergeben, die von Ihrer Regel-Aktion definiert wurde, wenn der Code generiert wird. Der gesamte Code zwischen den geschweiften Klammern wird zu einer mit dieser Regel verknüpften Funktion und wird aufgerufen, wenn die Regel zutrifft:
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
}
Hier sehen wir, dass Pigeon ausschließlich mit leeren Interface-Typen arbeitet. Das ist großartig für die Flexibilität, aber weniger ideal für das Schreiben der Implementierung, da wir diese berücksichtigen müssen.
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
Wie bereits erwähnt, können wir in den Regeln Zyklen haben. Daher wissen wir, dass es möglich ist, eine unendliche Anzahl von Terms zu erhalten, die der rest-Variable zugeordnet sind. Pigeon löst dies, indem es uns einen Slice aus leeren Interfaces übergibt. Wir haben ein Node-Interface erstellt, in das alles per Type-Inference umgewandelt werden muss, bevor wir es verwenden können.
Nachdem wir die gesamte Liste der AND-verknüpften Variablen durchlaufen haben, erstellen wir einen AndNode, der jeden der Terms enthält. Die Definition des AndNode ist im Code-Literal-Abschnitt zu finden, der ganz oben in der PEG definiert wurde. Als Implementierung des Node-Interfaces definiert sie eine Evaluate-Methode, die besagt, dass der Ausdruck nur dann als wahr evaluiert, wenn auch alle einzelnen Terms als wahr evaluiert werden.
An diesem Punkt sollte der Rest der Definition hoffentlich Sinn ergeben, also springen wir direkt zur Ausführung. Das folgende Code-Listing zeigt das Parsen unserer Regel, ihre Nutzung sowie einige zusätzliche Beispiele, um Fehler und Error-Handling zu demonstrieren:
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)
}
}
}
Führen Sie einfach Folgendes aus:
~> 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'
Herzlichen Glückwunsch! Sie haben nun Ihre eigene Sprache geschrieben – auch wenn sie von äußerst begrenztem Nutzen ist.
Überlegungen
An dieser Stelle denken Sie vielleicht:
- Verwenden nicht viele Absender solche Betreffzeilen?
- Ist eine Rules-Engine, die nur String-Literale abgleicht, überhaupt so nützlich?
- Hätte dieser Beitrag nicht auch halb so lang sein können?
Darauf würden wir antworten:
- Wir würden eine Art Handling für das
accountimplementieren wollen, wie im ursprünglichen Ereignis definiert. Mailgun löst dieses Problem, indem es Geschäftslogik in die Codebasis integriert, um Rate-Limiting basierend auf einem definierten Feld zu unterstützen. Mit anderen Worten können wir sagen: „Falls diese Regel zutrifft, speichere das Konto und die aktuelle Uhrzeit und führe diese Aktion für die nächsten N Minuten nicht für dieses Konto aus.“ Offensichtlich würde der Support eine Million Mal benachrichtigt, falls wir dieses Handling nicht hätten und der betreffende Absender eine Million E-Mails versenden würde. Das wäre ein hervorragender Weg, um Ihr Support-Team in Meldungen ertrinken zu lassen – und nach der Arbeit auf dem Parkplatz aufgelauert zu bekommen. - Man könnte Regeln implementieren, um reguläre Ausdrücke und Teilstrings (Substrings) zu parsen, was weitaus nützlicher wäre als ein expliziter String-Abgleich. Tatsächlich haben wir genau das getan.
- Entschuldigung.
Zu guter Letzt ist Ihnen wahrscheinlich aufgefallen, dass wir hier nicht definiert haben, was die Regel ausführt, wenn sie tatsächlich zutrifft. Eine mögliche Lösung ist, dass die Regel eine Nachricht in einem Slack-Kanal postet, wenn sie ausgelöst wird. Dies ist eine gängige Lösung hier bei Mailgun und sieht folgendermaßen aus:
slack:#channel-name
Die nächsten Schritte
Hoffentlich sprudeln Sie an diesem Punkt über vor lauter Möglichkeiten. Hier sind einige Überlegungen, die wir uns gemacht haben:
- In der Lucene-Syntax gibt es noch viel mehr zu emulieren, wie NOT- und OR-Anweisungen sowie Klammern.
- Eine separate Grammatik für Aktionen bereitstellen.
- Templatization implementieren, um Werte aus dem Ereignis in die Aktion einzufügen.
- Syntax-Zucker hinzufügen, um das Schreiben bestimmter Filter zu erleichtern.
- Ein System implementieren, das eine bestimmte Anzahl von Ereignissen über einen bestimmten Zeitraum hinweg zählt und darauf reagiert.
- Einen Cache implementieren, da das Parsen der Regeln ziemlich ressourcenintensiv ist.
Es gibt noch unzählige weitere Möglichkeiten, insbesondere beim Ausbau des Aktions-Parsers. Sie könnten andere Services aufrufen, Kunden benachrichtigen, das Licht ein- und ausschalten und vieles mehr. Wenn es darum geht, auf dieser Basis eigene Tools zu erfinden, sind Ihnen keine Grenzen gesetzt.
Vor- und Nachteile
Wahrscheinlich fragen Sie sich an diesem Punkt: „Warum haben die nicht $SOME_OTHER_TOOL genutzt?“
Die Antwort: Weil wir derzeit weder die Leistung eines dieser Tools benötigen noch die Komplexität, die ihr Betrieb häufig mit sich bringt. Unser aktuelles Stream-Processing-Tool ist eine einzelne, einfache Binary, die in einem Container bereitgestellt wird und Just Works™. Es gibt kaum etwas zu verwalten, und es hält mühelos mit unserem hochvolumigen Event-Feed mit.
Vorteile:
- Es ist einfach zu entwickeln
- Es nutzt weiterhin standardmäßige FOSS-Tools
- Es lässt sich genau auf unsere Bedürfnisse zuschneiden
- Die Syntax unserer DSL ist winzig, leicht zu artikulieren und zu verstehen. Zudem zwingt sie alle, Regeln in etwa auf die gleiche Weise zu verfassen. Dadurch wird es auch schwieriger, unbeabsichtigte Nebeneffekte zu erzeugen
Nachteile:
- Sprachfunktionen, die über das bereits Implementierte hinausgehen, stellen einen erheblichen Sprung in der Komplexität dar.
- Das Aktualisieren der Quell-PEG generiert neuen Code, was Code-Diffs ziemlich unübersichtlich macht.
- Die bewusste Einfachheit von Lucene kann das Verfassen komplexerer Regeln erschweren.
Vielleicht entscheiden wir uns irgendwann, dass $SOME_OTHER_TOOL besser für unsere Anforderungen geeignet ist. Für die absehbare Zukunft reicht die Leistung, die unsere Mailgun-DSL liefert, jedoch völlig aus.
Endlich am Ende
Wir hoffen, an diesem Punkt verdeutlicht zu haben, wie nützlich das Schreiben einer eigenen DSL sein kann. Unsere Implementierung verarbeitet täglich eine enorme Menge an Ereignissen und macht dabei das Leben vieler unserer Teammitglieder sehr viel leichter (zumindest reden wir ihnen das ein).
Was die unterstützten Features angeht: Wir fangen gerade erst an. Falls Sie das dazu inspiriert hat, die Implementierung Ihrer eigenen Stream-Processing-Grammatik in Betracht zu ziehen, lassen Sie es uns bitte wissen. Wir würden uns freuen, davon zu hören.
