用于存储系统中的基于对象的事务的方法和系统

摘要

公开了一种方法，包括：创建用于事务的事务对象，所述事务对象由TOI标识，并且与由OID标识的对象相关联；存储用于所述事务对象的TE和MD碎片；接收将数据写入到所述事务对象的写入请求；存储包括TOI和偏移的第二TE以及包括所述数据的数据碎片；存储包括散列值和所述数据碎片的物理地址的条目；并且接收提交所述事务的提交请求。响应于所述提交请求，存储用于所述事务对象的第三TE和第二MD碎片，其中，第二MD碎片标识所述对象，并且指定所述事务被提交；以及更新包括第二散列值和用于第二数据碎片的第二物理地址的第二条目，以用所述物理地址取代所述第二物理地址。

说明书

背景技术

应用程序通常要求各种数据在事务中被原子提交。在对象存储系统中，事 务是与将被修改的对象相应的一组逻辑存储位置(偏移)和将在每个偏移处被 写入的新数据，在所述每个偏移处，该新数据将全部都是可见的，或者如果发 生故障，它将全部都不可见，但具有修改的部分的任何其它中间状态都不被允 许。传统的用于实现事务的机制通常要求将数据作为事务的一部分写入多次以 便提交事务，导致处理开销大。

发明内容

一般地，在一个方面，本发明涉及一种非暂时性计算机可读介质，包括指令， 当由处理器执行时所述指令实施方法，所述方法包括：创建用于事务的事务对象， 其中，所述事务对象由事务对象ID(TOI)标识，并且与由对象ID(OID)标识的 对象相关联；将用于所述事务对象的内容表条目(TE)和元数据(MD)碎片存储 于永久存储器中，其中，所述TE引用所述MD碎片，所述MD碎片标识所述对象； 接收将数据作为所述事务的一部分写入到所述事务对象的写入请求，其中，所述写 入请求指定所述TOI和偏移；响应于所述写入请求：将第二TE和数据碎片存储于 所述永久存储器中，其中，所述第二TE指定所述TOI和所述偏移，并且其中，所 述第二TE引用所述数据碎片，并且所述数据碎片包括所述数据；将包括散列值和 所述数据碎片的物理地址的条目存储于存储器内数据结构中，其中，所述散列值从 所述TOI和所述偏移得出；接收提交所述事务的提交请求；响应于所述提交请求：

将用于所述事务对象的第三TE和第二元数据(MD)碎片存储于所述永久存 储器中，其中，所述第三TE引用所述第二MD碎片，其中，所述第二MD碎片标 识所述对象，并且指定所述事务被提交；在所述存储器内数据结构中更新包括第二 散列值和第二数据碎片的第二物理地址的第二条目，以用所述物理地址替代所述第 二物理地址，其中，所述第二散列值从所述OID和所述偏移得出。

一般地，在一个方面，本发明涉及一种非暂时性计算机可读介质，包括指 令，当由处理器执行时所述指令实施方法，所述方法包括：接收将数据作为事 务的一部分写入的写入请求，其中，所述写入请求指定用于事务对象的事务对 象ID(TOI)和偏移，并且其中，所述TOI与由对象ID(OID)标识的对象相 关联；响应于所述写入请求：将TE和数据碎片存储于永久存储器中，其中， 所述TE指定所述TOI和所述偏移，其中，所述TE引用所述数据碎片，并且 所述数据碎片包括所述数据；将包括散列值和所述数据碎片的物理地址的条目 存储于存储器内数据结构中，其中，所述散列值从所述TOI和所述偏移得出； 接收将第二数据作为第二事务的一部分写入的第二写入请求，其中，所述第二 写入请求指定用于第二事务对象的第二TOI和第二偏移，并且其中，所述第二 TOI与由第二OID标识的第二对象相关联；响应于所述第二写入请求：将第二 TE和第二数据碎片存储于所述永久存储器中，其中，所述第二TE指定所述第 二TOI和所述第二偏移，其中，所述第二TE引用所述第二数据碎片，并且所 述第二数据碎片包括所述第二数据；将包括第二散列值和所述第二数据碎片的 第二物理地址的第二条目存储于存储器内数据结构中，其中，所述第二散列值 从所述第二TOI和所述第二偏移得出；接收提交请求，其中，所述提交请求包 括所述TOI和所述第二TOI；响应于所述提交请求：将第三TE和复合碎片存 储于永久存储器中，其中，所述第三TE引用所述复合碎片，其中，所述复合 碎片包括第四TE和第五TE，其中，所述第四TE引用MD碎片，其中，所述 MD碎片标识所述TOI，并且指定所述事务被提交，其中，所述第五TE引用第 二MD碎片，其中，所述第二MD碎片标识所述第二TOI，并且指定所述第二 事务被提交；在所述存储器内数据结构中更新包括第三散列值和用于第三数据 碎片的第三物理地址的第三条目，以用所述物理地址替代所述第三物理地址， 其中，所述第三散列值从所述OID和所述偏移得出；在所述存储器内数据结构 中更新包括第四散列值和用于第四数据碎片的第四物理地址的第四条目，以用 所述第二物理地址取代所述第四物理地址，其中，所述第四散列值从所述第二 OID和所述第二偏移得出。

从以下的描述和所附的权利要求，本发明的其它方面将十分清楚明了。

附图说明

图1示出根据本发明的一个或多个实施例的系统。

图2A示出根据本发明的一个或多个实施例的固态存储器模块。

图2B示出根据本发明的一个或多个实施例的块。

图2C示出根据本发明的一个或多个实施例的碎片页面。

图2D示出根据本发明的一个或多个实施例的内容表(TOC)页面。

图2E示出根据本发明的一个或多个实施例的块。

图2F示出根据本发明的一个或多个实施例的内容表(TOC)条目。

图2G示出根据本发明的一个或多个实施例的数据碎片。

图2H示出根据本发明的一个或多个实施例的元数据碎片。

图2I示出根据本发明的一个或多个实施例的复合碎片。

图3示出根据本发明的一个或多个实施例的对象和相应的TOC条目。

图4示出根据本发明的一个或多个实施例的用于实施单对象事务的流程图。

图5A-5C示出根据本发明的一个或多个实施例的用于实施多对象事务的流程 图。

图6A-6D示出根据本发明的一个或多个实施例的例子。

图7A-7D示出根据本发明的一个或多个实施例的例子。

具体实施方式

现在参照附图详细描述本发明的具体实施例。在本发明的实施例的以下详 细描述中，为了使得能够更彻底地理解本发明，阐述大量的特定细节。但是， 对于本领域技术人员来说，显然可以在没有这些具体细节的情况下实施本发 明。在其它情况下，为了避免使描述不必要地复杂化，没有详细地描述公知的 特征。

在图1～7D的以下描述中，在本发明的各种实施例中针对附图描述的任何 组件可以与针对任何其它附图描述的一个或更多个名称类似的组件等同。为了 简便起见，对这些组件的描述并不针对每个附图进行重复。因此，各附图的组 件的每一个实施例通过引用被加入，并且被假定为可选地存在于具有一个或更 多个名称类似的组件的每一个其它附图中。另外，根据本发明的各种实施例， 附图的组件的任何描述要被解释为可选实施例，该可选实施例的实施可以附加 于、结合于或者替代针对其他任意附图中相应的名称类似组件所描述的实施 例。

一般地，本发明的实施例涉及一种用于实现存储系统中的事务的方法和系 统。更具体而言，本发明的实施例使用事务对象来实现事务，其中，每个事务 仅要求更新的数据被一次写入到永久存储器。在本发明的一个实施例中，事务 可与单个对象(参见例如图4和6A-6D)或多个对象(参见例如图5A-5C和 7A-7D)相关联。此外，本发明的实施例允许数据的单个副本在所有中间状态 期间以及事务提交之后表示事务。

图1示出根据本发明的一个实施例的系统。如图1所示，该系统包括一个或 多个客户机(100)、存储控制器(102)、存储器(104)和存储阵列(106)。

在本发明的一个实施例中，客户机(100)是在包括向存储控制器(102) 发出读取请求、写入请求或提交请求(具有一个或多个事务对象)的功能的系 统上执行的任何系统或处理。在本发明的一个实施例中，每个客户机(100) 可包括处理器(未示出)、存储器(未示出)和永久存储器(未示出)。在本 发明的一个实施例中，存储控制器(102)可操作地连接到一个或多个客户机 (100)，并且被配置为实现事务对象方案，该事务对象方案包括以与下述事 务对象方案(参见例如图4-5C)一致的方式将内容表条目和碎片写入到存储阵 列。在本发明的一个实施例中，存储控制器(102)包括被配置为执行用于实 现本发明的一个或更多个实施例的指令的处理器(未示出)，这里，指令存储 于位于存储控制器(102)内或者与存储控制器(102)可操作地连接的非暂时 性计算机可读介质(未示出)上。作为替代方案，可通过使用硬件实现存储控 制器(102)。在不背离本发明的情况下，可通过使用软件和/或硬件的任意组 合实现存储控制器(102)。

在本发明的一个实施例中，存储控制器(102)与存储器(104)可操作地 连接。存储器(104)可以是任何易失性存储器，包括但不限于动态随机存储 器(DRAM)、同步DRAM、SDR SDRAM和DDR SDRAM。在本发明的一个 实施例中，存储器(104)被配置为在各种数据(包括关于内容表条目和碎片 的数据)被存储于存储阵列中之前暂时存储这些数据。

在本发明的一个实施例中，存储阵列(106)包括若干个单个的永久存储 设备，包括但不限于磁存储设备、光学存储设备、固态存储设备、相变存储设 备、任何其它适当类型的永久存储设备或它们的任意组合。

在不背离本发明的情况下，可使用除了图1所示的系统配置之外的系统配 置。

如上所述，存储阵列可包括固态存储设备。以下讨论描述使用固态存储设备实 现的本发明的实施例。现讨论图2A，图2A示出根据本发明的一个或多个实施例 的固态存储设备(未示出)的固态存储模块。固态存储设备(未示出)可包括多个 固态存储模块。固态存储模块(200)包括一个或多个块。在本发明的一个实施例 中，块是固态存储模块(200)内的最小的可擦除存储单元。

图2B示出根据本发明的一个或多个实施例的块。更具体而言，每个块(202) 包括一个或多个页面。在本发明的一个实施例中，页面是固态存储模块中的用于读 取和程序操作(包括对页面的初始写入)的最小可寻址单元。在本发明的一个实施 例中，重写块内的页面要求整个块被重写。在本发明的一个实施例中，块内的每个 页面或者是碎片页面(参见图2C)，或者是TOC页面(参见图2D)。

图2C示出根据本发明的一个或多个实施例的碎片页面。在本发明的一个实施 例中，碎片页面(204)包括一个或多个碎片。在本发明的一个或多个实施例中， 碎片对应于有限量的用户数据(或者如果碎片页面是元数据碎片(参见图2H)， 对应于元数据，或者如果碎片是复合碎片(参见图2I)，对应于TOC条目)。此 外，给定页面内的碎片可以是大小统一的或者大小不统一的。此外，给定块内的碎 片可以是大小统一的或者大小不统一的。在本发明的一个实施例中，给定碎片可以 小于页面的大小，可以正好是页面的大小，可以延伸遍及一个或多个页面。在本发 明的一个实施例中，碎片页面仅包括碎片。在本发明的一个实施例中，每个碎片包 括用户数据(即，由客户机提供以供存储于存储装置中的数据)(参见图2G)、 用于对象的元数据(参见图2H)，或者如果碎片是复合碎片(参见图2I)，包括 TOC条目。给定的碎片页面可包括单一类型的碎片或者两种或更多种类型的碎片。

图2D示出根据本发明的一个或多个实施例的TOC页面。在本发明的一个实 施例中，TOC页面(206)包括一个或多个TOC条目，其中，每个TOC条目包 括用于给定碎片的元数据。另外，TOC页面(206)可包括对块(202)中的另一 TOC页面的引用。在本发明的一个实施例中，TOC页面仅包括TOC条目(以及 可选地，对块中的另一TOC页面的引用)，但是不包括任何碎片。在本发明的一 个实施例中，每个TOC条目对应于块(202)中的碎片(参见图2C)。TOC条 目仅对应于块内的碎片。换句话说，TOC页面与块相关联，并且仅包括用于该块 中的碎片的TOC条目。在本发明的一个实施例中，每个固态存储器模块内的每个 块中无缺陷的最后一个页面是TOC页面。

图2E示出根据本发明的一个或多个实施例的块。更具体而言，图2E示出包 括TOC页面(210、212、214)和碎片页面(216、218、220、222、224、226) 的块(208)。在本发明的一个实施例中，块(208)在概念上从“顶部”到“底部”被 填充。此外，一旦用于碎片页面中的碎片的TOC条目的累积大小等于页面的大小， 就产生并且存储TOC页面。翻到图2E，例如，碎片页面0(216)和碎片页面1 (218)被存储于块(208)中。用于碎片页面0(216)和碎片页面1(218)中 的碎片(未示出)的相应的TOC条目(未示出)具有等于块中的页面的大小的总 累积大小。因此，产生TOC页面(212)(通过使用与块中的碎片相应的TOC条 目)，并且将该TOC页面(212)存储于块(208)中。随后将碎片页面2(220) 写入到块(208)。因为与碎片页面2(220)中的碎片(未示出)相应的TOC条 目具有等于块中的页面的大小的总累积大小，所以创建TOC页面(212)，并且 将该TOC页面(212)存储于块(208)中。此外，因为在块(208)中已经存在 TOC页面，所以TOC页面(212)还包括对TOC页面(214)的引用。

重复该处理，直到在块(208)中仅剩余一个要填充的页面。此刻，创建TOC 页面(210)，并且将该TOC页面(210)存储于块(208)的最后一个页面中。 本领域技术人员将意识到，TOC页面(210)中的TOC条目的总累积大小可能小 于该页面的大小。在这样的情况下，TOC页面可包括解决TOC条目的累积大小和 页面大小之间的差异的填充。最后，因为在块(208)中存在其它TOC页面，所 以TOC页面(210)包括对一个其它TOC页面(212)的引用。

如图2E所示，TOC页面从块的“底部”链接到页面的“顶部”，以使得TOC页面 可通过追随该TOC页面“下方”的TOC页面的引用而获得。例如，TOC页面(212) 可使用TOC页面(210)中的引用访问。

本领域技术人员将意识到，虽然块(208)仅包括碎片页面和TOC页面，但 是在不背离本发明的情况下，块(208)可包括除了碎片页面和TOC页面之外的 页面(例如，包括奇偶校验数据的页面)。这样的其它的页面可位于块内，并且根 据实际情况，交织在TOC页面和碎片页面之间。

图2F示出根据本发明的一个或多个实施例的TOC条目。在本发明的一个实 施例中，每个TOC条目(230)包括用于碎片的元数据，并且可包括以下字段中 的一个或多个：(i)对象ID(232)，其标识存储的对象；(ii)出生时间(234)， 其指定与TOC条目相应的碎片被写入到存储阵列的时间(例如，控制模块中的处 理器的处理器时钟值)；(iii)偏移ID(236)，其标识对象中的相对于该对象(由 对象ID标识)的起始点的点；(iv)碎块大小(238)，其指定碎片的大小；(v) 页面ID(240)，其标识块中的存储碎片的页面；(vi)字节(242)，其标识页 面(由页面ID标识)中的碎片的起始位置；(vii)逻辑长度(244)，其指定碎 片中的用户数据的未压缩长度；以及(viii)类型(246)，其指定碎片中的数据的 类型(例如，对象、复合碎片等)。在不背离本发明的情况下，TOC条目(230) 可包括其它字段(由其它(248)表示)。

在本发明的一个实施例中，<对象ID,偏移ID>或<对象ID,偏移ID,出生时 间>标识例如由客户机提供的数据。此外，<对象ID,偏移ID>或<对象ID,偏移 ID,出生时间>可被客户机用于标识特定数据，而存储装置使用物理地址来标识存 储装置内的数据。本领域技术人员将意识到，客户机可提供逻辑地址，而不是对象 ID和偏移ID。

本领域技术人员将意识到，在不背离本发明的情况下，TOC条目可包括比图 2F所示的字段更多或更少的字段。此外，在不背离本发明的情况下，TOC条目中 的字段可按不同次序布置和/或组合在一起。另外，虽然图2F所示的TOC条目中 的字段表现为全都为相同大小，但是TOC条目中的各字段的大小可以是不统一的， 其中，任何给定字段的大小基于TOC条目的实际情况而变化。

图2G示出根据本发明的一个或多个实施例的数据碎片。数据碎片(250)仅 包括来自客户机的数据。例如，数据碎片中的数据可对应于文件中的数据，而该文 件由对象ID标识。

图2H示出根据本发明的一个或多个实施例的元数据碎片。元数据碎片(252) 包括对象元数据，该对象元数据是用于与该元数据碎片相关联的TOC条目中的对 象ID相应的对象的。换句话说，用于该对象的元数据被存储于元数据碎片中，并 且与包括该对象的对象ID和偏移＝-1的TOC条目相关联。在不背离本发明的情况 下，可使用除了-1之外的值。对象元数据的例子可包括但不限于对象类型、其最 大大小、其创建时间、其最近的修改时间和其它的每一对象属性。在本发明的一个 实施例中，在存储阵列中存在用于每个对象的一个元数据碎片。

图2I示出根据本发明的一个或多个实施例的复合碎片。在本发明的一个实施 例中，与其它碎片不同的复合碎片(254)不包括来自客户机的数据或用于对象的 元数据；相反，复合碎片(254)包括两个或更多个TOC条目，其中，每个TOC 条目与事务对象相关联，并且具有偏移＝-1。在本发明的一个实施例中，复合碎片 中的TOC条目中所指定的所有事务对象都属于单个事务。

图3示出根据本发明的一个或多个实施例的对象(300)和相应的TOC条目。 更具体而言，图3示出根据本发明的一个或多个实施例的对象和相应的TOC条目 的概念图。如图3所示，对象(300)包括位于偏移-1处的元数据碎片，该元数据 碎片包括用于该对象的元数据。此外，该对象包括位于偏移3和6处的两条数据 (存储于一个或多个碎片页面(未示出)中)。前述每个碎片与TOC条目(存储 于一个或多个TOC页面(未示出)中)相关联。

图4-5C示出根据本发明的一个或多个实施例的流程图。虽然流程图中的各步 骤被顺序地呈现和描述，但是普通技术人员将意识到，这些步骤中的一些或全部可 按不同次序执行，可被组合或省略，并且这些步骤中的一些或全部可并行执行。在 本发明的一个实施例中，在不背离本发明的情况下，图4-5C所示的步骤可与图 4-5C所示的任何其它步骤并行实施。

现讨论图4，图4示出根据本发明的一个或多个实施例的用于实施单对象事务 的流程图。在步骤400中，存储控制器接收对事务的请求，其中，该请求指定父 对象。父对象对应于将对其实施事务的对象。(参见例如图6A，父对象是具有对 象ID＝A的对象)。

在步骤402中，为事务创建事务对象。创建事务对象可包括为事务指定对象 ID。在步骤404中，为事务对象创建元数据(MD)碎片。元数据碎片可包括事务 对象ID(TOI)、父对象的对象ID以及指示事务未被提交的字段。元数据碎片还 可包括用于事务对象的其它元数据。

在步骤406中，为元数据碎片创建内容表(TOC)条目(被称为MD TE)。 MD TE包括TOI和偏移＝-1。在不背离本发明的情况下，MD TE可包括其它信息。 在步骤408中，随后将MD碎片和MD TE存储于存储阵列中。在本发明的一个实 施例中，MD碎片作为碎片页面的一部分存储于存储阵列中，MD TE作为TOC页 面的一部分存储于存储阵列中。写入前述碎片、TE和页面的时序可基于如何实现 本发明的实施例而变化。

在步骤410中，将TOI提供给发起事务的客户机。在不背离本发明的情况下， 可将TOI提供给参与事务的其它客户机。在步骤412中，接收将数据作为事务的 一部分写入的写入请求。写入请求包括TOI和偏移。

在步骤414中，将具有写入请求中所标识的数据的数据碎片存储于存储阵列 中(通常作为碎片页面的一部分)。在步骤416中，创建用于数据碎片(其在步 骤414中被存储)的TE，并且将该TE存储于存储阵列中(通常作为TOC页面 的一部分)。用于数据碎片的TE包括TOI和偏移。TE不包括父对象的对象ID。

在步骤418中，更新存储器内数据结构以包括下述条目，该条目包括(i)从 TOI和偏移得出的散列值；以及(ii)在步骤414中存储的数据碎片的物理地址。 在本发明的一个实施例中，可通过将函数(例如，MD5、SHA1等)应用于<TOI,偏 移>(或使用TOI和偏移产生的值)来得出散列值。本领域技术人员将意识到，在 不背离本发明的情况下，可使用任何内射函数。回到图4，在这个阶段，存储控制 器可处理包括TOI和偏移的读取请求以及包括父对象的对象ID和偏移的读取请 求。服务于前述读取请求的结果通常将导致获得两个不同的数据——一个对应于 <TOI,偏移>，一个对应于<父对象ID,偏移>，其中，偏移是相同的。

在步骤420中，确定是否存在另外的对事务的写入请求。如果存在另外的对 事务的写入请求，则所述处理进入步骤412；否则，所述处理进入步骤422。在步 骤422中，从客户机接收指定TOI的提交请求。在步骤424中，为事务对象创建 第二MD碎片，该第二MD碎片包括事务对象ID(TOI)、父对象的对象ID以及 指示事务被提交的字段。

在步骤426中，创建第二MD TE，其中，第二MD TE包括TOI和偏移＝-1。 当存储阵列和/或存储控制器实现写入时拷贝方案时，实施步骤424和426。如果 存储阵列和/或存储控制器不实现写入时拷贝方案，则可以不实施步骤424和426； 相反，可分别更新在步骤404和406中创建的MD TE和MD碎片以包括与在步骤 424和426中创建的MD TE和MD碎片相同的信息。

在步骤428中，将第二MD碎片存储于存储阵列中(通常存储于碎片页面中)， 并且将第二MD TE存储于存储阵列中(通常存储于TOC页面中)。在步骤430 中，更新所述存储器内数据结构以反映事务被提交。具体而言，在本发明的一个实 施例中，更新包括从父对象ID和偏移得出的散列值的条目以包括数据的物理地址， 其中，该物理地址先前已存在于包括TOI和偏移的另一条目(即，在步骤418中 创建的条目)中。如果在事务中接收并且处理多于一个的写入请求(参见步骤 412-420)，则更新所述存储器内数据结构中的多个条目。在这个阶段，控制器可 服务于使用<父对象ID,偏移>的读取请求，但是不能服务于指定TOI的任何请求。 此外，当在步骤412中接收到包括<父对象ID,偏移>的读取请求(其中，偏移对 应于在写入请求中接收的偏移)时，结果是在步骤414中存储于数据碎片中的数 据。

现讨论图5A-5C，图5A-5C示出根据本发明的一个或多个实施例的用于实施 多对象事务的流程图。在本发明的一个实施例中，图5A-5C示出用于实现与多个 对象相关的事务的方法，其中，每个对象与它自己的事务对象相关联。如下所述， 每个对象和相应的事务对象可独立于任何其它的对象和相应的事务对象进行操作， 直到整个事务(其包括多个对象)被提交为止。因此，在下面的讨论中，“事务”可 以指的是涉及单个事务对象的事务或涉及多个事务对象的事务。

现讨论图5A，在步骤500中，存储控制器接收对事务的请求，其中，该请求 指定父对象。父对象对应于将对其实施事务的对象。(参见例如图7A，父对象是 具有对象ID＝A的对象)。在步骤502中，为事务创建事务对象。创建事务对象可 包括指定事务的对象ID。在步骤504中，为事务对象创建元数据(MD)碎片。元 数据碎片可包括事务对象ID(TOI)、父对象的对象ID以及指示事务未被提交的 字段。元数据碎片还可包括用于事务对象的其它元数据。

在步骤506中，为元数据碎片创建内容表(TOC)条目(被称为MD TE)。 MD TE包括TOI和偏移＝-1。在不背离本发明的情况下，MD TE可包括其它信息。 在步骤508中，随后将MD碎片和MD TE存储于存储阵列中。在本发明的一个实 施例中，将MD碎片作为碎片页面的一部分存储于存储阵列中，并且将MD TE作 为TOC页面的一部分存储于存储阵列中。前述碎片、TE和页面的写入时序可基 于如何实现本发明的实施例而变化。

在步骤510中，将TOI提供给发起事务的客户机。在不背离本发明的情况下， 可将TOI提供给参与事务的其它客户机。在步骤512中，确定是否存在另外的要 创建的事务。如果是，则所述处理进入步骤502；否则，所述处理进入步骤514。 在步骤514中，接收将数据作为事务之一的一部分写入的写入请求。写入请求包 括TOI和偏移。TOI可对应于在步骤502的迭代期间创建的任何TOI。在步骤516 中，将具有写入请求中所标识的数据的数据碎片存储于存储阵列中的数据碎片中 (通常作为碎片页面的一部分)。在步骤518中，创建用于数据碎片(其在步骤 516中被存储)的TE，并且将该TE存储于存储阵列中(通常作为TOC页面的一 部分)。用于数据碎片的TE包括TOI和偏移。TE不包括父对象的对象ID。

在步骤520中，更新存储器内数据结构以包括下述条目，该条目包括(i)从 TOI和偏移得出(如以上在图4中所讨论的那样)的散列值以及(ii)在步骤516 中存储的数据碎片的物理地址。在这个阶段，存储控制器可处理包括TOI和偏移 的读取请求以及包括父对象的对象ID和偏移的读取请求。服务前述读取请求的结 果通常将导致获得两个不同的数据——一个对应于<TOI,偏移>，一个对应于<父 对象ID,偏移>，其中，偏移是相同的。在步骤522中，确定是否存在另外的对任 何事务的请求(即，指定在步骤502的任何迭代期间创建的TOI之一的写入请求)。 如果存在另外的对任何事务的写入请求，则所述处理进入步骤514；否则，所述处 理进入步骤524。

在步骤524中，从客户机接收指定两个或更多个TOI的提交请求。TOI对应 于在步骤502中创建的事务。在步骤526中，为每个事务对象(即，与在步骤502 中创建的事务相应的事务对象)创建第二MD碎片，第二MD碎片包括相应的事 务对象ID(TOI)、父对象的相应的对象ID以及指示事务被提交的字段。另外， 为前述每个第二MD碎片创建第二MD TE，其中，第二MD TE包括相应的TOI 和偏移＝-1。当存储阵列和/或存储控制器实现写入时拷贝方案时，实施步骤526。 如果存储阵列和/或存储控制器不实现写入时拷贝方案，则可以不实施步骤526； 相反，可分别更新在步骤504和506中创建的MD TE和MD碎片以包括与在步骤 424和426中创建的MD TE和MD碎片相同的信息。

在步骤528中，创建复合碎片，其中，该复合碎片与复合对象相关联，并且 包括在步骤526中创建的MD TE。在步骤530中，创建用于复合碎片的TE。用 于复合碎片的TE包括复合碎片的对象ID和偏移＝-1。用于复合碎片的TE还可指 示复合TE所引用的碎片是复合碎片。在步骤532中，将复合碎片、用于复合碎片 的TE和MD碎片(其在步骤526中创建)存储于存储阵列中。复合碎片和MD碎 片被存储于一个或多个碎片页面中，用于复合碎片的TE被存储于TOC页面中。 在本发明的一个实施例中，复合碎片的存储暗含地指示复合碎片中所指定的所有事 务(经由事务对象ID)已经被提交。

在步骤534中，更新所述存储器内数据结构以反映事务被提交。具体而言， 在本发明的一个实施例中，通过以上用于图4中的步骤430所讨论的方式更新所 述存储器内数据结构中的多个条目。

图6A-6D示出根据本发明的一个或多个实施例的例子。该例子并非意图限制 本发明的范围。

参照图6A，考虑在存储阵列中存在具有对象ID＝A的对象的情况。更具体而 言，存在用于该对象的MD TOC条目和用于该对象的相应的MD碎片，其中，MD 碎片可经由散列<A,-1>访问。此外，存在包括用于该对象的数据的数据碎片(数据 碎片B)，其中，该数据与<A,3>相关联。前述对象ID和偏移被存储于存储阵列 中的相应的数据TE(数据TOC条目B)中。在这个阶段，在存储阵列中存在四个 项，在存储器内数据结构中存在两个条目。存储器内数据结构中的每个条目指向前 述碎片之一。

参照图6B，考虑客户机请求指定对象ID＝B的事务的情况。在该情况下，创 建MD碎片(元数据碎片C)，并且将该MD碎片存储于存储阵列中，其中，该 MD碎片指定，事务对象ID＝B，对象B的类型是事务，父对象ID＝A，该事务未被 提交。还创建相应的MD TE(元数据TOC条目C)，并且将该MD TE存储于存 储阵列中，其中，该MD TE指定对象ID＝B以及偏移＝-1。还创建用于元数据碎片 C的相应条目，并且将该条目存储于存储器内数据结构中。

参照图6C，考虑随后接收并且处理对事务的写入请求的情况。服务写入请求 的结果是具有数据(Data’)的数据碎片D和相应的数据TE(数据TOC条目D)， 该数据TE指定对象ID＝B以及偏移＝3。还创建用于数据碎片D的相应条目，并且 将该条目存储于存储器内数据结构中。在这个阶段，存储阵列中的四个项可经由存 储器内数据结构中的相应条目访问。

参照图6D，在写入请求被接收并且如以上关于图6C所描述的那样被处理之 后，假定接收到包括对象ID＝B的提交请求。在这个阶段，事务被提交。如例子所 示的提交事务可包括(i)更新或创建新的元数据碎片C，该元数据碎片C指定与 对象ID＝B相应的事务被提交；(ii)使数据碎片B和数据TOC条目B无效；(iii) 更新存储器内数据结构以将散列<A,3>与数据碎片D的物理地址相关联。

图7A-7D示出根据本发明的一个或多个实施例的例子。该例子并非意图限制 本发明的范围。

考虑存在两个事务的情况，其中，一个与以下事务对象——对象ID＝B和对象 ID＝D中的每个相关联。此外，假定与对象ID＝B相关联的事务的父对象ID是对象 ID＝A，与对象ID＝D相关联的事务的父对象ID是对象ID＝C。最后，假定存在与 对象ID＝A和对象ID＝C中的每个相关联的数据(为数据碎片的形式)。图7A示 出基于以上假定的存储阵列的内容。此外，图7B示出基于以上假定的存储器内数 据结构的内容。

假定为前述事务中的每个服务于写入请求，导致两个另外的数据TE(数据 TOC条目B和数据TOC条目D)和两个另外的数据碎片(数据碎片B和数据碎 片D)被存储于存储阵列中，其中，数据碎片B与和数据碎片A相同的偏移相关 联，数据碎片D与和数据碎片C相同的偏移相关联。另外，假定在两个写入请求 都已经被服务之后，接收到指定对象ID＝B和对象ID＝D的提交请求。随后通过创 建复合碎片和相应的MD TE(元数据TOC条目E)并且将它们存储于存储阵列中 来服务于提交请求。最后，在存储阵列中使数据碎片A、数据TOC条目A、数据 碎片C和数据TOC条目C无效；使存储器内数据结构中的相应的散列条目失效。 图7C示出基于以上假定的存储阵列的内容。此外，图7D示出基于以上假定的存 储器内数据结构的内容。

在本发明的一个实施例中，可通过在所有的元数据TOC条目和相应的碎片 (即，元数据碎片或复合碎片)中读取来产生初始的存储器内数据结构。一旦获得 了该数据，存储控制器(或相关处理)就将能够通过查阅元数据碎片和复合碎片中 的信息以重新产生存储器内数据结构的最后状态来“重放(replay)”事务。具体而 言，如果给定的MD碎片指示对象是事务(或事务对象)并且该事务未被提交， 则不使用与该事务相关联的数据碎片(即，与指定事务对象ID的TE相应的数据 碎片)来创建存储器内数据结构中的条目。此外，当复合碎片被标识时，存储控制 器(或相关处理)递归地处理复合碎片中的元数据TE。

在本发明的一个实施例中，存储器内数据结构是在对存储于固态存储器模块中 的任何数据实施任何操作(例如，读取操作、写入操作和/或擦除操作)之前产生。

本领域的技术人员将意识到，虽然已经用于每个块中的被保留作为TOC页面 的最后一个页面描述了本发明，但是在不背离本发明的情况下，可通过将块中的另 一页面设置为保留的TOC页面来实现本发明的实施例。

虽然已经关于固态存储器设备上的实现描述了本发明的实施例，但是在不背离 本发明的情况下，可使用其它类型的存储设备来实现本发明的实施例。

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

虽然已经关于有限数量的实施例描述了本发明，但是得益于本公开的本领域技 术人员将意识到，可设计出不背离如本文中所公开的本发明的范围的其它实施例。 因此，本发明的范围应仅由所附权利要求限制。