Method for maintaining multiple fingerprint tables in a deduplicating storage system

• US 10,061,798 B2
• Filed: 11/03/2017
• Issued: 08/28/2018
• Est. Priority Date: 10/14/2011
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Colgrove, John, Hasbani, Joseph S., Hayes, John, Miller, Ethan, Sandvig, Cary
• Primary Examiner(s): Bragdon, Reginald
• Assistant Examiner(s): Namazi, Mehdi
• Application Number:
  US15/803,510
• Publication Number:
  US 20180060383A1
• Time in Patent Office: 298 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 tables in a storage system is described.

Claims

1. A system comprising:

a data storage medium;

a first fingerprint table comprising a first plurality of entries;

a second fingerprint table comprising a second plurality of entries;

wherein each of the first plurality of entries and each of the second plurality of entries are configured to store fingerprint data corresponding to data stored in the data storage medium;

wherein the first fingerprint table is configured to store entries corresponding to data stored in the data storage medium which has been deemed more likely to be commonly deduplicated than other data stored in the data storage medium; and

wherein the second fingerprint table is configured to store entries corresponding to data stored in the data storage medium which has been deemed less likely to be commonly deduplicated than other data stored in the data storage medium; and

a data storage controller configured to perform a data access to the fingerprint data of the first fingerprint table as part of a deduplication operation.

2. The system as recited in claim 1, wherein the data includes patterns as well as duplicates.

3. The system as recited in claim 1, wherein the system is a flash system.

4. The system as recited in claim 1, wherein the first plurality of entries comprises hashes.

5. A method comprising:

receiving data;

maintaining a first fingerprint table comprising a first plurality of entries; and

maintaining a second fingerprint table comprising a second plurality of entries;

wherein each of the first plurality of entries and each of the second plurality of entries are configured to store fingerprint data corresponding to a portion of the data stored in a data storage medium;

selecting the first fingerprint table for storage of an entry corresponding to given data stored in the data storage medium, responsive to the given data having been deemed more likely to be commonly deduplicated than other data stored in the data storage medium; and

selecting the second fingerprint table for storage of the entry, responsive to the given data having been deemed less likely to be commonly deduplicated than other data stored in the data storage medium; and

performing, by a data storage controller, a data access to the fingerprint data of the first fingerprint table as part of a deduplication operation.

6. The method of claim 5, wherein the data includes patterns as well as duplicates.

7. The method of claim 5, wherein the first plurality of entries comprises hashes.

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

receive data;

maintain a first fingerprint table comprising a first plurality of entries; and

maintain a second fingerprint table comprising a second plurality of entries;

wherein each of the first plurality of entries and each of the second plurality of entries are configured to store fingerprint data corresponding to a portion of the data that is stored in a data storage medium;

select the first fingerprint table for storage of an entry corresponding to given data stored in the data storage medium, responsive to the given data having been deemed more likely to be commonly deduplicated than other data stored in the data storage medium; and

select the second fingerprint table for storage of the entry, responsive to the given data having been deemed less likely to be commonly deduplicated than other data stored in the data storage medium; and

perform, by a data storage controller, a data access to the fingerprint data of the first fingerprint table as part of a deduplication operation.

9. The non-transitory computer readable storage medium of claim 8, wherein the data includes patterns as well as duplicates.

10. The non-transitory computer readable storage medium of claim 8, wherein the first plurality of entries comprises hashes.