大數(shù)據(jù)環(huán)境下并行計算模型的研究進(jìn)展

潘 巍， 李戰(zhàn)懷

（1.西北工業(yè)大學(xué) 計算機(jī)學(xué)院，西安 710072；2.廣東省普及型高性能計算機(jī)重點實驗室／深圳市服務(wù)計算與應(yīng)用重點實驗室，深圳 518000）

0 引 言

從計算機(jī)誕生以來，人類對于計算性能的追求從未停止，作為高性能計算和超級計算的核心技術(shù)，并行計算是充分利用資源加速計算的主要途徑.但是對于大多數(shù)程序員而言，編寫分布式并行應(yīng)用具有極高的編程門檻，不但需要程序員具有豐富的硬件、體系結(jié)構(gòu)、操作系統(tǒng)等背景知識，還需要其編寫大量復(fù)雜繁瑣的、應(yīng)用邏輯之外的分布式并行控制邏輯.這些因素使得并行程序設(shè)計始終沒有成為主流程序設(shè)計的核心.而且，由于遵循摩爾定律的處理器的性能在過去很長一段時間內(nèi)能夠持續(xù)穩(wěn)定的增長，因此設(shè)計和開發(fā)并行程序的必要性和緊迫性被無意的掩蓋.但是，隨著大數(shù)據(jù)時代的來臨，從應(yīng)用需求、硬件環(huán)境、互聯(lián)模式到計算技術(shù)都在發(fā)生顯著的變化，人們對分布式并行計算的需求也在日益突出.上述變化為分布式并行計算提供了新的發(fā)展契機(jī)，同時也帶來了巨大的研究挑戰(zhàn).其中，多樣化的并行計算模型是消除分布式并行應(yīng)用開發(fā)瓶頸、推動大數(shù)據(jù)發(fā)展的核心技術(shù)之一.目前，工業(yè)界和學(xué)術(shù)界正在進(jìn)行各種嘗試和探索，研究和開發(fā)不同的并行計算模型，以滿足大數(shù)據(jù)處理的多樣化需求.本文以并行計算模型相關(guān)研究為核心，首先回顧并行計算的發(fā)展以及大數(shù)據(jù)環(huán)境下推動其發(fā)展的主要變化，然后對現(xiàn)有的面向批處理模式、面向流處理模式、面向圖數(shù)據(jù)以及面向內(nèi)存的并行計算模型進(jìn)行歸納和總結(jié)，最后闡述大數(shù)據(jù)時代并行計算模型面臨的挑戰(zhàn)和發(fā)展趨勢.

1 并行計算的回顧

在計算機(jī)最初發(fā)展的十幾年里，從體系結(jié)構(gòu)到系統(tǒng)軟件以及應(yīng)用軟件都采用串行計算作為主要的設(shè)計和開發(fā)模式.但是很快人們就意識到，并行計算是突破串行計算效率瓶頸、提高計算性能的有力和必須的手段.相對于串行計算，并行計算可以劃分成由流水線技術(shù)為代表的時間并行，以及以多處理器并發(fā)執(zhí)行為代表的空間并行，兩種并行方式都可以有效地提高計算資源的利用能力，從而提高程序的執(zhí)行性能，并行計算的思想也開始滲透到計算機(jī)硬件和軟件技術(shù)發(fā)展的各個層面.

1954年，阿姆達(dá)爾定律的提出者Gene Amdahl設(shè)計出首臺內(nèi)建浮點硬件的商用機(jī)器IBM704，并行加速理念被隨之帶入.1964年第一臺在技術(shù)和市場上同時獲得成功的高性能大規(guī)模并行計算機(jī)CDC6600研制成功，多功能單元并行技術(shù)是其中領(lǐng)先的核心技術(shù)之一.同時，1965年由貝爾實驗室、MIT和美國通用電氣聯(lián)手開發(fā)的分時操作系統(tǒng)Multics，嘗試在操作系統(tǒng)層面通過引入并行計算思想提高運(yùn)行其上的應(yīng)用程序的性能和編程效率.雖然該系統(tǒng)最終因為超前的設(shè)計思維、執(zhí)行計劃延誤以及資金短缺等情況宣告失敗，但是受其思想激發(fā)和推動，誕生了兩個在計算機(jī)發(fā)展歷史中最具影響力的軟件產(chǎn)品：Unix系統(tǒng)和C語言.1966年，Michael Flynn根據(jù)指令流和數(shù)據(jù)流的倍數(shù)特征首次針對并行計算系統(tǒng)提出了著名的Flynn分類法［1］，SISD、SIMD、MISD、MIMD的分類至今仍然具有一定的代表性.此外，還有Handler分類法、Hockney－Jesshope等分類方法根據(jù)執(zhí)行特征或者結(jié)構(gòu)特征等不同條件對并行計算系統(tǒng)進(jìn)行分類，不同的分類方法更有利于人們根據(jù)應(yīng)用需求進(jìn)行適合的并行系統(tǒng)的選擇.當(dāng)然，還有大量數(shù)值并行算法和并行程序設(shè)計技術(shù)的出現(xiàn)也在有力推動著并行計算的發(fā)展和應(yīng)用.

計算科學(xué)也成為繼實驗科學(xué)、理論科學(xué)之后的第三種科學(xué)研究范式，并在以生物制藥、氣候預(yù)測、能源勘探、高精武器設(shè)計、制造環(huán)境模擬為代表的科學(xué)計算領(lǐng)域獲得了巨大的成功.但是，在非科學(xué)計算領(lǐng)域，并行計算的普及和應(yīng)用卻一直未得到長足的發(fā)展.發(fā)展滯后的主要原因有以下幾點：（1）首先，在2002年之前，如摩爾定律所言，隨著半導(dǎo)體技術(shù)的發(fā)展，單個處理器的性能以平均年50%的速度在不斷提升，使得大量應(yīng)用可以在不增加任何成本的情況下在新的處理器上獲得指數(shù)級的性能提升.“免費(fèi)的午餐”使普通程序員找不到編寫復(fù)雜分布式并行應(yīng)用的理由和動力；（2）其次，分布式并行編程的門檻相對較高，相對于執(zhí)行路徑可預(yù)測的串行程序，分布式并行程序的執(zhí)行具有不確定性和異步性，因而需要大量復(fù)雜的通信、同步以及調(diào)度等并發(fā)控制操作.雖然面向共享存儲體系結(jié)構(gòu)的OpenMP以及面向分布式存儲體系結(jié)構(gòu)的MPI等并行計算模型的出現(xiàn)在一定程度上解決了由程序員負(fù)責(zé)一切并發(fā)控制細(xì)節(jié)的困難局面，但是這些早期的計算模型在容錯性、可擴(kuò)展性、負(fù)載平衡等方面仍存在很大不足，而且抽象層次比較低，因此正確編寫高性能的分布式并行應(yīng)用仍具有極高的復(fù)雜度；（3）再者，并行計算的模式高度依賴于并行硬件環(huán)境和體系結(jié)構(gòu)，但是并行硬件環(huán)境本身的構(gòu)建也存在著成本高、可擴(kuò)展性差、管理困難、能耗大等諸多問題.因此，僅有國家實驗室、航天航空、國防安全等大型機(jī)構(gòu)有能力建設(shè)和維護(hù)此類高性能集群，也使得并行計算一直局限于計算密集型的科學(xué)計算領(lǐng)域.

上述這些問題成為廣泛采用并行計算機(jī)和分布式并行計算技術(shù)的主要阻礙，也使得分布式并行計算發(fā)展遇到了一些瓶頸.但是，在大數(shù)據(jù)時代，上述制約并行計算發(fā)展的掣肘正在發(fā)生改變，為分布式并行計算的發(fā)展帶來了前所未有的機(jī)遇和挑戰(zhàn).（1）摩爾定律的影響力正在減弱.因為受限于散熱問題、功耗問題以及處理器材料物理特性的極限，單一地通過增加晶體管集成度從而提高單個處理器的運(yùn)算能力和處理能力的可行性正在變得越來越低.因此，應(yīng)用越來越難以通過單純地依賴處理器性能穩(wěn)步提升而獲得“免費(fèi)”的性能提升.同時，多＼眾核技術(shù)、異構(gòu)多核集成技術(shù)（低功耗與高性能核心的集成、CPU與GPU的組合等）以及多CPU的并行處理技術(shù)，已經(jīng)成為目前提高處理器能力和運(yùn)算速度的主流途徑.但是，現(xiàn)有的軟件無法直接利用多核的優(yōu)勢提高執(zhí)行性能，并行技術(shù)成為最大限度利用多＼眾核處理器能力的必須途徑.（2）云計算為分布式并行計算提供了新的平臺.云計算從某種意義上來說，也是原始Beowulf集群的在商業(yè)應(yīng)用模式上經(jīng)過優(yōu)化的衍生物，都是使用非定制的普通硬件設(shè)備、網(wǎng)絡(luò)以及軟件構(gòu)建并行硬件環(huán)境.同時，云計算技術(shù)更強(qiáng)調(diào)其商業(yè)運(yùn)作模式，即如何通過虛擬化技術(shù)和統(tǒng)一的編程模型開放軟硬件資源供用戶使用.Pay－asyou－go的使用模式也使得大量中小型機(jī)構(gòu)甚至個人都可以根據(jù)需求構(gòu)建高可定制的并行集群環(huán)境，為分布式并行計算在非科學(xué)計算領(lǐng)域的普及與應(yīng)用帶來了新的可能性和可行性.（3）大數(shù)據(jù)帶來了迫切的應(yīng)用需求.在大數(shù)據(jù)時代，藉由自動感知、模擬實驗、軟件處理已經(jīng)累積了足夠多的數(shù)據(jù)，對科研人員而言如何從海量數(shù)據(jù)中發(fā)現(xiàn)信息、提取知識、預(yù)測趨勢、制定決策成為更為緊迫的任務(wù).數(shù)據(jù)密集型科學(xué)研究成為工業(yè)界和學(xué)術(shù)界新的共同關(guān)注點，由于它有別于計算科學(xué)的特點、需求和環(huán)境，一種稱之為“數(shù)據(jù)密集型計算”的新的研究范式成為“第四范式”.在大數(shù)據(jù)背景下，數(shù)據(jù)密集型應(yīng)用越來越多，計算系統(tǒng)的發(fā)展正在由高性能計 算 （HPC，High－Performance Computing）向 高 吞 吐 計 算 （HTC，High－Throughput Computing）轉(zhuǎn)變.相比于傳統(tǒng)的CPU密集型計算，數(shù)據(jù)密集型計算是結(jié)合數(shù)據(jù)局部性原則采用數(shù)據(jù)并行方法實現(xiàn)大規(guī)模并行計算的應(yīng)用技術(shù)，計算數(shù)據(jù)量級為TB級或PB級.這種數(shù)量級是傳統(tǒng)數(shù)據(jù)處理技術(shù)無法支撐的，分布式并行處理再次成為應(yīng)對大數(shù)據(jù)應(yīng)用需求的熱點研究方向.

在這樣的前提下，集群規(guī)模的可伸縮性和分布式并行應(yīng)用的可編程性成為了主要的發(fā)展矛盾，而架構(gòu)在硬件和應(yīng)用之間的計算模型則成為緩解兩者之間矛盾的最關(guān)鍵的技術(shù)之一.計算模型是一種涵蓋存儲模型、執(zhí)行模型、調(diào)度模型、恢復(fù)模型的綜合抽象，可以有效屏蔽大量繁雜的并行控制細(xì)節(jié)，能夠在大規(guī)模廉價集群中以并行、可擴(kuò)展、容錯、易用、透明的方式支持各種并行算法的高效執(zhí)行，為開發(fā)人員提供簡潔的編程抽象，極大降低大規(guī)模集群并行編程的門檻.在過去，分布式并行計算領(lǐng)域多呈現(xiàn)出一種應(yīng)用比硬件規(guī)模小的軟硬失衡的格局，關(guān)鍵問題就在于缺乏易用、高效、多樣化的計算模型.但是在大數(shù)據(jù)背景下，隨著以MapReduce／Hadoop為代表的大規(guī)模數(shù)據(jù)分布式并行計算模型的出現(xiàn)與巨大成功，工業(yè)界和學(xué)術(shù)界對于并行計算模型的關(guān)注越來越高.而且隨著應(yīng)用需求的變化，目前在不同應(yīng)用領(lǐng)域中也涌現(xiàn)了多種并行計算模型.本文在后續(xù)章節(jié)從面向批處理、面向流處理、面向圖數(shù)據(jù)以及面向內(nèi)存等幾個層面介紹多樣化的并行計算模型，以及國內(nèi)外相關(guān)的研究成果.

2 并行計算模型

2.1 面向批處理的并行計算模型及優(yōu)化技術(shù)

目前，具有代表性的面向批處理式分析的分布式并行計算模型有微軟公司的Dryad［2］、谷歌公司的MapReduce［3］等.其中，谷歌公司的MapReduce是最早受到關(guān)注且應(yīng)用最廣泛的并行編程模型，并且隨著其開源實現(xiàn)Hadoop的興起，目前已經(jīng)形成了初具規(guī)模的海量數(shù)據(jù)分析新生態(tài)系統(tǒng)，大量的周邊系統(tǒng)［4－8］為其成功應(yīng)用提供了堅實的支撐.MapReduce已經(jīng)成為學(xué)術(shù)界和工業(yè)界事實上的海量數(shù)據(jù)并行批量處理的標(biāo)準(zhǔn).相比于傳統(tǒng)的并行計算技術(shù)，MapReduce具備了線性可擴(kuò)展性、高可用性、易用性、容錯性、負(fù)載平衡以及魯棒性等大數(shù)據(jù)處理系統(tǒng)所必須的特性.而且，用戶在使用MapReduce并行編程模型時只需要關(guān)注與具體應(yīng)用相關(guān)的高層處理邏輯，而將其余低層復(fù)雜的并行事務(wù)（如輸入分布、任務(wù)劃分與調(diào)度、任務(wù)間通信、容錯處理以及負(fù)載平衡等）交與執(zhí)行引擎完成.同時，配合用戶自定義的輸入輸出流處理、任務(wù)調(diào)度、中間數(shù)據(jù)分區(qū)和排序等可編程接口，該模型可伸縮性和可編程性上實現(xiàn)了極佳的平衡點.但是，當(dāng)MapReduce在工業(yè)界和學(xué)術(shù)界一路高歌猛進(jìn)的同時，越來越多質(zhì)疑和負(fù)面的聲音［9，10］也隨之出現(xiàn).爭論主要來自于傳統(tǒng)關(guān)系數(shù)據(jù)管理技術(shù)陣營，爭論的焦點直指MapReduce的執(zhí)行性能.作為一個優(yōu)先考慮易用性和通用性的編程模型，MapReduce在完成同等級任務(wù)的執(zhí)行性能上低于同等規(guī)模的并行數(shù)據(jù)庫系統(tǒng)［11］.這種性能上的差距部分來自于架構(gòu)上的制約，部分來自于實現(xiàn)上的差異［12］.因此，MapReduce仍存在很大的優(yōu)化改進(jìn)和性能提升空間.大量面向MapReduce的優(yōu)化研究工作隨之展開.

原始的MapReduce更關(guān)注工作節(jié)點間的高層次并行，并未針對多核或GPU等新型硬件進(jìn)行專門的優(yōu)化處理，為提供對多核和GPU的充分支持，研究人員做了大量的工作.架構(gòu)在共享內(nèi)存體系結(jié)構(gòu)上Phoenix［13］系統(tǒng)是MapReduce在多核環(huán)境下的實現(xiàn)方案.Phoenix的底層實現(xiàn)建立在P－threads之上，使用線程創(chuàng)建并行化的Map和Reduce任務(wù)，并為使用者提供了一組易用的API和高效的運(yùn)行時.Phoenix發(fā)布后，很多文獻(xiàn)圍繞Phoenix開展了有針對性的優(yōu)化.文獻(xiàn)［14］針對UltraSPARC處理器實現(xiàn)了Phoenix系統(tǒng)多層次的優(yōu)化，包括算法、實現(xiàn)以及OS接口.Mao等人［15］通過定位多核處理中的性能瓶頸，實現(xiàn)了針對中間數(shù)據(jù)分組處理的數(shù)據(jù)結(jié)構(gòu)級的Phoenix優(yōu)化，并引入了一個新的MapReduce庫Metis.文獻(xiàn)［16］在Phoenix系統(tǒng)上提供了抽象程度更高更易用的MATE編程接口和環(huán)境，同時大幅減少了數(shù)據(jù)密集型應(yīng)用所需的內(nèi)存空間.而Phoenix＋＋［17］則提供了一個支持模塊化和可擴(kuò)展流水線的Phoenix增強(qiáng)版本.此外，文獻(xiàn)［18］和［19］分別關(guān)注了 MapReduce在非對

稱多核集群以及異構(gòu)多核集群上的研究挑戰(zhàn)，并給出了相應(yīng)的解決方案.除了在通用多核處理器（集群）上的研究外，MapReduce在專用的多核處理器芯片Cell B.E（Cell Broadband Engine）以及 GPU 上也有相關(guān)的優(yōu)化研究工作［20－23］.

此外，為提高并行的效率，針對MapReduce架構(gòu)性的優(yōu)化也受到了廣泛的關(guān)注，主要改善內(nèi)容包括提高迭代性能［24］、優(yōu)化調(diào)度效率［25］、增強(qiáng)流水線處理［26］、減小數(shù)據(jù)傾斜對性能的影響［27］、增加索引［28］以及對關(guān)系代數(shù)提供支持［29］等.雖然 MapReduce模型在大量優(yōu)化技術(shù)的改善和支持下，在可擴(kuò)展性、易用性、可用性、性價比等方面都具有較強(qiáng)的優(yōu)勢，但是作為通用的大數(shù)據(jù)分布式并行計算模型，其并沒有針對某些特殊數(shù)據(jù)類型、應(yīng)用領(lǐng)域以及新型存儲器件進(jìn)行專門的優(yōu)化.而且面向特定需求的優(yōu)化技術(shù)既難以從根本上解決多樣化數(shù)據(jù)處理需求給計算模型帶來的挑戰(zhàn)，甚至還可能會對模型本身造成不同程度的影響和損害.CCCF《2014年大數(shù)據(jù)發(fā)展趨勢預(yù)測》一文中指出：“大數(shù)據(jù)處理架構(gòu)的多樣化模式并存”將成為未來并行計算模型發(fā)展的新趨勢，MapReduce框架一統(tǒng)天下的格局將被打破，而根據(jù)不同需求設(shè)計的多樣化并行計算模型將成為與之并存的重要研究內(nèi)容.后面幾節(jié)將介紹在不同領(lǐng)域獲得成功應(yīng)用的并行計算模型.

2.2 面向流處理的并行計算模型及優(yōu)化技術(shù)

在大數(shù)據(jù)應(yīng)用中，實時數(shù)據(jù)流應(yīng)用是一類新型的用瞬態(tài)數(shù)據(jù)建模的數(shù)據(jù)密集型應(yīng)用.其典型特征是數(shù)據(jù)價值具有時效性，即數(shù)據(jù)蘊(yùn)含的價值會隨著時間的流逝而降低.因此，低延遲是對數(shù)據(jù)流處理系統(tǒng)的一個基本要求.同時，數(shù)據(jù)以大量、連續(xù)、快速、時變的方式到達(dá)系統(tǒng)，需要處理的數(shù)據(jù)不可能全部存儲在可隨機(jī)訪問的磁盤或內(nèi)存中.使用面向批處理高度優(yōu)化的MapReduce直接處理無界的數(shù)據(jù)流具有很大的應(yīng)用局限性.一種典型的MapReduce數(shù)據(jù)流處理策略是將無界的數(shù)據(jù)流劃分成較小的有界批處理子集，然后用批處理模式對已持久化的數(shù)據(jù)流快照進(jìn)行分析.因為該處理策略會引入大量不必要的磁盤及網(wǎng)絡(luò)I／O開銷，所以無法滿足流式應(yīng)用對實時性的需求.此外，在該策略中處理延遲與劃分的長度以及MR作業(yè)的初始化開銷高度耦合，在執(zhí)行代價和響應(yīng)時間上存在難以調(diào)和的矛盾.也有部分研究者嘗試改進(jìn)MapReduce體系使其適應(yīng)數(shù)據(jù)流，如HOP［30］，但其僅解決了任務(wù)間數(shù)據(jù)傳輸模式導(dǎo)致的阻塞問題，缺少完整的面向數(shù)據(jù)流處理的系統(tǒng)設(shè)計.

為緩解上述問題，一些研究者嘗試將MapReduce模型與典型的數(shù)據(jù)流系統(tǒng)進(jìn)行融合，形成更高效的處理架構(gòu).其中，文獻(xiàn)［31］將MapReduce與分布式流處理系統(tǒng)Mortar進(jìn)行了融合，實現(xiàn)了適合數(shù)據(jù)流處理的連續(xù)型MapReduce.Kumar［32］等人通過在IBM的System S數(shù)據(jù)流處理中間件上進(jìn)行MapReduce擴(kuò)展實現(xiàn)了DEDUCE系統(tǒng)，該系統(tǒng)可同時支持批量處理與數(shù)據(jù)流處理.Brito［33］等人則試圖將事件流處理系統(tǒng)（ESP）的設(shè)計概念與MapReduce思想進(jìn)行結(jié)合，嘗試構(gòu)建可擴(kuò)展且低延遲的數(shù)據(jù)處理系統(tǒng).布朗大學(xué)的C－MR［34］則在MapReduce模型中引入滑動窗口概念以支持?jǐn)?shù)據(jù)流的連續(xù)執(zhí)行，但是其只適用于多核架構(gòu)的單機(jī)系統(tǒng).而M3［35］則是利用大容量內(nèi)存屏蔽低效的磁盤IO提高流數(shù)據(jù)處理效率的MapReduce改進(jìn)版.對基于MapReduce的數(shù)據(jù)流處理而言，這些研究都是有益的嘗試.但事實上，MapReduce在內(nèi)部架構(gòu)上還存在大量不利于流水處理的阻塞式設(shè)計，其中包括基于磁盤的容錯、Map階段和Reduce階段之間的障柵延遲、基于拉模式的中間數(shù)據(jù)傳輸方式等都是導(dǎo)致其高處理延遲的內(nèi)在原因.因此面向流數(shù)據(jù)的專用并行計算模型才是解決問題的根本途徑.

在大數(shù)據(jù)概念出現(xiàn)之前，實時數(shù)據(jù)流處理領(lǐng)域已經(jīng)出現(xiàn)了許多專用系統(tǒng)，如布朗大學(xué)與MIT聯(lián)合開發(fā)的Aurora［36］以及后續(xù)演化的加入分布式特征的Borealis［37］、加州大學(xué)伯克利分校的 Telegraph［38］、IBM 的SPC［39］、威斯康星大學(xué)的 NiagaraCQ［40］等.但是在大數(shù)據(jù)環(huán)境下，上述專用系統(tǒng)在可擴(kuò)展性、并行度、吞吐量、可處理數(shù)據(jù)對象的多樣性等方面難以滿足新的挑戰(zhàn)和需求.近年來伴隨社交網(wǎng)絡(luò)的急速發(fā)展，大規(guī)模高擴(kuò)展的流式計算模型再次成為業(yè)界研究的熱點，具有代表性的有 Yahoo！的S4［41］、Facebook的Puma［42］、谷歌的MillWheel［43］等、Twitter的Storm［44］等，這些系統(tǒng)與企業(yè)自身的具體需求緊密結(jié)合，致力于解決實際的應(yīng)用問題.相比于批處理計算模型，上述流式并行計算模型從流數(shù)據(jù)本身的特征出發(fā)，從底層架構(gòu)上就與流數(shù)據(jù)處理高度耦合，雖然適用范圍比較局限，但是可以有效地將系統(tǒng)響應(yīng)時間控制在毫秒級，但是在吞吐能力、負(fù)載平衡等方面尚有待進(jìn)一步提高.

2.3 面向大圖數(shù)據(jù)的并行計算模型及優(yōu)化技術(shù)

大數(shù)據(jù)時代背景下，數(shù)十億頂點級別大規(guī)模圖的不斷涌現(xiàn)以及云計算基礎(chǔ)設(shè)施的持續(xù)完善，推動著圖數(shù)據(jù)處理的研究重心由單機(jī)圖算法的高度優(yōu)化逐漸轉(zhuǎn)向分布式并行大圖處理的優(yōu)化.目前，大圖數(shù)據(jù)處理存在兩種典型的模式：一是采用通用的海量數(shù)據(jù)分布式并行計算框架MapReduce進(jìn)行處理；二是采用完全面向圖結(jié)構(gòu)設(shè)計的專用大圖計算框架［45－48］.由于MapReduce在應(yīng)用定位與設(shè)計目標(biāo)上主要是針對模式自由（schema－free）的數(shù)據(jù)對象實現(xiàn)高吞吐的批量處理，因此其缺乏有效處理大圖的內(nèi)部機(jī)制.相比之下，專用大圖并行計算模型有針對性地考慮了圖計算的基本特征，因此從框架內(nèi)部就已經(jīng)提供了對大圖處理的支持，能獲得較好的性能.其顯著的特征是提供了對圖計算中最常見的迭代操作的支持和實現(xiàn)了直觀易用的以頂點為中心的編程抽象［45］.

從存儲架構(gòu)上可以將大圖并行計算模型分為：面向分布內(nèi)存架構(gòu)以及面向單機(jī)多核共享內(nèi)存架構(gòu)兩類.在分布內(nèi)存架構(gòu)下，目前具有代表性的大圖并行計算模型有Pregel［45］、HAMA［49］、Giraph［47］、Distributed GraphLab［50］以及 Trinity［46］等.由于圖結(jié)構(gòu)的高耦合性，分布式環(huán)境下圖計算的網(wǎng)絡(luò)通信代價很高，圖劃分是優(yōu)化分布式大圖計算通信開銷的有效手段.部分大圖處理系統(tǒng)采用經(jīng)典的劃分方法，如ParMetis［51］，也有其他一些系統(tǒng)探索了新的劃分方法，如GraphX和PowerGraph均采用vertex－cut的劃分方法［52，53］緩解自然圖中高度數(shù)（high－degree）頂點通信集中的問題；Trinity采用多層標(biāo)簽傳遞的劃分方法［54］，借助圖的語義有效支持了十億頂點級別大圖的劃分；而GPS和Mizan都利用動態(tài)的劃分方法［55，56］緩解了大圖計算過程中負(fù)載失衡時的頂點重分配的問題.除了最棘手的圖劃分問題外，分布式內(nèi)存架構(gòu)仍然面臨很多困難，如需要開發(fā)者具有專門的分布式編程知識在集群環(huán)境中進(jìn)行復(fù)雜的調(diào)試與優(yōu)化工作.鑒于此，一些研究工作面向單機(jī)環(huán)境提出了有針對性的優(yōu)化技術(shù)，如序列化隨機(jī)訪問［57］、利用多核以及新型存儲的高并發(fā)能力［58］、引入異步機(jī)制［59］等，并設(shè)計了相應(yīng)的大圖計算模型.上述研究利用外存的一些訪問特性，通過有針對性的優(yōu)化提升處理效率，緩解大圖對內(nèi)存的壓力.此外，還有一些基于單機(jī)的圖計算系統(tǒng)［60－62］，仍然假設(shè)以全內(nèi)存的方式進(jìn)行圖數(shù)據(jù)處理.雖然這些研究的側(cè)重點不在存儲模式，但是在大圖環(huán)境下這些研究成果的實施效果可能會受到一定的影響.

此外，從計算模式上，又可以將大圖并行計算模型分為同步與異步兩種模式.BSP同步計算模型對數(shù)據(jù)競爭是免疫的，無需特別的調(diào)度來保證程序執(zhí)行結(jié)果的確定性（determinacy），同時超步（super step）概念天然的與圖計算的迭代操作相匹配.因此，大量圖計算系統(tǒng)［45－47，49，55］采用BSP同步計算模型.雖然BSP同步模型具有諸多優(yōu)點，但是模型本身也存在自身所固有的性能瓶頸：通信與同步.在通信代價優(yōu)化技術(shù)方面，基于鄰接鏈表的冗余存儲［55］和基于本地內(nèi)存的異步訪問［63］都是減少通信代價的有效手段.在成本量化中，相比于通信，BSP模型固有的同步開銷在整體計算成本中所占的比例相對更高.因此，異步執(zhí)行機(jī)制成為解決該問題的關(guān)鍵所在.基于共享內(nèi)存的GraphLab［61］及其分布式版本Distributed GraphLab［50］是同時期具有代表性的異步大圖處理系統(tǒng).相比于只能使用上輪迭代獲得的輸入進(jìn)行計算的同步模型，異步執(zhí)行模型可以使用最新的數(shù)據(jù)作為計算輸入，因此其能夠加快迭代的收斂速度.此外，使用基于優(yōu)先級［64］或增量［65］的優(yōu)化技術(shù)還可以進(jìn)一步提高迭代的收斂速度.同時，面向頂點的執(zhí)行調(diào)度也可以加快收斂，例如，動態(tài)重劃分［55］和基于殘差值的優(yōu)先級調(diào)度［60］都是有效技術(shù).需要說明的是，異步雖然在圖計算效率上具有優(yōu)勢，但對于基于異步模型的大圖算法實現(xiàn)上，需要應(yīng)用開發(fā)者管理更多的控制細(xì)節(jié)，增加了編程的難度.因此，在大數(shù)據(jù)環(huán)境下，一方面，圖在結(jié)構(gòu)和計算上的高耦合性給分布式環(huán)境下大圖計算模型的設(shè)計帶來了難以回避的研究挑戰(zhàn)；另一方面，新型硬件技術(shù)特別是存儲級內(nèi)存（storage class memory，SCM）［66］的高速發(fā)展，從硬件層面為重構(gòu)分布式大圖計算模型的支撐環(huán)境提供了新的機(jī)遇.

2.4 基于內(nèi)存的并行計算模型及優(yōu)化技術(shù)

受限于廉價PC構(gòu)建的運(yùn)行環(huán)境以及面向領(lǐng)域高度優(yōu)化的系統(tǒng)架構(gòu)，上述并行計算模型難以有效應(yīng)對新型實時型應(yīng)用對于實時、即席、交互式分析的復(fù)雜業(yè)務(wù)訴求.同時，大數(shù)據(jù)不同維度特征所表現(xiàn)出的增量速度快、持續(xù)增加規(guī)模大、數(shù)據(jù)類型差異明顯等客觀事實，也進(jìn)一步加劇了現(xiàn)有計算模型所面臨的內(nèi)存容量有限、I／O效率低下、并發(fā)控制困難、數(shù)據(jù)處理總體性能較低等諸多問題.然而，隨著計算機(jī)硬件、體系結(jié)構(gòu)的快速發(fā)展，客觀上為設(shè)計以數(shù)據(jù)為中心的基于高性能服務(wù)器集群的內(nèi)存數(shù)據(jù)管理新格局創(chuàng)造了發(fā)展契機(jī).大數(shù)據(jù)的海量特征一直在強(qiáng)調(diào)有限的存儲空間無法容納數(shù)據(jù)密集型應(yīng)用的全部工作負(fù)載，但是使用基于磁盤的分布式存儲環(huán)境又難以滿足性能上的實時需求.而隨著SCM技術(shù)的快速發(fā)展，內(nèi)存容量越來越大，同時價格越來越便宜，目前適用于內(nèi)存計算的擁有TB級內(nèi)存容量的服務(wù)器正在逐步普及，為內(nèi)存計算提供了物理條件上的保障.而且，相比于全部數(shù)據(jù)級，大部分應(yīng)用的活躍的工作數(shù)據(jù)集明顯有限，也為常駐內(nèi)存處理提供了事實的依據(jù)，典型的例子如采用讀寫事務(wù)分離架構(gòu)的OceanBase.

在基于內(nèi)存的面向大數(shù)據(jù)的分布式并行計算模型研究工作開展之前，工業(yè)界和學(xué)術(shù)界在基于內(nèi)存的數(shù)據(jù)管理技術(shù)，特別是主存數(shù)據(jù)庫領(lǐng)域已經(jīng)累積的大量的研究成果和經(jīng)驗.關(guān)于主存數(shù)據(jù)庫研究的早期動因是內(nèi)存容量的增長速度可能高于磁盤，但是當(dāng)九十年代后期，新型巨磁阻技術(shù)的出現(xiàn)將磁盤容量年增量率由原來的30%大幅提升到200%后，基于內(nèi)存的單一系統(tǒng)的發(fā)展逐漸放緩.面向磁盤的分布式數(shù)據(jù)管理系統(tǒng)由于其高可擴(kuò)展的顯著優(yōu)勢成為大數(shù)據(jù)時代初期最有效的數(shù)據(jù)管理技術(shù).但是其性能上的不足，又促使基于分布式內(nèi)存的數(shù)據(jù)管理系統(tǒng)的發(fā)展成為新的焦點.近些年工業(yè)界和學(xué)術(shù)界都針對于分布式內(nèi)存數(shù)據(jù)庫系統(tǒng)進(jìn)行了研究.工業(yè)界出現(xiàn)了很多相關(guān)產(chǎn)品，Memcached［67］是最著名的全內(nèi)存式數(shù)據(jù)存取系統(tǒng)，被Facebook，Twitter，YouTube，Reddit等多家世界知名企業(yè)所使用，該系統(tǒng)使用DHT實現(xiàn)網(wǎng)絡(luò)拓?fù)涞臉?gòu)建以及數(shù)據(jù)的布局及查詢，為上層應(yīng)用提供了高可用的狀態(tài)存儲和可伸縮的應(yīng)用加速服務(wù).與Memcached類似，VMware的Redis［68］也提供了性能卓越的內(nèi)存存儲功能，支持包括字符串、哈希表、鏈表、集合、有序集合等多種數(shù)據(jù)類型以及更加易于使用的API，相比于Memcached，Redis提供了更靈活的緩存失效策略和持久化機(jī)制.此外，還有如微軟的Hekaton［69］，SAP的HANA［70］等內(nèi)存數(shù)據(jù)庫產(chǎn)品隨著需求的發(fā)展仍在不斷涌現(xiàn).在學(xué)術(shù)界，MIT的H－Store［71］（VoltDB的前身）是內(nèi)存數(shù)據(jù)處理環(huán)境下的原型系統(tǒng)，其根據(jù)CPU Core進(jìn)行數(shù)據(jù)分區(qū)，通過數(shù)據(jù)庫多副本來獲得數(shù)據(jù)的持久性.為解決處理數(shù)據(jù)超過內(nèi)存容量的問題，布朗大學(xué)的DeBrabant等人還針對H－Store系統(tǒng)提出了Anti－Caching策略［72］.此外，慕尼黑工業(yè)大學(xué)開發(fā)的HyPer［73］原型系統(tǒng)試圖利用內(nèi)存計算的特點基于統(tǒng)一的存儲模型將傳統(tǒng)上分離的OLTP和OLAP融合在一起進(jìn)行處理.

近年來，在新型實時應(yīng)用的驅(qū)動下，以最短響應(yīng)時間為設(shè)計目標(biāo)的面向內(nèi)存設(shè)計的編程模型及其系統(tǒng)也在不斷涌現(xiàn)，為即席實時可交互的分析提供了多樣化的選擇.其中具有代表性的是UCBerkeley的基于內(nèi)存的分布式并行處理框架Spark［74］，其利用內(nèi)存計算避免了高延遲的磁盤物化，有效保證了處理的實時性并提供了交互式的迭代分析能力.Spark提供的最主要的抽象即彈性分布式數(shù)據(jù)集RDD（resilient distributed datasets）［75］，RDD是一個分布在一組節(jié)點之間的只讀的對象集合.這些集合是彈性的，能夠在部分?jǐn)?shù)據(jù)集丟失的情況下利用血統(tǒng)（lineage）容錯機(jī)制進(jìn)行重建.為了提供操作的便捷性，Spark框架還提供了和Hive類似的類SQL命令接口Shark［76］.同時，基于Spark的內(nèi)存計算分析生態(tài)系統(tǒng)，如處理流數(shù)據(jù)的Spark streaming［77］，用于大圖計算的GraphX［53］等，正在不斷的完善與開發(fā)之中.需要指出的是，內(nèi)存數(shù)據(jù)管理并不是一個全新的話題，但是在大數(shù)據(jù)背景下，該研究領(lǐng)域的外延和內(nèi)涵都在發(fā)生變化，特別是隨著各種新型存儲技術(shù)、多／眾核處理器技術(shù)、虛擬化技術(shù)、硬件圖形加速技術(shù)的發(fā)展，內(nèi)存數(shù)據(jù)管理特別是內(nèi)存計算模型的發(fā)展將迎來新一輪的研究高峰，并將成為未來大數(shù)據(jù)實時處理領(lǐng)域的熱點.

3 結(jié) 論

在大數(shù)據(jù)背景下，傳統(tǒng)應(yīng)用領(lǐng)域以及新興應(yīng)用領(lǐng)域都對信息系統(tǒng)的數(shù)據(jù)處理能力提出越來越高的需求.從吞吐量到響應(yīng)時間，從可擴(kuò)展性到可容錯性，從易用性到高性價比，這些指標(biāo)無一不給數(shù)據(jù)處理技術(shù)帶來了重大的挑戰(zhàn).此外，基礎(chǔ)硬件環(huán)境的重大技術(shù)突破以及云計算等商業(yè)模式的成功也為數(shù)據(jù)處理提供了新的發(fā)展契機(jī).上述原因決定了在未來很長一段時間內(nèi)，分布式并行處理將是解決大數(shù)據(jù)處理問題的主要技術(shù)手段，而分布式并行計算模型在多個指標(biāo)上有針對性的優(yōu)化和平衡則是推動分布式并行計算在大數(shù)據(jù)環(huán)境下成功應(yīng)用的關(guān)鍵所在.目前，在應(yīng)用需求和技術(shù)變革的雙重推動下，并行計算模型已經(jīng)起步，但是仍處于發(fā)展初期，尚面臨著大量的研究挑戰(zhàn).不過可以預(yù)見的是，未來多樣化的并行計算模型百花齊放的發(fā)展格局將成為推動并行計算快速發(fā)展的有力助推器.

［1］ FLYNN M J.Some computer organizations and their effectiveness［J］.IEEE Transactions on Computers.1972，21（9）：948－960.

［2］ ISARD M，BUDIU M，YU Y，et al.Dryad：distributed data－parallel programs from sequential building blocks［C］／／Proceedings of ACM SIGOPS／EuroSys European Conference on Computer Systems（SIGOPS 2007）.Lisbon，Portugal：ACM，2007：59－72.

［3］ DEAN J，GHEMAWAT S.MapReduce：a flexible data processing tool［J］.Commun ACM2010，53（1）：72－77.

［4］ CAFARELLA M，CUTTING D.Building Nutch：Open Source Search［J］.Queue，2004，2（2）：54－61.

［5］ RABKIN A，KATZ R.Chukwa：a system for reliable large－scale log collection［C］／／Proceedings of the International Conference on Llarge Installation System Administration（LISA2010）.San Jose，CA：［s.n.］2010：1－15.

［6］ HUNT P，KONAR M，JUNQUEIRA F P，et al.ZooKeeper：wait－free coordination for internet－scale systems［C］／／Proceedings of the USENIX Conference on USENIX Annual Technical Conference（USENIXATC2010）.Boston，MA：［s.n.］，2010：11－11.

［7］ OLSTON C，REED B，SRIVASTAVA U，et al.Pig latin：a not－so－foreign language for data processing［C］／／Proceedings of the ACM SIGMOD international conference on management of data（SIGMOD2008）.Vancouver，Canada：［s.n.］，2008：1099－1110.

［8］ THUSOO A，SARMA J S，JAIN N，et al.Hive：a warehousing solution over a map－reduce framework［J］.Proceedings of the VLDB Endowment（VLDB2009）.2009，2（2）：1626－1629.

［9］ DEWITT D J，STONEBRAKER M.MapReduce：A major step backwards［J］.論壇.2009.

［10］ STONEBRAKER M，ABADI D，DEWITT D J，et al.MapReduce and parallel DBMSs：friends or foes？［J］.Communications of the ACM，2010，53（1）：64－71.

［11］ PAVLO A，PAULSON E，RASIN A，ABADI D J，et al.A Comparision of Approaches to Large－Scale Data Analysis［J］.SIGMOD.2009.

［12］ JIANG D，OOI B C，SHI L，et al.The performance of MapReduce：An in－depth study［J］.VLDB.2010.

［13］ RANGER C，RAGHURAMAN R，PENMETSA A，et al.Evaluating MapReduce for Multi－core and Multiprocessor Systems［C］／／Proceedings of the 2007 IEEE13th International Symposium on High Performance Computer Architecture.2007：13－24.

［14］ YOO R M，ROMANO A，KOZYRAKIS C.Phoenix rebirth：Scalable MapReduce on a large－scale shared－memory system［C］／／Proceedings of the 2009 IEEE International Symposium on Workload Characterization （IISWC）.2009：198－207.

［15］ MAO Y，MORRIS R，KAASHOEK M F.Optimizing MapReduce for Multicore Architectures［J］.Technical Report MIT－CSAIL－TR－2010－020.2010.

［16］ JIANG W，RAVI V T，AGRAWAL G.A Map－Reduce System with an Alternate API for Multi－core Environments［C］／／Proceedings of the 10th IEEE／ACM International Conference on Cluster，Cloud and Grid Computing（CCGRID2010）.2010：84－93.

［17］ TALBOT J，YOO R M，KOZYRAKIS C.Phoenix＋＋：modular MapReduce for shared－memory systems［C］／／Proceedings of the Second International Workshop on MapReduce and Its Applications（MapReduce 2011）.San Jose，California：［s.n.］，2011：9－16.

［18］ RAFIQUE M M，ROSE B，BUTT A R，et al.Supporting MapReduce on large－scale asymmetric multi－core clusters［J］.ACM SIGOPS Operating Systems Review.2009，43（2）：25－34.

［19］ LINDERMAN M D，COLLINS J D，WANG H，et al.Merge：aprogramming model for heterogeneous multi－core systems［J］.ACM SIGOPS Operating Systems Review，2008，42（2）：287－296.

［20］ KRUIJF M D，SANKARALINGAM K.MapReduce for the cell broadband engine architecture［J］.IBM Journal of Research and Development，2009，53（5）：747－758.

［21］ RAFIQUE M M，ROSE B，BUTT A R，et al.CellMR：A framework for supporting mapreduce on asymmetric cell－based clusters［C］／／Proceedings of the 2009 IEEE International Symposium on Parallel＆Distributed Processing.2009：1－12.

［22］ CHEN L，AGRAWAL G.Optimizing MapReduce for GPUs with effective shared memory usage［C］／／Proceedings of the 21st international symposium on High－Performance Parallel and Distributed Computing（HDPC2012）.Delft，The Netherlands：［s.n.］，2012：199－210.

［23］ HE B，F(xiàn)ANG W，LUO Q，et al.Mars：a MapReduce framework on graphics processors［C］／／Proceedings of the International Conference on Parallel Architectures and Compilation Techniques（PACT2008）.Toronto，Ontario：［s.n.］，2008：260－269.

［24］ ONIZUKA M，KATO H，HIDAKA S，et al.Optimization for iterative queries on MapReduce［C］.Proceedings of the VLDB Endowment（VLDB2014）.2014，7（4）.

［25］ SUN X，HE C，LU Y.ESAMR：An Enhanced Self－Adaptive MapReduce Scheduling Algorithm［C］／／Proceedings of the 2012 IEEE18th International Conference on Parallel and Distributed Systems.2012：148－155.

［26］ LI B，MAZUR E，DIAO Y，et al.A platform for scalable one－pass analytics using MapReduce［C］／／Proceedings of ACM SIGMOD International Conference on Management of Data（SIGMOD2011）.Athens，Greece，2011：985－996.

［27］ KWON Y，BALAZINSKA M，HOWE B，et al.SkewTune：mitigating skew in mapreduce applications［C］／／Proceedings of the ACM SIGMOD International Conference on Management of Data（SIGMOD2012）.Scottsdale，Arizona，USA，2012：25－36.

［28］ DITTRICH J，QUIANERUIZ J A，RICHTER S，et al.Only aggressive elephants are fast elephants［J］.Proceedings of the VLDB Endowment（VLDB2012）.2012，5（11）：1591－1602.

［29］ ZHANG X，CHEN L，WANG M.Efficient multi－way theta－join processing using MapReduce［C］.Proceedings of the VLDB Endowment（VLDB2012）.2012，5（11）：1184－1195.

［30］ CONDIE T，CONWAY N，ALVARO P，et al.MapReduce online［C］／／Proceedings of USENIX conference on networked systems design and implementation（NSDI 2010）.San Jose，California，2010：21－21.

［31］ LOGOTHETIS D，YOCUM K.Ad－h(huán)oc data processing in the cloud［C］.Proceedings of the VLDB Endowment（VLDB2008）.2008，1（2）：1472－1475.

［32］ KUMAR V，ANDRADE H，B U，＃287，GEDIK R，et al.DEDUCE：at the intersection of MapReduce and stream processing［C］／／Proceedings of the 13th International Conference on Extending Database Technology（EDBT2010）.Lausanne，Switzerland，2010：657－662.

［33］ BRITO A，MARTIN A，KNAUTH T，et al.Scalable and Low－Latency Data Processing with Stream MapReduce［C］／／Proceedings of the 2011 IEEE Third International Conference on Cloud Computing Technology and Science（CLOUDCOM2011）.2011：48－58.

［34］ BACKMAN N，PATTABIRAMAN K，F(xiàn)ONSECA R，et al.C－MR：continuously executing MapReduce workflows on multi－core processors［C］／／Proceedings of Third International Workshop on MapReduce and Its Applications Date（MapReduce 2012）.Delft，The Netherlands：［s.n.］，2012：1－8.

［35］ ALY A M，SALLAM A，GNANASEKARAN B M，et al.M3：Stream processing on main－memory mapReduce［C］／／Proceedings of the IEEE28th International Conference on Data Engineering（ICDE 2012）.2012：1253－1256.

［36］ ABADI D J，CARNEY D，CETINTEMEL U，et al.Aurora：a new model and architecture for data stream management［C］.Proceedings of the VLDB Endowment（VLDB2003）.2003，12（2）：120－139.

［37］ AHMAD Y，BERG B，CETINTEMEL U，et al.Distributed operation in the Borealis stream processing engine［C］／／Proceedings of the ACM SIGMOD international conference on Management of data（SIGMOD2005）.Baltimore，Maryland：［s.n.］，2005：882－884.

［38］ MADDEN S，SHAH M，HELLERSTEIN J M，et al.Continuously adaptive continuous queries over streams［C］／／Proceedings of the ACM SIGMOD international conference on management of data（SIGMOD2002）.Madison，Wisconsin：［s.n.］，2002：49－60.

［39］ AMINI L，ANDRADE H，BHAGWAN R，et al.SPC：a distributed，scalable platform for data mining［C］／／Proceedings of the international workshop on data mining standards，services and platforms（DMSSP2006）.Philadelphia，Pennsylvania：［s.n.］，2006：27－37.

［40］ CHEN J，DEWITT D J，TIAN F，et al.NiagaraCQ：a scalable continuous query system for Internet databases［C］／／Proceedings of the ACM SIGMOD international conference on Management of data（SIGMOD2000）.Dallas，Texas：［s.n.］，2000：379－390.

［41］ NEUMEYER L，ROBBINS B，NAIR A，et al.S4：Distributed Stream Computing Platform［J］.Proceedings of the IEEE International Conference on Data Mining Workshops（ICDMW2010）.2010：170－177

［42］ ZHENG S.Data Freeway and Puma：Realtime Data Streams and Analytics［C］／／Proceedings of Hadoop in China（HiC2011）2011.

［43］ AKIDAU T，BALIKOV A，BEKIROGLU K，et al.Whittle.MillWheel：fault－tolerant stream processing at internet scale［C］.Proceedings of the VLDB Endowment（VLDB2013）.2013，6（11）：1033－1044.

［44］ STORM，http：／／storm.incubator.apache.org／.

［45］ MALEWICZ G，AUSTERN M H，BIK A J C，et al.Pregel：a system for large－scale graph processing［C］／／Proceedings of the ACM SIGMOD International Conference on Management of data（SIGMOD2010）.Indianapolis，Indiana：［s.n.］，2010：135－146.

［46］ SHAO B，WANG H，LI Y.Trinity：a distributed graph engine on a memory cloud［C］／／Proceedings of the ACM SIGMOD International Conference on Management of Data（SIGMOD2013）.New York：［s.n.］，2013：505－516.

［47］ Giraph，https：／／giraph.apache.org／.

［48］ VENKATARAMANI V，AMSDEN Z，BRONSON N，et al.TAO：how facebook serves the social graph［C］／／Proceedings of the ACM SIGMOD International Conference on Management of Data（SIGMOD2012）Scottsdale，Arizona：［s.n.］，2012：791－792.

［49］ HAMA，https：／／hama.apache.org／.

［50］ LOW Y，BICKSON D，GONZALEZ J，et al.Distributed GraphLab：a framework for machine learning and data mining in the cloud［C］.Proceedings of the VLDB Endowment（VLDB2012）.2012，5（8）：716－727.

［51］ KARYPIS G，KUMAR V.A parallel algorithm for multilevel graph partitioning and sparse matrix ordering［J］.Journal of Parallel and Distributed Computing，1998，48（1）：71－95.

［52］ GONZALEZ J E，LOW Y，GU H，et al.PowerGraph：distributed graph－parallel computation on natural graphs［C］／／Proceedings of the USENIX Conference on Operating Systems Design and Implementation（OSDI 2012）.Hollywood，CA：［s.n.］，2012：17－30.

［53］ XIN R S，GONZALEZ J E，F(xiàn)RANKLIN M J，et al.GraphX：a resilient distributed graph system on Spark［C］／／First International Workshop on Graph Data Management Experiences and Systems（GRADES2013）.New York：［s.n.］，2013：1－6.

［54］ WANG L，XIAO Y，SHAO B，et al.How to Partition a Billion－Node Graph［C］／／Proceedings of the IEEE International Conference on Data Engineering（ICDE2014）.（Accepted）.

［55］ SALIHOGLU S，WIDOM J.GPS：agraph processing system［C］／／Proceedings of the International Conference on Scientific and Statistical Database Management（SSDBM2013）.Baltimore，Maryland，2013：1－12.

［56］ KHAYYAT Z，AWARA K，ALONAZI A，et al.Mizan：a system for dynamic load balancing in large－scale graph processing［C］／／Proceedings of the ACM European Conference on Computer Systems（EuroSys 2013）.Prague：［s.n.］，2013：169－182.

［57］ KYROLA A，BLELLOCH G，GUESTRIN C.GraphChi：large－scale graph computation on just a PC［C］／／Proceedings of the USENIX conference on Operating Systems Design and Implementation（OSDI 2012）.Hollywood，CA：［s.n.］，2012：31－46.

［58］ HAN W S，LEE S，PARK K，et al.TurboGraph：a fast parallel graph engine handling billion－scale graphs in a single PC［C］／／Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining（SIGKDD2013）.Chicago，Illinois：［s.n.］，2013：77－85.

［59］ PEARCE R，GOKHALE M，Amato N M.Multithreaded Asynchronous Graph Traversal for In－Memory and Semi－External Memory［C］／／Proceedings of the ACM／IEEE International Conference for High Performance Computing，Networking，Storage and Analysis（SC2010）.2010：1－11.

［60］ WANG G，XIE W，DEMERS A，et al.Asynchronous Large－Scale Graph Processing Made Easy［C］／／Proceedings of the Conference on Innovative Data Systems Research（CIDR2013）.2013.

［61］ LOW Y，GONZALEZ J，KYROLA A，et al.Graphlab：A new parallel framework for machine learning［C］／／Conference on Uncertainty in Artificial Intelligence（UAI 2010）.Catalina Island，CA，USA，2010：340－349.

［62］ XIE W，WANG G，BINDEL D，et al.Fast iterative graph computation with block updates［C］.Proceedings of the VLDB Endowment（VLDB2013）.2013，6（14）：2014－2025.

［63］ TIAN Y，BALMIN A，CORSTEN S A，et al.From"Think Like a Vertex"to"Think Like a Graph"［C］.Proceedings of the VLDB Endowment（VLDB2013）.2013，7（3）：193－204.

［64］ ZHANG Y，GAO Q，GAO L，et al.PrIter：a distributed framework for prioritized iterative computations［C］／／Proceedings of the ACM Symposium on Cloud Computing（SOCC2011）.Cascais，Portugal，2011：1－14.

［65］ ZHANG Y，GAO Q，GAO L，et al.Maiter：An Asynchronous Graph Processing Framework for Delta－based Accumulative Iterative Computation［J］.IEEE Transactions on Parallel and Distributed Systems（TPDS），2013：Pre－Print.

［66］ JUNG J，WON Y，KIM E，et al.FRASH：Exploiting storage class memory in hybrid file system for hierarchical storage［J］.ACM Transactions on Storage（TOS），2010，6（1）：1－25.

［67］ FITZPATRICK B.Distributed caching with memcached［J］.Linux Journal.2004，2004（124）：5.

［68］ ZAWODNY J.Redis：Lightweight key／value Store That Goes the Extra Mile［J］.Linux Magazine.2009.

［69］ DIACONU C，F(xiàn)REEDMAN C，ISMERT E，et al.Hekaton：SQL server＇s memory－optimized OLTP engine［C］／／Proceedings of the ACM SIGMOD International Conference on Management of Data（SIGMOD2013）.New York，New York：［s.n.］，2013：1243－1254.

［70］ SIKKA V，F(xiàn)ARBER F，GOEL A，et al.SAP HANA：the evolution from a modern main－memory data platform to an enterprise application platform［C］／／Proceedings of the VLDB Endowment（VLDB 2013）.2013，6（11）：1184－1185.

［71］ KALLMAN R，KIMURA H，NATKINS J，et al.H－store：a high－performance，distributed main memory transaction processing system［C］／／Proceedings of the VLDB Endowment（VLDB2008）.2008，1（2）：1496－1499.

［72］ DEBRABANT J，PAVLO A，TU S，et al.Anti－caching：a new approach to database management system architecture［J］.Proceedings of the VLDB Endowment（VLDB2013）.2013，6（14）：1942－1953.

［73］ KEMPER A，NEUMANN T.HyPer：A hybrid OLTP＆OLAP main memory database system based on virtual memory snapshots［C］／／Proceedings of the IEEE International Conference on Data Engineering （ICDE 2011）.2011：195－206.

［74］ ZAHARIA M，CHOWDHURY M，F(xiàn)RANKLIN M J，et al.Spark：cluster computing with working sets［C］／／Proceedings of the USENIX conference on hot topics in cloud computing（HotCloud2010）.Boston，MA：［s.n.］，2010：10.

［75］ ZAHARIA M，CHOWDHURY M，DAS T，et al.Resilient distributed datasets：a fault－tolerant abstraction for in－memory cluster computing［C］／／Proceedings of the USENIX Conference on Networked Systems Design and Implementation（NSDI 2012）.San Jose，CA：［s.n.］，2012：2－2.

［76］ XIN R S，ROSEN J，ZAHARIA M.et al.Shark：SQL and rich analytics at scale［C］／／Proceedings of the ACM SIGMOD International Conference on Management of Data（SIGMOD2013）.New York：［s.n.］，2013：13－24.

［77］ ZAHARIA M，DAS T，LI H，et al.Discretized streams：an efficient and fault－tolerant model for stream processing on large clusters［C］／／Proceedings of the USENIX Conference on Hot Topics in Cloud Computing（HotCloud 2012）.Boston，MA：［s.n.］，2012：10－10.