Data deduplication using truncated fingerprints
The system, devices, and methods disclosed herein relate to data ratio reduction technology adapted to reduce storage costs by weeding out duplicative data write operations. The techniques and systems disclosed achieve deduplication benefits by reducing the size of hash values stored hash tables used to compare unwritten data blocks to data that has already been written and stored somewhere in physical storage. The data deduplication systems, methods, and products facilitate deduplication at the block level as well as for misaligned data chunks within data blocks, that is an unwritten data block that has been stored sequentially in two different physical locations. The deduplication teachings herein are amenable to varying data block sizes as well as data chunk sizes within blocks. Our embodiments enhance computer performance by substantially reducing computational speeds and storage requirements attendant to deduplication systems using larger hash table data sizes.
1. A computer executable method for deduplicating data within a data storage system during a write operation comprising the steps of:
prior to writing a data block to memory, creating two or more hash strings corresponding to an unwritten data block, wherein the creating further comprises iteratively truncating two or more hash strings corresponding to the plurality of unwritten data chunks using a first truncating function and a second truncation function, the first truncating function being different than the second truncating function;
comparing a plurality of values within the iteratively truncated two or more hash strings to a hash table, wherein the hash table contains hash values corresponding to stored data blocks, the stored hash values having been created using the first truncating function and the second truncating function;
determining if a sequential match between the iteratively truncated two or more hash strings and a first stored hash table value and a last stored hash table value can be found; and
avoiding writing the unwritten data block if two sequential matches are found.
2. The computer executable method of claim 1 , wherein the first truncating function reduces the size of each of the unwritten hash values and the stored hash values to less than 20 bytes.
3. The computer executable method of claim 1 , wherein the first truncating function reduces a size of each of the unwritten hash values and the stored hash values to 10 bytes.
4. The computer executable method of claim 1 , wherein the second truncating function reduces the size of each of the unwritten hash values and the stored hash values to less than 5 bytes.
5. The computer executable method of claim 1 , wherein the second truncating function reduces a size of each of the unwritten hash values and the stored hash values to 1 byte.
6. The computer executable method of claim 1 further comprising writing the unwritten data block if no sequential match is found.
7. The computer executable method of claim 1 further comprising recording at least one pointer in a memory, wherein the at least one pointer is an indication of a location of a duplicate version of the unwritten data block with the data storage system.
8. A system for deduplicating data within a data storage system during a write operation comprising a memory and a processor, the processor configured to perform the steps of:
prior to writing a data block to memory, creating two or more hash strings corresponding to an unwritten data block, wherein the creating further comprises iteratively truncating two or more hash strings corresponding to the plurality of unwritten data chunks using a first truncating function and a second truncation function, the first truncating function being different than the second truncating function;
comparing a plurality of values within the iteratively truncated two or more hash strings to a hash table, wherein the hash table contains hash values corresponding to stored data blocks, the stored hash values having been created using the first truncating function and the second truncating function;
determining if a sequential match between the iteratively truncated two or more hash strings and a first stored hash table value and a last stored hash table value can be found; and
avoiding writing the unwritten data block if two sequential matches are found.
9. The system of claim 8 , wherein the first truncating function reduces the size of each of the unwritten hash values and the stored hash values to less than 20 bytes.
10. The system claim 8 , wherein the first truncating function reduces a size of each of the unwritten hash values and the stored hash values to 10 bytes.
11. The system of claim 8 , wherein the second truncating function reduces the size of each of the unwritten hash values and the stored hash values to less than 5 bytes.
12. The system of claim 8 , wherein the second truncating function reduces a size of each of the unwritten hash values and the stored hash values to 1 byte.
13. The system of claim 8 further comprising writing the unwritten data block if no sequential match is found.
14. The system of claim 8 further comprising recording at least one pointer in a memory, wherein the at least one pointer is an indication of a location of a duplicate version of the unwritten data block with the data storage system.
15. A compute product for deduplicating data within a data storage system during a write operation, the computer program product being embodied in a tangible, non-transitory computer readable storage medium and comprising computer instructions for
prior to writing a data block to memory, creating two or more hash strings corresponding to an unwritten data block, wherein the creating further comprises iteratively truncating two or more hash strings corresponding to the plurality of unwritten data chunks using a first truncating function and a second truncation function, the first truncating function being different than the second truncating function;
comparing a plurality of values within the iteratively truncated two or more hash strings to a hash table, wherein the hash table contains hash values corresponding to stored data blocks, the stored hash values having been created using the first truncating function and the second truncating function;
determining if a sequential match between the iteratively truncated two or more hash strings and a first stored hash table value and a last stored hash table value can be found; and
avoiding writing the unwritten data block if two sequential matches are found.
16. The computer program product of claim 15 , wherein the first truncating function reduces the size of each of the unwritten hash values and the stored hash values to less than 20 bytes.
17. The computer program product of claim 15 , wherein the first truncating function reduces a size of each of the unwritten hash values and the stored hash values to 10 bytes.
18. The computer program product of claim 15 , wherein the second truncating function reduces the size of each of the unwritten hash values and the stored hash values to less than 5 bytes.
19. The computer program product of claim 15 further comprising writing the unwritten data block if no sequential match is found.
20. The computer program product of claim 15 further comprising recording at least one pointer in a memory, wherein the at least one pointer is an indication of a location of a duplicate version of the unwritten data block with the data storage system.