# US 9,436,561 B2 · Recovery processing using torn write detection

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 9,436,561 B2
- Document ID: US9436561B2
- Status: Granted
- Kind: B2
- Application number: 13/892,124
- Filed: 2013-05-10
- Published: 2014-10-02
- Granted: 2016-09-06
- Earliest claimed: 2013-03-28
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Per-Ake Larson; Robert Patrick Fitzgerald; Cristian Diaconu; Michael James Zwilling
- Web page: https://patentgrep.com/patent/US9436561B2

## CPC

- G06F 11/1471: involving logging of persistent data for recovery
- G06F 9/466: {Transaction processing}
- G06F 9/467: {Transactional memory (G06F9/528 takes precedence)}
- G06F 11/1458: {Management of the backup or restore process}
- G06F 11/1469: {Backup restoration techniques}
- G06F 16/1873: {Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files}
- G06F 16/219: {Managing data history or versioning (querying versioned data G06F16/2474; querying temporal data G06F16/2477)}
- G06F 16/2322: {using timestamps}
- G06F 16/2329: {using versioning}
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/2379: {Updates performed during online database operations; commit processing}
- G06F 11/1438: {Restarting or rejuvenating}
- G06F 2201/84: Using snapshots, i.e. a logical point-in-time copy of the data
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The recovery of a transaction, and perhaps the recovery of multiple transactions, in a computing system in which one or more persistent systems are coupled via a bus to one or more processors. As an example, the persistent system may serve as part of the main memory of the computing system. The transaction might implement multi-versioning in which a record is not updated in place. Rather, each record is represented as a sequence of one or more record versions, each version having a valid interval during which that the record version is considered to properly represent the record. Torn write guards may be used to verify that there are no torn writes in the record versions or in the log buffer associated with the transaction.

## Claims

### Claim 1

A recovery method implemented by a computing system that includes a persistent system coupled to one or more processors via a bus, the method comprising:
an act of accessing from a log buffer a transaction-level torn-write guard associated with post-commit processing information associated with a transaction, the transaction-level torn-write guard comprising at least one of a checksum of the log buffer or a bitmap associated with predetermined pattern written to the log buffer;
an act of verifying that the post-commit processing information contains no torn writes using the transaction-level torn-write guard accessed from the log buffer;
in response to the act of verifying, an act of performing the following for each of at least one record version of the record versions created by the transaction:
an act of identifying the at least one record version created by the transaction using the post-commit processing information;
an act of finding a record-version-level torn-write guard included within the log buffer associated with the at least one record version, the record-version torn-write guard comprising at least one of a checksum of the at least one record version or a bitmap associated with a predetermined pattern written to the at least one record version; and
an act of using the corresponding record-version-level torn-write guard from the log buffer to confirm whether or not the corresponding record version has no torn writes.

### Claim 2 (depends on 1)

The recovery method in accordance with claim 1, wherein for each of the at least some of the record versions created by the transaction, the act of using the corresponding record-version-level torn-write guard results in a confirmation that each of the at least some record versions have no torn writes.

### Claim 3 (depends on 1)

The recovery method in accordance with claim 1, further comprising the following for each record version updated by the transaction:
an act of modifying the corresponding updated record version to show that it is invalid after a commit time of the transaction.

### Claim 4 (depends on 3)

The recovery method in accordance with claim 3, wherein the corresponding updated record version is modified by setting a valid interval end boundary of the corresponding updated record version equal to a commit marker associated with the transaction.

### Claim 5 (depends on 3)

The recovery method in accordance with claim 3, further comprising:
an act of providing at least modifications to the updated record versions to a persistent system.

### Claim 6 (depends on 3)

The recovery method in accordance with claim 3, further comprising the following for each record version created by the transaction:
an act of modifying the corresponding created record version to show that it is valid after the commit time of the transaction.

### Claim 7 (depends on 6)

The recovery method in accordance with claim 6, wherein the corresponding created record version is modified by setting a valid interval begin boundary of the corresponding created record version equal to a commit marker associated with the transaction.

### Claim 8 (depends on 6)

The recovery method in accordance with claim 6, further comprising:
an act of providing at least modifications to the created record versions to the persistent system.

### Claim 9 (depends on 8)

The recovery method in accordance with claim 8, further comprising:
an act of confirming that the modifications to the updated and created record versions have been persisted in the persistent system.

### Claim 10 (depends on 1)

The method in accordance with claim 1, wherein the computing system responds to a confirmation that a log buffer has torn writes by at least undoing a transaction associated with the log buffer.

### Claim 11 (depends on 1)

The method in accordance with claim 1, wherein the computing system responds to a confirmation that a log buffer does not have torn writes by at least performing the following for each of at least some of the record versions created by the corresponding transaction:
an act of identifying the corresponding record version created by the transaction using contents of the log buffer;
an act of finding a record-version-level torn-write guard associated with the corresponding record version in the log buffer; and
an act of using the corresponding record-version-level torn-write guard to determine whether or not the corresponding record version has any torn writes.

### Claim 12 (depends on 11)

The method in accordance with claim 11, wherein the computing system responds to a confirmation that a record version of a log buffer associated with a transaction has torn writes by at least undoing a transaction associated with the log buffer.

### Claim 13 (depends on 11)

The method in accordance with claim 11, wherein the computing system responds to a confirmation that there are no record versions of a log buffer associated with a transaction that has torn writes by performing the following for each record version updated by the transaction:
an act of modifying the corresponding updated record version to show that it is invalid after a commit time of the transaction; and
an act of providing at least modifications to the updated record versions to a persistent system.

### Claim 14 (depends on 13)

The method in accordance with claim 13, wherein the computing system responds to a confirmation that there are no record versions of a log buffer associated with a transaction that has torn writes by performing the following for each record version created by the transaction:
an act of modifying the corresponding created record version to show that it is valid after a commit time of the transaction; and
an act of providing at least modifications to the created record versions to a persistent system.

### Claim 15 (depends on 13)

The method in accordance with claim 13, wherein the computing system responds to a confirmation that there are no record versions of a log buffer associated with a transaction that has torn writes by performing the following:
an act of confirming that the modifications to the updated and created record versions have been persisted in the persistent system.

### Claim 16 (depends on 15)

The method in accordance with claim 15, wherein the computing system responds to a confirmation that the modifications to the updated and created record versions have been persisted in the persistent system by performing the following:
an act of cleaning up garbage and rebuilding the indexes of a database.

### Claim 17 (depends on 16)

The method in accordance with claim 16, further comprising the following for each of at least some memory portions corresponding to a database in the persistent system:
an act of accessing a valid interval begin boundary for the memory portion;
an act of using the valid interval begin boundary to identify that the memory portion contains at least a portion of a record version that is not part of a transaction; and
an act of adding the memory portion to a free list of the persistent memory.

### Claim 18 (depends on 16)

The method in accordance with claim 16, wherein the act of rebuilding indexes comprises the following for each of at least some portions corresponding to a database in the persistent system:
an act of accessing a valid interval begin boundary for the memory portion;
an act of using the valid interval begin boundary to identify that the memory portion contains at least a portion of a record version that part of an uncommitted transaction;
an act of modifying the memory portion so that the record version is no longer part of the uncommitted transaction; and
an act of adding the memory portion to a free list of the persistent memory.

### Claim 19 (depends on 16)

The method in accordance with claim 16, wherein the act of rebuilding indexes comprises the following for each of at least some portions corresponding to a database in the persistent system:
an act of accessing a valid interval begin boundary for the memory portion;
an act of using the valid interval begin boundary to identify that the memory portion contains at least a portion of a record version that is part of a committed transaction; and
an act of accessing a valid interval end boundary for the memory portion.

### Claim 20 (depends on 19)

The method in accordance with claim 19, the method further comprising:
an act of using the valid interface end boundary for the memory portion to identify that the memory portion includes at least a portion of a particular record version that is current; and
an act of identifying which table of the database the current record version belongs to; and
an act of adding the current record version to the identified table of one or more indexes of the identified table.

### Claim 21 (depends on 19)

The method in accordance with claim 19, the method further comprising:
an act of using the valid interface end boundary for the memory portion to identify that the memory portion includes at least a portion of a particular record version; and
an act of identifying that the particular record version belongs to an uncommitted transaction that attempted to delete the particular record version;
an act of modifying the memory portion so that the particular record version is no longer part of the uncommitted transaction;
an act of identifying which table of the database the particular record version belongs to; and
an act of adding the particular record version to the identified table of one or more indexes of the identified table.

### Claim 22 (depends on 19)

The method in accordance with claim 19, the method further comprising:
an act of using the valid interface end boundary for the memory portion to identify that the memory portion includes at least a portion of a record version deleted by a committed transaction; and
an act of adding the memory portion to a free list of the persistent memory.

### Claim 23

A system comprising:
one or more processors:
a persistent system;
a bus coupling the one or more processors to the persistent system; and
a recovery system configured to communicate with the persistent system over the bus to perform a recovery by performing the following acts:
an act of accessing from a log buffer a transaction-level torn-write guard associated with post-commit processing information associated with a transaction, the transaction-level torn-write guard comprising at least one of a checksum of the log buffer or a bitmap associated with predetermined pattern written to the log buffer;
an act of verifying that the post-commit processing information contains no torn writes using the transaction-level torn-write guard accessed from the log buffer;
in response to the act of verifying that the post-commit processing information contains no torn writes, an act of performing the following for each of at least one record version of the record versions created by the transaction:
an act of identifying the at least one record version created by the transaction using the post-commit processing information;
an act of finding a record-version-level torn-write guard included within the log buffer associated with the at least one record version, the record-version torn-write guard comprising at least one of a checksum of the at least one record version or a bitmap associated with a predetermined pattern written to the at least one record version; and
an act of using the corresponding record-version-level torn-write guard from the log buffer to confirm whether or not the corresponding record version has no torn writes.

### Claim 24 (depends on 23)

The system of claim 23, wherein the recovery system is configured to verify that the post-commit processing information contains no torn writes by at least comparing the checksum to a newly computed checksum of the log buffer or by at least checking for one or more atomic units in the log buffer that contain the predetermined pattern.