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

閆振東

（中國電子科學(xué)研究院，北京100041）

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

閆振東

（中國電子科學(xué)研究院，北京100041）

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

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

1 引 言

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

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

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

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

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

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

2 數(shù)據(jù)存儲(chǔ)的原理和架構(gòu)

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

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

圖1 系統(tǒng)存儲(chǔ)架構(gòu)Fig.1 The storage stucture

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

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

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

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

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

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

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

平均搜索長度［5］指的是為確定某數(shù)據(jù)塊在索引塊區(qū)中的索引位置而所需執(zhí)行的關(guān)鍵碼的比較次數(shù)的期望值?？梢圆捎脭?shù)據(jù)塊的塊序列號(hào)作為關(guān)鍵碼。對(duì)于一個(gè)含有n個(gè)索引項(xiàng)的塊區(qū)，搜索成功時(shí)的平均搜索長度是：

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

假定每個(gè)索引項(xiàng)的搜索概率都相同，即pi＝1/n，那么此種情況下的ASLsucc可以計(jì)算為：

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

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

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

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

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

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

當(dāng)且僅當(dāng)m＞n，n＞0，且n＝m－n時(shí)成立。

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

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

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

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

4 塊區(qū)設(shè)計(jì)的一些思路

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

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

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

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

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

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

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

5 結(jié)束語

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

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

［1］ 劉越.云計(jì)算技術(shù)與應(yīng)用［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］.電訊技術(shù)，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)絡(luò)，海量數(shù)據(jù)存儲(chǔ)方面的研究。

2014－07－28