System and method for estimating duplicate data

• US 8,793,226 B1
• Filed: 08/28/2007
• Issued: 07/29/2014
• Est. Priority Date: 08/28/2007
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Yadav, Sandeep, Trimmer, Don, Cho, Yong
• Primary Examiner(s): HASAN, SYED HAROON
• Application Number:
  US11/846,033
• Time in Patent Office: 2,527 Days
• US Class Current: 707/692
• 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 3/0604 Improving or facilitating administration, e.g. storage management

Abstract

The present invention provides a system and method for estimating duplicate data in a storage system. A duplicate estimation application executes on a client of a storage system selects an element from an intended destination such as, e.g., a data store of the storage system. If the element is a file (or other data container), the application reads data from the file and computes a fingerprint of the read data. The computed fingerprint is then logged in a fingerprint database, which is illustratively stored on a storage device connected to the client executing the application. This process repeats until the entire file (or other data container) has been read and fingerprinted. Once all elements have been scanned, fingerprinted and recorded, the application identifies any unique entries within the fingerprint database. Utilizing this information, the application computes an estimated space savings that may be realized by employing a data de-duplication technique.

Claims

1. A method for estimating duplicate data, comprising:

executing a duplicate estimation application on a system having a processor and memory;

selecting a data element stored on a storage device of the system;

reading a plurality of segments of data from the data element;

computing a fingerprint for each of the plurality of segments to produce a plurality of fingerprints;

storing the plurality of fingerprints in a fingerprint database;

identifying a total number of fingerprints entries in the fingerprint database;

identifying a total number of unique fingerprint entries of the total number of fingerprint entries in the fingerprint database, wherein each unique fingerprint represents a single instance of a fingerprint in the total number of fingerprint entries in the fingerprint database;

calculating an estimated amount of duplicate data by multiplying a size of a segment of data to a value obtained by subtracting the total number of unique fingerprint entries in the fingerprint database from the total number of fingerprint entries in the fingerprint database; and

providing the calculated estimated amount of duplicate data to a display, wherein the calculated estimated amount of duplicate data indicates estimated storage space saving that is realized by employing a data de-duplication technique to eliminate the duplicate data.

2. The method of claim 1 wherein the fingerprint database comprises a fingerprint database file.

3. The method of claim 1 wherein the selected data element comprises a file.

4. The method of claim 1 wherein size of the segment of data comprises 4 KB.

5. The method of claim 1 wherein the selected data element comprises a data container.

6. The method of claim 1 wherein reading the plurality of segments of data from the data element comprises reading the plurality of segments of data from a sub-component of the system.

7. A non-transitory computer-readable storage medium stored with executable program instructions for execution by a processor, the non-transitory computer-readable storage medium comprising:

program instructions that select a data element stored on a computer;

program instructions that read a plurality of segments of data from the data element;

program instructions that compute a fingerprint for each of the plurality of segments to produce a plurality of fingerprints;

program instructions that store the plurality of fingerprints in a fingerprint database;

program instructions that identify a total number of fingerprint entries in the fingerprint database;

program instructions that identify a total number of unique fingerprint entries of the total number of fingerprint entries in the fingerprint database, wherein each unique fingerprint represents a single instance of a fingerprint in the total number of fingerprint entries in the fingerprint database;

program instructions that calculate an estimated amount of duplicate data by multiplying a size of a segment of data to a value obtained by subtracting the total number of unique fingerprint entries in the fingerprint database from the total number of fingerprint entries in the fingerprint database; and

program instructions that provide the calculated estimated amount of duplicate data to a display, wherein the calculated estimated amount of duplicate data indicates estimated storage space saving that is realized by employing a data de-duplication technique to eliminate the duplicate data.

8. A computing system, comprising:

a fingerprint database; and

a processor configured to operatively connect with the fingerprint database and a storage system, the processor configured to execute a duplicate estimation application to;

(i) select a plurality of data elements from the storage system,

(ii) read data from the plurality of data elements,

(iii) compute a fingerprint for each of the plurality of data elements to produce a plurality of fingerprints,

(iv) populate the fingerprint database with the plurality of fingerprints,

(v) identify a total number of fingerprints entries in the fingerprint database populated with the plurality of fingerprints,

(vi) identify a total number of unique fingerprint entries of the total number of fingerprint entries in the fingerprint database wherein each unique fingerprint represents a single instance of a fingerprint in the total number of is fingerprint entries in the fingerprint database,

(vii) compute an estimated amount of duplicate data by multiplying a size of a segment of data to a value obtained by subtracting the total number of unique fingerprint entries in the fingerprint database from the total number of fingerprint entries in the fingerprint database, and

(viii) providing the estimated amount of duplicate data to a display, wherein the estimated amount of duplicate data indicates estimated storage space saving that is realized by employing a data de-duplication technique to eliminate the duplicate data.

9. The system of claim 8 wherein the fingerprint database comprises a fingerprint log file stored on a storage device operatively connected with the processor.

10. The system of claim 8 wherein the plurality of data elements comprises a file.

11. The system of claim 8 wherein the plurality of data elements comprises a data container.

12. The system of claim 8 wherein the duplicate estimation application is further configured to, in response to selecting a directory as one of the plurality of data elements, read each data element within the directory and further configured to populate the fingerprint database based on the data elements within the directory.

13. The system of claim 8 wherein the duplicate estimation application is further configured to, in response to selecting a link as one of the plurality of data elements, record state information.

14. The system of claim 13 wherein the state information is utilized to prevent overestimation of the duplicate data due to a link to a data element.

15. The system of claim 13 wherein the duplicate estimation application is further configured to increment a counter to track a number of links to a fingerprint in the fingerprint database.

16. A system configured to estimate duplicate data, comprising:

means for executing a duplicate estimation application on a system having a processor and a memory;

means for selecting a data element stored on a storage device of the system;

means for reading a plurality of segments from the data element;

means for computing a fingerprint for each of the plurality of segments to produce a plurality of fingerprints;

means for storing the plurality of fingerprint in a fingerprint database;

means for identifying a total number of fingerprint entries in the fingerprint database;

means for identifying a total number of unique fingerprint entries of the total number of fingerprint entries in the fingerprint database wherein each unique fingerprint is represents a single instance of a fingerprint in the total number of fingerprint entries in the fingerprint database;

means for calculating an estimated amount of duplicate data by multiplying a size of a segment of data to a value obtained by subtracting the total number of unique fingerprint entries in the fingerprint database from the total number of fingerprint entries in the fingerprint database; and

means for providing the calculated estimated amount of duplicate data to a display wherein the calculated estimated amount of duplicate data indicates estimated storage space saving that is realized by employing a data de-duplication technique to eliminate the duplicate data.

17. The system of claim 16 further comprising means for estimating bandwidth savings using the estimated amount of duplicate data.