一种基于多层块区的数据存储架构

闫振东

（中国电子科学研究院，北京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