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

　　關(guān)鍵詞： 陣列數(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ù)進行分析，省略了數(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）的分割機制，針對其固有存儲塊分割機制的缺陷進行分析，提出一種改進的存儲塊的分割優(yōu)化方案，并通過基準(zhǔn)測試（Benchmark）實驗與未優(yōu)化的分割策略進行對比。

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ù)所需要進行的操作[6-7]。SciDB是一種采用無共享分布式架構(gòu)、擁有可靠的消息和任務(wù)機制保障系統(tǒng)的陣列數(shù)據(jù)庫；它采用了一種一次寫入多次讀取型的多維數(shù)組模型，并通過一種高效的版本控制方法，保證數(shù)組數(shù)據(jù)的動態(tài)更新和高效壓縮存儲；同時通過一種數(shù)組分塊機制（Chunking）實現(xiàn)了數(shù)據(jù)的分布式存儲。

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

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

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的計算過程為：

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

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

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

　　3.1 實驗環(huán)境

　　實驗是在輕量級云平臺Proxmox上完成的。Proxmox采用KVM作為其虛擬化方案，本實驗構(gòu)建了6個KVM虛擬機節(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é)點的基本配置信息。

　　3.2 實驗設(shè)計

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

　　表2中未加括號的數(shù)值為優(yōu)化前各個查詢的響應(yīng)時間，括號內(nèi)的數(shù)值為優(yōu)化后的響應(yīng)時間。總體來看，優(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讀取時間所占的比重減小，使總的性能下降。

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

4 結(jié)論

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

參考文獻

　　[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/.