閆振東

（中國電子科學研究院，北京100041）

一種基于多層塊區(qū)的數(shù)據(jù)存儲架構

閆振東

（中國電子科學研究院，北京100041）

借鑒了云存儲的的基本思想與技術平臺，針對大容量數(shù)據(jù)的海量和訪問頻度不同的特點，提出多層塊區(qū)概念，并研究基于此的數(shù)據(jù)存儲方法。對數(shù)據(jù)訪問性能的定量分析表明，合理劃分塊區(qū)能夠得到比傳統(tǒng)存儲方法更好的訪問效率。最后闡述了塊區(qū)設置的思路和方法。研究結果可為存儲系統(tǒng)的設計提供參考。

云存儲；大容量數(shù)據(jù)；多層塊區(qū)

1 引 言

現(xiàn)代網(wǎng)絡技術的快速發(fā)展，使得越來越多的系統(tǒng)應用對大容量數(shù)據(jù)的需求也越來越高。通過云技術來實施海量數(shù)據(jù)的處理和解決方案，目前主要有如下的云存儲平臺［1－3］：

1）Amazon云存儲器［1］：擁有與亞馬遜全球網(wǎng)絡站點相同的高可擴展性、高可靠性、快捷、數(shù)據(jù)存儲措施，而且所有的通信都采用了HTTPS加密協(xié)議。

2）IBM［2］：包括需要納入云計算中心的軟硬件資源，存儲服務器、交換機和路由器等網(wǎng)絡設備，軟件包括操作系統(tǒng)，中間件，數(shù)據(jù)庫等。

3）BigTable［3］：BigTable是Google公司用來存儲海量數(shù)據(jù)的分布式存儲系統(tǒng)，此系統(tǒng)可以將網(wǎng)頁存儲為分布式的、多維的而且有序的圖。

上述各云存儲平臺各有自己突出的特性，如亞馬遜平臺以可靠性和安全性著稱，IBM則通過二次開發(fā)，可擴展性比較好。然而對大容量數(shù)據(jù)存儲的訪問不一定保證具有更好的效率，比如Google公司的Google BigTable，以GFS［4］為基礎，提供了以Chunk分塊為存儲數(shù)據(jù)的物理單元，Master管理元數(shù)據(jù)信息的方法來進行分布式存儲。GFS基于數(shù)據(jù)“順序讀多，隨機讀少”的原則來設計系統(tǒng)，效率比較高。如果數(shù)據(jù)訪問的順序讀較少，而且具有一定訪問頻度，則GFS的訪問性能則會有較大差異，而且由于Chunk塊的設置相對固定，使得對不同類型數(shù)據(jù)訪問的處理方式不夠靈活。

基于上述原因，著眼于提高數(shù)據(jù)訪問性能，提出了一種海量數(shù)據(jù)存儲的“多層塊區(qū)”機制，用于實現(xiàn)數(shù)據(jù)存儲的高效管理與訪問。

2 數(shù)據(jù)存儲的原理和架構

傳統(tǒng)文件存儲系統(tǒng)的分布式結構采用單元數(shù)據(jù)服務器和多數(shù)據(jù)服務器模式。為了提高訪問性能，一般采用數(shù)據(jù)緩沖機制，即將經(jīng)常訪問的數(shù)據(jù)或者數(shù)據(jù)塊放在緩沖區(qū)中。如果所訪問的數(shù)據(jù)在緩沖區(qū)中，則直接返回緩沖區(qū)中數(shù)據(jù)，否則需要在磁盤中檢索數(shù)據(jù)塊。如果所訪問的數(shù)據(jù)不在緩沖中，則仍然需要在磁盤的數(shù)據(jù)塊中進行搜索。為了提高搜索性能，如圖1所示，可以采用多級分布式存儲體系，即多個分級塊區(qū)和相對應的多個數(shù)據(jù)塊區(qū)。分級塊區(qū)屬于索引塊區(qū)，其本身不含有數(shù)據(jù)信息，它存儲了可以索引的數(shù)據(jù)塊區(qū)元信息，比如塊區(qū)編號，塊區(qū)位置等等。數(shù)據(jù)塊區(qū)則存儲了實際的文件數(shù)據(jù)。塊區(qū)之后是存儲末端介質(zhì)，一般為磁盤陣列。每一個塊區(qū)都會被存儲于某一個磁盤陣列中。對于某個文件，它會被按照一定規(guī)則劃分為一個或多個數(shù)據(jù)塊區(qū)。相應的，每個數(shù)據(jù)塊區(qū)都會在某個索引塊區(qū)中有一個索引項，這樣管理程序可以根據(jù)索引項提供的元信息找到對應的數(shù)據(jù)塊。

對于這樣的存儲架構，所有的數(shù)據(jù)存取與讀取都會被轉化為對塊區(qū)的操作。分級塊區(qū)管理文件系統(tǒng)的元數(shù)據(jù)，數(shù)據(jù)塊區(qū)存儲實際的數(shù)據(jù)。每個文件被或多或少的分割成多個文件“塊”，每個文件“塊”都根據(jù)相應的策略存儲在某個數(shù)據(jù)塊區(qū)中。

圖1 系統(tǒng)存儲架構Fig.1 The storage stucture

當客戶需要訪問某個數(shù)據(jù)塊區(qū)的時候，首先要由管理程序在索引塊區(qū)（多級塊區(qū)）中查找數(shù)據(jù)塊區(qū)的位置，如果能找到則返回數(shù)據(jù)塊區(qū)元信息，否則返回錯誤信息。在索引塊區(qū)中查找數(shù)據(jù)塊區(qū)時，要從上層塊區(qū)到下層塊區(qū)逐層進行，即首先在一級塊區(qū)中查找所需塊區(qū)，如能找到則直接返回元信息，否則在二級塊區(qū)中進行查找。如還是找不到則繼續(xù)往下級塊區(qū)查找，如此反復此過程。當?shù)竭_最底層塊區(qū)的時候，如果還是找不到那么就認為訪問數(shù)據(jù)有誤，返回錯誤信息。此訪問流程如圖2所示。

圖中實線表示對塊區(qū)的訪問，而虛線表示得到訪問結果。第①步，管理程序首先搜索一級塊區(qū)，看所需數(shù)據(jù)塊索引是否在本塊區(qū)中。第②步則表示沒有在本塊區(qū)（一級塊區(qū)）找到索引。于是第③步管理程序開始搜索二級塊區(qū)。第④步也沒有得到結果。第⑤步終于在某級塊區(qū)中找到了數(shù)據(jù)塊的索引，于是在第⑥步時返回了數(shù)據(jù)塊元信息。在第⑦步，管理程序根據(jù)元信息直接訪問對應的數(shù)據(jù)塊，訪問結束。

圖2 數(shù)據(jù)請求流程Fig.2 The stream of data request

3 數(shù)據(jù)訪問性能分析

為了比較基于多層塊區(qū)的存儲架構和傳統(tǒng)的只有單層索引的存儲架構的性能區(qū)別，可以用某個具體定量指標來考量，即訪問時間。公式表示為：

其中T搜索時間表示管理程序在索引塊區(qū)中搜索數(shù)據(jù)塊元信息所需時間，而T讀寫時間則表示找到數(shù)據(jù)塊后，對數(shù)據(jù)塊進行讀或者寫所需時間。對于指標T讀寫時間來說，無論是哪種架構，對特定位置的數(shù)據(jù)進行讀寫所需時間都是一樣的，例如訪問磁盤位于p磁道、q扇區(qū)的塊數(shù)據(jù)所需時間是與架構無關的。故此，可以將T搜索時間作為定量指標來考量不同架構的數(shù)據(jù)訪問性能。

但T搜索時間不僅和存儲架構有關，還與訪問數(shù)據(jù)所在的索引位置有關。比如在索引塊區(qū)中，排在靠前位置的索引項所需的搜索時間就比排在靠后位置的索引項所需的搜索時間短。為了排除數(shù)據(jù)特殊性影響，無論是多層塊區(qū)架構還是傳統(tǒng)架構，可以用平均搜索長度ASL（Average Search Length）來衡量T搜索時間。

平均搜索長度［5］指的是為確定某數(shù)據(jù)塊在索引塊區(qū)中的索引位置而所需執(zhí)行的關鍵碼的比較次數(shù)的期望值。可以采用數(shù)據(jù)塊的塊序列號作為關鍵碼。對于一個含有n個索引項的塊區(qū)，搜索成功時的平均搜索長度是：

其中pi是搜索索引塊區(qū)中第i項的概率，ci是搜索到第i項所需的關鍵碼比較次數(shù)。根據(jù)使用的搜索方法不同，ci可以不同。假定使用順序搜索的方法，則搜索到第i個對象（i＝1，2，…，n），需要比較i次。因此ci＝i。那么搜索成功時的平均搜索長度則有如下公式：

假定每個索引項的搜索概率都相同，即pi＝1/n，那么此種情況下的ASLsucc可以計算為：

此公式的意義為，等概率情形下搜索到一個索引項的平均搜索長度為（n＋1）/2。

根據(jù)上述理論，下面分析在等概率情形下，傳統(tǒng)模型和多級塊區(qū)模型的平均搜索長度。假定兩種模型的數(shù)據(jù)塊區(qū)大小和數(shù)量均相同，而且索引塊區(qū)以及索引項的長度也都相同，并且都是使用順序搜索方法。定義m為系統(tǒng)中數(shù)據(jù)塊的總個數(shù)，則系統(tǒng)中索引塊區(qū)中所有索引項的個數(shù)也為m。n為要搜索的數(shù)據(jù)塊個數(shù)，且有n≤m。

在傳統(tǒng)模型中，由于采用了單層索引架構，故而對任意一個索引項的平均搜索長度都是相同的，由公式（3）得到均為（m＋1）/2。那么訪問N個數(shù)據(jù)塊的總搜索長度即為n*（m＋1）/2。所以有下列公式：

如果采用多級塊區(qū)模型，則首先需要劃分塊區(qū)的層數(shù)，以及每層塊區(qū)的索引項個數(shù)。為了簡化討論，采用二層塊區(qū)來進行分析，即系統(tǒng)有一級塊區(qū)和二級塊區(qū)。同時定義一級塊區(qū)的的索引項個數(shù)為p，那么二級塊區(qū)索引項的個數(shù)即為m－p。由于所訪問的數(shù)據(jù)塊索引項位于不同層級，故而對其訪問的搜索長度也是不同的。具體來說，如果索引項位于一級塊區(qū)，那么此索引項的平均搜索長度即為（P＋1）/2，于是p個索引項的總搜索長度為p×（p＋1）/2。如果索引項位于二級塊區(qū)中，且p≤n，那么管理程序首先要在一級塊區(qū)中查找此索引項，查找長度為固定的p，然后在二級塊區(qū)的m－p個索引項中查找，查找平均長度為（m－p＋1）/2。那么對于（n－p）個索引項來說，在二級塊區(qū)中的總搜索長度即為（n－p）×［（m－p＋1）/2＋p］，從而得到n個數(shù)據(jù)塊的總搜索長度為：

對比公式（4），可得用L1表示的L2，即

分析公式（6），由于p＞0且m≥n，故而p×（m－n）/2≥n，同時由于p≤n，故而p×（m－n）/2≤n×（m－n）/2＝L1，于是可確定L2∈［0，L1］。這表明采用多層塊區(qū)架構的訪問時間至少不高于傳統(tǒng)架構，而且當訪問的數(shù)據(jù)塊個數(shù)n小于塊區(qū)總個數(shù)m時，L2＜L1。另外根據(jù)均值不等式定理有：

當且僅當m＞n，n＞0，且n＝m－n時成立。

綜合上述（4）（6）（7）式，可得如下分析結果：

（a）用二層塊區(qū)架構的訪問時間一定不高于傳統(tǒng)架構的訪問時間。

（b）采用二層塊區(qū)架構時，位于一級塊區(qū)的數(shù)據(jù)塊個數(shù)越多，則訪問時間越少。

（c）采用二層塊區(qū)架構時，如果訪問的數(shù)據(jù)塊個數(shù)等于總數(shù)據(jù)塊個數(shù)，那么訪問時間和傳統(tǒng)架構一樣；如果訪問的數(shù)據(jù)塊個數(shù)恰好等于總數(shù)據(jù)塊個數(shù)的一半，而且所訪問的數(shù)據(jù)塊均位于一級塊區(qū)時，所需時間比傳統(tǒng)架構最少。

4 塊區(qū)設計的一些思路

通過上節(jié)分析，可以得知數(shù)據(jù)訪問性能和數(shù)據(jù)塊區(qū)總數(shù)、訪問塊區(qū)數(shù)量、塊區(qū)大小設置有關。如果訪問塊區(qū)數(shù)量和系統(tǒng)的數(shù)據(jù)塊區(qū)總數(shù)相同，那么多層塊區(qū)方法的性能最差；在二層塊區(qū)架構中，如果所訪問的數(shù)據(jù)塊均不在一級塊區(qū)中時，此方法性能也是最差的。

根據(jù)公式（5），在總數(shù)據(jù)塊區(qū)個數(shù)m固定的情況下，所訪問數(shù)據(jù)塊個數(shù)n越小，而其中位于一級塊區(qū)的數(shù)據(jù)塊個數(shù)p越多，則方法性能要更好。然而，由于p≤n，且n≤m，導致三者有相互制約性，也就是說當n大到與m相同時，方法性能反而最差。而根據(jù)公式（7），在p＝n的情況下，如果n＝m/2，那么L1－L2可以得到最大值，表示兩種方法的訪問性能差別最大。

在實際的數(shù)據(jù)訪問時，可以根據(jù)需要動態(tài)調(diào)整不同層級塊區(qū)的大小，以及塊區(qū)索引項的內(nèi)容，以便使得每次訪問都能得到較好的性能。于是，塊區(qū)設計的基本步驟如下：

1）首先確定此次訪問所需數(shù)據(jù)塊個數(shù)。一般來說這個數(shù)值遠遠小于總數(shù)據(jù)塊區(qū)個數(shù)，如果超過則只取總數(shù)據(jù)塊個數(shù)的一半。

2）根據(jù)數(shù)據(jù)訪問的特點，確定或者預測這些數(shù)據(jù)塊的訪問頻度，并且按照頻度高低將數(shù)據(jù)塊排序，形成隊列l(wèi)。本步驟的算法不限于此，可借鑒于資源分配新算法［6］等。

3）調(diào)整塊區(qū)。確定一級塊區(qū)的大小，即塊區(qū)中索引項的個數(shù)。假定設定為p，那么從隊列l(wèi)中依次取出p個數(shù)據(jù)塊，將索引項置于一級塊區(qū)中。若隊列l(wèi)的長度為len，如果p＜len的長度，則將len－p個數(shù)據(jù)塊的索引項置于二級塊區(qū)中。

4）進行本次數(shù)據(jù)訪問。完成后轉到步驟1）繼續(xù)下次訪問。

5 結束語

在提出多層塊區(qū)存儲方法的基礎上，為考量數(shù)據(jù)訪問性能，以平均搜索長度為主要指標對基于二層塊區(qū)的情形進行了數(shù)學理論推導，并根據(jù)推導的數(shù)學分析結果，得出了塊區(qū)設計的一些原則以及方法，這些都可以為存儲系統(tǒng)設計提供有益的參考。

但由于多層塊區(qū)的數(shù)據(jù)訪問效率不僅與存儲架構以及塊區(qū)設計方法有關，還與所訪問數(shù)據(jù)的特性有密切關聯(lián)，即對一個設計好的塊區(qū)架構，不一定對所有的訪問都具有最優(yōu)的訪問性能。同時，塊區(qū)設計層數(shù)越多，所訪問數(shù)據(jù)的特性越復雜，則數(shù)學理論推導的模型也越復雜，故此處未對三層以上的、具有復雜訪問頻度的數(shù)據(jù)塊性能進行建模及分析討論，相關工作有待后續(xù)跟進。

［1］ 劉越.云計算技術與應用［M］.北京：工業(yè)和信息化部電信研究院通信信息研究所，2009.

［2］ H Zhang，A Goel，R Govindan.Using the small world model to improve freenet performance［C］.Twenty－First Annual Joint Conference of the IEEE Computer and Communications Societies.Proceedings.IEEE.America：IEEE infocom，2002.

［3］ P Bak.How Nature Works：The Science of Self－Organized Criticality［M］.Newyork：Copernicus Inc.1996.

［4］ Sanjay Ghemawat，Howard Gobioff，Shun－Tak Leung.The Google File System［M］.America：Google lnc.2003.

［5］ LRodero－Merino，A Fernández Anta，L López.Estimation of the Average Search Length of Random Walks in Power－Law Networks［C］.IEEE Latin America Transactions.Latin America：IEEE，2007.

［6］ 褚衍杰，徐正國.基于行為規(guī)律的搜索資源分配新算法［J］.電訊技術，2014，54（2）：195－200.

A Structure of Data Storage Based on Multi－Level Blocks

Yan Zhendong
（China Academy of Electronics and Information Technology，Beijing 100041，China）

Based on the ideology and technical platform of cloud－storage，aiming at the characteristics ofmass data which are quite large and are accessed with different frequency，the concept ofmulti－level block is brought up and the storage method is put forward as well.The quantitative analysis for access performance of the data shows that dividing blocks reasonably can get better access efficiency than classic method does.Some principles are demonstrated over block setup and the conclusions can provide reference for the design of storage system.

Cloud storage；Mass data；Multi－level block

10.3969/j.issn.1002－2279.2015.01.015

TP315

B

1002－2279（2015）01－0052－03

閆振東（1981－），男，山西晉中人，碩士研究生，工程師，主研方向：信息網(wǎng)絡，海量數(shù)據(jù)存儲方面的研究。

2014－07－28