Index structure using atomic multiword update operations

• US 10,599,485 B2
• Filed: 06/08/2018
• Issued: 03/24/2020
• Est. Priority Date: 01/31/2018
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Levandoski, Justin J, Minhas, Umar Farooq, Larson, Per-Ake, Wang, Tianzheng, Arulraj, Joy James Prabhu
• Primary Examiner(s): Grullon, Francisco A
• Application Number:
  US16/003,568
• Publication Number:
  US 20190235933A1
• Time in Patent Office: 655 Days
• CPC Class Codes: G06F 12/0238 Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 2209/521 Atomic
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 9/30043 LOAD or STORE instructions; Clear instruction
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A computer implemented method includes receiving multiple requests to update a data structure stored in non-volatile memory (NVM) and applying an atomic multiword update to the data structure to arbitrate access to the NVM. In a further embodiment, a computer implemented method includes allocating a descriptor for a persistent multi-word compare-and-swap operation (PMwCAS), specifying targeted addresses of words to be modified, returning an error if one of the targeted addresses contains a value not equal to a corresponding compare value, executing the operation atomically if the targeted addresses contain values that match the corresponding compare values, and aborting the operation responsive to the returned error.

Claims

1. A computer implemented method comprising:

receiving multiple requests to update a data structure stored in non-volatile memory (NVM); and

applying an atomic multiword update to the data structure to arbitrate access to the NVM, wherein the atomic multiword update tracks metadata for an update operation in a descriptor table that includes a dirty bit used to signify that a value is volatile and should be flushed by a reader and unset prior to reading the value.

2. The method of claim 1 wherein the data structure comprises a lock free B+ tree.

3. The method of claim 2 wherein the B+ tree includes internal nodes that store search keys and pointers to child nodes and leaf nodes that store keys and either record pointer or actual payload values.

4. The method of claim 2 wherein the B+ tree includes a root pointer to a root node to an index, and a global index epoch that is updated responsive to a failure.

5. The method of claim 1 wherein the atomic multiword update comprises a persistent multi-word compare-and-swap (PMwCAS) operation.

6. The method of claim 5 and further comprising recovering the data structure following a failure by rolling back or forward PMwCAS operations that were in-flight during the failure.

7. The method of claim 1 wherein the descriptor table metadata includes an update operation status, multiple target word addresses, expected old values, and new values.

8. The method of claim 7 wherein the descriptor table further includes a memory recycling policy value.

9. A computer-readable storage device having instructions for execution by computing resources to perform operations comprising:

receiving multiple requests to update a data structure stored in non-volatile memory (NVM); and

applying an atomic multiword update to the data structure to arbitrate access to the NVM, wherein the atomic multiword update tracks metadata for an update operation in a descriptor table that includes a dirty bit used to signify that a value is volatile and should be flushed by a reader and unset prior to reading the value.

10. The computer-readable storage device of claim 9 wherein the data structure comprises a lock free B+ tree that includes internal nodes that store search keys and pointers to child nodes, leaf nodes that store keys and either record pointer or actual payload values, a root pointer to a root node to an index, and a global index epoch that is updated responsive to a failure.

11. The computer-readable storage device of claim 9 wherein the atomic multiword update comprises a persistent multi-word compare-and-swap (PMwCAS) operation.

12. The computer-readable storage device of claim 11 and further comprising recovering the data structure following a failure by rolling back or forward PMwCAS operations that were in-flight during the failure.

13. The computer-readable storage device of claim 9 wherein the descriptor table metadata includes an update operation status, multiple target word addresses, expected old values, and new values.

14. A device comprising:

a processor; and

a memory device coupled to the processor and having a program stored thereon for execution by the processor to perform operations comprising;

receiving multiple requests to update a data structure stored in non-volatile memory (NVM); and

applying an atomic multiword update to the data structure to arbitrate access to the NVM, wherein the atomic multiword update tracks metadata for an update operation in a descriptor table that includes a dirty bit used to signify that a value is volatile and should be flushed by a reader and unset prior to reading the value.

15. The device of claim 14 wherein the data structure comprises a lock free B+ tree that includes internal nodes that store search keys and pointers to child nodes, leaf nodes that store keys and either record pointer or actual payload values, a root pointer to a root node to an index, and a global index epoch that is updated responsive to a failure.

16. The device of claim 14 wherein the atomic multiword update comprises a persistent multi-word compare-and-swap (PMwCAS) operation and wherein the operations further comprise recovering the data structure following a failure by rolling back or forward PMwCAS operations that were in-flight during the failure.

17. The device of claim 14 wherein the descriptor table metadata includes an update operation status, multiple target word addresses, expected old values, and new values.