用于数据存储系统中的错误检测和纠正的方法和装置

摘要

本文公开了用于处理所存储的具有纠错位的数据以检测并且在一些实例中以纠正错误的数据处理方法和装置。数据处理包括，例如，通过对比从存储元件取回的数据的散列值与在存储过程中所生成的数据的散列值来检测错误的技术。例如，根据本发明的方法的一个实施例包括：从存储设备读取与纠错位一起存储的数据，对从存储设备读取的数据执行散列操作以生成第一散列值，将所述第一散列值与对应于所述数据的先前生成的散列值进行对比，以及当所述第一散列值不匹配所述先前生成的散列值时，确定发生了读错误。在一些实施例中，该方法还包括在检测到错误时执行错误恢复操作。

说明书

技术领域

本申请涉及数据处理方法和装置，并且更具体地涉及用于数据存储系 统中的错误检测和纠正的方法和装置。

背景技术

随着计算机系统的兴起以及工业、企业和个人对使用电子数据的依赖 性持续增长，产生了对于能够以快速、有效和经济的方式成功地存储和取 回以电子形式的大量数据的需求。为了存储电子数据(此后简称为数 据)，数据经常被分解为特定大小的块。例如，数据可以被分解为4千字 节的块，被称为数据的4k块。

数据存储和取回的一个重要方面是应该通过由读操作取回的数据与由 先前的写操作存储的数据相同来维护数据的完整性。另一重要方面是数据 可被存储和取回的速度。在一些已知的系统中，要被存储的数据跨多个数 据存储元件(例如，硬盘和/或固态驱动)进行分布。

在一些已知的系统中，由于检查错误所花费的时间，当先前存储的数 据被从存储设备中读取时，这些已知的系统通常使用轻权重错误纠正技 术，例如，单比特位错误检测技术。单比特位错误检测技术(例如，简单 的奇偶校验)易于实现，例如，位被取异或，并且结果与和数据一起存储 的奇偶检验位进行对比。奇偶校验可以对相对较小的数据单元(例如，一 组几比特位或数百比特位)执行。虽然奇偶校验易于实现，但是其具有以 下缺陷：如果偶数位具有错误(例如，存在两比特位错误)，则该错误可 能不能被奇偶校验检测到。因此，当两比特位或多比特位错误掩盖读取数 据错误，使得其不能被奇偶校验操作检测到时，多比特位错误可能导致未 检测到的读取数据错误。

如果没有奇偶校验失败，多数驱动系统通常在不对从盘中读取的数据 执行额外检验的情况下返回该数据，即使系统可以在例如与该数据被读取 的数据存储设备不同的数据存储设备上存储额外的错误纠正和/或检测信息 (例如，一组奇偶校验位)以用于检测读错误的情形中。此外，在驱动中 实现的轻权重错误检查(例如，CRC奇偶校验和BCH校验)不检测由噪 声信道(例如，经历电磁干扰(EMI)的信道)引入的错误。这是因为驱 动错误检测是在数据未被读取的驱动处做出的。

应该认识到，存在对于能够通过增加所检测到的读错误的数量来增加 数据存储完整性，并且在读操作上能够提供比当前轻权重错误检测技术 (例如，简单的单比特位奇偶检验)所提供的比特位错误检测更高级的比 特位错误检测。虽然需要改进的错误检测技术，但是也希望用于读操作的 新的或改进的错误检测技术针对每个读操作不引入过量的附加处理和/或延 时。

发明内容

本文描述了用于向存储器有效地存储数据(例如，数据块)和从存储 器有效地取回数据(例如，数据块)的数据处理方法和装置，其中所取回 的数据以比使用先前已知的轻权重技术(例如，单比特位奇偶校验、轻权 重循环冗余校验或轻权重BCH错误检测码)的可能方式更鲁棒的方式检 查错误。

在各个实施例中，该方法和装置利用散列值，该散列值例如根据 mumur散列函数生成并在将数据块写入存储设备的过程中被存储。散列值 提供了更鲁棒的错误检测能力，其是比通常使用的单比特位奇偶校验、循 环冗余校验或BCH错误检测码更重权重的技术。这至少部分是因为至少 在一些实施例中，使用了相对较大的散列值(例如，24-31比特位)，其 相当大，因此比通常所使用的很多CRC或BCH码更可靠。对应于数据块 的散列值(其作为写过程的一部分被存储)在一些实施例中被用于执行快 速且相对容易的方式，以对从存储设备读取的经恢复的数据块实现错误检 查。在一些实施例中，散列值的生成和存储是写操作的数据去重复的一部 分。

在写过程中，被存储的数据块经受散列操作，并且针对被存储的数据 块生成散列值。散列值可以并且在一些实施例中的确被用作数据去重复过 程的一部分。数据块的散列值被存储并且可用于执行读操作时。

在至少一些实施例中，数据块的部分(例如，数据部分)被存储在存 储阵列的不同驱动上。各个奇偶校验位可以并且通常针对被存储在单独的 驱动上的数据部分而被存储在每个驱动上。存储在包括数据块的一部分的 驱动上的奇偶校验位被用于在数据被从盘中读取时对数据执行简单奇偶校 验。假设简单奇偶校验未产生错误，则从驱动读取的数据被返回。从多个 驱动读取的数据部分由驱动控制器(例如，RAID控制器)响应于请求读 取所存储的数据块的请求而提供，并且假设没有奇偶校验错误，则响应于 请求读取数据块的请求而被返回。

根据一个特征，根据所返回的数据块，使用与在写操作期间针对数据 块生成原散列值相同的散列函数生成散列值。所生成的散列值与先前(例 如，作为在写操作期间执行的数据去重复过程的一部分)生成的所存储的 散列值进行对比。

然后，根据从存储驱动读取的所恢复的数据块生成的散列值与先前存 储的散列值进行对比。如果存在失配，则指示错误情况，并且执行故障 (例如，错误)通知和/或纠正操作。注意，因为散列值是使用散列函数在 整个块上生成的，该散列函数与可被用于实现简单奇偶校验的简单异或操 作不同，因此能够检测在读操作期间未被由各个驱动所执行的简单奇偶校 验检测到的错误。

假设响应于读操作所返回的数据块的散列值的生成能够相对较快实 现，并且该生成往往利用已经被包括来支持作为针对写操作执行的数据去 重复操作的一部分的散列值的生成的硬件和/或软件，并且假设将所生成的 散列值与先前生成并存储的散列值进行对比不是计算密集或复杂的，本文 所描述的错误检测技术能够以很小或没有额外开销并且不向与恢复先前存 储的数据块相关联的读操作引入显著延时的情况下被实现。

在各个实施例中，当通过根据从读操作返回的数据块的散列而生成的 散列值与作为写操作的一部分而生成的数据块的散列值的对比指示失配检 测到错误，从而检测到返回数据块中有错误时，启动错误通知过程，并且 在一些实施例中，采取步骤以识别对返回错误数据负责的存储阵列中的驱 动。

错误通知过程可以并且在一些实施例中的确包括通知驱动控制器返回 数据块中的错误。然后驱动控制器(例如，RAID控制器)可以采取步骤 以检查被用于存储包括错误的数据块部分的驱动。这可以包括对由控制器 管理的一个或多个驱动使用奇偶校验位，以识别被存储于用于存储数据块 部分的各个驱动上的数据部分中的错误。

在一些实施例中，其中，被存储于各个驱动上的数据块部分的奇偶校 验信息被生成并存储为一组奇偶校验位，例如，发生在RAID3、4、5或6 的情况下，检测错误的系统能够并且有时的确协助驱动控制器(例如， RAID控制器)识别错误驱动。

在一个这样的实施例中：其中，N-1个驱动存储读回数据块的错误部 分，并且第N个驱动存储针对存储于所述N-1个驱动上的数据的一组奇偶 校验位，例如跨越存储于多个驱动上的数据的条带而生成的奇偶校验位， 检测到读错误的系统请求RAID控制器对跨驱动存储的数据块执行多个不 同的读取，但是从N-1个驱动的不同组读取数据，例如，通过指示用于存 储数据块部分和/或跨数据块部分的奇偶校验位的N个驱动中特定的一个 驱动被排除在读操作之外。因此，在每次读取数据块期间，在检测到错误 后，返回的数据将根据N-1个驱动的不同组合来生成。

散列根据响应于请求从N-1个驱动读取块的请求所提供的每个返回块 而生成。针对返回块所生成的散列值与作为写操作的一部分而生成的所存 储的散列值进行对比。当根据返回的数据块而生成的散列值匹配所存储的 散列值时，被排除在读操作之外的驱动被确定为包括错误，该错误导致检 测到的错误。以这种方式，错误的驱动能够被识别。

在识别出错误的驱动之后，驱动控制器和/或被确定为错误的驱动被通 知所检测到的错误，并且驱动控制器和/或驱动实现步骤以重建错误的数据 块、识别导致错误的错误存储位置(例如，驱动扇区)、和/或排除驱动存 储元件中被用于存储包括所检测到的错误的数据块部分的所有或一些驱动 存储元件。

通过利用散列计算功能以及作为数据写操作的一部分的散列值的存 储，对应于读操作的错误检测被增强，其中向读操作引入很少或没有额外 的硬件开销以及延时(如果有的话)最小。在一些实施例中使用的散列函 数(不像奇偶校验和CRC校验)是单向不可逆的。在一些实施例中，使 用由单向不可逆散列函数生成的相对较长的散列值提供了重得多的权重错 误检测功能，当与被用于一些系统中的相对较轻权重的现有技术奇偶位校 验相比时，其提供改进的并且更鲁棒的错误检测和恢复机制。

在一些实施例中，本发明的方法和装置被实现在存储节点上，该存储 节点包括处理器，在没有专用散列功能硬件的帮助下，该处理器使用软件 来执行散列功能。存储节点可以包括用于存储数据块以及用于访问所存储 的数据块的表和/或链表的硅存储设备。

虽然已经描述了各个示例性实施例和特征，但是在以下具体实施方式 中描述了很多额外的特征和实施例。

附图说明

图1根据本发明的一个实施例，示出了示例性系统。

图2根据本发明的一个实施例，示出了用于被耦合到网络的示例性固 态存储阵列的示例性硅存储节点。

图3根据本发明的一个实施例，示出了示例性存储设备。

图4根据本发明的一个实施例，示出了示例性存储设备的示例性存储 元件。

图5示出了可以并且在一些实施例中的确被用于实现本发明的示例性 表。

图6A是图6的第一部分，其根据本发明的一个实施例，示出了用于 处理所存储的数据的示例性方法的第一部分。

图6B是图6的第二部分，其根据本发明的一个实施例，示出了用于 处理所存储的数据的示例性方法的第二部分。

图6C是图6的第三部分，其根据本发明的一个实施例，示出了用于 处理所存储的数据的示例性方法的第三部分。

图7根据本发明的一个实施例，示出了用于将数据存储于多个存储器 存储元件上的示例性子例程。

图8A是图8的第一部分，其根据本发明的一个实施例，示出了用于 执行错误恢复操作的示例性子例程的第一部分。

图8B是图8的第二部分，其根据本发明的一个实施例，示出了用于 执行错误恢复操作的示例性子例程的第二部分。

图9示出了可以并且在一些实施例中的确被用于实现本发明的示例性 逻辑块地址对散列值表。

图10示出了可以并且在一些实施例中的确被用于实现本发明的示例 性存储块地址表。

图11根据本发明的一个实施例，示出了示例性存储设备的示例性存 储元件。

图12示出了可被用于图1的计算机系统的模块的示例性配件。

具体实施方式

图1根据本发明的一个实施例，示出了用于处理数据(例如，从诸如 存储设备(例如，RAID5存储设备)的存储器写和读数据)的示例性系 统，例如，计算机系统100。在各个实施例中，被处理的数据可以是数据 块。在本发明的一些实施例中，示例性系统100被实现为装置。

示例性系统100包括显示设备102，用于发送和接收项目(例如，请 求、命令、指令、数据和信息)的收发器104，输入设备106(例如，可 被用于输入信息、数据和/或指令的键盘)，存储器108，存储设备122， 处理器110，网络接口114，以及I/O接口112。在一些实施例中，显示设 备102可以被用于显示关于系统配置和/或正在由系统执行的数据处理的状 态的信息。显示设备102、收发器104和输入设备106由I/O接口112耦合 到总线116。总线116还被耦合到存储器108、存储设备122、处理器110 和网络接口114。网络接口114将系统100的内部组件耦合到外部网络， 例如，互联网，从而允许系统100通过网络接收用于处理的数据，或向网 络输出经处理的数据。

处理器110在存储于存储器108中的程序和/或软件模块的指导下控制 系统100的操作。存储器108包括模块的存储器配件118，其中一个或多 个模块包括用于实现本发明的数据处理方法的一个或多个软件程序，例 如，机器可执行指令。118的模块中的各个步骤和/或代码行在被处理器 110执行时，控制处理器110执行本发明的方法的步骤。当由处理器110 执行时，数据处理模块118使得至少一些数据由处理器110根据本发明的 方法进行处理。所产生的数据和信息(例如，要从存储设备读取的数据块 的所接收的逻辑块地址、从存储设备读取的逻辑块、所读取的数据块的经 计算的散列值、以及到散列表的逻辑块地址)被存储于数据/信息存储器 120中以供未来使用或附加处理和/或输出，例如，发送给显示设备102以 进行显示。存储设备122是包括存储器的设备，该存储器用于存储诸如被 接收以用于存储和以后取回的数据块的数据。存储设备122可以是奇偶 RAID(独立盘冗余阵列)存储系统，例如，包含3个或更多存储器存储元 件的RAID3、4或5系统，或包含4个或更多存储器存储元件的RAID6 系统。示例性存储器存储元件包括光盘驱动、磁盘驱动、固态硅存储器驱 动(例如，NAND闪存驱动)等。存储器108包括不同类型的存储器，例 如，在一些实施例中，在数据处理活动期间模块的配件118和数据/信息 120可以被存储于其中的随机存取存储器(RAM)、和模块的配件118存 储器被存储于其中以例如在停电或断电之后可用的只读存储器(ROM)或 其他非易失性存储器。

在一些但非全部实施例中，网络接口114支持4/8GB/s光纤信道连 接、1/10Gb以太网连接和/或40Gb无线带宽信道。

在本发明的一些实施例中，示例性系统100是硅存储节点(SSN) (例如，图2的SSN-1202)，在本发明的一些实施例中，其可以是固态 存储阵列的一部分。

图2示出了示例性固态存储阵列200，包括示例性硅存储路由器SSR- A202和SSR-B204以及硅存储节点SSN-1206、SSN-2208、……、SSN- X210。数据链路212、214、……、216、218、220、……、222耦合固态 存储阵列的各个元件，并且允许在包括在固态存储阵列200中的各个组件 之间发生请求、命令、指令、数据和信息的通信。数据链路224将SSR-A 202耦合到网络228，其可以并且在一些实施例中的确包括额外的存储设 备。与数据链路224类似的数据链路226将SSR-B204耦合到网络228。 SSR-A和SSR-B只意味着是示例性的，因为在一些系统中存在额外的硅存 储路由器和额外的数据链路用于将路由器连接到硅存储节点和网络228。 数据链路224和226允许在网络228中包括的设备和固态阵列的硅存储路 由器之间发生请求、命令、指令、数据和信息的通信。数据链路212、214 和216将硅存储路由器SSR-A202分别耦合到硅存储节点SSN-1206、 SSN-2208和SSN-X210。数据链路218、220和222将硅存储路由器SSR- B204分别耦合到硅存储节点SSN-1206、SSN-2208和SSN-X210。所示 出的硅存储路由器、硅存储节点的数量以及用于将它们耦合在一起的数据 链路的数量和安排只意味着是示例性的并且可以改变。

图3提供了来自图1的示例性存储设备122的额外细节。示例性存储 设备122例如是RAID5存储设备，包括输入/输出(I/O)接口308、存储 设备控制器302(例如，RAID控制模块)、存储器存储元件1312(例 如，盘1)、存储器存储元件2314(例如，盘2)、存储器存储元件3 316(例如，盘3)、存储器存储元件4318(例如，盘4)、……、存储 器存储元件N320(例如，盘N)。在示例性实施例中，存储设备控制模 块302(其还将被称为RAID控制模块302)包括处理器304和存储器 306。存储器306包括指令，这些指令在处理器304上被执行以操作存储 设备122并且存储、取回和维护RAID存储器存储元件312、314、316、 318、……、320上的数据。通信链路310(其可以是总线)将I/O接口 308耦合到RAID控制模块302，并耦合到存储器存储元件312、314、 316、318、……、320。存储设备122能够并行处理、读取、写入和传递 数据，例如，从存储器存储元件1、2、3、4、……、N中读取或写入这些 存储器存储元件的数据。

在至少一些实施例中，RAID控制模块302不包含处理器，而是软件 模块，该软件模块包括存储在控制器存储器306中的软件指令。在至少一 些这样的实施例中，存储设备包括处理器，该处理器被连接到总线310， 在该处理器上执行控制模块的软件指令。在RAID控制模块302是软件模 块的一些实施例中，模块的指令在系统100的处理器110上被执行。

在很多但非全部实现方式中，存储器存储元件1、2、3、4、……、N 是非易失性存储器存储元件。用于每个存储器存储元件1、2、3、 4、……、N的存储器类型可以不同，但是在多数实施例中被选择为相同 的，使得数据块能够被存储和从存储器存储元件中取回的速度基本相同。 在一些实施例中，固态或硅盘阵列(例如，NAND闪存硅存储元件)根据 本发明的一个实施例而被使用。在一些实施例中使用光盘。在一些实施例 中使用鼓代替盘。

图4根据本发明的一个实施例，示出了示例性存储设备的示例性存储 元件。图4示出了当N＝5时，即当存在五个存储器存储元件用于存储示例 性数据块和相应的纠错代码位(例如，奇偶校验位)时，五个数据块A、 B、C、D和E可被分段并存储在存储设备122的存储器存储元件中的一种 示例性方式。在图4所示的示例性实施例中，实现了RAID5存储配置， 其中，数据块A被分成四个相等的部分A1、A2、A3和A4，其中对应于 A1部分的数据比特位存储在存储器存储元件1312中，对应于A2部分的 数据比特位存储在存储器存储元件2314中，对应于A3部分的数据比特位 存储在存储器存储元件3316中，对应于A4部分的数据比特位存储在存储 器存储元件4318中，并且纠错位(例如，根据对应于A1、A2、A3和A4 部分的位生成的奇偶校验位)被存储在存储器存储元件5中。数据块A及 其相应的奇偶校验位所处的存储器存储元件的部分被称为条带(stripe)。 数据块B、C、D和E及其相应的部分和纠错位被类似地以如图4所示的 分布式方式存储在存储器存储元件1、2、3、4和5中。通过将与数据A 相关联的数据和奇偶校验位跨越多个存储器存储元件进行分布，即使在存 储器存储元件中的一个故障或被损坏的情况下，系统依然能够恢复所存储 的数据A。然而，对于在比特位被损坏的情况下要进行恢复的数据A，系 统需要识别哪些存储器存储元件包含被损坏的比特位。一些存储系统针对 存储在存储器存储元件上的数据的每个部分生成校验和，例如，可以针对 A1、A2、A3和A4部分生成校验和。然后每个校验和被存储在存储器存 储元件的数据完整性部分或段中，在该存储器存储元件上存储着校验和根 据其而生成的相应的数据比特位。例如，对应于形成A1部分的数据比特 位的校验和被存储在存储器存储元件1上。对应于形成A2部分的数据比 特位的校验和被存储在存储器存储元件2上。对应于形成A3部分的数据 比特位的校验和被存储在存储器存储元件3上。对应于形成A4部分的数 据比特位的校验和被存储在存储器存储元件4上。当发生读取数据A的操 作并且A1部分的数据比特位被从存储元件1读出时，生成校验和并且将 校验和与存储在存储器存储元件1的数据完整性部分中的A1部分校验和 的值进行对比。类似地，A2部分的数据比特位被从存储元件2读出，生成 校验和并且将校验和与存储在存储器存储元件2的数据完整性部分中的 A2部分校验和的值进行对比；A3部分的数据比特位被从存储元件3读 出，生成校验和并且将校验和与存储在存储器存储元件3的数据完整性部 分中的A3部分校验和的值进行对比；并且A4部分的数据比特位被从存储 元件4读出，生成校验和并且将校验和与存储在存储器存储元件4的数据 完整性部分中的A4部分校验和的值进行对比。虽然这些校验和检查能够 识别一些错误，但是它们是轻权重错误检测技术，并且不能识别很多错 误，例如，A1、A2、A3和A4部分中的两个比特位被反转的情况的错 误。例如，在这种情形中，针对从存储器存储元件1取回的数据生成的校 验和将匹配所存储的A1部分的校验和，即使其包含错误。校验和对比由 存储器存储元件做出，并且不是在RAID级别执行的。在RAID级别，虽 然可能检测到错误，但是如果跨越条带执行奇偶校验，则RAID控制模块 (例如，实现RAID5的RAID控制器)不能确定哪个数据存储元件包含 错误数据，甚至不能确定是否是数据未被损坏但是相应的奇偶校验位被损 坏。在本发明中，通过对读取的数据执行附加的散列值校验，具有损坏数 据比特位的存储器存储元件可被识别。

图5示出了示例性表格，其可以是并且在一些实施例中的确被用于实 现本发明。图700包括逻辑块地址(LBA)对散列值(散列)表702(在 本文中还被称为LBA对散列表702)，散列值对物理块地址(PBA)表 704(在本文中还被称为散列对PBA表)，以及物理块地址(PBA)表 706(在本文中还被称为PBA表)。

LBA对散列表702包括三列信息。LBA对散列表702的第一行714是 表头，其不是该表的一部分，而只是被提供用于帮助理解该表。LBA对散 列表702的第一列包括逻辑块地址，LBA对散列表702的第二列包括散列 值，并且LBA对散列表702的第三列包括标签值。该表包括多个行，其 中该表的每一行关联被包含在该行中的数据。例如，在可以包含内容行 716的该表的第一行中，行716的第一列708中的逻辑块地址与行716的 第二列710中的散列值以及行716的第三列712中的标签值相关联。在一 些实施例中，包括逻辑块地址信息的列708只是到该表的索引，而不是该 表中的数据列。

散列值对PBA表704包括两列信息。散列值对PBA表704的第一行 744是表头，其不是该表的一部分，而只是被提供用于帮助理解该表。散 列值对PBA表704的第一列742包括散列值，并且散列值对PBA表704 的第二列743包括物理块地址。该表包括多个行，其中该表的每一行关联 被包含在该行中的数据。例如，在可以包含内容行745的该表的第一行 中，行745的第一列742中的散列值与行745的第二列743中的物理块地 址相关联。在一些实施例中，包括散列值的列742只是到表704的索引， 而不是该表中的数据列。

物理块地址(PBA)表706包括五列信息。PBA表706的第一行765 是表头，其不是该表的一部分，而只是被提供用于帮助理解该表。PBA表 706的第一列760包括物理块地址，PBA表706的第二列761包括标签 值，PBA表706的第三列762包括参考值(REF)，PBA表706的第四列 763包括大小值，并且PBA表706的第五列764包括下一个物理块地址。 该表包括多个行，其中该表的每一行关联被包含在该行中的数据。例如， 在可以包含内容行766的该表的第一行中，行766的第一列760中的物理 块地址与行766的第二列761中的标签值、行766的第三列762中的参考 值、行766的第四列763的大小值以及行766的第五列764的下一个物理 块地址相关联。在一些实施例中，包括物理块地址信息的列760只是到该 表的索引，而不是该表中的数据列。

包括图6A、6B和6C的图6根据本发明的示例性实施例，示出了一 种处理读和/或写请求或命令的示例性方法。图6的方法600是用于解释本 发明的各个特征的示例。

鉴于图1的系统100和示例性存储设备122，现在将对图6的方法600 的处理步骤进行解释，在该示例中，示例性存储设备122被配置为RAID5 存储设备，其中，N是存储器存储元件的数量。

图6的方法600开始于开始步骤602，其中该方法的步骤在处理器 110上被执行，处理从开始步骤602进行到步骤604。

在步骤604，初始化系统，包括生成并初始化表和链表，这些表和链 表将被用于跟踪将被存储在存储设备122中的数据块的存储位置。例如， 在一些实施例中，步骤604包括建立物理块地址链表(PBA链表)、逻辑 块地址对散列值表(LBA对散列值表)、以及散列值对物理块地址表(散 列对PBA表)。在本发明的至少一些实施例中，物理块地址表(PBA 表)还被作为初始化过程的一部分进行创建。处理从步骤604进行到步骤 606。

在步骤606，网络接口114监控针对系统100的读或写请求。例如， 请求是读或写命令和其他类似的指令。在图6的方法600的示例中，读请 求包括先前被存储在存储设备122中的数据的逻辑块地址。在图6的示例 性方法600中的写请求包括要被存储在存储设备122中的数据块以及要与 该数据块相关联的逻辑块地址。处理进行到步骤608。在步骤608，网络 接口114检测针对系统100的读或写请求。然后处理进行到步骤610。

在步骤610，收发器104通过网络接口114和I/O接口112接收读或写 请求。在本发明的至少一些实施例中，I/O接口112包括收发器104。读或 写请求可以并且在一些实施例中的确被存储在存储器108的数据/信息120 部分，例如，使得其可用于方法600的另外的处理步骤中。

然后处理进行到确定步骤612。在确定步骤612，关于接收到的请求 是读请求还是写请求做出确定。然后处理进行到决策步骤614。

在决策步骤614，如果接收到的请求是读请求，则处理通过连接节点 A616进行到图6B的步骤620。如果接收到的请求不是读请求而是写请 求，则处理通过连接节点B618进行到图6C的步骤642。

在步骤620，接收到的读请求被解析。读数据请求(例如，读数据块 请求)包括要从存储设备122中读取的数据块的逻辑块地址(PBA)。被 包括在读数据请求中的逻辑块地址被识别。然后处理从步骤620并行进行 到步骤622和624。虽然在示例性实施例中，步骤622和624被独立且并 行处理，但是步骤622和624可以并且在本发明的一些实施例中的确是顺 序处理的。在步骤622和624被顺序处理的那些实施例中，可以首先执行 或是步骤622或是步骤624。

在步骤622中，例如通过从散列值存储表中恢复对应于正在被请求的 数据(即，要从存储设备122中读取的数据)的先前生成的散列值，来确 定对应于正在被请求从存储设备122读取的数据的先前生成的散列值。散 列值存储表中的散列值对应于写入存储设备122的数据块。例如，在一些 实施例中，使用逻辑块地址对散列值表，例如，图5的表702。与读请求 一起接收的逻辑块地址被用作到LBA对散列值表702的索引，以确定与 所请求的数据块将被从其读取的逻辑块地址相关联的先前生成的散列值。 先前生成的散列值是在数据块响应于写请求被写到存储设备122时被生成 的。在一些实施例中，先前生成的散列值被作为数据去重复过程(例如， 在于2013年1月18日递交的、题为MethodsandApparatusforData Processing的共同未决的美国专利申请序列号13/745,503所描述的数据去 重复过程，其全部内容被通过引用结合于此)的一部分而被生成。在步骤 622，对应于数据625的先前生成的散列值被输出。处理从步骤622进行 到步骤628。

在步骤624，与纠错位一起存储的数据被从存储设备中读取。在一些 实施例中(例如，使用RAID5兼容存储阵列的实施例)，纠错位包括存 储于N个存储元件中的存储数据和奇偶校验位的一个存储元件上的块奇偶 条带。在示例性实施例中，与读请求一起接收的逻辑块地址被用于确定所 请求的数据块的物理块地址。处理器110通过总线116、I/O接口308和通 信链路310将读请求以及所请求的数据被存储于存储设备122中的所确定 的物理块地址发送给RAID控制模块302。处理从步骤624进行到步骤 626。

在步骤626，处理器110对从存储设备122读取的数据执行散列操 作，以使用与当该数据被写入存储设备时生成散列值(在步骤622中被称 为先前生成的散列值)相同的散列函数来生成第一散列值。在本发明的一 些实施例中，使用mumur散列函数(例如，mumurhash2)来生成24位散 列值，以与从存储设备存储和取回数据结合使用。通过将mumur散列函数 应用到数据块计算出的值的前24位是所生成的散列值。mumur散列函数 非常快并且具有很好的抗冲突性特性。所生成的散列值的大小可以并且在 一些实施例中的确是用户可配置的，例如，通过从24-31位的范围中选择 的位数。因为通过散列函数的分布基本相同，因此所计算的前24-31位将 被用作所生成的散列值。所使用的位数越高，则冲突数越低，即，独特的 数据块具有相同的散列值。在这些实例中，当散列值的大小可配置时，散 列值的大小通常在初始化步骤604期间进行配置。一旦被设置，则当散列 值被用作本发明的存储、取回、错误检测、错误纠正和/或去重复过程的一 部分时，散列值大小针对数据块的所有后续处理保持有效。

在一些实施例中，所生成的第一散列值627被存储在存储器108的数 据/信息120部分中，使得其可用于后续使用，例如，用于方法600的另外 的处理步骤中。

处理进行到对比步骤628。在对比步骤628中，在步骤626中生成的 第一散列值627与在步骤622中所确定的对应于所述数据625的先前生成 的散列值进行对比。然后处理进行到决策步骤630。

在决策步骤630，如果在步骤626中所生成的所述第一散列值627匹 配在步骤622中所确定的所述先前生成的散列值625，则处理进行到确定 步骤632。否则，处理进行到步骤636。

在确定步骤632中，确定未检测到读错误。这是因为根据从存储设备 122取回的数据块生成的第一散列值627匹配当数据块被写到存储设备时 所先前生成的散列值625。因为未检测到错误，因此处理进行到返回步骤 634。在返回步骤634，从存储设备122读取的数据响应于读请求被例如通 过I/O接口112和网络接口114经由收发器104返回。然后针对该读请求 的处理结束，但是处理与其他请求相结合并且对于其他读和写请求的监控 继续。

在步骤636，确定发生了读错误，因为第一散列值627与在数据块被 存储时所生成的先前生成的散列值625不匹配，从而指示存在错误。然后 处理进行到步骤638。

在步骤638，使用对应于所述数据的被存储的纠错位来执行错误恢复 操作。图8的子例程800是示例性子例程，其可以并且在一些实施例中的 确被用于实现步骤638的错误恢复操作。错误恢复子例程800将在下文进 行详细描述。在本发明的一些实施例中，错误恢复操作通过以下方式来实 现：由处理器110向RAID5控制器模块302发送命令以指示包含所取回 的数据块的RAID5存储器元件1、2、3、4、……、N上的条带包含错误 并且需要使用对应于从存储设备读取的数据块的纠错位进行重建。当完成 错误恢复操作时，处理进行到返回步骤640。

在返回步骤640，对应于在读请求中所请求的数据的、从存储设备 122恢复的数据例如通过I/O接口112和网络接口114经由收发器104被返 回给请求者。然后针对该读请求的处理结束，但是处理与其他请求相结合 并且对于其他读和写请求的监控继续。在一些实施例中，如果错误恢复操 作失败，并且所请求的数据不能被恢复，则读错误失败消息例如通过I/O 接口112和网络接口114经由收发器104被返回给请求者。

当接收到的请求是写请求时，处理从决策步骤614通过连接节点B 618进行到图6C所示的步骤642。在步骤642，写请求被解析，例如，根 据对写请求的分析，识别要被存储的数据(例如，数据的逻辑块)，并且 确定对应于要被存储的数据的逻辑块地址。然后处理进行到散列生成步骤 644。

在步骤644，从所接收的要被存储的数据块和散列函数生成散列值。 然后处理进行到步骤646。在步骤646，在步骤644中生成的散列值随后 被存储在与相应的逻辑块地址相关联的存储器中的散列表中，该相应的逻 辑块地址也是与写请求一起接收的。例如，所生成的散列值可以并且在一 些实施例中的确被存储在LBA对散列值表702中接收到的逻辑块地址 处。LBA对散列值表702可以并且在一些实施例中的确被存储在存储器 108的数据/信息120中。然后处理进行到步骤648。

在步骤648，在步骤644中生成的散列值与对应于先前存储的数据块 的散列值进行对比。然后处理进行到步骤650。在步骤650，对于具有匹 配的散列的每个先前存储的数据块，确定与写请求一起接收的数据块是否 是重复的。在一些实施例中，这是通过从存储设备取回先前存储的数据块 并将其与接收到的数据块进行对比以查看这两个块是否相同来实现的。然 后处理进行到步骤652。

在决策步骤652中，如果接收到的数据块是重复的，则处理进行到步 骤658。否则，处理进行到步骤654。

在步骤654，要被存储的接收数据被存储到存储设备122。在示例性 实施例中，数据被分成N-1个相等的部分，并且确定纠错位(例如，奇偶 校验位)。在数据不是相等地分成N-1个相等的部分的一些实施例中，填 充位(例如，零位)被添加到数据中，使得该数据能够被分成N-1个相等 的部分。然后数据的部分和奇偶校验位被分布到存储元件，使得存储设备 122的每个存储元件或是包括数据的一部分或是纠错位(例如，奇偶校验 位)。在一些实施例中，存储设备122是奇偶校验RAID存储设备，例 如，奇偶校验RAID5兼容存储设备，其中实现了具有分布式奇偶校验的 块级别的分条。在一些实施例中，使用RAID3兼容存储设备，其中使用 了具有专用奇偶校验的字节级别的分条。在一些实施例中，存储设备122 是具有块级别分条的RAID4兼容存储设备，并且使用专用奇偶校验存储 元件。在一些实施例中，存储设备122是具有双分布式奇偶校验的块级别 的分条的RAID6兼容存储设备。在一些实施例中，纠错位是奇偶校验 位。在一些这样的实施例中，数据被分成N-2个相等的部分，其中奇偶纠 错位被存储在总共N个存储元件中不被用于存储数据的部分的两个存储元 件上。在一些实施例中，例如，RAID-6实施例读取所罗门纠错编码还可 以在存储过程中实现。图7的子例程700示出了示例性子例程，其可以并 且在一些实施例中的确被用于实现存储步骤654。子例程700将在下文进 行详细解释。然后处理进行到步骤656。

在步骤656，数据存储跟踪表(例如，图5的表702、704和706)被 更新，以适当地跟踪已被存储的接收数据及其被存储的物理块地址。于 2013年1月18日递交的题为用于数据处理的方法和装置(Methodsand ApparatusforDataProcessing)的共同未决的美国专利申请序列号 13/745,503提供了更新数据存储跟踪表702、704和706的示例性方法的细 节。然后处理进行到返回步骤660。

在步骤658，通过递增与物理块地址(在该物理块地址处，对于先前 存储的数据块，接收到的数据块是重复的)相关联的计数值，例如，PBA 表中与匹配接收到的数据块的数据块的PBA地址相关联的计数值)对接收 到的数据块进行去重复。此外，数据存储和跟踪表(例如，图5所示的表 702、704和706)被更新以跟踪重复的数据块。处理进行到返回步骤 660。

在返回步骤660，确认数据被存储消息被返回，然后结合例程600的 处理针对该接收到的写请求结束，但是针对其他接收到的请求的处理继续 并且监控其他请求。

图7的子例程7000示出了示例性子例程，其可以并且在一些实施例 中的确被用于实现存储步骤654。子例程7000的步骤在存储设备122的存 储控制模块302的处理器304上实现。子例程开始于开始步骤7002，其中 处理器304执行子例程的步骤。然后处理进行到步骤7004。在步骤 7004，与写请求一起接收的数据被分成包含相等比特位数的N-1个部分。 N指代数据存储设备122中的存储器存储元件的数量。在一些实施例中， 如果有必要，则执行用被设置为零的附加位填充数据，使得数据能够被分 成包含相等比特位数的N-1个部分。然后处理进行到步骤7006。

在步骤7006，根据在步骤7004中生成的所述接收数据的所述N-1个 部分，生成奇偶纠错段(例如，奇偶字或块)。然后处理进行到步骤 7008。在步骤7008，所述接收数据的N-1个部分和奇偶段以分布式方式跨 N个存储器存储元件1、2、3、4、……、N被存储。例如，如结合图4例 如针对数据A所示和所解释的。然后处理进行到返回步骤7010，其中结 合子例程7000的处理结束。

图8示出了示例性子例程800，其可以并且在本发明的一些实施例中 的确被用于实现图6的方法600的步骤638，该步骤使用对应于所述数据 的所存储的纠错位来执行错误恢复操作。图8包括第一部分(图8A)和 第二部分(图8B)。如图8A所示，子例程800开始于开始步骤802，其 中子例程800在处理器110上被执行，执行从开始步骤802进行到步骤 804。在步骤804，变量“当前RAID数据存储元件”被设置等于0。这么 做是为了初始化变量“当前RAID数据存储元件”。不存在RAID存储元 件0。第一RAID存储元件是RAID存储元件1312。然后处理进行到步骤 806。

在步骤806，“当前RAID数据存储元件”以1递增，例如，当前 RAID数据存储元件＝当前RAID数据存储元件+1。然后处理进行到步骤 808。

在步骤808，信号被传输给基于奇偶校验的RAID存储控制器(例 如，RAID存储控制器模块302)，以在不使用“当前RAID数据存储元 件”的情况下，从所述存储设备(例如，122)恢复所请求的数据，例 如，当“当前RAID数据存储元件”为1时，所请求的数据块将从存储所 请求的数据及其纠错信息的RAID存储元件2、3、4、……、N恢复。 RAID控制器在接收到信号时，将使用对应于所存储的数据的纠错位来恢 复所请求的数据。然后，RAID控制器将通过I/O接口308将所恢复的数据 块发送给处理器110。然后处理将进行到步骤810。

在步骤810，处理器110从所述存储设备122接收所恢复的数据。所 恢复的数据可以并且在本发明的一些实施例中的确被存储在存储器108的 数据/信息120中，使得其可用于后续使用，例如，用于子例程800的后续 处理步骤。然后处理进行到步骤812。

在步骤812，根据所恢复的数据块生成第二散列值。然后处理进行到 对比步骤814。在对比步骤814，第二散列值与对应于所述数据625的先 前存储的散列值进行对比。然后处理进行到决策步骤816。在决策步骤 816，如果第二散列值匹配先前生成的散列值625，则处理进行到步骤 828。否则，处理进行到步骤818。

在步骤818，确定存在错误，因为根据所恢复的数据生成的第二散列 值不匹配先前生成的散列值。处理从确定步骤818经由连接节点D820进 行到图8B所示的决策步骤822。

在决策步骤822，如果确定存在可用于存储所述数据的一部分的额外 的RAID存储元件，则处理经由连接节点F824进行到图8A的步骤806。 在步骤806，“当前RAID数据存储元件”变量例如通过将该变量设置为 等于“当前RAID数据存储元件”+1的值来递增。在这种情况下，“当前 RAID数据存储元件”将被设置为等于2。然后，处理如先前针对从步骤 806到808进行的处理所讨论的那样继续进行，其中第二RAID数据存储 元件314被RAID控制器排除在数据恢复过程之外，如先前结合第一 RAID数据存储元件所讨论的那样。以这种方式，每个RAID存储元件将 被测试，直到数据被适当地恢复。

在决策步骤822，如果确定不存在可用于存储所述数据的一部分的额 外的RAID存储元件(例如，所述数据的条带)，则处理进行到返回步骤 826。在返回步骤826，返回不可恢复读错误消息，因为错误恢复子例程 800在恢复数据中失败，该数据具有散列值与对应于该数据并且在该数据 被存储时生成的先前存储的散列值发生匹配。然后处理针对子例程800结 束，但针对方法600继续。

如前所述，在决策步骤816中，如果第二散列值匹配先前生成的散列 值，则处理进行到确定步骤828。在确定步骤828，确定针对所恢复的数 据未发生错误。虽然可能存在以下散列值冲突：所恢复的数据具有与先前 存储的数据相同的散列值但却与先前存储的数据不同，但是由于散列值的 计算权重，这种情况的可能性极低。此外，具有匹配的散列值的恢复数据 的数据完整性远远大于不进行散列值检查的读取的数据完整性。因此，确 定没有发生错误。处理从步骤828经由连接节点E830并行进行到图8B所 示的步骤832和836。

在步骤832，“当前RAID数据存储元件”被标识为所述读错误的 源。然后处理进行到步骤834，其中RAID控制模块302被通知错误的 RAID存储元件。然后RAID控制模块能够对错误的存储元件执行各种检 查和测试，例如，状态检查、针对数据损坏的测试、错误检查、坏扇区检 查、针对校验和错误和/或奇偶不一致的检查。如果发现可纠正的错误，则 RAID控制模块可以并且在一些实施例中的确纠正所识别出的错误。在一 些实施例中，在第一方便的时间(例如，历史上较低容量读取时)或恰当 的时间(例如，在识别到错误的源之后的第一晚)，RAID控制模块可以 对RAID存储元件执行RAID级别的数据清洗。

在步骤836，错误RAID存储元件被通知其在用于存储所述数据的一 个或多个扇区中具有错误。在一些实施例中，这是通过处理器110经由总 线116和I/O接口308向错误存储元件(例如，存储元件1312)发送消息 来实现的。在至少一些实施例中，当错误的RAID存储元接收到该RAID 存储元件中的一个或多个扇区错误的通知时，该RAID存储元件将测试对 应于数据条带的那些扇区，并且它如果那些扇区故障，则将那些扇区标记 为坏的。在至少一些实施例中，RAID存储元件将仅把用于存储数据条带 的所有扇区标记为坏的，直到能够对各个扇区做出检查。然后处理进行到 步骤838。

在步骤838，RAID控制模块302被通知重建条带，该条带的一部分被 存储在所标识的错误RAID元件的一个或多个错误扇区中。在多数实施例 但非所有实施例中，当接收到该通知时，RAID控制模块将使用与数据的 一部分坏掉的条带相关联的纠错位(例如，奇偶控制位)重建条带。

虽然针对步骤832、834和836和838示出并描述了两个并行的路径， 但是这两个单独的并行路径的步骤可以并且在一些实施例中确定是顺序执 行的。在并行路径的步骤被顺序执行的那些实施例中，首先通过哪条路径 的顺序是不重要的。

处理从步骤834和838进行到返回步骤840。在返回步骤840，具有 匹配先前存储的散列值的第二散列值的恢复数据被返回。然后针对子例程 800的处理结束，但是针对方法600的处理继续。

在本发明的一些实施例中，不执行去重复过程。例如，在方法600 中，当不使用去重复时，不执行步骤648、650、652和步骤658。而是处 理从步骤646进行到步骤654，在步骤646，所生成的散列值被存储在 LBA对散列值表中的与写请求一起接收的逻辑块地址处的，在步骤654， 接收到的数据被存储到存储设备，其中中间步骤被忽略。然后处理从步骤 654继续，如前所述。

图9示出了第二示例性LBA对散列值表900，其可以并且的确被用于 本发明的一些实施例中。LBA对散列表900包括三列信息。LBA对散列表 900的第一行914是表头，其不是该表的一部分，而只是被提供用于帮助 理解该表。LBA对散列值表900的第一列908包括逻辑块地址，LBA对散 列值表900的第二列910包括散列值，并且LBA对散列值表的第三列912 包括存储设备块地址，其是与存储设备上的数据块的存储相关联的地址。 该表包括多个行，其中该表的每一行关联被包含在该行中的数据。例如， 在可以包含内容行916的该表的第一行中，行916的第一列908中的逻辑 块地址与行916的第二列910中的散列值以及行916的第三列912中的存 储块地址相关联。在一些实施例中，包括逻辑块地址信息的列908只是到 该表的索引，而不是该表中的数据列。行916包含以下信息：行916列 908的条目中的逻辑块地址10，与逻辑块地址10相关联的行916列910的 条目中的散列值HA，以及行916列912的条目中的存储设备地址100。从 这些条目中可以理解，被写到逻辑块地址10的数据块具有散列值HA，并 且该数据块被存储在存储设备中的存储块地址100处，该存储块地址100 可以并且在一些实施例中的确是逻辑块地址。在一些实施例中，存储块地 址是物理块地址。表900可以并且在一些实施例中的确被存储在存储器 108的数据/信息120中。在一些实施例中，该散列值表可以并且的确包括 关于数据块是否重复的信息，例如，指示重复的数据块的数量的计数条 目。

图10示出了示例性存储块地址表，其可以并且在一些实施例中的确 被用于实现本发明。在本发明的一些实施例中，该示例性存储块地址表与 图9的LBA对散列值表结合使用。SBA表1000的第一行1014是表头， 其不是该表的一部分，而只是被提供用于帮助理解该表。SBA表1000的 第一列1008包括与数据块相关联的存储块地址。在一些实施例中，存储 块地址是物理块地址。在一些实施例中，存储块地址是存储设备的逻辑块 地址。SBA表1000的第二列1010包括计数值，其是存储在列1008的 SBA地址处的数据块在系统中被参考的次数。对于与SBA地址相关联的 每个LBA地址，计数以1增加。该表包括多个行，其中该表的每一行关 联被包含在该行中的数据。例如，在可以包含内容行1016的该表的第一 行中，行1016的第一列1008中的存储块地址与行1016的第二列1010中 的计数值相关联。在一些实施例中，包括逻辑块地址信息的列1008只是 到该表的索引，而不是该表中的数据列。行1016包含以下信息：行1016 列1008的条目中的存储块地址100，以及行1016列1010的条目中与存储 块地址100相关联的计数值1。

现在提供一个示例，该示例解释了当使用去重复时，可以并且在一些 实施例中的确是如何更新表900和1000的。当接收到具有与存储在SBA 100中的数据块相同的数据块A的写入LBA20的写请求时，数据块A的 散列值将被确定为HA。在LBA对散列值表中的LBA20处，散列值HA 将被输入作为散列列的第二列中。LBA对散列值表将被搜索，以获得匹配 的散列值条目。在这种情况下，与LBA10相关联的散列值将被确定为匹 配。然后将确定在与LBA10相关联的SBA值100处的数据块是否匹配接 收到的要被存储的数据块A，例如，通过进行按比特位对比。在这种情况 下，接收到的要被写到LBA20的数据块A是被写到SBA100的数据块A 的重复。然后SBA表1000被访问，并且在SBA100处，计数增加1。然 后LBA对散列值表中对应于LBA20的SBA地址被更新以包括SBA地址 100。

在一些实施例(例如，使用具有总共N个存储元件的RAID6实现方 式的那些实施例，其中，条带中的2个存储元件被用于奇偶校验(即，双 奇偶校验)，并且条带中的N-2个存储元件被用于数据)中，可以通过对 条带中的存储元件执行N-2次读取并且执行恢复操作来检测最多两个错误 的存储元件。虽然在一些实施例中使用RAID6，但是在其他实施例中使 用RAID5。

在本发明的一些实施例中，存储元件数据块大小是逻辑数据块大小的 多倍，散列值基于逻辑数据块大小来计算。在这些实施例中，被写到存储 元件的存储元件数据块是多个逻辑数据块的聚合。此外，整个RAID数据 条带的大小是存储元件数据块的数目乘以在RAID阵列中要分布数据的存 储元件的数目。

以上示例还可以针对图11进行解释，图11示出了RAID5实现方 式。在图11的示例中，存在总共5个存储器存储元件：存储器存储元件1 1102、存储器存储元件21104、存储器存储元件31106、存储器存储元件 41108、以及存储器存储元件51110。RAID条带A包括存储在存储器存 储元件11102上的A1部分、存储在存储器存储元件21104上的A2部 分、存储在存储器存储元件31106上的A3部分、存储在存储器存储元件 41108上的A4部分、以及存储在存储器存储元件51110上的A奇偶校 验。A1、A2、A3、A4部分和A奇偶校验全部具有相同的大小，即存储元 件大小。在该示例中为了解释的目的，存储元件大小为64千字节。因 此，A1部分1112包含64千字节的数据，A2部分1112包含64千字节的 数据，A3部分1112包含64千字节的数据，A4部分1112包含64千字节 的数据，并且A奇偶校验包含根据A1、A2、A3和A4部分生成的64千 字节的纠错信息，例如，奇偶校验位。因为存在4个存储元件使得数据A 通过其被分布在RAID5阵列1100的条带A中，因此RAID数据存储条带 大小是256千字节，即，64千字节乘以数据被分布于其上的4个存储元 件。每个数据部分A1、A2、A3和A4包含16个子元素，每个子元素等于 4千字节，其是单个逻辑数据块的大小。例如，A1部分1112被分成具有4 千字节的16个子元素。A1部分示出了示例性第一子元素1114。跨该条带 存储的256千字节是64个逻辑数据块的聚合，其中在A1部分、A2部 分、A3部分和A4部分中的每一个上存储16个逻辑数据块。为了解释的 目的，假设与逻辑块地址10相关联的具有4千字节大小的逻辑数据块G 已被存储在存储元件11102的A部分1112的子元素1114中。

在该示例中，当接收到与逻辑数据块G相关联的读取逻辑块地址请求 时，系统从散列值表(例如，LBA对散列表900)确定针对该逻辑块地址 的先前生成的散列值，并且获取存储数据块的存储块地址。读请求被发送 给RAID控制模块，RAID控制模块取回所请求的块，然后从存储块中取 回子元素1114。RAID控制模块将所取回的4千字节数据块提供给处理器 110。处理器110对所取回的数据块G执行散列生成操作，然后将根据所 取回的数据块生成的值与当块G被写入存储元件时针对块G所先前生成的 散列值进行对比。如果这两个散列值不匹配，则确定存在读错误。读错误 可能是总线116上的噪声的结果，或者是未被由存储元件在取回时执行的 轻权重奇偶校验检测到的被反转的两个比特位的结果。此时，处理器110 能够请求RAID控制模块提供从中取回逻辑数据块G的RAID阵列中的存 储元件的标识。在该示例中，RAID控制模块将标识存储元件1。然后处理 器110能够请求RAID控制模块从条带取回包含在A2部分、A3部分、A4 部分和A奇偶校验中的数据，并将该数据与条带中对应于存储元件1中的 逻辑块地址G的具有4千字节的位置的标识一起提供给RAID控制模块。

在该示例中，逻辑块地址G的位置是A1部分中的第一子元素，即， A1部分中的前4千字节。然后，处理器110能够使用来自A2部分、A3 部分、A4部分的包含在前4千字节中的数据(即，第一子元素)以及来自 A奇偶校验的相应的奇偶校验位，以试图恢复逻辑数据块G。在一些实施 例中，处理器110能够只请求并接收对应于A2、A3、A4和A奇偶校验 的、重建被包含在A1部分112的子元素1114中的逻辑数据块G所必需的 部分。在至少一些实施例中，不是处理器110重建数据块G，而是处理器 向RAID控制模块发送指示从存储元件21104、31106、41108和51110 提供重建的子元素1114的命令。重建的子元素1114对应于数据块G。

处理器在重建数据块G或从RAID控制模块接收重建的数据块G之 后，其根据重建的数据块生成散列值，并将其与当数据块G被存储在存储 器中时所先前生成的散列值进行对比。如果这两个散列值现在匹配，则处 理器能够向RAID控制模块发送消息以指示对应于第一子元素1114的(一 个或多个)扇区和/或(一个或多个)擦除块包含错误(例如，被损坏)以 及数据条带A应被重建。然后RAID控制模块能够标记相应的一个或多个 扇区和/或一个或多个擦除块并重建条带A。

在一些实施例中，例如，使用具有N个存储元件的RAID6配置的存 储阵列的那些实施例，其中，数据被跨越N-2个存储元件上的阵列的条带 分布，并且该条带的奇偶纠错位被存储在该条带的其余两个存储元件上， 并且其中逻辑块地址小于存储块地址，当在读操作的散列对比步骤期间检 测到散列错误时，RAID控制模块被请求作出N-1个读操作以确定条带中 的一个或多个存储元件数据是否包含错误。

根据本发明的一个实施例，一种处理所存储的数据的方法包括以下步 骤：从存储设备(例如，存储设备122)读取与纠错位一起存储的数据， 对从存储设备读取的数据执行散列操作以生成第一散列值，将所述第一散 列值与对应于所述数据的先前生成的散列值进行对比，以及当所述第一散 列值不匹配所述先前生成的散列值时，确定发生了读错误。该方法可以在 系统100上实现，其中系统100的处理器110执行该方法的步骤。在本发 明的一些实施例中，所述先前生成的散列值是响应于写请求而生成的，并 且该方法还包括从散列值的存储表中恢复所述散列值，所述散列值对应于 被写入所述存储设备的数据块。在本发明的多数实施例中，所述数据是逻 辑数据块，并且所述先前生成的散列值是根据所述逻辑数据块，使用与用 于生成所述第一散列值的散列函数相同的散列函数生成的。

本发明的一些实施例包括一种处理所存储的数据的方法，包括以下步 骤：从存储设备(例如，存储设备122)读取与纠错位一起存储的数据， 对从存储设备读取的数据执行散列操作以生成第一散列值，将所述第一散 列值与对应于所述数据的先前生成的散列值进行对比，以及当所述第一散 列值不匹配所述先前生成的散列值时，确定发生了读错误，并且当确定发 生了读错误时，使用所存储的对应于所述数据的纠错位来执行错误恢复操 作。在本发明的一些这样的实施例中：其中，存在N个存储元件，并且数 据通过N-1个元件被分布在条带中，并且针对数据存储条带的错误恢复奇 偶校验位被存储在1个存储元件上，执行所述错误恢复操作包括：向基于 奇偶校验的RAID存储控制器发送信号，以指示执行N-1个存储元件的读 取，从而恢复信息，其中N是所述存储设备的条带中的存储元件的数目， 并且其中在单独的条带中，所述N个存储元件中的至少M个存储奇偶校 验位，并且其余N-M个存储元件存储对应于该条带的数据，M和N是整 数值，M至少是1，N至少是3；根据存储在条带的N-M个存储元件中的 数据生成M个奇偶校验位根据所恢复的信息生成第二散列值，将所生成的 第二散列值与对应于所述数据的先前生成的散列值进行对比，以及当不存 在匹配时确定存在错误，而当存在匹配时确定未发生错误。

在本发明的一些实施例中，错误恢复操作包括：向基于奇偶校验的 RAID存储控制器发送信号，以指示执行N-1个存储元件的读取，从而恢 复信息，其中N是所述存储设备的条带中的存储元件的数目，并且其中在 单独的条带中，所述N个存储元件中的至少M个存储奇偶校验位，并且 其余N-M个存储元件存储对应于该条带的数据，M和N是整数值，M至 少是1，N至少是3；根据从所述N-1个存储元件的读取所获得的经恢复 的信息生成第二散列值，将所生成的第二散列值与对应于所述数据的先前 生成的散列值进行对比，以及当不存在匹配时确定存在错误，而当存在匹 配时确定未发生错误。

在本发明的一些实施例中，该方法还包括：基于哪个从错误恢复操作 返回的结果不包括错误来识别哪个RAID存储元件是错误的源。

在本发明的一些实施例中，该方法包括：通知错误的RAID存储元件 的RAID控制模块，使得RAID存储设备可以例如将错误存储元件下线， 并且在空闲的存储元件上重建被存储在错误元件上的数据。

在本发明的一些实施例中，RAID控制模块可以并且的确是软件控制 模块。

在本发明的一些实施例中，该方法包括：向所识别的错误RAID存储 元件通知该存储元件在用于存储所述数据的一个或多个扇区中具有错误， 并且还通知RAID控制模块重建条带，该条带的一部分被存储在错误的扇 区中。在这样的实施例中，RAID存储元件可以并且通常的确封闭被标识 为错误的一个或多个扇区。

在本发明的一些实施例中，该方法包括：例如，当存储元件是NAND 闪存时，向所识别的错误RAID存储元件通知该存储元件在用于存储所述 数据的一个或多个擦除块中具有错误，并且还通知RAID控制模块重建条 带，该条带的一部分被存储在一个或多个错误的擦除块中。

被生成为数据去重复操作的一部分。

本发明的一些实施例包括一种处理所存储的数据的方法，包括以下步 骤：从存储设备读取与纠错位一起存储的数据，在没有指示错误的情况 下，由RAID控制模块从RAID存储元件接收所述数据，对从存储设备读 取的数据执行散列操作以生成第一散列值，将所述第一散列值与对应于所 述数据的先前生成的散列值进行对比，以及当所述第一散列值不匹配所述 先前生成的散列值时，确定发生了读错误。在一些这样的实施例中，该方 法检测RAID控制器的错误检查(例如，CRC检查或校验和)未检测到的 错误(例如，如果连个比特位反转)。

虽然示出了本发明的方法、例程和子例程的示例性实施例的处理步骤 的逻辑序列，但是该序列只是示例性的，并且步骤的排序可以改变。

包含一个或多个以上所讨论的特征的很多实施例都是可以的。在一个 示例性实施例中，数据处理装置包括：数据取回模块，被配置为从存储设 备读取与纠错位一起存储的数据；散列生成模块，被配置为对从存储设备 读取的数据执行散列操作以生成第一散列值；对比模块，被配置为将所述 第一散列值与对应于所述数据的先前生成的散列值进行对比；以及读错误 确定模块，被配置为当所述第一散列值不匹配所述先前生成的散列值时， 确定发生了读错误。在一个这样的实施例中，先前生成的散列值是响应于 写请求而生成的，并且该装置还包括散列值恢复模块，被配置为从散列值 的存储表中恢复所述先前生成的散列值，所述散列值对应于被写入所述存 储设备的数据块。在至少一个实施例中，数据是逻辑数据块，并且先前生 成的散列值是根据所述逻辑数据块，使用与用于生成所述第一散列值的散 列函数相同的散列函数生成的。示例性装置可以并且在一些实施例中的确 包括错误恢复模块，被配置为当确定发生了读错误时，使用对应于所述存 储的所述数据的纠错位来执行错误恢复操作。在至少一些实施例中，错误 恢复模块包括：发送信号模块，被配置为向基于奇偶校验的RAID存储控 制器发送信号，以指示执行N-1个存储元件的读取，从而恢复信息，其中 N是所述存储设备的条带中的存储元件的数目，并且其中在单独的条带 中，所述N个存储元件中的至少M个存储奇偶校验位，并且其余N-M个 存储元件存储对应于该条带的数据，M和N是整数值，M至少是1，N至 少是3。在至少一些这样的实施例中，该装置包括：第二散列生成模块， 被配置为根据所恢复的信息生成第二散列值；散列值对比模块，被配置为 将所生成的第二散列值与对应于所述数据的先前生成的散列值进行对比； 以及错误确定模块，被配置为当不存在匹配时确定存在错误，而当存在匹 配时确定未发生错误。该装置可以并且在一些示例中的确包括：错误源识 别模块，被配置为基于哪个返回的结果不包括错误来识别哪个RAID存储 元件是错误的源；以及RAID控制器错误通知模块，被配置为通知所识别 的错误数据存储元件的RAID控制模块。此外，该装置包括：第一数据存 储元件错误通知模块，被配置为向所识别的错误数据存储元件通知该存储 元件在用于存储所述数据的一个或多个扇区中具有错误；以及第一RAID 控制器重建通知模块，被配置为通知RAID存储控制器重建条带，该条带 的一部分被存储在错误的扇区中。

在一些实施例中，该装置还包括：第二数据存储元件错误通知模块， 被配置为向所识别的错误数据存储元件通知该存储元件在用于存储所述数 据的一个或多个擦除块中具有错误；以及第二RAID控制器重建通知模 块，被配置为通知RAID控制器重建条带，该条带的一部分被存储在错误 的擦除块中。

在一些但不必是全部的实施例中，该装置还包括数据去重复模块，被 配置为执行数据去重复操作，所述数据去重复操作包括生成所述先前生成 的散列值。

在一些实施例中，在没有指示错误的情况下，数据由RAID存储控制 器从数据存储元件接收。

图12根据各个示例性实施例，示出了模块1200的示例性配件。模块 1200的配件例如是模块118的配件，其被包括在图1的计算机系统100的 存储器108中。

模块1200的配件包括数据取回模块1202，被配置为从存储设备读取 与纠错位一起存储的数据；散列生成模块1204，被配置为对从存储设备读 取的数据执行散列操作以生成第一散列值；对比模块1206，被配置为将所 述第一散列值与对应于所述数据的先前生成的散列值进行对比；以及读错 误确定模块1208，被配置为当所述第一散列值不匹配所述先前生成的散列 值时，确定发生了读错误。

在一些实施例中，先前生成的散列值是响应于写请求而生成的。模块 1200的配件还包括散列值恢复模块1210，被配置为从散列值的存储表中 恢复所述先前生成的散列值，所述散列值对应于被写入所述存储设备的数 据块。在至少一个实施例中，数据是逻辑数据块，并且先前生成的散列值 是根据所述逻辑数据块，使用与用于生成所述第一散列值的散列函数相同 的散列函数生成的。

模块1200的配件还包括错误恢复模块1212，被配置为当确定发生了 读错误时，使用对应于所述存储的所述数据的纠错位来执行错误恢复操 作。在至少一些实施例中，错误恢复模块1212包括：发送信号模块 1214，被配置为向基于奇偶校验的RAID存储控制器发送信号，以指示执 行N-1个存储元件的读取，从而恢复信息，其中N是所述存储设备的条带 中的存储元件的数目，并且其中在单独的条带中，所述N个存储元件中的 至少M个存储奇偶校验位，并且其余N-M个存储元件存储对应于该条带 的数据，M和N是整数值，M至少是1，N至少是3。在至少一些这样的 实施例中，错误恢复模块1212包括：第二散列生成模块1216，被配置为 根据所恢复的信息生成第二散列值；散列值对比模块1218，被配置为将所 生成的第二散列值与对应于所述数据的先前生成的散列值进行对比；以及 错误确定模块1220，被配置为当不存在匹配时确定存在错误，而当存在匹 配时确定未发生错误。

模块1200的配件还包括：错误源标识模块1222，被配置为基于哪个 返回的结果不包括错误来识别哪个RAID存储元件是错误的源；以及 RAID控制器错误通知模块1224，被配置为通知所识别的错误数据存储元 件的RAID控制模块。此外，模块1200的配件包括：第一数据存储元件错 误通知模块1226，被配置为向所识别的错误数据存储元件通知该存储元件 在用于存储所述数据的一个或多个扇区中具有错误；以及第一RAID控制 器重建通知模块1228，被配置为通知RAID存储控制器重建条带，该条带 的一部分被存储在错误的扇区中。模块1200的配件还包括：第二数据存 储元件错误通知模块1230，被配置为向所识别的错误数据存储元件通知该 存储元件在用于存储所述数据的一个或多个擦除块中具有错误；以及第二 RAID控制器重建通知模块1232，被配置为通知RAID控制器重建条带， 该条带的一部分被存储在错误的擦除块中。模块1200的配件还包括数据 去重复模块1234，被配置为执行数据去重复操作，所述数据去重复操作包 括生成所述先前生成的散列值。

各个实施例的技术可以使用软件、硬件(例如，电路)和/或软件和硬 件的组合来实现。各个实施例针对装置，例如，数据处理系统。各个实施 例还针对方法，例如，处理数据的方法。各个实施例还针对非暂态机器 (例如，计算机)可读介质，例如，ROM、RAM、固态存储设备、硅存 储盘、CD、硬盘等，其包括机器可读指令以用于控制机器实现方法的一个 或多个步骤。

本发明的各个特征使用模块来实现。例如，所公开的各个例程和/或子 例程中的每一个可以在一个或多个模块中实现。这些模块可以并且在一些 实施例中的确被实现为软件模块。在其他实施例中，模块在硬件中实现， 例如，每个模块被实现为用于执行对应于单独模块的功能的电路。在其他 实施例中，模块使用软件和硬件的组合来实现。各种实施例可以被设想， 包括不同模块被不同实现(例如，一些以硬件实现，一些以软件实现，并 且一些使用硬件和软件的组合实现)的一些实施例。还应注意，例程和/或 子例程或由这些例程执行的一些步骤可以在专用硬件中实现，而不是在通 用处理器上执行的软件中实现。这些实施例仍在本发明的范围内。很多上 述方法或方法步骤能够使用包括在机器可读介质(例如，存储器设备，例 如，RAM、软盘、固态存储设备、硅存储设备等)中的机器可执行指令 (例如，软件)来实现，以控制机器(例如，具有或不具有额外硬件的通 用计算机)实现上述方法的全部或部分。因此，除其他事项外，本发明针 对包括机器可执行指令的机器可读介质，该指令用于使机器(例如，吹利 器及相关联的硬件)执行上述(一个或多个)方法的一个或多个步骤。

鉴于以上描述，对上述各个实施例的方法和装置的很多附加改变对于 本领域技术人员而言将是明显的。这些改变将被认为在本发明的范围内。