《中国计算机学会通讯201210-2大规模数据中心的数据存储可靠性》由会员分享，可在线阅读，更多相关《中国计算机学会通讯201210-2大规模数据中心的数据存储可靠性（9页珍藏版）》请在金锄头文库上搜索。
1、8 专题 第 8 卷 第 10 期 2012 年 10 月 沈志荣 易乐天 舒继武 清华大学 大规模数据中心的数据存储可靠性 引言 近年来，社交网络、网络新闻媒体和娱乐视 频等各种信息化服务的开展产生了大量的数据，使 得数据存储规模也呈现爆炸性增长。个人用户的数 据存储规模已经逐渐从GB（109字节）级别上升为 TB（1012字节）级别，一些大中型企业所需要存储 的数据甚至已经上升到了PB（1015字节）级别甚至 是EB（1018字节）级别。随着云计算和物联网的迅 速发展，越来越多的个人和企业选择将自己的业务 迁移到大规模的数据中心，以此来降低本地的硬件 成本和系统维护费用。数据变得越来越重要
2、，其价 值不仅体现在数据内容本身，还体现在为业务发展 所带来的利益，用户体验、公司盈利状况等等对数 关键词：数据存储可靠性 大规模数据中心 据的可靠性提出了要求。同时，从数据中心级别上 看，由于存储的数据量十分庞大，管理系统的复杂 性较高；从存储设备级别上看，由于数据中心为了控 制成本，大量采用廉价存储设备，致使数据极易因硬 件设备故障而丢失。这些都对海量数据存储带来了挑 战。例如，谷歌和亚马逊的数据服务中断事故开始让 人们担忧自己存储在数据中心的数据能否确保可靠。 因此，如何提高大规模数据中心的数据存储可靠性成 为了近年来的研究重点。 数据存储的可靠性 数据存储的可靠性研究包括磁盘阵列的可靠
3、性 和文件系统的可靠性两个方面。针 对大规模数据中心的数据存储可靠 性问题，下面将介绍上述两方面的 研究情况。 磁盘阵列的可靠性 长期以来，磁盘作为主流的存 储设备，存储容量不断增长，已从 最初的MB（106字节）级发展到如今 的TB级。一个PB级的数据中心需要 采用上千个磁盘，一个EB级的数据 中心需要采用上百万个磁盘。磁盘 作为一种机械式存储设备，它的可 靠性一直没有得到显著地改善，所 产生的磁盘错误会导致数据丢失或 扇区错误 磁盘故障 不可检测读写 错误磁盘错误检测 可检测磁盘错误 不可检测磁盘错误 图1 磁盘错误 9 第 8 卷 第10 期 2012 年 10 月 者损坏。这些磁盘错误
4、包括：磁盘故障（disk fail- ures）、潜在扇区错误（latent sector errors）和一些 不可检测的磁盘错误（undetected disk errors）。磁 盘作为数据的承载体，其可靠性与存储数据的可靠 性直接相关。 磁盘的可靠性 磁盘中存在的各种错误容易影响数据的可靠 性。这些磁盘错误主要分为可检测的和不可检测 的。其中，可检测的磁盘错误包括磁盘故障和潜在 扇区错误。 磁盘故障指磁盘硬件错误导致整个磁盘数据变 得无法访问。谷歌公司的数据表明，磁盘的年故障 率处于1.7%至8.6%之间；美国卡耐基梅隆大学的数 据显示，磁盘的年替换率在某些系统中甚至会达到 13%。由
5、此可见，对于由上千个磁盘组成的PB级存 储系统来说，一年内发生故障的磁盘个数就会达到 几十甚至上百个；而对于由上百万个磁盘组成的EB 级存储系统，一年内发生故障的磁盘个数则会达到 几万甚至几十万个。 潜在扇区错误指磁盘盘片表面磁 介质损坏或ECC错误导致某些扇区数 据变得无法访问或不可修复。NetApp 公司的统计数据显示，在32个月内， 153万个磁盘中出现潜在扇区错误的磁 盘比例为3.45%，并且这些出现错误的 磁盘中潜在扇区错误个数的平均值高 达19.7。 不可检测的磁盘错误指磁盘固件 或硬件错误导致从磁盘读出的数据与 磁盘预存的数据不一致。根据它们被 引起的时间点，可分为不可检测的读
6、错误和不可检测的写错误。需要注意 的是，不论是不可检测的读错误还是 不可检测的写错误，在上层应用中对 读操作表现出来的症状是一样的 要么是过时的数据，要么是不正确的 数据。这里，过时的数据和不正确的 数据的区别在于，过时的数据是指正 确的但过期的数据，而不正确的数据是指错误的数 据。需要注意的是，不可检测的读错误是瞬时的错 误，而不可检测的写错误则是持久的错误。因此， 不可检测的写错误对存储系统的可靠性的影响更严 重，受到研究者的关注也更多。不可检测的写错误 主要分为如下三种： 误地址写（misdirected write） 磁盘固件 中的缺陷（bug）会使正确的数据被写到错误的位 置，从而导
7、致误地址写。 丢失写（lost write） 如果磁盘的磁头信号强 度不够就不能将写数据送达磁盘盘片，并覆盖盘片上 原先存储的旧数据。但此时，如果磁盘又向上层发出 “写操作已完成”的报告，就会发生丢失写。 破写（torn write） 如果磁盘在写数据的过 程中电源被循环重启，就会导致一部分数据刚写入 磁盘时，写操作就结束了，由此发生破写。 磁盘阵列的可靠性 为了防止磁盘故障和潜在的扇区错误引起数据 丢失，通常采用冗余技术将磁盘组织成磁盘阵列。可 图2 磁盘阵列的条带化示意图，其中条带是独立构成纠删码算法 的信息集合。 磁盘阵列 磁盘阵列控制器 磁盘 条带 磁盘数据 10 专题 第 8 卷 第
8、 10 期 2012 年 10 月 用于磁盘阵列的冗余技术主要分为多路镜像技术（n- way mirroring）和纠删码技术（erasure coding）。 多路镜像技术又称为多副本技术，就是将数据 复制为多个副本并分别存储，以实现冗余备份。例 如，将每份数据同时存储到t+1个磁盘中，以容忍t 个磁盘同时发生故障。但是这种方法需要t倍的额外 存储开销，导致存储成本非常高。RAID11是该技术 的一个典型应用，采用2路镜像并且能容忍1个磁盘 发生故障。 纠删码技术的基本思想是将k个原始数据元 素通过编码计算，得到m块冗余元素，在所有的 （k+m）块元素中，任意不高于m块元素出错都可 以通过重
9、构算法恢复出原来的k块原始数据。过程 如图2所示，先将k个磁盘的原始数据存储到由n个 磁盘组成的磁盘阵列中（其中kn2k），并对磁 盘阵列进行条带化；然后用一个纠删码对每个条带 中的数据进行编码，以便在多个磁盘同时发生故障 时丢失的数据能被恢复出来。这里如果采用的纠删 码是最大距离可分（maximum distance separable， MDS）码，则可以容忍多达m=n-k个磁盘同时发生 故障。为了容忍t个磁盘同时发生故障，纠删码技术 可以只需要t/n（1）倍的额外冗余。RAID5是该技 术的一个典型应用，采用1个冗余磁盘并且能容忍1 个磁盘发生故障。 与多路镜像技术相比，纠删码技术极大地
10、提 高了磁盘阵列的存储效率，并且只引入了少量的 额外能耗开销。于是，许多纠删码技术被提出， 并应用于RAID6产品（如英特尔公司的基于P+Q 的RAID6和NetApp公司的RAID-DP）和各种高容 错存储系统。 纠删码技术 在理论研究方面，现有的纠删码主要包括RS （Reed-Solomon）码、奇偶校验码和阵列码（array code），分别介绍如下： RS码 RS码最早是由里德（Reed）和所罗门 （Solomon）于1960年提出的，能够提供任意高容 错能力的最大距离可分码。由于它是基于伽罗瓦域 运算实现的，因此编码和解码开销较大。RS码的原 理是利用生成矩阵与数据列向量的乘积得到信
11、息列 向量。在重构的时候，利用未出错的信息列向量所 对应的残余生成矩阵的逆矩阵与未出错的信息列向 量相乘，来恢复原始数据。如果要满足任意k个剩 余元素（经过编码后的元素个数为n=k+m个，可以 容忍最高m个元素错误）都能通过重构算法恢复原 来的数据，则其对应的残余生成矩阵均要在GF(2w) 域上满足可逆。RS码有基于范德蒙矩阵和基于柯西 矩阵两种形式，分别是利用范德蒙矩阵和柯西矩阵 作为生成矩阵。冯（Feng，音译）等人于2005年也 提出了两种分别类似于范德蒙RS码和柯西RS码的 基于异或（XOR）运算的水平码1,2。其中，类似于 范德蒙RS码的纠删码（冯等人称其为reed-solomon-
12、 like code）虽然具有很好的性能，但是容错能力不 能超过3；类似于柯西RS码的纠删码（冯等人称其 为rabin-like code）虽然能提供任意高的容错能力， 但由于它的生成矩阵是基于柯西矩阵和循环置换矩 阵构造的，因此性能仍然较低。 奇偶校验码 奇偶校验码是一种完全基于异 或运算的纠删码。其中，最简单的奇偶校验码是单 奇偶校验码，即在一个条带中，只有唯一的一个校 验条块。这个校验条块由所有用户数据条块的异或 运算之和得到。由此可见，单奇偶校验码的容错能 力为1。RAID5是单奇偶校验码的典型应用。基于 单奇偶校验码，可以构造出具有更高容错能力的奇 偶校验码。根据构造方式，奇偶校验码
13、可以分为两 大类：一类是根据几何结构构造的奇偶校验码。这 类校验码将一个条带中的条块在逻辑上组织成多维 几何结构，然后在每个方向上采用单奇偶校验码进 行编码，因此具有十分规整的结构。虽然此类校验 码易于实现，但是存储效率通常较低；另一类是根 据图结构构造的奇偶校验码。这类校验码主要由基 于Tanner图构造的低密度奇偶校验码（low-density parity-check code，LDPC）组成。低密度奇偶校验码 1 RAID：redundant arrays of inexpensive disks，独立冗余磁盘阵列 11 第 8 卷 第10 期 2012 年 10 月 最初是为通信链路
14、的容错而设计的，近年来才开始 用于基于广域网的存储中。它的优点是高容错，具 有接近最高的存储效率，解码复杂度很低。但是由 于它通常是基于不规整的图结构构造的，因此不仅 在磁盘阵列中很难实现，还会使硬件设计复杂化。 阵列码 阵列码是奇偶校验阵列码的简称，其 原理是将原始数据和冗余数据都存储在二维或者多 维的阵列中。与传统的RS码相比，阵列码具有易于 实现，编码和重构的过程相对简单等特点，因此应 用较为广泛。阵列码根据冗余数据和原始数据的排 放方式可分为水平和垂直两类。 第一类水平阵列码是指冗余数据单独存放在独 立的冗余磁盘中，而剩余磁盘存放原始数据，这种 排放方式具有良好的可扩展性。1995年，
15、容错能力 为2的EVENODD码的提出标志着阵列码研究的开 始。之后，NetApp公司在EVENODD码的基础上提 出了RDP（row-diagonal parity）码。2008年，普兰 克（Plank）又提出了一种具有接近最优性能的容 错能力为2的Liberation码。其解码可以完全基于异 或运算实现。此外，还有一些容错能力可高达8的 推广的水平阵列码，如推广的EVENODD码和推广 的RDP码。它们的性能虽然优于RS码，但解码除了 需要异或运算外，还需要循环移位运算，因此解码 的复杂度仍然较高。前面列举的这些水平阵列码都 是最大距离可分码，而MDS水平阵列码存在一个无 法突破的理论，即
16、它的更新复杂度始终要高于容错 能力。 为了使更新复杂度降到最低，人们开始研究另 一类垂直阵列码。在MDS垂直阵列码中，某些条块 中既存储了冗余数据，也存储了原始数据。由于垂 直阵列码一般具有简单的几何结构，因此其计算开 销可均匀地分布到各个磁盘上。1999年，许（Xu， 音译）等人提出了两种容错能力为2的MDS垂直阵 列码X码3和B码4。其中，X码是根据几何结 构构造的，它的一个条块中包含两个校验单元， 条带长度必须为质数；B码是利用图的完全一因式 分解（perfectone-factorization，P1F）构造的，它 的一个条块中只包含一个校验单元。之后李（Li， 音译）等人5还研究了具有循环对称性的B码 C码，并提出了用群论中的Starter6构造C码。由于 MDS垂直阵列码向高容错能力扩展十分困难，哈 夫纳（Hafner）在2005年提出了一种容错能力可达 12的非MDS垂直阵列码阵列码种容错码7。在 WEAVER码中，所有用户数据单元的数据出度都等 于容错能力，并且所有校验单元的校验入度都被限 定为一个固定值，由此保证了WEAVE
