Latch-free, log-structured storage for multiple access methods

• US 9,519,591 B2
• Filed: 06/22/2013
• Issued: 12/13/2016
• Est. Priority Date: 06/22/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Lomet, David B., Levandoski, Justin, Sengupta, Sudipta
• Primary Examiner(s): Rutz, Jared
• Assistant Examiner(s): EDOUARD, JEAN C
• Application Number:
  US13/924,567
• Publication Number:
  US 20140379991A1
• Time in Patent Office: 1,270 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2315 Optimistic concurrency control
• CPC Class Codes: G06F 2212/60 Details of cache memory
• CPC Class Codes: G06F 2212/621 Coherency control relating to peripheral accessing, e.g. from DMA or I/O device

Abstract

A data manager may include a data opaque interface configured to provide, to an arbitrarily selected page-oriented access method, interface access to page data storage that includes latch-free access to the page data storage. In another aspect, a swap operation may be initiated, of a portion of a first page in cache layer storage to a location in secondary storage, based on initiating a prepending of a partial swap delta record to a page state associated with the first page, the partial swap delta record including a main memory address indicating a storage location of a flush delta record that indicates a location in secondary storage of a missing part of the first page. In another aspect, a page manager may initiate a flush operation of a first page in cache layer storage to a location in secondary storage, based on atomic operations with flush delta records.

Claims

1. A system comprising:

a device that includes at least one processor, the device including a data manager comprising instructions tangibly embodied on a computer readable storage medium for execution by the at least one processor, the data manager including;

a data opaque interface configured to provide, to an arbitrarily selected page-oriented access method, interface access to page data storage that includes latch-free access to the page data storage, the data opaque interface providing latch-free page updating via atomic operations on storage address entries representing page states in an indirect address mapping table that is used in common for management of data storage that includes cache layer storage and secondary storage.

2. The system of claim 1, wherein:

the data opaque interface is configured to provide, to the arbitrarily selected page-oriented access method, interface access to page data storage that includes log structured access to the page data storage.

3. The system of claim 1, further comprising:

a cache layer manager that includes;

a map table manager configured to initiate table operations on an indirect address mapping table associated with the data opaque interface, the table operations including initiating atomic compare and swap operations on entries in the indirect address mapping table, to replace prior states of pages that are associated with the page data storage, with new states of the pages.

4. The system of claim 3, wherein:

the map table manager is configured to initiate the table operations on the indirect address mapping table associated with the data opaque interface, wherein the indirect address mapping table is used in common for management of data storage that includes cache layer storage and secondary storage.

5. The system of claim 3, wherein:

the indirect address mapping table separates logical locations of pages from corresponding physical locations of the pages, wherein;

users of the page data storage store page identifier values in lieu of physical location address values for the pages, elsewhere in data structures referencing the page data storage.

6. The system of claim 3, further comprising:

a log-structured storage layer manager configured to control page location changes associated with log structuring resulting from page flushes, using latch-free compare and swap operations on entries in the indirect address mapping table.

7. The system of claim 3, further comprising:

a record manager configured to control updates based on update delta record operations and replacement update operations.

8. The system of claim 1, further comprising:

a first epoch manager configured to initiate enrollment of a first processor operation in a first epoch enrollment list associated with a first epoch, prior to accessing page information by the first processor operation.

9. The system of claim 1, further comprising:

a page manager configured to flush a page state to secondary storage based on installing a pointer to a flush delta record in a mapping table, via a compare and swap (CAS) operation, the flush delta record prepended to an existing page state that is replaced in the mapping table via the CAS operation.

10. The system of claim 9, wherein:

the page manager is configured to;

determine whether the CAS operation succeeds, and to initiate a write operation to write the existing page state to a secondary storage flush buffer, if it is determined that the CAS operation succeeds.

11. The system of claim 10, wherein:

the page manager is configured to;

initiate a void operation to storage space previously allocated for the existing page, if it is determined that the CAS operation fails.

12. The system of claim 1, further comprising:

a buffer manager configured to control updates to a log-structured secondary storage buffer via latch-free update operations.

13. The system of claim 12, wherein:

the buffer manager is configured to enable a plurality of threads to simultaneously update the log-structured secondary storage buffer, via latch-free operations.

14. The system of claim 12, wherein:

the buffer manager is configured to initiate a stability operation for determining that pages flushed to the log-structured secondary storage buffer, having lower addresses, up to a first secondary storage address argument, are stable in the log-structured secondary storage.

15. The system of claim 1, further comprising:

a page manager configured to initiate a flush operation of a first page in cache layer storage to a location in secondary storage, based on;

initiating a copy of a page state of the first page into a secondary storage buffer,

initiating a prepending of a flush delta record to the page state, the flush delta record including a secondary storage address indicating a storage location of the first page in secondary storage and an annotation associated with a caller, and

initiating an update to the page state based on installing an address of the flush delta record in a mapping table, via a compare and swap (CAS) operation.

16. The system of claim 1, further comprising:

a page manager configured to initiate a swap operation of a portion of a first page in cache layer storage to a location in secondary storage, based on initiating a prepending of a partial swap delta record to a page state associated with the first page, the partial swap delta record including a main memory address indicating a storage location of a flush delta record that indicates a location in secondary storage of a missing part of the first page.

17. A system comprising:

a device that includes at least one processor, the device including a data manager comprising instructions tangibly embodied on a computer readable storage medium for execution by the at least one processor, the data manager including;

a page manager configured to initiate a flush operation of a first page in cache layer storage to a location in secondary storage, based on;

initiating a copy of a page state of the first page into a secondary storage buffer,

initiating a prepending of a flush delta record to the page state, the flush delta record including a secondary storage address indicating a storage location of the first page in secondary storage and an annotation associated with a caller, and

initiating a latch-free update to the page state based on installing an address of the flush delta record in a mapping table, via a compare and swap (CAS) operation.

18. The system of claim 17, further comprising:

a data opaque interface configured to provide, to an arbitrarily selected page-oriented access method, interface access to page data storage that includes latch-free access to the page data storage; and

a buffer manager configured to control updates to a log-structured secondary storage buffer via latch-free update operations.

19. A system comprising:

a device that includes at least one processor, the device including a data manager comprising instructions tangibly embodied on a computer readable storage medium for execution by the at least one processor, the data manager including;

a page manager configured to initiate a latch-free swap operation of a portion of a first page in cache layer storage to a location in secondary storage, by initiating a prepending, via an atomic operation, of a partial swap delta record to a page state associated with the first page, the partial swap delta record including a main memory address indicating a storage location of a flush delta record that indicates a location in secondary storage of a missing part of the first page.

20. The system of claim 19, further comprising:

a data opaque interface configured to provide, to an arbitrarily selected page-oriented access method, interface access to page data storage that includes latch-free access to the page data storage, wherein the data opaque interface is configured to provide, to the arbitrarily selected page-oriented access method, interface access to page data storage that includes log structured access to the page data storage.