用于镜像多维RAID的方法和系统

摘要

一种用于存储数据的方法。所述方法包括接收写入数据的请求，确定用于数据的存储模式是镜像模式，基于存储模式在RAID网格中选择要写入数据的独立器件冗余阵列(RAID)网格位置，将数据写入到存储器，更新数据结构以指示该RAID网格位置被填充，以及确定数据网格被填充；基于该确定，确定持久性储存器中对应于RAID网格位置的第一物理地址和第二物理地址；将数据写入到持久性储存器中对应于第一物理地址的第一物理位置并将数据写入到持久性储存器中对应于第二物理地址的第二物理位置，以及将与数据网格相关联的奇偶值写入到持久性储存器。

说明书

背景技术

为了针对存储系统中的潜在数据损耗进行保护，实施复制方案常常是有利的。 当前复制方案只能在不能读取存储系统内的数据之前维持有限的错误量。

发明内容

一般地，在一个方面，本发明涉及一种非临时计算机可读介质，其包括指 令，当该指令被处理器执行时执行一种方法，该方法用于存储数据，该方法包 括接收写入数据的请求，确定用于数据的存储模式，其中，用于数据的存储模 式是镜像模式，基于该存储模式来选择要写入数据的RAID网格中的独立器件 冗余阵列(RAID)网格位置，将数据写入存储器，其中，该数据被临时地存储 在存储器中，更新数据结构以指示该RAID网格位置被填充，使用数据结构来 确定RAID网格中的数据网格是否被填充，其中，RAID网格位置在数据网格中， 基于数据网格被填充的确定：使用数据来计算用于RAID网格的奇偶值，确定 对应于RAID网格位置的持久性储存器中的第一物理地址，确定对应于RAID 网格位置的持久性储存器中的第二物理地址，将数据写入对应于第一物理地址 的持久性储存器中的第一物理位置，将数据写入对应于第二物理地址的持久性 储存器中的第二物理位置，以及将与数据网格相关联的奇偶值写入到持久性储 存器。

一般地，在一个方面，本发明涉及一种非临时计算机可读介质，其包括指 令，当该指令被处理器执行时执行一种方法，该方法用于获得重构数据，该方 法包括接收对于数据的第一请求，识别与数据相关联的独立器件冗余阵列 (RAID)网格中的网格位置，其中，该网格位置与第一物理位置和第二物理位 置相关联，进行用于网格位置的存储模式是镜像模式的第一确定，基于第一确 定，进行第一物理位置被占用的第二确定，基于第二确定，向第二物理位置发 布对于数据的第二请求，以及响应于第二请求，从第二物理位置接收数据，其 中，该网格位置与虚拟条纹相关联，其中，该虚拟条纹与第一物理条纹和第二 物理条纹相关联，其中，第一物理位置是第一物理条纹的一部分，并且第二物 理位置是第二物理条纹的一部分。

根据以下描述和所附权利要求，本发明的其它方面将是显而易见的。

附图说明

图1示出了根据本发明的一个实施方式的系统。

图2A示出了根据本发明的一个实施方式的RAID网格。

图2B示出了根据本发明的一个实施方式的虚拟和物理条纹。

图2C示出了根据本发明的一个实施方式的存储模块。

图3A示出了根据本发明的一个实施方式的RAID立方体和RAID立方体的 各种视图。

图3B—3C示出了根据本发明的一个实施方式的示例性RAID立方体和 RAID网格。

图4A—4B示出了根据本发明的一个实施方式的数据结构。

图5A—5C示出了根据本发明的一个实施方式的流程图。

图6A—6C示出了根据本发明的一个或多个实施方式的示例。

图7A—7B示出了根据本发明的一个或多个实施方式的流程图。

图8A—8E示出了根据本发明的一个或多个实施方式的示例。

具体实施方式

现在将参考附图来详细地描述本发明的特定实施方式。在本发明的实施方 式的以下详细描述中，阐述了许多特定细节以便提供本发明的更透彻理解。然 而，对于本领域的技术人员将而言将显而易见的是可在没有这些特定细节的情 况下实施本发明。在其它情况下，未详细地描述众所周知的特征以避免不必要 地使本描述复杂化。

在图1—8E的以下描述中，在本发明的各种实施方式中，相对于附图描述 的任何部件可等同于相对于任何其它图描述的一个或多个类似名称的部件。简 洁地，将不会相对于每个图重复这些部件的描述。因此，通过引用而结合每个 图的部件的每个实施方式并假定为可选地存在于具有一个或多个类似名称的 部件的每个图内。另外，根据本发明的各种实施方式，图的部件的任何描述将 被解释为除相对于任何其它图中的相应类似名称部件所述的实施方式之外、与 之相结合或作为其替代可实现的可选实施方式。

一般地，本发明的实施方式涉及用于使用在网格位置水平实现镜像的多维 RAID方案来复制数据的方法和系统。更具体地，本发明的实施方式提供了一 种用于实现2D RAID方案和3D RAID方案的方法和系统，其中的2D RAID方 案和3D RAID方案均在网格位置水平实现镜像。

使用2D RAID方案，当在给定RAID条纹中存在超过两个错误时，可恢复 存储在实现此类RAID方案的RAID网格内的数据。相似地，使用3D RAID方 案，当在给定RAID条纹中存在超过两个错误时，可利用3D RAID方案恢复存 储在实现此类RAID方案的RAID立方体内的数据。在本发明的各种实施方式 中，当在超过一个独立故障域(IFD)中存在故障时，能够恢复所有数据。此 外，通过使得能够在网格位置水平实现镜像，本发明的实施方式在缓解与从持 久性储存器访问数据有关的潜在延迟问题的同时提供复制/冗余的附加水平。

在本发明的一个或多个实施方式中，IFD对应于故障模式，其导致给定位 置处的数据不可访问。每个IFD对应于存储阵列中的故障的独立模式。例如， 如果将数据存储在NAND闪存中，其中，NAND闪存是存储模块(其包括多个 NAND管芯)的一部分，则IFD可以是(i)存储模块，(ii)通道(即被存储 模块中的存储模块控制器(未示出)用来向NAND闪存写入数据的通道)，以 及(iii)NAND闪存管芯。

出于本发明的目的，如这里所使用的术语“RAID”指的是“独立器件冗余阵 列”。相应的，可使用任何类型的持久性存储器件来实现本发明的实施方式，其 中，可基于本发明的实施方式(参见例如图2B—4B)使RAID网格位置(参 见例如图2A)跨一个或多个持久性存储器分布。

图1示出了根据本发明的一个实施方式的系统。如图1中所示，该系统包 括一个或多个客户端(100A、100M)、RAID控制器(104)、存储器(106)、 可选地FPGA(102)以及存储阵列(108)。

在本发明的一个实施方式中，客户端(100A、100M)是任何系统或在系 统上执行的过程，其包括用以向RAID控制器(104)发布读请求或写请求的 功能。在本发明的一个实施方式中，每个客户端(100A、100M)可包括处理 器(未示出)、存储器(未示出)和持久性储存器(未示出)。在本发明的一 个实施方式中，RAID控制器(104)被配置成实现多维RAID方案，其包括以 与多维RAID方案一致的方式(参见图5A—5C)向存储阵列写入数据并以与 多维RAID方案一致的方式(参见图7A—7B)从存储阵列读取数据(包括重 构数据)。在本发明的一个实施方式中，RAID控制器(104)包括被配置成执 行指令以实现本发明的一个或多个实施方式的处理器，其中，该指令被存储在 位于RAID控制器(104)内或被操作连接到RAID控制器(104)的非临时计 算机可读介质(未示出)上。替换地，可使用硬件来实现RAID控制器(104)。 本领域的技术人员将认识到可使用软件和/或硬件的任何组合来实现RAID控制 器(104)。

在本发明的一个实施方式中，RAID控制器(104)被操作连接到存储器 (106)。存储器(106)可以是任何易失性存储器，包括但不限于动态随机存 取存储器(DRAM)、同步DRAM、SDR SDRAM以及DDR SDRAM。在本发 明的一个实施方式中，存储器(106)被配置成在各种数据(包括奇偶数据) 被存储在存储阵列中之前临时地存储此类数据。

在本发明的一个实施方式中，FPGA(102)(如果存在的话)包括用以出 于将数据存储在存储阵列(108)中的目的计算P和/或Q奇偶信息的功能和/ 或用以执行恢复使用(一个或多个)多维RAID方案存储的已损坏数据所需的 各种计算的功能。根据本发明的一个或多个实施方式，RAID控制器(104)可 使用FPGA(102)来卸载各种数据的处理。在本发明的一个实施方式中，存 储阵列(108)包括许多单独持久性存储设备，包括但不限于磁存储器件、光 存储器件、固态存储器件、相变存储器件、任何其它适当类型的持久性存储器 件或其任何组合。在整个说明书中，一般地可将每一个上述器件中称为存储模 块，除非另外指明。

本领域的技术人员将认识到虽然图1示出了FPGA，但可在没有FPGA的 情况下实现本发明。此外，本领域的技术人员将认识到在不脱离本发明的情况 下可使用其它部件来代替FPGA。例如，可使用(一个或多个)ASIC、(一个 或多个)图形处理单元(GPU)、(一个或多个)通用处理器、能够出于将数 据存储在存储阵列中的目的而计算P和/或Q奇偶信息和/或执行使用多维RAID 方案恢复存储的已损坏数据所需的各种计算的任何其它硬件器件、包括被配置 成出于将数据存储在存储阵列(108)中的目的而计算P和/或Q奇偶信息和/ 或执行使用多维RAID方案恢复存储的已损坏数据所需的各种计算的硬件、固 件和/或软件的组合的任何器件，或其任何组合。

图2A示出了根据本发明的一个实施方式的RAID网格。在本发明的一个 实施方式中，如果RAID控制器实现2D RAID方案或3D RAID方案(参见图 3A)，则RAID控制器将数据存储在RAID网格(200)中。图2A示出了根据 本发明的一个或多个实施方式的RAID网格的概念部分。RAID网格(200)包 括许多RAID网格位置，其中，与每个RAID网格位置相关联的数据最终被写 入到存储阵列中的两个(或更多)唯一物理位置(参见图2B)。RAID网格(200) 包括(i)数据网格(202)，其包括存储从客户端接收到的数据(即，客户端 已命令RAID控制器写入到存储阵列的数据)的RAID网格位置；(ii)行P奇 偶组(204)，其包括RAID网格位置，该RAID网格位置存储使用沿着行维度 的虚拟条纹中的RAID网格位置中的数据计算的P奇偶值(参见图2A、214 和图6A、602)；(iii)行Q奇偶组(206)，其包括RAID网格位置，该RAID 网格位置存储使用沿着行维度的虚拟条纹中的RAID网格位置中的数据计算的 Q奇偶值(参见图2A、214和图6A、602)；(iv)列P奇偶组(208)，其 包括RAID网格位置，该RAID网格位置存储使用沿着列维度的虚拟条纹中的 RAID网格位置中的数据计算的P奇偶值(参见图2A、214和图6A、604)； (v)列Q奇偶组(210)，其包括RAID网格位置，该RAID网格位置存储使 用沿着列维度的虚拟条纹中的RAID网格位置中的数据计算的Q奇偶值(参见 图2A、214和图6A、602)；和(vi)交叉奇偶组(212)，其包括使用(a) 来自行P奇偶组(204)中的RAID网格位置上的数据，(b)来自行Q奇偶 组(206)中的RAID网格位置的数据，(c)来自列P奇偶组(208)中的RAID 网格位置的数据以及(d)来自列Q奇偶组(210)中的RAID网格位置的数据 计算的奇偶值(下面描述)。

参考行(214),在本发明的一个实施方式中，通过对包括数据(例如，P_r2＝ f_P(D₁,D₂,D₃,D₄))的行(214)中的所有RAID网格位置应用P奇偶函数来计 算存储在行(214)中的表示为P_r2的RAID网格位置中的数据。同样地，在本 发明的一个实施方式中，通过对包括数据(例如，Q_r2＝f_Q(D₁,D₂,D₃,D₄))的 行(214)中的所有RAID网格位置应用Q奇偶函数来计算存储在行(214)中 的表示为Q_r2的RAID网格位置中的数据。

参考列(216)，在本发明的一个实施方式中，通过对包括数据(例如， P_C6＝f_P(D₅,D₂,D₆,D₇))的列(216)中的所有RAID网格位置应用P奇偶函 数来计算存储在列(216)中的表示为P_c6的RAID网格位置上的数据。同样地， 在本发明的一个实施方式中，通过对包括数据(例如，Q_C6＝f_Q(D₅,D₂,D₆,D₇)) 的列(216)中的所有RAID网格位置应用Q奇偶函数来计算存储在列(216) 中的表示为Q_C6的RAID网格位置上的数据。

参考交叉奇偶组(212)，在本发明的一个实施方式中，可以通过对行P 奇偶组(204)中的所有RAID网格位置应用P奇偶函数或者通过对列P奇偶 组(208)中的所有RAID网格位置应用P奇偶函数来计算存储在表示为I_r1的 RAID网格位置上的数据。例如，I_r1＝f_P(P_r1,P_r2,P_r3,P_r4)或者I_r1＝f_P(P_c5,P_c6, P_c7,P_c8).

在本发明的一个实施方式中，可以通过对行Q奇偶组(204)中的所有RAID 网格位置应用P奇偶函数或者通过对列P奇偶组(208)中的所有RAID网格 位置应用Q奇偶函数来计算存储在表示为I_r2的RAID网格位置上的数据。例如， I_r2＝f_P(Q_r1,Q_r2,Q_r3,Q_r4)或I_r2＝f_Q(P_c5,P_c6,P_c7,P_c8).

在本发明的一个实施方式中，可以通过对列Q奇偶组(210)中的所有RAID 网格位置应用P奇偶函数或者通过对行P奇偶组(204)中的所有RAID网格 位置应用Q奇偶函数来计算存储在表示为I_r3的RAID网格位置上的数据。例如， I_r3＝f_P(Q_c5,Q_c6,Q_c7,Q_c8)或者I_r3＝f_Q(P_c1,P_c2,P_c3,P_c4).

在本发明的一个实施方式中，可以通过对列Q奇偶组(210)中的所有RAID 网格位置应用Q奇偶函数或者通过对行Q奇偶组(206)中的所有RAID网格 位置应用Q奇偶函数来计算存储在表示为I_r4的RAID网格位置上的数据。例如， I_r4＝f_Q(Q_c1,Q_c2,Q_c3,Q_c4)或者I_r4＝f_Q(Q_c5,Q_c6,Q_c7,Q_c8).

在本发明的一个实施方式中，用来计算用于所有奇偶组的值的P和Q奇偶 函数可对应于用来实现RAID 6的任何P和Q奇偶函数。

如上文所讨论的，图2A中所示的RAID网格(200)表示RAID网格的概 念布局。然而，各种RAID网格位置的相对位置可跨一行和/或一列而改变。例 如，参考行(214)，包括数据(用“D”表示)的RAID网格位置和包括奇偶数 据的RAID网格位置(即，表示为“Pr”和“Qr”的RAID网格位置)的相对位置可 如下：<D₁，D₂，P_r2，D₃，Qr₂，D₄>、<P_r2，Q_r2，D₁，D₂，D₃，D₄>，或行(214) 内的任何其它布置。同样地，参考列(216)，包括数据(用“D”表示)的RAID 网格位置和包括奇偶数据的RAID网格位置(即，表示为“Pc”和“Qc”的RAID 网格位置)的相对位置可如下：<D₅，D₂，D₆，P_c6，D₆，Q_c6>、<P_c6，D₅， D₂，Q_c6，D₆，D₇>，或列(216)内的任何其它布置。

RAID控制器(或系统中的另一实体)可确定每个RAID网格位置被写入到 存储阵列中的哪个物理地址。可在从客户端接收到用于特定RAID网格的任何 数据(表示为“D”)之前进行此确定。替换地，可在将RAID网格位置上的数据 写入到存储阵列来进行该确定。

本领域的技术人员将认识到虽然图2D示出了为6×6的RAID网格，但在 不脱离本发明的情况下可使用任何其它维度来实现RAID网格。

在本发明的一个实施方式中，P奇偶值是里德-所罗门(Reed-Solomon) 综合症(syndrome)，并且同样地，P奇偶函数可对应于可生成里德-所罗门 综合症的任何函数。在本发明的一个实施方式中，P奇偶函数是XOR函数。

在本发明的一个实施方式中，Q奇偶值是里德-所罗门综合症，并且同样地， Q奇偶函数可对应于可生成里德-所罗门综合症的任何函数。在本发明的一个实 施方式中，Q奇偶值是里德-所罗门代码。在本发明的一个实施方式中，Q＝g⁰·D₀+g¹·D₁₊g²·D_2+…+g^n-1·D_n-1，其中，Q对应于关于图2A定义的Q奇偶值 中的任何一个，g是字段的发生器，并且D的值对应于数据(其可包括来自数 据网格的值和/或来自包括P或Q奇偶值的一个或多个行或列的值两者)。

本领域的技术人员将认识到虽然图2A中的RAID网格包括用于每个行和 列的P和Q奇偶，但在不脱离本发明的情况下可使用更多或更少的奇偶值来实 现本发明的实施方式。例如，每个行和列可仅包括P奇偶值。在另一示例中， 每个行和列可包括三个奇偶值。上述示例并不意图限制本发明。在本发明的一 个实施方式中，无论在实现本发明时使用的奇偶值的数目如何，奇偶值中的每 一个是里德-所罗门综合症。

图2B示出了根据本发明的一个实施方式的虚拟和物理条纹。在本发明的 一个实施方式中，每个RAID网格位置(例如，222)与持久性存储器(218， 220)中的两个物理位置相关联。出于本描述的目的，可将两个物理位置称为 左物理位置(PL_L)和右物理位置(PL_R)。仅仅是出于描述本发明的目的而包 括上述标记且其并不意图限制本发明。

上述物理位置(PL_L(218)，PL_R(220))中的每一个对应于持久性储 存器中的不同物理位置。在本发明的一个实施方式中，物理位置可在同一存储 模块上，但是在存储模块的不同NAND芯片上(在同一NAND管芯上)。替 换地，每个物理位置可位于单独存储模块上。

参考图2B，可将图2A中所示的RAID网格中的每个行和列称为虚拟条纹。 例如，如图2B中所示，一个虚拟条纹是行(214)，其中，行(214)由RAID 网格位置构成(表示为D₁、D₂、D₃、P_r2、Qr₂、D₄)。如上文所讨论的，每个 RAID网格位置与持久性储存器中的两个物理位置相关联。据此，从而每个虚 拟条纹与表示为左物理条纹(PSL)和右物理条纹(PSR)的两个物理条纹 (214L，214R)相关联。仅仅是出于描述本发明的目的而包括上述标记且其 并不意图限制本发明。PSL(214L)包括与用于行(214)的RAID网格位置 相关联的所有PL_Ls，和PSR(214R)包括与用于行(214)的RAID网格位置 相关联的所有PL_Rs。如下面所讨论的，使用PSL和PSR中的数据值来计算 PSL和PSR中的每一个中的奇偶值。如果虚拟条纹在镜像模式下操作，则用 于给定虚拟条纹中的PSL和PSR中的奇偶值相同。替换地，如果虚拟条纹在 非镜像模式下操作，则用于给定虚拟条纹中的PSL和PSR中的奇偶值可不同。

参考图2B，通过对包括PSL(例如，PL_5L＝f_P(PL_1L,PL_2L,PL_3L,PL_4L))中 的数据(与奇偶值相对)的PL_Ls应用P奇偶函数来确定PL_5L的值。同样地， 通过对包括PSL(例如，PL_6L＝f_Q(PL_1L,PL_2L,PL_3L,PL_4L)中的数据(与奇偶值 相对)的PL_Ls应用Q奇偶函数来确定PL_6L的值。给定PSL和PSR中的数据 值和奇偶值的位置对应于相应虚拟条纹中的数据值和奇偶值的位置。例如，在 图2B中，虚拟条纹(214)P奇偶值与RAID网格位置P_2R相关联。因此，PL_5L 和PL_5R包括P奇偶值。

图2C示出了根据本发明的一个实施方式的存储模块。如图2C中所示， 可将与给定RAID网格位置相关联的值(数据或奇偶)写入到同一存储模块 (224)，但是到存储模块中的不同芯片(226、228)。在本发明的一个实施 方式中，可使用以下n元组来表示对应于存储模块中的物理位置的物理地址： ＜存储模块、通道、芯片、平面、块、页面、字节＞。在此类实施方式中且参 考图2C，用于PLL和PLR的物理位置可与以下物理位置相关联：PL_L：＜存 储模块、通道、芯片0、平面、块、页面、字节＞和PL_R：＜存储模块、通道、 芯片1、平面、块、页面、字节＞。本领域的技术人员将认识到的是在不脱离 本发明的情况下可使用其它n元组来表示存储模块中的物理地址。

图3A示出了根据本发明的一个实施方式的RAID立方体和RAID立方体的 各种视图。如图3A中所示，RAID立方体(300)对应于RAID网格的概念堆 栈(仅仅为了明了起见，在RAID立方体(300)内示出了RAID网格(304))。 如上文所讨论的，RAID控制器(或系统中的另一实体)选择将在其中存储用 于每个RAID网格位置的数据的存储阵列内的物理地址。在本发明的一个实施 方式中，可根据RAID网格(或RAID立方体)被设计成针对其进行保护的IFD 来确定物理地址的选择。换言之，可以针对一个或多个IFD中的故障进行保护 的方式来选择物理地址。例如，如图3A中所示，用于给定RAID网格(304) 的每个RAID网格位置(未示出)被写入到使用来自IFD 1和IFD 2的唯一一 对值选择的存储阵列(未示出)中的物理地址(或者将被写入到物理地址)， 但是对于IFD 3而言具有相同的值。例如，如果存储阵列中的数据被存储在 NAND闪存中，其中，NAND闪存是存储模块(其包括多个NAND管芯)的一 部分，则IFD可如下：(i)IFD 1＝存储模块，(ii)IFD 2＝通道，并且(iii) IFD 3＝NAND管芯。因此，在给定RAID网格中，每个RAID网格位置上的数 据被写入到存储模块(IFD 1)和通道(IFD 2)的唯一组合，但是被写入到同 一NAND管芯(在每个存储模块中上)。本领域的技术人员将认识到本发明不 限于上面所述的三个独立故障域。此外，本领域的技术人员将认识到本发明不 限于包括NAND闪存的存储阵列。

继续图3A，如上文所讨论的，RAID立方体(300)是RAID网格的概念 堆栈。更具体地，在本发明的一个实施方式中，RAID立方体(300)可包括(i) 数据部分(314)，其包括两个或更多RAID网格(304、306、308)(参见 图2A)和奇偶部分(316)，其包括P奇偶RAID网格(310)和Q奇偶RAID 网格(312)。

在本发明的一个实施方式中，数据部分(314)中的RAID网格(304，306， 308)包括奇偶数据(参见图2A)，其允许仅使用RAID网格内的数据(包括 奇偶数据)来恢复RAID网格内的数据。在本发明的一个实施方式中，RAID 立方体被布置成使得可使用来自其它RAID网格的数据(包括奇偶数据)(在 数据部分(314)和奇偶部分(316)两者中)来恢复用于给定RAID网格(304、 306、308)中的给定RAID网格位置的数据。在本发明的一个实施方式中，RAID 立方体的奇偶部分(316)使得能够实现此类恢复机制。

在本发明的一个实施方式中，P奇偶RAID网格(310)是与底层RAID网 格(304、306、308)相同的维度，其中，通过对数据部分(316)(参见图 3B—3C)中的来自RAID网格的数据(包括奇偶数据)应用P奇偶函数(例如， XOR函数)来计算P奇偶RAID网格内的每个RAID网格位置上的数据。同样 地，Q奇偶RAID网格(316)是与底层RAID网格(304、306、308)相同的 维度，其中，通过对数据部分(316)(参见图3B—3C)中的来自RAID网格 的数据(包括奇偶数据)应用Q奇偶函数来计算Q奇偶RAID网格内的每个 RAID网格位置上的数据。

图3B—3C示出了根据本发明的一个或多个实施方式的填充RAID立方体 的示例。上述示例并不意图限制本发明的范围。

考虑图3A中描述的RAID立方体，其包括RAID网格1(304)、RAID 网格2(306)、RAID网格3(308)、P奇偶RAID网格(310)以及Q奇偶 RAID网格(312)。此外，RAID立方体中的每个RAID网格(304、306、308) 包括跨IFD 1和IFD 2写入但具有IFD 3的恒定值的RAID网格位置。因此， 在本发明的一个实施方式中，可使用以下各项来恢复RAID网格中的RAID网 格位置(“目标RAID网格位置”)的值：(i)仅目标RAID网格位置位于其中 的行或列中的RAID网格位置的值；(ii)使用目标RAID网格位置位于其中的 RAID网格内的任何RAID网格位置的值；或者(iii)使用目标RAID网格位置 位于其中的RAID立方体内的任何RAID网格位置的值。换言之，在本发明的 一个实施方式中，RAID网格和/或RAID立方体内的数据和奇偶值的布置允许 当在目标RAID网格位置位于其中的行和列中的每一个中存在超过两个错误时 恢复目标RAID网格位置上的值。

参考图3B，图3B包括三个RAID网格(304、306、308)，其构成RAID 立方体(300)的数据部分(314)。RAID网格(304、306、308)中的每一 个中的RAID网格位置中的每一个包括3元组，其定义RAID网格位置中的数 据被写入其中的存储阵列中的物理位置。在本示例中，3元组中的元素如下对 应于IFD：<IFD1，IFD2，IFD3>。3元组图示出如何跨各种IFD选择存储阵列 中的物理位置。特别地，RAID网格1中的每个RAID网格位置包括IFD1和IFD2 的唯一组合，但对于IFD3而言是相同的值。例如，如果IFD1是存储模块，IFD2 是通道，并且IFD3是NAND管芯，则3元组<4,2,1>指示特定RAID网格位置 上的数据将被使用通道2而写入到与存储模块4中的NAND管芯1中的(一个 或多个)物理位置相对应的(一个或多个)物理地址。同样地，3元组<2,3,1> 指示特定RAID网格位置上的数据将被使用通道3而写入到与存储模块2中的 NAND1中的(一个或多个)物理位置相对应的(一个或多个)物理地址。

以与RAID网格1(304)类似的方式来布置RAID网格2(306)和RAID 网格3(308)。然而，用于RAID网格2(306)中的RAID网格位置的3元 组中的IFD3的值不同于用于针对RAID网格1(304)的RAID网格位置的3 元组中的IFD3的值。此外，用于RAID网格3(308)中的RAID网格位置的 3元组中的IFD3的值不同于用于针对RAID网格1(304)和RAID网格2(306) 的RAID网格位置的3元组中的IFD3的值。

参考图3C，以与RAID网格1(304)、RAID网格2(306)和RAID网 格3(308)类似的方式布置P奇偶RAID网格(310)中的每个RAID网格位 置上的数据。此外，如上所述，使用来自RAID立方体(即，RAID网格1(304)、 RAID网格2(306)以及RAID网格3(308))中的每个数据网格中的一个 RAID网格位置上的数据来计算P奇偶RAID网格(310)中的每个RAID网格 位置上的数据的值。例如，通过对来自以下RAID网格位置的数据应用P奇偶 函数(例如，XOR函数)来确定P奇偶RAID网格(310)中的RAID网格位 置<1，1，4>处的数据的值：(i)来自RAID网格1(304)<1,1,1>的数据， (ii)来自RAID网格2(306)<1,1,2>的数据，以及(iii)来自RAID网格3 (308)<1,1,3>的数据。以类似方式计算用于P奇偶RAID网格(310)中的 其它RAID网格位置上的数据的值。

此外，以与RAID网格1(304)、RAID网格2(306)以及RAID网格3 (308)类似的方式布置Q奇偶RAID网格(312)中的每个RAID网格位置上 的数据。此外，如上所述，使用来自RAID立方体(即，RAID网格1(304)、 RAID网格2(306)以及RAID网格3(308))中的每个数据网格中的一个 RAID网格位置上的数据来计算Q奇偶RAID网格(312)中的每个RAID网格 位置上的数据的值。例如，通过对来自以下RAID网格位置的数据应用Q奇偶 函数(如上所述)来确定Q奇偶RAID网格(312)中的RAID网格位置<1，1， 5>处的数据的值：(i)来自RAID网格1(304)<1,1,1>的数据，(ii)来自 RAID网格2(306)<1,1,2>的数据，以及(iii)来自RAID网格3(308)<1,1,3> 的数据。以类似方式计算用于Q奇偶RAID网格(312)中的其它RAID网格位 置上的数据的值。

图4A—4B示出了根据本发明的一个或多个实施方式的系统中的各种部件 之间的关系。在本发明的一个实施方式中，RAID控制器包括一个或多个数据 结构以跟踪图4A—4B中所示的关系。在不脱离本发明的情况下，RAID控制 器可跟踪以下关系中的一个或多个。换言之，RAID控制器可在不跟踪图 4A—4B中所示的所有关系的情况下实现本发明。

在本发明的一个实施方式中，每个RAID立方体(400)与两个或更多RAID 网格(402A、402N)相关联。如果RAID控制器并未实现RAID网格，则不跟 踪RAID立方体与RAID网格之间的关系。

每个RAID网格(402)与两个或更多网格位置(也称为RAID网格位置) (404A、404N)相关联。与每个RAID网格相关联的网格位置的数目可基于 RAID网格的实施方式而改变。

如图2B中所示，每个网格位置(404)与至少两个物理位置(406A 406B) 相关联。如果存在与网格位置相关联的两个物理位置，则可将物理位置称为左 物理位置(406A)和右物理位置(406B)。在本发明的一个实施方式中，与 特定RAID网格相关联的所有网格位置与相同数目的物理位置相关联。然而， 与由RAID控制器实现的其它RAID网格相关联的网格位置可与不同数目的物 理位置相关联。

如上文所讨论的，每个RAID网格(402)与一个或多个虚拟条纹(408A、 408N)(参见图2B)相关联，其中，每个虚拟条纹(408)由与RAID网格(402) 相关联的各组网格位置(404A、404N)构成。给定网格位置(404A、404N) 可与多个虚拟条纹(408)相关联。

如例如图2B中所示，每个虚拟条纹(408)与至少两个物理条纹(401A、 410B)相关联。如果存在与虚拟条纹相关联的两个物理条纹，则可将该物理条 纹称为左物理条纹(410A)和右物理条纹(410B)。在本发明的一个实施方 式中，与特定RAID网格相关联的所有虚拟条纹与相同数目的物理条纹相关联。 然而，与由RAID控制器实现的其它RAID网格相关联的虚拟条纹可与不同数 目的物理条纹相关联。

每个虚拟条纹(408)与存储模式(412)相关联。该存储模式可以是镜像 模式或非镜像模式。在镜像模式下，与虚拟条纹相关联的物理条纹包括相同的 数据(包括奇偶数据)。在非镜像模式下，与虚拟条纹相关联的物理条纹可包 括不同数据(包括奇偶数据)。在本发明的一个实施方式中，给定RAID网格 可包括处于镜像模式的虚拟条纹和处于非镜像模式的虚拟条纹。在本发明的替 换实施方式中，每个网格位置基础可指定存储模式，与每个虚拟条纹相反。在 此类实施方式中，给定虚拟条纹可包括实现镜像和非镜像模式两者的网格位 置。

每个物理位置与状态(414)相关联。可将状态(414)设定为已填充(表 示数据(或奇偶数据)已被写入到物理位置)或空(表示没有数据(或奇偶数 据)已被写入到该位置)。如果RAID控制器在RAID控制器中已识别到写入 到物理位置的数据，则可将物理位置的状态设置成已填充(参见例如图5A，步 骤516)。RAID控制器可将每个物理位置的状态初始化为空。

每个物理位置(406)与定义持久性储存器内的物理位置的物理地址(416) 相关联。可使用以下n元组来指定物理地址：＜存储模块、通道、芯片、平面、 块、页面、字节＞。在不脱离本发明的情况下，可使用其它n元组来表示物理 地址。此外，在不脱离本发明的情况下，可使用其它形式的物理地址。

每个物理地址(406)还与逻辑地址(418)相关联，例如<对象，偏移> (400)，其从客户端的角度出发识别数据。在不脱离本发明的情况下可使用 任何形式的逻辑地址。RAID控制器可提供用于将特定逻辑地址转换成特定物 理地址或者另外使特定逻辑地址与特定物理地址相关联的机制。

虽然在图4A—4B中未示出，但RAID控制器还可保持关于RAID网格几 何结构的信息。RAID网格几何结构包括但不限于RAID网格的尺寸、RAID网 格的每个维度的IFD、RAID立方体的尺寸、与RAID立方体的每个维度相关联 的IFD以及每个RAID网格内的每个行和/或列内的每个P和Q奇偶值(包括 交叉奇偶组内的奇偶值(参见图2A))的位置。

图5A—5C示出了根据本发明的一个或多个实施方式的流程图。更具体地， 图5A—5C示出了根据本发明的一个或多个实施方式的用于在存储阵列中存储 数据的方法。虽然连续地提出并描述流程图中的各种步骤，但本领域的技术人 员将认识到可按照不同的顺序执行某些或所有步骤，可将其组合或省略，并且 可并行地执行某些或所有步骤。在本发明的一个实施方式中，可并行地执行图 5A、5B和5C中所示的方法。

参考图5A，在步骤500中，从客户端接收到用以写入数据的请求。在本 发明的一个实施方式中，该请求包括客户端正在请求写入到存储阵列的数据的 逻辑地址。在步骤502中，确定存储模式(例如，镜像或非镜像)。在本发明 的一个实施方式中，基于来自客户端的请求中的信息或者基于在单独请求中或 用另一通信机制传送到客户端的信息来确定存储模式。在本发明的其它实施方 式中，由RAID控制器(或系统中的另一过程或部件)来确定存储模式。在此 类实施方式中，RAID控制器(或系统中的另一过程或部件)基于例如策略设 置、关于发布写请求的客户端的信息、QoS保证和/或关于数据的信息(例如， 尺寸、类型等)来确定存储模式。

在步骤504中，进行关于是否存在实现在步骤502中确定的存储模式的(一 个或多个)可用网格位置的确定。在本发明的一个实施方式中，步骤504中的 确定涉及到例如使用如图4A—4B中所描述的存储信息的数据结构来搜索当前 活动RAID网格(即，其中图2A中的数据网格部分未被填充的RAID网格)中 的可用网格位置。如果存在(一个或多个)可用网格位置，则识别该(一个或 多个)网格位置，并且过程前进至步骤512；否则，该过程前进至步骤506。

在步骤506中，分配新的RAID网格。在步骤508中，从该新RAID网格 中选择虚拟条纹。在步骤510中，用于所选虚拟条纹的存储模式具有对应于在 步骤502中确定的存储模式的存储模式。

在步骤512中，选择网格位置。在本发明的一个实施方式中，该网格位置 选自在步骤504中识别的网格位置或在步骤508中选择的新虚拟条纹中的网格 位置。

在本发明的一个实施方式中，如果每个网格位置基础而不是每个虚拟条纹 基础确定存储模式，则可对特定网格位置而不是虚拟条纹执行步骤508和510。

继续图5A，在步骤514中，确定与网格位置相关联的(一个或多个)物 理位置。在本发明的一个实施方式中，所识别的物理位置的数目取决于在步骤 502中确定的存储模式。例如，如果存储模式是非镜像的，则仅识别与网格位 置相关联的一个物理位置。替换地，如果存储模式是镜像的，则识别与网格位 置相关联的至少两个物理位置。

在步骤516中，RAID控制器更新数据结构中的一个或多个以反映数据将 被写入到(一个或多个)物理位置(参见图4A—4B)。可每当数据将被写入 到存储阵列时执行图5A中所示的步骤。

参考图5B，图5B示出了根据本发明的一个或多个实施方式的用于向存储 阵列写入RAID网格的方法。参考图5B，在步骤520中，进行关于给定RAID 网格中的数据网格(例如，图2A中的202)是否被填充的确定。在本发明的 一个实施方式中，当与数据网格中的网格位置相关联的所有物理位置的所有状 态被设置为已填充时，数据网格为“被填充”。在本发明的一个实施方式中，使 用关于图4A和4B所述的数据结构中的一个或多个来进行此确定。如果给定 RAID网格内的数据网格被填充，则该过程前进至步骤522；否则，该过程结 束。

在步骤522中，使用来自相应物理位置的适当值针对与行P奇偶组(例如， 图2A中的204)中的RAID网格位置相对应的每个物理位置计算P奇偶(参 见例如上文所讨论的图2B)。在步骤524中，使用来自相应物理位置的适当 值针对与行Q奇偶组(例如，图2A中的206)中的RAID网格位置相对应的 每个物理位置计算Q奇偶(参见例如上文所讨论的图2B)。在步骤526中， 使用来自相应物理位置的适当值针对与列P奇偶组(例如，图2A中的208) 中的RAID网格位置相对应的每个物理位置计算P奇偶(参见例如上文所讨论 的图2B)。在步骤528中，使用来自相应物理位置的适当值针对与列Q奇偶 组(例如，图2A中的210)中的RAID网格位置相对应的每个物理位置计算Q 奇偶(参见例如上文所讨论的图2B)。

在步骤530中，使用来自与行P奇偶组(例如，图2A中的204)、行Q 奇偶组(例如，图2A中的206)、行Q奇偶组(例如，图2A中的206)以 及列Q奇偶组(例如，图2A中的210)中的一个或多个中的RAID网格位置 相对应的物理位置的适当值而计算用于与交叉奇偶组(例如，图2A中的212) 中的RAID网格位置相对应的每个物理位置的奇偶值。

在步骤532中，将与对应于用于RAID网格的RAID网格位置的每个物理 位置相关联的数据写入到存储阵列中的适当物理地址。在本发明的一个实施方 式中，分两个阶段将数据(包括奇偶数据)写入到存储阵列。在第一阶段中， 将与每个物理位置相关联的数据或奇偶数据并行地写入到适当的存储模块，所 述每个物理位置与RAID网格中的网格位置的左部分相关联。在第二阶段中， 将与每个物理位置相关联的数据或奇偶数据并行地写入到适当的存储模块，所 述每个物理位置与RAID网格中的网格位置的右部分相关联。下面在图6A—6C 中描述两阶段写入的示例。在本发明的一个实施方式中，从相对于图4A—4B 所述的数据结构中的一个或多个获得要将用于每个RAID网格位置的数据写入 到那里的物理地址。在步骤534中，更新关于图4A—4B所述的一个或多个数 据结构以反映RAID网格已被写入到存储阵列。

虽然以上实施方式描述了并行地写入用于RAID网格的所有数据(包括奇 偶数据)，但在不脱离本发明的情况下可将数据(包括奇偶数据)的写入分阶 段。例如，可将数据(不包括奇偶数据)并行地写入到存储阵列，同时可在稍 后的时间将奇偶数据写入到存储阵列。在不脱离本发明的情况下可以其它方式 将写入分阶段。

在本发明的一个实施方式中，如果RAID控制器正在实现3D RAID方案， 则RAID控制器可执行图5C中所示的方法。参考图5C，在步骤536中，进行 关于RAID立方体的数据部分是否被填充的确定。在本发明的一个实施方式中， 当与RAID立方体的数据部分中的网格位置相对应的所有物理位置的状态被设 置为被填充，则RAID立方体的数据部分被填充。如果RAID立方体的数据部 分被填充，则该过程前进至步骤538；否则过程结束。在本发明的一个实施方 式中，使用关于图4A—4B所述的数据结构中的一个或多个来进行此确定。

在步骤538中，计算用于与P奇偶RAID网格(例如，图3A中的310) 中的RAID网格位置相对应的每个物理位置的P奇偶值。在本发明的一个实施 方式中，使用从RAID立方体的数据部分(例如，图3A中的314)中的每个 RAID网格获得的一个值来计算用于每个RAID网格位置的值。

在步骤540中，计算用于与Q奇偶RAID网格(例如，图3A中的312) 中的RAID网格位置相对应的每个物理位置的Q奇偶值。在本发明的一个实施 方式中，使用从RAID立方体的数据部分(例如，图3A中的314)中的每个 RAID网格位置获得的一个值来计算用于每个RAID网格位置的值。

在步骤542中，将与每个物理位置相关联的数据写入到存储阵列中的适当 物理地址，所述每个物理位置与奇偶RAID网格(例如，P奇偶RAID网格和 Q奇偶RAID网格)中的RAID网格位置相对应。在本发明的一个实施方式中， 从关于图4A—4B所述的数据结构中的一个或多个获得要将用于每个RAID网 格位置的数据写入到那里的物理地址。在步骤544中，更新关于图4A-4B所述 的一个或多个数据结构以反映RAID立方体已被写入到存储阵列。

图6A—6C示出了根据本发明的一个或多个实施方式的示例。上述示例并 不意图限制本发明的范围。

参考图6A，示出了包括36个网格位置(GL)的RAID网格(600)。此 外，对应于上述GL的物理位置跨存储模块和通道分布，如图6A中所示。考 虑其中数据的四个部分(D_1A—D_4A)被写入到对应于虚拟条纹(602)中的GL₁、 GL₂、GL₃、GL₄的物理位置的情形。此外，出于本示例的目的，假设虚拟条纹 正在实现镜像模式，并且GL₅包括P奇偶值且GL₆包括用于虚拟条纹(602) 的Q奇偶值。以下表格概述了当虚拟条纹正在实现镜像模式时的存储在具有虚 拟条纹(602)的每个相应物理位置上的数据。

表1：镜像模式

考虑其中数据的八个部分(D_1A—D_4A和D_1B—D_4B)被写入到对应于虚拟条 纹(602)中的GL₁、GL₂、GL3、GL₄的要被写入的物理位置的替换情形。此 外，出于本示例的目的，假设虚拟条纹正在实现非镜像模式，并且GL₅包括P 奇偶值且GL₆包括用于虚拟条纹(602)的Q奇偶值。以下表格概述了虚拟条 纹正在实现非镜像模式时的存储在具有虚拟条纹(602)的每个相应物理位置 上的数据。

表2：非镜像模式示例

参考图6A，可以与如上文关于虚拟条纹(602)所述的相同方式来填充虚 拟条纹(604)。

在本发明的一个实施方式中，一旦RAID网格中的每个物理位置与来自客 户端的数据或奇偶数据(即，P或Q奇偶数据)相关联，则RAID网格准备好 被写入到存储模块。该写入过程分成两个阶段。在第一阶段中，将与每个物理 位置相关联的数据或奇偶数据并行地写入到存储阵列中的适当位置，所述每个 物理位置与网格位置的左部分相关联。在第二阶段中，将与每个物理位置相关 联的数据或奇偶数据并并行地写入到存储阵列中的适当位置，所述每个物理位 置与网格位置的右部分相关联。

以下是根据镜像模式将数据(表示为D)写入到存储阵列的示例。在本示 例中，假设数据(D_1A—D_4A)(如上所述)将被写入到存储阵列。当RAID网 格(包括虚拟条纹(602))准备好被写入到存储阵列时，RAID控制器(未示 出)并行地在写入过程的阶段1中发布三十六个写命令。具体地，向每个存储 模块发布六个写命令，其中，用于给定存储模块的每个写命令以存储模块上的 不同芯片为目标。表3示出了写入过程的阶段1期间的对应于虚拟条纹(602) 的“左部分”的写命令的子集。

表3：阶段1用于网格位置的“左部分”的写命令

在写入过程的阶段1之后，RAID控制器在写入过程的阶段2中并行地发 布三十六个写命令。具体地，向每个存储模块发布六个写命令，其中，用于给 定存储模块的每个写命令以存储模块上的不同芯片为目标。表4示出了写入过 程的阶段2期间的对应于虚拟条纹(602)的“右部分”的写命令的子集。

表4：阶段2用于网格位置的“右部分”的写命令

图6B示出了在每个上述写入阶段期间每个闪存模块中的哪个芯片主动地 写入(W)或可用于服务于读请求(R)。图6C示出了在已发布表3和4中 的命令之后的存储模块中的12个芯片的状态。

图7A—7B示出了根据本发明的一个或多个实施方式的流程图。更具体地， 图7A—7B示出了根据本发明的一个或多个实施方式的用于从存储阵列获得数 据的方法。虽然连续地提出并描述流程图中的各种步骤，但本领域的技术人员 将认识到可按照不同的顺序执行某些或所有步骤，可将其组合或省略，并且可 并行地执行某些或所有步骤。在本发明的一个实施方式中，可并行地执行图7A 和7B中所示的方法。

在步骤700中，接收用以从持久性储存器获得数据的请求。在本发明的一 个实施方式中，该请求可以是由客户端分布的读请求。在本发明的一个实施方 式中，该请求可指定与数据相关联的逻辑地址。

在步骤702中，获得与所请求数据相关联的(一个或多个)物理地址。在 本发明的一个实施方式中，可使用上文关于图4A—4B所述的数据结构来确定 上述物理地址。

在步骤704中，进行关于数据是否被镜像的确定。在本发明的一个实施方 式中，此确定可包括(i)确定与物理地址相关联的网格位置，(ii)确定与网 格位置相关联的虚拟条纹，以及(iii)确定与在(ii)中识别的虚拟条纹相关联 的存储模式。如果每个网格水平设定存储模式，则可通过(i)确定与物理地址 相关联的网格位置和(ii)确定与在(i)中识别的网格位置相关联的存储模式 来执行在步骤704中的确定。如果虚拟储存器正在实现镜像模式，则数据被镜 像且过程前进至步骤706；否则过程前进至步骤708。

当数据被镜像时，可从至少两个不同的物理位置获得数据。在这种情况下， 在步骤706中，进行关于数据位于其中的物理位置中的任何一个是否为非占用 (即，数据位于其上面的芯片当前并未服务于写或擦除请求)的确定。如果数 据位于其中的任何物理位置是非占用的，则过程前进至步骤710；否则过程前 进至步骤708。

在步骤708中，则使用在步骤702中获得的物理地址将读请求发布到持久 性储存器。在步骤710中，使用物理地址(在步骤702中获得)来向持久性储 存器发布读请求，对应于非占用物理位置。在步骤712中，从对应于请求中的 物理地址的物理位置获得数据(经由步骤708或710)。

参考图7B，在步骤714中，进行关于在步骤712中获得的数据是否被损 坏的确定。在本发明的一个实施方式中，RAID控制器可实现用于确定数据是 否被损坏的任何已知方法(例如，检查和)。如果数据未被损坏，则过程前进 至步骤716；否则过程前进至步骤718。在步骤716中，将数据返回到客户端， 并且该过程结束。在本发明的另一实施方式中，如果不能获得数据—例如，因 为持久性储存器被损坏或拔掉插头，或者读命令失败，则过程可前进至步骤 718。

在步骤718中，RAID控制器确定从其获得数据的RAID网格。在步骤720 中，RAID控制器尝试使用数据的镜像副本(如果可用的话)(参见图2A)和 /或使用与包括数据的物理位置位于其中的行和/或列内的其它RAID网格位置 相对应的物理位置来重构数据。

在步骤722中，进行关于步骤720中的重构尝试是否成功的确定。在本发 明的一个实施方式中，RAID控制器可实现用于确定重构尝试是否成功的任何 已知方法(例如，检查和)。如果步骤722中的重构尝试成功，则过程前进至 步骤724；否则过程前进至步骤727。在步骤724中，将重构数据返回到客户 端且该过程结束。

在步骤726中，RAID控制器尝试重构与RAID网格中的其它行和/或列中 的其它RAID网格位置相对应的物理位置来重构数据。在步骤727中，进行关 于步骤726中的重构尝试是否成功的确定。在本发明的一个实施方式中，RAID 控制器可实现用于确定重构尝试是否成功的任何已知方法(例如，检查和)。 如果步骤726中的重构尝试成功，则过程前进至步骤724；否则过程前进至步 骤730。

在步骤730中，RAID控制器尝试使用与RAID立方体中的其它RAID网 格相对应的物理位置来重构数据。在步骤732中，进行关于步骤730中的重构 尝试是否成功的确定。在本发明的一个实施方式中，RAID控制器可实现用于 确定重构尝试是否成功的任何已知方法(例如，检查和)。如果步骤730中的 重构尝试成功，则过程前进至步骤734；否则过程前进至步骤736。在步骤734 中，将重构数据返回到客户端且该过程结束。在步骤736中，RAID控制器向 客户端返回错误，其指示不能由RAID控制器从存储阵列检索所请求的数据。

本领域的技术人员将认识到的是使用RAID立方体中的其它RAID网格来 重构数据仅在RAID控制器正在实现3D RAID方案的情况下发生。

图8A—8E示出了根据本发明的一个或多个实施方式的示例。上述示例并 不意图限制本发明的范围。参考图8A，考虑其中系统包括RAID网格(800) 的情形，该RAID网格包括一组网格位置(参见例如2A)。此外，该网格位置 (未示出)与全部实现镜像模式的一组虚拟条纹(未示出)相关联。最后，如 图8A中所示，每个网格位置(未示出)与两个物理位置(参见例如2B)相关 联。结果，RAID网格(800)与两组物理位置——左物理位置(800L)和右物 理位置(800R)相关联。

参考图8B，考虑其中客户端请求位于左物理位置(800L)中的PL_L1和右 物理位置(800R)中的PL_R1处的数据的情形。然而，PL_L1和PL_R1中的数据被 损坏(如阴影所表示的)。RAID控制器首先尝试(按照图7B中的步骤720) 使用来自行(804)和/或列(802)的物理位置的数据来重构PL_L1中的数据。 然而，由于行(804)和列(802)每个包括已损坏数据的三个物理位置，所以 不能仅使用来自行(804)和列(802)的数据来恢复PL_L1中的数据。

参考图8C，RAID控制器尝试(按照图7B中的步骤726)使用来自左物 理位置(800L)中的其它物理位置的数据来重构PL_L1中的数据。在本示例中， 不存在不能用来最终重构PL_L1的左物理位置(800L)中的行或列。然而，RAID 控制器可以与左物理位置(800L)中的行(806)中的其余物理位置上的数据 相组合地使用来自右物理位置(800R)中的PL_R2(参见图8B)的数据来重构 行(806)中的所有已损坏数据。参考图8D，基于行(806)中的已损坏数据 的重构，RAID控制器能够重构列(808)中的所有已损坏数据。最后，参考图 8E，基于列(808)中的已损坏数据的重构，RAID控制器能够使用行(810) 中的其它未损坏数据来重构PL_L1中的数据。在本发明的一个实施方式中，作为 图7B的步骤720和726的一部分来执行如图8B—8E中所示的各种已损坏数 据的重构。

虽然在图8A—8E中未示出，但如果不能仅使用RAID网格中的数据来重 构PL_L1中的数据，则RAID控制器将尝试使用RAID立方体(未示出)内的其 它RAID网格中的数据来重构PL_L1中的数据(按照图7B中的步骤7300)，如 果RAID控制器正在实现3D RAID方案的话。

本领域的技术人员将认识到的是虽然相对于沿着IFD将数据存储在存储阵 列中和/或将数据存储在NAND闪存中而描述了本发明的各种实施方式，但在 不脱离本发明的情况下可在任何多维存储器件阵列上实现本发明的实施方式。 例如，可使用存储器件(磁、光、固态或任何其它类型的存储器件)的二维阵 列来实现本发明的一个或多个实施方式，其中，用于RAID网格中的每个RAID 网格位置的数据被存储在单独存储器件上。

此外，在本发明的一个实施方式中，在RAID控制器正在使用存储器件的 二维阵列来实现3D RAID方案的情况下，RAID控制器可使用以下n元组来存 储用于每个RAID网格位置的数据：＜存储器件x，存储器件y，逻辑块地址 (LBA)z＞，其中，x和y是存储器件阵列的维度。此外，用于给定RAID网 格而言，LBA对于用于单个RAID网格的每个RAID网格位置而言是恒定的； 然而，LBA跨RAID立方体中的RAID网格不同。

用于使用二维存储器件来实现本发明的实施方式的上述示例并不意图限 制本发明的范围。

本领域的技术人员将认识到虽然已关于2D RAID方案和3D RAID方案描 述了本发明，但可将本发明的实施方式扩展至任何多维RAID方案。

可使用由系统中的一个或多个处理器执行的指令来实现本发明的一个或 多个实施方式。此外，此类指令可对应于存储在一个或多个非临时计算机可读 介质上的计算机可读指令。

虽然已相对于有限数目的实施方式描述了本发明，但受益于本公开的本领 域的技术人员将认识到可以设计不脱离如在这里公开的本发明的范围的其它 实施方式。因此，应仅由所附权利要求来限制本发明的范围。