METHOD FOR HORIZONTAL SCALE DELTA ENCODING

• US 20130185265A1
• Filed: 02/26/2013
• Published: 07/18/2013
• Est. Priority Date: 05/23/2011
• Status: Active Grant

• Current Assignee: Autodesk, Inc.
• Original Assignee: Ilesfay Technology Group LLC
• Inventors: McLennan, Christopher S., Kramer, Joseph T., Taylor, James P.
• Granted Patent: US 8,996,655 B2
• Time in Patent Office: Days
• US Class Current: 707/690
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

Data can be transferred between computers at remote sites by transferring the data itself, or by transferring files showing how data at an originating site can be recreated from data already present at a receiving site. As part of the data transfer, a determination can be made as to what is the most appropriate way for the transfer to take place. Further, in cases where data is not transferred directly between originating and receiving sites, it is possible that some preparatory steps might be performed to improve the efficiency of the transfers to the receiving sites when they do take place. Additional efficiencies can be obtained in some cases by using the parallel processing capabilities provided by a cloud based architecture.

Claims

1. A method comprising designating a return difference package obtained by performing a differencing process with a first set of data as an input set of data and a set of sub-signatures corresponding to portions of a second set of data as an input base set of sub-signatures as a difference package indicating a derivation of the first set of data, wherein:

a. the differencing process comprises;

determining if a signature corresponding to a portion of the input set of data matches a sub-signature from the input base set of sub-signatures;

ii. performing a difference package modification taken from a set of difference package modifications comprising;

(a) modifying the return difference package to include an instruction to use the portion corresponding to a matching sub-signature from the input base set of sub-signatures in deriving the input set of data; and

(b) modifying the return difference package to include an instruction to use a sub-portion of the portion of the input set of data in deriving the input set of data;

b. the first set of data is stored on a first non-transitory computer readable medium local to a computer executing a set of computer executable instructions to perform the differencing process with the first set of data as the input set of data and a set of sub-signatures corresponding to the set of portions of the second set of data as the input base set of sub-signatures;

c. the second set of data is stored on a second non-transitory computer readable medium which is remote from the first non-transitory computer readable medium.

2. The method of claim 1, further comprising designating a return difference package obtained by performing the differencing process with a third set of data as the input set of data and a set of sub-signatures corresponding to portions of a fourth set of data as the input base set of sub-signatures as a difference package indicating a derivation of the third set of data, wherein:

a. the set of sub-signatures corresponding to portions of the second set of data comprises a sub-signature corresponding to a portion of the second set of data having a first size;

b. the set of sub-signatures corresponding to portions of the fourth set of data comprises a sub-signature corresponding to a portion of the fourth set of data having a second size; and

c. the first size and the second size are different sizes.

3. The method of claim 2, wherein:

a. the second set of data consists of a file having a first format;

b. the fourth set of data consists of a file having a second format;

c. the first size is a portion size identified for use with files having the first format; and

d. the second size is a portion size identified for use with files having the second format.

4. The method of claim 2, wherein:

a. the differencing process is performed with the first set of data as the input set of data and the set of sub-signatures corresponding to portions of the second set of data as the input base set of sub-signatures is performed at a first time;

b. the differencing process is performed with the third set of data as the input set of data and the set of sub-signatures corresponding to portions of the fourth set of data as the input base set of sub-signatures is performed at a second time; and

c. a determinination to use sub-signatures corresponding to portions having the second size rather than sub-signatures corresponding to portions having the first size when determining matches is made between the first time and the first time and the second time.

5. The method of claim 4, wherein the first size is larger than the second size.

6. The method of claim 4, wherein the first size is smaller than the second size.

7. The method of claim 1, wherein:

a. the differencing process comprises determining if a second signature corresponding to second portion of the input set of data matches a second sub-signature from the input base set of sub-signatures;

b. the portion of the input set of data has a first size;

c. the second portion of the input set of data has a second size; and

d. the first size and the second size are not the same size.

8. The method of claim 7, wherein the portion of the input set of data is a sub-portion of the second portion of the input set of data.

9. The method of claim 1, wherein:

a. the first set of data includes only one file; and

b. the second set of data comprises a plurality of files.

10. The method of claim 9, wherein the return difference package obtained by performing the differencing process with the first set of data as the input set of data and the set of sub-signatures corresponding to portions of the second set of data as the input base set of sub-signatures comprises:

a. an instruction to use a portion of a first file from the plurality of files in deriving the input set of data; and

b. an instruction to use a portion of a second file from the plurality of files in deriving the input set of data.

11. A machine comprising:

a. a first non-transitory computer readable medium having stored thereon a first set of data;

b. a second non-transitory computer readable medium having stored thereon a second set of data;

c. a first computer local to the first non-transitory computer readable and configured with a set of computer executable instructions operable to cause the computer to perform a differencing process comprising;

i. determining if a signature corresponding to a portion of an input set of data matches a sub-signature from an input base set of sub-signatures;

ii. performing a difference package modification taken from a set of difference package modifications comprising;

(a) modifying a return difference package to include an instruction to use existing data corresponding to a matching sub-signature from the input base set of sub-signatures in deriving the input set of data; and

(b) modifying the return difference package to include an instruction to use a sub-portion of the portion of the input set of data in deriving the input set of data;

d. a second computer, wherein the second computer is configured with instructions operable to cause the second computer to cause the first computer to;

i. perform the differencing process with

(a) the first set of data as the input set of data; and

(b) a set of sub-signatures corresponding to portions of the second set of data as the input base set of sub-signatures;

ii. designate the return difference package obtained by performing the differencing process with

(a) the first set of data as the input set of data; and

(b) the set of sub-signatures corresponding to portions of the second set of data as the input base set of sub-signatures

as a difference package indicating a derivation of the first set of data by sending the difference package to the second computer in response to a communication requesting the difference package indicating the derivation of the first set of data.

12. The machine of claim 11 wherein:

a. the second computer is configured with instructions which are operable to cause the second computer to cause the first computer to;

i. perform the differencing process with

(a) a third set of data as the input set of data; and

(b) a set of sub-signatures corresponding to portions of a fourth set of data as the input base set of sub-signatures;

ii. designate the return difference package obtained by performing the differencing process with

(a) the third set of data as the input set of data; and

(b) the set of sub-signatures corresponding to portions of the fourth set of data as the input base set of sub-signatures;

as a difference package indicating a derivation of the third set of data by sending the difference package to the second computer in response to a communication requesting the difference package indicating the derivation of the third set of data;

b. the set of sub-signatures corresponding to portions of the second set of data comprises a sub-signature corresponding to a portion of the second set of data having a first size;

c. the set of sub-signatures corresponding to portions of the fourth set of data comprises a sub-signature corresponding to a portion of the fourth set of data having a second size; and

d. the first size and the second size are different sizes.

13. The machine of claim 12, wherein:

a. the second set of data consists of a file having a first format;

b. the fourth set of data consists of a file having a second format;

c. the first size is a portion size identified for use with files having the first format; and

d. the second size is a portion size identified for use with files having the second format.

14. The machine of claim 12, wherein the second computer is configured with instructions operable to cause the second computer to:

a. cause the first computer to;

i. perform the differencing process with

(a) the first set of data as the input set of data; and

(b) the set of sub-signatures corresponding to portions of the second set of data as the input base set of sub-signatures

at a first time;

ii. perform the differencing process with

(a) the third set of data as the input set of data; and

(b) the set of sub-signatures corresponding to portions of the fourth set of data as the input base set of sub-signatures

at a second time;

b. determine to use sub-signatures corresponding to portions having the second size rather than sub-signatures corresponding to portions having the first size between the first time and the second time.

15. The machine of claim 11, wherein:

a. the differencing process comprises determining if a second signature corresponding to a second portion of the input set of data matches a second sub-signature from the input base set of sub-signatures;

b. the portion of the input set of data has a first size;

c. the second portion of the input set of data has a second size; and

d. the first size and the second size are not the same size.

16. The machine of claim 11, wherein:

a. the first set of data includes only one file; and

b. the second set of data comprises a plurality of files.

17. The machine of claim 16, wherein the return difference package obtained by performing the differencing process with

a. the first set of data as the input set of data;

and

b. the set of sub-signatures corresponding to portions of the second set of data as the input base set of sub-signatures;

comprises;

A. an instruction to use a portion of a first file from the plurality of files in deriving the input set of data; and

B. an instruction to use a portion of a second file from the plurality of files in deriving the input set of data.