Granted Patent B1

US 10,915,260 · App. 15/964,309 · Granted Feb 9, 2021

Inventors: Chao Lei (Beijing, CN); Hui Yuan (Beijing, CN); Qing Fu Dong (Beijing, CN)

Assignee: Veritas Technologies LLC

G06F3/0641G06F3/0608G06F12/0893G06F16/137G06F16/1748G06F16/907

Abstract

Claims (79)

1. A computer-implemented method, comprising:

storing segment layout information of a backup image in a cache;

receiving a data stream having a plurality of variable-length data segments;

executing a fast mode of deduplication operations including,

calculating a fingerprint of a variable-length data segment received in the data stream, wherein the length of the data segment corresponds to the length of a corresponding data segment defined in the cache,

determining whether the calculated fingerprint of the variable-length data segment received in the data stream matches a fingerprint of the corresponding data segment in the cache,

if the calculated fingerprint matches the fingerprint of the corresponding data segment in the cache, continuing to execute deduplication operations in the fast mode on subsequent data segments in the data stream so long as the calculated fingerprint of each variable-length data segment received in the data stream matches the fingerprint for the corresponding data segment in the cache;

if it is determined that the calculated fingerprint of the variable-length data segment received in the data stream does not match the fingerprint for the corresponding data segment in the cache, executing a slow mode of deduplication operations, wherein the slow mode of deduplication operations include,

calculating a new segment boundary for the data segment that does not match the fingerprint in the data stream using a rolling hash operation,

calculating a new fingerprint for the data segment defined by the new segment boundary,

continuing execution of the slow mode of deduplication operations on subsequent segments in the data stream until a fingerprint calculated based on a subsequent variable length data segment matches the fingerprint of a corresponding data segment in the cache; and

returning to the execution of the fast mode of deduplication operations if it is determined that the fingerprint calculated based on a subsequent data segment matches the fingerprint for a corresponding data segment in the cache.

2. The computer-implemented method of claim 1 , wherein

the subsequent data segments in the data stream used in the fast mode of deduplication operations are adjacent to one another; and

the subsequent data segments in the data stream used in the slow mode of deduplication operations are adjacent data segments having the new data segment boundary.

3. The computer-implemented method of claim 1 , further comprising:

retrieving data segment metadata associated with the backup image, wherein

the backup image is maintained by a backup server,

the backup image is a previous backup image, and

the data segment metadata comprises fingerprints and respective data segment lengths.

4. The computer-implemented method of claim 1 , further comprising:

deduplicating substantially all of the variable-length data segments of the data stream.

5. The computer-implemented method of claim 4 , wherein

deduplication operations are executed in a dual-mode deduplication process including the fast mode of deduplication operations and the slow mode of deduplication operations, wherein

the fast mode of the dual-mode implements hashing of data in the data stream for calculating the fingerprints of the variable-length data segments, and

the slow mode of the dual-mode implements a rolling hashing of data in the data stream.

6. The computer-implemented method of claim 1 , further comprising:

switching between the fast mode of deduplication operations and the slow mode of deduplication operations, and vice-versa, to implement dual-mode deduplication operations on the data stream.

7. The computer-implemented method of claim 1 , wherein

the fast mode of deduplication operations utilizes segment length information from a previous backup image as a segment boundary to chunk a current data stream to compute one or more fingerprints of one or more data segments in the current data stream.

8. A non-transitory computer readable storage medium comprising program instructions executable to:

store segment layout information of a backup image in a cache;

receive a data stream having a plurality of variable length data segments;

execute a fast mode of deduplication operations including,

calculating a fingerprint of a variable-length data segment received in the data stream, wherein the length of the data segment corresponds to the length of a corresponding data segment defined in the cache,

determining whether the calculated fingerprint of the variable-length data segment matches a fingerprint of the corresponding data segment in the cache;

if the calculated fingerprint matches the fingerprint of the corresponding fingerprint in the cache, continuing execution of deduplication operations in the fast mode of deduplication operations on subsequent data segments in the data stream so long as the calculated fingerprint of each variable-length data segment received in the data stream matches the fingerprint of a corresponding data segment in the cache;

if it is determined that the calculated fingerprint of the variable-length data segment received in the data stream does not match the fingerprint for the corresponding data segment in the cache, executing a slow mode of deduplication operations, wherein the slow mode of deduplication operations include,

calculating a new segment boundary of the data segment that does not match the fingerprint in the data stream using a rolling hash operation,

calculating a new fingerprint for the data segment defined by the new segment boundary,

continue execution of the slow mode of deduplication operations on subsequent variable-length data segments in the data stream until a fingerprint calculated based on a subsequent variable length data segment matches a fingerprint of a corresponding data segment in the cache; and

returning to the execution of the fast mode of deduplication operations if it is determined that the fingerprint calculated based on a subsequent data segment matches a fingerprint for a corresponding data segment in the cache.

9. The non-transitory computer readable storage medium of claim 8 , wherein

the subsequent data segments in the data stream used in the fast mode of deduplication operations are adjacent to one another; and

the subsequent data segments in the data stream used in the slow mode of deduplication operations are adjacent data segments having the new data segment boundary.

10. The non-transitory computer readable storage medium of claim 8 , further comprising:

retrieving data segment metadata associated with the backup image, wherein

the backup image is maintained by a backup server,

the backup image is a previous backup image, and

the data segment metadata comprises fingerprints and respective data segment lengths.

11. The non-transitory computer readable storage medium of claim 8 , further comprising:

duplicating substantially all of the variable-length data segments of the data stream.

12. The non-transitory computer readable storage medium of claim 11 , wherein

deduplication operations are executed in a dual-mode deduplication process including the fast mode of deduplication operations and the slow mode of deduplication operations, wherein

the fast mode of the dual-mode deduplication process implements hashing of data in the data stream for calculating the fingerprints of the variable-length data segments, and

the slow mode of the dual-mode deduplication process implements a rolling hash of data in the data stream.

13. A system comprising:

one or more processors; and

a memory coupled to the one or more processors, wherein the memory stores program instructions executable by the one or more processors to:

store segment layout information of a backup image in a cache;

receive a data stream having a plurality of variable length data segments;

execute a fast mode of deduplication operations including,

calculating a fingerprint of a variable-length data segment received in the data stream, wherein the variable-length corresponds to the length of a corresponding data segment defined in the cache;

determining whether the calculated fingerprint of the variable-length data segment matches a fingerprint of the corresponding data segment in the cache;

if the calculated fingerprint matches the fingerprint of the corresponding fingerprint in the cache, continuing to execute deduplication operations in the fast mode on subsequent data segments in the data stream so long as the calculated fingerprint of each variable-length data segment received in the data stream matches the fingerprint for the corresponding data segment in the cache,

if it is determined that the calculated fingerprint of the variable-length data segment received in the data stream does not match the fingerprint for the corresponding data segment in the cache, executing a slow mode of deduplication operations, wherein the slow mode of deduplication operations include,

calculating a new segment boundary of the data segment that does not match the fingerprints in the data stream using a hash operation,

calculating a new fingerprint for the data segment defined by the new segment boundary,

continuing execution of the slow mode of deduplication operations on subsequent variable-length data segments in the data stream until a fingerprint calculated based on a subsequent variable length data segment matches a corresponding data segment in the cache; and

returning to execution of the fast mode of deduplication operations if it is determined that the fingerprint calculated based on a subsequent data segment matches a fingerprint for a corresponding data segment in the cache.

14. The system of claim 13 , wherein

the subsequent data segments in the data stream used in the fast mode of deduplication operations are adjacent to one another; and

the subsequent data segments in the data stream used in the slow mode of deduplication operations are adjacent data segments having the new data segment boundary.

15. The system of claim 14 , further comprising:

deduplicating substantially all of the data segments of the data stream.

16. The system of claim 15 , wherein

the deduplication operations are executed in a dual-mode deduplication process including the fast mode of deduplication operations and the slow mode of de-duplication operations, wherein

the fast mode of the dual-mode deduplication process implements hashing of data in the data stream, and

the slow mode of the dual-mode deduplication process implements a rolling hash of data in the data stream.

Assignments (11)

Cited By (5)

US 12,411,776 US 12,581,161 US 12,608,279 US 12,645,545 US 12,664,245