Reducing metadata in a write-anywhere storage system

• US 9,116,819 B2
• Filed: 10/17/2013
• Issued: 08/25/2015
• Est. Priority Date: 10/17/2012
• Status: Active Grant

• Current Assignee: DataDirect Networks Incorporated
• Original Assignee: DataDirect Networks Incorporated
• Inventors: Cope, Jason M., Nowoczynski, Paul J., Uppu, Pavan Kumar, Molaro, Donald J., Piszczek, Michael J., Manning, John G.
• Primary Examiner(s): Shin, Christopher
• Application Number:
  US14/056,265
• Publication Number:
  US 20140108723A1
• Time in Patent Office: 677 Days
• Field of Search: 711/117, 710/52, 710/310
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0895 of parts of caches, e.g. directory or tag array
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 12/1081 for peripheral access to main memory, e.g. direct memory access [DMA]
• 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 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/164 File meta data generation
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/163 Server or database system
• CPC Class Codes: G06F 2212/263 Network storage, e.g. SAN or NAS
• CPC Class Codes: G06F 2212/311 In host system
• CPC Class Codes: G06F 2212/463 File
• CPC Class Codes: G06F 2212/466 Metadata, control data

Abstract

Systems and methods for reducing metadata in a write-anywhere storage system are disclosed herein. The system includes a plurality of clients coupled with a plurality of storage nodes, each storage node having a plurality of primary storage devices coupled thereto. A memory management unit including cache memory is included in the client. The memory management unit serves as a cache for data produced by the clients before the data is stored in the primary storage. The cache includes an extent cache, an extent index, a commit cache and a commit index. The movement of data and metadata is by an interval tree. Methods for reducing data in the interval tree increase data storage and data retrieval performance of the system.

Claims

1. A data storage method comprising:

receiving a write request from client for a data item;

storing the data item in an extent cache while concurrently storing metadata for the data item in an extent index including updating an interval tree, the updating including

evaluating the interval tree to determine if the data item overlaps or is adjacent to an already cached data item,

when the data item overlaps or is adjacent to an already cached data item, merging the metadata for the data item into the interval tree,

when the data item overlaps or is adjacent to an already cached data item, adding a new metadata entry for the data item into the interval tree;

upon receipt of a first interrupt or event, moving the data item and the meta data for the data item from the extent cache and the extent index to a commit cache and a commit index;

upon receipt of a second interrupt or event, moving the data item from the commit cache to a primary storage device and removing the metadata for the data item from the commit index.

2. The method of claim 1 wherein the merging the metadata for the data item into the interval tree includes:

removing an existing entry from the interval tree for the already cached data item; and

adding a new entry into the interval tree reflecting a full size and pertinent information about a combined entry for the new and existing data item entries.

3. The method of claim 1 wherein the merging the metadata for the data item into the interval tree includes:

replacing information in an existing entry from the interval tree for the already cached data item with information reflecting a full size of a combined entry for the new and existing data item entries.

4. The method of claim 1 further comprising:

calculating metrics based on information stored in the interval tree including pending data to be stored to a particular primary storage device;

load balancing data and metadata stored in the extent cache and extent index based on the metrics obtained by the calculating.

5. The method of claim 1 further comprising:

load balancing data and metadata stored in the extent cache and extent index based on failure information provided by at least one client.

6. The method of claim 1 wherein the client is a computing node of a supercomputer or compute cluster.

7. The method of claim 1 wherein the client is a server computer or computer workstation.

8. The method of claim 1 wherein the primary storage device is a hard disk drive or a non-volatile memory device.

9. The method of claim 1 wherein extent cache, the commit cache, the extent index and the commit index are included in a memory management unit coupled via a high speed interconnect to the client.

10. The method of claim 1 wherein extent cache, the commit cache, the extent index and the commit index are included in a cache memory comprising non-volatile memory.

11. A computer system comprising:

a plurality of clients including a plurality of processors;

a plurality of storage nodes coupled with the plurality of clients;

a memory management unit included in each of the clients, the memory management unit including a multi-tiered cache memory, the cache memory including an upper level comprising an extent cache and an extent index and a lower level comprising a commit cache and a commit index, wherein each client and corresponding memory management unit operate in conjunction to perform actions including;

receiving a write request for a data item;

storing the data item in the extent cache while concurrently storing metadata for the data item in the extent index including updating an interval tree, the updating including

evaluating the interval tree to determine if the data item overlaps or is adjacent to an already cached data item,

when the data item overlaps or is adjacent to an already cached data item, merging the metadata for the data item into the interval tree,

when the data item overlaps or is adjacent to an already cached data item, adding a new metadata entry for the data item into the interval tree;

upon receipt of a first interrupt or event, moving the data item and the meta data for the data item from the extent cache and the extent index to the commit cache and the commit index;

upon receipt of a second interrupt or event, moving the data item from the commit cache to a primary storage device and removing the metadata for the data item from the commit index.

12. The computer system of claim 11 wherein the merging the metadata for the data item into the interval tree includes:

removing an existing entry from the interval tree for the already cached data item; and

adding a new entry into the interval tree reflecting a full size and pertinent information about a combined entry for the new and existing data item entries.

13. The computer system of claim 11 wherein the merging the metadata for the data item into the interval tree includes:

replacing information in an existing entry from the interval tree for the already cached data item with information reflecting a full size of a combined entry for the new and existing data item entries.

14. The computer system of claim 11 wherein the actions further include:

calculating metrics based on information stored in the interval tree including pending data to be stored to a particular primary storage device;

load balancing data and metadata stored in the extent cache and extent index based on the metrics obtained by the calculating.

15. The computer system of claim 11 wherein the action further include:

load balancing data and metadata stored in the extent cache and extent index based on failure information provided by at least one of the clients.

16. The computer system of claim 11 wherein the clients are arranged as a supercomputer or compute cluster.

17. The computer system of claim 11 wherein the primary storage device is a hard disk drive or a non-volatile memory device.

18. The computer system of claim 11 wherein the memory management unit is coupled via a high speed interconnect to the clients.

19. The computer system of claim 11 wherein the cache memory comprises non-volatile memory.

20. The computer system of claim 11 wherein the interval tree operates in conjunction with a splay tree organized so that more recently accessed data items appear higher in the splay tree, such that a root of the interval tree is a child in the splay tree.