System and method for retrieving and using block fingerprints for data deduplication

• US 20080005141A1
• Filed: 06/29/2006
• Published: 01/03/2008
• Est. Priority Date: 06/29/2006
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Zheng, Ling, Fong, Yinfung
• Granted Patent: US 8,412,682 B2
• Time in Patent Office: Days
• US Class Current: 707/101
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A system and method for calculating and storing block fingerprints for data deduplication. A fingerprint extraction layer generates a fingerprint of a predefined size, e.g., 64 bits, for each data block stored by a storage system. Each fingerprint is stored in a fingerprint record, and the fingerprint records are, in turn, stored in a fingerprint database for access by the data deduplication module. The data deduplication module may periodically compare the fingerprints to identify duplicate fingerprints, which, in turn, indicate duplicate data blocks.

Claims

1. A method for identifying duplicate data in a storage system, the method comprising:

storing data in a plurality of data blocks;

calculating a plurality of checksum values, each checksum value associated with the data of each data block;

storing each checksum value in a fingerprint of a plurality of fingerprints, each fingerprint associated with a data block of the plurality of data blocks; and

identifying duplicate data blocks of the plurality of data blocks by identifying identical fingerprints of the plurality of fingerprints.

2. The method of claim 1, further comprising:

sampling data from a predefined offset within one of the plurality of data blocks; and

storing the sampled data in one of the plurality of fingerprints associated with the one of the plurality of data blocks.

3. The method of claim 2, further comprising:

modifying data stored in the one of the plurality of data blocks; and

eliminating the one of the plurality of fingerprints in response to the data sampled from the predefined offset differing from the modified data stored in the one of the plurality of data blocks at the predefined offset.

4. The method of claim 1, further comprising:

storing metadata associated with one of the plurality of data blocks;

copying the metadata to a fingerprint record associated with the one of the plurality of data blocks; and

storing the fingerprint associated with the one of the plurality of data blocks in the fingerprint record.

5. The method of claim 4, wherein the metadata comprises a generation number of an index node (inode) copied to the fingerprint record as a generation number copy, the method further comprising:

deleting the inode;

reallocating the inode in response to a write operation;

modifying the generation number; and

eliminating the fingerprint record in response to the generation number copy differing from the modified generation number.

6. The method of claim 4, wherein the metadata comprises a consistency point (CP) count copied to the fingerprint record as a CP count copy, the method further comprising:

modifying the CP count in response to a write operation; and

eliminating the fingerprint record in response to the CP count copy differing from the modified CP count.

7. The method of claim 4, wherein the metadata comprises a size value associated with a number of data blocks within a data container, and further comprises a file block number (fbn) copied to the fingerprint record as a fbn copy, the method further comprising:

modifying the size value in response to a change in the number of data blocks within the data container; and

eliminating the fingerprint record in response to the fbn copy indicating an offset greater than the number of data blocks associated with the modified size value.

8. The method of claim 1, wherein the storage system comprises a fingerprint queue and a fingerprint database, each adapted to store at least one fingerprint of the plurality of fingerprints, and wherein the step of identifying duplicate data blocks further comprises:

storing one of the plurality of fingerprints in the fingerprint queue;

comparing the one of the plurality of fingerprints to at least one fingerprint of the plurality of fingerprints stored in the fingerprint database; and

storing the one of the plurality of fingerprints in the fingerprint database.

9. The method of claim 8, further comprising:

comparing the one of the plurality of fingerprints to at least one fingerprint of the plurality of fingerprints stored in the fingerprint queue.

10. The method of claim 8, further comprising:

sorting the fingerprint queue by the plurality of checksum values stored in the plurality of fingerprints.

11. The method of claim 8, further comprising:

sorting the fingerprint queue by a plurality of index node (inode) numbers, wherein the plurality of inode numbers indicate a plurality of inodes associated with the plurality of data blocks.

12. The method of claim 1, wherein the storage system further comprises a storage module adapted to implement a storage protocol, and wherein the step of calculating a plurality of checksum values further comprises:

calculating the plurality of checksum values according to the storage protocol.

13. The method of claim 12, wherein the storage protocol is a Redundant Array of Inexpensive Disks (RAID) protocol.

14. The method of claim 12, further comprising:

utilizing the plurality of checksum values to verify data integrity of the plurality of data blocks.

15. The method of claim 1, further comprising:

eliminating one of the plurality of fingerprints in response to the one of the plurality of fingerprints being associated with a duplicate data block.

16. The method of claim 1, further comprising:

eliminating one of the plurality of fingerprints in response to the plurality of fingerprints being associated with a predetermined number of data blocks.

17. The method of claim 1, wherein the step of identifying duplicate data blocks further comprises:

identifying a stale fingerprint of the plurality of fingerprints; and

eliminating the stale fingerprint.

18. A storage operating system adapted to identify duplicate data, the storage operating system comprising:

a file system layer;

a storage module layer cooperating with the file system layer to process a write operation, the storage module layer further adapted to store a data block and to calculate a checksum value associated with the data block;

a fingerprint extraction layer adapted to store the checksum value to a fingerprint database, wherein the fingerprint database comprises a plurality of checksum values; and

a deduplication module adapted to identify duplicate data blocks by identifying identical checksum values in the fingerprint database.

19. The storage operating system of claim 18, wherein the fingerprint extraction layer is further adapted to store, in the fingerprint database, sampling data from a predetermined offset within the data block and to associate the sampling data with the checksum value from the storage module layer.

20. The storage operating system of claim 18, wherein the file system layer is adapted to associate metadata with the data block, and wherein the fingerprint extraction layer is further adapted to associate the checksum value and a copy of the metadata as a fingerprint record.

21. The storage operating system of claim 20, wherein the fingerprint extraction layer is further adapted to store an index node (inode) number and a file block number (FBN) in the fingerprint record, wherein the inode number identifies an inode associated with the data block and the FBN indicates an offset within a data container, and wherein the metadata comprises:

a generation number indicating reallocation of the data block; and

a consistency point (CP) count indicating modification of the data block.

22. The storage operating system of claim 18, wherein the fingerprint extraction layer is further adapted to store the checksum value in response to the data block being associated with a subset of a plurality of data blocks.

23. The storage operating system of claim 22, wherein the subset excludes an indirect data block of the plurality of data blocks.

24. The storage operating system of claim 22, wherein the subset comprises data blocks associated with a data container of a predetermined type.

25. The storage operating system of claim 18, further comprising a fingerprint queue adapted to store at least one checksum value of the plurality of checksum values in response to the write operation, and wherein the deduplication module is further adapted to identify duplicate data blocks by identifying identical checksum values among the fingerprint queue and the fingerprint database.

26. The storage operating system of claim 18, wherein the storage module layer is adapted to implement a Redundant Array of Inexpensive Disks (RAID) protocol, and wherein the checksum value is calculated according to the RAID protocol.

27. A computer readable medium for identifying duplicate data in a storage system, the computer readable medium including program instructions for performing the steps of:

storing data in a plurality of data blocks;

calculating a plurality of checksum values, each checksum value associated with the data of each data block;

storing each checksum value in a fingerprint of a plurality of fingerprints, each fingerprint associated with a data block of the plurality of data blocks; and

identifying duplicate data blocks of the plurality of data blocks by identifying identical fingerprints of the plurality of fingerprints.