其缺点主要在于:
大量虚函数调用:火山模型的next方法通常实现为一个虚函数,在编译器中,虚函数调用需要查找虚函数表, 并且虚函数调用是一个非直接跳转 (indirect jump), 会导致一次错误的CPU分支预测 (brance misprediction), 一次错误的分支预测需要十几个周期的开销。火山模型为了返回一个元组,需要调用多次next 方法,导致昂贵的函数调用开销
类型装箱:对于a + 2 * b之类表达式,由于需要对不同数据类型的变量做解释,所以在Java中需要把这些本来是primitive(如int等类型)的变量包装成Object,但执行时又需要调用具体类型的实现函数,这本质上也是虚函数调用的效率问题;
CPU Cache利用效率低:next方法一次只返回一个元组,元组通常采用行存储,如果仅需访问第一列而每次均将一整行填入CPU Cache,将导致Cache Miss;
条件分支预测失败:现在的CPU都是有并行流水线的,但是如果出现条件判断会导致无法并行。比如判断数据的类型(是string还是int),或判断某一列是否因为其他字段的过滤条件导致本行不需要被读取等场景;
CPU与IO性能不匹配:每次从磁盘读取一个行数据,经过多次调用交给CPU进行处理,显然,大部分时间都是CPU等待数据就绪,导致CPU空转。
通过上述描述,可以得出解决问题的基本方法。可以将问题分为2大类,分别用下述的向量化引擎和动态代码生成技术来解决。
(4)向量化执行引擎
向量化执行以列存为前提,主要思想是每次从磁盘上读取一批列,这些列以数组形式组织。每次next都通过for循环处理列数组。这么做可以大幅减少next的调用次数。相应的CPU的利用率得到了提高,另外数据被组织在一起。可以进一步利用CPU硬件的特性,如SIMD,将所有数据加载到CPU的缓存当中去,提高缓存命中率,提升效率。在列存储与向量化执行引擎的双重优化下,查询执行的速度会有一个非常巨大的飞跃。
动态代码生成
向量化执行减少CPU等待时间,提高CPU Cache命中率,通过减少next调用次数来缓解虚函数调用效率问题。而动态代码生成,则是进一步解决了虚函数调用问题。
动态代码生成技术不使用解释性的统一代码,而是直接生成对应的执行语言的代码并直接用primitive type。对于判断数据类型造成的分支判断,动态代码的效果可以消除这些类型判断,使用硬件指令来进一步提高循环处理效率。
具体实现来说,JVM系如Spark SQL,Presto可以用反射,C++系的Impala则使用了llvm生成中间码。相对来说,C++的效率更高。
向量化和动态代码生成技术往往是一起工作达到更好的效果。
都有哪些存储空间和访问效率优化方法?
存储和IO模块的优化方法很多,这里我们还是在Hadoop生态下来考虑,当然,很多优化方法不是Hadoop特有的,而是通用的。OLAP场景下,数据存储最基础而有效的优化是该行存储为列存储,下面讨论的优化措施均基于列存。
(5)数据压缩和编码
数据压缩是存储领域常用的优化手段,以可控的CPU开销来大幅缩小数据在磁盘上的存储空间,一来可以节省成本,二来可以减小IO和数据在内存中跨线程和跨节点网络传输的开销。目前在用的主流压缩算法包括zlib、snappy和lz4等。压缩算法并不是压缩比越高越好,压缩率越高的算法压缩和解压缩速度往往就越慢,需要根据硬件配置和使用场景在cpu 和io之间进行权衡。
数据编码可以理解为轻量级压缩,包括RLE和数据字典编码等。
上图截至Presto论文,展示了RLE编码和数据字典编码的使用方式。RLE用在各列都是重复字符的情况,比如page0中6行记录的returnflag都是"F"。数据字典可高效使用在区分度较低的列上,比如列中只有几种字符串的场景。考虑到同个表的列的值相关性,数据字典可以跨page使用。
与数据压缩相比,数据编码方式在某些聚合类查询场景下,无需对数据进行解码,直接返回所需结果。比如假设T1表的C1列为某个字符,RLE算法将16个C1列的值“aaaaaabbccccaaaa”编码为6a2b4c4a,其中6a表示有连续6个字符a。当执行 select count(*) from T1 where C1=’a’时,不需要解压6a2b4c4a,就能够知道这16行记录对应列值为a有10行。
在列存模式下,数据压缩和编码的效率均远高于行存。
(6)数据精细化存储
所谓数据精细化存储,是通过尽可能多得提供元数据信息来减少不必要的数据扫描和计算,常用的方法包括但不限于如下几种: