武汉的开发者们注意啦!AI技术战略、框架以及最佳实战尽在Azure OpenAI Day 了解详情
写点什么

从 0 到 1 搭建技术中台之报警平台实践:匹配器演进

  • 2020-06-22
  • 本文字数:12954 字

    阅读完需:约 43 分钟

从0到1搭建技术中台之报警平台实践:匹配器演进

本文介绍伴鱼内部服务报警平台中匹配器模块的演进,及其利用 Lex 和 Yacc 同类工具构建 DSL 编译器的过程。

背景

报警平台是伴鱼内部各端、应用、基础设施等服务异常状态信息的集散中心。整体流程如下图所示:



信息源将信息投递给报警平台,后者将这些信息最终通过邮件、即时消息、电话呼叫的形式路由给理应关心它的人。总体而言,路由的需求可以分为以下几种:


  • 路由给服务的负责人及其团队

  • 路由给服务依赖方人员及其团队

  • 路由给所有值班人员所在的即时消息群


为了满足这样的需求,报警平台采用树状结构组织路由信息,如下图所示:



每个节点是一个路由节点,节点上可以挂载不同的规则,如抑制规则、通知规则;也可以存放不同的配置信息,如触发报警的阈值,以及相关负责人及其团队的联系方式。


根路由是所有异常信息的必经之路,经过这里的信息会路由给所有值班人员;一级子路由节点是所有的服务,经过这里的信息会路由给该服务的负责人及其团队;如果有其它团队想要订阅某服务的异常消息,如 Service A 团队想要了解 Service B 的崩溃 (panic) 信息,则可以在 Service B 节点下创建子路由 Service B Panic,并在上面配置 Service A 团队的联系方式,从而达到订阅目的。


那么如何判断一条报警信息将经过哪些路由节点,一条规则是否起作用?这就需要引入本文的主角:匹配器 (matcher),每个路由、每条规则上都会挂载一个匹配器,当它成功匹配到报警信息时,路由和规则就会生效。一条典型的报警信息会有许多信息,我们不妨将它看作是任意数量的键值对,如:


{  "title": "Web 服务 ServiceB 崩溃报警",  "source": "192.168.0.1",  "error_type": "panic",  "project_name": "ServiceB",  "project_source": "web",  "details": "(call stack)",  //...}
复制代码


我们可以试着写出路由节点 ServiceBService B Panic 的匹配器:


  • ServiceB:project_source 为 web 且 project_name 为 ServiceB

  • Service B Panic:project_source 为 web,且 project_name 为 Service B,且 error_type 为 panic


报警平台的用户需要亲自配置部分路由和规则,能否定制一套简单、易上手的 DSL?如:


project_source = "web" AND project_name = "ServiceB"
复制代码


这样即使用户不是工程师,看过几个例子后也能熟练地书写匹配表达式。

匹配表达式定义

匹配器表达式由原始表达式和复合表达式构成。原始表达式是最小的匹配器,有完全匹配正则匹配两种:


# 完全匹配project_source = "web"# 正则匹配details =~ "duplicate key when insert"
复制代码


原始表达式的左手边是报警信息的标签,不带双引号;原始表达式的右手边是匹配文本,带双引号。不同的原始表达式可通过二元关系运算,AND (且) 和 OR (或) ,组合成复合表达式如:


project_source = "web" AND project_name = "ServiceB" OR "error_type" = "panic"
复制代码


类似于乘除之于加减,AND 的优先级大于 OR,如果要改变优先级,可通过增加括号来实现,如:


project_source = "web" AND (project_name = "ServiceB" OR "error_type" = "panic")
复制代码

编译过程

一个完整的编译过程大致分三阶段:



  1. 前端:验证源码的语法和语义,并解析成中间表述 (Immediate Representation, IR)

  2. 中端:针对 IR 作一些与目标 CPU 架构无关的优化

  3. 后端:针对目标 CPU 架构优化并生成可执行的机器指令


我们也可以将匹配器表达式理解成一门语言,但我们只需要将它转化成合理的内存数据结构即可,因此这里只涉及到完整编译过程的前端:


  1. 词法分析 (Lexical Analysis):将完整的语句拆成词语和标点符号

  2. 语法分析 (Syntax Analysis):根据语法规范,将词语和标点符合组合成抽象语法树 (AST)

  3. 语义分析 (Semantic Analysis):向语法树中添加语义信息,完成校验变量类型等各种语义检查

  4. 生成中间表述 (IR Generation):转化成合理的内存数据结构


以下就是匹配表达式的 IR:


type PrimitiveMatcher struct {  Label    string  Text     string  IsRegexp bool  re       *regexp.Regexp}
type Matcher struct { PrimitiveMatcher *PrimitiveMatcher IsCompound bool Operator MatcherOperator Operands []*Matcher}
复制代码


其中 Matcher 既可以是原始匹配器 (表达式) 也可以是复合匹配器 (表达式)。


下面分别介绍报警平台匹配器编译器的两个版本实现,Matcher Compiler V1 (MCV1) 和 Matcher Compiler V2 (MCV2)。

Matcher Compiler V1

在实现 MCV1 时我们并未从编译的角度看待这个模块,而只是单纯地想实现从表达式到 IR 的转化。凭借工程师的本能,MCV1 将编译的前端处理过程分成 3 步:


err = m.parseToken()if err != nil {  return}
err = m.toElements()if err != nil { return}
return m.buildMatcher()
复制代码

parseToken

parseToken 将原始表达式转化成一个词语数组,是词法分析的雏形,其整体过程如下:


for i, c := m.expr {  hasLeftDoubleQuote := false  switch c {    case '(':      //...    case ')':      //...    case '=':      //...    case '~'    //...    default:      //...  }}
复制代码


parseToken 需要许多状态,如:


  • 是否在括号内

  • 是否在引号内

  • 遇到 ~ 要考虑是否会和上一个字符共同组成 =~


由于状态较多,要同时考虑各种状态及其之间的转化过程,使得 parseToken 足够健壮,过程烧脑且容易出错。

toElements

toElements 遍历词语数组,构建其中的原始表达式,可以看作理解成是语法分析和语义分析的一部分,其整体过程如下:


for i, word := range m.words {  switch strings.ToLower(word) {    case "=":      leftWord, rightWord, _ := m.tryFetchBothSideWord(i)      m.addElement(m.buildPrimitiveMatcher(leftWord, rightWord, false))    case "=~":      leftWord, rightWord, _ := m.tryFetchBothSideWord(i)      m.addElement(m.buildPrimitiveMatcher(leftWord, rightWord, true))    // deal with more cases    default:      // ...}
复制代码


这部分逻辑比较简单,遇到 = 或者 =~ 时看一下前后的词语,看是否能构成原始表达式。

buildMatcher

buildMatcher 遍历 elements 数组,构建最终的树状复合表达式,其实就是中缀表达式的计算过程,是栈的典型应用场景,利用操作符栈和操作数栈即可实现,其整体过程如下:


var (  valueStack Stack  opStack Stack)
for i, element := range m.elements { switch e := element; { case e == "(": opStack.Push("(") case e == ")": for op := opStack.Pop(); op != "(" { rhs, lhs := valueStack.Pop(), valueStack.Pop() // apply } // operators case isOp(e): currOp = e for prevOp := opStack.Peek(); precedence[currOp] <= precedence[prevOp] { opStack.Pop() rhs, lhs := valueStack.Pop(), valueStack.Pop() // apply prevOp } opStack.Push(currOp) default: valueStack.Push(e) }}
// deal with the rest valueStack and opStack
复制代码

MCV1 小结

MCV1 是凭借工程师本能构建的一个模块,优势就在于可以迅速地搭建原型,验证想法。从代码健壮性角度看, parseToken 的状态管理比较脆弱;从可读性角度看,无法从逻辑中直接看出其所支持的语法,为后期维护造成障碍;从可扩展性角度看,buildMatcher 目前只支持中缀表达式,如果有语法变化将整体逻辑产生较大影响;从效率角度看,编译一次表达式需要 3 次遍历,如果将 toElementsbuildMatcher 逻辑合并可以优化到 2 次。

Matcher Compiler V2

为了解决上述问题,我们想到了 Lex 和 Yacc。Lex 是 lexical analyzer generator,能够帮助我们生成词法分析器 (lexical analyzer);Yacc 是 parser generator,能够帮助我们生成解析器 (parser),完成语法分析。Lex 和 Yacc 是 Unix 系统的原生工具,Linux 与 MacOS 平台也都自带这两个工具。既然已经有前人为我们栽树,我们为什么不趁机乘凉?

Lex & Yacc

Lex 和 Yacc 的协作过程如下图所示:



开发者将构词规则和一些定制化逻辑 (C Code) 定义到 lex.l 文件中,利用 lex 命令生成词法分析器;将语法规则和一些定制化逻辑定义到 parser.y 文件中,利用 yacc 命令生成解析器。词法分析器的 yylex 方法将输入文本转化成 token,投喂给 yyparse,后者根据语法和定制化逻辑将 token 流转化成最终的目标数据结构,即 IR。

Example:Calculator

以一个支持加减运算的计算机为例,先定义语法规则:


// parser.y%token NUMBER%%
// 括号中的 $$ 表示语法左手边 (LHS) 的值// 括号中的 $1、$2、$3 表示语法右手边 (RHS) 的值statement: expression { printf("= %d\n", $1); } ;
expression: NUMBER '+' NUMBER { $$ = $1 + $3; } | NUMBER '-' NUMBER { $$ = $1 - $3; } | NUMBER { $$ = $1; } ;
复制代码


第一行的 token 定义语法中的数据类型,由于单个字符本身没有歧义,在 Lex 和 Yacc 无需特别定义单字符 token,如 +-,因此在这里我们只需要数字 NUMBER。在第一个 %% 之后,定义了计算器的语法,含义非常直白,可读性强。


然后再定义构词规则:


// lex.l%{#include "y.tab.h"extern int yylval;%}
%%[0-9]+ { yylval = atoi(yytext); return NUMBER; }[ \t] ;\n return 0;. return yytext[0];%%
复制代码


在两个 %% 中间的就是构词规则:


  • 符合正则表达式 [0-9]+ 就是数字类型的词语,其对应的值为 atoi(yytext)

  • 符合正则表达式 [ \t] 的不处理,即忽略空格和制表符

  • 符合正则表达式 \n 的返回 0,即用换行符标识文本结束位置

  • 符合正则表达式 . 的返回文本本身,即所有非数字的字符直接返回,这里实际上指的就是 +-


接下来只需要用 lexyacc 命令生成词法分析器和解析器,然后运行即可:


# MacOS$ lex lex.l$ yacc -d parser.y$ gcc y.tab.c lex.yy.c -ly -ll -o calculator$ ./calculator> 128 + 128> = 256
复制代码

对比分析

从代码健壮性角度上看,lex 生成的词法分析器已经经受时间的检验,开发者大可相信其代码的健壮性;从可读性角度看,构词规则和语法规则定义简短,通俗易懂;从可扩展性角度看,任何可以通过上下文无关文法 (context-free grammar) 表达的语法都能支持;从效率角度看,yylexyyparse 可以流式地处理文本,yyparseyylex 获取词语,即时地根据语法规则组合成 IR,这种做法使得编译前端的工作只需要 1 次遍历便可完成。但 lexyacc 为了支持更复杂的场景,其生成的代码也会更复杂,这也是效率与通用性权衡的表现。

Nex & Goyacc

报警平台使用 Go 语言编码,直接使用 lexyacc 需要引入 cgo,这也使得二者的使用门槛变高。好在 Go 官方提供了 goyacc,方便我们在 parser.y 中引入用 Go 语言编写的定制化逻辑;斯坦福的一位博士 Ben Lynn 开源了它的 nex 项目,作为用 Go 语言原生开发的词法分析器生成器,能与 goyacc 兼容,形成类似 lexyacc 一般的搭档。接下来我们将利用 nexgoyacc 来实现匹配器编译器。


与计算器的例子类似,我们先看语法规则中定义的数据类型:


%union{  str string  expr *MatchExpr  pexpr *PrimitiveExpr}
%token LABEL VALUE%token REG_EQ AND OR
%type <expr> expr%type <pexpr> pexpr %type <str> LABEL VALUE%type <str> REG_EQ AND OR
复制代码


其中,语法中的数据类型包括:


  • LABEL:原子表达式的 LHS

  • VALUE:原子表达式的 RHS

  • REG_EQANDOR 分别为正则匹配,且和或


此外我们还定义了原始表达式 pexpr 和复合表达式 expr 供定义语法规则时引用。由于语法中有多种关系运算符,它们的优先级不同,因此我们还需要定义运算符的优先级:


%left OR%left AND%left '(' ')'
复制代码


left 表示先从运算符的 LHS 开始计算,三者的优先级关系是 OR < AND < '(' == ')',非常直观。最后进入我们的语法规则:


// 匹配器表达式可以是空字符串,也可以是一个合法的表达式matcher:  { setResult(yylex, &Matcher{}) }| expr  { setResult(yylex, $1) }
// 表达式可能以下之一:// 复合表达式:expr AND expr// 复合表达式:expr OR expr// 原始表达式:pexpr// 括号表达式:(expr)expr: expr AND expr { $$ = &Matcher{IsCompound: true, Operator:$2, Operands:[]*Matcher{$1,$3}} }| expr OR expr { $$ = &Matcher{IsCompound: true, Operator:$2, Operands:[]*Matcher{$1,$3}} }| pexpr { $$ = &Matcher{IsCompound: false, PrimitiveMatcher:$1} }| '(' expr ')' { $$ = $2 }// 原始表达式要么是 LABEL = VALUE, 要么是 LABEL =~ VALUEpexpr: LABEL '=' VALUE { $$ = &PrimitiveMatcher{Label:$1, Text:$3, IsRegex: false} }| LABEL REG_EQ VALUE { $$ = &PrimitiveMatcher{Label:$1, Text:$3, IsRegex: true} }
复制代码


每条语法规则的含义已经标明在注释中,在每条语法规则之后,是 Go 语言编码的简单逻辑,告诉解析器在不同情况下如何拼装 IR。搞定语法后,我们就可以定义构词规则:


/[aA][nN][dD]/                      { lval.str = "AND"; return AND }/[oO][rR]/                          { lval.str = "OR"; return OR }/=~/                                { return REG_EQ }/=/                                 { return int(yylex.Text()[0]) }/\(/                                { return int(yylex.Text()[0]) }/\)/                                { return int(yylex.Text()[0]) }/[A-Za-z][A-Za-z0-9_]*/             { lval.str = yylex.Text(); return LABEL }/".*"/                     { lval.str = yylex.Text()[1:len(yylex.Text())-1]; return VALUE }/[ \t\r\n]+/                        { /* white spaces ignored */ }//package c
复制代码


  • 大小写无关的字符串 “AND” 返回类型 AND;“OR” 返回类型 OR

  • “=~”、"="、"("、")" 直接返回相应的数据类型

  • 正则表达式 /[A-Za-z][A-Za-z0-9_]*/ 匹配的是原始表达式中的 LABEL

  • 正则表达式 /".*"/ 匹配的是原始表达式中的 VALUE

  • 正则表达式 /[ \t\r\n]+/ 匹配的是空格字符,即忽略所有类型的空格


最后使用 nexgoyacc 就可以生成词法分析器和解析器:


$ nex nex.l$ goyacc -o parser.go parser.y
复制代码


然后再把二者串起来即可:


// 忽略细节处理func Compile(ctx context.Context, in io.Reader) (m *Matcher, err error) {  lr := NewLexer(in)  yyParse(lr)
if lr.parseResult == nil { err = SyntaxError return }
m = lr.parseResult.(*Matcher) return}
复制代码

Rob Pike Style Lexer

完成上面的工作,本可以告一段落,但有一个问题还困扰着我们:”为什么 Go 只推出了 yacc 的移植版本,而不顺便推出 lex 的移植版本?“ 几经周折找到了 Rob Pike 2011 年的一次演讲: “Lexical Scanning in Go”。在演讲中他认为 ” lex 生成的代码太多,过于复杂,用 Go 语言实现一个并非难事,且 Go 的 channel 能方便地实现 lexyacc 的流水线协作。“ 尽管这种观点也是在为 Go 站台,我们还是决定试一试他提出的 lexical scanning 方案。


词法分析的过程,就是从输入字符流起点扫描至终点的线性过程,在扫描期间,词法分析器需要正确地判断自己所处的状态,以起点为例,刚开始扫描,可能进入 LABEL 状态,也可能进入 ( 状态:


labela = "a" AND (labelb = "b" OR labelc = "c")在LABEL中                 
(labela = "a") OR labelb = "b"在'('中
复制代码


扫描完 VALUE 后,可能进入结束状态,也可能进入 ) 状态或 关系运算符 状态:


labela = "a" AND (labelb = "b" OR labelc = "c")            进入[关系运算符]状态(labela = "a")            进入 ')' 状态labela = "a"           进入[结束]状态
复制代码


不难看出,这实际上就是一个状态机,详细的状态转移过程如下图所示:


# start: [开始]; leftParen: '('; label: [标签]; eq: [匹配符]; value: [文本];# rightParen: ')'; binaryOp: [关系运算符]; end: [结束]                                                +------------+                                                | rightParen | -------------+                                                +------------+              |                                                  ^  |                      |                                                  |  |                      |  +----------------------+                        |  ----------------+      |  |                      v                        |                  v      |  |  +-----------+     +-------+     +----+     +------------+     +-----+  |  |  |   start   | --> | label | --> | eq | --> |   value    | --> | end |  |  |  +-----------+     +-------+     +----+     +------------+     +-----+  |  |    |                 ^                        |                         |  |    |                 |                        |                         |  |    v                 |                        v                         |  |  +-----------+       |                      +------------+              |  +- | leftParen |       +--------------------- |  binaryOp  | <------------+     +-----------+                              +------------+       ^                                          |       +------------------------------------------+


复制代码


接下来就需要让这个状态机动起来:


type lexer struct {  name  string    // used only for error reports.  input string    // the string being scanned.  start int       // start position of this item.  pos   int       // current position in the input.  width int       // width of last rune read from input.  items chan item // channel of scanned items.}
// stateFn represents the state of the scanner// as a function that returns the next state.type stateFn func(*lexer) stateFn
func (l *lexer) run() { for state := lexStart; state != nil; { state = state(l) } close(l.items)}
复制代码


其中 stateFn 就是状态转移方程,约定当 stateFn == nil 时,状态机停止,即 nil 就是结束状态的转移方程。接下来只需要定义各个状态转移方程即可:


func lexStart(l *lexer) stateFn {}func lexLabel(l *lexer) stateFn {}func lexLeftParen(l *lexer) stateFn {}func lexRightParen(l *lexer) stateFn {}func lexEq(l *lexer) stateFn {}func lexValue(l *lexer) stateFn {}func lexBinaryOp(l *lexer) stateFn {}
复制代码


每当状态即将转移时,stateFn 内部就会将在本状态中扫描到的词语传给 item channel,这个 channel 就是 lexer 与 parser 之间通信的媒介。


值得一提的是,Go 的模板引擎 template,就是按照上述方式构建的,感兴趣可以阅读源码

参考文献


2020-06-22 08:306775
用户头像
赵钰莹 InfoQ 主编

发布了 870 篇内容, 共 598.0 次阅读, 收获喜欢 2669 次。

关注

评论

发布
暂无评论
发现更多内容

技术实操丨SoundNet迁移学习之由声音分类到语音情感识别

华为云开发者联盟

AI 数据 语音识别

Nacos-技术专题-配置中心实现

洛神灬殇

区块链是一个不知道要解决什么问题的解决方案吗?

CECBC

比特币 区块链 银行

lldb常用命令与调试技巧

iOSer

ios lldb常用命令 lldb调试技巧

光大银行刘淼:基于华为云GaussDB(DWS) 数据仓库创新实践

华为云开发者联盟

数据仓库 数据 huawei

来不及解释了,快上车!力软快速开发平台,助力企业搭乘万物互联的顺风车

Learun

架构师训练营1期第三周作业

木头发芽

Java程序员月薪多少K才能在北上广买得起房?

Java架构之路

Java 程序员 编程语言

31道Java核心面试题,一次性打包送给你

小Q

Java 学习 程序员 架构 面试

区块链教育 丨 首批区块链专业新生正式入学

CECBC

区块链技术 区块链教育

国庆期间,我造了台计算机

yes

计算机 底层

字节跳动 Flink 单点恢复功能实践

Apache Flink

flink

SpringBoot-技术专题-启动原理

洛神灬殇

Web前后端:如何分离,如何解耦?

华为云开发者联盟

大前端 后端 开发

spring-boot-route(十)多数据源切换

Java旅途

Java Spring Boot

PyFlink + 区块链?揭秘行业领头企业 BTC.com 如何实现实时计算

Apache Flink

flink

开源数据库这么香,为什么我们还要下功夫自研?

华为云开发者联盟

数据库 开源 数据

Python时间序列分析简介(2)

计算机与AI

Python 时间序列

节日快乐…吗?

小天同学

个人感悟 国庆中秋 假期 节日

2020年秋招阿里136道Java高级岗面试题(含答案及复习资源)

Java架构之路

Java 程序员 面试 算法 编程语言

建筑行业区块链应用场景是怎样的

CECBC

区块链 行业资讯

互联网应用系统技术方案主要解决什么问题?

博古通今小虾米

开源=免费?

Learun

深入分析CRM系统对现代企业的作用

Learun

从构建小系统到架构分布式大系统,Spring Boot2的精髓全在这里了

Java架构之路

Java 程序员 面试 Spring Boot 编程语言

程序员去外包真的不可取吗?

Java架构师迁哥

MySQL-技术专题-问题分析

洛神灬殇

MySQL-技术专题-查询速度性能

洛神灬殇

EffectiveJava读书笔记-01-对象创建与销毁

wander

读书笔记 编程开发

架构师训练营第四周作业

郎哲158

架构师训练营第四章 系统架构总结

郎哲158

从0到1搭建技术中台之报警平台实践:匹配器演进_架构_伴鱼技术团队_InfoQ精选文章