面向社交數(shù)據(jù)流連續(xù)查詢(xún)的基準(zhǔn)評(píng)測(cè)

李 葉， 夏 帆， 錢(qián)衛(wèi)寧

（華東師范大學(xué) 數(shù)據(jù)科學(xué)與工程研究院，上海 200062）

0 引 言

社交媒體服務(wù)被廣泛應(yīng)用于記錄和分享用戶(hù)的所見(jiàn)所聞所想，已經(jīng)成為現(xiàn)實(shí)世界中感知事件發(fā)生的重要手段.如今，社交媒體數(shù)據(jù)正迅速成為最熱門(mén)的市場(chǎng)研究資料，被數(shù)據(jù)科學(xué)家視為金礦，其在集群行為感知與監(jiān)控、在線廣告、意見(jiàn)挖掘等方面的應(yīng)用層出不窮；而這些應(yīng)用的成功，正是依賴(lài)于對(duì)社交媒體數(shù)據(jù)的有效分析.社交數(shù)據(jù)流指元素間具有聯(lián)系的數(shù)據(jù)流，常被用于對(duì)社交媒體數(shù)據(jù)進(jìn)行建模.不僅如此，它還能被用來(lái)表示科技文獻(xiàn)和科學(xué)觀測(cè)的數(shù)據(jù).

社交數(shù)據(jù)流上的連續(xù)查詢(xún)處理是基于實(shí)時(shí)的社交數(shù)據(jù)應(yīng)用的關(guān)鍵.傳統(tǒng)數(shù)據(jù)庫(kù)處理持久存儲(chǔ)的數(shù)據(jù)處理模式已不能適應(yīng)現(xiàn)在大量的實(shí)時(shí)在線應(yīng)用需求：數(shù)據(jù)到達(dá)過(guò)程是連續(xù)的，數(shù)據(jù)的查詢(xún)處理要求是單步處理，既來(lái)不及儲(chǔ)存也無(wú)法存儲(chǔ)流數(shù)據(jù).流數(shù)據(jù)管理系統(tǒng)可實(shí)現(xiàn)連續(xù)查詢(xún)、實(shí)時(shí)查詢(xún)、適應(yīng)的數(shù)據(jù)及數(shù)據(jù)量的變化等功能，是存儲(chǔ)和管理社交媒體數(shù)據(jù)的最佳選擇.流數(shù)據(jù)管理系統(tǒng)早在10年前就已經(jīng)成為數(shù)據(jù)庫(kù)領(lǐng)域的研究熱點(diǎn)，比較成熟的流數(shù)據(jù)管理系統(tǒng)包括麻省理工學(xué)院的Aurora和Medusa項(xiàng)目［1］，伯克利大學(xué)的TelegraphCQ項(xiàng)目［2］，斯坦福大學(xué)的STREAM項(xiàng)目［3］.文獻(xiàn)［4］提出的Linear Road是最早的針對(duì)流數(shù)據(jù)庫(kù)管理系統(tǒng)的評(píng)測(cè)基準(zhǔn)，該基準(zhǔn)模擬了高速公路收費(fèi)的應(yīng)用場(chǎng)景，數(shù)據(jù)集較為簡(jiǎn)單是該基準(zhǔn)的一個(gè)特點(diǎn).

社交媒體數(shù)據(jù)分析型的應(yīng)用具有以下特征：首先，不同于傳統(tǒng)的流數(shù)據(jù)，社交媒體數(shù)據(jù)流中的各條數(shù)據(jù)相互交織，組成了圖結(jié)構(gòu)的數(shù)據(jù)；例如，用戶(hù)之間關(guān)系的構(gòu)成了在線社交網(wǎng)絡(luò)圖數(shù)據(jù)流，信息的分享則構(gòu)成了消息的傳播圖，而用戶(hù)與消息之間的關(guān)聯(lián)則將兩個(gè)數(shù)據(jù)流聯(lián)通起來(lái)；其次，社交媒體數(shù)據(jù)在數(shù)據(jù)分布和數(shù)據(jù)到達(dá)模式上與傳統(tǒng)數(shù)據(jù)流均有不同，具有動(dòng)態(tài)、高度數(shù)據(jù)傾斜的特點(diǎn)；例如少部分微博在短時(shí)間內(nèi)被大量轉(zhuǎn)發(fā).然而，已有的基準(zhǔn)測(cè)試在流數(shù)據(jù)集上并未能很好地覆蓋這些特征［5］.與此同時(shí)，社交媒體流數(shù)據(jù)上的查詢(xún)也因?yàn)閿?shù)據(jù)模型以及實(shí)際應(yīng)用的不同而與傳統(tǒng)流數(shù)據(jù)查詢(xún)存在差別.綜上所述，目前缺乏一個(gè)基準(zhǔn)測(cè)試用于衡量社交數(shù)據(jù)流處理系統(tǒng)的整體性能.

考慮這樣一個(gè)問(wèn)題：在面向社交數(shù)據(jù)流的連續(xù)查詢(xún)中，不同的流數(shù)據(jù)管理系統(tǒng)其各自的優(yōu)勢(shì)在哪里？不同系統(tǒng)在執(zhí)行不同類(lèi)型的查詢(xún)時(shí)效果如何？針對(duì)這些問(wèn)題，我們提出了一套面向社交數(shù)據(jù)流上連續(xù)查詢(xún)的基準(zhǔn)評(píng)測(cè).

本文余下章節(jié)將作如下安排：第1節(jié)對(duì)社交數(shù)據(jù)流上的連續(xù)查詢(xún)問(wèn)題進(jìn)行建模，介紹該基準(zhǔn)評(píng)測(cè)中所用到的數(shù)據(jù)集，包括數(shù)據(jù)的收集及預(yù)處理，數(shù)據(jù)特征的定義.接下來(lái)第2節(jié)中介紹該基準(zhǔn)評(píng)測(cè)的負(fù)載類(lèi)型與分布，以及性能測(cè)度.最后在第3節(jié)中進(jìn)行總結(jié).

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

本節(jié)首先介紹社交媒體流數(shù)據(jù)的數(shù)據(jù)模型，然后介紹對(duì)本評(píng)測(cè)所使用的數(shù)據(jù)集.

1.1 數(shù)據(jù)流模型

在社交媒體應(yīng)用中，在線社交網(wǎng)絡(luò)是信息傳播的基石，用戶(hù)通過(guò)訂閱好友、娛樂(lè)明星和公知等的信息流，實(shí)時(shí)地獲取感興趣的信息.隨著關(guān)系親密度的改變或者用戶(hù)興趣的遷移，用戶(hù)會(huì)訂閱新的用戶(hù)，也會(huì)取消對(duì)已關(guān)注用戶(hù)的訂閱.另一方面，社交網(wǎng)絡(luò)服務(wù)成功地降低了用戶(hù)創(chuàng)建和發(fā)布信息的成本.每個(gè)用戶(hù)既可以發(fā)布個(gè)人原創(chuàng)信息，也可以分享好友的觀點(diǎn)，這些發(fā)布與分享行為產(chǎn)生的數(shù)據(jù)構(gòu)成了社交媒體的信息流，同時(shí)所有用戶(hù)的信息流按照時(shí)間序合并之后，又構(gòu)成了全局的信息流.因此，本文的數(shù)據(jù)流模型將主要基于社交網(wǎng)絡(luò)的圖數(shù)據(jù)流和用戶(hù)生成數(shù)據(jù)流.

圖1描述了4個(gè)用戶(hù)的個(gè)人社交媒體流以及每個(gè)流之間的交互關(guān)系，所有消息從左到右，從上到下就構(gòu)成了全局的社交媒體流.圖中左端用戶(hù)間的連線表示在消息m1，1發(fā)布之時(shí)用戶(hù)之間的訂閱關(guān)系；如用戶(hù)2和用戶(hù)3均訂閱了用戶(hù)1，同時(shí)用戶(hù)4訂閱了用戶(hù)3.在右端的信息流中，空心的菱形表示用戶(hù)發(fā)出的消息，而實(shí)心的菱形則表示用戶(hù)分享他人的消息；如圖中用戶(hù)1發(fā)布了3條原創(chuàng)消息，用戶(hù)2和用戶(hù)3都分享了用戶(hù)1的第一條原創(chuàng)消息.另外，星形表示的是用戶(hù)間的訂閱關(guān)系，空心表示訂閱，實(shí)心則表示取消訂閱；如圖中用戶(hù)3訂閱了用戶(hù)1，用戶(hù)4對(duì)用戶(hù)1取消訂閱.

圖1 社交媒體流數(shù)據(jù)Fig.1 Social stream

新浪微博將用戶(hù)之間的關(guān)系定義為關(guān)注關(guān)系：若用戶(hù)1訂閱了用戶(hù)2，則表示用戶(hù)1關(guān)注了用戶(hù)2，相反則為取消關(guān)注.用戶(hù)發(fā)布的內(nèi)容以微博的形式存在，微博可以用特定的標(biāo)記來(lái)關(guān)聯(lián)用戶(hù)和話題，并且可以被其他用戶(hù)轉(zhuǎn)發(fā).本基準(zhǔn)評(píng)測(cè)完全基于新浪微博數(shù)據(jù)，其標(biāo)準(zhǔn)的輸入主要由以下6個(gè)流組成：

（1）Tweet（type＝Tweet，uid，mid，time，location，content）：構(gòu)成該數(shù)據(jù)流的元素是用戶(hù)uid發(fā)出的一條標(biāo)識(shí)符為mid的微博.其中time為該微博發(fā)出時(shí)間，location為用戶(hù)所在地域，content為微博內(nèi)容.

（2）Retweet（type＝Retweet，uid，mid，remid，recontent，time）：該數(shù)據(jù)流表示用戶(hù)uid轉(zhuǎn)發(fā)一條標(biāo)識(shí)符為mid的微博，被轉(zhuǎn)發(fā)的原始微博的標(biāo)識(shí)符為remid.其中time為轉(zhuǎn)發(fā)的時(shí)間，recontent為轉(zhuǎn)發(fā)內(nèi)容.

（3）Topic（type＝Topic，topicname，mid，uid，time）：該數(shù)據(jù)流表示用戶(hù)uid通過(guò)發(fā)布微博mid參與了話題topicname的討論，其中time為uid參與話題討論的時(shí)間.

（4）Follow （type＝Follow，uid1，uid2，time）：該數(shù)據(jù)流記錄了用戶(hù)的關(guān)注行為，本條記錄表示用戶(hù)uid1在時(shí)間time關(guān)注了用戶(hù)uid2.

（5）UnFollow（type＝UnFollow，uid1，uid2，time）：該數(shù)據(jù)流記錄表示用戶(hù)uid1在時(shí)間time取消了對(duì)用戶(hù)uid2的關(guān)注.

（6）Login（type＝Login，uid，time）：該數(shù)據(jù)流表示用戶(hù)uid在時(shí)間time登錄了新浪微博.

為了方便查詢(xún)的定義，我們額外定義了一張關(guān)系表followship（見(jiàn)表1），它用于表示某個(gè)時(shí)刻用戶(hù)之間的關(guān)注網(wǎng)絡(luò).

表1 用戶(hù)關(guān)系表Tab.1 The schema of social network

盡管數(shù)據(jù)模型中包含流數(shù)據(jù)和關(guān)系數(shù)據(jù)表，本基準(zhǔn)不限制系統(tǒng)采用的數(shù)據(jù)模型和數(shù)據(jù)管理系統(tǒng)，即，該基準(zhǔn)可用于探測(cè)流數(shù)據(jù)管理系統(tǒng).關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)以及基于其他專(zhuān)用系統(tǒng).

1.2 數(shù)據(jù)的爬取及預(yù)處理

爬蟲(chóng)程序運(yùn)用新浪提供的API，用以爬取社交網(wǎng)絡(luò)信息、微博信息及微博用戶(hù)信息.圖2為數(shù)據(jù)爬取過(guò)程示意圖，其中種子用戶(hù)中包含了32個(gè)熱點(diǎn)用戶(hù)，爬蟲(chóng)采用寬度優(yōu)先遍歷的方式，從種子用戶(hù)出發(fā)沿著關(guān)注邊遍歷3層.圖示中前3層用戶(hù)共包含約170萬(wàn)個(gè)用戶(hù)，被稱(chēng)為核心用戶(hù)；在核心用戶(hù)確定之后，程度開(kāi)始爬取這批用戶(hù)的在線社交網(wǎng)絡(luò)以及發(fā)布的微博數(shù)據(jù)［6］.

圖2 數(shù)據(jù)爬取流程示意圖Fig.2 Figure of data crawling process

隨后爬蟲(chóng)程序周期性地更新整個(gè)數(shù)據(jù)集，爬取核心用戶(hù)的社交網(wǎng)絡(luò)關(guān)系變更以及發(fā)表的微博.在最終爬取的社交網(wǎng)絡(luò)數(shù)據(jù)集中包含了大約12億條關(guān)注關(guān)系，含從2009年8月至2012年12月時(shí)間內(nèi)用戶(hù)發(fā)布的微博數(shù)量約6億4千萬(wàn)條.

數(shù)據(jù)集以文本形式保存，其中每行數(shù)據(jù)對(duì)應(yīng)一條社交媒體流中的一條記錄，數(shù)據(jù)記錄按照時(shí)間增序排列.數(shù)據(jù)集基于爬取的微博數(shù)據(jù)執(zhí)行了以下的預(yù)處理數(shù)據(jù)操作：

（1）轉(zhuǎn)發(fā)鏈重構(gòu)：由于微博API返回的微博數(shù)據(jù)只顯示被轉(zhuǎn)發(fā)的原始微博信息，而從原始微博到當(dāng)前微博的轉(zhuǎn)發(fā)關(guān)系則體現(xiàn)在當(dāng)前微博的內(nèi)容當(dāng)中.因此，通過(guò)一個(gè)基于Map Reduce框架的分布式數(shù)據(jù)轉(zhuǎn)發(fā)程序，以原始微博為鍵值，在reduce過(guò)程中對(duì)轉(zhuǎn)發(fā)同一條微博的微博數(shù)據(jù)重構(gòu)出轉(zhuǎn)發(fā)鏈.

（2）數(shù)據(jù)匿名化：由于微博數(shù)據(jù)使用的限制以及可能存在的個(gè)人隱私保護(hù)問(wèn)題，所有數(shù)據(jù)均做了匿名化處理.這一步主要包括對(duì)用戶(hù)信息和微博內(nèi)容的匿名化，對(duì)于微博內(nèi)容，保留了微博話題信息以及話題相關(guān)的詞條.

2 連續(xù)查詢(xún)負(fù)載與評(píng)測(cè)標(biāo)準(zhǔn)

本節(jié)基于上節(jié)提出的數(shù)據(jù)模型，根據(jù)實(shí)際應(yīng)用場(chǎng)景抽象一組查詢(xún)，并提出相應(yīng)的性能評(píng)測(cè)標(biāo)準(zhǔn).

2.1 連續(xù)查詢(xún)負(fù)載

社交媒體數(shù)據(jù)本質(zhì)上由多個(gè)流數(shù)據(jù)構(gòu)成，因而能夠很好地支持許多社交媒體上的應(yīng)用.例如，針對(duì)個(gè)人用戶(hù)，常用的應(yīng)用包括未讀微博、熱門(mén)微博及熱門(mén)話題的提醒功能；基于微博管理系統(tǒng)維護(hù)的角度，發(fā)現(xiàn)發(fā)布微博行為異常的用戶(hù).此外，基于已有的數(shù)據(jù)流被轉(zhuǎn)換之后，可以為更復(fù)雜的任務(wù)生成流數(shù)據(jù)作為輸入.例如，在基于圖數(shù)據(jù)流的實(shí)時(shí)在線社區(qū)或者事件發(fā)現(xiàn)應(yīng)用中，需要獲取用戶(hù)的交互流，流中每條元素由某段時(shí)間內(nèi)用戶(hù)交互頻率超過(guò)某個(gè)閾值的用戶(hù)交互邊構(gòu)成.本基準(zhǔn)測(cè)試從實(shí)際應(yīng)用出發(fā)定義了一組查詢(xún)，它們涵蓋了參與到流數(shù)據(jù)中的各個(gè)角色，以及各種實(shí)際應(yīng)用場(chǎng)景.

由于流數(shù)據(jù)引入了時(shí)間維度，關(guān)系數(shù)據(jù)查詢(xún)語(yǔ)言SQL無(wú)法直接用于表示流數(shù)據(jù)上的查詢(xún)，文獻(xiàn)［7－9］通過(guò)擴(kuò)展SQL語(yǔ)言的語(yǔ)義來(lái)定義流數(shù)據(jù)上的查詢(xún)語(yǔ)言.其中Standford針對(duì)流數(shù)據(jù)處理缺乏明確語(yǔ)義的統(tǒng)一的查詢(xún)語(yǔ)言，提出了用于連續(xù)查詢(xún)的抽象語(yǔ)義，并且設(shè)計(jì)了CQL［7］（continous query languange）來(lái)實(shí)現(xiàn)這些抽象語(yǔ)義.CQL定義了關(guān)系到關(guān)系、關(guān)系到數(shù)據(jù)流以及數(shù)據(jù)流到關(guān)系間的轉(zhuǎn)換.它通過(guò)使用查詢(xún)窗口的概念，將流數(shù)據(jù)映射成相應(yīng)的關(guān)系數(shù)據(jù).通過(guò)引入Istream，Dstream，Rstream3個(gè)操作，CQL能將關(guān)系數(shù)據(jù)轉(zhuǎn)換成流數(shù)據(jù).最后，通過(guò)重用關(guān)系查詢(xún)語(yǔ)言SQL中對(duì)關(guān)系操作的語(yǔ)義，它能夠表示不同關(guān)系之間的查詢(xún)，例如聚合查詢(xún)、子查詢(xún)以及連接等.

為了表達(dá)準(zhǔn)確的語(yǔ)義，本基準(zhǔn)測(cè)試將主要使用CQL語(yǔ)言表示基準(zhǔn)測(cè)試中使用的查詢(xún)，但不強(qiáng)制被測(cè)試的流數(shù)據(jù)管理系統(tǒng)支持CQL語(yǔ)言，用戶(hù)只需要針對(duì)每條查詢(xún)提供正確的實(shí)現(xiàn).基準(zhǔn)測(cè)試中包含的查詢(xún)主要分為3類(lèi)：熱點(diǎn)查詢(xún)，實(shí)時(shí)查詢(xún)，混合查詢(xún)，接下來(lái)將詳細(xì)介紹這3類(lèi)查詢(xún).

（1）熱點(diǎn)查詢(xún)

在新浪微博中，熱點(diǎn)指的是在某個(gè)特定的時(shí)間范圍內(nèi)微博平臺(tái)中滿(mǎn)足某些過(guò)濾條件且統(tǒng)計(jì)值最大的某類(lèi)元素集合.這里的元素可以是用戶(hù)、微博或話題，這些分別稱(chēng)為熱點(diǎn)用戶(hù)、熱門(mén)微博或熱門(mén)話題.

熱點(diǎn)查詢(xún)（Hot Spot Query，HSQ）是查詢(xún)當(dāng)前時(shí)間點(diǎn)Ta到之前的一個(gè)時(shí)間點(diǎn)Tb間具體元素的內(nèi)容.在連續(xù)查詢(xún)中，這樣一個(gè)時(shí)間段被稱(chēng)為一個(gè)窗口（WINDOW），窗口的大小即是時(shí)間段的長(zhǎng)短.一個(gè)熱點(diǎn)查詢(xún)可以用來(lái)回答類(lèi)似“近期內(nèi)微博被大量轉(zhuǎn)發(fā)的用戶(hù)”等類(lèi)似的問(wèn)題.

舉一個(gè)簡(jiǎn)單的實(shí)例，查詢(xún)“上海地區(qū)1小時(shí)內(nèi)被轉(zhuǎn)發(fā)的微博數(shù)量前十名的用戶(hù)”，用CQL語(yǔ)言描述如下：

Select Count（Tweet.uid）From Tweet［Range 1 Hour］

Where Tweet.location＝“上?！?/p>

Order by Count（Tweet.uid）Desc

Limit 10

上述查詢(xún)只截取Tweet一個(gè)數(shù)據(jù)流，過(guò)濾Tweet流的Location屬性，為數(shù)據(jù)流Tweet開(kāi)了一個(gè)時(shí)長(zhǎng)為1小時(shí)的窗口，并從這個(gè)窗口中查詢(xún)最活躍的Top10的用戶(hù)，即返回?cái)?shù)據(jù)流到達(dá)的時(shí)間點(diǎn)往前一個(gè)小時(shí)內(nèi)最活躍的Top10的用戶(hù).

該熱點(diǎn)查詢(xún)?yōu)閱螌傩缘臒狳c(diǎn)查詢(xún)，僅包含一個(gè)過(guò)濾條件.在更復(fù)雜的熱點(diǎn)查詢(xún)中，過(guò)濾的屬性往往不止一個(gè)，且數(shù)據(jù)流之間需要進(jìn)行連接，同時(shí)也可以包含子查詢(xún).對(duì)多屬性的熱

點(diǎn)查詢(xún)舉例如下：查詢(xún)“一小時(shí)內(nèi)上海用戶(hù)對(duì)‘爸爸去哪兒第二季收視率’討論的熱烈程度”.該查詢(xún)用CQL語(yǔ)言可以描述如下：

Select Count（Tweet.uid）

From Tweet［Range 1 Hour］，Topic［Range 1 Hour］

Where Tweet.location＝“上海”and Tweet.mid＝Topic.mid

and Topic.topicname＝“爸爸去哪兒第二季收視率”

上述查詢(xún)同時(shí)截取Tweet和Topic兩條數(shù)據(jù)流，過(guò)濾多個(gè)屬性并返回Tweet流中用戶(hù)的總數(shù)來(lái)反應(yīng)對(duì)“爸爸去哪兒第二季”收視率討論的熱烈程度.

（2）實(shí)時(shí)查詢(xún)

實(shí)時(shí)查詢(xún)（Realtime Query，RQ）關(guān)注的是當(dāng)前時(shí)間點(diǎn)的信息，查詢(xún)的是當(dāng)前時(shí)間點(diǎn)微博平臺(tái)中滿(mǎn)足某些過(guò)濾條件的元素.不同于熱點(diǎn)查詢(xún)是，實(shí)時(shí)查詢(xún)是絕對(duì)連續(xù)的，查詢(xún)當(dāng)前時(shí)間點(diǎn)的內(nèi)容.實(shí)時(shí)查詢(xún)一般用來(lái)回答“當(dāng)前正在討論某話題的用戶(hù)”等類(lèi)似的問(wèn)題.

下面給出一個(gè)實(shí)時(shí)查詢(xún)的具體實(shí)例.查詢(xún)“微博內(nèi)容包含了‘爸爸去哪兒第二季’的微博內(nèi)容”，用CQL語(yǔ)言描述如下：

Select Istream（Tweet.content）

From Tweet［Now］

Where contains（Tweet.content，“爸爸去哪兒第二季”）上述查詢(xún)中，查詢(xún)實(shí)時(shí)截取Tweet流中content元素，并對(duì)其進(jìn)行過(guò)濾，Now標(biāo)簽是實(shí)時(shí)查詢(xún)的特征，表示查詢(xún)的窗口為當(dāng)前時(shí)間，而不再是一個(gè)給定的范圍，Istream（Tweet.content）則表示返回查詢(xún)結(jié)果也是一個(gè)數(shù)據(jù)流.

（3）混合查詢(xún)

混合查詢(xún)（Mix Query，MQ）同時(shí)包括熱點(diǎn)查詢(xún)和實(shí)時(shí)查詢(xún)，查詢(xún)的元素既包含當(dāng)前時(shí)間點(diǎn)滿(mǎn)足過(guò)濾內(nèi)容的元素，同時(shí)也包含當(dāng)前時(shí)間點(diǎn)的前一個(gè)時(shí)間段內(nèi)滿(mǎn)足過(guò)濾條件的元素.

混合查詢(xún)可以用來(lái)回答更多更復(fù)雜的問(wèn)題，下面給出一個(gè)混合查詢(xún)的具體實(shí)例.查詢(xún)“在1小時(shí)內(nèi)上海地區(qū)轉(zhuǎn)發(fā)內(nèi)容包含‘爸爸去哪兒第二季’的微博”.該查詢(xún)用CQL描述如下：

Select Istream（Retweet.＊）

From Retweet［Now］，Tweet［Range 1 Hour］

Where contains（Tweet.content.，“爸爸去哪兒第二季”）

and Retweet.remid＝Tweet.mid and Tweet.location＝“上?！鄙鲜霾樵?xún)中，對(duì)Retweet流，關(guān)注的是實(shí)時(shí)的信息，而對(duì)Tweet流，關(guān)注的是一個(gè)小時(shí)內(nèi)的所有信息.返回的數(shù)據(jù)是一個(gè)符合所有過(guò)濾條件的Retweet流.

（4）具體查詢(xún)描述

綜合考慮6種輸入流及3種查詢(xún)，基準(zhǔn)評(píng)測(cè)共提供了10個(gè)查詢(xún)，查詢(xún)的CQL語(yǔ)言表述見(jiàn)附錄.表2描述了這些查詢(xún)的查詢(xún)編號(hào)、查詢(xún)描述和查詢(xún)類(lèi)型.

上述查詢(xún)中，查詢(xún)1，2，3，4，8，9，10為熱點(diǎn)查詢(xún)，查詢(xún)5為實(shí)時(shí)查詢(xún)，查詢(xún)6，7為混合查詢(xún).

表2 查詢(xún)描述Tab.2 Description of queries

熱點(diǎn)查詢(xún)?cè)谖⒉?yīng)用中運(yùn)用較為廣泛，查詢(xún)結(jié)果可用作微博數(shù)據(jù)的統(tǒng)計(jì)，也可實(shí)現(xiàn)對(duì)熱點(diǎn)微博的監(jiān)控.其中查詢(xún)1，2，3，4為簡(jiǎn)單的微博熱點(diǎn)監(jiān)控查詢(xún)，其查詢(xún)邏輯較為簡(jiǎn)單，查詢(xún)1是對(duì)單個(gè)數(shù)據(jù)流進(jìn)行查詢(xún)，查詢(xún)2，3，4分別是對(duì)不同的數(shù)據(jù)流進(jìn)行交叉的查詢(xún)，其過(guò)濾條件也有多個(gè).查詢(xún)8，9，10為的微博熱點(diǎn)監(jiān)控查詢(xún)，查詢(xún)針對(duì)數(shù)據(jù)流中的所有用戶(hù)，邏輯較為復(fù)雜.其中查詢(xún)8，9是針對(duì)個(gè)人用戶(hù)的查詢(xún)，查詢(xún)8為用戶(hù)的未讀微博提醒功能，查詢(xún)了用戶(hù)上次登錄之后新發(fā)布的微博數(shù)，在實(shí)際應(yīng)用系統(tǒng)中，若未讀微博數(shù)超過(guò)一定閾值，則向用戶(hù)發(fā)出未讀微博提醒.同樣，查詢(xún)9查詢(xún)用戶(hù)上次登錄之后好友圈內(nèi)討論數(shù)量超過(guò)閾值的話題.查詢(xún)10查詢(xún)近期交互頻繁的用戶(hù)組，可用于基于圖數(shù)據(jù)流的實(shí)時(shí)事件發(fā)現(xiàn).

實(shí)時(shí)查詢(xún)主要用于對(duì)微博的實(shí)時(shí)監(jiān)控.通過(guò)實(shí)時(shí)查詢(xún)，可以過(guò)濾數(shù)據(jù)流中不感興趣的信息，僅獲取想要監(jiān)控的數(shù)據(jù).如查詢(xún)5即為從所有Tweet流中過(guò)濾出參與話題T討論的微博.由于實(shí)時(shí)查詢(xún)?cè)眍?lèi)似，這里僅給出一條多數(shù)據(jù)流交叉的實(shí)時(shí)查詢(xún).

混合查詢(xún)同樣主要用于對(duì)微博的實(shí)時(shí)監(jiān)控，但其過(guò)濾條件更為復(fù)雜，過(guò)濾時(shí)要和當(dāng)前數(shù)據(jù)流的前一個(gè)時(shí)間段的所有數(shù)據(jù)進(jìn)行交叉過(guò)濾.查詢(xún)6是普通的混合查詢(xún)，監(jiān)控的是Retweet流，查詢(xún)一段時(shí)間之內(nèi)被轉(zhuǎn)發(fā)的由用戶(hù)A原創(chuàng)的微博.查詢(xún)7為嵌套的混合查詢(xún).

（5）查詢(xún)參數(shù)說(shuō)明

查詢(xún)中共有以下4個(gè)可變參數(shù)：用戶(hù)、話題、地區(qū)和時(shí)間.下面對(duì)這4個(gè)參數(shù)的取值做詳細(xì)說(shuō)明.

（1）用戶(hù)：根據(jù)用戶(hù)當(dāng)前的好友數(shù)成正比的概率作選擇，即每個(gè)用戶(hù)被選擇的概率與其好友個(gè)數(shù)成正比.

（2）話題：根據(jù)測(cè)試點(diǎn)之前的24小時(shí)內(nèi)話題的討論微博數(shù)來(lái)作選擇.

（3）地區(qū)：根據(jù)數(shù)據(jù)集中每個(gè)地區(qū)所發(fā)布的微博數(shù)來(lái)作選擇.

（4）時(shí)間：查詢(xún)中的時(shí)間在每條查詢(xún)相應(yīng)的時(shí)間區(qū)間內(nèi)隨機(jī)選擇.

2.2 性能測(cè)試配置

性能測(cè)試的配置主要包含以下3個(gè)參數(shù)：測(cè)試點(diǎn)、操作數(shù)和查詢(xún)比.

（1）測(cè)試點(diǎn)：測(cè)試點(diǎn)設(shè)置的是在測(cè)試過(guò)程中開(kāi)始執(zhí)行測(cè)試時(shí)流的位置，用戶(hù)可以設(shè)置多個(gè)測(cè)試點(diǎn).例如它的默認(rèn)設(shè)置包含100 000，1 000 000，10 000 000等，即當(dāng)?shù)?00 000，1 000 000，10 000 000個(gè)流元素到來(lái)時(shí)開(kāi)始執(zhí)行測(cè)試.

（2）操作數(shù)：操作數(shù)設(shè)置的是在所有測(cè)試點(diǎn)的測(cè)試過(guò)程中執(zhí)行查詢(xún)的總條數(shù)，默認(rèn)設(shè)置為1 000.

（3）查詢(xún)比：查詢(xún)比設(shè)置的是在測(cè)試過(guò)程中10個(gè)查詢(xún)執(zhí)行次數(shù)的占比情況，默認(rèn)設(shè)置下所有查詢(xún)的占比情況是相等的.

2.3 性能測(cè)試指標(biāo)

對(duì)流數(shù)據(jù)的查詢(xún)都是連續(xù)的，因此，基于關(guān)系數(shù)據(jù)庫(kù)的性能評(píng)測(cè)指標(biāo)，如“查詢(xún)完成時(shí)間”等指標(biāo)則不適用于流數(shù)據(jù)管理系統(tǒng).為了測(cè)試不同的流數(shù)據(jù)管理系統(tǒng)對(duì)社交媒體數(shù)據(jù)流的性能，基準(zhǔn)測(cè)試制定了如下性能測(cè)試指標(biāo).

數(shù)據(jù)延遲時(shí)間：假定在t1時(shí)間到達(dá)的數(shù)據(jù)，而被查詢(xún)到的時(shí)間為t2，數(shù)據(jù)延遲時(shí)間t＝t2－t1.該屬性越小，則說(shuō)明系統(tǒng)性能越好.

數(shù)據(jù)處理吞吐量：在滿(mǎn)足指定的數(shù)據(jù)延遲時(shí)間約束的要求下，系統(tǒng)處理數(shù)據(jù)流的速度定義為數(shù)據(jù)處理吞吐量.該屬性越大，則說(shuō)明系統(tǒng)性能越好.

數(shù)據(jù)可擴(kuò)展性：被測(cè)系統(tǒng)在不同的測(cè)試點(diǎn)已處理的數(shù)據(jù)量不同，對(duì)由數(shù)據(jù)量和吞吐值構(gòu)成的點(diǎn)計(jì)算其斜率.該斜率表示為數(shù)據(jù)可擴(kuò)展性，該屬性越大，則說(shuō)明系統(tǒng)受數(shù)據(jù)量的影響越小.

其中，數(shù)據(jù)延遲時(shí)間反映的是系統(tǒng)對(duì)查詢(xún)處理的速度，不同的系統(tǒng)在處理不同的社交數(shù)據(jù)流查詢(xún)時(shí)，對(duì)查詢(xún)結(jié)果的響應(yīng)時(shí)間都不相同，數(shù)據(jù)延遲時(shí)間通過(guò)計(jì)算查詢(xún)結(jié)果到達(dá)時(shí)間與數(shù)據(jù)流輸入時(shí)間的差值，來(lái)體現(xiàn)系統(tǒng)的延遲，該時(shí)間差值越小，則系統(tǒng)對(duì)查詢(xún)的響應(yīng)數(shù)據(jù)越快，數(shù)據(jù)延遲度越低，系統(tǒng)對(duì)該查詢(xún)的處理性能則更好.

數(shù)據(jù)處理吞吐量反映的是系統(tǒng)在固定時(shí)間內(nèi)處理的流數(shù)據(jù)量的多少，針對(duì)一個(gè)具體的查詢(xún)，該值越大，則說(shuō)明在給定的時(shí)間內(nèi)，系統(tǒng)能成功處理越多量的輸入流，系統(tǒng)對(duì)該查詢(xún)的處理性能越好.在這里，成功的處理指系統(tǒng)接收輸入流并在滿(mǎn)足數(shù)據(jù)延遲時(shí)間約束的前提下返回查詢(xún)結(jié)果.因此數(shù)據(jù)處理吞吐量能夠體現(xiàn)系統(tǒng)在滿(mǎn)足服務(wù)要求的前提下，系統(tǒng)抗擊數(shù)據(jù)流到達(dá)峰值的能力，例如平緩地處理突發(fā)事件導(dǎo)致的短時(shí)間內(nèi)發(fā)布的大量微博.

數(shù)據(jù)處理吞吐量可用下述值表示：

其中，size為基準(zhǔn)測(cè)試發(fā)出的數(shù)據(jù)流元素的個(gè)數(shù)；Q（i）為查詢(xún)i在大小為size時(shí)發(fā)起的測(cè)試獲得的吞吐量；R（j）為第j個(gè)流的更新速率，即執(zhí)行一次測(cè)試操作的時(shí)間內(nèi)更新的元素個(gè)數(shù).

數(shù)據(jù)可擴(kuò)展性反映的是系統(tǒng)對(duì)數(shù)據(jù)量的適應(yīng)程度，它是由以數(shù)據(jù)量和吞吐量構(gòu)成的點(diǎn)的斜率來(lái)表示.根據(jù)該值能夠體現(xiàn)系統(tǒng)隨著被處理數(shù)據(jù)集的規(guī)模增大的情況下，系統(tǒng)性能的變化趨勢(shì).

3 總 結(jié)

本文提出了一個(gè)面向社交數(shù)據(jù)流連續(xù)查詢(xún)的基準(zhǔn)評(píng)測(cè).本基準(zhǔn)測(cè)試是基于新浪微博的數(shù)據(jù)構(gòu)建而成，首先介紹數(shù)據(jù)的爬取及預(yù)處理，定義了最終的輸入數(shù)據(jù)流模型.其次基于輸入數(shù)據(jù)流的特點(diǎn)，定義了基準(zhǔn)評(píng)測(cè)的連續(xù)查詢(xún)負(fù)載，定義了3類(lèi)查詢(xún).最后，制定了性能測(cè)試指標(biāo)，用以測(cè)試不同的流數(shù)據(jù)管理系統(tǒng)在社交數(shù)據(jù)流連續(xù)查詢(xún)上的表現(xiàn).本文的工作對(duì)社交數(shù)據(jù)流處理應(yīng)用的系統(tǒng)選型、相關(guān)查詢(xún)處理技術(shù)性能比較具有重要意義.未來(lái)工作將進(jìn)一步補(bǔ)充各類(lèi)查詢(xún)，尤其是基于社交流數(shù)據(jù)上的數(shù)據(jù)挖掘類(lèi)查詢(xún).

［1］ ABADI D，CARNEY D，CETINTEMEL U，et al.Aurora：A new model and architecture for data stream management［J］.VLDB Journal，2003，12（3）：120－139.

［2］ CHANDRASEKARAN S，COOPER O，DESHPANDE A，et al.Telegraphcq：Continuous dataflow processing for an uncertain world［C］／／Proceedings of the 1st Biennial Conference on Innovative Database Research（CIDR）.Asilomar，CA：［s.n.］，2003.

［3］ MOTWANI R，WIDOM J，ARASU A，et al.Query processing，resource management，and approximation in a data stream management system［C］／／Proceedings of the 1st Biennial Conference on Innovative Database Research（CIDR）.Asilomar，CA：［s.n.］，2003.

［4］ ARASU A，CHERNIACK M，GALVEZ E，et al.Linear road：a stream data management benchmark［C］／／Proceedings of the Thirtieth International Conference on Very Large Data Bases.VLDB Endowment，2004，30：480－491.

［5］ MA H，WEI J，QIAN W，et al.On benchmarking online social media analytical queries［C］／／First International Workshop on Graph Data Management Experiences and Systems.ACM，2013：10.

［6］ MA H，QIAN W，XIA F，et al.Towards modeling popularity of microblogs［J］.Frontiers of Computer Science，2013，7（2）：171－184.

［7］ ARASU A，BABU S，WIDOM J.CQL：A language for continuous queries over streams and relations［C］／／Database Programming Languages.Berlin：Springer，2004：1－19.

［8］ JAIN N，MISHRA S，SRINIVASAN A，et al.Towards a streaming SQL standard［J］.Proceedings of the VLDB Endowment，2008，1（2）：1379－1390.

［9］ ARMBRUST M，CURTIS K，KRASKA T，et al.PIQL：success－tolerant query processing in the cloud［J］.Proc VLDB Endow，2011，5（3）：181－192.

附 錄

連續(xù)查詢(xún)

· 查詢(xún)1.最近一段時(shí)間的熱門(mén)話題

selectInstream（topicname）from

topic［range MYMHMYM hour］

group by topicname

having count（＊）＞10000；

· 查詢(xún)2.最近一段時(shí)間微博被大量轉(zhuǎn)發(fā)的用戶(hù)：

Select tweet.uid，count（＊）as num

from retweet［Range MYMHMYM Hour］，tweet［Range MYMHMYM Hour］whereretweet.remid＝tweet.mid

group by tweet.uid

order by numdesc；

· 查詢(xún)3.用戶(hù)A的好友圈內(nèi)最近一段時(shí)間的熱門(mén)話題：

Select topicname，count（＊）as num

from topic［range MYMHMYM hour］，followship

wherefollowship.uid＝“A”and topic.uid＝followship.foluid

order by numdesc；

· 查詢(xún)4.最近一段時(shí)間對(duì)地區(qū)L話題T的討論的熱烈程度：

Select Count（Tweet.uid）

From Tweet［Range MYMHMYM Hour］，Topic［Range MYMHMYM Hour］

Where Tweet.location＝L and Tweet.mid＝Topic.mid

andTopic.topicname＝“T”

· 查詢(xún)5.參與話題T討論的微博

Select Istream（Tweet）

From Tweet［Now］，Topic

Where Tweet.mid＝Topic.mid and Topic.name＝“T”

· 查詢(xún)6.用戶(hù)A一段時(shí)間內(nèi)被轉(zhuǎn)發(fā)的微博

Select Istream（Retweet.＊）

From Retweet［Now］，Tweet［Range MYMHMYM Hour］

Where Tweet.uid＝“A”andRetweet.remid＝Tweet.mid

· 查詢(xún)7.用戶(hù)A一段時(shí)間內(nèi)關(guān)注的好友中，查詢(xún)參與話題T討論的微博

Select Istream（Tweet）

From Tweet［Now］

Where Tweet.mid＝Topic.mid and Topic.name＝“T”

andTweet.uidin（Select Follow.uid2

From Follow［Range MYMHMYM Hour］Where Follow.uid1＝“A”）

· 查詢(xún)8.所有用戶(hù)的未讀微博提醒查詢(xún)

Select Istream（Login.uid），count（＊）as unread

From friendlist，Tweet［Range MYMHMYM Hour］，Login［Partition By uid Rows 1］as unlogin

Where friendlist.uid＝unlogin.uid and friendlist.followee＝tweet.uid

Group by Login.uid

Having unread＞N

· 查詢(xún)9.所有用戶(hù)的熱門(mén)話題提醒查詢(xún)

Select Istream（Login.uid），count（＊）as unread

From friendlist，Topic［Range MYMHMYM Hour］，Login［Partition By uid Rows 1］as unlogin

Where friendlist.uid＝unlogin.uid and friendlist.followee＝Topic.uid

Group by Login.uid

Having unread＞N

· 查詢(xún)10.交互頻率超過(guò)某個(gè)閾值的用戶(hù)組

Select Instream（Retweet.uid，Tweet.uid），count（＊）as Interact

From Retweet［Range MYMHMYM Hour］，Tweet［Range 48 Hour］

Where Retweet.remid＝Tweet.mid

Gourp by（Retweet.uid，Tweet.uid）

Having Interact＞N