覃 昇 談子敬 肖永松

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

0 引 言

數(shù)據(jù)質(zhì)量問題在大數(shù)據(jù)時代變得更為突出。無論系統(tǒng)能夠以多么快的速度處理多么大的數(shù)據(jù)量，如果數(shù)據(jù)質(zhì)量得不到保證，一切得到的分析結(jié)果可能都是無意義的。在對數(shù)據(jù)質(zhì)量進(jìn)行評估的多個維度中，數(shù)據(jù)一致性是一個常見的指標(biāo)。數(shù)據(jù)一致性通常基于用邏輯表達(dá)式的形式所給出的數(shù)據(jù)依賴來進(jìn)行描述。簡而言之，若數(shù)據(jù)不滿足給定的數(shù)據(jù)依賴，則稱該數(shù)據(jù)為不一致，這通常意味著數(shù)據(jù)中存在錯誤或誤差。

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

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

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

1 背景知識

1.1 差別依賴

首先回顧一下差別依賴的具體定義[2]。

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

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

(1)

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

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

(2)

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

對一個信用卡交易的數(shù)據(jù)庫，可以有如下差別依賴：

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

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

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

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

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

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

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

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

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

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

2 三角分布算法

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

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

2.1 隨機(jī)三角算法

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

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

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

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

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

三角分布邊長l；

差別依賴DD。

輸出：違背DD的所有元組對。

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

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

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

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

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

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

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

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

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

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

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

2.3 排序三角算法

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

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

(3)

t表示單位區(qū)間長度，則整個[smin,smax)區(qū)間可以被分成l個長度為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為在編號為i的reducer中，需要比較的兩個元組的屬性A上值的差的范圍。例如dif7=(p,3p)，因?yàn)樵谶@個reducer中需要比較的兩個元組的A屬性的值分別屬于[3p,4p)和[p,2p)，所以兩個數(shù)據(jù)之差的范圍為(p,3p)。

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

圖3顯示了在圖2條件下各reducer中可能進(jìn)行的運(yùn)算，顯然針對特定的θ,并非所有reducer都有工作。記numθ為θ取不同運(yùn)算符時所需要的reducer數(shù)量，在忽略少量的邊界情況和暫定k為整數(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)算符的對應(yīng)關(guān)系

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

另一方面，既然可以減少需要使用的reducer，那自然也可以用這些reducer來加速整個過程。

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

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

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

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

表1 Spark啟動參數(shù)表

實(shí)驗(yàn)所使用的測試數(shù)據(jù)集有兩個，均為人為構(gòu)造的大數(shù)據(jù)集。兩個數(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作為測試數(shù)據(jù)測試三角算法的性能，而在實(shí)驗(yàn)3中，使用Data1和Data2作為測試數(shù)據(jù)，比較隨機(jī)三角算法和排序三角算法的優(yōu)缺點(diǎn)。

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

3.1 時間比較

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

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

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

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

例如，在表格Table1上有差分依賴：

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

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

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)行差別依賴的驗(yàn)證，比較不同數(shù)據(jù)量下的時間。此處三角分布的邊長取l=14。

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

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

3.2 不同邊長下性能比較

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

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

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

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

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

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

3.3.1 邊長相同時reducer的減少

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

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

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

3.3.2 時間上的比較

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

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

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

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

另外，對比表2和表3可以得出，即使是均勻分布的數(shù)據(jù)，時間減少的百分比，也不如上一個實(shí)驗(yàn)中預(yù)估reducer減少的百分比。這主要是因?yàn)樵谥暗姆治鲋校糠忠蛩乇缓雎粤耍阂徊糠衷蚴窃赟huffle步驟的耗時是固定的(大致只與元組數(shù)量有關(guān))，這部分時間無法按比例降低；另一方面，邊長增加后，由于不為整數(shù)，所以也無法做到將所有的有效比較完全均勻分配到每一個reducer中，依舊會存在部分的冗余比較無法避免。

4 結(jié) 語

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

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