一種改進(jìn)的多維度并行匹配發(fā)布與訂閱算法

張澧楓，殷銘，袁平

（1.四川大學(xué)計(jì)算機(jī)學(xué)院,成都 610061；2.東華大學(xué)信息科學(xué)與技術(shù)學(xué)院，上海 201620；3.重慶第二師范學(xué)院數(shù)學(xué)與信息工程學(xué)院，重慶 400067）

0 引言

物聯(lián)網(wǎng)時(shí)代伴隨5G技術(shù)的發(fā)展，不同領(lǐng)域的數(shù)據(jù)被聯(lián)系在一起，使得數(shù)據(jù)采集和傳輸過程生成的數(shù)據(jù)成指數(shù)級(jí)增長[5]。與十年前相比，以往的數(shù)據(jù)采集系統(tǒng)和工具已經(jīng)很難滿足現(xiàn)有的場(chǎng)景性能要求。發(fā)布訂閱是指通過一個(gè)中間件將通信的兩端從時(shí)間和空間上解耦，是一種常見的通信方式。發(fā)布訂閱有三種常見的類型：基于主題、基于頻道和基于內(nèi)容[2]，基于主題和基于頻道雖然實(shí)現(xiàn)簡單且使用普遍，但是表達(dá)能力遠(yuǎn)遠(yuǎn)不及基于內(nèi)容的模式，而一個(gè)高效的匹配算法是基于內(nèi)容的發(fā)布訂閱最關(guān)鍵的部分。

提升匹配算法的關(guān)鍵是設(shè)計(jì)高效的索引結(jié)構(gòu)和快速的匹配過程[3]。REIN算法以一種流水線式的方式將不同維度匹配的結(jié)果串聯(lián)起來，上一個(gè)維度匹配的結(jié)果是下一個(gè)維度的輸入，減少了不必要的搜索空間。但是整個(gè)過程是單維度串行匹配，在還沒有得到上一個(gè)維度的匹配結(jié)果時(shí)當(dāng)前維度不會(huì)開始匹配。另外，REIN算法在做訂閱劃分的時(shí)候，為了匹配的方便訂閱需要有序的插入到訂閱表中，然而鏈表有序插入的時(shí)間復(fù)雜度為O（n），當(dāng)數(shù)據(jù)規(guī)模很大時(shí)訂閱的插入和匹配速度會(huì)很慢。本文提出了一種多維度并行匹配算法，充分利用CPU資源提高匹配算法的速度，并且改進(jìn)了REIN算法中索引結(jié)構(gòu)的設(shè)計(jì)，利用跳躍表在匹配和插入上的高效，提升了插入和匹配的效率。

實(shí)驗(yàn)結(jié)果表明，本文提出的多維度并行搜索機(jī)制和跳躍表索引結(jié)構(gòu)在匹配速度上有提升，并且插入和刪除的速度也有提升，這對(duì)于頻繁訂閱和取關(guān)的場(chǎng)景有很大的意義。整個(gè)算法的提出使得在面對(duì)大規(guī)模發(fā)布訂閱場(chǎng)景時(shí)，仍然能夠具有不錯(cuò)的性能。

1 算法分析與系統(tǒng)設(shè)計(jì)

1.1 MP-REIN數(shù)據(jù)模型

MP-REIN是一個(gè)基于內(nèi)容的多維度范圍匹配模型，維度定義為,m是維度數(shù)目。訂閱集合表示為，n是當(dāng)前訂閱空間的大小。訂閱是由Si包含的所有屬性的區(qū)間組成的集合，表示在屬性am上Si的區(qū)間約束。約束具有不同的值包括(<,?,>,?,=,≠)。事件表示為E={v1,…,vm}。

事件匹配結(jié)果分為部分匹配和全部匹配，如果Si上某幾個(gè)維度上的區(qū)間包含了事件E中vm的值，稱之為事件E與Si部分匹配，如果Si和E在全維度上匹配則稱之為全維度匹配，只有全維度匹配的訂閱才會(huì)收到對(duì)應(yīng)的事件通知。

1.2 跳躍表索引結(jié)構(gòu)

REIN算法的核心思想是盡早的標(biāo)記不匹配的訂閱，減少后續(xù)維度的事件匹配訂閱空間大小，其索引結(jié)構(gòu)是由多個(gè)桶鏈表組成，這種索引結(jié)構(gòu)在遇到大量訂閱落到某個(gè)獨(dú)立的桶時(shí)，因?yàn)殒湵聿檎液筒迦胄仕俣扔邢?，事件匹配的效率就?huì)大大降低。同時(shí)，REIN算法對(duì)每個(gè)維度建立兩條桶鏈，一條是對(duì)指定屬性的下邊界范圍約束，另一條是對(duì)指定屬性的上邊界范圍約束。桶鏈的建立是通過劃分屬性值域?yàn)槎鄠€(gè)單元，每個(gè)桶內(nèi)存儲(chǔ)值域在該區(qū)間的訂閱。REIN的索引結(jié)構(gòu)如圖所示。這種存儲(chǔ)方式帶來了額外的匹配，且增加了額外的內(nèi)存開銷，MP-REIN針對(duì)REIN的不足對(duì)索引結(jié)構(gòu)進(jìn)行了改進(jìn)。

跳躍表在工程中使用廣泛，是一種隨機(jī)化數(shù)據(jù)結(jié)構(gòu)，大多數(shù)操作如查找和插入的平均時(shí)間復(fù)雜度都為O（logn）。跳躍表是由多層有序鏈表關(guān)聯(lián)的數(shù)據(jù)結(jié)構(gòu)，層級(jí)越高元素個(gè)數(shù)越少，每次查找或者插入時(shí)會(huì)隨機(jī)選擇一層開始，向鏈表末尾移動(dòng)，如果在本層并沒有找到元素，就會(huì)在下一層向前查找，直到找到符合要求的元素為止。圖MP-REIN的索引結(jié)構(gòu)由數(shù)組和跳躍表組成，每個(gè)桶用跳躍表將訂閱有序的聯(lián)系起來。面對(duì)大規(guī)模發(fā)布訂閱時(shí)，跳躍表帶來的插入時(shí)間和匹配時(shí)間上的收益會(huì)大幅度提高事件匹配的效率。

自適應(yīng)索引結(jié)構(gòu)的訂閱劃分過程使用一個(gè)例子來說明，假設(shè)現(xiàn)有某訂閱集合S={S1,S2,S3,S4,S5,S6,S7,S8,S9,S10}，屬性空間A={a1,a2,a3}，S在屬性空間上的約束如圖2所示，系統(tǒng)根據(jù)屬性空間大小生成3條桶鏈，其中屬性a1,a2,a3值域?yàn)閇0,30],屬性a1,a2,a3的值域都被劃分為7個(gè)單元。一次事件匹配中，在a1屬性上，S1到S8的約束下邊界均在[10,15]區(qū)間，REIN在該區(qū)間上形成一個(gè)桶鏈，MP-REIN在該區(qū)間上形成一個(gè)跳躍表。S9和S10落入[20,25]區(qū)間，a1屬性上的訂閱劃分結(jié)束。限于篇幅，省去在a2和a3上的詳細(xì)匹配過程描述。訂閱劃分結(jié)束后，會(huì)得到所有屬性上整個(gè)訂閱集合劃分的結(jié)果。

圖1 REIN和MP-REIN索引結(jié)構(gòu)（左圖為REIN，右圖為MP-REIN，灰色節(jié)點(diǎn)是跳躍表為了提高速度而建立的輔助節(jié)點(diǎn)）

表1 10個(gè)訂閱列表

圖2 MP-REIN事件匹配流程圖

1.3 多維度事件匹配

REIN算法采用流水線式的單維度匹配算法，在前一個(gè)屬性上過濾掉一些不匹配的訂閱，縮減搜索空間的大小。然而，REIN單維度匹配算法的局限性限制了事件匹配的過程只能是單線程的，并沒有充分利用CPU的性能給事件匹配的速度帶來提升。MP-REIN使用多線程同時(shí)對(duì)訂閱集合的所有屬性展開搜索，當(dāng)某個(gè)線程在某一屬性上過濾掉某個(gè)訂閱Si時(shí)，會(huì)在輔助bit數(shù)組中標(biāo)記這個(gè)訂閱，其余線程在匹配到該訂閱的時(shí)候就會(huì)跳過，避免冗余的匹配。這種內(nèi)存標(biāo)記法不用維護(hù)額外的計(jì)數(shù)器，并得到了并行搜索帶來的時(shí)間收益，以較低的代價(jià)在事件匹配速度上得到了很大的提升。

圖2 展示了MP-REIN事件匹配的全部過程，在一次事件匹配中，會(huì)經(jīng)過如下步驟：

（1）開啟屬性空間大小數(shù)目的線程（線程的創(chuàng)建使用線程池，線程池創(chuàng)建線程減少了頻繁創(chuàng)建線程的開銷）。

第五，要大力發(fā)展高效節(jié)水灌溉技術(shù)。農(nóng)業(yè)是用水大戶，現(xiàn)在9.05億畝（0.60億hm2）的有效灌溉面積中節(jié)水灌溉面積只占到4.3億畝（0.29億hm2），還不到一半。另外，節(jié)水灌溉面積中的高效節(jié)水灌溉技術(shù)，像噴灌、微灌、管道輸水灌溉還不到2億畝（0.13億hm2），所以說，這方面節(jié)水的潛力非常大。

（2）初始化一個(gè)bit數(shù)組用來標(biāo)記不匹配的訂閱，所有任務(wù)線程并行標(biāo)記數(shù)組元素，基于最終的標(biāo)記數(shù)組向匹配的訂閱者廣播事件通知。

（3）預(yù)先創(chuàng)建的線程在此處用來并行劃分訂閱空間到按照各個(gè)屬性值域構(gòu)建的索引結(jié)構(gòu)中，用于后續(xù)的事件匹配和訂閱標(biāo)記。

（4）同樣使用預(yù)先創(chuàng)建的線程對(duì)到來的事件作并行劃分，落到（3）中已經(jīng)劃分過訂閱空間的索引結(jié)構(gòu)中

（5）并行執(zhí)行事件與訂閱匹配，對(duì)標(biāo)記數(shù)組中不匹配的訂閱作標(biāo)記。如果其他線程標(biāo)記過某個(gè)訂閱，則跳過。

（6）根據(jù)最終標(biāo)記的數(shù)組，篩選出匹配的訂閱并轉(zhuǎn)發(fā)事件給相關(guān)訂閱者。

1.4 匹配過程示例

在1.2小節(jié)中用一個(gè)例子展示了訂閱集合劃分的過程，并得到了最終劃分的結(jié)果。此時(shí)，發(fā)布者發(fā)布了一個(gè)事件，MP-REIN 算法根據(jù)事件中的屬性確定要在a1和a2對(duì)應(yīng)的屬性鏈上進(jìn)行匹配。

MP-REIN算法此時(shí)喚醒線程池中兩個(gè)線程T1和T2分別用來處理a1和a2兩個(gè)屬性鏈上的事件匹配，同時(shí)初始化一個(gè)大小為10的標(biāo)記數(shù)組B={0,0,0,0,0,0,0,0,0,0}，0表示S1到S10的初始匹配狀態(tài)。當(dāng)有線程判斷某個(gè)訂閱不匹配的時(shí)候就在標(biāo)記數(shù)組中將這個(gè)訂閱的狀態(tài)標(biāo)記為1。假設(shè)T1和T2同時(shí)開始事件匹配，但由于不同屬性中訂閱集合大小的差異，線程的執(zhí)行速度是有快慢的。

假設(shè)T2根據(jù)a2=7將B中下標(biāo)為2,4的元素標(biāo)記為1，表示不匹配。原本根據(jù)a1=12落在[10,15]區(qū)間，T1還需要將Ea1和S4的約束區(qū)間[10,12]的上邊界比較一次，但T2通過內(nèi)存數(shù)組感知到S4已經(jīng)被標(biāo)記，于是跳過此次比較。

2 實(shí)驗(yàn)評(píng)估

為了綜合評(píng)估MP-REIN的性能，通過大量實(shí)驗(yàn)對(duì)比了MP-REIN在三個(gè)指標(biāo)上的優(yōu)越性：匹配時(shí)間、插入時(shí)間和刪除時(shí)間。所有的實(shí)驗(yàn)在三臺(tái)8G內(nèi)存，Windows7操作系統(tǒng)，處理器為Inter酷睿i5-4460的臺(tái)式機(jī)上進(jìn)行。語言上選擇Java編程語言，所有的實(shí)驗(yàn)結(jié)果在本節(jié)展示。

MP-REIN將和REIN算法在性能上做全方位的比較，匹配算法的性能受到多個(gè)因素的影響，如表2所示，實(shí)驗(yàn)過程中將調(diào)整這些參數(shù)的取值，測(cè)量匹配時(shí)間、插入時(shí)間和刪除時(shí)間。為了簡化實(shí)驗(yàn)復(fù)雜性，將屬性的值域都設(shè)置為[0,1]。

實(shí)驗(yàn)過程中使用A、B、C三臺(tái)PC，分別用作發(fā)布者、代理器和訂閱者。測(cè)量匹配時(shí)間時(shí)，定義匹配時(shí)間為訂閱劃分和一次事件匹配的平均時(shí)間，為了測(cè)量代理器匹配時(shí)間，開啟一個(gè)Daemon線程用于在后臺(tái)記錄訂閱劃分的初始時(shí)間和事件匹配完成的結(jié)束時(shí)間；匹配算法的插入時(shí)間定義為全屬性訂閱插入桶中的平均時(shí)間，為了測(cè)量代理器插入時(shí)間，用同樣的Daemon線程在后臺(tái)記錄第一個(gè)訂閱插入的時(shí)間作為起始時(shí)間，在一組訂閱插入完畢后記錄當(dāng)前時(shí)刻用作結(jié)束時(shí)間。為了實(shí)驗(yàn)的準(zhǔn)確性，每一組實(shí)驗(yàn)進(jìn)行5次，結(jié)果取每一次的平均值。

表2 實(shí)驗(yàn)參數(shù)

2.1 匹配時(shí)間

所有的參數(shù)都會(huì)對(duì)算法產(chǎn)生性能上的影響，一般來說訂閱個(gè)數(shù)越多，匹配算法執(zhí)行的時(shí)間就越長。在匹配時(shí)間的性能評(píng)估中，設(shè)置實(shí)驗(yàn)參數(shù)：m=10,j=30,c=15,k=10,訂閱數(shù)目設(shè)置多組值：100、1000、10000、20000、40000、60000、80000、100000。訂閱個(gè)數(shù)對(duì)匹配時(shí)間的影響結(jié)果如圖3所示。MP-REIN在100、1000、10000組和REIN的匹配時(shí)間相差并不大，但是MPREIN在訂閱個(gè)數(shù)增加的過程中表現(xiàn)出了很明顯的優(yōu)勢(shì)，且差距越來越大，MP-REIN匹配速度快于REIN的原因在于：第一，訂閱個(gè)數(shù)較少（低于10000）的時(shí)候，MP-REIN的優(yōu)勢(shì)不是很明顯，因?yàn)榻⑻S表需要占用了一些時(shí)間，但當(dāng)訂閱個(gè)數(shù)逐漸增多的時(shí)候，構(gòu)建跳躍表的代價(jià)和其帶來的查找和插入速度上的收益來比就顯得很有意義了，跳躍表索引結(jié)構(gòu)優(yōu)勢(shì)體現(xiàn)，匹配速度提升明顯。第二，多維度匹配充分的利用了CPU的性能，帶來了匹配速度的提升。

圖3 訂閱個(gè)數(shù)對(duì)匹配時(shí)間的影響

2.2 插入時(shí)間

每當(dāng)有新的訂閱時(shí)就會(huì)有插入操作，發(fā)布者發(fā)布新的事件時(shí)也會(huì)有插入操作，評(píng)估一個(gè)發(fā)布訂閱算法，插入時(shí)間也是一個(gè)重要的衡量標(biāo)準(zhǔn)。設(shè)置實(shí)驗(yàn)參數(shù)同2.1節(jié)：m=10,j=30,c=15,k=10，記錄每一次的訂閱插入時(shí)間。觀察訂閱個(gè)數(shù)增長的過程中，MP-REIN和REIN插入時(shí)間的變化。訂閱個(gè)數(shù)對(duì)插入時(shí)間的影響如圖4所示?？梢钥吹皆诓迦霑r(shí)間上，MP-REIN優(yōu)勢(shì)明顯，可能的原因：第一，MP-REIN只需要插入一條鏈中，但是REIN需要插入兩條鏈。第二，MP-REIN索引結(jié)構(gòu)的插入時(shí)間復(fù)雜度是O（logn）低于鏈表的插入時(shí)間復(fù)雜度O（n），這個(gè)優(yōu)勢(shì)在數(shù)據(jù)量大的時(shí)候更加明顯，而受限于鏈表，REIN的插入速度難以提升。

圖4 訂閱個(gè)數(shù)對(duì)插入時(shí)間的影響

3 結(jié)語

本文提出了一種多維度并行匹配的匹配算法，一改傳統(tǒng)的單維度流水線匹配算法，充分利用CPU資源，事件匹配初始階段就在全屬性空間上匹配所有訂閱，一旦發(fā)現(xiàn)某個(gè)訂閱在某屬性上不符合約束，任意包含該訂閱的搜索都會(huì)跳躍這個(gè)訂閱，這一機(jī)制大大地提高了事件匹配的效率。另外，跳躍表索引結(jié)構(gòu)在面對(duì)大規(guī)模發(fā)布訂閱時(shí)，能夠依賴數(shù)據(jù)結(jié)構(gòu)在查找、插入和刪除上的優(yōu)勢(shì)，提高了整個(gè)事件匹配流程的效率。

實(shí)驗(yàn)結(jié)果表明，MP-REIN較傳統(tǒng)的算法在匹配時(shí)間和插入時(shí)間上都有一定的優(yōu)勢(shì)。