郭俊石 羅軼鳳

(復(fù)旦大學(xué)計算機(jī)科學(xué)技術(shù)學(xué)院上海市智能信息處理重點實驗室 上海 200433)

EarnCache:一種增量式大數(shù)據(jù)緩存策略

郭俊石 羅軼鳳

(復(fù)旦大學(xué)計算機(jī)科學(xué)技術(shù)學(xué)院上海市智能信息處理重點實驗室 上海 200433)

在共享的大數(shù)據(jù)集群中，租戶競爭可能導(dǎo)致內(nèi)存資源分配不公平以及利用效率低下。為了提高緩存利用效率和公平性，針對大數(shù)據(jù)應(yīng)用的特性，提出一種增量式緩存策略稱為EarnCache，即文件被訪問得越多，獲得的緩存資源就越多。利用文件被訪問頻率的歷史信息，將緩存分配與替換問題抽象成優(yōu)化問題，給出解決方案。并在分布式存儲系統(tǒng)中實現(xiàn)了EarnCache及MAX-MIN等不同算法，進(jìn)行性能分析。實驗表明，EarnCache可以提高大數(shù)據(jù)緩存效率和總體資源利用率。

大數(shù)據(jù) 緩存分配 增量式

0 引 言

隨著大數(shù)據(jù)應(yīng)用對實時運算需求的提升和內(nèi)存價格的下降，使用內(nèi)存來緩存數(shù)據(jù)、加速運算逐漸成為一種趨勢。大數(shù)據(jù)集群通常由多個計算框架、應(yīng)用或者終端用戶共享，而大數(shù)據(jù)海量的特征決定了無法將數(shù)據(jù)全部放入內(nèi)存，因而內(nèi)存資源競爭不可避免。大數(shù)據(jù)應(yīng)用通常為分析型事務(wù)，數(shù)據(jù)顯示出相似的訪問熱度；另一方面，大數(shù)據(jù)的數(shù)據(jù)塊較大(如HDFS[6]默認(rèn)64 MB)，緩存替換代價比傳統(tǒng)KB級別的頁式存儲高得多。針對大數(shù)據(jù)應(yīng)用的特性，以提高集群使用公平性和緩存效率為目標(biāo)設(shè)計特定內(nèi)存資源管理策略，成為一個重要問題。

文獻(xiàn)[2]針對大型Web行用，提出將所有數(shù)據(jù)放在內(nèi)存中提供服務(wù)。文獻(xiàn)[1,11]在底層分布式文件系統(tǒng)之上，實現(xiàn)了額外的一個緩存層，使用類似HDFS[6]的數(shù)據(jù)管理方式管理緩存。文獻(xiàn)[4]則進(jìn)一步實現(xiàn)了一個可基于內(nèi)存的分布式文件系統(tǒng)，引入Lineage和Checkpoting機(jī)制保證數(shù)據(jù)一致性和可用性。文獻(xiàn)[10]緩存MapReduce[3]的中間結(jié)果以加速MapReduce類型的應(yīng)用。文獻(xiàn)[7]發(fā)現(xiàn)了并行計算All-or-Nothing的特性，即并行的一波計算任務(wù)中，緩存部分任務(wù)數(shù)據(jù)對加速整體計算沒有明顯作用。文獻(xiàn)[5,14-15]分別提出了動態(tài)資源分區(qū)的方法來保證公平性，同時盡量最大化總體性能。文獻(xiàn)[8]擴(kuò)展了MAX-MIN公平性算法[12-13]，加入概率阻斷，以防止作弊行為，提高共享緩存的公平性。

本文提出一種增量式的大數(shù)據(jù)緩存分配策略，稱為EarnCache，從存儲系統(tǒng)角度出發(fā)，根據(jù)文件被訪問的頻率分配內(nèi)存資源。主要工作包含：1) 提出一種增量式緩存分配機(jī)制；2) 將緩存資源分配與替換問題歸納成一個最優(yōu)化問題并提供解決方案；3) 實現(xiàn)EarnCache的原型，并在其上進(jìn)行實驗驗證方案的有效性。

1 系統(tǒng)框架與算法設(shè)計

在共享的大數(shù)據(jù)集群上，緩存資源競爭十分常見。為了提高緩存使用效率，應(yīng)當(dāng)將“熱”數(shù)據(jù)保留在緩存中。大數(shù)據(jù)應(yīng)用通常為分析型事務(wù)，數(shù)據(jù)表現(xiàn)出相似的被訪問熱度。而在共享集群中，不同應(yīng)用、用戶的數(shù)據(jù)文件之間則會表現(xiàn)出不同的熱度。EarnCache從文件的角度出發(fā)，考慮緩存分配的方案。理想情況下，最近最常被訪問的文件應(yīng)當(dāng)獲得更多的緩存資源?；谖募辉L問的歷史信息，尤其是最近的訪問信息，EarnCache實現(xiàn)了一種增量式的緩存分配方案，即一個文件最近被訪問得越多，就會獲得越多的內(nèi)存來緩存數(shù)據(jù)。

本節(jié)將首先介紹EarnCache的總體系統(tǒng)架構(gòu)設(shè)計，然后分別介紹使用歷史訪問信息進(jìn)行緩存分配的方案設(shè)計和緩存替換的算法設(shè)計。

1.1 系統(tǒng)框架設(shè)計

EarnCache是一個塊式存儲系統(tǒng)，整體框架，如圖1所示。整個系統(tǒng)由一個中心的主節(jié)點(Master)和一系列位于存儲節(jié)點上的工作節(jié)點(Worker)組成。主節(jié)點負(fù)責(zé)維護(hù)元數(shù)據(jù)，并根據(jù)歷史訪問信息進(jìn)行緩存分配(詳見1.2節(jié))；工作節(jié)點負(fù)責(zé)數(shù)據(jù)的讀寫，并在收到緩存數(shù)據(jù)塊請求時，根據(jù)主節(jié)點的緩存分配結(jié)果進(jìn)行緩存替換。

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

一個數(shù)據(jù)塊被訪問的流程可以總結(jié)為：1) 客戶進(jìn)程詢問主節(jié)點，獲得數(shù)據(jù)塊的位置；2) 客戶進(jìn)程向數(shù)據(jù)塊所處的工作節(jié)點請求數(shù)據(jù)；3) 工作節(jié)點將嘗試從緩存中讀數(shù)據(jù)塊，如果讀到，則將數(shù)據(jù)返回給客戶進(jìn)程；4) 如果緩存中不存在該數(shù)據(jù)塊，則嘗試從底層文件系統(tǒng)讀，并嘗試將讀到的數(shù)據(jù)緩存到內(nèi)存中(詳見1.3節(jié))。

1.2 增量式緩存分配

EarnCache利用最近歷史訪問信息進(jìn)行緩存分配，EarnCache從訪問數(shù)據(jù)量的角度出發(fā)定義了考察窗口，并只關(guān)注該窗口內(nèi)的文件訪問信息。表1列出了所有分配方案中用到的參數(shù)及其定義。

表1 參數(shù)定義

文件的緩存比例越高，該文件的緩存收益就越大，本文將第i個文件的緩存收益定義為：hi(xi)=lnxi，該函數(shù)為凸函數(shù)意為緩存比例的基數(shù)越大，增加緩存比例獲得的緩存收益增加越少。于是總體收益可表示為式(1)，服從于式(2)的約束：

(1)

(2)

在任意給定時刻，xi是優(yōu)化目標(biāo)中的唯一變量，針對凸函數(shù)fi·lnxi可使用拉格朗日乘子法進(jìn)行求解。定義拉格朗日函數(shù)為：

(3)

(4)

式(4)表明，分配給某個文件的緩存量正比于其在窗口內(nèi)被訪問的頻數(shù)，這與EarnCache增量式分配目標(biāo)一致。在主節(jié)點進(jìn)行緩存資源分配時，如果某個文件的分配量超出其總體需求量，EarnCache則會把剩余的資源平均分配給其他文件使用。

1.3 緩存替換

工作節(jié)點負(fù)責(zé)數(shù)據(jù)的讀寫，當(dāng)讀取的數(shù)據(jù)塊來自于底層文件系統(tǒng)時，工作節(jié)點會嘗試將數(shù)據(jù)塊緩存到自己的內(nèi)存中。緩存過程如圖2所示，當(dāng)緩存某個文件F的數(shù)據(jù)塊時，如果當(dāng)前系統(tǒng)有足夠空閑緩存，則將直接緩存數(shù)據(jù)塊；否則在文件F緩存實際使用量小于分配量時，將從其他已緩存文件處獲取緩存資源，即踢出其他某一文件R的緩存塊并將資源分配給文件F。EarnCache選擇實際緩存使用量超出分配量最多的文件作為R，從而防止緩存資源使用過于集中，保證公平性。EarnCache嘗試這一過程直到回收的緩存量足夠F緩存新的數(shù)據(jù)塊為止。

圖2 緩存替換流程圖

2 實驗分析

本文基于Tachyon[4]實現(xiàn)了EarnCache的原型。實驗使用HDFS作為底層分布式文件系統(tǒng)，使用Spark作為上層計算框架。測試集群由5臺Amazon EC2 m4.2xlarge型號機(jī)器組成，其中一臺為主節(jié)點，其余四臺為工作節(jié)點。每個集群節(jié)點配置有32 GB內(nèi)存，其中12 GB為工作內(nèi)存，20 GB作為緩存資源；集群總共分配80 GB作為緩存數(shù)據(jù)的資源。實驗?zāi)J(rèn)設(shè)置預(yù)設(shè)窗口W的大小為1 000 GB；每個數(shù)據(jù)塊的大小為128 MB。

實驗主要通過運行Spark掃描任務(wù)來對比EarnCache和LRU、LFU、MAX-MIN等緩存替換算法的性能。實驗環(huán)境包含三個文件的掃描任務(wù)，一次測試包含以不同模式進(jìn)行三個文件(FILE-1，F(xiàn)ILE-2，F(xiàn)ILE-3)的掃描任務(wù)。ROUND：以FILE-1, FILE-2, FILE-3順序循環(huán)訪問。ONE：以FILE-1, FILE-2, FILE-1, FILE-3模式訪問，F(xiàn)ILE-1的訪問頻率高。TWO：以FILE-1, FILE-2, FILE-1, FILE-2, FILE-3模式訪問，F(xiàn)ILE-1和FILE-2的訪問頻率較高。實驗?zāi)J(rèn)設(shè)置三個文件的大小均為40 GB。

2.1 總體運行時間對比

我們分別設(shè)置三個文件大小相等(40 GB)和不等(70 GB，40 GB，10 GB)兩種情況，然后將EarnCache在不同訪問模式下與不同緩存替換算法進(jìn)行比較，平均運行時間的結(jié)果。如圖3所示。可以發(fā)現(xiàn)EarnCache的性能是最好的，這是因為EarnCache算法可以讓更多的數(shù)據(jù)塊緩存命中，直接從內(nèi)存中被訪問。同時我們也發(fā)現(xiàn)，EarnCache的性能并沒有預(yù)期的好，尤其是和LRU、LFU算法比較，這是因為：1) 由于實驗設(shè)置，EarnCache只能緩存部分文件，所以只能達(dá)到部分加速的效果；2) 沒有保證緩存局部性(locality)，即很多數(shù)據(jù)塊是通過訪問其他節(jié)點的緩存獲得的。

圖3 程序運行時間對比

2.2 數(shù)據(jù)塊訪問方式分析

為了更好地說明緩存局部性問題，我們分析了EarnCache從本地緩存、遠(yuǎn)程緩存和底層文件系統(tǒng)(UFS)訪問數(shù)據(jù)塊的比例構(gòu)成，如圖4所示?？梢园l(fā)現(xiàn)，EarnCache從本地或者遠(yuǎn)程緩存中訪問的數(shù)據(jù)塊數(shù)量是最多的，這佐證了EarnCache的緩存使用效率是最高的，也解釋了時間性能更好的現(xiàn)象。同時，EarnCache從遠(yuǎn)程緩存讀的數(shù)據(jù)塊數(shù)量也是最多的。如果上層計算框架能夠利用緩存本地性信息，那么EarnCache的性能將有進(jìn)一步提升。

圖4 數(shù)據(jù)塊訪問方式分布圖

2.3 資源的動態(tài)分配

觀察發(fā)現(xiàn)EarnCache和MAX-MIN兩種算法的時間性能比較接近，這是因為實驗設(shè)置決定了兩者的緩存分配方案差別不大。但是MAX-MIN無法動態(tài)重分配資源，當(dāng)三個大小相同的文件中有兩個文件不再被訪問時，緩存分配方案的變化如圖5。EarnCache算法可以保證隨著預(yù)設(shè)窗口的移動，緩存方案逐漸變化，繼續(xù)被訪問的FILE-1逐漸獲得其他文件的緩存資源；而MAX-MIN則依然保持每個文件持有大致相同量的資源。

圖5 FILE-2與FILE-3不再被訪問時的資源動態(tài)分配圖

2.4 預(yù)設(shè)窗口大小的影響

最后我們分析了預(yù)設(shè)窗口大小對性能的影響。如圖6所示，當(dāng)預(yù)設(shè)窗口太小時，總體緩存效率和性能下降明顯，而當(dāng)窗口大小與數(shù)據(jù)集大小相比足夠大時，EarnCache可以有效地管理緩存資源，提升緩存使用效率。

圖6 預(yù)設(shè)觀察窗口大小對性能的影響

3 結(jié) 語

在大數(shù)據(jù)應(yīng)用中國年使用內(nèi)存來緩存數(shù)據(jù)、加速運算逐漸稱為一種趨勢，而在共享的分布式集群中，內(nèi)存資源的競爭不可避免。為了保證緩存分配的公平性以及提高緩存資源使用的效率，本文提出了一種增量式緩存管理方案稱為EarnCache?；诖髷?shù)據(jù)應(yīng)用多為分析型事務(wù)以及數(shù)據(jù)塊緩存替換代價大的特性，利用文件被訪問頻率的歷史信息，本文將緩存分配與替換抽象成一個優(yōu)化問題并給出解決方案。對比實驗表明，EarnCache可以提高大數(shù)據(jù)緩存效率和總體資源利用率。

[1] Zhang J, Wu G, Hu X, et al. A Distributed Cache for Hadoop Distributed File System in Real-Time Cloud Services[C]//ACM/IEEE, International Conference on Grid Computing. ACM, 2012:12-21.

[2] Ousterhout J, Agrawal P, Erickson D, et al. The Case for RAMCloud[J]. Acm Sigops Operating Systems Review, 2011, 54(4):121-130.

[3] Dean J, Ghemawat S. MapReduce: Simplified Data Processing on Large Clusters[C]//Conference on Symposium on Opearting Systems Design & Implementation,2004:107-113.

[4] Li H, Ghodsi A, Zaharia M, et al. Tachyon:Reliable, Memory Speed Storage for Cluster Computing Frameworks[J]. Proceedings of the ACM Symposium on Cloud Computing, 2014,37(3):1-15.

[5] Li Y, Feng D, Shi Z. Enhancing both fairness and performance using rate-aware dynamic storage cache partitioning[C]//International Workshop on Data-Intensive Scalable Computing Systems,2013:31-36.

[6] Shvachko K, Kuang H, Radia S, et al. The hadoop distributed file system[C]//Mass storage systems and technologies (MSST), 2010 IEEE 26th symposium on. IEEE, 2010:1-10.

[7] Ananthanarayanan G, Ghodsi A, Wang A, et al. PACMan: coordinated memory caching for parallel jobs[C]//Usenix Conference on Networked Systems Design and Implementation,2012:20-20.

[8] Pu Q, Li H, Zaharia M, et al. Fairride: Near-optimal, fair cache sharing[C]//13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16). USENIX Association,2016:393-406.

[9] Zaharia M, Chowdhury M, Das T, et al. Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing[C]// Usenix Conference on Networked Systems Design and Implementation. USENIX Association,2012:2-2.

[10] Zhang S, Han J, Liu Z, et al. Accelerating MapReduce with Distributed Memory Cache[C]//IEEE, International Conference on Parallel and Distributed Systems, ICPADS 2009, 8-11 December 2009, Shenzhen, China. DBLP, 2009:472-478.

[11] Luo Y, Luo S, Guan J, et al. A RAMCloud Storage System based on HDFS: Architecture, implementation and evaluation[J]. Journal of Systems & Software, 2013, 86(3):744-750.

[12] Ma Q, Steenkiste P, Zhang H. Routing high-bandwidth traffic in max-min fair share networks[C]//Conference proceedings on Applications, technologies, architectures, and protocols for computer communications. ACM, 1996:206-217.

[13] Cao Z, Zegura E W. Utility max-min: an application-oriented bandwidth allocation scheme[C]//INFOCOM '99. Eighteenth Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. IEEE Xplore,1999,2:793-801.

[14] Tang S, Lee B S, He B, et al. Long-term resource fairness: Towards economic fairness on pay-as-you-use computing systems[C]//Proceedings of the 28th ACM international conference on Supercomputing. ACM, 2014: 251-260.

[15] Ghodsi A, Zaharia M, Hindman B, et al. Dominant resource fairness: fair allocation of multiple resource types[C]//Usenix Conference on Networked Systems Design and Implementation. USENIX Association, 2011:323-336.

EARNCACHE:ANINCREMENTALBIGDATACACHINGSTRATEGY

Guo Junshi Luo Yifeng

(ShanghaiKeyLabofIntelligentInformationProcessing,SchoolofComputerScience,FudanUniversity,Shanghai200433,China)

In shared big data clusters, there exists intense competition for memory resources, which may lead to unfairness and low efficiency in cache utilization. In view of this and based on the characteristics of big data applications, we propose an incremental caching strategy called EarnCache. The basic idea is that the more frequently a file is assessed, the more cache resource it gains. We utilize file accessing information, and further formulize and solve cache allocation and replacement problem as an optimization problem. EarnCache and other cache replacement algorithms like MAX-MIN are implemented on a distributed file system and analyzed in detail. The experimental evaluation demonstrates that EarnCache could enhance the cache efficiency for shared big data clusters with improved resource utilization.

Big data Cache allocation Incremental

2017-03-02。郭俊石，碩士生，主研領(lǐng)域：數(shù)據(jù)庫與知識庫。羅軼鳳，博士。

TP3

A

10.3969/j.issn.1000-386x.2017.11.008