Systems and methods for persistent cache logging

• US 9,842,053 B2
• Filed: 03/15/2013
• Issued: 12/12/2017
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Joshi, Vikram, Luan, Yang, Brown, Michael F., Mehta, Bhavesh
• Primary Examiner(s): Elmore, Reba I
• Application Number:
  US13/837,210
• Publication Number:
  US 20140281131A1
• Time in Patent Office: 1,733 Days
• Field of Search: 709229, 709249, 713150, 713189, 713193
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 2212/313 In storage device
• CPC Class Codes: G06F 2212/466 Metadata, control data

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.

Claims

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 responsive to the write requests, wherein caching the write-back data of a write request comprises;

performing a first cache write operation to cache the write-back data of the write request within a first cache, the write-back data designated to be written to the primary storage from the first cache;

performing a second cache write operation to store a redundant copy of the write-back data in a second cache, separate from the first cache, wherein performing the second cache write operation comprises appending a log entry comprising the write-back data of the write request to a persistent, ordered log on a non-volatile storage device of the second cache the persistent, ordered log comprising log entries corresponding to respective cache write operations performed on the first cache during respective log periods; and

associating the write-back data of the write request cached within the first cache storage with a log period of the persistent, ordered log on the non-volatile storage device of the second cache.

19. The non-transitory computer-readable storage medium of claim 18, wherein:

each of the plurality of virtual machines is configured to maintain cache metadata pertaining to the virtual machine, the cache metadata comprising;

mappings between logical identifiers of the virtual machine and write-back data cached within the first cache; and

mappings between the logical identifiers of the virtual machine and respective log periods of the persistent, ordered log,

the operations further comprising;

identifying write-back data corresponding to one or more log periods by use of the cache metadata of the virtual machines; and

writing the identified write-back data to primary storage.

20. The non-transitory computer-readable storage medium of claim 19, wherein:

the one or more log periods comprise log entries corresponding to a plurality of cache write operations pertaining to a particular logical identifier; and

the operations further comprise identifying write-back data corresponding to a most recent one of the plurality of cache write operations pertaining to the particular logical identifier within the one or more log periods.

21. The non-transitory computer-readable storage medium of claim 18, the operations further comprising:

providing an identifier of a current log period to a virtual machine; and

wherein the virtual machine is configured to associate write requests of the virtual machine with the provided identifier.

22. The non-transitory computer-readable storage medium of claim 21, the operations further comprising providing an updated identifier to the virtual machine in response to incrementing the current log period before completion of a particular write request;

wherein the virtual machine is configured to associate write-back data of the write request with the updated identifier.

23. The non-transitory computer-readable storage medium of claim 18, the operations further comprising indicating that a request to cache write-back data of a particular write request is complete in response to determining that a log entry comprising the write-back data of the particular write request is stored in the persistent, ordered log on the second cache storage.