荊忠航，張 偉,2，王佳慧，馬利民,2，徐 濤

(1.北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院，北京 100101；2.北京信息科技大學(xué) 北京材料基因工程高精尖創(chuàng)新中心，北京 100101；3.國(guó)家信息中心 信息與網(wǎng)絡(luò)安全部,北京 100045；4.清華大學(xué) 微處理器與片上系統(tǒng)技術(shù)研究中心，北京 100084)

0 引言

在Hive底層存儲(chǔ)方面，HDFS(Hadoop distributed file system，Hadoop分布式文件系統(tǒng))將結(jié)構(gòu)化數(shù)據(jù)文件劃分為多個(gè)數(shù)據(jù)塊，并將數(shù)據(jù)塊副本順序或隨機(jī)地均勻放置在集群中不同節(jié)點(diǎn)上，這種數(shù)據(jù)塊存儲(chǔ)策略可以使集群具有良好的負(fù)載均衡及容錯(cuò)性。但是結(jié)構(gòu)化數(shù)據(jù)之間的關(guān)系比較復(fù)雜，數(shù)據(jù)塊之間往往具有一定的關(guān)系，其中，并行關(guān)系和相交關(guān)系是兩種常見的數(shù)據(jù)塊運(yùn)算關(guān)系。在向集群放置數(shù)據(jù)塊的過(guò)程中，如果忽略了上述關(guān)系，則會(huì)降低查詢?nèi)蝿?wù)的執(zhí)行效率。

近年來(lái)，基于相關(guān)關(guān)系分析的數(shù)據(jù)存儲(chǔ)策略越來(lái)越受到學(xué)術(shù)界和工業(yè)界的重視，并取得了一定的研究成果。Cohadoop[1]可以通過(guò)配置文件屬性locater將相關(guān)文件關(guān)聯(lián)起來(lái)并存儲(chǔ)在同一個(gè)節(jié)點(diǎn)上，增強(qiáng)了數(shù)據(jù)本地化程度，減少了運(yùn)算過(guò)程中的網(wǎng)絡(luò)傳輸開銷和磁盤，輸入/輸出(input/output，I/O)，提高了查詢效率；Hadoop++[2]將協(xié)同劃分(Co-Paritioned)文件或者數(shù)據(jù)保存在定制的Trojan文件中，不需要對(duì)HDFS做其他改動(dòng)，實(shí)現(xiàn)對(duì)用戶的透明化。鄭湃等[3]對(duì)數(shù)據(jù)集及之間的相關(guān)關(guān)系進(jìn)行分析并建模，通過(guò)數(shù)據(jù)集之間的相關(guān)關(guān)系構(gòu)建聚類矩陣并劃分?jǐn)?shù)據(jù)子集，將子集分配到相應(yīng)的節(jié)點(diǎn)上存儲(chǔ)；Yuan等[4]綜合考慮了數(shù)據(jù)之間的相關(guān)性、數(shù)據(jù)與計(jì)算節(jié)點(diǎn)之間的相關(guān)程度，提出了同樣采用構(gòu)建聚類矩陣的數(shù)據(jù)放置策略。Agarwal等[5]根據(jù)數(shù)據(jù)本身的特性,提出了一種動(dòng)態(tài)數(shù)據(jù)放置策略。Wu等[6]根據(jù)用戶上傳文件請(qǐng)求,挖掘出這些文件之間的相關(guān)性，并在初始放置文件時(shí),嘗試把具有相關(guān)性的文件放置在經(jīng)常使用的節(jié)點(diǎn)上。

本文提出了一種基于相關(guān)關(guān)系分析的數(shù)據(jù)塊優(yōu)化放置策略，通過(guò)分析數(shù)據(jù)之間的相關(guān)關(guān)系，構(gòu)建并發(fā)關(guān)系矩陣和相交關(guān)系矩陣，并綜合數(shù)據(jù)塊的訪問(wèn)頻率，采用優(yōu)化放置方案將數(shù)據(jù)塊存儲(chǔ)在集群中。經(jīng)過(guò)實(shí)驗(yàn)對(duì)比，相較于默認(rèn)的數(shù)據(jù)塊放置策略，使用基于相關(guān)關(guān)系分析的數(shù)據(jù)塊優(yōu)化放置策略，Hive的查詢效率提升了約10%。

1 問(wèn)題分析

在分布式環(huán)境下，影響Hive集群性能的關(guān)鍵因素有兩個(gè)：一是節(jié)點(diǎn)的I/O能力，二是網(wǎng)絡(luò)帶寬。在既定的硬件條件下，如何在任務(wù)運(yùn)行的過(guò)程中減少磁盤I/O和網(wǎng)絡(luò)傳輸開銷是提高集群性能的關(guān)鍵問(wèn)題[7]。

Hive執(zhí)行查詢?nèi)蝿?wù)依賴于MapReduce，它是一個(gè)并行計(jì)算框架，將計(jì)算任務(wù)部署到集群中的多個(gè)甚至所有節(jié)點(diǎn)并發(fā)執(zhí)行，可以充分利用集群的計(jì)算資源，提高任務(wù)執(zhí)行效率。

同時(shí)，MapReduce在調(diào)度任務(wù)時(shí)會(huì)考慮輸入數(shù)據(jù)的位置信息，盡量將任務(wù)調(diào)度在存儲(chǔ)了相關(guān)輸入數(shù)據(jù)的節(jié)點(diǎn)上執(zhí)行。如果上述調(diào)度任務(wù)失敗，MapReduce將嘗試在存儲(chǔ)了相關(guān)輸入數(shù)據(jù)的節(jié)點(diǎn)附近節(jié)點(diǎn)上執(zhí)行任務(wù)[8]。這樣做的目的是在集群上運(yùn)行MapReduce任務(wù)時(shí)，大部分輸入數(shù)據(jù)都能在本地讀取，盡量避免移動(dòng)數(shù)據(jù)帶來(lái)的I/O與網(wǎng)絡(luò)傳輸開銷。因此，在執(zhí)行MapReduce任務(wù)的過(guò)程中，數(shù)據(jù)本地化程度越高，數(shù)據(jù)傳輸造成的時(shí)間浪費(fèi)越少，磁盤I/O和網(wǎng)絡(luò)傳輸開銷也越少[9-10]。

相較于非結(jié)構(gòu)化數(shù)據(jù)，結(jié)構(gòu)化數(shù)據(jù)之間的關(guān)系比較復(fù)雜，數(shù)據(jù)之間具有一定的相關(guān)關(guān)系，同時(shí)這種關(guān)系可以映射到相應(yīng)的數(shù)據(jù)塊之間。并發(fā)關(guān)系和相交關(guān)系是結(jié)構(gòu)化數(shù)據(jù)之間經(jīng)常存在的兩種關(guān)系：并發(fā)關(guān)系，即運(yùn)行在這些數(shù)據(jù)塊之上的計(jì)算任務(wù)互不影響，可以分布在不同節(jié)點(diǎn)上并發(fā)執(zhí)行；相交關(guān)系，即數(shù)據(jù)塊之間通常做連接或者聯(lián)合查詢。

在數(shù)據(jù)塊放置的過(guò)程中，具有并發(fā)關(guān)系的數(shù)據(jù)塊應(yīng)該盡量分散存放，這樣可以充分利用集群資源，提高任務(wù)的并發(fā)性；具有相交關(guān)系的數(shù)據(jù)塊應(yīng)該存儲(chǔ)于同一個(gè)節(jié)點(diǎn)或者相鄰節(jié)點(diǎn)，提高數(shù)據(jù)本地化程度，在進(jìn)行連接或者聯(lián)合查詢時(shí)，可以減少網(wǎng)絡(luò)傳輸開銷和磁盤I/O，提高查詢效率。

但是，HDFS默認(rèn)的數(shù)據(jù)塊放置策略是隨機(jī)地將數(shù)據(jù)塊存儲(chǔ)在集群中，這種數(shù)據(jù)塊存儲(chǔ)策略可以使集群具有不錯(cuò)的負(fù)載均衡及容錯(cuò)性，但是它忽略了數(shù)據(jù)塊之間的相關(guān)關(guān)系可能會(huì)導(dǎo)致如下問(wèn)題：一是可能會(huì)將訪問(wèn)頻率高且具有并行關(guān)系的數(shù)據(jù)塊存儲(chǔ)在同一節(jié)點(diǎn)，導(dǎo)致執(zhí)行查詢?nèi)蝿?wù)的過(guò)程中整個(gè)集群的壓力集中在有限個(gè)節(jié)點(diǎn)上，不能充分利用集群資源；二是可能會(huì)將具有相交關(guān)系的數(shù)據(jù)塊存儲(chǔ)在不同節(jié)點(diǎn)或者距離較遠(yuǎn)的節(jié)點(diǎn)上，導(dǎo)致數(shù)據(jù)本地化程度低，在查詢的過(guò)程中產(chǎn)生額外的網(wǎng)絡(luò)傳輸開銷和磁盤I/O。上述問(wèn)題都會(huì)降低Hive的查詢效率。

2 關(guān)系表分區(qū)

具有相同屬性或相同取值范圍的數(shù)據(jù)可能分散地分布在關(guān)系表中，這種情況下劃分出的數(shù)據(jù)塊之間的關(guān)聯(lián)復(fù)雜度高，增加了分析數(shù)據(jù)塊相關(guān)關(guān)系的難度，不利于構(gòu)建關(guān)系矩陣，本文選取范圍分區(qū)對(duì)關(guān)系表進(jìn)行分區(qū)處理。通過(guò)范圍分區(qū)將關(guān)系表劃分為多個(gè)子表，每個(gè)子表中關(guān)鍵列的數(shù)據(jù)具有相同的屬性或者取值范圍。通過(guò)范圍分區(qū)，有效降低了數(shù)據(jù)塊之間關(guān)聯(lián)復(fù)雜度，有利于分析數(shù)據(jù)塊之間的相關(guān)關(guān)系。

基于范圍分區(qū)的關(guān)系表劃分過(guò)程如下：

1)根據(jù)數(shù)據(jù)集D上的歷史查詢命令統(tǒng)計(jì)結(jié)果及用戶查詢習(xí)慣選取關(guān)鍵列，得到關(guān)鍵列集合K={K0,K1,K2，…，Kn-1}，n為關(guān)鍵列的數(shù)量。

2)為每個(gè)關(guān)鍵列劃定分區(qū)范圍，關(guān)鍵列Ki的分區(qū)范圍為{Fi0，F(xiàn)i1,…Fi(mi-1)}，F(xiàn)為每個(gè)關(guān)鍵列的取值范圍，mi為關(guān)鍵列Ki分區(qū)數(shù)，0≤i≤n-1。

關(guān)系表分區(qū)后子表數(shù)量t為:

(1)

關(guān)系表分區(qū)過(guò)程如圖1所示。

圖1 關(guān)系表分區(qū)過(guò)程

3)將t個(gè)子表劃分到s(s≥1)個(gè)數(shù)據(jù)塊中，由于每個(gè)子表文件的大小可能與HDFS的數(shù)據(jù)塊大小(默認(rèn)為128 MB)不一致，因此需要將子表文件進(jìn)行拆分整合。第j(0≤j≤t-1)個(gè)子表文件處理流程如圖2所示。

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

如果子表文件容量小于數(shù)據(jù)塊的大小，則不做任何拆分處理，將該子表文件與其他小于數(shù)據(jù)塊大小的子表文件合并。如果合并后新的子表文件依然小于數(shù)據(jù)塊，則繼續(xù)等待合并，直到新的子表文件與數(shù)據(jù)塊大小保持一致。

如果子表文件的大小不小于數(shù)據(jù)塊，則對(duì)子表文件做拆分處理。如果子表文件的大小為數(shù)據(jù)塊的整數(shù)倍，則將子表文件劃分為K個(gè)數(shù)據(jù)塊：

K=S÷128

(2)

式中S為子表文件的大小，單位為MB。

如果子表文件大小不是數(shù)據(jù)塊的整數(shù)倍，則需要將子表文件拆分為K個(gè)數(shù)據(jù)塊和一個(gè)不大于數(shù)據(jù)塊的子表：

K=floor(S÷128)

(3)

式中floor()為向下取整。

對(duì)子表文件執(zhí)行文件合并操作。

4)子表文件劃分后的數(shù)據(jù)塊集合為D={D0，D1，D2，…，Ds-1}，經(jīng)過(guò)上述的拆分整合，子表文件與數(shù)據(jù)塊無(wú)法形成一一對(duì)應(yīng)的關(guān)系，為了更方便統(tǒng)計(jì)數(shù)據(jù)塊之間的相關(guān)關(guān)系及構(gòu)建關(guān)系矩陣，需要建立元數(shù)據(jù)表來(lái)描述子表文件與數(shù)據(jù)塊之間的映射關(guān)系，D的元數(shù)據(jù)表如表1所示。元數(shù)據(jù)表包含2個(gè)字段：子表文件、數(shù)據(jù)塊。

表1 元數(shù)據(jù)表

根據(jù)子表文件和數(shù)據(jù)塊之間的映射關(guān)系表，可以很容易地定位子表文件的數(shù)據(jù)所在的數(shù)據(jù)塊。

假設(shè)s個(gè)數(shù)據(jù)塊D={D0，D1，D2，…，Ds-1}需要存儲(chǔ)在集群中的q(s≥q)個(gè)節(jié)點(diǎn)上：O={O0，O1，O2，…，Oq-1}。接下來(lái)需要根據(jù)關(guān)系表的查詢命令集以及映射關(guān)系表構(gòu)建關(guān)系矩陣，并通過(guò)優(yōu)化放置方案將s個(gè)數(shù)據(jù)塊放置在q個(gè)節(jié)點(diǎn)上。

3 關(guān)系矩陣構(gòu)建

3.1 運(yùn)算關(guān)系分析

在Hive中執(zhí)行SQL命令時(shí)，數(shù)據(jù)之間存在3種運(yùn)算關(guān)系：

1)并發(fā)關(guān)系。運(yùn)行在數(shù)據(jù)之上的計(jì)算任務(wù)之間互不影響，數(shù)據(jù)和操作之間不存在交集，可以在集群中的不同節(jié)點(diǎn)上并發(fā)執(zhí)行，通過(guò)符號(hào)∪表示。

2)相交關(guān)系。運(yùn)行在數(shù)據(jù)之上的計(jì)算任務(wù)之間相互影響，數(shù)據(jù)和操作之間存在交集，例如數(shù)據(jù)塊之間需要進(jìn)行join或者聯(lián)合查詢，位于不同節(jié)點(diǎn)之間的數(shù)據(jù)塊需要通過(guò)網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)的傳輸，以完成相應(yīng)的計(jì)算任務(wù)，通過(guò)符號(hào)∩表示。

3)獨(dú)立關(guān)系。將滿足SQL語(yǔ)句中Where條件的數(shù)據(jù)塊與被過(guò)濾掉的數(shù)據(jù)塊之間的關(guān)系稱為獨(dú)立關(guān)系，通過(guò)符號(hào)φ表示。

分析數(shù)據(jù)塊Di、Dj之間的關(guān)系：

(4)

式中0≤i

3.2 構(gòu)建并發(fā)關(guān)系矩陣

給定數(shù)據(jù)集D下的一個(gè)SQL命令集合：

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

并發(fā)關(guān)系矩陣和相交關(guān)系矩陣可以清楚地描述Q下數(shù)據(jù)塊之間的相關(guān)關(guān)系，同時(shí)有利于分析數(shù)據(jù)塊之間的并發(fā)度θ和相交度ε?；诮⒑玫年P(guān)系矩陣，通過(guò)優(yōu)化放置方案綜合考慮數(shù)據(jù)塊之間的相關(guān)度，并放置數(shù)據(jù)塊，可以提高給定查詢命令集Q下的查詢效率。

首先根據(jù)Q中Qi(0≤i

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

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

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

根據(jù)每條查詢命令Qi的子命令序列得到Di中數(shù)據(jù)塊之間的運(yùn)算關(guān)系集。

以某新零售大數(shù)據(jù)平臺(tái)中的查詢命令集為例，其中的一條SQL命令如下：

統(tǒng)計(jì)prediction_target表中名稱包含“GSHBSCN”的售貨機(jī)的每一件商品在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兩個(gè)表之間做join查詢，兩表劃分出的數(shù)據(jù)塊集合D={D0,D1,D2,…,D10}。

根據(jù)該命令的Where條件中date等關(guān)鍵列的邊界值{′GSHBSCN′,′2018-05-01′,′2019-12-01′}可以定位到相應(yīng)的數(shù)據(jù)塊，即T={D3,D4,D6,D7,D8,D9}，然后根據(jù)該指令的子命令序列得到數(shù)據(jù)塊之間的運(yùn)算關(guān)系表達(dá)式：

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

根據(jù)運(yùn)算關(guān)系表達(dá)式可以分解出并發(fā)關(guān)系集合

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

和相交關(guān)系集合：

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

分析查詢命令集中的所有指令的運(yùn)算關(guān)系，并推算出運(yùn)算關(guān)系表達(dá)式，如表2所示。

表2 查詢命令集運(yùn)算關(guān)系表達(dá)式集合

每條指令相應(yīng)的并發(fā)關(guān)系集合如表3所示。

表3 Qnls并發(fā)關(guān)系集合

根據(jù)表中的運(yùn)算關(guān)系表達(dá)式集合，構(gòu)建并發(fā)關(guān)系矩陣。

查詢命令集合Q下，由s個(gè)數(shù)據(jù)塊D={D0,D1,D2,…,Ds-1}構(gòu)建的并發(fā)關(guān)系矩陣是一個(gè)s行s列的對(duì)稱矩陣，矩陣中非對(duì)角線的元素Pij為第i個(gè)數(shù)據(jù)塊與第j個(gè)數(shù)據(jù)塊的并發(fā)度θ，即第i個(gè)數(shù)據(jù)塊在Q的運(yùn)算關(guān)系表達(dá)式中出現(xiàn)的次數(shù)。

并發(fā)度θ代表著兩個(gè)數(shù)據(jù)塊之間在查詢命令集Q下并發(fā)執(zhí)行的頻率，定義如下：假設(shè)第i個(gè)數(shù)據(jù)塊與第j個(gè)數(shù)據(jù)塊的并發(fā)關(guān)系在Q的并發(fā)關(guān)系集合下出現(xiàn)的次數(shù)為c,則：

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

(5)

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

某新零售大數(shù)據(jù)平臺(tái)中的查詢命令集合下，數(shù)據(jù)塊的并發(fā)關(guān)系矩陣如圖3所示。

圖3 數(shù)據(jù)塊并發(fā)關(guān)系矩陣

3.3 構(gòu)建相交關(guān)系矩陣

在3.2節(jié)某新零售大數(shù)據(jù)平臺(tái)中的查詢命令集合中，每條指令相應(yīng)的相交關(guān)系集合如表4所示。

表4 相交關(guān)系集合

查詢命令集合Q下，由s個(gè)數(shù)據(jù)塊D={D0,D1,D2，…，Ds-1}構(gòu)建的相交關(guān)系矩陣是一個(gè)s行s列的方陣且是一個(gè)對(duì)稱矩陣，矩陣中非對(duì)角線的元素Iij為第i個(gè)數(shù)據(jù)塊與第j個(gè)數(shù)據(jù)塊的相交度ε。

相交度ε代表著兩個(gè)數(shù)據(jù)塊之間在查詢命令集Q下相交查詢的頻率，定義如下：假設(shè)第i個(gè)數(shù)據(jù)塊與第j個(gè)數(shù)據(jù)塊的相交關(guān)系在Q的相交關(guān)系集合下出現(xiàn)的次數(shù)為c,則：

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

(6)

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

在3.2節(jié)某新零售大數(shù)據(jù)平臺(tái)中的查詢命令集合下，數(shù)據(jù)塊的相交關(guān)系矩陣如圖4所示。

圖4 數(shù)據(jù)塊相交關(guān)系矩陣

4 數(shù)據(jù)塊優(yōu)化放置方案

4.1 統(tǒng)計(jì)目標(biāo)數(shù)據(jù)塊訪問(wèn)頻率

在數(shù)據(jù)塊放置的過(guò)程中，如果忽略數(shù)據(jù)塊的訪問(wèn)頻率，可能會(huì)導(dǎo)致熱點(diǎn)問(wèn)題，即經(jīng)常被訪問(wèn)的數(shù)據(jù)塊有可能被存放在同一節(jié)點(diǎn)上，導(dǎo)致集群的工作壓力集中在某幾個(gè)節(jié)點(diǎn)上，無(wú)法充分利用集群資源，同時(shí)給Hive的數(shù)據(jù)查詢帶來(lái)負(fù)面的影響。

為了防止數(shù)據(jù)熱點(diǎn)，在數(shù)據(jù)塊優(yōu)化放置方案中，將數(shù)據(jù)塊的訪問(wèn)頻率作為重要的參數(shù)。

計(jì)算目標(biāo)數(shù)據(jù)塊Dn的訪問(wèn)頻率時(shí)，首先統(tǒng)計(jì)查詢命令集Q中包含該目標(biāo)數(shù)據(jù)塊的SQL語(yǔ)句，得到包含h(0≤h≤q)個(gè)元素的集合：

M={Qn1,Qn2,…，Qnh}

然后在用戶歷史查詢記錄中統(tǒng)計(jì)M中的每一條語(yǔ)句的執(zhí)行頻率fi(0≤i≤h)。

最后計(jì)算目標(biāo)數(shù)據(jù)塊Dn在查詢命令集Q下的訪問(wèn)頻率：

(7)

因此，目標(biāo)數(shù)據(jù)塊集合D={D0,D1,D2，…，Ds-1}在查詢命令集Q下存在對(duì)應(yīng)的訪問(wèn)頻率集合：

F={F0,F1,F2，…，F(xiàn)s-1}

目標(biāo)數(shù)據(jù)塊訪問(wèn)頻率存放在數(shù)據(jù)庫(kù)的訪問(wèn)頻率表中，有兩個(gè)字段：目標(biāo)數(shù)據(jù)塊和訪問(wèn)頻率。該表保存集合D中的數(shù)據(jù)塊訪問(wèn)頻率如表5所示。

表5 訪問(wèn)頻率表

4.2 優(yōu)化放置方案

并發(fā)關(guān)系矩陣元素Pij和相交關(guān)系矩陣元素Iij描述了數(shù)據(jù)塊之間的并發(fā)程度和相交程度，在將數(shù)據(jù)塊放置在集群的過(guò)程中根據(jù)關(guān)系矩陣綜合考慮數(shù)據(jù)塊之間的相關(guān)關(guān)系，選擇合適的節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)塊。

假設(shè)s個(gè)數(shù)據(jù)塊D={D0,D1,D2，…，Ds-1}需要存儲(chǔ)在集群中q(s≥q)個(gè)節(jié)點(diǎn)上，節(jié)點(diǎn)的集合為

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

定義q個(gè)集合T0、T1、T2、…、Tq-1、Ti為放置在節(jié)點(diǎn)Oi上的數(shù)據(jù)塊集合?；谙嚓P(guān)關(guān)系分析的數(shù)據(jù)塊優(yōu)化放置方案步驟如下：

1)在集合D中順序取出q個(gè)數(shù)據(jù)塊，放置在集合數(shù)據(jù)塊緩存集合中。

2)在數(shù)據(jù)塊緩存集合中取出第一個(gè)待放置數(shù)據(jù)塊，放置在任意一個(gè)T中。

3)在數(shù)據(jù)塊緩存集合中取出下一個(gè)待放置數(shù)據(jù)塊Dt(0≤t≤s)，計(jì)算Dt與每一個(gè)T集合的β值和φ值。

設(shè)βi為待放置數(shù)據(jù)塊與Ti={Di0,Di1,Di2，…，Dij}(0≤i≤q,0≤j≤s)中的數(shù)據(jù)塊并發(fā)度之和：

(8)

設(shè)φi為待放置數(shù)據(jù)塊與Ti中的數(shù)據(jù)塊相交度之和：

(9)

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

4)計(jì)算待放置數(shù)據(jù)塊Dt與每一個(gè)T集合的α值：

αi=βi+φi

(10)

式中0≤i≤q。

α值反映了待放置數(shù)據(jù)塊與T集合的相關(guān)程度。如果α的值為正，則代表Dt與T集合中的數(shù)據(jù)塊主要為并發(fā)關(guān)系；如果α的值為負(fù)，則代表Dt與T集合中的數(shù)據(jù)塊主要為相交關(guān)系；如果α的值為0，則代表T集合中無(wú)數(shù)據(jù)塊或Dt與T集合具有同等的并發(fā)度和相交度。且α越小代表Dt與T集合的并發(fā)度和相交度越接近。

5)計(jì)算μ值。

μ值為待放置數(shù)據(jù)塊Dt的訪問(wèn)頻率Ft與每一個(gè)T集合中已存入數(shù)據(jù)塊的訪問(wèn)頻率之和。

設(shè)

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

(11)

μi反映了Dt存入第i個(gè)節(jié)點(diǎn)Ti后，該節(jié)點(diǎn)的總的訪問(wèn)頻率，μi的值越高，則說(shuō)明Ti越有可能存在熱點(diǎn)問(wèn)題。

用戶在配置文件中設(shè)置節(jié)點(diǎn)訪問(wèn)頻率的閾值σ，當(dāng)μi>σ時(shí)，則Dt不放置在節(jié)點(diǎn)Ti中。

6)放置數(shù)據(jù)塊。

如果α存在唯一最小值，且μ的值小于閾值σ，則Dt放置在最小α值的T集合中；如果存在多個(gè)最小值，且μ的值小于閾值σ，則考慮集群的負(fù)載均衡，在所有最小α值的T中選擇數(shù)據(jù)塊數(shù)量最少的T集合并將Dt放置在其中。

如果最小α值的集合Ti，其μ的值大于閾值σ，待放置數(shù)據(jù)塊Dt存入該節(jié)點(diǎn)，則有可能導(dǎo)致熱點(diǎn)問(wèn)題，需要選擇其他節(jié)點(diǎn)進(jìn)行存儲(chǔ)。

考慮到網(wǎng)絡(luò)帶寬對(duì)于數(shù)據(jù)通信的影響，選擇與Ti位于同一機(jī)架的節(jié)點(diǎn)作為新的候選節(jié)點(diǎn)。在Hadoop集群中位于同一機(jī)架的節(jié)點(diǎn)在物理結(jié)構(gòu)上是指連接在同一臺(tái)交換機(jī)的所有節(jié)點(diǎn)。一般情況下，機(jī)架內(nèi)節(jié)點(diǎn)之間的數(shù)據(jù)通信效率要高于機(jī)架間節(jié)點(diǎn)的數(shù)據(jù)通信效率。因此選擇同一機(jī)架內(nèi)的節(jié)點(diǎn)存放數(shù)據(jù)塊Dt，當(dāng)執(zhí)行連接或聯(lián)合查詢時(shí)，在一定程度上也降低了網(wǎng)絡(luò)傳輸開銷。

7)獲取Dt候選節(jié)點(diǎn)集合：

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

A即與節(jié)點(diǎn)Oi位于同一機(jī)架上的節(jié)點(diǎn)集合。

相應(yīng)的候選T集合為：

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

計(jì)算Dt與T中每一個(gè)T集合的α值與μ值。將T集合按照α值遞增的順序進(jìn)行排序，從第一個(gè)T開始，比較μ值與閾值σ的大小，如果μ值大于閾值σ，則選擇下一個(gè)T繼續(xù)比較，直到找到μ值小于閾值σ的T，并將Dt放置在該T中。

8)如果候選T中的所有μ值大于閾值σ，則選擇不同機(jī)架的節(jié)點(diǎn)構(gòu)成候選節(jié)點(diǎn)，重復(fù)執(zhí)行步驟7)。

9)重復(fù)步驟3)～8)，直到A中的數(shù)據(jù)塊全部放置在T集合中為止。

10)依次將Ti中的數(shù)據(jù)塊存入節(jié)點(diǎn)Oi中(0≤i≤q)，并清空Ti，直到所有T集合中的數(shù)據(jù)塊存入相應(yīng)的節(jié)點(diǎn)并清空為止。

11)重復(fù)步驟1)～10)，直到集合D中的所有數(shù)據(jù)塊存入集群中為止。

5 實(shí)驗(yàn)

5.1 實(shí)驗(yàn)環(huán)境

本文搭建了一個(gè)實(shí)驗(yàn)平臺(tái)，用于測(cè)試使用數(shù)據(jù)塊優(yōu)化放置方案存儲(chǔ)數(shù)據(jù)相較于HDFS默認(rèn)的數(shù)據(jù)存儲(chǔ)方式下Hive的查詢效率是否有效提升。

實(shí)驗(yàn)平臺(tái)由包含10個(gè)節(jié)點(diǎn)的集群構(gòu)成，集群上安裝運(yùn)行Hadoop和Hive。實(shí)驗(yàn)平臺(tái)中每個(gè)物理節(jié)點(diǎn)的硬件條件是相同的：8 G內(nèi)存，4核CPU和200 GB硬盤。

實(shí)驗(yàn)數(shù)據(jù)使用某新零售大數(shù)據(jù)平臺(tái)中智能終端售貨機(jī)采集的真實(shí)商品銷量數(shù)據(jù)，包括兩張表：商品銷售記錄表all_in_one，該表中包含236 304 718條商品銷售記錄，文件大小約16 GB；預(yù)測(cè)目標(biāo)表prediction_target，該表中包含45 113 525條記錄，每條記錄代表一件預(yù)測(cè)目標(biāo)商品，文件大小約3 GB。

本文中Hive的查詢效率即單次H-SQL開始執(zhí)行至返回查詢結(jié)果的時(shí)間S(單位為s)，由兩部分組成，即S=(t1+t2)，t1為MapReduce任務(wù)執(zhí)行時(shí)間，t2為查詢結(jié)果打印時(shí)間。由于兩種存儲(chǔ)策略下實(shí)驗(yàn)的數(shù)據(jù)集和查詢命令相同，因此兩種策略下查詢結(jié)果的打印時(shí)間t2相差無(wú)幾，誤差可以忽略。因此S可以反映兩種存儲(chǔ)策略下MapReduce任務(wù)執(zhí)行時(shí)間的差異，即Hive查詢效率的差異。

5.2 對(duì)比實(shí)驗(yàn)

將數(shù)據(jù)塊優(yōu)化放置方案和HDFS默認(rèn)數(shù)據(jù)塊放置方案下的Hive查詢效率進(jìn)行對(duì)比。

兩種數(shù)據(jù)塊放置方案下，每個(gè)節(jié)點(diǎn)放置的數(shù)據(jù)塊數(shù)量如表6所示。

表6 數(shù)據(jù)塊分布情況

實(shí)驗(yàn)使用的查詢工作集Q中共5條查詢命令，Q0、Q1、Q2、Q3執(zhí)行同一類查詢?nèi)蝿?wù)：統(tǒng)計(jì)數(shù)臺(tái)售貨機(jī)在某一時(shí)間范圍內(nèi)的每日銷量，按指令順序增加目標(biāo)售貨機(jī)數(shù)量和延長(zhǎng)時(shí)間范圍，觀察Hive查詢?nèi)蝿?wù)在不同負(fù)載下查詢效率是否得到提升；Q4統(tǒng)計(jì)每一臺(tái)售貨機(jī)的每一件商品在某時(shí)間范圍內(nèi)的商品總銷量。

Q0、Q1、Q2、Q3查詢結(jié)果中分別包含2 737、110 972、1 464 528、31 792 854行數(shù)據(jù)，Q4查詢結(jié)果中包含87 975行數(shù)據(jù)。每條指令執(zhí)行20次取時(shí)間S的平均值，Q0、Q1、Q2、Q3在優(yōu)化放置方案和默認(rèn)放置方案下的效率對(duì)比如圖5所示。Q4的執(zhí)行效率如圖6所示。

圖5 Q0、Q1、Q2、Q3查詢性能對(duì)比

圖6 Q4查詢性能對(duì)比

從上述實(shí)驗(yàn)對(duì)比可知，相較于默認(rèn)的數(shù)據(jù)塊放置策略，使用基于相關(guān)關(guān)系分析的數(shù)據(jù)塊優(yōu)化放置策略存儲(chǔ)數(shù)據(jù)，Hive的查詢效率提升了約10%。

6 結(jié)束語(yǔ)

HDFS存儲(chǔ)結(jié)構(gòu)化數(shù)據(jù)時(shí)忽略了數(shù)據(jù)之間的相關(guān)關(guān)系對(duì)上層Hive查詢效率存在的不利影響，本文由此提出了一套基于相關(guān)關(guān)系分析的數(shù)據(jù)存儲(chǔ)策略。劃分?jǐn)?shù)據(jù)塊前對(duì)數(shù)據(jù)集使用范圍分區(qū)重新組織，然后根據(jù)查詢命令集分析數(shù)據(jù)塊之間的相關(guān)關(guān)系并構(gòu)建關(guān)系矩陣，最后通過(guò)數(shù)據(jù)塊優(yōu)化放置方案將數(shù)據(jù)存儲(chǔ)在HDFS集群中合適的節(jié)點(diǎn)上。通過(guò)實(shí)驗(yàn)對(duì)比可知，相較于默認(rèn)的數(shù)據(jù)塊放置策略，使用基于相關(guān)關(guān)系分析的數(shù)據(jù)塊優(yōu)化放置策略存儲(chǔ)數(shù)據(jù)，Hive的查詢效率有了一定的提升。