Managing cache data and metadata

• US 8,489,815 B2
• Filed: 02/02/2012
• Issued: 07/16/2013
• Est. Priority Date: 09/15/2008
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Iyigun, Mehmet, Bak, Yevgeniy M., Fortin, Michael, Fields, Mahlon David, Ergan, Cenk, Kirshenbaum, Alexander
• Primary Examiner(s): Bertram, Ryan
• Application Number:
  US13/365,093
• Publication Number:
  US 20120173824A1
• Time in Patent Office: 530 Days
• Field of Search: 711/3, 711117-146, 711206-207
• US Class Current: 711/118
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 12/14 Protection against unauthorised use of memory or access to memory
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/1052 Security improvement
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 2212/466 Metadata, control data

Abstract

Embodiments of the invention provide techniques for managing cache metadata providing a mapping between addresses on a storage medium (e.g., disk storage) and corresponding addresses on a cache device at which data items are stored. In some embodiments, cache metadata may be stored in a hierarchical data structure comprising a plurality of hierarchy levels. When a reboot of the computer is initiated, only a subset of the plurality of hierarchy levels may be loaded to memory, thereby expediting the process of restoring the cache metadata and thus startup operations. Startup may be further expedited by using cache metadata to perform operations associated with reboot.

Claims

1. A computer system, comprising:

a memory;

a storage medium storing a plurality of data items at respective addresses;

a cache device also storing the plurality of data items at corresponding addresses and cache metadata providing a mapping between the address on the storage medium and the corresponding address on the cache device at which each data item is stored, the cache metadata being stored in a hierarchical data structure comprising a plurality of hierarchy levels;

at least one processor programmed to;

store cache metadata on the cache device in response to a command to shut down or reboot the computer;

upon initiating a reboot of the computer, load only a subset of the plurality of hierarchy levels to the memory; and

verify that a first data item of the plurality of data items was not modified after storage of the first data item in the cache device.

2. The computer system of claim 1, wherein the at least one processor is programmed to verify that the first data item was not modified at least in part by verifying a consistency between generations of cache contents.

3. The computer system of claim 2, wherein the at least one processor is programmed to evict the first data item from the cache device if determined to belong to an inconsistent cache generation.

4. The computer system of claim 1, wherein the at least one processor is further programmed to verify that the first data item was not modified at least in part by:

associating a representation of at least a portion of the first data item with the first data item;

retrieving at least a portion of the first data item from the cache device;

re-generating the representation of at least a portion of the first data item based on the retrieved at least the portion of the first data item; and

compare the associated representation with the re-generated representation to determine whether the retrieved at least the portion of the first data item is authentic.

5. The computer system of claim 4, wherein the at least one processor is programmed to generate the associated representation when the first data item is first written to the cache device.

6. The computer system of claim 5, wherein the at least one processor is programmed to write the associated representation to the cache device.

7. The computer system of claim 6, wherein the at least one processor is programmed to write the associated representation at a location adjacent to a location at which the first data item is stored in the cache device.

8. The computer system of claim 6, wherein the at least one processor is programmed to store the associated representation in cache metadata for the first data item.

9. The computer system of claim 6, wherein the at least one processor is programmed to retrieve the associated representation from the cache device.

10. The computer system of claim 4, wherein the at least one processor is programmed to generate the associated representation to comprise a cyclic redundancy code (CRC) of the at least the portion of the first data item.

11. The computer system of claim 4, wherein the at least one processor is programmed to generate the associated representation using a cryptographic technique.

12. The computer system of claim 11, wherein the cryptographic technique comprises generation of a message authentication code (MAC) for the at least the portion of the first data item.

13. The computer system of claim 4, wherein the at least one processor is programmed to, if it is determined that the retrieved at least the portion of the data item is inauthentic, evict the inauthentic at least the portion of the data item from the cache device.

14. The computer system of claim 13, wherein the at least one processor is programmed to, if it is determined that the retrieved at least the portion of the data item is inauthentic, read the data item from the address on the storage medium.

15. The computer system of claim 1, further comprising an operating system comprising programmed instructions, wherein the at least one processor executes the programmed instructions of the operating system to verify that the first data item was not modified after storage of the first data item.

16. A method for use in a computer system comprising a memory, a storage medium storing a plurality of data items at respective addresses, and a cache device also storing the plurality of data items at corresponding addresses and cache metadata providing a mapping between the address on the storage medium and the corresponding address on the cache device at which each data item is stored, the cache metadata being stored in a hierarchical data structure comprising a plurality of hierarchy levels, the method comprising acts of:

storing cache metadata on the cache device in response to a command to shut down or reboot the computer;

upon initiating a reboot of the computer system, loading only a subset of the plurality of hierarchy levels to the memory; and

verifying that a first data item of the plurality of data items was not modified after storage of the first data item in the cache device.

17. At least one recording medium storing instructions encoded thereon that, when executed by a computer system comprising a memory, a storage medium storing a plurality of data items at respective addresses, and a cache device also storing the plurality of data items at corresponding addresses and cache metadata providing a mapping between the respective address on the storage medium and the corresponding address on the cache device at which each data item is stored, the cache metadata being stored in a hierarchical data structure comprising a plurality of hierarchy levels, cause the computer system to perform a method comprising acts of:

storing cache metadata on the cache device in response to a command to shut down or reboot the computer;

upon initiating a reboot of the computer system, loading only a subset of the plurality of hierarchy levels to the memory; and

verifying that a first data item of the plurality of data items was not modified after storage of the first data item in the cache device.