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

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

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

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

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

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

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

目前廣泛認(rèn)為大數(shù)據(jù)具有所謂的“4V”特征,即規(guī)模大(volume)、變化快(velocity)、種類雜(variety)和價(jià)值密度低(value).為了有效地應(yīng)對(duì)大數(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ù)處理場(chǎng)景中都有所體現(xiàn).例如社交媒體應(yīng)用中的用戶關(guān)系數(shù)據(jù),若用圖數(shù)據(jù)模型進(jìn)行建模,其涉及的節(jié)點(diǎn)數(shù)可高達(dá)幾億.為了處理這類大規(guī)模的數(shù)據(jù),一個(gè)樸素的想法是分而治之,即,將數(shù)據(jù)分布式地存儲(chǔ)在多臺(tái)機(jī)器上分別處理.據(jù)此,人們提出了各類分布式數(shù)據(jù)管理系統(tǒng).

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

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

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

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

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

1.1 引 言

在大數(shù)據(jù)時(shí)代下,移動(dòng)互聯(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)維、容錯(cuò)容災(zāi)以及滿足ACID屬性的高并發(fā)事務(wù)處理能力.但在實(shí)際設(shè)計(jì)中,一方面受限于 CAP理論[1],即,在必須支持分區(qū)容錯(cuò)性(partition tolerance)的前提下,系統(tǒng)實(shí)現(xiàn)只能側(cè)重一致性(consistency)和可用性(availability)的一個(gè)方面而無法同時(shí)滿足;另一方面,支持ACID事務(wù)屬性及高并發(fā)事務(wù)處理一直是分布式關(guān)系數(shù)據(jù)庫的難點(diǎn).針對(duì)這些挑戰(zhàn),現(xiàn)有的解決策略大致可分成 3類:(1) 將現(xiàn)有商業(yè)關(guān)系數(shù)據(jù)庫(如Oracle、SQLServer、MySQL、PostgreSQL)在分布式集群或者云平臺(tái)上進(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ì)的新型數(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)更新操作完成之后,任何多個(gè)后續(xù)進(jìn)程或線程的訪問都要求返回最近更新值.如果在這個(gè)分布式系統(tǒng)中沒有數(shù)據(jù)副本,那么系統(tǒng)必然滿足數(shù)據(jù)強(qiáng)一致性要求,原因是只有獨(dú)本數(shù)據(jù),才不會(huì)出現(xiàn)數(shù)據(jù)不一致的問題.但是分布式數(shù)據(jù)庫系統(tǒng)的設(shè)計(jì)需要保存多個(gè)副本來提高可用性和容錯(cuò)性,以避免宕機(jī)時(shí)數(shù)據(jù)還沒有復(fù)制,導(dǎo)致提供的數(shù)據(jù)不夠準(zhǔn)確.如何低成本地保證數(shù)據(jù)的強(qiáng)一致性,是分布式數(shù)據(jù)庫系統(tǒng)的一個(gè)重要難題;

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

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

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

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

MySQL集群是一種常見的開源分布式數(shù)據(jù)庫,它基于無共享的(shared-nothing)數(shù)據(jù)存儲(chǔ)模式,采用讀寫分離的主從模式(master-slave)來實(shí)現(xiàn)高可用性.該設(shè)計(jì)方法也被主流的云平臺(tái)關(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ù)庫往往同時(shí)支持MySQL、SQL Server及PostgreSQL等數(shù)據(jù)庫引擎,具有低成本、易運(yùn)維、可伸縮、高可用等優(yōu)勢(shì),并提供容災(zāi)、備份、恢復(fù)、監(jiān)控、遷移等數(shù)據(jù)庫運(yùn)維全套解決方案.

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

國內(nèi)的云關(guān)系數(shù)據(jù)庫也對(duì)數(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管理.同時(shí),用BinlogSvr來支持MySQL的異步復(fù)制協(xié)議以支撐微信后臺(tái)的賬號(hào)系統(tǒng)、企業(yè)微信及QQ郵箱等.網(wǎng)易R(shí)DS則是采用虛擬同步復(fù)制技術(shù),確保所有主機(jī)的更新事務(wù)在提交前都首先在從機(jī)上落盤,保證主從切換后數(shù)據(jù)完全一致.在節(jié)點(diǎn)上使用了并行復(fù)制技術(shù),大幅度提高了從機(jī)回放主機(jī)事務(wù)的速度,復(fù)制延遲消失,保證了在秒級(jí)完成主從切換.

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

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

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

· CP 模式

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

BigTable是一個(gè)GFS[18]之上的索引層,采用兩級(jí)的B+樹索引結(jié)構(gòu).GFS保證至少寫入一次成功的記錄并由BigTable記錄索引.為了保證BigTable的強(qiáng)一致性,同一時(shí)刻同一份數(shù)據(jù)只能被一臺(tái)機(jī)器服務(wù),且BigTable中的Tablet Server沒有對(duì)每個(gè)Tablet備份.HBase是Apache Hadoop中的一個(gè)子項(xiàng)目,屬于BigTable的開源版本,是滿足強(qiáng)一致性的分布式數(shù)據(jù)庫,主要用來存儲(chǔ)非結(jié)構(gòu)化和半結(jié)構(gòu)化的松散數(shù)據(jù).HBase利用Hadoop HDFS[19]作為其文件存儲(chǔ)系統(tǒng),借助 MapReduce[20]計(jì)算模型來處理海量數(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)失敗時(shí),slave節(jié)點(diǎn)有機(jī)會(huì)被提升為主節(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ù)不是最新,則自動(dòng)地從主服務(wù)器請(qǐng)求同步數(shù)據(jù).MongoDB使用基于Raft協(xié)議選主策略,一旦主節(jié)點(diǎn)發(fā)生故障,整個(gè)MongoDB會(huì)進(jìn)行交流,然后選擇一個(gè)合適的slave節(jié)點(diǎn)快速實(shí)現(xiàn)故障恢復(fù).

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

· AP模式

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

Amazon Dynamo[13]是一個(gè)分布式鍵值存儲(chǔ)系統(tǒng),它采用去中心化、松散耦合方式,由數(shù)百個(gè)服務(wù)組成面向服務(wù)架構(gòu),不支持復(fù)雜的查詢.Dynamo利用一致性哈希來完成數(shù)據(jù)分區(qū),給系統(tǒng)中的每個(gè)節(jié)點(diǎn)隨機(jī)分配一個(gè)token,這些token構(gòu)成一個(gè)哈希環(huán).執(zhí)行數(shù)據(jù)存放操作時(shí),首先計(jì)算key的哈希值,然后存放到順時(shí)針方向第1個(gè)大于等于該哈希值的 token節(jié)點(diǎn)上.這種算法的優(yōu)點(diǎn)是:節(jié)點(diǎn)的增刪只會(huì)影響哈希環(huán)中相鄰的節(jié)點(diǎn),對(duì)其他節(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)行存儲(chǔ).在Cassandra寫入數(shù)據(jù)之前,需要先記錄日志(CommitLog),再將數(shù)據(jù)開始寫入ColumnFamily對(duì)應(yīng)的MemTable中.

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

Apache CouchDB[16]是一個(gè)面向文檔數(shù)據(jù)管理的開源數(shù)據(jù)庫,使用JSON存儲(chǔ)半結(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ù)存儲(chǔ)和分析帶來了SQL、NoSQL之外的新思路.NewSQL指的是提供與NoSQL相同的可擴(kuò)展性和性能,并同時(shí)能支持滿足ACID特性的事務(wù).這保留了 NOSQL的高可擴(kuò)展和高性能,且支持關(guān)系模型.融合一致性和可用性的 NewSQL可能是未來大數(shù)據(jù)存儲(chǔ)新的發(fā)展方向.

Spanner是第一個(gè)將數(shù)據(jù)分布到全球規(guī)模的系統(tǒng),并且在外部支持一致的分布式事務(wù),設(shè)計(jì)目標(biāo)是橫跨全球上百個(gè)數(shù)據(jù)中心,覆蓋百萬臺(tái)服務(wù)器.不同于 BigTable版本控制的鍵值存儲(chǔ)模型,Spanner演化為時(shí)間上的多維數(shù)據(jù)庫.舊版本數(shù)據(jù)根據(jù)可配置的垃圾回收政策處理,應(yīng)用可以讀取具有舊時(shí)間戳的數(shù)據(jù).Spanner顯著的特點(diǎn)是外部一致讀寫和在某一時(shí)間戳的全度跨數(shù)據(jù)庫一致讀取.對(duì)于最典型的讀寫事務(wù),Spanner使用常見的兩階段鎖策略(2PL)來控制并發(fā),并實(shí)現(xiàn)了一個(gè)所謂的外部一致性.F1[29]是Google公司提出的建立在Spanner基礎(chǔ)上的用于廣告業(yè)務(wù)的存儲(chǔ)系統(tǒng).F1實(shí)現(xiàn)了豐富的關(guān)系型數(shù)據(jù)庫的特點(diǎn),包括嚴(yán)格遵從的 schema、強(qiáng)力的并行 SQL查詢引擎、通用事務(wù)、變更與通知的追蹤和索引.其存儲(chǔ)被動(dòng)態(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)一致.存儲(chǔ)采用讀寫分離架構(gòu),沒有主從結(jié)構(gòu),集群節(jié)點(diǎn)全對(duì)等,每個(gè)節(jié)點(diǎn)都具備計(jì)算和存儲(chǔ)能力,無單點(diǎn)瓶頸.騰訊DCDB又名TDSQL,是一種兼容MySQL協(xié)議和語法且支持自動(dòng)水平拆分的高性能分布式數(shù)據(jù)庫,即:業(yè)務(wù)顯示為完整的邏輯表,數(shù)據(jù)卻均勻地拆分到多個(gè)分片中.每個(gè)分片默認(rèn)采用主備架構(gòu),提供災(zāi)備、恢復(fù)、監(jiān)控、不停機(jī)擴(kuò)容等全套解決方案,適用于TB或PB級(jí)的海量數(shù)據(jù)場(chǎng)景.這幾年,TDSQL不斷進(jìn)步,研發(fā)了很多新特性,諸如多級(jí)分區(qū)、熱點(diǎn)更新、隱含主鍵、分布式事務(wù)等,不僅有力地支撐了事務(wù)型數(shù)據(jù)庫應(yīng)用,而且在體系結(jié)構(gòu)上也朝Spanner架構(gòu)上邁進(jìn),是一個(gè)名副其實(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ù)副本,才能對(duì)外返回成功,即使丟掉少數(shù)副本,也能保證系統(tǒng)中還有最新的數(shù)據(jù).TiDB的事務(wù)模型采用樂觀鎖,只有在真正提交時(shí)才會(huì)做沖突檢測(cè),如果有沖突,則需要重試.由于分布式事務(wù)要做兩階段提交,并且底層還需要做 Raft復(fù)制,一個(gè)非常大的事務(wù)會(huì)使得提交過程非常慢,并且會(huì)卡住下面的 Raft復(fù)制流程,所以在設(shè)計(jì)上,TiDB和Spanner對(duì)事務(wù)的大小進(jìn)行了限制.

1.4 總結(jié)與展望

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

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

未來幾年,融合關(guān)系數(shù)據(jù)庫和NoSQL優(yōu)勢(shì)的NewSQL將繼續(xù)在分布式數(shù)據(jù)庫領(lǐng)域大放光彩,并成為一個(gè)重要的研究熱點(diǎn).以O(shè)ceanBase和DCDB為代表的國內(nèi)NewSQL系統(tǒng)也將在海量復(fù)雜業(yè)務(wù)的推動(dòng)下持續(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億個(gè)紅包[33].在語義網(wǎng)的Linked Open Data項(xiàng)目中,已有超過1 184個(gè)RDF圖數(shù)據(jù)集,合計(jì)超過800億條邊[34].針對(duì)這些規(guī)模巨大的圖數(shù)據(jù),設(shè)計(jì)與實(shí)現(xiàn)高效的圖數(shù)據(jù)管理系統(tǒng)成為一個(gè)很重要的研究熱點(diǎn).

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

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

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

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

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

2.2 主要研究問題

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

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

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

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

· 圖匹配查詢:給定數(shù)據(jù)圖和查詢圖,圖匹配查詢找出所有在數(shù)據(jù)圖上與查詢圖同構(gòu)的子圖,這個(gè)問題常用于描述針對(duì)圖結(jié)構(gòu)的查詢.圖匹配查詢的應(yīng)用包括化學(xué)分子庫中的分子拓?fù)浣Y(jié)構(gòu)查詢[42]、在一個(gè)社交網(wǎng)絡(luò)圖中的特定社交結(jié)構(gòu)查詢[43]等.面向RDF知識(shí)圖譜數(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)會(huì)將常見的圖運(yùn)算中的基本操作抽象成編程接口.雖然這類系統(tǒng)屏蔽了包括圖數(shù)據(jù)的內(nèi)部數(shù)據(jù)結(jié)構(gòu)表示、分布式環(huán)境下的通信處理等底層系統(tǒng)問題,但是由于是低層次抽象的編程接口,用戶還需要將具體的圖計(jì)算任務(wù)轉(zhuǎn)換成系統(tǒng)提供的低層次抽象編程接口邏輯.

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

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

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

GraphX[53]將圖計(jì)算任務(wù)分成兩種:圖并行計(jì)算任務(wù)(graph-parallel computation)和數(shù)據(jù)并行計(jì)算任務(wù)(dataparallel computation).所謂圖并行計(jì)算任務(wù),主要是指基于BSP點(diǎn)計(jì)算模型來實(shí)現(xiàn)的迭代計(jì)算任務(wù),如PageRank;所謂數(shù)據(jù)并行計(jì)算任務(wù),主要是指圖上代數(shù)運(yùn)算,如構(gòu)建一個(gè)圖、合并兩個(gè)圖、跨越多個(gè)圖等等.GraphX的作者認(rèn)為:現(xiàn)有的圖計(jì)算系統(tǒng)(如Pregel[46]、GraphLab[49])通過限定編程框架的形式來提高圖并行計(jì)算任務(wù)的執(zhí)行效率,但是這些系統(tǒng)并不適合數(shù)據(jù)并行計(jì)算任務(wù).基于上述觀察,GraphX在分布式計(jì)算平臺(tái)Spark[55]的基礎(chǔ)上構(gòu)建了GraphX,以同時(shí)處理圖并行計(jì)算任務(wù)和數(shù)據(jù)并行計(jì)算任務(wù).GraphX以圖為第1類組成對(duì)象,以屬性圖為數(shù)據(jù)模型.所謂屬性圖,就是每個(gè)點(diǎn)和每條邊都可以關(guān)聯(lián)一個(gè)屬性值表.GraphX定義了很多圖上的操作.既包括一些圖并行計(jì)算任務(wù),如Pregel等,也包括一些數(shù)據(jù)并行計(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)為了方便用戶對(duì)圖數(shù)據(jù)的使用,在構(gòu)建圖數(shù)據(jù)管理系統(tǒng)的基礎(chǔ)上,設(shè)計(jì)或者采用了一些描述性查詢管理語言.用戶可以將自身的需求表達(dá)成描述性語句,然后系統(tǒng)將這些任務(wù)語句解析成執(zhí)行計(jì)劃,最后由系統(tǒng)按照?qǐng)?zhí)行計(jì)劃進(jìn)行處理進(jìn)而得到計(jì)算結(jié)果.因?yàn)檫@類系統(tǒng)用描述性查詢語言作為用戶和系統(tǒng)的交互中介,所以這類系統(tǒng)具有較好的用戶友好性.

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

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

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

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

2.4 總結(jié)與展望

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

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

3.1 引 言

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

3.2 主要研究問題

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

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

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

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

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

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

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

數(shù)據(jù)流管理系統(tǒng)(DSMS)是指管理持續(xù)性數(shù)據(jù)流的計(jì)算機(jī)軟件.不同于傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)(DBMS),數(shù)據(jù)流管理系統(tǒng)支持持續(xù)性查詢,每個(gè)查詢從注冊(cè)開始有效直至撤銷結(jié)束,不僅僅執(zhí)行一次.在有效期間內(nèi),隨著數(shù)據(jù)流的不斷更新,持續(xù)性查詢的結(jié)果也會(huì)更新.傳統(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]等.流查詢語言也會(huì)支持窗口表達(dá).在圖示化的查詢語言中,每個(gè)細(xì)分的查詢由一個(gè)“查詢盒”表達(dá),各個(gè)細(xì)分查詢的關(guān)聯(lián)與組合通過“查詢盒”[68]間的箭頭連線表達(dá).這個(gè)結(jié)構(gòu)可以理解為流計(jì)算框架(諸如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ù)流計(jì)算時(shí)的內(nèi)存管理以及近似查詢.Aurora是一個(gè)以工作流為導(dǎo)向的數(shù)據(jù)流管理系統(tǒng),用戶可以通過“查詢盒”來定義查詢計(jì)劃,每個(gè)“查詢盒”含有基礎(chǔ)的操作命令,“查詢盒”之間的數(shù)據(jù)流指向決定了各個(gè)步驟結(jié)果的傳輸框架.TelegraphCQ是一個(gè)由伯克利大學(xué)開發(fā)的自適應(yīng)數(shù)據(jù)流管理系統(tǒng),用于支持不同場(chǎng)景的數(shù)據(jù)流應(yīng)用.NiagaraCQ是針對(duì)動(dòng)態(tài) Web內(nèi)容進(jìn)行持續(xù)性 XML-QL查詢的數(shù)據(jù)流管理引擎(XML-QL是 XML查詢語言的一種擴(kuò)展,用來支持大 XML文檔上的數(shù)據(jù)抽取,能夠跨多個(gè)不同的DTD解釋XML數(shù)據(jù)以及集成多個(gè)不同源的XML數(shù)據(jù)).它對(duì)XML數(shù)據(jù)的抽取、查詢與監(jiān)控分別由3個(gè)主要組件來支撐:搜索引擎、查詢引擎以及觸發(fā)管理.Gigascope是面向網(wǎng)絡(luò)數(shù)據(jù)流監(jiān)控的分布式數(shù)據(jù)流管理系統(tǒng),可以用來支撐網(wǎng)絡(luò)流量分析、入侵檢測(cè)、路由配置分析等,也能夠進(jìn)行網(wǎng)絡(luò)搜索、性能監(jiān)控等.

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

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

3.3.2 流計(jì)算框架

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

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

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

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

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

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

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

Kafka Stream是Apache Kafka[80,88]中的一個(gè)輕量級(jí)流式處理類庫,用來支撐Kafka中存儲(chǔ)數(shù)據(jù)的流式計(jì)算與分析.利用這個(gè)類庫計(jì)算的結(jié)果既可以寫回 Kafka,也可以作為數(shù)據(jù)源向外輸出.目前的流式計(jì)算系統(tǒng)基本都支持以Kafka Stream的輸出作為數(shù)據(jù)源,如Storm的Kafka Spout.Kafka Stream作為一個(gè)Java類庫而非系統(tǒng),是流計(jì)算的重要工具之一.它可以非常方便地嵌入任意Java應(yīng)用中,也可以任意方式打包和部署,除了Kafka之外,并沒有任何外部依賴.與流計(jì)算系統(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)最主要的相似性是針對(duì)數(shù)據(jù)獨(dú)立性設(shè)計(jì)分布式并行計(jì)算策略,即:針對(duì)流式的輸入,利用集群進(jìn)行協(xié)作計(jì)算,而整體的數(shù)據(jù)依賴框架一般是一個(gè)有向無環(huán)圖.集群的整體協(xié)作更像是流水線的協(xié)作,計(jì)算框架中的數(shù)據(jù)依賴所形成的數(shù)據(jù)流動(dòng)方向基本上是單一既定的.除了數(shù)據(jù)處理的先后關(guān)系外,這些流系統(tǒng)對(duì)不同工作組之間的數(shù)據(jù)獨(dú)立性往往要求更高,可實(shí)現(xiàn)較好的并行效果.

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

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

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í)意義有限),對(duì)應(yīng)的研究問題除了傳統(tǒng)的圖計(jì)算問題之外,還有針對(duì)時(shí)間先后信息定義的研究問題,如滿足時(shí)序約束的路徑、子圖查詢等[91].常見的時(shí)序約束有時(shí)間先后、時(shí)間間隔.例如,阿里巴巴通過網(wǎng)購交易數(shù)據(jù)中的環(huán)形子圖的實(shí)時(shí)監(jiān)控來追蹤通過網(wǎng)購進(jìn)行惡意信用卡套現(xiàn)的行為[92].如圖1所示:一個(gè)信用卡惡意的套現(xiàn)模式中,套現(xiàn)者向商戶發(fā)起信用卡虛假購買,銀行將真實(shí)的資金支付給商戶之后,商戶通過中間人將資金回流到套現(xiàn)者儲(chǔ)蓄卡中,實(shí)現(xiàn)惡意套現(xiàn).整個(gè)流程中,參與的對(duì)象和資金的流向構(gòu)成了圖的結(jié)構(gòu),而每個(gè)行為環(huán)節(jié)有其明確的時(shí)間先后關(guān)系.因此,針對(duì)圖數(shù)據(jù)流的管理能夠解決很多現(xiàn)實(shí)中的重要問題.

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

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

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

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

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

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

3.5 總結(jié)與展望

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

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

4.1 引 言

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

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

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

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

4.2 主要研究問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在過去的20年里,時(shí)態(tài)數(shù)據(jù)管理一直是數(shù)據(jù)庫的活躍領(lǐng)域之一,研究內(nèi)容包括數(shù)據(jù)模型、查詢語言、索引結(jié)構(gòu)及高效查詢算法,各種查詢語言也被提出以支持時(shí)態(tài)數(shù)據(jù)查詢的形式化描述.Enderle等人基于常見的時(shí)態(tài)數(shù)據(jù)索引之一——Interval-tree設(shè)計(jì)了相應(yīng)的外存結(jié)構(gòu)以及在關(guān)系數(shù)據(jù)庫系統(tǒng)中的實(shí)現(xiàn)方法,可以有效支持相交查詢和連接查詢[96];Top-k查詢用于返回與查詢點(diǎn)(區(qū)間)相交且權(quán)重最大的k個(gè)對(duì)象.Dign?s等人將時(shí)態(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ù).

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

4.3.3 移動(dòng)對(duì)象數(shù)據(jù)庫

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

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

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

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

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

并行處理技術(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],其對(duì) SparkSQL進(jìn)行了擴(kuò)展,能夠有效地支持并發(fā)查詢.在時(shí)態(tài)數(shù)據(jù)庫方面,有基于PostgreSQL的時(shí)態(tài)數(shù)據(jù)查詢?cè)拖到y(tǒng)和在線實(shí)時(shí)時(shí)態(tài)數(shù)據(jù)分析系統(tǒng) OceanRT.在移動(dòng)對(duì)象數(shù)據(jù)庫方面,有針對(duì)軌跡數(shù)據(jù)處理的引擎 Hermes、支持多種軌跡數(shù)據(jù)挖掘操作及可視化系統(tǒng) MoveMine、基于內(nèi)存的分布式系統(tǒng) SharkDB、DITA[107]、軌跡數(shù)據(jù)在線分析系統(tǒng)T-Warehouse、大規(guī)模軌跡數(shù)據(jù)管理和分析平臺(tái)UlTraMan[108].SECONDO是一個(gè)開源可擴(kuò)充性數(shù)據(jù)庫管理系統(tǒng),可對(duì)空間、時(shí)態(tài)和移動(dòng)對(duì)象數(shù)據(jù)有效管理且支持并行處理[109].

4.4 總結(jié)與展望

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

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

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

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

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

5.1 引 言

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

5.2 主要研究問題

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

· 第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)對(duì)這些結(jié)果進(jìn)行集成和處理后,將最終結(jié)果反饋給眾包任務(wù)發(fā)布者;

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

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

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

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

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

除上述研究問題外,眾包數(shù)據(jù)管理還研究眾包任務(wù)的設(shè)計(jì)、對(duì)眾包參與者隱私的保護(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è)計(jì)和開發(fā)了各類眾包數(shù)據(jù)管理系統(tǒng).

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

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

1) 任務(wù)分配

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

2) 質(zhì)量控制

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

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

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

(3) 激勵(lì)機(jī)制

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

綜上所述,3類眾包數(shù)據(jù)管理機(jī)制的研究都針對(duì)于現(xiàn)存的在線眾包平臺(tái),如 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é)主要對(duì)現(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類情況,并對(duì)每種情況給出了確定性與概率性求解算法.其后續(xù)擴(kuò)展工作進(jìn)一步放松了文獻(xiàn)[139]的眾多假設(shè)條件,從而進(jìn)一步提高了通用性[140].通過增加眾包參與者們的先驗(yàn)信息與后驗(yàn)信息,以及對(duì)不同用戶能力的細(xì)化分析,大幅度提高了算法執(zhí)行效率,同時(shí)也降低了眾包支付成本.

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

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

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

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

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

枚舉查詢也是傳統(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ū)間以估計(jì)值快速計(jì)算枚舉結(jié)果的可信度,同時(shí),在滿足置信度約束的情況下最小化眾包支付成本.

(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)?”的問題來估計(jì)不同項(xiàng)集的支持度,從而估計(jì)出關(guān)聯(lián)規(guī)則的置信度.文獻(xiàn)[152]提出了一個(gè)貝葉斯模型來學(xué)習(xí)不同眾包參與者的聚類特點(diǎn)與數(shù)據(jù)項(xiàng)自身的結(jié)構(gòu)性特點(diǎn),從而獲取基于眾包的高質(zhì)量聚類結(jié)果.

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

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

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

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

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

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

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

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

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

5.4 總結(jié)與展望

現(xiàn)存的研究已將眾包策略成功地集成到傳統(tǒng)數(shù)據(jù)處理技術(shù)之中.眾包策略可以提高傳統(tǒng)數(shù)據(jù)處理技術(shù)的準(zhǔn)確性,同時(shí)可打破傳統(tǒng)數(shù)據(jù)處理的“封閉世界假設(shè)”,從而擴(kuò)展傳統(tǒng)數(shù)據(jù)處理技術(shù)的適用范圍.此外,近年來,隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)的廣泛應(yīng)用,時(shí)空眾包數(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)確的估計(jì),且優(yōu)化目標(biāo)較為單一;在眾包數(shù)據(jù)庫中,由于所涉及的眾包群體存在較大不確定性,且優(yōu)化目標(biāo)涉及時(shí)延、質(zhì)量、花費(fèi)等諸多復(fù)雜因素,眾包數(shù)據(jù)管理系統(tǒng)的查詢優(yōu)化問題還未得到有效解決;

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

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

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

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

6.1 新硬件

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

· 基于高性能和專用處理器的數(shù)據(jù)管理方法:目前,高性能處理器技術(shù)進(jìn)入多核時(shí)代.相對(duì)應(yīng)地,數(shù)據(jù)庫底層核心算法需要充分考慮多核并行的能力,重新設(shè)計(jì)連接、排序等基本操作[160].圖形處理器GPU[161]、現(xiàn)場(chǎng)可編程門陣列 FPGA[162]等專用處理器具備更大規(guī)模的數(shù)據(jù)并行操作能力,從而提升數(shù)據(jù)的向量處理效率,支持?jǐn)?shù)據(jù)庫內(nèi)核范圍內(nèi)的機(jī)器學(xué)習(xí)等任務(wù).同時(shí),不同特性異構(gòu)硬件的協(xié)同操作也成為研究問題.例如,GPU的顯存相比于內(nèi)存容量要小,數(shù)據(jù)加載到 GPU顯存的操作代價(jià)較高,面向數(shù)據(jù)管理的CPU和GPU的協(xié)同架構(gòu)就是希望充分發(fā)揮不同硬件的優(yōu)勢(shì)[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ò)傳輸作為主要代價(jià)之一.隨著RDMA等高速網(wǎng)絡(luò)技術(shù)的發(fā)展,網(wǎng)絡(luò)傳輸代價(jià)大幅度降低.現(xiàn)有的研究工作基于RDMA高速網(wǎng)絡(luò)的特性,設(shè)計(jì)了新的分布式連接方法[164]和分布式并發(fā)控制策略[165]等;

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

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

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

傳統(tǒng)數(shù)據(jù)庫查詢執(zhí)行的主要瓶頸在于 I/O操作,而在內(nèi)存數(shù)據(jù)庫中,內(nèi)外存數(shù)據(jù)交換不再成為代價(jià)的主要來源.內(nèi)存數(shù)據(jù)庫需要考慮現(xiàn)有CPU特性對(duì)內(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)行劃分,同一個(gè)劃分中數(shù)據(jù)操作串行,減少并發(fā)控制帶來的各種代價(jià);也可以采用所有處理器核都可以訪問全部數(shù)據(jù)的方式.從數(shù)據(jù)版本的角度,內(nèi)存數(shù)據(jù)庫通常采用多版本機(jī)制,提升查詢處理效率.從行列存儲(chǔ)的角度,內(nèi)存數(shù)據(jù)庫可以選擇行存儲(chǔ)或者列存儲(chǔ),同時(shí),其列存儲(chǔ)在交易型應(yīng)用中表現(xiàn)良好[169];

· 數(shù)據(jù)索引.內(nèi)存數(shù)據(jù)庫索引設(shè)計(jì)主要考慮兩個(gè)主要因素:首先,內(nèi)存索引節(jié)點(diǎn)的大小一般與CPU緩存大小相關(guān),其索引數(shù)據(jù)的存儲(chǔ)滿足一定的連續(xù)性,從而在索引操作過程中提升CPU緩存的命中率,典型工作如 CSB+樹[170]等;其次,內(nèi)存索引結(jié)構(gòu)的設(shè)計(jì)需要考慮多核環(huán)境中的并發(fā)查詢和更新,盡量減少內(nèi)存數(shù)據(jù)結(jié)構(gòu)中并發(fā)鎖的使用,降低索引維護(hù)代價(jià),典型工作如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è)計(jì)劃分串行執(zhí)行協(xié)議[173],即:同一劃分內(nèi)數(shù)據(jù)串行操作,劃分之間數(shù)據(jù)并行操作.目標(biāo)是減少多核對(duì)同一數(shù)據(jù)并發(fā)控制代價(jià)或者沖突導(dǎo)致的回滾代價(jià).

6.3 近似查詢

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

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

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

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

數(shù)據(jù)可視化利用計(jì)算機(jī)圖形學(xué)、數(shù)據(jù)分析、用戶交互界面等技術(shù),通過數(shù)據(jù)建模等手段,為用戶提供有效的數(shù)據(jù)呈現(xiàn)方式.數(shù)據(jù)可視化能夠幫助用戶迅速理解數(shù)據(jù)、定位問題.近期發(fā)展的可視化技術(shù)可以從不同維度來刻畫,如可視化后臺(tái)的數(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)建不同層次的圖,同時(shí)引入交互策略,支持用戶對(duì)其感興趣的部分作進(jìn)一步的動(dòng)態(tài)分析;

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

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

7 總 結(jié)

數(shù)據(jù)相關(guān)技術(shù)的發(fā)展給整個(gè)社會(huì)帶來了巨大的變革,也給相關(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ù).針對(duì)應(yīng)用中出現(xiàn)的不同類型數(shù)據(jù)管理需求,現(xiàn)有的系統(tǒng)大多是通過構(gòu)建專用系統(tǒng)來解決,例如圖數(shù)據(jù)管理系統(tǒng)、時(shí)空數(shù)據(jù)管理系統(tǒng)等.而應(yīng)用中,這些數(shù)據(jù)混雜在一起,按照數(shù)據(jù)類型劃分到不同數(shù)據(jù)系統(tǒng)中,這種管理方式不高效,也不自然.新型數(shù)據(jù)管理系統(tǒng)需要提供通用的底層數(shù)據(jù)模型,統(tǒng)一支持不同類型數(shù)據(jù)的存儲(chǔ)、查詢、分析、優(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)的計(jì)算資源.異構(gòu)計(jì)算環(huán)境廣泛存在于真實(shí)應(yīng)用場(chǎng)景中,包括資源共享與競(jìng)爭、網(wǎng)絡(luò)和計(jì)算能力差異以及新型硬件帶來的異構(gòu)性.異構(gòu)計(jì)算環(huán)境會(huì)對(duì)新型數(shù)據(jù)管理系統(tǒng)的效率帶來極大的影響,同時(shí),新型硬件的發(fā)展也為新型數(shù)據(jù)管理系統(tǒng)提供了新的機(jī)遇;

· 新型數(shù)據(jù)管理系統(tǒng)需要在計(jì)算模型方面實(shí)現(xiàn)擴(kuò)展,滿足不同數(shù)據(jù)模型的管理需求,支持系統(tǒng)松耦合管理體系.機(jī)器學(xué)習(xí)是目前的技術(shù)熱點(diǎn),在自然語言處理、計(jì)算機(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)的效率和可用性.