IP Library › Granted Patent US 9,047,304
Granted Patent B2
US 9,047,304 · App. 13/305,218 · Granted Jun 2, 2015

Optimization of fingerprint-based deduplication

Inventors: Mark L. Yakushev (San Jose, CA); Mark A. Smith (Los Gatos, CA)
Assignee: International Business Machines Corporation
G06F17/30159G06F17/30156
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 9,047,304
App. No.
13/305,218
Granted
Jun 2, 2015
Kind
B2
Abstract

Described are embodiments of an invention for identifying chunk boundaries for optimization of fingerprint-based deduplication in a computing environment. Storage objects that are backed up in a computing environment are often compound storage objects which include many individual storage objects. The computing device of the computing environment breaks the storage objects into chunks of data by determining a hash value on a range of data. The computing device creates an artificial chunk boundary when the end of data of the storage object is reached. When an artificial chunk boundary is created for the end of data of a storage object, the computing device stores a pseudo fingerprint for the artificial chunk boundary. If a hash value matches a fingerprint or a pseudo fingerprint, then the computing device determines that the range of data corresponds to a chunk and the computing system defines the chunk boundaries.

Claims (53)

1. A computer implemented method for deduplicating a storage object comprising:

determining a chunk identifying hash value for a window of data of said storage object;

determining if said chunk identifying hash value of said window of data matches a fingerprint;

determining if said chunk identifying hash value of said window of data matches a stored pseudo fingerprint created for an artificial chunk boundary for an end of data of a storage object;

determining said window of data is an end of data of said storage object when it is determined that said chunk identifying hash value of said window of data does not match either said fingerprint or said stored pseudo fingerprint;

defining a chunk boundary of a chunk of said storage object corresponding to said window of data and storing said chunk boundary of said chunk when it is determined that said window of data is said end of data of said storage object;

replacing data in said window of data with new data to produce a new window of data having the new data and performing another instance of the operations of determining the chunk, determining if the chunk matches the fingerprint and the pseudo fingerprint, and defining the chunk boundary for said new window of data when it is determined that said window of data is said end of data of said storage object; and

storing said determined chunk identifying hash value as a pseudo fingerprint of said chunk of said storage object corresponding to said window of data when it is determined that said window of data of said storage object is said end of data of said storage object.

2. The computer implemented method of claim 1 , further comprising determining a chunk uniqueness hash on said chunk of said storage object and storing said chunk uniqueness hash information in a deduplication index for said chunk of said storage object.

3. The computer implemented method of claim 1 , wherein said determining if said chunk identifying hash value matches said known fingerprint comprises determining if said chunk identifying hash value meets a predetermined mathematical property.

4. The computer implemented method of claim 1 , wherein storing said pseudo fingerprint of said chunk of said storage object corresponding to said window of data of said storage object comprises storing said pseudo fingerprint in a pseudo fingerprint list.

5. The computer implemented method of claim 4 , wherein said determining if said chunk identifying hash value matches a pseudo fingerprint comprises determining if said chunk identifying hash value is stored on said pseudo fingerprint list.

6. The computer implemented method of claim 1 , wherein determining said chunk identifying hash value of said window of data of said storage object comprises calculating a rolling hash value of said window of data of said storage object.

7. The computer implemented method of claim 6 , wherein calculating said rolling hash value of said window of data of said storage object comprises calculating a Karp-Rabin rolling hash of said window of data of storage object.

8. The computer implemented method of claim 1 , further comprising defining a chunk of said storage object corresponding to said window of data and storing a chunk boundary of said chunk when it is determined that said chunk identifying hash value matches said fingerprint.

9. A computing device of a computing environment for deduplicating a storage object comprising:

a processor and a memory coupled to said processor;

said memory including computer readable storage medium having code executed by the processor to perform operations, wherein the operations comprise:

determining a chunk identifying hash value for a window of data of said storage object;

determining if said chunk identifying hash value of said window of data matches a fingerprint;

determining if said chunk identifying hash value of said window of data matches a stored pseudo fingerprint created for an artificial chunk boundary for an end of data of a storage object;

determining said window of data is an end of data of said storage object when it is determined that said chunk identifying hash value of said window of data does not match either said fingerprint or said stored pseudo fingerprint;

defining a chunk boundary of a chunk of said storage object corresponding to said window of data and storing a chunk boundary of said chunk when it is determined that said window of data is said end of data of said storage object;

replacing data in said window of data with new data to produce a new window of data having the new data and performing another instance of the operations of determining the chunk, determining if the chunk matches the fingerprint and the pseudo fingerprint, and defining the chunk boundary for said new window of data when it is determined that said window of data is said end of data of said storage object; and

storing said determined chunk identifying hash value as a pseudo fingerprint of said chunk of said storage object corresponding to said window of data in said memory when it is determined that said window of data of said storage object is said end of data of said storage object.

10. The computing device of claim 9 , wherein the operations further comprise:

determining a chunk uniqueness hash on said chunk of said storage object and storing said chunk uniqueness hash information in a deduplication index for said chunk of said storage object.

11. The computing device of claim 9 , wherein said determining if said chunk identifying hash value matches said known fingerprint comprises determining if said chunk identifying hash value meets a predetermined mathematical property.

12. The computing device of claim 9 , wherein said storing of said pseudo fingerprint of said chunk of said storage object corresponding to said window of data of said storage object comprises storing said pseudo fingerprint in a pseudo fingerprint list.

13. The computing device of claim 12 , wherein said determining if said chunk identifying hash value matches a pseudo fingerprint comprises determining if said chunk identifying hash value is stored on said pseudo fingerprint list.

14. The computing device of claim 9 , wherein said determining said chunk identifying hash value of said window of data of said storage object comprises calculating a rolling hash value of said window of data of said storage object.

15. The computing device of claim 14 , wherein said calculating said rolling hash value of said window of data of said storage object comprises calculating a Karp-Rabin rolling hash of said window of data of storage object.

16. The computing device of claim 9 , wherein the operations further comprise:

defining a chunk of said storage object corresponding to said window of data and storing a chunk boundary of said chunk when it is determined that said chunk identifying hash value matches said fingerprint.

17. A computer program product for deduplicating a storage, the computer program product comprising a computer readable storage medium having computer readable program code embodied therein that executes to perform operations, the operations comprising:

a processor and a memory coupled to said processor;

said memory including computer readable storage medium having code executed by the processor to perform operations, wherein the operations comprise:

determining a chunk identifying hash value for a window of data of said storage object;

determining if said chunk identifying hash value of said window of data matches a fingerprint;

determining if said chunk identifying hash value of said window of data matches a stored pseudo fingerprint created for an artificial chunk boundary for an end of data of a storage object;

determining if said window of data is an end of data of said storage object when it is determined that said chunk identifying hash value of said window of data does not match either said fingerprint or said stored pseudo fingerprint;

defining a chunk boundary of a chunk of said storage object corresponding to said window of data and storing a chunk boundary of said chunk when it is determined that said window of data is said end of data of said storage object;

replacing data in said window of data with new data to produce a new window of data having the new data and performing another instance of the operations of determining the chunk, determining if the chunk matches the fingerprint and the pseudo fingerprint, and defining the chunk boundary for said new window of data when it is determined that said window of data is said end of data of said storage object; and

storing said determined chunk identifying hash value as a pseudo fingerprint of said chunk of said storage object corresponding to said window of data in said memory when it is determined that said window of data of said storage object is said end of data of said storage object.

18. The computer program product of claim 17 , wherein the operations further comprise:

determining a chunk uniqueness hash on said chunk of said storage object and storing said chunk uniqueness hash information in a deduplication index for said chunk of said storage object.

19. The computer program product of claim 17 , wherein said determining if said chunk identifying hash value matches said known fingerprint comprises determining if said chunk identifying hash value meets a predetermined mathematical property.

20. The computer program product of claim 17 , wherein said storing of said pseudo fingerprint of said chunk of said storage object corresponding to said window of data of said storage object comprises storing said pseudo fingerprint in a pseudo fingerprint list.

21. The computer program product of claim 20 , wherein said determining if said chunk identifying hash value matches a pseudo fingerprint comprises determining if said chunk identifying hash value is stored on said pseudo fingerprint list.

22. The computer program product of claim 17 , wherein said determining said chunk identifying hash value of said window of data of said storage object comprises calculating a rolling hash value of said window of data of said storage object.

23. The computer program product of claim 22 , wherein said calculating said rolling hash value of said window of data of said storage object comprises calculating a Karp-Rabin rolling hash of said window of data of storage object.

24. The computer program product of claim 17 , wherein the operations further comprise:

defining a chunk of said storage object corresponding to said window of data and storing a chunk boundary of said chunk when it is determined that said chunk identifying hash value matches said fingerprint.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Dec 29, 2011
From: YAKUSHEV, MARK L.; SMITH, MARK A.
To: INTERNATIONAL BUSINESS MACHINES CORPORATION
Reel/Frame 027456/0966 →
Continuity (1)
Related Publication 20130138620A1 · May 30, 2013