摘  要： 陣列數(shù)據(jù)庫系統(tǒng)是存儲(chǔ)和分析大規(guī)?？茖W(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%。

　　關(guān)鍵詞： 陣列數(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)測(cè)試（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組成。

　　從圖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 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ì)算過程為：

　　其中，表示數(shù)組的面積。由于有些數(shù)組的各個(gè)維度的長度不盡相同，因此使Chunk的各個(gè)維度邊長的比值與原數(shù)組的比值相同，可以減少在維度邊界產(chǎn)生的細(xì)小的Chunk總數(shù)，因?yàn)檫@些細(xì)小的Chunk有可能包含的都是空cell值（Chunk碎片），會(huì)增加內(nèi)存的開銷。

　　因此，根據(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)的基本配置信息。

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

　　Benchmark測(cè)試通常被譯成基準(zhǔn)測(cè)試，基準(zhǔn)測(cè)試是指通過設(shè)計(jì)科學(xué)的測(cè)試方法、測(cè)試工具和測(cè)試系統(tǒng)，實(shí)現(xiàn)對(duì)一類測(cè)試對(duì)象的某項(xiàng)性能指標(biāo)進(jìn)行定量的和可對(duì)比的測(cè)試。例如，對(duì)計(jì)算機(jī)CPU進(jìn)行浮點(diǎn)運(yùn)算、數(shù)據(jù)訪問的帶寬和延遲等指標(biāo)的基準(zhǔn)測(cè)試，可以使用戶清楚地了解每一款CPU的運(yùn)算性能及作業(yè)吞吐能力是否滿足應(yīng)用程序的要求。再如對(duì)數(shù)據(jù)庫管理系統(tǒng)的ACID（原子性、一致性、獨(dú)立性和持久性）、查詢時(shí)間和聯(lián)機(jī)事務(wù)處理能力等方面的性能指標(biāo)進(jìn)行基準(zhǔn)測(cè)試，有助于使用者挑選最符合自己需求的數(shù)據(jù)庫系統(tǒng)。作為一個(gè)能夠評(píng)估科學(xué)數(shù)據(jù)庫的Benchmark，其測(cè)試過程應(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ì)觀測(cè)值（Observations）進(jìn)行聚集操作和分組操作、對(duì)組（Groups）進(jìn)行復(fù)雜的幾何操作等)達(dá)到測(cè)試的目的。因此，SS-DB測(cè)試完整地包含以上四個(gè)階段，是較為可行的Benchmark測(cè)試方案。

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

　　實(shí)驗(yàn)測(cè)試數(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)測(cè)試過程，每次測(cè)試都為冷啟動(dòng)，這樣可以消除系統(tǒng)緩存帶來的誤差影響。表2展示了未優(yōu)化前和采用CLD算法后的Benchmark測(cè)試結(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)勢(shì)也隨之下降。如Q5查詢所涉及的表為數(shù)據(jù)集經(jīng)過分割后的子表，其目的在于把觀測(cè)值在空間上聚合成邊長為100的切片，并找出觀測(cè)值大于20的切片?？梢钥闯鲞@是相對(duì)比較復(fù)雜的一個(gè)操作，針對(duì)這種情況查詢性能結(jié)果并不理想，原因是其查詢響應(yīng)時(shí)間中CPU處理的時(shí)間比重增大，而通過CLD算法節(jié)省的Chunk讀取時(shí)間所占的比重減小，使總的性能下降。

　　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算法較適合的場(chǎng)景為中等或者輕量復(fù)雜度的分析查詢。

4 結(jié)論

　　本文提出的CLD算法改進(jìn)了原有SciDB的Chunk分割策略，通過SS-DB基準(zhǔn)測(cè)試取得了不錯(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)一步研究。

參考文獻(xià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. SS-DB： a standard science DBMS benchmark[R/OL]. （2012-08）[2015-03-05] http：//www.xldb.org/science-benchmark/.