基于雙哈希模糊布隆濾波器云存儲(chǔ)數(shù)據(jù)融合

洪文圳，李冬睿，沈 陽(yáng)

(1.廣東農(nóng)工商職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)學(xué)院，廣東 廣州 510507； 2.華南理工大學(xué) 軟件學(xué)院，廣東 廣州 510641)

0 引 言

工業(yè)物聯(lián)網(wǎng)(IIoT)在各領(lǐng)域的應(yīng)用越來(lái)越多，IIoT連接傳感器和執(zhí)行器快速大量生成異構(gòu)數(shù)據(jù)[1,2]。當(dāng)前面臨挑戰(zhàn)是高效和安全地存儲(chǔ)和處理/分析大量數(shù)據(jù)，特別是敏感IIoT數(shù)據(jù)[3,4]。此外，流式數(shù)據(jù)可能是短暫的，因此需要能夠在一次傳輸中對(duì)此類數(shù)據(jù)進(jìn)行及時(shí)的分析和處理[5]。

當(dāng)前已有許多針對(duì)IIoT數(shù)據(jù)的處理方法，例如，熊等。文獻(xiàn)[6]設(shè)計(jì)了一種近似的基于Bloom濾波器的密鑰值(k-v)存儲(chǔ)方法。文獻(xiàn)[7]提出一種動(dòng)態(tài)Bloom濾波器數(shù)組，用于云存儲(chǔ)系統(tǒng)中成員身份的有效表示。文獻(xiàn)[8]提出可調(diào)節(jié)Bloom過(guò)濾器，稱為Scalable Bloom濾波器(SBF)，通過(guò)添加新的過(guò)濾器來(lái)執(zhí)行批量數(shù)據(jù)的插入，并且在兩個(gè)不同級(jí)別上執(zhí)行查詢處理以提高其準(zhǔn)確性和查詢復(fù)雜度。文獻(xiàn)[9]提出基于SDN的大數(shù)據(jù)管理方法來(lái)優(yōu)化多云DT中的網(wǎng)絡(luò)資源消耗，Bloom濾波器被用來(lái)分析他們提出的解決方案的性能。Bloom濾波器在各個(gè)領(lǐng)域廣泛應(yīng)用，可有效地處理可擴(kuò)展性問(wèn)題，缺點(diǎn)是查詢復(fù)雜度隨著輸入數(shù)據(jù)量增加而增加。

本文提出一種在確保失效數(shù)據(jù)魯棒性條件下，將兩個(gè)Bloom濾波器壓縮成一個(gè)濾波器的新方法，可更為有效利用存儲(chǔ)容量：①使用模糊交叉操作壓縮合并兩個(gè)Bloom濾波器，大量元素被容納在m大小Bloom濾波器中；②數(shù)據(jù)緩慢衰減，允許流數(shù)據(jù)在內(nèi)存中駐留相當(dāng)長(zhǎng)的時(shí)間；③在不損失精度的情況下高效優(yōu)化利用存儲(chǔ)空間。

1 數(shù)據(jù)存儲(chǔ)系統(tǒng)模型描述

1.1 IIoT網(wǎng)絡(luò)結(jié)構(gòu)模型

圖1描繪了包括不同層的典型IIoT網(wǎng)絡(luò)結(jié)構(gòu)設(shè)置，這些層結(jié)構(gòu)的主要作用是信息獲取、計(jì)算、存儲(chǔ)和檢索。在初始階段，從地理分布的傳感器和執(zhí)行器獲取異構(gòu)數(shù)據(jù)。然后，通過(guò)IIoT和Internet基礎(chǔ)設(shè)施將收集的數(shù)據(jù)傳送到地理上分布的云DCs中，在那里存儲(chǔ)和深入分析數(shù)據(jù)。數(shù)據(jù)分析的結(jié)果隨后提供給授權(quán)用戶(例如，通過(guò)移動(dòng)設(shè)備)。

圖1 IIoT環(huán)境下的數(shù)據(jù)存儲(chǔ)

典型的IIoT環(huán)境中的數(shù)據(jù)存儲(chǔ)包含以下兩個(gè)階段：①數(shù)據(jù)從連接設(shè)備、傳感器以及執(zhí)行器進(jìn)行發(fā)送；②一旦收到數(shù)據(jù)，對(duì)其進(jìn)行濾波以去除異常和冗余值，并將過(guò)濾后的數(shù)據(jù)保存在內(nèi)存中，直到在主內(nèi)存中找到足夠存儲(chǔ)空間。與數(shù)據(jù)存儲(chǔ)相關(guān)的重要任務(wù)是明確數(shù)據(jù)壓縮(例如，在不影響其準(zhǔn)確性的情況下，將減少的數(shù)據(jù)保存在較小的內(nèi)存空間中)。目的是研究數(shù)據(jù)壓縮，以確保有效地利用可用的存儲(chǔ)空間進(jìn)行大規(guī)模數(shù)據(jù)存儲(chǔ)。

1.2 Bloom濾波器

fp≈(1-e-kn/m)k

(1)

假陽(yáng)性率可能隨著Bloom濾波器中潛在的插入過(guò)程而增加。然而，Bloom濾波器固有的節(jié)省空間的能力，往往克服了這一缺點(diǎn)。

1.3 問(wèn)題描述

給定具有n個(gè)元素的數(shù)據(jù)流(Ds)，即Ds={x1,x2,…,xn}，主要要求是在存儲(chǔ)器和搜索復(fù)雜度方面改進(jìn)現(xiàn)有的Bloom濾波器的性能。所設(shè)計(jì)結(jié)構(gòu)可表示為如下問(wèn)題[13]：

(1)流數(shù)據(jù)在很短時(shí)間內(nèi)是可用的，因此必須一次性處理，并在內(nèi)存中保留足夠長(zhǎng)時(shí)間以便查詢。

(2)與散列相關(guān)的計(jì)算成本(Cc)應(yīng)最小化。

(3)處理動(dòng)態(tài)數(shù)據(jù)集時(shí)的查詢復(fù)雜性(Qc)應(yīng)得到優(yōu)化。

(4)用于存儲(chǔ)數(shù)據(jù)的存儲(chǔ)器應(yīng)以最大數(shù)量的元素可容納的方式進(jìn)行優(yōu)化(Ea)。

(5)假陽(yáng)性(fp)，Bloom濾波器的重要性能參數(shù)不應(yīng)超過(guò)預(yù)定限值。

上述問(wèn)題可表示為如下數(shù)學(xué)模型

(2)

2 模糊交叉Bloom濾波器(FFBF)

2.1 模糊交叉操作

模糊交叉操作[14]，首先合并ax∈BFi[]和by∈BFj[]的元素，其中x=y。這兩個(gè)元素在兩部分中具有相同的索引，彼此重疊并在上半部分存儲(chǔ)為單個(gè)模糊值。在此過(guò)程中，指紋位用于數(shù)據(jù)壓縮。融合的兩個(gè)Bloom濾波器，BFi[]和BFj[]，被稱為第一交叉或第一壓縮形式。它由符號(hào)CRi,j表示，并且需要兩個(gè)位(塊位和指紋位)來(lái)表示使用模糊符號(hào)存儲(chǔ)在其中的元素。模糊交叉操作表示為⊙，并表示為如下模型

(3)

圖2 模糊交叉過(guò)程

表1 模糊操作

初始階段數(shù)據(jù)m/2,m/4,m/8,…可以壓縮形式查詢。簡(jiǎn)單Bloom濾波器的主要特點(diǎn)是具有幾乎立即衰減率，F(xiàn)FBF與之相比具有相對(duì)較慢的衰減過(guò)程。FFBF中采用的交叉操作的計(jì)算成本幾乎可忽略，因?yàn)樗鼉H對(duì)二進(jìn)制集應(yīng)用簡(jiǎn)單的模糊操作。此外，當(dāng)m取值較小時(shí)，所提模糊交叉操作在計(jì)算上變得低效。在這種情況下，通過(guò)將所有比特位設(shè)置為零可獲得相對(duì)更高的計(jì)算效率。

定理1模糊交叉運(yùn)算不可交換，即

(BFi[]⊙BFj[])≠(BFj[]⊙BFi[])

(4)

證明：在FFBF算法中，Bloom濾波器的位置在交叉操作中起著重要作用。根據(jù)式(3)，CR1,2是指BF1和BF2的壓縮形式。CR1,2中元素qy的查詢過(guò)程表示如下

(5)

因此，在模糊操作中Bloom濾波器的位置發(fā)生變化，搜索結(jié)果將受到重大影響。可以得出結(jié)論，模糊交叉運(yùn)算不可交換

CR1,2≠CR2,1

(BFi[]⊙BFj[])≠(BFj[]⊙BFi[])

(6)

對(duì)于上述引理，得出結(jié)論如下：在模糊交叉運(yùn)算中，α和β是互補(bǔ)的，而γ獨(dú)立于Bloom濾波器的位置。

定理2對(duì)于具有m和k哈希函數(shù)數(shù)組的給定Bloom濾波器，由FFBF容納的元素?cái)?shù)(NFFBF)是簡(jiǎn)單Bloom濾波器(SBF)容納的元素?cái)?shù)(NSBF)的1.9倍

NFFBF≈1.9×(NSBF)

(7)

(8)

總迭代次數(shù)k由b個(gè)塊表示，如下所示

(9)

對(duì)于給定的m大小的Bloom濾波器，與SBE相比FFBF中可用的總內(nèi)存(MFFBF)可計(jì)算如下

(10)

(11)

假設(shè)n個(gè)元素可由使用m大小Bloom濾波器的SBF容納。在相同大小數(shù)組中，F(xiàn)FBF可容納的元素總數(shù)如下所示

(12)

(13)

定理3CRi,i+1壓縮表示的假陽(yáng)性率(FPCR)等于BFi[]和BFi+1[]的假陽(yáng)性率(即FPi和FPi+1)

(14)

證明：模糊折疊是一種算術(shù)運(yùn)算，CRi,i+1中的單個(gè)元素(即，來(lái)自BFi[]和BFi+1[]的個(gè)數(shù))用模糊符號(hào)α,β,γ表示。每個(gè)符號(hào)都有唯一的簽名，見表1。例如，BFj[]中α表示1，而在BFj[]中α表示0。CRi,i+1的誤差主要來(lái)自于BFi[]和BFi+1[]中的突變位。但是，使用模糊符號(hào)不會(huì)導(dǎo)致CRi,i+1出現(xiàn)誤差。

(15)

因此，壓縮表示的假陽(yáng)性率與具有參數(shù)m和k的SBF假陽(yáng)性率相同。

2.2 FFBF中的數(shù)據(jù)插入

gi(x)={h1(x)+i×h2(x)}modmp

(16)

在上面公式中，mp是相對(duì)于BF(m)大小的最大限制范圍(1:m)和最接近素?cái)?shù)(減少?zèng)_突次數(shù))之間的散列函數(shù)的值。mp的選擇采取可生成最佳散列值方式進(jìn)行選取。插入首先將m大小的數(shù)組劃分為兩個(gè)相同大小的Bloom濾波器

(17)

最初，元素被添加到第i個(gè)Bloom濾波器中。然而，當(dāng)BFi[]的填充容量超過(guò)閾值填充比(Fthres)時(shí)，插入從BFi+1[]開始。在插入的第一級(jí)，根據(jù)以下散列值，只有塊位被設(shè)置為1

(18)

一旦達(dá)到BFi+1[]濾波器的閾值，模糊交叉操作⊙被應(yīng)用在兩個(gè)濾波器(BFi[]和BFi+1[])上，以便在現(xiàn)有的Bloom濾波器中為更多的數(shù)據(jù)存儲(chǔ)空間。為使模糊交叉操作有效，m和k應(yīng)該是2的倍數(shù)(即，表示為2x)。具體計(jì)算過(guò)程見算法1所示。

算法1：FFBF中的數(shù)據(jù)插入過(guò)程

輸入：數(shù)據(jù)流(S)

輸出：Bloom濾波器操作—插入&&折疊

(1) 設(shè)置S(Bloom濾波器的數(shù)據(jù)集)；

(2) 設(shè)置m←Bloom濾波器的大?。?/p>

(3) 設(shè)置k←哈希函數(shù)(2x)；

(4) 設(shè)置i←1；

(5) 設(shè)置BF[i]←Size(1,m/2)；

(6) 設(shè)置BF[i+1]←Size(m/2+1,m)；

(7) forx∈Sdo

(8) ifm≥kdo

(9) if FillRatio(BFi[])>Fthresthen

(10) if FillRatio(BFi+1[])>Fthresthen

(12)BFi[]←Size(1,m/2)；BFi+1[]←Size(m/2+1,m)；

(13) endif

(14) else

(17) endfor

(18) end

(19) endif

(20) else

(23) endfor

(24) end

(25) endif

(26) else

(27) 達(dá)到最大插入極限；

(28) end

(29) end

2.3 FFBF中的數(shù)據(jù)查詢

FFBF中的查詢過(guò)程與標(biāo)準(zhǔn)Bloom濾波器的相同，這表明查詢的數(shù)據(jù)最初是散列的，Bloom濾波器中的相應(yīng)位置被掃描以獲取HIGH位。在FFBF中，查詢過(guò)程始終從活動(dòng)時(shí)隙A開始。如果在第A個(gè)時(shí)隙中找到元素，則查詢過(guò)程返回TRUE；否則，掃描將繼續(xù)，直到A=1搜索開始，按如下散列查詢方式

(19)

(20)

下面是根據(jù)上面定義的hResult()函數(shù)得出的結(jié)論

(21)

根據(jù)以上討論可得，查詢CR中的一個(gè)項(xiàng)目(y∈Q)的時(shí)間復(fù)雜度是O(k)，如果CRi,i+1表示時(shí)隙BF[i]和BF[i+1]的2n個(gè)元素。算法2描述了上述FFBF中使用的整個(gè)查詢過(guò)程。

算法2：FFBF中的數(shù)據(jù)查詢過(guò)程

輸入：數(shù)據(jù)流(S)

輸出：Bloom濾波器操作—插入&&折疊

(1) 設(shè)置a←insertion(i)；

(2) whilea≠0 do

(3) ifa→(BF[a]) then

(5)y∈BF[a]th；

(6) endif

(7) endif

(8) else ifa→(CRa-1,a) then

(9) Update(Cα,Cβ,Cγ)←hResult(y)；

(11) endif

(12) if memPa==1 then

(13)y∈BFa-1[]th；

(14) endif

(15) else if memPa-1==1&&memPa==1 then

(16)y∈BFa[]th&&BFa-1[]th；

(17) end

(18) endif

(19)a=a-1；

(20) end

(21)y?S；

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

為實(shí)現(xiàn)對(duì)所提云存儲(chǔ)數(shù)據(jù)融合算法的性能測(cè)試，本實(shí)驗(yàn)選取PBC 0.5.15測(cè)試庫(kù)進(jìn)行模擬測(cè)試，可實(shí)現(xiàn)對(duì)文件失效情況下的批量審計(jì)模型設(shè)計(jì)，同時(shí)選取文獻(xiàn)[13-15]這3種云存儲(chǔ)算法進(jìn)行對(duì)比實(shí)驗(yàn)，該測(cè)試系統(tǒng)選取的開發(fā)語(yǔ)言是C語(yǔ)言。測(cè)試系統(tǒng)平臺(tái)軟件選取Linux 3.8.0-29，處理器配置為CPU Intel(R) E5605@2.55 GHz，系統(tǒng)內(nèi)存大小是32 GB，系統(tǒng)硬盤是1 TB希捷機(jī)械硬盤。

設(shè)置云存儲(chǔ)過(guò)程中的數(shù)據(jù)塊大小是|id|=50 b，云存儲(chǔ)過(guò)程的測(cè)試文件大小為1 GB，設(shè)定模擬測(cè)試過(guò)程中的文件損壞的最大比例是1%，選取所有數(shù)據(jù)塊中的500組作為模擬對(duì)象進(jìn)行數(shù)據(jù)審計(jì)。實(shí)驗(yàn)對(duì)比指標(biāo)首先選取云存儲(chǔ)過(guò)程中的通信數(shù)據(jù)開銷進(jìn)行實(shí)驗(yàn)對(duì)比，為確保測(cè)試過(guò)程所得結(jié)果穩(wěn)定，每組實(shí)驗(yàn)單獨(dú)運(yùn)行30次求取實(shí)驗(yàn)結(jié)果的均值進(jìn)行對(duì)比測(cè)試。表2為本文算法與選取的3種對(duì)比算法的實(shí)驗(yàn)對(duì)比結(jié)果。

表2 通信開銷測(cè)試數(shù)據(jù)對(duì)比

根據(jù)表2實(shí)驗(yàn)數(shù)據(jù)可知，在算法的通信開銷指標(biāo)上，本文所提的云存儲(chǔ)數(shù)據(jù)融合算法相對(duì)于選取的文獻(xiàn)[13-15]這3種云存儲(chǔ)對(duì)比算法具有較為顯著的性能優(yōu)勢(shì)。隨著文件數(shù)量的增加，數(shù)據(jù)云存儲(chǔ)過(guò)程的通信開銷均逐漸增加，并且本文算法相對(duì)于選取的對(duì)比算法的通信開銷優(yōu)勢(shì)逐漸增加，上述實(shí)驗(yàn)結(jié)果驗(yàn)證了所提算法在云存儲(chǔ)數(shù)據(jù)通信開銷指標(biāo)上的性能優(yōu)勢(shì)。

首先，利用本文算法與最差設(shè)定實(shí)驗(yàn)情形進(jìn)行對(duì)比實(shí)驗(yàn)，即失效文件多數(shù)是成對(duì)出現(xiàn)。圖3為最差情形下，批量審計(jì)次數(shù)指標(biāo)隨失效文件個(gè)數(shù)變化對(duì)比情況，模擬測(cè)試過(guò)程中設(shè)置文件總個(gè)數(shù)是256個(gè)。

圖3 批量審計(jì)次數(shù)實(shí)驗(yàn)對(duì)比(最差)

根據(jù)圖3結(jié)果可知，在最不理想情況下，對(duì)于選取的幾種對(duì)比實(shí)驗(yàn)算法中,本文算法的批量審計(jì)次數(shù)最少，這表明所提算法在給定失效文件情況下，所需要的失效文件審計(jì)指標(biāo)最佳。對(duì)比算法中，文獻(xiàn)[13]算法因?yàn)樾枰獙?duì)失效文件交叉內(nèi)容進(jìn)行重復(fù)性質(zhì)的查詢操作，因此其在失效文件審計(jì)指標(biāo)上要高于文獻(xiàn)[14]算法，表明其針對(duì)失效數(shù)據(jù)的處理能力要弱于文獻(xiàn)[14]算法。文獻(xiàn)[15]算法設(shè)計(jì)了一種快速識(shí)別算法，但是在最差實(shí)驗(yàn)環(huán)境下，失效文件往往多數(shù)是成對(duì)出現(xiàn)的，這種實(shí)驗(yàn)環(huán)境下，無(wú)法有效發(fā)揮文獻(xiàn)[15]算法快速識(shí)別過(guò)程的有效性，因此在實(shí)驗(yàn)結(jié)果上的表現(xiàn)就是文獻(xiàn)[15]算法的批量審計(jì)指標(biāo)雖然要優(yōu)于文獻(xiàn)[13，14]算法，但是與本文算法相比仍有較大的差距。

其次，為了對(duì)上述情況進(jìn)行對(duì)比分析，選取隨機(jī)情況再次進(jìn)行實(shí)驗(yàn)?zāi)M，對(duì)比算法仍然選取文獻(xiàn)[13-15]這3種算法，實(shí)驗(yàn)對(duì)比結(jié)果如圖4所示，模擬測(cè)試過(guò)程中設(shè)置文件總個(gè)數(shù)仍是256個(gè)。

圖4 批量審計(jì)次數(shù)實(shí)驗(yàn)對(duì)比(隨機(jī))

根據(jù)圖4結(jié)果可知，在隨機(jī)情況下，對(duì)于選取的幾種對(duì)比實(shí)驗(yàn)算法中的本文算法的批量審計(jì)次數(shù)仍然最少，這與最差情形下的實(shí)驗(yàn)結(jié)果一致，表明本文算法具有更廣的適應(yīng)性。同樣，與最差情形相似，對(duì)比算法中文獻(xiàn)[13]算法因?yàn)樾枰獙?duì)失效文件交叉內(nèi)容進(jìn)行重復(fù)性質(zhì)的查詢操作，因此其在失效文件審計(jì)指標(biāo)上要高于文獻(xiàn)[14]算法。由于設(shè)定為隨機(jī)實(shí)驗(yàn)情形，因此文獻(xiàn)[15]算法設(shè)計(jì)的快速識(shí)別過(guò)程具有一定的效果，與本文算法實(shí)驗(yàn)結(jié)果具有相對(duì)的接近性。

對(duì)于選取的256個(gè)模擬測(cè)試過(guò)程的總文件個(gè)數(shù)，設(shè)定其中失效的文件總數(shù)是17個(gè)，這些失效文件仍然采取隨機(jī)方式進(jìn)行分布設(shè)置。對(duì)比算法仍然選取文獻(xiàn)[13-15]這3種算法，實(shí)驗(yàn)指標(biāo)選取查詢時(shí)間，單位是ms，實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 查詢時(shí)間對(duì)比

根據(jù)圖5所示實(shí)驗(yàn)結(jié)果，文獻(xiàn)[13]算法因?yàn)樾枰诓樵冞^(guò)程中首先對(duì)測(cè)試數(shù)據(jù)的行列數(shù)據(jù)進(jìn)行審計(jì)定位，因此其在查詢時(shí)間上相對(duì)于選取的對(duì)比算法具有更高的查詢時(shí)間。對(duì)于少量文件損壞情形，因?yàn)槲墨I(xiàn)[15]算法選取的是一種冪指查詢方式，因此其數(shù)據(jù)查詢時(shí)間相對(duì)較快，但是在文件損壞數(shù)量增加后，算法的查詢時(shí)間逐漸增加，并且查詢時(shí)間的增加幅度要顯著高于本文算法。文獻(xiàn)[14]算法查詢時(shí)間指標(biāo)介于文獻(xiàn)[13]和文獻(xiàn)[15]兩種算法之間。根據(jù)上述時(shí)間結(jié)果可知，本文算法在查詢時(shí)間指標(biāo)上也要優(yōu)于選取的對(duì)比算法，體現(xiàn)了所提算法的性能優(yōu)勢(shì)。

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

本文提出的濾波器采用一種模糊技術(shù)來(lái)解決Bloom濾波器的空間需求問(wèn)題。我們驗(yàn)證了所提出的方法可以在同一空間容納更多的元素。與SBF相比，由于所提出的濾波器僅包含二元集合上的簡(jiǎn)單模糊運(yùn)算，因此交叉和與之相關(guān)的運(yùn)算的代價(jià)幾乎可以忽略不計(jì)。壓縮后的誤報(bào)率與標(biāo)準(zhǔn)Bloom濾波器相同。由于使用了雙哈希技術(shù)，兩個(gè)哈希函數(shù)生成k個(gè)哈希函數(shù)，因此哈希運(yùn)算的計(jì)算時(shí)間也大大減少。FFBF的查詢復(fù)雜度取決于Bloom濾波器被劃分的塊的數(shù)量。從m大小的Bloom濾波器和相同大小的壓縮表示中搜索元素保持不變。實(shí)驗(yàn)結(jié)果驗(yàn)證了所提算法有效性。下一步，①對(duì)雙哈希模糊交叉Bloom濾波器進(jìn)行進(jìn)一步改進(jìn)，提高算法計(jì)算效率；②考慮引入稀疏數(shù)據(jù)表示方式，對(duì)算法執(zhí)行效率進(jìn)一步改進(jìn)提升；③考慮實(shí)際應(yīng)用軟件開發(fā)，驗(yàn)證真實(shí)環(huán)境算法性能。