Systems and methods for persistent cache logging

Patent metadata

Field	Value
Publication number	US-9842053-B2
Application number	US-201313837210-A
Country	US
Kind code	B2
Filing date	Mar 15, 2013
Priority date	Mar 15, 2013
Publication date	Dec 12, 2017
Grant date	Dec 12, 2017

Abstract

A cache log module stores an ordered log of cache storage operations sequentially within the physical address space of a non-volatile storage device. The log may be divided into segments, each comprising a set of log entries. Data admitted into the cache may be associated with respective log segments. Cache data may be associated with the log segment that corresponds to the cache storage operation in which the cache data was written into the cache. The backing store of the data may be synchronized to a particular log segment by identifying the cache data pertaining to the segment (using the associations), and writing the identified data to the backing store. Data lost from the cache may be recovered from the log by, inter alia, committing entries in the log after the last synchronization time of the backing store.

First claim

We claim:

1. A method comprising:
caching write requests directed to a backing store, the write requests for storing respective write data on the backing store, wherein caching a write request comprises:
caching write data corresponding to the write request within a first cache storage, the write data designated to be written to the backing store from the first cache storage; and
storing a redundant copy of the write data cached within the first cache storage on a second, persistent cache storage, separate from the first cache storage, wherein storing the redundant copy of the write data comprises recording a log entry comprising the write data in an ordered sequence of log entries on the second, persistent cache storage, each log entry corresponding to a set of write requests directed to the backing store; and

maintaining associations between the write data cached within the first cache storage and log entries comprising redundant copies of the write data stored on the second, persistent cache storage.

2. The method of claim 1 , further comprising:
identifying write data cached within the first cache storage that is associated with a selected one of a plurality of log periods recorded on the second, persistent cache storage, each log period comprising one or more log entries corresponding to respective sets of one or more write requests directed to the backing store; and
writing the identified write data from the first cache storage to the backing store.

3. The method of claim 2 , further comprising marking the backing store with an indicator of the selected log period in response to writing the identified write data from the first cache storage to the backing store.

4. The method of claim 1 , further comprising:
in response to a failure condition:
identifying a set of log entries recorded on the second, persistent cache storage that are associated with cached write requests that correspond to write data that have not been written to the backing store from the first cache storage; and
transferring write data corresponding to the identified set of log entries to one or more of the first cache storage and the backing store.

5. The method of claim 4 , wherein identifying the set of log entries comprises determining an indicator of a last log period committed to the backing store.

6. The method of claim 4 , further comprising:
queuing the write data corresponding to the identified set of log entries in a buffer;
removing queued write data made redundant by one or more other write data from the buffer; and
transferring data from the buffer to one or more of the first cache storage and the backing store.

7. The method of claim 4 , further comprising admitting write data corresponding to one or more of the identified set of log entries into the first cache storage.

8. An apparatus, comprising:
a request monitor configured to identify write requests directed to a backing store; and
a cache manager configured to cache the identified write requests, wherein to cache the identified write requests, the cache manager is configured to:
admit write data corresponding to the identified write requests into a first cache storage, wherein the write data of the identified write requests are cached within the first cache storage in one or more cache write operations, and wherein the write data admitted into the first cache storage are designated to be written to the backing store from the first cache storage; and
maintain redundant copies of the write data corresponding to the identified write requests within a second cache storage, separate from the first cache storage, the redundant copies comprising log entries stored on a non-volatile storage device of the second cache storage, the log entries corresponding to the one or more cache write operations performed on the first cache storage to admit the write data into the first cache storage;

wherein the request monitor is further configured to acknowledge completion of a write request, of the identified write requests in response to:
completing a cache write operation to admit the write data corresponding to the write request into the first cache storage; and
storing a redundant copy of the write data corresponding to the write request as a log entry on the non-volatile storage device of the second cache storage.

9. The apparatus of claim 8 , wherein the cache manager is further configured to store log entries corresponding to the cache write operations performed on the first cache storage sequentially within a physical address space of the non-volatile storage device of the second cache storage.

10. The apparatus of claim 8 , wherein the cache manager is further configured to:
divide a log comprising the log into an ordered sequence of log segments, each log segment comprising log entries comprising redundant copies of write data corresponding to a respective group of write requests; and
store the write data associated with the log entries of a selected log segment on the backing store.

11. The apparatus of claim 10 , wherein the cache manager is further configured to combine log entries that comprise redundant copies of write data associated with a same data identifier into a single log entry.

12. The apparatus of claim 10 , wherein the cache manager is further configured to maintain cache metadata, the cache metadata configured to associate write data admitted into the first cache storage with log segments comprising log entries storing redundant copies of the copies of the write data on the second cache storage.

13. The apparatus of claim 10 , wherein the cache manager is further configured to record an indication that the selected log segment has been committed to the backing store in response to writing the write data corresponding to the log entries of the selected log segment to the backing store.

14. The apparatus of claim 10 , wherein the cache manager is further configured to: identify a last log segment committed to the backing store; and select the log segment to commit to the backing store based on the determined last log segment.

15. The apparatus of claim 10 , wherein the cache manager is further configured to reclaim the selected log segment in response to storing the write data associated with selected log segment on the backing store.

16. The apparatus of claim 8 , wherein:
the log entries are stored as an ordered sequence on the non-volatile storage device, each log entry of the ordered sequence comprising a redundant copy of write data admitted into the first cache storage in a respective cache write operation; and the apparatus further comprises
a recovery module configured to access the log entries from a starting entry in the ordered sequence to a last entry in the ordered sequence and to implement write operations corresponding to the accessed log entries on one or more of the backing store and the first cache storage, the starting entry identified based on a synchronization state of the backing store.

17. The apparatus of claim 8 , wherein: the request monitor is configured to operate within a virtual machine; and the cache manager is configured to operate within a virtualization kernel.

18. A non-transitory computer-readable storage medium comprising instructions configured to cause a computing system to perform operations, the operations comprising:
caching write-back data responsive to write requests, the write requests corresponding to respective virtual machines of a plurality of virtual machines, the write-back data comprising data to be written to primary storage resp

Assignees

• Sandisk Technologies Llc

Inventors

• Joshi Vikram
• Luan yang
• Brown Michael F
• Mehta Bhavesh

Classifications

• G06F12/0871

  Allocation or management of cache space · CPC title

• G06F12/0804

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

• G06F2212/466

  Metadata, control data · CPC title

• G06F12/0868 Primary

  Data transfer between cache memory and other subsystems, e.g. storage devices or host systems · CPC title

• G06F2212/313

  In storage device · CPC title