ADCS:一種基于SSD的陣列數(shù)據(jù)庫緩存技術(shù)?
楊慶1,2李暉1,2陳梅1,2戴震宇1,2朱明3
(1.貴州大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院貴陽550025)(2.貴州大學(xué)貴州省先進(jìn)計算與醫(yī)療信息服務(wù)工程實驗室貴陽550025)(3.中國科學(xué)院國家天文臺北京100012)
論文提出了在陣列數(shù)據(jù)庫中引入固態(tài)硬盤作為Cache的內(nèi)存-SSD-磁盤的多級存儲架構(gòu),研發(fā)了以陣列數(shù)據(jù)庫的存儲單元chunk為粒度的緩存技術(shù)—ADCS,并在FASTDB中進(jìn)行了實現(xiàn)。ADCS采用最近最少使用(LRU)算法作為緩存淘汰算法,得益于內(nèi)存和磁盤之間的SSD cache構(gòu)建技術(shù),陣列數(shù)據(jù)庫的查詢性能提升了34%左右。
二級緩存;陣列數(shù)據(jù)庫;ADCS;LRU
Class NumberTP392
隨著科學(xué)技術(shù)的發(fā)展,在各個研究領(lǐng)域均產(chǎn)生了PB級的科學(xué)數(shù)據(jù)。科學(xué)數(shù)據(jù)一般為數(shù)組模型且數(shù)據(jù)量大。很多科學(xué)應(yīng)用利用關(guān)系型數(shù)據(jù)庫很難實現(xiàn)??茖W(xué)分析需要涉及大量復(fù)雜的矩陣運(yùn)算等,這些運(yùn)算難以用SQL語句表示出來。科學(xué)應(yīng)用中需要的版本控制等信息在關(guān)系型數(shù)據(jù)中也很難實現(xiàn)[3~4]。當(dāng)前用在天文方面的主流關(guān)系型數(shù)據(jù)庫,有Oracle、Mysql、PostgreSQL、SQL Server等。如LSST[5]項目,每晚產(chǎn)出TB量級的科學(xué)數(shù)據(jù),關(guān)系型數(shù)據(jù)庫在處理這樣量級的數(shù)據(jù)時依然顯得力不從心[6]。因此,關(guān)系型數(shù)據(jù)庫(RDBMS)已經(jīng)不能滿足科學(xué)數(shù)據(jù)處理的需求。于是,陣列數(shù)據(jù)庫應(yīng)運(yùn)而生。以SciDB[7~8]為代表的陣列數(shù)據(jù)庫具有典型的非關(guān)系型科學(xué)數(shù)據(jù)庫的特征。SciDB是share-noth?ing架構(gòu)的分布式數(shù)據(jù)庫,存儲單元是chunk,chunk中的屬性采用垂直分割的形式,一個chunk存儲了一個屬性。并且采用分發(fā)數(shù)據(jù)到各個節(jié)點(diǎn),更好地進(jìn)行并行查詢。
SciDB在處理簡單查詢時,性能很好。但是,針對復(fù)雜查詢,SciDB查詢效率不高。其中低速的磁盤IO是其主要瓶頸。
固態(tài)硬盤已成為目前廣泛使用的一種存儲設(shè)備。目前的混合存儲應(yīng)用中,SSD主要有兩種優(yōu)化思路。一種是SSD-HDD混合存儲系統(tǒng)[9~11],SSD和HDD是同等的存儲設(shè)備。另一種是SSD-HDD構(gòu)成多級緩存的層次存儲模型[12~15]。第一類將SSD作為主要的存儲設(shè)備,數(shù)據(jù)的讀寫先重定向到SSD中,隨后將SSD中的臟數(shù)據(jù)寫到HDD中。文獻(xiàn)[12]通過過濾合適的數(shù)據(jù)到SSD,提高SSD的利用率。文獻(xiàn)[13]通過降低SSD緩存代價,提升cache的有效容量。第一類在數(shù)據(jù)量較小時效果很好,但是將海量天文數(shù)據(jù)全部存儲在SSD中的方式不經(jīng)濟(jì)。因此,本文采用的是第二種方式。
在處理海量規(guī)模數(shù)據(jù)時,第一種方式不可行。于是有人提出,根據(jù)每個頁面產(chǎn)生的隨機(jī)I/O的數(shù)量,將產(chǎn)生隨機(jī)IO多的表或者索引放在SSD上可以最大化利用SSD的特征,提升數(shù)據(jù)庫的性能[16~17]。但是這種方法要搜集每個頁面的統(tǒng)計信息,將數(shù)據(jù)移動到SSD或者從SSD中移出去,代價很大。也可以采取整個表或者索引為粒度進(jìn)行替換的策略。但是進(jìn)行數(shù)據(jù)庫查詢時,并不是表中的每個記錄都被訪問到,而是表中的一部分經(jīng)常被訪問。因此SSD緩存的數(shù)據(jù)可能被污染。
根據(jù)數(shù)據(jù)訪問的局部性原理,現(xiàn)在訪問的數(shù)據(jù)將來也可能訪問到,因此,內(nèi)存中暫時不用的數(shù)據(jù)以后也可能訪問到,將這部分?jǐn)?shù)據(jù)緩存到SSD中,若再次訪問到該數(shù)據(jù),則可以提升性能。陣列數(shù)據(jù)庫SciDB在進(jìn)行查詢時是以chunk為單位進(jìn)行查詢的。例如,數(shù)組A與數(shù)組B進(jìn)行連接查詢,是A中的chunk與B中的chunk進(jìn)行連接,其中各個chunk中的cell分別進(jìn)行連接操作。如果以陣列(Array)為粒度進(jìn)行緩存,由于科學(xué)應(yīng)用具有傾斜性[18],Ar?ray中的經(jīng)常訪問的屬性集中在一小部分,緩存整個Array必定會造成SSD中存儲的大量的無效空間。如果以chunk中的cell為單位進(jìn)行緩存,過多的小塊會增加內(nèi)存定位的開銷。因此,本文以chunk為粒度進(jìn)行緩存,可以避免緩存空間的浪費(fèi),又可降低大量cell造成的內(nèi)存定位開銷。
FastDB是基于陣列數(shù)據(jù)庫SciDB研發(fā)的一個原型系統(tǒng)。FastDB系統(tǒng)架構(gòu)如圖1所示。
圖1 FastDB系統(tǒng)架構(gòu)圖
此系統(tǒng)主要由協(xié)調(diào)(Coordinate)節(jié)點(diǎn)和工作(Worker)節(jié)點(diǎn)組成。Coordinate節(jié)點(diǎn)負(fù)責(zé)分發(fā)任務(wù),Worker結(jié)點(diǎn)負(fù)責(zé)接收任務(wù),執(zhí)行任務(wù)將結(jié)果返回給Coordinate節(jié)點(diǎn)。Coordinate節(jié)點(diǎn)收集整理返回給客戶端。
這些年來,CPU處理速度增加570倍,而磁盤的速度卻只增加了20倍[19],可見,低速的磁盤已經(jīng)成為陣列數(shù)據(jù)庫I/O性能的瓶頸。因此針對磁盤IO瓶頸,我們進(jìn)行了優(yōu)化工作,優(yōu)化后的FastDB系統(tǒng)如圖2所示。SSD作為擴(kuò)展緩存,存放的是內(nèi)存暫時不用的數(shù)據(jù)。由于科學(xué)應(yīng)用的傾斜性[18],這部分?jǐn)?shù)據(jù)很可能再次被訪問,提高了cache的有效性。
在FASTDB陣列數(shù)據(jù)庫中,查詢執(zhí)行引擎通過緩沖管理器調(diào)用塊,緩沖區(qū)管理通過磁盤管理訪問具體的IO設(shè)備。當(dāng)請求數(shù)組中的一個chunk時,緩沖管理首先檢查緩沖池,如果找到直接返回;否則,首先檢查緩沖池是否有空閑,如果有,磁盤管理器直接從磁盤讀數(shù)據(jù)到緩沖區(qū);如果緩沖區(qū)沒有空閑,緩沖管理器根據(jù)替換算法將chunk淘汰。磁盤管理器主要處理緩沖區(qū)發(fā)送的讀寫請求,處理異步IO,最大化CPU和IO資源。
圖2 加入了SSD的FastDB系統(tǒng)架構(gòu)圖
在天文學(xué)領(lǐng)域中,有各種不同的研究方向。某一類研究方向主要涉及某些數(shù)據(jù),即數(shù)據(jù)具有傾斜性。例如,小行星巡天目標(biāo)識別的研究,主要涉及到小行星相關(guān)表的查詢。此外,河外星系的研究主要涉及到河外星系的查詢。因此在很長一段時間內(nèi),科學(xué)分析只訪問某一部分的數(shù)據(jù),也就是訪問具有時間和空間局部性。
針對以上這些特性,結(jié)合FASTDB陣列數(shù)據(jù)庫的特點(diǎn),提出了基于SSD的陣列數(shù)據(jù)庫緩存算法(Array Database Caching algorithm based on SSD,ADCS),設(shè)計了基于SSD的緩存系統(tǒng)—CSBSF(Cache system based on SSD on FASTDB)。由于天文學(xué)應(yīng)用主要包括巡天觀測、數(shù)據(jù)檢索、交叉證認(rèn),很少進(jìn)行數(shù)據(jù)的修改操作,并且考慮到SSD的讀寫不對稱性以及SSD的壽命問題,因此SSD主要緩存的是從內(nèi)存淘汰的干凈chunk。而從內(nèi)存淘汰的臟的chunk則直接寫回磁盤。如圖3所示,內(nèi)存中淘汰的chunk存入SSD緩存表,SSD緩存表負(fù)責(zé)維護(hù)干凈chunk。把共享緩沖池中淘汰出來的干凈的chunk寫入SSD中,這樣把多數(shù)可能被訪問的chunk緩存到SSD中,明顯減少了對磁盤的I/O操作,提高了數(shù)據(jù)庫的性能。將內(nèi)存中淘汰的chunk,緩存到SSD中。如果SSD中有空間存放chunk,就直接將chunk放入SSD中,并將chunk加入到SSD最近最少訪問(ssdLRU)鏈表中;否則循環(huán)淘汰ssdLRU中的鏈表末尾元素直到SSD中有位置可以存放chunk。
當(dāng)一個查詢請求到來時,例如SQL查詢“select name from Student”,經(jīng)過詞法分析,語法分析,最終轉(zhuǎn)換成對于數(shù)組Student中的屬性name的數(shù)據(jù)請求。進(jìn)行查詢時,為了在SSD中快速查找數(shù)據(jù),數(shù)組ID(arrId)和屬性ID(attId)作為key,通過key可以判斷此chunk是否在SSD中,如果在,則直接從SSD中讀取數(shù)據(jù)。否則,從磁盤讀取,并把chunk放到SSD中。
當(dāng)數(shù)據(jù)庫請求某個chunk,而chunk不在內(nèi)存,要先將chunk放入到cache中。算法1描述了這個過程。當(dāng)內(nèi)存空間滿,放不下此塊chunk時,根據(jù)LRU淘汰算法,需要淘汰內(nèi)存中暫時不用的塊vic?tim到SSD中。這個過程首先要檢查SSD是否能夠容納得下victim,如果不能存放,則從SSDlru鏈表末尾淘汰一個chunk,直至可以放victim到SSD中。算法2描述了SSD存儲空間滿,不能存放內(nèi)存淘汰的chunk時,根據(jù)最近最少使用(LRU)算法,從SSDlru鏈表的末尾獲得victim,淘汰SSD中的chunk并將其在SSD上占用的空間刪除。
圖3 SSD緩存管理圖
如圖3所示,當(dāng)往SSD中寫數(shù)據(jù)時,首先查找SSD空閑列表SsdFreelists。SsdFreelists設(shè)計成一個有序map,std::map<size_t,std::set<o(jì)ff_t>>。其中根據(jù)請求的chunk的大小,從集合中找到一個位置(offset),將chunk緩存到SSD緩沖池的offset上。并將此位置從空閑列表中刪除。
算法1.SSD中塊的加入算法(ADCS)
Input:chunk為不在內(nèi)存,要加入到cache的塊。
Begin:
1do while memory is full
2do while ssd is full
3 Evict chunk from SSD
4loop
5Get the victim from the memlru
6Add victim to SSDlru
7Allocate address of SSD to victim
8Erase victim adderss from SSD FreeLists
9loop
10Add chunk to cache
End
算法2.SSD淘汰算法
Begin:
1Get the victim from the SSDlru
2Remove victim from SSDlru
3Add victim adderss to SSD FreeLists
4Erase victim from SSD
End
算法3.塊的讀算法
Input:chunk為要查找的chunk
Begin:
1if find chunk in memory then
2read chunk from memory
3else
4if chunk in SSD
5 read chunk from SSD
6else
7 read chunk from Disk
8 Add chunk to SSD
End
算法3描述了讀chunk的過程。首先獲得chunk的描述(屬性ID,數(shù)組ID等),從內(nèi)存中查找chunk,命中則直接讀取。否則,通過圖3中的SSD映射表,根據(jù)屬性ID,數(shù)組ID等信息,判斷SSD中是否存在此chunk。如果存在,則根據(jù)SSD映射表中的地址找到在SSD緩沖池中的位置,讀取chunk。如果不存在,則從磁盤中讀取chunk,并將chunk加入到SSD中。
這一節(jié)主要介紹實驗的配置。為了驗證構(gòu)建的SSD緩存的效果,對比了FASTDB和基于SSD的緩存系統(tǒng)CSBSF的性能。
所有實驗都在Intel(R)Xeon(R)CPU E5-2630 V2@2.6GHz(2 Sockets),4核amd64,CentOS6.6操作系統(tǒng)上運(yùn)行。我們的FASTDB和CSBSF中使用SciDB的版本是15.7,SciDB有4個結(jié)點(diǎn),SciDB中每個結(jié)點(diǎn)均配置8G內(nèi)存,500GB硬盤,轉(zhuǎn)速為15000r/ min。兩者用的內(nèi)存,硬盤配置完全相同。其中CS?BSF中用的是三星(SAMSUNG)750 EVO 250G SA?TA3固態(tài)硬盤,總?cè)萘吭O(shè)為200GB。
實驗的數(shù)據(jù)量分為四個規(guī)模,分別為5GB、50GB、100GB、250GB。選取天文學(xué)中常見的8個查詢(Q1-Q8)作為代表,測試緩存的效果。主要測試查詢時間、磁盤IO、網(wǎng)絡(luò)開銷等指標(biāo)。每次實驗結(jié)束后,數(shù)據(jù)都不清空。
查詢結(jié)果如表1所示。其中,第一類為簡單查詢語句(Q1-Q6)。查詢特定區(qū)域,滿足特定條件的天體;該類語句可以歸為“SELECT*FROM* WHERE*”形式。
第二類查詢?yōu)閹OIN的簡單查詢語句(Q7)。例如找出混雜在星體表Star中的星系,并輸出該星系的光度以及天體的objID等信息。該類語句可以歸為“SELECT*FROM*JOIN*ON*WHERE*”形式。
第三類查詢?yōu)閹OIN的復(fù)雜條件查詢語句(Q8)。例如合并所有星系,并輸出星系的總數(shù)。該類語句可以歸為“SELECT*FROM*AS*JOIN *ON*AS*JOIN*ON*WHERE*AND*”形式。
表1 各個查詢執(zhí)行時間(s)
SciDB中一個chunk存儲了一個屬性,SciDB中一個一維數(shù)組[i=0:*,500000,0],假設(shè)有三個實例分別存儲這些數(shù)據(jù)。采用round robin的方式存儲,主要是為了負(fù)載均衡[20]。則實例0將存儲chunk{0},chunk{1500000},chunk{3000000};實例1將存儲chunk{500000},chunk{2000000},chunk{3500000},實例2將存儲chunk{1000000},chunk{2500000},chunk{4000000}。其中實例分布在各個節(jié)點(diǎn)中。正是這種靈活分割的垂直存儲的數(shù)據(jù)結(jié)構(gòu),使得FASTDB能夠更好地并行執(zhí)行。但是當(dāng)執(zhí)行復(fù)雜查詢時,例如Join或者Aggregate查詢,數(shù)據(jù)庫涉及到大量的對磁盤的隨機(jī)訪問以及大量的網(wǎng)絡(luò)開銷,因此,將以后可能訪問的數(shù)據(jù)緩存到SSD上,由于SSD隨機(jī)訪問的開銷比磁盤訪問開銷小,因此能夠有效提升數(shù)據(jù)庫性能。
如圖4中所示,當(dāng)數(shù)據(jù)量為5GB時,數(shù)據(jù)能夠完全放入內(nèi)存,當(dāng)請求到來時,數(shù)據(jù)能夠在內(nèi)存中命中,因此,有SSD時和沒有SSD做緩存時候的性能幾乎一樣。隨著數(shù)據(jù)量的增大,數(shù)據(jù)不能夠完全在內(nèi)存中進(jìn)行,內(nèi)存出現(xiàn)換進(jìn)換出現(xiàn)象,若換出的chunk需要再次被訪問,若能夠在SSD中命中,那么數(shù)據(jù)庫的性能能夠在一定程度上得到提升。圖5,當(dāng)數(shù)據(jù)量小于內(nèi)存時,有緩存和無緩存時間無明顯差異;當(dāng)數(shù)據(jù)量大于內(nèi)存時,性能提升增幅從5%到25%,增長速度提升了20%。當(dāng)數(shù)據(jù)量大于內(nèi)存而小于SSD緩存的容量時,由于SSD緩存的命中使得FASTDB性能提升越來越快。而從100GB到250GB的時候,性能提升增幅從25%~34%,增長速度提升了9%。圖5中相對執(zhí)行時間表示查詢執(zhí)行過程中每隔40s取樣一次,獲得磁盤讀取的字節(jié)數(shù)。圖7中相對執(zhí)行時間類似。隨著數(shù)據(jù)規(guī)模越來越大,由于FASTDB中采用分發(fā)數(shù)據(jù)到節(jié)點(diǎn)的方式進(jìn)行查詢,分布式數(shù)據(jù)庫FASTDB中產(chǎn)生的網(wǎng)絡(luò)開銷也越來越大,網(wǎng)絡(luò)性能越來越差,此時網(wǎng)絡(luò)開銷成為主要瓶頸,因此性能增長幅度變緩。
圖4 不同數(shù)據(jù)量下有緩存和無緩存時查詢響應(yīng)時間
圖5 不同數(shù)據(jù)量下有緩存的性能增長幅度
如圖7所示,在沒有緩存的情況下,從磁盤讀的字節(jié)數(shù)比有緩存時候的字節(jié)數(shù)多。這是因為二級緩存的存在,使chunk在內(nèi)存中缺失時,一部分?jǐn)?shù)據(jù)在SSD中命中,所以從磁盤讀的字節(jié)數(shù)減少,從而提升了查詢的性能。
圖6 有緩存下,不同數(shù)據(jù)量的數(shù)據(jù)產(chǎn)生的網(wǎng)絡(luò)開銷
圖7 有緩存和無緩存時,執(zhí)行查詢磁盤讀的字節(jié)數(shù)
本文針對陣列數(shù)據(jù)庫中復(fù)雜查詢效率低下的問題,提出了用新型硬件SSD作為數(shù)據(jù)庫二級緩存的方法。當(dāng)進(jìn)行復(fù)雜查詢,查找的chunk不在內(nèi)存時,若在SSD中能夠命中,則能夠有效提升數(shù)據(jù)庫性能。結(jié)果表明,使用SSD作為二級緩存有34%左右的性能提升。隨著數(shù)據(jù)量的增大,網(wǎng)絡(luò)開銷也越來越大,分布式查詢中的主要瓶頸從I/O變?yōu)榫W(wǎng)絡(luò)開銷,下一步我們的研究方向是降低網(wǎng)絡(luò)開銷,進(jìn)一步提升陣列數(shù)據(jù)庫的性能。
[1]Soroush E,Balazinska M,Wang D.Arraystore:a storage manager for complex parallel array processing[C]//Pro?ceedings of the 2011 ACM SIGMOD International Confer?ence on Management of data.ACM,2011:253-264.
[2]Li H,Qiu N,Chen M,et al.FASTDB:An Array Database System for Efficient Storing and Analyzing Massive Scien?tific Data[C]//International conference on algorithms and architectures for parallel processing,2015:606-616.
[3]Hey T,Tansley S,Tolle K.The Fourth Paradigm:Data In?tensive Scientific Discoveries[J].Microsoft Research,2009,1:153-164.
[4]Gray J,Liu T D,DeWitt D,et al.Scientific Data Manage?ment in the Coming Decade[R].MSR-TR-2005-10,2005,34:35-41.
[5]Ivezic Z,Tyson J A,Abel B,et al.LSST:from science drivers to reference design and anticipated data products[J].American Astronomical Society,2014,41:336.
[6]Li J,Cui C,He B,et al.Review and Prospect of astronomi?cal database[J].Progress in Astronomy,2013,31(1):1-16.
李建,崔辰州,何勃亮,等.天文數(shù)據(jù)庫回顧與展望[J].天文學(xué)進(jìn)展,2013,31(1):1-16.
[7]Stonebraker M,Becla J,Dewitt D,et al.Requirements for Science Data Bases and SciDB[C]//Conference on Innova?tive Data Systems Research(CIDR)Perspectives,2009:7-16.
[8]Brown P G.Overview of sciDB:large scale array storage,processing and analysis[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of data.ACM,2010:963-968.
[9]Xiao W,Lei X,Li R,et al.PASS:A Hybrid Storage Sys?tem for Performance-Synchronization Tradeoffs Using SS?Ds[C]//IEEE,International Symposium on Parallel and Distributed Processing with Applications.IEEE,2012:485-91.
[10]Yamato Y.Use case study of HDD-SSD hybrid storage,distributed storage and HDD storage on OpenStack[C]// international database engineering and applications sym?posium,2015:228-229.
[11]Jo H,Kwon Y,Kim H,et al.SSD-HDD-Hybrid Virtual Disk in Consolidated Environments[C]//European con?ference on parallel processing,2009:375-384.
[12]Huang M,Serres O,Narayana V K,et al.Efficient cache design for solid-state drives[C]//Proceedings of the 7th ACM international conference on Computing frontiers. ACM,2010:41-50.
[13]Jiang D,Che Y,Xiong J,et al.uCache:A utility-aware multilevel SSD cache management policy[C]//High Per?
ADCS:An Array Database Caching Technology Based on SSD
YANG Qing1,2LI Hui1,2CHEN Mei1,2DAI Zhenyu1,2ZHU Ming3
(1.College of Computer Science and Technology,Guizhou University,Guiyang550025)(2.Guizhou Engineering Laboratory for Advanced Computing and Medical Information Services,Guizhou University,Guiyang 550025)(3.National Astronomical Observatories,Chinese Academy of Sciences,Beijing100012)
This paper introduced solid state disk(SSD)as cache in array database,designed a hierarchical storage architec?ture with memory-SSD-disk and proposed an array database caching technology based on SSD(ADCS),which in granularity of chunk and finally realized in FASTDB.The least recently used(LRU)algorithm was used as the cache elimination algorithm. Through cache construction technology between the memory and disk,the query performance of array database was increased by about 34%.
L2 cache,array database,ADCS,LRU
TP392
10.3969/j.issn.1672-9722.2017.05.029
2016年11月4日,
2016年12月19日
國家自然科學(xué)基金(編號:61462012,61562010,U1531246);基于云計算的醫(yī)療信息管理系統(tǒng)關(guān)鍵技術(shù)研究及應(yīng)用(編號:GY[2014]3018);貴州省重大應(yīng)用基礎(chǔ)研究項目(編號:JZ20142001,JZ20142001-01,JZ20142001-05);貴州省教育廳自然科學(xué)項目(黔科合人才團(tuán)隊字[2015]53號);貴州大學(xué)研究生創(chuàng)新基金(院級);貴州大學(xué)研究生創(chuàng)新基金(編號:2016049)資助。
楊慶,女,碩士研究生,研究方向:分布式數(shù)據(jù)庫、數(shù)據(jù)庫查詢優(yōu)化。李暉,男,副教授,碩士生導(dǎo)師,研究方向:大規(guī)模數(shù)據(jù)管理與分析,高性能數(shù)據(jù)庫,云計算。陳梅,女,碩士生導(dǎo)師,研究方向:數(shù)據(jù)庫新技術(shù)、計算機(jī)應(yīng)用技術(shù)。戴震宇,男,實驗師,研究方向:數(shù)據(jù)庫新技術(shù)、計算機(jī)應(yīng)用技術(shù)。朱明,男,研究員,博士生導(dǎo)師,研究方向:射電天文學(xué),天文大數(shù)據(jù)處理。