Structuring storage based on latch-free B-trees

• US 9,003,162 B2
• Filed: 06/20/2012
• Issued: 04/07/2015
• Est. Priority Date: 06/20/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Lomet, David, Levandoski, Justin, Sengupta, Sudipta
• Primary Examiner(s): Chery, Mardochee
• Assistant Examiner(s): Dewan, Kamal K
• Application Number:
  US13/527,880
• Publication Number:
  US 20130346725A1
• Time in Patent Office: 1,021 Days
• Field of Search: 711/114, 711/118, 711/206, 711/154, 711/E12.061, 707/999.2, 717/120
• US Class Current: 711/206
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: Y10S 707/99951 File or database maintenance

Abstract

A request to modify an object in storage that is associated with one or more computing devices may be obtained, the storage organized based on a latch-free B-tree structure. A storage address of the object may be determined, based on accessing a mapping table that includes map indicators mapping logical object identifiers to physical storage addresses. A prepending of a first delta record to a prior object state of the object may be initiated, the first delta record indicating an object modification associated with the obtained request. Installation of a first state change associated with the object modification may be initiated via a first atomic operation on a mapping table entry that indicates the prior object state of the object. For example, the latch-free B-tree structure may include a B-tree like index structure over records as the objects, and logical page identifiers as the logical object identifiers.

Claims

1. A system comprising:

at least one hardware device processor;

a structured data manager tangibly embodied via executable instructions stored on a machine readable storage device for execution by the at least one hardware device processor, the structured data manager including;

a tree manager that, when executed, controls tree operations associated with latch-free updates associated with a latch-free B-tree structure; and

a map table manager that, when executed, initiates table operations on an indirect address mapping table associated with the latch-free B-tree structure, the table operations including initiating an atomic compare and swap operation on an entry in the indirect address mapping table, to replace a prior state of a page associated with the latch-free B-tree structure with a new state of the page.

2. The system of claim 1, wherein replacing the prior state of the page with the new state of the page includes at least one of:

replacing a physical address of a first storage object that includes stored information representing the prior state of the page with a physical address of a delta record that is associated with the new state of the page, or

replacing a physical address of the first storage object that includes stored information representing the prior state of the page with a physical address of the new state of the page.

3. The system of claim 1, wherein:

the tree operations include search and update operations on the latch-free B-tree structure, and

the indirect address mapping table includes map indicators mapping logical storage object identifiers to physical storage addresses, wherein;

the system further comprises a storage manager that, when executed, initiates operations on storage areas located on one or more storage devices that include storage space associated with the physical storage addresses, wherein the physical storage addresses include one or more of;

storage addresses of pages in volatile memory, or

storage addresses of pages in stable storage.

4. The system of claim 3, wherein:

the storage manager is configured to initiate a flush operation of a first page in volatile memory to a location in stable storage, based on;

initiating a prepending of a flush delta record to the first page in volatile memory, and

initiating installation of a first state change associated with the flush operation via a first atomic compare and swap operation on a mapping table entry that indicates a current state of the first page, wherein the first state change indicates a flush state of the page.

5. The system of claim 1, wherein:

the indirect address mapping table includes map indicators mapping logical page identifiers to storage addresses, based on mapping logical pages to physical pages in storage,

the latch-free B-tree structure includes node links for traversal, wherein the node links include logical page identifiers, in lieu of storage addresses, and

the physical pages include a group of physical pages that each include a right sibling link that includes a right sibling page identifier associated with a rightmost sibling physical page to the each physical page, based on the latch-free B-tree structure.

6. The system of claim 1, wherein:

the tree manager is configured to initiate a first update operation on the latch-free B-tree structure based on initiating a prepending of a first delta record to a first state of a first page, and initiating installation of a first state change associated with the first update operation via a first atomic compare and swap operation on a mapping table entry that indicates the first state of the first page, wherein the first state change indicates a second state of the page; and

the map table manager is configured to initiate the first atomic compare and swap operation on the mapping table entry that indicates the first state of the first page, wherein the mapping table entry that indicates the first state of the first page is updated to indicate the first delta record as a result of the first atomic compare and swap operation, wherein the first delta record represents at least one modification of the first page associated with the first update operation.

7. A method comprising:

obtaining a request to modify an object in storage that is associated with one or more computing devices, the storage organized based on a latch-free B-tree structure that is updated via latch-free updates;

determining, via a hardware device processor, a storage address of the object, based on accessing a mapping table that includes map indicators mapping logical object identifiers to physical storage addresses;

initiating a prepending of a first delta record to a prior object state of the object, the first delta record indicating an object modification associated with the obtained request; and

initiating installation of a first state change associated with the object modification via a first atomic operation on a mapping table entry that indicates the prior object state of the object.

8. The method of claim 7, wherein:

a process initiates the installation of the first state change, and

if the installation of the first state change fails;

the process retries initiating the installation of the first state change, if the first state change includes an update to an object in storage, or

the installation of the first state change is retried lazily, if the first state change includes one or more of a modification to the latch-free B-tree structure or a flush of a page from volatile storage to stable storage.

9. The method of claim 7, wherein:

a process initiates the installation of the first state change, and

if the process encounters an incomplete modification operation on the latch-free B-tree structure, the process initiates completion of the incomplete modification prior to completion of the installation of the first state change.

10. The method of claim 7, wherein:

the first delta record represents a first modification of the object associated with the request,

the first delta record includes a link that includes a physical address associated with the prior object state of the object, and

the installation of the first state change includes installation of a physical storage address of the first delta record to replace a physical storage address of the prior object state of the object.

11. The method of claim 7, wherein:

the first atomic operation includes a compare and swap (CAS) operation.

12. The method of claim 7, further comprising:

obtaining a second request to modify the object;

determining, via a hardware device processor, the storage address of the object, based on accessing the mapping table;

initiating a prepending of a second delta record to the first delta record prepended to the prior object state of the object, the second delta record indicating a second object modification associated with the obtained second request; and

initiating installation of a second state change associated with the second object modification via a second atomic operation on the mapping table entry that indicates the first state change.

13. The method of claim 12, further comprising:

initiating a consolidation of the object with the first and second delta records, based on generating a second object, based on updating the object via the first and second object modifications; and

initiating installation of a third state change associated with the object based on initiating a third atomic operation on the mapping table entry that indicates the second state change, installing the physical address of the second object therein.

14. The method of claim 7, further comprising:

determining that a size of a page associated with the latch-free B-tree structure exceeds a predetermined maximal value threshold; and

initiating a split of at least one node of the latch-free B-tree structure that is associated with the page, wherein initiating the split of the at least one node includes;

initiating a prepending of a split delta record to the node, wherein the split delta record includes a separator key value and a logical address corresponding to a side pointer associated with a sibling node that includes node data from the split node, and

initiating a prepending of an index term delta record to a parent node of the node, wherein the index term delta record includes a logical address corresponding to a pointer to the node, the separator key value, and a logical address corresponding to a pointer to the sibling node.

15. The method of claim 7, further comprising:

determining that a size of a page associated with the latch-free B-tree structure is smaller than a predetermined low value threshold; and

initiating a merge of a node of the latch-free B-tree structure that is associated with the page, wherein initiating the merge of the node includes;

initiating a prepending of a remove node delta record to the node, wherein the remove node delta record indicates a removal of the node,

initiating a prepending of a node merge delta record to a left sibling node of the node, wherein the node merge delta record includes a physical address of the contents of the node, and

initiating a prepending of an index term delete delta record to a parent node of the node, wherein the index term delete delta record indicates a deletion of the node and an indication that the left sibling node of the node includes a key space of the node.

16. A method comprising:

determining that a size of a page associated with a latch-free B-tree structure that is updated via latch-free updates, is unacceptable; and

initiating via a hardware device processor a modification of a node of the latch-free B-tree structure that is associated with the page, based on;

initiating a prepending of a delta record to the node, the delta record including an indication of the modification and a physical address pointer to the node, and

initiating at least one atomic operation to update an indirect address table to replace the physical address of the node with a physical address of the delta record, the indirect address table including logical page identifiers and corresponding physical addresses of physical pages associated with the logical page identifiers.

17. The method of claim 16,

wherein:

a process that initiates the modification of the node is registered in a start epoch structure on entry to current processing of the latch-free B-tree, and is removed from registration in the start epoch structure on completion of current processing of the latch-free B-tree that is associated with the process.

18. The method of claim 16, wherein:

a process initiates the modification of the node, and

if a second process encounters a partially completed multi-atomic action modification to the latch-free B-tree structure, the second process initiates completion of a remainder of actions for completion of the multi-atomic action modification, based on information obtained from prior modification actions by one or more other process actions.

19. The method of claim 16, wherein:

the modification of the node includes a node split, wherein

initiating the prepending of the delta record to the node includes initiating a prepending of a split delta record to the node, wherein the split delta record includes a separator key value and a logical address corresponding to a side pointer associated with a sibling node that includes node data from the split node, and

initiating a prepending of an index term delta record to a parent node of the node, wherein the index term delta record includes a logical address corresponding to a pointer to the node, the separator key value, and a logical address corresponding to a pointer to the sibling node.

20. The method of claim 16, wherein:

the modification of the node includes a node merge, wherein initiating the prepending of the delta record to the node includes;

initiating a prepending of a remove node delta record to the node, wherein the remove node delta record indicates a removal of the node,

initiating a prepending of a node merge delta record to a left sibling node of the node, wherein the node merge delta record includes a physical address of the contents of the node, and

initiating a prepending of an index term delete delta record to a parent node of the node, wherein the index term delete delta record indicates a deletion of the node and an indication that the left sibling node of the node includes a key space of the node.