Efficient algorithm for finding candidate objects for remote differential compression

• US 20060085561A1
• Filed: 09/24/2004
• Published: 04/20/2006
• Est. Priority Date: 09/24/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Teodosiu, Dan, Wable, Akhil, Manasse, Mark S.
• Granted Patent: US 7,613,787 B2
• Time in Patent Office: Days
• US Class Current: 709/247
• CPC Class Codes: G06F 16/174 Redundancy elimination performed by the file system management of the data involved in backup or backup restore using de-duplication of the data G06F11/14

Abstract

The present invention finds candidate objects for remote differential compression. Objects are updated between two or more computing devices using remote differential compression (RDC) techniques such that required data transfers are minimized. An algorithm provides enhanced efficiencies for allowing the receiver to locate a set of objects that are similar to the object that needs to be transferred from the sender. Once this set of similar objects has been found, the receiver may reuse any chunks from these objects during the RDC algorithm.

Claims

1. A method for identifying objects for remote differential compression, comprising:

calculating traits for an object;

using the traits to identify candidate objects that are at least somewhat similar to the object; and

selecting final objects from the identified candidate objects.

2. The method of claim 1, wherein calculating the traits for the object, further comprises:

partitioning the object into chunks;

computing signatures for each of the object chunks;

grouping the signatures into shingles;

computing at least one shingle signature for each of the shingles;

mapping the shingle signatures into image sets;

calculating pre-traits from the image sets; and

computing the traits using the pre-traits, wherein the traits are smaller in size as compared to the pre-traits.

3. The method of claim 2, further comprising using the set of candidate objects when performing remote differential compression techniques.

4. The method of claim 2, further comprising:

generating fingerprints at each byte position of the object by using the values of the bytes in a small window around each position.

5. The method of claim 4, wherein partitioning the object into chunks comprises chunking the object based on the fingerprints.

6. The method of claim 2, wherein grouping the signatures into shingles consists of concatenating q consecutive signatures to form a shingle.

7. The method of claim 2, wherein mapping the shingles into image sets, comprises:

applying t hash functions to each shingle in turn, thereby creating t image sets.

8. The method of claim 2, wherein calculating the pre-traits from the image sets, comprises applying a deterministic mathematical function that selects one of the computed hash values from each image set.

9. The method of claim 8, wherein the deterministic mathematical function is selected from a maxima function and a minima function.

10. The method of claim 7, wherein calculating the traits using the pre-traits, comprises applying a deterministic function to each of the pre-traits that creates traits each having a predetermined number of bits that is smaller than the traits.

11. The method of claim 9, wherein the deterministic function, comprises selecting a specified set of b bits out of each pre-trait.

12. The method of claim 1, wherein using the traits to identify candidate objects that are at least somewhat similar to the object comprises calculating the number of traits that match between the two objects.

13. The method of claim 12, further comprising:

selecting the k best-matching objects guided by the values of the trait similarity.

14. The method of claim 3, wherein the remote differential compression techniques, comprise:

partitioning the k best matching local objects into local chunks;

computing a local signature for each local chunk;

comparing remote signatures received from a remote device to the local signatures; and

reusing local chunks to reconstruct the remote object when the signature comparison indicates the local chunk may be reused.

15. The method of claim 2, further comprising storing the traits within volatile memory of a device by compactly encoding the traits.

16. The method of claim 15, further comprising storing within volatile memory of a device only a selected subset of the traits.

17. The method of claim 2, further comprising storing the traits within persistent memory of a device.

18. The method of claim 17, further comprising storing within persistent memory of a device only a selected subset of the traits.

19. The method of claim 15, further comprising:

creating an object map that compactly represents the object IDs on a device, wherein each compact representation is represented using a predetermined size; and

creating trait tables that form at least a two-level index that maps from a trait number and a trait value to a trait set.

20. The method of claim 19, further comprising rebuilding the object map when it determined that the object map is sparse.

21. The method of claim 19, further comprising:

finding objects with similar traits, including steps for;

creating buckets (OB_x . . . OB_t) to store local objects that match at least x traits of a remote object O_B;

selecting t TraitSets (TS₁ . . . TS_t) corresponding to t traits of object O_B;

initializing indices (P₁ . . . P_t) to point to the first element of TS₁ . . . TS_t, respectively, wherein TS_k[P_k] is the notation for the object ID pointed to by P_k;

selecting a desired number of similar objects when it is determined that each of P₁ . . . P_t point past the last element of their TraitSet arrays TS₁ . . . TS_t, respectively,

selecting a MinP set, wherein the MinP set is the set of indices pointing to the minimum object ID;

setting MinID to be the minimum object ID pointed to by all the indices in MinP.

appending MinID to OB_k when it is determined that k≧

x and ObjectMap(MinP) is not a dead entry, wherein k=|MinP|, which corresponds to the number of matching traits; and

advancing each index P_k in MinP to the next object ID in its respective TraitSet array TS_k.

22. The method of claim 21, wherein selecting a desired number of similar objects comprises first selecting objects from OB_t, and decrementing t and selecting from OB_t until the desired number of similar objects has been selected.

23. The method of claim 21, wherein selecting a desired number of similar objects comprises first selecting objects from OB_t, and decrementing t and selecting from OB_t.

24. A computer-readable medium having computer executable instructions for identifying objects for remote differential compression, comprising:

partitioning an object into chunks;

computing signatures for each of the object chunks;

grouping the signatures into shingles;

computing at least one shingle signature for each of the shingles;

mapping the shingle signatures into image sets;

calculating pre-traits from the image sets; and

computing the traits using the pre-traits, wherein the traits are smaller in size as compared to the pre-traits using the traits to identify candidate objects that are at least somewhat similar to the object; and

selecting final objects from the identified candidate objects.

25. The computer-readable medium of claim 24, wherein partitioning the object into chunks comprises:

generating fingerprints at each byte position of the object by using the values of the bytes in a small window around each position and chunking the object based on the fingerprints.

26. The computer-readable medium of claim 24, wherein grouping the signatures into shingles consists of concatenating signatures to form a shingle.

27. The computer-readable medium of claim 24, wherein mapping the shingles into image sets, comprises:

applying at least one hash functions to each shingle.

28. The computer-readable medium of claim 24, wherein calculating the pre-traits from the image sets, comprises applying a deterministic mathematical function that selects one of the computed hash values from each image set, wherein the deterministic mathematical function is selected from a maxima function and a minima function.

29. The computer-readable medium of claim 28, wherein calculating the traits using the pre-traits, comprises applying a deterministic function to each of the pre-traits that creates traits each having a predetermined number of bits that is smaller than the traits.

30. The computer-readable medium of claim 24, wherein using the traits to identify candidate objects that are at least somewhat similar to the object comprises calculating the number of traits that match between the two objects.

31. The computer-readable medium of claim 24, further comprising:

creating an object map that compactly represents the object IDs on a device, wherein each compact representation is represented using a predetermined size; and

creating trait tables that form at least a two-level index that maps from a trait number and a trait value to a trait set.

32. The computer-readable medium of claim 31, further comprising rebuilding the object map when it determined that the object map is sparse.

33. The computer-readable medium of claim 31, further comprising:

finding objects with similar traits, including steps for;

creating buckets (OB_x . . . OB_t) to store local objects that match at least x traits of a remote object O_B;

selecting t TraitSets (TS₁ . . . TS_t) corresponding to t traits of object O_B;

initializing indices (P₁ . . . P_t) to point to the first element of TS₁ . . . TS_t, respectively, wherein TS_k[P_k] is the notation for the object ID pointed to by P_k;

selecting a desired number of similar objects when it is determined that each of P₁ . . . P_t point past the last element of their TraitSet arrays TS₁ . . . TS_t, respectively,

selecting a MinP set, wherein the MinP set is the set of indices pointing to the minimum object ID;

setting MinID to be the minimum object ID pointed to by all the indices in MinP.

appending MinID to OB_k when it is determined that k≧

x and ObjectMap(MinP) is not a dead entry, wherein k=|MinP|, which corresponds to the number of matching traits; and

advancing each index P_k in MinP to the next object ID in its respective TraitSet array TS_k.

34. A system for identifying objects for remote differential compression, comprising:

a remote device configured to perform steps, comprising;

receive a request for an Object O_B;

send a set of traits of Object O_B to a local device;

partition Object O_B into chunks and compute signatures for each of the chunks;

send the list of chunk signatures to the local device; and

provide requested chunks when requested; and

the local device configured to perform steps, comprising;

request Object O_B from the remote device;

receive the set of traits of Object O_B from the remote device;

use the set of traits of Object O_B to identify similar objects that it already stores on the local device;

partition the similar objects into chunks;

compute signatures for each of the similar object chunks;

receive the list of chunk signatures from the remote device;

compare the received signatures against the locally computed signatures;

request chunks from the remote device that did not match in the comparison;

receive the requested chunks; and

reconstruct Object O_B using the received chunks and chunks reused from the similar objects.

35. The system of claim 34, wherein the local device is further configured, to:

group the signatures into shingles;

compute at least one shingle signature for each of the shingles;

map the shingle signatures into image sets;

calculate pre-traits from the image sets; and

compute the traits using the pre-traits, wherein the traits are smaller in size as compared to the pre-traits using the traits to identify candidate objects that are at least somewhat similar to the object; and

select final objects from the identified candidate objects.

36. The system of claim 35, wherein partitioning the object into chunks comprises:

generating fingerprints at each byte position of the object by using the values of the bytes in a small window around each position and chunking the object based on the fingerprints.

37. The system of claim 36, wherein mapping the shingles into image sets on the local device, comprises:

applying at least one hash functions to each shingle.

38. The system of claim 37, wherein calculating the pre-traits from the image sets, comprises applying a deterministic mathematical function that selects one of the computed hash values from each image set, wherein the deterministic mathematical function is selected from a maxima function and a minima function.

39. The system of claim 38, wherein calculating the traits using the pre-traits, comprises applying a deterministic function to each of the pre-traits that creates traits each having a predetermined number of bits that is smaller than the traits.

40. The system of claim 36, wherein using the traits to identify candidate objects that are at least somewhat similar to the object comprises calculating the number of traits that match between the two objects.

41. The system of claim 36, wherein the local device is further configured to:

create an object map that compactly represents the object IDs on the local device, wherein each compact representation is represented using a predetermined size; and

create trait tables that form at least a two-level index that maps from a trait number and a trait value to a trait set.

42. The system of claim 41, further comprising rebuilding the object map when it determined that the object map is sparse.

43. The system of claim 41, further comprising:

finding objects with similar traits, including steps for;

creating buckets (OB_x . . . OB_t) to store local objects that match at least x traits of a remote object O_B;

selecting t TraitSets (TS₁ . . . TS_t) corresponding to t traits of object O_B;

initializing indices (P₁ . . . P_t) to point to the first element of TS₁ . . . TS_t, respectively, wherein TS_k[P_k] is the notation for the object ID pointed to by P_k;

selecting a desired number of similar objects when it is determined that each of P₁ . . . P_t point past the last element of their TraitSet arrays TS₁ . . . TS_t, respectively,

selecting a MinP set, wherein the MinP set is the set of indices pointing to the minimum object ID;

setting MinID to be the minimum object ID pointed to by all the indices in MinP.

appending MinID to OB_k when it is determined that k≧

x and ObjectMap(MinP) is not a dead entry, wherein k=|MinP|, which corresponds to the number of matching traits; and

advancing each index P_k in MinP to the next object ID in its respective TraitSet array TS_k.

44. The system of claim 43, wherein selecting a desired number of similar objects comprises first selecting objects from OB_t, and decrementing t and selecting from OB_t until the desired number of similar objects has been selected.

45. The system of claim 43, wherein selecting a desired number of similar objects comprises first selecting objects from OB_t, and decrementing t and selecting from OB_t.