要了解如何处理海量文件，推荐阅读@geofflangdale和@lemire撰写的《秒级解析千兆字节JSON》。

🔗 https://t.co/dlomnFq1fV

如果你想深入学习SIMD，而不仅仅是停留在“它能加快速度”的肤浅理解，强烈推荐这篇文章。

🔗 https://t.co/oAoBcxkWpb https://t.co/6z2ZxBcY3Q

秒级解析千兆字节JSON

来源：https://arxiv.org/html/1902.08318 11institutetext:Geoff Langdale22institutetext:branchfree.org 悉尼，新南威尔士州 澳大利亚 22email:[email protected]:Daniel Lemire44institutetext:魁北克大学（TELUQ） 蒙特利尔，魁北克 加拿大 44email:[email protected]###### 摘要

JavaScript对象表示法（JSON）是Web上一种普遍使用的数据交换格式。由于数据量庞大，解析JSON文档可能成为性能瓶颈。因此，我们有动力让JSON解析尽可能快。

尽管JSON解析问题已经相当成熟，但我们表明，仍然可以实现显著的加速。我们提出了第一个符合标准、能在单核上使用商用处理器每秒处理千兆字节数据的JSON解析器。与最先进的参考解析器（如RapidJSON）相比，我们使用的指令数可以减少四分之一或更多。与其他验证解析器不同，我们的软件（simdjson）广泛使用单指令多数据流（SIMD）指令。为确保可重复性，simdjson在宽松许可下作为开源软件免费提供。

1 引言

JavaScript对象表示法（JSON）是一种用于表示数据的文本格式Bray (2017 (https://arxiv.org/html/1902.08318v7#bib.bib4))。它通常用于Web上的浏览器-服务器通信。它被许多数据库系统支持，如MySQL、PostgreSQL、IBM DB2、SQL Server、Oracle，以及数据科学框架（如Pandas）。许多面向文档的数据库（如CouchDB或RethinkDB）都以JSON为核心。

JSON语法可以看作是JavaScript的一种受限形式，但它被许多编程语言使用。JSON有四种基本类型或原子（字符串、数字、布尔值、null），可以嵌入到复合类型（数组和对象）中。对象采用大括号内一系列键值对的形式，其中键是字符串（例如，{“name”:“Jack”,“age”:22}）。数组是方括号内以逗号分隔的值列表（例如，[1,“abc”,null]）。复合类型可以包含基本类型或任意深度嵌套的复合类型作为值。参见图1 (https://arxiv.org/html/1902.08318v7#S1.F1) 示例。JSON规范定义了六个结构字符（‘[’, ‘{’, ‘]’, ‘}’, ‘:’, ‘,’）：它们用于界定对象和数组的位置和结构。

⬇{“Width”:800,“Height”:600,“Title”:“Viewfrommyroom”,“Url”:“http://ex.com/img.png”,“Private”:false,“Thumbnail”:{“Url”:“http://ex.com/th.png”,“Height”:125,“Width”:100},“array”:[116,943,234],“Owner”:null}root”Width”: 800”Height”: 600”Title”: ”View from my room””Url”: ”http://ex.com/img.png””Private”: false”Thumbnail””Url”: ”http://ex.com/th.png””Height”: 125”Width”: 100”array”116943234”Owner”: null图1:JSON示例要从软件访问JSON文档中包含的数据，通常会将JSON文本转换为类似树形的逻辑表示，类似于图1 (https://arxiv.org/html/1902.08318v7#S1.F1) 的右侧，我们称之为JSON解析。我们将解析树中的每个值、对象和数组称为节点。解析后，程序员可以依次访问每个节点，并导航到其兄弟节点或子节点，而无需进行复杂且容易出错的字符串解析。

解析大型JSON文档是一项常见任务。Palkar等人指出，大数据应用程序可能花费80-90%的时间来解析JSON文档Palkar等人 (2018 (https://arxiv.org/html/1902.08318v7#bib.bib25))。Boncz等人将加速JSON解析确定为加速数据库处理的一个感兴趣主题Boncz等人 (2019 (https://arxiv.org/html/1902.08318v7#bib.bib2))。

JSON解析意味着错误检查：数组必须以方括号开头和结尾，对象必须以大括号开头和结尾，对象必须由以逗号分隔的值对（以冒号分隔）组成，其中所有键都是字符串。数字必须符合规范并位于有效范围内。在字符串值之外，只允许少量ASCII字符。在字符串值内部，某些字符（如ASCII行结束符）必须转义。JSON规范要求文档使用Unicode字符编码（UTF-8、UTF-16或UTF-32），其中UTF-8是默认值。因此，我们必须验证所有字符串的字符编码。因此，JSON解析比仅仅定位节点更为繁重。我们认为，接受错误JSON的解析器既危险——因为它会静默接受格式错误的JSON，无论是意外生成还是恶意生成——而且规范不明确——很难预测或广泛同意错误格式JSON文件的语义。

为了加速处理，我们应该尽可能高效地使用处理器。商用处理器（Intel、AMD、ARM、POWER）支持单指令多数据（SIMD）指令。这些SIMD指令与常规指令不同，可以同时处理多个字。例如，从Haswell微架构（2013年）开始，Intel和AMD处理器支持AVX2指令集和256位向量寄存器。因此，在最新的x64处理器上，我们可以在一条指令中比较两个32字符的字符串。因此，直接使用SIMD指令可以用很少的指令定位重要字符（例如，‘“’, ‘=’）。我们将SIMD指令的应用称为向量化。向量化软件通常比传统软件使用更少的指令。在其他条件相同的情况下，生成更少指令的代码运行更快。

与向量化密切相关的一个概念是无分支处理：每当处理器必须在两条代码路径（分支）之间做出选择时，在当前的流水线处理器上，由于分支预测错误，存在遭受几个周期惩罚的风险。根据我们的经验，SIMD指令在无分支环境中最有可能有益。

据我们所知，公开可用的JSON验证解析器很少使用SIMD指令。由于其复杂性，整个JSON解析问题可能不会立即看起来适合向量化。

我们的核心结果之一是，SIMD指令结合最小化分支可以创下JSON解析的新速度记录——通常在单个核心上每秒处理千兆字节数据。我们提出了几个具有普遍兴趣的特定性能导向策略。

• •我们使用纯算术和逻辑运算以及每个输入字节固定数量的指令来检测带引号的字符串，同时省略转义引号（§3.1.1 (https://arxiv.org/html/1902.08318v7#S3.SS1.SSS1)）。
• •我们使用向量化分类来区分码点值集合，从而避免了进行NN次比较以识别某个值属于大小为NN的集合的负担（§3.1.2 (https://arxiv.org/html/1902.08318v7#S3.SS1.SSS2)）。
• •我们仅使用SIMD指令验证UTF-8字符串（§3.1.5 (https://arxiv.org/html/1902.08318v7#S3.SS1.SSS5)）。

2 相关工作

文献中加速JSON解析的一种常见策略是选择性解析。Alagiannis等人Alagiannis等人 (2012 (https://arxiv.org/html/1902.08318v7#bib.bib1))提出了NoDB，一种无需先将JSON数据加载到数据库中即可查询的方法。它部分依赖于对输入的选择性解析。Bonetta和Brantner使用推测性即时（JIT）编译和选择性数据访问来加速JSON处理Bonetta和Brantner (2017 (https://arxiv.org/html/1902.08318v7#bib.bib3))。他们发现重复的常量结构，并生成针对这些结构的代码。

Li等人提出了他们的快速解析器Mison，它可以跳过中间内容直接跳转到查询字段Li等人 (2017 (https://arxiv.org/html/1902.08318v7#bib.bib17))。Mison使用SIMD指令快速识别一些结构字符，但除此之外，通过使用分支密集循环在通用寄存器中处理位向量。Mison不尝试验证文档；它假设文档是纯ASCII而不是Unicode（UTF-8）。我们将Mison架构中最相关的组件总结如下：

1. 1.第一步，将输入文档与每个结构字符（‘[’, ‘{’, ‘]’, ‘}’, ‘:’, ‘,’）以及反斜杠（‘\’）进行比较。每次比较使用一条SIMD指令，一次比较32对字节。然后将比较结果转换为位图，其中位值1表示相应结构字符的存在。当不需要时，Mison省略与数组相关的结构字符（‘[’, ‘]’）。Mison仅在此第一步使用SIMD指令；这似乎也是唯一基本无分支的步骤。
2. 2.第二步，Mison识别文档中每个字符串的起始和结束点。它使用引号和反斜杠位图。对于每个引号字符，Mison使用快速指令（popcnt）计算其前面反斜杠的数量：前面有奇数个反斜杠的引号将被关闭并忽略。
3. 3.第三步，Mison识别由引号分隔的字符串跨度。它从第二步生成的位图中提取每个字（例如，32位）。它迭代地将引号对转换为字符串掩码（其中1位表示字符串的内容）；每次迭代使用少量算术和逻辑运算。
4. 4.最后一步，Mison使用字符串掩码关闭并忽略字符串内包含的结构字符（例如，{,},:）。Mison将所有左大括号存储在堆栈中。每遇到一个右大括号，就从堆栈中弹出一个左大括号，从左开始，从而找到匹配的大括号对。对于每个可能的嵌套深度，可以通过部分复制输入的冒号位图来构建指示冒号位置的位图。

从位图中提取的冒号位置开始，Mison可以通过向后扫描来解析键，通过向前扫描来解析值。它可以只选择给定深度的内容。实际上，冒号位图充当索引，用于选择性解析输入文档。在某些情况下，在3.5 GHz的Intel处理器上，Mison对于高选择性查询可以以超过2 GB/s的速度扫描JSON文档。这比使用传统的验证解析器（如RapidJSON）所能达到的速度要快。

FishStoreXie等人 (2019 (https://arxiv.org/html/1902.08318v7#bib.bib29))解析JSON数据并选择感兴趣的子集，将结果存储在快速键值存储中Chandramouli等人 (2018 (https://arxiv.org/html/1902.08318v7#bib.bib6))。虽然最初的FishStore依赖于Mison，但开源版本111https://github.com/microsoft/FishStore默认使用simdjson进行快速解析。

Pavlopoulou等人Pavlopoulou等人 (2018 (https://arxiv.org/html/1902.08318v7#bib.bib26))提出了一种并行JSON处理器，支持高级查询和重写规则。它避免了首先加载数据的需求。

Sparser快速过滤未处理的文档，以找到大部分相关信息Palkar等人 (2018 (https://arxiv.org/html/1902.08318v7#bib.bib25))，然后依赖解析器。我们可以将simdjson与Sparser结合使用。

基于选择性解析的系统（如Mison或Sparser）可能仅在只有一小部分数据感兴趣时有益。但是，如果数据被重复访问，最好使用标准解析器将数据加载到数据库引擎中。非验证解析器（如Mison）可能最适合于紧密集成的系统，其中不太可能出现无效输入。

2.1 XML解析

在JSON之前，关于XML解析已经有了许多类似的工作。Noga等人Noga等人 (2002 (https://arxiv.org/html/1902.08318v7#bib.bib24))报告说，当需要解析的值少于80%时，只解析所需的值更为经济。Marian等人Marian和Siméon (2003 (https://arxiv.org/html/1902.08318v7#bib.bib19))提出在执行查询之前将XML文档“投影”到较小的文档。Green等人Green等人 (2004 (https://arxiv.org/html/1902.08318v7#bib.bib14))表明，我们可以使用确定性有限自动机（DFA）快速解析XML，其中状态是在解析期间惰性计算的。Farfán等人Farfán等人 (2007 (https://arxiv.org/html/1902.08318v7#bib.bib10))更进一步，使用内部物理指针跳过XML文档的整个部分。Takase等人Takase等人 (2005 (https://arxiv.org/html/1902.08318v7#bib.bib28))通过避免对先前遇到过的文本子集进行语法分析来加速XML解析。Kostoulas等人设计了一个名为Screamer的快速验证XML解析器：它通过减少不同处理步骤的数量来实现更高的速度Kostoulas等人 (2006 (https://arxiv.org/html/1902.08318v7#bib.bib15))。Cameron等人表明，我们可以使用SIMD指令更快地解析XMLCameron等人 (2008 (https://arxiv.org/html/1902.08318v7#bib.bib5))，他们的解析器称为Parabix。Zhang等人Zhang等人 (2009 (https://arxiv.org/html/1902.08318v7#bib.bib31))展示了如何通过首先索引文档，然后分别解析文档的分区来并行解析XML文档。

Mytkowicz等人Mytkowicz等人 (2014 (https://arxiv.org/html/1902.08318v7#bib.bib22))展示了如何使用SIMD指令向量化有限状态机。他们展示了在HTML分词方面的良好结果，比基线快两倍以上。

2.2 CSV解析

数据也以逗号分隔值（CSV）的形式出现。Mühlbauer等人使用SIMD指令优化CSV解析和加载，以定位分隔符和无效字符Mühlbauer等人 (2013 (https://arxiv.org/html/1902.08318v7#bib.bib20))。Ge等人使用两遍方法，第一遍识别分隔符之间的区域，而第二遍处理记录Ge等人 (2019 (https://arxiv.org/html/1902.08318v7#bib.bib12))。

3 解析器架构与实现

根据我们的经验，大多数JSON解析器通过自上而下的递归下降Cohen和Roth (1978 (https://arxiv.org/html/1902.08318v7#bib.bib7))进行，单遍扫描输入字节，逐字符解码。我们采用不同的策略，使用两遍不同的扫描。我们在后续章节详细讨论之前，先简要描述这两个阶段。

1. 1.在第一阶段，我们验证字符编码并识别所有JSON节点（例如，数字、字符串、null、true、false、数组、对象）的起始位置。我们还需要JSON规范Bray (2017 (https://arxiv.org/html/1902.08318v7#bib.bib4))中定义的所有结构字符（‘[’, ‘{’, ‘]’, ‘}’, ‘:’, ‘,’）的位置。这些位置以整数索引的形式写入一个单独的数组。在此阶段，有必要区分