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

　　關鍵詞： 陣列數(shù)據(jù)庫,；存儲塊分割,；查詢分析

0 引言

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

　　以SciDB[3-5]為代表的陣列數(shù)據(jù)庫系統(tǒng)，其主要應用領域為科學領域中超大規(guī)模陣列數(shù)據(jù)的存儲和分析，其設計初衷是解決科學研究中數(shù)據(jù)量大,、數(shù)據(jù)世襲等科學問題,。通過SciDB等陣列數(shù)據(jù)庫系統(tǒng)可以直接對科學數(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)能夠為科學應用領域提供大規(guī)模的復雜分析支持,，用以滿足日益增長的需求,。它采用數(shù)組數(shù)據(jù)模型（一種具有數(shù)學中數(shù)組特性的數(shù)據(jù)模型），支持多維數(shù)據(jù),，其基本組成單元是cell,，各個cell有相同的值類型。cell的值可以是一個或多個標量值,，也可以是一個或多個數(shù)組,。

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

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

　　陣列數(shù)據(jù)庫（Array DBMS）是以陣列（Array,，亦稱作數(shù)組）作為數(shù)據(jù)庫“一等公民”,。一個典型的3維數(shù)組結構如圖1所示。通過數(shù)組模型可以實現(xiàn)數(shù)學概念中數(shù)組的一系列特定操作,，比如特征值提取,、交叉試驗等，這些都是科學家分析和處理科學數(shù)據(jù)所需要進行的操作[6-7],。SciDB是一種采用無共享分布式架構、擁有可靠的消息和任務機制保障系統(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é)調節(jié)點和工作節(jié)點兩種類型,。協(xié)調節(jié)點在每個集群中只存在于一臺物理機上,，它主要負責協(xié)調分發(fā)任務和收集各個節(jié)點返回的結果，同時進行結果整合和處理,，并返回給客戶端,。集群中剩余的節(jié)點成為工作節(jié)點，主要負責本地數(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大小會影響內存以及查詢性能,。例如,，一個Chunk大小如果分配過大的話，Chunk范圍內的cell總數(shù)就會增多,，那么在進行查詢分析時會增加定位cell的響應時間,，影響查詢性能；反之,，如果一個Chunk大小分配過小,，那么在有很多cell出現(xiàn)空值的情況下，由于每個cell都在內存中進行映射,，而實際上并不是所有的cell都有意義,，因此造成內存壓力增大，甚至超過可用內存,，進而引發(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ù)組有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碎片），會增加內存的開銷,。

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

3 實驗結果與分析

　　3.1 實驗環(huán)境

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

　　3.2 實驗設計

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

　　3.3 結果與性能分析

　　實驗測試數(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測試結果。

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

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

4 結論

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

參考文獻

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