Log-structured storage for data access

Patent metadata

Field	Value
Publication number	US-2017199818-A1
Application number	US-201615372381-A
Country	US
Kind code	A1
Filing date	Dec 7, 2016
Priority date	Jun 22, 2013
Publication date	Jul 13, 2017
Grant date	—

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.

First claim

1 . (canceled)

2 . A system comprising:
a memory device; a secondary storage device; and a processor configured via executable instructions to:
store a page of data in the memory device, the page comprising a first portion and a second portion;
modify a log-structured store on the secondary storage device to reflect an update to a first portion of the page of data;
remove the first portion of the page from the memory device while retaining the second portion of the page in the memory device; and
retrieve the first portion of the page from the log-structured store on the secondary storage device and store the first portion of the page in the memory device, the first portion of the page being retrieved into the memory device while the second portion of the page remains in the memory device.

3 . The system of claim 2 , the processor being further configured via the executable instructions to:
while the first portion of the page is removed from the memory device and stored in the log-structured store on the secondary storage device, receive a request to read the page; and retrieve the first portion of the page into the memory device responsive to the request to read the page.

4 . The system of claim 2 , the processor being further configured via the executable instructions to:
maintain a mapping table identifying different physical addresses of different pages of data, the different physical addresses including memory addresses on the memory device and secondary storage addresses on the secondary storage device.

5 . The system of claim 2 , the secondary storage device being a flash storage device.

6 . The system of claim 5 , the memory device being a random access memory device.

7 . A method comprising:
maintaining a mapping table that maps pages of data to addresses on a memory device and a storage device; flushing a first portion of a selected page to the storage device; removing the first portion of the selected page from the memory device while a second portion of the selected page remains in the memory device; modifying the mapping table to reflect that the first portion of the selected page has been removed from the memory device; and using the mapping table to retrieve the first portion of the selected page from the storage device and store the first portion of the selected page in the memory device, the first portion of the selected page being retrieved while the second portion of the selected page is present in the memory device.

8 . The method of claim 7 , wherein modifying the mapping table comprises inserting a partial swap delta record into the mapping table.

9 . The method of claim 8 , further comprising:
storing, on the storage device, a flush delta record identifying a storage address where the first portion of the selected page is stored on the storage device, the partial swap delta record in the mapping table pointing to the flush delta record on the storage device.

10 . The method of claim 7 , further comprising:
freeing one or more addresses on the memory device where the first portion of the selected page is stored prior to being removed.

11 . The method of claim 7 , further comprising:
storing the first portion of the selected page and a third portion of the selected page in different storage blocks on the storage device.

12 . The method of claim 11 , further comprising:
linking at least the first portion of the selected page to the third portion in a log-structured store on the storage device.

13 . The method of claim 11 , further comprising:
reading the entire page into memory by retrieving the first portion and the third portion from the different storage blocks.

14 . The method of claim 7 , wherein the modifying the mapping table is performed without obtaining a latch.

15 . A hardware computer-readable storage medium storing instructions which, when executed by a processor, cause the processor to perform acts comprising:
maintaining a mapping table that maps pages of data to physical addresses where the pages are stored in memory and on secondary storage; flushing a first portion of a selected page from the memory to the secondary storage; removing the first portion of the selected page from the memory while a second portion of the selected page remains in the memory; modifying the mapping table to indicate that the first portion of the selected page has been removed from the memory; and using the mapping table to retrieve the first portion of the selected page from the secondary storage and store the first portion of the selected page in the memory, the first portion of the selected page being retrieved into the memory while the second portion is present in the memory.

16 . The hardware computer-readable storage medium of claim 15 , the acts further comprising:
flushing the first portion of the selected page responsive to a request identifying the selected page, the request identifying a delta relative to a previous page state of the selected page.

17 . The hardware computer-readable storage medium of claim 16 , the acts further comprising:
returning to the request without ensuring that the delta is stable on the secondary storage.

18 . The hardware computer-readable storage medium of claim 16 , the acts further comprising:
storing a record on the secondary storage that identifies a particular address where the delta resides.

19 . The hardware computer-readable storage medium of claim 18 , the acts further comprising:
storing, in the mapping table, another address of the record on the secondary storage.

20 . The hardware computer-readable storage medium of claim 15 , the acts further comprising:
freeing memory from which the first portion of the selected page is removed.

21 . The hardware computer-readable storage medium of claim 15 , the acts further comprising:
storing links chaining multiple different portions of the selected page together on the secondary storage; and retrieving the selected page into memory by following the links.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Lomet David B
• Levandoski Justin
• Sengupta Sudipta

Classifications

• G06F12/123

  with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list · CPC title

• G06F12/0891

  using clearing, invalidating or resetting means · CPC title

• G06F2212/60

  Details of cache memory · CPC title

• G06F17/30327

  Physics · mapped topic

• G06F12/0804 Primary

  with main memory updating (G06F12/0806 takes precedence) · CPC title