Hierarchically tagged cache

• US 8,874,850 B1
• Filed: 05/10/2012
• Issued: 10/28/2014
• Est. Priority Date: 05/10/2012
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Goodson, Garth, Shao, Minglong, Smith, Keith
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): WONG, NANCI N
• Application Number:
  US13/468,798
• Time in Patent Office: 901 Days
• Field of Search: 711/133
• US Class Current: 711/133
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 12/0893 Caches characterised by their organisation or structure
• CPC Class Codes: G06F 12/0895 of parts of caches, e.g. directory or tag array
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/461 Sector or disk block
• CPC Class Codes: G06F 2212/465 Structured object, e.g. database record

Abstract

A hierarchically tagged cache provides abstraction between access requests for data and the cached data. The cache is managed by hierarchical layers of indexes including reference to the data. Access requests indicate a header for the requested data, which is associated with one of the layers. Cache management determines what layer is associated with the header, and can traverse the indexes, beginning at the layer associated with the header, to access the data. If the header does not exist at the index of that layer, it can be created. Indexes can be appropriately updated with indexes at each layer being referenced by one or more indexes of the layer higher up in the hierarchy.

Claims

1. A method for cache management, comprising:

identifying, by a cache device controller, a header of a received data access request as being associated with one of a filesystem layer, a physical mapping layer, or an indirection layer, where each layer is indicated with an indexing structure of headers and the indexing structure of each of the layers is in a cache corresponding to the cache device controller,

wherein the cache device controller manages headers in the cache hierarchically, manages indexes of the physical mapping layer indexing structure to map to physical addresses for data buffers, manages indexes of the indirection layer indexing structure each to map to an index of the physical mapping layer, and manages indexes of the filesystem layer indexing structure each to map to an index of the indirection layer; and

accessing the data buffer when an index includes the header, wherein accessing the data buffer comprises hierarchically traversing the indexes of the layers to a physical address for the data buffer, beginning at the index of the layer identified as being associated with the header, wherein the header comprises metadata when associated with either the filesystem layer or the indirection layer;

when an index does not include the header, creating an entry, for the header, in the indexing structure of the layer identified as being associated with the header;

maintaining a generation count for each data buffer, wherein for each data buffer the generation count is incremented each time the data buffer is evicted from the cache or each time the data buffer is used to hold a different data block; and

maintaining a generation count in each index entry created that references a data buffer, wherein an index entry that has a generation count different from a generation count of the referenced data buffer is evicted.

2. The method of claim 1, wherein each indexing structure includes a separate lookup table, and wherein accessing the data buffer further comprises using an identifier of the header as a key for the lookup table of the index for the layer associated with the header.

3. The method of claim 1, wherein the indirection layer comprises a first indirection layer, and wherein the identifying further comprises:

identifying the header as being associated with one of the filesystem layer, the physical mapping layer, the first indirection layer, or a second indirection layer.

4. The method of claim 1, wherein the cache supports de-duplication of data buffers, where one or more index entries of the indirection layer map to an index entry of the physical mapping layer.

5. The method of claim 1, wherein accessing the data buffer further comprises:

updating information in a header associated with a layer different than the one associated with the header in the received request.

6. The method of claim 1, wherein for a write request, the cache device controller delays mapping of the header to an entry of the index of a different layer to allow allocation of contiguous addresses for the write.

7. A cache system comprising:

a cache storage device to store multiple data buffers; and

a cache controller to,

manage access to the data buffers of the cache storage device, the cache controller to identify a header indicated in a data access request as being associated with one of a filesystem layer, a physical mapping layer, or an indirection layer, where each layer is indicated with an indexing structure of headers and the indexing structures are in the cache storage device,

manage the headers hierarchically,

manage indexes of the physical mapping layer indexing structure to map to physical addresses for data buffers,

manage indexes of the indirection layer indexing structure each to map to an index of the physical mapping layer, and

manage indexes of the filesystem layer indexing structure each to map to an index of the indirection layer,

access a data buffer when one of the indexing structures includes the header, wherein the cache controller to access the data buffer comprises the cache controller to hierarchically traverse the indexes of the layers to a physical address for the data buffer, beginning at the index of the layer identified as being associated with the header, wherein the header comprises metadata when associated with either the filesystem layer or the indirection layer; and

when an index does not include the header, create an entry, for the header, in the indexing structure of the layer identified as being associated with the header;

maintain a generation count for each data buffer, wherein for each data buffer the generation count is incremented each time the data buffer is evicted from the cache or each time the data buffer is used to hold a different data block; and

maintain a generation count in each index entry created that references a data buffer, wherein an index entry that has a generation count different from a generation count of the referenced data buffer is evicted.

8. The system of claim 7, wherein each indexing structure includes a separate lookup table, and wherein to access the data buffer further comprises use of an identifier of the header as a key for the lookup table of the index for the layer associated with the header.

9. The system of claim 7, wherein the indirection layer comprises a first indirection layer, and wherein to identify further comprises the cache controller to identify the header as being associated with one of the filesystem layer, the physical mapping layer, the first indirection layer, or a second indirection layer.

10. The system of claim 7, wherein the cache controller supports de-duplication of data buffers, where one or more index entries of the indirection layer map to an index entry of the physical mapping layer.

11. The system of claim 7, wherein the cache controller to access the data buffer further comprises the cache controller to update information in a header associated with a layer different than the one associated with the header in the data access request.

12. The system of claim 7, wherein for a write request, the cache controller delays mapping of the header to an entry of the index of a different layer to allow allocation of contiguous addresses for the write.

13. A non-transitory computer-readable storage medium having program instructions stored thereon, the program instructions comprising program instructions to:

identify a header of a received data access request as being associated with one of a filesystem layer, a physical mapping layer, or an indirection layer, where each layer is indicated with an indexing structure of headers and the indexing structure of each of the layers is in a cache of a computing device,

manage headers in the cache hierarchically, manage indexes of the physical mapping layer indexing structure to map to physical addresses for data buffers, manage indexes of the indirection layer indexing structure each to map to an index of the physical mapping layer, and manage indexes of the filesystem layer indexing structure each to map to an index of the indirection layer;

access the data buffer when an index includes the header, wherein the program instructions to access the data buffer comprise program instructions to hierarchically traverse the indexes of the layers to a physical address for the data buffer, beginning at the index of the layer identified as being associated with the header, wherein the header comprises metadata when associated with either the filesystem layer or the indirection layer; and

when an index does not include the header, create an entry, for the header, in the indexing structure of the layer identified as being associated with the header;

maintain a generation count for each data buffer, wherein for each data buffer the generation count is incremented each time the data buffer is evicted from the cache or each time the data buffer is used to hold a different data block; and

maintain a generation count in each index entry created that references a data buffer, wherein an index entry that has a generation count different from a generation count of the referenced data buffer is evicted.

14. The non-transitory computer-readable storage medium of claim 13, wherein each indexing structure includes a separate lookup table, and wherein the program instructions to access the data buffer further comprises program instructions to use an identifier of the header as a key for the lookup table of the index for the layer associated with the header.

15. The non-transitory computer-readable storage medium of claim 13, wherein the indirection layer comprises a first indirection layer, and wherein the program instructions to identify comprise program instructions to:

identify the header as being associated with one of the filesystem layer, the physical mapping layer, the first indirection layer, or a second indirection layer.

16. The non-transitory computer-readable storage medium of claim 13, further comprising program instructions to support de-duplication of data buffers, where one or more index entries of the indirection layer map to an index entry of the physical mapping layer.

17. The non-transitory computer-readable storage medium of claim 13, wherein the program instructions to access the data buffer further comprise program instructions to:

update information in a header associated with a layer different than the one associated with the header in the received request.

18. The non-transitory computer-readable storage medium of claim 13, wherein the program instructions further comprise program instructions to delay mapping of a header to an entry of the index of a different layer to allow allocation of contiguous addresses for a write request.