SHARED LOG-STRUCTURED MULTI-VERSION TRANSACTIONAL DATASTORE WITH METADATA TO ENABLE MELDING TREES

• US 20120011106A1
• Filed: 07/07/2010
• Published: 01/12/2012
• Est. Priority Date: 07/07/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Reid, Colin W., Bernstein, Pilip A.
• Granted Patent: US 8,412,689 B2
• Time in Patent Office: Days
• US Class Current: 707/695
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 9/466 Transaction processing

Abstract

Architecture that includes an ordered and shared log of indexed transaction records represented as multi-version data structures of nodes and node pointers. The log is a sole monolithic source of datastore state and is used for enforcing concurrency control. The architecture also includes a transaction processing component that appends transaction records to the log from concurrent transactions executing on different processors. Each node of a record is assigned a log address.

Claims

1. A computer-implemented concurrency control system having one or more computer readable media that store executable instructions executed by a processor, comprising:

an ordered and shared log of indexed transaction records represented as multi-version data structures of nodes and node pointers, the log is a sole monolithic source of datastore state and is used for enforcing concurrency control; and

a transaction processing component that appends transaction records to the log from concurrent transactions executing on different processors, each node of a record is assigned a log address.

2. The system of claim 1, wherein the record includes a dependency that is stored in the log as a log address.

3. The system of claim 1, wherein the node of the record is associated with versioned content, the versioned content identified in the log by a log address.

4. The system of claim 1, wherein the log includes a data structure having a deleted child node, the deleted child node represented by an annotation to a parent node.

5. The system of claim 1, wherein the log stores an oldest reachable node associated with a given node.

6. The system of claim 1, wherein each node is annotated with metadata, the metadata stored in association with a pointer to a node.

7. The system of claim 1, wherein the transaction records include an intention record having an assigned base location value, the intention record having nodes where each node is referenced according to its offset from the base location value.

8. The system of claim 1, wherein the transaction records include intention records that reference other intention records using far pointers, the transaction processing component stores one physical far pointer for an intention record and references to other pointers of the intention record are redirected via the physical far pointer.

9. The system of claim 1, wherein the transaction records in the log are assigned sequence numbers for an order in which the records commit, the commit of a record based on a count of nodes in the record and a sequence number of a previously committed transaction record.

10. A computer-implemented concurrency control system having one or more computer readable media that store executable instructions executed by a processor, comprising:

an ordered and shared log of indexed transaction records represented as multi-version data structures of nodes and node pointers, the log is a sole monolithic source of datastore state and is used for enforcing concurrency control; and

a transaction processing component that appends transaction records to the log from concurrent transactions executing on different processors, each node of a record is assigned a log address, a node dependency is stored in the log as a log address, and a node of the record is associated with versioned content identified in the log by a log address.

11. The system of claim 10, wherein the log includes a data structure having a deleted child node, the deleted child node represented by an annotation to a parent node, and stores an oldest reachable node associated with a given node.

12. The system of claim 10, wherein each node is annotated with metadata, the metadata stored in association with a pointer to a node.

13. The system of claim 10, wherein the concurrent transaction records include an intention record having an assigned base location value, the intention record having nodes where each node is addressed according to its offset from the base location value.

14. The system of claim 10, wherein the transaction records include intention records that reference other records using far pointers, the transaction processing component stores one physical far pointer for an intention record and references to other pointers of the intention record are redirected via the physical far pointer.

15. A computer-implemented concurrency control method executed via a processor, comprising:

storing transaction records as a monolithic index in an ordered and shared log;

representing the records as data structures having nodes and node dependencies;

tracking the nodes and node dependencies in the log using log addresses; and

concurrently appending the records into the log at distinct log addresses.

16. The method of claim 15, further comprising storing versioned content of a node in the log at a log address.

17. The method of claim 15, further comprising denoting node deletion of a record according to an annotated parent node.

18. The method of claim 15, further comprising annotating a node with metadata and storing the metadata on a pointer.

19. The method of claim 15, further comprising referencing records in the log based on log addresses offset from a prior log address.

20. The method of claim 15, further comprising storing in the log an oldest reachable node associated with a node.