ADCS：一種基于SSD的陣列數據庫緩存技術?

ADCS：一種基于SSD的陣列數據庫緩存技術?

楊慶1，2李暉1，2陳梅1，2戴震宇1，2朱明3

（1.貴州大學計算機科學與技術學院貴陽550025）（2.貴州大學貴州省先進計算與醫療信息服務工程實驗室貴陽550025）（3.中國科學院國家天文臺北京100012）

論文提出了在陣列數據庫中引入固態硬盤作為Cache的內存-SSD-磁盤的多級存儲架構，研發了以陣列數據庫的存儲單元chunk為粒度的緩存技術—ADCS，并在FASTDB中進行了實現。ADCS采用最近最少使用（LRU）算法作為緩存淘汰算法，得益于內存和磁盤之間的SSD cache構建技術，陣列數據庫的查詢性能提升了34%左右。

二級緩存；陣列數據庫；ADCS；LRU

Class NumberTP392

1 引言

隨著科學技術的發展，在各個研究領域均產生了PB級的科學數據?？茖W數據一般為數組模型且數據量大。很多科學應用利用關系型數據庫很難實現。科學分析需要涉及大量復雜的矩陣運算等，這些運算難以用SQL語句表示出來?？茖W應用中需要的版本控制等信息在關系型數據中也很難實現［3～4］。當前用在天文方面的主流關系型數據庫，有Oracle、Mysql、PostgreSQL、SQL Server等。如LSST［5］項目，每晚產出TB量級的科學數據，關系型數據庫在處理這樣量級的數據時依然顯得力不從心［6］。因此，關系型數據庫（RDBMS）已經不能滿足科學數據處理的需求。于是，陣列數據庫應運而生。以SciDB［7～8］為代表的陣列數據庫具有典型的非關系型科學數據庫的特征。SciDB是share-noth?ing架構的分布式數據庫，存儲單元是chunk，chunk中的屬性采用垂直分割的形式，一個chunk存儲了一個屬性。并且采用分發數據到各個節點，更好地進行并行查詢。

SciDB在處理簡單查詢時，性能很好。但是，針對復雜查詢，SciDB查詢效率不高。其中低速的磁盤IO是其主要瓶頸。

固態硬盤已成為目前廣泛使用的一種存儲設備。目前的混合存儲應用中，SSD主要有兩種優化思路。一種是SSD-HDD混合存儲系統［9～11］，SSD和HDD是同等的存儲設備。另一種是SSD-HDD構成多級緩存的層次存儲模型［12～15］。第一類將SSD作為主要的存儲設備，數據的讀寫先重定向到SSD中，隨后將SSD中的臟數據寫到HDD中。文獻［12］通過過濾合適的數據到SSD，提高SSD的利用率。文獻［13］通過降低SSD緩存代價，提升cache的有效容量。第一類在數據量較小時效果很好，但是將海量天文數據全部存儲在SSD中的方式不經濟。因此，本文采用的是第二種方式。

在處理海量規模數據時，第一種方式不可行。于是有人提出，根據每個頁面產生的隨機I/O的數量，將產生隨機IO多的表或者索引放在SSD上可以最大化利用SSD的特征，提升數據庫的性能［16～17］。但是這種方法要搜集每個頁面的統計信息，將數據移動到SSD或者從SSD中移出去，代價很大。也可以采取整個表或者索引為粒度進行替換的策略。但是進行數據庫查詢時，并不是表中的每個記錄都被訪問到，而是表中的一部分經常被訪問。因此SSD緩存的數據可能被污染。

根據數據訪問的局部性原理，現在訪問的數據將來也可能訪問到，因此，內存中暫時不用的數據以后也可能訪問到，將這部分數據緩存到SSD中，若再次訪問到該數據，則可以提升性能。陣列數據庫SciDB在進行查詢時是以chunk為單位進行查詢的。例如，數組A與數組B進行連接查詢，是A中的chunk與B中的chunk進行連接，其中各個chunk中的cell分別進行連接操作。如果以陣列（Array）為粒度進行緩存，由于科學應用具有傾斜性［18］，Ar?ray中的經常訪問的屬性集中在一小部分，緩存整個Array必定會造成SSD中存儲的大量的無效空間。如果以chunk中的cell為單位進行緩存，過多的小塊會增加內存定位的開銷。因此，本文以chunk為粒度進行緩存，可以避免緩存空間的浪費，又可降低大量cell造成的內存定位開銷。

2 基于SSD的緩存技術

FastDB是基于陣列數據庫SciDB研發的一個原型系統。FastDB系統架構如圖1所示。

圖1 FastDB系統架構圖

此系統主要由協調（Coordinate）節點和工作（Worker）節點組成。Coordinate節點負責分發任務，Worker結點負責接收任務，執行任務將結果返回給Coordinate節點。Coordinate節點收集整理返回給客戶端。

這些年來，CPU處理速度增加570倍，而磁盤的速度卻只增加了20倍［19］，可見，低速的磁盤已經成為陣列數據庫I/O性能的瓶頸。因此針對磁盤IO瓶頸，我們進行了優化工作，優化后的FastDB系統如圖2所示。SSD作為擴展緩存，存放的是內存暫時不用的數據。由于科學應用的傾斜性［18］，這部分數據很可能再次被訪問，提高了cache的有效性。

在FASTDB陣列數據庫中，查詢執行引擎通過緩沖管理器調用塊，緩沖區管理通過磁盤管理訪問具體的IO設備。當請求數組中的一個chunk時，緩沖管理首先檢查緩沖池，如果找到直接返回；否則，首先檢查緩沖池是否有空閑，如果有，磁盤管理器直接從磁盤讀數據到緩沖區；如果緩沖區沒有空閑，緩沖管理器根據替換算法將chunk淘汰。磁盤管理器主要處理緩沖區發送的讀寫請求，處理異步IO，最大化CPU和IO資源。

圖2 加入了SSD的FastDB系統架構圖

3 基于SSD的陣列數據庫緩存算法ADCS

在天文學領域中，有各種不同的研究方向。某一類研究方向主要涉及某些數據，即數據具有傾斜性。例如，小行星巡天目標識別的研究，主要涉及到小行星相關表的查詢。此外，河外星系的研究主要涉及到河外星系的查詢。因此在很長一段時間內，科學分析只訪問某一部分的數據，也就是訪問具有時間和空間局部性。

針對以上這些特性，結合FASTDB陣列數據庫的特點，提出了基于SSD的陣列數據庫緩存算法（Array Database Caching algorithm based on SSD，ADCS），設計了基于SSD的緩存系統—CSBSF（Cache system based on SSD on FASTDB）。由于天文學應用主要包括巡天觀測、數據檢索、交叉證認，很少進行數據的修改操作，并且考慮到SSD的讀寫不對稱性以及SSD的壽命問題，因此SSD主要緩存的是從內存淘汰的干凈chunk。而從內存淘汰的臟的chunk則直接寫回磁盤。如圖3所示，內存中淘汰的chunk存入SSD緩存表，SSD緩存表負責維護干凈chunk。把共享緩沖池中淘汰出來的干凈的chunk寫入SSD中，這樣把多數可能被訪問的chunk緩存到SSD中，明顯減少了對磁盤的I/O操作，提高了數據庫的性能。將內存中淘汰的chunk，緩存到SSD中。如果SSD中有空間存放chunk，就直接將chunk放入SSD中，并將chunk加入到SSD最近最少訪問（ssdLRU）鏈表中；否則循環淘汰ssdLRU中的鏈表末尾元素直到SSD中有位置可以存放chunk。

當一個查詢請求到來時，例如SQL查詢“select name from Student”，經過詞法分析，語法分析，最終轉換成對于數組Student中的屬性name的數據請求。進行查詢時，為了在SSD中快速查找數據，數組ID（arrId）和屬性ID（attId）作為key，通過key可以判斷此chunk是否在SSD中，如果在，則直接從SSD中讀取數據。否則，從磁盤讀取，并把chunk放到SSD中。

當數據庫請求某個chunk，而chunk不在內存，要先將chunk放入到cache中。算法1描述了這個過程。當內存空間滿，放不下此塊chunk時，根據LRU淘汰算法，需要淘汰內存中暫時不用的塊vic?tim到SSD中。這個過程首先要檢查SSD是否能夠容納得下victim，如果不能存放，則從SSDlru鏈表末尾淘汰一個chunk，直至可以放victim到SSD中。算法2描述了SSD存儲空間滿，不能存放內存淘汰的chunk時，根據最近最少使用（LRU）算法，從SSDlru鏈表的末尾獲得victim，淘汰SSD中的chunk并將其在SSD上占用的空間刪除。

圖3 SSD緩存管理圖

如圖3所示，當往SSD中寫數據時，首先查找SSD空閑列表SsdFreelists。SsdFreelists設計成一個有序map，std：：map＜size_t，std：：set＜off_t＞＞。其中根據請求的chunk的大小，從集合中找到一個位置（offset），將chunk緩存到SSD緩沖池的offset上。并將此位置從空閑列表中刪除。

算法1.SSD中塊的加入算法（ADCS）

Input：chunk為不在內存，要加入到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，數組ID等），從內存中查找chunk，命中則直接讀取。否則，通過圖3中的SSD映射表，根據屬性ID，數組ID等信息，判斷SSD中是否存在此chunk。如果存在，則根據SSD映射表中的地址找到在SSD緩沖池中的位置，讀取chunk。如果不存在，則從磁盤中讀取chunk，并將chunk加入到SSD中。

4 實驗設計

這一節主要介紹實驗的配置。為了驗證構建的SSD緩存的效果，對比了FASTDB和基于SSD的緩存系統CSBSF的性能。

所有實驗都在Intel（R）Xeon（R）CPU E5-2630 V2@2.6GHz（2 Sockets），4核amd64，CentOS6.6操作系統上運行。我們的FASTDB和CSBSF中使用SciDB的版本是15.7，SciDB有4個結點，SciDB中每個結點均配置8G內存，500GB硬盤，轉速為15000r/ min。兩者用的內存，硬盤配置完全相同。其中CS?BSF中用的是三星（SAMSUNG）750 EVO 250G SA?TA3固態硬盤，總容量設為200GB。

實驗的數據量分為四個規模，分別為5GB、50GB、100GB、250GB。選取天文學中常見的8個查詢（Q1-Q8）作為代表，測試緩存的效果。主要測試查詢時間、磁盤IO、網絡開銷等指標。每次實驗結束后，數據都不清空。

5 實驗結果及性能分析

查詢結果如表1所示。其中，第一類為簡單查詢語句（Q1-Q6）。查詢特定區域，滿足特定條件的天體；該類語句可以歸為“SELECT*FROM* WHERE*”形式。

第二類查詢為帶JOIN的簡單查詢語句（Q7）。例如找出混雜在星體表Star中的星系，并輸出該星系的光度以及天體的objID等信息。該類語句可以歸為“SELECT*FROM*JOIN*ON*WHERE*”形式。

第三類查詢為帶JOIN的復雜條件查詢語句（Q8）。例如合并所有星系，并輸出星系的總數。該類語句可以歸為“SELECT*FROM*AS*JOIN *ON*AS*JOIN*ON*WHERE*AND*”形式。

表1 各個查詢執行時間（s）

SciDB中一個chunk存儲了一個屬性，SciDB中一個一維數組［i=0：*，500000，0］，假設有三個實例分別存儲這些數據。采用round robin的方式存儲，主要是為了負載均衡［20］。則實例0將存儲chunk｛0｝，chunk｛1500000｝，chunk｛3000000｝；實例1將存儲chunk｛500000｝，chunk｛2000000｝，chunk｛3500000｝，實例2將存儲chunk｛1000000｝，chunk｛2500000｝，chunk｛4000000｝。其中實例分布在各個節點中。正是這種靈活分割的垂直存儲的數據結構，使得FASTDB能夠更好地并行執行。但是當執行復雜查詢時，例如Join或者Aggregate查詢，數據庫涉及到大量的對磁盤的隨機訪問以及大量的網絡開銷，因此，將以后可能訪問的數據緩存到SSD上，由于SSD隨機訪問的開銷比磁盤訪問開銷小，因此能夠有效提升數據庫性能。

如圖4中所示，當數據量為5GB時，數據能夠完全放入內存，當請求到來時，數據能夠在內存中命中，因此，有SSD時和沒有SSD做緩存時候的性能幾乎一樣。隨著數據量的增大，數據不能夠完全在內存中進行，內存出現換進換出現象，若換出的chunk需要再次被訪問，若能夠在SSD中命中，那么數據庫的性能能夠在一定程度上得到提升。圖5，當數據量小于內存時，有緩存和無緩存時間無明顯差異；當數據量大于內存時，性能提升增幅從5%到25%，增長速度提升了20%。當數據量大于內存而小于SSD緩存的容量時，由于SSD緩存的命中使得FASTDB性能提升越來越快。而從100GB到250GB的時候，性能提升增幅從25%～34%，增長速度提升了9%。圖5中相對執行時間表示查詢執行過程中每隔40s取樣一次，獲得磁盤讀取的字節數。圖7中相對執行時間類似。隨著數據規模越來越大，由于FASTDB中采用分發數據到節點的方式進行查詢，分布式數據庫FASTDB中產生的網絡開銷也越來越大，網絡性能越來越差，此時網絡開銷成為主要瓶頸，因此性能增長幅度變緩。

圖4 不同數據量下有緩存和無緩存時查詢響應時間

圖5 不同數據量下有緩存的性能增長幅度

如圖7所示，在沒有緩存的情況下，從磁盤讀的字節數比有緩存時候的字節數多。這是因為二級緩存的存在，使chunk在內存中缺失時，一部分數據在SSD中命中，所以從磁盤讀的字節數減少，從而提升了查詢的性能。

圖6 有緩存下，不同數據量的數據產生的網絡開銷

圖7 有緩存和無緩存時，執行查詢磁盤讀的字節數

6 結語

本文針對陣列數據庫中復雜查詢效率低下的問題，提出了用新型硬件SSD作為數據庫二級緩存的方法。當進行復雜查詢，查找的chunk不在內存時，若在SSD中能夠命中，則能夠有效提升數據庫性能。結果表明，使用SSD作為二級緩存有34%左右的性能提升。隨著數據量的增大，網絡開銷也越來越大，分布式查詢中的主要瓶頸從I/O變為網絡開銷，下一步我們的研究方向是降低網絡開銷，進一步提升陣列數據庫的性能。

［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.

李建，崔辰州，何勃亮，等.天文數據庫回顧與展望［J］.天文學進展，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日

國家自然科學基金（編號：61462012，61562010，U1531246）；基于云計算的醫療信息管理系統關鍵技術研究及應用（編號：GY［2014］3018）；貴州省重大應用基礎研究項目（編號：JZ20142001，JZ20142001-01，JZ20142001-05）；貴州省教育廳自然科學項目（黔科合人才團隊字［2015］53號）；貴州大學研究生創新基金（院級）；貴州大學研究生創新基金（編號：2016049）資助。

楊慶，女，碩士研究生，研究方向：分布式數據庫、數據庫查詢優化。李暉，男，副教授，碩士生導師，研究方向：大規模數據管理與分析，高性能數據庫，云計算。陳梅，女，碩士生導師，研究方向：數據庫新技術、計算機應用技術。戴震宇，男，實驗師，研究方向：數據庫新技術、計算機應用技術。朱明，男，研究員，博士生導師，研究方向：射電天文學，天文大數據處理。