（译注：旧称廉价磁盘冗余阵列（Redundant Array of Inexpensive Disks），本章原标题就是这个）
当我们使用磁盘时，我们有时希望它更快;I/O操作很慢，因此可能成为整个系统的瓶颈。当我们使用磁盘时，我们有时希望它更大;越来越多的数据被放到网上，因此我们的磁盘变得越来越满。当我们使用磁盘时，我们有时希望它更可靠;当磁盘出现故障时，如果我们的数据没有备份，所有有价值的数据就都消失了。
关键的问题：如何制作一个大型、快速、可靠的磁盘 如何才能做出一个大型、快速、可靠的存储系统?关键技术是什么?不同方法之间的权衡是什么?
在本章中，我们将介绍**廉价磁盘冗余阵列(Redundant Array of Inexpensive Disks)，也就是RAID** [P+88]，这是一种使用多个磁盘协同构建更快、更大、更可靠的磁盘系统的技术。这个词是在20世纪80年代末由加州大学伯克利分校的一组研究人员(由大卫·帕特森教授和兰迪·卡茨教授以及后来的学生加思·吉布森教授领导)引入的;正是在这个时候，许多不同的研究人员同时想到了使用多个磁盘来构建更好的存储系统的基本想法[BG88,K86,K88,PB86,SG86]。<br />从外部看，RAID看起来像一个磁盘:一组可以读或写的块。在内部，RAID是一个复杂的怪兽，由多个磁盘、内存(易失性和非易失性)和一个或多个处理器组成，用于管理系统。硬件RAID非常类似于计算机系统，专门用于管理一组磁盘。<br />与单个磁盘相比，RAID 具有许多优势。** 优势之一是性能**。 并行使用多个磁盘可以大大加快 I/O 时间。 **另一个好处是容量**。 大型数据集需要大型磁盘。 最后，**RAID 可以提高可靠性**； 将数据分散到多个磁盘（没有 RAID 技术）会使数据容易受到单个磁盘丢失的影响； 通过某种形式的**冗余（redundancy）**，RAID 可以容忍磁盘丢失并继续运行，就好像没有任何问题一样。
Tip：透明度可部署（TRANSPARENCY ENABLES DEPLOYMENT） 在考虑如何向系统添加新功能时，应始终考虑是否可以透明地（transparently）添加此类功能，而无需更改系统的其余部分。 要求完全重写现有软件（或彻底的硬件更改）会减少想法产生影响的机会。 RAID 就是一个完美的例子，当然它的透明度有助于它的成功。 管理员可以安装基于 SCSI 的 RAID 存储阵列而不是 SCSI 磁盘，系统的其余部分（主机、操作系统等）无需更改一点即可开始使用。 通过解决这个部署（deployment）问题，RAID 从一开始就取得了更大的成功。
令人惊讶的是，RAID为使用它们的系统**透明地（transparently）**提供了这些优势，也就是说，RAID对主机系统来说就像一个大磁盘。当然，透明的美妙之处在于，它使人们能够简单地用RAID替换磁盘，而不改变任何一行软件;操作系统和客户端应用程序无需修改就可以继续运行。这样，透明度大大提高了RAID的**可部署性（deployability）**，用户和管理员可以放心使用RAID，而不用担心软件兼容性。<br />我们现在讨论一下RAIDs的一些重要方面。我们从接口、故障模型开始，然后讨论如何沿着三个重要的轴(容量、可靠性和性能)评估RAID设计。然后讨论对RAID设计和实现很重要的其他一些问题。
38.1 接口和RAID内部 Interface And RAID Internals
对于上面的文件系统，RAID看起来像一个大的、(希望)快速的、(希望)可靠的磁盘。与单个磁盘一样，它将自己表示为一个块的线性数组，文件系统(或其他客户机)可以读取或写入每个块。
当文件系统向 RAID 发出逻辑 I/O 请求时，RAID 内部必须计算要访问哪个（或哪些）磁盘以完成请求，然后发出一个或多个物理 I/O 来执行此操作。 这些物理 I/O 的确切性质取决于 RAID 层级，我们将在下面详细讨论。 然而，作为一个简单的例子，考虑一个 RAID，它为每个块保留两个副本（每个都在一个单独的磁盘上）； 当写入这样的镜像（mirrored） RAID 系统时，RAID 必须为它发出的每个逻辑 I/O 执行两个物理 I/O。
RAID 系统通常构建为单独的硬件盒，具有到主机的标准连接（例如，SCSI 或 SATA）。 然而，在内部，RAID 相当复杂，包括运行固件以指导 RAID 操作的微控制器、在读取和写入数据块时缓冲数据块的易失性存储器（如 DRAM），以及在某些情况下安全地缓冲写入数据块的非易失性存储器，甚至可能是专门的逻辑来执行奇偶校验计算（在某些 RAID 层级中很有用，我们还将在下面看到）。 在高层次上，RAID 是一种非常专业的计算机系统：它具有处理器、内存和磁盘； 但是，它不是运行应用程序，而是运行专门用于操作 RAID 的软件。
38.2 故障模型 Fault Model
要了解 RAID 并比较不同的方法，我们必须牢记故障模型。 RAID 旨在检测某些类型的磁盘故障并从中恢复； 因此，准确了解预期的哪些故障对于实现工作设计至关重要。
我们假设的第一个故障模型非常简单，被称为故障停止（fail-stop）故障模型[S84]。在此模型中，磁盘可以处于两种状态之一:工作状态或故障状态。使用工作磁盘，可以读取或写入所有块。相反，当磁盘发生故障时，我们假设它永久丢失了。
故障停止模型的一个关键方面是它对故障检测的假设。具体地说，当磁盘发生故障时，我们假设这很容易检测到。例如，在RAID阵列中，我们假设RAID控制器硬件(或软件)可以立即观察到磁盘何时发生故障。
因此，目前，我们不必担心更复杂的“静默（silent）”故障，例如磁盘损坏。 我们也不必担心单个块在其他工作的磁盘上变得无法访问（有时称为潜在扇区错误（latent sector error））。 稍后我们将考虑这些更复杂（不幸的是，更现实）的磁盘故障。
38.3 如何评估RAID How To Evaluate A RAID
我们很快就会看到，构建RAID有许多不同的方法。每一种方法都有不同的特点，值得评估，以便了解它们的优缺点。
具体来说，我们将沿着三个轴评估每个RAID设计。第一个轴是容量（capacity）; 给定一组N个磁盘，每个磁盘都有B个块，RAID的客户端有多少可用容量?如果没有冗余，答案是
;相比之下，如果我们有一个系统，每个块都保留两个副本(称为镜像（mirroring）)，我们将获得
的有用容量。不同的方案(如奇偶校验的方案)往往介于两者之间。
评价的第二个轴是可靠性（reliability）。给定的设计可以容忍多少磁盘故障?与我们的故障模型一致，我们假设只有整个磁盘会发生故障;在后面的章节(即关于数据完整性的章节)中，我们将考虑如何处理更复杂的故障模式。
最后，第三个轴是性能（performance）。性能的评估有些困难，因为它严重依赖于提供给磁盘阵列的工作负载。因此，在评估性能之前，我们将首先介绍一组应该考虑的典型工作负载。
我们现在考虑三个重要的 RAID 设计：RAID 层级 0（分条（striping））、RAID 层级 1（镜像（mirroring））和 RAID 层级 4/5（基于奇偶校验的冗余（parity-based redundancy））。 将这些设计中的每一个命名为“层级（level）”源于Patterson，Gibson，和 Katz在伯克利 [P+88] 的开创性工作。
38.4 RAID层级0：分条 RAID Level 0: Striping
第一个RAID层级实际上根本不是RAID层级，因为它没有冗余。但是，RAID级别0(或者更广为人知的分条（striping）)是性能和容量的一个极好的上限，因此值得理解。
分条最简单的形式是在系统的磁盘上进行分条，如下所示(假设有4个磁盘阵列):
Figure 38.1: RAID-0: Simple Striping
从图38.1中可以看出基本思想:以轮循方式将阵列的块分布在磁盘上。这种方法的目的是在请求阵列中连续的块时(例如在大的连续读取中)从阵列中提取最大的并行性。我们称同一行中的块为条带（stripe）;因此，块0、1、2和3在上面的同一个条带中。
在这个例子中，我们做了一个简化的假设，即在移动到下一个磁盘之前，每个磁盘上只放置了 1 个块（每个大小为 4KB）。 然而，这种安排不必如此。 例如，我们可以在磁盘上排列块，如图 38.2：
Figure 38.2: Striping With A Bigger Chunk Size
在本例中，我们在每个磁盘上放置两个4KB的块，然后再移动到下一个磁盘。因此，该RAID组的chunk（组块）大小为8KB，一个条带由4个chunk或32KB的数据组成。
Aside：RAID映射问题 在研究RAID的容量、可靠性和性能特征之前，我们先提一下所谓的映射问题（the mapping problem）。这个问题出现在所有RAID阵列中;简单地说，给定要读或写的逻辑块，RAID如何确切地知道要访问哪个物理磁盘和偏移量? 对于这些简单的RAID级别，我们不需要太复杂，就可以将逻辑块正确地映射到它们的物理位置。以上面的第一个分段示例为例(chunk size = 1，block = 4KB)。在这种情况下，给定逻辑块地址A, RAID可以很容易地通过两个简单的方程计算所需的磁盘和偏移量:
Disk = A % number_of_disksOffset = A / number_of_disks注意，这些都是整数运算(例如，4 / 3 = 1而不是1.33333…)。让我们通过一个简单的例子来看看这些方程是如何工作的。想象一下，在上面的第一个RAID中，有一个请求到达block 14。假设有4个磁盘，这意味着我们感兴趣的磁盘是(14% 4 = 2):磁盘2。精确的块计算为(14 / 4 = 3):块3。因此，应该在第三个磁盘(磁盘2，从0开始)的第四个磁盘块(块3，从0开始)上找到块14，这正是块14所在的位置。 您可以考虑如何修改这些方程以支持不同的组块大小（chunk sizes）。试一试!这并不难。
组块大小 Chunk Sizes
Chunk的大小主要影响阵列的性能。例如，较小的块大小意味着许多文件将跨多个磁盘被分条，从而增加了对单个文件的读写并行性;但是，跨多个磁盘访问块的定位时间会增加，因为整个请求的定位时间是由跨所有驱动器的请求的最大定位时间决定的。
另一方面，较大的组块大小（Chunk Sizes）会减少这种文件内的并行性，因此依赖于多个并发请求来实现高吞吐量。然而，组块大小减少了定位时间;例如，如果一个文件适合于一个组块（Chunk），因此被放置在一个磁盘上，那么在访问它时产生的定位时间将只是单个磁盘的定位时间。
因此，很难确定“最佳”组块大小（Chunk Sizes），因为它需要大量有关呈现给磁盘系统的工作负载的知识 [CL95]。 对于本讨论的其余部分，我们将假设阵列使用单个块 (4KB) 的组块大小（Chunk Sizes）。 大多数阵列使用更大的组块大小（例如，64 KB），但对于我们下面讨论的问题，确切的块大小并不重要； 因此，为了简单起见，我们使用单个块。
回到 RAID-0 分析 Back To RAID-0 Analysis
现在让我们评估分条的容量、可靠性和性能。从容量的角度来看，它是完美的: 给定N个大小为B块的磁盘，分条提供
块可用容量。从可靠性的角度来看，分条也是完美的，但在坏的方面: 任何磁盘故障都会导致数据丢失。最后，性能很好:所有磁盘都被利用，通常是并行地，为用户I/O请求服务。
评估RAID性能 Evaluating RAID Performance
在分析RAID性能时，可以考虑两种不同的性能指标。第一个是单请求延迟（single-request latency）。理解对RAID的单个I/O请求的延迟是有用的，因为它揭示了在单个逻辑I/O操作期间可以存在多少并行性。第二个是RAID的稳态吞吐量（steady-state throughput），即许多并发请求的总带宽。由于RAID通常用于高性能环境，因此稳态带宽非常关键，因此将是我们分析的主要焦点。
为了更详细地理解吞吐量，我们需要提出一些感兴趣的工作负载。对于本文的讨论，我们将假设有两种类型的工作负载: 连续的和随机的（sequential and random）。对于连续的工作负载，我们假设对数组的请求是大的连续块;例如，一个请求(或一系列请求)访问 1 MB 的数据，从块x开始，到块(x + 1 MB)结束，将被认为是连续的。连续工作负载在许多环境中都很常见(可以考虑在大文件中搜索关键字)，因此被认为很重要。
对于随机工作负载，我们假设每个请求都相当小，并且每个请求都指向磁盘上不同的随机位置。例如，一个随机的请求流可能首先访问逻辑地址10的4KB，然后是逻辑地址550,000，然后是20,100，依此类推。一些重要的工作负载，例如数据库管理系统(DBMS)上的事务性工作负载，显示了这种类型的访问模式，因此它被认为是一种重要的工作负载。
当然，实际的工作负载并没有这么简单，通常是连续和看似随机的部分以及两者之间的行为的混合。为了简单起见，我们只考虑这两种可能性。
可以看出，连续和随机的工作负载与磁盘的性能特征有很大的不同。使用连续访问，磁盘以其最有效的模式运行，只花很少的时间寻道和等待旋转延迟，大部分时间用于传输数据。对于随机访问，情况正好相反:大部分时间花在寻道和等待旋转延迟上，而花在传输数据上的时间相对较少。为了在我们的分析中捕捉这种差异，我们将假设磁盘在连续工作负载下可以以S MB/s的速度传输数据，在随机工作负载下可以以R MB/s的速度传输数据。一般来说，S比R大得多(即
)。
为了确保我们理解了这个区别，让我们做一个简单的练习。具体来说，让我们根据下列磁盘特征计算S和R。假设顺序传输平均大小为10 MB，随机传输平均大小为10 KB。另外，假设磁盘具有以下特征:
- 平均寻道时间 7 ms
- 平均旋转延迟 3 ms
- 磁盘传输速率 50 MB/s
要计算S，我们首先需要知道典型的10 MB传输花费了多少时间。首先，我们花7毫秒寻找，然后3毫秒旋转。最后,开始传输; 10 MB @ 50 MB/s 将花费1/5秒，即200ms的传输时间。因此，对于每个10 MB的请求，我们将花费210毫秒来完成请求。要计算S，我们只需要相除:
正如我们所看到的，由于传输数据花费了大量的时间，S非常接近磁盘的峰值带宽（peak bandwidth） (寻道和旋转成本已被平摊)。
我们可以用类似的方法计算R。寻找和旋转是一样的; 然后计算传输所花费的时间，即10 KB @ 50 MB/s，或0.195 ms。
我们可以看到，R小于1 MB/s , S/R 接近 50。
再次回到RAID-0分析 Back To RAID-0 Analysis, Again
现在让我们来评估分条的性能。就像我们上面说的，总的来说是好的。例如，从延迟的角度来看，单个块请求的延迟应该与单个磁盘的延迟完全相同;毕竟，RAID-0将简单地将请求重定向到它的一个磁盘。
从稳态连续吞吐量的角度，我们期望得到系统的全带宽。因此，吞吐量等于N(磁盘数量)乘以S(单个磁盘的连续带宽)。对于大量的随机I/O，我们可以再次使用所有的磁盘，从而获得 N·R MB/s。正如我们在下面看到的，这些值都是最容易计算的，并且将作为与其他RAID层级比较的上限。
38.5
RAID层级1：镜像 RAID Level 1: Mirroring
除条带之外的第一个RAID级别称为RAID级别1，即镜像。对于镜像系统，我们只需为系统中的每个块创建多个副本;当然，每个副本应该放在单独的磁盘上。通过这样做，我们可以容忍磁盘故障。
在一个典型的镜像系统中，我们假设对于每个逻辑块，RAID保持它的两个物理副本。下面是一个例子:
Figure 38.3: Simple RAID-1: Mirroring
在示例中，磁盘0和磁盘1具有相同的内容，磁盘2和磁盘3也具有相同的内容;数据在这些镜像对上被分条。实际上，您可能已经注意到有许多不同的方法可以跨磁盘放置块副本。上面的安排是一种常见的安排，有时称为RAID-10(或RAID 1+0，镜像条带)，因为它使用镜像对(RAID-1)，然后在它们之上使用条带(RAID-0);另一种常见的安排是RAID-01(或RAID 0+1，条带镜像)，它包含两个大的条带(RAID-0)阵列，然后在它们之上进行镜像(RAID-1)。现在，我们只讨论基于上述布局的镜像。
当从镜像阵列读取块时，RAID有一个选择:它可以读取任意一个副本。例如，如果对逻辑块5的读被下发到RAID，则可以从磁盘2或磁盘3任意读取逻辑块5。但是，当写入一个块时，不存在这样的选择:RAID必须更新数据的两个副本，以保持可靠性。不过，请注意，这些写入可以并行进行;例如，对逻辑块5的写入可以同时进行到磁盘2和磁盘3。
RAID-1分析 RAID-1 Analysis
让我们评估RAID-1。从容量的角度来看，RAID-1是昂贵的;当镜像级别为2时，我们只能获得峰值可用容量的一半。N盘B块时，RAID-1的有效容量为(N·B)/2。
从可靠性的角度来看，RAID-1做得很好。它可以容忍任何一个磁盘的故障。您可能还注意到，如果幸运的话，RAID-1实际上可以做得更好。想象一下，在上图中，磁盘0和磁盘2都失败了。在这种情况下，没有数据丢失!一般情况下，镜像系统(镜像级别为2)可以容忍1个磁盘故障，最多可以容忍N/2个磁盘故障。在实践中，我们通常不喜欢让这样的事情碰运气;因此，大多数人认为镜像很适合处理单个故障。
最后，我们分析性能。从单个读请求的延迟角度来看，我们可以看到它与单个磁盘上的延迟相同;RAID-1所做的只是将读操作指向它的一个副本。写略有不同:它需要在完成之前完成两次物理写。这两个写操作是并行进行的，因此时间大致相当于单个写操作的时间;但是，由于逻辑写必须等待两个物理写完成，因此它会遭受两个请求的最坏情况的寻道和旋转延迟，因此(平均)将略高于对单个磁盘的写。
Aside：ARID一致性更新问题 在分析RAID-1之前，让我们首先讨论任何多磁盘RAID系统中都会出现的一个问题，即一致性更新问题（consistent-update problem）[DAA05]。该问题发生在写入任何 RAID 时，该 RAID 在单个逻辑操作期间必须更新多个磁盘。 在这种情况下，让我们假设我们正在考虑镜像磁盘阵列。 想象一下，写入被发送到RAID，然后RAID决定必须将其写入两个磁盘，磁盘0和磁盘1。然后，RAID向磁盘0发出写入，但就在RAID向磁盘1发出请求之前，发生了断电(或系统崩溃)。在这种不幸的情况下，让我们假设对磁盘0的请求已经完成(但对磁盘1的请求显然没有完成，因为它从未发出)。 这种不合时宜的断电的结果是，块的两个副本现在是不一致的（inconsistent）;磁盘0上的副本是新版本，磁盘1上的副本是旧版本。我们希望发生的是两个磁盘的状态以原子（atomically）方式改变，也就是说，要么两个磁盘都应该是新版本，要么都不是。 解决这个问题的一般方法是使用某种类型的预写日志（write-ahead log），在做之前首先记录RAID将要做什么(即，用特定的数据块更新两个磁盘)。通过采取这种方法，我们可以确保在出现崩溃时，正确的事情会发生;通过运行一个恢复（recovery）程序，将所有挂起的事务重放到RAID，我们可以确保没有两个镜像副本(在RAID-1的情况下)不同步。 最后一个注意事项:由于在每次写入时将日志记录到磁盘上的开销非常高，大多数RAID硬件都包含少量的非易失性RAM(例如，电池支持的)，在那里执行这种类型的日志记录。因此，可以提供一致的更新，而无需花费很高的日志记录到磁盘的成本。
为了分析稳定状态的吞吐量，让我们从连续工作负载开始。当连续写到磁盘时，每个逻辑写必须导致两次物理写;例如，当我们写入逻辑块0(上图中)时，RAID内部会将其写入磁盘0和磁盘1。因此，我们可以得出这样的结论:在连续写入镜像阵列的过程中获得的最大带宽是()，或者是峰值带宽的一半。<br />不幸的是，在连续读取过程中，我们获得了完全相同的性能。有人可能会认为连续读取可以做得更好，因为它只需要读取数据的一个副本，而不是两个副本。但是，让我们用一个例子来说明为什么这没有多大帮助。假设我们需要读取0、1、2、3、4、5、6和7块。假设我们将 0 的读取发送到磁盘 0，将 1 的读取发送到磁盘 2，将 2 的读取发送到磁盘 1 ，以及将 3 读取到磁盘 3。我们继续分别向磁盘 0、2、1 和 3 发出对 4、5、6 和 7 的读取。 人们可能天真地认为，因为我们正在利用所有磁盘，所以我们正在实现阵列的全部带宽。 <br />然而，要看到这不是（必然）情况，请考虑单个磁盘接收的请求（例如磁盘 0）。 首先，它收到块 0 的请求； 然后，它收到块 4 的请求（跳过块 2）。 事实上，每个磁盘都会收到一个对每个其他块的请求。 当它在跳过的块上旋转时，它没有向客户端提供有用的带宽。 因此，每个磁盘只能提供其峰值带宽的一半。 因此，连续读取只会获得（%22%20aria-hidden%3D%22true%22%3E%0A%3Cg%20transform%3D%22translate(120%2C0)%22%3E%0A%3Crect%20stroke%3D%22none%22%20width%3D%22748%22%20height%3D%2260%22%20x%3D%220%22%20y%3D%22220%22%3E%3C%2Frect%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMATHI-4E%22%20x%3D%2284%22%20y%3D%22629%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-32%22%20x%3D%22278%22%20y%3D%22-589%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-22C5%22%20x%3D%221210%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-53%22%20x%3D%221711%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=%5Ctfrac%20%7BN%7D%7B2%7D%20%5Ccdot%20S&id=XEdt3)）MB/s 的带宽。 <br />随机读是镜像RAID的最佳情况。在这种情况下，我们可以将读取分布在所有磁盘上，从而获得全部可能的带宽。因此，对于随机读取，RAID-1提供 MB/s。<br />最后，随机写的性能如您所料:  MB/s。每个逻辑写必须转换为两个物理写，因此当所有磁盘都在使用时，客户端将只认为这是可用带宽的一半。即使对逻辑块x的写变成对两个不同物理磁盘的并行写，许多小请求的带宽也只达到分条的一半。我们很快就会看到，获得可用带宽的一半实际上是相当不错的。
38.6
RAID层级4：通过奇偶校验节省空间 RAID Level 4: Saving Space With Parity
现在，我们提出一种不同的方法来增加磁盘阵列的冗余，称为奇偶校验（parity）。基于奇偶校验的方法试图使用更少的容量，从而克服镜像系统所付出的巨大空间代价。然而，它们这样做是有代价的: 性能。
下面是一个5盘RAID-4系统的示例(图38.4)。对于每个数据条带，我们都添加了一个奇偶校验（parity）块，用于存储该条带的冗余信息。例如，校验块P1有冗余信息，它是从块4、5、6、7中计算出来的。
Figure 38.4: RAID-4 With Parity
为了计算奇偶校验，我们需要使用一个数学函数，使我们能够承受从我们的条带中任何一个块的损失。简单的XOR（异或）函数很好地解决了这个问题。对于给定的位集合，如果位中有偶数个1，那么所有这些位的XOR返回0，如果位中有奇数个1，则返回1。例如:
在第一行(0,0,1,1)中，有两个1 (C2, C3)，因此所有这些值的XOR为0 (P);类似地，在第二行只有一个1 (C1)，因此异或必须是1 (P)。你可以用一种简单的方式记住这一点:任何一行的1的数量，包括奇偶校验位，必须是偶数(而不是奇数);这是RAID必须维护的不变量（invariant），以便奇偶校验正确。
从上面的示例中，您可能还可以猜测如何使用奇偶校验信息从故障中恢复。 想象一下，标记为 C2 的列丢失了。 要确定列中必须有哪些值，我们只需读入该行中的所有其他值（包括 XOR 奇偶校验位）并重建正确答案。 具体来说，假设列 C2 中第一行的值丢失（它是 1）； 通过读取该行中的其他值（C0 中的 0、C1 中的 0、C3 中的 1 和奇偶校验列 P 中的 0），我们得到值 0、0、1 和 0。因为我们知道 XOR 保持一个 每行中有偶数个 1，我们知道丢失的数据必须是什么：1。这就是在基于 XOR 的奇偶校验方案中重建的工作原理！ 还要注意我们如何计算重构值：我们只是将数据位和奇偶校验位异或在一起，与我们首先计算奇偶校验的方式相同。
现在您可能想知道:我们正在讨论XORing所有这些位，但是从上面我们知道RAID在每个磁盘上放置了4KB(或更大)的块;我们如何对一堆数据块应用异或运算来计算奇偶校验?这也很简单。只需在数据块的每个位上执行逐位异或;将每个逐位异或的结果放入奇偶校验块中相应的位槽中。例如，如果我们有大小为4位的块(是的，这仍然比4KB的块小很多，但你已经知道了)，它们可能看起来像这样:
从图中可以看到，对每个块的每个位计算奇偶校验，并将结果放置在奇偶校验块中。
RAID-4分析 RAID-4 Analysis
现在让我们分析RAID-4。从容量的角度来看，RAID-4为它所保护的每组磁盘使用1个磁盘作为奇偶校验信息。因此，RAID组的可用容量为
。
可靠性也很容易理解:RAID-4只允许1个硬盘故障。如果多个磁盘丢失，则根本没有办法重建丢失的数据。
最后，还有性能。这一次，让我们从分析稳态吞吐量开始。连续读性能可以利用除奇偶校验磁盘以外的所有磁盘，从而提供
MB/ S(简单情况)的峰值有效带宽。
为了理解连续写的性能，我们必须首先理解它们是如何完成的。当将大块数据写入磁盘时，RAID-4可以执行一种称为全条带写（full-stripe write）的简单优化。例如，假设块0、1、2和3作为写请求的一部分被发送到RAID(图38.5)。
Figure 38.5: Full-stripe Writes In RAID-4
在这种情况下，RAID可以简单地计算P0的新值(通过在块0、1、2和3上执行异或)，然后将所有块(包括奇偶校验块)并行地写入上面的5个磁盘(图中以灰色突出显示)。因此，对于RAID-4来说，全条带写是最有效的写入磁盘的方式。
一旦我们理解了全条带写，计算RAID-4上连续写的性能就很容易了;有效带宽也为 
MB/ S。即使在操作期间经常使用校验磁盘，客户端也不会从中获得性能优势。
现在让我们分析随机读的性能。从上图还可以看到，一组1块的随机读将分布在系统的数据磁盘上，而不是奇偶磁盘上。因此，有效性能为: 
MB/s。
随机写入(我们将其保留到最后)为RAID-4提供了最有趣的情况。假设我们希望覆盖上面例子中的块1。我们可以直接重写它，但这将给我们留下一个问题:奇偶校验块P0将不再准确地反映条带的正确奇偶校验值;在本例中，P0也必须更新。我们怎样才能正确而有效地更新它?
结果有两种方法。第一种称为加法奇偶性（additive parity），要求我们做以下工作。为了计算新的奇偶校验块的值，并行地读入条带中的所有其他数据块(在本例中为块0、2和3)，并与新块(1)的数据块异或。结果就是新的奇偶校验块。为了完成写操作，可以将新数据和新的奇偶校验写入各自的磁盘，而且是并行的。
这种技术的问题是，它随着磁盘数量的增加而扩大，因此在较大的RAID中需要大量的读操作来计算奇偶校验。因此，采用减法奇偶校验（ subtractive parity）法。
例如，假设这串位(4个数据位，一个奇偶校验):
假设我们希望用一个新值覆盖 
位，我们称之为 
。 减法方法分三步工作。 首先，我们读入 
处的旧数据
和旧奇偶校验
。 然后，我们比较旧数据和新数据； 如果它们相同（例如，
），那么我们知道奇偶校验位也将保持不变（即 
）。 但是，如果它们不同，那么我们必须将旧的奇偶校验位翻转到与其当前状态相反的状态，即如果 
，则 
将设置为 0； 如果 
，
将被设置为 1。我们可以用 XOR 巧妙地表达这整个混乱（其中 
是 XOR 运算符）： 
因为我们处理的是块，而不是位，所以我们对块中的所有位执行这个计算(例如，每个块中的4096字节乘以每个字节的8位)。因此，在大多数情况下，新块将与旧块不同，因此新的奇偶校验块也将不同。
您现在应该能够确定何时使用加法奇偶校验计算以及何时使用减法计算。 考虑系统中需要多少个磁盘，以便加法方法比减法方法执行更少的 I/O； 交汇点是什么？
对于此性能分析，让我们假设我们使用的是减法方法。 因此，对于每次写入，RAID 必须执行 4 个物理 I/O（两次读取和两次写入）。 现在假设有很多写入提交到 RAID； RAID-4 可以并行执行多少个？ 为了理解，让我们再次看一下 RAID-4 布局（图 38.6）。 
Figure 38.6: Example: Writes To 4, 13, And Respective Parity Blocks
现在，假设在RAID-4上同时提交了2个小的写操作，分别是block 4和block 13(图中用标记)。这些磁盘的数据位于磁盘0和磁盘1上，因此对数据的读和写可以并行进行，这很好。出现的问题是奇偶磁盘;这两个请求都必须读取4和13、1和3(用+标记)的奇偶校验块。希望问题现在已经清楚了:在这种工作负载下，奇偶校验磁盘是一个瓶颈;因此，我们有时将此称为基于奇偶校验的RAID的小型写入问题（small-write problem）。
因此，即使可以并行访问数据磁盘，奇偶校验磁盘也阻止了任何并行化;由于奇偶校验磁盘，对系统的所有写都将被串行。由于奇偶校验磁盘在每个逻辑I/O上必须执行两个I/O(一个读，一个写)，因此我们可以通过计算奇偶校验磁盘在这两个I/O上的性能来计算RAID-4中小的随机写的性能，从而得到(R/2) MB/s。小的随机写操作下的RAID-4吞吐量非常糟糕;*当您向系统添加磁盘时，它不会得到改善。
我们通过分析RAID-4中的I/O延迟得出结论。正如您现在所知道的，单个读(假设没有故障)只是映射到单个磁盘，因此它的延迟相当于单个磁盘请求的延迟。单个写的延迟需要两次读和两次写; 可以并行进行读取，就像可以并行写一样，因此总延迟大约单个磁盘的两倍(有一些差异，因为我们必须等待读取完成，从而得到最坏的定位时间，但随后更新不导致寻道成本，因此可能比平均定位成本要好)。
38.7
RAID层级5：轮流奇偶校验块 RAID Level 5: Rotating Parity
为了解决小型写入问题(至少部分地解决)，Patterson、Gibson和Katz引入了RAID-5。RAID-5的工作原理与RAID-4几乎相同，除了它在驱动器之间轮流（rotates）奇偶块(图38.7)。
Figure 38.7: RAID-5 With Rotated Parity
可以看到，每个条带的奇偶校验块现在在磁盘之间轮流，以消除RAID-4的奇偶校验瓶颈。
RAID-5分析 RAID-5 Analysis
RAID-5的大部分分析与RAID-4相同。例如，这两个级别的有效容量和容错能力是相同的。顺序读写性能也是如此。单个请求(无论是读还是写)的延迟也与RAID-4相同。
随机读性能稍微好一些，因为我们现在可以利用所有磁盘。最后，随机写性能比RAID-4显著提高，因为它允许请求之间的并行性。想象一个写第1块，一个写第10块;这将转化为对磁盘1和磁盘4的请求(用于块1及其奇偶校验)，以及对磁盘0和磁盘2的请求(用于块10及其奇偶校验)。因此，它们可以并行进行。事实上，我们通常可以假设，给定大量的随机请求，我们将能够保持所有磁盘均匀繁忙。如果是这种情况，那么小型写入的总带宽将是 
MB/s。4 损失的因素是由于每个 RAID-5 写入仍然会生成 4 个总 I/O 操作，这只是使用基于奇偶校验的 RAID 的成本。
38.8 RAID对比：总结 RAID Comparison: A Summary
我们现在总结了图 38.8 中 RAID 级别的简化比较。 请注意，我们省略了许多细节以简化我们的分析。 例如，在镜像系统中写入时，平均寻道时间比仅写入单个磁盘时略高，因为寻道时间最多为两次寻道（每个磁盘上一次）。 因此，两个磁盘的随机写入性能通常会略低于单个磁盘的随机写入性能。 此外，在 RAID-4/5 中更新奇偶校验磁盘时，旧奇偶校验的第一次读取可能会导致完整的寻道和旋转，但奇偶校验的第二次写入只会导致旋转。 最后，与其他方法相比，镜像 RAID 的连续 I/O 会付出 2 倍的性能损失。
1/2惩罚假设镜像采用简单的读/写模式;对每个镜像的不同部分发出大型I/O请求的更复杂的方法可能会实现全带宽。想想看，你是否能找出原因。
Figure 38.8: RAID Capacity, Reliability, and Performance
然而，图38.8中的比较确实捕捉到了本质的差异，并且有助于理解RAID级别之间的权衡。对于延迟分析，我们只需使用T表示请求到单个磁盘所需的时间。
综上所述，如果您严格要求性能而不关心可靠性，分条显然是最好的。然而，如果你想要随机的I/O性能和可靠性，镜像是最好的;你付出的代价是丧失容量。如果容量和可靠性是您的主要目标，那么RAID-5就是赢家;你支付的成本是小型写入性能。最后，如果您总是执行连续I/O，并希望最大化容量，那么RAID-5也是最有意义的。
38.9 其他有趣RAID问题 Other Interesting RAID Issues
在考虑RAID时，还有许多其他有趣的想法可以(也许应该)讨论。以下是我们最终可能会写的一些东西。
例如，还有许多其他的RAID设计，包括原始分类法中的层级2和3，以及容忍多个硬盘故障的层级6 [C+04]。当磁盘出现故障时，RAID也会做同样的事情;有时它会有一个热备盘（hot spare）来填补失效的磁盘。故障下的性能和故障磁盘重构期间的性能会发生什么变化?还有更现实的故障模型，以考虑潜在的扇区错误（latent sector errors）或块损坏（block corruption）[B+08]，以及许多处理此类故障的技术(详情请参阅数据完整性章节)。最后，您甚至可以将RAID构建为软件层:这样的软件RAID系统（software RAID）成本更低，但存在其他问题，包括一致性更新问题[DAA05]。
38.10
总结 Summary
我们已经讨论了 RAID。 RAID 将多个独立的磁盘转变为一个更大、更容积大、更可靠的单一实体； 重要的是，它是透明的，因此上面的硬件和软件对这种变化是相对不敏感的
有许多可能的RAID层级可供选择，而要使用的确切RAID层级在很大程度上取决于对最终用户来说什么是重要的。例如，镜像RAID简单、可靠，一般性能较好，但容量成本较高。相反，RAID-5从容量的角度来看是可靠的，但是当工作负载中有小型写操作时，性能相当差。为特定的工作负载选择RAID并正确设置它的参数(块大小、磁盘数量等)是一项挑战，而且仍然是一门艺术而不是科学。
References
[B+08] “An Analysis of Data Corruption in the Storage Stack” by Lakshmi N. Bairavasun-daram, Garth R. Goodson, Bianca Schroeder, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-
Dusseau. FAST ’08, San Jose, CA, February 2008.
我们自己的工作分析磁盘实际损坏你的数据的频率。不是经常，但有时!因此，一个可靠的存储系统必须考虑一些问题。
[BJ88] “Disk Shadowing” by D. Bitton and J. Gray. VLDB 1988.
最早讨论镜像的论文之一，叫做“影子”。
[CL95] “Striping in a RAID level 5 disk array” by Peter M. Chen and Edward K. Lee. SIGMET-
RICS 1995.
对RAID-5磁盘阵列中的一些重要参数进行了很好的分析。
[C+04] “Row-Diagonal Parity for Double Disk Failure Correction” by P. Corbett, B. English, A.
Goel, T. Grcanac, S. Kleiman, J. Leong, S. Sankar. FAST ’04, February 2004.
虽然这不是第一篇关于具有两个磁盘的RAID系统的论文，但它是上述观点的最新且易于理解的版本。阅读它来了解更多。
[DAA05] “Journal-guided Resynchronization for Software RAID” by Timothy E. Denehy, A.
Arpaci-Dusseau, R. Arpaci-Dusseau. FAST 2005.
我们自己在持续更新问题上的工作。在这里，我们通过集成上面文件系统的日志机制和下面的软件RAID来解决软件RAID的问题。
[HLM94] “File System Design for an NFS File Server Appliance” by Dave Hitz, James Lau,
Michael Malcolm. USENIX Winter 1994, San Francisco, California, 1994.
这篇稀疏论文介绍了存储领域的一个里程碑式产品，即位于NetApp文件服务器基础上的随处写文件布局或WAFL文件系统。
[K86] “Synchronized Disk Interleaving” by M.Y. Kim. IEEE Transactions on Computers, Volume C-35: 11, November 1986.
关于RAID的一些最早的工作可以在这里找到。
[K88] “Small Disk Arrays – The Emerging Approach to High Performance” by F. Kurzweil.
Presentation at Spring COMPCON ’88, March 1, 1988, San Francisco, California.
另一个早期RAID参考。
[P+88] “Redundant Arrays of Inexpensive Disks” by D. Patterson, G. Gibson, R. Katz. SIGMOD 1988.
这被认为是由著名作家帕特森、吉布森和卡茨撰写的RAID论文。自那以后，该论文赢得了许多考验时间的奖项，并迎来了RAID时代，包括名称RAID本身!
[PB86] “Providing Fault Tolerance in Parallel Secondary Storage Systems” by A. Park, K. Bal- asubramaniam. Department of Computer Science, Princeton, CS-TR-O57-86, November 1986.
另一个关于RAID的早期工作。
[SG86] “Disk Striping” by K. Salem, H. Garcia-Molina. IEEE International Conference on Data
Engineering, 1986.
是的，另一个早期的RAID工作。当RAID的论文在SIGMOD上发表时，就有了很多这样的东西。
[S84] “Byzantine Generals in Action: Implementing Fail-Stop Processors” by F.B. Schneider.
ACM Transactions on Computer Systems, 2(2):145154, May 1984.
最后，一篇不是关于RAID的论文!这篇论文实际上是关于系统是如何失败的，以及如何让某些东西以一种故障停止的方式运行。
Homework (Simulation)
本节介绍RAID.py，这是一个简单的RAID模拟器，您可以使用它来巩固RAID系统如何工作的知识。有关详细信息，请参阅README。
Questions
- 使用模拟器执行一些基本的RAID映射测试。运行不同的级别(0、1、4、5)，看看能否找出一组请求的映射。对于RAID-5，请看看能否找出左对称和左不对称布局之间的区别。使用一些不同的随机种子来产生不同的问题。
- 执行与第一个问题相同的操作，但这次用-C改变块大小。块大小如何改变映射？
- 执行与上面相同的操作，但是使用-r标志来逆转每个问题的性质。
- 现在使用反向标志，但是用-S标志增加每个请求的大小。尝试指定8k、12k和16k的大小，同时更改RAID级别。当请求的大小增加时，底层I/O模式会发生什么变化?确保对顺序工作负载也尝试这样做(-W sequential);在多大的请求大小下，RAID-4和RAID-5的I/O效率更高?
- 使用模拟器的定时模式(-t)来估计对RAID进行100次随机读取的性能，同时改变RAID级别，使用4个硬盘。
- 执行上面的操作，但是增加磁盘的数量。随着硬盘数量的增加，每个RAID级别的性能如何扩展?
- 执行上面的操作，但是使用所有的写(-w 100)而不是读。现在每个RAID级别的性能如何扩展?你能粗略估计一下完成100个随机写的工作量所需的时间吗?
- 最后一次运行计时模式，但这一次使用顺序工作负载(-W sequential)。性能如何随RAID级别而变化，以及何时读写?改变每个请求的大小又如何呢?在使用RAID-4或RAID-5时，应该向RAID写入多大的数据?
若有收获，就点个赞吧
0 人点赞
