用于处理可变大小数据的高效且动态大小反向映射

摘要

一种系统，所述系统包括处理器以及存储指令的存储器，所述指令当被执行时使得所述系统：接收数据流，所述数据流包括一个或多个数据块；确定所述一个或多个数据块的大小；基于数据块的大小和物理块的大小，确定所述物理块所需的映射数量，其中，根据存储在所述物理块中的所述一个或多个数据块的所述大小，所述映射数量针对不同物理块是可变的；检索动态大小反向映射，所述动态大小反向映射是动态树结构；确定在所述动态大小反向映射中用于所述一个或多个数据块的映射的起始位置；并且在所述动态大小反向映射中针对所述物理块创建条目。

说明书

背景技术

本公开涉及管理存储设备中的数据块集合。具体地，本公开描述了一种用于存储应用的可变大小反向映射。更具体地，本公开涉及一种用于处理可变大小数据的高效且动态大小反向映射。

许多存储设备系统使用跟踪最新逻辑-物理媒体映射的动态转换表。随着并且在重写逻辑块时，更新转换表以指向物理媒体中的新位置，并且通过垃圾收集过程收回旧物理媒体位置。垃圾收集过程处理物理媒体中邻近范围的位置；因此，这种过程要求物理媒体-逻辑块地址的位置反向映射。

由于存储设备支持数据缩减，一个物理块能够以简化形式存储多个逻辑块。因此，物理块的大小和能够存储在存储设备中的逻辑块数量之间不存在一一对应的关系。这种系统中反向映射的大小应是动态的，并且优选地取决于工作量。例如，如果物理块大小是4096字节并以8倍压缩，则最小可寻址单元的大小是512字节，而仅扩展反向映射以寻址512字节块将产生8倍以上的存储器消耗。反向转换表被实施为分页转换表以限制存储器消耗，因此更大的反向映射将消耗物理媒体中更多空间。系统软件的存储器占用和垃圾收集过程的整体效率高度依赖于反向映射的实施。

发明内容

本公开涉及用于硬件高效数据管理的系统和方法。根据本公开主题的一个新颖方面，一种系统包括：动态大小反向映射，所述动态大小反向映射具有与用于因存储设备执行的压缩而不同的物理块的可变映射数量相对应的可变大小；以及处理器，耦合至所述动态大小反向映射，所述处理器被配置成用于：接收数据流，所述数据流包括一个或多个数据块；确定所述一个或多个数据块的大小；基于数据块的大小和物理块的大小，确定所述物理块所需的映射数量，其中，根据存储在所述物理块中的所述一个或多个数据块的所述大小，所述映射数量针对不同物理块是可变的；确定在所述动态大小反向映射中用于所述一个或多个数据块的映射的起始位置；以及在所述动态大小反向映射中针对所述物理块创建条目，所述条目包括所述物理块的所述映射数量以及所述一个或多个数据块的所述起始位置，所述条目是用于所述物理块的所述可变映射数量的索引。

通常，本公开中描述的主题的另一新颖方面可以通过多种方法实施，所述方法包括：接收数据流，所述数据流包括一个或多个数据块；确定所述一个或多个数据块的大小；基于所述一个或多个数据块的所述大小以及物理块的大小确定映射数量，根据存储在所述物理块中的所述一个或多个数据块的所述大小，所述映射数量针对不同物理块是可变的；检索动态大小反向映射，所述动态大小反向映射的大小与用于不同物理块的所述可变映射数量相对应；确定在所述动态大小反向映射中用于所述一个或多个数据块的映射的起始位置；以及在所述动态大小反向映射中针对所述物理块创建条目，所述条目包括所述物理块的所述映射数量以及所述一个或多个数据块的所述起始位置，所述条目是用于所述物理块的所述映射数量的索引。

一个或多个这种方面的其他实施方式包括相应系统、装置和计算机程序，所述计算机程序被配置成用于执行方法的动作并被编码在计算机存储设备上。

这些和其他实施方式均可以可选地包括一个或多个以下特征。例如，特征包括：所述动态大小反向映射包括动态树结构，所述动态树结构具有用于多个缓冲条目的可扩展节点，一个缓冲条目用于所述一个或多个数据块中每个数据块；操作包括：创建用于所述一个或多个数据块中每个数据块的缓冲条目，所述缓冲条目包括逻辑块号、物理块号、所述物理块中的起始扇区和所述物理块中占用的扇区数量；所述缓冲条目被持久化到所述存储设备中；所述物理块中占用的所述扇区数量是基于所述一个或多个数据块中每个数据块的大小以及所述扇区的大小来确定的；所述物理块的所述映射数量表示物理块消耗的缓冲条目数量；以及所述映射片段存储包含所述正向指针和所述引用数量的所述动态大小反向映射。

例如，操作进一步包括：接收将多个数据块从第一逻辑地址范围复制到第二逻辑地址范围的请求；确定所述多个数据块的大小；基于所述多个数据块的所述大小，确定所述多个数据块占用的引用数量；基于所述动态大小反向映射针对所述多个数据块确定正向指针；以及使用具有所述正向指针和所述引用数量的额外条目来更新所述动态大小反向映射。

例如，操作进一步包括：从片段报头中检索映射片段的信息；确定所述映射片段的写入块的使用计数；基于所述映射片段的所述使用计数，判定所述映射片段是否满足动态大小反向映射更新标准；响应于所述映射片段满足所述动态大小反向映射更新标准，对所述映射片段执行动态大小反向映射更新；以及更新所述片段报头中的所述映射片段的所述信息。

这些实施方式在许多方面都是特别有利的。例如，本文中所描述的技术提供了一种用于在支持数据缩减的系统中进行高效数据存储的动态大小反向映射。进一步地，所述动态大小反向映射是可扩展的并支持块复制操作。

应该理解的是，在本公开中使用的语言主要是为了可读性和指导目的而被选择的，而不是限制本文中所公开的主题的范围。

附图说明

以示例性而非限制性方式在附图中展示本公开，在附图中，类似号码用于指示类似元件。

图1是展示了根据本文中所描述技术的用于实施存储系统动态大小反向映射的示例系统的高级框图。

图2是展示了根据本文中所描述技术的存储逻辑示例的框图。

图3是展示了根据本文中所描述技术的所述存储逻辑使用的动态大小反向映射布局的示例图形表示。

图4是展示了根据本文中所描述技术的所述动态大小反向映射支持块复制的布局的示例图形表示。

图5A和5B是根据本文中所描述技术的用于生成存储设备写过程动态大小反向映射的示例方法的流程图。

图6是根据本文中所描述技术的实施动态大小反向映射以包括用于存储设备数据块的缓冲条目的示例方法的流程图。

图7是根据本文中所描述技术的实施用于存储设备动态大小反向映射的垃圾收集操作的示例方法的流程图。

图8是根据本文中所描述技术的实施用于块复制过程的存储设备动态大小反向映射的示例方法的流程图。

具体实施方式

以下描述了用于实施动态大小反向映射架构的系统和方法。具体地，在本公开中，以下描述了用于实施存储设备(具体是具有压缩的闪存存储设备)的动态大小反向映射的系统和方法。虽然本公开的系统和方法是在使用了闪存存储的特定系统架构的背景下描述的，应该理解的是，所述系统和方法可以应用于硬件和其他具有类似属性的存储器设备的其他架构和组织。

本公开涉及实施用于写过程、垃圾收集过程和块复制过程的存储设备的动态大小反向映射。在一些实施例中，本公开描述了一种用于存储应用的可变大小反向映射布局。本公开与现有实施方式的区别在于解决了各种问题。例如，当存储设备的存储容量不断增大时，动态转换表和反向映射的大小也相应增大。同时，将数据缩减技术应用于存储器管理领域以在相同的存储设备中存储更多数据，这导致存储设备中的转换表变得更大。进一步地，由于所述数据缩减技术中使用了可变数据压缩比率，这要求可变大小转换表。因此，在存储业，亟需以下描述的基于工作量的反向映射。另外，垃圾收集(GC)是一种部署在存储器管理中的典型技术。垃圾收集收回被不再使用的对象所占用的存储器。垃圾收集机制处理存储媒体中邻近范围的位置。因此，需要物理媒体-逻辑块地址的反向映射(反向转换表)。由此，本公开通过提供一种用于实施存储设备存储应用的高度基于工作量的反向映射，解决了与高效数据存储相关联的问题。

系统

图1是展示了根据本文中所描述技术的用于实施存储设备动态大小反向映射的示例系统100的高级框图。在描绘的实施例中，系统100可以包括存储逻辑104和一个或多个存储设备或存储媒体110a、110b至110n。应当注意的是，本公开通篇互换使用了术语“存储媒体”和“存储设备”，用于指示存储数据的物理媒体。在展示的实施例中，存储逻辑104与所述一个或多个存储设备110a、110b至110n经由信号线126a、126b至126n通信地耦合。但是，本公开并不局限于这种配置，可以部署各种不同的系统环境和配置，并且所述各种不同的系统环境和配置是在本公开的范围内。其他实施例可以包括额外的或更少的部件。应该理解的是，图1和其他图是用于展示实施例的，并且参考号或标记后字母(例如“110a”)的指示是对由该特定参考标记指定的元件或部件的具体引用。如文中参考标号(例如“110”)没有后跟字母，应该理解的是，这种参考标记是对包含该参考标记的元件或部件的不同实施例的总体参考。

在一些实施例中，存储逻辑104实施存储设备的动态大小反向映射以及存储相关操作。存储逻辑104能够提供计算功能、服务和/或资源以发送、接收、读、写和变换来自系统100其他实体的数据。在一些实施例中，存储逻辑104可以是计算设备，被配置成用于使存储设备110的一部分或全部存储空间可用。存储逻辑104经由信号线126耦合至存储设备110，用于与系统110的存储设备110a-110n通信和合作。在其他实施例中，存储逻辑104经由信号线126a-126n在存储设备110a-110n之间传输数据。应该理解的是，可以以分布式架构或其他方式利用多个存储逻辑104。为了本申请的目的，系统100执行的系统配置和操作是在单个存储逻辑104的背景下描述的。

存储设备110a、110b至110n可以包括非瞬态计算机可使用(例如可读、可写等)介质，所述非瞬态计算机可使用介质可以是任何包含、存储、传达、传播或传输由处理器处理或者与其结合处理的指令、数据、计算机程序、软件、代码例程等的非瞬态装置或设备。在一些实施例中，存储设备110a、110b至110n经由信号线126a、126b至126n与存储逻辑104通信和合作。虽然本公开将存储设备110视为闪速存储器，应该理解的是，在一些实施例中，存储设备110可以包括其他具有类似特性的非易失性存储器设备。

图2是展示了根据本文中所描述技术的存储逻辑104示例的框图。存储逻辑104是组合逻辑、固件、软件、代码或例程或其一些组合，用于实施存储设备110的动态大小反向映射。如在图2中所描绘的，存储逻辑104可以包括数据接收模块202、存储控制器204、存储器212和垃圾收集模块210，上述部件可经由通信总线(未示出)电耦合和通信地耦合以相互合作和通信。存储器212可以进一步包括动态转换表206和动态大小反向映射208。部件202、204、206、208、210和212还经由信号线126耦合以与系统100的其他实体(例如存储设备110)进行通信。但是，本公开并不局限于这种配置，可以部署各种不同的系统环境和配置，并且所述各种不同的系统环境和配置是在本公开的范围内。其他实施例可以包括额外的或更少的部件。

在一个实施例中，数据接收模块202、存储控制器204、存储器212和垃圾收集模块210是用于执行以下描述的操作的硬件。在一些实施例中，数据接收模块202、存储控制器204、存储器212和垃圾收集模块210是可由处理器执行的指令集或包括在一个或多个定制处理器中的逻辑，以便提供其各自功能。在一些实施例中，数据接收模块202、存储控制器204、存储器212和垃圾收集模块210存储在存储装置中，并且可由处理器访问和执行，以便提供其各自功能。在进一步实施例中，数据接收模块202、存储控制器204、存储器212和垃圾收集模块210被适配成用于与处理器和系统100的其他部件合作和通信。单元、模块、例程、特征、属性、方法和其他方面的特定命名和分割不是必需遵守的或者不是重要的，并且实施本公开或其特征的机制可以有不同的名称、分割和/或格式。

数据接收模块202是用于接收来自一个或多个设备的数据和/或命令和/或检索数据的缓冲和软件、代码或例程。在一个实施例中，数据接收模块202接收来自一个或多个设备的数据流(数据包)，并将它们准备好以存储在非易失性存储设备(例如存储设备110)中。在一些实施例中，数据接收模块202接收进入数据包并暂时将所述数据包存储在存储器缓冲(可以是或可以不是存储器212的一部分)中。

数据接收模块202接收进入数据和/或在一个或多个数据库(例如，但不限于，存储器212和系统100的存储设备110)中检索数据。进入数据可以包括但不限于数据流和/或命令。所述数据流可以包括数据块集合(例如，新数据流的当前数据块、来自存储设备的现有数据块等)。所述数据块集合(例如，所述数据流的数据块集合)可以与但不限于由定制处理器执行和渲染和/或存储在存储器中的文档、文件、邮件、消息、博客和/或任何应用相关联。所述命令可以包括但不限于与新数据流的当前数据块相关联的写操作请求，例如写命令。在一些实施例中，数据接收模块202可以向存储控制器204传输所述命令以执行。

存储控制器204是用于提供高效数据管理的软件、代码、逻辑或例程。存储控制器204可经由通信总线(未示出)电耦合和通信地耦合以与存储逻辑104的其他部件合作和通信。在一些实施例中，存储控制器204是处理器。存储控制器204可以接收来自数据接收模块202的数据块和来自检索动态转换表206的其他数据和/或来自存储器212的动态大小反向映射208。在一些实施例中，存储控制器204可以执行存储逻辑104的高效数据管理，例如，实施用于写过程、垃圾收集过程和块复制过程等的动态大小反向映射208。以下参考图5-8详细地描述了存储控制器204执行的高效数据管理过程。

存储器212还可以存储可由定制处理器(例如存储控制器204)执行的指令和/或数据。在展示的实施例中，存储器212可以包括动态转换表206和动态大小反向映射208。存储器212耦合至总线(未示出)以与存储逻辑104的其他部件通信。存储在存储器212的所述指令和/或数据可以包括用于执行本文中所描述技术的代码。存储器212可以是例如非瞬态存储器，如动态随机访问存储器(DRAM)设备、静态随机访问存储器(SRAM)设备或其他易失性存储器设备。

动态转换表206是一种具有将逻辑地址映射至物理地址的转换结构的表。在一些实施例中，动态转换表206可以存储在存储器212中并在需要时由存储控制器204检索。应该理解的是，动态转换表206还可以存储在其他存储单元中，例如存储设备110。在一些实施例中，动态转换表206可以与数据存储操作同步更新，以跟踪最新逻辑地址-物理地址转换。在展示的实施例中，动态转换表206由存储控制器204用于将数据块写至存储设备110、擦除存储设备110的数据块等。在完成写过程并将其用于以下描述的垃圾收集过程时，动态转换表206还可由存储控制器204进行更新。

动态大小反向映射208是一种具有将物理地址映射至逻辑地址的转换结构的映射。在一些实施例中，动态大小反向映射208可以存储在存储器212中并在需要时由存储控制器204检索。应该理解的是，动态大小反向映射208还可以存储在其他存储单元中，例如存储设备110。在一些实施例中，动态大小反向映射208可以与数据存储操作同步更新，以跟踪最新物理地址-逻辑地址转换。在展示的实施例中，动态大小反向映射208由存储控制器204用于将数据块写至存储设备110以及用于以下描述的垃圾收集过程。在完成写过程时，动态大小反向映射208还可由存储控制器204进行更新。以下参考图3详细地描述了反向映射208的布局。

垃圾收集模块210是用于执行存储设备110的垃圾收集的软件、代码、逻辑或例程。垃圾收集模块210可经由通信总线(未示出)电耦合和通信地耦合以与存储逻辑104的其他部件合作和通信。垃圾收集模块210定期执行系统100的存储设备110的数据垃圾收集。垃圾收集模块210可以指动态大小反向映射208决定数据块是否有效以及是否需要重新定位。所述机制针对该数据块比较动态转换表206和动态大小反向映射208中的两个实体；如果发现在两个映射中物理块是一样的，则判定垃圾收集过程中所述数据块有效且需要重新定位。

垃圾收集模块210可以执行用于映射片段的动态大小反向映射更新(例如，动态大小反向映射208的垃圾收集)。判定是否执行动态大小反向映射更新的时间可以根据需要来改变和限定。在一些实施例中，垃圾收集模块210可以判定是否定期执行动态大小反向映射片段的垃圾收集。在其他实施例中，垃圾收集模块210可以响应于所述数据垃圾收集的完成，判定是否执行动态大小反向映射片段的垃圾收集。在说明性实施例中，垃圾收集模块210可以从片段报头中检索映射片段的信息。

仅出于说明性目的，应该理解的是，片段是存储媒体110上固定范围的邻近物理块，所述物理块依次填充并一起擦除。映射片段可以是存储动态转换表206和动态大小反向映射208的专用片段。在动态大小反向映射208的树结构中，所述片段报头(例如，如图3中所展示的动态大小反向映射208中的L1节点304)可以是比扩展节点(例如，如图3中所展示的动态大小反向映射208中的L0节点306)更高级别的节点，所述节点存储一个或多个扩展节点的元信息。所述信息可以包括但不限于所述映射片段的写入块的使用计数。写入块可以是数据颗粒或扇区，所述数据颗粒或扇区是逻辑块可以缩小的最小单元。作为示例，如果物理块的大小是4096字节，则其可以容纳八(8)个512字节的缩小逻辑块。在一些实施例中，垃圾收集模块210可以基于在所述片段报头中检索的所述信息确定所述映射片段的写入块的使用计数。在进一步实施例中，垃圾收集模块210可以基于所述映射片段的所述使用计数，判定所述映射片段是否满足动态大小反向映射更新标准。例如，假设映射片段包括8个写入块，当预定义数量(例如6个)的写入块无效时，确定所述映射片段满足所述动态大小反向映射更新标准。应该理解的是，以上数字仅是出于说明性目的而提供的，可以使用各种数字和不同预定义的动态大小反向映射更新标准。

当垃圾收集模块210确定所述映射片段满足所述动态大小反向映射更新标准时，垃圾收集模块210可以执行动态大小反向映射更新过程，例如，用于所述映射片段的垃圾收集。在进一步实施例中，在完成所述动态大小反向映射更新过程时，垃圾收集模块210可以更新所述片段报头中的所述映射片段信息。

图3是展示了根据本文中所描述技术的存储逻辑104所见的动态大小反向映射208布局的示例图形表示。如在图3中所描绘的，动态大小反向映射208可以是树结构，并且可以使用基数树的形式来实施树的节点。在展示的实施例中，动态大小反向映射208可以包括L2节点302、L1节点304、L0节点306、L0e映射节点308和L0节点缓冲310。应该理解的是，图3和其他图是用于展示实施例的，并且参考号或标记(例如“304”)的指示是对由该特定参考标记指定的元件或部件的具体引用。如文中参考标号跟在多词术语(例如“L1节点304”)后，应该理解的是，这种参考标记是对包含该参考标记的元件或部件的不同实施例的总体参考。

如图3所示的L2节点302是动态大小反向映射树结构的根节点或母节点。在一些实施例中，可以在动态大小反向映射树结构中利用比L2节点302更高级别的节点。应该理解的是，可以利用多个L2节点302。为了本申请的目的，执行的与动态大小反向映射208相关联的功能和操作是在单个L2节点的背景下描述的。

如图3所示的L1节点304是L2节点302的子节点。在一些实施例中，L1节点304可以存储映射片段的信息，即，L1节点用作片段报头。映射片段可以是存储动态转换表206和动态大小反向映射208的专用片段。在动态大小反向映射树结构中，所述片段报头(例如，如图3中所展示的动态大小反向映射208中的L1节点304)可以是比扩展节点(例如，如图3中所展示的动态大小反向映射208中的L0节点306)更高级别的节点，所述节点存储动态大小反向映射208的节点L0 306的信息。所述信息可以包括但不限于所述映射片段的写入块的使用计数。写入块可以是数据颗粒或扇区，所述数据颗粒或扇区是逻辑块可以缩小的最小单元。作为示例，如果物理块的大小是4096字节，则其可以容纳八(8)个512字节的缩小逻辑块。

如在图3中所描绘的展示的实施例中，动态大小反向映射208树结构的叶节点被称为L0节点306。在一些实施例中，一个L0节点306包括用于片段物理块的映射。此处的片段可以是存储设备110上固定范围的邻近物理块，所述物理块依次填充并一起擦除。应该理解的是，由于片段的大小是固定的，其可能包括固定数量的物理块。例如，假设片段是32K字节且物理块大小是4096字节，则所述片段包括八(8)个物理块。在这种情况下，一个L0节点306包括用于该片段中这八(8)个物理块的映射。

为了支持L0节点306的动态尺寸(从而整个反向映射的动态尺寸)，动态大小反向映射208树结构再扩展了一个级别，如图3所示的L0e映射节点308。L0e映射节点308又称L0条目映射节点，并且本公开通篇互换使用了这两个名称。存储器查找时，基数树搜索物理块将使其前往L0e映射节点308中的条目。如在图3中所描绘的，L0e映射节点308包括多个条目：条目3080、条目3081、条目3082和条目3083。应该理解的是，尽管图3仅示出4个条目，可以利用其他数量的条目，并且所述其他数量的条目是在本公开的范围内。在展示的实施例中，条目3083为空并且将依次填充。在一些实施例中，所述条目中每个条目与一个物理块相对应。因此，L0e映射节点308是固定大小的节点，并且条目数量等于片段物理块的数量。通过以上描述的相同例子，假设在展示的实施例中的片段包括八(8)个物理块。L0e映射节点308的每个条目具有用于所述八(8)个物理块的一个物理块的映射数据。因此，L0e映射节点308可以具有8个条目。如图3中所示，当这些条目表示的物理块被依次填充时，这些条目被依次填充。该特征增强了动态大小反向映射208的位置，并且有益于整体性能，尤其是存储设备的垃圾收集操作。本领域技术人员将会认识到，以上描述的片段大小和物理块大小仅用于示例展示。片段和物理块的各种其他大小被视为在本公开的范围内。

仅出于描述目的，假设图3中所展示的物理块大小是4096字节，并且应该理解的是，可以利用物理块的各种大小。在图3和其他图中，物理块号可以简称为PBN，而逻辑块号可以简称为LBN。

如图3中所展示的，L0e映射节点308的所述条目中每个条目的大小是32比特且格式为<N:E>，其中“N”是该物理块所需的映射数量，“E”是L0节点306中该物理块第一映射的条目索引。更具体地，“N”表示由该条目代表的一个特定物理块所需的映射数量。可以基于数据块的大小和物理块的大小计算一个特定物理块所需的映射数量。例如，如果输入数据流包括一个或多个数据块，其中，所述一个或多个数据块在被压缩后的大小均是1024字节，并且将数据流准备好以在物理块0(PBN＝0)中存储所述一个或多个数据块，如果物理块的大小是4096字节，则当该物理块0存储该数据流时，动态大小反向映射208树结构需要用于该物理块的四(4)个映射。本领域技术人员将会认识到，以上描述的物理块大小和数据块大小仅用于示例展示。物理块和数据块的各种其他大小(由于不同压缩程度)被视为在本公开的范围内。如图3中所示，基于所展示的示例，条目3080代表物理块0，并且该条目3080中的“N”是四(4)。应该理解的是，由于不同的压缩量，物理块所需的映射数量可以基于数据块的大小来改变，数据块需要存储在物理块中。例如，如果需要存储在物理块1中的数据块的大小是2048字节，则该物理块1所需的映射数量是二(2)。如图3中所示，基于以上示例，条目3081代表物理块1，并且该条目3081中的“N”是二(2)。应该理解的是，基于压缩比率，数据块可以具有不同的大小，并且存储在相同物理块的数据块可以具有不同的大小。在一些实施例中，当一个物理块中的可用空间不够用于下一个进入数据块时，系统100可以跨物理块边界存储所述进入数据块。

如以上所讨论的，条目<N:E>中的“E”是L0节点306中第一映射的条目索引。更具体地，“E”代表L0节点306中一个物理块的映射相对起始位置。如在存储业已知的，存储设备的物理块被依次填充。可以理解的是，L0e映射节点308的第一条目(即条目3080)代表片段的物理块号0，并且物理块0的映射起始位置是0。因此，条目3080的条目索引“E”是“0”。如以上所讨论的，物理块0所需的映射数量是4，这意味着物理块0进行4次映射。这4次映射自0开始，即0、1、2和3。由于存储设备的物理块被依次填充，下一个物理块1的映射自数字4开始。在展示的实施例中，条目3081代表片段中的物理块1。因此，条目3081的“E”是4。如以上所讨论的，条目3081的“N”是2；因此这2次映射自4开始，即4和5。依次地，在条目3081后的下一个条目3082的“E”是6。此外，如图3中所示，条目3082可能消耗2次映射，则应为6和7。下一个条目3803为空并且将随后填充。根据先前的分析，条目3803的“E”将是8。这意味着物理块3的第一映射的起始位置地址将是8。

返回参照图3中的L0节点306，所述节点包含用于片段物理块的映射。如图3中所示，L0节点306是由整数个固定大小的分块组成的，所述分块被称为L0节点缓冲310。在一些实施例中，根据需求，从预分配池中分配这些分块。这实现了L0节点306的动态尺寸，从而实现了整个反向映射的动态尺寸。这些分块具有写入块的大小，所述写入块是存储媒体的最小可编程单元。

如图3中所示，L0节点缓冲310包括多个缓冲条目：缓冲条目3100、缓冲条目3101、缓冲条目3102、缓冲条目3103、缓冲条目3104、缓冲条目3105、缓冲条目3106、缓冲条目3107和缓冲条目3108。应该理解的是，尽管图3仅示出9个缓冲条目，可以利用其他数量的条目，并且所述其他数量的条目是在本公开的范围内。在展示的实施例中，缓冲条目3108为空并且将依次填充。在一些实施例中，所述缓冲条目中每个缓冲条目与一个物理块的一个映射相关联。因此，应该理解的是，一个物理块的映射数量等于代表该物理块的缓冲条目数量。例如，如在图3中所描绘的，代表物理块号0的条目3080是<4:0>，意味着其需要4次映射以代表物理块号0；因此，为物理块号0分配了四(4)个缓冲条目，即缓冲条目3100、3101、3102和3103。

如图3中所展示的，缓冲条目的格式为<L:P:S:N>，其中“L”是逻辑块号(LBN)，“P”是物理块号(PBN)，“S”代表物理块中的起始扇区，以及“N”代表物理块的扇区数量。

缓冲条目的“L”代表数据块存储的逻辑块号。在一些实施例中，所述逻辑块号是基于写命令中包括的信息来确定的。

缓冲条目的“P”代表数据块存储的物理块号。应该理解的是，针对一个特定物理块，“P”在其占有的缓冲条目中应相同。例如，物理块0具有4次映射，即缓冲条目3100、3101、3102和3103。这些缓冲条目中的所有“P”均应相同，即PBN是零(0)。类似地，缓冲条目3104和3105中的“P”均应相同，即PBN是一(1)。

缓冲条目的“S”代表物理块的起始扇区。如以上所讨论的，所述缓冲条目中每个缓冲条目代表一个映射。例如，一个物理块的第一映射占用所述物理块的第一整数个扇区，并且用于其的“S”应是零(0)。该相同物理块的第二映射自所述第一映射的结束位置开始，并且可以基于所述物理块的第一映射的“S”和“N”来确定用于其的“S”。

缓冲条目的“N”代表该映射消耗的所述物理块的扇区数量。应该理解的是，可以基于压缩数据块的大小和该物理块扇区的大小来计算用于一次映射的“N”。例如，假设压缩数据块的大小是1024字节(可在存储之前进行压缩，压缩比率为4，例如，4096字节压缩至1024字节)，扇区的大小是512字节，则该压缩数据块可能消耗二(2)个扇区以进行存储。这意味着用于该数据块的映射(缓冲条目)中的“N”是2。在其他实施例中，如果进入压缩数据块的大小(可在存储之前进行压缩，压缩比率为2，例如，4096字节压缩至2048字节)和扇区的大小是512字节，则该压缩数据块可能消耗四(4)个扇区以进行存储。应该理解的是，存储在相同物理块中的压缩数据块的大小可能不同。在一些实施例中，当一个物理块中的可用空间不够用于下一个进入数据块时，系统100可以跨物理块边界存储所述进入数据块。例如，针对一个物理块号0，进入数据流包括若干(第一、第二和第三)压缩数据块，其大小分别为2048字节、1024字节和2048字节。第一2048字节数据块可能消耗四(4)个扇区，并且用于其的映射可以是<L:P:0:4>，其中L代表逻辑块号，P代表物理块号，两者可以根据以上描述来确定。这里，如以上所讨论的，用于该第一2048字节数据块的“S”是零(0)，并且用于其的“N”是四(4)。第二1024字节数据块可能消耗两(2)个扇区，并且用于其的映射可以是<L P:4:2>，其中用于其的“S”是四(4)，这意味着用于其的起始扇区是4。可以理解的是，由于第一数据块已经采用了4个扇区，即0、1、2和3，用于该第二数据块的“N”是二(2)，这意味着其消耗2个扇区以进行存储。如以上所讨论的，本公开允许相同物理块中的不同数据块具有不同大小的物理空间。然后，参照相同的示例，如以上所讨论的，所述进入数据流的第三数据块是2048字节，并且其将采用4个扇区以进行存储。但是，如以上所讨论的，假设物理块的大小是4096字节，前两个数据块已经消耗了3072字节。这使得该物理块中仅1024字节可用，这不够用于整个第三数据块。在一些实施例中，可以跨物理块边界存储数据块。因此，用于第三数据块的映射可以是<L P:6:4>，其中“S”是6，“N”是4。如以上所讨论的，该物理块的可用空间不够用于第三数据块；因此，所述第三数据块采用该物理块的2个扇区和下一个物理块的2个扇区以存储。应该理解的是，第二物理块的第一映射应反映出所述第二物理块的第一1024字节(2个扇区)已经被采用；由此，所述第一映射应是<L P:2:N>。这意味着，所述第二物理块的第一映射自扇区2开始，反映出该物理块的前2个扇区已经被采用。应该理解的是，以上示例仅是一个示例且并未在图3中示出。

由于本文中所描述的技术引入了基于工作量的动态大小反向映射208，其是有益的。如以上所讨论的，由于存储设备110支持数据缩减，一个物理块能够以简化形式存储多个逻辑块。因此，基于不同的压缩比率，每个物理块可能需要不同的映射数量。因此，尽管所述L0节点306中每个节点代表相同数量的物理块，但是因为L0节点306可以根据需求包括不同数量的L0节点缓冲，其大小可能互不相同。因此，基于工作量，动态大小反向映射208的总体大小可以是可变的。

图4是展示了根据本文中所描述技术的动态大小反向映射208支持块复制的布局的示例图形表示。块复制是一种将一定范围的逻辑块复制至另一范围的逻辑块的机制。为了在本文中所描述的动态大小反向映射208实施中支持块复制，L0节点306的可变大小特征可以是有益的。如参照图3而讨论的，可将L0节点扩展至超过片段能够具有的最大映射数量。在块复制后，可以将这些新映射用于物理块指向的新范围的逻辑块。

如在图4中所描绘的，L0节点缓冲310可以包括整数个缓冲条目。当系统100接收到将多个数据块从第一逻辑地址范围复制到第二逻辑地址范围的请求时，系统100可以更新动态大小反向映射208以指示块复制过程。例如，假设块复制请求旨在将数据从逻辑块号5复制至逻辑块号8，则可以更新动态大小反向映射208以指示数据的物理块至逻辑块号8的新映射。如在图4中所描绘的，可以更新缓冲条目3105以包括格式为<FP:NR>的额外信息，其中，“FP”代表正向指针，“NR”代表引用数量。以下参考图8详细地描述了块复制过程。

图5A和5B是根据本文中所描述技术的用于生成存储设备110写过程动态大小反向映射208的示例方法500的流程图。方法500可以通过以下方式来开始：接收502数据流，所述数据流包括一个或多个数据块。在一个实施例中，数据接收模块202接收来自一个或多个设备(未示出)的数据流(数据包)，并将它们准备好以存储在存储设备110中。进入数据可以包括但不限于数据流和/或命令。所述数据流可以包括数据块集合(例如，新数据流的当前数据块)。在一些实施例中，数据接收模块202接收的所述数据流呈压缩形式。在其他实施例中，数据接收模块202接收的所述数据流传输至存储控制器204以在存储过程前进行压缩。在一些实施例中，步骤502中执行的操作可以由数据接收模块202与系统100的一个或多个其他部件协作执行。

然后，响应于步骤502的接收数据流，方法500通过以下方式继续：检索504动态转换表206。在一个实施例中，存储控制器204在存储器212中检索动态转换表206。在一些实施例中，如果需要，存储控制器204可以在存储过程前压缩所述进入数据流。

然后，方法500可以通过以下方式前进：标识506物理地址和逻辑地址，以基于动态转换表206存储检索的数据流的所述一个或多个数据块。应该理解的是，可以在存储过程前压缩所述检索的数据流的所述一个或多个数据块。在一个实施例中，存储控制器204标识物理地址和逻辑地址以存储所述一个或多个数据块。

然后，方法500可以将所述数据块存储508在存储设备110中，并更新动态转换表206以包括用于所述数据块的物理地址和逻辑地址。在一个实施例中，存储控制器204将所述数据块存储至存储设备110中，并更新动态转换表206以包括用于所述数据块的逻辑地址-物理地址映射。在一些实施例中，存储控制器204还将更新的动态转换表206存储至存储器212中。

然后，方法500可以通过以下方式前进：确定510所述数据块的大小。在一个实施例中，存储控制器204确定所述数据块的大小。返回参照图3，所述数据块的大小可用于确定一个特定物理块所需的映射数量。此外，所述数据块的大小可用于确定物理块缓冲条目中每个缓冲条目占用的扇区数量。

然后，方法500可以基于数据块的大小(压缩后)和物理块的大小确定512物理块所需的映射数量。应该理解的是，如果已经压缩了数据块，基于压缩比例，所述数据块的大小是可变化的。在一个实施例中，存储控制器204基于数据块的大小(或数据块的压缩后大小)和物理块的大小确定物理块所需的映射数量。例如，如果输入数据流包括一个或多个数据块，其中，所述一个或多个数据块在被压缩后的大小是1024字节(由于逻辑块大小最初为4096字节且压缩至1024字节)，并且准备好以存储在物理块0(PBN＝0)，如果物理块的大小是4096字节，则当该物理块0存储该数据流时，动态大小反向映射208树结构需要用于该物理块的四(4)个映射。应该理解的是，如图3中所展示的，物理块所需的映射数量是L0e映射节点308中的“N”。应该理解的是，基于压缩比率，数据块可以具有不同的大小，并且存储在相同物理块的数据块可以具有不同的大小。在一些实施例中，当一个物理块中的可用空间不够用于下一个进入数据块时，系统100可以跨物理块边界存储所述进入数据块。

然后，方法500可以检索514动态大小反向映射208。在一些实施例中，动态大小反向映射208可以存储在存储器212中并在需要时由存储控制器204检索。应该理解的是，动态大小反向映射208还可以存储在其他存储单元中，例如存储设备110。在一些实施例中，动态大小反向映射208可以与数据存储操作同步更新，以跟踪最新物理地址-逻辑地址转换。

然后，方法500可以通过以下方式前进：确定动态大小反向映射208中用于存储数据块的映射的相对起始位置。在一个实施例中，存储控制器204确定动态大小反向映射208中用于存储数据块的映射的相对起始位置。如以上参照图3所讨论的，所述相对起始位置是L0e映射节点308中条目的条目索引“E”。返回参照图3，“E”代表L0节点306中一个物理块的映射相对起始位置。如在存储业已知的，存储设备的物理块被依次填充。可以理解的是，L0e映射节点308的第一条目(即条目3080)代表片段的物理块号0，并且物理块0的映射起始位置是0。因此，条目3080的条目索引“E”是“0”。如以上所讨论的，物理块0所需的映射数量是4，这意味着物理块0进行4次映射。这4次映射自0开始，即0、1、2和3。由于存储设备110的物理块被依次填充，下一个物理块1的映射自数字4开始。在展示的实施例中，条目3081代表片段中的物理块1。因此，条目3081的“E”是4。如以上所讨论的，条目3081的“N”是2；因此这2次映射自4开始，即4和5。依次地，在条目3081后的下一个条目3082的“E”是6。条目3803为空并且将随后填充。根据先前的分析，条目3803的“E”将是8。这意味着物理块3的第一映射的起始位置地址将是8。再次，还应该理解的是，基于压缩比率，数据块可以具有不同的大小，并且存储在相同物理块的数据块可以具有不同的大小。在一些实施例中，当一个物理块中的可用空间不够用于下一个进入数据块时，系统100可以跨物理块边界存储所述进入数据块。

返回参照图5B，方法500可以通过以下方式前进：在动态大小反向映射208中针对物理块中每个物理块创建一个条目，所述条目包括该物理块的映射数量和存储数据块的映射的相对起始位置。在一个实施例中，存储控制器204创建用于动态大小反向映射208物理块中每个物理块的一个条目。所述条目被创建为包括该物理块所需的映射数量和用于该物理块的第一映射相对起始位置。在一些实施例中，如在图3中所描绘的，创建多个所述条目并将其存储为L0e映射节点308。然后，方法500可以更新520动态大小反向映射208。在一些实施例中，存储控制器204更新动态大小反向映射208，并将更新的动态大小反向映射208存储至存储器212中。

图6是根据本文中所描述技术的实施动态大小反向映射208以包括用于存储设备110数据块的缓冲条目的示例方法600的流程图。如以上所讨论的，动态大小反向映射208是可变大小映射。针对每个物理块，动态大小反向映射208可以具有不同数量的缓冲条目以存储用于该物理块的不同数量的映射。应该理解的是，如果已经压缩了数据块，基于压缩比例，所述数据块的大小是可变化的。因此，尽管物理块的大小是固定的，一个物理块可以存储多个呈圧缩形式的逻辑块。由此，基于工作量和/或存储在存储设备110中的逻辑块的数量，动态大小反向映射208的大小可以是可变的。本文参照图6描述了建立用于数据块的缓冲条目的详细步骤。如在图3中所描绘的，缓冲条目包括在L0节点306中，格式为<L:P:S:N>，其中“L”是逻辑块号(LBN)，“P”是物理块号(PBN)，“S”代表物理块中的起始扇区，以及“N”代表物理块的扇区数量。

方法600可以通过以下方式来开始：针对所述数据块中每个数据块，基于动态大小反向映射208确定602物理块号。如以上所讨论的，当系统100接收数据流，所述数据流包括一个或多个数据块时，系统100将所述数据块存储至存储设备110中。所述数据流可以由存储逻辑104的数据接收模块202接收。在一些实施例中，存储控制器204基于动态大小反向映射208确定用于所述数据块中每个数据块的物理块号。如以上参照图3所讨论的，动态大小反向映射208可以包括下一个可用物理块号的映射信息。缓冲条目的“P”代表数据块存储的物理块号。应该理解的是，针对一个特定物理块，“P”在其占有的缓冲条目中应相同。例如，如图3中所示，物理块0具有4次映射，即缓冲条目3100、3101、3102和3103。这些缓冲条目中的所有“P”均应相同，即PBN是零(0)。类似地，缓冲条目3104和3105中的“P”均应相同，即PBN是一(1)。

返回参照图6，方法600可以通过以下方式继续：关于所述数据块中每个数据块，基于所述数据块中每个数据块的大小确定604其将占用的物理块中的扇区数量。应该理解的是，如果已经压缩了数据块，基于压缩比例，所述数据块的大小是可变化的。如以上参照图3所讨论的，缓冲条目的“N”代表该数据块消耗的所述物理块的扇区数量。在一些实施例中，存储控制器204基于该物理块存储的压缩数据块的大小和该物理块扇区的大小来计算所述“N”。例如，假设压缩数据块的大小是1024字节(可在存储之前进行压缩，压缩比率为4，例如，4096字节压缩至1024字节)，扇区的大小是512字节，则该压缩数据块可能消耗二(2)个扇区以进行存储。这意味着用于该数据块的映射(缓冲条目)中的“N”是2。在其他实施例中，如果进入压缩数据块的大小(可在存储之前进行压缩，例如压缩比率为2)和扇区的大小是512字节，则该压缩数据块可能消耗四(4)个扇区以进行存储。应该理解的是，存储在相同物理块中的压缩数据块的大小可能不同。在一些实施例中，当一个物理块中的可用空间不够用于下一个进入数据块时，系统100可以跨物理块边界存储所述进入数据块。

返回参照图6，方法600可以通过以下方式前进：关于所述数据块中每个数据块，基于动态大小反向映射208确定606的物理块中的起始扇区。物理块的起始扇区由缓冲条目的“S”来表示。如以上参照图3所讨论的，所述缓冲条目中每个缓冲条目代表一个映射。例如，一个物理块的第一映射/缓冲条目占用所述物理块的第一整数个扇区，并且用于其的“S”应是零(0)。该相同物理块的第二映射/缓冲条目自所述第一映射的结束位置开始，并且可以基于所述物理块的第一映射/缓冲条目的“S”和“N”来确定用于其的“S”。

然后，方法600可以通过以下方式继续：确定608用于数据块的逻辑块号。在一些实施例中，存储控制器204可以基于写命令推断出用于数据块的逻辑块号。如在图3中所描绘的，所述逻辑块号由缓冲条目的“L”来表示。

方法600可以通过以下方式继续：更新610动态大小反向映射208以包括针对数据块中每个数据块的缓冲条目，其中，缓冲条目包括逻辑块号(L)、物理块号(P)、物理块中的起始扇区(S)和存储数据块所需要的扇区数量(N)。在一些实施例中，存储控制器204可以更新动态大小反向映射208，然后将更新的动态大小反向映射208存储至存储器212中，并且方法600可结束。

图7是根据本文中所描述技术的实施用于存储设备110动态大小反向映射208的垃圾收集操作的示例方法700的流程图。通过垃圾收集过程收回物理块后，所述物理块将由新逻辑块使用。这将产生新反向映射，使得该物理块的旧反向映射无效。这种无效映射会随着时间在存储设备110中积累。这些无效映射消耗的空间通过动态大小反向映射更新过程收回，即用于动态大小反向映射208的垃圾收集。所述动态大小反向映射208的垃圾收集每次处理一个片段，并至少基于所述片段中存在的无效数据量来选择用于垃圾收集的最佳片段。针对可变大小L0节点306，动态大小反向映射208需要记录L0节点消耗的片段空间。如以上所讨论的，L0节点306是由整数个写入块组成。由此，片段的无效空间是以写入块为单元计算的。

方法700可以通过以下方式来开始：对存储设备110执行702数据垃圾收集。在一些实施例中，垃圾收集模块210定期执行系统100的存储设备110的数据垃圾收集。应该理解的是，垃圾收集是一种发现程序中无法再访问的数据对象并收回被这些对象使用的资源的自动存储器管理形式。

然后，方法700则可以通过以下方式继续：从片段报头中检索704映射片段的信息。在一些实施例中，存储控制器204可以响应于数据垃圾收集的完成而在片段报头中检索映射片段的信息。仅出于说明性目的，应该理解的是，片段是存储设备110上固定范围的邻近物理块，所述物理块依次填充并一起擦除。映射片段可以是存储动态转换表206和动态大小反向映射208的专用片段。在动态大小反向映射208的树结构中，所述片段报头(例如，如图3中所展示的动态大小反向映射208中的L1节点304)可以是比扩展节点(例如，如图3中所展示的动态大小反向映射208中的L0节点306)更高级别的节点。所述映射片段信息存储在L0节点报头中，即图3动态大小反向映射208的树结构中所描绘的L1节点304。L1节点304存储构成存储设备110上L0节点306的写入块的数量信息以及该L0节点306写入的片段地址。当L0节点306写入存储设备110时，从L1节点304中提取旧片段地址和写入块的数量。旧片段中无效写入块的数量(使用计数)按照该L0节点306已经消耗的写入块数量递增。

返回参照图7，方法700可以通过以下方式继续：确定706映射片段的写入块的使用计数。写入块可以是数据颗粒或扇区，所述数据颗粒或扇区是逻辑块可以缩小的最小单元。作为示例，如果物理块的大小是4096字节，则其可以容纳八(8)个512字节的缩小逻辑块。在一些实施例中，垃圾收集模块210可以基于在所述片段报头中检索的所述信息确定所述映射片段的写入块的使用计数。步骤706中执行的操作可以由存储控制器204与系统100的一个或多个其他部件协作执行。

然后，方法700可以通过以下方式前进：基于所述映射片段的所述使用计数，判定708所述映射片段是否满足动态大小反向映射更新标准。在一些实施例中，垃圾收集模块210可以基于所述映射片段的所述使用计数，判定所述映射片段是否满足动态大小反向映射更新标准。例如，所述动态大小反向映射更新标准可以预先定义为比较使用计数和阈值。该过程在方法700的步骤710中进行了描述。例如，如果映射片段的使用计数递增为36且预定阈值为30，则垃圾收集模块210确定该映射片段满足动态大小反向映射更新标准。在另一个实施例中，如果映射片段的使用计数为26且预定阈值为30，则垃圾收集模块210确定该映射片段不满足动态大小反向映射更新标准。如在图7中所描绘的，响应于映射片段不满足动态大小反向映射更新标准的判定，方法700可以结束。

然后，方法700则可以通过以下方式继续：响应于确定映射片段满足动态大小反向映射更新标准，执行712对映射片段的动态大小反向映射更新过程。在一些实施例中，垃圾收集模块210可以执行动态大小反向映射更新过程，即动态大小反向映射208的垃圾收集。步骤712中执行的操作可以由存储控制器204与系统100的一个或多个其他部件协作执行。

然后，方法700可以通过以下方式继续：更新714片段报头中的映射片段的信息。在一些实施例中，垃圾收集模块210可以更新片段报头中的映射片段的信息。在展示的实施例中，在映射片段的垃圾收集过程后，重置映射片段的使用计数。所述映射片段信息可以存储在映射片段报头中，即如在图3中所描绘的L1节点304。在更新所述映射片段信息后，方法700可以结束。

图8是根据本文中所描述技术的实施用于块复制过程的存储设备110动态大小反向映射208的示例方法800的流程图。方法800可以通过以下方式来开始：接收802将多个数据块从第一逻辑地址范围复制到第二逻辑地址范围的请求。在一个实施例中，数据接收模块202接收将多个数据块从第一逻辑地址范围复制到第二逻辑地址范围的请求。所述请求可以包括但不限于所述第一逻辑地址范围的信息、所述第二逻辑地址范围的信息和数据块的信息。

然后，方法800可以通过以下方式继续：检索804动态转换表206。在一些实施例中，存储控制器204可以检索动态转换表206。

然后，方法800可以通过以下方式前进：基于所述第一逻辑地址范围和所述转换表，确定806所述数据块的物理地址。在一些实施例中，存储控制器204可以基于所述第一逻辑地址范围和动态转换表206，确定所述数据块的物理地址。

然后，方法800可以通过以下方式继续：更新808动态转换表206以包括第二逻辑地址范围到物理地址的条目。在一些实施例中，存储控制器204可以更新动态转换表206以包括第二逻辑地址范围到物理地址的条目。通过步骤808中执行的操作，第二逻辑地址范围指向存储多个数据块的物理地址。

然后，方法800可以通过以下方式继续：检索810动态大小反向映射208。

方法800可以通过以下方式继续：确定812所述数据块的大小。在一些实施例中，存储控制器204可以基于所述将多个数据块从第一逻辑地址范围复制到第二逻辑地址范围的请求，确定所述数据块的大小。所述请求可以包括所述数据块的信息。

然后，方法800可以通过以下方式前进：基于数据块的大小和动态大小反向映射208，确定814所述数据块占用的引用数量。如以上参照图4所讨论的，可以基于数据块的大小和动态大小反向映射208确定引用数量。缓冲条目3105复制至缓冲条目3108，并且引用数量为“1”。

方法800可以通过以下方式前进：基于动态大小反向映射208确定816正向指针，所述正向指针指示所述物理块指向的第二逻辑地址范围。如在图4中所描绘的，当将数据块从第一逻辑地址范围(例如，缓冲条目3105中所示的逻辑块号5)复制至第二逻辑地址范围(例如，缓冲条目3108中所示的逻辑块号8)时，确定所述正向指针(FP)为8。

方法800可以通过以下方式前进：使用所述正向指针和所述引用数量来更新818动态大小反向映射208中的数据块的映射。如在图4中所描绘的，可以更新缓冲条目3105以包括<FP:NR>信息，其中，“FP”代表正向指针，“NR”代表引用数量。在更新动态大小反向映射208的数据块映射后，方法800可以结束。

以下描述了用于实施存储设备的动态大小反向映射的系统和方法。在以上描述中，出于解释的目的，阐述了许多具体的细节。然而，可能显而易见的是，可以在没有任何这些具体细节给定子集的情况下实践所公开的技术。在其他实例中，以框图的形式示出了结构和设备。例如，参考用户界面和特定硬件，以上在一些实现方式中描述了所公开的技术。而且，以上所公开的技术主要针对在线服务；但是，所公开的技术适用于其他数据来源和其他数据类型(例如，收集如图像、音频、网页等其他资源)。

本说明书中对“一个实施例”、“一些实施例”或“实施例”的引用意味着结合该实施例所描述的特定特征、结构、或特性包括在所公开的技术的至少一个实施例中。短语“在一个实施例中”在本说明书中各地方的出现不一定全都引用相同的实施例。

已经在对计算机存储器内数据位的操作的处理和符号表示方面呈现了以上详细描述的某些部分。通常，过程被认为是导致结果的自相一致的一序列步骤。这些步骤可以涉及物理量的物理操纵。这些量采用能够被存储、传递、组合、比较、以及以另外方式操纵的电或磁信号的形式。这些信号可以称为呈比特、值、元素、符号、字符、术语、数字等形式。

这些和类似的术语与适当的物理量相关联并且可以被视为应用于这些量的标记。如从现有讨论中明显看到，除非另外特别声明，否则应认识到，贯穿本说明书，使用如“处理”或“运算”或“计算”或“确定”或“显示”等术语的讨论可以指计算机系统或类似电子计算设备的动作和过程，所述计算机系统或类似电子计算设备对表示为计算机系统的寄存器和存储器的物理(电子)量的数据进行操纵并且将其转换成类似地表示为计算机系统存储器或寄存器或其他此类信息存储、传输或显示设备中的物理量的其他数据。

所公开的技术还可涉及一种用于执行本文中的操作的装置。该装置可以是为了所需目的而特别构造的，或者它可以包括通过存储在计算机中的由计算机程序选择性地激活或重新配置的通用计算机。

所公开的技术可以采用完全硬件实现方式、完全软件实现方式或包含硬件和软件元件两者的实现方式的形式。在一些实现方式中，通过软件实施技术，所述软件包括但不限于固件、驻留软件、微代码等。

进一步地，所公开的技术可以采用计算机程序产品的形式，可以从提供由计算机或任何指令执行系统使用或者与其结合使用的程序代码的非瞬态计算机可使用或计算机可读介质访问所述计算机程序产品。为了本申请的目的，计算机可使用或者计算机可读介质可以是任何包含、存储、传达、传播或传输由指令执行系统、装置或设备使用或者与其结合使用的程序的装置。

适合于存储和/或执行程序代码的计算机系统或数据处理系统将包括至少一个处理器(例如，硬件处理器)，所述处理器经由系统总线直接或间接耦合至存储器元件。所述存储器元件可以包括在实际执行程序代码时采用的本地存储器、大容量存储器和高速缓冲存储器，所述高速缓冲存储器提供临时存储至少一些程序代码，以便减少执行时必须在大容量存储器中检索代码的次数。

输入/输出或I/O设备(包括但不限于键盘、显示器、指点设备等)可以直接或通过介于其间的I/O控制器耦合至系统。

网络适配器也可以耦合至系统，以使数据处理系统通过介于其间的私有或公共网络耦合至其他数据处理系统或远程打印机或存储设备。调制解调器、缆线调制解调器和以太网卡仅是少数当前可用的网络适配器类型。

最后，本文呈现的处理器和显示器可能不是固有地与任何特定计算机或其他装置相关。各种通用系统可以与根据本文中的教导的程序一起使用，或者可以证明构建更加专用的装置来执行所需的方法步骤是方便的。多种这些系统所需的结构将出现在以下描述中。此外，没有引用任何具体的编程语言来描述所公开的技术。应认识到，各种编程语言可以用于实现如在本文中所描述的技术的教导。

出于说明和描述的目的，提供了先前的本技术实施方式描述。未旨在详尽地展示或将本技术限制在所公开的确切形式。鉴于以上教导，可以做出许多修改和变更。本技术的范围旨在不受此详细说明的限制。可以以其他具体形式实施技术而不偏离其精神或必要特征。同样，模块、例程、特征、属性、方法和其他方面的特定命名和分割不是必需遵守的或者不是重要的，并且实施本技术或其特征的机制可以有不同的名称、分割或格式。进一步地，本技术的模块、例程、特征、属性、方法和其他方面可以被实现为软件、硬件、固件、或任何三者的组合。另外，在部件(其示例是模块)被实现为软件的情况下，所述部件可以被实现为独立的程序、更大程序的一部分、多个单独的程序、静态或动态链接库、内核可加载模块、设备驱动程序、和/或计算机编程现在已知或将来知晓的每一个和任何其他方式。另外，本技术绝不限于使用任何具体编程语言或者用于任何具体操作系统或环境的实现。因此，本技术的公开旨在说明而非旨在限制。