Large block misaligned deduplication
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 of smaller block, finer granularity, deduplication systems while simultaneously reducing the enormous metadata costs traditionally associated with small block deduplication. According to an exemplary 128 K block deduplication system and method, we disclose deduplication rates nearly equivalent to 4 K deduplication systems.
1. A computer executable method for deduplicating data within a data storage system during a write operation comprising the steps of:
a. calculating a plurality of hash values for a plurality of data chunks within an unwritten data block, each hash value having a one-to-one correspondence with an individual data chunk within the plurality of data chunks;
b. querying a hash table to determine if a match can be found for each of the of the plurality of hash values in at most two sequential patterns, the sequential patterns corresponding to physical data block locations for the plurality of data chunks;
c. if the query results in a single physical data block location match, recording a pointer within a virtual table of pointers corresponding to a physical location of the single physical data block location; and
d. if the query results in a double physical data block location match:
i. recording a first pointer within the virtual table of pointers corresponding to a first physical data block location;
ii. recording a hash value offset; and
iii. recording a second pointer within the virtual table of pointers corresponding to a second physical data block location.
2. The computer executable method of claim 1 further comprising, if no sequential match of the plurality of hash values can be found, writing the data block to the data storage device.
3. The computer executable method of claim 1 wherein a size for each of the plurality of data chunks is 32 KB.
4. The computer executable method of claim 1 wherein a size for the unwritten data block is 128K.
5. A system for deduplicating data blocks on a set of storage devices, the system comprising a memory, a processor, and a deduplication engine configured for deduplicating data within a data storage system during a write operation comprising the deduplication engine performing the steps of:
a. calculating a plurality of hash values for a plurality of data chunks within an unwritten data block, each hash value having a one-to-one correspondence with an individual data chunk within the plurality of data chunks;
b. querying a hash table to determine if a match can be found for each of the of the plurality of hash values in at most two sequential patterns, the sequential patterns corresponding to physical data block locations for the plurality of data chunks;
c. if the query results in a single physical data block location match, recording a pointer within a virtual table of pointers corresponding to a physical location of the single physical data block location; and
d. if the query results in a double physical data block location match:
i. recording a first pointer within the virtual table of pointers corresponding to a first physical data block location;
ii. recording a hash value offset; and
iii. recording a second pointer within the virtual table of pointers corresponding to a second physical data block location.
6. The system of claim 5 wherein the deduplication engine is further configured to perform the steps of writing the data block to the data storage device if no sequential match of the plurality of hash values can be found.
7. The system of claim 5 wherein a size for each of the plurality of data chunks is 32 KB.
8. The system of claim 5 wherein a size for the unwritten data block is 128K.
9. A non-transitory computer readable storage medium having instructions stored thereon when executed by a processor during a write operation, the non-transitory computer readable storage medium comprising instructions for:
a. calculating a plurality of hash values for a plurality of data chunks within an unwritten data block, each hash value having a one-to-one correspondence with an individual data chunk within the plurality of data chunks;
b. querying a hash table to determine if a match can be found for each of the of the plurality of hash values in at most two sequential patterns, the sequential patterns corresponding to physical data block locations for the plurality of data chunks;
c. if the query results in a single physical data block location match, recording a pointer within a virtual table of pointers corresponding to a physical location of the single physical data block location; and
d. if the query results in a double physical data block location match:
i. recording a first pointer within the virtual table of pointers corresponding to a first physical data block location;
ii. recording a hash value offset; and
iii. recording a second pointer within the virtual table of pointers corresponding to a second physical data block location.
10. The non-transitory computer readable storage medium of claim 9 wherein the non-transitory computer readable storage medium further comprises instructions for writing the data block to the data storage device if no sequential match of the plurality of hash values can be found.
11. The non-transitory computer readable storage medium of claim 9 wherein a size for each of the plurality of data chunks is 32 KB.
12. The non-transitory computer readable storage medium of claim 9 wherein a size for the unwritten data block is 128 K wherein the two or more operational parameters are accorded differing priorities.