High performance and memory efficient metadata caching

Patent metadata

Field	Value
Publication number	US-2017192892-A1
Application number	US-201614989392-A
Country	US
Kind code	A1
Filing date	Jan 6, 2016
Priority date	Jan 6, 2016
Publication date	Jul 6, 2017
Grant date	—

Abstract

A technique provides memory efficient caching of metadata managed by a volume layer of a storage input/output stack executing on one or more nodes of a cluster. Efficient caching of the metadata in a memory of a node may be realized through the use of a caching data structure, i.e., a page cache, configured to store a key-value pair, wherein the key is an extent key and the value is a metadata page containing the index entries. The page cache illustratively includes two data structures configured to maintain the properties of Least Recently Used (LRU) and Least Frequently Used (LFU) for the cache. The first data structure is a hash table that stores a dense tree metadata page (value) indexed by the extent key. The second data structure is a recycle queue that controls the metadata page stored in the hash table based on spatial and temporal locality of the page.

First claim

What is claimed is:

1 . A system comprising:
a processor of a storage system; and a memory coupled to the processor and configured to store a storage input/output (I/O) stack executable by the processor, the memory including a page cache configured to provide caching of metadata managed the storage I/O stack, the metadata embodied as mappings from logical block addresses of a logical unit to extent keys associated with storage locations of extents organized as metadata pages, the page cache including a hash table having one or more entries, each entry configured to store a metadata page indexed by an extent key, the page cache further including a recycle queue configured to control the metadata page stored in the hash table based on spatial and temporal locality of the metadata page.

2 . The system of claim 1 wherein the recycle queue is configured to transform the page cache into a priority cache by controlling the metadata page stored in the cache based on priority.

3 . The system of claim 1 wherein the hash table and the recycle queue are configured to maintain properties of Least Recently Used (LRU) and Least Frequently Used (LFU) for the metadata pages in the cache.

4 . The system of claim 3 wherein the recycle queue comprises a multi-level data structure and wherein each level indicates a priority associated with each metadata page at a time of insertion into the hash table of the page cache.

5 . The system of claim 4 wherein each level of the recycle queue is organized as a doubly-linked list of elements and wherein each element has a first pointer referencing a corresponding entry in the hash table that includes a second pointer referencing the element in the recycle queue.

6 . The system of claim 5 wherein a position of the element within the doubly-linked list indicates an ordinal ranking of access to the metadata page corresponding to the element to maintain the LRU property of the page cache.

7 . The system of claim 6 wherein each entry of the hash table includes a pointer field configured to store a pointer that references a corresponding element of the recycle queue.

8 . The system of claim 7 wherein each entry of the hash table further includes a reference count field configured to store a first value indicating a number of references to the metadata page of the entry.

9 . The system of claim 8 wherein each entry of the hash table further includes a recycle count field configured to store a second value indicating a number of times the metadata page of the entry is inserted into the recycle queue.

10 . A method comprising:
storing a storage input/output (I/O) stack in a memory coupled to a processor, the storage I/O stack executable by the processor to manage metadata cached in a page cache of the memory, the metadata embodied as mappings from logical block addresses of a logical unit to extent keys associated with storage locations of extents organized as metadata pages; organizing the page cache as a hash table and a recycle queue; storing a metadata page in an entry of the hash table; indexing the metadata page by an extent key; and controlling the metadata page stored in the hash table using the recycle queue, wherein the metadata page is controlled based on spatial and temporal locality of the metadata page.

11 . The method of claim 10 wherein controlling the metadata page comprises:
controlling the metadata page stored in the cache based on priority to transform the page cache into a priority cache.

12 . The method of claim 11 further comprising:
configuring the hash table and the recycle queue to maintain properties of Least Recently Used (LRU) and Least Frequently Used (LFU) for the metadata pages in the cache.

13 . The method of claim 12 further comprising:
organizing the recycle queue as a multi-level data structure, wherein each level indicates a priority associated with each metadata page at a time of insertion into the hash table of the page cache.

14 . The method of claim 13 further comprising:
organizing each level of the recycle queue as a doubly-linked list of elements, wherein each element has a first pointer referencing a corresponding entry in the hash table that includes a second pointer referencing the element in the recycle queue.

15 . The method of claim 14 further comprising:
indicating an ordinal ranking of access to the metadata page corresponding to the element based on a position of the element within the doubly-linked list to maintain the LRU property of the page cache.

16 . The method of claim 15 further comprising:
storing a pointer that references a corresponding element of the recycle queue in a pointer field of each entry of the hash table.

17 . The method of claim 16 further comprising:
storing a first value indicating a number of references to the metadata page of each entry in a reference count field of the respective entry of the hash table.

18 . The method of claim 17 further comprising:
storing a second value indicating a number of times the metadata page of each entry is inserted into the recycle queue in a recycle count field of the respective entry of the hash table.

19 . A non-transitory computer readable medium including program instructions for execution on a processor of a storage system, the program instructions when executed operable to:
store a storage input/output (I/O) stack in a memory coupled to a processor, the storage I/O stack executable by the processor to manage metadata cached in a page cache of the memory, the metadata embodied as mappings from logical block addresses of a logical unit to extent keys associated with storage locations of extents organized as metadata pages; organize the page cache as a hash table and a recycle queue; store a metadata page in an entry of the hash table; index the metadata page by an extent key; and control the metadata page stored in the hash table using the recycle queue, wherein the metadata page is controlled based on spatial and temporal locality of the metadata page.

20 . The non-transitory computer readable medium of claim 19 wherein the program instructions when executed to control the metadata page is are further operable to:
control the metadata page stored in the page cache based on priority to transform the page cache into a priority cache.

Assignees

• Netapp Inc

Inventors

• Pundir Anshul
• Pednekar Ashwin
• Zheng Ling
• Federwisch Michael L

Classifications

• G06F12/0804 Primary

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

• G06F2212/313

  In storage device · CPC title

• G06F12/0824 Primary

  Distributed directories, e.g. linked lists of caches · CPC title

• G06F12/0868

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

• G06F2212/1008

  Correctness of operation, e.g. memory ordering · CPC title