SYSTEM AND METHOD FOR APPLYING DELTAS IN A VERSION CONTROL SYSTEM

• US 20100082580A1
• Filed: 10/01/2008
• Published: 04/01/2010
• Est. Priority Date: 10/01/2008
• Status: Active Grant

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Inventors: DeFrang, Bruce
• Granted Patent: US 8,341,132 B2
• Time in Patent Office: Days
• US Class Current: 707/706
• CPC Class Codes: G06F 40/197 Version control for software G06F8/71
• CPC Class Codes: G06F 8/71 Version control security arrangements therefor G06F21/57; Configuration management

Abstract

A system and method that efficiently maintains multiple versions of a dataset using recursive calls is provided. The method may include fully storing one or more versions of the dataset and storing only changes, called deltas, that occurred from one version to another. Using recursive techniques eliminates the need to generate interim versions in their entirety to generate a requested version. For each position in the requested version the method may include generating content by recursive calls. Each recursive call may initiate a request on an adjacent version to produce content at its corresponding position. The request triggers a recursive call by the adjacent version, which may in turn initiate another request on its adjacent version. This series of recursive calls may be repeated until a fully stored version, which simply returns its content, is reached. The requested version may then generated using content generated for each position by the recursive calls.

Claims

1. A computer-implemented method for retrieving a particular version of a document having a plurality of versions comprising:

receiving a request to retrieve the particular version of the document from among the plurality of versions of the document;

retrieving one or more deltas corresponding to the requested particular version of the document, wherein each delta of the one or more deltas respectively corresponds to at least one change to data at one or more positions in the requested particular version of the document relative to an adjacent version of the document;

for each delta of the one or more deltas;

recursively determining adjacent data corresponding to the delta at the adjacent version of the document,

applying the delta to the determined adjacent data, and

generating data accounting for the at least one change to data at the one or more positions based on the applied delta;

generating the requested particular version of the document based at least in part on the generated data for each delta of the one or more deltas, whereby the requested particular version of the document is generated without generating the adjacent version of the document in its entirety; and

presenting the requested particular version in response to the received request.

2. The computer-implemented method of claim 1, wherein the adjacent version of the document comprises one or more second deltas, and wherein recursively determining adjacent data comprises:

retrieving the one or more second deltas corresponding to the adjacent version of the document, wherein each delta of the one or more second deltas respectively corresponds to at least one change to data at one or more positions in the adjacent version of the document relative to a second adjacent version of the document, wherein the second adjacent version of the document is adjacent to the adjacent version of the document;

for each second delta of the one or more second deltas that corresponds to the adjacent data;

recursively determining second adjacent data corresponding to the second delta at the second adjacent version of the document,

applying the second delta to the determined second adjacent data, and

generating second data based on the applied second delta;

generating the adjacent data based on the generated second data; and

returning the adjacent data.

3. The computer-implemented method of claim 1, wherein the adjacent version of the document is a fully stored version of the document.

4. The computer-implemented method of claim 1, wherein the one or more deltas are forward deltas, wherein the a fully stored version of the document is a prior version of the document relative to the one or more delta versions of the document.

5. The computer-implemented method of claim 1, wherein the one or more deltas are reverse deltas, wherein a fully stored version of the document is a subsequent version of the document relative to the one or more delta versions of the document.

6. The computer-implemented method of claim 1, wherein at least one of the one or more deltas is an insert delta.

7. The computer-implemented method of claim 1, wherein at least one of the one or more deltas is a delete delta.

8. The computer-implemented method of claim 1, wherein the document is text and the one or more positions are line numbers.

9. The computer-implemented method of claim 1, wherein the document is binary and the one or more positions are byte locations.

10. The computer-implemented method of claim 1, further comprising:

tracking a current position while recursively determining adjacent data.

11. The computer-implemented method of claim 10, further comprising:

tracking a current delta being applied.

12. A tangible computer readable medium storing computer executable instructions for retrieving a particular version of a document having a plurality of versions, the instructions operable when executed to:

receive a request to retrieve the particular version of the document from among the plurality of versions of the document;

retrieve one or more deltas corresponding to the requested particular version of the document, wherein each delta of the one or more deltas respectively corresponds to at least one change to data at one or more positions in the requested particular version of the document relative to an adjacent version of the document;

for each delta of the one or more deltas;

recursively determine adjacent data corresponding to the delta at the adjacent version of the document,

apply the delta to the determined adjacent data, and

generate data accounting for the at least one change to data at the one or more positions based on the applied delta;

generate the requested particular version of the document based at least in part on the generated data for each delta of the one or more deltas, whereby the requested particular version of the document is generated without generating the adjacent version of the document in its entirety; and

present the requested particular version in response to the received request.

13. The tangible computer readable medium of claim 12, wherein the adjacent version of the document comprises one or more second deltas, and wherein recursively determining adjacent data comprises:

retrieve the one or more second deltas corresponding to the adjacent version of the document, wherein each delta of the one or more second deltas respectively corresponds to at least one change to data at one or more positions in the adjacent version of the document relative to a second adjacent version of the document, wherein the second adjacent version of the document is adjacent to the adjacent version of the document;

for each second delta of the one or more second deltas that corresponds to the adjacent data;

recursively determine second adjacent data corresponding to the second delta at the second adjacent version of the document,

apply the second delta to the determined second adjacent data, and

generate second data based on the applied second delta;

generate the adjacent data based on the generated second data; and

return the adjacent data.

14. The tangible computer readable medium of claim 12, wherein the adjacent version of the document is a fully stored version.

15. The tangible computer readable medium of claim 12, wherein the one or more deltas are forward deltas, wherein a fully stored version of the document is a prior version of the document relative to the one or more delta versions of the document.

16. The tangible computer readable medium of claim 12, wherein the one or more deltas are reverse deltas, wherein a fully stored version of the document is a subsequent version of the document relative to the one or more delta versions of the document.

17. The tangible computer readable medium of claim 12, wherein at least one of the one or more deltas is an insert delta.

18. The tangible computer readable medium of claim 12, wherein at least one of the one or more deltas is a delete delta.

19. The tangible computer readable medium of claim 12, wherein the document is text and the one or more positions are line numbers.

20. The tangible computer readable medium of claim 12, wherein the document is binary and the one or more positions are byte locations.

21. The tangible computer readable medium of claim 12, the instructions further operable when executed to:

track a current position while recursively determining adjacent data.

22. The tangible computer readable medium of claim 21, the instructions further operable when executed to:

track a current delta being applied.

23. A system for retrieving a particular version of a document having a plurality of versions comprising:

one or more processors configured to;

receive a request to retrieve the particular version of the document from among the plurality of versions of the document;

retrieve one or more deltas corresponding to the requested particular version of the document, wherein each delta of the one or more deltas respectively corresponds to at least one change to data at one or more positions in the requested particular version of the document relative to an adjacent version of the document;

for each delta of the one or more deltas;

recursively determine adjacent data corresponding to the delta at the adjacent version of the document,

apply the delta to the determined adjacent data, and

generate data accounting for the at least one change to data at the one or more positions based on the applied delta;

generate the requested particular version of the document based at least in part on the generated data for each delta of the one or more deltas, whereby the requested particular version of the document is generated without generating the adjacent version of the document in its entirety; and

present the requested particular version in response to the received request.

24. The system of claim 23, wherein the adjacent version of the document comprises one or more second deltas, and wherein recursively determining adjacent data comprises:

retrieve the one or more second deltas corresponding to the adjacent version of the document, wherein each delta of the one or more second deltas respectively corresponds to at least one change to data at one or more positions in the adjacent version of the document relative to a second adjacent version of the document, wherein the second adjacent version of the document is adjacent to the adjacent version of the document;

for each second delta of the one or more second deltas that corresponds to the adjacent data;

recursively determine second adjacent data corresponding to the second delta at the second adjacent version of the document,

apply the second delta to the determined second adjacent data, and

generate second data based on the applied second delta;

generating the adjacent data based on the generated second data; and

return the adjacent data.

25. The system of claim 23, wherein the adjacent version of the document is a fully stored version.

26. The system of claim 23, wherein the one or more deltas are forward deltas, wherein a fully stored version of the document is a prior version of the document relative to the one or more delta versions of the document.

27. The system of claim 23, wherein the one or more deltas are reverse deltas, wherein a fully stored version of the document is a subsequent version of the document relative to the one or more delta versions of the document.

28. The system of claim 23, wherein at least one of the one or more deltas is an insert delta.

29. The system of claim 23, wherein at least one of the one or more deltas is a delete delta.

30. The system of claim 23, wherein the document is text and the one or more positions are line numbers.

31. The system of claim 23, wherein the document is binary and the one or more positions are byte locations.

32. The system of claim 23, the one or more processors further configured to:

track a current position while recursively determining adjacent data.

33. The system of claim 32, the one or more processors further configured to:

track a current delta being applied.