基于謂詞的大數(shù)據(jù)抽樣技術(shù)研究

姜 群，傅 瑜，李文生，梁瑞仕，楊 武

(1.電子科技大學(xué) 中山學(xué)院 計算機學(xué)院， 廣東 中山 528400；2.廣州華立科技職業(yè)學(xué)院 傳媒部， 廣州 511325；3.重慶理工大學(xué) 計算機科學(xué)與工程學(xué)院， 重慶 400054)

基于謂詞的大數(shù)據(jù)抽樣技術(shù)研究

姜 群1，2，3，傅 瑜1，李文生1，梁瑞仕1，楊 武3

(1.電子科技大學(xué) 中山學(xué)院 計算機學(xué)院， 廣東 中山 528400；2.廣州華立科技職業(yè)學(xué)院 傳媒部， 廣州 511325；3.重慶理工大學(xué) 計算機科學(xué)與工程學(xué)院， 重慶 400054)

為解決大數(shù)據(jù)抽樣問題，采用MapReduce產(chǎn)生內(nèi)容滿足給定謂詞的固定規(guī)模樣本，并擴展了默認的Hadoop[1]設(shè)置，使其支持作業(yè)按需動態(tài)管理其資源消耗以解決MapReduce進程中的資源浪費問題。實驗結(jié)果證明：本文所提策略的執(zhí)行性能優(yōu)于默認的Hadoop，從而證明MapReduce解決大數(shù)據(jù)抽樣問題的可行性和有效性。

抽樣；動態(tài)；謂詞

處理和分析大量數(shù)據(jù)的能力已成為決定(數(shù)據(jù)驅(qū)動的)企業(yè)成功的關(guān)鍵因素[2]。隨著存儲設(shè)備價格的逐漸下降，企業(yè)不僅對收集更多的數(shù)據(jù)感興趣，而且希望有效利用這些大數(shù)據(jù)。然而，處理這些大數(shù)據(jù)以導(dǎo)出有用信息或發(fā)現(xiàn)有用模式是一個具有挑戰(zhàn)性的任務(wù)。由于所收集的數(shù)據(jù)沒有對預(yù)建的索引提供高效的處理，也沒有事先分類排序或提供統(tǒng)計信息，因此需要研究數(shù)據(jù)的適當(dāng)劃分，構(gòu)造有用的索引，或過濾數(shù)據(jù)保持其有用的部分。但是，任何一種施加在大數(shù)據(jù)上的分析或處理技術(shù)都可能是非常昂貴的[3]。

抽樣是減少輸入數(shù)據(jù)規(guī)模、避免在任何隨后處理過程中產(chǎn)生巨大費用的有效工具[4]。本研究以給定謂詞作為入選標(biāo)準(zhǔn)抽樣大數(shù)據(jù)的方法，該方法抽樣基本上等同于抽樣關(guān)系型選擇操作的結(jié)果[4]，它可表示為SQL查詢[5]如下：

SELECT 屬性 FROM 數(shù)據(jù)集

WHERE 條件值 LIMITk

以上條件值表示給定的謂詞集，k為所需的樣本大小。

1 使用MapReduce實現(xiàn)基于謂詞的采樣

應(yīng)用MapReduce實現(xiàn)基于謂詞的抽樣方法：把輸入數(shù)據(jù)集分區(qū)，在每個分區(qū)中并行搜索滿足謂詞條件的候選記錄。將不同分區(qū)中搜索到的候選記錄集中起來做進一步加工處理，以產(chǎn)生所需規(guī)模的隨機樣本。具體算法如下：

基于謂詞抽樣算法1：Map

k <= required size for the sample

foundRecords <= 0

kdummy <= dummy key

for all (key,value) pairs (ki; vi) in input do

if foundRecords < k then

if value satisfies the predicate then

foundRecords++

output (kdummy; vi) pair

end if

end if

end for

基于謂詞抽樣算法2：Reduce

k <= required size for the sample

{注：由于Map階段使用單個鍵kdummy,則Reduce任務(wù)接收單個[kdummy, list(value)]值對。}

sampledRecords <= list(value)

if sampledRecords.size() <= k then

output sampledRecords

else

Output the first k (kdummy,value) pairs from sampledRecords

end if

在Map階段每個Map輸出使用一個虛擬鍵kdummy，Map函數(shù)計算每個輸入端(key，value)對的value部分的謂詞，如果謂詞計算結(jié)果為true，Map任務(wù)輸出(kdummy，value)對。Map階段需要輸出k對值，k為所需樣本的規(guī)模。由于每個輸入分區(qū)被獨立處理，不是任何一個Map任務(wù)都能輸出任何期望的結(jié)果，因而每個Map任務(wù)嘗試輸出最多k對值。由于所有的Map輸出共享同一個鍵(kdummy)，Reduce任務(wù)接收一個鍵和含有滿足謂詞值的列表，該列表可能包含0到N×k個值，N是Map任務(wù)的數(shù)量。如果列表大小超過k，則Reduce任務(wù)從列表中選擇第一組k個值。每個被選值與虛擬鍵配成對，并形成最終結(jié)果的一部分。顯然，該算法能夠產(chǎn)生所需的樣本，但它的響應(yīng)時間和資源利用率較低，因為默認的Hadoop要求對所有輸入分區(qū)進行處理，沒有機會部分地處理輸入數(shù)據(jù)來收集所需數(shù)目的匹配記錄。作業(yè)的完成時間在很大程度上由Map階段消耗的時間決定，它與Map功能應(yīng)用到每個輸入分區(qū)所需要的時間一樣多。因此，默認的Hadoop策略的響應(yīng)時間隨輸入數(shù)據(jù)規(guī)模的增加而增加。

2 提高效率降低響應(yīng)時間

鑒于默認Hadoop執(zhí)行模型的局限性，即MapReduce的響應(yīng)時間和資源利用率較低，本文提出一種機制，能從不斷增加的大量數(shù)據(jù)中抽取所需的樣本而使用最少的資源，使抽樣任務(wù)能與其他任務(wù)同時使用一個共享集群上的運行數(shù)據(jù)。

2.1 增量式處理機制

默認的Hadoop執(zhí)行模型假設(shè)每個任務(wù)都需要處理它整個的輸入以產(chǎn)生所需結(jié)果。當(dāng)這種假設(shè)不為真時，其結(jié)果是一個低效的執(zhí)行從而導(dǎo)致資源浪費。默認的Hadoop對任務(wù)語義的理解有限，因而當(dāng)任務(wù)增大時，該任務(wù)如何消耗它的輸入應(yīng)由任務(wù)自己決定而不是由Hadoop。因此，任務(wù)需要動態(tài)控制其數(shù)據(jù)的攝入量，即動態(tài)任務(wù)。

本文把輸入提供器(input provider)的概念引入默認的Hadoop執(zhí)行模型中，一個輸入提供器包含了任務(wù)動態(tài)決策攝入量的邏輯。Hadoop的輸入是一個DFS輸入分區(qū)，動態(tài)任務(wù)開始執(zhí)行一個小任務(wù)，即僅處理輸入分區(qū)的一個子集。初始的輸入分區(qū)和所有隨后的增量(如果需要的話)都由輸入提供器決定。隨著Map階段的進行，執(zhí)行框架在規(guī)定的時間間隔調(diào)用輸入提供器，并把已完成的Mapper產(chǎn)生的輸出、作業(yè)狀態(tài)、當(dāng)前的負載和集群中Map插槽可用性等統(tǒng)計信息提供給它，輸入提供器對收到的信息按以下3種情形作出回應(yīng)：

1) 輸入提供器發(fā)現(xiàn)該任務(wù)不需要處理額外的輸入,它將返回“輸入結(jié)束”消息，表明作業(yè)不需要消耗額外的輸入分區(qū)，允許完成當(dāng)前正在進行的Map任務(wù)，輸入提供器不再調(diào)用，作業(yè)然后進入到shuffle階段。此后，該作業(yè)的行為就像任何其他作業(yè)一樣。

2) 輸入提供器意識到需處理額外的輸入，它返回“輸入可用”消息，提供Hadoop下一個要處理的其他分區(qū)列表。

3) 輸入提供器可能會決定“觀望”。在這種情況下，將推遲增加輸入，等到下一次調(diào)用重新評估作業(yè)的進展情況，輸入提供器返回“無輸入可用”消息。

Map任務(wù)動態(tài)作業(yè)的最終數(shù)目要等到輸入提供器返回“輸入結(jié)束”消息才能確定，待所有預(yù)定map已經(jīng)完成，Reduce階段才開始處理一個給定的中間鍵所有中間值。由于輸入提供器可能會增加額外的輸入，對于一個動態(tài)作業(yè)，該要求是必要的但不充分。當(dāng)輸入提供器已經(jīng)返回“輸入結(jié)束”的響應(yīng)，執(zhí)行框架才開始Reduce階段。為獲得需要的結(jié)果，動態(tài)作業(yè)的輸入供應(yīng)器嘗試最小化作業(yè)處理的輸入數(shù)量，它給作業(yè)一個探索由隱蔽特性所引起的任何優(yōu)化機會。更重要的是，執(zhí)行時間特性不再僅僅是一個輸入數(shù)據(jù)規(guī)模的函數(shù)，而取決于被處理數(shù)據(jù)的特征。這種執(zhí)行模型允許一個作業(yè)在資源有限的環(huán)境中作用于更大的數(shù)據(jù)集，其結(jié)構(gòu)如圖1所示。

圖1 輸入的增量處理結(jié)構(gòu)

2.2 相應(yīng)策略

前面引入了輸入提供器機制，它允許一個作業(yè)以增量方式消耗輸入。作業(yè)可以多種方式使用這種機制，每個都具有不同的執(zhí)行行為和在集群上的通過量。為了控制輸入數(shù)據(jù)的攝入量，決策需要考慮集群的能力、可接受的響應(yīng)時間，以及使用資源方面可接受的成本。為了有最大的靈活性使作業(yè)按自身的需求使用系統(tǒng)，本文制定了一套管理動態(tài)決策策略，它由以下3個參數(shù)定義：

評估間隔：一個動態(tài)作業(yè)配置了評估作業(yè)進展情況，以及是否需要添加任何額外輸入的輸入提供器，而評估間隔定義了每次評估之間的時間間隔。

工作閾值：工作閾值設(shè)置一個在連續(xù)的評估之間作業(yè)完成額外工作的下界。工作完成由處理分區(qū)數(shù)來衡量，閾值表示為其作業(yè)的輸入總數(shù)的百分比。

搶抓限制：搶抓限制設(shè)置了新輸入分區(qū)的上限。由于每個分區(qū)需要一個空映射插槽，搶抓限制通過改變參數(shù)限制了額外的需求“搶”作業(yè)下一步的映射插槽，本文使用的4個一組的策略見表1，它們之間添加增量的方式各不相同。

表1 增量式輸入處理策略

3 實驗

本文使用MapReduce和輸入提供器來生產(chǎn)基于謂詞的資源有效逐步攝入Hadoop的抽樣，作業(yè)設(shè)置為動態(tài)執(zhí)行，由一個相關(guān)的輸入提供器控制其輸入的攝入量。Hadoop提供了一個概念JobConf作為描述Hadoop作業(yè)的主接口。JobConf對象由一組配置參數(shù)組成。本文擴展了參數(shù)見表2，使其支持動態(tài)作業(yè)。

實驗是在10個節(jié)點的IBM x3650集群上進行的，每個節(jié)點有一個英特爾2.26 GHz的處理器(4核)，12 GB內(nèi)存和4個300 GB硬盤。因此，測試集群包括共40核和40磁盤。本文使用Hadoop-0.20.2版本，并對其進行修改使其支持動態(tài)作業(yè)。在客戶端，本文使用Hive-0.5.0修改編譯器使其在JobConf中設(shè)置所需參數(shù)。實驗數(shù)據(jù)集來自TPC-H[6]數(shù)據(jù)集LINEITEM表。表中每行捕獲銷售一個產(chǎn)品項的屬性，如數(shù)量、價格、折扣、稅等。為了評價本文的方法對不同數(shù)據(jù)規(guī)模的效果，本文以5、10、20、40和100的比例生成LINEITEM數(shù)據(jù)。

表2 擴展參數(shù)列

表3 生成數(shù)據(jù)集

負載的平衡分配所需的輸入數(shù)據(jù)無重復(fù)地均勻分布在40個磁盤上，由于輸入跨多個磁盤分區(qū)，每個分區(qū)可以包含不同數(shù)量的記錄，以匹配給定的Hive查詢謂詞(多個)。實驗分為2部分：第1部分研究單用戶設(shè)置下每個策略對不同大小數(shù)據(jù)集的響應(yīng)時間；第2部分研究均勻多用戶設(shè)置下執(zhí)行性能比較。為了生成工作負載，本文使用了一個作業(yè)負載生成器[7]，它允許對一組使用Hive并行工作的終端用戶進行建模。

實驗使用固定樣本規(guī)模10 000，Hive查詢每個作業(yè)的模板：

SELECT ORDERKEY，PARTKEY，SUPPKEY

FROM LINEITEM

WHERE謂詞LIMIT 10000

本文使用表4中列出的謂詞。

表4 謂詞

評價集群上各種策略在沒有其他并發(fā)作業(yè)情況下的執(zhí)行性能，集群上的每個節(jié)點配置成支持4個并發(fā)Map任務(wù)。由于沒有其他作業(yè)競爭Map插槽，Hadoop的作業(yè)可以并行執(zhí)行共40個Map任務(wù)。圖2提供每項策略對不同數(shù)據(jù)集的響應(yīng)時間之間的比較。

圖2 單用戶設(shè)置下每個策略對不同大小數(shù)據(jù)集的響應(yīng)時間(s)

在多用戶負荷設(shè)置中，集群能力設(shè)置為每個節(jié)點有16個Map插槽。本文模擬10個并發(fā)的一組用戶，其中每個用戶提交查詢，并等待它在提交另一個查詢之前完成。本文評估了每個策略下集群的總吞吐量，同時還監(jiān)測了CPU利用率(%)和磁盤在30 s時間間隔讀取(KBS/s)集群上的每個節(jié)點，其結(jié)果如圖3所示。 圖3為多用戶設(shè)置下執(zhí)行性能比較，其中：(a)為每個策略的吞吐量(作業(yè)/h)；(b)和(c)分別為資源使用率(%CPU利用率和磁盤讀取(KBS/s))。

4 結(jié)束語

本文采用Map-Reduce實現(xiàn)基于謂詞的大數(shù)據(jù)抽樣。由于默認的Hadoop執(zhí)行模型假設(shè)需要處理所有輸入數(shù)據(jù)，它的響應(yīng)時間和資源利用依賴于輸入的總體規(guī)模，所以抽樣在Hadoop上執(zhí)行效率低。本文改進了Hadoop執(zhí)行模型，使其支持增量式處理輸入，這有助于作業(yè)按照集群中資源的可用性適應(yīng)其生長。為提高使用增量處理機制的靈活性，本文制定了一套用于管理作業(yè)的發(fā)展和其輸入的動態(tài)攝入量決定策略。在沒有并行作業(yè)的空閑簇上實驗表明：保守策略C不能充分利用它的能力，導(dǎo)致較長的響應(yīng)時間；而在多用戶設(shè)置中，保守策略消耗最少的資源，產(chǎn)生最高吞吐量。策略LA在單用戶和多用戶設(shè)置中的總體效果較好。在所有情況下，默認的Hadoop策略導(dǎo)致使用最多的資源而吞吐量最少。實驗結(jié)果證明了MapReduce解決大數(shù)據(jù)抽樣問題的可行性和有效性。

圖3 多用戶設(shè)置下執(zhí)行性能比較

[1] 覃雄派,王會舉,杜小勇,等.大數(shù)據(jù)分析——RDBMS與MapReduce 的競爭與共生[J].軟件學(xué)報,2012,23(1):32-45.

[2] 李德毅.大數(shù)據(jù)認知——“2015 大數(shù)據(jù)價值實現(xiàn)之路高峰論壇” 主題報告[J].重慶理工大學(xué)學(xué)報(自然科學(xué)),2015,29(9):1-6.

[3] 王勇,王李福,饒勤菲,等.半徑自適應(yīng)的初始中心點選擇 K-medoids 聚類算法[J].重慶理工大學(xué)學(xué)報(自然科學(xué)),2017,31(2):95-101.

[4] OLKEN F,ROTEM D.Random sampling from databases:a survey[J].Statistics and Computing,1995,5(1):25-42.

[5] 李寶蓮，路瑜亮.基于SQLServer應(yīng)用的大數(shù)據(jù)量實時處理[J].無線電工程,2007,37(3):56-58.

[6] COUNCIL T P P.TPC-H benchmark specification[EB/OL].[2008-10-10].Published at http://www.tcp.org/hspec.html.

[7] AYYALASOMAYAJULA V.HERDER:A Heterogeneous Engine for Running Data Intensive Experiments and Reports.M.S Thesis[M].California:University of California-Irvine,2011.

(責(zé)任編輯 劉 舸)

Research on Predicate-Based Sampling Technology of Big Data

JIANG Qun1,2,3， FU Yu1， LI Wensheng1， LIANG Ruishi1, YANG Wu3

(1.College of Computer Science, Zhongshan Institute，University of Electronic Science and Technology of China, Zhongshan 523960, China； 2.Media Department, Guangzhou Huali Science and Technology Vocational College, Guangzhou 511325, China；3.College of Computer Science and Engineering, Chongqing University of Technology，Chongqing 400054, China)

To solve big data sampling problem, this paper uses MapReduce to sample big data and produce a sample whose content satisfy a given predicate. Since the default Hadoop execution depends on the size of the input and is wasteful of cluster resources. The paper has extended the default Hadoop to support job-demand dynamic management of its resource consumption on cluster. Experiments results show that the implementation of the proposed policy performance is better than the default Hadoop policy. Therefore, it was proved that sampling big by using MapReduce is feasible and effective.

sample; dynamic; predicate

2017-01-18 基金項目：國家自然科學(xué)基金青年科學(xué)基金資助項目(61300095)；留學(xué)人員科技活動擇優(yōu)資助項目“商業(yè)智能應(yīng)用軟件研究與開發(fā)”(2009CR02)

姜群(1959—)，女，重慶人,雙碩士，副教授，主要從事大數(shù)據(jù)處理、智能計算研究，E-mail:gingerqun@hotmail.com；梁瑞仕(1979—),男，重慶人，博士，副教授，主要從事云計算、大數(shù)據(jù)研究。

姜群，傅瑜，李文生，等.基于謂詞的大數(shù)據(jù)抽樣技術(shù)研究[J].重慶理工大學(xué)學(xué)報(自然科學(xué))，2017(8):120-124.

format：JIANG Qun，F(xiàn)U Yu，LI Wensheng,et al.Research on Predicate-Based Sampling Technology of Big Data[J].Journal of Chongqing University of Technology(Natural Science)，2017(8):120-124.

10.3969/j.issn.1674-8425(z).2017.08.020

TP392

A

1674-8425(2017)08-0120-05