Systems and methods for managing delta version chains

• US 8,589,363 B2
• Filed: 03/29/2012
• Issued: 11/19/2013
• Est. Priority Date: 07/19/2011
• Status: Active Grant

• Current Assignee: ExaGrid Systems, Inc.
• Original Assignee: ExaGrid Systems, Inc.
• Inventors: Poirier, Jamey C., Sylva, William Joseph
• Primary Examiner(s): Fleurantin, Jean B
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US13/434,306
• Publication Number:
  US 20130024435A1
• Time in Patent Office: 600 Days
• Field of Search: 707/695, 707/638, 707/E17.005, 707/999.203, 707/999.1, 715/229, 715/242, 715/FOR.221, 382/232, 382/233, 382/235, 382/243, 382/244
• US Class Current: 707/695
• CPC Class Codes: G06F 16/1756 based on delta files
• 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

Abstract

A system, a method, and a computer program product for managing delta version chains are provided. A version chain having a plurality of versions of data is provided. A first delta-compressed version and a second delta-compressed version corresponding to a first version of data in the version chain and a second version of data in the version chain, respectively, are selected. A third delta-compressed version configured to be independent of at least one of the first delta-compressed version and the second delta-compressed version and further configured to contain at least one third instruction determined based on at least one of the following: the first insert instruction, the second insert instruction, the first copy instruction, and the second copy instruction, is generated.

Claims

1. A computer implemented method, comprising:

providing a version chain having a plurality of versions of data;

selecting a first delta-compressed version and a second delta-compressed version corresponding to a first version of data in the version chain and a second version of data in the version chain, respectively, wherein

the second delta-compressed version is configured to depend on the first delta compressed version;

the first delta-compressed version is configured to include at least one of a first copy instruction and a first insert instruction; and

the second delta-compressed version is configured to include at least one of a second copy instruction and a second insert instruction;

generating a third delta-compressed version configured to be independent of at least one of the first delta-compressed version and the second delta-compressed version and further configured to contain at least one third instruction determined based on a predetermined combination of at least one of the following;

the first insert instruction, the second insert instruction, the first copy instruction, and the second copy instruction, whereby the third delta-compressed version is configured to be used to retrieve any version in the version chain;

wherein the at least one of the providing, the selecting, and the generating is performed on at least one processor; and

wherein the at least one third instruction is configured to include at least one parameter, wherein the at least one parameter includes at least one of the following a length parameter defining a length of data to be copied in the uncompressed version of data and an offset parameter defining a location of data to be copied in the uncompressed version of data; and

wherein at least one the first and second copy instructions is configured to cause a copy of a data segment into an uncompressed version of data in the version chain, wherein the data segment is present in both a first uncompressed version of data configured to be generated based on the first delta-compressed version and in a second uncompressed version of data configured to be generated based on the second delta-compressed version.

2. The method according to claim 1, wherein the third delta-compressed version is configured to contain at least one of the first insert instruction and the second insert instruction.

3. The method according to claim 2, wherein the third delta-compressed version is configured to contain an instruction that is modified from at least one of the first insert instruction and the second insert instruction.

4. The method according to claim 1, wherein the third delta-compressed version is configured to contain at least one of the first and second copy instructions depending on whether the first and second instructions are different from one another.

5. The method according to claim 4, wherein the third delta-compressed version is configured to contain an instruction that is modified from at least one of the first copy instruction and the second copy instruction.

6. The method according to claim 1, further comprising

executing the at least one third instruction contained in the generated third delta-compressed version to generate an uncompressed version of data in the version chain.

7. The method according to claim 1, wherein the executing further comprises executing the at least one third instruction contained in the generated third delta-compressed version in a predetermined order.

8. The method according to claim 1, wherein

the first insert operation is configured to cause insertion of a first data segment into the uncompressed version of data in the version chain, wherein the first data segment is present in a first uncompressed version of data configured to be generated based on the first delta-compressed version;

the second insert instruction is configured to cause insertion of a second data segment into the uncompressed version of data in the version chain, wherein the second data segment is present in a second uncompressed version of data configured to be generated based on the second delta-compressed version.

9. The method according to claim 1, further comprising

deleting at least one of the first delta-compressed version and the second delta-compressed version without uncompressing the first delta-compressed version and the second delta-compressed version.

10. The method according to claim 1, further comprising repeating the providing, the selecting, and the generating to enable faster restore of a version in the version chain.

11. A system for storing data, comprising:

at least one processor; and

at least one machine-readable medium storing instructions that, when executed by the at least one processor, cause the at least one processor to perform operations comprising;

providing a version chain having a plurality of versions of data;

selecting a first delta-compressed version and a second delta-compressed version corresponding to a first version of data in the version chain and a second version of data in the version chain, respectively, wherein

the second delta-compressed version is configured to depend on the first delta compressed version;

the first delta-compressed version is configured to include at least one of a first copy instruction and a first insert instruction; and

the second delta-compressed version is configured to include at least one of a second copy instruction and a second insert instruction;

generating a third delta-compressed version configured to be independent of at least one of the first delta-compressed version and the second delta-compressed version and further configured to contain at least one third instruction determined based on a predetermined combination of at least one of the following;

the first insert instruction, the second insert instruction, the first copy instruction, and the second copy instruction, whereby the third delta-compressed version is configured to be used to retrieve any version in the version chain; and

wherein the at least one third instruction is configured to include at least one parameter, wherein the at least one parameter includes at least one of the following a length parameter defining a length of data to be copied in the uncompressed version of data and an offset parameter defining a location of data to be copied in the uncompressed version of data; and

wherein at least one the first and second copy instructions is configured to cause a copy of a data segment into an uncompressed version of data in the version chain, wherein the data segment is present in both a first uncompressed version of data configured to be generated based on the first delta-compressed version and in a second uncompressed version of data configured to be generated based on the second delta-compressed version.

12. The system according to claim 11, wherein the third delta-compressed version is configured to contain at least one of the first insert instruction and the second insert instruction.

13. The system according to claim 12, wherein the third delta-compressed version is configured to contain an instruction that is modified from at least one of the first insert instruction and the second insert instruction.

14. The system according to claim 11, wherein the third delta-compressed version is configured to contain at least one of the first and second copy instructions depending on whether the first and second instructions are different from one another.

15. The system according to claim 14, wherein the third delta-compressed version is configured to contain an instruction that is modified from at least one of the first copy instruction and the second copy instruction.

16. The system according to claim 11, wherein the operations further comprise

executing the at least one third instruction contained in the generated third delta-compressed version to generate an uncompressed version of data in the version chain.

17. The system according to claim 11, wherein the executing further comprises executing the at least one third instruction contained in the generated third delta-compressed version in a predetermined order.

18. The system according to claim 11, wherein

the first insert operation is configured to cause insertion of a first data segment into the uncompressed version of data in the version chain, wherein the first data segment is present in a first uncompressed version of data configured to be generated based on the first delta-compressed version;

the second insert instruction is configured to cause insertion of a second data segment into the uncompressed version of data in the version chain, wherein the second data segment is present in a second uncompressed version of data configured to be generated based on the second delta-compressed version.

19. The system according to claim 11, further comprising

deleting at least one of the first delta-compressed version and the second delta-compressed version without uncompressing the first delta-compressed version and the second delta-compressed version.

20. The system according to claim 11, further comprising repeating the providing, the selecting, and the generating to enable faster restore of a version in the version chain.

21. A non-transitory computer program product comprising machine-readable medium storing instructions that, when executed by the at least one processor, cause the at least one processor to perform operations comprising:

providing a version chain having a plurality of versions of data;

selecting a first delta-compressed version and a second delta-compressed version corresponding to a first version of data in the version chain and a second version of data in the version chain, respectively, wherein

the second delta-compressed version is configured to depend on the first delta compressed version;

the first delta-compressed version is configured to include at least one of a first copy instruction and a first insert instruction; and

the second delta-compressed version is configured to include at least one of a second copy instruction and a second insert instruction;

generating a third delta-compressed version configured to be independent of at least one of the first delta-compressed version and the second delta-compressed version and further configured to contain at least one third instruction determined based on a predetermined combination of at least one of the following;

the first insert instruction, the second insert instruction, the first copy instruction, and the second copy instruction, whereby the third delta-compressed version is configured to be used to retrieve any version in the version chain; and

wherein the at least one third instruction is configured to include at least one parameter, wherein the at least one parameter includes at least one of the following a length parameter defining a length of data to be copied in the uncompressed version of data and an offset parameter defining a location of data to be copied in the uncompressed version of data; and

wherein at least one the first and second copy instructions is configured to cause a copy of a data segment into an uncompressed version of data in the version chain, wherein the data segment is present in both a first uncompressed version of data configured to be generated based on the first delta-compressed version and in a second uncompressed version of data configured to be generated based on the second delta-compressed version.

22. The computer program product according to claim 21, wherein the third delta-compressed version is configured to contain at least one of the first insert instruction and the second insert instruction.

23. The computer program product according to claim 22, wherein the third delta-compressed version is configured to contain an instruction that is modified from at least one of the first insert instruction and the second insert instruction.

24. The computer program product according to claim 21, wherein the third delta-compressed version is configured to contain at least one of the first and second copy instructions depending on whether the first and second instructions are different from one another.

25. The computer program product according to claim 24, wherein the third delta-compressed version is configured to contain an instruction that is modified from at least one of the first copy instruction and the second copy instruction.

26. The computer program product according to claim 21, wherein the operations further comprise

executing the at least one third instruction contained in the generated third delta-compressed version to generate an uncompressed version of data in the version chain.

27. The computer program product according to claim 21, wherein the executing further comprises executing the at least one third instruction contained in the generated third delta-compressed version in a predetermined order.

28. The computer program product according to claim 21, wherein

the first insert operation is configured to cause insertion of a first data segment into the uncompressed version of data in the version chain, wherein the first data segment is present in a first uncompressed version of data configured to be generated based on the first delta-compressed version;

the second insert instruction is configured to cause insertion of a second data segment into the uncompressed version of data in the version chain, wherein the second data segment is present in a second uncompressed version of data configured to be generated based on the second delta-compressed version.

29. The computer program product according to claim 21, further comprising

deleting at least one of the first delta-compressed version and the second delta-compressed version without uncompressing the first delta-compressed version and the second delta-compressed version.

30. The computer program product according to claim 21, further comprising repeating the providing, the selecting, and the generating to enable faster restore of a version in the version chain.