Method for maintaining multiple fingerprint tables in a deduplicating storage system
A system and method for managing multiple fingerprint tables in a deduplicating storage system. A computer system includes a data storage medium, a first fingerprint table comprising a first plurality of entries, and a second fingerprint table comprising a second plurality of entries. Each of the first plurality of entries and each of the second plurality of entries are configured to store fingerprint related data corresponding to data stored in the data storage medium. A data storage controller is configured to select the first fingerprint table for storage of entries corresponding to data stored in the data storage medium that has been deemed more likely to be successfully deduplicated than other data stored in the data storage medium; and select the second fingerprint table for storage of entries corresponding to data stored in the data storage medium that has been deemed less likely to be successfully deduplicated than other data stored in the data storage medium.
1. A computer system comprising:
a data storage medium;
a first fingerprint table comprising a first plurality of entries; and
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 is configured to store a fingerprint corresponding to data stored in the data storage medium; and
a data storage controller configured to:
generate a first fingerprint corresponding to a data component of a received write operation;
access the first fingerprint table; and
write the data component to the data storage medium without accessing the second fingerprint table, in response to determining the first fingerprint table does not include an entry that corresponds to the first fingerprint.
2. The system as recited in claim 1 , wherein the second fingerprint table comprises a fingerprint for at least one deduplicated data component not included in the first fingerprint table.
3. The system as recited in claim 1 , wherein a search of the second fingerprint table for the first fingerprint is deferred to a later time subsequent to the write data being stored in the data storage medium.
4. The system as recited in claim 1 , where the data storage controller is configured to:
store write data corresponding to the write operation in the data storage medium; and
search the second fingerprint table for the first fingerprint corresponding to the write data during a garbage collection operation.
5. The system as recited in claim 1 , wherein the first fingerprint table and the second fingerprint table are stored across a hierarchy of different storage media.
6. 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 first fingerprint table and the second 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.
7. The system as recited in claim 6 , wherein as the first data component grows older said number of accesses performed during a deduplication operation increases.
8. A method comprising:
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 is configured to store a fingerprint corresponding to data stored in a data storage medium;
generating a first fingerprint corresponding to a data component of a received write operation;
accessing the first fingerprint table; and
writing the data component to a data storage medium without accessing the second fingerprint table; and
in response to determining the first fingerprint table does not include an entry that corresponds to the first fingerprint first fingerprint table.
9. The method as recited in claim 8 , wherein the second fingerprint table comprises a fingerprint for at least one deduplicated data component not included in the first fingerprint table.
10. The method as recited in claim 8 , further comprising deferring a search of the second fingerprint table for the first fingerprint subsequent to the write data being stored in the data storage medium.
11. The method as recited in claim 8 , further comprising caching a copy of the first fingerprint table in memory.
12. The method as recited in claim 8 , further comprising storing the first fingerprint table and the second fingerprint table across a hierarchy of different storage media.
13. The method as recited in claim 8 , wherein in response to detecting a deduplication operation corresponding to a first data component stored in the data storage medium, the method comprises performing one or more accesses to the first fingerprint table and the second 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.
14. The method as recited in claim 10 , further comprising searching the second fingerprint table for a fingerprint corresponding to the write data during a garbage collection operation.
15. A non-transitory computer readable storage medium comprising program instructions, wherein said program instructions are executable to:
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 is configured to store a fingerprint corresponding to data stored in a data storage medium;
generating a fingerprint corresponding to a data component of a received write operation;
access the first fingerprint table; and
write the data component to a data storage medium without accessing the second fingerprint table, in response to determining the first fingerprint table does not include an entry that corresponds to the first fingerprint.
16. The non-transitory computer readable storage medium as recited in claim 15 , wherein the second fingerprint table comprises a fingerprint for at least one deduplicated data component not included in the first fingerprint table.
17. The non-transitory computer readable storage medium as recited in claim 15 , wherein the program instructions are further executable to defer a search of the second fingerprint table for the first fingerprint subsequent to the write data being stored in the data storage medium.
18. The non-transitory computer readable storage medium as recited in claim 15 , wherein the program instructions are further executable to cache a copy of the first fingerprint table in memory.
19. The non-transitory computer readable storage medium as recited in claim 17 , wherein the program instructions are further executable to search the second fingerprint table for a fingerprint corresponding to the write data during a garbage collection operation.
20. The non-transitory computer readable storage medium as recited in claim 15 , wherein in response to detecting a deduplication operation corresponding to a first data component stored in the data storage medium, the program instructions are executable to perform a number of accesses to the first fingerprint table and the second 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.