邱能俊，陳梅，李暉

（1.貴州大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，貴州貴陽550025；2.貴州大學(xué)貴州省先進(jìn)計算與醫(yī)療信息服務(wù)工程實驗室，貴州貴陽550025）

陣列數(shù)據(jù)庫系統(tǒng)的存儲塊分割策略研究*

邱能俊1，2，陳梅1，2，李暉1，2

（1.貴州大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，貴州貴陽550025；2.貴州大學(xué)貴州省先進(jìn)計算與醫(yī)療信息服務(wù)工程實驗室，貴州貴陽550025）

陣列數(shù)據(jù)庫系統(tǒng)是存儲和分析大規(guī)?？茖W(xué)數(shù)據(jù)的常用技術(shù)方案。目前主流的陣列數(shù)據(jù)庫中存儲塊分割策略采用固定邊長作為塊的邊界，若邊長過大會增加查詢分析時定位Cell的時間，反之則產(chǎn)生過多的小塊增加內(nèi)存開銷。本文提出一種改進(jìn)的Chunk邊長分割算法CLD，其通過減少讀取數(shù)據(jù)時的磁道數(shù)以及預(yù)取技術(shù)提高陣列數(shù)據(jù)庫系統(tǒng)的性能。在陣列數(shù)據(jù)庫系統(tǒng)SciDB集群上的實驗表明，在最優(yōu)情況下系統(tǒng)性能提升了10.9%。

陣列數(shù)據(jù)庫；存儲塊分割；查詢分析

0 引言

在商業(yè)領(lǐng)域，基于關(guān)系模型的數(shù)據(jù)庫管理系統(tǒng)（RDBMS，如SQLServer等）有廣泛的應(yīng)用，且取得了巨大的成功。但是，科學(xué)領(lǐng)域收集的數(shù)據(jù)結(jié)構(gòu)與傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)有很大不同，科學(xué)數(shù)據(jù)是以陣列為數(shù)據(jù)模型，與自然界中的數(shù)組模型類似。而商業(yè)數(shù)據(jù)管理系統(tǒng)適合關(guān)系型數(shù)據(jù)的處理，在應(yīng)用到科學(xué)領(lǐng)域時將面臨著許多難以克服的問題。同時，關(guān)系型數(shù)據(jù)庫管理系統(tǒng)在存儲和處理多維數(shù)組數(shù)據(jù)時改變了數(shù)據(jù)的天然數(shù)組結(jié)構(gòu)，使后續(xù)的數(shù)據(jù)管理過程變得極其復(fù)雜[1-2]，因此，RDBMS已經(jīng)不能滿足科學(xué)數(shù)據(jù)處理的需求。

以SciDB[3-5]為代表的陣列數(shù)據(jù)庫系統(tǒng)，其主要應(yīng)用領(lǐng)域為科學(xué)領(lǐng)域中超大規(guī)模陣列數(shù)據(jù)的存儲和分析，其設(shè)計初衷是解決科學(xué)研究中數(shù)據(jù)量大、數(shù)據(jù)世襲等科學(xué)問題。通過SciDB等陣列數(shù)據(jù)庫系統(tǒng)可以直接對科學(xué)數(shù)據(jù)進(jìn)行分析，省略了數(shù)據(jù)從存儲模塊到分析模塊之間的過渡，這是其與RDBMS最主要的區(qū)別之一。陣列數(shù)據(jù)庫系統(tǒng)SciDB在開源社區(qū)力量的幫助下快速發(fā)展，其有商業(yè)版和社區(qū)版本，社區(qū)版本已經(jīng)更新到14.12。與傳統(tǒng)RDBMS不同的是，SciDB這樣的陣列數(shù)據(jù)庫系統(tǒng)能夠為科學(xué)應(yīng)用領(lǐng)域提供大規(guī)模的復(fù)雜分析支持，用以滿足日益增長的需求。它采用數(shù)組數(shù)據(jù)模型（一種具有數(shù)學(xué)中數(shù)組特性的數(shù)據(jù)模型），支持多維數(shù)據(jù)，其基本組成單元是cell，各個cell有相同的值類型。cell的值可以是一個或多個標(biāo)量值，也可以是一個或多個數(shù)組。

本文首先以SciDB為例介紹其自身實現(xiàn)的存儲塊（Chunk）的分割機(jī)制，針對其固有存儲塊分割機(jī)制的缺陷進(jìn)行分析，提出一種改進(jìn)的存儲塊的分割優(yōu)化方案，并通過基準(zhǔn)測試（Benchmark）實驗與未優(yōu)化的分割策略進(jìn)行對比。

1 陣列數(shù)據(jù)庫SciDB的存儲塊分割規(guī)則

陣列數(shù)據(jù)庫（Array DBMS）是以陣列（Array，亦稱作數(shù)組）作為數(shù)據(jù)庫“一等公民”。一個典型的3維數(shù)組結(jié)構(gòu)如圖1所示。通過數(shù)組模型可以實現(xiàn)數(shù)學(xué)概念中數(shù)組的一系列特定操作，比如特征值提取、交叉試驗等，這些都是科學(xué)家分析和處理科學(xué)數(shù)據(jù)所需要進(jìn)行的操作[6-7]。SciDB是一種采用無共享分布式架構(gòu)、擁有可靠的消息和任務(wù)機(jī)制保障系統(tǒng)的陣列數(shù)據(jù)庫；它采用了一種一次寫入多次讀取型的多維數(shù)組模型，并通過一種高效的版本控制方法，保證數(shù)組數(shù)據(jù)的動態(tài)更新和高效壓縮存儲；同時通過一種數(shù)組分塊機(jī)制（Chunking）實現(xiàn)了數(shù)據(jù)的分布式存儲。

SciDB可以是單節(jié)點也可以是分布式的。在分布式環(huán)境中，它把許多廉價的計算機(jī)組成一個集群，每個集群上可以有一個或者多個數(shù)據(jù)庫實例，每個數(shù)據(jù)庫實例僅處理存儲在本地的數(shù)據(jù)。SciDB將節(jié)點分成了協(xié)調(diào)節(jié)點和工作節(jié)點兩種類型。協(xié)調(diào)節(jié)點在每個集群中只存在于一臺物理機(jī)上，它主要負(fù)責(zé)協(xié)調(diào)分發(fā)任務(wù)和收集各個節(jié)點返回的結(jié)果，同時進(jìn)行結(jié)果整合和處理，并返回給客戶端。集群中剩余的節(jié)點成為工作節(jié)點，主要負(fù)責(zé)本地數(shù)據(jù)的存儲和分析。而Chunking則是SciDB中用于分配存儲塊的機(jī)制，其實現(xiàn)原理是把載入到SciDB中的數(shù)組分布到各個節(jié)點的SciDB實例（instance）上，每個節(jié)點通過自身的引擎對子數(shù)組進(jìn)行分塊，并且把分成的Chunk以輪詢算法重新分布到集群的所有節(jié)點中。在這個過程中，每個SciDB節(jié)點需要對分配到本地的子數(shù)組進(jìn)行Chunk的分割，而Chunk的大小范圍由數(shù)組的每個維度的長度組成，如圖2所示，Chunk的范圍大小由數(shù)組的兩個維度i、j組成，i和j的長度分別為i和j維度上cell的個數(shù)，圖2中所示每個Chunk的i長度為5，j長度為8，因此Chunk范圍大小為40，表示一個Chunk由40個cell組成。

圖1 三維數(shù)組結(jié)構(gòu)

從圖2可以看出一個Chunk大小由數(shù)組的所有維度邊長大小所決定，因此Chunk大小的確定取決于每個維度的大小選擇。而數(shù)組的Chunk大小會影響內(nèi)存以及查詢性能。例如，一個Chunk大小如果分配過大的話，Chunk范圍內(nèi)的cell總數(shù)就會增多，那么在進(jìn)行查詢分析時會增加定位cell的響應(yīng)時間，影響查詢性能；反之，如果一個Chunk大小分配過小，那么在有很多cell出現(xiàn)空值的情況下，由于每個cell都在內(nèi)存中進(jìn)行映射，而實際上并不是所有的cell都有意義，因此造成內(nèi)存壓力增大，甚至超過可用內(nèi)存，進(jìn)而引發(fā)其他異常錯誤。由此可見，合理選擇Chunk大小可在某種程度上提升SciDB數(shù)據(jù)庫的性能。在SciDB固有的存儲塊Chunk的分割策略中把每個Chunk的各個維度大小固定為1 000 000，其并沒有考慮以上問題。針對SciDB原有的存儲塊Chunk分割策略，本文提出一種改進(jìn)的Chunk大小分割方案，即塊長度分割（Chunk Length Division，CLD）算法。

圖2 SciDB中塊Chunk的范圍

2 CLD算法

CLD算法的基本思想是根據(jù)載入的數(shù)據(jù)總量計算出磁盤每個柱面的容量大小，再由操作系統(tǒng)中的block大小得出初步的Chunk總數(shù)，接著取原數(shù)組中的每個維度長度的乘積與Chunk總數(shù)的比值得出Chunk的面積（cell總數(shù)），再根據(jù)原數(shù)組中各個維度的長度比值得出Chunk中的每條邊長的比值，最后得出Chunk的每個維度長度。假設(shè)數(shù)組有n個維度，算法的符號定義如下：

SIZE：數(shù)組中的總數(shù)據(jù)大小。

d：存儲總數(shù)據(jù)所需的最小磁道數(shù)。

Di：數(shù)組的第i個維度的邊長，i=1，2，…，N。

ci：Chunk的第i維度的邊長。

B：每個磁道能存儲的block總數(shù)。

b：每個Chunk的cell總數(shù)。

s：每個Chunk的面積。

size：每個cell的大小。

則存儲總數(shù)據(jù)所需的最小磁道數(shù)為：

則每個Chunk的面積s的計算過程為：

因此，根據(jù)式（1）、（2）、（3）可以組成多元一次方程組，求解得出每個Chunk的維度邊長的一組整數(shù)解。下面通過Benchmark對采用CLD算法后SciDB的內(nèi)存和查詢性能進(jìn)行實驗分析。

3 實驗結(jié)果與分析

3.1 實驗環(huán)境

實驗是在輕量級云平臺Proxmox上完成的。Proxmox采用KVM作為其虛擬化方案，本實驗構(gòu)建了6個KVM虛擬機(jī)節(jié)點的集群，每個節(jié)點的CPU型號為Intel（R）Xeon（R）E5-2620，2.00 GHz。集群中有1臺是協(xié)調(diào)節(jié)點，其內(nèi)存為32 GB，硬盤大小為200 GB；剩余5臺為工作節(jié)點，其內(nèi)存為8 GB，硬盤大小為200 GB。表1為每個SciDB節(jié)點的基本配置信息。

表1 各個節(jié)點配置信息

3.2 實驗設(shè)計

Benchmark測試通常被譯成基準(zhǔn)測試，基準(zhǔn)測試是指通過設(shè)計科學(xué)的測試方法、測試工具和測試系統(tǒng)，實現(xiàn)對一類測試對象的某項性能指標(biāo)進(jìn)行定量的和可對比的測試。例如，對計算機(jī)CPU進(jìn)行浮點運算、數(shù)據(jù)訪問的帶寬和延遲等指標(biāo)的基準(zhǔn)測試，可以使用戶清楚地了解每一款CPU的運算性能及作業(yè)吞吐能力是否滿足應(yīng)用程序的要求。再如對數(shù)據(jù)庫管理系統(tǒng)的ACID（原子性、一致性、獨立性和持久性）、查詢時間和聯(lián)機(jī)事務(wù)處理能力等方面的性能指標(biāo)進(jìn)行基準(zhǔn)測試，有助于使用者挑選最符合自己需求的數(shù)據(jù)庫系統(tǒng)。作為一個能夠評估科學(xué)數(shù)據(jù)庫的Benchmark，其測試過程應(yīng)該包括模擬所有的科學(xué)數(shù)據(jù)管理階段，這些階段包括：原始圖像數(shù)據(jù)或傳感數(shù)據(jù)的獲取，這是原始數(shù)據(jù)的獲取階段；對原始數(shù)據(jù)進(jìn)行相關(guān)查詢階段；把原始數(shù)據(jù)Cook成能夠?qū)С龅臄?shù)據(jù)集階段；對Cook后的數(shù)據(jù)進(jìn)行查詢處理階段。本實驗采用SS-DB[8]，它是一個標(biāo)準(zhǔn)的科學(xué)數(shù)據(jù)庫管理系統(tǒng)的Benchmark，其用途是利用一系列相對復(fù)雜的用戶自定義程序模擬操作面向數(shù)組的數(shù)據(jù)。SS-DB是通過模擬天文工作中的動作(如提取原始圖像的像素、對觀測值（Observations）進(jìn)行聚集操作和分組操作、對組（Groups）進(jìn)行復(fù)雜的幾何操作等)達(dá)到測試的目的。因此，SS-DB測試完整地包含以上四個階段，是較為可行的Benchmark測試方案。

3.3 結(jié)果與性能分析

實驗測試數(shù)據(jù)為Tiny、Small和Normal三種數(shù)據(jù)集，其中Tiny數(shù)據(jù)集的大小為93 KB，總記錄數(shù)為2 000條；Small數(shù)據(jù)集的大小為13 GB，總記錄條數(shù)約為2.8億條；Normal數(shù)據(jù)集的大小為123 GB，總記錄數(shù)約為16億條。對Tiny、Small和Normal三種數(shù)據(jù)集分別進(jìn)行6次循環(huán)測試過程，每次測試都為冷啟動，這樣可以消除系統(tǒng)緩存帶來的誤差影響。表2展示了未優(yōu)化前和采用CLD算法后的Benchmark測試結(jié)果。

表2中未加括號的數(shù)值為優(yōu)化前各個查詢的響應(yīng)時間，括號內(nèi)的數(shù)值為優(yōu)化后的響應(yīng)時間?？傮w來看，優(yōu)化后的存儲塊分割策略比優(yōu)化前在查詢分析性能上有所改善，最優(yōu)情況提高了10.9%。而分析Q1～Q6查詢可知，其查詢的復(fù)雜度由小到大，且這些分析查詢語句都是CPU密集型的，對于以Chunk為基本處理單元的SciDB來說，Chunk存儲塊的大小對查詢分析的性能有比較大的影響。但是，從實驗結(jié)果可以發(fā)現(xiàn)，隨著查詢復(fù)雜度的提升，CLD算法帶來的優(yōu)勢也隨之下降。如Q5查詢所涉及的表為數(shù)據(jù)集經(jīng)過分割后的子表，其目的在于把觀測值在空間上聚合成邊長為100的切片，并找出觀測值大于20的切片?？梢钥闯鲞@是相對比較復(fù)雜的一個操作，針對這種情況查詢性能結(jié)果并不理想，原因是其查詢響應(yīng)時間中CPU處理的時間比重增大，而通過CLD算法節(jié)省的Chunk讀取時間所占的比重減小，使總的性能下降。

表2 Benchmark測試結(jié)果

CLD算法本質(zhì)上是根據(jù)適合操作系統(tǒng)讀寫的block大小來設(shè)計Chunk的長度范圍，它減少了磁盤獲取數(shù)據(jù)需要掃描的磁道數(shù)，進(jìn)而改善系統(tǒng)的性能。從實驗結(jié)果可以看出，雖然應(yīng)用CLD算法能夠改善系統(tǒng)的性能，但是面對非常復(fù)雜的查詢，其復(fù)雜分析時的計算時間比重會增大，通過CLD算法取得的性能表現(xiàn)也會隨之下降。

因此，CLD算法較適合的場景為中等或者輕量復(fù)雜度的分析查詢。

4 結(jié)論

本文提出的CLD算法改進(jìn)了原有SciDB的Chunk分割策略，通過SS-DB基準(zhǔn)測試取得了不錯的效果，最優(yōu)情況下系統(tǒng)性能可以提升10.9%。CLD算法的主要思想是通過減少磁道訪問次數(shù)以及預(yù)取技術(shù)減少Chunk讀取的時間。然而算法中的參數(shù)并沒有進(jìn)行很好的調(diào)整，因此算法還有提高的可能性。另一方面，CLD算法針對復(fù)雜度較高的科學(xué)查詢，如多表連接、大矩陣計算等效果并不理想。因此，如何提升復(fù)雜查詢的性能需要進(jìn)一步研究。

[1]HEY T，TANSLEY S，TOLLE K.The fourth paradigm：data-intensive scientific discoveries[J].Microsoft Research，2009（1）：153-164.

[2]GRAY J，LIU T D，DEWITT D，et al.Scientific data management in the coming decade[R].2005.

[3]STONEBRAKER M，BECLA J，DEWITT D，et al.Requirements for science data bases and SciDB[C].Conference on Innovative Data Systems Research（CIDR）Perspectives，2009：7-16.

[4]CUDRE-MAUROUX P，KIMURA H，CUDRE-MAUROUX P，et al.A demonstration of SciDB：a science-oriented DBMS[C].VLDB，2009，1534-1537.

[5]STONEBRAKER M，BROWN P，POLIAKOV A，et al.The architecture of SciDB[C].Scientific and Statistical Database Management（SSDBM），2011：1-16.

[6]CHANG C，ACHARYA A，SUSSMAN A，et al.T2：a customizable parallel database for multi-dimensional data[C]. Proceedings of ACM SIGMOD Record，1998：58-66.

[7]STONEBRAKER M，BEAR C，CETINTEMEL U，et al. Zdonik：one size fits all？Part 2：benchmarking studies[C]. CIDR，2007：173-184.

[8]CUDRE-MAUROUX P，KIMURA H，LIM K-T，et al.SSDB：a standard science DBMS benchmark[R/OL].（2012-08）[2015-03-05]http：//www.xldb.org/science-benchmark/.

The research of chunk segmentation strategy for array database system

Qiu Nengjun1，2，Chen Mei1，2，Li Hui1，2
（1.College of Computer Science and Technology，Guizhou University，Guiyang 550025，China；2.Guizhou Engineering Laboratory for Advanced Computing and Medical Information Services，Guizhou University，Guiyang 550025，China）

Array database is often used for massive scientific data storage and analysis.The major array database systems primarily employ the fixed length strategy for chunk segmentation.If the length of the chunk is too big，it will increase the overhead of cell location during query analysis.On the contrary，it will make too many small chunks and increase the memory overhead.This paper proposed a chunk length divide（CLD）algorithm to improve the performance of array database by reducing the number of track and prefetching technique when the data is read.Based on the evaluation of array database SciDB cluster，our approach lead the performance of SciDB improved about 10.9%under the optimal conditions.

array database；storage chunk；query analysis

TP392

A

1674-7720（2015）09-0026-03

2015-03-06）

邱能俊（1989-），男，碩士，主要研究方向：分布式數(shù)據(jù)庫、云計算。

國家自然科學(xué)基金（61462012）；貴州省應(yīng)用基礎(chǔ)研究重大項目子課題（黔科合JZ字[2014]2001-05）；貴州大學(xué)研究生創(chuàng)新基金（研理工2014010）

陳梅（1964-），女，教授，主要研究方向：數(shù)據(jù)庫新技術(shù)、計算機(jī)應(yīng)用技術(shù)。

李暉（1982-），通信作者，男，博士，副教授，主要研究方向：大規(guī)模數(shù)據(jù)管理與分析，高性能數(shù)據(jù)庫，云計算。E-mail：cse.HuiLi@gzu.edu.cn。