Combining hash-based duplication with sub-block differencing to deduplicate data
View Patent ↗In one embodiment, a method includes accessing data; partitioning the data into sub-blocks; determining whether a first one of the sub-blocks is identical to another one of the sub-blocks or similar to another one of the sub-blocks; if the first one of the sub-blocks is identical to another one of the sub-blocks, applying by the one or more computer systems hash-based deduplication to storage of the first one of the sub-blocks with respect to the other one of the sub-blocks; and, if the first one of the sub-blocks is similar to another one of the sub-blocks, applying by the one or more computer systems sub-block differencing to storage of the first one of the sub-blocks with respect to the other one of the sub-blocks.
1. A method comprising, by one or more computer systems:
partitioning data into a plurality of variable-sized sub-blocks;
computing a cryptographic hash for a member of the plurality of sub-blocks, where the cryptographic hash is computed from all the data in the member; and
upon determining that the member is not identical to a sub-block stored in a data de-duplication system based, at least in part, on the cryptographic hash;
computing an additional hash for the member, where the additional hash is computed from less than all the data in the member; and
determining whether the sub-block is similar to another sub-block stored in the data de-duplication system based, at least in part, on the additional hash.
2. The method of claim 1 , comprising computing a plurality of additional hashes for the member, where the additional hashes are computed from less than all the data in the member, and where the additional hashes are computed from different subsets of data in the member.
3. The method of claim 2 , comprising determining whether the sub-block is similar to another sub-block stored in the data de-duplication system based, at least in part, on the plurality of additional hashes.
4. The method of claim 3 , where determining whether the sub-block is similar to another sub-block comprises comparing the plurality of additional hashes computed for the member to a plurality of additional hashes available for the other sub-block.
5. The method of claim 4 , where the sub-block is determined to be similar to the other sub-block when more than a threshold number of the plurality of additional hashes computed for the member match members of the plurality of additional hashes available for the other member.
6. The method of claim 5 , comprising storing the member in the data de-duplication system using sub-block differencing.