差別依賴(lài)驗(yàn)證的分布式算法

覃 昇 談子敬 肖永松

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 200433)

0 引 言

數(shù)據(jù)質(zhì)量問(wèn)題在大數(shù)據(jù)時(shí)代變得更為突出。無(wú)論系統(tǒng)能夠以多么快的速度處理多么大的數(shù)據(jù)量，如果數(shù)據(jù)質(zhì)量得不到保證，一切得到的分析結(jié)果可能都是無(wú)意義的。在對(duì)數(shù)據(jù)質(zhì)量進(jìn)行評(píng)估的多個(gè)維度中，數(shù)據(jù)一致性是一個(gè)常見(jiàn)的指標(biāo)。數(shù)據(jù)一致性通?；谟眠壿嫳磉_(dá)式的形式所給出的數(shù)據(jù)依賴(lài)來(lái)進(jìn)行描述。簡(jiǎn)而言之，若數(shù)據(jù)不滿(mǎn)足給定的數(shù)據(jù)依賴(lài)，則稱(chēng)該數(shù)據(jù)為不一致，這通常意味著數(shù)據(jù)中存在錯(cuò)誤或誤差。

因?yàn)閿?shù)據(jù)依賴(lài)的重要性，有大量的研究針對(duì)各種數(shù)據(jù)依賴(lài)展開(kāi)。常見(jiàn)的數(shù)據(jù)依賴(lài)多數(shù)強(qiáng)調(diào)的是數(shù)據(jù)間的相等關(guān)系，例如函數(shù)依賴(lài)、條件函數(shù)依賴(lài)[1]等。在現(xiàn)實(shí)中，相關(guān)數(shù)據(jù)之間可能存在一定差異，而并非嚴(yán)格完全相等，也可能需要在依賴(lài)定義中引入大于、小于等序列關(guān)系。差別依賴(lài)[2]是一個(gè)表達(dá)能力較強(qiáng)的數(shù)據(jù)依賴(lài)定義形式，它滿(mǎn)足了以上這些需求。常見(jiàn)的函數(shù)依賴(lài)是差別依賴(lài)的一個(gè)特例。

在數(shù)據(jù)一致性的相關(guān)工作中，數(shù)據(jù)集上的數(shù)據(jù)依賴(lài)驗(yàn)證是一個(gè)基礎(chǔ)且重要的步驟：其目標(biāo)是在數(shù)據(jù)集中找到不滿(mǎn)足數(shù)據(jù)依賴(lài)的部分?jǐn)?shù)據(jù)，以對(duì)其進(jìn)行進(jìn)一步的分析和修復(fù)。隨著數(shù)據(jù)量的變大，數(shù)據(jù)依賴(lài)驗(yàn)證所需的內(nèi)存和對(duì)處理器的要求越來(lái)越高，單機(jī)無(wú)法實(shí)現(xiàn)。這需要引入分布式計(jì)算技術(shù)，將問(wèn)題并行處理。和單機(jī)算法不同，分布式算法需將整個(gè)問(wèn)題分成若干個(gè)可并行的子問(wèn)題，每個(gè)子問(wèn)題由一臺(tái)計(jì)算機(jī)作為一個(gè)節(jié)點(diǎn)(reducer)進(jìn)行并行處理，最終整合結(jié)果。和設(shè)計(jì)單機(jī)算法只注重時(shí)間空間消耗不同，設(shè)計(jì)一個(gè)分布式算法需要考慮的主要因素，包括如何將問(wèn)題盡可能平均地并行化分解；如何在保證正確的情況下減少并發(fā)運(yùn)行時(shí)間，同時(shí)減少分發(fā)和收集過(guò)程中的數(shù)據(jù)量等。

本文研究的問(wèn)題是：基于大規(guī)模分布式計(jì)算平臺(tái)，在數(shù)據(jù)集上進(jìn)行分布式差別依賴(lài)的驗(yàn)證。算法將基于差別依賴(lài)的特征，對(duì)部分情況進(jìn)行優(yōu)化，以提出更優(yōu)的算法。

1 背景知識(shí)

1.1 差別依賴(lài)

首先回顧一下差別依賴(lài)的具體定義[2]。

對(duì)于關(guān)系數(shù)據(jù)表R中的一個(gè)屬性B，在其值域dom(B)上定義一個(gè)二元差別dB(a,b)(a,b∈dom(B))。這個(gè)二元差別滿(mǎn)足：(1) 非負(fù)性：dB(a,b)≥0，dB(a,b)=0當(dāng)且僅當(dāng)a=b；(2) 對(duì)稱(chēng)性：dB(a,b)=dB(b,a)。例如，實(shí)數(shù)域上的絕對(duì)值運(yùn)算dB(a,b)=|a-b|是一個(gè)符合上述要求的二元差別，字符串的最小編輯距離也同樣屬于二元差別。

對(duì)于多屬性上的差別函數(shù)φ[Z]，其中Z為若干個(gè)屬性組成的集合。則有：

(1)

定義2一個(gè)數(shù)據(jù)表R的差別依賴(lài)DD，其形式為:

DD:φ1(X)→φ2(Y)

(2)

其中：X、Y是R中屬性集的子集，φ1(X)和φ2(Y)是兩個(gè)不同的差別函數(shù)。

對(duì)一個(gè)信用卡交易的數(shù)據(jù)庫(kù)，可以有如下差別依賴(lài)：

DD1[cardno(= 0)]∩[position(≥60)]→[transtime(≥20)]

其含義為：當(dāng)兩筆交易的卡號(hào)(cardno)相同，并且發(fā)生地點(diǎn)(position)相距不小于60時(shí)，則這兩筆交易的時(shí)間(transtime)一定不小于20。

對(duì)于一個(gè)產(chǎn)品價(jià)格記錄的數(shù)據(jù)庫(kù)，可能有如下約束：當(dāng)兩條記錄的日期(date)相距在7～30天時(shí)，則價(jià)格之差將在100～900的范圍內(nèi)，其表達(dá)式為：

DD2[date(>7,≤30)]→[price(≥100,≤900)]

可以看到，差別依賴(lài)是一個(gè)具有較強(qiáng)表達(dá)能力的依賴(lài)類(lèi)型，并且函數(shù)依賴(lài)是它的一個(gè)特例。由差別依賴(lài)的定義可知，差別依賴(lài)的約束驗(yàn)證，需要對(duì)數(shù)據(jù)集中的任意元組對(duì)進(jìn)行比較。該算法的復(fù)雜度是元組個(gè)數(shù)的平方。當(dāng)數(shù)據(jù)集具有較大規(guī)模時(shí)，單機(jī)的內(nèi)存和時(shí)間將無(wú)法承受該負(fù)荷，所以使用分布式系統(tǒng)進(jìn)行差別依賴(lài)的驗(yàn)證。

1.2 分布式系統(tǒng)及算法

在MapReduce[3]和Spark系統(tǒng)中，一個(gè)分布式系統(tǒng)由若干無(wú)共享存儲(chǔ)空間的計(jì)算機(jī)構(gòu)成，每一臺(tái)計(jì)算機(jī)被視作一個(gè)節(jié)點(diǎn)(reducer)，所有節(jié)點(diǎn)之間的交互通過(guò)網(wǎng)絡(luò)中的發(fā)送和收集信息來(lái)實(shí)現(xiàn)。一個(gè)分布式算法由若干輪映射歸約(MapReduce)操作組成，每一輪操作分為映射(Map)、轉(zhuǎn)移(Shuffle)和歸約(Reduce)三部分。其中：Map為數(shù)據(jù)傳輸做準(zhǔn)備，產(chǎn)生包含數(shù)據(jù)內(nèi)容的鍵值對(duì)(Key-Value)；Shuffle根據(jù)數(shù)據(jù)的鍵值進(jìn)行實(shí)際的數(shù)據(jù)傳輸，使得所有鍵值相同的數(shù)據(jù)被歸約到同一個(gè)節(jié)點(diǎn)；當(dāng)每一個(gè)reducer將具有相同鍵值的數(shù)據(jù)收集之后，便繼續(xù)完成Reduce中之后的步驟，可能進(jìn)行統(tǒng)計(jì)或輸出，也可能開(kāi)始下一輪的MapReduce操作。三個(gè)操作之中，以Map和Reduce為算法核心。

1.3 分布式驗(yàn)證相關(guān)工作

文獻(xiàn)[4]中主要討論了當(dāng)數(shù)據(jù)表以水平分割或垂直分割的形式存儲(chǔ)時(shí)，如何進(jìn)行條件函數(shù)依賴(lài)的檢驗(yàn)，使得數(shù)據(jù)傳輸量或并發(fā)運(yùn)行時(shí)間最小。文獻(xiàn)[5]中提出了一種基于等價(jià)類(lèi)的分布式環(huán)境多函數(shù)依賴(lài)沖突檢測(cè)的方法，給出了沖突檢測(cè)的響應(yīng)時(shí)間代價(jià)模型，并且將問(wèn)題化為整數(shù)規(guī)劃問(wèn)題，給出近似解。文獻(xiàn)[6]中提出了一種分布式環(huán)境多函數(shù)依賴(lài)不一致性檢測(cè)方法，依靠最小集合覆蓋的理論，通過(guò)一次數(shù)據(jù)遍歷，對(duì)多個(gè)函數(shù)依賴(lài)進(jìn)行并行檢測(cè)。文獻(xiàn)[7]中將數(shù)據(jù)依賴(lài)的檢測(cè)和數(shù)據(jù)清洗化歸為一系列的原子操作，并針對(duì)多操作提出了并行或合并的改進(jìn)。

本文研究的是差別依賴(lài)在分布式環(huán)境下的驗(yàn)證。如前所述，差別依賴(lài)不僅包括函數(shù)依賴(lài)，還包括一系列建立在不相等或相近的數(shù)據(jù)上的依賴(lài)條件。本文的算法設(shè)計(jì)考慮了差別依賴(lài)的定義形式，同時(shí)針對(duì)部分的數(shù)據(jù)分布特征，進(jìn)一步給出優(yōu)化策略。

2 三角分布算法

差別依賴(lài)的驗(yàn)證基于表中元組的兩兩比較、直觀理解，這和數(shù)據(jù)庫(kù)中一個(gè)表上的自連接(join)運(yùn)算有相似之處。在分布式的設(shè)定下，為了實(shí)現(xiàn)元組的兩兩比較，并且保證不重復(fù)、不遺漏以及時(shí)間上的可接受，需要一定的運(yùn)算技巧。文獻(xiàn)[8]針對(duì)大數(shù)據(jù)下元組的查重問(wèn)題，使用了一種三角形分布的算法。算法的本質(zhì)是模仿向量的叉乘，同時(shí)根據(jù)運(yùn)算的對(duì)稱(chēng)性，刪去其中約一半的運(yùn)算。從結(jié)果上看，三角分布算法是將reducer排列成一個(gè)三角形，元組根據(jù)一定要求，通過(guò)MapReduce算法，分發(fā)到對(duì)應(yīng)的reducer中。該算法不僅保證了正確性和比較次數(shù)的最優(yōu)化，同時(shí)也保證了每一臺(tái)機(jī)器的時(shí)間復(fù)雜度都相同。

以文獻(xiàn)[8]中的方法為基礎(chǔ)，本文給出一個(gè)適用于差別依賴(lài)檢測(cè)的隨機(jī)三角發(fā)表算法。

2.1 隨機(jī)三角算法

當(dāng)reducer數(shù)目給定時(shí)，比如為m，取最大的正整數(shù)l，使得l(l+1)/2≤m成立，此時(shí)l為三角分布的邊長(zhǎng)。圖1為m=21、l=6的情況，其中每一個(gè)小方塊表示一個(gè)reducer，左上角的數(shù)字為其編號(hào)。按照?qǐng)D1對(duì)每行每列進(jìn)行編號(hào)，每一臺(tái)reducer可以由一個(gè)整數(shù)對(duì)來(lái)表示。例如編號(hào)為9的reducer同樣可以表示為(4，2)。

圖1 三角分布節(jié)點(diǎn)示意圖

利用三角分布策略，可以有效實(shí)現(xiàn)元組的成對(duì)比較，其具體算法見(jiàn)算法1。

算法1隨機(jī)三角分布算法

輸入：數(shù)據(jù)表的元組t；

三角分布邊長(zhǎng)l；

差別依賴(lài)DD。

輸出：違背DD的所有元組對(duì)。

1: class MAPPER

2: method MAP(Tuple t)

3: Iht a ← a random value from [1,l]

4: for all p∈[1,a) do

5: EMIT(Reducer(p,a),(L,Tuple t))

6: EMIT(Reducer(a,a),(S,Tuple t))

7: for all q∈(a,I] do

8: EMIT(Reducer(a,q),(R,TupIe t))

9: class Partitioner

10: method PARTITION(Key rid,Pair(c,t))

11: Return rid

12: class REDUCER

13: method REDUCE(Key rid,Pairs[(c1,t1),(c2,t2)…])

14: Left,Right,Self ← ?

15: for all Pair (c,t)∈Pairs[(c1,t1),(c2,t2)…〗

16: if (c=L) then Left ← Left+t

17: else if (c=R) then Right ← Right+t

18: else if (c=S) then Self ← Self+t

19: if Self ≠ ? then

20: for all t1∈Self do

21: for aIl t2∈Self do

22: check t1and t2

23: else

24: for all t1∈Left do

25: for all t2∈Right do

26 : check t1and t2

27: Return Pairs(t1,t2) violating the DD

整個(gè)算法建立在分布式結(jié)構(gòu)中，共有一次MapReduce操作，包含Map、Shuffle和Reduce三個(gè)階段。

在Map階段(第1-8行)，對(duì)每一個(gè)元組，選取一個(gè)1到l的隨機(jī)數(shù)a(第3行)，將元組發(fā)射到第a行和第a列的所有reducer中(第4-8行)。發(fā)射的過(guò)程中，需要進(jìn)行標(biāo)記，例如一個(gè)元組的隨機(jī)數(shù)為4，則在發(fā)送到第4列的4、9、13號(hào)機(jī)器上時(shí)，標(biāo)記為L(zhǎng)；發(fā)送到對(duì)角線上的16號(hào)機(jī)器上時(shí)，標(biāo)記為S；發(fā)送到第4行的17、18號(hào)機(jī)器上時(shí)，標(biāo)記為R。

在Shuffle階段(第9-11行)，數(shù)據(jù)根據(jù)機(jī)器序號(hào)進(jìn)行分組。

在Reduce階段(第12-27行)，每一臺(tái)非對(duì)角線上的機(jī)器，接收到標(biāo)記為L(zhǎng)和R的兩類(lèi)數(shù)據(jù)(第16-17行)，雙重循環(huán)比較L和R集合之間的元組對(duì)(第23-26行)，是否符合需要驗(yàn)證的差別依賴(lài)；而在對(duì)角線上的機(jī)器，則只會(huì)收到標(biāo)記為S的數(shù)據(jù)(第18行)，收集之后對(duì)其內(nèi)部的所有元組對(duì)進(jìn)行兩兩比較(第19-22行)。全部比較結(jié)束之后，返回違背DD的元組對(duì)(第27行)。

2.2 算法正確性和時(shí)間復(fù)雜度

算法的正確性等價(jià)于任意兩條元組都必須進(jìn)行過(guò)比較。對(duì)于任意兩條元組，設(shè)它們?cè)诘?行得到的隨機(jī)數(shù)為i和j，由于差別依賴(lài)具有對(duì)稱(chēng)性，設(shè)i≤j。若i=j時(shí)，元組會(huì)在機(jī)器(i,i)上進(jìn)行比較；若i

從時(shí)間上看，算法的整體耗時(shí)主要集中在Reduce階段的數(shù)據(jù)比較上。設(shè)元組總數(shù)為n，則取到相同隨機(jī)數(shù)的元組個(gè)數(shù)平均值為n/l。

對(duì)于非對(duì)角線上的機(jī)器，其L和R集合中的元素?cái)?shù)量均為n/l，所以總比較次數(shù)為n2/l2；

對(duì)于對(duì)角線上的機(jī)器，其S集合中元素?cái)?shù)量為n/l，所以總比較次數(shù)為n2/l2；考慮到差別依賴(lài)的對(duì)稱(chēng)性，(t1,t2)和(t2,t1)的比較完全一致，所以總比較次數(shù)可以減少至n2/2t2。

綜上，三角分布策略時(shí)間復(fù)雜度為O(n2/l2)，并且每一臺(tái)機(jī)器上的時(shí)間平均復(fù)雜度相同。

2.3 排序三角算法

對(duì)于一部分?jǐn)?shù)據(jù)集，其在某些屬性上的值的上下界是已知的，并且分布大致均勻。若能通過(guò)這些已有的信息，在Map過(guò)程中就進(jìn)行初篩，則可以減少部分運(yùn)算時(shí)間?；谶@樣的想法，可以對(duì)部分?jǐn)?shù)據(jù)集上的差別依賴(lài)的檢驗(yàn)，使用如下的排序三角算法。

考慮一條左側(cè)含有[A(θp)]的差別依賴(lài)，其中A是屬性，θ是判斷運(yùn)算符(θ∈{≥,>,=,<,≤)，p是常數(shù)。同時(shí)A屬性的值存在上下界，大致地均勻分布在區(qū)間[smin,smax]中。令:

(3)

t表示單位區(qū)間長(zhǎng)度，則整個(gè)[smin,smax)區(qū)間可以被分成l個(gè)長(zhǎng)度為t的單位區(qū)間。在算法1中，a為1到l中的隨機(jī)數(shù)(算法1第3行)，而在排序三角算法中，a的取值為:

(4)

式中：t[A]為該元組在A屬性上的取值，則a∈[1,l]，并且所有元組被有序分散到reducer中。令k=p/t，則可以根據(jù)k的值免去部分reducer上的元組比較。

如圖2所示，取k=1，l=4。記difi為在編號(hào)為i的reducer中，需要比較的兩個(gè)元組的屬性A上值的差的范圍。例如dif7=(p,3p)，因?yàn)樵谶@個(gè)reducer中需要比較的兩個(gè)元組的A屬性的值分別屬于[3p,4p)和[p,2p)，所以?xún)蓚€(gè)數(shù)據(jù)之差的范圍為(p,3p)。

圖2 節(jié)點(diǎn)數(shù)據(jù)示意圖

圖3顯示了在圖2條件下各reducer中可能進(jìn)行的運(yùn)算，顯然針對(duì)特定的θ,并非所有reducer都有工作。記numθ為θ取不同運(yùn)算符時(shí)所需要的reducer數(shù)量，在忽略少量的邊界情況和暫定k為整數(shù)時(shí)，計(jì)算可得：

num≤=num<=(l+l-k)(k+1)/2

(5)

num==l-k

(6)

num≥=num>=(l-k)(l-k+1)/2

(7)

圖3 各節(jié)點(diǎn)和運(yùn)算符的對(duì)應(yīng)關(guān)系

當(dāng)初始條件都給定時(shí)，可以計(jì)算出對(duì)應(yīng)的numθ，所以只需要這些數(shù)量的reducer工作就可以完成所有的比較，剩下的reducer無(wú)需運(yùn)行。所以可以在map階段，直接減少數(shù)據(jù)的發(fā)射量，數(shù)據(jù)發(fā)射(emit)時(shí)，若目標(biāo)reducer不需要進(jìn)行運(yùn)算，則可以跳過(guò)這個(gè)當(dāng)前的發(fā)射步驟，減少Shuffle階段的數(shù)據(jù)運(yùn)輸量。

另一方面，既然可以減少需要使用的reducer，那自然也可以用這些reducer來(lái)加速整個(gè)過(guò)程。

在已知reducer數(shù)目情況下(數(shù)目為m)，可以令邊長(zhǎng)l′為變量，根據(jù)之前k和numθ的定義式，解出滿(mǎn)足numθ≤m的最大l′值，顯然有l(wèi)′≥l。當(dāng)三角分布邊長(zhǎng)從l變大到l′以后，由于每一臺(tái)機(jī)器分配到的運(yùn)算量的復(fù)雜度相同，而總運(yùn)算量不變，所以每一臺(tái)使用到的機(jī)器上分到的運(yùn)算量會(huì)相應(yīng)變少，總時(shí)間減少。

如果k=p/t不為整數(shù)，則需要在上述numθ的基礎(chǔ)上進(jìn)行一定的增加。從圖2中可以看出，若k=1.5，θ取<，則編號(hào)為3和7的reducer同樣需要進(jìn)行運(yùn)算，num<會(huì)增大。在這個(gè)情況下，在一部分的行上需要額外增加一個(gè)reducer，所以每個(gè)numθ都會(huì)增加，增加的數(shù)目上界為l。在這些額外加入的reducer中，并不是所有的元組對(duì)都符合[A(θp)]，所以還需要進(jìn)行檢驗(yàn)。

3 實(shí)驗(yàn)分析

實(shí)驗(yàn)使用的分布式環(huán)境是Spark 2.0.0，主要的啟動(dòng)參數(shù)見(jiàn)表1。

表1 Spark啟動(dòng)參數(shù)表

實(shí)驗(yàn)所使用的測(cè)試數(shù)據(jù)集有兩個(gè)，均為人為構(gòu)造的大數(shù)據(jù)集。兩個(gè)數(shù)據(jù)集均含有屬性A，該屬性的值域?yàn)閇0,100)，不同點(diǎn)在于，數(shù)據(jù)集Data1在屬性A上的值為均勻分布，數(shù)據(jù)集Data2在屬性A上的值呈正態(tài)分布，平均值為50，方差為20，即在[30,70]范圍內(nèi)包含了總數(shù)據(jù)的約70%。

在實(shí)驗(yàn)1和實(shí)驗(yàn)2中，只使用Data1作為測(cè)試數(shù)據(jù)測(cè)試三角算法的性能，而在實(shí)驗(yàn)3中，使用Data1和Data2作為測(cè)試數(shù)據(jù)，比較隨機(jī)三角算法和排序三角算法的優(yōu)缺點(diǎn)。

實(shí)驗(yàn)所使用的差別依賴(lài)DD，其左側(cè)共有兩個(gè)差別函數(shù)，其中包含有差別函數(shù)φ(A)=[A(θ,30)]。在實(shí)驗(yàn)1和2中，指定θ為<，在實(shí)驗(yàn)3中，將取θ分別為<、=和>，進(jìn)行兩種三角分布的性能比較。

3.1 時(shí)間比較

目前在分布式平臺(tái)上，用來(lái)處理結(jié)構(gòu)化數(shù)據(jù)的常見(jiàn)工具有SparkSQL和Hive。

SparkSQL是Spark上的一個(gè)模塊，可以從外部讀入數(shù)據(jù)內(nèi)容，將其轉(zhuǎn)化為特有的DataFrame數(shù)據(jù)結(jié)構(gòu)，分布式地進(jìn)行存儲(chǔ)和運(yùn)算。同時(shí)它包含了部分?jǐn)?shù)據(jù)庫(kù)常見(jiàn)的操作函數(shù)，可在分布式平臺(tái)上進(jìn)行用戶(hù)的查詢(xún)或修改操作。

Hive是基于分布式平臺(tái)的一個(gè)數(shù)據(jù)倉(cāng)庫(kù)工具，可以將結(jié)構(gòu)化的數(shù)據(jù)文件映射為一張數(shù)據(jù)庫(kù)表。在Hive上可以進(jìn)行結(jié)構(gòu)化查詢(xún)語(yǔ)言SQL的語(yǔ)句查詢(xún)。當(dāng)輸入SQL語(yǔ)句之后，Hive會(huì)把SQL語(yǔ)句轉(zhuǎn)換為MapReduce任務(wù)，然后在分布式系統(tǒng)上進(jìn)行運(yùn)行。

通過(guò)將差別約束的驗(yàn)證改寫(xiě)為SQL語(yǔ)句，在Hive和SparkSQL下運(yùn)行。

例如，在表格Table1上有差分依賴(lài)：

DD3[A(> 10)]→[B≤20)]

現(xiàn)需要返回違背DD3的元組對(duì)的數(shù)量，可以用如下SQL語(yǔ)句來(lái)描述：

SELECT COUNT(*)

FROM Table AS X,Table AS Y

WHERE(X.A-Y.A)>10 AND ABS(X.B-Y.B)>20

實(shí)驗(yàn)1使用隨機(jī)三角分布、SparkSQL和Hive進(jìn)行差別依賴(lài)的驗(yàn)證，比較不同數(shù)據(jù)量下的時(shí)間。此處三角分布的邊長(zhǎng)取l=14。

需要注意的是，由于Hive的運(yùn)行時(shí)間過(guò)長(zhǎng)，圖4中使用了對(duì)數(shù)縱坐標(biāo)來(lái)顯示運(yùn)行時(shí)間，橫坐標(biāo)為實(shí)驗(yàn)數(shù)據(jù)集的元組個(gè)數(shù)。當(dāng)數(shù)據(jù)量為20萬(wàn)行時(shí)，Hive的執(zhí)行時(shí)間已經(jīng)超過(guò)了7個(gè)小時(shí)，由此省略了40萬(wàn)行時(shí)Hive的運(yùn)行結(jié)果。從圖4可知，三角算法的時(shí)間非?？?，是SparkSQL和Hive時(shí)間的1/10～1/100。當(dāng)數(shù)據(jù)量達(dá)到40萬(wàn)行時(shí)，SparkSQL的耗時(shí)已經(jīng)達(dá)到了近2個(gè)小時(shí)，而三角分布只需要不到5分鐘，時(shí)間優(yōu)勢(shì)非常明顯。

圖4 實(shí)驗(yàn)1的實(shí)驗(yàn)結(jié)果

3.2 不同邊長(zhǎng)下性能比較

以隨機(jī)三角分布的邊長(zhǎng)和數(shù)據(jù)量作為變量，比較各情況下檢驗(yàn)差別依賴(lài)所需要的時(shí)間。

觀察圖5中同一條曲線，當(dāng)邊長(zhǎng)一定的時(shí)候，reducer數(shù)目不變，顯然數(shù)據(jù)量的增加會(huì)導(dǎo)致總時(shí)間增加。另一方面，在同數(shù)據(jù)量的情況下，隨著邊長(zhǎng)的增加，參與的reducer數(shù)目會(huì)增加，時(shí)間隨之下降，這和預(yù)期一致。

圖5 實(shí)驗(yàn)2的實(shí)驗(yàn)結(jié)果

需要注意reducer數(shù)目的增加并不會(huì)使得總時(shí)間一直下降。從實(shí)驗(yàn)結(jié)果看，當(dāng)reducer數(shù)目已經(jīng)較大時(shí)，再增加其數(shù)目(即增加邊長(zhǎng))對(duì)繼續(xù)縮短時(shí)間的幫助變得不再明顯。這是因?yàn)橹虚g的Shuffle過(guò)程是需要有實(shí)際的數(shù)據(jù)傳輸?shù)?。若過(guò)度增加邊長(zhǎng)和reducer數(shù)目，會(huì)造成數(shù)據(jù)傳輸量增大，而每個(gè)reducer上的工作減少卻不明顯，這可能反而會(huì)造成總時(shí)間的增加。

3.3 兩種三角分布算法性能比較

排序三角算法相較于隨機(jī)三角算法，可以在邊長(zhǎng)相同的情況下省去部分的reducer，或者可以增加reducer利用率，減少時(shí)間，但這兩點(diǎn)都建立在數(shù)據(jù)分布較為平均的情況下?，F(xiàn)對(duì)于兩個(gè)數(shù)據(jù)集，進(jìn)行兩種算法的性能比較。

3.3.1 邊長(zhǎng)相同時(shí)reducer的減少

當(dāng)邊長(zhǎng)固定時(shí)，隨機(jī)三角算法的reducer數(shù)目是不變的，而排序三角算法需要的reducer數(shù)目可以通過(guò)計(jì)算得出。以邊長(zhǎng)l=10為例，計(jì)算得出θ取不同運(yùn)算符時(shí)的reducer數(shù)量，和隨機(jī)三角算法進(jìn)行比較，如表2所示。

表2 reducer數(shù)目計(jì)算結(jié)果

分析表2得出，使用優(yōu)化算法，對(duì)于同一個(gè)差別依賴(lài)，其使用的reducer數(shù)目得到了顯著的下降，特別是在取值為=的時(shí)候。實(shí)際上，reducer可減少的數(shù)目與常數(shù)值和該屬性的取值范圍有很大關(guān)系：當(dāng)常數(shù)值接近于屬性值取值范圍的中間值時(shí)，不論θ的取值多少，都可以減少很大占比的reducer數(shù)目；而當(dāng)常數(shù)值接近于屬性值的一端時(shí)，至少也有兩個(gè)θ的取值可以使得reducer數(shù)目減少很多。

3.3.2 時(shí)間上的比較

排序三角算法相較于隨機(jī)三角算法，依賴(lài)于原始數(shù)據(jù)的具體分布。雖然三角邊長(zhǎng)可以增大，但若原始數(shù)據(jù)分布不均勻，會(huì)使得某些機(jī)器上的比較次數(shù)變多，進(jìn)而影響總體運(yùn)行時(shí)間。本次實(shí)驗(yàn)的數(shù)據(jù)集為均勻分布數(shù)據(jù)集Data1和正態(tài)分布數(shù)據(jù)集Data2，行數(shù)為20萬(wàn)行；隨機(jī)三角算法的邊長(zhǎng)l=10，與排序三角算法在θ的不同取值下進(jìn)行比較，如表3所示。

表3 時(shí)間比較結(jié)果

由表3可得，在均勻分布的數(shù)據(jù)集上，排序三角分布算法非常出色，可以更加高效地利用所有的reducer進(jìn)行計(jì)算。而在正態(tài)分布的數(shù)據(jù)集上，當(dāng)運(yùn)算符為<和>時(shí)，時(shí)間和隨機(jī)分布的耗時(shí)差距不大。這說(shuō)明排序三角算法相對(duì)來(lái)說(shuō)依賴(lài)于初始數(shù)據(jù)和初始條件，以及此時(shí)的方差和的取值是采取何種三角分布算法的分界點(diǎn)。

對(duì)于排序三角算法，若數(shù)據(jù)分布不均勻，會(huì)導(dǎo)致部分reducer上的工作量超過(guò)平均值，而MapReduce算法的時(shí)間，依賴(lài)于所有reducer中最晚結(jié)束的時(shí)間，所以非平均數(shù)據(jù)集的排序三角算法的時(shí)間會(huì)長(zhǎng)于使用相同數(shù)量reducer的隨機(jī)三角算法的時(shí)間。對(duì)于一個(gè)數(shù)據(jù)集更適合于何種三角分布算法，可以先通過(guò)抽樣來(lái)對(duì)數(shù)據(jù)分布進(jìn)行分析。

另外，對(duì)比表2和表3可以得出，即使是均勻分布的數(shù)據(jù)，時(shí)間減少的百分比，也不如上一個(gè)實(shí)驗(yàn)中預(yù)估reducer減少的百分比。這主要是因?yàn)樵谥暗姆治鲋?，部分因素被忽略了：一部分原因是在Shuffle步驟的耗時(shí)是固定的(大致只與元組數(shù)量有關(guān))，這部分時(shí)間無(wú)法按比例降低；另一方面，邊長(zhǎng)增加后，由于不為整數(shù)，所以也無(wú)法做到將所有的有效比較完全均勻分配到每一個(gè)reducer中，依舊會(huì)存在部分的冗余比較無(wú)法避免。

4 結(jié) 語(yǔ)

差別依賴(lài)用于描述數(shù)據(jù)表中元組對(duì)間屬性變化量之間的關(guān)系。差別依賴(lài)的約束驗(yàn)證需進(jìn)行元組的兩兩比較，通過(guò)引入分布式計(jì)算技術(shù)可以有效提高該過(guò)程的可用性。本文針對(duì)該問(wèn)題進(jìn)行研究，在分布式系統(tǒng)上提出了隨機(jī)三角分布的分布式算法，實(shí)現(xiàn)了差別依賴(lài)的大數(shù)據(jù)檢驗(yàn)。本文提出了排序三角分布，在均勻分布的數(shù)據(jù)集上，能夠更快速高效地完成約束驗(yàn)證。通過(guò)實(shí)驗(yàn)，兩個(gè)算法的時(shí)間優(yōu)勢(shì)非常明顯。

在未來(lái)的工作中，本文將考慮多差別依賴(lài)的分布式檢測(cè)算法。針對(duì)多依賴(lài)，通過(guò)合并檢測(cè)的方式以減少重復(fù)的工作量。另外，經(jīng)分析，數(shù)據(jù)傳輸量這一要素相對(duì)被忽略。在Spark等并行處理的系統(tǒng)中，Shuffle步驟會(huì)進(jìn)行數(shù)據(jù)的傳輸，數(shù)據(jù)傳輸量在reducer間的分派情況也會(huì)實(shí)際影響到最終的總計(jì)算時(shí)間。我們將由此探討邊長(zhǎng)、數(shù)據(jù)轉(zhuǎn)移量以及時(shí)間上的關(guān)系，以期進(jìn)一步進(jìn)行算法優(yōu)化。