基于內(nèi)容發(fā)布訂閱系統(tǒng)中高并發(fā)事件匹配算法

張志遠(yuǎn)，錢 玭

(中國(guó)民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300)

0 引 言

分布式發(fā)布訂閱系統(tǒng)是一個(gè)多對(duì)多的異步消息(事件)傳遞模型，在時(shí)間、空間和同步上完全解耦，同時(shí)還具有易擴(kuò)展和多對(duì)多的通訊特點(diǎn)[1]，被廣泛應(yīng)用于各種大規(guī)模數(shù)據(jù)交換平臺(tái)中，如在線廣告[2]、信息過(guò)濾[3]、移動(dòng)消息推送[4,5]、物聯(lián)網(wǎng)傳輸[6,7]等。在整個(gè)發(fā)布訂閱系統(tǒng)中，事件匹配算法作為核心組件，是保證系統(tǒng)匹配性能的關(guān)鍵因素。發(fā)布訂閱系統(tǒng)按照消息類型可分為3類：基于主題的、基于類型的和基于內(nèi)容的[8]。與基于主題和基于類型的系統(tǒng)相比，基于內(nèi)容的發(fā)布訂閱系統(tǒng)訂閱信息的描述更加詳細(xì)，表達(dá)能力也更強(qiáng)。

近年來(lái)，學(xué)術(shù)界提出的事件匹配機(jī)制按照索引結(jié)構(gòu)大致可以分為兩個(gè)方面：

(1)樹(shù)形索引結(jié)構(gòu)。Be-Tree[9]是一種動(dòng)態(tài)樹(shù)索引結(jié)構(gòu)，采用了一種兩相空間切割技術(shù)。通過(guò)屬性來(lái)劃分訂閱區(qū)間，對(duì)屬性和屬性值約束，快速過(guò)濾不滿足訂閱來(lái)提高匹配效率。H-Tree[10]是哈希表和哈希鏈的結(jié)合。在每個(gè)索引屬性的值域被分成幾個(gè)部分重疊的單元格后，所有索引屬性的哈希列表都鏈接到哈希樹(shù)中。CBPS[11]提出了一種樹(shù)匹配結(jié)構(gòu)四叉樹(shù)。將謂詞匹配問(wèn)題轉(zhuǎn)化為查詢問(wèn)題，并對(duì)這個(gè)區(qū)間進(jìn)行劃分。

(2)線性索引結(jié)構(gòu)。TAMA[12]使用分層索引表來(lái)存儲(chǔ)訂閱，將每個(gè)屬性的范圍從多層索引結(jié)構(gòu)的頂部到底部分成多個(gè)單元格。REIN[13]將事件匹配問(wèn)題轉(zhuǎn)化為矩形相交問(wèn)題，對(duì)于每個(gè)屬性，構(gòu)建兩個(gè)桶列表。一個(gè)桶列表用于范圍約束的低值，另一個(gè)用于范圍約束的高值。PHSIH[14]通過(guò)水平分割數(shù)據(jù)結(jié)構(gòu)的索引層次來(lái)實(shí)現(xiàn)并行化，以支持多個(gè)線程在公共數(shù)據(jù)結(jié)構(gòu)上并行執(zhí)行匹配任務(wù)。GEM[15]設(shè)計(jì)了一種基于解析幾何的索引結(jié)構(gòu)，將訂閱的謂詞映射到每個(gè)維度的三角形區(qū)域。

以上算法研究只關(guān)注單個(gè)事件與訂閱之間的匹配，在高并發(fā)情形下多個(gè)事件批量到達(dá)時(shí)，對(duì)單個(gè)事件逐一進(jìn)行匹配的速度可能落后于事件的到達(dá)速度，導(dǎo)致事件不能及時(shí)處理。為此，關(guān)注多個(gè)事件之間的匹配關(guān)系，在REIN算法的基礎(chǔ)上，提出一種面向高并發(fā)事件的匹配算法HCEM，旨在解決傳統(tǒng)算法并行能力上的缺陷。

1 相關(guān)概念及索引結(jié)構(gòu)的構(gòu)建

1.1 基本定義

定義1 事件

事件由發(fā)布者發(fā)布，通常也稱之為消息、通知和發(fā)布。屬性用attr表示，屬性值用value表示，事件E是由多個(gè)attr=value的屬性值對(duì)的連詞，以及一個(gè)標(biāo)識(shí)事件的事件號(hào)id組成，規(guī)定每個(gè)屬性在事件中出現(xiàn)且僅只能出現(xiàn)一次。例如： E={id=1,temperature=25,humidity=50} 表示一個(gè)事件號(hào)為1的天氣事件，溫度等于25 ℃，濕度50%。定義A={a1,a2,a3,…,am} 為事件的屬性集合。

定義2 約束

約束是指A上的某個(gè)屬性需滿足的條件。簡(jiǎn)單約束通常表示為 {attr,operator,value,type} 的形式，其中operator是操作符，包括≥、≤、=，type表示屬性的數(shù)據(jù)類型，和REIN算法一致本文僅考慮integer型。范圍約束通常表示為 {attr,vlow,vhigh,type} 的四元組形式，其中vlow表示下界值，vhigh表示上界值，并且vlow始終小于等于vhigh。給定屬性的取值范圍，則簡(jiǎn)單約束可用范圍約束定義，例如：數(shù)據(jù)類型為integer的溫度值域?yàn)閇0,100]，那么簡(jiǎn)單約束 {temperature,≥,20,integer} 可轉(zhuǎn)換為 {temperature,20,100,integer}。

定義3 訂閱

訂閱是用戶對(duì)事件興趣的表達(dá)，由多個(gè)合取的約束構(gòu)成，即必須同時(shí)滿足所有的約束條件。每個(gè)訂閱由一個(gè)唯一的訂閱號(hào)進(jìn)行標(biāo)識(shí)，訂閱中的約束數(shù)量不大于m，其中m為事件中出現(xiàn)的屬性個(gè)數(shù)。

定義4 事件匹配

給定一組n個(gè)訂閱S={S1,S2,S3,…,Sn} 和事件E，從S中檢索與事件E匹配的所有訂閱的過(guò)程稱為事件匹配。匹配訂閱集Se是訂閱集S的一個(gè)子集，Se?S

1.2 索引結(jié)構(gòu)設(shè)計(jì)

為實(shí)現(xiàn)高效事件匹配，采取負(fù)搜索策略，即在事件匹配過(guò)程中及時(shí)刪除所有不匹配訂閱。本節(jié)對(duì)索引結(jié)構(gòu)作詳細(xì)介紹和說(shuō)明。

索引結(jié)構(gòu)由多個(gè)索引桶列表組成，每個(gè)索引桶里儲(chǔ)存映射到該索引值的所有謂詞值value和訂閱號(hào)id。索引桶列表的個(gè)數(shù)為2 m，其中m為事件中出現(xiàn)的屬性個(gè)數(shù)。對(duì)于每一個(gè)屬性，都為其構(gòu)建兩個(gè)索引桶列表Llow和Lhigh，Llow用來(lái)存儲(chǔ)所有訂閱謂詞的下界值，Lhigh用來(lái)存儲(chǔ)所有訂閱謂詞的上界值。同時(shí)為每個(gè)事件創(chuàng)建一個(gè)bits集合，大小為訂閱數(shù)量，用來(lái)標(biāo)記不匹配訂閱。

對(duì)于訂閱Sj∈S中的任意維度屬性ai∈A，采用離散化屬性值方法將范圍約束的謂詞vi映射到相應(yīng)的索引桶中(假設(shè)謂詞的下界值為vilow，上界值為vihigh，屬性ai的值域?yàn)?[Ui,Ri]， 訂閱Sj有唯一的標(biāo)識(shí)符Sj·id)，具體計(jì)算過(guò)程如下，其中T為索引桶個(gè)數(shù)

(1)

(2)

例如對(duì)于表1中的15條訂閱，構(gòu)建的索引結(jié)構(gòu)如圖1所示。為屬性a1創(chuàng)建兩個(gè)索引桶鏈表La1low和La1high，假設(shè)T=7，即為L(zhǎng)a1low和La1high分別劃分7個(gè)索引儲(chǔ)存桶，每個(gè)索引桶由唯一索引值標(biāo)識(shí)，索引桶儲(chǔ)存所有映射到索引值的謂詞值value和訂閱號(hào)id。

表1 訂閱清單

圖1 HCEM索引結(jié)構(gòu)

1.3 訂閱插入

步驟1 輸入訂閱s；

步驟2 判斷訂閱中謂詞約束屬于簡(jiǎn)單約束還是范圍約束，簡(jiǎn)單約束轉(zhuǎn)步驟3，范圍約束轉(zhuǎn)步驟4；

步驟3 若約束操作符operator為“≥”，令vlow=va-lue，vhigh=Ri；若約束操作符operator為“≤”，令vlow=Ui，vhigh=value；若約束操作符operator為“=”，令vlow=vhigh=value；

步驟4 把上下界值vhigh和vlow代入式(1)和式(2)，分別計(jì)算謂詞映射到維度ai上下界索引結(jié)構(gòu)中的位置Tihigh和Tilow；

步驟5 把約束值vi和訂閱號(hào)id插入到索引值相對(duì)應(yīng)的儲(chǔ)存桶中。

例如，假設(shè)表1中屬性a1的值域?yàn)閇0，70]，則對(duì)于約束S1，下界值vlow=8映射到La1low索引桶0中儲(chǔ)存，上界值vhigh=24映射到La1high索引桶2中存儲(chǔ)。

2 HCEM

HCEM(high concurrency event matching)模型設(shè)計(jì)有兩個(gè)重要指標(biāo)。首先，匹配速度對(duì)發(fā)布訂閱系統(tǒng)的影響至關(guān)重要，因此模型的首要目標(biāo)是追求高匹配速度；其次，匹配性能必須穩(wěn)定，匹配時(shí)間不會(huì)隨著訂閱數(shù)量、屬性數(shù)量等因素的增加而急劇上升[16]。為了追求高匹配速度和減輕訂閱匹配的影響，模型采用了負(fù)搜索策略[17]。其基本思想是從訂閱集中快速檢索出不匹配訂閱并將其從搜索空間中剔除，最后剩下的即為匹配訂閱。

2.1 動(dòng)態(tài)調(diào)整機(jī)制

為提高系統(tǒng)在事件高并發(fā)情形下的處理能力，設(shè)計(jì)了動(dòng)態(tài)調(diào)整機(jī)制。針對(duì)某時(shí)刻內(nèi)同時(shí)到達(dá)的多個(gè)事件，考慮事件之間的內(nèi)在特性，動(dòng)態(tài)調(diào)整事件進(jìn)入搜索空間的順序。隨著搜索的不斷深入搜索空間不斷減小，從而減少不必要的遍歷，提高事件匹配效率。

當(dāng)事件同時(shí)到達(dá)時(shí)，事件匹配按照屬性維度進(jìn)行。依次在屬性ai(i=0,1,…,m)上對(duì)事件值進(jìn)行排序，確定事件進(jìn)入屬性ai搜索空間的順序。根據(jù)負(fù)搜索策略，找出與事件不匹配的訂閱，所以，在下界值索引結(jié)構(gòu)中找出大于事件值的訂閱，在上界值索引結(jié)構(gòu)中找出小于事件值的訂閱。若存在事件ej>ek，那么在下界值索引結(jié)構(gòu)中滿足ej的訂閱必定也滿足ek，在上界值索引結(jié)構(gòu)中滿足ek的訂閱必定滿足ej。故而確定在下界值索引結(jié)構(gòu)中，事件值越大，越優(yōu)先進(jìn)入搜索空間。相反，在上界值索引結(jié)構(gòu)中，事件值越小，事件就越先進(jìn)入搜索空間。

例如，假設(shè)在屬性a1上同時(shí)到達(dá)3個(gè)事件 {e1(a1=57), e2(a1=15), e3(a1=32)}。 根據(jù)動(dòng)態(tài)調(diào)整機(jī)制，在下界值索引結(jié)構(gòu)中事件進(jìn)入搜索空間的順序?yàn)閑1→e3→e2。如圖2(a)所示，因?yàn)閰^(qū)間X1的值始終大于區(qū)間X2的值，符合事件e1的訂閱必定也符合事件e3，所以，事件e3的遍歷空間為X2，同理，事件e2的搜索空間為X3。在上界值索引結(jié)構(gòu)中，事件進(jìn)入搜索空間的順序?yàn)閑2→e3→e1。如圖2(b)所示，因?yàn)閰^(qū)間X1的值始終小于區(qū)間X2的值，符合事件e2的訂閱必定也滿足事件e3，所以事件e3的遍歷空間為X2。同理，事件e1的搜索空間為X3。如此，在上下界索引的遍歷過(guò)程中，排序后只需從頭到尾掃描一遍索引結(jié)構(gòu)，因此大大縮減了遍歷空間，減少不必要的搜索，從而提高事件匹配效率。

圖2 動(dòng)態(tài)調(diào)整機(jī)制

2.2 事件匹配

給定同時(shí)到達(dá)事件集合 E={e1,e2,…,en}， 其中事件e={a1=v1,a2=v2,…,am=vm}， 對(duì)每個(gè)約束(含下界和上界)的謂詞與事件值進(jìn)行比較，發(fā)現(xiàn)和標(biāo)記所有與事件不匹配的訂閱。具體事件匹配算法見(jiàn)表2。

表2 事件匹配算法

例如，同時(shí)到達(dá)事件為E={e1(a1=57),e2(a1=15),e3(a1=32)}， 查找圖2中與事件匹配的訂閱。根據(jù)事件匹配規(guī)則，先為每個(gè)事件建立bits集，并初始化為0。然后根據(jù)動(dòng)態(tài)調(diào)整機(jī)制，確定事件進(jìn)入下界值索引結(jié)構(gòu)順序?yàn)閑1→e3→e2。首先事件e1進(jìn)入，先在索引桶b5中查找，沒(méi)有找到不匹配訂閱，然后遍歷X1區(qū)間所有訂閱S10，并在事件e1、e2、e3的bits集中標(biāo)記為1。其次事件e3進(jìn)入，先在索引桶b3找到不匹配訂閱S8、S13并在bitse3集中標(biāo)記為1，然后遍歷X2區(qū)間所有訂閱S6、S7、S12、S14，并在事件e3、e2的bits集中標(biāo)記為1。最后事件e2進(jìn)入,在索引桶b1找到不匹配訂閱S3并在bitse2集中標(biāo)記為1，然后遍歷X3區(qū)間的所有訂閱S2、S4、S5、S8、S9、S13，并在事件e2的bits集中標(biāo)記為1。上界值索引結(jié)構(gòu)中匹配同理。最終結(jié)果如圖3所示，bits集中值為0的即為每個(gè)事件的匹配訂閱。

圖3 事件匹配bits集

2.3 事件匹配性能分析

為分析事件匹配性能，設(shè)同時(shí)到達(dá)的事件數(shù)為h，每個(gè)事件中的屬性數(shù)為m，訂閱數(shù)為n，每個(gè)訂閱中的謂詞數(shù)為k，儲(chǔ)存桶個(gè)數(shù)為b。為每個(gè)屬性創(chuàng)建兩個(gè)由b個(gè)索引桶組成的索引結(jié)構(gòu)。儲(chǔ)存桶的總數(shù)為m*b，訂閱的謂詞總數(shù)為n*k，假設(shè)謂詞被均勻的插入到儲(chǔ)存桶中，則每個(gè)儲(chǔ)存桶里的謂詞數(shù)量為

事件匹配成本主要由兩部分組成，第一部分是在不完全匹配的索引桶中依次比較找出不匹配訂閱的比較成本，第二部分是在完全不匹配的索引桶中遍歷所有訂閱的遍歷成本。設(shè)比較一個(gè)謂詞(不完全匹配時(shí))的單位時(shí)間為α，遍歷一個(gè)謂詞(完全不匹配時(shí))的單位時(shí)間為β。在最壞情況下，HCEM的匹配時(shí)間為

THCEM=2qαmh+2bqβm

其中，前一部分為比較時(shí)間，因?yàn)楸容^操作只在上下界索引結(jié)構(gòu)各一個(gè)索引桶中完成，所以單個(gè)事件在單個(gè)屬性上的比較時(shí)間為2qα，總的比較時(shí)間為2qαmh。后一部分為遍歷時(shí)間，最壞情況下，遍歷索引結(jié)構(gòu)中的所有訂閱，所以總遍歷時(shí)間為2bqβm。相比之下，REIN算法的匹配時(shí)間為

TREIN=2qαmh+bqβmh

與REIN算法相比，HCEM與REIN有著相同的比較時(shí)間，但HCEM算法的遍歷時(shí)間僅為REIN的2/h，即當(dāng)同時(shí)到達(dá)的事件越多時(shí)，HCEM的匹配時(shí)間相對(duì)于REIN就越短，匹配性能更具優(yōu)勢(shì)。原因在于HCEM算法大大減小了遍歷空間，從而減少大量不必要的遍歷，事件匹配速度也得到很大程度提高。

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

3.1 實(shí)驗(yàn)設(shè)置

為全面評(píng)價(jià)HCEM的匹配性能，我們?cè)诓煌瑢?shí)驗(yàn)場(chǎng)景下對(duì)HCEM和其它算法進(jìn)行了大量對(duì)比測(cè)試。實(shí)驗(yàn)環(huán)境為：CPU AMD Ryzen7 4800H 2.90 GHz，RAM 16 GB，Windows10 64位。所有代碼均用C++編寫。

本文選擇TAMA、H-Tree、REIN這3種匹配算法與HCEM進(jìn)行比較。TAMA是一種近似匹配和轉(zhuǎn)發(fā)引擎，使用層次索引表來(lái)轉(zhuǎn)發(fā)訂閱。H-Tree是一個(gè)由多個(gè)哈希列表組成的組合，通過(guò)對(duì)屬性進(jìn)行新的劃分來(lái)建立哈希列表。REIN為每個(gè)屬性構(gòu)建高低兩個(gè)約束儲(chǔ)存鏈表，將事件匹配問(wèn)題轉(zhuǎn)化為矩形相交問(wèn)題。這些算法的設(shè)置如下：TAMA中的離散化水平設(shè)置為γ=13；H-Tree中單元格數(shù)和索引屬性數(shù)設(shè)置為τ=δ=6；REIN中索引桶數(shù)量設(shè)置為b=1000。

實(shí)驗(yàn)的3個(gè)重要指標(biāo)是事件匹配時(shí)間、訂閱插入時(shí)間和訂閱刪除時(shí)間，在這個(gè)3個(gè)指標(biāo)中，事件匹配時(shí)間是評(píng)估事件匹配算法最重要的因素。HCEM算法與REIN算法索引結(jié)構(gòu)基本一致，訂閱的插入和刪除也基本一致，本文只改變了其中的匹配算法，所以HCEM與REIN的訂閱插入時(shí)間和訂閱刪除時(shí)間基本一致。

表3 實(shí)驗(yàn)參數(shù)設(shè)置

HCEM的匹配時(shí)間受多個(gè)參數(shù)的影響，包括訂閱的數(shù)量、訂閱中包含的約束數(shù)量、謂詞寬度、輸入的事件數(shù)和索引桶數(shù)量等。在實(shí)驗(yàn)部分，我們進(jìn)行了大量實(shí)驗(yàn)來(lái)觀測(cè)這些參數(shù)在不同設(shè)置下對(duì)事件匹配算法的影響。如無(wú)特殊說(shuō)明，設(shè)置同時(shí)到達(dá)500個(gè)事件來(lái)測(cè)量每個(gè)實(shí)驗(yàn)中的事件平均匹配時(shí)間。實(shí)驗(yàn)中，除非有明確說(shuō)明，否則事件屬性、事件值、約束屬性、約束值都隨機(jī)生成。

3.2 索引桶數(shù)量對(duì)事件匹配的影響

對(duì)于HCEM，比較操作在每個(gè)屬性的兩個(gè)索引桶中進(jìn)行，桶的大小勢(shì)必會(huì)對(duì)事件匹配性能造成影響，為此我們?cè)O(shè)計(jì)實(shí)驗(yàn)驗(yàn)證最佳索引桶的個(gè)數(shù)。設(shè)置訂閱數(shù)量n=200萬(wàn)，事件中屬性數(shù)量m=20，訂閱中約束數(shù)量k=10，謂詞寬度θ=0.5，只改變索引桶b的數(shù)量。結(jié)果如圖4所示，當(dāng)訂閱為200萬(wàn)時(shí)，最佳的索引桶數(shù)為1000。當(dāng)桶數(shù)大于1000時(shí)，匹配事件不再隨著桶數(shù)的增加而減少，匹配性能反而下降。原因?yàn)楫?dāng)訂閱數(shù)量較大時(shí)，需要更多的索引桶來(lái)提高匹配效率，但隨著桶的增加，桶之間的切換成本就會(huì)增加，抵消減少比較操作所獲取的好處。所以，當(dāng)桶的數(shù)量達(dá)到一個(gè)臨界值時(shí)，匹配性能就會(huì)下降。

圖4 索引桶數(shù)量的影響

3.3 事件批處理能力

HCEM利用動(dòng)態(tài)調(diào)整機(jī)制確定事件進(jìn)入搜索空間的優(yōu)先級(jí)，相對(duì)于其它算法來(lái)說(shuō)，最大的優(yōu)勢(shì)在于其批處理能力。本節(jié)通過(guò)實(shí)驗(yàn)研究4種算法的批處理能力，設(shè)置事件中屬性數(shù)量m=20，訂閱中約束數(shù)量k=10，謂詞寬度θ=0.5，索引桶數(shù)b=1000，訂閱數(shù)量n=100萬(wàn)，只改變同時(shí)處理的事件數(shù)量。實(shí)驗(yàn)結(jié)果如圖5所示，4種算法的匹配時(shí)間都隨著事件數(shù)的增多而增加。當(dāng)同時(shí)到達(dá)的事件越少時(shí)，HCEM與REIN的匹配時(shí)間差距越小，當(dāng)事件為1時(shí)，退化為REIN。當(dāng)同時(shí)處理1000個(gè)事件時(shí)，相比于TAMA、H-Tree和REIN，HCEM匹配時(shí)間分別是這3種算法的12.1倍、6.4倍和2.2倍。由此可見(jiàn)，HCEM對(duì)事件批處理的能力大大優(yōu)于其它算法。

圖5 批處理性能

3.4 訂閱數(shù)對(duì)事件匹配時(shí)間的影響

在本實(shí)驗(yàn)中，我們?cè)O(shè)置事件中屬性數(shù)量m=20，訂閱中約束數(shù)量k=10，謂詞寬度θ=0.5，索引桶數(shù)b=1000，只改變訂閱數(shù)量，觀察訂閱數(shù)對(duì)事件匹配算法性能的影響。給定謂詞寬度，為保證下界值的分布和上界值分布相同，范圍約束的下界值從[0,1-θ]中隨機(jī)生成，上界值從[θ,1]中隨機(jī)生成。

結(jié)果如圖6所示，總體而言，所有匹配算法的事件匹配時(shí)間都隨著訂閱數(shù)量的增加而增加。與其它3種匹配算法相比，HCEM算法的性能受訂閱次數(shù)的影響最小。當(dāng)訂閱為200萬(wàn)時(shí)，HCEM相比于TAMA、H-Tree、REIN的事件匹配時(shí)間分別下降91.04%、83.17%和47.02%，平均下降89.59%、81.75%和47.11%。

圖6 訂閱數(shù)量對(duì)匹配時(shí)間的影響

為了測(cè)試匹配算法性能的穩(wěn)定性，我們對(duì)匹配時(shí)間的最小值、最大值和標(biāo)準(zhǔn)差進(jìn)行分析，結(jié)果見(jiàn)表4，相比于TAMA、H-Tree、REIN，HCEM的標(biāo)準(zhǔn)差小了11.3倍、6.1倍和1.9倍。此外TAMA、H-Tree、REIN和FEMA在匹配時(shí)間的最大值和最小值的差上。因此，HCEM可以為事件匹配提供更穩(wěn)定的匹配性能，保證事件匹配的穩(wěn)定性。

表4 事件匹配算法的性能

3.5 約束個(gè)數(shù)對(duì)事件匹配的影響

本節(jié)進(jìn)行實(shí)驗(yàn)來(lái)評(píng)估約束個(gè)數(shù)對(duì)事件匹配性能的影響。實(shí)驗(yàn)中，設(shè)置謂詞寬度θ=0.5，訂閱數(shù)量n=100萬(wàn)，索引桶數(shù)b=1000，只改變事件屬性m和約束屬性k的數(shù)量，并保證k為m的一半。實(shí)驗(yàn)結(jié)果如圖7所示，當(dāng)訂閱約束數(shù)量增加時(shí)，訂閱的選擇性降低[10]，因此H-Tree的匹配時(shí)間首先隨著約束數(shù)量的增加而迅速下降。一般情況下，4種算法的匹配時(shí)間都隨著約束數(shù)量的增長(zhǎng)而增長(zhǎng)。當(dāng)約束數(shù)量k=20時(shí)，HCEM分別是TAMA、H-Tree、REIN的9.8倍、4.3倍、2.0倍。

圖7 約束數(shù)量對(duì)匹配時(shí)間的影響

3.6 謂詞寬度對(duì)事件匹配的影響

給定事件值的分布，謂詞寬度決定了訂閱的匹配性，一般來(lái)說(shuō)，寬度越大，訂閱匹配性越高。本節(jié)通過(guò)實(shí)驗(yàn)研究謂詞寬度對(duì)事件匹配的影響，設(shè)置事件中屬性數(shù)量m=20，訂閱中約束數(shù)量k=10，索引桶數(shù)b=1000，訂閱數(shù)量n=100萬(wàn)，改變謂詞寬度θ，結(jié)果如圖8所示。TAMA的事件匹配時(shí)間隨著θ的增長(zhǎng)呈現(xiàn)線性增加；H-Tree的性能隨著θ的增長(zhǎng)呈指數(shù)級(jí)惡化，因?yàn)棣仍酱螅蕉嗟闹^詞落在相對(duì)少的單元格中，需要遍歷的單元數(shù)呈指數(shù)級(jí)增加。當(dāng)θ≥0.8時(shí)，內(nèi)存被消耗完，因此圖中沒(méi)有結(jié)果。REIN和HCEM的匹配時(shí)間隨著θ的增加而減少，因?yàn)椴黄ヅ溆嗛嗠S著謂詞寬度θ的增長(zhǎng)而減少，需要遍歷和被排除的訂閱也就減少。當(dāng)謂詞寬度越大時(shí)，HCEM與REIN的匹配時(shí)間越接近。因?yàn)棣仍酱?，謂詞越集中分布在少量的索引桶中，動(dòng)態(tài)調(diào)整機(jī)制作用越小?？傮w來(lái)說(shuō)，HCEM相比于其它3種算法，謂詞寬度對(duì)事件匹配時(shí)間的影響都是最小的。

圖8 謂詞寬度對(duì)匹配時(shí)間的影響

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

本文提出了一種基于內(nèi)容的發(fā)布訂閱系統(tǒng)中高并發(fā)事件匹配方法HCEM。以往的算法中，事件之間是獨(dú)立的，只考慮每個(gè)事件的匹配流程，忽略了事件之間的聯(lián)系，系統(tǒng)的并行能力不能滿足高并發(fā)事件的需求。為此，本文考慮事件高并發(fā)情況，設(shè)計(jì)動(dòng)態(tài)調(diào)整機(jī)制對(duì)事件優(yōu)先級(jí)進(jìn)行處理，并采用負(fù)搜索策略進(jìn)行事件匹配。為了評(píng)估HCEM的性能，進(jìn)行了一系列綜合實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，該算法在匹配速度、性能穩(wěn)定和批處理能力等方面均優(yōu)于其它同類算法。同時(shí)也表明了HCEM具有快速性、穩(wěn)定性和動(dòng)態(tài)性等特征。