Systems and methods for managing delta version chains

• US 9,430,546 B2
• Filed: 11/18/2013
• Issued: 08/30/2016
• 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): Ly, Anh
• Application Number:
  US14/082,921
• Publication Number:
  US 20140122425A1
• Time in Patent Office: 1,016 Days
• Field of Search: 707/610, 707/695, 707/638, 707/693, 707/661, 707/637, 707/692, 707/737, 707/E17.005, 707/E17.011, 707/E17.044, 707/812, 707/E17.002, 709/247, 709/231, 715/229, 715/242, 382/238, 382/232, 382/233, 382/235, 382/244, 382/243, 382/305, 714/805
• US Class Current: 1/1
• 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:

generating an instruction for uncompressing at least one compressed version of data corresponding to an uncompressed version of data in a version chain containing a plurality of versions of data, the instruction containing a key representative of a location of a data segment to be copied in the uncompressed version of data and a value representative of a length of data segment to be copied in the uncompressed version of data, the data segment is present in at least another uncompressed version of data in the version chain; and

uncompressing, based on the generated instruction, the at least one compressed version of data;

wherein the compressed version of data depends on another compressed version of data corresponding to the another uncompressed version of data in the version chain;

wherein the at least one of the generating and the uncompressing is performed on at least one processor of at least one computing system.

2. The method according to claim 1, wherein the instruction includes a predetermined combination of at least one of the following:

at least one insert instruction and at least one copy instruction corresponding to at least one compressed version of data.

3. The method according to claim 1, wherein the compressed version of data is a delta-compressed version of data.

4. The method according to claim 1, wherein the generated instruction is used to uncompress any version of data in the version chain.

5. The method according to claim 1, wherein the generated instruction includes an instruction that is modified based on the at least one insert instruction.

6. The method according to claim 1, wherein the generated instruction includes a plurality of different copy instructions.

7. The method according to claim 6, wherein the generated instruction includes an instruction modified based on at least one copy instruction in the plurality of different copy instructions.

8. The method according to claim 1, wherein the uncompressing further comprises executing the generated instruction in a predetermined order.

9. The method according to claim 1, further comprising purging any version of data in the version chain.

10. 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;

generating an instruction for uncompressing at least one compressed version of data corresponding to an uncompressed version of data in a version chain containing a plurality of versions of data, the instruction containing a key representative of a location of a data segment to be copied in the uncompressed version of data and a value representative of a length of data segment to be copied in the uncompressed version of data, the data segment is present in at least another uncompressed version of data in the version chain; and

uncompressing, based on the generated instruction, the at least one compressed version of data;

wherein the compressed version of data depends on another compressed version of data corresponding to the another uncompressed version of data in the version chain.

11. The system according to claim 10, wherein the instruction includes a predetermined combination of at least one of the following:

at least one insert instruction and at least one copy instruction corresponding to at least one compressed version of data.

12. The system according to claim 10, wherein the compressed version of data is a delta-compressed version of data.

13. The system according to claim 10, wherein the generated instruction is used to uncompress any version of data in the version chain.

14. The system according to claim 10, wherein the generated instruction includes an instruction that is modified based on the at least one insert instruction.

15. The system according to claim 10, wherein the generated instruction includes a plurality of different copy instructions.

16. The system according to claim 15, wherein the generated instruction includes an instruction modified based on at least one copy instruction in the plurality of different copy instructions.

17. The system according to claim 10, wherein the uncompressing further comprises executing the generated instruction in a predetermined order.

18. The system according to claim 10, further comprising purging any version of data in the version chain.

19. 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:

generating an instruction for uncompressing at least one compressed version of data corresponding to an uncompressed version of data in a version chain containing a plurality of versions of data, the instruction containing a key representative of a location of a data segment to be copied in the uncompressed version of data and a value representative of a length of data segment to be copied in the uncompressed version of data, the data segment is present in at least another uncompressed version of data in the version chain;

uncompressing, based on the generated instruction, the at least one compressed version of data;

wherein the compressed version of data depends on another compressed version of data corresponding to the another uncompressed version of data in the version chain;

wherein the at least one of the generating and the uncompressing is performed on at least one processor of at least one computing system.

20. The computer program product according to claim 19, wherein the instruction includes a predetermined combination of at least one of the following:

at least one insert instruction and at least one copy instruction corresponding to at least one compressed version of data.

21. The computer program product according to claim 19, wherein the compressed version of data is a delta-compressed version of data.

22. The computer program product according to claim 19, wherein the generated instruction is used to uncompress any version of data in the version chain.

23. The computer program product according to claim 19, wherein the generated instruction includes an instruction that is modified based on the at least one insert instruction.

24. The computer program product according to claim 19, wherein the generated instruction includes a plurality of different copy instructions.

25. The computer program product according to claim 24, wherein the generated instruction includes an instruction modified based on at least one copy instruction in the plurality of different copy instructions.

26. The computer program product according to claim 19, wherein the uncompressing further comprises executing the generated instruction in a predetermined order.

27. The computer program product according to claim 19, further comprising purging any version of data in the version chain.