朱彥杰

許昌學(xué)院

數(shù)據(jù)流處理在某種程度上包含流的匯總過(guò)程，考慮如何從流中抽取有用樣本，以及如何從流中過(guò)濾大部分不想要的元素。估計(jì)流中的元素個(gè)數(shù)，其中估計(jì)方法所用的存儲(chǔ)開(kāi)銷(xiāo)遠(yuǎn)小于列舉所有所見(jiàn)元素的開(kāi)銷(xiāo)。

Web 網(wǎng)站收到的流包括各種類(lèi)型，如百度一天收到幾億個(gè)搜索查詢(xún)，新浪各個(gè)不同網(wǎng)站上收到數(shù)十億個(gè)“點(diǎn)擊”，基于這些流數(shù)據(jù)可以學(xué)習(xí)到很多有趣的結(jié)果，如某個(gè)鏈接的點(diǎn)擊率的突然上升可能意味著有些新聞連向此網(wǎng)頁(yè)，否則的話(huà)可能意味著該鏈接失效急需修復(fù)。

1 流數(shù)據(jù)

Web 網(wǎng)站收到的流包括各種類(lèi)型，如百度一天收到幾億個(gè)搜索查詢(xún)，新浪各個(gè)不同網(wǎng)站上收到數(shù)十億個(gè)“點(diǎn)擊”，基于這些流數(shù)據(jù)可以學(xué)習(xí)到很多有趣的結(jié)果，如某個(gè)鏈接的點(diǎn)擊率的突然上升可能意味著有些新聞連向此網(wǎng)頁(yè)，否則的話(huà)可能意味著該鏈接失效急需修復(fù)。數(shù)據(jù)以一個(gè)或多個(gè)流的方式到來(lái)，如果不對(duì)數(shù)據(jù)進(jìn)行及時(shí)的處理或存儲(chǔ)，數(shù)據(jù)將會(huì)永遠(yuǎn)丟失，即是數(shù)據(jù)到來(lái)的速度太快，以致將全部數(shù)據(jù)存在傳統(tǒng)數(shù)據(jù)庫(kù)并在選定的時(shí)間進(jìn)行交互是不可能的。流數(shù)據(jù)處理所受的一些限制，一方面，流元素的分發(fā)速度通常很快，必須對(duì)元素進(jìn)行實(shí)時(shí)處理，否則就會(huì)永遠(yuǎn)失去處理它們的機(jī)會(huì)，除非訪問(wèn)歸檔存儲(chǔ)器。流處理算法通常在內(nèi)存中執(zhí)行，一般不會(huì)或者極少數(shù)訪問(wèn)二級(jí)存儲(chǔ)器；此外，即使當(dāng)數(shù)據(jù)流很慢時(shí)，也可能存在多個(gè)這樣的數(shù)據(jù)流，即每個(gè)流本身能夠基于很小的內(nèi)存就能處理，但所有數(shù)據(jù)流的內(nèi)存需求加在一起可能就很容易超過(guò)內(nèi)存的可用容量。所以，當(dāng)內(nèi)存足夠大時(shí)，流數(shù)據(jù)的很多問(wèn)題很容易解決，而實(shí)際情況，在一個(gè)真實(shí)規(guī)模的機(jī)器上獲得現(xiàn)實(shí)的處理速度，問(wèn)題變得相當(dāng)困難，需要采用新技術(shù)解決：1）通常情況下，獲得問(wèn)題的近似解比精確解要高效得多；2）為了產(chǎn)生與精確解相當(dāng)接近的近似解，需采用哈希相關(guān)技術(shù)。

2 流當(dāng)中的數(shù)據(jù)抽樣

從流中選擇一個(gè)子集，以便能夠?qū)λM(jìn)行查詢(xún)并給出統(tǒng)計(jì)上對(duì)整個(gè)流具有代表性的結(jié)果；流由一系列n 字段元組構(gòu)成，這些字段的一個(gè)子集稱(chēng)為關(guān)鍵詞段，樣本的選擇基于它來(lái)進(jìn)行，比如，一個(gè)流由三元組（user，query，time）組成，其中user 可以作為關(guān)鍵詞段。若關(guān)鍵詞段包含的字段不止一個(gè)，那么哈希函數(shù)就要將這些字段的值組合起來(lái)形成單一的哈希值。最后得到樣本由有某些特定鍵值的所有元組構(gòu)成。為了保證樣本由鍵值子集所對(duì)應(yīng)的所有元組組成，可以選擇一個(gè)哈希函數(shù)h，將鍵值映射到一個(gè)很大的取值范圍0，1，…，B-1。另外，維護(hù)一個(gè)閥值t，它的初始值可以設(shè)置成最大的桶編號(hào)B-1。任何時(shí)候，樣本都由鍵值K 滿(mǎn)足h（K）＜=t 的元組構(gòu)成。當(dāng)且僅當(dāng)滿(mǎn)足同樣條件的情況下，流中的新元組才會(huì)加入到樣本中。如果樣本中存儲(chǔ)的元組數(shù)目超過(guò)分配的空間大小，那么就將閥值降低為t-1，并將那些鍵值K 滿(mǎn)足h（K）=t 的元組去掉。為提高效率，還可以將閥值降低更多。無(wú)論何時(shí)需要將某些鍵值從樣本中丟棄時(shí)，都可以將幾個(gè)具有最高哈希值的元組去掉。

3 流過(guò)濾

只想接受流中滿(mǎn)足某個(gè)準(zhǔn)則的元組集合。如果選擇的準(zhǔn)則基于元組的某個(gè)可計(jì)算屬性得到，那么選擇操作很容易完成，當(dāng)選擇準(zhǔn)則中包含集合元素的查找時(shí)，特別當(dāng)集合大到無(wú)法在內(nèi)存中存放時(shí)，問(wèn)題就變得尤其困難；對(duì)此要去掉不滿(mǎn)足選擇準(zhǔn)則的大部分元組，可以采用布隆過(guò)濾器：布隆過(guò)濾器的目的是讓所有鍵值在S 中的流元素通過(guò)，而阻擋大部分鍵值不在S 中的流元素。一個(gè)布隆過(guò)濾器由如下幾部分組成：

（1）n 個(gè)位組成的數(shù)組，每個(gè)位的初始值都為0；

（2）一系列哈希函數(shù) h1,h2,…h(huán)k組成的集合。每個(gè)哈希函數(shù)將“鍵”值映射到上述的n 個(gè)桶（對(duì)應(yīng)于位數(shù)組中n個(gè)位）中；

（3）m 個(gè)鍵值組成的集合S。

位數(shù)組的所有位的初始值為0。對(duì)S 中的每個(gè)鍵值K，利用每個(gè)哈希函數(shù)進(jìn)行處理。對(duì)于一些哈希函數(shù) ih 及S 中的鍵值K，將每個(gè) hi(K)對(duì)應(yīng)的位置為1。

當(dāng)鍵值為K 的流元素到達(dá)時(shí)，檢查所有的h1(K ),h2(K),… hk(K)對(duì)應(yīng)的位是否全部為1，如果是，則允許該流元素通過(guò)，若有一位或多位為0，則認(rèn)為K 不可能在S 中，于是拒絕該流元素通過(guò)。另外可以將多個(gè)過(guò)濾器串聯(lián)起來(lái)使用來(lái)進(jìn)一步過(guò)濾。

4 流中元素的數(shù)目統(tǒng)計(jì)

假定流元素選自某個(gè)全集，想知道流當(dāng)中從開(kāi)始或某個(gè)已知的過(guò)去時(shí)刻開(kāi)始所出現(xiàn)的不同元素?cái)?shù)目。如百度網(wǎng)站，它不需要登錄就可以提交搜索查詢(xún)，可能只能通過(guò)用戶(hù)提交查詢(xún)時(shí)的URL 來(lái)識(shí)別用戶(hù)。這里所有可能的URL全集可以想象成所有登錄主機(jī)名的全集。這需要在內(nèi)存中保存當(dāng)前已有的所有流元素，但是如果不同的元素?cái)?shù)目太多，或需要即刻處理多個(gè)流，那么就無(wú)法在內(nèi)存中存儲(chǔ)所需數(shù)據(jù)。處理策略是僅僅對(duì)獨(dú)立元素?cái)?shù)目進(jìn)行估計(jì)，具體思想是：通過(guò)將全集中的元素哈希到一個(gè)足夠長(zhǎng)的位串，就可以對(duì)獨(dú)立元素個(gè)數(shù)進(jìn)行估計(jì)。位串必須要足夠長(zhǎng)，以致哈希函數(shù)的可能結(jié)果數(shù)目要大于全集中的元素個(gè)數(shù)。流中的不同元素越多，那么不同哈希值也越多，在眾多不同哈希值中，其中有一個(gè)值變得異常，該值后面會(huì)以多個(gè)0結(jié)束。任何時(shí)候在流元素a 上應(yīng)用哈希函數(shù)h 時(shí)，位串h（a）的尾部將以一些0 結(jié)束，當(dāng)然也可能沒(méi)有0，尾部0 的數(shù)目稱(chēng)為a 和h 的尾長(zhǎng)。假設(shè)流當(dāng)中目前所有已有元素a 的最大尾長(zhǎng)為R。那么將使用2R 來(lái)估計(jì)到目前為止流中所看到的獨(dú)立元素?cái)?shù)目。

上述估計(jì)方法有直觀上意義：給定流元素a 的哈希值h（a）末尾至少有r 個(gè)0 的概率為2-r 。假定流中有m個(gè)獨(dú)立元素，那么任何元素的哈希值末尾都不滿(mǎn)足至少有r 個(gè)0 的概率為(1-2-r)m，該表達(dá)式可以改為((1-2-r)2r)m2-r。當(dāng)r 相當(dāng)大時(shí)，上式表達(dá)式就是(1-ε)1/ε，其大小約等于1/e。因此任何元素的哈希值末尾都不滿(mǎn)足至少有r 個(gè)0 的概率為 e-m2-r。于是可以得到如下結(jié)論：（1）如果m 遠(yuǎn)大于2r，那么發(fā)現(xiàn)一個(gè)尾部長(zhǎng)度至少為r 的概率接近1；（2）如果m 遠(yuǎn)小于2r，那么發(fā)現(xiàn)一個(gè)尾部長(zhǎng)度至少為r 的概率接近0；基于以上兩點(diǎn)結(jié)論，m 的估計(jì)值2R（R 是所有流元素中的最大尾長(zhǎng)）不可能過(guò)高或過(guò)低。

5 總結(jié)

對(duì)任一到達(dá)流元素的鍵值進(jìn)行哈希處理，使用哈希值來(lái)確定包含該鍵值的全部元素會(huì)是抽樣樣本的一部分。采用布隆過(guò)濾器允許屬于某個(gè)特定集合的流元素通過(guò)，而大部分其他元素被丟棄。為了估計(jì)流中出現(xiàn)的不同元素的數(shù)目，可以將元素哈希成整數(shù)，這些整數(shù)可以解釋為二進(jìn)制整數(shù)，任意流元素的哈希值中最長(zhǎng)的0 序列長(zhǎng)度作為2 的冪得到的結(jié)果會(huì)作為獨(dú)立元素?cái)?shù)目的估計(jì)值。