Cyclic commit transaction protocol

Patent metadata

Field	Value
Publication number	US-9542431-B2
Application number	US-25778508-A
Country	US
Kind code	B2
Filing date	Oct 24, 2008
Priority date	Oct 24, 2008
Publication date	Jan 10, 2017
Grant date	Jan 10, 2017

Abstract

A cyclic commit protocol is used to store relationships between transactions and is used by the technology to determine whether a transaction is committed or not. The protocol allows creation of a cycle of transactions which can be used to recover the state of a storage device after a host failure by identifying the last committed version of intention records as committed or uncommitted based on the data stored in the physical pages.

First claim

We claim:

1. A method of managing storage of information to non-volatile storage where storage of such information can be interrupted before completion, the method comprising:
defining a series of to be completed write operations associated with a transaction, each write operation including a write intention that is part of a linked list including one or more write intentions;
writing data of the write operations in respective storage pages of a non-volatile storage media, each storage page including a data page and metadata, the metadata including an identification of at least a next write intention of the linked list where the linked list defines a closed transaction cycle, and
in response to a storage interruption, using the closure of the transaction cycle to indicate all write intentions of the closed transaction cycle are committed ones.

2. The method of claim 1 wherein the method further includes recovering a storage media state after one or more of to be completed write operations has been interrupted.

3. The method of claim 2 wherein each intention represents an intended update to a storage page;
said step of recovering the storage media state includes identifying a last committed intention for each page; and
indicating that any intention superseded by a later version of a same committed intention to each same page may be garbage collected.

4. The method of claim 1 wherein the step of writing data includes writing the metadata so as to identify at least one of a next intention in a transaction and a last committed intention in the transaction.

5. The method of claim 1 further including a recovery method which determines a last version of a committed intention for each page and which expunges uncommitted intentions before resuming normal operation.

6. The method of claim 5 wherein the step of expunging comprises one or more of:
marking a page as invalid; altering the page to appear rubbed-out; or writing a record in a different location indicating that the transaction was aborted.

7. The method of claim 5 wherein
a new intention that conflicts with the said uncommitted intentions is restricted until the said uncommitted intentions are expunged.

8. The method of claim 5 wherein storage pages containing top-level uncommitted intentions are scheduled for priority in re-use.

9. The method of claim 1 wherein an in-progress transaction may be aborted without interfering with other in-progress transactions.

10. A method of managing storage of information on non-volatile storage, comprising:
writing a series of data write operations in a transaction, each write operation including a write intention, each intention defining a storage page of a non-volatile storage media, the storage page having a data structure, the data structure including a metadata portion identifying at least a next intention in a closed transaction cycle and a data page,
detecting closure of the transaction cycle and using the detected closure as an indication that all write intentions of the closed transaction cycle are committed;
determining whether a write operation is completed by determining whether the closed transaction cycle of intentions has completed; and
in response to one or more of a series of write operations being interrupted, using one or more closed transaction cycles for recovering a storage media state.

11. The method of claim 10 wherein the step of using one or more closed transaction cycles for recovering includes:
determining all intentions on a storage device are committed intentions except for intentions that belong to a transaction currently in progress and
said step of recovering storage device state include determining a last committed intention for each page; and
any intention superseded by a later committed intention to each same page may be garbage collected.

12. The method of claim 10 wherein the step of writing further includes writing metadata in the page identifying a last prior committed intention in the transaction cycle.

13. The method of claim 12 wherein each next intention is a subsequent version of a page and each last prior committed intention is a previous version of the page.

14. A method of managing storage of information to non-volatile storage, where storage of such information can be interrupted before completing, the method comprising:
defining a series of write operations in a transaction, each write operation including a write intention; and
writing data of the write operations in respective storage pages of a non-volatile storage media, each storage page including metadata identifying a next intention in a closed transaction cycle, the metadata also identifying a previous intention in the transaction cycle, each storage page further including page data,
in response to a storage interruption, detecting closure of the transaction cycle and using the detected closure as an indication that all write intentions of the closed transaction cycle are committed; and
determining whether a write operation completed by determining whether writing a closed cycle of intentions has completed.

15. The method of claim 14 wherein the metadata for each intention indicates a last prior committed intention for its page;
any uncommitted intention not part of an in-progress transaction may be garbage collected; and
the method further includes determining the last committed intention for each page.

16. The method of claim 15 wherein the step of determining includes determining whether a last committed intention comprises a version of a page with at least one intervening uncommitted intention created between a later evaluated version and a last committed version, the later evaluated version comprising a straddler;
assigning a designated straddler to the at least one uncommitted intention; and
maintaining a record of the designated straddler.

17. The method of claim 16 wherein any intention superseded by a later committed intention on a same page may be garbage collected provided it is not assigned as a designated straddler.

18. The method of claim 17 further including the step of releasing the designated straddler from its uncommitted intention when either:
a subsequent intention is committed on each same page as said uncommitted intention, or
when said uncommitted intention is expunged.

19. The method of claim 16 further including the step of recovering a storage media state when one or more of the series of write operations is interrupted, said recovering including
rebuilding top-level intention classifications;
rebuilding straddle responsibility sets; and
initializing a set of free pages.

20. The method of claim 15 wherein the step of writing further includes:
associating each update intention with a version number for a page;
linking intentions comprising a transaction into a cycle;
and step metadata includes the last committed version number of the page with each intention;
and the method further includes:
maintaining top level version classifications and straddle responsibility sets in volatile memory; and
freeing the page of any top-level uncommitted version not part of a current transaction and any non-top level version with an empty straddle responsibility set.

Assignees

• Prabhakaran Vijayan
• Zhou Lidong
• Rodeheffer Thomas Lee
• Microsoft Technology Licensing Llc

Inventors

• Prabhakaran Vijayan
• Zhou Lidong
• Rodeheffer Thomas Lee

Classifications

• G06F17/30371 Primary

  Physics · mapped topic

• G06F16/2365 Primary

  Ensuring data consistency and integrity · CPC title

• G06F2201/82

  Solving problems relating to consistency · CPC title

• G06F11/1471

  involving logging of persistent data for recovery · CPC title

• G06F3/0685

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