前　　言

正则表达式的概念早在20世纪50年代就由美国数学家Kleene提出了。由于其丰富的描述性特征，正则表达式在网络安全场景下被广泛用于以规则匹配为核心的深度报文检测。流量特征的多样性决定了网络处理需要定义大量正则规则进行匹配，这成为了网络处理中的一大性能瓶颈。尽管在几十年的发展过程中，人们对正则表达式匹配的研究层出不穷，并沉淀了许多经典的算法，但在CPU上以软件形式运行这些经典算法还是难以满足网络处理性能的要求。因此定制化硬件（如FPGA）的正则匹配加速方案曾经一直主导潮流。在如今网络功能虚拟化（Network Function Virtualization，NFV）的浪潮中，如何在CPU上进行高效正则匹配以满足网络场景的需求已成为一大痛点。Hyperscan 应运而生，它让使用通用 x86 处理器进行高性能深度报文检测成为可能。

学术界研究者和产品开发者因此对Hyperscan产生了浓厚的兴趣，是什么样的算法设计让其显著优于先前的软件解决方案？由于实现上的复杂性，单纯从代码层面剖析Hyperscan对大多数人而言较为晦涩和烦琐，这也成为诸多探索者身前的一大壁垒。作为Hyperscan的开发者，我们想通过更好的渠道来分享其中的技术精华，让大家从中汲取一些核心设计思想以应用于实际工作和学习中。因此，我们编写了本书，将开发过程中的经验总结整理成册，供广大读者参考。

本书由浅入深，从正则表达式的介绍和经典算法的剖析来引导感兴趣的初学者入门；接着从Hyperscan总体设计原理逐步深入内部匹配引擎的介绍，梳理Hyperscan的核心技术点；最后以性能优化和应用场景收尾。为使本书更易于理解，我们使用大量图片和伪代码来解释各种算法和概念。

本书适合那些对算法有强烈兴趣的初学者，以及觉得算法晦涩难懂而无所适从的人阅读，也适合作为计算机相关专业的师生用书。同时它可为相关领域的工作者提供技术上的参考。本书不仅能帮助你理解经典的匹配算法，同时可以在系统设计层面教授你如何将理论与实践相结合。希望广大读者都能从本书中有所收获！

本书内容

本书主要介绍正则表达式算法库Hyperscan的设计原理、实现方法、技术细节以及具体应用。本书围绕Hyperscan的以下方面展开。

第1章介绍正则表达式的语法和相关背景知识。

第2章讲解字符串匹配和正则匹配的各类常规算法。

第3章介绍并比较目前业界广泛使用的较为成熟的正则匹配算法库。

第4章全面介绍Hyperscan算法库的功能特性。

第5章和第6章是本书的核心内容。

第5章介绍Hyperscan总体设计原则，并详细描述了对正则表达式的全新解构思路。

第6章介绍解构后的正则表达式模型的实现方法，并详细描述了优化手段。

第7章针对Hyperscan的使用，介绍了性能调优的若干原则与技巧。

第8章展示了Hyperscan与现实应用的整合案例。

本书特色

本书具有以下几个特色。

（1）算法思想，由浅入深。字符串匹配和正则匹配算法，一直是基础算法中比较晦涩的一类，讲解难度较大。而这些都是Hyperscan思想的“基石”。本书搜集诸多基础匹配算法，介绍顺序从简单到复杂，从直观到抽象。本书对每个算法源码抽丝剥茧，分析其优势或局限，对于Hyperscan算法本身的介绍，也蕴含着自顶向下、从宏观到微观的叙述脉络。读者可以从本书的内容编排感受到，即使是思想艰深的算法，也能有层次感。

（2）优化手段，精心打磨。Hyperscan算法的灵魂是优化。本书会在合适的位置展示经过体系化总结的Hyperscan与传统匹配方案的差异性内容，比如基于有效字符串提取的过滤设计、状态机的分类和调优思想、x86指令集加速技术等。上述内容作为对算法基础思想的完整补充，可以使读者充分体会Hyperscan算法之所以高性能的必要原因。

（3）伪码源码，相辅相成。代码是算法书中讲解算法必不可少的素材，但伪码和源码的取舍，却有讲究。本书基于“因地制宜”的原则来安排所需代码的形式。本着让读者完全明晰细节的初衷，我们会选择源码来介绍基础算法，完全展示算法的实现步骤，并配以详细讲解。而对于Hyperscan内部的算法实现，则会使用伪码，因为Hyperscan相较于基础算法而言，背景问题的上下文离一般读者更远，有许多实现细节是和项目本身强相关的，放在书中不免带来干扰，因此我们抽取了最核心的部分，写成伪代码，方便读者理解。

（4）图例表格，精准实用。本书对算法讲解的基本模式是，从基本思想出发，借助代码来解释关键步骤，通常还会辅以一个精心设计的实例运行过程。本书为算法实例的运行设计了风格简约的示意图和表格，力求还原出可以匹配算法运行的整个动态过程，以加深读者对算法的理解。

（5）理论实践，兼收并重。除了最核心的Hyperscan算法库的设计和相关内容的实现，本书还涵盖了算法库在实际应用中的更多丰富内容，比如：业界同类型算法库产品的对比；针对Hyperscan普通用户给出进行性能调优的实用建议；Hyperscan与成熟的开源产品整合的案例分析。本书将这些内容也分享出来，期望给读者呈现出一个全面的、立体的关于Hyperscan这个产品的故事。

建议和反馈

写书是一项极其琐碎、繁重的工作，尽管我已经竭力使本书接近完美，但仍然可能存在漏洞和瑕疵。欢迎读者提供关于本书的反馈意见，这有利于我们改进和提高，从而帮助更多的读者。如果你对本书有任何评论和建议，可以致信作者邮箱xiang.w.wang@intel.com进行交流或登录异步社区的本书页面进行评论，我将不胜感激。

致谢

感谢Langdale Geoffrey和Ravisundar Subhiksha为本书撰写的宝贵内容！感谢网络平台事业部经理周林和李雪峰在本书编写过程中提供的大力支持！感谢提供宝贵意见的同事们，感谢提供技术支持的同学们！感恩我遇到的众多良师益友！