1.摘要
intel在2015年10月开源了其第一个hyperscan版本4.0。在其之前很多网络设备公司都自研或使用类似pcre之类的正则匹配工具。
也许是dpdk的光环太多,导致大家对hyperscan也趋之若鹜。而且从实际来看,hyperscan也确实表现不俗。
本文主要介绍一下hyperscan的一些概念,基础使用,以及在性能敏感的情况下的一些注意事项。
2.环境
工欲善其事,必先利其器。但hyperscan这个器,也需要在特定的环境下,才能表现出你要的性能来。hyperscan的表现和平台以及cpu是紧密相关的。
在compile正则的时候,我们可以指定平台,比如haswell,Sandy Bridg。也可以指定CPU的指令集,比如AVX 2和AVX512等。
hyperscan可以充分利用如下的指令集。
- Intel Streaming SIMD Extensions 4.2 (SSE4.2)
- the POPCNT instruction
- Bit Manipulation Instructions (BMI, BMI2)
- Intel Advanced Vector Extensions 2 (Intel AVX2)
我们可以通过如下的指令看看本机的指令1
1 | cat /proc/cpuinfo |
关于软件也确实有一些要求:
- GCC, v4.8.1 or higher
- Clang, v3.4 or higher (with libstdc++ or libc++)
- Intel C++ Compiler v15 or higher
编译的时候,需要一些依赖的lib
lib | Version | Note |
---|---|---|
CMake | >=2.8.11 | |
Ragel | 6.9 | |
Python | 2.7 | |
Boost | >=1.57 | |
Pcap | >=0.8 |
3.编译正则表达式
为什么需要编译正则表达式呢?这也正好是多模匹配(我理解的)的一个特点了。多模匹配是说一个待匹配字符串和目标N个正则表达式匹配,得到匹配上的正则表达式,进行响应的处理。单模匹配自然是说一次只能判断是否和一个正则表达式匹配。如果想和多个正则表达式匹配,那就只能for循环了。
hyperscan就是用于支持多个正则表达式匹配的,内部状态机超级复杂,但好处是,基本以O(n)甚至更少的的代价,查找出其匹配的正则表达式。
把一组正则表达式编译好的二机制叫做pattern database。我们可以通过如下3个API,去执行编译操作:
- hs_compile(): 把一个正则表达式编译成一个pattern database
- hs_compile_multi(): 把一组正则表达式编译成一个pattern database.
- hs_compile_ext_multi(): 基本和2一样,但多了一些参数可以设置,基本用于帮助我们限制一些查匹配件,以至于更快结束匹配过程,我们后续介绍。
当编译正则表达式的时候,我们需要决定,我们后续的匹配使用什么样的方式?hyperscan允许我们使用如下的三种方式:
- Stream模式:流模式匹配,即待匹配数据不是连续的一块,比如tcp stream,我们的正则可能匹配的数据是跨块的。
- Block模式:待匹配的数据很明确,就在这个块里。
- Vector模式:在Stream和Block之间的模式,数据在指定的一系列Block里。
使用哪种模式,需要我们的权衡,单纯的从性能比较,BLock模式肯定最好,因为比Stream模式比较,少了对跨块的内部状态的跟踪。但Stream能很好的解决包分多Block来的情况。
3.1.支持什么样的正则?
hyperscan对正则的支持比PCRE要少,但对于我们大多数人来说是足够用了,我们可以简单的看一下:
- 所有字符串字符以及字符转义的匹配
- 字符类(charactor class) . (dot), [abc], 和 [^abc],以及\s, \d, \w, \v,及其否定形式(\S, \D, \W, \V, and \H).
- 量词形式?,*,+,{n}, {m,n}, {n,}
- 多选模式 foo|bar
- 锚 ^, $, \A, \Z 和 \z.
- 选项 i,m,s,x等
差不多够用了不是?不支持的我都不知道啥意思
3.2.关于匹配的语义Semantics
语法是和PCRE相同的,但语义Semantics是标准正则表达式是不一样的。不一样的有这么几个地方
- 多模匹配:hyperscan的匹配是一次匹配多个正则表达式,这和PCRE里的 表达式1|表达式2|表达式3 这样从左到右依次匹配是不一样的
- 无序:由于是多模匹配,所以多个表达式是一起匹配的,没有明显顺序,虽然基本按照谁先到匹配边界谁先结束
- 默认仅返回匹配的尾部offset:默认情况下,在返回的时候,仅仅知道匹配的end的offset,如果想知道begin offset。需要编译的时候设置flag,但会影响性能
- 全量匹配:比如从fooxyzbarbar里匹配/foo.*bar/, 默认PCRE采用贪婪匹配方式,只会匹配fooxyzbarbar,但hyperscan会匹配fooxyzbar和fooxyzbarbar两个。
在stream模式下,像PCRE语义那样支持最长匹配是不太可能的。还是举上面的例子,正则是 /foo.*bar/,如果数据分下面的3个block来:
block 1 | block 2 | block 3
fooxyzbar | baz |qbar
Stream模式最多匹配到第一个block就结束了,因为block 2又不匹配,考虑到效率,hyperscan不会无限制的等待后面是否有个bar了。否则,如果第500个block里有个bar,该怎么搞呢?
3.3.SOM
SOM是Start of Match。表示哪里开始匹配,我们之前也介绍过,默认情况下hyperscan只记录end of Match,不记录Start of Match。如果非要记录SOM,我们可以
在编译的时候设置 HS_FLAG_SOM_LEFTMOST这个flag。但设置之后有如下的缺点:
- 减少hyperscan支持的正则样式。可能在编译的时候出现『Pattern too large』这样的错误
- 增加Stream模式的状态,很容易了解,多了记录内容了嘛
- 性能问题
- 和其他的一些flag不兼容。 比如HS_FLAG_SINGLEMATCH和 HS_FLAG_PREFILTER。
此外,考虑性能问题,我们在使用SOM的时候,可以设置一个阈值,即start offset和end offset之间的差值,太长了还没到结尾的话,就重新来过,来减少过多的内部状态追踪
3.4.扩展参数
我们在hs_compile_ext_multi里提到的扩展参数,
- flags: flags标记
- min_offset: 用于标识最小匹配的offset
- max_offset: 用于标识最大匹配的offset
- min_length: 最小匹配多长
- edit_distance: Levenshtein距离参数,用于模糊匹配.
比如还是正则表达式/foo.*bar/,如果指定min_offset是10,max_offset是15的话,foobar和foo0123456789bar就不会匹配,而foo0123bar和foo0123456bar就会匹配。
如果edit_distance是2的话,foobar, fooba, fobr, fo_baz, foooobar和/foobar/都会匹配
4.匹配过程
hyperscan对于上面的3种模式,也提供了不同的scan函数,都是以hs_scan开头。
一旦一个正则匹配后,会回调下面的函数
1 | typedef (* match_event_handler)(unsigned int id, unsigned long long from, unsigned long long to, unsigned int flags, void *context) |
这个函数的返回非0的话停止匹配,否则继续匹配下去,直到找到满意的。
from参数就是前面提到的start of match,to就是end of match,
4.1.Stream模式
在stream模式里会调用如下几个函数
- hs_open_stream()
- hs_scan_stream()
- hs_close_stream()
匹配上正则后,会回调callback,callback函数如果返回非0,则终止此次匹配过程。虽然在callback里中止了,但实际上stream的状态机还是停留在一个一个状态。
后续如果继续调用hs_scan_stream,会立即返回HS_SCAN_TERMINATED。 最终还是需要调用者调用一个hs_close_stream,去释放资源。
再次强调一下,由于Stream需要记录跨块扫描的内部状态,所以会有一定的性能损耗。
hyperscan也是从前往后的匹配,当遇到 $ \b等字符时,并不会在当前stream就发生回调,只有在收到下一个stream或者stream关闭的时候才能决定回调与否
4.1.1.Stream的管理
除了前面提到的几个stream的操作函数,还有如下的API可是使用
- hs_reset_stream(): resets a stream to its initial state; this is equivalent to calling hs_close_stream() but will not free the memory used for stream state.
- hs_copy_stream(): constructs a (newly allocated) duplicate of a stream.
- hs_reset_and_copy_stream(): constructs a duplicate of a stream into another, resetting the destination stream first. This call avoids the allocation done by hs_copy_stream().
此外stream还支持如何在stream的内容是压缩的情况下做scan操作
- hs_compress_stream()
- hs_expand_stream()
- hs_reset_and_expand_stream()
4.2.Block模式
Block模式特别简单,调用hs_scan()即可。
4.3.Vector模式
使用API hs_scan_vector()从block数组做正则匹配,从调用者来看,从block list里scan和a)把这些block看成stream的若干写入或b)把这些block list通过memcpy拼写成一个大的block,匹配的效果是一样的。但还需要根据实际情况决定使用哪种模式
4.4.Scratch空间
当做正则扫描的时候,需要一些额外的内存,来保存运行时内部数据。如果栈上申请又比较大,运行时临时申请又影响性能,所以需要我们提前申请的这些空间,我们叫
Scratch空间。
我们使用 hs_alloc_scratch()来申请Scratch空间,指定pattern database即可,不需要我们知道具体空间大小。如果我们有多个database的话,虽然我们会对
每个database调用hs_alloc_scratch,但实际上只生成一个一份大小最合适的Scratch空间。
- 如果是递归scan,比如在回调的时候再做另一次scan,这时需要2个Scratch空间
- 没有递归的情况下,Scratch空间应是per-thread的
- 如果是一写多读的话,我们推荐使用hs_clone_scratch() 来替代多次 hs_alloc_scratch()
4.5.关于自定义内存申请/释放函数
默认情况下,我们都使用malloc/free作为内部申请函数,如果我们系统自己构造了自己的内存管理函数的话,把下面一些函数赋值成自己的函数即可:
- hs_set_database_allocator(), which sets the allocate and free functions used for compiled pattern databases.
- hs_set_scratch_allocator(), which sets the allocate and free functions used for scratch space.
- hs_set_stream_allocator(), which sets the allocate and free functions used for stream state in streaming mode.
- hs_set_misc_allocator(), which sets the allocate and free functions used for miscellaneous data, such as compile error structures and informational strings.
5.关于序列化
对于一些应用来说,确保scan操作之前,pattern database编译好了即可。但对于一些应用来说,也有其他的考量。比如:
- 在其他主机上编译database(如果规则特别多,编译起来很慢的)
- 把编译好的database持久化起来,仅在正则该表的时候才重新编译
- 随时根据情况调整database的所在内存,比如从A地址迁移到B地址
但database在内存的存储里不是顺次存放的,里边有指针引用来引用去,为了让database是可移植的,所以hyperscan提供了如下的函数:
- hs_serialize_database(): serializes a pattern database into a flat relocatable buffer of bytes.
- hs_deserialize_database(): reconstructs a newly allocated pattern database from the output of hs_serialize_database().
- hs_deserialize_database_at(): reconstructs a pattern database at a given memory location from the output of hs_serialize_database().
- hs_serialized_database_size(): given a serialized pattern database, returns the size of the memory block required by the database when deserialized.
- hs_serialized_database_info(): given a serialized pattern database, returns a string containing information about the database. This call is analogous to hs_database_info().
6.关于性能考虑
性能是我们使用hyperscan最最重要的原因,但不恰当的使用,会导致性能大打折扣。我们依次列举一下可能的影响性能的因素,大家共勉:
6.1.不要手工优化表达式
hyperscan比我们更懂正则表达式,比如不区分大小写匹配/abc/,如下几种写法都可以:
- /[Aa][Bb][Cc]/
- /(A|a)(B|b)(C|c)/
- /(?i)abc(?-i)/
- /abc/i
6.2.不必刻意优化对lib的使用
hyperscan能处理很多case,比如小包流,超大包等。除非确实遇到性能问题,否则就用最简单的方式使用hyperscan即可,即大道至简。比如我们知道block模式的匹配效果比stream的匹配效果好,但没有必要特意把一个stream上的所有数据收齐了后一起比较,除非包是一个字节一个字节收到的。
此外,hyperscan的性能随着正则表达式数量增加而性能逐渐下降,是平滑的,不想其他有些软件那样当到达一个阈值后陡降,这是hyperscan的一个优点
hyperscan的throughput也很大,对于3.0G频率的CPU来说,一个core在1us内能scan 3000-bit block 数据。但并不意味着22us能扫描完毕22*3000-bit block数据。
所以不要试图缓存数据来提升scan性能
6.3.如可能尽量使用block模式
block的性能表现要比stream好很多
6.4.pattern database的拆解
如果我们需要统计5种不同的流量,最好建立5个pattern database,分别存放5种待待匹配特征,而不是把所有正则混在一个database里,除非这5种流量的绝大部分的待匹配的内容是一样的,比如第一种流量里有abc,第二种也有,以此类推,并且相同的程度到达90%。
6.5.scratch空间
- 提前申请好scratch空间,不要到匹配的时候申请,而是编译好database后马上申请。
- 为每个context(一个线程)申请一个,不同的database可以复用一个scratch空间
6.7.多使用锚
- 如果明确从开始匹配则使用\A或^作为表达式的开头 比如\^abc\
- 如果明确结尾可使用$, \z 和 \Z
- 前面提到的min_offset和max_offset扩展参数,可以提前帮我们判定匹配结束
6.8.避免任意匹配
比如 /./这样的正则会导致我们进行最多次的匹配,比如abcd这样的字符,会返回5次回调(pcre因为采用贪婪匹配只会返回最后的一个)
另外一个就是待匹配正则的前面和后面不要有可选的部分,比如/x?abcd/ 前面的x?就是多余的,不影响匹配结果,后面的*也会导致我们匹配很多次
如果把这个正则改写成/abc/就会好很多,因为
- 匹配/abc/的集合包含匹配/x?abcd*/,
- 匹配次数明显减少,比如样本 0123abcdddd 匹配/abc/一次,但匹配/x?abcd*/高达5次。abc abcd abcdd abcddd abcddd
6.9.在stream模式下避免使用高重复的方式
/X.{1000,1001}abcd/ 高达1000多次的重复,会给性能带来很大的影响
6.10.
需要匹配的字符尽早出现,可变的部分或者正则发部分扔到后面去
/\wab\d\w\w\w/ 比下面的好
/\w\w\d\w\w/,
/\w(abc)?\d*\w\w\w/
隐式的一些声明也比没有字符好,比如/[0-2][3-5].\w\w/ 也有效的包含了一些信息,注意,即使展开的很详细,比如/(03|04|05|13|14|15|23|24|25).\w\w/也是没啥帮助的
越长字符越有帮助,比如100个字符的表达式里有14字符比有4个字符性能会高出很大一截。
6.11.使用Dot all
Dot all模式,是使用HS_FLAG_DOTALL 这个标志控制的,关闭的话的代价会比较大。 /A.B/ 会变成 /A[^\n]B/.也就是跨行匹配。我们在执行匹配的时候
如果能1行匹配一次,最好打开这个标志
6.12仅匹配一次
前面提到过,hyperscan是多次匹配的,如果设计上确实只需要匹配一次就行了,比如有10条封禁规则,任何一条都可以封禁的话,那么该模式就需要启动。
可以通过(HS_FLAG_SINGLEMATCH)来开启这个模式
6.13.SOM
这个前面已经提到过,如果没有必要,需要关闭这个
6.14.模糊匹配
这个也是明显降低行呢功能的,能不用尽量不用
7.一些测试数据
我们做一点测试的对比,先不测正则,只测试子串查找,子串是16字节的数据,待匹配串是随机的64到96长度的串
测试多模匹配,子串个数分别测试1,8,16,测试算法是 strstr,ac,以及hyperscan,测试100w数据的匹配时间。
算法 | 1个子串 | 8个子串 | 16个子串 | 64个子串 |
---|---|---|---|---|
strstr | 7.660327 | 48.659695 | 95.293705 | 358.87231 |
hyperscan | 12.827749 | 20.445274 | 22.351201 | 22.909993 |
ac | 101.493826 | 101.534645 | 101:596807 | 102:515976 |