鄭緯民

清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 北京 100084

從系統(tǒng)角度審視大數(shù)據(jù)計(jì)算

鄭緯民

清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 北京 100084

大數(shù)據(jù)計(jì)算是實(shí)現(xiàn)大數(shù)據(jù)“巨大價(jià)值”的必要手段，而計(jì)算系統(tǒng)是大數(shù)據(jù)計(jì)算的有效載體。試著從系統(tǒng)角度審視大數(shù)據(jù)計(jì)算，透過大數(shù)據(jù)的體量巨大、速度極快、模態(tài)多樣、真?zhèn)坞y辨等宏觀特征，針對(duì)批量計(jì)算、流式計(jì)算、大圖計(jì)算等計(jì)算形式，分別探討大數(shù)據(jù)計(jì)算的典型特征，論述了這些特征給大數(shù)據(jù)計(jì)算系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)帶來的技術(shù)挑戰(zhàn)，進(jìn)而梳理了為了應(yīng)對(duì)這些挑戰(zhàn)所取得的研究成果，最后從系統(tǒng)角度指出未來大數(shù)據(jù)計(jì)算可能的一些研究方向。

大數(shù)據(jù)計(jì)算；批量計(jì)算；流式計(jì)算；大圖計(jì)算；系統(tǒng)實(shí)例

1 引言

大數(shù)據(jù)已成為當(dāng)前社會(huì)各界關(guān)注的焦點(diǎn)[1～4]。從一般意義上講，大數(shù)據(jù)是指在可容忍的時(shí)間內(nèi)，無法用現(xiàn)有信息技術(shù)和軟硬件工具對(duì)其進(jìn)行感知、獲取、管理、處理和服務(wù)的數(shù)據(jù)集合。大數(shù)據(jù)呈現(xiàn)出多種鮮明特征[3～8]，在數(shù)據(jù)量方面，體量巨大，當(dāng)前全球所擁有的數(shù)據(jù)總量已經(jīng)遠(yuǎn)遠(yuǎn)超過歷史上的任何時(shí)期，更為重要的是，數(shù)據(jù)量的增加速度呈現(xiàn)出倍增趨勢(shì)；在數(shù)據(jù)速率方面，速度極快，數(shù)據(jù)產(chǎn)生、傳播的速度更快，在不同時(shí)空中流轉(zhuǎn)，呈現(xiàn)出鮮明的流式特征，更為重要的是，數(shù)據(jù)價(jià)值的有效時(shí)間急劇減少，也要求越來越高的數(shù)據(jù)計(jì)算和使用能力；在數(shù)據(jù)復(fù)雜性方面，模態(tài)多樣，種類繁多，在編碼方式、存儲(chǔ)格式、應(yīng)用特征等多個(gè)方面也存在多層次、多方面的差異性，結(jié)構(gòu)化、半結(jié)構(gòu)化、非結(jié)構(gòu)化數(shù)據(jù)并存；在數(shù)據(jù)價(jià)值方面，價(jià)值稀疏，真?zhèn)坞y辨，但價(jià)值總量巨大，隨著數(shù)據(jù)規(guī)模的不斷增大，隱含于大數(shù)據(jù)中的知識(shí)也隨之增多，但這些知識(shí)隱含程度很深，對(duì)發(fā)現(xiàn)這些知識(shí)的方式、方法提出了更高的要求。此外，大數(shù)據(jù)還呈現(xiàn)出個(gè)性化、不完備化、交叉復(fù)用等諸多鮮明特征。

大數(shù)據(jù)蘊(yùn)含大信息，大信息提煉大知識(shí)，大知識(shí)將在更高的層面、更廣的視角、更大的范圍幫助用戶提高洞察力、提升決策力，將為人類社會(huì)創(chuàng)造前所未有的大價(jià)值。但與此同時(shí)，這些總量極大的價(jià)值往往隱藏在大數(shù)據(jù)中，表現(xiàn)出價(jià)值密度極低、分布極其不規(guī)律、信息隱藏程度極深、真?zhèn)涡畔⒔豢椈旌习l(fā)現(xiàn)有用價(jià)值極其困難的鮮明特性，這些特征必然為大數(shù)據(jù)的計(jì)算帶來前所未有的挑戰(zhàn)和機(jī)遇。

大數(shù)據(jù)計(jì)算是發(fā)現(xiàn)信息、挖掘知識(shí)、滿足應(yīng)用的必要途徑，也是大數(shù)據(jù)從收集、傳輸、存儲(chǔ)、計(jì)算到應(yīng)用等整個(gè)生命周期中最關(guān)鍵、最核心的環(huán)節(jié)，只有有效的大數(shù)據(jù)計(jì)算，才能滿足大數(shù)據(jù)的上層應(yīng)用需要，才能挖掘出大數(shù)據(jù)的內(nèi)在價(jià)值，才能使大數(shù)據(jù)具有意義。大數(shù)據(jù)計(jì)算系統(tǒng)是實(shí)現(xiàn)大數(shù)據(jù)科學(xué)計(jì)算的基礎(chǔ)平臺(tái)。對(duì)于規(guī)模巨大、價(jià)值稀疏、結(jié)構(gòu)復(fù)雜、時(shí)效性強(qiáng)的大數(shù)據(jù)，其計(jì)算亦面臨不同于傳統(tǒng)數(shù)據(jù)計(jì)算的諸多新挑戰(zhàn)，如計(jì)算復(fù)雜度高、任務(wù)周期長(zhǎng)、數(shù)據(jù)實(shí)時(shí)性強(qiáng)、計(jì)算通用性差等。大數(shù)據(jù)及其計(jì)算的這些挑戰(zhàn)對(duì)大數(shù)據(jù)計(jì)算系統(tǒng)的系統(tǒng)架構(gòu)、計(jì)算框架、處理方法等提出了新的挑戰(zhàn)。同時(shí)，大數(shù)據(jù)時(shí)代出現(xiàn)了很多新的應(yīng)用需求，如面向社交媒體的大圖關(guān)系分析與發(fā)現(xiàn)，需要結(jié)合具體的應(yīng)用場(chǎng)景，開展針對(duì)性的關(guān)于計(jì)算模式的研究。

為了滿足和適應(yīng)大數(shù)據(jù)計(jì)算的需要，隨著大數(shù)據(jù)及相關(guān)技術(shù)的全面和深入發(fā)展，大數(shù)據(jù)計(jì)算模式也呈現(xiàn)出多樣化、專業(yè)化特征，以滿足不同領(lǐng)域大數(shù)據(jù)應(yīng)用范式的要求。本文首先針對(duì)大數(shù)據(jù)計(jì)算的3種代表性模式進(jìn)行了深入的分析，主要包括大數(shù)據(jù)批量計(jì)算、流式計(jì)算和交互計(jì)算，對(duì)其中各計(jì)算模式的基本概念、典型特征和技術(shù)挑戰(zhàn)進(jìn)行了系統(tǒng)的歸納和分類。其次，分別針對(duì)這3種計(jì)算模式中當(dāng)前具有廣泛代表性的系統(tǒng)進(jìn)行了具體實(shí)例分析。再次，從系統(tǒng)的角度，對(duì)3種計(jì)算模式的未來研究方向和重點(diǎn)進(jìn)行了初步分析。最后，對(duì)全文進(jìn)行了總結(jié)。

2 大數(shù)據(jù)計(jì)算模式

大數(shù)據(jù)計(jì)算模式主要包括批量計(jì)算、流式計(jì)算、交互計(jì)算3種。其中，交互計(jì)算需要在計(jì)算過程中與用戶進(jìn)行互動(dòng)，才能進(jìn)行后續(xù)的計(jì)算動(dòng)作，可以把交互計(jì)算看作批量計(jì)算的一種特殊形式。本文不再對(duì)交互計(jì)算進(jìn)行深入分析。大圖計(jì)算本屬于批量計(jì)算范疇，但隨著互聯(lián)網(wǎng)應(yīng)用的發(fā)展，其重要性日益凸顯，并且因其各個(gè)節(jié)點(diǎn)的關(guān)聯(lián)緊密性而具有不同于其他普通批量計(jì)算的顯著特征。本文對(duì)大圖計(jì)算進(jìn)行單獨(dú)討論。

2.1 批量計(jì)算的特征及挑戰(zhàn)

大數(shù)據(jù)批量計(jì)算[9～13]（big data batch computing）是大數(shù)據(jù)計(jì)算的一種主要計(jì)算模式，當(dāng)前階段，大多數(shù)應(yīng)用場(chǎng)景均通過批量計(jì)算模式實(shí)現(xiàn)。同時(shí)，批量計(jì)算也可以同其他計(jì)算模式進(jìn)一步結(jié)合起來，以完成對(duì)數(shù)據(jù)的進(jìn)一步處理。在大數(shù)據(jù)批量計(jì)算環(huán)境中，其計(jì)算架構(gòu)如圖1所示。數(shù)據(jù)通過多個(gè)數(shù)據(jù)源進(jìn)行收集，按照與應(yīng)用場(chǎng)景所需要的方式進(jìn)行組織，在各種外存存儲(chǔ)介質(zhì)（如硬盤、磁帶等）上靜態(tài)地存儲(chǔ)起來。當(dāng)需要進(jìn)行數(shù)據(jù)計(jì)算時(shí)，開啟數(shù)據(jù)的計(jì)算過程，進(jìn)行數(shù)據(jù)的集中處理，數(shù)據(jù)被處理完后，計(jì)算過程也隨之結(jié)束。在數(shù)據(jù)的計(jì)算過程中，數(shù)據(jù)的計(jì)算順序、計(jì)算速度等各種因素可以有效控制，也可以有選擇地、重復(fù)地進(jìn)行部分?jǐn)?shù)據(jù)的重計(jì)算。數(shù)據(jù)的計(jì)算結(jié)果是確定、準(zhǔn)確、全面、可重現(xiàn)的，但數(shù)據(jù)的計(jì)算時(shí)延往往較長(zhǎng)，往往在數(shù)分鐘到數(shù)小時(shí)之間。可見，對(duì)于先存儲(chǔ)后計(jì)算的實(shí)時(shí)性要求不高，同時(shí)，對(duì)于數(shù)據(jù)的準(zhǔn)確性、全面性更為重要的應(yīng)用場(chǎng)景，批量計(jì)算模式更加適合。

圖1 大數(shù)據(jù)批量計(jì)算架構(gòu)

大數(shù)據(jù)批量計(jì)算場(chǎng)景通常呈現(xiàn)出以下典型特征及挑戰(zhàn)。

（1）數(shù)據(jù)體量巨大

數(shù)據(jù)量從TB級(jí)別躍升到PB級(jí)別，甚至更高。數(shù)據(jù)往往以靜態(tài)的形式在硬盤等外部存儲(chǔ)介質(zhì)上永久存儲(chǔ)，一次寫入，很少再進(jìn)行更新，存儲(chǔ)時(shí)間長(zhǎng)，可以重復(fù)多次利用，但很難對(duì)其進(jìn)行移動(dòng)和備份。面向如此體量的數(shù)據(jù)，需要在數(shù)據(jù)的組織方式、計(jì)算形式等方面根據(jù)具體的應(yīng)用場(chǎng)景，構(gòu)建一個(gè)高效、分布式的大數(shù)據(jù)計(jì)算系統(tǒng)，以滿足對(duì)相關(guān)數(shù)據(jù)的并行、分布式處理要求。

（2）數(shù)據(jù)精確度高

批量數(shù)據(jù)通常是從應(yīng)用中沉淀下來的，對(duì)于了解上次應(yīng)用的各種內(nèi)在關(guān)系、潛在邏輯以及預(yù)測(cè)未來發(fā)展都很關(guān)鍵。需要對(duì)其中所有數(shù)據(jù)進(jìn)行全量式的計(jì)算，數(shù)據(jù)處理結(jié)果的精度要求較高。為了滿足如此高的數(shù)據(jù)精度，需要在數(shù)據(jù)處理效率和數(shù)據(jù)處理結(jié)果精度等方面進(jìn)行權(quán)衡，在數(shù)據(jù)的單次處理和再現(xiàn)方面進(jìn)行權(quán)衡。

（3）數(shù)據(jù)價(jià)值稀疏

在數(shù)據(jù)的收集過程中，往往需要盡可能全面、密集地進(jìn)行數(shù)據(jù)收集，避免任何有價(jià)值數(shù)據(jù)的遺失。隨著數(shù)據(jù)收集工具和方法的不斷進(jìn)步，數(shù)據(jù)收集面和收集頻率的不斷增廣和增加，數(shù)據(jù)價(jià)值的稀疏程度也急劇增強(qiáng)。因此，需要通過合理的計(jì)算架構(gòu)和高效的數(shù)據(jù)處理算法才能從大量的數(shù)據(jù)中抽取少數(shù)有用的價(jià)值。此外，批量數(shù)據(jù)處理往往比較耗時(shí)，而且不提供用戶與系統(tǒng)的交互手段，當(dāng)發(fā)現(xiàn)處理結(jié)果和預(yù)期結(jié)果有很大差別時(shí)，會(huì)浪費(fèi)很多時(shí)間。因此，批量數(shù)據(jù)處理適合大型的相對(duì)比較成熟的應(yīng)用場(chǎng)景。數(shù)據(jù)價(jià)值稀疏性特征使得在大數(shù)據(jù)計(jì)算系統(tǒng)中，需要構(gòu)建一個(gè)高效、精準(zhǔn)、面向特定應(yīng)用和領(lǐng)域的數(shù)據(jù)處理模式，在極其稀疏甚至稀疏程度不斷增加的應(yīng)用場(chǎng)景下，能快速發(fā)現(xiàn)并挖掘出其中所存在的數(shù)據(jù)價(jià)值。

2.2 流式計(jì)算的特征及挑戰(zhàn)

大數(shù)據(jù)流式計(jì)算[14～18]（big data stream computing）是大數(shù)據(jù)計(jì)算的另一種重要計(jì)算模式，特別是在數(shù)據(jù)時(shí)效性、實(shí)時(shí)性需要不斷增加的應(yīng)用場(chǎng)景不斷增多的情況下，其重要性日益凸顯。在大數(shù)據(jù)流式計(jì)算環(huán)境中，其計(jì)算架構(gòu)如圖2所示。數(shù)據(jù)以數(shù)據(jù)流的形式，通過多個(gè)不同的數(shù)據(jù)源實(shí)時(shí)到達(dá)大數(shù)據(jù)流式計(jì)算平臺(tái)，然后，利用數(shù)據(jù)流圖所描述的處理過程被在線處理，并實(shí)時(shí)產(chǎn)生結(jié)果，滿足相關(guān)上層應(yīng)用系統(tǒng)的需要。整個(gè)數(shù)據(jù)的處理過程往往在毫秒級(jí)的時(shí)間范圍內(nèi)完成，原始數(shù)據(jù)、中間狀態(tài)、處理結(jié)果等數(shù)據(jù)根據(jù)具體應(yīng)用場(chǎng)景的需要，不全部保存，只是選擇性地存儲(chǔ)。描述用戶特定應(yīng)用的數(shù)據(jù)流圖一旦提交到系統(tǒng)中，將會(huì)永遠(yuǎn)在線運(yùn)行，實(shí)時(shí)對(duì)輸入的數(shù)據(jù)流進(jìn)行處理，除非整個(gè)處理平臺(tái)意外中斷或顯示終止。由于整個(gè)數(shù)據(jù)流的處理時(shí)間極短，判讀的依據(jù)也往往集中在當(dāng)前時(shí)間點(diǎn)附近（時(shí)間窗口）的數(shù)據(jù)，加上數(shù)據(jù)流中各數(shù)據(jù)項(xiàng)的不斷變化，留給大數(shù)據(jù)流式計(jì)算平臺(tái)進(jìn)行調(diào)整和應(yīng)對(duì)的時(shí)間也很少，因此，流式數(shù)據(jù)處理的結(jié)果往往不夠精確、不夠全面，只能給出一個(gè)實(shí)時(shí)性很強(qiáng)的、相對(duì)準(zhǔn)確的、基于當(dāng)前局部數(shù)據(jù)判斷的結(jié)果?？梢?，對(duì)于無需先存儲(chǔ)、可以直接進(jìn)行數(shù)據(jù)計(jì)算、實(shí)時(shí)性要求很嚴(yán)格但數(shù)據(jù)的精確度往往不太重要的應(yīng)用場(chǎng)景，流式計(jì)算具有明顯優(yōu)勢(shì)。

圖2 大數(shù)據(jù)流式計(jì)算架構(gòu)

大數(shù)據(jù)流式計(jì)算場(chǎng)景通常呈現(xiàn)出以下典型特征及挑戰(zhàn)。

大數(shù)據(jù)流呈現(xiàn)出鮮明的實(shí)時(shí)性、易失性、突發(fā)性、無序性、無限性等特征。流式大數(shù)據(jù)是實(shí)時(shí)產(chǎn)生、實(shí)時(shí)計(jì)算，結(jié)果反饋往往也需要保證及時(shí)性。數(shù)據(jù)的使用往往是一次性的、易失的，即使重放，得到的數(shù)據(jù)流和之前的數(shù)據(jù)流也不同。數(shù)據(jù)的產(chǎn)生完全由數(shù)據(jù)源確定，由于不同的數(shù)據(jù)源，在不同時(shí)空范圍內(nèi)的狀態(tài)不統(tǒng)一且動(dòng)態(tài)變化，導(dǎo)致數(shù)據(jù)流的速率呈現(xiàn)出突發(fā)性的特征。各數(shù)據(jù)流之間、同一數(shù)據(jù)流內(nèi)部各數(shù)據(jù)元素之間是無序的。數(shù)據(jù)是實(shí)時(shí)產(chǎn)生、動(dòng)態(tài)增加的，只要數(shù)據(jù)源處于活動(dòng)狀態(tài)，數(shù)據(jù)就會(huì)一直產(chǎn)生和持續(xù)增加，可以說，潛在的數(shù)據(jù)量是無限的。

大數(shù)據(jù)流式環(huán)境中的數(shù)據(jù)計(jì)算在系統(tǒng)的可伸縮性、系統(tǒng)容錯(cuò)、狀態(tài)一致性等方面均面臨著前所未有的新的挑戰(zhàn)。在系統(tǒng)的可伸縮性上，一方面，需要大數(shù)據(jù)流式系統(tǒng)具有很好的“可伸”特征，可以實(shí)時(shí)適應(yīng)數(shù)據(jù)增長(zhǎng)的需求，實(shí)現(xiàn)對(duì)系統(tǒng)資源的動(dòng)態(tài)調(diào)整和快速部署；另一方面，當(dāng)流式數(shù)據(jù)的產(chǎn)生速率持續(xù)減少時(shí)，需要及時(shí)回收在高峰時(shí)期所分配的目前已處于閑置或低效利用的資源，實(shí)現(xiàn)整個(gè)系統(tǒng)“可縮”的友好特征。在系統(tǒng)容錯(cuò)上，一方面，數(shù)據(jù)流實(shí)時(shí)、持續(xù)地到來，呈現(xiàn)出同時(shí)間相識(shí)的一維特征，一旦數(shù)據(jù)流流過，再次重放數(shù)據(jù)流的成本很大，甚至是不現(xiàn)實(shí)的；另一方面，在流式大數(shù)據(jù)的計(jì)算過程中，大部分“無用”的數(shù)據(jù)將被直接丟棄，所被永久保存下來的數(shù)據(jù)量是極少的，當(dāng)需要進(jìn)行系統(tǒng)容錯(cuò)時(shí)，其中不可避免地會(huì)出現(xiàn)一個(gè)時(shí)間段內(nèi)數(shù)據(jù)的不完整；再則，需要針對(duì)不同類型的應(yīng)用，從系統(tǒng)層面上設(shè)計(jì)符合其應(yīng)用特征的數(shù)據(jù)容錯(cuò)級(jí)別和容錯(cuò)策略。在各節(jié)點(diǎn)間狀態(tài)的一致性上，一方面，如何從高速、海量的數(shù)據(jù)流中識(shí)別并維護(hù)一致性狀態(tài)的數(shù)據(jù)是一個(gè)巨大的挑戰(zhàn)；另一方面，在大規(guī)模分布式環(huán)境中，如何組織和管理實(shí)現(xiàn)系統(tǒng)狀態(tài)一致性的相關(guān)數(shù)據(jù)，滿足系統(tǒng)對(duì)數(shù)據(jù)的高效組織和精準(zhǔn)管理的要求也是一個(gè)巨大的挑戰(zhàn)。

2.3 大圖計(jì)算的特征及挑戰(zhàn)

大數(shù)據(jù)圖計(jì)算[19～21]（big data graph computing）是大數(shù)據(jù)計(jì)算的一種計(jì)算模式，隨著社交媒體、移動(dòng)互聯(lián)網(wǎng)的不斷發(fā)展，在大數(shù)據(jù)計(jì)算中的重要性日益凸顯。大數(shù)據(jù)圖計(jì)算主要用來分析數(shù)據(jù)節(jié)點(diǎn)之間的關(guān)系和相似度，該計(jì)算范式已經(jīng)廣泛應(yīng)用于用戶分析、欺詐檢測(cè)、社交媒體、移動(dòng)互聯(lián)網(wǎng)、生命科學(xué)等諸多領(lǐng)域，其巨大的商業(yè)價(jià)值已經(jīng)凸顯。

大數(shù)據(jù)圖計(jì)算中的大圖數(shù)據(jù)往往以圖中的節(jié)點(diǎn)以及連接節(jié)點(diǎn)的邊呈現(xiàn)，其中節(jié)點(diǎn)數(shù)目往往是數(shù)以萬計(jì)的，邊的數(shù)量更大，通常具有如下3個(gè)特征。

（1）節(jié)點(diǎn)之間的關(guān)聯(lián)性

大圖中各節(jié)點(diǎn)之間的關(guān)系是通過邊來展現(xiàn)的。通常情況下，大圖中邊的數(shù)量是節(jié)點(diǎn)數(shù)量的指數(shù)倍。因此，節(jié)點(diǎn)和關(guān)系信息同等重要，圖結(jié)構(gòu)的差異也是由于對(duì)邊做了限制，在圖中，頂點(diǎn)和邊實(shí)例化構(gòu)成各種類型的圖，如標(biāo)簽圖、屬性圖、語(yǔ)義圖以及特征圖等。如何針對(duì)節(jié)點(diǎn)和邊的不同作用和特征，進(jìn)行節(jié)點(diǎn)和邊的存儲(chǔ)方式、組織模式以及計(jì)算途徑等挑戰(zhàn)的研究，結(jié)合具體應(yīng)用，提供一種高效的存儲(chǔ)方式、可擴(kuò)展的組織模式以及有效的計(jì)算途徑，滿足具體應(yīng)用場(chǎng)景的需要，是研究的關(guān)鍵點(diǎn)。

（2）圖計(jì)算的數(shù)據(jù)耦合性強(qiáng)

在大圖中，數(shù)據(jù)之間是相互關(guān)聯(lián)的，對(duì)圖數(shù)據(jù)的計(jì)算也是相互關(guān)聯(lián)的。這種數(shù)據(jù)耦合的特性對(duì)圖的規(guī)模日益增大達(dá)到上百萬甚至上億節(jié)點(diǎn)的大圖數(shù)據(jù)計(jì)算提出了巨大的挑戰(zhàn)。大圖數(shù)據(jù)是無法使用單臺(tái)機(jī)器進(jìn)行處理的，但如果對(duì)大圖數(shù)據(jù)進(jìn)行并行處理，對(duì)于每一個(gè)頂點(diǎn)之間都是連通的圖來講，難以分割成若干完全獨(dú)立的子圖進(jìn)行獨(dú)立的并行處理。即使可以分割，也會(huì)面臨并行機(jī)器的協(xié)同處理以及將最后的處理結(jié)果進(jìn)行合并等一系列問題。這需要圖數(shù)據(jù)處理系統(tǒng)選取合適的圖分割以及圖計(jì)算模型來迎接挑戰(zhàn)并解決問題。

在大數(shù)據(jù)時(shí)代，大圖的分割是大數(shù)據(jù)圖計(jì)算最為突出的問題。由于對(duì)整個(gè)圖的訪問是隨機(jī)進(jìn)行的，在圖劃分時(shí)需要考慮3個(gè)方面：通信代價(jià)，訪問跨機(jī)器的各邊通信量；負(fù)載均衡，讓每一臺(tái)機(jī)器的問題規(guī)?；窘咏淮鎯?chǔ)冗余，為了減少通信量，需要在機(jī)器上復(fù)制其他機(jī)器的存儲(chǔ)信息（存在數(shù)據(jù)一致性問題）。通過考慮存儲(chǔ)的冗余度，使綜合開銷達(dá)到最優(yōu)。

此外，大數(shù)據(jù)圖計(jì)算還存在以下問題：圖數(shù)據(jù)的局部性差，由于節(jié)點(diǎn)眾多，兩個(gè)相連接的點(diǎn)（連接的點(diǎn)對(duì)也是隨機(jī)的、無法預(yù)知的）可能存儲(chǔ)的位置相隔很遠(yuǎn)，即不在同一個(gè)存儲(chǔ)塊，這使得系統(tǒng)需要隨機(jī)訪問這些節(jié)點(diǎn)及邊，而訪問磁盤的效率又極低，從而嚴(yán)重影響了計(jì)算效率；數(shù)據(jù)及圖結(jié)構(gòu)驅(qū)動(dòng)，不同的圖形結(jié)構(gòu)會(huì)使用不同的計(jì)算方法，需要設(shè)計(jì)一個(gè)通用的方法；存儲(chǔ)和效率，大圖處理的規(guī)模（點(diǎn)的數(shù)量）基本上是10億量級(jí)，依靠單臺(tái)PC進(jìn)行存儲(chǔ)似乎不太可能，所以大多數(shù)圖計(jì)算系統(tǒng)是分布式系統(tǒng)。由于這種系統(tǒng)是把存儲(chǔ)容量和計(jì)算分?jǐn)偨o每一個(gè)機(jī)器，因此需要考慮如何劃分才能使各機(jī)器負(fù)載均衡以及如何減少各個(gè)劃分之間通信等問題。

3 典型計(jì)算系統(tǒng)

3.1 批量大數(shù)據(jù)計(jì)算系統(tǒng)

當(dāng)前典型的大數(shù)據(jù)批量計(jì)算的應(yīng)用系統(tǒng)有Hadoop[11]、Spark[13]。在Hadoop系統(tǒng)中，其體系結(jié)構(gòu)如圖3所示，由名字節(jié)點(diǎn)、數(shù)據(jù)節(jié)點(diǎn)、客戶端節(jié)點(diǎn)組成。其中，名字節(jié)點(diǎn)負(fù)責(zé)管理文件系統(tǒng)的命名空間、集群配置以及數(shù)據(jù)塊的備份、容錯(cuò)等內(nèi)容；數(shù)據(jù)節(jié)點(diǎn)負(fù)責(zé)管理數(shù)據(jù)的存儲(chǔ)位置、副本數(shù)目等內(nèi)容，并以數(shù)據(jù)塊的形式存儲(chǔ)原始數(shù)據(jù)與校驗(yàn)信息；客戶端節(jié)點(diǎn)通過與名字節(jié)點(diǎn)、數(shù)據(jù)節(jié)點(diǎn)進(jìn)行通信，訪問HDFS，實(shí)現(xiàn)文件操作。數(shù)據(jù)通過HDFS的方式進(jìn)行組織，可以將各類數(shù)據(jù)存儲(chǔ)在各種外部存儲(chǔ)介質(zhì)上，并通過MapReduce模式將計(jì)算邏輯分配到各數(shù)據(jù)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)計(jì)算和知識(shí)發(fā)現(xiàn)。

圖3 Hadoop體系結(jié)構(gòu)

圖4 RDD的操作繼承關(guān)系

在Spark系統(tǒng)中，數(shù)據(jù)被轉(zhuǎn)換成彈性分布式數(shù)據(jù)集（resilient distributed dataset，RDD），并以RDD為單位實(shí)現(xiàn)有效的數(shù)據(jù)處理。每個(gè)RDD都是一個(gè)不可變的分布式可重算的數(shù)據(jù)集，其記錄著確定性的操作繼承關(guān)系。如圖4所示，每一個(gè)橢圓形表示一個(gè)RDD，橢圓形中的每個(gè)圓形代表一個(gè)RDD中的一個(gè)分區(qū)。通過對(duì)RDD的操作繼承關(guān)系進(jìn)行跟蹤，當(dāng)任意一個(gè)RDD的分區(qū)出錯(cuò)或不可用時(shí)，只要輸入數(shù)據(jù)可重現(xiàn)，就可以利用原始輸入數(shù)據(jù)通過轉(zhuǎn)換操作而重新算出，實(shí)現(xiàn)系統(tǒng)的容錯(cuò)。

同時(shí)，Spark系統(tǒng)也可以在一定程度上支持大數(shù)據(jù)流式計(jì)算和交互計(jì)算的應(yīng)用范式。

3.2 流式大數(shù)據(jù)計(jì)算系統(tǒng)

早期流式計(jì)算的研究往往集中在數(shù)據(jù)庫(kù)環(huán)境中開展數(shù)據(jù)計(jì)算的流式化，數(shù)據(jù)規(guī)模較小，數(shù)據(jù)對(duì)象比較單一。大數(shù)據(jù)環(huán)境中的流式數(shù)據(jù)在實(shí)時(shí)性、易失性、突發(fā)性、無序性、無限性等方面提出了更高要求，現(xiàn)階段關(guān)于大數(shù)據(jù)流式計(jì)算的研究則更多地從系統(tǒng)架構(gòu)、數(shù)據(jù)傳輸、編程接口、高可用策略等方面開展和實(shí)施。當(dāng)前典型的大數(shù)據(jù)流式計(jì)算的應(yīng)用系統(tǒng)有Storm[17]、S4[18]。

在Storm系統(tǒng)中，采用主從式系統(tǒng)架構(gòu)。如圖5所示，一個(gè)Storm系統(tǒng)中有兩類節(jié)點(diǎn)，即一個(gè)主節(jié)點(diǎn)Nimbus和多個(gè)從節(jié)點(diǎn)supervisor，有3種運(yùn)行環(huán)境，即master、cluster和slaves。其中，主節(jié)點(diǎn)Nimbus運(yùn)行在master環(huán)境中，是無狀態(tài)的，負(fù)責(zé)全局的資源分配、任務(wù)調(diào)度、狀態(tài)監(jiān)控和故障檢測(cè)；從節(jié)點(diǎn)supervisor運(yùn)行在slaves環(huán)境中，也是無狀態(tài)的，負(fù)責(zé)監(jiān)聽并接收來自于主節(jié)點(diǎn)Nimbus所分配的任務(wù)，并啟動(dòng)或停止自己所管理的工作進(jìn)程worker，其中，工作進(jìn)程worker負(fù)責(zé)具體任務(wù)的執(zhí)行。zookeeper是一個(gè)針對(duì)大型分布式系統(tǒng)的可靠協(xié)調(diào)服務(wù)和元數(shù)據(jù)存儲(chǔ)系統(tǒng)，通過配置zookeeper集群，可以使用zookeeper系統(tǒng)所提供的高可靠性的服務(wù)。Storm系統(tǒng)引入zookeeper，極大地簡(jiǎn)化了Nimbus、supervisor、worker之間的設(shè)計(jì)，保障了系統(tǒng)的穩(wěn)定性。

圖5 Storm系統(tǒng)架構(gòu)

在S4系統(tǒng)中，采用對(duì)等式系統(tǒng)架構(gòu)。如圖6所示，一個(gè)S4系統(tǒng)由用戶空間、資源調(diào)度空間和S4處理節(jié)點(diǎn)空間組成。其中，在用戶空間中，多個(gè)用戶可以通過本地的客戶端驅(qū)動(dòng)實(shí)現(xiàn)服務(wù)的請(qǐng)求訪問；在資源調(diào)度空間中，為用戶提供了客戶適配器，通過TCP/IP實(shí)現(xiàn)用戶的客戶端驅(qū)動(dòng)與客戶適配器間的連接和通信，多個(gè)用戶可以并發(fā)地同多個(gè)客戶適配器進(jìn)行服務(wù)請(qǐng)求；在S4處理節(jié)點(diǎn)空間中，提供了多個(gè)處理節(jié)點(diǎn)Pnode，進(jìn)行用戶服務(wù)請(qǐng)求的計(jì)算，主要包括監(jiān)聽并分發(fā)接收到的事件計(jì)算請(qǐng)求，實(shí)現(xiàn)對(duì)事件流的路由選擇、負(fù)載均衡、邏輯影射、故障恢復(fù)等功能。各個(gè)處理節(jié)點(diǎn)間保持相對(duì)的獨(dú)立性、對(duì)等性和高并發(fā)性，極大地提高了系統(tǒng)的性能，并通過散列方式將事件路由到一個(gè)或多個(gè)目標(biāo)處理節(jié)點(diǎn)上。

圖6 S4系統(tǒng)結(jié)構(gòu)

3.3 大數(shù)據(jù)圖計(jì)算系統(tǒng)

大數(shù)據(jù)圖計(jì)算主要用來分析數(shù)據(jù)節(jié)點(diǎn)之間的關(guān)系和相似度，其巨大的商業(yè)價(jià)值已經(jīng)凸顯。例如，利用PageRank技術(shù)發(fā)現(xiàn)有影響力的用戶，將GraphLab技術(shù)[20]用于社區(qū)、欺詐檢測(cè)和推薦系統(tǒng)，還有一些分布式計(jì)算應(yīng)用到Giraph、GraphX、Faunus和Grappa。GraphLab是美國(guó)卡耐基大學(xué)開發(fā)的一個(gè)并行的圖挖掘分布式系統(tǒng)。該技術(shù)解決了傳統(tǒng)MapReduce中有關(guān)機(jī)器學(xué)習(xí)處理頻繁迭代計(jì)算和大量節(jié)點(diǎn)通信導(dǎo)致的計(jì)算效率低下的問題。具體來講，在GraphLab中，以頂點(diǎn)為計(jì)算單元，將機(jī)器學(xué)習(xí)算法抽象為聚集、應(yīng)用和分散3個(gè)步驟。在每一個(gè)迭代過程中，點(diǎn)的計(jì)算需要經(jīng)過這3個(gè)步驟。并且，Graphlab是在共享內(nèi)存的基礎(chǔ)上，各機(jī)器異步、動(dòng)態(tài)并行地執(zhí)行計(jì)算任務(wù)，比BSP（bulk synchronous parallel，整體同步并行）計(jì)算效率更高，并且能夠很好地保證數(shù)據(jù)的一致性。

4 未來研究方向

從系統(tǒng)角度看大數(shù)據(jù)計(jì)算，未來可能的研究方向包括以下幾個(gè)方面。

（1）批量計(jì)算

大數(shù)據(jù)批量計(jì)算需要讀寫大量數(shù)據(jù)，而目前的存儲(chǔ)系統(tǒng)主要針對(duì)計(jì)算密集型應(yīng)用設(shè)計(jì)，從存儲(chǔ)系統(tǒng)讀出原始數(shù)據(jù)進(jìn)行批量計(jì)算，計(jì)算結(jié)束后將計(jì)算結(jié)果寫入存儲(chǔ)系統(tǒng)。相應(yīng)存儲(chǔ)系統(tǒng)強(qiáng)調(diào)數(shù)據(jù)吞吐量，數(shù)據(jù)一致性保證程度高，數(shù)據(jù)讀寫時(shí)延相對(duì)較高。一個(gè)有潛力的研究方向是利用大數(shù)據(jù)批量計(jì)算的特征，解決大數(shù)據(jù)計(jì)算中的存儲(chǔ)瓶頸問題。

另一類研究工作是針對(duì)典型應(yīng)用進(jìn)行定制化的性能優(yōu)化，一個(gè)代表性例子是深度學(xué)習(xí)算法的并行加速技術(shù)研究。以深度學(xué)習(xí)中的卷積神經(jīng)元網(wǎng)絡(luò)為例，一個(gè)研究方向是使用GPU對(duì)卷積神經(jīng)元網(wǎng)絡(luò)進(jìn)行加速，另一個(gè)方向是使用多臺(tái)機(jī)器對(duì)卷積神經(jīng)元網(wǎng)絡(luò)進(jìn)行并行化加速。

（2）大數(shù)據(jù)流式計(jì)算

需要構(gòu)建一個(gè)高效、可擴(kuò)展的計(jì)算平臺(tái)，一方面需要具有很好的通用性，滿足對(duì)流式數(shù)據(jù)計(jì)算的需要，提供一系列公用的流式計(jì)算工具和屬性；同時(shí)要在在線資源管理、狀態(tài)一次性維護(hù)、用戶級(jí)容錯(cuò)策略等方面具有良好的性能。

大數(shù)據(jù)流式計(jì)算中，數(shù)據(jù)流具有多流混合、流速波動(dòng)等特性，一個(gè)研究方向是如何設(shè)計(jì)并優(yōu)化流式計(jì)算中的資源調(diào)度策略，同時(shí)實(shí)現(xiàn)數(shù)據(jù)流速高時(shí)處理速度快和數(shù)據(jù)流速低時(shí)能耗低兩個(gè)目標(biāo)。大數(shù)據(jù)流式計(jì)算需要提供7×24 h的連續(xù)計(jì)算能力，對(duì)于系統(tǒng)可靠性方面的要求很高。另一個(gè)研究方向是如何利用流式計(jì)算的特征，同時(shí)實(shí)現(xiàn)數(shù)據(jù)流計(jì)算高可靠和可靠性維護(hù)開銷低兩個(gè)目標(biāo)。

（3）大數(shù)據(jù)圖計(jì)算

圖計(jì)算系統(tǒng)的構(gòu)建有兩個(gè)思路：一種是為了避免數(shù)據(jù)關(guān)聯(lián)性帶來的機(jī)間通信而采用單機(jī)圖處理。往往采用圖數(shù)據(jù)分區(qū)的方法，每次加載一個(gè)分區(qū)，循環(huán)多次處理一張大圖。網(wǎng)絡(luò)大數(shù)據(jù)的多維關(guān)聯(lián)性，導(dǎo)致大數(shù)據(jù)計(jì)算對(duì)網(wǎng)絡(luò)圖空間的訪問發(fā)散性。由于緩存機(jī)制和介質(zhì)特性，整個(gè)存儲(chǔ)棧都對(duì)數(shù)據(jù)局部性表現(xiàn)出更好的性能。一個(gè)重要的研究方向是如何解決網(wǎng)絡(luò)圖空間的訪問發(fā)散性與高效存儲(chǔ)所需的數(shù)據(jù)局部性之間的矛盾。

另一種思路是充分發(fā)揮多臺(tái)機(jī)器并行計(jì)算的優(yōu)勢(shì)而采用多機(jī)圖計(jì)算。這種大數(shù)據(jù)圖計(jì)算方式面臨的最為突出的問題就是大圖分割問題。由于對(duì)整個(gè)圖的訪問是隨機(jī)進(jìn)行的，一個(gè)研究方向是如何在圖劃分時(shí)實(shí)現(xiàn)通信代價(jià)低、計(jì)算及傳輸負(fù)載均衡、存儲(chǔ)冗余度合理3個(gè)目標(biāo)。

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

在大數(shù)據(jù)時(shí)代，大數(shù)據(jù)計(jì)算是大數(shù)據(jù)整個(gè)生命周期中的核心，是大數(shù)據(jù)中知識(shí)發(fā)現(xiàn)的關(guān)鍵。大數(shù)據(jù)計(jì)算模式主要包括大數(shù)據(jù)批量計(jì)算、流式計(jì)算、圖計(jì)算、交互計(jì)算等，這些不同的計(jì)算模式分別滿足不同的應(yīng)用范式對(duì)數(shù)據(jù)計(jì)算結(jié)果在處理精度、實(shí)時(shí)性等方面的不同要求。這些計(jì)算模式并不是相互獨(dú)立的，可以相互配合，滿足同一應(yīng)用范式在不同階段對(duì)數(shù)據(jù)計(jì)算結(jié)果的要求。當(dāng)前，批量計(jì)算是大數(shù)據(jù)計(jì)算的最主要模式。隨著用戶應(yīng)用需求和技術(shù)的不斷變化，所需要的計(jì)算模式也會(huì)不斷變化，亟待根據(jù)最新應(yīng)用范式的發(fā)展和要求，針對(duì)具體場(chǎng)景，開展對(duì)相關(guān)計(jì)算模式中出現(xiàn)的新情況、新問題的研究。

[1] Chen C L, Zhang C Y. Data-intensive applications, challenges, techniques and technologies: a survey on big data. Information Sciences, 2014(275): 314～347 [2] Chang R M, Kauffman R J, Kwon Y. Understanding the paradigm shift to computational social science in the presence of big data. Decision Support Systems, 2014(63): 67～80

[3] Kambatla K, Kollias G, Kumar V, et al. Trends in big data analytics. Journal of Parallel and Distributed Computing, 2014(74): 2561～2573

[4] 李國(guó)杰, 程學(xué)旗. 大數(shù)據(jù)研究: 未來科技及經(jīng)濟(jì)社會(huì)發(fā)展的重大戰(zhàn)略領(lǐng)域——大數(shù)據(jù)的研究現(xiàn)狀與科學(xué)思考. 中國(guó)科學(xué)院院刊, 2012, 27(6): 647～657 Li G J, Cheng X Q. Big data research: the major strategic areas of technology and economic development——research status and scientific thinking of big data. Bulletin of the Chinese Academy of Sciences, 2012, 27(6): 647～657

[5] 孫大為, 張廣艷, 鄭緯民. 大數(shù)據(jù)流式計(jì)算：關(guān)鍵技術(shù)及系統(tǒng)實(shí)例. 軟件學(xué)報(bào), 2014, 25(4): 839～862 Sun D W, Zhang G Y, Zheng W M. Big data stream computing: technologies and instances. Journal of Software, 2014, 25(4): 839～862

[6] 程學(xué)旗, 靳小龍, 王元卓等. 大數(shù)據(jù)系統(tǒng)和分析技術(shù)綜述. 軟件學(xué)報(bào), 2014, 25(9):1889～1908 Cheng X Q, Jin X L, Wang Y Z, et al. Survey on big data system and analytic technology. Journal of Software, 2014, 25(9): 1889～1908

[7] 王元卓, 靳小龍, 程學(xué)旗. 網(wǎng)絡(luò)大數(shù)據(jù)：現(xiàn)狀與展望. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(6): 1125～1138 Wang Y Z, Jin X L, Cheng X Q. Network big data: present and future. Chinese Journal of Computers, 2013, 36(6): 1125～1138

[8] 李學(xué)龍, 龔海剛. 大數(shù)據(jù)系統(tǒng)綜述. 中國(guó)科學(xué):信息科學(xué), 2015, 45(1): 1～44 Li X L, Gong H G. Survey on big data system. Scientia Sinica Informationis, 2015, 45(1): 1～44

[9] Dobre C, Xhafa F. Intelligent services for big data science. Future Generation Computer Systems, 2014(37): 267～281

[10] Aisling O D, Jurate D, Roy D S. Big data, Hadoop and cloud computing in genomics. Journal of Biomedical Informatics, 2013(46): 774～781

[11] Hadoop. http://hadoop.apache.org/,2005

[12] Zaharia M, Das T, Li H, et al. Discretized streams: fault-tolerant streaming computation at scale. Proceedings of the SOSP 2013, Pennsylvania, USA, 2013

[13] Spark. http://spark-project.org,2013

[14] Cugola G, Margara A. Processing flows of information: from data stream to complex event processing. ACM Computing Surveys, 2012, 44(3): 51～62

[15] Zhang Z, Gu Y, Ye F, et al. A hybrid approach to high availability in stream processing systems. Proceedings of the 30th IEEE International Conference on Distributed Computing Systems, Genova, Italy, Jun 2010: 138～148

[16] Liu X F, Lftikhar N, Xie X. Survey of real-time processing systems for big data. Proceedings of IDEAS 2014, Porto Portugal, 2014: 356～361

[17] Storm. http://storm-project.net/,2015

[18] Chauhan J, Chowdhury S A, Makaroff D. Performance evaluation of Yahoo! S4: a first look. Proceedings of 7th International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, Victoria, BC, Canada, 2012: 58～65

[19] Chatziantoniou D, Pramatari K, Sotiropoulos Y. Supporting real-time supply chain decisions based on RFID data streams. Journal of Systems and Software, 2011, 84(4): 700～710

[20] GraphLab. http://graphlab.org/projects/ index.html,2015

[21] Furedi Z, Kostochka A, Kumbhat M. Choosability with separation of complete multipartite graphs and hypergraphs. Journal of Graph Theory, 2014, 76(2): 129～137

Zheng W M. Reviewing big data computation from a system perspective. Big Data Research, 2015002

Reviewing Big Data Computation from a System Perspective

Zheng Weimin
Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China

Big data computing is a necessary way to acquire the “great value” behind the big data, and a computing system is an effective tool for big data computing. Big data computing from a system perspective was reviewed. Based on the fact that big data has the macro characteristics of huge volume, growing fast, complex structure, and quality disparity, the typical features of big data computing by analyzing batch computing, stream computing, and graph computing respectively, were discussed. These features may bring technical challenges to the design and implementation of big data computing system. The related works for overcoming these challenges were further categoried. In the end, some prospective research directions of big data computing from the system perspective were listed.

big data computing, batch computing, stream computing, graph computing, system instance

鄭緯民，男，清華大學(xué)教授、博士生導(dǎo)師，中國(guó)計(jì)算機(jī)學(xué)會(huì)理事長(zhǎng)，目前主要從事并行與分布式計(jì)算、存儲(chǔ)系統(tǒng)的研究工作，主持和參與多項(xiàng)國(guó)家“973”計(jì)劃、“863”計(jì)劃、國(guó)家自然科學(xué)基金項(xiàng)目。近年來在IEEE TC/IEEE TPDS/ACM TOS/FAST等本領(lǐng)域頂級(jí)期刊與國(guó)際會(huì)議發(fā)表論文40余篇。

2015-05-03；

2015-05-06

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（“973”計(jì)劃）基金資助項(xiàng)目（No.2014CB340402），國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61170008，No.61272055）

Foundation Items:The National Basic Research Program of China(973 Program)(No.2014CB340402), The National Natural Science Foundation of China(No.61170008，No.61272055)

鄭緯民. 從系統(tǒng)角度審視大數(shù)據(jù)計(jì)算. 大數(shù)據(jù), 2015002