斯坦福开源数据解析引擎Sparser：解析速度提升22倍

过滤之后再解析：用Sparser更快地分析原始数据

很多大型数据应用程序通常在非结构化或半结构化的原始数据格式（如JSON）上运行。查询这些文件常常是非常耗时的，尤其是那些探索性应用程序，数据科学家用来运行查询以探索及更好地理解其数据。令人惊讶的是，这些应用程序实际上有80%-90%的执行时间是用于解析数据，而不是用于评估实际查询本身。因此，解析实际上才是瓶颈。

我们将在本文中介绍 Sparser （请点击 这里 查看代码），它来自斯坦福DAWN团队最近的一个研究项目，该项目解决了这个性能瓶颈。Sparser的关键见解是，利用SIMD加速过滤函数在解析之前过滤数据。在JSON、Avro和Parquet数据上，Sparser的速度比最先进的解析器最多快22倍，并且能将Apache Spark中的端对端的查询运行时间最多提高9倍。

解析为什么那么慢？

在数据库社区中，原始数据流的解析很慢不是一个新问题。在2017年的VLDB大会上，微软的研究人员展示了 Mison ，这是一种新的JSON解析器，它利用SIMD命令在每个JSON记录上构建结构化的索引，从而在不完全反序列化记录的情况下实现高效的字段投影。尽管Misaon比之前最先进的解析器（如 RapidJSON ）的速度有显著的提高，但是它仍然有很大的改进余地。当我们在JSON数据样本上测量Mison的解析吞吐量时，发现它平均每个字节仍然执行多个CPU周期。与简单的逐字节SIMD数据扫描相比（解析的理论上限），Mison的速度慢了几个数量级。

使用最先进的解析器在L1缓存中解析单个5KB大小的 JSON记录所花费的CPU周期， 与在同一缓冲区中使用SIMD指令搜索单字节值的扫描比较。性能差异超过100倍。

将过滤器下推到解析器

Mison基于以前的解析器上的改进来自一个简单的想法：先投影再解析。也即，获取大多数用户指定的，在JSON数据查询中找到的投影，并且先投影再解析，从而只解析用户需要的必要字段。

受到Mison的启发，Sparser采用了一种类似的想法：假如我们把过滤器也下推到解析器，会怎样？这对于数据分析中的探索性查询来说，尤其有帮助，因为这些查询通常都具有高度选择性。比如，在读取JSON或CSV数据的Databrick的云设备上，当我们查看跟Spark SQL查询有关的分析元数据时，发现40%的查询选择了不到20%的记录。在研究人员对来自Censys（用于互联网端口扫描的搜索引擎）的JSON数据的查询上，我们进行了类似的分析，发现对这些查询甚至有更高的选择性。这个观察结果带来了优化解析的一个直观的想法：如果JSON记录不会出现在呈现给用户的最终结果中，那么我们就根本不该解析它！

在读取JSON和CSV数据的Databricks上，来自Spark SQL的有选择性的CDF，和在Censys搜索引擎上，研究人员对JSON数据的查询。这两组查询都具有高度选择性。

Sparser：先过滤再解析

基于这个见解，Sparser把JSON和用户指定的SQL查询作为输入，通过以下步骤评估解析之后JSON文件上的查询：

1. Sparser从查询中提取谓词，并把每个谓词编译成一个或多个原始过滤器（Raw Filter，简称RF）。RF是SIMD高效的过滤函数，可以遍历原始数据和丢弃记录；RF可以允许假阳性，但不允许假阴性。
2. Sparser在所有候选RF上运行一个基于成本的优化器，并生成一个RF级联，也即一系列RF，这些RF可以最大化给定查询和原始数据的解析吞吐量。
3. Sparser在原始数据上应用所选择的RF级联，并丢弃那些没有通过级联的记录。最后，其余的行传递给下游的解析器，如RapidJSON或Mison。

左边：传统解析器。右边：Sparser， 利用快速的基于SIMD原始过滤器先过滤再解析，具有假阳性，但不具有假阴性。

因为Sparser的优化与先前的解析工作是正交的， 所以Sparser实际上是对其他解析器的补充，其中包括最先进的那些解析器，如Mison。此外，Sparser还推广到其他更结构化的数据形式，如Avro和Parquet。这些数据形式不依赖显式字符（如JSON中的‘{’和‘}’）来划分记录；因此，Mison的结构化索引技术（扫描这些字符）无法应用。

Sparser与现有技术的比较

为了衡量Sparser的有效性，首先，我们在一台机器上对它进行基准测试，与RapidJSON和Mison比较。我们从Censys下载了一个16GB大小的JSON记录，评估了9个不同选择度的查询，测量了它们使用每个解析器在用Sparser和不用Sparser情况下的运行时间。



在Censys数据集上，Sparser与RapidJSON和Mison的对比。在所有我们进行基准测试的9个查询上，Sparser最多把解析时间提高了22倍。

当与RapidJSON或Mison组合使用时，Sparser平均减少了大约1个数量级的解析时间，最多缩短了22倍。因为这些查询具有较低选择性，Sparser的原始过滤器可以有效地过滤那些不需要解析的记录，即使与Mison结合使用时也是如此。因此，原始过滤对于Mison的投影优化是个补充。

接下来，我们把Sparser与Apache Spark集成，并将它和Spark常用的Jackson JSON解析库结合起来。我们选择了更多的记录，这次有来自Censys的652GB大小的JSON记录，还有来自推特的68GB大小的推文。然后，对于每个数据集，我们对1）从磁盘下载数据所耗费的时间，2）在Spark SQL中端到端的查询运行时间，其中包括从磁盘加载数据的时间、解析数据的时间和评估查询的时间，3）查询评估运行时间本身进行基准测试。

在推文查询（左侧）和Censys 查询（右侧）上，Spark + Sparser 与 Spark + Jackson的对比情况。Sparser将查询时间最多提高了9倍。实验是在10个节点GCE集群上的Spark 2.2中进行的。

对于4个推文查询，Sparser把端到端运行时间最多提高了9倍，而对于9个Censys查询，速度则最多提高了4倍。对于这两种情况而言，回复查询的时间仅仅比从磁盘加载文件所需时间多了一点。

最后，为了在Avro和Parquet上对Sparser进行基准测试，我们把一个小一些的推文数据集（32GB大小）转换成这两种格式，并对同样的4个推文查询进行基准测试。我们发现，即使对这些优化过的数据格式，Sparser还是可以加速查询速度，最多可以提高5倍。

在Avro格式（左侧）和Parquet格式（右侧）上对推文查询使用Sparser的比较。Sparser分别将查询时间最多提高了5倍和4.3倍。

总结

简单回顾一下，Sparser是新的解析引擎，用于非结构化和半结构化的数据格式，例如JSON、Avro和Parquet。

Sparser：

• 用原始过滤器过滤后再解析，丢弃那些不需要用假阳性率解析的记录

• 用高效的优化器选择级联的原始过滤器

• 提供超过现有解析器22倍的加速度

Sparser是开源软件，并且还在开发中；您可以看看我们在 GitHub上发布的alpha版本代码 （ https://github.com/stanford-futuredata/sparser ）。最近，我们在旧金山召开的 Spark+AI峰会 上演示了Sparser（相关录像 https://vimeo.com/274496506 ）。我们将于8月30日（周四）在里约热内卢的 2018年VLDB大会 上再次演示Sparser。请查看我们 准备印制的论文 （ http://www.vldb.org/pvldb/vol11/p1576-palkar.pdf ）以获得更多信息；有其他问题的话，欢迎写邮件联络我们，电邮地址是[email protected]和[email protected]。

查看英文原文：

Filter Before You Parse: Faster Analytics on Raw Data with Sparser

https://dawn.cs.stanford.edu/2018/08/07/sparser/

感谢蔡芳芳对本文的审校及策划。