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

郭俊石 羅軼鳳

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

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

郭俊石 羅軼鳳

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

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

1.2 增量式緩存分配

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

表1 參數(shù)定義

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

(1)

(2)

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

(3)

(4)

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

1.3 緩存替換

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

圖2 緩存替換流程圖

2 實(shí)驗(yàn)分析

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

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

2.1 總體運(yùn)行時(shí)間對(duì)比

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

圖3 程序運(yùn)行時(shí)間對(duì)比

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

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

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

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

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

圖5 FILE-2與FILE-3不再被訪問(wèn)時(shí)的資源動(dòng)態(tài)分配圖

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

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

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

3 結(jié) 語(yǔ)

在大數(shù)據(jù)應(yīng)用中國(guó)年使用內(nèi)存來(lái)緩存數(shù)據(jù)、加速運(yùn)算逐漸稱為一種趨勢(shì)，而在共享的分布式集群中，內(nèi)存資源的競(jìng)爭(zhēng)不可避免。為了保證緩存分配的公平性以及提高緩存資源使用的效率，本文提出了一種增量式緩存管理方案稱為EarnCache。基于大數(shù)據(jù)應(yīng)用多為分析型事務(wù)以及數(shù)據(jù)塊緩存替換代價(jià)大的特性，利用文件被訪問(wèn)頻率的歷史信息，本文將緩存分配與替換抽象成一個(gè)優(yōu)化問(wèn)題并給出解決方案。對(duì)比實(shí)驗(yàn)表明，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ù)庫(kù)與知識(shí)庫(kù)。羅軼鳳，博士。

TP3

A

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