Efficient algorithm for finding candidate objects for remote differential compression

• US 8,112,496 B2
• Filed: 07/31/2009
• Issued: 02/07/2012
• Est. Priority Date: 09/24/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Manasse, Mark S., Teodosiu, Dan, Wable, Akhil
• Primary Examiner(s): Dinh, Khanh
• Application Number:
  US12/533,437
• Publication Number:
  US 20100064141A1
• Time in Patent Office: 921 Days
• Field of Search: 709/217, 709/238, 709/247, 706/13
• US Class Current: 709/217
• 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 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.

2. The system of claim 1, 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.

3. The system of claim 2, 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.

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

applying at least one hash functions to each shingle.

5. The system of claim 4, 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.

6. The system of claim 5, 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.

7. The system of claim 3, 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.

8. The system of claim 3, 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.

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

10. The system of claim 8, 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.

11. The system of claim 10, 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.

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