大數(shù)據(jù)技術發(fā)展的十個前沿方向（中）

Ten Fronties for Big Data Technologies (Part B)

吳甘沙，男，現(xiàn)任英特爾中國研究院院長。2000年加入英特爾，先后在編程系統(tǒng)實驗室與嵌入式軟件實驗室承擔了技術與管理職位，期間參與或主持的研究項目有受控運行時、XScale微架構(gòu)、眾核架構(gòu)、數(shù)據(jù)并行編程及高生產(chǎn)率嵌入設備驅(qū)動程序開發(fā)工具等。2011年晉升為首席工程師，共同領導了公司的大數(shù)據(jù)中長期技術規(guī)劃，主持大數(shù)據(jù)方面的研究，工作重點為大數(shù)據(jù)內(nèi)存分析與數(shù)據(jù)貨幣化。在英特爾工作期間，發(fā)表了10余篇學術論文，有23項美國專利（10余項成為國際專利），14項專利進入審核期。

6 前沿方向四：軟硬兼施

大數(shù)據(jù)計算的一個核心要義是軟硬兩手抓，從具體應用出發(fā)，仔細選擇軟硬件架構(gòu)實現(xiàn)，并且在運行過程中持續(xù)不斷地協(xié)同優(yōu)化。

首先，從大數(shù)據(jù)應用角度出發(fā)，硬件架構(gòu)重點體現(xiàn)在計算、存儲、互聯(lián)。

6.1 計算硬件架構(gòu)

在計算這一塊，首先要選擇的是大小核。brawny cores是大核，主要是至強服務器芯片，wimpy cores是小核，F(xiàn)AWN（fast array of wimpy nodes）最早展示了小核陣列在特定計算和I/O輪廓下的數(shù)據(jù)密集型應用中具有一定的能耗優(yōu)勢，其所指的核是Atom或ARM這種級別的核。小核往往需要跟閃存存儲結(jié)合才能體現(xiàn)系統(tǒng)級的能耗效率提升。對于絕大多數(shù)的大數(shù)據(jù)應用，大核系統(tǒng)優(yōu)于小核，谷歌公司基礎設施的領導者Urs Holzle[21]和亞馬遜公司AWS的主要架構(gòu)師James Hamilton[22]在相關文獻中有所論述。另外，基于小核的系統(tǒng)還面臨其他一些挑戰(zhàn)，比如需要軟件做額外的優(yōu)化、串行部分變慢影響了整體并行加速比、調(diào)度無法保證很多小核的高利用率等。

第二，硬件架構(gòu)方面，要從同構(gòu)計算到異構(gòu)計算進行多方面考慮。數(shù)據(jù)中心成本戰(zhàn)略已經(jīng)從虛擬化（提高IT設備利用率）向每瓦特性能轉(zhuǎn)移，其中，對運行負載做特化（specialization）、走向異構(gòu)計算是必然趨勢。首先是集成異構(gòu)多核，英特爾公司的E3級服務器芯片在一個芯片上同時集成了CPU和GPU，兩者通過LLC（last level cache，三級緩存）進行數(shù)據(jù)交互，相比基于PCIe加速器或其他高速互聯(lián)的異構(gòu)架構(gòu)更為高效。第二類是獨立GPGPU，分立GPU卡做計算加速，比如深度學習框架Caffe就有針對GPGPU的優(yōu)化。類似地，英特爾公司的Xeon Phi（應用在超級計算機天河2號上，并且?guī)椭@得世界排名第一的計算加速芯片和板卡）將對Caffe做深度的優(yōu)化。目前來說，GPGPU和Xeon Phi都是插在PCIe插槽上的加速器，它們的加速性能都受到PCIe帶寬的限制。2016年Xeon Phi的新版本Knights Landing可以獨立啟動系統(tǒng)，因此PCIe的限制就不存在了，相對GPGPU方案來說，其可以消除PCIe瓶頸。

另外，F(xiàn)PGA（field－programmable gate array，現(xiàn)場可編程門陣列）加速也是現(xiàn)在廣為采用的一種方法，美國自然科學基金會最近的一個報告6http://insidehpc. com/2014/08/ nsf-studyprobeadvantages-f/指出，對于深度學習（比如卷積神經(jīng)網(wǎng)絡），F(xiàn)PGA比GPGPU更有效。百度公司和微軟公司都明確聲稱在生產(chǎn)集群中利用FPGA加速深度神經(jīng)網(wǎng)絡，傳言谷歌公司也在做類似嘗試。另外，微軟公司的Catapult項目還將FPGA應用于Bing搜索引擎網(wǎng)頁排名的加速，在功耗增加10%的情況下得到了95%的性能提升7http://research. microsoft.com/ pubs/212001/ Catapult_ ISCA_2014.pdf。如果英特爾公司對Altera公司的收購順利完成，這一技術路線將有更多的想象空間。目前來說，F(xiàn)PGA一般用于已訓練模型的分類，還不適合對訓練過程的加速（比如不容易實現(xiàn)對參數(shù)的更新）。

還有一種技術路線是ASIP（application specific instruction processor，專用指令集處理器），最典型的是NPU（neural processing unit，神經(jīng)處理單元）?？傮w來說，NPU分兩大類：人工神經(jīng)網(wǎng)絡的加速器和類腦芯片（neuromorphic architecture）。前者如中國科學院計算技術研究所DianNao芯片系列[23]和已經(jīng)商業(yè)化的Teradeep（來源于Yann LeCun的工作NeuFlow，一種基于數(shù)據(jù)流的卷積神經(jīng)網(wǎng)絡加速器）；對于類腦芯片，常常見諸媒體的有IBM的TrueNorth芯片和高通的Zeroth芯片，兩者都基于更類似于生物神經(jīng)網(wǎng)絡的尖峰神經(jīng)網(wǎng)絡（spike neural network）。TrueNorth展示了在100 mW功耗下模擬復雜的循環(huán)神經(jīng)網(wǎng)絡（recurrent neural network）的能力，體現(xiàn)了這一架構(gòu)的獨特之處（但也有人指出功耗優(yōu)勢來自較低的主頻）。Zeroth的商業(yè)試用并不成功，目前已轉(zhuǎn)向人工神經(jīng)網(wǎng)絡加速器。雖然類腦芯片的商用化還需多年，但它所代表的新型處理范式——計算與記憶的一體化、復雜互聯(lián)、遞歸、時空編碼、異步、低精度、隨機性等特征，有很高的研究價值。目前的努力方向為器件和架構(gòu)兩個方面。美國DARPA的多個項目在架構(gòu)上做出了有益的探索，包括SyNAPSE（IBM的TrueNorth即來源于此）和Cortical Processor（基于hierarchical temporal memory算法）。在器件方面，DARPA UPSIDE基于模擬芯片，另外還有一些工作基于憶阻器（memristor）。

第三，大數(shù)據(jù)跟經(jīng)典高性能計算的區(qū)別在于計算和數(shù)據(jù)的關系。不同于傳統(tǒng)意義上的并行計算，大數(shù)據(jù)以數(shù)據(jù)密集型應用為主，計算依附于數(shù)據(jù)，以至于從效率出發(fā)，數(shù)據(jù)必須全部放在內(nèi)存。由此一個很重要的架構(gòu)上的變化就是讓內(nèi)存跟處理器能夠更加靠近，比如利用eDRAM，使得處理器跟內(nèi)存之間有更大的緩存；或者把內(nèi)存和處理器做2.5D/3D堆疊，獲得更大的帶寬；或者把處理器反過來放到內(nèi)存里面去，即內(nèi)存計算（computing in memory）。多年以前學術界曾經(jīng)嘗試主動式存儲（active storage），把一些特定的計算置入磁盤控制器，從而更靠近數(shù)據(jù)。隨著閃存和3D XPoint這樣的新型非易失內(nèi)存的普及，內(nèi)存計算可能得到更多的應用。

6.2 存儲和互聯(lián)的優(yōu)化

大數(shù)據(jù)存儲體系中，大內(nèi)存加非易失性塊存儲是性能提升的首選架構(gòu)。

首先，大內(nèi)存服務器成為主流。2014年9月，英特爾開發(fā)者峰會展示了2U服務器可以容納1.5 TB內(nèi)存和100 TB硬盤，使高密度部署更上臺階。而同年發(fā)布的Intel E7 v2系列處理器，能夠支持高達32-socket的高端服務器，單服務器最高內(nèi)存容量可達48 TB。這推動了高端大數(shù)據(jù)一體機的發(fā)展。微軟在10月份宣布的Azure G系列虛擬機能夠提供單虛擬機448 GB內(nèi)存。與之對應的內(nèi)存計算需要解決容錯的問題，比如Spark的lineage、傳統(tǒng)的checkpoint、多數(shù)據(jù)冗余、基于日志的容錯機制等。大內(nèi)存時代來臨以后，這些技術成為了在PC級硬件條件下保障大規(guī)模計算的可靠性、大規(guī)模計算的成本控制的必不可少的技術基礎。

大數(shù)據(jù)應用同樣引導永久性塊存儲軟硬件技術路線產(chǎn)生了重大改變。從SSD（solid state drives，固態(tài)硬盤）到PCIe SSD到閃存存儲，這一路的發(fā)展經(jīng)歷了硬件局部變革、軟件進步、軟硬件共同演進的3個階段歷程。

硬件局部變革：SSD是以硬件為主的進步，傳統(tǒng)的硬盤文件系統(tǒng)架構(gòu)基本保留。

軟件進步：PCIe SSD開始觸及塊設備管理和文件系統(tǒng)軟件棧，各種輕量級、多任務優(yōu)化的文件系統(tǒng)軟件棧蓬勃發(fā)展。傳統(tǒng)文件系統(tǒng)針對毫秒級訪問時延優(yōu)化，而閃存將時延縮短到微秒級，并且支持1 000 000/s讀寫操作以上的并發(fā)度，勢必需要新的文件系統(tǒng)設計。

軟硬件共同演進：全閃存存儲開始出現(xiàn)，同時文件系統(tǒng)發(fā)生巨大變革甚至被放棄，許多新型應用系統(tǒng)可以讓應用直接操作閃存里面的數(shù)據(jù)塊，實現(xiàn)相當程度的DRAM和flash的統(tǒng)一尋址，最大化性能提升。未來的NVRAM（nonvolatile random access memory，非易失隨機存取存儲器）[24]，能夠兼具數(shù)據(jù)永久性和數(shù)據(jù)動態(tài)訪問性能，所以數(shù)據(jù)靜態(tài)保存和動態(tài)使用的狀態(tài)徹底統(tǒng)一，文件系統(tǒng)需求降低，序列化和反序列化重要程度下降，整個系統(tǒng)棧會更淺、更簡單，性能更優(yōu)異。在這些NVRAM中，英特爾公司的3D XPoint最受矚目，其性能和耐用性都將達到目前NAND閃存的1 000倍，接近于DRAM，這將進一步模糊內(nèi)存和存儲的界限。該技術預期2016年上市，可以用在幾乎所有存儲用途——主內(nèi)存、緩存或塊存儲。如果該技術性價比按照摩爾定律降低，勢必引導大數(shù)據(jù)服務器設計發(fā)生重大變革。

大數(shù)據(jù)中常見的聚合（aggregation）、置換（shuffle）等操作對互聯(lián)帶寬和通信時延提出了很高的要求。物理層面，如今節(jié)點和節(jié)點之間的網(wǎng)絡帶寬已經(jīng)達到40 Gbit/s，未來基于全光交換結(jié)構(gòu)的設計能達到數(shù)百Gbit/s甚至Tbit/s，比如英特爾公司的硅光（silicon photonics）技術。分立的高性能NIC將逐漸消失，處理器（板）與其他節(jié)點處理器（板）的內(nèi)存直接通信。軟硬件界面上，為了發(fā)揮內(nèi)存計算的效用，需要更便宜、更高擴展性的RDMA互聯(lián)解決方案。純軟件部分，一些新的網(wǎng)絡協(xié)議被應用于數(shù)據(jù)中心，比如data center TCP（DCTCP）針對Fork-Join結(jié)果的網(wǎng)絡流量進行了優(yōu)化。另外，Spark采用了類似BitTorrent的協(xié)議來減少shuffle產(chǎn)生的節(jié)點間網(wǎng)絡流量。

6.3 軟硬件協(xié)同優(yōu)化

隨著硬件的巨大進步，軟件架構(gòu)逐漸成為瓶頸，軟硬件架構(gòu)協(xié)同的優(yōu)化成為必然。數(shù)據(jù)中心出現(xiàn)了重新垂直化（reverticalization）的趨勢。各家大廠都針對硬件特點優(yōu)化軟件棧，而做法各有不同。

（1）把硬件特性暴露給軟件棧

相比于過去逐步抽象隔離的多層次架構(gòu)設計，新發(fā)展方向強調(diào)核心信息上下溝通，這體現(xiàn)了螺旋上升的技術發(fā)展模式。一個值得注意的趨勢是一些互聯(lián)網(wǎng)和大數(shù)據(jù)巨頭都建立了自有編譯器團隊，甚至是自有Java虛擬機團隊。流行的Hadoop、Spark等開源分布式系統(tǒng)都運行在Java虛擬機上面。經(jīng)典的Java虛擬機具有對軟件隔離硬件細節(jié)的特性，實現(xiàn)了軟件架構(gòu)的平臺無關的巨大優(yōu)勢，但同時這個特性也大大削弱了軟件針對硬件優(yōu)化的潛力。當大數(shù)據(jù)從以推廣為主過渡到以性能應用為主的階段后，就需要通過一種方式來打破這個界限。比如英特爾公司嘗試的NativeTask[25]，把MapReduce中間結(jié)果的重排過程從Java代碼轉(zhuǎn)移到原生代碼，并且針對系統(tǒng)緩存架構(gòu)進行優(yōu)化，MapReduce的總體系統(tǒng)效能提升了30%～50%。Spark最近創(chuàng)造了Terasort的世界紀錄，其中網(wǎng)絡通信也通過Netty利用了原生代碼優(yōu)化庫?，F(xiàn)在很多基于Java的大數(shù)據(jù)計算系統(tǒng)，都選擇利用底層特殊優(yōu)化的線性代數(shù)原生庫來提升性能。

即使不采用原生代碼，仍需要對軟件進行內(nèi)存訪問模式的優(yōu)化，盡量使隨機訪問發(fā)生在CPU緩存，內(nèi)存訪問量盡可能降低，而對塊設備的操作基本是順序讀寫。另外，Java虛擬機帶來的另一個開銷是內(nèi)存管理，在大內(nèi)存模式下垃圾回收器（garbage collector）效率降低，管理開銷可能占總體運行時間的10%以上，應對方案除了虛擬機采用針對大內(nèi)存高度優(yōu)化的并行、并發(fā)回收算法，還出現(xiàn)了硬件加速的垃圾回收8http://link. springer.com/ar ticle/10.1007% 2Fs11227-010-0493-0。另外，應用本身也必須采用如Tachyon這樣的并發(fā)存儲管理的內(nèi)存文件系統(tǒng)，多個應用自主把共享的數(shù)據(jù)放入Tachyon，從而有效減少單個應用內(nèi)存的堆需求，降低管理開銷。

最新的例子是Spark從2014年開始的Tungsten項目9https:// databricks.com/ blog/2015/04/28/ projecttungstenbringing-sparkcloser-to-baremetal.html。Databricks公司在項目中為性能目標引入3項重大改進：自主內(nèi)存管理，以降低Java對象管理和垃圾回收機制的開銷；CPU Cache-aware Computation，從數(shù)據(jù)結(jié)構(gòu)和算法上針對處理器緩存作優(yōu)化；直接代碼生成，更好地利用現(xiàn)代編譯器的硬件優(yōu)化功能。

（2）重新設計軟件棧

如前文所述的全閃存存儲和NVRAM，或者從更高角度，以硬盤為代表的塊設備也正在IP化、對象存儲化，傳統(tǒng)的塊設備軟件棧正在重新設計。

（3）多服務器范圍或者機架范圍的一體機設計

現(xiàn)在服務器商業(yè)模式不再是簡單地銷售服務器硬件或者單純銷售軟件，而是把軟件、硬件打包成一體機，推出一個以應用為導向的整體解決方案。最有名的一體機就是SAP的HANA。一體機方案是從某個具體應用出發(fā)，以機架為單位，對服務器單機配置、塊設備、網(wǎng)絡互聯(lián)、單機操作系統(tǒng)、分布式管理系統(tǒng)、分布式應用等進行大深度和大廣度的優(yōu)化定制。比如HANA的B+樹是針對高速緩存優(yōu)化的，單機上它能用SSE對數(shù)據(jù)進行流式、在線的壓縮和解壓縮，多機上能夠高效地執(zhí)行任務分配和結(jié)果匯總。IBM的Netezza一體機則從高性能在線數(shù)據(jù)分析出發(fā)，采用了基于FPGA的軟硬件協(xié)同設計。

（4）從傳統(tǒng)數(shù)據(jù)中心大數(shù)據(jù)機群建設轉(zhuǎn)向私有云/公有云為基礎的大數(shù)據(jù)服務

這代表一種行業(yè)發(fā)展方向。以Hadoop基礎架構(gòu)為例，在早期各個公司普遍致力于建設自有數(shù)據(jù)中心內(nèi)的大規(guī)模Hadoop機群，這里面有早期Hadoop套件對多租戶支持差的原因。隨著云平臺商業(yè)模式的發(fā)展和Hadoop套件的進化，各種以“Hadoop as Servive”為主打賣點的云端大數(shù)據(jù)基礎設施服務成為行業(yè)新熱點，極大地降低了新興公司利用大數(shù)據(jù)技術的門檻。而后來者主推Spark的Databricks公司從一開始就認識到云服務模式，Databricks Cloud是該公司的主要運作模式之一。

大數(shù)據(jù)云化發(fā)展中，除了商業(yè)模式創(chuàng)新，還包括大數(shù)據(jù)平臺技術和云端虛擬平臺技術的深度整合。因為從一般意義上來說，大數(shù)據(jù)平臺如Hadoop、HDFS和虛擬技術是性能不兼容的，其中涉及虛擬化本地數(shù)據(jù)I/O接口的效率問題。各家公司都為此做出了不懈努力，如VMWare公司開發(fā)了Hadoop virtual extensions10http://www. vmware.com/ files/pdf/ techpaper/ Virtualized-Hadoop-Performancewith-VMwarevSphere6.pdf技術，專門解決Hadoop軟件棧的效率；Hadoop和Spark社區(qū)都和Docker社區(qū)緊密合作，提高協(xié)同效率。

第二個大方向是硬件可重構(gòu)。最初的硬件可重構(gòu)是從塊存儲設備開始逐步發(fā)展的。傳統(tǒng)硬盤機柜只能在SAN、NAS、DAS 3種模式靜態(tài)選擇一種固定配置，由于傳統(tǒng)高性能計算和大數(shù)據(jù)計算本質(zhì)不同，兩種平臺不能運行時共享單一硬件。SeaMicro開發(fā)的freedom fabric storage技術允許動態(tài)劃分硬盤組，從而解決這個問題，極大地提高了硬件利用率。

工業(yè)界繼續(xù)推廣數(shù)據(jù)中心硬件重構(gòu)的概念。英特爾公司推出了Rack Scale Architecture，鼓勵機群設計人員把眼光從服務器單機放寬到全機架，從3個突破口出發(fā)，根據(jù)應用對硬件進行橫向整合。第一個突破口是按類別構(gòu)建資源池。傳統(tǒng)服務器設計單機內(nèi)部集成計算、內(nèi)存、存儲和網(wǎng)絡各個模塊。重構(gòu)以后單機只保留最基礎的啟動系統(tǒng)的硬件，盡可能把大內(nèi)存、大容量塊設備、大型加速器等單獨組成模塊，并且為機架內(nèi)所有服務器所用。第二個突破口是提升高速互聯(lián)的速度和層級，互聯(lián)帶寬從萬兆提高到100 Gbit/s以上，并且革新協(xié)議棧，使RDMA成為標準配置。從單機互聯(lián)，發(fā)展到各個資源模塊通過新型技術直接互聯(lián)。第三個突破口是用軟件對資源池動態(tài)劃分、動態(tài)掛載到各個應用的虛擬服務器，從而實現(xiàn)大數(shù)據(jù)應用的核心需求，在機架尺度上針對應用負載進行動態(tài)優(yōu)化。

在當下的大數(shù)據(jù)應用中，軟硬件協(xié)同優(yōu)化的最成功、最普及的范例是基于神經(jīng)網(wǎng)絡的深度學習系統(tǒng)。各個業(yè)內(nèi)著名互聯(lián)網(wǎng)公司紛紛構(gòu)建了大規(guī)模的機群，專用于針對視覺和語音的深度學習。而后在系統(tǒng)運營過程中紛紛進行軟硬件協(xié)同優(yōu)化提升學習系統(tǒng)的效率。英特爾公司資助參與了GraphLab和Petuum的開源系統(tǒng)。

7 前沿方向五：多、快、好、省

“多、快、好、省”就是在實現(xiàn)數(shù)據(jù)量（多）和計算性能（快）的前提下，易于編程和管理（好），追求資本和運維成本最低（省）。

7.1 垂直化優(yōu)化

實現(xiàn)“多、快、好、省”的方式，首先是垂直打通技術棧、做跨層次的優(yōu)化。第6節(jié)舉例說明了基于閃存塊設備的軟硬件協(xié)同設計，這里以內(nèi)存計算為例描述一個新方向。它不是對技術棧的單獨某一層技術進行改造或者革新，而是從下到上的“大手術”。

在硬件平臺層，主張配置大容量內(nèi)存（DRAM），搭配大容量SSD甚至全閃存，未來采用3D XPoint內(nèi)存，將大容量非易失存儲器的內(nèi)存直接可尋址化，板級之間用RDMA互聯(lián)，支持NVM express over fabrics。

在系統(tǒng)軟件的數(shù)據(jù)管理和存儲層，主流方案是內(nèi)存數(shù)據(jù)庫、內(nèi)存文件系統(tǒng)和具有內(nèi)存緩存的分布式文件系統(tǒng)（如Tachyon、HDFS），特點是優(yōu)化的內(nèi)存緩存、基于堆外大內(nèi)存的Java虛擬機優(yōu)化、基于內(nèi)存文件系統(tǒng)的進程間文件數(shù)據(jù)交換。

在系統(tǒng)軟件的計算框架層面，強調(diào)應用全新的分布式內(nèi)存計算平臺。所謂的內(nèi)存計算，術語是in memory computing，初始主要指那些優(yōu)化數(shù)據(jù)存儲方式，在內(nèi)存（DRAM）中完成數(shù)據(jù)存儲、檢索、分析的數(shù)據(jù)庫技術，最新的發(fā)展方向被稱為內(nèi)存中的數(shù)據(jù)網(wǎng)格（in memory data grid）技術。Spark進一步發(fā)展了這個概念，除了在內(nèi)存中完成SQL/HQL計算以外，Spark能夠綜合利用分布式機群的所有內(nèi)存來完成復雜機器學習計算。

在應用層面，尤其是數(shù)據(jù)可視化層面，重新設計數(shù)據(jù)結(jié)構(gòu)、注重數(shù)據(jù)模型創(chuàng)新，是實現(xiàn)“多、快、好、省”的主要措施。在數(shù)據(jù)實時查詢和可視化領域，一個代表性的例子是NanoCube。通過獨創(chuàng)的基于樹的數(shù)據(jù)存儲和查詢算法，對于上百萬甚至上億的數(shù)據(jù)集，NanoCube可以在普通筆記本電腦的內(nèi)存中完成索引，空間利用率很高。在數(shù)據(jù)分析領域，一個鮮明的例子是圖計算框架GraphChi。GraphChi的目標是在單機上實現(xiàn)大數(shù)據(jù)計算，其技術基礎為：新的分層的圖計算架構(gòu)，支持流式圖計算；支持實時更新的圖計算。

7.2 降低空間和時間的復雜度

7.2.1 降低空間復雜度

降低空間復雜度最直觀的做法就是把大數(shù)據(jù)變小。變小的方式有很多，具體如下。

（1）對數(shù)據(jù)壓縮幾乎已經(jīng)是所有大數(shù)據(jù)架構(gòu)的標配，除了Hadoop采用的幾種壓縮算法，2013年初谷歌公司開源了Zopfli，在最大壓縮率下的數(shù)據(jù)比zlib小3%～8%。壓縮率與消耗的CPU時間相關，Zopfli消耗的CPU時間比zlib大2～3個數(shù)量級，所以更適合變化性較小的數(shù)據(jù)（壓縮一次即可）。多數(shù)系統(tǒng)的壓縮解壓縮發(fā)生在內(nèi)存和I/O之間，也就是說內(nèi)存里已經(jīng)是解壓的數(shù)據(jù)。也有少數(shù)系統(tǒng)，如IBM的Netezza，數(shù)據(jù)在內(nèi)存中仍保持壓縮狀態(tài)，F(xiàn)PGA配合CPU實時地邊解壓邊處理，進一步提升了內(nèi)存空間效率。

（2）列式存儲，例如Apache Parquet，能夠使壓縮率獲得數(shù)量級的提升，而它本身也是舍大得小的辦法，因為往往查詢并不需要訪問所有列，所以數(shù)據(jù)加載時無須讀入不相干的列。當然，好的SQL優(yōu)化器也對行存儲進行修剪。

（3）多維度存儲的緩存機制，找出最重要的大數(shù)據(jù)并放在內(nèi)存和閃存里面，以加速計算主體。

（4）采用稀疏的結(jié)構(gòu)，比如在進行商品推薦應用時，用戶和購買商品的映射矩陣是核心數(shù)據(jù)結(jié)構(gòu)，通過采用各種稀疏存儲結(jié)構(gòu)就能夠把映射矩陣的空間復雜度下降。

（5）在大數(shù)據(jù)規(guī)模下，處理所產(chǎn)生的中間數(shù)據(jù)是比較困難的問題。比如MapReduce和Spark在shuffle操作中如果粒度不當，可能產(chǎn)生大量的中間數(shù)據(jù)。除了采用合適的粒度外，Spark采取了一種新的shuffle機制，從基于散列的分桶變成了基于sort的分桶，極大地提高了內(nèi)存使用效率。無論是Terasort創(chuàng)造世界紀錄，還是在實際應用場景，如大規(guī)模的廣告分析邏輯回歸（logistics regression），Spark的新機制都扮演了重要角色。

7.2.2 降低時間復雜度

另外一方面是時間復雜度的降低。

（1）嘗試“簡單”、高可變（high variance）的模型。這些模型雖然計算上較為簡單，但特征較為復雜，在小數(shù)據(jù)場景下，往往會過擬合。但更多的數(shù)據(jù)解決了這一問題，使得模型的功效急劇增長。比如谷歌公司Peter Norvig的文章[26]指出，數(shù)據(jù)賦予了簡單模型不可名狀的魔力，以Web文本處理為例，n-gram相當簡單，但這類模型具有較大的特征空間（詞匯表里每一個單詞作為一個特征），經(jīng)過大量的數(shù)據(jù)訓練，機器翻譯有了一個質(zhì)的提升。同時，相比較而言，簡單模型的計算復雜度較低，計算效率提升很顯著。

（2）使用簡單模型的組合。模型組合（ensemble）是一個機器學習的專業(yè)領域。例如，Netflix曾經(jīng)通過競賽，百萬美元獎勵推薦有效性提升10%的創(chuàng)新。很多團隊參加這個競賽，但是沒有單個團隊能達到10%；后來若干個團隊之間進行模型的組合，一舉超越10%。在美國版開心辭典Jeopardy上打敗人類冠軍的IBM Watson系統(tǒng)，采用了一百多種模型的組合。當數(shù)據(jù)增大時，ensemble公司往往也能獲得更好的邊際效益。值得一提的是模型組合要考慮計算復雜性問題，Netflix公司就是因為獲獎者組合模型計算量太大而放棄了它的實際應用。但一般而言，假設每種模型是O(N2)復雜度，當N非常大時，多個模型的組合遠遠比一個O(N3)的復雜模型更高效。

（3）采樣和近似。采樣是統(tǒng)計工具中重要的數(shù)據(jù)處理方法，在大數(shù)據(jù)里面它被賦予更多含義。大數(shù)據(jù)處理中，因為數(shù)據(jù)體量的問題，查詢處理基本只能以批處理方式進行，實時響應在理論上是不可能的。工業(yè)界大膽引入采樣技術以應對實時要求，依靠精心設計的針對具體應用場景優(yōu)化的原始數(shù)據(jù)采樣算法，可以實現(xiàn)TB級別數(shù)據(jù)規(guī)模下秒級時延的不精確結(jié)果的查詢響應，比如BlinkDB。近似則用在另外一個領域。如果能夠確保應用對輸入精度不敏感，就可以在數(shù)據(jù)處理中有意識地放寬條件、引入誤差，從而通過降低復雜度或提升并行性來大幅度降低處理時間。經(jīng)典的廣告應用場景有Bloom filter、CountMinSketch算法等。

（4）降維和混合建模。考慮到在多數(shù)應用中大數(shù)據(jù)有兩個特點經(jīng)常同時出現(xiàn)：高緯度和稀疏數(shù)據(jù)點，所以如果能共同應用各種稀疏數(shù)據(jù)結(jié)構(gòu)的優(yōu)化，必將能夠極大地提升計算效率。

所有這些方法都能降低機器學習的復雜度，需要從應用出發(fā)靈活運用。

7.3 分布式和并行化

大數(shù)據(jù)中分布式優(yōu)化的經(jīng)典案例是從ACID到BASE（basically available, soft state,eventually consistent）11http://queue. acm.org/detail. cfm?id=1394128的變化。ACID是傳統(tǒng)關系數(shù)據(jù)庫事務特性的必然條件，但是其代價高昂，成為數(shù)據(jù)庫規(guī)模和性能雙提升的致命瓶頸。BASE只選中其最終一致性，結(jié)果NoSQL數(shù)據(jù)庫的規(guī)模和性能實現(xiàn)雙贏，后者實現(xiàn)了并行的可能。

對于迭代計算，計算數(shù)學上有許多例子，經(jīng)典的是線性方程求解的兩種常用近似方法，雅可比（Jacobi）迭代法和高斯—賽德爾（Gauss-Seidel）迭代法。對于Jacobi方法，當前迭代必須基于上一迭代的結(jié)果數(shù)據(jù)，這就給分布式優(yōu)化帶來巨大困難，因為每個迭代的結(jié)果數(shù)據(jù)分布在許多節(jié)點上，細粒度的計算同步和數(shù)據(jù)同步抵消了分布式優(yōu)化的收益。對于Gauss-Seidel方法，當前迭代可以不依賴最新數(shù)據(jù)，結(jié)果同樣收斂，只是理論上的收斂速度會下降，但是輔以分布式優(yōu)化，整體的計算時間反而大大節(jié)省。因此，很多新開發(fā)的機器學習算法能夠容忍模糊性，能夠基于本地節(jié)點上過時的數(shù)據(jù)（不一定是其他節(jié)點發(fā)送過來的最新數(shù)據(jù)）進行計算，打破迭代之間數(shù)據(jù)的依賴。這樣使所有節(jié)點能夠盡可能快地并行計算，但同時算法依然能夠收斂。深度學習領域在這個方面迅猛發(fā)展，谷歌公司采用了參數(shù)服務器（parameter server）的方式，CMU既有參數(shù)服務器，也有更通用的SSP（stale synchronous parallel）[27]。CMU的Petuum進一步發(fā)展了SSP的思想，針對超大模型的機器學習實現(xiàn)數(shù)據(jù)并行、模型并行和調(diào)度層面的任務并行。

并行化是分布式的必須手段。分布式機器學習依賴于一種并行方法或者幾種并行方法的組合。首先是數(shù)據(jù)并行，然后是圖并行或者模型并行。模型并行需要基于模型或圖結(jié)構(gòu)進行數(shù)據(jù)劃分、任務調(diào)度，使用比較廣泛的是GraphLab，較為新穎的是Petuum。

總體來說，并行化和分布式的核心訴求就是減少通信、減少同步、提高效率。從分布式系統(tǒng)實踐出發(fā)，一定會碰到許多問題，諸如緩存問題、一致性問題、本地化問題、劃分問題、調(diào)度問題、同步粒度問題等。這些問題有多種解決方式，需要針對具體問題實際考慮。比如同步問題就有BSP全同步、GraphLab異步或者SSP的半同步等多種選擇；狀態(tài)更新可以批量進行，也可以個別進行；數(shù)據(jù)通信可以單次傳輸全部數(shù)據(jù)，也可以只傳輸改變的數(shù)據(jù)。

總結(jié)起來，“多、快、好、省”有賴于軟硬件的協(xié)同優(yōu)化、時空復雜度的降低以及分布化和并行化。

8 前沿方向六：天下三分

在傳統(tǒng)計算時代，系統(tǒng)研究者常常希望能夠設計出一套軟硬件架構(gòu)覆蓋盡可能多的問題領域。2000年后，Michael Stonebraker提出要針對不同的計算需求提供不同的計算引擎，效果會更好（database is not a one-size-fits-all category），他因為在這一方向上的長期實踐獲得了2015年的圖靈獎，由此出現(xiàn)了數(shù)據(jù)和計算的分野。

（1）數(shù)據(jù)類型

大數(shù)據(jù)時代的主流特征是提升優(yōu)化了很多原來傳統(tǒng)高性能計算不太關注的數(shù)據(jù)類型。首先，最被關注的數(shù)據(jù)結(jié)構(gòu)是表格——鍵值對（key-value）。基于關系型數(shù)據(jù)庫的表格是結(jié)構(gòu)化數(shù)據(jù)，利于并行。各種長度未知的相關性未知的鍵值對序列，就欠缺結(jié)構(gòu)化。大數(shù)據(jù)NoSQL數(shù)據(jù)庫專門優(yōu)化鍵值對查詢。其次，圖結(jié)構(gòu)也被重視，比如圖計算，大數(shù)據(jù)大大提升了圖計算的重要性，把它提升到一種編程語言、分布式處理框架的高度來解決問題。再如矩陣和數(shù)組，大數(shù)據(jù)大大拓展了對不規(guī)則矩陣和不規(guī)則多緯數(shù)組的支持，比如SciDB。

（2）計算范式

大數(shù)據(jù)的興起是源于計算范式的突破。

首先是MapReduce編程模型的創(chuàng)新、推廣和改進。MR是一種批處理計算，主要出發(fā)點有：數(shù)據(jù)規(guī)模太大，把計算任務發(fā)送到數(shù)據(jù)節(jié)點；簡化任務間通信模型，去掉底層顯示的同步編程，用抽象的數(shù)學范式來重構(gòu)整個并行計算，降低學習門檻，簡化分布式支撐平臺設計。

其次是以圖結(jié)構(gòu)為基礎的計算范式。

（3）編程模型

大數(shù)據(jù)平臺的成熟激發(fā)了大數(shù)據(jù)編程模型的繁榮，目前主流的編程模型有：數(shù)據(jù)并行、流式計算的任務并行、圖并行。

尤其值得一提的是，大數(shù)據(jù)為圖計算帶來的機會是圖并行，因為圖結(jié)構(gòu)的稀疏性，多數(shù)頂點只有較小的鄰域，這樣，在一個迭代中整個圖可以劃分為很多并行處理的鄰域。圖并行中的計算依賴必須有一致性保證，如GraphLab的可變一致性模型。

目前的最新發(fā)展方向又要求在圖結(jié)構(gòu)上支持關系操作，比如加入一張表，Spark的GraphX最早實現(xiàn)了這一能力，接著一些圖計算編程模型（如GraphLab）也加入了這種特性。還有一種概率編程模型12http:// probabilisticprogramming. org/wiki/Home，適用于一些基于概率圖的機器學習，它的未來趨勢有待觀察。

大數(shù)據(jù)領域的另外一個特殊領域是reactive programming或事件驅(qū)動編程模型，主要面向?qū)Υ笠?guī)模并發(fā)事件有實時響應要求的場景，比如海量廣告點擊、海量金融交易等。一個非常流行的范式叫reactive范式。最早在Erlang里，叫actor模式。如今在Scala Akka語言里面優(yōu)化了異步處理邏輯，有更好的可擴展性?；谶@一模型，英特爾中國開發(fā)了一個新的開源項目GearPump，目前獲得廣泛好評13http:// downloads. typesafe. com/website/ presentations/ GearPump_Final. pdf。

總體而言，針對應用特性選擇特殊定制方案是當前大數(shù)據(jù)實現(xiàn)3V的主要思路。

9 前沿方向七：分久必合

大數(shù)據(jù)爆發(fā)以來，各種新編程語言編程方式層出不窮、百家爭鳴。經(jīng)過一段時間積淀，各種編程語言之間發(fā)生了融合。

Big Dawg14http://istcbigdata.org/ index.php/ building-a-newapplicationto-hardwaremanagementstack-for-bigdata/是英特爾公司在MIT最近支持的研究工作，Stonebraker也參與了這一工作。Big Dawg提出了普適的編程模型，一種叫做BQL的語言，它支持關系和線性代數(shù)、復雜數(shù)據(jù)模型、迭代計算、并行計算。這種語言能夠把計算映射到底層的不同計算和存儲引擎。

Twitter Summingbird是在編程接口層面融合，同時支持批量（MapReduce,Spark）和流式（Storm）的計算。

Lambda架構(gòu)則是在應用框架層面的融合，嘗試用一個編程框架把實時流計算和批量計算統(tǒng)一，以高效率的批處理為基礎，輔以流處理實現(xiàn)增量計算，綜合起來幾乎形成一個完美的大數(shù)據(jù)框架15http://lam bdaarchitecture. net/。Nathan Marz聲稱這一模型可以突破CAP理論的限制。

Spark則是在實現(xiàn)框架層面的融合，如圖1所示。

微軟的REEF則是通過資源管理層（如YARN）來實現(xiàn)多計算模型的融合。YARN在大數(shù)據(jù)不同計算范型的融合上起到了至關重要的作用。

Databricks公司以Spark為核心，雄心勃勃地開發(fā)BDAS軟件棧，目的是實現(xiàn)一個多層面、多模型融合的面向多種應用的統(tǒng)一大數(shù)據(jù)處理平臺?；A性的底層構(gòu)件是HDFS，它負責永久性存儲，在HDFS之上搭建Tachyon內(nèi)存文件系統(tǒng)，以提升訪問效率。在計算框架上，以Spark內(nèi)存計算框架為核心，重大改進是引入Velox的模型管理，這可以看作數(shù)據(jù)并行和模型并行的一種嘗試。框架之上，就是各種計算范式的支持模塊，比如流計算有Spark streaming的流計算、關系數(shù)據(jù)庫，NonSQL應用有SparkSQL，圖計算有GraphX，機器學習有MLlib等。

圖1 Spark架構(gòu)

除了Databricks，Cloudera也不甘人后，Hadoop創(chuàng)始人Doug Cutting在以“The One Platform Initiative”為副標題的網(wǎng)絡演講中提出引入Spark作為Hadoop下一個通用處理框架，以補充MapReduce。更宏觀地講，就是促使BDAS和Hadoop的融合。

傳統(tǒng)的大規(guī)模并行編程（MPP）和Hadoop/MapReduce各有擅長，現(xiàn)在也在融合。早期的混合架構(gòu)，用MPP處理大規(guī)模的結(jié)構(gòu)化數(shù)據(jù)，用Hadoop/MR處理海量的半結(jié)構(gòu)化、非結(jié)構(gòu)化數(shù)據(jù)。最新的趨勢是兩者開始融合，高性能計算/超算跟大數(shù)據(jù)開始朝向統(tǒng)一平臺發(fā)展，出現(xiàn)了高性能數(shù)據(jù)分析（high performance data analysis）和數(shù)據(jù)密集型計算（data intensive supercomputing）等新的子領域。英特爾公司已經(jīng)開始推動“one single system for HPC and big data”。

在基礎設施層面，hyper-converged infrastructure更是勢不可擋。

天下三分之后，分久必合。這個合與分并不矛盾，基于負載特性在應用層劃分，再在總體架構(gòu)層面汲取共性、打通彼此來“合”，是符合事物的發(fā)展規(guī)律的。

[21] Holzle U. Brawny cores still beat wimpy cores, most of the time. IEEE Micro, 2010, 30(4)

[22] Hamilton J. Cooperative expendable micro-slice servers (CEMS): low cost, low power servers for Internet scale services. http://mvdirona.com/jrh/ TalksAndPapers/JamesHamilton_CEMS.pdf, 2009

[23] Chen T S, Du Z D, Sun N H,et al. Diannao: a small-footprint highthroughput accelerator for ubiquitous machine-learning. ACM Sigplan Notices, 2014, 49(4): 269～284

[24] Mittal S, Vetter J S, Li D J. A survey of architectural approaches for managing embedded DRAM and non-volatile onchip caches. IEEE Transactions on Parallel and Distributed Systems, 2014, 26(6): 1524～1537

[25] Dong Y, Yin X S, Lian C,et al. Unleash the architecture power to accelerate big data processing. Journal of Computer Science and Technology, 2014

[26] Halevy A, Norvig P, Pereira F. The unreasonable effectiveness of data. IEEE Intelligent Systems, 2009, 24(2): 8～12

[27] Ho Q R, Cipar J, Cui H,et al. More effective distributed ml via a stale synchronous parallel parameter server. Advances in Neural Information Processing Systems, 2013: 1223～1231 □

10.11959/j.issn.2096-0271.2015034