潘鋒烽 熊 勁

(計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室(中國(guó)科學(xué)院計(jì)算技術(shù)研究所) 北京 100190)(中國(guó)科學(xué)院大學(xué) 北京 100049)(panfengfeng@ict.ac.cn)

非易失性?xún)?nèi)存(non-volatile memory, NVM)的出現(xiàn)為解決磁盤(pán)性能瓶頸問(wèn)題提供了新的機(jī)會(huì)，本文中的NVM指的是基于內(nèi)存總線(xiàn)接口、字節(jié)尋址的非易失內(nèi)存.在內(nèi)存計(jì)算的場(chǎng)景下，非易失性?xún)?nèi)存有著非常廣泛的應(yīng)用場(chǎng)景.與磁盤(pán)和DRAM相比，NVM的主要優(yōu)勢(shì)有：1)NVM有著與DRAM相接近的讀寫(xiě)延遲和吞吐率，有望用來(lái)消除磁盤(pán)IO開(kāi)銷(xiāo)，提升系統(tǒng)的IO性能；2)NVM的存儲(chǔ)密度比DRAM更大，與NAND Flash SSD相似，它能存放更多的數(shù)據(jù)；3)相比于內(nèi)存，NVM具備非易失、可持久化的優(yōu)勢(shì).隨著工業(yè)界大力發(fā)展非易失內(nèi)存，其進(jìn)展相當(dāng)迅速，2013年Micro公司推出了搭載Flash與DRAM的Hybrid DIMM[1].2014年，AgigA Tech公司推出了DDR接口的 NVDIMM[2-4].Intel與Micro聯(lián)合推出的DDR接口的3D XPoint[5]產(chǎn)品預(yù)計(jì)2018年面市，3D XPoint閃存速度堪比內(nèi)存，因此解決磁盤(pán)性能問(wèn)題的一個(gè)較為直接的方式是替換存儲(chǔ)介質(zhì)，將傳統(tǒng)的磁盤(pán)替換成NVM，這樣使得內(nèi)存計(jì)算中的數(shù)據(jù)讀寫(xiě)能夠獲得NVM的性能，與此同時(shí)也保證了數(shù)據(jù)的持久化.

眾所周知，Shuffle的性能是決定大數(shù)據(jù)處理性能的關(guān)鍵因素之一[6-9].由于傳統(tǒng)Shuffle階段的數(shù)據(jù)一般是通過(guò)磁盤(pán)文件系統(tǒng)進(jìn)行持久化，所以影響Shuffle性能的一個(gè)重要因素是IO開(kāi)銷(xiāo)[7,10-11]，NVM有助于解決內(nèi)存計(jì)算在Shuffle階段由于持久化所帶來(lái)的IO開(kāi)銷(xiāo).因此本文將NVM引入到Shuffle階段中，但是由于NVM的性能接近DRAM，有研究工作表明，對(duì)于NVM現(xiàn)有的系統(tǒng)軟件(NVM文件系統(tǒng))開(kāi)銷(xiāo)過(guò)高，不能充分發(fā)揮NVM的性能[12-15].表1展示了在壓縮[16]過(guò)程中文件系統(tǒng)各個(gè)部分的開(kāi)銷(xiāo)比例[17].

從表1可以看出，大約60.5%的時(shí)間花費(fèi)在了文件系統(tǒng)上，其中關(guān)于元數(shù)據(jù)的開(kāi)銷(xiāo)依然占據(jù)著較大的比例.上述結(jié)果表明，即使使用最新的NVM文件系統(tǒng)，其開(kāi)銷(xiāo)也是非常大的.如何高效使用NVM來(lái)提升Shuffle階段的IO性能是當(dāng)前內(nèi)存計(jì)算使用NVM所面臨的一個(gè)重要問(wèn)題與挑戰(zhàn).

Table 1 Percentage of Time Spent in File System表1 文件系統(tǒng)中各個(gè)部分的開(kāi)銷(xiāo)比例[17]

在本文中，我們提出了一種基于NVM的Shuffle優(yōu)化策略——NV-Shuffle.為了最大化發(fā)揮NVM的性能優(yōu)勢(shì)，NV-Shuffle摒棄了以文件系統(tǒng)進(jìn)行Shuffle數(shù)據(jù)存取的方式，而是采用持久化內(nèi)存的方式，直接在用戶(hù)態(tài)訪(fǎng)問(wèn)持久化內(nèi)存，避免了傳統(tǒng)存儲(chǔ)系統(tǒng)中的冗長(zhǎng)的IO路徑，例如文件系統(tǒng)、設(shè)備驅(qū)動(dòng)等.

本文的主要貢獻(xiàn)如下：

1) 利用pVM構(gòu)建Java的持久化內(nèi)存訪(fǎng)問(wèn)接口——NV-Shuffle接口，使大數(shù)據(jù)平臺(tái)能夠直接使用與訪(fǎng)問(wèn)NVM；

2) 針對(duì)NVM提出了一種Shuffle數(shù)據(jù)的組織方式——基于Hash的私有持久化緩沖區(qū)，從而能夠高效處理并發(fā)、故障、網(wǎng)絡(luò)傳輸?shù)确矫娴膯?wèn)題；

3) 針對(duì)傳統(tǒng)Shuffle階段預(yù)先創(chuàng)建文件的問(wèn)題，提出一種符合NVM空間自身的分配策略——延遲分配，從而能夠提升NVM的空間利用率；

4) 對(duì)于Shuffle數(shù)據(jù)的讀取與恢復(fù)，通過(guò)使用映射表方式來(lái)管理，使其能夠快速定位、讀取數(shù)據(jù)以及在出現(xiàn)失效之后進(jìn)行快速的數(shù)據(jù)恢復(fù).

1 相關(guān)工作

本節(jié)主要分為2個(gè)部分：傳統(tǒng)計(jì)算框架關(guān)于Shuffle的優(yōu)化以及NVM的相關(guān)工作.

1.1 Shuffle優(yōu)化

傳統(tǒng)大數(shù)據(jù)處理平臺(tái)中的Shuffle階段都是使用單一類(lèi)型的存儲(chǔ)設(shè)備(Disk或者SSD)，以文件系統(tǒng)的方式進(jìn)行數(shù)據(jù)的存取，并沒(méi)有涉及到異構(gòu)存儲(chǔ)的使用.因此關(guān)于該部分的優(yōu)化主要圍繞的是在使用磁盤(pán)的場(chǎng)景下，如何減少磁盤(pán)的IO開(kāi)銷(xiāo)，主要涉及2個(gè)問(wèn)題：

1) 數(shù)據(jù)重復(fù)讀寫(xiě)引起的磁盤(pán)IO開(kāi)銷(xiāo)；

2) 數(shù)據(jù)拉取過(guò)程中隨機(jī)、小粒度的IO模式引起的磁盤(pán)IO開(kāi)銷(xiāo).

根據(jù)不同的優(yōu)化方法，分為內(nèi)存加速、磁盤(pán)IO聚合和高速網(wǎng)絡(luò)加速.

1.1.1 內(nèi)存加速

在Shuffle階段，都會(huì)存在數(shù)據(jù)重復(fù)讀寫(xiě)的問(wèn)題，由于節(jié)點(diǎn)分配給每個(gè)Task的內(nèi)存是有限的，使得數(shù)據(jù)多次從磁盤(pán)中讀取出來(lái)之后寫(xiě)回，例如Map端可能會(huì)使數(shù)據(jù)重復(fù)2次讀寫(xiě)，Reduce端則可能會(huì)更多，這無(wú)疑引起較多的磁盤(pán)IO開(kāi)銷(xiāo)，影響作業(yè)的執(zhí)行效率.針對(duì)該問(wèn)題，Themis系統(tǒng)[18]提出了“2-IO property”，即作業(yè)在處理數(shù)據(jù)的過(guò)程中，數(shù)據(jù)從磁盤(pán)的讀寫(xiě)次數(shù)只有2次(HDFS和中間結(jié)果各一次)，其余過(guò)程都不會(huì)與磁盤(pán)交互.為了達(dá)到該目標(biāo)，Themis系統(tǒng)在Shuffle階段使用了動(dòng)態(tài)內(nèi)存分配策略對(duì)該過(guò)程中的數(shù)據(jù)進(jìn)行存儲(chǔ)，從而大幅度減少磁盤(pán)IO開(kāi)銷(xiāo)，降低了作業(yè)時(shí)間.類(lèi)似地，SpongeFiles[19]發(fā)現(xiàn)由于某些作業(yè)存在數(shù)據(jù)傾斜的問(wèn)題，引發(fā)的一個(gè)現(xiàn)象是某些Task的內(nèi)存空間已經(jīng)用完且觸發(fā)了Spill，而某些Task的內(nèi)存空間還有剩余，如圖1(a).基于該現(xiàn)象，SpongeFiles通過(guò)共享Task中未使用的內(nèi)存空間，如圖1(b)，減少Spill的次數(shù)，從而降低了磁盤(pán)IO開(kāi)銷(xiāo).

Fig. 1 The way how task organizes memory圖1 Task內(nèi)存的使用方式

1.1.2 聚合磁盤(pán)IO

在Shuffle階段過(guò)程中，Reduce端在讀取過(guò)程中會(huì)存在大量的小粒度、隨機(jī)讀，從而引起磁盤(pán)的大量尋道，降低IO性能，延長(zhǎng)作業(yè)執(zhí)行時(shí)間，對(duì)于磁盤(pán)而言，適用的IO模式是大粒度、順序的.因此當(dāng)中間結(jié)果的數(shù)據(jù)量較大時(shí)，磁盤(pán)會(huì)出現(xiàn)性能瓶頸.為了解決該問(wèn)題，Sailfish系統(tǒng)[20]采用了“Batching Data IO”的技術(shù)來(lái)避免Shuffle讀取時(shí)產(chǎn)生的大量尋道問(wèn)題，即寫(xiě)Shuffle數(shù)據(jù)時(shí)，聚集每個(gè)Map Task相對(duì)應(yīng)的分區(qū)的數(shù)據(jù)，利用分布式文件系統(tǒng)來(lái)存儲(chǔ)相應(yīng)的數(shù)據(jù)，從而在讀取中間結(jié)果時(shí)，原先的隨機(jī)、小粒度的讀轉(zhuǎn)換成了順序、大粒度的讀，加速了中間結(jié)果的數(shù)據(jù)讀取，如圖2所示，但是存在的問(wèn)題是將中間結(jié)果寫(xiě)入到分布式文件系統(tǒng)中，需要涉及到2次網(wǎng)絡(luò)IO：前期寫(xiě)入和后期讀取，而原始Shuffle將中間結(jié)果寫(xiě)入到本地磁盤(pán)時(shí)，網(wǎng)絡(luò)IO只涉及到了“后期讀取”，因此在考慮使用分布式文件系統(tǒng)存儲(chǔ)中間結(jié)果時(shí)，還需要考慮當(dāng)前集群的網(wǎng)絡(luò)環(huán)境.

1.1.3 高速網(wǎng)絡(luò)加速

Shuffle過(guò)程中，Reduce端拉取數(shù)據(jù)會(huì)引起重復(fù)數(shù)據(jù)的讀寫(xiě)，重復(fù)數(shù)據(jù)的讀寫(xiě)意味著大量的磁盤(pán)操作，并且以小粒度、隨機(jī)為主，因此當(dāng)中間結(jié)果的數(shù)據(jù)量較大時(shí)，該階段可能會(huì)存在磁盤(pán)性能瓶頸.

Fig. 2 Batching data IO圖2 聚合磁盤(pán)IO

Hadoop-A[21]和Hadoop-IB[22]利用高速網(wǎng)絡(luò)(RDMA[23-24])的特性，通過(guò)高效的算法，避免了重復(fù)數(shù)據(jù)的讀寫(xiě).大致流程:首先建立關(guān)于key的優(yōu)先隊(duì)列；然后Reduce根據(jù)優(yōu)先隊(duì)列中key的順序，進(jìn)行數(shù)據(jù)的Shuffle，Merge，Reduce操作.優(yōu)先隊(duì)列的主要作用是使得Shuffle,Merge,Reduce三階段進(jìn)行pipeline：由于key是有序排列的，因此根據(jù)key的順序從Map端進(jìn)行讀取，從而避免了Reduce端的重復(fù)數(shù)據(jù)讀寫(xiě).

1.2 非易失內(nèi)存相關(guān)工作

隨著非易失內(nèi)存NVM(主要指的是持久化內(nèi)存)的發(fā)展，一部分研究工作集中于如何對(duì)該存儲(chǔ)介質(zhì)上的數(shù)據(jù)進(jìn)行訪(fǎng)問(wèn)和管理，大致可以分為2類(lèi)：1)提供文件系統(tǒng)抽象，即基于NVM的文件系統(tǒng)(NVM file system)；2)提供持久化內(nèi)存抽象，上層應(yīng)用可通過(guò)新的接口或者編程模型來(lái)直接使用NVM(persistent regionsheaps).

Fig. 3 The stack of Linux file system圖3 Linux IO軟件棧

1.2.1 基于NVM的文件系統(tǒng)

傳統(tǒng)文件系統(tǒng)主要是針對(duì)慢速塊設(shè)備(例如磁盤(pán))而設(shè)計(jì)的，如圖3所示，應(yīng)用程序關(guān)于文件的讀寫(xiě)請(qǐng)求發(fā)出之后，通過(guò)虛擬文件系統(tǒng)到達(dá)文件所在的文件系統(tǒng)，例如EXT4，并且需要經(jīng)過(guò)通用塊層、IO調(diào)度層和塊設(shè)備驅(qū)動(dòng)等軟件層次才能最終到達(dá)存儲(chǔ)設(shè)備，而對(duì)于內(nèi)存文件系統(tǒng)而言，其訪(fǎng)問(wèn)層次就明顯減少，它主要利用高度優(yōu)化的內(nèi)存管理來(lái)訪(fǎng)問(wèn)內(nèi)存.

典型的工作，例如BPFS[25]，SCMFS[26]，PMFS[27]等.BPFS是由Condit等人在2009年提出的一種關(guān)于字節(jié)尋址的持久化內(nèi)存文件系統(tǒng)，它主要利用了NVM的兩大特性，即字節(jié)尋址和原地更新.BPFS以?xún)?nèi)存的方式來(lái)管理持久化內(nèi)存，并在其上構(gòu)建文件系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)，避免了數(shù)據(jù)拷貝，通過(guò)short-circuit shadow paging技術(shù)來(lái)支持?jǐn)?shù)據(jù)的原子性、細(xì)粒度、一致的更新，從而使得機(jī)器重啟之后仍能正確訪(fǎng)問(wèn)其中的數(shù)據(jù)[25].Wu等人在2011年提出了一個(gè)在虛擬地址空間中實(shí)現(xiàn)的文件系統(tǒng)SCMFS，該系統(tǒng)利用內(nèi)存管理單元實(shí)現(xiàn)虛擬地址到物理地址的轉(zhuǎn)換，并且利用現(xiàn)有的內(nèi)存管理模塊進(jìn)行塊管理，使得每個(gè)文件的虛擬地址空間都是連續(xù)的，簡(jiǎn)化了文件操作，減少了CPU開(kāi)銷(xiāo)，另外它還采用了空間預(yù)分配機(jī)制以及相應(yīng)的垃圾回收機(jī)制[26].Intel在2014年提出了基于NVM的文件系統(tǒng)——PMFS，它繞開(kāi)了傳統(tǒng)文件系統(tǒng)的緩存層，而直接對(duì)持久化內(nèi)存進(jìn)行訪(fǎng)問(wèn)，通過(guò)該種方式能夠有效避免數(shù)據(jù)拷貝，大幅提升文件系統(tǒng)的性能[27].

基于NVM的文件系統(tǒng)主要設(shè)計(jì)目標(biāo)是降低傳統(tǒng)文件系統(tǒng)軟件棧的開(kāi)銷(xiāo)，并且利用NVM的特性來(lái)提升文件系統(tǒng)的性能，如字節(jié)尋址、原子更新、高性能的隨機(jī)訪(fǎng)問(wèn)，但是這些文件系統(tǒng)都是基于虛擬文件系統(tǒng)，文件系統(tǒng)本身的開(kāi)銷(xiāo)還是存在的，例如元數(shù)據(jù)的管理、名字空間的維護(hù)，這些對(duì)于文件系統(tǒng)而言也是一個(gè)較大的開(kāi)銷(xiāo)，無(wú)法最大化發(fā)揮NVM的性能優(yōu)勢(shì)，因此有一部分研究工作集中于為上層應(yīng)用程序提供用戶(hù)態(tài)的編程接口，程序能夠在用戶(hù)態(tài)訪(fǎng)問(wèn)NVM.

1.2.2 持久化內(nèi)存的編程模型與接口

傳統(tǒng)存儲(chǔ)系統(tǒng)中，數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)2種格式：內(nèi)存格式和磁盤(pán)格式.這2種格式之間的轉(zhuǎn)換只有在數(shù)據(jù)持久化的過(guò)程中進(jìn)行.而在持久化內(nèi)存中，數(shù)據(jù)結(jié)構(gòu)可以直接持久化在內(nèi)存中，無(wú)需進(jìn)行格式的轉(zhuǎn)換.一些研究工作[13,15,28-29]利用該特性簡(jiǎn)化了NVM的使用，例如，Volos等人提出的輕量級(jí)主存系統(tǒng)Mnemosyne[15]在PCM設(shè)備能保證64 b原子寫(xiě)的假設(shè)下修改系統(tǒng)庫(kù)函數(shù)，為程序員設(shè)計(jì)了一個(gè)直接訪(fǎng)問(wèn)非易失存儲(chǔ)器的接口，對(duì)于開(kāi)發(fā)過(guò)程中想要持久化的數(shù)據(jù), 只需用特定的數(shù)據(jù)類(lèi)型pstatic聲明即可.Coburn等人提出了一個(gè)輕量級(jí)高性能持久化對(duì)象系統(tǒng)——NV-heaps(non-volatile memory heaps)[13]，它是基于BPFS[25]的硬件設(shè)計(jì)結(jié)構(gòu)，為程序員提供了包括對(duì)象、指針、主存分配等接口，實(shí)現(xiàn)指針安全(防止非易失存儲(chǔ)上的指針指向易失性存儲(chǔ)介質(zhì)的情況發(fā)生)、ACID事務(wù)處理、傳統(tǒng)API服務(wù)、高性能以及可靠的功能，以便在系統(tǒng)崩潰、斷電或其他常見(jiàn)失效發(fā)生時(shí)保護(hù)非易失存儲(chǔ)設(shè)備上數(shù)據(jù)的正確性.另外，NV-Tree[30]，CDDS[31]等工作提出了一個(gè)基于NVM的一致性、可持久化的數(shù)據(jù)結(jié)構(gòu)，使得應(yīng)用可以直接使用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，而不需要關(guān)心數(shù)據(jù)結(jié)構(gòu)在持久化內(nèi)存上的具體實(shí)現(xiàn)細(xì)節(jié).上述工作主要還是在基于文件系統(tǒng)之上(粗粒度的空間管理)提供了細(xì)粒度的數(shù)據(jù)管理、空間分配與釋放、持久化以及事務(wù)管理，而pVM[17]，它是基于VM(virtual memory)，而不是文件系統(tǒng)，因此在性能上，pVM更勝一籌.

2 NV-Shuffle設(shè)計(jì)與實(shí)現(xiàn)

NV-Shuffle的主要設(shè)計(jì)目標(biāo)是高效利用NVM加速Shuffle階段，其核心思想是基于持久化內(nèi)存的訪(fǎng)問(wèn)接口進(jìn)行NV-Buffer的分配與數(shù)據(jù)讀寫(xiě)，通過(guò)Hash-based Private NV-Buffer進(jìn)行Shuffle數(shù)據(jù)的組織，使用KeyValue方式進(jìn)行NV-Buffer的管理.

Fig. 4 The architecture of NV-Shuffle圖4 NV-Shuffle架構(gòu)圖

圖4展示了NV-Shuffle的總體框架.從圖4中可以看出，NV-Buffer是Shuffle數(shù)據(jù)存儲(chǔ)的基本單位，在Shuffle過(guò)程中，通過(guò)NVmalloc和NVfree接口進(jìn)行NV-Buffer的分配與釋放，而對(duì)于NV-Buffer的訪(fǎng)問(wèn)與傳統(tǒng)的Memory訪(fǎng)問(wèn)類(lèi)似.至于Shuffle過(guò)程中數(shù)據(jù)如何組織、NV-Buffer如何分配與管理都將在下面幾節(jié)進(jìn)行詳細(xì)描述.

2.1 NV-Shuffle接口

傳統(tǒng)文件系統(tǒng)主要是為了磁盤(pán)而設(shè)計(jì)的，而對(duì)于NVM而言，其性能接近于DRAM，而且CPU可直接通過(guò)指令訪(fǎng)問(wèn)，導(dǎo)致文件系統(tǒng)自身的開(kāi)銷(xiāo)過(guò)大，例如元數(shù)據(jù)的管理、名字空間的維護(hù)等，而針對(duì)這些問(wèn)題，現(xiàn)有的一些研究針對(duì)NVM重新設(shè)計(jì)了新的文件系統(tǒng)，例如BPFS[25]，SCMFS[26]，PMFS[27]等，使其避免或者簡(jiǎn)化了文件系統(tǒng)的設(shè)計(jì)，從而獲取較高的性能.

NVM內(nèi)存除了用于外存儲(chǔ)(文件系統(tǒng))和易失性?xún)?nèi)存外，利用其非易失特性，還可以實(shí)現(xiàn)持久化內(nèi)存，比如，近年來(lái)的Mnemosyne[28]，NV-Heaps[29]，pVM[17]等工作，它們提供了用戶(hù)態(tài)的編程接口，使程序能夠在用戶(hù)態(tài)訪(fǎng)問(wèn)非易失主存, 避免了傳統(tǒng)存儲(chǔ)系統(tǒng)中的冗長(zhǎng)路徑，包括文件系統(tǒng)、設(shè)備驅(qū)動(dòng)等.在持久化內(nèi)存中實(shí)現(xiàn)持久化的數(shù)據(jù)結(jié)構(gòu)，保證系統(tǒng)掉電后數(shù)據(jù)的一致性和可訪(fǎng)問(wèn)性，從而使得程序可直接在用戶(hù)態(tài)進(jìn)行持久化數(shù)據(jù)結(jié)構(gòu)的高效訪(fǎng)問(wèn).而pVM與Mnemosyne,NV-Heap的區(qū)別在于前者是基于VM(virtual memory)實(shí)現(xiàn)的，而后者是基于VFS(virtual file system).相比于Mnemosyne,NV-Heap，pVM在擴(kuò)容、性能等方面存在優(yōu)勢(shì).

對(duì)于Shuffle數(shù)據(jù)而言，只需要保證它們?cè)谧鳂I(yè)運(yùn)行期間可靠地、持久化地存儲(chǔ)，持久化內(nèi)存比文件系統(tǒng)有更小的額外開(kāi)銷(xiāo)，因此，我們采用基于持久化內(nèi)存的Shuffle數(shù)據(jù)存儲(chǔ).NV-Shuffle接口需要滿(mǎn)足以下3個(gè)特征.

1) 基于持久化內(nèi)存的接口訪(fǎng)問(wèn)NVM.①提供類(lèi)似于Posix mallocfree的接口；②摒棄傳統(tǒng)文件系統(tǒng)的方式來(lái)存儲(chǔ)Shuffle數(shù)據(jù)；③應(yīng)用程序可以通過(guò)接口直接使用或者獲取NVM空間.

2) 數(shù)據(jù)可持久化.當(dāng)操作系統(tǒng)或者應(yīng)用由于故障等原因崩潰并重新啟動(dòng)時(shí)，NVM中的數(shù)據(jù)可以進(jìn)行恢復(fù)，以便后續(xù)進(jìn)行數(shù)據(jù)的讀取.

3) 接口的適用性.能夠在大數(shù)據(jù)平臺(tái)上使用.當(dāng)前大多數(shù)的大數(shù)據(jù)平臺(tái)都是基于JavaScala而編寫(xiě)的，因此能夠提供基于Java的接口以適應(yīng)大數(shù)據(jù)的場(chǎng)景.

NV-Shuffle使用持久化內(nèi)存分配和回收接口：NVmalloc和NVfree，其實(shí)現(xiàn)主要借鑒了pVM，由于pVM本身提供的是C++的接口，我們?cè)贘VM中添加了NVmalloc和NVfree接口，即用其封裝了pVM相應(yīng)的接口，以供大數(shù)據(jù)平臺(tái)上的應(yīng)用使用.但是在性能評(píng)測(cè)中，我們利用內(nèi)存來(lái)模擬 NVM，并且使用Java自帶的分配堆外內(nèi)存接口進(jìn)行內(nèi)存的分配與使用.

2.2 基于NVM的Shuffle數(shù)據(jù)組織方式

傳統(tǒng)基于文件系統(tǒng)的Shuffle數(shù)據(jù)的組織方式有2種：Sort-based組織方式和Hash-based組織方式.對(duì)于Sort-based Shuffle，每個(gè)Task最終產(chǎn)生一個(gè)文件，且在該文件中的數(shù)據(jù)是根據(jù)partition ID排序的.在最終文件形成的過(guò)程中，可能會(huì)存在多個(gè)文件，而最終文件是通過(guò)將這幾個(gè)文件合并而成.因此Sort-based Shuffle的主要開(kāi)銷(xiāo)在于Sort,Spill,Merge，并且在合并的過(guò)程中數(shù)據(jù)需要進(jìn)行序列化和反序列化，增加了開(kāi)銷(xiāo)；而對(duì)于Hash-based Shuffle，每個(gè)partition ID都會(huì)對(duì)應(yīng)一個(gè)文件，優(yōu)勢(shì)在于不需要進(jìn)行Sort,Spill，但是劣勢(shì)在于可能會(huì)存在大量的小文件，并且小文件同時(shí)打開(kāi)，會(huì)占用較多的內(nèi)存空間.

對(duì)于基于NVM的Shuffle數(shù)據(jù)的組織方式，主要從2個(gè)方面考慮.

1) Shuffle數(shù)據(jù)本身的特征：①Shuffle數(shù)據(jù)通過(guò)partition ID劃分成多個(gè)分區(qū)，每個(gè)分區(qū)的數(shù)據(jù)存儲(chǔ)在一起，分區(qū)之間按partition ID的順序進(jìn)行存儲(chǔ)；②多個(gè)Task同時(shí)進(jìn)行各自Shuffle數(shù)據(jù)的讀寫(xiě)，即多個(gè)Map Task之間不共享Shuffle數(shù)據(jù)；

2) NVM與磁盤(pán)之間的區(qū)別：NVM與磁盤(pán)的最大區(qū)別在于小粒度、隨機(jī)IO的性能，其中磁盤(pán)性能受小粒度、隨機(jī)IO的影響較大，而NVM的小粒度、隨機(jī)IO的性能基本上與順序IO性能相同.

綜上所述，對(duì)于NVM而言，Shuffle數(shù)據(jù)的組織方式采用Hash-based更為合適：可以減少Sort,Spill,Merge的性能開(kāi)銷(xiāo)；而且對(duì)于NVM而言沒(méi)有小文件和隨機(jī)IO的問(wèn)題.

根據(jù)Task,Partition,NV-Buffer三者之間的關(guān)系，又可以將Hash-based NV-Buffer分成2種形式：基于Hash的共享持久化緩沖區(qū)(Hash-based Shared NV-Buffer)和基于Hash的私有持久化緩沖區(qū)(Hash-based Private NV-Buffer).

2.2.1 基于Hash的共享持久化緩沖區(qū)

Shared NV-Buffer是通過(guò)partition ID進(jìn)行區(qū)分的，也就是，不同Task上具有相同partition ID的keyvalue存儲(chǔ)在同一個(gè)NV-Buffer上，如圖5所示：

Fig. 5 Hash-based Shared NV-Buffer圖5 基于Hash的共享持久化緩存

使用Hash-based Shared NV-Buffer的優(yōu)勢(shì)在于：1)NV-Buffer的空間利用率較高；2)申請(qǐng)NV-Buffer的開(kāi)銷(xiāo)較小.但是該種方式的劣勢(shì)在于：

1) 多個(gè)Task可能并發(fā)地往同一個(gè)NV-Buffer中寫(xiě)數(shù)據(jù)，這時(shí)會(huì)由于并發(fā)寫(xiě)而帶來(lái)鎖開(kāi)銷(xiāo)；

2) 由于所有Task中相同partition ID的數(shù)據(jù)都聚集在同一個(gè)NV-Buffer中，假設(shè)其中一個(gè)Task執(zhí)行失敗了，或者某一個(gè)Task執(zhí)行較慢，此時(shí)系統(tǒng)會(huì)在其他節(jié)點(diǎn)上同時(shí)啟動(dòng)一個(gè)Task處理相同的數(shù)據(jù)，此時(shí)就需要對(duì)失敗的或者執(zhí)行較慢的Task所產(chǎn)生的數(shù)據(jù)進(jìn)行清理與刪除.

2.2.2 基于Hash的私有持久化緩沖區(qū)

Private NV-Buffer是通過(guò)partition ID和Task進(jìn)行區(qū)分，也就是，每個(gè)Task的每個(gè)partition ID都會(huì)對(duì)應(yīng)一個(gè)NV-Buffer，這種方式與傳統(tǒng)Hash-based的方式是類(lèi)似的，如圖6所示：

Fig. 6 Hash-based Private NV-Buffer圖6 基于Hash的私有化持久化緩存

而使用Hash-based Private NV-Buffer的優(yōu)勢(shì)在于：1)Task并發(fā)寫(xiě)時(shí)沒(méi)有鎖競(jìng)爭(zhēng)開(kāi)銷(xiāo)；2)Task之間的數(shù)據(jù)是通過(guò)各自的NV-Buffer完全隔離，因此失效Task的數(shù)據(jù)直接進(jìn)行刪除即可，但是這種方式的劣勢(shì)在于：

1) 空間利用率低.每個(gè)Task上不同partition ID的數(shù)據(jù)量是不相同的，可能差異非常大，統(tǒng)一進(jìn)行分配N(xiāo)V-Buffer則會(huì)造成某些NV-Buffer空間利用率低，導(dǎo)致NVM空間的浪費(fèi).

2) 申請(qǐng)NV-Buffer的次數(shù)較多.每個(gè)Task的每個(gè)partition ID都會(huì)申請(qǐng)一個(gè)NV-Buffer，申請(qǐng)的次數(shù)是Shared NV-Buffer的M倍，其中M表示Map Task的個(gè)數(shù)，因此可能會(huì)在一定程度上存在性能開(kāi)銷(xiāo).

2.2.3 設(shè)計(jì)抉擇

通過(guò)對(duì)Hash-based Shared NV-Buffer和Hash-based Private NV-Buffer的優(yōu)缺點(diǎn)分析，我們采用Hash-based Private NV-Buffer的方式對(duì)Shuffle數(shù)據(jù)進(jìn)行組織，其原因主要有以下2點(diǎn)：

1) Hash-based Shared NV-Buffer的問(wèn)題主要來(lái)自于“多個(gè)Task共享一個(gè)NV-Buffer”，共享NV-Buffer帶來(lái)2個(gè)方面的問(wèn)題：并發(fā)帶來(lái)的開(kāi)銷(xiāo)和失效處理時(shí)帶來(lái)的開(kāi)銷(xiāo).另外，根據(jù)第2.2節(jié)對(duì)于Shuffle階段特征的描述，Hash-based Shared NV-Buffer與Shuffle階段的特征(Task之間互不影響)不匹配；

2) Hash-based Private NV-Buffer基本上與Shuffle階段的特征匹配.不過(guò)，它有2個(gè)方面的劣勢(shì)：空間利用率和性能開(kāi)銷(xiāo)，但是相比于共享NV-Buffer所帶來(lái)的2個(gè)問(wèn)題，Hash-based Private NV-Buffer所面臨的上述2個(gè)劣勢(shì)更易解決.

2.3 NVM空間(NV-Buffer)的分配策略

在2.2.3小節(jié)中，我們通過(guò)Hash-based Private NV-Buffer的方式來(lái)組織Shuffle數(shù)據(jù)，但是Hash-based Private NV-Buffer存在2個(gè)問(wèn)題：空間利用率低和性能開(kāi)銷(xiāo)大.而影響空間利用率和性能開(kāi)銷(xiāo)的一個(gè)重要因素在于空間分配粒度——NV-Buffer粒度.一方面，NV-Buffer的粒度較小，則會(huì)引發(fā)高頻率的空間分配，從而影響性能；另一方面，NV-Buffer的粒度較大，則會(huì)降低空間利用率，從而造成NVM空間的浪費(fèi).因此，NV-Buffer粒度的選取是空間和性能上的一種權(quán)衡.

2.3.1 NV-Buffer粒度的選取

首先，我們通過(guò)實(shí)驗(yàn)來(lái)觀察不同NV-Buffer粒度下的性能開(kāi)銷(xiāo)問(wèn)題.該實(shí)驗(yàn)主要集中在Map Task端，即事先為Map Task中的每個(gè)partition分配N(xiāo)V-Buffer，而partition的個(gè)數(shù)等于Reduce Task的個(gè)數(shù)，分配完成之后進(jìn)行Map Task的計(jì)算.在實(shí)驗(yàn)中，我們假設(shè)負(fù)載的數(shù)據(jù)分布是均勻的，即Map Task中每個(gè)partition的數(shù)據(jù)量基本上是相同的，因此partition數(shù)據(jù)量的計(jì)算公式如下所示：

(1)

其中Map Task所處理的數(shù)據(jù)量一般為Block Size的大小B，而partition個(gè)數(shù)為Reduce Task的個(gè)數(shù)R.因此在執(zhí)行過(guò)程中，一個(gè)Map Task需要執(zhí)行R次NV-Buffer的空間分配，且每次分配的空間大小約為BR，對(duì)于不同Reduce Task個(gè)數(shù)的結(jié)果如圖7所示：

Fig. 7 The time of malloc in Map Task圖7 Map Task中malloc所花費(fèi)的時(shí)間

從圖7中可以看出：1)malloc的開(kāi)銷(xiāo)隨著Reduce個(gè)數(shù)逐漸增加而上升，其主要原因在于Reduce個(gè)數(shù)增多，malloc執(zhí)行的次數(shù)也就相應(yīng)的增加，從而增加了總的malloc的開(kāi)銷(xiāo)；2)malloc所花費(fèi)的時(shí)間較小，以Reduce個(gè)數(shù)為215為例，一個(gè)map task執(zhí)行了215次malloc所所花費(fèi)的時(shí)間不到1 s，因此從總體上看malloc的開(kāi)銷(xiāo)較小，因此即使malloc次數(shù)較多(控制在一定范圍之內(nèi))，對(duì)于job整體上的性能影響也是有限的，所以在NV-Buffer粒度的選取上，由于malloc的開(kāi)銷(xiāo)比較小，為了能夠保證NVM空間較高的利用率，NV-Buffer粒度以小粒度為基準(zhǔn)進(jìn)行分配(默認(rèn)為8 KB).

2.3.2 延遲分配策略

選取了NV-Buffer粒度之后，需要解決如何進(jìn)行NV-Buffer的申請(qǐng)與分配.在Hash-based Private NV-Buffer中，按照之前的流程需要進(jìn)行M×R次NV-Buffer的申請(qǐng)與分配，然而，在一些場(chǎng)景下，可能某些partition并不存在數(shù)據(jù)，例如，

1) 工作負(fù)載的數(shù)據(jù)本身存在傾斜，導(dǎo)致某些partition的數(shù)據(jù)多，而某些partition的數(shù)據(jù)少甚至沒(méi)有；

Fig. 8 The impact of partition size on data distribution圖8 partition粒度對(duì)于數(shù)據(jù)分布的影響

2) partition粒度過(guò)細(xì)，即Reduce個(gè)數(shù)較多.從圖8中可以看出，當(dāng)Reduce個(gè)數(shù)較少時(shí)，基本上不存在size=0的partition，而當(dāng)Reduce個(gè)數(shù)較多是，size=0的partition個(gè)數(shù)上升，例如當(dāng)Reduce個(gè)數(shù)為2 048時(shí)，size=0的個(gè)數(shù)占到了約20%，而一般地，Reduce個(gè)數(shù)設(shè)置較大的作業(yè)在集群規(guī)模較大(成百上千個(gè)節(jié)點(diǎn))、輸入數(shù)據(jù)量較大(TB級(jí))的場(chǎng)景下是常見(jiàn)的[20].

因此，對(duì)于這些沒(méi)有數(shù)據(jù)的partition而言，并不需要進(jìn)行NV-Buffer的分配，而在原始流程中.會(huì)根據(jù)partition的個(gè)數(shù)首先創(chuàng)建好相應(yīng)個(gè)數(shù)的文件，然后進(jìn)行數(shù)據(jù)的寫(xiě)入，那么相對(duì)應(yīng)的，對(duì)于NV-Shuffle而言，首先會(huì)分配一定大小的NV-Buffer(8 KB)，然后往NV-Buffer中寫(xiě)數(shù)據(jù)，當(dāng)NV-Buffer寫(xiě)滿(mǎn)時(shí)，會(huì)繼續(xù)申請(qǐng)新的NV-Buffer來(lái)存儲(chǔ)Shuffle數(shù)據(jù)，如圖9所示：

Fig. 9 Original procedure圖9 原始流程(預(yù)先分配)

對(duì)于文件而言，沒(méi)有數(shù)據(jù)的寫(xiě)入時(shí)，只會(huì)存在少量的元數(shù)據(jù)；而對(duì)于NV-Buffer而言，事先分配了相應(yīng)粒度的NV-Buffer，如果沒(méi)有數(shù)據(jù)的寫(xiě)入，雖然NV-Buffer以小粒度分配，但還是會(huì)造成空間上的浪費(fèi)，因此，我們將原始的預(yù)先分配流程進(jìn)行優(yōu)化，采用延遲分配的方式，即只有當(dāng)partition有數(shù)據(jù)時(shí)，才會(huì)申請(qǐng)相應(yīng)的NV-Buffer，如果沒(méi)有數(shù)據(jù)則始終不進(jìn)行申請(qǐng)，具體流程如圖10所示：

Fig. 10 Late allocation policy圖10 延遲分配策略

從圖10可以看出，通過(guò)延遲分配能夠避免預(yù)先分配中為沒(méi)有數(shù)據(jù)的partition而分配的NV-Buffer.

2.4 NV-Buffer管理

NV-Shuffle摒棄了文件系統(tǒng)，而采用NV-Buffer的方式來(lái)使用NVM，并且由于NV-Shuffle采用Hash-based Private NV-Buffer的方式，會(huì)生成非常多的NV-Buffer，如何對(duì)這些NV-Buffer進(jìn)行管理是一個(gè)非常重要的問(wèn)題.

首先，我們需要了解Shuffle階段對(duì)于NV-Buffer的訪(fǎng)問(wèn)模式，如圖11所示：

Fig. 11 NV-Buffer access pattern圖11 NV-Buffer訪(fǎng)問(wèn)模式

從圖11可以看出，NV-Buffer的訪(fǎng)問(wèn)模式較為簡(jiǎn)單，當(dāng)進(jìn)行讀取時(shí)，不同Task需要讀取與之對(duì)應(yīng)的數(shù)據(jù)，而這些數(shù)據(jù)是根據(jù)partition ID進(jìn)行區(qū)分的.在讀取的過(guò)程中，一個(gè)partition ID會(huì)對(duì)應(yīng)多個(gè)NV-Buffer，因此需要一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)存放partition ID與NV-Buffer之間的關(guān)系，綜上所述，對(duì)于NV-Buffer組織與管理需求分為以下3個(gè)方面.

1) 簡(jiǎn)單.

2) 快速查詢(xún).直接通過(guò)partition ID查詢(xún)NV-Buffer.

3) 數(shù)據(jù)聚合.相同partition ID的NV-Buffer聚合.

根據(jù)上述特征，我們采用映射表的方式來(lái)存儲(chǔ)partition ID與NV-Buffer之間的關(guān)系，并且需要考慮的是一個(gè)partition ID會(huì)對(duì)應(yīng)多個(gè)NV-Buffer的場(chǎng)景.

當(dāng)一個(gè)Task寫(xiě)滿(mǎn)一個(gè)NV-Buffer，會(huì)將相應(yīng)的〈partition ID，NV-Buffer〉插入到映射表中，而當(dāng)一個(gè)Task執(zhí)行完成之后，會(huì)將該映射表中的內(nèi)容上傳到Driver中，由Driver來(lái)維護(hù)映射表，主要有3個(gè)作用：

1) 信息只有在執(zhí)行完成后才能上傳，失效的Task不上傳，保證了后續(xù)的Task所讀到的內(nèi)容都是正確的；

2) Reduce Task會(huì)根據(jù)Driver中記錄的信息，到相應(yīng)的節(jié)點(diǎn)上去拉取數(shù)據(jù)，如圖12所示；

Fig. 12 Shuffle數(shù)據(jù)位置信息的獲取圖12 Access to the address of shuffle data

3) 當(dāng)數(shù)據(jù)所在的Executor由于某些原因崩潰而重新啟動(dòng)一個(gè)新的Executor，Reduce Task還是能夠通過(guò)Driver中記錄的NV-Buffer信息進(jìn)行數(shù)據(jù)的拉取，從而避免了重計(jì)算的開(kāi)銷(xiāo).原始Spark中，Reduce Task也是按照上述流程進(jìn)行數(shù)據(jù)的讀取，但是從第3.5節(jié)中關(guān)于失效恢復(fù)的測(cè)試中可以看出，原始Spark中Shuffle數(shù)據(jù)是與Executor綁定的(Executor ID)，當(dāng)一個(gè)Executor崩潰后，重啟的Executor不復(fù)用原來(lái)Executor的ID，所以，即便原來(lái)的Executor崩潰前已運(yùn)行結(jié)束的Task的Shuffle數(shù)據(jù)已完好保存下來(lái)，在失效恢復(fù)后也無(wú)法利用，需要重新計(jì)算.而對(duì)于NV-Shuffle而言，我們對(duì)于NV-Buffer的管理與組織不依賴(lài)于Executor ID，從而使得在失效恢復(fù)時(shí)，能夠快速找到崩潰Executor的Shuffle數(shù)據(jù).

3 實(shí)驗(yàn)與結(jié)果

3.1 實(shí)驗(yàn)環(huán)境

3.1.1 測(cè)試平臺(tái)以及Spark集群配置信息

由于在評(píng)測(cè)中，我們直接使用內(nèi)存來(lái)模擬NVM，所以服務(wù)器上的內(nèi)存主要有2個(gè)用途：Spark自身使用以及Shuffle階段的數(shù)據(jù)存儲(chǔ).因此關(guān)于Spark主要參數(shù)的設(shè)置，如表2所示.

3.1.2 測(cè)試負(fù)載

根據(jù)Shuffle階段數(shù)據(jù)量的不同，我們將負(fù)載大體分為2類(lèi)：Shuffle-heavy和Shuffle-light.其中Shuffle-heavy的負(fù)載指Shuffle階段的數(shù)據(jù)量較大(通常與輸入數(shù)據(jù)量相同，或者遠(yuǎn)大于輸入數(shù)據(jù)量)，而Shuffle-light的負(fù)載指Shuffle階段的數(shù)據(jù)量較小(通常要遠(yuǎn)小于輸入數(shù)據(jù)量).因此在本次實(shí)驗(yàn)中我們使用了3種不同類(lèi)型的負(fù)載：1)Sort(Shuffle-heavy，即中間結(jié)果數(shù)據(jù)量≈輸入數(shù)據(jù)量)；2)Word-count(Shuffle-light，即中間結(jié)果數(shù)據(jù)量?輸入數(shù)據(jù)量)；3)TPC-H[32]的22條查詢(xún)語(yǔ)句，每一條語(yǔ)句所執(zhí)行的操作不同，因此為了得到其輸入數(shù)據(jù)量與中間結(jié)果數(shù)據(jù)量之間的關(guān)系，我們使用TPC-H官方的數(shù)據(jù)生成器，生成了160 GB的原始數(shù)據(jù)，并將其導(dǎo)入到HDFS中.TPC-H的數(shù)據(jù)是由8張不同的表構(gòu)成，在160 GB的原始數(shù)據(jù)量中，每張表的數(shù)據(jù)量分為是：lineitem 120 GB, orders 27 GB, partsupp 19 GB, customer 3.7 GB, part 3.7 GB, supplier 219 MB, nation 2.2 KB， region 389 B.通過(guò)Spark SQL執(zhí)行22條TPC-H查詢(xún)語(yǔ)句，執(zhí)行結(jié)果如表3所示.

Table 2 The Configuration of Spark表2 Spark配置信息

從輸入數(shù)據(jù)量和中間結(jié)果數(shù)據(jù)量來(lái)看，22條查詢(xún)語(yǔ)句有不同的特征，主要可以分為以下3類(lèi)：

1) Shuffle數(shù)據(jù)量?輸入數(shù)據(jù)量，例如Q8，Q9，Q21等；

2) Shuffle數(shù)據(jù)量≈輸入數(shù)據(jù)量，例如Q4，Q12，Q20等;

3) Shuffle數(shù)據(jù)量?輸入數(shù)據(jù)量，例如Q1，Q6，Q14等.

而對(duì)于NV-Shuffle而言，其有利的場(chǎng)景應(yīng)該包含2個(gè)方面：1)輸入數(shù)據(jù)量較大；2)中間結(jié)果數(shù)據(jù)量≈輸入數(shù)據(jù)量或者 Shuffle數(shù)據(jù)量?輸入數(shù)據(jù)量.由于節(jié)點(diǎn)的內(nèi)存是有限，因此我們?cè)谶x取數(shù)據(jù)集大小時(shí)，需要考慮集群內(nèi)存是否能夠存儲(chǔ)中間結(jié)果數(shù)據(jù)，集群內(nèi)存與Shuffle數(shù)據(jù)量之間的關(guān)系需要滿(mǎn)足式(2)：

集群剩余總內(nèi)存>2×Shuffle數(shù)據(jù)量,

(2)

其中，集群剩余總內(nèi)存表示的是集群留給Shuffle數(shù)據(jù)的存儲(chǔ)空間，Shuffle數(shù)據(jù)在job的過(guò)程中會(huì)存儲(chǔ)2份，即Map端1份，Reduce端1份.因此在條件中Shuffle數(shù)據(jù)所占用的空間需要是原先的2倍，只有當(dāng)集群剩余總內(nèi)存大于2倍Shuffle數(shù)據(jù)量，該job才能順利執(zhí)行，否則失敗.當(dāng)然，該限制條件主要是由于當(dāng)前的測(cè)試環(huán)境造成的.所以，對(duì)于上述負(fù)載所采取的數(shù)據(jù)量：1)Sort：～100 GB；2)Wordcount：～256 GB；3)TPC-H：～160 GB.

Fig. 13 The execution time of Sort and Wordcount圖13 Sort和Wordcount的執(zhí)行時(shí)間

Table 3 The Basic Characters of TPC-H Queries表3 TPC-H Queries的基本特征

3.1.3 對(duì)比對(duì)象

原始的Shuffle是使用文件系統(tǒng)存儲(chǔ)Shuffle數(shù)據(jù)，如果想將NVM應(yīng)用于原始Shuffle，一種簡(jiǎn)單的辦法是在NVM上創(chuàng)建一個(gè)本地文件系統(tǒng).由于我們是用內(nèi)存模擬NVM，因此可以在NVM上先創(chuàng)建塊設(shè)備(用RAMDisk)，再在RAMDisk上創(chuàng)建Ext4.此外，專(zhuān)門(mén)針對(duì)內(nèi)存設(shè)計(jì)的文件系統(tǒng)(如tmpfs)，也可以在NVM上直接使用，但它沒(méi)有持久化保存數(shù)據(jù)的功能，所以其性能優(yōu)勢(shì)在于消除了持久化數(shù)據(jù)帶來(lái)的開(kāi)銷(xiāo).因此，我們選擇了基于RAMDisk的Ext4和tmpfs做對(duì)比對(duì)象.

Table 4 Shuffle Data Storage表4 Shuffle數(shù)據(jù)的存儲(chǔ)方式

根據(jù)Shuffle模式不同，我們使用了常見(jiàn)的模式Hash-based和sort-based.因此，NV-Shuffle的對(duì)比對(duì)象如表5所示：

Table 5 Compared System表5 對(duì)比對(duì)象

3.2 性能測(cè)試

圖13展示了Sort和Wordcount在各種對(duì)比系統(tǒng)中的執(zhí)行時(shí)間以及歸一化執(zhí)行時(shí)間(以NV-Shuffle的執(zhí)行時(shí)間為基準(zhǔn))，從圖13中可以看出，NV-Shuffle對(duì)Shuffle-heavy類(lèi)型和Shuffle-light類(lèi)型負(fù)載的影響是不同的：

1) Shuffle-heavy類(lèi)型.相比于其他模式，NV-Shuffle有較為明顯的優(yōu)勢(shì).以Sort為例，圖13(b)顯示了Sort以NV-Shuffle為基準(zhǔn)的執(zhí)行時(shí)間比例，分別是1.4,1.52，1.18，1.26.由于Sort負(fù)載是Shuffle-heavy類(lèi)型的負(fù)載，輸入的數(shù)據(jù)量約為100 GB，且中間結(jié)果的數(shù)據(jù)量也為100 GB左右，因此在Shuffle階段讀寫(xiě)數(shù)據(jù)量較大，此時(shí)NV-Shuffle的性能優(yōu)勢(shì)得以體現(xiàn)；

2) Shuffle-light類(lèi)型.各種模式的執(zhí)行時(shí)間基本上相同.以Wordcount為例，從圖13(b)可以看出，其執(zhí)行時(shí)間比例大致都為1.其主要原因在于，Wordcount在Input,Shuffle，Output這3個(gè)階段的數(shù)據(jù)量分別是244.5 GB，15 GB，5.8 GB.中間結(jié)果的數(shù)據(jù)量太小，導(dǎo)致發(fā)揮不了NV-Shuffle的性能優(yōu)勢(shì)，因此對(duì)于Wordcount負(fù)載而言，5種對(duì)比系統(tǒng)的執(zhí)行時(shí)間基本上相同.

為了更加清楚地觀察Sort和Wordcount在5種不同模式下的執(zhí)行時(shí)間，我們統(tǒng)計(jì)了Sort和Wordcount在Map stage和Reduce stage的執(zhí)行時(shí)間，如圖14所示：

Fig. 14 The execution time of different stages圖14 不同負(fù)載的Map Stage和Reduce Stage的執(zhí)行時(shí)間

圖14展示了Sort和Wordcount在Map Stage和Reduce Stage的執(zhí)行時(shí)間.從圖14中也可以看出，Shuffle階段的數(shù)據(jù)量是決定NV-Shuffle性能優(yōu)勢(shì)的重要因素.另外，通過(guò)比較不同存儲(chǔ)方式和Shuffle模式，我們也可以看出：

1) tmpfs與RAMDisk在性能上的差異.由于tmpfs是內(nèi)存文件系統(tǒng)，而RAMDisk則是使用內(nèi)存來(lái)模擬塊設(shè)備，并且在其上格式化一個(gè)普通的文件系統(tǒng)，例如在本次實(shí)驗(yàn)中使用的Ext4，因此在性能上，本身tmpfs是要優(yōu)于RAMDisk.由于Shuffle數(shù)據(jù)量上的差異，Sort的差異要比Wordcount的差異更為明顯.

2) Hash-based Shuffle與Sort-based Shuffle在性能上的差異.在數(shù)據(jù)規(guī)模與Reduce Task個(gè)數(shù)不是特別多的場(chǎng)景下，Hash-based模式的性能還是要優(yōu)于Sort-based模式，但是當(dāng)Reduce Task個(gè)數(shù)較大時(shí)，Hash-based模式的局限性就會(huì)體現(xiàn)出來(lái)：小文件對(duì)系統(tǒng)性能的影響.我們使用RAMDisk模式測(cè)試了不同Reduce Task個(gè)數(shù)對(duì)于Sort負(fù)載的影響，其結(jié)果如圖15所示.

Fig. 15 The executing time of different configuration圖15 不同配置下的執(zhí)行時(shí)間

圖15展示了在不同Reduce Task個(gè)數(shù)的場(chǎng)景下，Sort執(zhí)行時(shí)間的變化情況.從圖15中可以看出，當(dāng)Reduce Task設(shè)置得較小時(shí)，Hash-based模式在性能上還是存在優(yōu)勢(shì)的；當(dāng)Reduce Task個(gè)數(shù)較大時(shí)，由于本身的局限性，Hash-based的性能不如Sort-based.這也是為什么在原始Spark中，會(huì)存在一個(gè)參數(shù)“spark.shuffle.sort.bypassMergeThreshold”的原因.當(dāng)然，由于NV-Shuffle摒棄了文件系統(tǒng)的存儲(chǔ)方式，因此小文件問(wèn)題不會(huì)影響NV-Shuffle的性能，從而NV-Shuffle仍舊采用類(lèi)似于Hash-based的數(shù)據(jù)組織方式.

同樣地，我們使用TPC-H的22條查詢(xún)語(yǔ)句對(duì)比了上述5種對(duì)比系統(tǒng)的執(zhí)行時(shí)間，為了能夠更好地展現(xiàn)22條查詢(xún)語(yǔ)句的執(zhí)行時(shí)間，我們根據(jù)RAMDisk上Sort的執(zhí)行時(shí)間進(jìn)行分類(lèi)：

1) 執(zhí)行時(shí)間T?200 s；

2) 執(zhí)行時(shí)間T>200 s；

3) 執(zhí)行時(shí)間100 s

4) 執(zhí)行時(shí)間T<100 s.

圖16展示了TPC-H中查詢(xún)語(yǔ)句的執(zhí)行時(shí)間和Shuffle數(shù)據(jù)量，圖16中左坐標(biāo)表示的是查詢(xún)的執(zhí)行時(shí)間，右坐標(biāo)表示的是該查詢(xún)語(yǔ)句執(zhí)行過(guò)程中Shuffle的數(shù)據(jù)總量.為了能夠更好地展現(xiàn)NV-Shuffle與其他4種對(duì)比對(duì)象在TPC-H負(fù)載中的差異，我們選擇了每條查詢(xún)語(yǔ)句在RAMDisk Hash，tmpfs Hash，RAMDisk Sort，tmpfs Sort這4種方式下執(zhí)行時(shí)間最少的方式，與NV-Shuffle進(jìn)行對(duì)比，對(duì)比的結(jié)果如圖17所示：

Fig. 16 The results of TPC-H圖16 TPC-H的測(cè)試結(jié)果

圖17展示了相比于MinTime(RAMDisk Hash，tmpfs Hash，RAMDisk Sort，tmpfs Sort)，NV-Shuffle降低的百分比.從圖17中可以看出：

Fig. 17 Comparison of NV-Shuffle with Min(RAMDisk Hash, tmpfs Hash, RAMDisk Sort, tmpfs Sort)圖17 NV-Shuffle與Min (RAMDisk Hash，tmpfs Hash，RAMDisk Sort，tmpfs Sort)之間的對(duì)比

1) Shuffle數(shù)據(jù)量越大，NV-Shuffle的效果越明顯(10%～25%)，例如Q5,Q8,Q9,Q21等；

2) 由于其Shuffle數(shù)據(jù)量少，NV-Shuffle基本上沒(méi)有效果，例如Q1,Q6,Q15,Q19等；

3) 其他Query語(yǔ)句，雖然存在一定量的Shuffle數(shù)據(jù)，但是NV-Shuffle能夠降低的執(zhí)行時(shí)間非常有限(3%～8%)，例如Q2,Q3,Q15等.

3.3 Shuffle數(shù)據(jù)的組織方式測(cè)試

NV-Shuffle使用了Hash-based Private NV-Buffer的方式，而與之對(duì)應(yīng)的是Hash-based Shared NV-Buffer方式，在本節(jié)中，我們主要對(duì)比這2種方式的性能差異.

Fig. 18 The relationship between parallelism, the number of partitions and performance overheads圖18 并行度P、partition個(gè)數(shù)R、性能開(kāi)銷(xiāo)O三者之間的關(guān)系

在第2.2節(jié)中，我們提到Hash-based Shared NV-Buffer的2個(gè)缺點(diǎn)是并發(fā)寫(xiě)帶來(lái)的鎖開(kāi)銷(xiāo)和失效恢復(fù)(暫不評(píng)價(jià)).因此，我們來(lái)看并發(fā)寫(xiě)帶來(lái)的鎖開(kāi)銷(xiāo)對(duì)于Hash-based Shared NV-Buffer的影響.影響并發(fā)寫(xiě)的2個(gè)因素：節(jié)點(diǎn)上Task的并行度和partition個(gè)數(shù).并行度P、partition個(gè)數(shù)R、鎖競(jìng)爭(zhēng)引發(fā)的開(kāi)銷(xiāo)O這三者之間的關(guān)系，如圖18所示：

圖18中的橫坐標(biāo)表示的是并行度與partition個(gè)數(shù)的比例，縱坐標(biāo)表示的是性能開(kāi)銷(xiāo)，從圖18中可以看出，當(dāng)PR越小，性能開(kāi)銷(xiāo)就越小，反之，性能開(kāi)銷(xiāo)則越大.因此，我們進(jìn)行了一些對(duì)比實(shí)驗(yàn)，該實(shí)驗(yàn)我們使用了一個(gè)1+1的Spark集群，且使用了Sort負(fù)載進(jìn)行測(cè)試.

圖19展示了Shared與Private在極端場(chǎng)景下的性能對(duì)比，即partition的個(gè)數(shù)為1，并行度分別為4,8,16,32,64，則PR的比例是逐漸增大.在實(shí)驗(yàn)中，我們統(tǒng)計(jì)了Map Task的平均執(zhí)行時(shí)間，從圖19中可以看出：1)Private的平均時(shí)間都要小于Shared的平均時(shí)間，一個(gè)主要的原因在于Shared存在鎖競(jìng)爭(zhēng)的開(kāi)銷(xiāo)；2)當(dāng)并行度逐漸增大時(shí)，例如32,64，無(wú)論是Private還是Shared，平均時(shí)間都有一個(gè)明顯的上升，引起該現(xiàn)象的主要原因在于測(cè)試節(jié)點(diǎn)的CPU核數(shù)為12，啟用超線(xiàn)程之后變?yōu)?4，因此當(dāng)并行度為32或者64時(shí)，存在CPU資源的競(jìng)爭(zhēng)，從而導(dǎo)致性能的下降.為了更加清晰地看出不同并行度下的CPU利用率，我們列舉了并行度為8,32時(shí)節(jié)點(diǎn)在Map Stage時(shí)的CPU利用率，如圖20所示.

Fig. 19 The results when R=1圖19 R=1的性能評(píng)測(cè)

Fig. 20 The CPU utilization under different parallelism圖20 不同并行度下的CPU利用率

Fig. 21 The results when R=128圖21 R=128的性能評(píng)測(cè)

從圖20可以看出，當(dāng)并行度超過(guò)節(jié)點(diǎn)本身的CPU資源限制時(shí)CPU利用率較高，也會(huì)導(dǎo)致系統(tǒng)性能的下降.但是在實(shí)際的生產(chǎn)環(huán)境中，partition個(gè)數(shù)為1的場(chǎng)景并不常見(jiàn)，例如Taobao的負(fù)載[33]，其job的平均Reduce個(gè)數(shù)為12，而Sailfish[20]使用Yahoo的負(fù)載，它的Reduce個(gè)數(shù)為1 024～65 536之間.因此我們以R=128為測(cè)試場(chǎng)景，其測(cè)試結(jié)果如圖21所示.

從圖21可以看出，由于增加了partition個(gè)數(shù)，能夠在一定程度上緩解競(jìng)爭(zhēng)所帶來(lái)的性能開(kāi)銷(xiāo)，即在同一時(shí)間內(nèi)，并不是所有的Task都往一個(gè)partition上寫(xiě)，如圖22所示:

Fig. 22 The Shared mode under different partitions圖22 不同partition個(gè)數(shù)下的Shared模式

雖然通過(guò)增加partition的個(gè)數(shù)能夠緩解鎖競(jìng)爭(zhēng)，但是從圖22的測(cè)試結(jié)果看，Private模式的性能要優(yōu)于Shared模式，并且在2.2.1節(jié)中描述了Shared模式在失效處理上的劣勢(shì)，因此無(wú)論從性能還是錯(cuò)誤處理的角度，Private模式都要優(yōu)于Shared模式.

3.4 NVM空間分配策略測(cè)試

在2.3.2節(jié)中，我們了解到NV-Shuffle malloc對(duì)于不同粒度NV-Buffer的開(kāi)銷(xiāo)較小，并且我們修改了原先流程中對(duì)于NV-Buffer的分配機(jī)制(預(yù)先分配變?yōu)檠舆t分配)，因此在本節(jié)中，一方面，我們需要觀察不同粒度的NV-Buffer對(duì)于負(fù)載執(zhí)行時(shí)間的影響；另一方面，延遲分配對(duì)于系統(tǒng)的影響.

1) 不同粒度的NV-Buffer對(duì)于執(zhí)行時(shí)間的影響.在該實(shí)驗(yàn)中，我們使用不同粒度的NV-Buffer(4 KB，8 KB，16 KB，32 KB，64 KB)對(duì)Sort和Wordcount進(jìn)行測(cè)試，其結(jié)果如圖23所示：

Fig. 23 The impact of the NV-Buffer size on job execution圖23 NV-Buffer粒度對(duì)于作業(yè)執(zhí)行的影響

圖23展示了不同粒度對(duì)于作業(yè)的執(zhí)行時(shí)間的影響，從圖23中可以看出，隨著分配粒度逐漸增大，執(zhí)行時(shí)間存在小幅度的降低，但是整體上對(duì)于執(zhí)行時(shí)間的影響不大，但是分配粒度的選取在一定程度上會(huì)影響空間利用率，因此我們將分配粒度的默認(rèn)值設(shè)置為8 KB.

2) 延遲分配的影響.延遲分配可以避免為那些不存在數(shù)據(jù)的partition進(jìn)行分配N(xiāo)V-Buffer，從而在一定程度上節(jié)省NVM空間資源.在第2.3節(jié)中，我們統(tǒng)計(jì)了不同Reduce個(gè)數(shù)下size=0的partition個(gè)數(shù)，如圖8所示，即當(dāng)Reduce個(gè)數(shù)越大時(shí)，其size=0的partition個(gè)數(shù)就越多，例如當(dāng)Reduce個(gè)數(shù)為2 048時(shí)，平均每個(gè)Map Task中size=0的partition個(gè)數(shù)為419，相比于預(yù)先分配，延遲分配不會(huì)為這個(gè)419個(gè)partition分配N(xiāo)V-Buffer，從而在一定程度上節(jié)省了空間資源，那么與預(yù)先分配對(duì)比能夠節(jié)省的空間資源大小，如式(3)所示：

節(jié)省的空間=M×P0×NV-Buffer,

(3)

其中，M表示是Map Task的總個(gè)數(shù)，P0表示Map Task中size=0的partition的平均個(gè)數(shù)，NV-Buffer則是NV-Shuffle的分配粒度.上例中，通過(guò)延遲分配可以節(jié)省大約2.6 GB的NVM空間.

3.5 失效恢復(fù)測(cè)試

該部分主要評(píng)測(cè)NV-Shuffle的Shuffle數(shù)據(jù)恢復(fù)時(shí)間與傳統(tǒng)Spark的Shuffle數(shù)據(jù)恢復(fù)時(shí)間.我們通過(guò)人工手動(dòng)的方式在“一定的時(shí)間”kill集群中某一個(gè)節(jié)點(diǎn)上的Executor進(jìn)程，從而觀察作業(yè)最終完成的時(shí)間.其中“一定的時(shí)間”包含2個(gè)部分：1)在Map Stage階段，以完成Map Task個(gè)數(shù)為準(zhǔn)；2)在Reduce Stage階段，以完成Reduce Task個(gè)數(shù)為準(zhǔn).在該實(shí)驗(yàn)中，我們使用2種較為簡(jiǎn)單的負(fù)載：Sort和Wordcount，其中Map Task的個(gè)數(shù)分別為800和2 048，Reduce Task的個(gè)數(shù)都設(shè)置為256.對(duì)于Spark，我們使用了tmpfs Hash的模式來(lái)存儲(chǔ)Shuffle數(shù)據(jù)，從而與NV-Shuffle進(jìn)行對(duì)比.

圖24展示了在Map階段的不同時(shí)機(jī)進(jìn)行kill Executor時(shí)，Sort與Wordcount的執(zhí)行時(shí)間.從圖24中可以看出：1)NV-Shuffle的執(zhí)行時(shí)間不受Executor被kill的影響，其主要原因在于由于NV-Shuffle對(duì)于NV-Buffer的管理和組織不依賴(lài)于Executor ID，因此不需要重新執(zhí)行之前已經(jīng)完成的Map Task；2)對(duì)于Spark而言，其對(duì)Map階段產(chǎn)生的數(shù)據(jù)的組織與維護(hù)是與Executor ID相關(guān)的，因此當(dāng)Executor被kill時(shí)，之前所生成的數(shù)據(jù)便無(wú)效，需要進(jìn)行重計(jì)算，因此在Map階段越晚進(jìn)行kill Executor，重計(jì)算的Task越多，執(zhí)行時(shí)間越長(zhǎng).圖25展示了不同時(shí)機(jī)進(jìn)行kill Executor時(shí)需要重計(jì)算的Task個(gè)數(shù).

Fig. 24 The execution time when executor is killed during Map Stage圖24 在Map階段不同類(lèi)型負(fù)載在Executor被kill時(shí)的執(zhí)行時(shí)間

Fig. 25 The number of recomputing tasks when executor is killed during Map Stage圖25 在Map階段Executor被kill之后重計(jì)算Task的個(gè)數(shù)

Fig. 26 The execution time when executor is killed during Reduce Stage圖26 在Reduce階段不同類(lèi)型負(fù)載在Executor被kill時(shí)的執(zhí)行時(shí)間

圖26展示了在Reduce階段的不同時(shí)機(jī)進(jìn)行kill Executor時(shí)，Sort與Wordcount的執(zhí)行時(shí)間.從圖26可以看出：

1) NV-Shuffle的執(zhí)行時(shí)間不受Executor被kill的影響，其主要原因在于由于NV-Shuffle對(duì)于NV-Buffer的管理和組織不依賴(lài)于Executor ID，因此當(dāng)Executor被kill時(shí)，Reduce Task還是能夠通過(guò)Driver找回?cái)?shù)據(jù)進(jìn)行拉取；

2) 當(dāng)Executor被kill后，重啟的Executor的ID已經(jīng)發(fā)生改變，Reduce Task無(wú)法通過(guò)新的Executor ID去獲取數(shù)據(jù)，Spark需要重新計(jì)算以產(chǎn)生相應(yīng)的數(shù)據(jù)，因此比正常Sort和Wordcount的執(zhí)行時(shí)間分別超出了約36.8%和27.3%；

3) 不同kill時(shí)機(jī)對(duì)NV-Shuffle和Spark的作業(yè)執(zhí)行時(shí)間都沒(méi)有產(chǎn)生影響：①NV-Shuffle由于不需要進(jìn)行重計(jì)算就能夠找回?cái)?shù)據(jù)，因此無(wú)論何時(shí)Executor被kill都不會(huì)影響最終的執(zhí)行時(shí)間；②對(duì)于Spark而言，kill集群中某個(gè)節(jié)點(diǎn)上的Executor，則它所生成的數(shù)據(jù)就要通過(guò)重計(jì)算重新獲取，即所有在該節(jié)點(diǎn)上執(zhí)行完成的Map Task都要重新執(zhí)行一遍，鑒于當(dāng)前數(shù)據(jù)均勻分布在集群上，則需要重新執(zhí)行的Map Task的個(gè)數(shù)分別約為200(Sort)和512(Wordcount)(如圖27所示).等Map Task都執(zhí)行完成之后Reduce Stage則繼續(xù)執(zhí)行剩余沒(méi)有完成的Reduce Task，因此不同的kill時(shí)機(jī)不會(huì)影響作業(yè)的執(zhí)行時(shí)間，增加的時(shí)間只是重新執(zhí)行Map Task的時(shí)間.

Fig. 27 The number of recomputing tasks when executor is killed during Reduce Stage圖27 在Reduce階段Executor被kill之后重計(jì)算Task的個(gè)數(shù)

4 總 結(jié)

Shuffle階段由于持久化所帶來(lái)的IO開(kāi)銷(xiāo)可能大大延長(zhǎng)數(shù)據(jù)處理的時(shí)間，NVM憑借其讀寫(xiě)速度快、非易失性以及高密度性等諸多優(yōu)點(diǎn)，為改變大數(shù)據(jù)處理過(guò)程中對(duì)持久化IO的依賴(lài)、克服目前基于內(nèi)存計(jì)算的大數(shù)據(jù)處理中的IO性能瓶頸提供了新機(jī)會(huì).鑒于上述2點(diǎn)，我們提出了NV-Shuffle，一種基于NVM的Shuffle優(yōu)化策略.NV-Shuffle摒棄了以文件系統(tǒng)進(jìn)行Shuffle數(shù)據(jù)存取的方式，而是采用持久化內(nèi)存的方式，直接在用戶(hù)態(tài)訪(fǎng)問(wèn)持久化內(nèi)存，避免了傳統(tǒng)存儲(chǔ)系統(tǒng)中的冗長(zhǎng)的 IO 路徑帶來(lái)的額外開(kāi)銷(xiāo).為此我們利用pVM構(gòu)建Java的持久化內(nèi)存訪(fǎng)問(wèn)接口，并針對(duì)傳統(tǒng)大數(shù)據(jù)平臺(tái)中的Shuffle階段，提出了基于NVM的Shuffle數(shù)據(jù)組織方式、NVM空間的分配策略以及NV-Buffer的組織管理方式.我們?cè)赟park上實(shí)現(xiàn)了NV-Shuffle，并進(jìn)行了詳細(xì)的性能評(píng)測(cè)與分析.實(shí)驗(yàn)結(jié)果顯示，對(duì)于Shuffle-heavy類(lèi)型的負(fù)載，在用內(nèi)存模擬的NVM上，相比于原始的Shuffle實(shí)現(xiàn)，NV-Shuffle可節(jié)省10%～40%的執(zhí)行時(shí)間.而且，在有節(jié)點(diǎn)上的Executor失效的情況下，NV-Shuffle可節(jié)省時(shí)間的百分比根據(jù)失效時(shí)間點(diǎn)的不同而不同，具體表現(xiàn)為：在Map階段，失效越晚，節(jié)省時(shí)間的百分比越大；在Reduce階段，節(jié)省時(shí)間的百分比與失效時(shí)間點(diǎn)無(wú)關(guān).

[1]Micron. Micron sdram[EB/OL]. [2017-09-29]. https://www.micron.com/products/dram/sdram

[2]AgigA Tech. Agigaram?ddr2 nvdimm[EB/OL]. [2017-09-29]. http://www.agigatech.com/ddr2.php

[3]AgigA Tech. Agigaram?ddr3 nvdimm[EB/OL]. [2017-09-29]. http://www.agigatech.com/ddr3.php

[4]AgigA Tech. Agigaram?ddr4 nvdimm[EB/OL]. [2017-09-29]. http://www.agigatech.com/ddr4.php

[5]Intel. Intel-micron memory 3d xpoint[EB/OL]. [2017-09-29]. http://intel.ly/1eicr0a,

[6]Guo Y, Rao J, Zhou X. ishuffle: Improving Hadoop performance with shuffle-on-write[C] //Proc of the 10th Int Conf on Autonomic Computing (ICAC). Berkeley, CA: USENIX, 2013: 107-117

[7]Rao S, Ramakrishnan R, Silberstein A, et al. Sailfish: A framework for large scale data processing[C] //Proc of the 3rd ACM Symp on Cloud Computing (SoCC). New York: ACM, 2012: 4-16

[8]Wang Y, Que X, Yu W, et al. Hadoop acceleration through network levitated merge[C] //Proc of the 2011 Int Conf for High Performance Computing, Networking, Storage and Analysis (SC). New York: ACM, 2011: 57-70

[9]Rahman M, Islam N S, Lu X, et al. High-performance RDMA-based design of Hadoop MapReduce over infiniband[C] //Proc of the 27th IEEE Int Parallel and Distributed Processing Symp Workshops and PhD Forum (IPDPSW). Piscataway, NJ: IEEE, 2013: 1908-1917

[10]Ruan X, Chen H. Improving shuffle I/O performance for big data processing using hybrid storage[C] //Proc of the 2017 Int Conf on Computing, Networking and Communications (ICNC). Piscataway, NJ: IEEE, 2017: 476-480

[11]Hong J, Li L, Han C, et al. Optimizing Hadoop framework for solid state drives[C] //Proc of the 2016 IEEE Int Congress on Big Data (BigData Congress). Piscataway, NJ: IEEE, 2016: 9-17

[12]Arulraj J, Pavlo A, Dulloor S R. Let’s talk about storage and recovery methods for non-volatile memory database systems[C] //Proc of the 2015 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2015: 707-722

[13]Coburn J, Caulfield A M, Akel A, et al. NV-heaps: Making persistent objects fast and safe with next-generation, non-volatile memories[C] //Proc of the 16th Int Conf on Architectural Support for Programming Languages and Operating Systems (ASPLOS XVI). New York: ACM, 2011: 105-118

[14]Dulloor S R, Kumar S, Keshavamurthy A, et al. System software for persistent memory[C] //Proc of the 9th European Conf on Computer Systems. New York: ACM, 2014: 15-26

[15]Volos H, Tack A J, Swift M M. Mnemosyne: Lightweight persistent memory[C] //Proc of the 16th Int Conf on Architectural Support for Programming Languages and Operating Systems (ASPLOS XVI). New York: ACM, 2011: 91-104

[16]TinyURL. Snappy compession[EB/OL]. [2017-09-29]. http://tinyurl.com/ku899co

[17]Kannan S, Gavrilovska A, Schwan K. pVM: Persistent virtual memory for efficient capacity scaling and object storage[C] //Proc of the 11th European Conf on Computer Systems. New York: ACM, 2016: 1-14

[18]Rasmussen A, Conley M, Porter G, et al. Themis: An I/O-efficient MapReduce[C] //Proc of the 3rd ACM Symp on Cloud Computing (SoCC). New York: ACM, 2012: No.13

[19]Elmeleegy K, Olston C, Reed B. SpongeFiles: Mitigating data skew in MapReduce using distributed memory[C] //Proc of the 2014 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2014: 551-562

[20]Rao S, Ramakrishnan R, Silberstein A, et al. Sailfish: A framework for large scale data processing[C] //Proc of the 3rd ACM Symp on Cloud Computing (SoCC). New York: ACM, 2012: No.4

[21]Wang Y, Que X, Yu W, et al. Hadoop acceleration through network levitated merge[C] //Proc of the 2011 Int Conf for High Performance Computing, Networking, Storage and Analysis (SC). New York: ACM, 2011: 57-70

[22]Rahman M, Islam N S, Lu X, et al. High-performance RDMA-based design of Hadoop MapReduce over infiniband[C] //Proc of the 27th IEEE Int Parallel and Distributed Processing Symp Workshops and PhD Forum (IPDPSW). Piscataway, NJ: IEEE, 2013: 1908-1917

[23] RDMA. Introduction to Remote Direct Memory Access [EB/OL]. [2017-09-29]. http://www.rdmamojo.com/2014/03/31/remote-direct-memory-access-rdma

[24]IBTA. Infiniband Trade Association[EB/OL]. [2017-09-29]. http://www.infinibandta.org

[25]Condit J, Nightingale E B, Frost C, et al. Better I/O through byte-addressable, persistent memory[C] //Proc of the 22nd ACM SIGOPS Sym on Operating Systems Principles. New York: ACM, 2009: 133-146

[26]Wu X, Reddy A. SCMFS: A file system for storage class memory[C] //Proc of 2011 Int Conf for High Performance Computing, Networking, Storage and Analysis. New York: ACM, 2011: 39-51

[27]Dulloor S R, Kumar S, Keshavamurthy A, et al. System software for persistent memory[C] //Proc of the 9th European Conf on Computer Systems. New York: ACM, 2014: 15-26

[28]GitHub. PMemLibrary[EB/OL]. [2017-09-29]. https://github.com/pmem/linux-examples

[29]Moraru I, Andersen D G, Kaminsky M, et al. Consistent, durable, and safe memory management for byte-addressable non-volatile main memory[C] //Proc of the 1st ACM SIGOPS Conf on Timely Results in Operating Systems. New York: ACM, 2013: 1-13

[30]Yang J, Wei Q, Chen C, et al. NV-tree: Reducing consistency cost for NVM-based single level systems[C] //Proc of the 13th USENIX Conf on File and Storage Technologies (FAST). Berkeley, CA: USENIX, 2015: 167-181

[31]Venkataraman S, Tolia N, Ranganathan P, et al. Consistent and durable data structures for non-volatile byte-addressable memory[C] //Proc of the 9th USENIX Conf on File and Storage Technologies (FAST). Berkeley, CA: USENIX, 2011: 61-75

[32]TPC. TPC BenchmarkTMH: Standard Specification, Revision 2.17.3[S]. San Francisco: TPC, 2017

[33]Ren Z, Xu X, Wan J, et al. Workload characterization on a production Hadoop cluster: A case study on Taobao [C] //Proc of 2012 IEEE Int Symp on Workload Characterization (IISWC). Piscataway, NJ: IEEE, 2012: 1-11