Method to optimize random IOS of a storage device for multiple versions of backups using incremental metadata

• US 10,055,420 B1
• Filed: 06/30/2015
• Issued: 08/21/2018
• Est. Priority Date: 06/30/2015
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Pogde, Prashant, Allu, Yamini, Kamat, Mahesh
• Primary Examiner(s): Oberly, Van
• Application Number:
  US14/788,598
• Time in Patent Office: 1,148 Days
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 16/184 implemented as replicated file system
• CPC Class Codes: G06F 16/185 Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof details of archiving G06F16/11
• CPC Class Codes: G06F 2201/00 Indexing scheme relating to error detection, to error correction, and to monitoring

Abstract

Methods, systems, and apparatus for optimizing a cache memory device of a storage system are described. In one embodiment, a first base segment tree representing a first full backup including data and metadata describing the data is cached in a cache memory device. Subsequently, a plurality of incremental segment trees representing incremental backups to the first full backup are cached in the cache memory device. Each of incremental segment trees corresponding to the changes to the first full backup, without modifying the first base segment tree in response to the changes. At least two of the incremental segment trees are merged into an updated incremental segment tree to reduce a storage space of the cache memory device to store the incremental segment trees. The updated incremental segment tree comprises data and metadata represented by two or more incremental segment trees.

Claims

1. A computer-implemented method for optimizing a cache memory device of a storage system, the method comprising:

caching a first base segment tree in a cache memory device, the first base segment tree representing deduplicated segments of a file that is stored in a storage disk of a storage system;

in response to a plurality of changes of the file subsequently received from a client at different points in time, caching in the cache memory device a plurality of incremental segment trees corresponding to the changes of the file, without modifying the first base segment tree in response to the changes, wherein one or more of the incremental segment trees together with the first base segment tree collectively represent a different one of the changes at a particular time; and

merging two or more of the incremental segment trees into an updated incremental segment tree to reduce a storage space of the cache memory device to store the incremental segment trees, wherein the updated incremental segment tree comprises data and metadata represented by two or more incremental segment trees, wherein merging two or more of the incremental segment trees into an updated incremental segment tree comprises;

determining whether two or more of the incremental segment trees stored in the cache memory device exceeds a predetermined threshold;

when the predetermined threshold is exceeded, merging the two or more of the incremental segment trees into the undated incremental segment tree; and

removing at least one of the two or more incremental segment trees from the cache memory device.

2. The method of claim 1, wherein merging two or more of the incremental segment trees is performed in response to a request for cache eviction to make room for storing other data in the cache memory device.

3. The method of claim 1, wherein merging two or more of the incremental segment trees is performed in response to a subsequent request for accessing data associated with at least one of the deduplicated segments represented by at least one of the incremental segment trees.

4. The method of claim 1, wherein merging two or more of the incremental segment trees is periodically performed to reduce a number of incremental segment trees stored in the cache memory device.

5. A computer-implemented method for optimizing a cache memory device of a storage system, the method comprising:

caching a first base segment tree in a cache memory device, the first base segment tree representing deduplicated segments of a file that is stored in a storage disk of a storage system;

in response to a plurality of changes of the file subsequently received from a client at different points in time, caching in the cache memory device a plurality of incremental segment trees corresponding to the changes of the file, without modifying the first base segment tree in response to the changes, wherein one or more of the incremental segment trees together with the first base segment tree collectively represent a different one of the changes at a particular time;

merging two or more of the incremental segment trees into an updated incremental segment tree to reduce a storage space of the cache memory device to store the incremental segment trees, wherein the updated incremental segment tree comprises data and metadata represented by two or more incremental segment trees;

determining whether a number of merges of incremental segment trees exceeds a predetermined threshold;

when the number of merges exceeds the predetermined threshold, merging the updated incremental segment tree with the first base segment tree to generate a second base segment tree, the second base segment tree being an updated base segment that includes data and metadata of both the first base segment tree and the updated incremental segment tree; and

storing the second base segment tree in the storage disk to replace the first base segment tree stored therein.

6. The method of claim 5, wherein the second base segment tree is written to the storage disk in response to a signal indicating that a current access session to the file has been closed.

7. A storage system, comprising:

one or more storage units configured to;

store a first base segment tree, the first base segment tree representing deduplicated segments of a file that is stored in the one or more storage units; and

a cache memory device configured to;

cache the first base segment tree;

in response to a plurality of changes of the file subsequently received from a client at different points in time, cache a plurality of incremental segment trees corresponding to the changes of the file, without modifying the first base segment tree in response to the changes, wherein one or more of the incremental segment trees together with the first base segment tree collectively represent a different one of the changes at a particular time; and

merge two or more of the incremental segment trees into an updated incremental segment tree to reduce a storage space of the cache memory device to store the incremental segment trees, wherein the updated incremental segment tree comprises data and metadata represented by two or more incremental segment trees, wherein merging two or more of the incremental segment trees into an updated incremental segment tree comprises;

determining whether two or more of the incremental segment trees stored in the cache memory device exceeds a predetermined threshold;

when the predetermined threshold is exceeded, merging the two or more of the incremental segment trees into the updated incremental segment tree; and

removing at least one of the two or more incremental segment trees from the cache memory device.

8. The storage system of claim 7, wherein merging two or more of the incremental segment trees is performed in response to a request for cache eviction to make room for storing other data in the cache memory device.

9. The storage system of claim 7, wherein merging two or more of the incremental segment trees is performed in response to a subsequent request for accessing data associated with at least one of the deduplicated segments represented by at least one of the incremental segment trees.

10. The storage system of claim 7, wherein merging two or more of the incremental segment trees is periodically performed to reduce a number of incremental segment trees stored in the cache memory device.

11. A storage system comprising:

one or more storage units configured to;

store a first base segment tree, the first base segment tree representing deduplicated segments of a file that is stored in the one or more storage units;

a cache memory device configured to;

cache the first base segment tree;

in response to a plurality of changes of the file subsequently received from a client at different points in time, cache a plurality of incremental segment trees corresponding to the changes of the file, without modifying the first base segment tree in response to the changes, wherein one or more of the incremental segment trees together with the first base segment tree collectively represent a different one of the changes at a particular time; and

merge two or more of the incremental segment trees into an updated incremental segment tree to reduce a storage space of the cache memory device to store the incremental segment trees, wherein the updated incremental segment tree comprises data and metadata represented by two or more incremental segment trees; and

a storage/cache manager executed on a processor that is configured to;

determine whether a number of merges of incremental segment trees exceeds a predetermined threshold;

when the number of merges exceeds the predetermined threshold, the cache memory device is further configured to;

merge the updated incremental segment tree with the first base segment tree to generate a second base segment tree, the second base segment tree being an updated base segment that includes data and metadata of both the first base segment tree and the updated incremental segment tree; and

the one or more storage units are further configured to;

store the second base segment tree to replace the first base segment tree stored therein.

12. The storage system of claim 11, wherein the second base segment tree is written to the one or more storage units in response to a signal indicating that a current access session to the file has been closed.

13. A non-transitory computer-readable storage medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations for optimizing a cache memory device of a storage system, the operations comprising:

caching a first base segment tree in a cache memory device, the first base segment tree representing deduplicated segments of a file that is stored in a storage disk of a storage system;

in response to a plurality of changes of the file subsequently received from a client at different points in time, caching in the cache memory device a plurality of incremental segment trees corresponding to the changes of the file, without modifying the first base segment tree in response to the changes, wherein one or more of the incremental segment trees together with the first base segment tree collectively represent a different one of the changes at a particular time;

merging two or more of the incremental segment trees into an updated incremental segment tree to reduce a storage space of the cache memory device to store the incremental segment trees, wherein the updated incremental segment tree comprises data and metadata represented by two or more incremental segment trees, wherein merging two or more of the incremental segment trees into an updated incremental segment tree comprises;

determining whether two or more of the incremental segment trees stored in the cache memory device exceeds a predetermined threshold;

when the predetermined threshold is exceeded, merging the two or more of the incremental segment trees into the undated incremental segment tree; and

removing at least one of the two or more incremental segment trees from the cache memory device.

14. The non-transitory computer-readable storage medium of claim 13, wherein merging two or more of the incremental segment trees is performed in response to a request for cache eviction to make room for storing other data in the cache memory device.

15. The non-transitory computer-readable storage medium of claim 13, wherein merging two or more of the incremental segment trees is performed in response to a subsequent request for accessing data associated with at least one of the deduplicated segments represented by at least one of the incremental segment trees.

16. The non-transitory computer-readable storage medium of claim 13, wherein merging two or more of the incremental segment trees is periodically performed to reduce a number of incremental segment trees stored in the cache memory device.

17. A non-transitory computer-readable storage medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations for optimizing a cache memory device of a storage system, the operations comprising:

caching a first base segment tree in a cache memory device, the first base segment tree representing deduplicated segments of a file that is stored in a storage disk of a storage system;

in response to a plurality of changes of the file subsequently received from a client at different points in time, caching in the cache memory device a plurality of incremental segment trees corresponding to the changes of the file, without modifying the first base segment tree in response to the changes, wherein one or more of the incremental segment trees together with the first base segment tree collectively represent a different one of the changes at a particular time;

merging two or more of the incremental segment trees into an updated incremental segment tree to reduce a storage space of the cache memory device to store the incremental segment trees, wherein the updated incremental segment tree comprises data and metadata represented by two or more incremental segment trees;

determining whether a number of merges of incremental segment trees exceeds a predetermined threshold;

when the number of merges exceeds the predetermined threshold, merging the updated incremental segment tree with the first base segment tree to generate a second base segment tree, the second base segment tree being an updated base segment that includes data and metadata of both the first base segment tree and the updated incremental segment tree; and

storing the second base segment tree in the storage disk to replace the first base segment tree stored therein.

18. The non-transitory computer-readable storage medium of claim 17, wherein the second base segment tree is written to the storage disk in response to a signal indicating that a current access session to the file has been closed.