一種基于多層塊區的數據存儲架構

閆振東

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

一種基于多層塊區的數據存儲架構

閆振東

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

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

云存儲；大容量數據；多層塊區

1 引 言

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

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

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

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

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

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

2 數據存儲的原理和架構

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

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

圖1 系統存儲架構Fig.1 The storage stucture

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

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

圖2 數據請求流程Fig.2 The stream of data request

3 數據訪問性能分析

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

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

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

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

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

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

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

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

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

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

對比公式（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］。這表明采用多層塊區架構的訪問時間至少不高于傳統架構，而且當訪問的數據塊個數n小于塊區總個數m時，L2＜L1。另外根據均值不等式定理有：

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

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

（a）用二層塊區架構的訪問時間一定不高于傳統架構的訪問時間。

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

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

4 塊區設計的一些思路

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

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

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

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

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

3）調整塊區。確定一級塊區的大小，即塊區中索引項的個數。假定設定為p，那么從隊列l中依次取出p個數據塊，將索引項置于一級塊區中。若隊列l的長度為len，如果p＜len的長度，則將len－p個數據塊的索引項置于二級塊區中。

4）進行本次數據訪問。完成后轉到步驟1）繼續下次訪問。

5 結束語

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

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

［1］ 劉越.云計算技術與應用［M］.北京：工業和信息化部電信研究院通信信息研究所，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］ 褚衍杰，徐正國.基于行為規律的搜索資源分配新算法［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－），男，山西晉中人，碩士研究生，工程師，主研方向：信息網絡，海量數據存儲方面的研究。

2014－07－28