陣列數據庫系統的存儲塊分割策略研究*

邱能俊，陳梅，李暉

（1.貴州大學計算機科學與技術學院，貴州貴陽550025；2.貴州大學貴州省先進計算與醫療信息服務工程實驗室，貴州貴陽550025）

陣列數據庫系統的存儲塊分割策略研究*

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

（1.貴州大學計算機科學與技術學院，貴州貴陽550025；2.貴州大學貴州省先進計算與醫療信息服務工程實驗室，貴州貴陽550025）

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

陣列數據庫；存儲塊分割；查詢分析

0 引言

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

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

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

1 陣列數據庫SciDB的存儲塊分割規則

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

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

圖1 三維數組結構

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

圖2 SciDB中塊Chunk的范圍

2 CLD算法

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

SIZE：數組中的總數據大小。

d：存儲總數據所需的最小磁道數。

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

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

B：每個磁道能存儲的block總數。

b：每個Chunk的cell總數。

s：每個Chunk的面積。

size：每個cell的大小。

則存儲總數據所需的最小磁道數為：

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

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

3 實驗結果與分析

3.1 實驗環境

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

表1 各個節點配置信息

3.2 實驗設計

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

3.3 結果與性能分析

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

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

表2 Benchmark測試結果

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

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

4 結論

本文提出的CLD算法改進了原有SciDB的Chunk分割策略，通過SS-DB基準測試取得了不錯的效果，最優情況下系統性能可以提升10.9%。CLD算法的主要思想是通過減少磁道訪問次數以及預取技術減少Chunk讀取的時間。然而算法中的參數并沒有進行很好的調整，因此算法還有提高的可能性。另一方面，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.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-），男，碩士，主要研究方向：分布式數據庫、云計算。

國家自然科學基金（61462012）；貴州省應用基礎研究重大項目子課題（黔科合JZ字[2014]2001-05）；貴州大學研究生創新基金（研理工2014010）

陳梅（1964-），女，教授，主要研究方向：數據庫新技術、計算機應用技術。

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