[go: up one dir, main page]

CN102656566B - 固态存储系统中的数据管理 - Google Patents

固态存储系统中的数据管理 Download PDF

Info

Publication number
CN102656566B
CN102656566B CN201080056483.7A CN201080056483A CN102656566B CN 102656566 B CN102656566 B CN 102656566B CN 201080056483 A CN201080056483 A CN 201080056483A CN 102656566 B CN102656566 B CN 102656566B
Authority
CN
China
Prior art keywords
group
code
symbol
code word
data
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
CN201080056483.7A
Other languages
English (en)
Other versions
CN102656566A (zh
Inventor
R·D·西德哲扬
E·S·埃莱夫特里乌
R·哈斯
胡晓宇
I·伊利亚迪斯
T·米特尔霍尔泽
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Publication of CN102656566A publication Critical patent/CN102656566A/zh
Application granted granted Critical
Publication of CN102656566B publication Critical patent/CN102656566B/zh
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1076—Parity data used in redundant arrays of independent storages, e.g. in RAID systems
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1008—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1008—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices
    • G06F11/1012—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices using codes or arrangements adapted for a specific type of error
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1008—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices
    • G06F11/1068—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices in sector programmable memories, e.g. flash disk
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1076—Parity data used in redundant arrays of independent storages, e.g. in RAID systems
    • G06F11/108—Parity data distribution in semiconductor storages, e.g. in SSD

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Quality & Reliability (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Techniques For Improving Reliability Of Storages (AREA)
  • Detection And Correction Of Errors (AREA)
  • Error Detection And Correction (AREA)

Abstract

提供了用于控制数据管理操作的方法和装置，所述数据管理操作包括将数据存储在固态存储系统（5）的固态存储器（6）中。将输入数据存储在所述固态存储器（6）中的连续多组数据写入位置中。每个组包括在所述固态存储器（6）的多个逻辑子区中的每个子区内的一组写入位置。根据第一和第二线性错误校正码对要存储在每个组中的输入数据进行编码。通过从要存储在每个组中的输入数据构建包括数据符号行和列的逻辑阵列来执行编码。分别根据所述第一和第二线性错误校正码对所述行和列进行编码，以产生其中所有行对应于相应第一码字而列对应于相应第二码字的编码阵列。执行所述编码和存储操作以使得在每个所述组中，编码后的输入数据包括在多个所述逻辑子区中的每个子区内的多个第一码字，并且每个逻辑子区包含该组的每个所述第二码字的一部分。

Description

固态存储系统中的数据管理
本发明一般地涉及固态存储系统中的数据管理。提供了用于控制数据存储过程（具体地说，错误校正（EC）编码数据的存储）以及其他数据管理操作的方法和装置。
固态存储器是使用电子电路（一般是集成电路（IC））而非常规磁性或光学介质（例如盘或磁带）来存储数据的非易失性存储器。诸如闪存器件之类的固态存储器件（SSD）目前正革命性地改变数据存储领域。相较于常规存储器件，这些器件因为缺少移动部件而较稳定，且与硬盘驱动器（HDD）相比，这些器件提供更大的带宽、更节约的功耗以及更好的随机I/O（输入/输出）性能。
在SSD中，存储器被组织成存储区或“块”，每个区皆包含一组可写入数据的存储位置。（以下将参照基于NAND的闪存器件来描述SSD的许多工作特性。然而，将理解，类似原理亦适用于其它类型的SSD。）例如，闪存被组织成许多包含数据写入位置的存储块（称为“页”）。典型闪存页的大小是4kB，且典型闪存块包括64个闪存页（因此为256kB）。读取与写入操作逐页执行，而擦除操作仅可以逐块执行。仅可在成功擦除闪存块后才能写入数据。自闪存单元将一个页读到闪存裸片中的数据缓冲器一般需要15到25微秒。将一个页写入闪存单元需要约200微秒，而擦除闪存块正常需要约2毫秒。由于擦除一个块所需的时间比读取或写入一个页的时间长得多，因此将使用称为“写入非到位（writeoutofplace）”的写入方案来改进写入吞吐量与延迟。使用此方案时，不会在闪存存储器中在原位置更新已存储的数据页，而是将更新后的页写入另一个可用闪存页，并在存储为每个页的一部分的元数据中，设置一个有效性标志，以将关联的旧闪存页标记为无效。
写入非到位方案以及其它闪存存储特征需要执行某些“清扫”操作以用于闪存存储器的内部管理。例如，在更新页并使旧页无效时，需要后续过程以消除无效数据，并释放存储位置给新输入数据。此内部管理过程一般称为“垃圾收集（garbagecollection）”。垃圾收集过程包括选择已使用的闪存块，以及自该块恢复所有仍有效的数据。有效数据页被复制到闪存存储器中的另一个位置，接着擦除该块。垃圾收集通常根据块所包含的无效页的数量来选择这些块。然而，垃圾收集与块擦除亦可作为其它内部管理过程的一部分执行，这些过程包括在固态存储器内移动数据。此类内部管理过程的一个实例是耗损均衡（wear-leveling）。此过程解决闪存的耗损特性。具体而言，在其存储完整性开始降低前，闪存具有有限数量的写入-擦除循环。耗损均衡程序旨在在所有可用闪存块间平均分布写入-擦除循环，以避免不平均的耗损，进而延长整体寿命。具体而言，耗损均衡功能根据写入-擦除循环计数，掌管选择新数据应写入的块，以及在闪存内移动已存储的数据，以释放具有较低循环计数的块，并平均耗损
数据放置与内部管理操作一般由闪存存储器附带的专用控制装置（称为闪存控制器）执行。闪存控制器在总体上管理闪存内的数据、控制所有内部管理操作、以及在控制器存储器内维护地址元数据，以追踪闪存存储器中数据的位置。具体而言，闪存控制器运行中间软件层（称为“LBA-PBA（逻辑块地址-物理块地址）”映射）（亦称为“闪存解译层（FTL）”或“LPN-FPN（逻辑页码-闪存页码）地址映射”）。此层以地址映射的方式维护元数据，所述地址映射将与来自上层（例如存储系统中的文件系统或主机）的输入数据块关联的逻辑地址映射到闪存上的物理地址（闪存页码）。此软件层隐藏闪存擦除前写入的复杂性，并支持透明的数据写入与更新而无需擦除操作的介入。
SSD中执行的内部管理功能导致所谓的“写入放大”。写入放大的发生是因为数据在存储器内部移动，导致数据写入操作的总数相比于SSD所收到的原始数据写入请求的数量而被放大。写入放大是限制固态存储器件的随机写入性能与写入持久寿命的重要问题之一。另一个关键问题是错误性能。通过在写入单元级别增加冗余而在SSD中执行错误校正（EC）编码。具体而言，为写入每个页的输入数据或页内的每个区段的输入数据计算EC码，且此EC码与输入数据一起记录在该页或该区段内。此编码允许在各个数据页内从错误中恢复。然而，固态存储系统可采用额外的EC编码防止器件级别的故障。通过以RAID（独立设备冗余阵列）阵列的方式管理器件集合来执行此编码，如通常HDD存储系统使用的那样。在美国专利申请公开号US2008/0320214A1以及http://www.storagenewsletter.com/news/flash/sandforce-ssd-controllers处的“启动Sandforce的SSD控制器”中讨论了采用类似RAID保护的SSD系统。在一种情况下，存储系统可使用多个SSD，每个SSD与管理其本身的逻辑存储的控制器一同工作，如上述的那样。可接着以类似RAID阵列的方式在更高级别管理SSD的集合。将参照附图的图1描述此类系统的基本操作原理。
图1是一个示意性的类似RAID的基于SSD的存储系统1的方块图。在此系统中，多个SSD2在存储控制器3下工作，存储控制器3负责处理来自主机的读/写请求。每个SSD2管理其内部存储器4中的数据，已如上述。一般而言，存储器4可包括一个或多个存储通道，每个通道具有一个或多个芯片或许多芯片封装，其中每个芯片可包括一个或多个固态存储裸片。在存储控制器3中，主机LBA（逻辑块地址）空间被逻辑地分区，且将每个逻辑块的一个区段分配给相应SSD2。在此阶段增加冗余，进而得以增加RAID奇偶校验。具体而言，存储控制器3对每个输入主机数据块（对应于给定主机（“全局”）LBA）进行错误校正编码，且产生的RAID奇偶校验被添加到主机数据块。编码有奇偶校验的块接着被控制器3分成“单元数据块”。每个单元数据块在已分配单元LBA（uLBA）下供应给相应SSD2以便存储。SSD集合中，全局LBA（gLBA）到uLBA的映射由控制器3记录在gLBA-uLBA映射表中。每个SSD存储其相应单元数据块，并像往常一般将物理存储位置记录在uLBA-PBA映射表中。作为此过程的结果，RAID码字分布在SSD2阵列间，如图中阴影区域所示。这提供了额外级别的EC编码以避免SSD级别的故障。在每个SSD2内，局部控制器执行存储器4的内部管理，已如上述，但在此架构中，此功能及uLBA到PBA的随后重新映射对存储控制器3而言是透明的。
图1例示所谓的“外部RAID”配置，其中RAID码字跨多个SSD，因此亦跨多个控制器。除了外部RAID或替代外部RAID，还可采用“内部RAID”系统。内部RAID在SSD控制器内实现。在此控制器中，LBA空间被逻辑地分区，且将每个逻辑块的一个区段分配给整个存储空间的不同子单元。再次添加冗余以允许添加内部RAID奇偶校验，以将内部RAID码字分区并分布在子单元的集合中。具体而言，将内部RAID码字分区成子单元数据块，且每个子单元数据块在各个子单元的地址空间中分配有子单元LBA（suLBA）。LBA到suLBA的映射由控制器记录在LBA-suLBA地址映射中。每个子单元数据块接着被存储到物理存储位置处的相应存储子单元，其位置记录在该单元的suLBA-PBA映射表中。此过程提供EC编码，以避免SSD中子单元级别的故障。如外部RAID系统那样，控制器在每个存储子单元内独立执行内部管理（垃圾收集、耗损均衡等），使此功能与suLBA到PBA的随后重新映射得以在比逻辑块级别处的RAID编码更低的逻辑级别处工作。
还可以在固态存储区域中应用第一和第二EC编码过程以改善错误恢复，所述第二EC编码处理由所述第一EC编码过程产生的码字。NAND闪存制造商越来越多地使用多级单元（MLC），每个单元存储多个位，以便降低每个位的成本并增加存储容量。MLC固有地不如单级存储单元（SLC）可靠。由于这种趋势，MLCNAND闪存的耐久性从大约100,000次写入/擦除循环减少到大约10,000次写入/擦除循环。在这些情况下，扇区或页的第一EC编码的错误校正能力不再足够，因为与MLCNAND关联的原始位错误率比与SLCNAND关联的原始位错误率降低更快。因此，需要其他编码以延长MLCNAND寿命/耐久性并提供应用通常所需的1e-11至1e-19的低用户位错误率。例如，国际专利申请公开WO2007/084751A2描述了EC编码和具有一个或两个EC编码器的处理系统。通常提及各种代码，其中包括诸如RS（里德-所罗门）和BCH（博斯乔赫里霍克文黑姆）之类的线性代码，但通常不考虑存储装置中的码字排列的细节。提及了以如上描述的内部RAID式方式跨一系列存储器使用RS编码。另一个实施例建议针对数据行使用TCM（格式码调制）编码而针对数据列使用RS编码，其中得到的矩形数据块将作为整体块被写入存储区域。这种编码类似于在其他类型的数据存储装置（具体地说，CD（光盘）、DVD（数字视频光盘）和磁带存储系统）中使用的RS乘积码。在此，输入数据被组织成包括数据符号行和列的逻辑阵列并根据相应第一和第二RS码对行和列进行编码，以便得到的编码阵列的每个行是RS码字，每个列也是RS码字。但是，WO2007/084751A2的主要焦点是所述第一码与所描述的处理系统的调制器/解调器之间的交互。
本发明的一个方面提供了一种用于将数据存储在固态存储系统的固态存储器中的方法。所述方法包括：
将输入数据存储在所述固态存储器中的连续多组数据写入位置中，每个组包括在所述固态存储器的多个逻辑子区中的每个子区内的一组写入位置；以及
对要存储在每个组中的输入数据进行编码，方式为：从该输入数据构建包括数据符号行和列的逻辑阵列并根据相应第一和第二线性错误校正码对所述行和列进行编码，以产生其中所有行对应于相应第一码字而列对应于相应第二码字的编码阵列；
所述方法使得在所述每个组中，编码后的输入数据包括在多个所述逻辑子区中的每个子区内的多个第一码字，并且每个逻辑子区包含该组的每个所述第二码字的一部分。
因此，在本发明的各实施例中，固态存储系统中的存储空间被逻辑分区为多个逻辑子区，并且输入数据被写入跨这些逻辑子区分布的多组写入位置。具体地说，每个组包含在多个逻辑子区中的每个子区内的一组（一个或多个）写入位置。使用第一和第二线性EC码对要存储在每个组中的输入数据进行编码。从该组的输入数据构建包括数据符号行和列的逻辑阵列。根据所述第一和第二错误校正码分别对所述阵列的行和列进行编码，以产生其中所有行对应于相应第一码字而列对应于相应第二码字的（逻辑）编码阵列。然后跨多个所述存储子区写入得到的码字，以在单独子区中和作为整体跨一组子区提供所述第一和第二码字的特定排列。具体地说，所述编码和数据存储过程使得在每组写入位置中，将多个所述第一码字存储在多个所述存储子区的每个子区中，并且每个子区包含该组的每个所述第二码字的一部分。这在固态存储系统中提供卓越的性能，且通过编码过程在存储子区中和跨整体存储装置提供改进的错误保护以及防止系统中单独存储子区中的故障。此外，在所描述的编码架构中使用线性码允许以特别简单而高效的方式实现编码，并通过使用下面进一步描述的“暂时”EC码提供进一步改进的基础。因此，本发明的各实施例提供高效、可靠和稳健的固态存储系统以及卓越的整体性能。
如上面指出的，针对组中输入数据的EC编码过程通过从该输入数据构建包括数据符号行和列的逻辑阵列来执行。当然，此阵列结构只是用于EC编码操作目的的逻辑结构，而不需要在物理上如此形成。根据所述第一EC码对此逻辑阵列的行进行编码而根据所述第二EC码对列进行编码。（在此过程中，何者为“行”和“列”取决于根据认定的阵列方向进行的选择，因此“行”和“列”在此实际上可互换）。在不同的实施例中，所述第一和第二编码过程的执行顺序（即，首先对哪些行和列进行编码）可以不同。当然，无论哪个代码被最后应用都会处理由首先应用的代码生成的码字。例如，如果首先执行行编码，则针对输入数据的编码行（即，第一码字）执行列编码。要指出的是，行和列编码的符号大小无需相同，即，第一和第二码字的符号可具有不同数量的位。在得到的编码阵列（再次地，仅为逻辑结构）中，行和列分别对应于第一和第二码字。虽然所有行对应于相应第一码字，但并非所有列均一定对应于相应第二码字。这将在下面进一步讨论。
通常，所述第一和第二编码过程可以通过系统性编码（其中编码不改变编码过程的输入数据，但向未编码符号添加奇偶校验码以获得输出码字）或通过非系统性编码（其中编码将编码过程的输入数据嵌入输出码字中）来实现。但优选地，采用系统性编码。具体地说，所述第二码字优选地通过系统性编码过程产生，由此针对每个第二码字向一组未编码符号添加奇偶校验码。本发明的各优选实施例然后利用所述第一和第二EC码的线性来不仅提供简单而高效的编码器实施方式，而且还提供额外的错误恢复机制。此机制使用在此所述的“暂时奇偶校验码”。具体地说，对于每个第二码字，在存储该码字的一组未编码符号期间的连续阶段，针对目前为止为该码字存储的符号生成暂时奇偶校验码。此暂时奇偶校验码允许在部分写入的组中从例如由于在组的写入过程中的故障引起的错误恢复。此外，响应于所述存储系统的电力中断，将暂时奇偶校验码有利地复制到所述固态存储器中，由此在出现电源故障时保留暂时码。这可防止同时发生的电源和存储子区故障。
所述暂时奇偶校验码在存储第二码字的一组未编码符号期间的连续阶段生成，优选地在存储每个连续符号时生成。通过利用所述EC码的线性特性，可以在每个阶段以简单的方式生成暂时奇偶校验码，方式为：计算每个新存储的符号的“奇偶校验矢量”并简单地将其添加到针对先前存储的符号生成的暂时奇偶校验码。最后一个符号的暂时奇偶校验码于是包括该码字的奇偶校验码。这可以通过简单的反馈寄存器电路高效地实现，如下面进一步讨论的。此外，特别优选的实施例采用循环码作为第二错误校正码，利用循环特性以实现更进一步的优点。这将在下面详细描述。这些实施例提供带有暂时奇偶校验码生成的非常简单而高效的编码器实施方式。
所述固态存储器的数据写入位置可以是闪存系统中的闪存页。但通常，写入位置可以是固态存储系统中可向其中写入数据的整体存储器的任何区域。可以在具有多个SSD的系统中（例如，在图1中的存储控制器的级别）应用体现本发明的某些方法，由此输入数据被写入跨多个SSD的多组写入位置。在此，整体系统存储器的每个逻辑子区例如可以是特定SSD中的存储器。其他实施例在单个SSD、跨此器件的存储器的子区的多组写入位置中实现。存储器作为整体通常可以包括存储项目（从诸如芯片或裸片之类的单个项目到多组项目）的任何所需配置。但是，典型的SSD将具有多个存储通道，每个存储通道提供存储库（bank）或站（site），其通常包含具有一个或多个存储芯片的多个封装，每个存储芯片具有一个或多个固态裸片。在SSD中，可用存储器被逻辑分区成的子区可以是整体存储区域的任何子集。例如，在其中SSD具有多个存储通道而每个存储通道具有一组固态存储单元（其中每个单元通常可以包括封装、芯片、裸片或任何其他存储区域）的实施例中，每个逻辑子区可以包括相应通道中的一组单元。（通常，在此提及一组项目时，该组可以包含一个或多个项目，除非上下文另外规定）。备选地，每个逻辑子区例如可以包括相应存储单元。
在前面描述的RAID式系统中，当跨整体存储器的若干子单元执行EC编码时，此编码在逻辑块（LBA）级别执行。涉及在存储区域中移动数据和擦除写入位置块的内部管理（垃圾收集、耗损均衡等）功能对编码系统而言是透明的。具体地说，在每个存储子单元中独立执行内部管理，以便此功能和随后suLBA到PBA的重新映射将在低于RAID编码的逻辑级别运行。在与申请人的案号为CH9-2009-0006的申请同时提交的未决欧洲专利申请中披露了一种备选系统。该申请（其相关内容在此引入作为参考）披露了一种系统，其中EC编码在物理块（PBA）级别执行，并且可以针对整体存储区域执行内部管理功能。相应地，本发明的第二方面提供了一种用于管理固态存储器件中的数据的方法，其中固态存储器包括可擦除块，每个可擦除块包括多个数据写入位置。所述方法包括：
通过如本发明第一方面所述的方法存储输入数据，其中每个所述组包括在所述逻辑子区中的每个子区内的一组可擦除块中的写入位置；
维护指示输入数据在所述固态存储器中的位置的元数据；
维护存储在每个数据写入位置内的数据的有效性的指示；以及
在擦除块之前，从包含该块中的写入位置的一个或每个所述组恢复有效输入数据，并将所恢复的数据重新存储为新输入数据。
在本发明的此方面的各实施例中，块擦除过程适于在组的基础上恢复有效数据。当例如在垃圾收集或其他内部管理功能期间需要块擦除时，则在擦除给定块之前，从包含该块中的写入位置的一个或每个所述组恢复有效数据。如此恢复的有效输入数据然后可以作为新的输入数据重新存储在新的EC编码后的组中。因此，本发明的此方面的各实施例提供所述第一方面的编码和存储系统的优点，同时允许针对整体存储器执行内部管理功能。与上面讨论的RAID式系统（在LBA到PBA映射之上实现）不同，EC编码在物理块（PBA）级别而不是在逻辑块（LBA）级别执行，并且整个存储区域可以作为一个实体管理以实现内部管理目的。通过协同基本内部管理功能在物理块级别执行EC编码，这些实施例以高度性能高效的方式提供改进的错误保护。具体地说，EC编码和内部管理过程之间的协同提供卓越的错误恢复以及增强的整体性能。例如，可以实现改进的错误保护，而没有因在较高级别执行EC编码而引起的性能损失（就写入放大增加和耐久性降低而言）。因此，总体上，这些实施例在固态存储器件中提供卓越的性能。
本发明的第三方面提供了一种计算机程序，其包括用于使计算机执行根据本发明的第一或第二方面的方法的程序代码装置。将理解，“计算机”一词是作最一般的使用，其包括具有实施计算机程序所需的数据处理能力的任何设备、组件或系统。此外，体现本发明的计算机程序可构成独立程序、或可为较大程序中的一个元素，且可提供（例如体现）于计算机可读介质（例如，磁盘或电子传输以载入计算机）。计算机程序的程序代码装置可包括一组指令的任何语言表示、代码或注释，旨在导致计算机直接执行本方法、或在（a）转换成另一语言、代码或注释和/或（b）以不同材料形式重现后执行本方法。
本发明的第四方面提供了一种用于控制在固态存储系统的固态存储器中存储数据的装置。所述装置包括：
控制逻辑，其用于控制将输入数据存储在所述固态存储器中的连续多组数据写入位置中，每个组包括在所述固态存储器的多个逻辑子区中的每个子区内的一组写入位置；以及
第一和第二编码器，其用于根据相应第一和第二线性错误校正码对要存储在每个组中的输入数据进行编码；
其中所述控制逻辑适于从要存储在每个组中的输入数据构建包括数据符号行和列的逻辑阵列，以及其中所述第一和第二编码器适于分别对所述行和列进行编码以产生其中所有行对应于相应第一码字而列对应于相应第二码字的编码阵列；
所述装置适于使得在所述每个组中，编码后的输入数据包括在该组的多个所述逻辑子区中的每个子区内的多个第一码字，并且每个逻辑子区包含该组的每个所述第二码字的一部分。
本发明的第五方面提供了一种固态存储器件，包括多个固态存储单元和根据本发明的第四方面的用于控制在所述存储单元中存储数据的装置。
一般而言，在参照本发明的一方面的一个实施例描述特征的情况下，本发明的另一方面的实施例中亦可提供对应特征。
现在将仅通过实例的方式参考附图描述本发明，这些附图是：
图1是具有RAID式编码的现有基于SSD的存储系统的示意性表示；
图2是体现本发明的固态存储器件的示意性表示；
图3示出了将输入数据写入跨图2的实施例中的存储子区分布的一组写入位置；
图4示出了对图2的SSD中的输入数据进行EC编码；
图5示出了图2的器件的存储子区中的第一和第二码字的排列；
图6示出了图2的器件的第二编码器中的暂时奇偶校验生成电路的一个实施例；
图7a和7b示出了图2的器件的第二编码器的暂时奇偶校验生成电路的另一个实施例的两种不同表示；
图8示出了跨图2中的存储子区的一组写入位置中的写入位置的配置的一个实例；
图9示出了组中的写入位置的配置的另一个实例；
图10示出了在图2的SSD中执行的内部管理过程；以及
图11和12是示出图2的器件中的两种不同编码方案的错误校正性能改进的表。
图2是体现本发明的示意性SSD5的方块图，其示出以下所述的数据管理操作所涉及的主要元素。SSD5具有固态存储器6与控制装置（总体以7表示）。在此实例中，存储器6包括N个存储通道Ch（1）到Ch（N），每个通道提供具有多个存储单元的一个存储库8，在此为闪存存储器裸片9。每个存储库8中的一组闪存裸片9一般可设置于一个或多个芯片或芯片封装上，且可包括SLC（单层单元）裸片、MLC（多层单元）裸片或它们的组合。例如，一个或多个通道可提供MLC存储，而剩余的通道可提供SLC存储。
SSD5的控制装置7包括闪存控制器10形式的控制逻辑、用于为到器件的数据读取与写入请求服务的读/写（R/W）接口（I/F）11、以及用于与闪存存储通道进行数据通信的闪存链路接口12。闪存控制器10一般控制器件5的工作、管理数据的读写以响应收到的请求、并处理闪存存储器6的所有内部管理功能。闪存控制器10还执行数据的EC编码/解码。具体地说，控制器10的控制逻辑包括用于根据第一线性EC码（此后称为“C1码”）执行编码/解码的第一EC编码器/解码器模块EC1，在图中通过方块13示意性地表示。控制器10还包括用于根据第二线性EC码（此后称为“C2码”）执行编码/解码的第二EC编码器/解码器模块EC2，在图中通过方块14示意性地表示。在此特定实例中，将EC编码实现为乘积码，且C1和C2码均为RS码。将在下面描述备选方案。第二编码器模块14还执行暂时奇偶校验码的生成，如下面更详细描述的。控制装置7还包括用于存储闪存控制器10的操作中的各种元数据的存储器15，如下面进一步讨论的。存储器15可以例如包括SDRAM（同步动态随机存取存储器）。
通常，闪存控制器10的控制逻辑（包括EC模块13和14）可以以硬件、软件或它们的组合实现。例如，所述控制逻辑可以全部或部分通过软件实现，所述软件配置控制装置7的处理器以执行所描述的功能。从在此的描述，适合的软件对于本领域的技术人员来说是显而易见的。在本实例中，EC模块13和14通过下面描述的硬连线逻辑电路实现，所述硬连线逻辑电路在闪存控制逻辑的总体控制下执行编码/解码操作。
器件5可直接与主机通信以负责读/写请求，或由更高级的控制器管理，所述高级控制器负责存储系统中多个器件的主机请求。例如，器件5可形成RAID式阵列的一部分，其中存储控制器管理多个SSD，如图1系统所示。因此，与输入读/写请求中所指定的数据关联的逻辑地址可引用全局（主机）地址空间或某些逻辑上的低级地址空间。这些地址此后将简单地称为LBA。
指定起始LBA和请求大小的数据写入请求通过读/写接口11异步到达控制装置7。闪存控制器10控制将输入数据块（对应于相应LBA）写入到闪存6，在写入过程中执行C1和C2编码。在此实例中，首先执行C1编码。（因为在此实例中采用乘积码，所以C1和C2编码的顺序无关紧要，在每一种情况下都获得相同的结果，如本领域的技术人员将理解的那样。因此如果需要，可以颠倒编码顺序）。在写入单元级别执行C1编码。也就是说，将输入数据写入到存储器6中的单独闪存页时，EC1模块13针对此输入数据执行C1编码以便为每个页产生一个或多个C1码字。这些C1码字然后由EC2模块14进一步编码，如下面进一步讨论的。闪存控制器10还将元数据存储在每个页中。此元数据包括页无效（PI）标志形式的有效性指示符。作为闪存控制器10的正常控制操作的一部分，所述控制器可以设置页的PI标志，前提是此页中的数据因某种原因（例如，由于数据更新）而被视为无效，如下面进一步讨论的。
为了将编码数据写入到SSD5的存储区域6，闪存控制器10将存储器6逻辑分区成多个逻辑子区。在此实例中，存在N个逻辑子区，其对应于一组N个通道上的相应存储库8。（编码后的）输入数据块流被写入连续的多组闪存页。在此实施例中，每个组的页跨存储器6的所有逻辑子区分布。具体地说，每个页组（在此称为“步距”（stride））包含每个通道的存储区域8中的一组或“一条”页。每个条通常包含通道存储区域8的一个或多个闪存块中的预定义数量的连续页（即，具有连续PBA的页）。每个条在存储区域8中具有唯一条id。为了方便，条id可以是该条中的第一个页的PBA。
存储控制器10通过控制器10在存储器15中维护的地址元数据记录输入数据在存储器6中的位置。在此，地址元数据包括LBA/PBA地址映射，其指示输入数据块所关联的逻辑地址（LBA）与存储器6中的物理地址（PBA）之间的映射。此类地址映射一般可包括一个或多个表或其它数据结构，从中可确定存储输入数据块的步距（以及其所包括的条）的物理位置。例如，地址映射可在一个表中指明LBA到步距id的映射，以及在另一表中指明步距id到条id的映射，且再一个表指示在条中可找到每个LBA的PBA。然而，实际上，为了方便起见，优选使用包括所有地址元数据的单个查找表。
通过依次写入到每个步距而存储编码后的输入数据。图3示出了当前活动步距的此写入过程。输入数据被写入到步距的每个条，一个条（例如，Ch(N)中的最后一个条）中一组页，从而针对该步距的C2编码过程提供了冗余。也就是说，执行编码和存储过程以便跨器件5的N个存储通道在C2编码步距中分配输入数据。现在将参考图4和5对此进行详细解释。
图4是闪存控制器10的模块13和14为了对C1/C2乘积码进行编码而执行的C1和C2编码过程的示意图。闪存控制器10组织要存储在每个步距中的输入数据以便从此输入数据构建包括数据符号行和列的逻辑阵列。EC1和EC2编码器（13、14）适于分别对该阵列的行和列进行编码。因为在此实例中首先执行C1编码，所以C2编码处理得到的C1编码行的列。在此，在两个编码器模块13、14中使用系统性编码，由此通过向未编码数据添加奇偶校验符号来产生每个码字，而编码过程不改变数据本身。图4更详细地示出了此过程。控制器10将要编码的输入数据分区为连续逻辑块，每个逻辑块包括由k2行和k1列数据符号组成的逻辑阵列，如图中所示。EC1编码器13根据C1码对每个行进行系统性编码以针对此行生成（n1-k1）个奇偶校验符号。将此C1奇偶校验码添加到k1个输入数据符号以产生n1符号C1码字。当所有k2个行均由EC1编码器编码时，得到的一组k2个C1码字形成k2×n1个C1编码符号的逻辑阵列。EC2编码器14执行的C2编码处理此阵列的列。EC2编码器14根据C2码对每个列进行系统性编码以针对此列生成（n2-k2）个奇偶校验符号。将此C2奇偶校验码添加到k2个列符号以产生n2符号C2码字。当所有n1个列均由EC2编码器编码时，得到的一组n1个C2码字形成逻辑（n2×n1）符号阵列，如图中所示。
图4中示出的编码符号阵列被写入单个步距中，如上面参考图3描述的那样。此过程被设计为在单独逻辑子区（在此为存储通道8）中和跨一组子区作为整体提供C1和C1码字的特定配置。此配置通过图5的示意图示出。在所示实例中，为了简单，假设一个步距在N个通道的每一个中包含一个页，并且每个页存储多个C1码字。该码字排列的主要特性为：（1）步距所跨的每个存储子区包含多个C1码字；以及（2）这些存储子区的每一个都包含步距中的每个第二码字的一部分。在图5中示出的步距中，不同的C2码字由具有不同阴影的垂直条表示。第一个通道包含n1个C2码字中的每一个的第一部分。第二个通道包含每个所述C2码字的第二部分，以此类推。在此实例中，最后一个通道（通道N）包含每个C2码字的C2奇偶校验码。
由上述过程产生的C1和C2码字的“正交”排列在SSD5中提供卓越的错误校正性能。这将通过下面的实例示出。但要指出的是，虽然示出的简单实例描述了步距中码字配置的一般原则，但通常C1码字大小可以小于、等于或大于页大小，并且步距可以在每个存储子区中包含多个页。C2编码页当然无需在不同的通道中对齐，并且C2码字部分的排序无需遵循通道顺序。此外，虽然在此将C2奇偶校验码存储在第N个通道中，但任何通道都可以用于奇偶校验，甚至根据需要针对不同的步距使用不同的通道。
通常，取决于系统架构，可以按顺序或并行填充给定步距的条。在本实施例中，其中存储器6由通道逻辑地分区，可以并行将条写入到N个通道。在任何情况下，C2编码器14都旨在利用C1和C2RS码的线性，提供简单而高效的实施方式以及进一步的错误保护特性。具体地说，将步距的C1码字逐渐存储在每个存储子区内的条中时，C2编码器针对目前为止为每个C2码字存储的符号重复计算暂时奇偶校验码。现在将参考图6、7a和7b描述优选编码器设计。（从编码器描述，对应的解码器实施方式对于本领域的技术人员来说很容易地显而易见）。
线性错误校正码的编码器以一对一方式将来自矢量空间GF(q)k的k元组映射成码字，其中k是代码的维度，GF(q)k是元素来自有限域（伽罗瓦域）的所有k元组的集合，且q个元素（q是素数的幂）由GF(q)表示。线性块代码C的系统性编码器可以通过k×n生成矩阵G=[IP]表征，其中I是k×k单位矩阵，P是k×(n-k)矩阵。用于生成码字c（行矢量，具有n个分量）的编码过程可以通过将具有k个分量的输入数据行矢量a与生成矩阵G的相乘来描述，即c=aG。编码过程是k维矢量空间到由代码C定义的k维子空间的线性一对一映射。
线性C2码的系统性编码器可以通过生成矩阵G=[IP]表征，其中I是k2×k2单位矩阵，P是k2×(n2-k2)矩阵。矩阵P的第i行由p i 表示，其中1≤i≤k2。此外，数据矢量a是元素由ai表示的k2元组（行矢量），其中1≤i≤k2。由此编码器生成的逐符号暂时奇偶校验码t i 通过递归方程t i ＝t i-1+ai p i 定义，其中t 0=0且1≤i≤k2。作为数据矢量a的系统性编码过程的结果生成的C2码字是行矢量[ap]，其中奇偶校验行矢量p是编码过程结束（即，在时间i=k2）时的暂时奇偶校验矢量t i 。以下，假设页中的C1码字的数量由整除k2的整数M给定。换言之，页中的每个C2码字具有来自GF(q)的M个元素。在处理第一个页之后生成的暂时奇偶校验码是t M，并且在处理第二个页之后生成的暂时奇偶校验码是t 2M等。最后，在处理最后第（k2/M）个页之后生成的码字是[ap]，其中如上所述，奇偶校验行矢量p是编码过程结束时的暂时奇偶校验码t i 。
图6示出了可如何在C2编码器14中生成C2码字的暂时奇偶校验码。对于每个C2码字，此编码器包括简单的反馈寄存器电路20，如图中示出。当提供每个连续符号ai（来自该C2码字的一组未编码符号）以便存储时，电路20针对该符号生成奇偶校验矢量ai p i 。然后将奇偶校验矢量ai p i 添加到针对由寄存器21输出的前一个符号生成的暂时奇偶校验码t i-1。（在此要指出的是，第一个符号的暂时奇偶校验码t 1只是该符号的奇偶校验矢量a1 p 1 ）。此矢量添加的结果是到目前为止为C2码字存储的符号的当前暂时奇偶校验码t i 。然后将暂时奇偶校验码t i 存储在寄存器21中。当在时间i=k2存储最后一个符号ai时，由电路20输出的暂时奇偶校验码是该码字的奇偶校验码p。
从上面将看到，使用通过来自GF(q)的(n2-k2)个符号和简单的反馈电路存储t i 的寄存器21，以特别简单的方式在存储连续符号ai时生成暂时奇偶校验码t i 。可以将C2奇偶校验存储在(n2-k2)/M个页或芯片上。如果(n2-k2)/M=1，则只需要一个“额外的”芯片来存储C2奇偶校验，并且此方案可以恢复由于单个芯片故障引起的丢失数据。如果(n2-k2)/M=2，则需要两个额外的芯片来存储C2奇偶校验，并且此方案可以在恢复过程中恢复由于两个芯片故障引起的丢失数据。此外，当需要暂时奇偶校验码以便在部分完成的步距中从错误恢复时，闪存控制器10可以使用存储在寄存器21中的暂时奇偶校验码。此外，如果闪存控制器检测到控制装置7的电力中断，则在关机之前，所述控制器将当前暂时奇偶校验码（连同存储器15中的其他元数据，包括当前地址映射）复制到闪存存储器6中的可用区域。因此，可以在出现电源故障时保留暂时奇偶校验码，防止同时发生的电源故障和存储单元/通道错误。
要指出的是，虽然上面的描述专注于C2编码器14以解释暂时奇偶校验机制，但可以类似地根据上述原则通过简单的反馈寄存器电路实现C1编码器13。
在特别优选的实施例中，C2编码器14中使用的C2码是循环码，并且编码器设计利用此类代码的特性以获得特别简单而高效的实施方式。对于循环码，可以方便地引入多项式表示法。以下，码字c=(c0,c1,…,cn-1)通过码字多项式表示。类似地，诸如数据矢量之类的所有行矢量也将通过多项式表示。循环码通过唯一首一生成多项式表征，其中生成多项式的所有系数都来自GF(q)，并且生成多项式的首项系数是1，即gn-k=1。循环码的所有码字是生成多项式g(x)的倍数。换言之，循环码中的每个码字都可以表示为生成多项式与次数为(k-1)或更低的多项式的乘积。
可以按如下方式获得循环码的系统性编码器。假设系统性编码器的输入端处的数据多项式为循环码的对应码字（通过生成多项式g(x)表征）于是由c(x)=xn-ka(x)+p(x)给出，其中选择次数为(n-k-1)或更低的奇偶校验多项式p(x)，使得c(x)可被g(x)整除。
图7a示出了可如何在C2编码器14中生成使用生成多项式g(x)的循环C2码的暂时奇偶校验码。对于每个C2码字c(x)，此编码器包括线性反馈移位寄存器电路（LFSR）25，如图中示出。当提供来自C2码字的一组未编码符号的每个连续符号以便存储时，电路25生成通过多项式表示的暂时奇偶校验码。移位寄存器电路的反馈系数由生成多项式的系数gj给出，j均为0≤j≤n2-k2-1。移位寄存器的内容是在时间i的暂时奇偶校验多项式的系数。在开始时，寄存器被初始化为0，即对于所有0≤j≤n2-k2-1，作为数据多项式a(x)的系统性编码过程的结果生成的C2码字于是为码字多项式其中奇偶校验多项式p(x)是编码过程结束（即，在时间i=k2）时的暂时奇偶校验多项式ti(x)。将i个符号移位到反馈移位寄存器电路之后，计算暂时奇偶校验多项式ti(x)。以下，假设页中的C1码字的数量通过整除k2的整数M给出。换言之，页中的每个C2码字具有来自GF(q)的M个元素。在处理第一个页之后生成的暂时奇偶校验多项式ti(x)则是tM(x)，在处理第二个页之后生成的暂时奇偶校验多项式是t2M(x)等。最后，在处理最后第（k2/M）个页之后生成的码字是其中如上所述，奇偶校验多项式p(x)是C2码字的奇偶校验码并对应于编码过程结束时的暂时奇偶校验多项式ti(x)。如前所述，在出现电源故障时，可以将来自寄存器电路25的暂时奇偶校验码复制到闪存存储器6中。
图7a的LFSR电路25是有限状态机，其中在时间i的状态由暂时奇偶校验多项式ti(x)定义，并且输入符号是因此，所述LFSR电路可以通过状态更新方程描述，1≤i≤k2，如图7b中示出。初始条件通过t0(x)=0给出。
在SSD5的操作中，错误检查通常在每次数据写入之后执行，以及响应于读取请求在读出数据时执行或在下面讨论的内部管理操作期间执行。每当EC1模块13的C1解码器无法对C1码字进行解码时，便会将C1码字声明为“已擦除”（错误）。然后可以通过EC2模块14的C2解码器校正这些C1擦除。如果步距中的C2奇偶校验仅位于一个通道上，则C2RS解码器的错误校正能力是每个页的C1码字的数量除以二，而C2RS解码器的擦除校正能力是每个页的C1码字的数量。C1码字还可以包含CRC（循环冗余校验码），其可以用于在CRC不校验的情况下在C1解码器的输出处将C1码字声明为已擦除。每当条包含无法通过C1错误校正过程校正的页或块错误时，闪存控制器10便会执行下面的过程。从与包含错误的条相同的存储区域8中选择新条。此条将替换有问题的步距中的“坏条”。通过存储器15中的地址元数据标识步距中的其他条，并读取这些条的内容。读取坏条的内容，并使用步距中的其他条的内容通过C2解码算法来重构坏条中的错误数据。然后将已重构的（已校正错误的）数据写入替换条，并更新地址元数据以反映修改后的步距结构。然后在旧的坏条的每个页中设置页无效（PI）标志以指示这些页的内容无效。将在下面描述的后续垃圾收集过程中回收这些页。
条到特定步距的分配以及写入操作中步距选择的顺序可以以各种方式在控制器10中实现，并且适合的实施方式对于本领域的技术人员将是显而易见的。这些特性并不是本发明的中心所在，在此不需要详细讨论。但通常，每个条包含在给定通道中的一个或多个闪存块中的页。图8和9示出了可能步距配置的两个实例。在图8中，C2条大小为四个页。单个步距通过图中的箭头指示。假设闪存块大小为64个页，则每个块将包含16个不同步距的条。这16个步距在所有通道中共享同一块。共享一组公共块的这样一组步距在此后称为步距组。要指出的是，不同通道存储区域8中的同一步距组的块不需要在物理上对齐。图9示出了备选实例，其中C2条大小为两个块。因此每个步距包括每个存储通道中的两个块，并且在此步距组包括一个步距。要指出的是，每个通道存储区域8中的同一步距的块不需要在物理上对齐。
当使用前面解释的写入非到位方案在闪存存储器6中更新数据时，闪存控制器10针对任何已通过LBA盖写更新的页设置页无效（PI）标志。PI标志的设置类似于针对包含由主机删除的数据的页进行的设置。存储控制器10还针对每个步距组维护指示该整个步距组中的无效页数量的计数。步距组的这些PI计数作为在存储器15中维护的元数据的一部分被记录。在由控制器10执行的内部管理操作期间使用PI计数，如下面进一步描述的。
尽管存储器6被逻辑分区以实现上述C2编码，但针对整体存储器执行内部管理功能。也就是说，闪存控制器10将所有子区（N个存储通道）视为单个存储实体以实现内部管理目的。在此方面，涉及擦除块的内部管理功能（例如，垃圾收集与耗损均衡）适于负责跨区的C2编码。具体而言，此类过程期间，有效数据的恢复在步距组而非块的基础上执行。在擦除块之前，从步距组中包含该块的写入位置的一个或每个步距中恢复有效输入数据。参照图10的垃圾收集过程进一步描述了此操作。
图10的方块图示出了在SSD5中执行的垃圾收集过程中的主要步骤。当启动垃圾收集（通过图中的步骤30表示）时，闪存控制器10首先选择要擦除的块。在步骤31执行的此选择基于针对步距组存储在存储器15中的PI计数。具体地说，可以选择具有最高PI计数的步距组中的块以便首先回收。选择步距组之后，在步骤32，闪存控制器从该步距组的页恢复所有仍有效的数据。因此，从没有设置相应PI标志的步距组中的所有页中读取数据。在此过程中，可以根据需要执行上述基于C1和C2码的错误校正处理。然后，反馈如此恢复的有效数据以作为要重新存储在闪存存储器6中的输入数据。因此，所恢复的数据重新存储在新步距中，如步骤33所示。在步骤34，闪存控制器10更新存储器15中的地址映射以反映新的数据位置。然后在步骤35，闪存控制器10可以擦除旧的已回收步距组的块。控制器10可以立即或在后续任一时间执行块擦除以释放这些块供存储新数据。
如上所示，垃圾收集期间将一起回收步距组的所有条。相同原理亦适用于在块擦除之前需要移动闪存内的数据的任何内部管理过程（例如，耗损均衡）。作为控制器10正常监视功能的一部分，显示持久性问题（太多C1错误）的块可在回收过程期间被识别并标示为“坏块”。此加标志操作可基于由闪存控制器10作为存储器15内存储的元数据的一部分而维护的块错误计数。藉此，控制器10随后的数据放置将不会使用被标记为坏的块。
从上面将理解，与现有RAID式系统不同，在SSD5中在物理块级别执行C2编码，并将整个存储区域作为一个实体管理以实现内部管理目的。C2编码操作对LBA/PBA映射而言是透明的，并防止在页、块、芯片、存储库和通道级别发生完全故障。如上述那样使用暂时奇偶校验码还防止同时发生电源和单元故障。通过如上所述以与内部管理功能协作的方式执行C2编码，SSD5可获得改进的错误率以及卓越的整体性能。例如，错误校正性能得以增强，而没有较高级编码的写入放大和耐久性降低。例如，假设在每个情况下使用一个通道作冗余，则SSD5可与上述RAID式基于SSD的系统相比较。在SSD5中，假设通道N全部分配给C2码，定义w1为内部管理（垃圾收集与耗损均衡）所导致的写入放大。如果为了方便，假设每个条仅包含一个页，则每个页写入导致（1+1/（N-1））w1个页写入，因为控制器为（N-1）个页计算奇偶校验页，每个通道皆有一个奇偶校验页。相比之下，对于RAID式系统，如果w2表示垃圾收集与耗损均衡所导致的写入放大，则每个页写入导致2w2个页写入、一个数据页与一个RAID奇偶校验页。此外，w1<w2，因为内部管理“全局地”执行，将所有的存储通道视为一个统一存储区。
上述特性在固态存储系统中导致卓越的性能。通过实例的方式，图11的表将使用上述基于RS的C2码方案的结果与使用无C2码和简单的基于XOR的C2码的结果进行比较。此表总结了使用平均猝发长度为5位的吉尔伯特猝发错误通道的为1e-3的原始NAND位错误率的结果。列显示对于不同的C1数据字大小512字节（512B）、1KB、2KB和4KB，三种编码系统（“无C2”、XOR和“RS”）中的每一种的所需C1开销（以位为单位）。（要指出的是，C1码字大小（以位为单位）是C1数据字大小（以位为单位）和C1奇偶校验大小（以位为单位）的总和。此外，1KB代表1024B，2KB代表2048B，4KB代表4096B）。每个行提供不同用户位错误率（BER）的结果。假设（8+1个奇偶校验）个通道（页）。页大小假设为4096个字节。可以清楚地看到，基于RS的C2码显著降低了所需的C1RS开销。实际上，所有情况现在都在足够开销的范围内，即对于情况[512B、1KB、2KB、4KB]需要的开销小于或等于[218、436、872、1744]位。在此假设4KB+218B的MLC闪存，即，一个页包含（4096+218）个字节。借助新的40纳米NAND闪存技术，已经可提供8KB页大小。对于8KB页大小，基于RS的C2码的增益甚至更为显著，因为对于相同的C2码率，基于RS的C2码字更长。
要指出的是，还可以针对C1和/或C2码使用诸如BCH码之类的其他线性码，前提是编码架构如上述那样通过存储子区提供所需的C1和C2码字排列。作为一个实例，图12的表提供了3位MLC闪存的C1开销（以位为单位），并以8阵列BCH码作为C1码。在此，开销（以位为单位）是上界，因为使用BCH界限。C2码是RS码，并假设（8+1个奇偶校验）个通道（页），与图11的表中那样。原始NAND位错误率再次为1e-3。假设在通道中发生单独8阵列符号错误，并且页大小与之前一样假设为4096个字节。
从上面将看到，本发明的各实施例显著减少了页EC开销（C1开销）。对于固定的C1开销，这相当于显著改进了所存储数据的完整性。此外，以就计算和存储器资源而言高效的方式计算暂时奇偶校验码，并提供额外的错误恢复机制。
在给定情况下，通过适当选择C2步距和条大小以及条大小与LBA大小的关系，可以甚至进一步提高效率。这些考虑事项类似于在RAID应用中遇到的考虑事项，如本领域的技术人员将显而易见的那样。在本发明的某些实施例中，所述闪存控制器可以适于在操作中动态调整C2条和步距大小。例如，所述闪存控制器可以根据预定准则（例如，根据写入请求的大小），在不同的条/步距大小之间切换。步距长度亦可随着块变得越来越不稳定（例如，因为耗损与老化）而减短。对所描述的实施例的适当修改将对本领域技术人员显而易见。
因为在上面的实例中采用乘积码，所以符号大小对于C1和C2编码是相同的。因此，图4中的每个小矩形表示C1和C2码字两者的符号。此外，在得到的编码阵列中，所有行对应于相应C1码字而所有列对应于相应C2码字。但是，并非必需使用乘积码。通常，可以针对级联编码方案的C1和C2码采用任何线性码，并且这些C1和C2码的符号大小（因而行和列编码）无需相同。对于此类更常见的级联编码，通常首先执行C2编码。因此，参考图4（并为了简单，假设C1和C2符号大小相等），首先对k2×k1输入数据阵列的列进行编码以产生k1个C2码字。然后对得到的阵列的行进行编码以产生n2个C1码字。在这种情况下，得到的编码阵列的所有行均为C1码字。但是，编码阵列的包含C1奇偶校验符号的最后几个（在此为n1-k1）列无需是C2码字。因此对于这种情况，在等效的图5排列中，每个通道中的最后几个（在此为n1-k1）垂直条不需要是C2码字的部分，而是可以只是包含C1奇偶校验符号。
将理解的是，可以对上面的实施例进行各种进一步的更改和修改。通过实例的方式，虽然用于C2编码的存储器6的逻辑子区与SSD5中的存储通道对齐，但通常这些子区可以是可用存储器的任何子集。例如，在图2中子区可以备选地包括相应闪存裸片9。也可以跨存储系统中的一组SSD应用所描述的编码架构，每个存储子区对应于特定SSD中的存储器。此外，个体C2码字不一定需要跨所有子区。在器件5中，C2步距例如可以备选地跨少于总数N的多个通道，整体步距集合跨所有通道分布。在这种情况下，当在C2错误校正过程中选择新条以替换坏条时，可以从同一存储通道或任何其他已经不包含同一步距的条的通道中选择新条。如上所述，当块变得不可靠时，步距长度也可减小以便步距跨更少的通道。
在上述实施例中，步距包含每个存储子区中的一个块或每个块中的多个页，每个块中的页是连续的（即，具有连续物理地址）。但通常，任何一个子区中的步距的一组页可以包含多于或少于块中页数的页。为了获得简单的实施方式，每个子区中的页数优选地是块中页数的整数因子或整数倍数。如果每个子区中的组的页数小于块大小，则多个组可以共享同一块。在这种情况下，如果共享一个逻辑子区中的公共块的任何组也共享每个逻辑子区中的公共块，则内部管理操作将被显著简化。
在某些实施例中，系统可以从其中仅执行C1解码的模式切换到其中额外执行C2码字解码的模式。例如，在存储器寿命的早期，可能仅例行执行C1解码，除非器件故障需要C2解码。但是，当原始错误率随耗损增加而增大时，可例行执行C2解码以改进数据可靠性和器件耐久性。
虽然具体描述了NAND闪存器件，但本发明当然可以应用于其他类型的固态存储系统。此外，在给定系统中，可以根据使用的闪存类型和特定的错误机制来选择采用的特定C1码。通常，C1码可以是任何线性码，例如二进制BCH码或q阵列BCH码以及RS码。类似地，虽然优选RSC2码，但C2码通常可以是任何线性码，并且优选地也可以是循环码。
可对上述示意性实施例做出许多其它更改和修改而不偏离本发明的范围。

Claims (14)

1.一种用于将数据存储在固态存储系统(5)的固态存储器(6)中的方法，所述方法包括：
将输入数据存储在所述固态存储器(6)中的连续多组数据写入位置中，每个组包括在所述固态存储器(6)的多个逻辑子区中的每个子区内的一组写入位置；以及
对要存储在每个组中的输入数据进行编码，方式为：从该输入数据构建包括数据符号行和列的逻辑阵列，对数据符号的每一行根据第一线性错误校正码进行第一编码，产生对应于第一码字的对应行的编码阵列，然后对所述对应于第一码字的对应行的编码阵列的每一列，根据第二线性错误校正码进行第二编码，产生对应于第二码字的对应列的编码阵列，其中所述编码阵列的所有行对应于所述第一码字，而所述编码阵列的所有列对应于所述第二码字；
其中在所述每个组中，编码后的输入数据包括在多个所述逻辑子区中的每个子区内的多个第一码字，并且每个逻辑子区包含该组的每个所述第二码字的一部分，并且其中存储的第二码字包括一组未编码符号，编码后的输入数据进一步包括：
对于每个第二码字，在存储该第二码字的所述一组未编码符号期间的连续阶段，针对目前为止为该第二码字存储的所述未编码符号通过以下方式生成暂时奇偶校验码：
在存储所述一组未编码符号的每个所述符号时，针对该符号生成奇偶校验矢量；以及
在存储第一个符号之后的每个所述符号时，生成暂时奇偶校验码，方式为：向针对前一符号生成的所述暂时奇偶校验码添加该符号的奇偶校验矢量，其中所述第一个符号的暂时奇偶校验码是该符号的奇偶校验矢量；
由此在存储所述一组未编码符号的最后一个符号时生成的暂时奇偶校验码包括所述第二码字的奇偶校验码。
2.如权利要求1中所述的方法，其中所述第二线性错误校正码是循环码。
3.如权利要求1所述的方法，包括：
通过系统编码过程产生所述第二码字，由此向每个第二码字的一组未编码符号添加奇偶校验码。
4.如权利要求3中所述的方法，包括：响应于所述存储系统(5)的电力中断而将所述暂时奇偶校验码存储在所述固态存储器(6)中。
5.如权利要求1-4之一中所述的方法，其中所述第一和第二线性错误校正码均为里德-所罗门码。
6.如权利要求1-4之一中所述的方法，其中所述固态存储器件(5)具有多个存储通道，每个通道具有一组(8)固态存储单元(9)，其中所述逻辑子区中的每个子区包括相应通道中的所述一组固态存储(8)单元。
7.如权利要求1-4之一中所述的方法，其中所述固态存储器件(5)具有多个固态存储单元(9)，其中所述逻辑子区中的每个子区包括相应固态存储单元(9)。
8.如权利要求1中所述的方法，其中固态存储器(6)包括可擦除块，每个可擦除块包括多个数据写入位置，所述方法包括：
在所述固态存储器存储输入数据，其中每个所述组包括在所述多个逻辑子区中的每个子区内的一组所述可擦除块中的写入位置；
维护指示输入数据在所述固态存储器(6)中的位置的元数据；
维护存储在每个数据写入位置内的数据的有效性的指示；以及
在擦除块之前，从包含该块中的写入位置的一个或每个所述组恢复有效输入数据，并将所恢复的数据重新存储为新输入数据。
9.一种用于控制在固态存储系统(5)的固态存储器(6)中存储数据的装置(7)，所述装置包括：
控制逻辑(10)，其用于控制将输入数据存储在所述固态存储器(6)中的连续多组数据写入位置中，每个组包括在所述固态存储器(6)的多个逻辑子区中的每个子区内的一组写入位置；以及
第一和第二编码器(13、14)，其用于对要存储在每个组中的输入数据进行编码，方式为：从该输入数据构建包括数据符号行和列的逻辑阵列，对数据符号的每一行根据第一线性错误校正码进行第一编码，产生对应于第一码字的对应行的编码阵列，然后对所述对应于第一码字的对应行的编码阵列的每一列，根据第二线性错误校正码进行第二编码，产生对应于第二码字的对应列的编码阵列，其中所述编码阵列的所有行对应于所述第一码字，而所述编码阵列的所有列对应于所述第二码字；
其中，在所述每个组中，编码后的输入数据包括在该组的多个所述逻辑子区中的每个子区内的多个第一码字，并且每个逻辑子区包含该组的每个所述第二码字的一部分，并且其中存储的第二码字包括一组未编码符号，编码后的输入数据进一步包括：
对于每个第二码字，在存储该第二码字的所述一组未编码符号期间的连续阶段，针对目前为止为该第二码字存储的所述未编码符号通过以下方式生成暂时奇偶校验码：
在存储所述一组未编码符号的每个所述符号时，针对该符号生成奇偶校验矢量；以及
在存储第一个符号之后的每个所述符号时，生成暂时奇偶校验码，方式为：向针对前一符号生成的所述暂时奇偶校验码添加该符号的奇偶校验矢量，其中所述第一个符号的暂时奇偶校验码是该符号的奇偶校验矢量；
由此在存储所述一组未编码符号的最后一个符号时生成的暂时奇偶校验码包括所述第二码字的奇偶校验码。
10.如权利要求9中所述的装置，其中所述第二编码器(14)是用于向每个第二码字的一组未编码符号添加奇偶校验码的系统编码器。
11.如权利要求9中所述的装置，其中所述第二线性错误校正码是循环码。
12.如权利要求10或11中所述的装置，其中所述控制逻辑(10)适于响应于所述装置的电力中断而控制将所述暂时奇偶校验码存储在所述固态存储器(6)中。
13.如权利要求10或11中所述的装置，其中所述固态存储器件(5)具有多个固态存储单元(9)，其中所述逻辑子区中的每个子区包括一组(8)相应的所述存储单元(9)。
14.一种固态存储器件(5)，包括多个固态存储单元(9)和如权利要求13所述的用于控制在所述存储单元(9)中存储数据的装置。
CN201080056483.7A 2009-12-17 2010-12-16 固态存储系统中的数据管理 Expired - Fee Related CN102656566B (zh)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
EP09179741.5 2009-12-17
EP09179741 2009-12-17
PCT/IB2010/055875 WO2011073940A1 (en) 2009-12-17 2010-12-16 Data management in solid state storage systems

Publications (2)

Publication Number Publication Date
CN102656566A CN102656566A (zh) 2012-09-05
CN102656566B true CN102656566B (zh) 2015-12-16

Family

ID=43799567

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201080056483.7A Expired - Fee Related CN102656566B (zh) 2009-12-17 2010-12-16 固态存储系统中的数据管理

Country Status (5)

Country Link
US (1) US9037951B2 (zh)
CN (1) CN102656566B (zh)
DE (1) DE112010004863B4 (zh)
GB (1) GB2488462B (zh)
WO (1) WO2011073940A1 (zh)

Families Citing this family (44)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
TWI497293B (zh) * 2009-12-17 2015-08-21 Ibm 固態儲存裝置內之資料管理
JP5367686B2 (ja) * 2010-12-24 2013-12-11 株式会社東芝 データ記憶装置、メモリ制御装置及びメモリ制御方法
KR101778782B1 (ko) * 2011-04-08 2017-09-27 삼성전자주식회사 데이터 저장 장치 및 그것의 동작 방법
US8832506B2 (en) * 2012-01-20 2014-09-09 International Business Machines Corporation Bit error rate based wear leveling for solid state drive memory
US20130262942A1 (en) * 2012-03-27 2013-10-03 Yung-Chiang Chu Flash memory lifetime evaluation method
WO2014041638A1 (ja) * 2012-09-12 2014-03-20 株式会社 東芝 アレイにおける誤り訂正符号ブロック配置位置を管理するストレージ装置、ストレージコントローラ及び方法
US10445229B1 (en) 2013-01-28 2019-10-15 Radian Memory Systems, Inc. Memory controller with at least one address segment defined for which data is striped across flash memory dies, with a common address offset being used to obtain physical addresses for the data in each of the dies
US11249652B1 (en) * 2013-01-28 2022-02-15 Radian Memory Systems, Inc. Maintenance of nonvolatile memory on host selected namespaces by a common memory controller
GB2513377A (en) * 2013-04-25 2014-10-29 Ibm Controlling data storage in an array of storage devices
WO2015024603A1 (en) * 2013-08-23 2015-02-26 Nec Europe Ltd. Method and system for authenticating a data stream
US20150095747A1 (en) * 2013-09-30 2015-04-02 Itzhak Tamo Method for data recovery
KR101550762B1 (ko) * 2013-11-29 2015-09-08 한국과학기술원 연접 오류 정정 장치
CN103838608B (zh) * 2014-03-05 2019-05-24 深圳市中兴物联科技有限公司 NAND Flash页面自适应的方法及装置
GB2525430B (en) * 2014-04-25 2016-07-13 Ibm Error-correction encoding and decoding
US9430326B2 (en) * 2014-07-22 2016-08-30 HGST Netherlands B.V. Multiple ECC codeword sizes in an SSD
US9529672B2 (en) * 2014-09-25 2016-12-27 Everspin Technologies Inc. ECC word configuration for system-level ECC compatibility
WO2016051512A1 (ja) 2014-09-30 2016-04-07 株式会社日立製作所 分散型ストレージシステム
US9710199B2 (en) 2014-11-07 2017-07-18 International Business Machines Corporation Non-volatile memory data storage with low read amplification
CN105701021B (zh) * 2014-12-10 2021-03-02 慧荣科技股份有限公司 数据储存装置及其数据写入方法
US10162700B2 (en) 2014-12-23 2018-12-25 International Business Machines Corporation Workload-adaptive data packing algorithm
US9647694B2 (en) 2014-12-28 2017-05-09 International Business Machines Corporation Diagonal anti-diagonal memory structure
US20160269046A1 (en) * 2015-03-10 2016-09-15 Kabushiki Kaisha Toshiba Memory controller, memory system, and decoding method
US9733870B2 (en) 2015-05-06 2017-08-15 International Business Machines Corporation Error vector readout from a memory device
JP2017010600A (ja) * 2015-06-19 2017-01-12 株式会社日立エルジーデータストレージ 記録再生装置、再生装置、再生データの復元方法、書込みデータ生成方法
US9712190B2 (en) 2015-09-24 2017-07-18 International Business Machines Corporation Data packing for compression-enabled storage systems
TWI569279B (zh) * 2015-10-15 2017-02-01 財團法人工業技術研究院 記憶體保護裝置與方法
US10056920B1 (en) * 2015-11-03 2018-08-21 Western Digital Technologies, Inc. Data storage device encoding and interleaving codewords to improve trellis sequence detection
US10063257B1 (en) * 2015-11-03 2018-08-28 Western Digital Technologies, Inc. Data storage device encoding and interleaving codewords to improve trellis sequence detection
US9761273B1 (en) * 2015-11-03 2017-09-12 Western Digital Technologies, Inc. Data storage device encoding and interleaving codewords to improve trellis sequence detection
US9870285B2 (en) 2015-11-18 2018-01-16 International Business Machines Corporation Selectively de-straddling data pages in non-volatile memory
US10101939B2 (en) 2016-03-09 2018-10-16 Toshiba Memory Corporation Storage system having a host that manages physical data locations of a storage device
US10423500B2 (en) * 2016-06-01 2019-09-24 Seagate Technology Llc Technologies for limiting performance variation in a storage device
KR20180030329A (ko) * 2016-09-13 2018-03-22 에스케이하이닉스 주식회사 메모리 시스템 및 메모리 시스템의 동작방법
US10877842B2 (en) * 2017-09-08 2020-12-29 Intel Corporation Detecting silent data corruption for mass storage devices
CN108281160B (zh) * 2018-01-12 2020-06-19 南阳师范学院 Dvd纠错码的设计方法
US11275512B2 (en) * 2018-05-08 2022-03-15 Micron Technology, Inc. Asynchronous power loss impacted data structure
TWI712268B (zh) 2018-11-14 2020-12-01 慧榮科技股份有限公司 快閃記憶體控制器及其中的編碼電路與解碼電路
US10748606B2 (en) * 2018-12-14 2020-08-18 Western Digital Technologies, Inc. Multi-state programming for memory devices
KR20200078830A (ko) * 2018-12-24 2020-07-02 에스케이하이닉스 주식회사 메모리 시스템 및 메모리 모듈
US11311746B2 (en) 2019-03-08 2022-04-26 Mevion Medical Systems, Inc. Collimator and energy degrader for a particle therapy system
US11038533B2 (en) * 2019-04-25 2021-06-15 International Business Machines Corporation Expansion for generalized EVENODD codes
CN111177075B (zh) * 2019-12-26 2022-04-22 浪潮电子信息产业股份有限公司 一种垃圾数据的识别方法、系统、电子设备及存储介质
CN112910451B (zh) * 2021-01-18 2023-07-14 北京中科芯蕊科技有限公司 一种异步行波状态机
CN115016981B (zh) * 2022-06-16 2023-05-09 海光信息技术股份有限公司 存储区域的设置方法、数据读取、写入方法及相关装置

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7036068B2 (en) * 2001-07-25 2006-04-25 Hewlett-Packard Development Company, L.P. Error correction coding and decoding in a solid-state storage device
CN101477481A (zh) * 2009-02-06 2009-07-08 中国科学院计算技术研究所 一种自动纠错系统及方法

Family Cites Families (18)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4653051A (en) * 1983-09-14 1987-03-24 Matsushita Electric Industrial Co., Ltd. Apparatus for detecting and correcting errors on product codes
JP3328093B2 (ja) * 1994-07-12 2002-09-24 三菱電機株式会社 エラー訂正装置
US20080282128A1 (en) * 1999-08-04 2008-11-13 Super Talent Electronics, Inc. Method of Error Correction Code on Solid State Disk to Gain Data Security and Higher Performance
US8341332B2 (en) 2003-12-02 2012-12-25 Super Talent Electronics, Inc. Multi-level controller with smart storage transfer manager for interleaving multiple single-chip flash memory devices
US20030061558A1 (en) 2001-09-25 2003-03-27 Fackenthal Richard E. Double error correcting code system
US7076606B2 (en) * 2002-09-20 2006-07-11 Quantum Corporation Accelerated RAID with rewind capability
US20060256615A1 (en) 2005-05-10 2006-11-16 Larson Thane M Horizontal and vertical error correction coding (ECC) system and method
US8055979B2 (en) 2006-01-20 2011-11-08 Marvell World Trade Ltd. Flash memory with coding and signal processing
US9116823B2 (en) * 2006-12-06 2015-08-25 Intelligent Intellectual Property Holdings 2 Llc Systems and methods for adaptive error-correction coding
EP2100214B1 (en) * 2006-12-06 2013-10-30 Fusion-io, Inc. Apparatus, system, and method for storage space recovery in solid-state storage
US20090172335A1 (en) 2007-12-31 2009-07-02 Anand Krishnamurthi Kulkarni Flash devices with raid
JP5166074B2 (ja) * 2008-02-29 2013-03-21 株式会社東芝 半導体記憶装置、その制御方法、および誤り訂正システム
US20100180182A1 (en) * 2009-01-09 2010-07-15 Seagate Technology Llc Data memory device and controller with interface error detection and handling logic
US8307258B2 (en) * 2009-05-18 2012-11-06 Fusion-10, Inc Apparatus, system, and method for reconfiguring an array to operate with less storage elements
US8468292B2 (en) * 2009-07-13 2013-06-18 Compellent Technologies Solid state drive data storage system and method
US8463983B2 (en) * 2009-09-15 2013-06-11 International Business Machines Corporation Container marker scheme for reducing write amplification in solid state devices
US8055942B2 (en) * 2009-12-03 2011-11-08 Seagate Technology Llc Data storage devices and methods for power-on initialization
TWI497293B (zh) * 2009-12-17 2015-08-21 Ibm 固態儲存裝置內之資料管理

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7036068B2 (en) * 2001-07-25 2006-04-25 Hewlett-Packard Development Company, L.P. Error correction coding and decoding in a solid-state storage device
CN101477481A (zh) * 2009-02-06 2009-07-08 中国科学院计算技术研究所 一种自动纠错系统及方法

Also Published As

Publication number Publication date
US9037951B2 (en) 2015-05-19
DE112010004863T5 (de) 2012-12-06
GB2488462A (en) 2012-08-29
CN102656566A (zh) 2012-09-05
DE112010004863B4 (de) 2019-10-10
GB2488462B (en) 2018-01-17
WO2011073940A1 (en) 2011-06-23
GB201208241D0 (en) 2012-06-20
US20120260150A1 (en) 2012-10-11

Similar Documents

Publication Publication Date Title
CN102656566B (zh) 固态存储系统中的数据管理
US20190252035A1 (en) Decoding method, memory storage device and memory control circuit unit
US9673840B2 (en) Turbo product codes for NAND flash
US8904261B2 (en) Data management in solid state storage devices
US8307261B2 (en) Non-volatile memory management method
CN108062258A (zh) 用于错误恢复的循环交错的xor阵列
US10388400B2 (en) Generalized product codes for flash storage
US9583217B2 (en) Decoding method, memory storage device and memory control circuit unit
US9058288B2 (en) Redundant storage in non-volatile memory by storing redundancy information in volatile memory
US9710327B2 (en) Flash memory system and operating method thereof
CN105023613B (zh) 解码方法、存储器存储装置及存储器控制电路单元
CN101308706B (zh) 适用于闪存的数据写入方法及错误修正编解码方法
CN113223601A (zh) 一次写入型存储器码的纠错码管理的电路、系统和方法
TWI536749B (zh) 解碼方法、記憶體儲存裝置與記憶體控制電路單元
JP7177338B2 (ja) メモリコントローラ装置、メモリコントローラ装置を有するメモリ装置及びメモリコントロール方法
CA2918136A1 (en) High sum-rate write-once memory
US11271589B2 (en) Memory system with error-reduction scheme for decoding and method of operating such memory system
US20190286522A1 (en) Ldpc decoding device, memory system including the same and method thereof
CN104681095A (zh) 储存装置及其操作方法
US10073685B2 (en) Methods of system optimization by over-sampling read
US12174699B2 (en) Selective decoding for super chip-kill recovery and method of operating such memory system
US11973515B2 (en) Hybrid precision MS decoder to reduce gate-count for long codes
TWI798017B (zh) 編碼控制方法、記憶體儲存裝置及記憶體控制電路單元
KR20170067656A (ko) Nand 플래시용 터보 프로덕트 코드
CN108073469A (zh) 用于通用产品代码的数据映射方案

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
C14 Grant of patent or utility model
GR01 Patent grant
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20151216

Termination date: 20201216

CF01 Termination of patent right due to non-payment of annual fee