TECHNIQUES TO PERFORM POWER FAIL-SAFE CACHING WITHOUT ATOMIC METADATA

• US 20100250833A1
• Filed: 03/30/2009
• Published: 09/30/2010
• Est. Priority Date: 03/30/2009
• Status: Active Grant

• Current Assignee: SK Hynix NAND Product Solutions Corporation (SK Hynix Inc.)
• Original Assignee: Intel Corporation
• Inventors: Trika, Sanjeev N.
• Granted Patent: US 8,195,891 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 11/1441 Resetting or repowering
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• 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/0866 for peripheral storage systems, e.g. disk cache
• 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/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 2212/601 Reconfiguration of cache memory
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A method and system to allow power fail-safe write-back or write-through caching of data in a persistent storage device into one or more cache lines of a caching device. No metadata associated with any of the cache lines is written atomically into the caching device when the data in the storage device is cached. As such, specialized cache hardware to allow atomic writing of metadata during the caching of data is not required.

Claims

1. A method comprising:

caching data of a first device into one or more of a plurality of cache lines of a second device, wherein no state information associated with any of the cache lines is to be stored atomically with the data in the second device during caching of the data.

2. The method of claim 1, wherein caching the data of the first device into the one or more cache lines of the second device comprises:

determining from state information associated with the plurality of cache lines if any of the plurality of cache lines is tagged as unused;

if not,

evicting at least one of the plurality of cache lines; and

tagging the at least one evicted cache line as unused in the state information;

selecting one or more cache lines tagged as unused in the state information; and

caching the data of the first device into the selected one or more cache lines.

3. The method of claim 1, further comprising storing state information associated with one or more of the cache lines in a memory when the data of the first device is cached into the one or more cache lines of the second device.

4. The method of claim 3, further comprising:

updating the cached data in the one or more cache lines with new data when the new data is to be written to the one or more cache lines; and

updating the state information associated with the one or more cache lines based on the new data in the memory.

5. The method of claim 4, further comprising:

copying all state information in the memory to the second device when one of a restart, shutdown, hibernate, or standby, command is received.

6. The method of claim 4, further comprising resetting the second device when a power or system failure has occurred.

7. The method of claim 4, wherein the second device comprises a copy of the state information associated with the one or more cache lines in the memory, further comprising updating the state information associated with the one or more cache lines based on the new data in the copy of the state information in the second device responsive to updating the cached data.

8. The method of claim 4, wherein the second device comprises a copy of the state information associated with the one or more cache lines in the memory, further comprising tagging the one or more cache lines as pending an update of the state information associated with the one or more cache lines based on the new data in the copy of the state information in the second device responsive to updating the cached data.

9. The method of claim 8, further comprising updating the state information associated with the one or more tagged cache lines in the copy of the state information in the second device when one of a flush, restart, shutdown, hibernate, or standby, command is received.

10. The method of claim 4, further comprising copying the state information associated with the one or more cache lines in the memory to the second device when a flush command is received.

11. The method of claim 10, wherein copying the state information associated with the one or more cache lines in the memory to the second device comprises optimizing number of copy operations.

12. An apparatus comprising:

a NAND flash memory having a first logical segment of a plurality of cache lines and a second logical segment of a plurality of metadata, each metadata associated with a respective one of the plurality of cache lines, wherein the second logical segment does not have any metadata; and

a controller to cache data of a storage device into one or more cache lines.

13. The apparatus of claim 12, wherein each metadata of the second logical segment comprises at least one of a sequence number, a logical block address, a state information, and pinning information of cached data in its associated respective cache line.

14. The apparatus of claim 12, wherein the plurality of cache lines comprises a plurality of spare cache lines, and wherein the controller is further to:

determine if all the spare cache lines are used;

if so,

evict one or more selected cache lines, the selection based on an eviction policy;

add the evicted one or more selected cache lines to the spare cache lines;

and wherein the controller to cache the data of the storage device in the one or more cache lines is to cache the data of the storage device in the one or more spare cache lines.

15. The apparatus of claim 12, further comprising a memory to store the plurality of metadata, and wherein the controller is further to:

update the cached data of the one or more cache lines with new data when the new data is to be written to the one or more cache lines; and

update the metadata associated with the one or more cache lines based on new data in the memory.

16. The apparatus of claim 15, wherein the controller is further to:

update the storage device with the new data; and

overwrite the metadata associated with the one or more cache lines in the NAND flash memory with the metadata associated with the one or more cache lines in the memory when the apparatus is to be rebooted, shut down, or placed in a sleeping state.

17. The apparatus of claim 15, wherein the memory is further to store a cache table comprising link information between the data in the storage device and the plurality of cache lines and wherein the controller is further to copy the cache table in the memory to the NAND flash memory when the apparatus is to be rebooted, flushed, shut down, or placed in a sleeping state.

18. The apparatus of claim 15, wherein the controller is to update the metadata associated with the one or more cache lines based on the new data in the NAND flash memory when the new data is to be written to the one or more cache lines, responsive to updating the cached data.

19. The apparatus of claim 15, wherein the controller is further to add the one or more cache lines to a list, and wherein the list is to indicate that the metadata associated with the one or more cache lines in the NAND flash memory is pending to be updated with the metadata associated with the one or more cache lines in the memory.

20. The apparatus of claim 19, wherein the controller is further to update the metadata associated with the one or more cache lines in the NAND flash memory with the metadata associated with the one or more cache lines in the memory when the apparatus is to be powered off or rebooted, or when the NAND flash memory is to be flushed.

21. The apparatus of claim 14, wherein the controller is further to overwrite the metadata in the non-volatile media with the metadata in the memory when a flush command issued by an operating system (OS) executing on the system is received.

22. The apparatus of claim 20, wherein the controller is further to restore the metadata in the memory with the metadata in the NAND flash memory when the apparatus is to be powered up or restarted.

23. The apparatus of claim 17, wherein the controller is further to copy the cache table from the NAND flash memory to the memory when the apparatus is to be powered up or restarted.

24. The apparatus of claim 12, wherein the storage device is one of a hard disk, a tape drive, a compact disc, a zip disk, a flash memory, and a solid-state drive.

25. The apparatus of claim 12, wherein the controller is a block storage driver.

26. A computer readable storage medium having instructions stored thereon which, when executed, cause a processor to perform the following method:

write-back or write-through caching of data of a storage device into one or more of a plurality of cache lines of a caching device, wherein no metadata associated with any of the cache lines is to be written atomically into the caching device when the data is cached.

27. The medium of claim 26, wherein write-back or write-through caching of the data of the storage device into the one or more cache lines of the caching device comprises:

determining if any of the plurality of cache lines is tagged as unused;

if not,

evicting at least one of the plurality of cache lines; and

tagging the at least one evicted cache line as unused;

selecting one or more cache lines tagged as unused; and

caching the data of the storage device into the selected one or more cache lines.

28. The medium of claim 26, wherein write-through caching of the data comprises:

determining that the one or more cache lines of the caching device is to be updated with new data;

updating the one or more determined cache lines with the new data;

updating metadata associated with the one or more determined caches lines based at least on the new data in a memory; and

updating the storage device with the new data.

29. The medium of claim 26, wherein write-back caching of the data comprises:

determining that the one or more cache lines of the caching device is to be updated with new data;

updating metadata associated with the one or more determined caches lines based at least on the new data in a memory;

updating the one or more determined cache lines with the new data; and

marking the one or more determined caches lines, wherein the marking is to indicate that metadata associated with the one or more determined caches lines in the caching device is to be updated with the metadata associated with the one or more determined caches lines in the memory.

30. The medium of claim 26, wherein write-back caching of the data further comprises:

updating the metadata associated with the one or more determined caches lines in the caching device with the metadata associated with the one or more determined caches lines in the memory when a power down, a reboot or a flush command is received.

31. An system comprising:

a NAND flash memory having a first logical segment of a plurality of cache lines and a second logical segment of a plurality of metadata, each metadata associated with a respective one of the plurality of cache lines, wherein the second logical segment does not have any metadata; and

a memory controller to write-back or write-through cache data of a storage medium in one or more cache lines of the first logical segment of the NAND flash memory, wherein no metadata is to be written atomically into the first logical segment when the data is cached.

32. The system of claim 31, wherein each metadata of the second logical segment comprises at least one of a sequence number, a logical block address, a state information, and pinning information of cached data in its associated respective cache line.