Delta chunks and delta hashes
View Patent ↗Example apparatus, methods, and computers control processing delta chunks with delta hashes. One example method includes computing a first hash for a chunk for which a duplicate determination is to be made. The first hash is suitable for making the duplicate chunk determination. The method also includes computing a delta hash for the chunk. The delta hash is suitable for making a delta chunk determination. The method controls a de-duplication logic to process the chunk as a duplicate upon determining that the first hash matches a stored first hash. The method controls the de-duplication logic to process the chunk as a delta chunk upon determining that the first hash does not match a stored first hash and that the delta hash matches a stored delta hash. Processing a chunk as a delta chunk may include storing a reference to a stored chunk and storing delta hash information.
1. A computer readable medium storing computer executable instructions that when executed by a computer control the computer to perform a method, the method comprising:
computing a first hash for a chunk for which a duplicate determination is to be made, where the duplicate chunk determination is a function of the first hash being compared to a stored first hash, the stored first hash being stored in a first index;
selectively determining a type of delta hash to compute based on one or more of, chunk entropy, chunk size, chunk type, and a recently determinative delta hash;
selectively determining how many delta hashes to compute based on one or more of, chunk entropy, chunk size, and chunk type;
computing a delta hash for the chunk, where a delta chunk determination is to be made for the chunk, where the delta chunk determination is a function of the delta hash being compared to a stored delta hash, the stored delta hash being stored in a second, different index;
upon determining that the first hash matches a stored first hash, controlling a deduplication logic to process the chunk as a duplicate; and
upon determining that the first hash does not match a stored first hash and that the delta hash matches a stored delta hash, controlling the de-duplication logic to process the chunk as a delta chunk,
where the first hash and the delta hash are computed in parallel,
where determining that the first hash matches a stored first hash and determining that the delta hash matches a stored delta hash proceeds in parallel,
where a definitive answer concerning the first hash causes termination of the determination proceeding in parallel concerning the delta hash, and
where a definitive answer concerning the delta hash causes termination of the determination proceeding in parallel concerning the first hash.
2. The computer readable medium of claim 1 , where the first hash is a cryptographic hash having a first strength and a first width, and where the delta hash has a second strength and a second width, the first strength being greater than the second strength, the first width being wider than the second width.
3. The computer readable medium of claim 1 , the method comprising computing two or more different delta hashes for the chunk, and upon determining that a threshold number of the two or more delta hashes match stored delta hashes, controlling the de-duplication logic to process the chunk as a delta chunk.
4. The computer readable medium of claim 1 , where controlling the de-duplication logic to process the chunk as a delta chunk comprises:
controlling the de-duplication logic to not store the chunk; and
controlling the de-duplication logic to store a delta chunk,
where a delta chunk comprises a reference to a stored chunk and difference data.
5. The computer readable medium of claim 4 , where the difference data describes how to create the chunk from the stored chunk.
6. The computer readable medium of claim 4 , where the difference data describes one or more of, an addition to a stored chunk, a deletion from a stored chunk, and an edit to a stored chunk.
7. The computer readable medium of claim 1 , the method comprising:
upon determining that the delta hash matches a stored delta hash,
controlling the de-duplication logic to treat the chunk as a delta chunk upon determining that a byte-wise comparison of the chunk and a stored chunk associated with the delta hash satisfies a threshold.
8. The computer readable medium of claim 1 , the method comprising computing one or more subsequent delta hashes based on information gathered from comparing the delta hash to stored delta hashes and controlling the de-duplication logic to process the chunk as a delta chunk as a function of the subsequent delta hashes.
9. The computer readable medium of claim 3 , the two or more delta hashes comprising one or more of:
a first delta hash for a first portion of the chunk, the first portion being less than the entire chunk, the first portion being contiguous within the chunk;
a second delta hash for a second portion of the chunk, the second portion being less than the entire chunk, the second portion being contiguous within the chunk, the second portion not overlapping the first portion;
a third delta hash for a third portion of the chunk, the third portion being less than the entire chunk, the third portion being contiguous within the chunk, the third portion partially overlapping the first portion;
a fourth delta hash for a fourth portion of the chunk, the fourth portion being less than the entire chunk, the fourth portion not being contiguous within the chunk;
a fifth delta hash for a fifth portion of the chunk, the fifth portion being less than the entire chunk, the fifth portion not being contiguous within the chunk, the fifth portion not overlapping the fourth portion; and
a sixth delta hash for a sixth portion of the chunk, the sixth portion being less than the entire chunk, the sixth portion not being contiguous within the chunk, the sixth portion partially overlapping the fourth portion.