Method and apparatus for determining optimal chunk sizes of a deduplicated storage system

• US 8,639,669 B1
• Filed: 12/22/2011
• Issued: 01/28/2014
• Est. Priority Date: 12/22/2011
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Douglis, Frederick, Shilane, Philip N., Wallace, Grant
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): ALLEN, NICHOLAS E
• Application Number:
  US13/334,732
• Time in Patent Office: 768 Days
• Field of Search: 707/692, 707/747, 707/812
• US Class Current: 707/692
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Techniques for evaluating deduplication effectiveness of data chunks in a storage system are described herein. In one embodiment, metadata of first data chunks associated with a deduplicated storage system is examined, where the first data chunks have been partitioned according to a first chunk size. A second chunk size is calculated based on the examination of the metadata of first data chunks. Metadata of the first data chunks is merged according to the second chunk size to represent second data chunks to which the first data chunks would have been merged. A deduplication rate of the second data chunks is determined based on the merged metadata.

Claims

1. A computer-implemented method, comprising:

receiving a request to evaluate deduplication effectiveness of a deduplicated storage system;

examining, in response to the request, metadata of first data chunks associated with the deduplicated storage system, the first data chunks being partitioned from one or more data files according to a first chunk size;

calculating a plurality of new chunk sizes based on the examination of the metadata of first data chunks;

merging metadata of the first data chunks according to each of the plurality of new chunk sizes to represent new data chunks to which the first data chunks would have been merged;

determining a deduplication rate of each of the new data chunks based on the merged metadata; and

selecting a second chunk size from the plurality of new chunk sizes, wherein the second chunk size has the highest deduplication rate among all the plurality of new chunk sizes.

2. The method of claim 1, further comprising:

determining whether the deduplication rate satisfies a predetermined condition;

merging the first data chunks into the second data chunks according to the second chunk size if the deduplication rate satisfies the predetermined condition; and

storing the second data chunks in the deduplicated storage system replacing the first data chunks.

3. The method of claim 1, further comprising:

determining whether the second data chunk size improves storage system properties including write throughput by a predetermined amount;

merging the first data chunks into the second data chunks according to the second chunk size if the second data chunk size improves the storage system properties; and

storing the second data chunks in the deduplicated storage system replacing the first data chunks.

4. The method of claim 1, wherein the second chunk size is one of a plurality of chunk size candidates, wherein for each of the plurality of chunk size candidates, merging metadata and determining deduplication rate are iteratively performed.

5. The method of claim 4, further comprising selecting a final chunk size candidate based on the deduplication rates associated with the plurality of chunk size candidates.

6. The method of claim 5, wherein the final chunk size candidate is selected further based on a cost to maintain metadata associated with the final chunk size candidate and corresponding data chunks to be formed based on the final chunk size candidate.

7. The method of claim 4, further comprising, prior to examining metadata of the first data chunks, generating the first data chunks by partitioning original data chunks stored in the deduplicated storage system according to an initial chunk size, wherein the initial chunk size is smaller than or equal to the smallest chunk size candidate amongst the chunk size candidates.

8. The method of claim 4, wherein the second chunk size is within a predetermined proximity of a selected chunk size selected from the plurality of chunk size candidates during a corresponding iteration.

9. The method of claim 1, wherein boundaries of the second data chunks is determined based on values of metadata or features of the first data chunks to be merged therein.

10. A non-transitory computer-readable storage medium having instructions stored therein, which when executed by a computer, cause the computer to perform operations comprising:

receiving a request to evaluate deduplication effectiveness of a deduplicated storage system;

examining, in response to the request, metadata of first data chunks associated with the deduplicated storage system, the first data chunks being partitioned from one or more data files according to a first chunk size;

calculating a plurality of new chunk sizes based on the examination of the metadata of first data chunks;

merging metadata of the first data chunks according to each of the plurality of new chunk sizes to represent new data chunks to which the first data chunks would have been merged;

determining a deduplication rate of each of the new data chunks based on the merged metadata; and

selecting a second chunk size from the plurality of new chunk sizes, wherein the second chunk size has the highest deduplication rate among all the plurality of new chunk sizes.

11. The computer-readable storage medium of claim 10, wherein the operations further comprise:

determining whether the deduplication rate satisfies a predetermined condition;

merging the first data chunks into the second data chunks according to the second chunk size if the deduplication rate satisfies the predetermined condition; and

storing the second data chunks in the deduplicated storage system replacing the first data chunks.

12. The computer-readable storage medium of claim 10, wherein the operations further comprise:

determining whether the second data chunk size improves storage system properties including write throughput by a predetermined amount;

merging the first data chunks into the second data chunks according to the second chunk size if the second data chunk size improves the storage system properties; and

storing the second data chunks in the deduplicated storage system replacing the first data chunks.

13. The computer-readable storage medium of claim 10, wherein the second chunk size is one of a plurality of chunk size candidates, wherein for each of the plurality of chunk size candidates, merging metadata and determining deduplication rate are iteratively performed.

14. The computer-readable storage medium of claim 13, wherein the operations further comprise selecting a final chunk size candidate based on the deduplication rates associated with the plurality of chunk size candidates.

15. The computer-readable storage medium of claim 14, wherein the final chunk size candidate is selected further based on a cost to maintain metadata associated with the final chunk size candidate and corresponding data chunks to be formed based on the final chunk size candidate.

16. The computer-readable storage medium of claim 13, wherein the operations further comprise, prior to examining metadata of the first data chunks, generating the first data chunks by partitioning original data chunks stored in the deduplicated storage system according to an initial chunk size, wherein the initial chunk size is smaller than or equal to the smallest chunk size candidate amongst the chunk size candidates.

17. The computer-readable storage medium of claim 13, wherein the second chunk size is within a predetermined proximity of a selected chunk size selected from the plurality of chunk size candidates during a corresponding iteration.

18. The computer-readable storage medium of claim 10, wherein boundaries of the second data chunks is determined based on values of metadata or features of the first data chunks to be merged therein.

19. A storage system, comprising:

a storage unit to store a plurality of deduplicated data chunks; and

a chunk evaluation unit coupled to the storage unit configured to

receive a request to evaluate deduplication effectiveness of a deduplicated storage system,

examine metadata of first data chunks partitioned from one or more data files according to a first chunk size,

calculate a plurality of new chunk sizes based on the examination of the metadata of first data chunks,

merge metadata of the first data chunks according to each of the plurality of new chunk sizes to represent new data chunks to which the first data chunks would have been merged,

determine a deduplication rate of each of the new data chunks based on the merged metadata,

select a second chunk size from the plurality of new chunk sizes, wherein the second chunk size has the highest deduplication rate among all the plurality of new chunk sizes.

20. The system of claim 19, further comprising a chunking unit configured to:

determine whether the deduplication rate satisfies a predetermined condition;

merge the first data chunks into the second data chunks according to the second chunk size if the deduplication rate satisfies the predetermined condition; and

store the second data chunks in the deduplicated storage system replacing the first data chunks.

21. The system of claim 19, further comprising a chunking unit configured to:

determine whether the second data chunk size improves storage system properties including write throughput by a predetermined amount;

merge the first data chunks into the second data chunks according to the second chunk size if the second data chunk size improves the storage system properties; and

store the second data chunks in the deduplicated storage system replacing the first data chunks.

22. The system of claim 19, wherein the second chunk size is one of a plurality of chunk size candidates, wherein for each of the plurality of chunk size candidates, merging metadata and determining deduplication rate are iteratively performed.

23. The system of claim 22, wherein a final chunk size candidate is selected based on the deduplication rates associated with the plurality of chunk size candidates.

24. The system of claim 23, wherein the final chunk size candidate is selected further based on a cost to maintain metadata associated with the final chunk size candidate and corresponding data chunks to be formed based on the final chunk size candidate.