协同使用纠删码和纠错码的可靠闪存存储系统构建方法

协同使用纠删码和纠错码的可靠闪存存储系统构建方法
【技术领域】
[0001] 本发明设及计算机存储系统领域，具体设及一种协同使用纠删码和纠错码的可靠 闪存存储系统构建方法。
【背景技术】
[0002] 闪存因为其优越的性能而被广泛部署在大规模存储系统中，但是，其有限的寿命 在一定程度上阻碍了闪存在写密集型负载下的推广。闪存的寿命是指每个存储单元能够承 受的擦写次数。厂商在推出一款闪存巧片时，会给出该款巧片对应的标称寿命。若每个存 储单元的擦写次数在标称寿命W内，闪存的位错误率较低，保存在闪存上的数据被认为是 可靠的。实际上，在擦写次数超过标称寿命后的很大范围内，闪存仍然可W保存数据，只是 位错误率逐步变大，可能出现数据丢失现象。但是，随着擦写次数的进一步增加，位错误率 成指数增长，最终导致闪存不可用。根据W上所述的闪存位错误率增长趋势可知，在位错误 率随擦写次数的增加成指数增长之前，闪存仍然是可用的；若采用适当的手段纠正闪存中 出现的位错误，即使每个存储单元的擦写次数超过标称寿命，保存在闪存中的数据仍然是 可靠的。
[0003] ECC巧rrorCorrectionCode,纠错码）是存储设备中一种常用的容错机制。存储 设备向存储介质中写入一页用户数据时，同时为该页数据生成若干位的纠错码。纠错码与 用户数据一同保存在存储介质中。响应上层应用的读请求时，存储设备将上层应用请求的 用户数据W及对应的纠错码同时从存储介质中取出，并利用纠错码检测和纠正用户数据中 出现的位错误，从而保证用户数据完整可靠。纠错码的特点是空间开销很低，它利用十余位 信息即可保证数百字节的数据完整可靠。但其纠错能力有限，仅适用于出错几率较低的场 景。当闪存每个存储单元的擦写次数在标称寿命W内时，位出错率较低，纠错码能够保证数 据可靠。若擦写次数超过标称寿命，位出错率不断上升，纠错码必须采用更多的校验位、并 辅W复杂的计算才能纠正用户数据中出现的位错误。纠错码计算在10关键路径上，过大的 计算开销会严重影响10性能。所W，当闪存实际使用寿命超过标称寿命时，简单利用纠错 码并不能W很低的计算开销保证闪存存储系统的可靠性。
[0004] 纠删码巧rasureCode)是一种常用于系统级的容错机制，它主要通过保存大量的 冗余数据保证数据可靠性。对于抽象为（n，k)二元组的纠删码，当响应上层应用的写请求 时，它根据n份用户数据生成k份冗余数据，该n+k份数据大小一致，被同时写到存储系统 中。响应上层应用的读请求时，只要该n+k份数据中有n份仍然完整可靠，即可正确恢复出 所有用户数据。纠删码的特点是容错能力强，其容错能力随k值的增加而增长，适用于位出 错率较高的场景。当闪存每个存储单元的擦写次数超过标称寿命时，尽管位错误率较高，只 要纠删码选择足够大的k值，即可保证闪存上的数据完整可靠，但会引入一定的计算开销 和空间开销。
[0005] 综合比较W上所述的两种容错机制可知；纠错码只适用于错误率较低的场景，当 错误率较高时，纠错码的计算开销显著增加，甚至无法保证数据的正确性；纠删码适用于错 误率较高的场景，它能够w强大的容错能力纠正数据中出现的大量位错误，且计算开销恒 定，但当位错误较少时，纠删码的计算开销高于纠错码。独立使用W上两种机制很难在保证 10性能的同时将闪存的寿命延长到厂商标称寿命W外。因此，如何实现纠错码和纠删码的 协同使用，W避免对性能产生不利影响为前提，实现当闪存实际使用寿命超过标称寿命时 保障保存在闪存存储系统中的数据的可靠性，延长闪存的实际使用寿命，已成为亟待解决 的技术问题。

【发明内容】

[0006] 本发明要解决的技术问题是：针对现有技术的上述问题，提供一种计算开销低、10 速度快、实现当闪存实际使用寿命超过标称寿命时保障保存在闪存存储系统中的数据的可 靠性、闪存寿命延长效果显著的协同使用纠删码和纠错码的可靠闪存存储系统构建方法。
[0007] 为了解决上述技术问题，本发明采用的技术方案为：
[0008] -种协同使用纠删码和纠错码的可靠闪存存储系统构建方法，步骤包括：
[0009] 1)初始化接收10请求的缓冲区；
[0010] 2)接收10请求R，判定10请求R的读写类型，若读写类型为写请求，则跳转执行 步骤3);否则若读写类型为读请求，则跳转执行步骤4);
[0011] 3)将10请求R的写数据按照条带为单位进行选取，将选取的每一个条带的S个 用户数据页面采用纠删码生成k个冗余数据页面，分别计算所述S个用户数据页面和k个 冗余数据页面组成的s+k个页面的校验和、纠错码，并将所述s+k个页面及各个页面的校验 和、纠错码一同写入存储设备；
[0012] 4)将10请求R划分为分别属于不同条带的子请求，针对每一个子请求，读取子请 求的各个页面及其校验和、纠错码，计算各个页面的校验和并识别各个页面的位错误，找出 位错误最多的页面，判断位错误最多的页面的位错误数量是否大于所使用的纠错码能够纠 正的最大错误位数T，如果位错误最多的页面的位错误数量不大于所使用的纠错码能够纠 正的最大错误位数T，则使用纠错码纠正子请求中各个页面中出现的位错误；如果位错误 最多的页面的位错误数量大于所使用的纠错码能够纠正的最大错误位数T，则使用纠删码 纠正子请求中各个页面中出现的位错误，返回子请求各个页面所包含的数据。
[0013] 优选地，所述步骤1)还包括初始化用于记录待写入存储设备的页面总数的写请 求计数器Count，为0的步骤，所述步骤3)的详细步骤包括：
[0014] 3. 1)将写请求R包含的页面数累加到写请求计数器Count，中；
[0015] 3. 2)判断写请求计数器Count,是否超过预设的阔值h，其中h为大于一个完整条 带中包含的页面数量n的整数；如果写请求计数器Count，超过预设的阔值h，则跳转执行步 骤3.3);如果写请求计数器Count，不超过预设的阔值h，则跳转执行步骤2);
[0016] 3.3)根据页面编号为待写入的Count，个写数据页面作升序排序，将待写入的 Count，个写数据页面划分到不同的条带中，使得编号为X的页面被划分到第x/n个条带中， 其中n表示一个完整条带中包含的页面数量；从待写入的Count，个写数据页面中选取一个 完整条带，如果选取完整条带成功，则跳转执行步骤3. 4);否则如果选取完整条带不成功， 则选取包含用户数据页面最多的有一个不完整条带，跳转执行步骤3. 4);
[0017] 3. 4)将选取的完整条带或不完整条带中的S个用户数据页面采用纠删码生成k个 冗余页面共得到s+k个页面，分别计算所述s+k个页面中各个页面的校验和、纠错码，将所 述s+k个页面及所述s+k个页面中各个页面的纠错码和校验和一同写入存储设备；最终从 写请求计数器Count，中减去本次写入存储设备的用户数据页面数量S，跳转步骤3. 2)。
[001引优选地，所述步骤3. 2)中的阔值h为一个完整条带中包含的页面数量n的10倍。
[0019] 优选地，所述步骤3. 3)的详细步骤包括：
[0020] 3. 3. 1)从待写入的写请求计数器Count，个写数据页面中选取一个完整条带，如果 选取完整条带成功，则跳转执行步骤3. 4);否则如果选取完整条带不成功，则跳转执行步 骤 3. 3. 2);
[0021] 3. 3. 2)判断10请求R是否为连续的写请求，如果10请求R为连续的写请求，则跳 转执行步骤2);否则如果10请求R并非连续的写请求，则跳转执行步骤3.3.3);
[0022] 3. 3. 3)选取包含用户数据页面最多的有一个不完整条带，跳转执行步骤3. 4)。
[0023] 优选地，所述步骤3. 4)中将所述s+k个页面及所述s+k个页面中各个页面的纠错 码和校验和一同写入存储设备时，存储设备为所述s+k个页面中每个待写入的页面分配一 个空闲的物理页面，所述s+k个页面中每一个页面的数据被写入分配的物理页面的数据区 域，所述s+k个页面中每一个页面的纠错码和校验和被写入分配的物理页面的额外区域。
[0024] 优选地，所述步骤3. 4)中分别计算所述s+k个页面中各个页面的校验和具体是指 将待计算页面中的比特流划分为固定大小的字Word,每个字Word包含64个比特，然后将该 些字Word作异或计算得到的结果作为该页面的校验和。
[00巧]优选地，所述步骤4)的详细步骤包括：
[0026] 4. 1)将10请求R划分为分别属于不同条带的m个子请求；
[0027] 4. 2)初始化设置子请求计数器i为0;
[0028] 4.3)读取子请求而所包含的各个页面，一同读取各个页面对应的纠错码和校验 和；
[0029] 4. 4)计算子请求Ri所包含的各个页面的校验和，根据计算得到的校验和和步骤 4. 3)中读取得到的校验和进行比较识别子请求而所包含的各个页面中的位错误；
[0030] 4. 5)找出子请求而所包含的各个页面中错误位最多的页面，将所述错误位最多的 页面的错误位数和所采用的纠错码能够纠正的最大错误位数T进行比较，如果位错误最多 的页面的位错误数量不大于所使用的纠错码能够纠正的最大错误位数T，则跳转执行步骤 4. 6);否则如果位错误最多的页面的位错误数量大于所使用的纠错码能够纠正的最大错误 位数T，则跳转步骤4. 7);
[003。4.6)使用纠错码纠正子请求R冲各个页面的位错误，如果纠正失败，则跳转执行 步骤4.7);否则如果纠正成功，则跳转执行步骤4.8);
[0032] 4. 7)利用纠删码纠正子请求而中各个页面的位错误；
[0033] 4. 8)向上层应用返回子请求而所包含的用户数据；
[0034] 4. 9)增加子请求计数器i;
[00巧]4. 10)若子请求计数器i小于子请求拆分数量m，则判定还有未处理完的子请求， 跳转执行步骤4. 3);若子请求计数器i等于子请求拆分数量m，则判定已经处理完所有的子 请求，跳转执行步骤2)。
[0036]优选地，所述步骤4. 1)中将10请求R划分为分别属于不同条带的m个子请求时， m的值为（OffsetK+SizeK+n-l)/n-〇ffsetK/n，其中n表示一个完整条带中包含的用户数据 页数，Offset康示10请求R的起始地址，SizeK表示10请求R包含的页面数，10请求R由 W起始地址Offset,开始的SizeC个连续页面组成；所述m个子请求中第i个子请求Ri包 含的页面如式（1)所示；
[0037]
[0038] 式（1)中，而表示第i个子请求，n表示一个完整条带中的页面数量，Offset,表示 10请求R的起始地址，Size^表示10请求R包含的页面数。
[0039] 优选地，所述步骤4. 7)的详细步骤包括：
[0040] 4. 7. 1)初始化数据恢复次数计数器为0;在子请求而中属于同一条带的V个页面 已经被读取的基础上，从存储设备读取n-v份数据，共得到纠删码对所述条带作数据恢复 时至少需要的n份数据；
[0041] 4. 7. 2)根据读取出来的共n份数据通过纠删码纠正子请求Ri中各个页面的位错 误，若成功纠正子请求而中各个页面的位错误，则跳转执行步骤4.8);否则，将数据恢复次 数计数器加1，跳转执行步骤4. 7. 3);
[0042] 4. 7. 3)判断数据恢复次数计数器的值是否等于G'w-，如果数据恢复次数计数器的 值小于，側读取纠删码对所述条带作数据恢复时至少需要的另外n份数据，跳转执行 步骤4. 7. 2);否则如果数据恢复次数计数器的值等于，则判定利用纠删码纠正子请求 而中各个页面的位错误失败。
[0043] 本发明协同使用纠删码和纠错码的可靠闪存存储系统构建方法具有下述优点：
[0044] 1、本发明针对闪存寿命有限、位错误率随擦写次数的增多而逐步增长的问题，利 用纠删码纠正闪存中出现的位错误，从而将闪存的实际使用寿命延长到厂商标称寿命W 夕K由于纠删码具有很强的纠错能力，本发明能够将闪存寿命延长数十倍，具有寿命延长效 果好的优点，能够显著提高闪存存储系统的可靠性。
[0045] 2、本发明针对当闪存每个存储单元的平均擦写次数较少、位错误率还比较低时， 利用纠删码纠正闪存中出现的位错误计算开销相对较大。为了降低计算开销，本发明首先 采用校验和对闪存页面中出现的位错误作预判。当校验和判定的位错误较少时，采用纠错 码纠正页面中出现的位错误。纠错码纠错能力相对较弱，只适用于位错误率较低的情况，但 其计算开销较低，不会对10性能产生显著的影响。由于灵活采用纠删码和纠错码，本发明 既能显著延长闪存的寿命，又具有计算开销低的优点。
[0046] 3、本发明的计算开销较低，不会对10性能产生显著的负面影响。用纠删码作数据 恢复时，充分发挥闪存的高并发性，将数据恢复设及的读请求调度到多个并发通道上，具有 10性能好的优点。
【附图说明】
[0047] 图1为本发明实施例的基本实施流程示意图。
[0048] 图2为本发明实施例的详细实施流程示意图。
【具体实施方式】
[0049] 如图1所示，本实施例协协同使用纠删码和纠错码的可靠闪存存储系统构建方法 的步骤包括：
[0050] 1)初始化接收10请求的缓冲区；初始化接收10请求的缓冲区即为在内存中申请 一片区域，用W保存上层应用发送的读写请求；
[0051] 2)接收10请求R，判定10请求R的读写类型，若读写类型为写请求，则跳转执行 步骤3);否则若读写类型为读请求，则跳转执行步骤4);
[0052] 3)将10请求R的写数据按照条带为单位进行选取，将选取的每一个条带的S个用 户数据页面采用纠删码生成k个冗余数据页面，分别计算S个用户数据页面和k个冗余数 据页面组成的s+k个页面的校验和、纠错码，并将s+k个页面及各个页面的校验和、纠错码 一同写入存储设备（即闪存存储系统）；
[005引4)将10请求R划分为分别属于不同条带的子请求，针对每一个子请求，读取子请 求的各个页面及其校验和、纠错码，计算各个页面的校验和并识别各个页面的位错误，找出 位错误最多的页面，判断位错误最多的页面的位错误数量是否大于所使用的纠错码能够纠 正的最大错误位数T，如果位错误最多的页面的位错误数量不大于所使用的纠错码能够纠 正的最大错误位数T，则使用纠错码纠正子请求中各个页面中出现的位错误；如果位错误 最多的页面的位错误数量大于所使用的纠错码能够纠正的最大错误位数T，则使用纠删码 纠正子请求中各个页面中出现的位错误，返回子请求各个页面所包含的数据。
[0054] 10请求R可标识为（TypeK，OffsetK，SizeK)，其中Typeu表示10请求R的读写类型， Offset^表示10请求R的起始地址，SizeK表示10请求R包含的页面数；因此，本实施例步 骤2)判定10请求R的读写类型即为判断读写类型Type。的值类型。本实施例旨在利用容 错机制，协同使用纠错码和纠删码纠正闪存中出现的位错误，首先通过校验和技术（化eck Sum)初步统计数据中的位错误，在位错误率较低时使用纠错码校正错误，避免对性能产生 不利影响；在位错误较高时，采用纠删码校正错误，能够实现当闪存实际使用寿命超过标称 寿命时保障保存在闪存存储系统中的数据的可靠性，具有计算开销低、10速度快、闪存寿命 延长效果显著的优点。
[00巧]如图2所示，本实施例步骤1)还包括初始化用于记录待写入存储设备的页面总数 的写请求计数器Count，为0的步骤，Count，表示还未写入存储设备的页面总数，本实施例 步骤3)的详细步骤包括：
[0056] 3. 1)将写请求R包含的页面数累加到写请求计数器Count，中；
[0057] 3. 2)判断写请求计数器Count，是否超过预设的阔值h，其中h为大于一个完整条 带中包含的页面数量n的整数；如果写请求计数器Count，超过预设的阔值h，则跳转执行步 骤3.3);如果写请求计数器Count，不超过预设的阔值h，则跳转执行步骤2);
[0058] 3. 3)根据页面编号为待写入的Count,(表示写请求计数器Count,的值，下同）个 写数据页面作升序排序，将待写入的Count，个写数据页面划分到不同的条带中，使得编号 为X的页面被划分到第x/n个条带中，其中n表示一个完整条带中包含的页面数量；从待写 入的Count，个写数据页面中选取一个完整条带，如果选取完整条带成功，则跳转执行步骤 3. 4);否则如果选取完整条带不成功，则选取包含用户数据页面最多的有一个不完整条带， 跳转执行步骤3. 4);
[0059] 3. 4)将选取的完整条带或不完整条带中的S个用户数据页面采用纠删码生成k个 冗余页面共得到s+k个页面，分别计算s+k个页面中各个页面的校验和、纠错码，将s+k个 页面及s+k个页面中各个页面的纠错码和校验和一同写入存储设备；最终从写请求计数器 Count，中减去本次写入存储设备的用户数据页面数量S，跳转步骤3. 2)。
[0060] 纠删码可抽象为一个（n，k)二元组，表示纠删码根据n份用户数据生成k份校验 信息。该n+k份数据组成一个条带，一同写到底层的存储设备中。在采用纠删码的存储系 统中，每次写入操作都设及一个包含n+k个页面的条带，而不是简单写入一个页面。所W， 向存储设备中写入数据时，应该尽可能等到一个条带的所有数据都到达后，再向存储系统 发出写请求。本实施例中通过写请求计数器Count，则用来累积页面，每当通过写请求计数 器Count，记录的待写入存储设备的数据达到h个页面时，即可将部分数据写入存储设备 中；若待写入存储设备的页面总数Count，不超过h，则跳转执行步骤2)继续接受新的读写 请求，直到待写入存储设备的数据达到h个页面，从而W便纠删码力图从累积的页面中找 到完整的条带，从而W减少对闪存的写损耗，延长存储设备的使用寿命。
[0061] 本实施例中，步骤3. 2)中的阔值h为一个完整条带中包含的页面数量n的10倍。
[0062] 本实施例中，步骤3. 3)的详细步骤包括：
[0063] 3. 3. 1)从待写入的写请求计数器Count，个写数据页面中选取一个完整条带，如果 选取完整条带成功，则跳转执行步骤3. 4);否则如果选取完整条带不成功，则跳转执行步 骤 3. 3. 2);
[0064] 3. 3. 2)判断10请求R是否为连续的写请求，如果10请求R为连续的写请求，则跳 转执行步骤2);否则如果10请求R并非连续的写请求，则跳转执行步骤3.3.3);
[0065] 3. 3. 3)选取包含用户数据页面最多的有一个不完整条带，跳转执行步骤3. 4 )。
[0066]通过上述步骤3. 3. 1)~3. 3. 3)，能够尽可能避免一个条带中由于部分用户页面 的更新导致所有校验数据的更新，实现针对连续的写请求的优化，确保在面对连续的写请 求时，若当前没有找到完整条带，则跳转执行步骤2)继续接受后续的连续的写请求，直到 待写入存储设备的数据中存在完整条带或者后续为非连续的写请求，从而能够进一步减少 对闪存的写损耗，延长存储设备的使用寿命。
[0067] 本实施例中，步骤3. 4)将选取的完整条带或不完整条带中的S个用户数据页面采 用纠删码生成k个冗余页面共得到s+k个页面时；对于选取的完整条带而言，其中的用户数 据页面数量S即为完整条带中的页面数量n;对于选取的不完整条带而言，其中的用户数据 页面数量S小于为前述完整条带中的页面数量n。但是，不论选取的完整条带或不完整条 带，假定该条带中有S个用户页面待写入存储设备，则根据该S个页面生成k份新的校验信 息化个页面），从而共得到s+k个页面。
[0068] 闪存的物理页面包含两部分：保存数据的数据区域和保存元数据的额外区域。本 实施例中，步骤3. 4)中将s+k个页面及s+k个页面中各个页面的纠错码和校验和一同写入 存储设备时，存储设备为s+k个页面中每个待写入的页面分配一个空闲的物理页面，s+k个 页面中每一个页面的数据被写入分配的物理页面的数据区域，s+k个页面中每一个页面的 纠错码和校验和被写入分配的物理页面的额外区域。假定存储设备为待写入的数据页面 化gGdat。分配的物理页面为化gephysieal，则化ge<kt。对应的数据写到化gephysieal的数据区域， Paged。,。的纠错码和校验和写到化gephy,ied的额外区域。本实施例基于额外区域来存储页面 的纠错码和校验和，从而能够在不改变存储设备的存储结构的前提下，实现对页面的纠错 码和校验和的存储，从而为后续基于纠错码和纠删码提供基础信息。
[0069] 本实施例中，步骤3. 4)中分别计算s+k个页面中各个页面的校验和具体是指将待 计算页面中的比特流划分为固定大小的字Word,每个字Word包含64个比特，然后将该些字 Word作异或计算得到的结果作为该页面的校验和。毫无疑问，步骤4)中计算各个页面的校 验和的方法与步骤3. 4)中分别计算s+k个页面中各个页面的校验和的方法完全相同。需 要说明的是，校验和技术（化eckSum)是目前比较常见的校验技术，例如还可W根据需要采 用目前各类常见的校验和算法，而本实施例采用的校验和算法基于异或计算，计算开销小。
[0070] 如图2所示，本实施例中步骤4)的详细步骤包括：
[ocm] 4. 1)将10请求R划分为分别属于不同条带的m个子请求R。，Ri，R2…Rm_i;纠删码W条带为基本单位保证数据的可靠性，对于被抽象为（n，k)二元组的纠删码，一个条带包 含n+k页数据。响应上层应用的读请求时，纠删码首先需要找到上层应用请求的数据所在 的条带，该些数据可能分布在多个条带中。对于本实施例，m个子请求R。，Ri，R,…Rm_i共同 组成了用户请求的所有数据，但它们属于不同的条带，纠删码将依次读取该些条带，并从中 找出用户请求的数据；m个子请求中第i个子请求而包含的页面如公式（1)所示；
[0072]
[007引式（1)中，R康示第i个子请求，n表示一个完整条带中的页面数量，Offset康示 10请求R的起始地址，Size^表示10请求R包含的页面数。
[0074] 4. 2)初始化设置子请求计数器i为0;
[0075] 4.3)读取子请求而所包含的各个页面，一同读取各个页面对应的纠错码和校验 和；由于闪存及基于闪存的存储设备都存在固有的并行性，所W可并发地读取子请求Ri所 包含的各个页面，确保本实施例构建的可靠存储系统具有较高的读性能；
[0076] 4. 4)计算子请求Ri所包含的各个页面的校验和，根据计算得到的校验和和步骤 4. 3)中读取得到的校验和进行比较识别子请求Ri所包含的各个页面中的位错误；本实施 例中，和前述步骤3. 4)中分别计算s+k个页面中各个页面的校验和的步骤相同，样也是指 将待计算页面中的比特流划分为固定大小的字Word,每个字Word包含64个比特，然后将该 些字Word作异或计算得到的结果作为该页面的校验和；将计算结果与步骤4. 3)中读取得 到的校验和作异或运算，两种校验和的差异位数被标识为BEj.，BEj.可近似认为是该页面中 出现的位错误数；
[0077] 4. 5)找出子请求而所包含的各个页面中错误位最多的页面，将错误位最多的页 面的错误位数和所采用的纠错码能够纠正的最大错误位数T进行比较，如果位错误最多的 页面的位错误数量不大于所使用的纠错码能够纠正的最大错误位数T(说明子请求而中各 个页面的位错误率较低，仅采用纠错码即可校正各页面中出现的位错误），则跳转执行步骤 4.6);否则如果位错误最多的页面的位错误数量大于所使用的纠错码能够纠正的最大错 误位数T(说明子请求Ri中各个页面的位错误率较高，出现的错误位数超过了纠错码的纠 错能力，纠错码就不能成功恢复用户数据，因此需要采用纠删码纠正各页面中出现的位错 误），则跳转步骤4.7);其中，错误位最多的页面的错误位数可W表示为式（2)所示；
[0078]
(2)
[007引式似中，P表示子请求Ri的总页面数，邸j.表示子请求R冲的第j个页面中两种 校验和的差异位数；
[0080] 4.6)使用纠错码纠正子请求R冲各个页面的位错误，如果纠正失败，则跳转执行 步骤4. 7);否则如果纠正成功，则跳转执行步骤4. 8);实际上，校验和检测到的位错误可能 少于页面中实际出现的位错误，因此若页面中实际出现的位错误已经超过了纠错码的纠错 能力，纠错码就不能成功恢复用户数据，此时，跳转执行步骤4. 7)利用纠删码校正页面中 的位错误；若纠错码成功纠正Ri中所有页面的位错误，则跳转执行步骤4. 8)，从而能够提 高本实施例的位错误纠正能力；
[0081] 4. 7)利用纠删码纠正子请求而中各个页面的位错误；
[0082] 4. 8)向上层应用返回子请求而所包含的用户数据；
[0083] 4. 9)增加子请求计数器i;
[0084] 4. 10)若子请求计数器i小于子请求拆分数量m，则判定还有未处理完的子请求， 跳转执行步骤4. 3);若子请求计数器i等于子请求拆分数量m，则判定已经处理完所有的子 请求，跳转执行步骤2)。
[0085] 本实施例中，步骤4. 1)中将10请求R划分为分别属于不同条带的m个子请求时， m的值为（OffsetK+SizeK+n-l)/n-〇ffsetK/n，其中n表示一个完整条带中包含的用户数据 页数，Offset康示10请求R的起始地址，SizeK表示10请求R包含的页面数，10请求R由 W起始地址Offsetu开始的SizeK个连续页面组成。读请求R由WOffsetK为起始地址的 Size,个连续页面组成，该些用户数据页面可能分布在不同的条带中。由于每个条带包含 n页用户数据，则编号为1的用户数据页面包含在第1/n个条带中。通过W上计算方式，可 将R的所有用户数据页面划分到m个不同的条带中。其中，m的值为（Offsetc+Sizec+n-1)/ n-Offseti/n。落入到m个不同条带中的子请求分别被标识为R。，Ri,R2,…，Rm_i。
[0086] 本实施例中，步骤4. 7)的详细步骤包括；
[0087] 4. 7. 1)初始化数据恢复次数计数器为0;在子请求而中属于同一条带的V个页面 已经被读取的基础上，从存储设备读取n-v份数据，共得到纠删码对条带作数据恢复时至 少需要的n份数据；
[008引 4. 7. 2)根据读取出来的共n份数据通过纠删码纠正子请求R冲各个页面的位错 误，若成功纠正子请求而中各个页面的位错误，则跳转执行步骤4.8);否则，将数据恢复次 数计数器加1，跳转执行步骤4. 7. 3);
[0089] 4. 7. 3)判断数据恢复次数计数器的值是否等于如果数据恢复次数计数器的 值小于cr+A，则读取纠删码对条带作数据恢复时至少需要的另外n份数据，跳转执行步骤 4. 7. 2);否则如果数据恢复次数计数器的值等于GVt，则判定利用纠删码纠正子请求而中 各个页面的位错误失败。
[0090] 对于采用纠删码的存储系统而言，响应上层应用的读请求时，只要该n+k份数据 中有n份仍然完整可靠，即可正确恢复出所有用户数据。本实施例基于前述步骤4. 7. 1)~ 4. 7. 3)，确保能够基于n+k份数据中完整、正确、可靠的n份数据来实现对位错误的纠错。
[0091] 综上所述，本实施例联合使用纠删码和纠错码恢复闪存页面中出现的位错误，从 而达到显著延长闪存寿命、提高闪存存储系统可靠性的目的。上层应用发出写请求时，为待 写页面计算纠删码的冗余信息，并计算每个页面的纠错码和校验和，将纠删码冗余信息、纠 错码、校验和一同保存在存储设备上。上层应用读取数据时，先利用校验和初步判定页面中 出现的位错误数。若位错误较少，则用纠错码校正数据；若位错误较多，则采用纠删码恢复 数据。W上所述方法在保证强大纠错能力的同时，尽可能采用计算开销较低的方法校正用 户数据中出现的位错误，具有计算开销低、10性能好的优点。由于纠删码具有强大的纠错 能力，当闪存每个存储单元擦写次 数很多、出错率很高时，纠删码仍然能够成功恢复用户数 据中出现的位错误。所W本实施例能够显著增加闪存每个存储单元所能承受的擦写次数， 具有寿命延长效果好的优点。
[0092] W上所述仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施 例，凡属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域 的普通技术人员来说，在不脱离本发明原理前提下的若干改进和润饰，该些改进和润饰也 应视为本发明的保护范围。
【主权项】
1. 一种协同使用纠删码和纠错码的可靠闪存存储系统构建方法，其特征在于步骤包 括： 1) 初始化接收IO请求的缓冲区； 2) 接收IO请求R，判定IO请求R的读写类型，若读写类型为写请求，则跳转执行步骤 3);否则若读写类型为读请求，则跳转执行步骤4); 3) 将IO请求R的写数据按照条带为单位进行选取，将选取的每一个条带的s个用户数 据页面采用纠删码生成k个冗余数据页面，分别计算所述s个用户数据页面和k个冗余数 据页面组成的s+k个页面的校验和、纠错码，并将所述s+k个页面及各个页面的校验和、纠 错码一同写入存储设备； 4) 将IO请求R划分为分别属于不同条带的子请求，针对每一个子请求，读取子请求的 各个页面及其校验和、纠错码，计算各个页面的校验和并识别各个页面的位错误，找出位错 误最多的页面，判断位错误最多的页面的位错误数量是否大于所使用的纠错码能够纠正的 最大错误位数T，如果位错误最多的页面的位错误数量不大于所使用的纠错码能够纠正的 最大错误位数T，则使用纠错码纠正子请求中各个页面中出现的位错误；如果位错误最多 的页面的位错误数量大于所使用的纠错码能够纠正的最大错误位数T，则使用纠删码纠正 子请求中各个页面中出现的位错误，返回子请求各个页面所包含的数据。2. 根据权利要求1所述的协同使用纠删码和纠错码的可靠闪存存储系统构建方法，其 特征在于，所述步骤1)还包括初始化用于记录待写入存储设备的页面总数的写请求计数 器Count wS 0的步骤，所述步骤3)的详细步骤包括： 3. 1)将写请求R包含的页面数累加到写请求计数器Countw中； 3. 2)判断写请求计数器Countw是否超过预设的阈值h，其中h为大于一个完整条带中 包含的页面数量η的整数；如果写请求计数器Count w?过预设的阈值h，则跳转执行步骤 3.3);如果写请求计数器Countw不超过预设的阈值h，则跳转执行步骤2); 3. 3)根据页面编号为待写入的Countw个写数据页面作升序排序，将待写入的Count w 个写数据页面划分到不同的条带中，使得编号为x的页面被划分到第x/n个条带中，其中η 表示一个完整条带中包含的页面数量；从待写入的Count w个写数据页面中选取一个完整条 带，如果选取完整条带成功，则跳转执行步骤3. 4);否则如果选取完整条带不成功，则选取 包含用户数据页面最多的有一个不完整条带，跳转执行步骤3. 4); 3. 4)将选取的完整条带或不完整条带中的s个用户数据页面采用纠删码生成k个冗余 页面共得到s+k个页面，分别计算所述s+k个页面中各个页面的校验和、纠错码，将所述s+k 个页面及所述s+k个页面中各个页面的纠错码和校验和一同写入存储设备；最终从写请求 计数器Count w中减去本次写入存储设备的用户数据页面数量s，跳转步骤3. 2)。3. 根据权利要求2所述的协同使用纠删码和纠错码的可靠闪存存储系统构建方法，其 特征在于：所述步骤3. 2)中的阈值h为一个完整条带中包含的页面数量η的10倍。4. 根据权利要求3所述的协同使用纠删码和纠错码的可靠闪存存储系统构建方法，其 特征在于，所述步骤3. 3)的详细步骤包括： 3.3. 1)从待写入的写请求计数器Countw个写数据页面中选取一个完整条带，如果选 取完整条带成功，则跳转执行步骤3. 4);否则如果选取完整条带不成功，则跳转执行步骤 3. 3. 2)； 3. 3. 2)判断IO请求R是否为连续的写请求，如果IO请求R为连续的写请求，则跳转执 行步骤2);否则如果IO请求R并非连续的写请求，则跳转执行步骤3.3.3); 3. 3. 3)选取包含用户数据页面最多的有一个不完整条带，跳转执行步骤3. 4)。5. 根据权利要求4所述的协同使用纠删码和纠错码的可靠闪存存储系统构建方法，其 特征在于：所述步骤3. 4)中将所述s+k个页面及所述s+k个页面中各个页面的纠错码和校 验和一同写入存储设备时，存储设备为所述s+k个页面中每个待写入的页面分配一个空闲 的物理页面，所述s+k个页面中每一个页面的数据被写入分配的物理页面的数据区域，所 述s+k个页面中每一个页面的纠错码和校验和被写入分配的物理页面的额外区域。6. 根据权利要求5所述的协同使用纠删码和纠错码的可靠闪存存储系统构建方法，其 特征在于：所述步骤3. 4)中分别计算所述s+k个页面中各个页面的校验和具体是指将待计 算页面中的比特流划分为固定大小的字Word，每个字Word包含64个比特，然后将这些字 Word作异或计算得到的结果作为该页面的校验和。7. 根据权利要求1~6中任意一项所述的协同使用纠删码和纠错码的可靠闪存存储系 统构建方法，其特征在于，所述步骤4)的详细步骤包括： 4. 1)将IO请求R划分为分别属于不同条带的m个子请求； 4. 2)初始化设置子请求计数器i为0 ; 4.3)读取子请求Ri所包含的各个页面，一同读取各个页面对应的纠错码和校验和； 4. 4)计算子请求Ri所包含的各个页面的校验和，根据计算得到的校验和和步骤4. 3) 中读取得到的校验和进行比较识别子请求Ri所包含的各个页面中的位错误； 4. 5)找出子请求Ri所包含的各个页面中错误位最多的页面，将所述错误位最多的页 面的错误位数和所采用的纠错码能够纠正的最大错误位数T进行比较，如果位错误最多 的页面的位错误数量不大于所使用的纠错码能够纠正的最大错误位数T，则跳转执行步骤 4. 6);否则如果位错误最多的页面的位错误数量大于所使用的纠错码能够纠正的最大错误 位数T，则跳转步骤4. 7); 4. 6)使用纠错码纠正子请求Ri中各个页面的位错误，如果纠正失败，则跳转执行步骤 4.7);否则如果纠正成功，则跳转执行步骤4.8); 4. 7)利用纠删码纠正子请求氏中各个页面的位错误； 4.8)向上层应用返回子请求Ri所包含的用户数据； 4. 9)增加子请求计数器i ; 4. 10)若子请求计数器i小于子请求拆分数量m，则判定还有未处理完的子请求，跳转 执行步骤4. 3);若子请求计数器i等于子请求拆分数量m，则判定已经处理完所有的子请 求，跳转执行步骤2)。8. 根据权利要求7所述的协同使用纠删码和纠错码的可靠闪存存储系统构建方法，其 特征在于：所述步骤4. 1)中将IO请求R划分为分别属于不同条带的m个子请求时，m的值 为（0ffsetK+SizeK+n-l)/n-0ffset K/n，其中η表示一个完整条带中包含的用户数据页数， 0ffsetK表示IO请求R的起始地址，Size κ表示IO请求R包含的页面数，IO请求R由以起 始地址Offset,开始的Size κ个连续页面组成；所述m个子请求中第i个子请求R ,包含的 页面如式（1)所示；式（1)中，Ri表示第i个子请求，η表示一个完整条带中的页面数量，Offset ,表示IO 请求R的起始地址，SizeK表示IO请求R包含的页面数。9.根据权利要求8所述的协同使用纠删码和纠错码的可靠闪存存储系统构建方法，其 特征在于，所述步骤4. 7)的详细步骤包括： 4. 7. 1)初始化数据恢复次数计数器为0 ;在子请求Ri中属于同一条带的V个页面已经 被读取的基础上，从存储设备读取n-v份数据，共得到纠删码对所述条带作数据恢复时至 少需要的η份数据； 4. 7. 2)根据读取出来的共η份数据通过纠删码纠正子请求氏中各个页面的位错误，若 成功纠正子请求Ri中各个页面的位错误，则跳转执行步骤4. 8);否则，将数据恢复次数计 数器加1，跳转执行步骤4.7.3); 4. 7. 3)判断数据恢复次数计数器的值是否等于，如果数据恢复次数计数器的值小 于?。，则读取纠删码对所述条带作数据恢复时至少需要的另外η份数据，跳转执行步骤 4. 7. 2);否则如果数据恢复次数计数器的值等于，则判定利用纠删码纠正子请求氏中 各个页面的位错误失败。
【专利摘要】本发明公开了一种协同使用纠删码和纠错码的可靠闪存存储系统构建方法，步骤包括：接收IO请求R，判定读写类型；针对写请求，将每一个条带的s个用户数据页面采用纠删码生成共计待写入的s+k个页面，连同各页面的校验和、纠错码一同写入存储设备；针对读请求划分为属于不同条带的子请求，针对每一个子请求，读取各页面及其校验和、纠错码，计算各页面的校验和并识别位错误，找出位错误最多的页面，如果该页面的位错误数量不大于所使用的纠错码能够纠正的最大错误位数T，则使用纠错码纠正子请求中的位错误，否则使用纠删码纠正子请求中的位错误，返回子请求的数据。本发明具有计算开销低、IO速度快、闪存寿命延长效果显著的优点。
【IPC分类】G06F12/08, H03M13/35
【公开号】CN104881370
【申请号】CN201510236451
【发明人】肖侬, 陈志广, 卢宇彤, 周恩强, 张伟, 董勇
【申请人】中国人民解放军国防科学技术大学
【公开日】2015年9月2日
【申请日】2015年5月11日