DATA STORAGE SYSTEM, PROCESS AND COMPUTER PROGRAM FOR SUCH DATA STORAGE SYSTEM FOR REDUCING READ AND WRITE AMPLIFICATIONS

• US 20170329541A1
• Filed: 12/09/2016
• Published: 11/16/2017
• Est. Priority Date: 05/11/2016
• Status: Active Grant

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: HAYASAKA, Mitsuo, ASTON, Christopher James, SMITH, Jonathan Mark, MATSUI, Yuko, BENHAM, Simon Latimer, WILLIS, Trevor Edward
• Granted Patent: US 9,996,286 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 16/128 Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion use of snapshots for error detection or correction G06F11/14, G06F11/16
• CPC Class Codes: G06F 16/183 Provision of network file services by network file servers, e.g. by using NFS, CIFS network file access protocols H04L67/1097
• CPC Class Codes: G06F 16/1873 Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files
• CPC Class Codes: G06F 2212/283 Plural cache memories
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays

Abstract

The present disclosure relates to a data storage system, and processes and computer programs for such data storage system, for example including processing of: managing one or more metadata tree structures for storing data to one or more storage devices of the data storage system in units of blocks, each metadata tree structure including a root node pointing directly and/or indirectly to blocks, and a leaf tree level having one or more direct nodes pointing to blocks, and optionally including one or more intermediate tree levels having one or more indirect nodes pointing to indirect nodes and/or direct nodes of the respective metadata tree structure; maintaining the root node and/or nodes of at least one tree level of each of at least one metadata structure in a cache memory; and managing I/O access to data based on the one or more metadata structures.

Claims

1. A non-transitory computer readable storage medium storing a computer program including instructions to cause a computer to execute a method for managing a data storage system, the method comprising:

managing a metadata tree structure for storing data to one or more storage devices of the data storage system in units of blocks, the metadata tree structure including a root node pointing directly and/or indirectly to blocks, and a leaf tree level having one or more direct nodes pointing to blocks, and including one or more intermediate tree levels having one or more indirect nodes pointing to indirect nodes and/or direct nodes of the metadata tree structure;

performing caching of nodes of the metadata structure on the basis of the tree level, wherein the caching on the basis of the tree level includes systematically maintaining the root node in a cache memory and further includes systematically maintaining nodes of at least one first tree level of the metadata structure in the cache memory, wherein other nodes of the metadata structure, including nodes of at least one second tree level of the metadata structure, are stored to the one or more storage devices to be temporarily loaded to the cache memory upon being required for managing I/O access to data based on the metadata structure; and

managing I/O access to data based on the metadata structure, including obtaining the root node and one or more nodes of the at least one first tree level of the metadata structure systematically maintained in the cache memory from the cache memory and obtaining one or more nodes of the at least one second tree level of the metadata structure from the cache memory or the one or more storage devices.

3. The non-transitory computer readable storage medium according to claim 1, wherein

nodes of a first group associated with one or more lowest tree levels of the metadata structure, in particular including at least a tree level of direct nodes, are temporarily loaded to the cache memory when required for managing the I/O access to data based on the metadata structure, and/or nodes of a second group associated with one, more or all higher tree levels above the one or more lowest tree level in the metadata structure are systematically maintained in the cache memory.

4. The non-transitory computer readable storage medium according to claim 3, wherein

writing modified nodes of the first group to the one or more storage devices is controlled on the basis of taking a first-type of checkpoint, and writing modified nodes of the second group to the one or more storage devices is controlled on the basis of taking a second-type of checkpoint.

5. The non-transitory computer readable storage medium according to claim 3, wherein

taking a new first-type checkpoint and writing nodes of the first group which have been modified in a previous first-type checkpoint to the one or more storage devices, is performed more frequently than taking a new second-type checkpoint and writing nodes of the second group which have been modified in a previous second-type checkpoint to the one or more storage devices.

6. The non-transitory computer readable storage medium according to claim 3, wherein

modifying one or more nodes of the first group includes writing the one or more modified nodes to a non-volatile memory, and/or modifying one or more nodes of the second group includes writing respective delta data for each of the one or more modified nodes to the non-volatile memory, each respective delta data being indicative of a difference between the respective modified node of the second group as stored in the cache memory and the respective non-modified node as stored on the one or more storage devices.

7. The non-transitory computer readable storage medium according to claim 6, wherein

the size of a delta data unit is smaller than a size of an associated node.

8. The non-transitory computer readable storage medium according to claim 6, wherein

taking a new first-type checkpoint is performed when an amount of data of nodes of the first group in the non-volatile memory exceeds a first threshold, and/or

taking a new second-type checkpoint is performed when an amount of delta data associated with nodes of the second group in the non-volatile memory exceeds a second threshold.

9. The non-transitory computer readable storage medium according to claim 8, wherein

the second threshold is larger than the first threshold.

10. The non-transitory computer readable storage medium according to claim 6, wherein,

when performing a recovery operation, recovering a previously modified node of the first group includes reading the modified node of the first group from the non-volatile memory, and/or recovering a previously modified node of the second group includes reading the corresponding non-modified node from the one or more storage devices, reading corresponding delta data from the non-volatile memory, and modifying the non-modified node based on the corresponding delta data.

11. The non-transitory computer readable storage medium according to claim 6, the method further comprising:

changing a highest node tree level of the nodes of the first group to become a new lowest node tree level of the nodes of the second group based on monitoring a cache capacity, in particular if a data amount of nodes of the second group falls below a third threshold, and/or

changing a lowest node tree level of the nodes of the second group to become a new highest node tree level of the nodes of the first group based on monitoring a cache capacity, in particular if a data amount of nodes of the second group exceeds a fourth threshold.

12. The non-transitory computer readable storage medium according to claim 6, wherein,

when modifying a node of the second group associated with a new second-type checkpoint before a respective corresponding modified node of the second group associated with a previous second-type checkpoint is written to the one or more storage devices, the respective modified node of the second group associated with the new second-type checkpoint and corresponding reverse delta data is stored in the cache memory, the corresponding reverse delta data being indicative of a difference between the respective modified node of the second group as stored in the cache memory and the respective corresponding modified node of the second group associated the previous second-type checkpoint.

13. The non-transitory computer readable storage medium according claim 12, wherein,

writing the respective corresponding modified node of the second group associated with the previous second-type checkpoint to the one or more storage devices includes modifying the respective modified node of the second group as stored in the cache memory based on the corresponding reverse delta data as stored in the cache memory.

2. (canceled)

14. A method for managing a data storage system, comprising:

managing a metadata tree structure for storing data to one or more storage devices of the data storage system in units of blocks, the metadata tree structure including a root node pointing directly and/or indirectly to blocks, and a leaf tree level having one or more direct nodes pointing to blocks, and including one or more intermediate tree levels having one or more indirect nodes pointing to indirect nodes and/or direct nodes of the metadata tree structure;

performing caching of nodes of the metadata structure on the basis of the tree level, wherein the caching includes maintaining the root node and nodes of at least one tree level of each of the metadata structure in a cache memory; and

managing I/O access to data based on the metadata structure, including obtaining the root node and nodes of the at least one tree level of the metadata structure maintained in the cache memory from the cache memory and obtaining at least one node of another tree level of the metadata structure from the one or more storage devices.

15. The method according to claim 14, wherein

the root node and nodes of at least one tree level of the metadata structure are systematically maintained in the cache memory for managing the I/O access to data based on the metadata structures, and/or

nodes of at least one other tree level of each of the metadata structure are temporarily loaded to the cache memory when required for managing the I/O access to data based on the metadata structures.

16. The method according to claim 14, wherein

nodes of a first group associated with one or more lowest tree levels of the metadata structure, in particular including at least a tree level of direct nodes, are temporarily loaded to the cache memory when required for managing the I/O access to data based on the metadata structure, and/or nodes of a second group associated with one, more or all higher tree levels above the one or more lowest tree level in the metadata structure are systematically maintained in the cache memory.

17. The method according to claim 16, further comprising:

controlling writing modified nodes of the first group to the one or more storage devices on the basis of taking a first-type of checkpoint, and controlling writing modified nodes of the second group to the one or more storage devices on the basis of taking a second-type of checkpoint.

18. A data storage system connectable to one or more client computers, comprising:

a processing unit including a processor and/or a programmable logic device;

a cache memory; and

one or more storage devices and/or an interface to communicably connect with one or more storage devices;

the processing unit being adapted to execute;

managing a metadata tree structure for storing data to the one or more storage devices in units of blocks,

the metadata tree structure including a root node pointing directly and/or indirectly to blocks, and a leaf tree level having one or more direct nodes pointing to blocks, and including one or more intermediate tree levels having one or more indirect nodes pointing to indirect nodes and/or direct nodes of the metadata tree structure;

performing caching of nodes of the metadata structure on the basis of the tree level, wherein the caching includes maintaining the root node and nodes of at least one tree level of each of the metadata structure in the cache memory; and

managing I/O access to data based on the metadata structure, including obtaining the root node and nodes of the at least one tree level of the metadata structure maintained in the cache memory from the cache memory and obtaining at least one node of another tree level of the metadata structure from the one or more storage devices.

19. The data storage system according to claim 18, wherein

the root node and nodes of at least one tree level of the metadata structure are systematically maintained in the cache memory for managing the I/O access to data based on the metadata structures, and/or

nodes of at least one other tree level of each of the metadata structure are temporarily loaded to the cache memory when required for managing the I/O access to data based on the metadata structures.

20. The data storage system according to claim 18, wherein

nodes of a first group associated with one or more lowest tree levels of the metadata structure, in particular including at least a tree level of direct nodes, are temporarily loaded to the cache memory when required for managing the I/O access to data based on the metadata structure, and/or nodes of a second group associated with one, more or all higher tree levels above the one or more lowest tree level in the metadata structure are systematically maintained in the cache memory.

21. The data storage system according to claim 20, wherein

writing modified nodes of the first group to the one or more storage devices is controlled on the basis of taking a first-type of checkpoint, and writing modified nodes of the second group to the one or more storage devices is controlled on the basis of taking a second-type of checkpoint.

22. The data storage system according to claim 20, wherein

taking a new first-type checkpoint and writing nodes of the first group which have been modified in a previous first-type checkpoint to the one or more storage devices, is performed more frequently than taking a new second-type checkpoint and writing nodes of the second group which have been modified in a previous second-type checkpoint to the one or more storage devices.

23. The data storage system according to at least one of claims 20, wherein

modifying one or more nodes of the first group includes writing the one or more modified nodes to a non-volatile memory, and/or modifying one or more nodes of the second group includes writing respective delta data for each of the one or more modified nodes to the non-volatile memory, each respective delta data being indicative of a difference between the respective modified node of the second group as stored in the cache memory and the respective non-modified node as stored on the one or more storage devices.

24. The data storage system according to claim 23, wherein

the size of a delta data unit is smaller than a size of an associated node.

25. The data storage system according to claim 23, wherein

taking a new first-type checkpoint is performed when an amount of data of nodes of the first group in the non-volatile memory exceeds a first threshold, and/or

taking a new second-type checkpoint is performed when an amount of delta data associated with nodes of the second group in the non-volatile memory exceeds a second threshold.

26. The data storage system according to claim 25, wherein

the second threshold is larger than the first threshold.

27. The data storage system according to claim 23, wherein,

when performing a recovery operation, recovering a previously modified node of the first group includes reading the modified node of the first group from the non-volatile memory, and/or recovering a previously modified node of the second group includes reading the corresponding non-modified node from the one or more storage devices, reading corresponding delta data from the non-volatile memory, and modifying the non-modified node based on the corresponding delta data.

28. The data storage system according to claim 23, the method further comprising:

changing a highest node tree level of the nodes of the first group to become a new lowest node tree level of the nodes of the second group based on monitoring a cache capacity, in particular if a data amount of nodes of the second group falls below a third threshold, and/or

changing a lowest node tree level of the nodes of the second group to become a new highest node tree level of the nodes of the first group based on monitoring a cache capacity, in particular if a data amount of nodes of the second group exceeds a fourth threshold.

29. The data storage system according to claim 23, wherein,

when modifying a node of the second group associated with a new second-type checkpoint before a respective corresponding modified node of the second group associated with a previous second-type checkpoint is written to the one or more storage devices, the respective modified node of the second group associated with the new second-type checkpoint and corresponding reverse delta data is stored in the cache memory, the corresponding reverse delta data being indicative of a difference between the respective modified node of the second group as stored in the cache memory and the respective corresponding modified node of the second group associated the previous second-type checkpoint.

30. The data storage system according to claim 29, wherein,

writing the respective corresponding modified node of the second group associated with the previous second-type checkpoint to the one or more storage devices includes modifying the respective modified node of the second group as stored in the cache memory based on the corresponding reverse delta data as stored in the cache memory.