面向Hive查询的存储优化技术

荆忠航，张 伟,2，王佳慧，马利民,2，徐 涛

(1.北京信息科技大学 计算机学院，北京 100101；2.北京信息科技大学 北京材料基因工程高精尖创新中心，北京 100101；3.国家信息中心 信息与网络安全部,北京 100045；4.清华大学 微处理器与片上系统技术研究中心，北京 100084)

0 引言

在Hive底层存储方面，HDFS(Hadoop distributed file system，Hadoop分布式文件系统)将结构化数据文件划分为多个数据块，并将数据块副本顺序或随机地均匀放置在集群中不同节点上，这种数据块存储策略可以使集群具有良好的负载均衡及容错性。但是结构化数据之间的关系比较复杂，数据块之间往往具有一定的关系，其中，并行关系和相交关系是两种常见的数据块运算关系。在向集群放置数据块的过程中，如果忽略了上述关系，则会降低查询任务的执行效率。

近年来，基于相关关系分析的数据存储策略越来越受到学术界和工业界的重视，并取得了一定的研究成果。Cohadoop[1]可以通过配置文件属性locater将相关文件关联起来并存储在同一个节点上，增强了数据本地化程度，减少了运算过程中的网络传输开销和磁盘，输入/输出(input/output，I/O)，提高了查询效率；Hadoop++[2]将协同划分(Co-Paritioned)文件或者数据保存在定制的Trojan文件中，不需要对HDFS做其他改动，实现对用户的透明化。郑湃等[3]对数据集及之间的相关关系进行分析并建模，通过数据集之间的相关关系构建聚类矩阵并划分数据子集，将子集分配到相应的节点上存储；Yuan等[4]综合考虑了数据之间的相关性、数据与计算节点之间的相关程度，提出了同样采用构建聚类矩阵的数据放置策略。Agarwal等[5]根据数据本身的特性,提出了一种动态数据放置策略。Wu等[6]根据用户上传文件请求,挖掘出这些文件之间的相关性，并在初始放置文件时,尝试把具有相关性的文件放置在经常使用的节点上。

本文提出了一种基于相关关系分析的数据块优化放置策略，通过分析数据之间的相关关系，构建并发关系矩阵和相交关系矩阵，并综合数据块的访问频率，采用优化放置方案将数据块存储在集群中。经过实验对比，相较于默认的数据块放置策略，使用基于相关关系分析的数据块优化放置策略，Hive的查询效率提升了约10%。

1 问题分析

在分布式环境下，影响Hive集群性能的关键因素有两个：一是节点的I/O能力，二是网络带宽。在既定的硬件条件下，如何在任务运行的过程中减少磁盘I/O和网络传输开销是提高集群性能的关键问题[7]。

Hive执行查询任务依赖于MapReduce，它是一个并行计算框架，将计算任务部署到集群中的多个甚至所有节点并发执行，可以充分利用集群的计算资源，提高任务执行效率。

同时，MapReduce在调度任务时会考虑输入数据的位置信息，尽量将任务调度在存储了相关输入数据的节点上执行。如果上述调度任务失败，MapReduce将尝试在存储了相关输入数据的节点附近节点上执行任务[8]。这样做的目的是在集群上运行MapReduce任务时，大部分输入数据都能在本地读取，尽量避免移动数据带来的I/O与网络传输开销。因此，在执行MapReduce任务的过程中，数据本地化程度越高，数据传输造成的时间浪费越少，磁盘I/O和网络传输开销也越少[9-10]。

相较于非结构化数据，结构化数据之间的关系比较复杂，数据之间具有一定的相关关系，同时这种关系可以映射到相应的数据块之间。并发关系和相交关系是结构化数据之间经常存在的两种关系：并发关系，即运行在这些数据块之上的计算任务互不影响，可以分布在不同节点上并发执行；相交关系，即数据块之间通常做连接或者联合查询。

在数据块放置的过程中，具有并发关系的数据块应该尽量分散存放，这样可以充分利用集群资源，提高任务的并发性；具有相交关系的数据块应该存储于同一个节点或者相邻节点，提高数据本地化程度，在进行连接或者联合查询时，可以减少网络传输开销和磁盘I/O，提高查询效率。

但是，HDFS默认的数据块放置策略是随机地将数据块存储在集群中，这种数据块存储策略可以使集群具有不错的负载均衡及容错性，但是它忽略了数据块之间的相关关系可能会导致如下问题：一是可能会将访问频率高且具有并行关系的数据块存储在同一节点，导致执行查询任务的过程中整个集群的压力集中在有限个节点上，不能充分利用集群资源；二是可能会将具有相交关系的数据块存储在不同节点或者距离较远的节点上，导致数据本地化程度低，在查询的过程中产生额外的网络传输开销和磁盘I/O。上述问题都会降低Hive的查询效率。

2 关系表分区

具有相同属性或相同取值范围的数据可能分散地分布在关系表中，这种情况下划分出的数据块之间的关联复杂度高，增加了分析数据块相关关系的难度，不利于构建关系矩阵，本文选取范围分区对关系表进行分区处理。通过范围分区将关系表划分为多个子表，每个子表中关键列的数据具有相同的属性或者取值范围。通过范围分区，有效降低了数据块之间关联复杂度，有利于分析数据块之间的相关关系。

基于范围分区的关系表划分过程如下：

1)根据数据集D上的历史查询命令统计结果及用户查询习惯选取关键列，得到关键列集合K={K0,K1,K2，…，Kn-1}，n为关键列的数量。

2)为每个关键列划定分区范围，关键列Ki的分区范围为{Fi0，Fi1,…Fi(mi-1)}，F为每个关键列的取值范围，mi为关键列Ki分区数，0≤i≤n-1。

关系表分区后子表数量t为:

(1)

关系表分区过程如图1所示。

图1 关系表分区过程

3)将t个子表划分到s(s≥1)个数据块中，由于每个子表文件的大小可能与HDFS的数据块大小(默认为128 MB)不一致，因此需要将子表文件进行拆分整合。第j(0≤j≤t-1)个子表文件处理流程如图2所示。

图2 子表文件拆分整合流程

如果子表文件容量小于数据块的大小，则不做任何拆分处理，将该子表文件与其他小于数据块大小的子表文件合并。如果合并后新的子表文件依然小于数据块，则继续等待合并，直到新的子表文件与数据块大小保持一致。

如果子表文件的大小不小于数据块，则对子表文件做拆分处理。如果子表文件的大小为数据块的整数倍，则将子表文件划分为K个数据块：

K=S÷128

(2)

式中S为子表文件的大小，单位为MB。

如果子表文件大小不是数据块的整数倍，则需要将子表文件拆分为K个数据块和一个不大于数据块的子表：

K=floor(S÷128)

(3)

式中floor()为向下取整。

对子表文件执行文件合并操作。

4)子表文件划分后的数据块集合为D={D0，D1，D2，…，Ds-1}，经过上述的拆分整合，子表文件与数据块无法形成一一对应的关系，为了更方便统计数据块之间的相关关系及构建关系矩阵，需要建立元数据表来描述子表文件与数据块之间的映射关系，D的元数据表如表1所示。元数据表包含2个字段：子表文件、数据块。

表1 元数据表

根据子表文件和数据块之间的映射关系表，可以很容易地定位子表文件的数据所在的数据块。

假设s个数据块D={D0，D1，D2，…，Ds-1}需要存储在集群中的q(s≥q)个节点上：O={O0，O1，O2，…，Oq-1}。接下来需要根据关系表的查询命令集以及映射关系表构建关系矩阵，并通过优化放置方案将s个数据块放置在q个节点上。

3 关系矩阵构建

3.1 运算关系分析

在Hive中执行SQL命令时，数据之间存在3种运算关系：

1)并发关系。运行在数据之上的计算任务之间互不影响，数据和操作之间不存在交集，可以在集群中的不同节点上并发执行，通过符号∪表示。

2)相交关系。运行在数据之上的计算任务之间相互影响，数据和操作之间存在交集，例如数据块之间需要进行join或者联合查询，位于不同节点之间的数据块需要通过网络进行数据的传输，以完成相应的计算任务，通过符号∩表示。

3)独立关系。将满足SQL语句中Where条件的数据块与被过滤掉的数据块之间的关系称为独立关系，通过符号φ表示。

分析数据块Di、Dj之间的关系：

(4)

式中0≤i

3.2 构建并发关系矩阵

给定数据集D下的一个SQL命令集合：

Q={Q0，Q1，Q2，…，Qp-1}p≥1

并发关系矩阵和相交关系矩阵可以清楚地描述Q下数据块之间的相关关系，同时有利于分析数据块之间的并发度θ和相交度ε。基于建立好的关系矩阵，通过优化放置方案综合考虑数据块之间的相关度，并放置数据块，可以提高给定查询命令集Q下的查询效率。

首先根据Q中Qi(0≤i

Di={D0，D1，D2，…，Dr} 0≤r

遍历集合Q中的所有命令，得到集合V：

V={D0,D1,D2,…，Dx} 0≤x

根据每条查询命令Qi的子命令序列得到Di中数据块之间的运算关系集。

以某新零售大数据平台中的查询命令集为例，其中的一条SQL命令如下：

统计prediction_target表中名称包含“GSHBSCN”的售货机的每一件商品在2018年5月1日至2019年12月1日每天的销量：

SELECT a.merc_id,a.date,b.order_number FROM prediction_target a LEFT OUTER JOIN all_in_one b ON a.date= b.record_date AND a.vem_id=b.vem_id AND a.merc_id = b.merc_id WHERE a.vem_id like ′GSHBSCN%′ AND a.date>=′2018-05-01′ AND a.date<=′2019-12-01′;

该命令需要在prediction_target和all_in_one两个表之间做join查询，两表划分出的数据块集合D={D0,D1,D2,…,D10}。

根据该命令的Where条件中date等关键列的边界值{′GSHBSCN′,′2018-05-01′,′2019-12-01′}可以定位到相应的数据块，即T={D3,D4,D6,D7,D8,D9}，然后根据该指令的子命令序列得到数据块之间的运算关系表达式：

(D3∩D7)∪((D4∪D6)∩D9)∪D8

根据运算关系表达式可以分解出并发关系集合

((D3,D4),(D3,D6),(D3,D9),(D3,D8),(D7,D4),(D7,D6),(D7,D9),(D7,D8),(D4,D6),(D4,D8),(D6,D8))

和相交关系集合：

((D3,D7),(D4,D9),(D6,D9))

分析查询命令集中的所有指令的运算关系，并推算出运算关系表达式，如表2所示。

表2 查询命令集运算关系表达式集合

每条指令相应的并发关系集合如表3所示。

表3 Qnls并发关系集合

根据表中的运算关系表达式集合，构建并发关系矩阵。

查询命令集合Q下，由s个数据块D={D0,D1,D2,…,Ds-1}构建的并发关系矩阵是一个s行s列的对称矩阵，矩阵中非对角线的元素Pij为第i个数据块与第j个数据块的并发度θ，即第i个数据块在Q的运算关系表达式中出现的次数。

并发度θ代表着两个数据块之间在查询命令集Q下并发执行的频率，定义如下：假设第i个数据块与第j个数据块的并发关系在Q的并发关系集合下出现的次数为c,则：

Pij=Pji=θ=c×R(Di,Dj)

(5)

式中R(Di,Dj)=1且i≠j。

某新零售大数据平台中的查询命令集合下，数据块的并发关系矩阵如图3所示。

图3 数据块并发关系矩阵

3.3 构建相交关系矩阵

在3.2节某新零售大数据平台中的查询命令集合中，每条指令相应的相交关系集合如表4所示。

表4 相交关系集合

查询命令集合Q下，由s个数据块D={D0,D1,D2，…，Ds-1}构建的相交关系矩阵是一个s行s列的方阵且是一个对称矩阵，矩阵中非对角线的元素Iij为第i个数据块与第j个数据块的相交度ε。

相交度ε代表着两个数据块之间在查询命令集Q下相交查询的频率，定义如下：假设第i个数据块与第j个数据块的相交关系在Q的相交关系集合下出现的次数为c,则：

Iij=Iji=ε=c×R(Di,Dj)

(6)

式中R(Di,Dj)=-1且i≠j。

在3.2节某新零售大数据平台中的查询命令集合下，数据块的相交关系矩阵如图4所示。

图4 数据块相交关系矩阵

4 数据块优化放置方案

4.1 统计目标数据块访问频率

在数据块放置的过程中，如果忽略数据块的访问频率，可能会导致热点问题，即经常被访问的数据块有可能被存放在同一节点上，导致集群的工作压力集中在某几个节点上，无法充分利用集群资源，同时给Hive的数据查询带来负面的影响。

为了防止数据热点，在数据块优化放置方案中，将数据块的访问频率作为重要的参数。

计算目标数据块Dn的访问频率时，首先统计查询命令集Q中包含该目标数据块的SQL语句，得到包含h(0≤h≤q)个元素的集合：

M={Qn1,Qn2,…，Qnh}

然后在用户历史查询记录中统计M中的每一条语句的执行频率fi(0≤i≤h)。

最后计算目标数据块Dn在查询命令集Q下的访问频率：

(7)

因此，目标数据块集合D={D0,D1,D2，…，Ds-1}在查询命令集Q下存在对应的访问频率集合：

F={F0,F1,F2，…，Fs-1}

目标数据块访问频率存放在数据库的访问频率表中，有两个字段：目标数据块和访问频率。该表保存集合D中的数据块访问频率如表5所示。

表5 访问频率表

4.2 优化放置方案

并发关系矩阵元素Pij和相交关系矩阵元素Iij描述了数据块之间的并发程度和相交程度，在将数据块放置在集群的过程中根据关系矩阵综合考虑数据块之间的相关关系，选择合适的节点存储数据块。

假设s个数据块D={D0,D1,D2，…，Ds-1}需要存储在集群中q(s≥q)个节点上，节点的集合为

O={O0,O1,O2,…,Oq-1}。

定义q个集合T0、T1、T2、…、Tq-1、Ti为放置在节点Oi上的数据块集合。基于相关关系分析的数据块优化放置方案步骤如下：

1)在集合D中顺序取出q个数据块，放置在集合数据块缓存集合中。

2)在数据块缓存集合中取出第一个待放置数据块，放置在任意一个T中。

3)在数据块缓存集合中取出下一个待放置数据块Dt(0≤t≤s)，计算Dt与每一个T集合的β值和φ值。

设βi为待放置数据块与Ti={Di0,Di1,Di2，…，Dij}(0≤i≤q,0≤j≤s)中的数据块并发度之和：

(8)

设φi为待放置数据块与Ti中的数据块相交度之和：

(9)

如果Ti=φ，则βi=0，φi=0。

4)计算待放置数据块Dt与每一个T集合的α值：

αi=βi+φi

(10)

式中0≤i≤q。

α值反映了待放置数据块与T集合的相关程度。如果α的值为正，则代表Dt与T集合中的数据块主要为并发关系；如果α的值为负，则代表Dt与T集合中的数据块主要为相交关系；如果α的值为0，则代表T集合中无数据块或Dt与T集合具有同等的并发度和相交度。且α越小代表Dt与T集合的并发度和相交度越接近。

5)计算μ值。

μ值为待放置数据块Dt的访问频率Ft与每一个T集合中已存入数据块的访问频率之和。

设

Ti={Di0,Di1,Di2，…，Dij}(0≤i≤q,0≤j≤s) 则

(11)

μi反映了Dt存入第i个节点Ti后，该节点的总的访问频率，μi的值越高，则说明Ti越有可能存在热点问题。

用户在配置文件中设置节点访问频率的阈值σ，当μi>σ时，则Dt不放置在节点Ti中。

6)放置数据块。

如果α存在唯一最小值，且μ的值小于阈值σ，则Dt放置在最小α值的T集合中；如果存在多个最小值，且μ的值小于阈值σ，则考虑集群的负载均衡，在所有最小α值的T中选择数据块数量最少的T集合并将Dt放置在其中。

如果最小α值的集合Ti，其μ的值大于阈值σ，待放置数据块Dt存入该节点，则有可能导致热点问题，需要选择其他节点进行存储。

考虑到网络带宽对于数据通信的影响，选择与Ti位于同一机架的节点作为新的候选节点。在Hadoop集群中位于同一机架的节点在物理结构上是指连接在同一台交换机的所有节点。一般情况下，机架内节点之间的数据通信效率要高于机架间节点的数据通信效率。因此选择同一机架内的节点存放数据块Dt，当执行连接或联合查询时，在一定程度上也降低了网络传输开销。

7)获取Dt候选节点集合：

A={Oi1,Oi2,…，Oil} 0≤l≤q

A即与节点Oi位于同一机架上的节点集合。

相应的候选T集合为：

T={Ti1,Ti2,…，Til} 0≤l≤q

计算Dt与T中每一个T集合的α值与μ值。将T集合按照α值递增的顺序进行排序，从第一个T开始，比较μ值与阈值σ的大小，如果μ值大于阈值σ，则选择下一个T继续比较，直到找到μ值小于阈值σ的T，并将Dt放置在该T中。

8)如果候选T中的所有μ值大于阈值σ，则选择不同机架的节点构成候选节点，重复执行步骤7)。

9)重复步骤3)～8)，直到A中的数据块全部放置在T集合中为止。

10)依次将Ti中的数据块存入节点Oi中(0≤i≤q)，并清空Ti，直到所有T集合中的数据块存入相应的节点并清空为止。

11)重复步骤1)～10)，直到集合D中的所有数据块存入集群中为止。

5 实验

5.1 实验环境

本文搭建了一个实验平台，用于测试使用数据块优化放置方案存储数据相较于HDFS默认的数据存储方式下Hive的查询效率是否有效提升。

实验平台由包含10个节点的集群构成，集群上安装运行Hadoop和Hive。实验平台中每个物理节点的硬件条件是相同的：8 G内存，4核CPU和200 GB硬盘。

实验数据使用某新零售大数据平台中智能终端售货机采集的真实商品销量数据，包括两张表：商品销售记录表all_in_one，该表中包含236 304 718条商品销售记录，文件大小约16 GB；预测目标表prediction_target，该表中包含45 113 525条记录，每条记录代表一件预测目标商品，文件大小约3 GB。

本文中Hive的查询效率即单次H-SQL开始执行至返回查询结果的时间S(单位为s)，由两部分组成，即S=(t1+t2)，t1为MapReduce任务执行时间，t2为查询结果打印时间。由于两种存储策略下实验的数据集和查询命令相同，因此两种策略下查询结果的打印时间t2相差无几，误差可以忽略。因此S可以反映两种存储策略下MapReduce任务执行时间的差异，即Hive查询效率的差异。

5.2 对比实验

将数据块优化放置方案和HDFS默认数据块放置方案下的Hive查询效率进行对比。

两种数据块放置方案下，每个节点放置的数据块数量如表6所示。

表6 数据块分布情况

实验使用的查询工作集Q中共5条查询命令，Q0、Q1、Q2、Q3执行同一类查询任务：统计数台售货机在某一时间范围内的每日销量，按指令顺序增加目标售货机数量和延长时间范围，观察Hive查询任务在不同负载下查询效率是否得到提升；Q4统计每一台售货机的每一件商品在某时间范围内的商品总销量。

Q0、Q1、Q2、Q3查询结果中分别包含2 737、110 972、1 464 528、31 792 854行数据，Q4查询结果中包含87 975行数据。每条指令执行20次取时间S的平均值，Q0、Q1、Q2、Q3在优化放置方案和默认放置方案下的效率对比如图5所示。Q4的执行效率如图6所示。

图5 Q0、Q1、Q2、Q3查询性能对比

图6 Q4查询性能对比

从上述实验对比可知，相较于默认的数据块放置策略，使用基于相关关系分析的数据块优化放置策略存储数据，Hive的查询效率提升了约10%。

6 结束语

HDFS存储结构化数据时忽略了数据之间的相关关系对上层Hive查询效率存在的不利影响，本文由此提出了一套基于相关关系分析的数据存储策略。划分数据块前对数据集使用范围分区重新组织，然后根据查询命令集分析数据块之间的相关关系并构建关系矩阵，最后通过数据块优化放置方案将数据存储在HDFS集群中合适的节点上。通过实验对比可知，相较于默认的数据块放置策略，使用基于相关关系分析的数据块优化放置策略存储数据，Hive的查询效率有了一定的提升。