# US 9,519,591 B2 · Latch-free, log-structured storage for multiple access methods

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

- Number: US 9,519,591 B2
- Document ID: US9519591B2
- Status: Granted
- Kind: B2
- Application number: 13/924,567
- Filed: 2013-06-22
- Published: 2014-12-25
- Granted: 2016-12-13
- Earliest claimed: 2013-06-22
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: David B. Lomet; Justin Levandoski; Sudipta Sengupta
- Web page: https://patentgrep.com/patent/US9519591B2

## CPC

- G06F 12/0804: with main memory updating (G06F12/0806 takes precedence)
- G06F 12/0815: Cache consistency protocols
- G06F 12/0891: using clearing, invalidating or resetting means
- G06F 12/1009: using page tables, e.g. page table structures
- G06F 12/123: with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/2315: {Optimistic concurrency control}
- G06F 12/12: Replacement control
- G06F 2212/60: Details of cache memory
- G06F 2212/621: Coherency control relating to peripheral accessing, e.g. from DMA or I/O device
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 3)

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.

### Claim 5 (depends on 3)

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.

### Claim 6 (depends on 3)

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.

### Claim 7 (depends on 3)

The system of claim 3, further comprising:
a record manager configured to control updates based on update delta record operations and replacement update operations.

### Claim 8 (depends on 1)

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.

### Claim 9 (depends on 1)

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.

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 10)

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.

### Claim 12 (depends on 1)

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.

### Claim 13 (depends on 12)

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.

### Claim 14 (depends on 12)

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.

### Claim 15 (depends on 1)

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.

### Claim 16 (depends on 1)

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.

### Claim 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.

### Claim 18 (depends on 17)

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.

### Claim 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.

### Claim 20 (depends on 19)

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.