Cyclic commit transaction protocol

Patent metadata

Field	Value
Publication number	US-9836362-B2
Application number	US-201615385486-A
Country	US
Kind code	B2
Filing date	Dec 20, 2016
Priority date	Oct 24, 2008
Publication date	Dec 5, 2017
Grant date	Dec 5, 2017

Abstract

A machine-implemented method includes automatically determining that a host device is restarting from a disruptive stoppage of operations and that in-process write transactions by the host device to respective pages of non-volatile storage may have been interrupted. The method includes, in response to the determination, automatically scanning the non-volatile storage for all metadata-containing storage pages with respective identifications S(i) and having corresponding metadata relating each respective storage page S(i) to a corresponding data page P(j) and a corresponding version number V(k). The method includes automatically identifying scanned storage pages S(i) that have for their corresponding data page P(j) a most recent version number HV(k) and, in some cases, a secondmost recent version number. The method includes designating for expungement scanned storage pages S(i) that are not both of committed and having the more recent of the most recent and secondmost recent version number for their corresponding data structure page P(j).

First claim

We claim:

1. A machine-implemented method that recovers latest committed data within a non-volatile storage after disruptive stoppage of operations of a host device that is writing by way of write transactions to the non-volatile storage, the method comprising:
automatically determining that the host device has experienced and is restarting from a disruptive stoppage of operations and that in-process write transactions by the disrupted host device to respective pages of the non-volatile storage may have thereby been interrupted before completion;
in response to said determining that the host device has experienced a disruptive stoppage of operations, automatically scanning the non-volatile storage for all metadata-containing storage pages with respective identifications S(i) and having corresponding metadata relating each respective storage page S(i) to a corresponding data structure page P(j) and to a corresponding version number V(k) where i, j and k are variables, the respective storage pages S(i) also each having stored data that potentially constitutes latest valid data for the corresponding data structure page P(j) or obsolete or rubbed out data for the corresponding data structure page P(j);
automatically identifying those of the scanned storage pages S(i) that have for their corresponding data structure page P(j) a most recent version number HV(k) and additionally but not necessarily for each instance, a secondmost recent version number;
automatically tracing through the identified storage pages S(i) to further identify those with the most recent version number HV(k) that are uncommitted as opposed to being committed;
automatically designating for expungement those of the scanned storage pages S(i) that are not both of committed and having the more recent of the most recent and secondmost recent version number for their corresponding data structure page P(j);
beginning normal operations for the host device; and
after beginning the normal operations, expunging at least some of the storage pages S(i) that have been designated for expungement.

2. The method of claim 1 wherein:
said further identifying of the scan identified storage pages S(i) as being uncommitted as opposed to being committed includes automatically tracing through the respective metadata of the identified storage pages S(i) so as to thereby detect respective closures or nonclosures of one or more linked lists defined by the metadata for corresponding write intentions for the respective data structure pages P(j) of the disrupted host device, where a closure indicates commitment and nonclosure indicates lack of commitment.

3. The method of claim 2 wherein:
the traced-through respective metadata of the identified storage pages S(i) each respectively includes an identifier of the data structure page P(j) associated with the stored data of the storage page S(i), an identifier of the corresponding version number V(k) of the stored data and an identifier of the data structure page NP(m) associated with the stored data of a next storage page S(i+1) in the corresponding linked list of write intentions, where m is a variable.

4. The method of claim 3 wherein:
the traced-through respective metadata of the identified storage pages S(i) each respectively further includes an identifier of the corresponding version number NV(n) of the stored data of a next storage page S(i+1), where n is a variable.

5. The method of claim 1 wherein:
said non-volatile storage includes a solid state disk (SSD).

6. The method of claim 1 wherein:
said disruptive stoppage of operations of the host device is due to a hardware failure.

7. The method of claim 6 wherein:
said disruptive stoppage of operations of the host device is due to a power failure.

8. The method of claim 1 wherein:
said determining that the host device has experienced and is restarting from a disruptive stoppage of operations occurs before resumption of the normal operations for the host device.

9. The method of claim 1 wherein:
expungement of the designated storage pages S(i) includes erasing blocks of storage pages.

10. The method of claim 1 wherein:
said beginning of normal operations is characterized by launching or resuming one or more applications whose respective launches or resumptions do not include immediate employment of write transactions to the non-volatile storage such that substantial completion of said expunging of at least some of the storage pages S(i) after the beginning of the normal operations can be achieved before the launched or resumed applications begin employing write transactions to the non-volatile storage.

11. The method of claim 1 wherein:
said expunging of the at least some of the storage pages S(i) after the beginning of the normal operations is accompanied by monitoring the write transactions of applications launched or resumed with the beginning of normal operations for inclusion of restricted intentions, said restricted intentions being ones that identify as their corresponding data structure page P(j) and associated version number V(k) a same data structure page as identified by a to-be expunged storage page S(i) and a same as or more recent version number V(k) than the version number of the to-be expunged storage page S(i).

12. The method of claim 1 wherein:
said expunging of the at least some of the storage pages S(i) after the beginning of the normal operations is preceded by production of an abort record, said abort record identifying all the to-be expunged storage pages S(i) and blocking reading from those to-be expunged storage pages S(i) because the latter are intention violations.

13. The method of claim 1 wherein the beginning of the normal operations includes:
recording as a last committed version number the intention version number for each storage page S(i) referenced by an intention within a closed cycle of intentions; and determining straddle responsibilities for top level versions.

14. The method of claim 13 and further comprising:
starting a garbage collection operation that is responsive to the determined straddle responsibilities.

15. The method of claim 1 and further comprising:
automatically building a remap table based on said tracing through the identified storage pages S(i).

16. A machine system configured to recover latest committed data within a non-volatile storage thereof after disruptive stoppage of operations of a host device of the system that is writing by way of write transactions to the non-volatile storage, the machine system comprising:
volatile memory;
an operations resuming mechanism configured to automatically determine that the host device has experienced and is restarting from a disruptive stoppage of operations and that in-process write transactions by the disrupted host device to respective pages of the non-volatile storage may have thereby been interrupted before completion;
a scanning mechanism responsive to determining that the host device has experienced a disruptive stoppage of operations and is restarting from a disruptive stoppage of operations, the scanning mechanism being configured to responsively and automatically scan the non-volatile storage for all metadata-containing storage pages with respective identifications S(i) and having corresponding metadata relating each respective storage page S(i) to a corresponding data structure page P(j) and to a corresponding version number V(k) where i, j and k are variables, the respective storage pages S(i) also each having stored data that potentially constitutes latest valid data for the corresponding data structure pa

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Prabhakaran Vijayan
• Zhou Lidong
• Rodeheffer Thomas Lee

Classifications

• G06F3/0659

  Command handling arrangements, e.g. command buffers, queues, command scheduling · CPC title

• G06F11/1474 Primary

  in transactions (updating of structured data in databases G06F16/23) · CPC title

• G06F3/0685

  Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays · CPC title

• G06F11/1471

  involving logging of persistent data for recovery · CPC title

• G06F2201/805

  Real-time · CPC title