Utilizing multiple fingerprint tables in a deduplicating storage system

• US 9,811,551 B1
• Filed: 06/25/2015
• Issued: 11/07/2017
• Est. Priority Date: 10/14/2011
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Colgrove, John, Hayes, John, Miller, Ethan, Hasbani, Joseph S., Sandvig, Cary
• Primary Examiner(s): Bragdon, Reginald
• Assistant Examiner(s): Namazi, Mehdi
• Application Number:
  US14/751,099
• Time in Patent Office: 866 Days
• 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
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0637 Permissions
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A system and method for managing fingerprint tables in deduplicating storage systems. A computer system includes a storage device and a data storage controller coupled to the storage device. The controller is configured to for each of a plurality of data objects stored in a storage device, determine, based on one or more attributes corresponding to usage of the data object, a probability of the data object being deduplicated; store within a first fingerprint table, fingerprints of data objects with the highest probability of being deduplicated; store within a second fingerprint table, fingerprints of data objects with a lower probability of being deduplicated than the data objects having fingerprints stored in the first fingerprint table; and search fingerprints of the first fingerprint table to determine whether a fingerprint for a data object associated with a write request matches a fingerprint for any of the data objects in the first fingerprint table.

Claims

1. A computer system comprising:

a storage device;

a data storage controller coupled to the storage device, the controller configured to;

for each of a plurality of data objects stored in the storage device, determine, based on one or more attributes corresponding to usage of the data object, a probability of the data object being deduplicated;

store within a first fingerprint table, fingerprints of data objects with the highest probability of being deduplicated;

store within a second fingerprint table, fingerprints of data objects with a lower probability of being deduplicated than the data objects having fingerprints stored in the first fingerprint table; and

search fingerprints of the first fingerprint table to determine whether a fingerprint for a data object associated with a write request matches a fingerprint for any of the data objects in the first fingerprint table.

2. The system as recited in claim 1, wherein searching the fingerprints is performed in response to detecting a write operation.

3. The system as recited in claim 1, where the data storage controller is configured to cache a copy of the fingerprints stored in the first fingerprint table in memory.

4. The system as recited in claim 1, wherein the fingerprints of the first fingerprint table are stored across a hierarchy of different storage media.

5. The system as recited in claim 1, wherein in response to detecting a deduplication operation corresponding to a first data component stored in the data storage medium, the data storage controller is configured to perform a number of accesses to the fingerprints of the first fingerprint table as part of the deduplication operation, wherein the number of said accesses performed is based at least in part on an age of the first data component.

6. The system as recited in claim 5, wherein as the first data component grows older said number of accesses performed during a deduplication operation increases.

7. The system as recited in claim 1, wherein the attributes includes at least one of a number of access to the data object.

8. The system of claim 1, wherein a data storage controller coupled to the storage device, the controller configured to:

update one or more attributes of a particular data object having a fingerprint stored in a particular fingerprint table selected from one of the first fingerprint table and the second fingerprint table; and

in response to updating one or more attributes of the particular data object, moving the fingerprint from the particular fingerprint table to another fingerprint table selected from one of the first fingerprint table and the second fingerprint table.

9. A method comprising:

for each of a plurality of data objects stored in a storage device, determining, based on one or more attributes corresponding to usage of the data object, a probability of the data object being deduplicated;

storing within a first fingerprint table, fingerprints of data objects with the highest probability of being deduplicated;

storing within a second fingerprint table, fingerprints of data objects with a lower probability of being deduplicated than the data objects having fingerprints stored in the first fingerprint table; and

searching fingerprints of the first fingerprint table to determine whether a fingerprint for a data object associated with a write request matches a fingerprint for any of the data objects in the subset.

10. The method as recited in claim 9, wherein determining the probability of being deduplicated includes determining the probability of being duplicated based at least in part on one or more of the following:

a number of times the data had been deduplicated, and a determination that the data corresponded to a particular volume.

11. The method as recited in claim 9, further comprising:

detecting a write operation;

detecting a miss in the first fingerprint table; and

in response to detecting the write operation and detecting the miss in the first fingerprint table, storing data corresponding to the write operation on the storage device.

12. The method as recited in claim 9, further comprising caching a copy of the fingerprints stored in the first fingerprint table.

13. The method as recited in claim 9, further comprising storing the fingerprints of the first fingerprint table across a hierarchy of different storage media.

14. The method as recited in claim 9, wherein in response to detecting a deduplication operation corresponding to a first data component stored in the storage device, the method comprises performing one or more accesses to fingerprints of the first fingerprint table as part of the deduplication operation, wherein the number of said accesses performed is based at least in part on an age of the first data component.

15. The method as recited in claim 14, wherein the deduplication operation is initiated responsive to detecting a flush operation or a garbage collection operation.

16. A non-transitory computer readable storage medium comprising program instructions, wherein said program instructions are executable to:

for each of a plurality of data objects stored in a storage device, determine, based on one or more attributes corresponding to usage of the data object, a probability of the data object being deduplicated;

store within a first fingerprint table, fingerprints of data objects with the highest probability of being deduplicated;

store within a second fingerprint table, fingerprints of data objects with a lower probability of being deduplicated than the data objects having fingerprints stored in the first fingerprint table; and

search fingerprints of the first fingerprint table to determine whether a fingerprint for a data object associated with a write request matches a fingerprint for any of the data objects in the first fingerprint table.

17. The storage medium as recited in claim 16, wherein determining a probability of being deduplicated includes determining the probability of being duplicated is based at least in part on one or more of the following:

a number of times the data had been deduplicated, and a determination that the data corresponded to a particular volume.

18. The storage medium as recited in claim 17, wherein the program instructions are further executable to cache a copy of the fingerprints of the first fingerprint table.

19. The storage medium as recited in claim 16, further comprising program instructions executable to:

detect a write operation;

detect a miss in the first fingerprint table; and

in response to detecting the write operation and detecting the miss in the first fingerprint table, store data corresponding to the write operation on the storage device.

20. The storage medium as recited in claim 16, wherein the program instructions are further executable to store the fingerprints of the first fingerprint table across a hierarchy of different storage media.