Large block misaligned deduplication
AssigneeEMC IP Holding Company LLC
InventorsJeremy J. O'Hare, Kuolin Hua, Michael J. Scharland, Stephen M. Lathrop, Anoop Raghunathan
Life of this patent
Estimating the term…
Abstract
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.
Claims12
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.
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.
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.
Dependencies are inferred from the claim text.