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

邱能俊，陳梅，李暉

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 SciDB中塊Chunk的范圍

2 CLD算法

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

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

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

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

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

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

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

s：每個(gè)Chunk的面積。

size：每個(gè)cell的大小。

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

則每個(gè)Chunk的面積s的計(jì)算過程為：

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境

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

表1 各個(gè)節(jié)點(diǎn)配置信息

3.2 實(shí)驗(yàn)設(shè)計(jì)

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

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

實(shí)驗(yàn)測試數(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億條。對(duì)Tiny、Small和Normal三種數(shù)據(jù)集分別進(jìn)行6次循環(huán)測試過程，每次測試都為冷啟動(dòng)，這樣可以消除系統(tǒng)緩存帶來的誤差影響。表2展示了未優(yōu)化前和采用CLD算法后的Benchmark測試結(jié)果。

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

表2 Benchmark測試結(jié)果

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

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

4 結(jié)論

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

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

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

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

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