Bhagwat等人^[6]提出了一种根据数据块的重要性为其保存若干份副本的方法。这是一种自然、简单的想法,但它需要使用很大的存储空间,并且系统通讯量也随着副本份数的增多而增大,这些特性决定了其在大规模存储系统中的表现会比较低效^[7]。而且, Bhagwat的研究并没有考虑数据块的实际放置方法。Google公司的Google File System(GFS)也采用了副本的方法来增强系统的可靠性。在GFS中,文件被分成固定大小的块,每个块由一个不变的、全局唯一的64位的chunk-handle标识。

通过复制保证系统的可靠性是一种自然、简单的想法,但它需要占用的存储空间较大,并且系统通讯量也随着副本份数的增多而增大,这在一定程度上增加了系统构建成本。

还有一种方法是直接使用RAID类(RAID-like systems)系统作为底层的存储系统。该方法对上层透明,容易实现和部署。但是传统RAID系统(RAID1~RAID5)的容错能力是极其有限的,无法容忍两块硬盘同时出现故障的情况。

为了克服这一缺点, RAID6引入了双重校验机制,通过使用基于Galois Field算法或者有限场的数学MDS代码,在驱动器上对数据进行编码校验,可以容忍任意两块盘的错误。但RAID类系统只能进行整盘恢复,数据恢复时延相对较大,磁盘的容量越大,恢复所需的时间就越长,而恢复时间越长,数据丢失的可能性就越高。因此RAID技术并不适用于大规模存储系统中保证高数据可靠性。

数据容错编码按照误码控制的不同功能,可分为检错码、纠错码和纠删码等。检错码仅能够识别错码; 纠错码不仅具备检错码功能,同时具备纠正错码功能; 纠删码同时具备检错和纠错能力,而且当错码超过纠正范围时可把无法纠错的信息删除。两种典型的纠删编码是: Reed Solomon编码和Tornado编码。

1960年,里德(I. S. Reed)和所罗门(G. Solomon)提出一种构造纠错码的方法,使用该方法的纠错码被称作Reed-Solomon码,简称RS码^[8]。RS码是多元BCH码的一种,通过在数据传输和存储之前增加冗余, RS码能同时纠正突发错误和随机错误,其纠错能力达到了分组纠错码的极限。

RS码的软件实现采用传统线性分组码的编码方法。对RS( n, k)码,原始数据分成 k· m bit一组,每个码元由 m bit组成,因此一个码组共包括k个码元。

RS码能纠正 t个 m位二进制错误码组,其纠错能力由 t决定, t越大,纠错能力越强,但计算量也越大。RS码的编解码基于伽罗瓦域变换,计算比较复杂,且纠错时需要用到全部的 n个码元,数据传输开销较高,因此RS码的一个码组不能太大, n的大小一般为8~256。

Tornado码是M. G. Luby提出的一种基于低密度矩阵的纠错码^[9],对于出错率为 ρ的信道, Tornado码能够以 nlg(1/ ε)的编解码代价,纠正至多 ρ(1- ε)个错误,其中 ε是一个用于调控纠错能力和计算代价的参数。Tornado码通过构造不规则的级联二分图以及一系列异或操作来完成编码和解码。在恢复的时候,对于一个丢失的结点 A, 如果它的所有左结点都没有丢失,那么可以通过重新计算左结点的异或和恢复该结点。

由于Tornado码的编码和恢复操作都只需要进行简单的异或操作,因此计算开销比较小; 另外,由于Tornado码是基于不规则的稀疏级联二分图的,编码和解码用到的结点数目较少。因此,和传统的纠错码相比, Tornado码具有运算速度快,数据传输量小的特点,适用于在大规模分布式的系统中进行纠错。

对于有中心元数据管理节点的分布式文件系统来说,系统的容错主要体现在两个方面,即: 管理节点容错和存储节点容错。

2.1.1 管理节点容错

元数据是整个系统的核心,因此元数据服务器的稳定至关重要。目前主流方法多采用一个元数据管理节点,多个日志服务器的冷备份方式进行容错,如果元数据服务器宕机,可以通过日志服务器里面的元数据进行系统恢复。

此方法虽然可以解决元数据可靠性的问题,但是元数据服务器宕机时,同时也会使业务被迫中断,在实际应用时可能会造成用户数据丢失等,系统的恢复时间也比较长。

2.1.2 存储节点容错

分布式文件系统中,文件往往被分块分散存储在不同的存储节点。在成百上千台集群服务器中,存储节点组件的失效通常也被认为是常态,当组件失效时,数据完整性得不到保障,为保证数据调度的顺利进行,业界通常采用副本的方式容错,其优点是实现容易,缺点是对磁盘空间浪费很大,最低1∶1副本冗余,其有效利用率即损失50%。

基于RS编码技术构造的纠删码则称作RS纠删码。一个( n, k)纠删码是把 k个源数据编码为 n ( n>k)个数据,使得用这 n个数据中任意 k个数据均可重构原来的 k个源数据。采用 m个分片和 n个校验分片的纠删码体制就是( m+n, m)纠删码。采用RS纠删码方式对文件块进行编码存储,可通过较低的冗余度,实现高度的容错可靠性。

然而,基于纠删编解码的存储节点容错技术不能够满足快速访问的需求,因此在本文中,采用块副本和基于纠删编解码相结合的存储节点容错技术,根据数据的被访问频率情况选择不同的数据存储方式。

为全面分析云存储系统的容错技术和方法,本文给出了一个典型的云存储系统的架构设计。该架构是云存储文件系统容错机制设计和实现的基础。如图1所示。

图1

	Figure Option ViewDownloadNew WindowDownload As Powerpoint Slide
	图1 容错系统的模块设计

整个系统根据节点功能整体上分为三部分: 元数据管理节点、块数据存储节点以及应用访问接口,其具体功能及描述见下文。

2.2.1 元数据节点监控模块

为解决中心节点的单点故障问题,提出了一种双机热备策略,同一时刻有多台管理节点同时运行,但只有一台主机对外提供服务,若主机失效,立即从备机中选举出新的主机对外继续提供服务。

元数据节点监控模块是元数据节点容错调度模块的一部分,其主要用来监控元数据节点网络以及服务状态,同时也与其他元数据节点间维持心跳,在同一时刻,只有一台主元数据节点通过一个虚拟IP对外提供服务,其他备节点均处于待激活状态。

2.2.2 元数据管理同步模块

主备双机模式下,所备元数据节点均处于待激活状态,其配置及运行状态均与主机相同,为维持备机与主机的镜像关系,备机需要保持与主机元数据信息的同步。元数据管理同步流程如图2所示。

图2

	Figure Option ViewDownloadNew WindowDownload As Powerpoint Slide
	图2 主备元数据同步流程图

2.2.3 存储节点容错模块

系统采用块副本和基于纠删编解码相结合的存储节点容错技术。对于存入系统的数据,其被访问频率满足zipf分布。因此,实时统计该数据的被访问频率,当数据被访问频率很高时,可判断为热点数据,则对其进行块副本存储,并生成多个临时热点副本; 当数据被访问频率较低时,可判断为非热点数据,则对其进行基于RS编解码的冗余存储,并删除临时热点副本。

根据分布式文件系统的特点,本模块采用RS编解码技术构造块数据冗余策略,将一个文件划分为 M块标准大小的文件数据(不足以0补充), 通过巧妙的编码生成 N个校验块,将 M块原文件分块和N块校验块分别存放于 M+N个存储节点上。如图3所示。

图3

	Figure Option ViewDownloadNew WindowDownload As Powerpoint Slide
	图3 编解码数据块分布式存储示意图

将文件按序分块,每个块(Block)的大小为64 kB, 总共 n个block, 分别为: Block 1, Block 2, Block 3, …, Block n。按序以 m个Block为一组,进行编码,可以得到 n( n>m)个Block数据,其中,前 m个Block和输入的 m个Block完全一致,后面的 n-m个Block为计算出来的冗余数据。根据RS算法特性,在这 n个Block中,任意取出 m个Block进行译码,都可以将编码前的 n个Block的原始数据恢复出来。针对小文件,直接采用备份冗余策略而不进行编码,提高效率。

数据写入过程如图4所示。

图4

	Figure Option ViewDownloadNew WindowDownload As Powerpoint Slide
	图4 数据写入过程示意图

1) 客户端向元数据服务器请求写入文件数据,元数据服务器返回写入服务器列表;

2) 客户端进行文件切块写入有块数据服务器;

3) 客户端每写入一定量的块数据后,通知元数据服务器,由元数据服务器启动一个编码任务,进行编码; 而客户端继续写数据,真到写完成为止;

4) 元数据服务器调度一个或多个块数据服务器进行编码任务;

5) 被调度的块数据服务器,获取需要的原始信息块组进行编码,产生冗余数据块。

数据读出过程如图5所示。

图5

	Figure Option ViewDownloadNew WindowDownload As Powerpoint Slide
	图5 数据读出过程示意图

a) 客户端向元数据服务器请求读出文件数据,元数据服务器返回数据块位置列表;

b) 客户端进行数据块读出;

c) 客户端进行数据块校验;

d) 对未能读出的数据块或无效块通过同编码组内其他数据块进行解码,获得完整正解的文件数据。

元数据自动检测数据块的正确性、完整性,确定数据块损坏无效或丢失后,自动指定相应的存储服务器进行编码或解码恢复相应的数据块,确保数据的冗余容错能够及时恢复重建。

本文介绍的容错机制中,采用元数据节点双机热备实现管理节点容错,并用元数据自动同步保证主备两台管理节点能够提供的服务是同步的,称之为集中式元数据管理集群。假设在上述容错机制下,集中式元数据管理集群的可靠性为 R_master, 集群包括 p台管理节点,其中每个管理节点的磁盘数量为2, 设每块磁盘的可靠性为 R_HDD, 则 R_master的可靠性模型为

Rmaster=1-∏i=1p(1-RHDD2).(1)

假设每个磁盘的可靠性相同,根据Seagate和WesternDigital官网提供的数据,磁盘年损坏率约为0.34%,但实际使用中磁盘的可靠性远没有那么高,根据南京云创存储科技有限公司的测试部门提供的数据,磁盘的可靠性为0.97~0.99, 取最低值 R_HDD=0.97, p=1~5, 其中 p≥3时为一主多备方式。则采用双机热备容错机制的集中式元数据管理集群的可靠性随管理节点的个数增加而提高: 当管理节点为2个时,可靠性已达到0.996; 若增加至3个管理节点,则可靠性几乎为1。在实际应用中,考虑成本和可靠性之间的权衡,配置2个管理节点,实现双机热备即可。

本文介绍的容错机制中,采用副本容错技术和基于RS编解码算法的容错技术相结合的机制实现存储节点的容错。

块副本容错即保存多个要存储的数据的完整副本,一个云存储文件系统包含多个存储节点,这些存储节点组成云存储站点。设云存储站点可靠性为 R_storage, 存储节点的可靠性为 R_chunk, 数据冗余倍数为 p。则由大量存储节点组成的云存储站点的可靠性模型为

Rstorage=1-(1-Rchunk)p.(2)

根据文[1]的数据,取 R_chunk=0.9, p=1~5, 则当存储节点为1个时,云存储站点不存在块副本存储,可靠性仅为0.9; 当存储节点数等于2时,云存储站点可以提供1个副本存储,可靠性为0.99; 当存储节点数大于2时,云存储站点可以提供大于1个的块副本存储,可靠性则更加可靠。本文提出的容错机制中,对被访问频率高的数据采用块副本存储,并提供多个临时热点副本,因此可靠性会更好。

基于RS编解码算法的容错技术是将 k个文件分块数据生成为 n( n>k)个带有一定冗余的编码数据,然后将 n个冗余的编码数据分散存储到多个存储节点中,其中任意 k个部分可以用来恢复原始数据。设采用基于RS编解码算法的容错技术的云存储站点的可靠性为RRS, 存储节点的可靠性为 R_chunk, 文件分块数为 k, 文件编码数据分块数为 n, 冗余倍数为 s( s=n/k)。则采用基于RS编解码算法的容错技术的云存储站点的可靠性模型为

RRS=∑i=0ks-kCksiRchunkks-i(1-Rchunk)i.(3)

同样的,取 R_chunk=0.9, k=4~10, s=1~5。则采用基于RS编解码算法的容错技术的云存储站点的可靠性如图6所示。

图6

	Figure Option ViewDownloadNew WindowDownload As Powerpoint Slide
	图6 采用基于RS编解码算法的容错技术的云存储站点的可靠性

从图6可以看出,在低冗余度条件下(冗余倍数小于2), 编解码方式提供的云存储站点可靠性是很低的,并且文件分块数越多,可靠性越低; 当冗余度大于2时,编解码方式便能提供较高的可靠性,保持在0.999以上。但是这样极大地浪费了云存储站点的资源。

根据以上对块副本容错机制和基于RS编解码算法的容错技术的可靠性分析,可以看出,任何一种方式的容错,如果想提高云存储站点的可靠性,都需要较高的冗余度,耗费很多存储资源。通过将两种容错机制相结合,对文件的编码数据分块进行块副本存储,即能提高云存储站点的可靠性,且不需要太多冗余,节省大量的存储资源。

设采用两种容错机制相结合的云存储站点的可靠性为 R_cStor, 将式(2)带入式(3), 可以得到 R_cStor的可靠性模型为

RcStor=∑i=0ks-kCksi1-(1-Rchunk)pn-i(1-Rchunk)pi.(4)

同样,取单个存储节点的可靠性 R_chunk=0.9, 块副本数 p=2, 文件分块数 k=1~20, 文件编码数据分块按照编码冗余倍数 s=1~4来编码。采用两种容错机制结合的云存储站点的可靠性与编码冗余倍数及文件分块数的关系图如图7所示。

图7

	Figure Option ViewDownloadNew WindowDownload As Powerpoint Slide
	图7 云存储站点的可靠性与编码冗余倍数及文件分块数的关系图

已知块副本存储的副本数为2, 可以看出采用两种容错机制结合的云存储站点与编码冗余倍数及文件分块数之间的关系。当编码冗余倍数等于1时(即不编码), R_cStor随文件分块数增加而降低; 当编码冗余倍数大于或等于2时, R_cStor随文件分块数增加而增加,当文件分块数达到5块以上时, R_cStor大于0.999。但在实际应用中,编码冗余倍数大于1时, R_cStor便会随文件分块数增加而增加,且随着编码冗余倍数的增加, R_cStor随文件分块数增加而增加的效果越明显。因此,综合云存储站点的可靠性和存储空间资源利用率等,块副本存储的副本数取2, 编码冗余倍数取1.25, 文件分块数为8, 即文件编码数据分块为10块,此时云存储站点的可靠性可达到0.999 9。

在云存储文件系统中,管理节点和存储节点都非常重要,任何一方面产生数据丢失或数据灾难,都会导致文件系统中的文件丢失,因此云存储文件系统的可靠性,必须同时提高集中式元数据管理集群和云存储站点的可靠性。

本文介绍的容错机制从两个方面提高云存储文件系统的可靠性。一方面采用双机热备机制实现管理节点的数据容错,使集中式元数据管理集群的可靠性超过0.996; 另一方面采用副本容错技术和基于RS编解码算法的容错技术相结合的机制实现存储节点的容错,使云存储站点的可靠性达到0.999 9, 且保证数据的低冗余度。

综上所述,本文介绍的云存储文件系统容错机制的可靠性超过0.996。在实际应用中,管理节点配备的磁盘的可靠性远大于0.97, 在双机热备的基础上,还可以通过配备日志服务器来提高元数据管理集群的可靠性; 在云存储站点中,每一个存储节点配有16块磁盘,因此存储节点的可靠性也会远大于0.9, 从而云存储站点的实际可靠性还会更高。因而,实际应用的云存储文件系统的容错能力会更强,可靠性更好。

针对该策略的可靠性进行了测试。测试环境为一套云存储文件系统,管理节点采用两台元数据服务器的双机热备机制,存储节点采用块副本和基于RS编解码算法相结合的存储节点容错技术,对热点数据存储节点采用1+2的块副本存储,并提供4个临时热点副本,并对非热点数据采用10+6的RS编解码存储。

让系统执行10 GB文件的拷贝,在拷贝过程中拔掉主元数据服务器网线,经测算,系统在5 s内便恢复正常工作; 然后,关闭一定数量的存储节点,系统能够在关闭6个存储节点的情况下,保证数据完整性,拔出磁盘也产生同样的结果; 最后,同时拔掉主元数据服务器和6个存储节点的网线,系统在较短时间内恢复正常工作,并保证了数据完整性。

因此,本文提出的容错策略具有很高可靠性。