REGISTOR：SSD内部非结构化数据处理平台

REGISTOR：SSD存储裴舒怡，杨静，杨青，罗德岛大学，深圳市大普微电子有限公司。公司本文介绍了一个用于在存储器内部进行规则表达的平台REGISTOR。Registor的主要思想是在存储大型数据集的存储中加速正则表达式（regex）搜索，消除I/O瓶颈问题。在闪存SSD内部设计并增强了一个用于regex搜索的特殊硬件引擎，该引擎在从NAND闪存到主机的数据传输期间动态处理数据为了使regex搜索的速度与现代SSD的内部总线速度相匹配，在Registor硬件中设计了一种深度流水线结构，该结构由文件语义提取器、匹配候选查找器、regex匹配单元（REMU）和结果组织器组成。此外，流水线的每个阶段使得可能使用最大等位性。为了使Registor易于被高级应用程序使用，我们在Linux中开发了一组API和库，允许Registor通过有效地将单独的数据块重组为文件来处理SSD中的文件Registor的工作原型已经在我们新设计的NVMe-SSD中构建大量的实验和分析表明，Registor实现了高吞吐量，减少了高达97%的I/O带宽需求，并减少了高达82%的CPU利用率，用于大型数据集中的正则表达式搜索CCS概念：·硬件→外部存储器;·计算机系统组织→专用物理系统;其他关键词和短语：正则表达式，存储处理，近似数据处理，SSD存储，硬件加速器ACM参考格式：裴淑仪，杨靖，杨晴。2019年。REGISTOR：SSD存储内部非结构化数据处理平台 ACM Trans.存储15，1，第7条（2019年3月），24页。https://doi.org/10.1145/33101491介绍大数据的惊人增长在数据处理方面给研究界和IT行业带来了许多挑战其中最关键的是如何从这海量的数据中理解和提取有意义的信息，而这其中近80%是非结构化数据这项研究得到了NSF资助CCF-1439011和CCF-1421823的部分支持本材料中表达的任何意见，发现，这项工作也得到了URI和深圳市大普微电子有限公司之间的研究合同的部分支持，公司作者Pei，J.Yang和Q.杨，罗德岛大学，45 Upper College Road，Kingston，RI 02881，和深圳市大普微电子有限公司。有限公司、地址：深圳市龙岗区龙岗中心黄阁路天安允许制作本作品的全部或部分数字或硬拷贝供个人或课堂使用，无需付费，前提是复制品不以营利或商业利益为目的制作或分发，并且复制品在第一页上带有此通知和完整的引用版权的组成部分，这项工作所拥有的其他人比ACM必须尊重。允许用信用进行提取复制，或重新发布，张贴在服务器上或重新分发到列表，需要事先特定的许可和/或费用。从permissions@acm.org请求权限。© 2019计算机协会。1553-3077/2019/03-ART7 $15.00https://doi.org/10.1145/3310149ACM Transactions on Storage，Vol.号151、第七条。出版日期：2019年3月7第七章：S. Pei等人ACM Transactions on Storage，Vol.号151、第七条。出版日期：2019年3月[12、13、15、25]。在非结构化数据中获取有用的信息不仅需要搜索简单的字符串，还需要应用复杂的模式来获得更深入的见解。在许多不同的方法中，正则表达式（regex）搜索为非结构化数据分析提供了一种强大而灵活的方法[42]。但是，在文件中进行正则表达式搜索是计算密集型的，因为它需要对文件进行全面扫描并进行多个状态转换才能找到完整的匹配。传统的软件解决方案，如regex搜索的grep和awk，无法跟上数据量的快速增长和提供数十千兆字节数据速率的硬件速度由于加速regex搜索的重要性，在过去十年中加速regex搜索的文献。一些研究人员利用许多现代处理器[8，31，44]、多核架构[38]和广泛用于并行计算的GPU [30，62]中可用的SIMD硬件。最近的工作[12]提出了一个统一的自动机处理器（UAP），可以与传统的CPU架构集成，并支持各种自动机模型。另一条研究路线提供了基于FPGA或ASIC的解决方案[17，23，33，56]。Micron来自Titan IC的Helios正则表达式处理器，商业上用于网络入侵检测（NIDS），可以基于FPGA加速提供高达10 GB/s的吞吐量[23]。IBM PowerEN集成了一个正则表达式引擎（RegX），它将正则表达式拆分为子模式和并行进程，实现了20到20%的扫描率。40 GB/s [33，56]。HARE虽然已有的研究工作成功地加速了正则表达式搜索以匹配DRAM的速度，但I/O总线的主要瓶颈在研究界还没有得到足够的重视以电子商务[2]、社交计算[58]和生物信息学[45]为例的TB级非结构化数据存储在数据存储中，例如高速闪存SSD。所有现有的加速器技术都需要将大量数据从数据存储（如AWS S3存储服务[3]）加载到系统DRAM，然后才能进行任何分析将如此大的数据从存储器移动到系统DRAM给存储I/O总线带来了很大的负担目前使用的典型高速I/O总线（例如PCIe 3.0）仅提供3.94GB/s（四通道）和7.88GB/s（八通道）[39]。即使是下一代PCIe 4.0，预计也只能提供7.88GB/s的四通道和15.75GB/s的八通道[40]。然而，现代闪存技术在匹配高性能计算的速度方面表现出巨大的潜力闪存SSD控制器能够支持32个独立的闪存通道[35]，每个通道以每秒667兆传输（MT/s）[35]运行现代SSD后端闪存的总吞吐量达到32 GB/s，通道宽度为16位[34]。因此，我们一方面有高速DRAM，另一方面有高吞吐量闪存SSD，使存储I/O总线成为明显的系统瓶颈。为了真正提高正则表达式搜索的速度，消除系统瓶颈，本文提出了一种新的正则表达式搜索加速方法Registor（egularexpression grabbinginside SSDstore age）。Registor将计算带到存储中，以避免不必要的数据移动，从而消除处理存储中存储的大量数据时的I/O瓶颈。这项工作的初步版本可以在Pei等人[41]中找到。我们开发了寄存器硬件来执行在存储器中的动态regex搜索，目标是内部总线的速度。这个想法是找到匹配的候选人，然后并行检查它们。此外，注册表硬件能够从无序数据块中获取文件语义，并通过发送与正则表达式完全匹配的数据（与行号、位移、长度等相关联）来响应主机为了使Registor的搜索引擎能够为主机上运行的任何应用程序工作，我们开发了一个用户库，其中包括可以由用户应用程序调用的API，一个将regex转换为硬件可理解的格式的编译器，以及一个异常处理程序，REGISTOR：SSD存储内部非结构化数据处理平台第七章：ACM Transactions on Storage，Vol.号151、第七条。出版日期：2019年3月图1. 显示Registor所在位置的系统概述鲁棒性编译器针对Registor硬件进行了优化，以使搜索过程更高效。注册器硬件的数据路径绕过操作系统（OS）的长I/O堆栈以实现低延迟。为了评估我们提出的注册表的潜在优势并展示其性能，我们已经将注册表扩展到我们新开发的NVMe-SSD中，其中包括FPGA中的硬件加速器和在Linux主机上运行的用户库大量实验表明，Registor可将I/O带宽需求降低97%，CPU利用率降低82%，消除了I/O瓶颈，提供了高性能的正则表达式搜索。概括而言，我们的主要贡献如下：一个硬件搜索引擎已经被设计用于SSD中的动态正则表达式搜索搜索引擎是完全流水线的，包括一个文件语义提取器，匹配候选日期查找器，正则表达式匹配单元（REMU），和结果组织器。流水线的每个阶段都利用并行架构来实现高吞吐量。已经开发了一个用户库，使用户应用程序能够充分利用Registor硬件。我们还优化了搜索引擎的编译过程，并通过语法检查和异常处理来提高健壮性从搜索引擎到应用程序的数据传输路径绕过了主机系统中的长I/O堆栈，提供了低延迟。Registor的工作原型已经构建并集成在我们新开发的NVMe-SSD中，包括FPGA中的搜索引擎和运行在Linux主机上的用户库带有Registor的SSD可以被视为具有regex搜索功能的常规块级SSD存储它很容易被应用程序使用，无需修改操作系统。本文的其余部分组织如下。在第二节中，我们提出了注册器的整体架构，然后详细的硬件设计。第3节讨论了Registor软件的设计，第6节讨论了结果，以证明Registor相对于最先进解决方案的优势。第7节讨论了相关的工作，第8节结束了文章。2寄存器硬件考虑图1所示的系统。Registor位于主机应用程序和SSD设备之间它由两大部分组成：硬件搜索引擎和用户库。在本节中，我们将重点介绍硬件搜索引擎的架构，包括每个功能模块以及不同模块之间的交互，并讨论每个模块如何为SSD存储中的高性能正则表达式引擎做出贡献用户库将在下一节中讨论···第七章：S. Pei等人ACM Transactions on Storage，Vol.号151、第七条。出版日期：2019年3月2.1概述图2. 注册器为了在SSD存储中实现高性能的regex搜索，我们的目标是使Registor能够在数据流从闪存传输到主机时执行动态搜索。通过这种方式，存储处理时间对用户完全隐藏和透明。然而，由于正则表达式的遍历消耗多个时钟周期，因此这种引擎匹配SSD中的数据传输速度是具有挑战性的。此外，无序的数据流使得在正则表达式搜索中难以处理文件语义为了应对这些挑战，我们设计了四个硬件模块，文件语义提取器，匹配候选人发现器，RE-MU和结果组织器，充分利用并行和流水线的最大性能。图2显示了注册器硬件的流水线结构。文件语义提取器从NAND闪存中检索的无序数据块中恢复文件语义，并按文件顺序向匹配候选查找器提供数据流匹配候选查找器通过对数据流的快速扫描来定位可能的匹配，并将上下文信息与这些匹配相关联以形成任务。然后，REMU处理这些任务，通过执行正则表达式搜索来从这些匹配候选中确定精确匹配循环数据缓冲区（CDB）用于为REMU提供数据流（详见第2.4节）。由于这些REMU并行工作以获得加速，结果组织器在发送到主机之前对来自REMU的中间结果进行重新排序2.2文件语义提取器文件存储在SSD中的单独数据块中，并从NAND闪存中检索，而不管这些文件是否存在。然而，正则表达式匹配过程不仅需要块内语义，而且需要块间语义。块间语义对于跨块边界匹配正则表达式和提供匹配字符串的文件中位置是必要为了获得块间语义，文件语义提取器根据Registor软件提供的文件布局对数据块进行在下面的段落中，我们简要介绍如何检索文件布局在主机进行硬件设计之前正在检索文件布局。在SSD中，文件-数据块映射存储在inode中。inode中的数据在不同的磁盘文件系统中有不同的格式为了检索这些信息，我们首先从SSD读取超级块以获取文件系统的类型并确定正确的格式。然后，我们通过遍历文件路径中的inode找到文件的inode，并通过解析inode获得整个文件布局。请注意，此功能是在主机中的用户级别实现的，这将在第3.1节中进一步讨论。重新排序块。从NAND闪存中检索数据块遵循先准备先服务原则，无论顺序如何，都将准备好的数据块传递到前端接口。为了将数据块重组为一致的文件格式，我们为块设计了一个重排序缓冲区（RoBREGISTOR：SSD存储内部非结构化数据处理平台第七章：ACM Transactions on Storage，Vol.号151、第七条。出版日期：2019年3月重新排序RoB是具有k个块的容量的随机访问缓冲器。传入的数据块根据其逻辑块编号（LBN）在RoB中进行缓冲RoB中的块以其LBN的升序被发送到流水线的下一级，尽管它们可能无序地进入RoB输入（写）和输出（读）异步发生，以获得最佳性能。由于文件大小可以大于缓冲区大小，因此我们使用一个指针指示RoB的逻辑开始，并将其转换为循环缓冲区。在逻辑上，RoB可以被看作是正在搜索的文件上的大小为k的滑动窗口在用户库中使用相同大小的滑动窗口，以防止可能导致RoB溢出的超出范围的LBN2.3匹配候选人匹配候选查找器通过检查输入正则表达式的起点是否接受输入字符来查找可能的匹配起点是正则表达式中的字符，在检查正则表达式中的其余字符之前，我们将此字符与输入字符进行比较。因此，起始点取决于如何处理正则表达式在大多数情况下，正则表达式从第一个字符匹配到最后一个字符，其中正则表达式的第一个字符是起点。我们还在3.1节中介绍了一种从内部字符匹配正则表达式的方法，其中内部字符作为起点。匹配候选查找器在解析输入数据以找到起始点的同时，还通过计数“\ n”来重新编码行号，并通过计数字符来文件中的位移和行号记录在单独的寄存器中。这些匹配的候选者与它们各自的上下文信息一起封装，以形成要由下一阶段处理的任务，用于精确匹配的REMU这些任务基本上包含匹配候选项的位置，以便REMU知道从哪里重新播放数据流。这在两个方面有利于REMU的性能：一方面，这些任务彼此独立，因此可以在REMU中并行执行而不改变搜索结果;另一方面，每个REMU只需要检查输入流的一小部分，并且可以快速拒绝/接受可能的匹配。由于任务生成仅仅是一个字符的比较和计数器更新，因此它可以轻松地扩展以匹配传入流的带宽请注意，当文件（即，表、日志文件）和结果具有特殊模式，在最坏情况下，所有相关任务都可以分配给一个REMU为了最大限度地减少输入文件的性能影响，我们将随机性的调度策略，通过洗牌的任务在一个时钟周期内产生的调度到REMU。2.4Regex匹配单位正则表达式处理通常包括两个步骤：编译和匹配。编译过程是将正则表达式解释为可以在计算机上执行的代码，匹配过程是对输入流执行这样的代码我们只将匹配过程移植到SSD中的硬件上，因为每次查询只需要一次编译过程我们使用Thompson [53]和Cox [9]中描述的类似方法来生成代码，编译器。此外，我们优化了匹配候选查找器的编译过程，这将在3.1节中详细讨论。虽然这些代码可以直接在计算机上执行，但是需要特殊的硬件和针对硬件优化的指令集，在存储器中实现匹配过程。由于FPGA支持并行计算的自然，我们提出了一个新的指令集，能够处理更复杂的匹配逻辑在一个指令相比，传统的形式。 如表1所示，每条指令都由一个操作和操作数组成。例如，PPAIR可以用于可选地匹配单个字符或两个字符-例如，“PPAIRa，a”匹配char“a”，而“PPAIRa，b”m匹配字符集“[ab]”，并且“PPAIRa，A”匹配不区分大小写的“a”。此功能非常有用，第七章：S. Pei等人ACM Transactions on Storage，Vol.号151、第七条。出版日期：2019年3月|||||表1.指令集行动操作数描述行动操作数描述PPAIR甲乙丙匹配字符a或char BJMPp跳转到P行。NPAIR甲乙丙不匹配字符a而Char B分裂p，q跟踪p和q，其中p和q是行号。普兰奇甲乙丙匹配a到bLSPLITn，l，u，s如果计数器n在下限l和上限u内，则增加计数器n为1。否则，跳转到第s行。NRANGE甲乙丙不匹配ASCIIa到b接受虚空字符串由正则表达式匹配图3. 搜索正则表达式“a（b c）d”（左）和“a [ bc ] d”（右）的示例代码。指令集见表1Inbettercoodeefficienc y. 在图3中示出了用于搜索规则x“a（b c）d”的可切割代码的示例。“b c”不是用“SPL I T”和“JM P”来解释的，而“[ b c]”与“b c”意思相同，被编入“P P AIR b，c”。当前版本的编译器没有完全优化编码效率，这是我们未来的工作之一。我们现在设计的REMU，可以在FPGA中执行这样的代码，充分利用并行性。编译器生成的代码存储在FPGA的指令缓冲区中，每个条目对应于代码中的一行。我们保留一个动作指针（类似于程序计数器，PC），它保存指令缓冲区条目的位图。换句话说，动作指针中的每个位对应于指令缓冲器中的条目。位位置中的值动作指针在每个时钟周期中更新，以跟踪代码接下来应该在哪里执行。最初，action指针指向代码的开头，并按顺序逐行执行。当遇到SPLIT时，动作指针能够同时跟踪多个条目，从而实现并行执行。图4示出了REMU如何将输入字符串“a b d“确定为图3中的字符串x的完全匹配。动作指针在第1位初始化为“1”，在所有其他位初始化为“0”，表示代码从第1行开始执行。输入流提供了一个“a”，它被第1行接受，然后动作指针被更新，REMU现在执行第2行。请注意，第2行是一个SPLIT，它需要将下一个输入字符与第3行和第5行进行比较。这里，REMU通过在动作指针中将位3和5标记为“1”来跟踪这两行。然后，输入字符“b”匹配第3行，但拒绝第5行，因此REMU继续到第3行之后的行。在运行了几个时钟周期后，REMU重新到达第7行，这表明字符串“a b d“is accept e d by r eg e x“a（b c）d”。请注意，前面描述的REMU设计是使用FPGA实现正则表达式搜索的许多方法之一。它可以被其他设计取代，如NFA [47，61]，DFA [14，27]，REGISTOR：SSD存储内部非结构化数据处理平台第七章：ACM Transactions on Storage，Vol.号151、第七条。出版日期：2019年3月图第四章在REMU中执行的一个例子B-FSM [33，56]，位分裂自动机[17，51]等。每种方法都有其各自的优点和最佳适用范围。由于我们的目标是消除搜索非结构化数据的I/O瓶颈，我们专注于如何适应REMU到我们提出的搜索引擎，并采用更先进的自动机设计代替REMU是我们未来研究的一部分由于REMU通常需要多个时钟周期来确定完全匹配，因此将多个REMU编组以提高处理速率，其中每个REMU独立且同时地处理由匹配候选查找器分派的任务为了给REMU提供数据流，我们部署了一个CDB来为每个REMU重放数据流来自NAND闪存的输入数据流保存在匹配候选查找器的CDB中，并通过操纵读写指针在结果组织器处刷新2.5结果组织者在实际应用中，搜索引擎应该按照匹配结果在文件中的位置顺序显示匹配结果。但是，来自REMU的中间结果位于需要按顺序排序结果组织器通过一次弹出最小位移的结果，直到所有结果都被排序，将已排序的流合并为一个注意，每个时钟周期都需要在所有REMU如图2所示，我们使用一个树结构来流水线化这个过程，在这个3注册软件我们现在描述Registor的软件设计，包括用户库和数据路径。我们重点关注这些软件组件是如何与Registor的硬件相协调的3.1用户库用户库包括用于用户级应用程序的API、为Registor硬件生成可执行代码的编译器API 。表 2 列 出 了 两 个 级 别 的 用 户 API 。 更 高 级 别 的 API registor_sync_read（ ） 和registor_parc_read（）的功能与Linux Grep类似。这些函数有两个基本参数：文件名和正则表达式。较低级别的API registor_blks_sync_read（）和registor_blks_sync_read（）提供类似于直接I/O的功能，并允许用户基于单个页面或页面组处理数据。这些函数有三个参数：slba（起始逻辑块地址）、块的数量和输入正则表达式。slba信息可以通过调用registor_file_layout（）获得。此函数使用API（例如，ioctl（）[32]函数，参数为FS_IOC_FIEMAP），以获取文件布局。操作系统将检查访问权限第七章：S. Pei等人ACM Transactions on Storage，Vol.号151、第七条。出版日期：2019年3月\\\表2.用户应用程序的APIAPI函数描述参数registor_sync_read（）与注册表处理同步读取文件file_name，regexregistor_blog_read（）与注册表处理异步读取文件file_name，regexregistor_file_layout（）从SSD文件名registor_blks_sync_read（）与Registor处理同步读取某些块slba，长度，正则表达式registor_blks_blocks_read（）使用寄存器处理异步读取某些块slba，长度，正则表达式图5. 搜索正则表达式“[1-9] \ dapples”的示例代码基于从文件的inode和当前进程的凭证获得的访问控制信息的权限。值得指出的是，这些API可以用于广泛的实际应用程序，Registor可以轻松地针对搜索引擎的大规模文本注释进行定制（例如，Lucene [4]）或重新用于NoSQL或SQL数据库中的数据查询效率感知编译器。编译器将正则表达式转换为Registor硬件可理解的可执行代码。它由词法分析器和解析器组成，词法分析器将正则表达式分解为标记，解析器使用这些标记生成抽象语法树（AST）可执行代码可以通过AST的前序遍历获得为了提高效率，我们还提供了另一个生成可执行代码的函数的REMU。这个想法是在AST中找到一个更具体的节点作为可执行代码的开始。例如，确定性字符“a”比字符类“\d”更具体。在这种情况下，可执行代码从特定节点开始，由两部分组成。第一部分是从特定节点到尾的前序遍历，第二部分是从特定节点到前序遍历的开始。回想一下，我们根据起始点找到匹配的候选项在输入regex中。匹配候选查找器实际上检查输入字符是否被可执行代码的开头接受。为了实现这种优化，我们只需要生成通过从内部节点遍历AST来修改代码，并保持匹配候选查找器的操作不变。由于代码从特定节点开始，因此效率感知编译器可以减少匹配候选项的总数，从而使REMU更高效。图5提供了正则表达式“[1-9] dapples”的示例代码，其中字符类“[1-9]” 和转义字符因此，匹配候选者查找器检查输入流中的当REMU执行第7行时，它会将当前位置重置为起始偏移（“a”的位置）。在输入流中），然后反向扫描数据流以匹配注意，这种优化是以失去代码中多行的并行执行为代价的（例如，一些REGISTOR：SSD存储内部非结构化数据处理平台第七章：ACM Transactions on Storage，Vol.号151、第七条。出版日期：2019年3月图第六章注册表的数据路径行需要前向扫描，而其它行需要后向扫描）。因此，目前用于这些正则表达式的优化只包含字符和字符类。异常处理程序。 支持企业级系统需要软件平台实现健壮性，可靠性和可用性，而不仅仅是简单和可访问的界面。发送到注册器硬件的任何命令都通过语法检查功能和资源检查功能进行验证发生语法错误时，错误处理程序返回一个代码，通知异常的类型。然而，由于硬件资源限制或Registor硬件被其他应用程序占用，并非所有通过语法检查的正则表达式都可以从我们提出的Registor中受益例如，REMU中支持的回溯/循环的最大次数和可执行代码的允许长度受到硬件资源约束。寄存器硬件中的抢占可能导致数据一致性和完整性问题[5]。为了解决这个问题，我们向Registor添加了一个锁以防止抢占。当检测到硬件的无效输入时（例如，过度深度回溯、注册表硬件不可用），错误处理程序调用集成软件regex引擎，而不是使用注册表硬件。在我们的设计中，返回到主机的数据量在大小上被限制为小于每个I/O请求的数据如果搜索结果超过这样的限制，则丢弃超出的部分，并将结果中的一位然后异常处理程序检查此位并向上层应用程序报告溢出。3.2数据路径为确保系统级性能，Registor系统具有精心设计的数据路径，可实现低延迟并避免干扰SSD的正常I/O寄存器硬件放在正常I/O数据路径旁边正常的I/O不经过Registor路径，因此不受其干扰只有在应用程序发出搜索请求时，才会激活注册表数据路径在这种情况下，Registor有两种类型的数据路径，对应于处理的两个阶段：文件布局查询和正则表达式搜索，如图6所示。回想一下，检索文件布局需要SSD中的文件信息、超级块和inode用于文件布局查询的数据路径涉及用于文件路径的虚拟文件系统、用于数据传输的NVMe驱动程序与每次搜索只执行一次的文件布局查询不同，正则表达式搜索对整体性能有显著影响。为了减少延迟，我们将用户库直接连接到NVMe设备驱动程序，绕过文件系统。我们通过NVMe标准中定义的可选命令字段来扩展扩展NVMe命令，从而避免修改操作系统表3中列出了添加的NVMe命令集。这些新添加的NVMe命令兼容第七章：S. Pei等人ACM Transactions on Storage，Vol.号151、第七条。出版日期：2019年3月表3.用于注册器的扩展NVMe命令命令描述参数rgt_fsm_inst将编译器生成的可执行代码发送到设备devID，代码rgt_sync_pis_read同步读取注册表结果devID，slba，lenrgt_sync_data_read同步读取原始数据以进行异常处理devID，slba，lenrgt_blog_data_read异步读取原始数据以进行异常处理devID，slba，len图第七章带寄存器的NVMe-SSD表4.SSD规格FPGAXilinx Ultrascale+ 9P，xcvu9pflgb 2104 -2DRAM9× 1GB，其中1GB用于ECCNAND闪存32 ×256 GB，共8 TB接口PCIE Gen 3 ×4一个标准的NVMe，在操作系统中没有任何修改，使注册表随时可供用户应用程序使用。来自寄存器硬件的结果被视为正常I/O读取命令所请求的正常数据块，并直接发送到NVMe驱动程序，而不受SSD控制器的干扰，这简化了内部控制并减少了延迟。4执行为了对Registor进行评估，我们在SSD平台的资源限制下构建了Registor的工作原型本节介绍了其实现的细节，然后讨论了几个实际问题和解决方案，通过这些问题和解决方案，Registor显示了其优于传统技术的优势。4.1概述整个Registor硬件已在Xilinx FPGA（UltraScale+芯片）上使用Verilog语言实现实现的RTL集成在内部企业级SSD原型中，如图7和表4所示。用户库在运行Linux OS Ubuntu 16.04的主机系统的应用层以C语言实现我们编译器中的标准解析器和词法分析器是基于Flex和Bison开发的[29]。扩展的NVMe命令通过使用保留位来实现REGISTOR：SSD存储内部非结构化数据处理平台第七章：ACM Transactions on Storage，Vol.号151、第七条。出版日期：2019年3月图第八章使用固定分派机制的Registor的最坏情况示例(15：08）的写入命令Dword 13在NVMe标准修订版1.3a [11]。文件布局检索是使用Linux内核为用户空间提供的ioctl（）[32]系统调用来实现的，以获取文件扩展映射。为了使系统延迟不敏感，我们实现了具有背压机制的硬件流水线，流水线中的后一级可以请求前一级暂时停止其数据生产我们使用1MB RoB，数据块大小为4KB。由于我们的SSD原型的内部数据总线宽度为16 B，因此我们实现了16个REMU，如果总线宽度扩展，则可以扩展到32个或更多出于演示目的，每个REMU中支持的代码长度限制为32为了减少RAM资源的使用，我们为16个REMU部署了8个CDB，其中2个REMU共享1个CDB，每个CDB的大小为4KB，与一个数据块的大小相同当发生竞争时，我们使用轮询算法轮流服务来自两个REMU的读4.2REMU中的负载平衡基于第2.4节中描述的设计，REMU具有最高的计算复杂度，并且在寄存器HW的流水线中的所有阶段中消耗最多的硬件资源有效地利用这些硬件资源对Registor的整体性能至关重要。特别是，我们希望使所有REMU并行工作，平衡工作负载，以避免瓶颈问题。如果没有适当的负载平衡，REMU可能会遭受严重的每次开销损失。最坏的情况发生在匹配候选查找器生成的所有任务都被分派到同一个REMU时，与最好的情况相比，最多会导致16倍的速度减慢这种减速是由注册器设计中的固定调度机制引起的当使用固定分派时，匹配候选查找器的16个输出端口和16个REMU是一对一匹配的，并且连接在不同的时钟周期内保持不变在某些情况下，这会严重降低性能，例如当输入文本具有每16个字节的第一个字符匹配搜索字符串的模式时（图8）。每个时钟周期只有第一个字符可以通过匹配的候选查找器如果我们使用固定调度机制，所有这些任务都被调度到同一个REMU。为了有效地利用所有REMU并避免最坏情况的性能，我们实现了一个随机任务调度器，如下所示。回想一下，任务从匹配的候选查找器分派到REMU，具有从16个源到16个目的地的一对一映射，这是REMU之间的工作负载的潜在不平衡的根本原因一个简单的方法是随机生成16个对象的可能排列之一如果用一个查找表来做这个，它会有16个！这在实践中几乎是不可能实现的我们提出了一种实用的方法，称为伪随机洗牌，而不是直接处理16个对象的排列，以实现一个工作负载第七章：S. Pei等人ACM Transactions on Storage，Vol.号151、第七条。出版日期：2019年3月{}{}关于我们{}联系我们{}图第九章随机洗牌。平衡机制这在图9中示出。我们将16个对象分为4组（即，每组具有4个对象）。然后，随机洗牌包括两个阶段：组内阶段和组间阶段。每次洗牌都是基于集合0， 1， 2， 3的排列来执行的，我们称之为洗牌规则。例如，3， 1， 0， 2是一种可能的混洗规则，用于将输入位置0，1，2和3映射到输出位置3，1，0和2。在组内阶段，一个组内的4个对象一个物体相应的。在图9中，如果规则1是3、 1、 0、 2，则组1中名为a、b、c、d的4个对象被重新排列为c、b、d、a具体地，规则中的“3”意味着对象“a”应该是混洗之后的组的第三个对象。然后，我们通过选择 从每个组中选择1个对象以形成新组。在这一步中，我们只将相同位置的对象混合在不同的组中。例如，通过选择每个组中的第一个对象，我们有c，f，i，p。类似地，如果规则50、 1、 3、 2应用于c、f、i、p，则在组间混洗之后，我们获得最终组1作为c、f、p、i这种混洗过程在硬件实现中是可行的，因为它只需要4个对象的排列。整个表可以很容易地存储在一个查找表与4！=24个条目。如果我们希望在每个时钟周期进行混洗，我们只需要从表中选择8个条目作为混洗规则。在我们的实现中，我们使用八个线性反馈移位寄存器（LFSR）来进行选择。每个LFSR被配置为生成一个8位随机数（使结果看起来更随机），其中我们使用5位从1到31的范围中随机选择。由于查找表中有24个条目小于LFSR的输出范围，因此默认情况下，大于23的值被视为0。前面的过程如图10所示。虽然伪随机洗牌提供的随机性比直接方法少，因为它只从（4！）8种可能性，在实施上是切实可行的。该机制优于其他简单机制（例如，16个对象的一步线性移位），防止寄存器落入可能存在于输入文本。为了定量地证明注册表设计中随机分派的必要性，我们进行了基于UVM测试的实验，这将在第5节中描述。我们构造REGISTOR：SSD存储内部非结构化数据处理平台第七章：ACM Transactions on Storage，Vol.号151、第七条。出版日期：2019年3月\\图10. 伪随机数发生器。图十一岁固定调度与随机调度的性能比较一个10MB的文件，其中每行是32B，匹配的字符串只出现在每行的固定位置我们使用IP地址作为匹配字符串，并使用正则表达式来定位文件中的所有IP地址因此，匹配的串在每个32B中的固定位置处在这种情况下，完美的调度是一步线性移位。图11示出了固定调度（即，没有混洗）和根据时钟周期的数量的随机分派。我们观察到随机调度的性能接近完美调度，并且在这种情况下比固定调度快6.7倍4.3高级搜索Registor当前设计的一个优点是它保持了正则表达式的完整性，而不是将正则表达式拆分为并行可执行文件，从而保护了正则表达式中的语法关系因此，Registor很容易支持通常需要内部关系的高级语法在本节中，我们将重点介绍如何在我们的设计中实现以下功能插入符号锚。插入符号锚点匹配字符前的位置。例如，正则表达式“^ a”匹配“a”i t e xt“a b c”，而正则表达式“^ b”不匹配任何字符。 这是一个有用的语法，有助于在实际应用程序中过滤掉无意义的匹配。回想一下，当正则表达式包含字符以外的运算符时，RegistorHW中的匹配候选查找器插入符号锚可以很容易地在注册表中支持，方法是在匹配候选查找器中同时检查字符本身和它前面的字符。由于输入文本在每个时钟周期被截断为16B，因此需要保存16B的最后一个字符，以便在下一个时钟周期中进一步访问在我们的实现中，我们还让用户将“^“的具体含义定义为八个字符之一：“n“、”“（s pace）、“t”、““：”、“（、””[、”{”。 该功能提高了匹配候选查找器的效率，并潜在地减少了发送到REMU的工作量。由于插入符号锚点与正则表达式的开始字符组合在一起比一个字符更具体，因此编译器将始终处理第七章：S. Pei等人ACM Transactions on Storage，Vol.号151、第七条。出版日期：2019年3月\\--当regex包含插入符号锚时，从开始到结束的regex在硬件中支持插入符号锚的成本是1B额外的存储和将一个字符比较扩展为两个字符比较的额外逻辑Backreference和lookahead断言。反向引用匹配之前由捕获组匹配的字符串，其中捕获组通常由一对括号括起来。对于字符串，“（w）a 1”可以匹配“d ad”或“bab”，但不能匹配“bad“，因为符号“1”强制字符串的最后一当存在多个捕获组时，该数字根据正则表达式中的位置顺序表示特定的捕获组。在正则表达式语法的上下文中，Lookahead是一个零长度断言，这意味着lookahead匹配的字符串不包含在结果中。比如说，查找regex=cm）”仅产生结果“3”。引擎将检查数字后面是否有完全支持这两个函数是已知的，即使在软件正则表达式引擎中也是具有挑战性的，因为语法中的不规则性，通常的有限自动机（FA）构造不起作用。此外，当正则表达式有反向引用时，匹配过程是NP难的。为了实现这两个功能，RegistorSW识别FA中需要后向引用或前向断言的状态这些特殊状态被标记为断点并由REMU识别回想一下，REMU基于一个动作指针执行FA，它同时查看多个状态但是，由于需要特殊操作（如加载以前保存的字符串和回溯输入文本），因此必须单独处理断点为了使这些特性与动作指针一起工作当执行过程中遇到任何断点时，我们将操作指针的当前值保存在堆栈中，然后将断点设置为唯一的激活状态。一旦断点引发的所有状态都完成了，并且堆栈不为空，表明匹配过程没有完成，REMU就会弹出堆栈以恢复剩余的激活状态。由于可能同时激活多个断点，因此必须为不同类型的断点分配优先级以避免冲突。我们为更有可能结束匹配过程的断点分配更高的优先级，以实现更好的性能。因此，前向断言比后向引用具有更高的优先级出于演示的目的，我们将堆栈深度限制为2，这意味着在我们的实现中，每个正则表达式最多可以有一个反向引用和一个前瞻断言贪婪和懒惰的量词。 贪婪量词总是找到最长的匹配，而懒惰量词产生最短的匹配。默认情况下，大多数正则表达式引擎都是贪婪的，一个“？” 用于通知编译器量词是贪婪的还是懒惰的。例如，在文本“abbbc“g中查找reg ex“ab[2，3]”，默认情 况下 将返 回 结果 “abbb” 。 要启用延迟匹配，我们使用“ab[2，3]？” 结果是AB。”Registor HW通过使用不同的规则来确定何时停止搜索，从而支持贪婪和惰性量词具体地说，当惰性量化器被使能时，一旦设置了接受位，REMU就停止搜索，而不管动作指针中的其他激活位对于贪婪量词，