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

很多大型数据应用程序通常在非结构化或半结构化的原始数据格式(如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)以获得更多信息;有其他问题的话,欢迎写邮件联络我们,电邮地址是shoumik@cs.standford.edu和fabuzaid@cs.standford.edu。

查看英文原文:

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

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

  • 发表于:
  • 原文链接:http://www.infoq.com/cn/news/2018/09/stamford-opensource-Sparser

扫码关注云+社区

领取腾讯云代金券