新型數(shù)據(jù)管理系統(tǒng)研究進(jìn)展與趨勢*

崔 斌,高 軍,童詠昕,許建秋,張東祥,鄒 磊

1(北京大學(xué) 信息科學(xué)技術(shù)學(xué)院,北京 100871)

2(軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室(北京航空航天大學(xué)),北京 100083)

3(南京航空航天大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇 南京 211106)

4(電子科技大學(xué) 計算機(jī)科學(xué)與工程學(xué)院,四川 成都 611731)

5(北京大學(xué) 計算機(jī)科學(xué)技術(shù)研究所,北京 100871)

21世紀(jì)以來,隨著計算機(jī)技術(shù),尤其是互聯(lián)網(wǎng)和移動計算技術(shù)的發(fā)展,大量新型應(yīng)用應(yīng)運(yùn)而生.這些應(yīng)用不僅對人類的日常生活、社會的組織結(jié)構(gòu)以及生產(chǎn)關(guān)系形態(tài)和生產(chǎn)力發(fā)展水平產(chǎn)生了深刻的影響,也使得人們能夠獲取的數(shù)據(jù)規(guī)模呈爆炸性增長.“大數(shù)據(jù)”這一詞匯被發(fā)明出來,用以概括這種態(tài)勢.

目前廣泛認(rèn)為大數(shù)據(jù)具有所謂的“4V”特征,即規(guī)模大(volume)、變化快(velocity)、種類雜(variety)和價值密度低(value).為了有效地應(yīng)對大數(shù)據(jù)的上述“4V”特征,各類新型數(shù)據(jù)管理系統(tǒng)也逐漸涌現(xiàn)出來.表1中我們列舉了部分典型的新型數(shù)據(jù)管理系統(tǒng).

Table 1 Category of novel data management systems表1 新型數(shù)據(jù)管理系統(tǒng)分類

數(shù)據(jù)規(guī)模大在諸多數(shù)據(jù)處理場景中都有所體現(xiàn).例如社交媒體應(yīng)用中的用戶關(guān)系數(shù)據(jù),若用圖數(shù)據(jù)模型進(jìn)行建模,其涉及的節(jié)點(diǎn)數(shù)可高達(dá)幾億.為了處理這類大規(guī)模的數(shù)據(jù),一個樸素的想法是分而治之,即,將數(shù)據(jù)分布式地存儲在多臺機(jī)器上分別處理.據(jù)此,人們提出了各類分布式數(shù)據(jù)管理系統(tǒng).

數(shù)據(jù)變化快這一特征具體體現(xiàn)在數(shù)據(jù)實(shí)時到達(dá)、規(guī)模龐大、大小無法提前預(yù)知,并且數(shù)據(jù)一經(jīng)處理,除非進(jìn)行存儲,否則很難再次獲取.在金融應(yīng)用、網(wǎng)絡(luò)監(jiān)控、社交媒體等諸多行業(yè)領(lǐng)域,都會產(chǎn)生這類變化極快的數(shù)據(jù).為了解決這一問題,人們提出了流數(shù)據(jù)處理系統(tǒng).

針對數(shù)據(jù)種類雜的特征,人們采取“各個擊破”的手段,針對各類數(shù)據(jù)分別提出專門的數(shù)據(jù)管理系統(tǒng),圖數(shù)據(jù)管理系統(tǒng)和時空數(shù)據(jù)管理系統(tǒng)是典型代表.圖數(shù)據(jù)模型是一種具有高度概括性的數(shù)據(jù)模型,其典型應(yīng)用包括社交媒體數(shù)據(jù)的建模和知識圖譜等.時空數(shù)據(jù)在人們的日常生活中也十分常見,例如各類地圖應(yīng)用在提供導(dǎo)航服務(wù)時,都需要對大量的時空數(shù)據(jù)進(jìn)行高效的處理.

大數(shù)據(jù)的價值密度通常較低,例如社交媒體中大量的圖片數(shù)據(jù)在未經(jīng)標(biāo)注之前,并不具備顯著的價值.眾包正是解決該問題的有效手段之一.眾包通常是指“一種把過去由專職員工執(zhí)行的工作任務(wù)通過公開的Web平臺以自愿的形式外包給非特定的解決方案提供者群體來完成的分布式問題求解模式”,是完成大規(guī)模的對計算機(jī)較為困難而對人類相對容易的任務(wù)的有效手段,例如數(shù)據(jù)標(biāo)注.為了有效地對眾包過程中的數(shù)據(jù)和眾包參與者群體進(jìn)行有效管理,人們提出了眾包數(shù)據(jù)管理系統(tǒng).

如表1所示,我們可以看到:人們已經(jīng)提出了分布式數(shù)據(jù)管理系統(tǒng)、圖數(shù)據(jù)管理系統(tǒng)、流數(shù)據(jù)管理系統(tǒng)、時空數(shù)據(jù)管理系統(tǒng)和眾包數(shù)據(jù)管理系統(tǒng)以應(yīng)對大數(shù)據(jù)的“4V”特征帶來的挑戰(zhàn),并設(shè)計了大量代表性數(shù)據(jù)管理系統(tǒng),在實(shí)際應(yīng)用中已經(jīng)取得了較好的效果.下面我們將針對不同系統(tǒng)類型分別闡述上述技術(shù)及相關(guān)系統(tǒng)的進(jìn)展,并展望后續(xù)發(fā)展趨勢.本文最后對新型數(shù)據(jù)管理系統(tǒng)在數(shù)據(jù)模型、計算模型和體系結(jié)構(gòu)等方面的挑戰(zhàn)和機(jī)遇進(jìn)行了探討.

1 分布式數(shù)據(jù)庫

1.1 引 言

在大數(shù)據(jù)時代下,移動互聯(lián)網(wǎng)、智能設(shè)備以及物聯(lián)網(wǎng)技術(shù)的發(fā)展,使得全球數(shù)據(jù)量呈現(xiàn)爆發(fā)式增長,遠(yuǎn)遠(yuǎn)超出傳統(tǒng)的單機(jī)版數(shù)據(jù)庫的處理能力.近幾年,分布式數(shù)據(jù)庫一直是工業(yè)界和學(xué)術(shù)界的研究重點(diǎn).分布式數(shù)據(jù)庫應(yīng)該具備強(qiáng)一致性、高可用性、可擴(kuò)展性、易運(yùn)維、容錯容災(zāi)以及滿足ACID屬性的高并發(fā)事務(wù)處理能力.但在實(shí)際設(shè)計中,一方面受限于 CAP理論[1],即,在必須支持分區(qū)容錯性(partition tolerance)的前提下,系統(tǒng)實(shí)現(xiàn)只能側(cè)重一致性(consistency)和可用性(availability)的一個方面而無法同時滿足;另一方面,支持ACID事務(wù)屬性及高并發(fā)事務(wù)處理一直是分布式關(guān)系數(shù)據(jù)庫的難點(diǎn).針對這些挑戰(zhàn),現(xiàn)有的解決策略大致可分成 3類:(1) 將現(xiàn)有商業(yè)關(guān)系數(shù)據(jù)庫(如Oracle、SQLServer、MySQL、PostgreSQL)在分布式集群或者云平臺上進(jìn)行小規(guī)模擴(kuò)展和部署;(2) 放棄關(guān)系數(shù)據(jù)庫模型和 ACID的事務(wù)特性,選擇靈活的 schema-free數(shù)據(jù)模型及高可用性和最終一致性的NoSQL數(shù)據(jù)庫;(3) 融合關(guān)系數(shù)據(jù)庫和NoSQL優(yōu)勢的新型數(shù)據(jù)庫(NewSQL).

1.2 主要研究問題

主流的分布式數(shù)據(jù)庫基本上圍繞數(shù)據(jù)強(qiáng)一致性、系統(tǒng)高可用性和ACID事務(wù)支持等核心問題展開研究工作,這些性質(zhì)與系統(tǒng)的擴(kuò)展性和性能密切相關(guān),甚至相互制約,往往需要根據(jù)具體的應(yīng)用需求進(jìn)行取舍.

· 數(shù)據(jù)強(qiáng)一致性:銀行交易系統(tǒng)等金融領(lǐng)域往往有數(shù)據(jù)強(qiáng)一致性和零丟失的需求.當(dāng)更新操作完成之后,任何多個后續(xù)進(jìn)程或線程的訪問都要求返回最近更新值.如果在這個分布式系統(tǒng)中沒有數(shù)據(jù)副本,那么系統(tǒng)必然滿足數(shù)據(jù)強(qiáng)一致性要求,原因是只有獨(dú)本數(shù)據(jù),才不會出現(xiàn)數(shù)據(jù)不一致的問題.但是分布式數(shù)據(jù)庫系統(tǒng)的設(shè)計需要保存多個副本來提高可用性和容錯性,以避免宕機(jī)時數(shù)據(jù)還沒有復(fù)制,導(dǎo)致提供的數(shù)據(jù)不夠準(zhǔn)確.如何低成本地保證數(shù)據(jù)的強(qiáng)一致性,是分布式數(shù)據(jù)庫系統(tǒng)的一個重要難題;

· 系統(tǒng)高可用性:在分布式數(shù)據(jù)庫中,系統(tǒng)的高可用性和數(shù)據(jù)強(qiáng)一致性往往不可兼得.當(dāng)存在不超過 1臺機(jī)器發(fā)生故障的時候,要求至少能讀到一份有效的數(shù)據(jù),往往需要犧牲數(shù)據(jù)的強(qiáng)一致性來保證系統(tǒng)的高可用性.相當(dāng)一部分NoSQL數(shù)據(jù)庫采用這個思路來支持互聯(lián)網(wǎng)場景下的大規(guī)模用戶并發(fā)訪問請求,它們通過實(shí)現(xiàn)最終一致性來確保高可用性和分區(qū)容忍性,弱化了數(shù)據(jù)的強(qiáng)一致要求.為了解決數(shù)據(jù)不一致問題,不同的分布式數(shù)據(jù)庫設(shè)計各自的沖突機(jī)制.另外,有效的容錯容災(zāi)機(jī)制也是保障系統(tǒng)高可用性的堅實(shí)后盾;

· ACID 事務(wù)支持:ACID 指的是事務(wù)層面的原子性(atomicity)、一致性(consistency)、隔離性(isolation)和持久性(durability).如何有效地支持ACID事務(wù)屬性,一直是分布式數(shù)據(jù)庫的難點(diǎn),涉及到很多復(fù)雜的操作和邏輯,會嚴(yán)重影響系統(tǒng)的性能,很多NoSQL數(shù)據(jù)庫都是放棄支持事務(wù)ACID屬性來換取性能的提升.近年來,新型數(shù)據(jù)庫(NewSQL)的出現(xiàn)給分布式數(shù)據(jù)庫的發(fā)展帶來新的方向,它的目標(biāo)是提供與NoSQL相同的可擴(kuò)展性和性能,同時支持事務(wù)的ACID屬性.這種融合一致性和可用性的NewSQL已經(jīng)成為分布式數(shù)據(jù)庫的研究熱點(diǎn).

1.3 國內(nèi)外研究現(xiàn)狀

1.3.1 基于分布式集群或云平臺的關(guān)系數(shù)據(jù)庫

MySQL集群是一種常見的開源分布式數(shù)據(jù)庫,它基于無共享的(shared-nothing)數(shù)據(jù)存儲模式,采用讀寫分離的主從模式(master-slave)來實(shí)現(xiàn)高可用性.該設(shè)計方法也被主流的云平臺關(guān)系數(shù)據(jù)庫采納和應(yīng)用,包括亞馬遜的Amazon RDS(Amazon relational database service)[2]、谷歌的 Google Cloud SQL[3]、微軟的Azure SQL Database[4]以及國內(nèi)的阿里云RDS[5]、騰訊CDB(cloud DataBase)[6]和網(wǎng)易的蜂巢RDS[7].與傳統(tǒng)數(shù)據(jù)庫相比,這些云數(shù)據(jù)庫往往同時支持MySQL、SQL Server及PostgreSQL等數(shù)據(jù)庫引擎,具有低成本、易運(yùn)維、可伸縮、高可用等優(yōu)勢,并提供容災(zāi)、備份、恢復(fù)、監(jiān)控、遷移等數(shù)據(jù)庫運(yùn)維全套解決方案.

基于分布式集群或云平臺關(guān)系數(shù)據(jù)庫的主要缺陷是很難低成本地保持?jǐn)?shù)據(jù)的一致性,每次將數(shù)據(jù)寫到master節(jié)點(diǎn)后,都要及時同步slave節(jié)點(diǎn),所以往往犧牲性能來保障強(qiáng)一致性.另外,如果master節(jié)點(diǎn)宕機(jī),會直接導(dǎo)致業(yè)務(wù)不可寫,也會影響整個系統(tǒng)的高可用性.為解決這一問題,MySQL集群自帶的數(shù)據(jù)同步策略從最初的異步復(fù)制進(jìn)化為MySQL 5.7版本的半同步復(fù)制,但效果依舊有限.各大企業(yè)也紛紛設(shè)計MySQL補(bǔ)丁來保證數(shù)據(jù)一致.Amazon Aurora將事務(wù)引擎和存儲引擎分離,redo日志從事務(wù)引擎中剝離,歸并到存儲引擎中,屬于典型的shared disk架構(gòu),通過存儲層共享來解決一致性問題.Galera Cluster采用多主架構(gòu)(multi-master)來實(shí)現(xiàn)真正的多點(diǎn)讀寫,即集群中每個節(jié)點(diǎn)都可讀寫,無需讀寫分離.集群不同節(jié)點(diǎn)之間數(shù)據(jù)同步是基于 Galera replication中間件,避免了MySQL集群主從節(jié)點(diǎn)之間的復(fù)制延遲.

國內(nèi)的云關(guān)系數(shù)據(jù)庫也對數(shù)據(jù)一致性的提升做出了原創(chuàng)性貢獻(xiàn).阿里巴巴的AliSQL利用了分布式一致性協(xié)議(Raft)[8]以保障多節(jié)點(diǎn)狀態(tài)切換的可靠性和原子性.為了保證多節(jié)點(diǎn)之間的 binlog的強(qiáng)一致性,騰訊的PhxSQL使用分布式一致性協(xié)議Paxos實(shí)現(xiàn)master管理.同時,用BinlogSvr來支持MySQL的異步復(fù)制協(xié)議以支撐微信后臺的賬號系統(tǒng)、企業(yè)微信及QQ郵箱等.網(wǎng)易RDS則是采用虛擬同步復(fù)制技術(shù),確保所有主機(jī)的更新事務(wù)在提交前都首先在從機(jī)上落盤,保證主從切換后數(shù)據(jù)完全一致.在節(jié)點(diǎn)上使用了并行復(fù)制技術(shù),大幅度提高了從機(jī)回放主機(jī)事務(wù)的速度,復(fù)制延遲消失,保證了在秒級完成主從切換.

1.3.2 NoSQL數(shù)據(jù)庫

由于事務(wù)處理過程對 ACID屬性的嚴(yán)格要求,云關(guān)系數(shù)據(jù)庫的可擴(kuò)展性相對有限.為提升系統(tǒng)存儲和處理海量數(shù)據(jù)的能力,NoSQL從底層數(shù)據(jù)模型進(jìn)行考慮,放棄關(guān)系模型,也不保證支持 ACID事務(wù)處理.它采用schema-free的數(shù)據(jù)模型,可以根據(jù)不同應(yīng)用需求衍生出多種類型的分布式數(shù)據(jù)庫.按照存儲模型來分類,可將NoSQL 數(shù)據(jù)庫分為列式存儲(如 HBase[9]和 Cassandra[10])、鍵值存儲(如 Redis[11]、MemcacheDB[12]、DynamoDB[13]、SimpleDB[14])和文檔存儲(如 MongoDB[15]和 CouchDB[16]).

一個分布式系統(tǒng)最多同時滿足一致性(consistency,簡稱 C)、可用性(availability,簡稱 A)和分區(qū)容錯性(partition tolerance,簡稱 P)中的兩項(xiàng),可根據(jù)相應(yīng)的設(shè)計目的進(jìn)行選擇.對 NoSQL而言,分區(qū)容錯性是不能犧牲的,因此只能在一致性和可用性上加以取舍.如果在這個分布式系統(tǒng)中數(shù)據(jù)沒有副本,那么系統(tǒng)必然滿足強(qiáng)一致性條件,因?yàn)橹挥歇?dú)本數(shù)據(jù),不會出現(xiàn)數(shù)據(jù)不一致的問題,此時C和P都具備.但是,如果某些服務(wù)器宕機(jī),那必然會導(dǎo)致某些數(shù)據(jù)是不能訪問的,那 A就不符合了;反之,如果在這個分布式系統(tǒng)中數(shù)據(jù)是有副本的,那么如果某些服務(wù)器宕機(jī),系統(tǒng)還是可以提供服務(wù)的,即符合A,但是很難保證數(shù)據(jù)的一致性.因?yàn)殄礄C(jī)時可能有些數(shù)據(jù)還沒有復(fù)制到副本中,那么提供的數(shù)據(jù)就不準(zhǔn)確了.一般情況下,對于一致性要求比較高的業(yè)務(wù)在訪問延遲時間方面就會降低要求,適合選擇 CP模式;對于訪問延時有高要求的業(yè)務(wù)在數(shù)據(jù)一致性方面會降低要求,適合選擇 AP模式.

· CP 模式

CP模式要求分區(qū)容忍性,同時對數(shù)據(jù)一致性要求較高,即,能夠保證所有用戶看到相同的數(shù)據(jù).當(dāng)網(wǎng)絡(luò)通信出現(xiàn)問題時,暫時隔離開的子系統(tǒng)可繼續(xù)運(yùn)行(分區(qū)容忍性),但是不保證某些節(jié)點(diǎn)故障時,所有請求都能被響應(yīng).如果主節(jié)點(diǎn)宕機(jī),可能需要選舉新的主節(jié)點(diǎn),同步節(jié)點(diǎn)間數(shù)據(jù)以及進(jìn)行數(shù)據(jù)回滾等操作,這會使系統(tǒng)的可用性降低.常見的 CP 模式系統(tǒng)有 BigTable[17]、HBase[9]、Redis[11]、MongoDB[15]和 MemcacheDB[12].

BigTable是一個GFS[18]之上的索引層,采用兩級的B+樹索引結(jié)構(gòu).GFS保證至少寫入一次成功的記錄并由BigTable記錄索引.為了保證BigTable的強(qiáng)一致性,同一時刻同一份數(shù)據(jù)只能被一臺機(jī)器服務(wù),且BigTable中的Tablet Server沒有對每個Tablet備份.HBase是Apache Hadoop中的一個子項(xiàng)目,屬于BigTable的開源版本,是滿足強(qiáng)一致性的分布式數(shù)據(jù)庫,主要用來存儲非結(jié)構(gòu)化和半結(jié)構(gòu)化的松散數(shù)據(jù).HBase利用Hadoop HDFS[19]作為其文件存儲系統(tǒng),借助 MapReduce[20]計算模型來處理海量數(shù)據(jù),并使用 Zookeeper作為分布式協(xié)同服務(wù).HBase使用了事務(wù)機(jī)制中常見的一致性實(shí)現(xiàn)方式WAL(write-ahead logging)[21].

Redis集群通常是主備,主節(jié)點(diǎn)負(fù)責(zé)寫入和讀取,而slave節(jié)點(diǎn)只是用來備份.當(dāng)主節(jié)點(diǎn)失敗時,slave節(jié)點(diǎn)有機(jī)會被提升為主節(jié)點(diǎn).MongoDB采用類似于Redis的主從集群方式,主節(jié)點(diǎn)作為單點(diǎn)寫操作服務(wù),然后同步到slave節(jié)點(diǎn),可以通過設(shè)置 autoresync發(fā)現(xiàn) slave節(jié)點(diǎn)的數(shù)據(jù)不是最新,則自動地從主服務(wù)器請求同步數(shù)據(jù).MongoDB使用基于Raft協(xié)議選主策略,一旦主節(jié)點(diǎn)發(fā)生故障,整個MongoDB會進(jìn)行交流,然后選擇一個合適的slave節(jié)點(diǎn)快速實(shí)現(xiàn)故障恢復(fù).

MemcacheDB是一個新浪網(wǎng)基于 Memcached開發(fā)的分布式 Key-Value存儲持久化開源項(xiàng)目,它使用BerkeleyDB[22]作為存儲引擎,通過為Memcached增加Berkeley DB的持久化存儲機(jī)制和異步主輔復(fù)制機(jī)制,使Memcached具備了事務(wù)恢復(fù)能力、持久化能力和分布式復(fù)制能力,非常適合超高性能讀寫速度和持久化保存的應(yīng)用場景.

· AP模式

AP模式主要以實(shí)現(xiàn)最終一致性來確?？捎眯院头謪^(qū)容忍性,但卻弱化了對數(shù)據(jù)的一致要求,大部分NoSQL系統(tǒng)都屬于AP模式范疇.

Amazon Dynamo[13]是一個分布式鍵值存儲系統(tǒng),它采用去中心化、松散耦合方式,由數(shù)百個服務(wù)組成面向服務(wù)架構(gòu),不支持復(fù)雜的查詢.Dynamo利用一致性哈希來完成數(shù)據(jù)分區(qū),給系統(tǒng)中的每個節(jié)點(diǎn)隨機(jī)分配一個token,這些token構(gòu)成一個哈希環(huán).執(zhí)行數(shù)據(jù)存放操作時,首先計算key的哈希值,然后存放到順時針方向第1個大于等于該哈希值的 token節(jié)點(diǎn)上.這種算法的優(yōu)點(diǎn)是:節(jié)點(diǎn)的增刪只會影響哈希環(huán)中相鄰的節(jié)點(diǎn),對其他節(jié)點(diǎn)沒有影響.

Cassandra[10]由 Facebook開發(fā)并于 2008年開源,系統(tǒng)架構(gòu)與Dynamo一致,均為基于DHT(分布式哈希表)的完全P2P架構(gòu),具有高度可擴(kuò)展性和高度可用性,沒有單點(diǎn)故障.Cassandra使用由Dynamo引入的架構(gòu)特性來支持BigTable數(shù)據(jù)模型,并采用MemTable和SSTable方式進(jìn)行存儲.在Cassandra寫入數(shù)據(jù)之前,需要先記錄日志(CommitLog),再將數(shù)據(jù)開始寫入ColumnFamily對應(yīng)的MemTable中.

Amazon SimpleDB[14]是一個可大規(guī)模伸縮、用Erlang編寫的高可用數(shù)據(jù)存儲,類似于Amazon S3,但兩者的一致性有很大的區(qū)別.Amazon S3[23]一致性模型為弱一致性,只支持最基本的Put/Get/Delete操作,且每個操作之間是互相獨(dú)立的.SimpleDB除了支持Get/Put/Delete,還需要支持強(qiáng)一致讀以及基于條件更新或者刪除的樂觀鎖機(jī)制.Amazon S3直接使用“Last Write Wins”的方式解決沖突,因?yàn)榧簝?nèi)部機(jī)器時鐘不一致的概率很低.另外,發(fā)生同一條記錄被多個客戶端更新且同時發(fā)生機(jī)器故障等異常情況的概率也很低.SimpleDB需要支持一些條件更新或者刪除,從而支持樂觀鎖機(jī)制以實(shí)現(xiàn)最終一致性.

Apache CouchDB[16]是一個面向文檔數(shù)據(jù)管理的開源數(shù)據(jù)庫,使用JSON存儲半結(jié)構(gòu)化的數(shù)據(jù),查詢語言為JavaScript并封裝MapReduce和HTTP作為API,適合CMS、電話本、地址本等的應(yīng)用.其最顯著的特性是支持多主復(fù)制,沒有鎖機(jī)制,通過使用MVCC(多版本并發(fā)性控制)[24]實(shí)現(xiàn)最終一致性.Tokyo Cabinet[25]的開發(fā)者是日本人Mikio Hirabayashi,主要被用在日本最大的SNS網(wǎng)站mixi.jp上,也曾是鍵值數(shù)據(jù)庫領(lǐng)域的熱點(diǎn).其他的高可用性NoSQL數(shù)據(jù)庫還有Voldemort[26]、Riak[27]等(見表2).

Table 2 Comparison of representative NoSQL systems表2 代表性NoSQL數(shù)據(jù)庫比較

1.3.3 NewSQL數(shù)據(jù)庫

近年來,以Spanner[28]為代表的新型數(shù)據(jù)庫(NewSQL)的出現(xiàn),給數(shù)據(jù)存儲和分析帶來了SQL、NoSQL之外的新思路.NewSQL指的是提供與NoSQL相同的可擴(kuò)展性和性能,并同時能支持滿足ACID特性的事務(wù).這保留了 NOSQL的高可擴(kuò)展和高性能,且支持關(guān)系模型.融合一致性和可用性的 NewSQL可能是未來大數(shù)據(jù)存儲新的發(fā)展方向.

Spanner是第一個將數(shù)據(jù)分布到全球規(guī)模的系統(tǒng),并且在外部支持一致的分布式事務(wù),設(shè)計目標(biāo)是橫跨全球上百個數(shù)據(jù)中心,覆蓋百萬臺服務(wù)器.不同于 BigTable版本控制的鍵值存儲模型,Spanner演化為時間上的多維數(shù)據(jù)庫.舊版本數(shù)據(jù)根據(jù)可配置的垃圾回收政策處理,應(yīng)用可以讀取具有舊時間戳的數(shù)據(jù).Spanner顯著的特點(diǎn)是外部一致讀寫和在某一時間戳的全度跨數(shù)據(jù)庫一致讀取.對于最典型的讀寫事務(wù),Spanner使用常見的兩階段鎖策略(2PL)來控制并發(fā),并實(shí)現(xiàn)了一個所謂的外部一致性.F1[29]是Google公司提出的建立在Spanner基礎(chǔ)上的用于廣告業(yè)務(wù)的存儲系統(tǒng).F1實(shí)現(xiàn)了豐富的關(guān)系型數(shù)據(jù)庫的特點(diǎn),包括嚴(yán)格遵從的 schema、強(qiáng)力的并行 SQL查詢引擎、通用事務(wù)、變更與通知的追蹤和索引.其存儲被動態(tài)分區(qū),數(shù)據(jù)中心間的一致性復(fù)制能夠處理數(shù)據(jù)中心崩潰引起的數(shù)據(jù)丟失.Google F1提供了一種可能性:OLTP與OLAP融合的可能性,這是在其他數(shù)據(jù)庫中從未沒有實(shí)現(xiàn)過的.

國內(nèi)數(shù)據(jù)庫在NewSQL領(lǐng)域的代表性系統(tǒng)包括阿里巴巴的OceanBase[30]和騰訊的DCDB[31].OceanBase是支持海量數(shù)據(jù)的高性能分布式數(shù)據(jù)庫系統(tǒng),實(shí)現(xiàn)了數(shù)千億條記錄和數(shù)百PB數(shù)據(jù)的跨行跨表事務(wù).數(shù)據(jù)多副本通過 Paxos協(xié)議同步事務(wù)日志,多數(shù)派成功事務(wù)才能提交.缺省情況下,讀、寫操作都在主副本進(jìn)行,保證強(qiáng)一致.存儲采用讀寫分離架構(gòu),沒有主從結(jié)構(gòu),集群節(jié)點(diǎn)全對等,每個節(jié)點(diǎn)都具備計算和存儲能力,無單點(diǎn)瓶頸.騰訊DCDB又名TDSQL,是一種兼容MySQL協(xié)議和語法且支持自動水平拆分的高性能分布式數(shù)據(jù)庫,即:業(yè)務(wù)顯示為完整的邏輯表,數(shù)據(jù)卻均勻地拆分到多個分片中.每個分片默認(rèn)采用主備架構(gòu),提供災(zāi)備、恢復(fù)、監(jiān)控、不停機(jī)擴(kuò)容等全套解決方案,適用于TB或PB級的海量數(shù)據(jù)場景.這幾年,TDSQL不斷進(jìn)步,研發(fā)了很多新特性,諸如多級分區(qū)、熱點(diǎn)更新、隱含主鍵、分布式事務(wù)等,不僅有力地支撐了事務(wù)型數(shù)據(jù)庫應(yīng)用,而且在體系結(jié)構(gòu)上也朝Spanner架構(gòu)上邁進(jìn),是一個名副其實(shí)的NewSQL系統(tǒng).

TiDB[32]作為NewSQL開源社區(qū)的代表,是PingCAP公司基于Google Spanner/F1論文實(shí)現(xiàn)的開源分布式NewSQL數(shù)據(jù)庫,能夠?qū)崿F(xiàn)分布式事務(wù)以及跨數(shù)據(jù)中心數(shù)據(jù)強(qiáng)一致性保證.TiDB最底層用Raft來同步數(shù)據(jù).每次寫入都要寫入多數(shù)副本,才能對外返回成功,即使丟掉少數(shù)副本,也能保證系統(tǒng)中還有最新的數(shù)據(jù).TiDB的事務(wù)模型采用樂觀鎖,只有在真正提交時才會做沖突檢測,如果有沖突,則需要重試.由于分布式事務(wù)要做兩階段提交,并且底層還需要做 Raft復(fù)制,一個非常大的事務(wù)會使得提交過程非常慢,并且會卡住下面的 Raft復(fù)制流程,所以在設(shè)計上,TiDB和Spanner對事務(wù)的大小進(jìn)行了限制.

1.4 總結(jié)與展望

本節(jié)從CAP理論出發(fā),對分布式數(shù)據(jù)庫的數(shù)據(jù)一致性、系統(tǒng)可用性和ACID事務(wù)屬性進(jìn)行了綜述,并針對國內(nèi)外數(shù)據(jù)庫的發(fā)展?fàn)顩r,介紹了現(xiàn)有商業(yè)關(guān)系數(shù)據(jù)庫如何在云平臺上進(jìn)行擴(kuò)展和部署,NoSQL數(shù)據(jù)庫如何支持schema-free數(shù)據(jù)模型、高可用性和最終一致性,以及新型數(shù)據(jù)庫(NewSQL)如何提供與NoSQL相同的可擴(kuò)展性和性能,同時能夠支持滿足ACID特性的事務(wù).

在大數(shù)據(jù)環(huán)境下,NoSQL分布式數(shù)據(jù)庫與傳統(tǒng)分布式數(shù)據(jù)庫的最終目標(biāo)都是對用戶提供完善的數(shù)據(jù)存儲和查詢功能,并且在運(yùn)營上能夠?qū)崿F(xiàn)可伸縮和高可用等特性,并提供容災(zāi)、備份、恢復(fù)、監(jiān)控等功能.兩者最大的區(qū)別在于傳統(tǒng)分布式數(shù)據(jù)庫追求數(shù)據(jù)強(qiáng)一致性,并且需要提供ACID事務(wù)支持,導(dǎo)致其在峰值性能、伸縮性、容錯性、可擴(kuò)展性等方面的表現(xiàn)不盡如人意,很難滿足海量數(shù)據(jù)的柔性管理需求.NoSQL則是以犧牲支持ACID為代價,換取更好的可擴(kuò)展性和可用性.NewSQL是一種相對較新的形式,旨在將 SQL的 ACID保證與 NoSQL的可擴(kuò)展性和高性能相結(jié)合.

未來幾年,融合關(guān)系數(shù)據(jù)庫和NoSQL優(yōu)勢的NewSQL將繼續(xù)在分布式數(shù)據(jù)庫領(lǐng)域大放光彩,并成為一個重要的研究熱點(diǎn).以O(shè)ceanBase和DCDB為代表的國內(nèi)NewSQL系統(tǒng)也將在海量復(fù)雜業(yè)務(wù)的推動下持續(xù)發(fā)展和優(yōu)化,并作為國家大數(shù)據(jù)發(fā)展戰(zhàn)略提供有力支撐.這也意味著,我國有可能在下一波數(shù)據(jù)庫技術(shù)潮流當(dāng)中占領(lǐng)先機(jī),進(jìn)入第一梯隊(duì).

2 圖數(shù)據(jù)庫

2.1 引 言

近年來,隨著社交網(wǎng)絡(luò)與語義網(wǎng)的發(fā)展,基于互聯(lián)網(wǎng)的圖數(shù)據(jù)規(guī)模越來越大.截止到 2017年底,微信已經(jīng)有了將近 10億的活躍用戶,這些用戶相互關(guān)聯(lián)與通信,僅在 2016年春節(jié)期間,用戶之間就互相分發(fā)了 32億個紅包[33].在語義網(wǎng)的Linked Open Data項(xiàng)目中,已有超過1 184個RDF圖數(shù)據(jù)集,合計超過800億條邊[34].針對這些規(guī)模巨大的圖數(shù)據(jù),設(shè)計與實(shí)現(xiàn)高效的圖數(shù)據(jù)管理系統(tǒng)成為一個很重要的研究熱點(diǎn).

現(xiàn)階段,工業(yè)界和學(xué)術(shù)界已經(jīng)設(shè)計并實(shí)現(xiàn)了不少大規(guī)模圖數(shù)據(jù)管理系統(tǒng).按照對圖數(shù)據(jù)管理的抽象程度,可以將其分成如下兩類.

· 低層次抽象的提供編程接口的圖數(shù)據(jù)管理系統(tǒng):這類系統(tǒng)會針對圖數(shù)據(jù)管理中的基本操作設(shè)計并實(shí)現(xiàn)相應(yīng)的編程接口,用戶利用這些編程接口來實(shí)現(xiàn)相應(yīng)的管理功能;

· 高層次抽象的提供描述性查詢語言的圖數(shù)據(jù)管理系統(tǒng):這類系統(tǒng)設(shè)計圖數(shù)據(jù)管理描述性查詢語言,用戶將相應(yīng)的管理需求用描述性查詢語言表達(dá),系統(tǒng)解析這些描述性查詢語句并生成相應(yīng)的查詢計劃以進(jìn)行執(zhí)行處理.

表3中,我們列舉了本文即將介紹的圖數(shù)據(jù)管理系統(tǒng)以及它們的分類.

Table 3 Category of graph data management systems表3 圖數(shù)據(jù)管理系統(tǒng)分類

2.2 主要研究問題

針對大規(guī)模圖數(shù)據(jù)處理,主要有以下幾個常見問題.

· 圖搜索:給定一個圖,從一個點(diǎn)出發(fā)沿著邊搜索其他所有節(jié)點(diǎn).常見的圖搜素方法有寬度優(yōu)先、深度優(yōu)先和最短路徑等.圖搜索是圖計算問題的基礎(chǔ),用于衡量圖計算的 Benchmark Graph500[35]就是以寬度優(yōu)先搜索性能作為評測機(jī)器的圖計算能力的標(biāo)準(zhǔn);

· 基于圖的社區(qū)發(fā)現(xiàn):社區(qū)發(fā)現(xiàn)是社交網(wǎng)絡(luò)分析中一個重要的任務(wù),用于分析網(wǎng)絡(luò)圖中的密集子圖.這對于理解社交網(wǎng)絡(luò)中的用戶行為和朋友推薦等都具有非常重要的應(yīng)用價值,典型的社區(qū)發(fā)現(xiàn)算法有K-core[36]、K-truss[37]以及K-clique[38];

· 圖節(jié)點(diǎn)的重要性和相關(guān)性分析:計算圖中某個節(jié)點(diǎn)的重要程度,例如在網(wǎng)頁鏈接圖中分析網(wǎng)頁的重要程度,代表性工作是Pagerank[39];衡量圖上兩個節(jié)點(diǎn)的相關(guān)性,例如社交網(wǎng)絡(luò)中兩個人之間的關(guān)系,代表工作包括SimRank[40]和Random Walk[41]等;

· 圖匹配查詢:給定數(shù)據(jù)圖和查詢圖,圖匹配查詢找出所有在數(shù)據(jù)圖上與查詢圖同構(gòu)的子圖,這個問題常用于描述針對圖結(jié)構(gòu)的查詢.圖匹配查詢的應(yīng)用包括化學(xué)分子庫中的分子拓?fù)浣Y(jié)構(gòu)查詢[42]、在一個社交網(wǎng)絡(luò)圖中的特定社交結(jié)構(gòu)查詢[43]等.面向RDF知識圖譜數(shù)據(jù)的SPARQL查詢語言就是基于子圖匹配的查詢語義[44,45].

2.3 國內(nèi)外研究現(xiàn)狀

2.3.1 低層次抽象的提供編程接口的圖數(shù)據(jù)管理系統(tǒng)

提供低層次抽象編程接口的圖數(shù)據(jù)管理系統(tǒng)包括 Pregel[46]及其衍生[47-51]、Trinity[52]、GraphX[53]等;系統(tǒng)會將常見的圖運(yùn)算中的基本操作抽象成編程接口.雖然這類系統(tǒng)屏蔽了包括圖數(shù)據(jù)的內(nèi)部數(shù)據(jù)結(jié)構(gòu)表示、分布式環(huán)境下的通信處理等底層系統(tǒng)問題,但是由于是低層次抽象的編程接口,用戶還需要將具體的圖計算任務(wù)轉(zhuǎn)換成系統(tǒng)提供的低層次抽象編程接口邏輯.

這類系統(tǒng)中典型的是“點(diǎn)計算模型”,即允許用戶定義每個點(diǎn)的計算任務(wù).最早的系統(tǒng)是谷歌提出的一種分布式圖數(shù)據(jù)管理系統(tǒng)Pregel[46],該系統(tǒng)基于BSP分布式計算模型[54]進(jìn)行設(shè)計,圖數(shù)據(jù)的每個點(diǎn)為基本計算核心,機(jī)器之間通過消息傳遞來實(shí)現(xiàn)同步.Pregel將圖運(yùn)算用一系列的超級計算步(superstep)來描述,在運(yùn)算每一次超級計算步時,每一個頂點(diǎn)都能接收來自上一次超級計算步的信息,然后將這些信息傳送給下一個頂點(diǎn),并在此過程中修改其自身的狀態(tài)信息(例如以該頂點(diǎn)為起點(diǎn)的出邊狀態(tài)信息)或改變整個圖的拓?fù)浣Y(jié)構(gòu).Pregel系統(tǒng)將不同機(jī)器的通信進(jìn)行了封裝,用戶需要通過編程來描述點(diǎn)計算函數(shù)進(jìn)而實(shí)現(xiàn)自身的需求.

Pregel的基于BSP的點(diǎn)計算模型得到了工業(yè)界以及學(xué)術(shù)界的廣泛關(guān)注與認(rèn)可.很多人在Pregel上開發(fā)了效率更高的系統(tǒng),包括 Giraph[47]、PowerGraph[48]、GraphLab[49]、Quegel[50]、PAGE[51]等.

除了基于“點(diǎn)計算”的圖計算系統(tǒng),Trinity[52]是微軟研發(fā)的一個基于內(nèi)存的分布式圖數(shù)據(jù)管理系統(tǒng).Trinity認(rèn)為:隨著時代的發(fā)展,一方面內(nèi)存越來越大且越來越便宜;另一方面,圖數(shù)據(jù)上的基本操作非常復(fù)雜,將數(shù)據(jù)存儲在外存會導(dǎo)致操作不便,所以利用內(nèi)存進(jìn)行圖數(shù)據(jù)管理才是更好的選擇.因?yàn)閱螜C(jī)內(nèi)存規(guī)?？偸怯邢薜?所以Trinity使用了內(nèi)存云的技術(shù),也就是將多臺機(jī)器的內(nèi)存封裝起來,使得用戶能夠同時使用多臺機(jī)器的內(nèi)存,而且無需知道底層細(xì)節(jié).Trinity的基本數(shù)據(jù)結(jié)構(gòu)是鍵值對,可以通過鄰接表的形式存儲與管理數(shù)據(jù)圖,用戶通過編程調(diào)用內(nèi)存中的鄰接表來實(shí)現(xiàn)自身需求.

GraphX[53]將圖計算任務(wù)分成兩種:圖并行計算任務(wù)(graph-parallel computation)和數(shù)據(jù)并行計算任務(wù)(dataparallel computation).所謂圖并行計算任務(wù),主要是指基于BSP點(diǎn)計算模型來實(shí)現(xiàn)的迭代計算任務(wù),如PageRank;所謂數(shù)據(jù)并行計算任務(wù),主要是指圖上代數(shù)運(yùn)算,如構(gòu)建一個圖、合并兩個圖、跨越多個圖等等.GraphX的作者認(rèn)為:現(xiàn)有的圖計算系統(tǒng)(如Pregel[46]、GraphLab[49])通過限定編程框架的形式來提高圖并行計算任務(wù)的執(zhí)行效率,但是這些系統(tǒng)并不適合數(shù)據(jù)并行計算任務(wù).基于上述觀察,GraphX在分布式計算平臺Spark[55]的基礎(chǔ)上構(gòu)建了GraphX,以同時處理圖并行計算任務(wù)和數(shù)據(jù)并行計算任務(wù).GraphX以圖為第1類組成對象,以屬性圖為數(shù)據(jù)模型.所謂屬性圖,就是每個點(diǎn)和每條邊都可以關(guān)聯(lián)一個屬性值表.GraphX定義了很多圖上的操作.既包括一些圖并行計算任務(wù),如Pregel等,也包括一些數(shù)據(jù)并行計算任務(wù),如map、filter等.

2.3.2 高層次抽象的提供描述性語言的圖數(shù)據(jù)管理系統(tǒng)

所謂高層次抽象的提供描述性查詢語言的圖數(shù)據(jù)管理系統(tǒng)包括Neo4J[56]、EmptyHeaded[57,58]、gStore[44,45,59]等.這些系統(tǒng)為了方便用戶對圖數(shù)據(jù)的使用,在構(gòu)建圖數(shù)據(jù)管理系統(tǒng)的基礎(chǔ)上,設(shè)計或者采用了一些描述性查詢管理語言.用戶可以將自身的需求表達(dá)成描述性語句,然后系統(tǒng)將這些任務(wù)語句解析成執(zhí)行計劃,最后由系統(tǒng)按照執(zhí)行計劃進(jìn)行處理進(jìn)而得到計算結(jié)果.因?yàn)檫@類系統(tǒng)用描述性查詢語言作為用戶和系統(tǒng)的交互中介,所以這類系統(tǒng)具有較好的用戶友好性.

Neo4J[56]是一個由美國Neo Technology公司開發(fā)的基于Java平臺的開源圖數(shù)據(jù)管理系統(tǒng),具有如下4個特點(diǎn):支持滿足ACID特性的事務(wù)操作、很好的可用性、很高的可擴(kuò)展性、支持高效率遍歷查詢.Neo4J的描述性查詢語言是 Cypher[60],適合于開發(fā)者和在數(shù)據(jù)庫上進(jìn)行查詢的數(shù)據(jù)專業(yè)操作人員.針對實(shí)際中各種應(yīng)用需求,Cyper定義不同的方法來描述與表達(dá).Cyper的許多關(guān)鍵字受SQL的啟發(fā),如like和order by,它是一個申明式的語言,焦點(diǎn)在如何從圖中找回(what to retrieve),而不是怎么去做.在不公布實(shí)現(xiàn)細(xì)節(jié)的前提下,用戶關(guān)心如何查詢優(yōu)化.

EmptyHeaded[57,58]是由斯坦福大學(xué)開發(fā)的圖數(shù)據(jù)管理系統(tǒng),這個系統(tǒng)首先將圖上的計算任務(wù)轉(zhuǎn)化成邊的連接操作,然后利用現(xiàn)有關(guān)系數(shù)據(jù)庫關(guān)于多路連接的最新研究成果[61]找出最優(yōu)的多路連接查詢執(zhí)行計劃.在查詢執(zhí)行階段,EmptyHeaded利用SIMD技術(shù)來提高查詢執(zhí)行效率.EmptyHeaded提出了自己的描述性查詢語言,主要整合了聯(lián)合查詢、聚集操作和迭代運(yùn)算,支持常見的子圖匹配、PageRank計算、最短路徑計算等.

著語義網(wǎng)的發(fā)展,越來越多的數(shù)據(jù)被表示成 RDF(resource description framework,即資源描述框架)[62]形式發(fā)布到網(wǎng)絡(luò)上.在RDF模型下,網(wǎng)絡(luò)資源及其關(guān)系也可以被表示成一個圖,方便用戶利用圖技術(shù)進(jìn)行數(shù)據(jù)表示與管理.針對 RDF數(shù)據(jù),已經(jīng)有推薦的描述性結(jié)構(gòu)化查詢語言 SPARQL(simple protocol and RDF query language)[63],可以實(shí)現(xiàn)大規(guī)模RDF的數(shù)據(jù)管理.

針對 RDF知識圖譜的數(shù)據(jù)管理,可以采用基于關(guān)系數(shù)據(jù)庫的方法,也可以采用圖計算的策略.利用 RDF知識圖譜的圖結(jié)構(gòu)特性來管理數(shù)據(jù),代表性系統(tǒng)有基于圖的 RDF知識圖譜數(shù)據(jù)管理系統(tǒng) gStore[44,45,59]和支持自然語言問句的RDF知識圖譜檢索系統(tǒng)gAnswer[64].

2.4 總結(jié)與展望

本文分類闡述了兩類圖數(shù)據(jù)管理方法,對圖數(shù)據(jù)計算任務(wù)進(jìn)行了不同程度的抽象,進(jìn)而提出了不同的交互方式.研究人員也提出了一些新的研究問題,包括在異構(gòu)計算環(huán)境下的圖數(shù)據(jù)管理問題,例如,如何利用新型高性能計算芯片F(xiàn)PGA進(jìn)行圖數(shù)據(jù)處理.異構(gòu)計算環(huán)境下的圖數(shù)據(jù)計算問題是一個開放性研究課題,同時,在傳感器、社交網(wǎng)絡(luò)等環(huán)境下的圖數(shù)據(jù)管理問題具有多源且實(shí)時更新的特點(diǎn),面對多源的流式圖數(shù)據(jù)管理也是圖數(shù)據(jù)管理所面臨的新的挑戰(zhàn).

3 流數(shù)據(jù)管理

3.1 引 言

智能手機(jī)的普及和移動互聯(lián)網(wǎng)的發(fā)展極大地加速了數(shù)據(jù)的生成過程,令數(shù)據(jù)呈現(xiàn)出爆炸式的增長,并給大數(shù)據(jù)的實(shí)時管理帶來了前所未見的難題和挑戰(zhàn).例如,微信的月活躍用戶已超過了 10億,用戶之間的交互則會帶來更大規(guī)模的數(shù)據(jù),包括語音、視頻、圖片以及相關(guān)的文本等.數(shù)據(jù)的規(guī)模和復(fù)雜性還在高速增長,如社交網(wǎng)絡(luò)每天以億級別的發(fā)文[65]、軌道交通應(yīng)用形成的大規(guī)模定位與軌跡信息以及網(wǎng)絡(luò)通信中的數(shù)據(jù)傳播等.為了處理實(shí)時增長的大規(guī)模復(fù)雜數(shù)據(jù),流數(shù)據(jù)的管理和相關(guān)系統(tǒng)的研究一直是學(xué)術(shù)界和工業(yè)界的熱點(diǎn)問題,包括早期的關(guān)系型數(shù)據(jù)為主的數(shù)據(jù)流管理系統(tǒng)、近期在工業(yè)界普遍使用的流式計算系統(tǒng)以及目前廣泛關(guān)注的對圖數(shù)據(jù)流管理系統(tǒng)的探索.

3.2 主要研究問題

流數(shù)據(jù)有眾多不同的定義,但統(tǒng)一起來可以用隨時間不斷增長的數(shù)據(jù)模型來概括.除了基本的數(shù)據(jù)查詢統(tǒng)計等操作外,主要有3方面的研究問題——流數(shù)據(jù)采樣、持續(xù)性數(shù)據(jù)查詢和流數(shù)據(jù)并行計算.

· 流數(shù)據(jù)采樣.基于有限的存儲來管理無限的動態(tài)數(shù)據(jù)是流數(shù)據(jù)管理中的基本挑戰(zhàn)之一,應(yīng)對這一挑戰(zhàn)的最經(jīng)典的思路則在于流數(shù)據(jù)上的高效采樣.將高速更新的流數(shù)據(jù)采樣到有明確規(guī)模邊界的有限存儲中,通過對采樣數(shù)據(jù)的計算和挖掘來反映流數(shù)據(jù)所蘊(yùn)含的重要信息.一方面,需要研究不同流數(shù)據(jù)場景下采樣策略的選取,進(jìn)而能夠利用有限的資源盡可能地反映原流數(shù)據(jù)的特征信息;另一方面,需要結(jié)合計算需求,精準(zhǔn)分析采樣數(shù)據(jù)上的計算與挖掘結(jié)果相對于精確解的近似程度,控制計算結(jié)果的偏移范圍;

· 持續(xù)性數(shù)據(jù)查詢.流數(shù)據(jù)模型所對應(yīng)的最核心的現(xiàn)實(shí)場景是實(shí)時監(jiān)控.對不斷生成的現(xiàn)實(shí)數(shù)據(jù)進(jìn)行高效的計算挖掘,能夠及時獲取現(xiàn)實(shí)世界中的重要信息.例如銀行對實(shí)時的交易數(shù)據(jù)進(jìn)行監(jiān)控,及時規(guī)避欺詐風(fēng)險和追蹤洗錢等違法行為.因此,給定基于結(jié)構(gòu)特征、統(tǒng)計特征的數(shù)據(jù)查詢模式,實(shí)時地監(jiān)控流數(shù)據(jù)中匹配的目標(biāo),一直都是研究的熱點(diǎn).一方面,需要保存已計算的中間結(jié)果來減少重復(fù)性的計算,另一方面,又需要避免中間結(jié)果維護(hù)帶來過高的額外開銷;

· 流數(shù)據(jù)并行計算.應(yīng)對流數(shù)據(jù)高速生成的一個重要策略就是利用數(shù)據(jù)和計算的獨(dú)立性進(jìn)行并行處理,提高系統(tǒng)吞吐量.系統(tǒng)日志數(shù)據(jù)、銀行流水?dāng)?shù)據(jù)以及大量的移動應(yīng)用產(chǎn)生的用戶數(shù)據(jù)等在其初期的歸整處理上都可以利用數(shù)據(jù)獨(dú)立性進(jìn)行流水線式的并行處理.在更復(fù)雜的數(shù)據(jù)計算和分析過程中,針對計算獨(dú)立性和流場景的一致性要求,設(shè)計鎖機(jī)制來實(shí)現(xiàn)計算分析的并行化.

3.3 國內(nèi)外研究現(xiàn)狀

本節(jié)將通過流數(shù)據(jù)管理研究的 3個不同階段分別闡述流數(shù)據(jù)管理系統(tǒng)目前的研究脈絡(luò):首先,簡單了解早期以關(guān)系型數(shù)據(jù)為主的數(shù)據(jù)流管理系統(tǒng)(DSMS);然后,詳細(xì)介紹近期針對大規(guī)模復(fù)雜數(shù)據(jù)的流式計算系統(tǒng);最后討論目前興起的對圖數(shù)據(jù)流管理系統(tǒng)的探索.

3.3.1 數(shù)據(jù)流管理系統(tǒng)

數(shù)據(jù)流管理系統(tǒng)(DSMS)是指管理持續(xù)性數(shù)據(jù)流的計算機(jī)軟件.不同于傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)(DBMS),數(shù)據(jù)流管理系統(tǒng)支持持續(xù)性查詢,每個查詢從注冊開始有效直至撤銷結(jié)束,不僅僅執(zhí)行一次.在有效期間內(nèi),隨著數(shù)據(jù)流的不斷更新,持續(xù)性查詢的結(jié)果也會更新.傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)一般假定有足夠的外存用來持久化數(shù)據(jù),并且可以進(jìn)行隨機(jī)訪問.而數(shù)據(jù)流管理系統(tǒng)中主要強(qiáng)調(diào)用有限的內(nèi)存來處理無限的數(shù)據(jù)流,并且只能順序訪問,這也是數(shù)據(jù)流管理最獨(dú)特的特征以及最大的挑戰(zhàn).

目前,數(shù)據(jù)流管理系統(tǒng)并沒有統(tǒng)一的系統(tǒng)框架,但在查詢語言上,絕大多數(shù)都采用類似于傳統(tǒng)數(shù)據(jù)庫管理系統(tǒng)中SQL的聲明式語言來表達(dá)查詢,包括持續(xù)性查詢語言(continuous query language,簡稱CQL)[66]、流SQL[67]等.流查詢語言也會支持窗口表達(dá).在圖示化的查詢語言中,每個細(xì)分的查詢由一個“查詢盒”表達(dá),各個細(xì)分查詢的關(guān)聯(lián)與組合通過“查詢盒”[68]間的箭頭連線表達(dá).這個結(jié)構(gòu)可以理解為流計算框架(諸如Storm等)中數(shù)據(jù)處理與傳輸架構(gòu)的前身.

目前,主要的數(shù)據(jù)流管理系統(tǒng)有 STREAM[69]、Aurora[68]、TelegraphCQ[70]、NiagaraCQ[71]以及 Gigascope[72]等.STREAM 是斯坦福大學(xué)研發(fā)的基于關(guān)系模型的多功能數(shù)據(jù)流管理系統(tǒng),它聚焦在數(shù)據(jù)流計算時的內(nèi)存管理以及近似查詢.Aurora是一個以工作流為導(dǎo)向的數(shù)據(jù)流管理系統(tǒng),用戶可以通過“查詢盒”來定義查詢計劃,每個“查詢盒”含有基礎(chǔ)的操作命令,“查詢盒”之間的數(shù)據(jù)流指向決定了各個步驟結(jié)果的傳輸框架.TelegraphCQ是一個由伯克利大學(xué)開發(fā)的自適應(yīng)數(shù)據(jù)流管理系統(tǒng),用于支持不同場景的數(shù)據(jù)流應(yīng)用.NiagaraCQ是針對動態(tài) Web內(nèi)容進(jìn)行持續(xù)性 XML-QL查詢的數(shù)據(jù)流管理引擎(XML-QL是 XML查詢語言的一種擴(kuò)展,用來支持大 XML文檔上的數(shù)據(jù)抽取,能夠跨多個不同的DTD解釋XML數(shù)據(jù)以及集成多個不同源的XML數(shù)據(jù)).它對XML數(shù)據(jù)的抽取、查詢與監(jiān)控分別由3個主要組件來支撐:搜索引擎、查詢引擎以及觸發(fā)管理.Gigascope是面向網(wǎng)絡(luò)數(shù)據(jù)流監(jiān)控的分布式數(shù)據(jù)流管理系統(tǒng),可以用來支撐網(wǎng)絡(luò)流量分析、入侵檢測、路由配置分析等,也能夠進(jìn)行網(wǎng)絡(luò)搜索、性能監(jiān)控等.

表4給出了數(shù)據(jù)流管理系統(tǒng)的對比情況.這些系統(tǒng)的核心初衷在于對靜態(tài)數(shù)據(jù)管理系統(tǒng)的流模型擴(kuò)展,因此,這些系統(tǒng)在查詢語義和執(zhí)行計算的數(shù)據(jù)處理邏輯方面與傳統(tǒng)的數(shù)據(jù)管理模型有很大的重疊,可以認(rèn)為是在傳統(tǒng)數(shù)據(jù)管理系統(tǒng)的語義和架構(gòu)上的擴(kuò)展,以支撐數(shù)據(jù)流場景的持續(xù)性查詢.目前,大規(guī)模高速生成的數(shù)據(jù)結(jié)構(gòu)復(fù)雜,基于關(guān)系模型的數(shù)據(jù)流管理系統(tǒng)難以應(yīng)對這種大數(shù)據(jù)場景.

Table 4 Comparisons of data stream flow management systems表4 數(shù)據(jù)流管理系統(tǒng)對比

3.3.2 流計算框架

流計算系統(tǒng)是目前學(xué)術(shù)界和工業(yè)界廣泛使用的進(jìn)行大規(guī)模數(shù)據(jù)處理的計算系統(tǒng).目前,主流的流計算框架主要有5個:Storm[73,74]、Spark Stream[75]、Samza[76,77]、Flink[78,79]以及Kafka Stream[80].流計算框架具有兩個重要概念:交付保證(delivery guarantee)[81]、流處理類型中的實(shí)時處理流和微批量處理流.

交付保證是系統(tǒng)在處理新來的數(shù)據(jù)項(xiàng)時提供相應(yīng)層次的處理保障,分為3種:第1種是“至少1次”,也就是說,即便出現(xiàn)系統(tǒng)宕機(jī)等錯誤,也仍然能夠保證新來的每個數(shù)據(jù)項(xiàng)被處理1次,可能會出現(xiàn)多次重復(fù)處理;第2種是“最多1次”,也就是說,新來的數(shù)據(jù)最多會被處理1次,在宕機(jī)等錯誤情況發(fā)生時,有可能數(shù)據(jù)會被丟棄而導(dǎo)致沒有被處理;第3種則是“恰好1次”,也就是要求最嚴(yán)格的交付保證,確保無論發(fā)生什么情況,新來的數(shù)據(jù)項(xiàng)有且僅有1次處理.

流處理類型[82]的實(shí)時處理流是指每個新來的數(shù)據(jù)項(xiàng)都會被立即處理而無需等待后續(xù)的數(shù)據(jù)項(xiàng),代表流框架有Storm、Samza、Flink以及Kafka Stream;微批量處理流是指數(shù)據(jù)項(xiàng)并不是到達(dá)之后立即處理,而是等待一段很短的時間使其聚成一定單位大小的單個小批量數(shù)據(jù)后再處理,對應(yīng)的流框架有 Spark Stream以及 Storm-Trident(Storm的一個擴(kuò)展,一個以實(shí)時計算為目標(biāo)的基于 Storm的高度抽象.它在提供處理大吞吐量數(shù)據(jù)能力(每秒百萬次消息)的同時,也提供了低延時分布式查詢和有狀態(tài)流式處理的能力).

Storm是一個Twitter開源流系統(tǒng),也是最早出現(xiàn)的開源流式計算框架.在初始化時,需要用戶定義一個實(shí)時計算框架,其結(jié)構(gòu)是一個有向圖.圖中的點(diǎn)是集群中的計算節(jié)點(diǎn),而邊則對應(yīng)整體計算邏輯中數(shù)據(jù)的傳輸,這個圖框架也被稱為拓?fù)?在一個拓?fù)渲?傳輸?shù)臄?shù)據(jù)單元是一系列不可修改的鍵值對(tuple),鍵值對從 spout(消息源)點(diǎn)中輸出形成流數(shù)據(jù)并傳輸?shù)?bolts(消息處理者)點(diǎn)中進(jìn)行計算,進(jìn)而產(chǎn)生出新的輸出流.bolt輸出流也可以傳輸給其他bolts節(jié)點(diǎn),形成流水線式的計算處理流.Storm也有不足之處,它并不支持狀態(tài)管理以及窗口、聚集等操作,支持的交付保證為“至少一次”而不是高要求的“恰好一次”.Storm 的容錯機(jī)制是 Ack機(jī)制,通信過程中需要的額外開銷可能會影響流計算的吞吐量.

Spark Stream(又稱為Structured Stream)其實(shí)是Spark[83,84]核心API的一個擴(kuò)展,其對流式處理的支持其實(shí)是將流數(shù)據(jù)分割成離散的多個小批量的RDD數(shù)據(jù)(RDD是Spark的數(shù)據(jù)單元),然后再進(jìn)行處理.這些小批量的數(shù)據(jù)被稱為DStream(D為Discretized,即離散化的意思).Spark Stream采用的是Lambda[85,86]架構(gòu),即同時運(yùn)行批量處理和實(shí)時流處理的架構(gòu),其中,批量處理用來確保計算的正確性,而實(shí)時流處理則是為提高吞吐量.當(dāng)實(shí)時流處理計算結(jié)果與批量處理的計算結(jié)果不一致時,則會校正錯誤,因?yàn)橛信幚淼拇嬖?所以自然而然就實(shí)現(xiàn)了容錯機(jī)制.Spark Stream支持的是“恰好一次”的交付保證,而且與Storm一樣,Spark Stream并沒有狀態(tài)管理.

Samza系統(tǒng)處理的流數(shù)據(jù)單元是類型相同或相近的消息,這些消息在產(chǎn)生之后是不可修改的.新產(chǎn)生的消息將被追加到流中,而流中的消息也不斷地被讀取.每條消息可以有相應(yīng)的鍵值,這些鍵值可以被用來對流中的所有消息進(jìn)行分割.Samza的工作過程是按需計算轉(zhuǎn)換(或過濾)一組輸入流中的消息數(shù)據(jù),并將計算結(jié)果以消息數(shù)據(jù)的形式附加到輸出流中.因此,運(yùn)行工作負(fù)載可能包含多個工作組,工作組之間可能有流數(shù)據(jù)的依賴關(guān)系,進(jìn)而將整體計算抽象成一個數(shù)據(jù)流圖框架.Samza的一大特色在于對狀態(tài)管理的良好支持,可以用來支撐流數(shù)據(jù)的連接操作,其狀態(tài)管理的引擎主要是RocksDB[87]和Kafka Log.

Flink與Storm相似,其整個數(shù)據(jù)處理過程被稱為Stream Dataflow,既定的數(shù)據(jù)流動框架類似于Storm的拓?fù)?Flink提取數(shù)據(jù)流的操作Source Operator、數(shù)據(jù)轉(zhuǎn)換(map,aggregate)的操作Transformation Operator以及數(shù)據(jù)流輸出的操作Sink Operator與Storm架構(gòu)中Spout與Bolts之間、Bolts和Bolts之間的數(shù)據(jù)流是高度對應(yīng)的,區(qū)別在于容錯機(jī)制:Flink的容錯機(jī)制是Checkpoint,通過異步實(shí)現(xiàn)并不會打斷數(shù)據(jù)流,因此Checkpoint的開啟與關(guān)閉對吞吐量的影響很小;Storm采用的是Ack機(jī)制,開銷大而且對吞吐量的影響明顯.另外,Flink提供的API相對 Storm更高級.Storm的優(yōu)勢主要是具有比較成熟的社區(qū)支撐和經(jīng)過較長期迭代之后的穩(wěn)定性.目前,Flink成熟度較低,仍有部分功能需加以完善,如在線的動態(tài)資源調(diào)整等.Flink提供的交付保證是“恰好一次”,優(yōu)于Storm的“至少一次”.Flink廣泛受到大公司的親睞,包括Uber和阿里巴巴,其中,阿里巴巴開發(fā)了基于Flink的流計算系統(tǒng)Blink,并應(yīng)用在電商流數(shù)據(jù)計算中.

Kafka Stream是Apache Kafka[80,88]中的一個輕量級流式處理類庫,用來支撐Kafka中存儲數(shù)據(jù)的流式計算與分析.利用這個類庫計算的結(jié)果既可以寫回 Kafka,也可以作為數(shù)據(jù)源向外輸出.目前的流式計算系統(tǒng)基本都支持以Kafka Stream的輸出作為數(shù)據(jù)源,如Storm的Kafka Spout.Kafka Stream作為一個Java類庫而非系統(tǒng),是流計算的重要工具之一.它可以非常方便地嵌入任意Java應(yīng)用中,也可以任意方式打包和部署,除了Kafka之外,并沒有任何外部依賴.與流計算系統(tǒng)相比,使用 Kafka所受到的邏輯限制較少,開發(fā)者能夠更好地控制和使用Kafka Stream上的應(yīng)用.Kafka Stream提供的是“恰好一次”的交付保證,并且能夠利用RocksDB進(jìn)行狀態(tài)管理.目前,大公司在Kafka Stream上的實(shí)踐較少,相關(guān)技術(shù)有待進(jìn)一步成熟.

這些流系統(tǒng)最主要的相似性是針對數(shù)據(jù)獨(dú)立性設(shè)計分布式并行計算策略,即:針對流式的輸入,利用集群進(jìn)行協(xié)作計算,而整體的數(shù)據(jù)依賴框架一般是一個有向無環(huán)圖.集群的整體協(xié)作更像是流水線的協(xié)作,計算框架中的數(shù)據(jù)依賴所形成的數(shù)據(jù)流動方向基本上是單一既定的.除了數(shù)據(jù)處理的先后關(guān)系外,這些流系統(tǒng)對不同工作組之間的數(shù)據(jù)獨(dú)立性往往要求更高,可實(shí)現(xiàn)較好的并行效果.

已有針對這些流系統(tǒng)的基準(zhǔn)比較(benchmarking)[89],然而系統(tǒng)的參數(shù)各不相同,同一系統(tǒng)在不同參數(shù)下的性能也會大相徑庭,所以benchmarking的結(jié)果可信度不足(見表5).目前,從流系統(tǒng)支持的功能上來看,Flink的功能是最完備的,有狀態(tài)管理、高吞吐量和低延遲、支持最嚴(yán)格的“恰好一次”交付保證、可調(diào)控內(nèi)存使用等,并且不會出現(xiàn)容錯機(jī)制影響吞吐量的情況(如Storm).雖然Flink的社區(qū)積累較少,相關(guān)API不夠成熟,但在Uber、阿里巴巴等公司的使用和推廣之下,目前逐漸成為廣受歡迎、功能強(qiáng)大的流計算框架.

Table 5 Comparison of stream computing systems表5 流計算系統(tǒng)對比

3.4 圖數(shù)據(jù)流管理系統(tǒng)的探索

目前的流數(shù)據(jù)除了規(guī)模大和增長快之外,還有結(jié)構(gòu)復(fù)雜的特點(diǎn),而圖模型能夠以簡易的形式表達(dá)出豐富的語義,因此,圖模型與流數(shù)據(jù)模型融合而成的圖數(shù)據(jù)流模型應(yīng)運(yùn)而生[90].圖數(shù)據(jù)流的多種定義可以用無限增長的邊序列來概括(孤立點(diǎn)的現(xiàn)實(shí)意義有限),對應(yīng)的研究問題除了傳統(tǒng)的圖計算問題之外,還有針對時間先后信息定義的研究問題,如滿足時序約束的路徑、子圖查詢等[91].常見的時序約束有時間先后、時間間隔.例如,阿里巴巴通過網(wǎng)購交易數(shù)據(jù)中的環(huán)形子圖的實(shí)時監(jiān)控來追蹤通過網(wǎng)購進(jìn)行惡意信用卡套現(xiàn)的行為[92].如圖1所示:一個信用卡惡意的套現(xiàn)模式中,套現(xiàn)者向商戶發(fā)起信用卡虛假購買,銀行將真實(shí)的資金支付給商戶之后,商戶通過中間人將資金回流到套現(xiàn)者儲蓄卡中,實(shí)現(xiàn)惡意套現(xiàn).整個流程中,參與的對象和資金的流向構(gòu)成了圖的結(jié)構(gòu),而每個行為環(huán)節(jié)有其明確的時間先后關(guān)系.因此,針對圖數(shù)據(jù)流的管理能夠解決很多現(xiàn)實(shí)中的重要問題.

Fig.1 Malicious cash arbitrage model of credit card[92]圖1 信用卡惡意套現(xiàn)模式[92]

在圖數(shù)據(jù)流的管理方法上,核心的思路仍是在于利用已計算出來的結(jié)果來加速當(dāng)前的計算,并且需要將中間結(jié)果維護(hù)上的時間和空間代價控制在可接受的范圍內(nèi)[93].以流數(shù)據(jù)上的子圖匹配為例,如果采用靜態(tài)算法構(gòu)建復(fù)雜的索引的思路來加速查詢,則需要針對復(fù)雜的索引設(shè)計高速更新的算法.然而往往對查詢的加速容易增加更新的代價,在無索引的極端情況下,針對子圖的匹配需要完全重算;而在另一種極端情況下,即構(gòu)建復(fù)雜的索引時,往往需要高額的更新時間甚至整個索引重構(gòu).因此,圖數(shù)據(jù)流下的計算首要考慮的是計算結(jié)果的維護(hù)與計算加速的權(quán)衡.此外,在圖數(shù)據(jù)流的高速更新場景下,多線程的并發(fā)計算仍然具有重要的意義.然而,圖數(shù)據(jù)中不同部分的關(guān)聯(lián)程度較高,如單條邊的刪除能夠?qū)е麓罅柯窂教卣鞯母淖兊?因此,在圖數(shù)據(jù)流下進(jìn)行并行算法設(shè)計和并發(fā)訪問控制等具有嚴(yán)峻的挑戰(zhàn).

基于目前已有的圖數(shù)據(jù)管理的探索,可以總結(jié)出圖數(shù)據(jù)流管理系統(tǒng)所需要解決的三大重要問題.

· 第1個是對圖數(shù)據(jù)流中數(shù)據(jù)的基本操作的支撐,包括邊序列的存儲、增刪改查以及已獲取圖數(shù)據(jù)的基本訪問操作,如節(jié)點(diǎn)度數(shù)、鄰居等;

· 其次是針對圖數(shù)據(jù)流上的更復(fù)雜的挖掘和查詢支撐,包括邊流行為分析、路徑計算以及更復(fù)雜的子圖結(jié)構(gòu)匹配等.對于復(fù)雜查詢和挖掘的支撐,所設(shè)計的索引一方面需要考慮對計算的加速保證,另一方面需要考慮在高速更新場景下對索引的更新維護(hù)代價;

· 第3個問題則是事務(wù)管理和并發(fā)、并行調(diào)度等機(jī)制的設(shè)計,旨在提高系統(tǒng)的吞吐量和縮短響應(yīng)時間.

3.5 總結(jié)與展望

已有的數(shù)據(jù)流管理系統(tǒng)主要是在傳統(tǒng)的數(shù)據(jù)流管理模型和架構(gòu)上作了持續(xù)性查詢的簡單擴(kuò)展,兩者在語義和計算邏輯方面有相似之處,大部分?jǐn)?shù)據(jù)流管理系統(tǒng)來自高?？蒲袌F(tuán)隊(duì),而且這些數(shù)據(jù)流管理系統(tǒng)已經(jīng)難以處理大規(guī)模復(fù)雜數(shù)據(jù)流的查詢和計算.主流的流計算框架采用分布式的計算方式,利用數(shù)據(jù)獨(dú)立性的特點(diǎn)進(jìn)行并行計算,與傳統(tǒng)的數(shù)據(jù)管理模型有很大區(qū)別.對數(shù)據(jù)的格式要求不高,能夠處理大規(guī)模的多種復(fù)雜數(shù)據(jù)流,有大量的社區(qū)支持以及大規(guī)模企業(yè)的實(shí)踐與推廣,大部分是來自開源社區(qū)而鮮有是學(xué)術(shù)界的科研團(tuán)隊(duì)開發(fā)的.目前,對大規(guī)模生成的復(fù)雜數(shù)據(jù)的計算處理基本上依賴于流計算框架.由于對數(shù)據(jù)的獨(dú)立性要求較高,流計算框架不適于處理數(shù)據(jù)之間有高度關(guān)聯(lián)關(guān)系的模型,因此,目前針對圖數(shù)據(jù)流管理系統(tǒng)的研究受到了學(xué)術(shù)界和工業(yè)界的高度關(guān)注.

4 時空數(shù)據(jù)庫

4.1 引 言

時空數(shù)據(jù)庫是管理空間、時態(tài)以及移動對象數(shù)據(jù)的數(shù)據(jù)庫系統(tǒng),與傳統(tǒng)的關(guān)系型數(shù)據(jù)相比,時空數(shù)據(jù)具有多維度、多類型、動態(tài)變化、更新快等特點(diǎn),關(guān)系型數(shù)據(jù)庫不能很好地處理此類數(shù)據(jù),需要新的有效數(shù)據(jù)管理方法.近年來,時空數(shù)據(jù)庫在地理信息系統(tǒng)、城市交通管理及分析、計算機(jī)圖形圖像、金融、醫(yī)療、基于位置服務(wù)等領(lǐng)域有著廣泛的應(yīng)用.根據(jù)時空數(shù)據(jù)特點(diǎn),時空數(shù)據(jù)庫大致包括以下3種.

· 空間數(shù)據(jù)庫:主要處理點(diǎn)、線、區(qū)域等二維數(shù)據(jù),數(shù)據(jù)庫系統(tǒng)需提供相應(yīng)的數(shù)據(jù)類型以支持?jǐn)?shù)據(jù)表示、存儲、常見拓?fù)溥\(yùn)算操作和高效查詢處理,同時需要與傳統(tǒng)的關(guān)系數(shù)據(jù)庫系統(tǒng)融合以擴(kuò)展數(shù)據(jù)庫系統(tǒng)處理能力,支持不同類型數(shù)據(jù)的查詢處理;

· 時態(tài)數(shù)據(jù)庫:管理數(shù)據(jù)的時間屬性,包括有效時間(valid time)、事務(wù)時間(transaction time)等.時間可以為時間點(diǎn)或者時間區(qū)間:如果是時間區(qū)間,數(shù)據(jù)庫管理系統(tǒng)將以開始和結(jié)束時間兩個屬性或一個區(qū)間屬性進(jìn)行存儲.不同的應(yīng)用場景下,時間屬性會有相應(yīng)的特點(diǎn)(例如周期性);

· 移動對象數(shù)據(jù)庫:管理位置隨時間連續(xù)變化的空間對象,主要有移動點(diǎn)和移動區(qū)域:前者僅是位置隨時間變化,后者還包括形狀和面積的變化.移動對象具有數(shù)據(jù)量大、位置更新頻繁、運(yùn)算操作復(fù)雜等特點(diǎn).近年來,隨著定位設(shè)備的不斷普及,例如智能手機(jī),采集這類數(shù)據(jù)越來越容易.同時,與地圖興趣點(diǎn)(例如酒店、餐館等)相結(jié)合,使得移動對象具有語義信息,帶來各種新的應(yīng)用,例如基于位置服務(wù)、最優(yōu)路徑規(guī)劃等.

4.2 主要研究問題

· 數(shù)據(jù)模型和查詢語言

數(shù)據(jù)模型包含數(shù)據(jù)類型和運(yùn)算操作兩個方面.時空數(shù)據(jù)類型包含多個,有些為定長記錄存儲(例如點(diǎn)、區(qū)間),有些為變長記錄存儲(例如區(qū)域、移動點(diǎn)).運(yùn)算操作定義時空拓?fù)溥\(yùn)算(例如相交intersect、重合 overlap),包含語法和語義兩個層面:前者描述輸入輸出參數(shù)類型,后者定義抽象層含義.時態(tài)和移動對象數(shù)據(jù)庫均處理具有時間因素的對象,數(shù)據(jù)類型和運(yùn)算操作都涉及隨時間變化的數(shù)值,增加了復(fù)雜性,主要體現(xiàn)在如何表示數(shù)值的動態(tài)變化以及拓?fù)溥\(yùn)算定義和求解方法上.移動對象除了要考慮自身的時空屬性外,還需要結(jié)合對象所在的受限制空間環(huán)境,例如道路網(wǎng)、室內(nèi)空間等,因?yàn)槲恢帽硎九c此相關(guān).此外,不確定性時空數(shù)據(jù)也是研究內(nèi)容之一,包括數(shù)據(jù)模型和查詢語言.時空數(shù)據(jù)類型可作為關(guān)系屬性嵌套在關(guān)系模式下,從而對查詢語言SQL擴(kuò)展(運(yùn)算操作、謂詞),以得到時空數(shù)據(jù)查詢語言,支持形式化查詢描述.

· 索引結(jié)構(gòu)

根據(jù)不同時空數(shù)據(jù)的特點(diǎn)設(shè)計訪問結(jié)構(gòu),以支持快速查詢處理,常見的空間和時態(tài)索引有R-tree、K-d Tree、Interval-tree等.不同的索引結(jié)構(gòu)有相應(yīng)的運(yùn)算操作,包括創(chuàng)建、插入、刪除、更新及查詢.其中,R-tree是最為廣泛使用的結(jié)構(gòu),為提高查詢效率,需對數(shù)據(jù)排序(例如 z-order),目的是將相似數(shù)據(jù)存儲在鄰近結(jié)構(gòu)里,以減少搜索的I/O代價.同時,基于該結(jié)構(gòu)的預(yù)測模型可以估計查詢的I/O代價,為進(jìn)一步優(yōu)化提供分析的依據(jù).根據(jù)時間因素,移動對象索引可分為兩類:(i) 歷史數(shù)據(jù)索引,管理移動對象從開始到結(jié)束的所有位置和時間;(ii) 當(dāng)前數(shù)據(jù)及預(yù)測索引,管理移動對象當(dāng)前位置和速度并進(jìn)行預(yù)測,提供有效的位置更新策略及數(shù)據(jù)緩存方法.由于移動對象的位置、時空分布、查詢等頻繁發(fā)生變化,主存索引及并行技術(shù)往往比外存索引更具優(yōu)勢,自動調(diào)優(yōu)技術(shù)對索引的參數(shù)動態(tài)調(diào)整以使性能最優(yōu).時空數(shù)據(jù)索引可以融入語義描述,從而拓展時空數(shù)據(jù)管理能力,以支持具有語義的時空查詢.

· 查詢處理及優(yōu)化

選擇查詢和最近鄰查詢是空間和移動對象數(shù)據(jù)庫最常見的兩類查詢:前者返回在空間/時空查詢窗口內(nèi)的對象,后者返回距離查詢目標(biāo)最近的對象.當(dāng)查詢目標(biāo)是移動對象時,其最近鄰對象也動態(tài)地發(fā)生變化,稱為連續(xù)最近鄰查詢;當(dāng)返回結(jié)果的最近鄰是查詢目標(biāo)對象時,稱為反向最近鄰查詢.相似性查詢定義評價函數(shù),用于計算對象之間的相似度,返回與查詢目標(biāo)最相近的對象;連接查詢用于返回兩個數(shù)據(jù)集中所有符合查詢謂詞條件(例如相交、重合)的實(shí)體對,例如找出所有長江和黃河途經(jīng)的城市.與選擇查詢、最近鄰查詢相比,連接查詢的復(fù)雜性更高,相關(guān)優(yōu)化技術(shù)有數(shù)據(jù)劃分、索引創(chuàng)建、排序等.時空數(shù)據(jù)查詢還包括聚類查詢、模式匹配、距離查詢等.將關(guān)鍵字或語義描述與位置相結(jié)合,可進(jìn)行具有語義的ranking或top-k查詢,返回對象不僅符合時空約束,而且滿足關(guān)鍵字條件,增加了用戶對時空對象的全面理解.

· 時空數(shù)據(jù)管理系統(tǒng)

在定義了抽象模型的基礎(chǔ)上,需要有系統(tǒng)實(shí)現(xiàn)模型包括數(shù)據(jù)結(jié)構(gòu)和算法、邏輯設(shè)計及實(shí)現(xiàn),同時需要將時空數(shù)據(jù)模型和關(guān)系模型有效融合,從而擴(kuò)展數(shù)據(jù)庫處理能力.由于時空數(shù)據(jù)管理系統(tǒng)涉及多種索引結(jié)構(gòu)和查詢算法(例如,基于R-tree的深度優(yōu)先和寬度優(yōu)先),因此需對數(shù)據(jù)庫系統(tǒng)的功能、性能及可擴(kuò)展性等進(jìn)行全面測試和評估,發(fā)現(xiàn)系統(tǒng)性能瓶頸從而進(jìn)行優(yōu)化.這主要通過基準(zhǔn)測試完成,一般包括數(shù)據(jù)集(真實(shí)和模擬)、查詢集、索引結(jié)構(gòu)及參數(shù)設(shè)置等,為模擬各種時空數(shù)據(jù)分布,需要相應(yīng)的數(shù)據(jù)產(chǎn)生器及可視化工具.

除上述研究問題外,時空數(shù)據(jù)庫管理還涉及時空數(shù)據(jù)倉庫、時空圖數(shù)據(jù)、時空數(shù)據(jù)流、基于位置服務(wù)(最優(yōu)路徑規(guī)劃和交通預(yù)測)、軌跡數(shù)據(jù)壓縮、時空數(shù)據(jù)挖掘和分析等方面.

4.3 國內(nèi)外研究現(xiàn)狀

4.3.1 空間數(shù)據(jù)庫

依據(jù)不同的環(huán)境,空間數(shù)據(jù)庫的研究包括自由空間和受限空間(例如道路網(wǎng)、有障礙空間),主要區(qū)別在于距離函數(shù),受限空間的距離計算依賴于最短路徑求解,比自由空間要復(fù)雜.相關(guān)查詢有范圍查詢、最近鄰(反向最近鄰)、Skyline查詢、動態(tài)道路網(wǎng)下最短路徑查詢和路徑規(guī)劃等,索引技術(shù)和搜索策略在查詢中起到了關(guān)鍵性作用[94].查詢過程一般包括過濾和提煉兩個階段:過濾階段借助于索引和估計值找到一組備選對象,提煉階段對每個備選對象進(jìn)行準(zhǔn)確值求解.空間數(shù)據(jù)庫查詢還包括最大范圍求和、容量受限分配等.在基于位置服務(wù)的應(yīng)用中,隱私保護(hù)是一個重要的研究內(nèi)容,已有的工作包括基于位置隱私的攻擊及保護(hù)方法,如模糊表示、匿名等.

近10年來,空間關(guān)鍵字查詢(spatial keyword search)得到了廣泛和深入的研究[95],通過將空間位置與文本相結(jié)合,用戶可以查詢同時符合空間和語義條件約束的對象,常見查詢有Top-k、k-NN等.由于傳統(tǒng)的空間數(shù)據(jù)索引不支持文本數(shù)據(jù)管理,一般將空間索引與文本索引或位圖技術(shù)相結(jié)合構(gòu)成混合索引結(jié)構(gòu),支持同時對空間和文本數(shù)據(jù)的查詢,以縮小搜索范圍.

4.3.2 時態(tài)數(shù)據(jù)庫

在過去的20年里,時態(tài)數(shù)據(jù)管理一直是數(shù)據(jù)庫的活躍領(lǐng)域之一,研究內(nèi)容包括數(shù)據(jù)模型、查詢語言、索引結(jié)構(gòu)及高效查詢算法,各種查詢語言也被提出以支持時態(tài)數(shù)據(jù)查詢的形式化描述.Enderle等人基于常見的時態(tài)數(shù)據(jù)索引之一——Interval-tree設(shè)計了相應(yīng)的外存結(jié)構(gòu)以及在關(guān)系數(shù)據(jù)庫系統(tǒng)中的實(shí)現(xiàn)方法,可以有效支持相交查詢和連接查詢[96];Top-k查詢用于返回與查詢點(diǎn)(區(qū)間)相交且權(quán)重最大的k個對象.Dign?s等人將時態(tài)數(shù)據(jù)運(yùn)算操作、轉(zhuǎn)換原則及查詢優(yōu)化方法集成到關(guān)系數(shù)據(jù)庫系統(tǒng)內(nèi)核中(PostgreSQL),以擴(kuò)展其處理能力[97],商用數(shù)據(jù)庫Oracle提供了數(shù)據(jù)類型PERIOD及相關(guān)謂詞和函數(shù).

近幾年,時態(tài)數(shù)據(jù)庫的研究主要集中在高效處理各種連接查詢(例如 overlap join,merge join)、聚類查詢(aggregation)以及數(shù)據(jù)劃分和排列方法(partition/splitter,align).同時,硬件技術(shù)(例如多核 CPU)的發(fā)展也有助于提高查詢效率.不確定性時態(tài)數(shù)據(jù)將時態(tài)數(shù)據(jù)和不確定性相結(jié)合,也有不少相關(guān)研究工作,包括數(shù)據(jù)表示及建模、不確定性時態(tài)數(shù)據(jù)查詢等;時態(tài)數(shù)據(jù)集成是根據(jù)用戶指定優(yōu)先規(guī)則對多源時態(tài)數(shù)據(jù)加以融合.

4.3.3 移動對象數(shù)據(jù)庫

早期的移動對象數(shù)據(jù)庫研究主要集中在數(shù)據(jù)模型、索引和查詢處理等[98],代表性索引結(jié)構(gòu)有 TB-Tree、SETI、TPR-tree、STRIPES等[99],這些結(jié)構(gòu)的差異主要體現(xiàn)在時空數(shù)據(jù)的管理方法(例如插入原則、時空優(yōu)先權(quán))上,常見的移動對象查詢有范圍查詢、(連續(xù))最近鄰、相似性軌跡、連接查詢等.針對大規(guī)模移動對象位置的實(shí)時更新,有學(xué)者提出了有效的更新策略及監(jiān)控方法,也有學(xué)者對不確定性移動對象進(jìn)行了研究[100].近年來,面向特定應(yīng)用的移動對象查詢得到了廣泛的關(guān)注,例如軌跡模式匹配、異?，F(xiàn)象分析、基于軌跡的用戶行為推薦、軌跡壓縮等.由于大規(guī)模移動對象數(shù)據(jù)獲取已相對容易,對歷史數(shù)據(jù)分析其結(jié)果可為應(yīng)用提供支撐,例如最優(yōu)路徑推薦、最優(yōu)出行方式及路線規(guī)劃、交通流量預(yù)測等.除了支持時空查詢,系統(tǒng)也需要對用戶的位置信息進(jìn)行有效保護(hù),針對這一問題,有學(xué)者開展了基于位置隱私保護(hù)的研究.

人的運(yùn)動除了在自由空間下,更多的時候是在受限空間下,例如道路網(wǎng)[101]、有障礙空間[102]和室內(nèi)環(huán)境.不同環(huán)境的主要區(qū)別在于移動對象位置表示和距離函數(shù):自由空間的位置通過坐標(biāo)表示,距離函數(shù)基于歐式距離;而受限空間下的位置依賴于底層空間環(huán)境,距離函數(shù)與最短路徑相關(guān),求解過程相對復(fù)雜.例如,道路網(wǎng)環(huán)境下采用Map-matching技術(shù),將GPS位置(經(jīng)緯度)映射到道路網(wǎng)從而得到道路網(wǎng)移動對象;在室內(nèi)環(huán)境,移動對象位置獲取一般依靠RFID、WiFi等技術(shù),位置表示則采用基于符號的表示方法.上述工作均是針對單個空間環(huán)境下的移動對象,也有學(xué)者將多個環(huán)境的不同位置表示方法相融合,形成統(tǒng)一的位置表示方法,支持人的完整運(yùn)動軌跡表示以及不同運(yùn)動方式的移動對象數(shù)據(jù)管理,例如步行→公交車→步行→室內(nèi).

在大數(shù)據(jù)背景下,新應(yīng)用要求數(shù)據(jù)包含更多的信息以全面理解用戶行為,移動對象數(shù)據(jù)也從傳統(tǒng)的時空數(shù)據(jù)拓展到具有語義信息和行為描述[103,104].語義軌跡是將 GPS數(shù)據(jù)和時空場景相結(jié)合,例如興趣點(diǎn)或用戶行為,給移動對象賦予相關(guān)描述(可通過數(shù)據(jù)挖掘算法得出并以標(biāo)簽形式存儲),豐富移動對象表示.基于語義軌跡的常見查詢有模式挖掘和匹配[103]、時空語義關(guān)鍵字查詢、top-k查詢以及移動用戶行為分析(規(guī)律性地訪問某些位置、規(guī)避和會合等).基于硬件的技術(shù)也被用于大規(guī)模軌跡數(shù)據(jù)查詢和分析,例如基于主存的軌跡存儲和查詢方法、分布式/并行軌跡數(shù)據(jù)處理平臺(基于Spark和Hadoop)、基于GPU的交互式時空數(shù)據(jù)查詢等,軌跡數(shù)據(jù)可視化技術(shù)也有相關(guān)研究.

4.3.4 時空數(shù)據(jù)管理系統(tǒng)

時空數(shù)據(jù)管理系統(tǒng)的設(shè)計主要有兩種思路:一種是對傳統(tǒng)關(guān)系數(shù)據(jù)庫管理系統(tǒng)的內(nèi)核修改或擴(kuò)展以支持時空數(shù)據(jù)管理,包括數(shù)據(jù)類型、訪問方法、查詢語言等;另一種則通過在應(yīng)用層和傳統(tǒng)數(shù)據(jù)庫管理系統(tǒng)層之間構(gòu)建一層結(jié)構(gòu),用于時空數(shù)據(jù)和傳統(tǒng)數(shù)據(jù)的相互轉(zhuǎn)換,即,在應(yīng)用層以時空數(shù)據(jù)處理而在系統(tǒng)存儲層還是以傳統(tǒng)數(shù)據(jù)形式來加以處理.第1種方法能夠保證效率最優(yōu),第2種方法則能夠在較短時間內(nèi)達(dá)到實(shí)際可行的效果.

并行處理技術(shù)在時空數(shù)據(jù)庫領(lǐng)域也得到了快速發(fā)展,主要用于大規(guī)模數(shù)據(jù)查詢處理[105].在空間數(shù)據(jù)庫方面,SpatialHadoop和HadoopGIS均是基于Hadoop的空間數(shù)據(jù)處理系統(tǒng),Simba是基于Spark技術(shù)的空間數(shù)據(jù)分析系統(tǒng)[106],其對 SparkSQL進(jìn)行了擴(kuò)展,能夠有效地支持并發(fā)查詢.在時態(tài)數(shù)據(jù)庫方面,有基于PostgreSQL的時態(tài)數(shù)據(jù)查詢原型系統(tǒng)和在線實(shí)時時態(tài)數(shù)據(jù)分析系統(tǒng) OceanRT.在移動對象數(shù)據(jù)庫方面,有針對軌跡數(shù)據(jù)處理的引擎 Hermes、支持多種軌跡數(shù)據(jù)挖掘操作及可視化系統(tǒng) MoveMine、基于內(nèi)存的分布式系統(tǒng) SharkDB、DITA[107]、軌跡數(shù)據(jù)在線分析系統(tǒng)T-Warehouse、大規(guī)模軌跡數(shù)據(jù)管理和分析平臺UlTraMan[108].SECONDO是一個開源可擴(kuò)充性數(shù)據(jù)庫管理系統(tǒng),可對空間、時態(tài)和移動對象數(shù)據(jù)有效管理且支持并行處理[109].

4.4 總結(jié)與展望

時空大數(shù)據(jù)具有多維度、多類型、變化快等特點(diǎn),給數(shù)據(jù)庫管理系統(tǒng)提出了新的挑戰(zhàn):一方面,需要提供數(shù)據(jù)類型和運(yùn)算操作以支持時空數(shù)據(jù)查詢;另一方面,高效查詢處理對數(shù)據(jù)庫性能有較高的要求.迄今,時空數(shù)據(jù)庫的發(fā)展趨勢包含以下幾點(diǎn).

· 具有語義描述的時空數(shù)據(jù)管理,可分為時空數(shù)據(jù)和流數(shù)據(jù)兩類:前者針對包含關(guān)鍵字的時空數(shù)據(jù)進(jìn)行查詢,后者針對高頻率的流數(shù)據(jù)進(jìn)行連續(xù)查詢.為增加用戶滿意度,交互式和探索式查詢也是進(jìn)一步研究的方向之一;

· 并行/分布式環(huán)境下的大規(guī)模時空數(shù)據(jù)管理系統(tǒng).現(xiàn)有的時空數(shù)據(jù)庫原型系統(tǒng)需要在支持的查詢種類和通用性數(shù)據(jù)表示上進(jìn)一步提升.同時,隨著越來越多的時空數(shù)據(jù)管理系統(tǒng)被研發(fā),需要在統(tǒng)一標(biāo)準(zhǔn)下對系統(tǒng)的功能及性能進(jìn)行全面測試和評估(benchmark).新型存儲設(shè)備(例如,SSD具有快速隨機(jī)寫等特點(diǎn))的發(fā)展,將給位置頻繁更新的移動對象研究帶來新的契機(jī);

· 具有智能性的時空數(shù)據(jù)庫系統(tǒng).在人工智能技術(shù)快速發(fā)展的背景下,如何融入機(jī)器學(xué)習(xí)方法以增加系統(tǒng)的智能性,是新一代時空數(shù)據(jù)庫管理系統(tǒng)研究的內(nèi)容,即,系統(tǒng)根據(jù)當(dāng)前處理數(shù)據(jù)及查詢的特點(diǎn)自動進(jìn)行索引結(jié)構(gòu)和相關(guān)算法的調(diào)整以使性能最優(yōu),例如參數(shù)配置、數(shù)據(jù)劃分、緩存設(shè)置等.

5 眾包數(shù)據(jù)庫

5.1 引 言

Web 2.0時代涌現(xiàn)出了海量的在線互聯(lián)網(wǎng)應(yīng)用.這些應(yīng)用在悄然改變?nèi)藗兩畹耐瑫r,也為傳統(tǒng)的人本計算(human computation)提供了一種通過群體智慧求解問題的新模式——眾包[110],即“一種把過去由專職員工執(zhí)行的任務(wù),通過公開的 Web平臺,以自愿的形式外包給非特定的解決方案提供者群體來完成的分布式問題求解模式”[111].在過去的10余年里,基于Web的眾包技術(shù)已與人們的日常生活息息相關(guān).維基百科(Wikipedia)、雅虎問答(Yahoo! Answers)以及百度知道等各類“問答系統(tǒng)”平臺均是這一技術(shù)的典型代表.近年來,移動互聯(lián)網(wǎng)的爆發(fā)更是催生出眾包的新形態(tài)——時空眾包[112,113].這是一種新型眾包計算模式,以時空數(shù)據(jù)管理平臺為基礎(chǔ),將具有時空特性的眾包任務(wù)分配給非特定的眾包參與者群體為核心操作,并要求眾包參與者以主動或被動的方式來完成眾包任務(wù),并滿足任務(wù)所指定的時空約束條件.時空眾包因具有信息世界與物理世界相聯(lián)系的特點(diǎn),使其成為共享經(jīng)濟(jì)的新型計算范式.實(shí)時專車類應(yīng)用滴滴出行和物流派送類應(yīng)用百度外賣都是共享經(jīng)濟(jì)時代時空眾包應(yīng)用的典型代表,并取得了巨大成功.眾包在通過互聯(lián)網(wǎng)匯聚群體智慧求解各類問題的過程中,動態(tài)生成海量多源異構(gòu)數(shù)據(jù),對這些數(shù)據(jù)進(jìn)行有效的管理,是發(fā)揮眾包應(yīng)用價值的關(guān)鍵.

5.2 主要研究問題

眾包數(shù)據(jù)管理的主要研究問題來自眾包工作流程中的3個不同階段.

· 第1階段:眾包任務(wù)的發(fā)布者將任務(wù)提交至眾包數(shù)據(jù)管理系統(tǒng),系統(tǒng)將任務(wù)分配給適當(dāng)?shù)谋姲鼌⑴c者執(zhí)行;

· 第2階段:眾包參與者將任務(wù)執(zhí)行結(jié)果提交給眾包數(shù)據(jù)管理系統(tǒng),系統(tǒng)對這些結(jié)果進(jìn)行集成和處理后,將最終結(jié)果反饋給眾包任務(wù)發(fā)布者;

· 第3階段:眾包任務(wù)發(fā)布者收到系統(tǒng)反饋的任務(wù)執(zhí)行結(jié)果后,根據(jù)任務(wù)完成質(zhì)量等因素向眾包參與者提供適當(dāng)?shù)膱蟪?

上述工作流程中的3個階段反映了眾包數(shù)據(jù)管理中的3個研究問題.

· 任務(wù)分配:該問題涉及眾包工作流程的第 1階段,其核心目標(biāo)是將眾包任務(wù)分配給合適的參與者,以實(shí)現(xiàn)各類不同的優(yōu)化目標(biāo).例如,在基于Web的眾包中,眾包任務(wù)會根據(jù)其類型被分配給擅長執(zhí)行該類任務(wù)的參與者,以優(yōu)化任務(wù)完成的質(zhì)量;在時空眾包中,眾包任務(wù)通常會被分配給任務(wù)位置附近的參與者,以優(yōu)化任務(wù)發(fā)布者的等待時間.對該問題的研究主要面臨以下難點(diǎn):(1) 任務(wù)分配具有動態(tài)性,即眾包任務(wù)和參與者動態(tài)出現(xiàn)在眾包平臺上;(2) 任務(wù)分配具有約束復(fù)雜性,即將任務(wù)分配給參與者通常需滿足各項(xiàng)約束條件;(3) 任務(wù)分配還要求兼顧有效性和效率.上述難點(diǎn)要求研究人員在對眾包數(shù)據(jù)進(jìn)行有效存儲和索引的基礎(chǔ)上,設(shè)計高效的求解算法;

· 質(zhì)量控制:該問題涉及眾包工作流程的第 2階段.眾包通過匯聚人類的群體智慧求解各類問題.因?yàn)槿穗y免會犯錯,所以眾包數(shù)據(jù)管理系統(tǒng)通常無法將眾包參與者所反饋的任務(wù)執(zhí)行結(jié)果直接反饋給任務(wù)發(fā)布者,而需要對結(jié)果進(jìn)行質(zhì)量處理.在基于Web的眾包中,系統(tǒng)通常根據(jù)對眾包參與者可靠程度、擅長領(lǐng)域和對問題的難度等因素建模,通過投票等方式對任務(wù)的結(jié)果正確性進(jìn)行推斷,并將結(jié)果的可靠程度一并返回給任務(wù)發(fā)布者;在時空眾包中,系統(tǒng)則主要會考慮到任務(wù)位置與參與者的距離以及參與者的上線等時空因素,對任務(wù)完成的質(zhì)量進(jìn)行控制;

· 激勵機(jī)制:該問題涉及眾包工作流程的第3階段.眾包參與者執(zhí)行任務(wù)需要花費(fèi)各類稀缺資源,例如:在基于Web的眾包中,參與者執(zhí)行各類圖片標(biāo)注任務(wù)需花費(fèi)注意力;而在時空眾包中,網(wǎng)約車平臺的私家車車主則需付出車輛的使用成本等.眾包數(shù)據(jù)管理系統(tǒng)需要對參與者進(jìn)行有效激勵,以使得他們愿意繼續(xù)留在眾包系統(tǒng)中以提供服務(wù).雖然金錢激勵是直接而有效的激勵方式,但是制定健全而合理的激勵額度并不是一個簡單的問題.在基于 Web的眾包中,參與者完成任務(wù)的質(zhì)量以及任務(wù)的難度是激勵機(jī)制設(shè)計的重要參考指標(biāo),而在時空眾包中,不同時空區(qū)域內(nèi)任務(wù)和參與者之間的供需狀況也會對激勵機(jī)制產(chǎn)生影響.

除上述研究問題外,眾包數(shù)據(jù)管理還研究眾包任務(wù)的設(shè)計、對眾包參與者隱私的保護(hù)等方面.

5.3 國內(nèi)外研究現(xiàn)狀

近年來,國內(nèi)外研究人員已展開了眾包數(shù)據(jù)處理的相關(guān)研究,并取得了不少技術(shù)突破[114-116].眾包數(shù)據(jù)處理可分為兩類:眾包數(shù)據(jù)管理機(jī)制與基于眾包策略的數(shù)據(jù)處理技術(shù).此外,基于上述研究,人們還設(shè)計和開發(fā)了各類眾包數(shù)據(jù)管理系統(tǒng).

5.3.1 眾包數(shù)據(jù)管理機(jī)制

下文將對任務(wù)分配、質(zhì)量控制與激勵機(jī)制這3類問題進(jìn)行簡單分析.

1) 任務(wù)分配

任務(wù)分配一直都是算法研究領(lǐng)域的重要問題之一,文獻(xiàn)[117]首先針對單一用戶所提供的同一類型眾包任務(wù)定義了在線任務(wù)分配問題,旨在一段時間內(nèi),以在線方式最大化眾包任務(wù)分配數(shù)量.文獻(xiàn)[117]設(shè)計了一種采用原始對偶模式(primal-dual schema)的近似算法用于在線任務(wù)分配.后續(xù)工作擴(kuò)展了在線任務(wù)分配問題的定義,提出了在線異構(gòu)任務(wù)分配問題,也針對此問題擴(kuò)展了原始對偶模式近似算法[118].文獻(xiàn)[119]針對時空眾包中任務(wù)和參與者均動態(tài)出現(xiàn)的應(yīng)用場景,提出了具有競爭比保證的任務(wù)分配算法,以最大化總收益.文獻(xiàn)[120]研究了最小化眾包參與者總移動距離的雙邊在線任務(wù)分配問題.文獻(xiàn)[121]考慮到眾包任務(wù)執(zhí)行場所的影響,研究了面向 3類對象的在線任務(wù)分配問題.文獻(xiàn)[122]提出了基于預(yù)測[123]的眾包參與者調(diào)度和眾包任務(wù)分配算法.文獻(xiàn)[124]針對拼車問題提出了通用的優(yōu)化方法,其解決方案適用于眾包參與者具有容量約束的眾包任務(wù)分配問題.

2) 質(zhì)量控制

眾包技術(shù)已被應(yīng)用于眾多領(lǐng)域,質(zhì)量控制機(jī)制是眾包研究的核心問題之一,針對各類具體應(yīng)用的眾包質(zhì)量控制研究被廣泛提出.具體而言,眾包數(shù)據(jù)處理的質(zhì)量控制機(jī)制研究可分為如下兩類:(1) 眾包參與者誤差估計;(2) 眾包結(jié)果的集成機(jī)制.前者側(cè)重于對不同眾包參與者單一個體的誤差估計;而后者需根據(jù)誤差估計所得誤差概率,再進(jìn)一步對不同眾包參與者的反饋進(jìn)行符合質(zhì)量控制要求的結(jié)果集成,并匯聚成最終答案.下文將對這兩方面研究分別加以簡要回顧.

眾包參與者誤差估計通常是指采用少數(shù)服從多數(shù)原則、EM算法或其他學(xué)習(xí)算法,根據(jù)眾包參與者的歷史數(shù)據(jù)推斷出眾包參與者的誤差率.文獻(xiàn)[125]針對標(biāo)注查詢設(shè)計了一種概率圖模型,用來推斷任務(wù)標(biāo)注、每位眾包參與者的誤差率與眾包任務(wù)難度.文獻(xiàn)[126]提出了一種經(jīng)驗(yàn)貝葉斯算法——SpEM,通過EM框架中的迭代過程來清除水軍用戶,從而采用真實(shí)標(biāo)注對最終標(biāo)注結(jié)果進(jìn)行估計.另一類有代表性的工作是針對不同的眾包任務(wù)選擇不同的眾包參與者,從而保證執(zhí)行每個眾包任務(wù)的眾包參與者的誤差率盡可能地小.例如,文獻(xiàn)[127]提出了一種選擇性重復(fù)標(biāo)注的方法,通過重復(fù)標(biāo)注來提高標(biāo)注結(jié)果的準(zhǔn)確性.以上 3項(xiàng)研究均提供了啟發(fā)式的眾包參與者誤差估計算法,而如下 3項(xiàng)工作又進(jìn)一步對其所估計的誤差率進(jìn)行了定界分析:當(dāng)給定一個眾包參與者的集合時,文獻(xiàn)[128]證明了全部眾包參與者集體的誤差估計值上界,但無法用于單一眾包參與者誤差的估計;對于單一的眾包任務(wù),文獻(xiàn)[129]證明了每項(xiàng)任務(wù)所最終得到正確答案的概率上界與下界,但其所分析的目標(biāo)為眾包任務(wù)而非眾包參與者的誤差率;最后,文獻(xiàn)[130]對單一眾包參與者誤差進(jìn)行了區(qū)間估計分析,并對眾包參與者的誤差估計提供了置信區(qū)間估計算法.

眾包結(jié)果的集成機(jī)制:根據(jù)眾包參與者誤差的估計值,對一項(xiàng)眾包任務(wù)的不同眾包參與者反饋進(jìn)行集成并產(chǎn)生最終任務(wù)結(jié)果,也是眾包質(zhì)量控制機(jī)制的一個主要研究方向.文獻(xiàn)[131]提出了一個質(zhì)量敏感應(yīng)答模型CDAS,包含預(yù)測模型與驗(yàn)證模型兩個子模型:前者用于估計一項(xiàng)指定眾包任務(wù)所需眾包參與者的數(shù)量,后者則根據(jù)用戶反饋選擇最優(yōu)答案.另一類有代表性的工作是根據(jù)眾包參與者的誤差率,為一項(xiàng)眾包任務(wù)發(fā)現(xiàn)一個最優(yōu)的眾包參與者群體,又被稱為陪審團(tuán)(jury).最優(yōu)有兩類定義:第 1類是指在給定眾包預(yù)算成本的條件下,發(fā)現(xiàn)一個陪審團(tuán),使其對此任務(wù)的陪審團(tuán)錯誤率(jury error rate,簡稱JER)盡可能地小[132];另一類定義是指在給定陪審團(tuán)錯誤率的條件下,發(fā)現(xiàn)一個陪審團(tuán),使其支付成本盡可能地小[133].文獻(xiàn)[132]證明了第 1類定義是 NP-Hard的,并給出相應(yīng)的近似求解算法;隨后也對第2類定義給出了相應(yīng)的近似算法[133].

(3) 激勵機(jī)制

激勵機(jī)制也一直是眾包機(jī)制研究的核心.對于一項(xiàng)指定的眾包任務(wù),在眾包平臺中應(yīng)該如何定價才能保證有足夠的眾包參與者協(xié)同完成此任務(wù).文獻(xiàn)[134]針對通用在線眾包平臺上的眾包市場提出了兩種定價策略:第1種是在給定眾包任務(wù)預(yù)算約束的條件下,通過優(yōu)化定價策略來最大化被分配的任務(wù)數(shù)量;第2種是在給定需完成任務(wù)數(shù)量的約束條件下,最小化支付成本.針對每種定價策略,文獻(xiàn)[135]分別給出了常數(shù)競爭比的在線近似算法.文獻(xiàn)[135]提出了一個基于遺憾最小化方法(regret minimization approach)的在線定價機(jī)制,該機(jī)制提出一種基于貪心策略的采購拍賣算法,從而獲得近似最優(yōu)的求解保障.文獻(xiàn)[136]著重研究了完成眾包任務(wù)的時間延遲與眾包定價策略之間的關(guān)系.針對給定任務(wù)完成截止時間與給定任務(wù)預(yù)算成本兩類不同約束條件,分別設(shè)計了一系列基于隨機(jī)過程的最優(yōu)定價算法,并證明了近似算法存在近似最優(yōu)解.文獻(xiàn)[137]研究了針對復(fù)雜眾包任務(wù)的激勵機(jī)制,通過將復(fù)雜任務(wù)適當(dāng)?shù)胤纸獬晌⑷蝿?wù),在滿足任務(wù)完成質(zhì)量的約束下最小化支付成本.文獻(xiàn)[138]針對時空眾包市場中不同空間區(qū)域和時間段供需不平衡的特點(diǎn),提出了基于匹配的動態(tài)定價策略.

綜上所述,3類眾包數(shù)據(jù)管理機(jī)制的研究都針對于現(xiàn)存的在線眾包平臺,如 AMT、CrowdFlower和 oDesk等.下面兩節(jié)將分別進(jìn)一步闡述3類機(jī)制在眾包數(shù)據(jù)處理和眾包數(shù)據(jù)管理系統(tǒng)中的應(yīng)用和擴(kuò)展工作.

5.3.2 基于眾包策略的數(shù)據(jù)處理技術(shù)

眾包數(shù)據(jù)處理技術(shù)作為當(dāng)前數(shù)據(jù)庫與數(shù)據(jù)挖掘領(lǐng)域一項(xiàng)新興的研究熱點(diǎn),主要側(cè)重于如何將眾包策略融入到傳統(tǒng)數(shù)據(jù)庫管理系統(tǒng)的經(jīng)典查詢處理與挖掘操作之中,從而提高數(shù)據(jù)處理的質(zhì)量或拓寬查詢處理與挖掘操作的應(yīng)用范圍.本節(jié)主要對現(xiàn)存的基于眾包策略的幾類經(jīng)典查詢與挖掘技術(shù)進(jìn)行簡要的回顧.

(1) 篩選查詢

在基于眾包策略的查詢處理中,最基礎(chǔ)的一項(xiàng)查詢處理操作是篩選查詢(flitering query),文獻(xiàn)[139]首次在眾包數(shù)據(jù)處理的背景下提出此類查詢和其求解框架CrowdScreen.CrowdScreen的主要貢獻(xiàn)在于,其并不認(rèn)為簡單的少數(shù)服從多數(shù)原則是合理的,并分別以眾包期望成本與結(jié)果期望誤差率為優(yōu)化目標(biāo),將眾包的篩選查詢細(xì)化為 5類情況,并對每種情況給出了確定性與概率性求解算法.其后續(xù)擴(kuò)展工作進(jìn)一步放松了文獻(xiàn)[139]的眾多假設(shè)條件,從而進(jìn)一步提高了通用性[140].通過增加眾包參與者們的先驗(yàn)信息與后驗(yàn)信息,以及對不同用戶能力的細(xì)化分析,大幅度提高了算法執(zhí)行效率,同時也降低了眾包支付成本.

(2) 排序查詢與Top-k查詢

排序查詢(ranking query)與 Top-k查詢始終是數(shù)據(jù)處理技術(shù)中的核心操作之一.文獻(xiàn)[141]首先定義了眾包環(huán)境下的最大者查詢問題,即 Top-1查詢,該問題旨在返回滿足投票矩陣的條件下具有最大可能性的數(shù)值最大者.文獻(xiàn)[141]也證明了該問題是 NP-Hard,設(shè)計了一系列的啟發(fā)式求解算法.文獻(xiàn)[142]擴(kuò)展了上述研究結(jié)果,提出了基于眾包的Top-k查詢,即:在滿足誤差閾值的情況下,最小化眾包支付成本(即眾包參與者為成對數(shù)據(jù)項(xiàng)進(jìn)行比較的次數(shù)).文獻(xiàn)[142]證明了此眾包期望支付成本的理論下界.文獻(xiàn)[143]提出了一個基于打分和排序的眾包Top-k查詢計算框架.

(3) 連接查詢、實(shí)體同一與模式匹配

連接查詢是數(shù)據(jù)庫領(lǐng)域的經(jīng)典查詢操作之一,其在眾包數(shù)據(jù)處理中通常是指基于眾包的實(shí)體同一性查詢.實(shí)體同一性查詢(entity resolution)與模式匹配(schema matching)是關(guān)系數(shù)據(jù)庫的數(shù)據(jù)集成過程中兩類重要的操作.

實(shí)體同一(基于眾包的連接查詢):文獻(xiàn)[144]提出一種人機(jī)混合的實(shí)體同一性查詢通用求解框架——CrowdER.該框架假設(shè)眾包參與者的反饋一定正確,將基于眾包的實(shí)體同一性查詢歸約到基于聚類的 HIT(human intelligence task)產(chǎn)生問題,并證明了此問題是NP-Hard,同時給出兩種高效的啟發(fā)式算法求解該問題.文獻(xiàn)[145]擴(kuò)展了文獻(xiàn)[144]的求解框架,并融入了實(shí)體間傳遞性的概念,大幅度提升了基于眾包的實(shí)體同一性查詢效率.文獻(xiàn)[146]考慮了不同實(shí)體之間同一性的先驗(yàn)概率分布,以最小化眾包任務(wù)期望詢問數(shù)量為目標(biāo),證明該優(yōu)化問題是NP-Hard,并給出了相應(yīng)的隨機(jī)求解算法.

模式匹配:文獻(xiàn)[147]首先提出了基于眾包的模式匹配問題,并通過可能世界語義對該問題進(jìn)行了形式化描述,采用信息熵來度量模式匹配中任意兩模式相似度的穩(wěn)定性.根據(jù)信息熵設(shè)計了基于貪心策略的模式匹配問詢機(jī)制,從而最小化眾包支付成本.文獻(xiàn)[148]研究了基于眾包策略的Web表格匹配問題,提出一種新型的效用函數(shù),既包含匹配難度,又可測量不同Web表格屬性間的相似性.基于此效用函數(shù),文獻(xiàn)[148]證明Web表格匹配問題是NP-Hard,并給出了近似比為(1-1/e)的近似算法.

(4) 計數(shù)問題與枚舉查詢

計數(shù)問題是集成查詢(aggregation query)的基礎(chǔ),也是傳統(tǒng)關(guān)系數(shù)據(jù)庫理論中Group By子句執(zhí)行的關(guān)鍵.為了擴(kuò)展傳統(tǒng)集成查詢的適用范圍,文獻(xiàn)[149]首先提出了基于眾包的計數(shù)問題,即:給定一個數(shù)據(jù)項(xiàng)集合與一個篩選規(guī)則,令每名眾包參與者反饋符合篩選規(guī)則的數(shù)據(jù)項(xiàng)個數(shù)(可以不很精確),匯聚全部眾包參與者的反饋并估計最終符合篩選規(guī)則的數(shù)據(jù)項(xiàng)個數(shù).不同于傳統(tǒng)的基于二選一投票類型的眾包操作,文獻(xiàn)[149]的眾包基礎(chǔ)操作就是一個粗糙的計數(shù)問題.同時,也針對網(wǎng)絡(luò)水軍(spammers)的檢測與清除設(shè)計了處理機(jī)制,最終給出了一種基于置信區(qū)間的計數(shù)估計算法.

枚舉查詢也是傳統(tǒng)數(shù)據(jù)處理的核心問題之一,其結(jié)果集的唯一性源自于傳統(tǒng)數(shù)據(jù)庫中的封閉世界假設(shè)(closed world assumption).為了擴(kuò)展眾包數(shù)據(jù)處理的范圍,文獻(xiàn)[150]打破了封閉世界假設(shè),并提出了基于眾包策略的枚舉查詢.在沒有封閉數(shù)據(jù)庫支持的情況下,新型查詢將處理如“枚舉北京航空航天大學(xué)喜愛看電影的同學(xué)”的查詢問題.核心思想在于通過不同眾包參與者的反饋分析其所枚舉的交集比重,采用置信區(qū)間以估計值快速計算枚舉結(jié)果的可信度,同時,在滿足置信度約束的情況下最小化眾包支付成本.

(5) 關(guān)聯(lián)規(guī)則挖掘與聚類分析

本部分主要介紹兩類基于眾包策略的數(shù)據(jù)挖掘研究.其中,關(guān)聯(lián)規(guī)則挖掘與聚類分析都是傳統(tǒng)數(shù)據(jù)挖掘中的核心技術(shù),最近的相關(guān)研究已將眾包策略有效地融入到兩類技術(shù)之中,擴(kuò)展了它們的適用范圍.文獻(xiàn)[151]打破了傳統(tǒng)數(shù)據(jù)庫中的“封閉世界假設(shè)”,進(jìn)而提出基于眾包的關(guān)聯(lián)規(guī)則挖掘問題.旨在通過收集人腦中的關(guān)聯(lián)規(guī)則經(jīng)驗(yàn),通過詢問眾包參與者形如“A與B是否經(jīng)常一起出現(xiàn)?”的問題來估計不同項(xiàng)集的支持度,從而估計出關(guān)聯(lián)規(guī)則的置信度.文獻(xiàn)[152]提出了一個貝葉斯模型來學(xué)習(xí)不同眾包參與者的聚類特點(diǎn)與數(shù)據(jù)項(xiàng)自身的結(jié)構(gòu)性特點(diǎn),從而獲取基于眾包的高質(zhì)量聚類結(jié)果.

5.3.3 眾包數(shù)據(jù)管理系統(tǒng)

近年來,隨著對眾包數(shù)據(jù)管理機(jī)制和基于眾包策略的數(shù)據(jù)處理技術(shù)的研究日益深入,依據(jù)上述成果的眾包數(shù)據(jù)管理系統(tǒng)也被設(shè)計和開發(fā)出來.代表性的眾包數(shù)據(jù)管理系統(tǒng)有眾包數(shù)據(jù)庫 CrowdDB[153]、Deco[154]、Qurk[155]、CDB[156]和眾包數(shù)據(jù)管理平臺DOCS[157]、gMission[158]等,下面分別對這些系統(tǒng)進(jìn)行簡要介紹.

CrowdDB通過引入眾包機(jī)制,使得數(shù)據(jù)庫系統(tǒng)能夠完成一些本來無法完成的查詢操作,如針對未知或不完整信息的查詢、涉及主觀比較的查詢等.CrowdDB使用擴(kuò)展自 SQL的查詢語言 CrowdSQL,支持用戶使用“CROWD”關(guān)鍵字定義數(shù)據(jù)表和屬性,指示數(shù)據(jù)表的內(nèi)容和屬性列中的值需要通過眾包補(bǔ)充完整.CrowdDB設(shè)計和實(shí)現(xiàn)了相應(yīng)的查詢編譯和運(yùn)行時系統(tǒng),能夠通過自動生成的用戶接口利用眾包獲取數(shù)據(jù).

Deco與CrowdDB類似,同樣提供了基于SQL的查詢語言,允許用戶通過該語言在系統(tǒng)中存儲的關(guān)系數(shù)據(jù)和通過眾包獲取的數(shù)據(jù)上進(jìn)行各類查詢.此外,Deco設(shè)計了具備可擴(kuò)展性和通用性的數(shù)據(jù)模型,支持?jǐn)?shù)據(jù)清洗等功能,并定義了精確的查詢語義.Deco的查詢處理器使用了一種新型的推拉混合式執(zhí)行模型,在執(zhí)行查詢的同時,兼顧眾包本身具有的時延、不確定性等特點(diǎn)所帶來的挑戰(zhàn).

Qurk使用基于SQL的查詢語言,并支持用戶定義函數(shù)(user-defined functions,簡稱UDFs).為了方便用戶使用UDFs,Qurk提供了預(yù)定義的眾包任務(wù)模板,可以生成支持過濾和排序等眾包任務(wù)的眾包界面.此外,Qurk設(shè)計了任務(wù)緩存和任務(wù)模型進(jìn)行查詢優(yōu)化:任務(wù)緩存將先前眾包任務(wù)的結(jié)果緩存起來,任務(wù)模型基于已經(jīng)收集到的眾包數(shù)據(jù)訓(xùn)練模型預(yù)測眾包任務(wù)的結(jié)果.無法通過任務(wù)緩存和任務(wù)模型獲取的數(shù)據(jù),將由系統(tǒng)自動地通過眾包方式獲取.

CDB定義了查詢語言CQL并使用基于圖的模型進(jìn)行查詢優(yōu)化,可提供細(xì)粒度的元組級別優(yōu)化.在該模型的基礎(chǔ)上,CDB采取了一種統(tǒng)一框架,可對時延、成本、質(zhì)量等多種目標(biāo)進(jìn)行優(yōu)化.

表6對上述眾包數(shù)據(jù)庫進(jìn)行了比較[159].

Table 6 Comparison of crowdsourcing DB systems表6 眾包數(shù)據(jù)庫系統(tǒng)的比較

除了上述眾包數(shù)據(jù)庫之外,學(xué)術(shù)界也提出了一些眾包數(shù)據(jù)管理平臺.DOCS是一個具備領(lǐng)域感知能力的眾包數(shù)據(jù)管理平臺,它通過知識庫對眾包參與者和眾包任務(wù)涉及的知識領(lǐng)域進(jìn)行分析,并基于分析結(jié)果對參與者完成不同領(lǐng)域任務(wù)的質(zhì)量進(jìn)行細(xì)粒度建模.DOCS同時具備真值推斷和動態(tài)任務(wù)分配功能,能夠利用對參與者擅長領(lǐng)域的細(xì)粒度建模準(zhǔn)確推斷出任務(wù)的真實(shí)結(jié)果,并把眾包任務(wù)分配給擅長任務(wù)相關(guān)領(lǐng)域的眾包參與者.gMission是一個開源的通用時空眾包數(shù)據(jù)管理平臺,具有任務(wù)分配和結(jié)果集成功能.

5.4 總結(jié)與展望

現(xiàn)存的研究已將眾包策略成功地集成到傳統(tǒng)數(shù)據(jù)處理技術(shù)之中.眾包策略可以提高傳統(tǒng)數(shù)據(jù)處理技術(shù)的準(zhǔn)確性,同時可打破傳統(tǒng)數(shù)據(jù)處理的“封閉世界假設(shè)”,從而擴(kuò)展傳統(tǒng)數(shù)據(jù)處理技術(shù)的適用范圍.此外,近年來,隨著移動互聯(lián)網(wǎng)技術(shù)的廣泛應(yīng)用,時空眾包數(shù)據(jù)處理技術(shù)正在成為眾包數(shù)據(jù)處理研究中的新興熱點(diǎn).為了進(jìn)一步完善眾包數(shù)據(jù)管理系統(tǒng),以下問題還有待解決.

· 眾包數(shù)據(jù)管理系統(tǒng)的查詢優(yōu)化問題.不同于傳統(tǒng)數(shù)據(jù)庫的查詢優(yōu)化問題,其不同查詢方案的執(zhí)行成本可得到較為準(zhǔn)確的估計,且優(yōu)化目標(biāo)較為單一;在眾包數(shù)據(jù)庫中,由于所涉及的眾包群體存在較大不確定性,且優(yōu)化目標(biāo)涉及時延、質(zhì)量、花費(fèi)等諸多復(fù)雜因素,眾包數(shù)據(jù)管理系統(tǒng)的查詢優(yōu)化問題還未得到有效解決;

· 時空眾包數(shù)據(jù)的存儲與索引問題.因?yàn)闀r空眾包數(shù)據(jù)包含動態(tài)的時空數(shù)據(jù)、高維屬性數(shù)據(jù)與時空沖突數(shù)據(jù),所以,傳統(tǒng)的離線靜態(tài)場景中的時空數(shù)據(jù)查詢索引技術(shù)并不適用.如何對空間眾包數(shù)據(jù)進(jìn)行有效的存儲與索引,進(jìn)而支持各類時空眾包數(shù)據(jù)查詢處理,是未來研究的關(guān)鍵.一個極具潛力的研究問題是設(shè)計一種針對時空眾包數(shù)據(jù)特性的存儲策略與通用的索引結(jié)構(gòu);

· 隱私與數(shù)據(jù)保護(hù)問題.眾包機(jī)制已經(jīng)廣泛應(yīng)用于數(shù)據(jù)標(biāo)注和收集等任務(wù),在這些任務(wù),特別是時空眾包任務(wù)的執(zhí)行過程中,存在任務(wù)發(fā)布者數(shù)據(jù)泄露以及任務(wù)執(zhí)行者隱私泄露的問題.通用的隱私和數(shù)據(jù)保護(hù)方案可在一定程度上緩解該類問題,但均會對眾包的效率和質(zhì)量造成影響.

6 其他研究熱點(diǎn)

除了上述研究方向外,數(shù)據(jù)庫領(lǐng)域還涌現(xiàn)出很多其他研究熱點(diǎn).例如:新硬件技術(shù)(包括內(nèi)存技術(shù))改變了數(shù)據(jù)庫的底層框架設(shè)計和查詢優(yōu)化的代價模型;近似查詢技術(shù)能夠以更小的代價支持更大規(guī)模數(shù)據(jù)上的查詢;數(shù)據(jù)的可視化技術(shù)為用戶提供更加友好的數(shù)據(jù)展示方式.下面分別簡述這些研究熱點(diǎn).

6.1 新硬件

新硬件技術(shù)的發(fā)展為數(shù)據(jù)管理技術(shù)帶來新的挑戰(zhàn),也帶來明顯的機(jī)遇.作為系統(tǒng)軟件,數(shù)據(jù)庫底層需要針對新硬件的發(fā)展做出適應(yīng)性調(diào)整,充分利用新硬件帶來的便利,同時避免新硬件自身約束導(dǎo)致的新瓶頸.目前研究較多的新硬件包括高性能和專用處理器、高速網(wǎng)絡(luò)、大內(nèi)存(見下一小節(jié))和非易失性內(nèi)存等.

· 基于高性能和專用處理器的數(shù)據(jù)管理方法:目前,高性能處理器技術(shù)進(jìn)入多核時代.相對應(yīng)地,數(shù)據(jù)庫底層核心算法需要充分考慮多核并行的能力,重新設(shè)計連接、排序等基本操作[160].圖形處理器GPU[161]、現(xiàn)場可編程門陣列 FPGA[162]等專用處理器具備更大規(guī)模的數(shù)據(jù)并行操作能力,從而提升數(shù)據(jù)的向量處理效率,支持?jǐn)?shù)據(jù)庫內(nèi)核范圍內(nèi)的機(jī)器學(xué)習(xí)等任務(wù).同時,不同特性異構(gòu)硬件的協(xié)同操作也成為研究問題.例如,GPU的顯存相比于內(nèi)存容量要小,數(shù)據(jù)加載到 GPU顯存的操作代價較高,面向數(shù)據(jù)管理的CPU和GPU的協(xié)同架構(gòu)就是希望充分發(fā)揮不同硬件的優(yōu)勢[163],避免其中可能的瓶頸操作;

· 基于高速網(wǎng)絡(luò)連接的數(shù)據(jù)管理方法:在傳統(tǒng)的分布式數(shù)據(jù)庫或者并行數(shù)據(jù)庫環(huán)境中,網(wǎng)絡(luò)的傳輸速率遠(yuǎn)低于內(nèi)存訪問速率,在分布式查詢和事務(wù)管理等部件中都將網(wǎng)絡(luò)傳輸作為主要代價之一.隨著RDMA等高速網(wǎng)絡(luò)技術(shù)的發(fā)展,網(wǎng)絡(luò)傳輸代價大幅度降低.現(xiàn)有的研究工作基于RDMA高速網(wǎng)絡(luò)的特性,設(shè)計了新的分布式連接方法[164]和分布式并發(fā)控制策略[165]等;

· 基于非易失存儲的數(shù)據(jù)管理方法:非易失型存儲器支持內(nèi)存式的按字節(jié)的高速尋址,同時支持外存式的持久化能力,得到數(shù)據(jù)管理領(lǐng)域的高度關(guān)注.非易失型存儲器存在讀寫操作不對稱和寫耗損等約束.目前,非易失型存儲器的價格較高、容量較小.現(xiàn)有的研究討論了非易失性存儲器和內(nèi)存、閃存等不同特征的存儲介質(zhì)在體系結(jié)構(gòu)層面的結(jié)合方式[166]、非易失存儲環(huán)境中的數(shù)據(jù)庫恢復(fù)機(jī)制[167]等問題.

6.2 內(nèi)存數(shù)據(jù)庫

內(nèi)存數(shù)據(jù)庫就是以內(nèi)存為主要數(shù)據(jù)存儲介質(zhì)、在內(nèi)存中直接對數(shù)據(jù)進(jìn)行操作的數(shù)據(jù)庫.相對于以磁盤為主要存儲介質(zhì)的傳統(tǒng)數(shù)據(jù)庫,內(nèi)存數(shù)據(jù)庫帶來數(shù)量級的性能提升.內(nèi)存數(shù)據(jù)庫的發(fā)展受益于內(nèi)存價格的降低以及內(nèi)存容量的迅猛增加.同時,目前內(nèi)存常見的64位尋址,使得將全部數(shù)據(jù)加載到內(nèi)存空間成為可能.

傳統(tǒng)數(shù)據(jù)庫查詢執(zhí)行的主要瓶頸在于 I/O操作,而在內(nèi)存數(shù)據(jù)庫中,內(nèi)外存數(shù)據(jù)交換不再成為代價的主要來源.內(nèi)存數(shù)據(jù)庫需要考慮現(xiàn)有CPU特性對內(nèi)存操作的影響,如CPU中的緩存、指令和數(shù)據(jù)的預(yù)取、共享數(shù)據(jù)結(jié)構(gòu)上并發(fā)訪問的控制機(jī)制等.上述變化導(dǎo)致內(nèi)存數(shù)據(jù)庫在數(shù)據(jù)組織、數(shù)據(jù)索引、事務(wù)機(jī)制、查詢優(yōu)化等方面與傳統(tǒng)數(shù)據(jù)庫不同[168].

· 數(shù)據(jù)組織.從CPU的角度,內(nèi)存數(shù)據(jù)庫中數(shù)據(jù)可以按照其處理器核進(jìn)行劃分,同一個劃分中數(shù)據(jù)操作串行,減少并發(fā)控制帶來的各種代價;也可以采用所有處理器核都可以訪問全部數(shù)據(jù)的方式.從數(shù)據(jù)版本的角度,內(nèi)存數(shù)據(jù)庫通常采用多版本機(jī)制,提升查詢處理效率.從行列存儲的角度,內(nèi)存數(shù)據(jù)庫可以選擇行存儲或者列存儲,同時,其列存儲在交易型應(yīng)用中表現(xiàn)良好[169];

· 數(shù)據(jù)索引.內(nèi)存數(shù)據(jù)庫索引設(shè)計主要考慮兩個主要因素:首先,內(nèi)存索引節(jié)點(diǎn)的大小一般與CPU緩存大小相關(guān),其索引數(shù)據(jù)的存儲滿足一定的連續(xù)性,從而在索引操作過程中提升CPU緩存的命中率,典型工作如 CSB+樹[170]等;其次,內(nèi)存索引結(jié)構(gòu)的設(shè)計需要考慮多核環(huán)境中的并發(fā)查詢和更新,盡量減少內(nèi)存數(shù)據(jù)結(jié)構(gòu)中并發(fā)鎖的使用,降低索引維護(hù)代價,典型工作如BW樹[171]等;

· 事務(wù)機(jī)制.內(nèi)存數(shù)據(jù)庫的并發(fā)控制機(jī)制主要采用傳統(tǒng)數(shù)據(jù)庫的多版本并發(fā)控制協(xié)議[172],通過保存不同

版本,從而支持無阻塞高效率的讀取操作,部分協(xié)議采用樂觀并發(fā)機(jī)制,引入驗(yàn)證階段判定事務(wù)是否可以提交.此外,考慮 CPU 的多核特性,內(nèi)存數(shù)據(jù)庫還可以在數(shù)據(jù)按照處理器核來劃分的情況下,設(shè)計劃分串行執(zhí)行協(xié)議[173],即:同一劃分內(nèi)數(shù)據(jù)串行操作,劃分之間數(shù)據(jù)并行操作.目標(biāo)是減少多核對同一數(shù)據(jù)并發(fā)控制代價或者沖突導(dǎo)致的回滾代價.

6.3 近似查詢

相對于傳統(tǒng)的數(shù)據(jù)庫精確查詢,近似查詢能夠以較小的代價獲得近似的查詢結(jié)果.近似查詢技術(shù)在大規(guī)模數(shù)據(jù)分析、趨勢發(fā)現(xiàn)、快速可視化等領(lǐng)域都有一定的應(yīng)用前景.近似查詢技術(shù)可以通過不同維度來刻畫,包括所支持查詢的表達(dá)能力、錯誤模型和精度保證、運(yùn)行時刻代價節(jié)省以及預(yù)計算結(jié)構(gòu)的維護(hù)代價等[174].通常認(rèn)為,幾乎不可能構(gòu)建這樣的近似查詢系統(tǒng):其能夠支持豐富 SQL特征查詢,運(yùn)行時刻提供高質(zhì)量的查詢質(zhì)量保證,并且能夠明顯地節(jié)省運(yùn)行時刻的代價.近似查詢技術(shù)可以粗略劃分為兩大類——在線查詢執(zhí)行和通過預(yù)計算結(jié)果支持查詢[175].

· 在線查詢執(zhí)行.其基本思想是:查詢能夠時刻反饋當(dāng)前運(yùn)行結(jié)果,同時提供結(jié)果精度區(qū)間.隨著時間的推移,參與計算的數(shù)據(jù)量增多,查詢結(jié)果精度不斷提升.用戶可以決定什么啟動查詢或者停止查詢.這一模式在粗略觀察數(shù)據(jù)的場景中得到應(yīng)用.此外,這一模式?jīng)]有預(yù)計算結(jié)果的維護(hù)代價.執(zhí)行過程中一般采用采樣策略,查詢基于動態(tài)采樣的數(shù)據(jù)執(zhí)行.現(xiàn)有工作提出了不同采樣策略及其查詢處理策略,例如,偏有效查詢結(jié)果集合采樣的Wander連接策略[176]等.某些在線查詢的方法已經(jīng)集成到開源或者商業(yè)數(shù)據(jù)庫系統(tǒng)中;

· 通過預(yù)計算結(jié)果支持查詢.其基本思想是:引入可控誤差,將大數(shù)據(jù)預(yù)計算為某種形式的、與原有數(shù)據(jù)某個特征類似的“小數(shù)據(jù)”.后續(xù)的查詢直接基于預(yù)計算結(jié)果執(zhí)行.相對于在線采樣,基于預(yù)算結(jié)果的查詢執(zhí)行方式更加高效.針對特定的預(yù)計算結(jié)果和查詢,這種模式能夠給出查詢的精度保證.但是隨著底層數(shù)據(jù)的變化,這些預(yù)計算的數(shù)據(jù)也需要維護(hù).根據(jù)預(yù)計算結(jié)果的形態(tài)不同,預(yù)計算模式可以進(jìn)一步劃分為基于直方圖的近似查詢(等寬直方圖、等高直方圖、壓縮直方圖、自適應(yīng)直方圖等)、基于采樣的近似查詢(隨機(jī)采樣、有偏采樣、重要性采樣等)、基于小波的近似查詢等.這一模式也有相關(guān)的原型系統(tǒng),如 BlinkDB[177]等.

6.4 數(shù)據(jù)可視化

數(shù)據(jù)可視化利用計算機(jī)圖形學(xué)、數(shù)據(jù)分析、用戶交互界面等技術(shù),通過數(shù)據(jù)建模等手段,為用戶提供有效的數(shù)據(jù)呈現(xiàn)方式.數(shù)據(jù)可視化能夠幫助用戶迅速理解數(shù)據(jù)、定位問題.近期發(fā)展的可視化技術(shù)可以從不同維度來刻畫,如可視化后臺的數(shù)據(jù)類型、不同類型的可視化交互技術(shù)等[178].我們主要從數(shù)據(jù)類型的角度,分析數(shù)據(jù)可視化技術(shù)的進(jìn)展.

· 圖數(shù)據(jù)可視化:圖數(shù)據(jù)在很多領(lǐng)域中自然存在,如社交網(wǎng)絡(luò)等.圖數(shù)據(jù)的海量規(guī)模(包括海量的節(jié)點(diǎn)和邊數(shù)據(jù))以及有限的可視空間限制,成為圖數(shù)據(jù)可視化的主要挑戰(zhàn).現(xiàn)有工作側(cè)重于圖簡化的思路[179],通過邊聚集或者點(diǎn)聚集,構(gòu)建不同層次的圖,同時引入交互策略,支持用戶對其感興趣的部分作進(jìn)一步的動態(tài)分析;

· 時空數(shù)據(jù)可視化:時空數(shù)據(jù)是包含時間維度和空間維度的數(shù)據(jù),其空間維度通常與地理系統(tǒng)加以結(jié)合.為了展示對象隨著時空維度的變化情況,采用屬性可視化技術(shù),如將事件流和地理流相結(jié)合的Flowmap方式[180]、時間-空間-事件等信息的三維立方體方式等;

· 多維數(shù)據(jù)可視化:多維數(shù)據(jù)是包括多個維度屬性的數(shù)據(jù),如數(shù)據(jù)倉庫中銷售數(shù)據(jù)等.多維數(shù)據(jù)的可視化技術(shù)目標(biāo)是更加友好地呈現(xiàn)數(shù)據(jù),從而方便用戶對整體分布和不同維度之間關(guān)系的理解.具體的展示方式包括散點(diǎn)圖、平行坐標(biāo)等[181].

7 總 結(jié)

數(shù)據(jù)相關(guān)技術(shù)的發(fā)展給整個社會帶來了巨大的變革,也給相關(guān)的技術(shù)領(lǐng)域帶來了巨大的挑戰(zhàn).不同領(lǐng)域的學(xué)者均嘗試從自身的角度出發(fā)來解決大數(shù)據(jù)的種種問題,基于這些成果構(gòu)建了若干實(shí)際可行的新型系統(tǒng).但是隨著數(shù)據(jù)規(guī)模以及應(yīng)用需求的進(jìn)一步發(fā)展,未來的數(shù)據(jù)管理技術(shù)仍然面臨著新的問題和轉(zhuǎn)變.

· 新型數(shù)據(jù)管理系統(tǒng)需要更自然、更高效地支持不同類型、不同來源的數(shù)據(jù).針對應(yīng)用中出現(xiàn)的不同類型數(shù)據(jù)管理需求,現(xiàn)有的系統(tǒng)大多是通過構(gòu)建專用系統(tǒng)來解決,例如圖數(shù)據(jù)管理系統(tǒng)、時空數(shù)據(jù)管理系統(tǒng)等.而應(yīng)用中,這些數(shù)據(jù)混雜在一起,按照數(shù)據(jù)類型劃分到不同數(shù)據(jù)系統(tǒng)中,這種管理方式不高效,也不自然.新型數(shù)據(jù)管理系統(tǒng)需要提供通用的底層數(shù)據(jù)模型,統(tǒng)一支持不同類型數(shù)據(jù)的存儲、查詢、分析、優(yōu)化等操作;

· 新型數(shù)據(jù)管理系統(tǒng)需要在體系結(jié)構(gòu)方面實(shí)現(xiàn)擴(kuò)展.為了減少系統(tǒng)復(fù)雜性,提高系統(tǒng)穩(wěn)定性,在現(xiàn)階段通過松耦合包容不同類型數(shù)據(jù)的管理系統(tǒng),為用戶提供統(tǒng)一的數(shù)據(jù)管理和分析服務(wù),是支持不同數(shù)據(jù)模型的可行技術(shù)路線.此外,數(shù)據(jù)管理系統(tǒng)需要考慮異構(gòu)的計算資源.異構(gòu)計算環(huán)境廣泛存在于真實(shí)應(yīng)用場景中,包括資源共享與競爭、網(wǎng)絡(luò)和計算能力差異以及新型硬件帶來的異構(gòu)性.異構(gòu)計算環(huán)境會對新型數(shù)據(jù)管理系統(tǒng)的效率帶來極大的影響,同時,新型硬件的發(fā)展也為新型數(shù)據(jù)管理系統(tǒng)提供了新的機(jī)遇;

· 新型數(shù)據(jù)管理系統(tǒng)需要在計算模型方面實(shí)現(xiàn)擴(kuò)展,滿足不同數(shù)據(jù)模型的管理需求,支持系統(tǒng)松耦合管理體系.機(jī)器學(xué)習(xí)是目前的技術(shù)熱點(diǎn),在自然語言處理、計算機(jī)視覺等方面取得突破.新型數(shù)據(jù)管理系統(tǒng)需要和機(jī)器學(xué)習(xí)實(shí)現(xiàn)融合,包括在數(shù)據(jù)庫內(nèi)核層面實(shí)現(xiàn)機(jī)器學(xué)習(xí)方法,深度分析數(shù)據(jù),提供更加強(qiáng)大、友好的用戶接口.此外,機(jī)器學(xué)習(xí)技術(shù)為現(xiàn)有數(shù)據(jù)操作實(shí)現(xiàn)帶來新的思路,如通過學(xué)習(xí)構(gòu)建索引、自然語言查詢等,需要在數(shù)據(jù)管理內(nèi)核方面融入更多的機(jī)器學(xué)習(xí)技術(shù),通過緊耦合提升現(xiàn)有數(shù)據(jù)管理系統(tǒng)的效率和可用性.