Removing overlapping ranges from a flat sorted data structure

• US 9,720,928 B2
• Filed: 10/20/2014
• Issued: 08/01/2017
• Est. Priority Date: 03/01/2012
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Shukla, Ashish, Killamsetti, Praveen, Raghuwanshi, Rohini
• Primary Examiner(s): Liao, Jason
• Assistant Examiner(s): Frumkin, Jesse P
• Application Number:
  US14/518,403
• Publication Number:
  US 20150039572A1
• Time in Patent Office: 1,016 Days
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/128 Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion use of snapshots for error detection or correction G06F11/14, G06F11/16
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• 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/1752 based on file chunks

Abstract

A system can efficiently removes ranges of entries from a flat sorted data structure that represent stale fingerprints As part of fingerprint verification during deduplication, the system performs an attributes intersect range calculation (AIRC) procedure on the stale fingerprint data structure to compute a set of non-overlapping and latest consistency point (CP) ranges. During the AIRC procedure, an inode associated with a data container is selected and the FBN tuple of each deleted data block in the file is sorted in a predefined FBN order. The AIRC procedure then identifies the most recent fingerprint associated with a deleted data block. The set of non-overlapping and latest CP ranges is then used to remove stale fingerprints associated with that deleted block from the fingerprint database. A single pass through the fingerprint database identifies the set of non-overlapping and latest CP ranges, thereby improving efficiency of the storage system.

Claims

1. A computer implemented method for removing one or more stale fingerprints from a fingerprint database the method comprising:

sorting a list of stale fingerprints stored in a stale fingerprint data structure into an inode number order;

performing an attributes intersect range calculation on the sorted list that computes a non-overlapping and latest consistency point (CP) range, wherein the attributes intersect range calculation comprises determining a tuple that defines the non-overlapping and latest CP range, wherein the tuple includes a starting value, an ending value, and a CP count associated with a given inode; and

comparing the non-overlapping and latest CP range with the fingerprint database wherein the comparing includes;

determining whether an identifier, associated with a block of data, is located between the starting value and the ending value,

in response to determining that the identifier is located between the starting value and the ending value, determining whether one or more selected fingerprints associated with the block of data and in the fingerprint database have a specific CP count that is less than or equal to the CP count contained in the non-overlapping and latest CP range, and

removing from the fingerprint database the one or more selected fingerprints associated with the block of data and in the fingerprint database that have the specific CP count that is less than or equal to the CP count contained in the non-overlapping and latest CP range, wherein the one or more selected fingerprints that have the specific CP count that is less than or equal to the CP count are stale fingerprints.

2. The computer implemented method of claim 1 wherein the comparing further includes maintaining one or more other fingerprints associated with the block of data in the fingerprint database that have one or more other CP counts that are greater than the CP count contained in the non-overlapping and latest CP range.

3. The computer implemented method of claim 1 wherein a stale fingerprint includes a checksum value.

4. The computer implemented method of claim 3 further comprising computing the checksum value during execution of a storage system operation.

5. The computer implemented method of claim 1 further comprising logging fingerprints associated with file block numbers to which a specified operation has been performed to generate the list of stale fingerprints in the stale fingerprint data structure.

6. The computer implemented method of claim 5 wherein the specified operation is selected from a group consisting of file deletion, file truncation and hole punching.

7. The computer implemented method of claim 1 wherein comparing the non-overlapping and latest CP range with the fingerprint database to remove the one or more stale fingerprints from the fingerprint database is performed in a single pass through the fingerprint database.

8. The computer implemented method of claim 1 wherein performing the attributes intersect range calculation on the sorted list further comprises:

selecting a first inode;

sorting each file block number associated with the selected first inode in a predefined file block number order; and

traversing a set of file block number tuples to identify the non-overlapping and latest CP range.

9. The computer implemented method of claim 8 wherein the predefined file block number order comprises an increasing file number block order.

10. The computer implemented method of claim 1 wherein the starting value is a starting file block number, the ending value is an ending file block number, and the identifier is a file block number associated with the data block.

11. A system comprising:

a processor; and

a computer-readable medium comprising program instructions executable by the processor to cause the system to,

perform an attributes intersection range calculation on a stale fingerprint data structure, wherein the program instructions to perform the attributes intersection range calculation comprise instructions executable to cause the system to determine a tuple that defines a non-overlapping and latest consistency point (CP) range including a starting value, an ending value, and a CP count associated with a given inode,

compare a fingerprint database with the non-overlapping and latest CP range, wherein the program instructions to compare comprise program instructions executable by the processor to cause the system to;

determine whether an identifier, associated with a block of data, is located between the starting value and the ending value,

in response to determining that the identifier is located between the starting value and the ending value, determine whether one or more selected fingerprints associated with the block of data and in the fingerprint database have a specific CP count that is less than or equal to the CP count of the non-overlapping and latest CP range, and

remove from the fingerprint database the one or more selected fingerprints associated with the block of data and in the fingerprint database that have the specific CP count that is less than or equal to the CP count of the non-overlapping and latest CP range, wherein the one or more selected fingerprints that have the specific CP count that is less than or equal to the CP count are stale fingerprints.

12. The system of claim 11 wherein the computer-readable medium further comprises program instructions executable by the processor to cause the system to maintain one or more other fingerprints associated with the block of data in the fingerprint database that have one or more other CP counts that are greater than the CP count contained in the non-overlapping and latest CP range.

13. The system of claim 11 wherein the stale fingerprints are generated from a specified file system operation.

14. The system of claim 13 wherein the specified file system operation is selected from a group consisting of file deletion, file truncation and hole punching.

15. The system of claim 13 wherein the computer-readable medium further comprises program instructions executable by the processor to cause the system to perform the attributes intersection range calculation on a periodic basis.

16. The system of claim 11 wherein the non-overlapping and latest CP range is deleted after removal of the one or more selected fingerprints from the fingerprint database.

17. The system of claim 11 wherein each stale fingerprint includes a checksum value.

18. The system of claim 17 wherein the checksum value comprises a RAID checksum value.

19. The system of claim 17 wherein the computer-readable medium comprises program instructions executable by the processor to cause the system to generate the checksum during execution of a storage operation.

20. A non-transitory computer readable storage medium containing executable program instructions for execution by a processor, the program instructions executable to:

sort a list of stale fingerprints into a predefined order, wherein the stale fingerprints are associated with file block numbers to which a specified operation has been performed;

perform an attributes intersect range calculation on the sorted list, wherein the program instructions to perform the attributes intersect range calculation comprises program instructions executable to determine a tuple that defines a non-overlapping and latest consistency point (CP) range, wherein the tuple includes a starting value, an ending value, and a CP count associated with a given inode; and

compare the non-overlapping and latest CP range with a fingerprint database, wherein the program instructions that compare comprise program instructions executable to;

determine whether an identifier, associated with a block of data, is located between the starting value and the ending value,

in response to determining that the identifier is located between the starting value and the ending value, determine whether one or more selected fingerprints associated with the block of data and in the fingerprint database have a specific CP count that is less than or equal to the CP count contained in the non-overlapping and latest CP range,

remove from the fingerprint database the one or more selected fingerprints associated with the block of data and in the fingerprint database that have the specific CP count that is less than or equal to the CP count contained in the non-overlapping and latest CP range, wherein the one or more selected fingerprints that have the specific CP count that is less than or equal to the CP count are stale fingerprints.