EFFICIENTLY ESTIMATING COMPRESSION RATIO IN A DEDUPLICATING FILE SYSTEM

• US 20150363438A1
• Filed: 04/02/2015
• Published: 12/17/2015
• 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: Botelho, Fabiano
• Granted Patent: US 10,114,845 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1456 Hardware arrangements for backup
• CPC Class Codes: G06F 11/2074 Asynchronous techniques
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors

Abstract

A system for estimating a quantity of unique identifiers comprises a processor and a memory. The processor is configured to, for each of k times, associate a bin of a set of bins with each received identifier. The processor is further configured to determine an estimate of the quantity of unique identifiers based at least in part on an average minimum associated bin value. The memory is coupled to the processor and configured to provide the processor with instructions.

Claims

1. A system for estimating a quantity of unique identifiers, comprising:

a processor configured to;

for each of k times;

associate a bin of an ordered set of bins with each received identifier; and

determine a minimum bin number associated with each received identifier; and

determine an estimate of the quantity of unique identifiers based at least in part on an average minimum associated bin number; and

a memory coupled to the processor and configured to provide the processor with instructions.

2. A system as in claim 1, wherein the bin of the ordered set of bins is associated with each received identifier for each of the k times using one hash function of k hash functions.

3. A system as in claim 2, wherein each of the k hash functions is selected to distribute a set of input values evenly across the ordered set of bins.

4. A system as in claim 1, wherein the bin associated with each received identifier has a number identifying its place in the ordered set of bins.

5. A system as in claim 4, wherein a minimum bin number is determined associated with received identifiers for each of the k times.

6. A system as in claim 5, wherein the minimum bin number comprises a lowest bin number with an associated bin for a received identifier.

7. A system as in claim 5, wherein the minimum bin number is averaged for each of the k times to determine the average bin number.

8. A system as in claim 1, wherein determining the estimate of the quantity of unique identifiers comprises dividing the total number of bins by the average minimum associated bin value and subtracting one.

9. A system as in claim 1, wherein each received identifier comprises one of a plurality of identifiers determined from a segment of a set of segments.

10. A system as in claim 9, wherein the set of segments comprise segments determined from a data set desired to be stored by a deduplicating storage system.

11. A system as in claim 10, wherein the deduplicating storage system stores a reference to a stored segment in the event that a segment is already stored.

12. A system as in claim 10, wherein the deduplicating storage system stores meta information for reconstructing the data set from the set of segments.

13. A system as in claim 9, wherein the received identifier comprises a fingerprint of the segment.

14. A system as in claim 1, wherein an estimate of a required storage space is determined based at least in part on the estimate of the quantity of unique identifiers.

15. A system as in claim 1, wherein an error in the estimate of the quantity of unique identifiers is determined.

16. A system as in claim 15, wherein the error is based at least in part on k.

17. A system as in claim 15, wherein an estimate of a required storage space is determined based at least in part on the error in the estimate of the quantity of unique identifiers

18. A method for estimating a quantity of unique identifiers comprising:

for each of k times;

associating a bin of an ordered set of bins with each received identifier; and

determining, using a processor, a minimum bin number associated with each received identifier; and

determining an estimate of the quantity of unique identifiers based at least in part on an average minimum associated bin number.

19. A computer program product, the computer program product being embedded in a non-transitory computer readable storage medium and comprising computer instructions for:

for each of k times;

associating a bin of an ordered set of bins with each received identifier; and

determining, using a processor, a minimum bin number associated with each received identifier; and

determining an estimate of the quantity of unique identifiers based at least in part on an average minimum associated bin number.