IP Library › Granted Patent US 10,114,831

Granted Patent B2

US 10,114,831 · App. 13/961,259 · Granted Oct 30, 2018

Delta version clustering and re-anchoring

Inventors: Adrian VanderSpek (Worcester, MA); Jamey C. Poirier (Grafton, MA); Lucas H. Makosky (Harvard, MA); Ashok T. Ramu (Waltham, MA); Mark Bennett Hecker (Northborough, MA); Thomas G. Hansen (Bellingham, MA); David G. Therrien (Nashua, NH)

Assignee: Exagrid Systems, Inc.

G06F17/30153 G06F17/30162

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 10,114,831
App. No.: 13/961,259
Granted: Oct 30, 2018
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

A system, a method, and a computer program product for delta version clustering and re-anchoring are provided. A first anchor having a plurality of delta-compressed versions of data dependent on the first anchor is generated. The first anchor and the plurality of delta-compressed versions form a cluster. A second anchor is generated. The first anchor is replaced with the second anchor. The replacing includes re-computing at least one delta-compressed version in the plurality of delta-compressed versions to be dependent on the second anchor. The second anchor replaces the first anchor as an anchor of the cluster.

Claims (270)

1. A computer-implemented method comprising:

generating a first anchor in a plurality of anchors having a plurality of delta-compressed versions of data dependent on the first anchor, wherein the first anchor being at least one of the following: a version of data and a delta-compressed version of the data,

wherein the plurality of delta-compressed versions includes delta-compressed versions that do not linearly depend on one another, each delta-compressed version in at least a portion of the delta-compressed versions in the plurality of delta-compressed versions is computed against the first anchor, the first anchor and the plurality of delta-compressed versions form a cluster;

generating a decompressed second anchor in the plurality of anchors, wherein the decompressed second anchor includes at least another version of the data; and

replacing the first anchor with the generated decompressed second anchor,

wherein the replacing includes

decompressing the first anchor to generate a decompressed first anchor;

determining a difference between the decompressed first anchor and the generated decompressed second anchor;

generating a first reverse delta-compressed version representative of the determined difference between the decompressed first anchor and the generated decompressed second anchor, wherein the first reverse delta-compressed version is dependent on the generated decompressed second anchor, wherein each delta-compressed version in the at least a portion of the delta-compressed versions being previously dependent on the first anchor is computed to be dependent on the first reversed delta-compressed version;

re-computing, using the determined difference between the decompressed first anchor and the generated decompressed second anchor, at least one delta-compressed version in the plurality of delta-compressed versions to be dependent on the generated decompressed second anchor, wherein the re-computed at least one delta-compressed version is delta-compressed against the generated decompressed second anchor; and

compressing the generated decompressed second anchor, wherein the compressed second anchor replaces the first anchor as an anchor of the cluster;

wherein at least one of the generating the first anchor, the generating the decompressed second anchor, and the replacing is performed on at least one processor.

2. The method according to claim 1 , wherein the decompressed second anchor is created based on a determination that the plurality of versions meets at least one condition.

3. The method according to claim 2 , wherein the at least one condition includes at least one of the following: a size of at least one zone in at least delta-compressed version, a number of delta-compressed versions associated with the first anchor, an age of the first anchor, and a zone stamp edit distance.

4. The method according to claim 2 , wherein the decompressed second anchor is created by

computing a reverse delta between the first anchor and the decompressed second anchor; and

delta-compressing the at least one delta-compressed version against the decompressed second anchor.

5. The method according to claim 1 , further comprising

storing the compressed second anchor at a first storage location;

receiving a new version of data, wherein the new version of data represents a version of data different from a version of data represented by at least one delta-compressed version of data in the plurality of delta-compressed versions;

decompressing the compressed second anchor at the first storage location;

creating a forward delta-compressed version representative of the differences between the decompressed second anchor and the received new version of data; and

associating the created forward delta-compressed version with the decompressed second anchor.

6. The method according to claim 5 , further comprising

storing the decompressed second anchor at a second storage location;

transmitting the created forward delta-compressed version to the second storage location; and

associating the decompressed second anchor stored at the second location with the transmitted forward delta-compressed version.

7. The method according to claim 6 , wherein the second storage location is a disaster recovery storage location.

8. The method according to claim 1 , further comprising determining that the compressed second anchor is to be deleted;

wherein the determining includes

receiving a request to delete the compressed second anchor; and

determining whether the compressed second anchor includes at least one forward delta-compressed version dependent on the compressed second anchor and marking the at least one forward delta-compressed version dependent on the compressed second anchor for deletion.

9. The method according to claim 8 , wherein the determining further comprises

determining whether the compressed second anchor includes only forward delta-compressed versions dependent on the compressed second anchor;

deleting all forward delta-compressed versions; and

deleting the compressed second anchor.

10. The method according to claim 8 , wherein the determining further comprises:

determining whether the compressed second anchor includes at least one reverse delta-compressed version dependent on the compressed second anchor, wherein the at least one reverse delta-compressed version includes at least one forward delta-compressed version dependent on the at least one delta-compressed version;

deleting all forward delta-compressed versions dependent on the at least one reverse delta-compressed version;

deleting the at least one reverse delta-compressed version after deleting all forward delta-compressed versions dependent on the at least one reverse delta-compressed version;

determining whether the compressed second anchor includes forward delta-compressed versions dependent on the compressed second anchor;

deleting all forward delta-compressed versions dependent on the compressed second anchor but not dependent on the at least one reverse delta-compressed version; and

deleting the compressed second anchor after deleting the at least one reverse delta-compressed version dependent on the second anchor and all forward delta-compressed versions dependent on the compressed second anchor.

11. The method according to claim 8 , wherein the determining further comprises:

determining whether the compressed second anchor includes at least one of the following: a forward delta-compressed version dependent on the compressed second anchor and a reverse delta-compressed version dependent on the compressed second anchor;

selecting at least one delta-compressed version as a third anchor;

re-computing at least one delta-compressed version dependent on the compressed second anchor to be dependent on the third anchor;

associating the re-computed at least one delta-compressed version with the third anchor; and

deleting the compressed second anchor.

12. The method according to claim 9 , wherein the deleting the selected anchor is delayed until all forward delta-compressed versions that are dependent on the selected anchor are deleted.

13. The method according to claim 11 , wherein the deleting of the compressed second anchor is performed immediately after the third anchor is created.

14. The method according to claim 1 , further comprising:

selecting a delta-compressed version in the plurality of versions for deletion;

determining whether the selected delta-compressed version is a forward delta version; and

deleting the selected forward delta version without deletion of the compressed second anchor and other delta-compressed versions dependent on the compressed second anchor.

15. The method according to claim 8 , wherein the determining further comprises

determining whether the compressed second anchor includes at least one forward delta-compressed version and at least one reverse delta-compressed version dependent on the compressed second anchor;

deleting the at least one forward delta-compressed versions dependent on the compressed second anchor; and

preventing deletion of the compressed second anchor until the at least one reverse delta-compressed version is deleted.

16. The method according to claim 1 , further comprising

accessing a version of data represented by a delta-compressed version of data dependent on the compressed second anchor without decompressing another delta-compressed version of data dependent on the compressed second anchor, whereby access time to the version of data is reduced.

17. The method according to claim 1 , further comprising

determining whether a delta-compressed version in the cluster is found to be unrecoverable;

wherein if the unrecoverable delta-compressed version is a forward delta-compressed version, at least another delta-compressed version in the cluster is recoverable;

wherein if the unrecoverable delta-compressed version is a reverse delta-compressed version, at least one forward delta-compressed version dependent on the unrecoverable reverse delta-compressed version is unrecoverable and at least one delta-compressed version in the cluster that is not dependent on the unrecoverable reverse delta-compressed version is recoverable.

18. The method according to claim 1 , further comprising:

determining whether to duplicate the second anchor to create a copy of the compressed second anchor;

duplicating the compressed second anchor;

wherein the determination of whether to duplicate the compressed second anchor is based on at least one of the following: size of the second cluster, a number of delta-compressed versions dependent on the compressed second anchor, a number of delta-compressed versions added to the second cluster during a predetermined period of time, and a logical grouping of the second cluster and at least another version cluster.

19. The method according to claim 18 , wherein the first anchor is stored in a first storage location and the duplicated compressed second anchor is stored in a second storage location.

20. The method according to claim 18 , further comprising

determining whether the second cluster is corrupted; and

preventing duplication of the second cluster.

21. The method according to claim 18 , wherein the duplicating further comprises

performing a checksum of the second cluster by

splitting the second cluster into a plurality of data segments;

performing a checksum of at least one data segment in the plurality of data segments;

storing checksummed data segments; and

logically aggregating the checksummed data segments into a third anchor for replacing the compressed second anchor.

22. The method according to claim 1 , further comprising

storing the cluster anchored by the compressed second anchor at a first storage location; and

storing the cluster anchored by the compressed second anchor at a second storage location without re-computing the second cluster.

23. The method according to claim 22 , wherein the second storage location is a cloud storage.

24. The method according to claim 22 , wherein the storing at the second storage location further comprises

storing metadata associated with the second cluster at the second storage location and a catalog file, wherein the stored metadata is used to update the stored second cluster at the second storage location based on an update to the stored second cluster at the first storage location and the catalog file includes at least one pointer to a metadata having a link to an actual data represented by the metadata.

25. The method according to claim 24 , wherein the update includes at least one of the following: deletion of the at least one delta-compressed version dependent on the compressed second anchor, addition of a new delta-compressed version to be dependent on the compressed second anchor, deletion of the compressed second anchor, and changing the second cluster.

26. The method according to claim 24 , wherein the metadata includes at least of the compressed second anchor and the delta-compressed versions dependent on the compressed second anchor;

wherein the stored metadata is used to recreate the compressed second anchor and the delta-compressed versions dependent on the compressed second anchor in the event of an unavailability of the first storage location.

27. The method according to claim 26 , wherein the catalog file is a most recent catalog file containing a list of all active tapefiles representing data stored at the first storage location;

wherein the most recent catalog file is referenced when recreating at least one version of data at the second storage location in the event of an unavailability of the first storage location.

28. 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 a decompressed second anchor in the plurality of anchors, wherein the decompressed second anchor includes at least another version of the data; and

replacing the first anchor with the generated decompressed second anchor,

wherein the replacing includes

decompressing the first anchor to generate a decompressed first anchor;

determining a difference between the decompressed first anchor and the generated decompressed second anchor;

compressing the generated decompressed second anchor, wherein the compressed second anchor replaces the first anchor as an anchor of the cluster.

29. The system according to claim 28 , wherein the decompressed second anchor is created based on a determination that the plurality of versions meets at least one condition.

30. The system according to claim 29 , wherein the at least one condition includes at least one of the following: a size of at least one zone in at least delta-compressed version, a number of delta-compressed versions associated with the first anchor, an age of the first anchor, and a zone stamp edit distance.

31. The system according to claim 29 , wherein the decompressed second anchor is created by

computing a reverse delta between the first anchor and the decompressed second anchor; and

delta-compressing the at least one delta-compressed version against the decompressed second anchor.

32. The system according to claim 28 , wherein the operations further comprise

storing the compressed second anchor at a first storage location;

decompressing the compressed second anchor at the first storage location;

creating a forward delta-compressed version representative of the differences between the decompressed second anchor and the received new version of data; and

associating the created forward delta-compressed version with the decompressed second anchor.

33. The system according to claim 32 , wherein the operations further comprise

storing the decompressed second anchor at a second storage location;

transmitting the created forward delta-compressed version to the second storage location; and

associating the decompressed second anchor stored at the second location with the transmitted forward delta-compressed version.

34. The system according to claim 33 , wherein the second storage location is a disaster recovery storage location.

35. The system according to claim 28 , further comprising determining that the compressed second anchor is to be deleted;

wherein the determining includes

receiving a request to delete the compressed second anchor; and

determining whether the second anchor includes at least one forward delta-compressed version dependent on the compressed second anchor and marking the at least one forward delta-compressed version dependent on the second anchor for deletion.

36. The system according to claim 35 , wherein the determining further comprises

determining whether the second anchor includes only forward delta-compressed versions dependent on the compressed second anchor;

deleting all forward delta-compressed versions; and

deleting the compressed second anchor.

37. The system according to claim 35 , wherein the determining further comprises:

deleting all forward delta-compressed versions dependent on the at least one reverse delta-compressed version;

deleting the at least one reverse delta-compressed version after deleting all forward delta-compressed versions dependent on the at least one reverse delta-compressed version;

determining whether the compressed second anchor includes forward delta-compressed versions dependent on the compressed second anchor;

deleting all forward delta-compressed versions dependent on the compressed second anchor but not dependent on the at least one reverse delta-compressed version; and

deleting the compressed second anchor after deleting the at least one reverse delta-compressed version dependent on the compressed second anchor and all forward delta-compressed versions dependent on the compressed second anchor.

38. The system according to claim 35 , wherein the determining further comprises:

selecting at least one delta-compressed version as a third anchor;

re-computing at least one delta-compressed version dependent on the compressed second anchor to be dependent on the third anchor;

associating the re-computed at least one delta-compressed version with the third anchor; and

deleting the compressed second anchor.

39. The system according to claim 36 , wherein the deleting the selected anchor is delayed until all forward delta-compressed versions that are dependent on the selected anchor are deleted.

40. The system according to claim 38 , wherein the deleting of the compressed second anchor is performed immediately after the third anchor is created.

41. The system according to claim 28 , wherein the operations further comprise

selecting a delta-compressed version in the plurality of versions for deletion;

determining whether the selected delta-compressed version is a forward delta version; and

deleting the selected forward delta version without deletion of the compressed second anchor and other delta-compressed versions dependent on the compressed second anchor.

42. The system according to claim 35 , wherein the determining further comprises

determining whether the compressed second anchor includes at least one forward delta-compressed version and at least one reverse delta-compressed version dependent on the compressed second anchor;

deleting the at least one forward delta-compressed versions dependent on the compressed second anchor; and

preventing deletion of the second anchor until the at least one reverse delta-compressed version is deleted.

43. The system according to claim 28 , wherein the operations further comprise

44. The system according to claim 28 , wherein the operations further comprise

determining whether a delta-compressed version in the cluster is found to be unrecoverable;

wherein if the unrecoverable delta-compressed version is a forward delta-compressed version, at least another delta-compressed version in the cluster is recoverable;

45. The system according to claim 28 , wherein the operations further comprise

determining whether to duplicate the compressed second anchor to create a copy of the second anchor;

duplicating the compressed second anchor;

46. The system according to claim 45 , wherein the first anchor is stored in a first storage location and the duplicated compressed second anchor is stored in a second storage location.

47. The system according to claim 45 , wherein the operations further comprise

determining whether the second cluster is corrupted; and

preventing duplication of the second cluster.

48. The system according to claim 45 , wherein the duplicating further comprises

performing a checksum of the second cluster by

splitting the second cluster into a plurality of data segments;

performing a checksum of at least one data segment in the plurality of data segments;

storing checksummed data segments; and

logically aggregating the checksummed data segments into a third anchor for replacing the compressed second anchor.

49. The system according to claim 28 , wherein the operations further comprise

storing the cluster anchored by the compressed second anchor at a first storage location; and

storing the cluster anchored by the compressed second anchor at a second storage location without re-computing the second cluster.

50. The system according to claim 49 , wherein the second storage location is a cloud storage.

51. The system according to claim 49 , wherein the storing at the second storage location further comprises

52. The system according to claim 51 , wherein the update includes at least one of the following: deletion of the at least one delta-compressed version dependent on the compressed second anchor, addition of a new delta-compressed version to be dependent on the compressed second anchor, deletion of the compressed second anchor, and changing the second cluster.

53. The system according to claim 51 , wherein the metadata includes at least of the second anchor and the delta-compressed versions dependent on the compressed second anchor;

54. The system according to claim 53 , wherein the catalog file is a most recent catalog file containing a list of all active tapefiles representing data stored at the first storage location;

wherein the most recent catalog file is referenced when recreating at least one version of data at the second storage location in the event of an unavailability of the first storage location.

55. A computer program product comprising non-transitory 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 a decompressed second anchor in the plurality of anchors, wherein the decompressed second anchor includes at least another version of the data; and

replacing the first anchor with the generated decompressed second anchor,

wherein the replacing includes

decompressing the first anchor to generate a decompressed first anchor;

determining a difference between the decompressed first anchor and the generated decompressed second anchor;

compressing the generated decompressed second anchor, wherein the compressed second anchor replaces the first anchor as an anchor of the cluster.

56. The computer program product according to claim 55 , wherein the decompressed second anchor is created based on a determination that the plurality of versions meets at least one condition.

57. The computer program product according to claim 56 , wherein the at least one condition includes at least one of the following: a size of at least one zone in at least delta-compressed version, a number of delta-compressed versions associated with the first anchor, an age of the first anchor, and a zone stamp edit distance.

58. The computer program product according to claim 56 , wherein the decompressed second anchor is created by

computing a reverse delta between the first anchor and the decompressed second anchor; and

delta-compressing the at least one delta-compressed version against the decompressed second anchor.

59. The computer program product according to claim 55 , wherein the operations further comprise

storing the compressed second anchor at a first storage location;

decompressing the compressed second anchor at the first storage location;

creating a forward delta-compressed version representative of the differences between the decompressed second anchor and the received new version of data; and

associating the created forward delta-compressed version with the decompressed second anchor.

60. The computer program product according to claim 59 , wherein the operations further comprise

storing the decompressed second anchor at a second storage location;

transmitting the created forward delta-compressed version to the second storage location; and

associating the decompressed second anchor stored at the second location with the transmitted forward delta-compressed version.

61. The computer program product according to claim 60 , wherein the second storage location is a disaster recovery storage location.

62. The computer program product according to claim 55 , further comprising determining that the compressed second anchor is to be deleted;

wherein the determining includes

receiving a request to delete the compressed second anchor; and

63. The computer program product according to claim 62 , wherein the determining further comprises

determining whether the second anchor includes only forward delta-compressed versions dependent on the compressed second anchor;

deleting all forward delta-compressed versions; and

deleting the compressed second anchor.

64. The computer program product according to claim 62 , wherein the determining further comprises:

deleting all forward delta-compressed versions dependent on the at least one reverse delta-compressed version;

deleting the at least one reverse delta-compressed version after deleting all forward delta-compressed versions dependent on the at least one reverse delta-compressed version;

determining whether the compressed second anchor includes forward delta-compressed versions dependent on the compressed second anchor;

deleting all forward delta-compressed versions dependent on the compressed second anchor but not dependent on the at least one reverse delta-compressed version; and

65. The computer program product according to claim 62 , wherein the determining further comprises:

selecting at least one delta-compressed version as a third anchor;

re-computing at least one delta-compressed version dependent on the compressed second anchor to be dependent on the third anchor;

associating the re-computed at least one delta-compressed version with the third anchor; and

deleting the compressed second anchor.

66. The computer program product according to claim 63 , wherein the deleting the selected anchor is delayed until all forward delta-compressed versions that are dependent on the selected anchor are deleted.

67. The computer program product according to claim 65 , wherein the deleting of the compressed second anchor is performed immediately after the third anchor is created.

68. The computer program product according to claim 55 , wherein the operations further comprise

selecting a delta-compressed version in the plurality of versions for deletion;

determining whether the selected delta-compressed version is a forward delta version; and

deleting the selected forward delta version without deletion of the compressed second anchor and other delta-compressed versions dependent on the compressed second anchor.

69. The computer program product according to claim 62 , wherein the determining further comprises

determining whether the compressed second anchor includes at least one forward delta-compressed version and at least one reverse delta-compressed version dependent on the compressed second anchor;

deleting the at least one forward delta-compressed versions dependent on the compressed second anchor; and

preventing deletion of the compressed second anchor until the at least one reverse delta-compressed version is deleted.

70. The computer program product according to claim 55 , wherein the operations further comprise

71. The computer program product according to claim 55 , wherein the operations further comprise

determining whether a delta-compressed version in the cluster is found to be unrecoverable;

wherein if the unrecoverable delta-compressed version is a forward delta-compressed version, at least another delta-compressed version in the cluster is recoverable;

72. The computer program product according to claim 55 , wherein the operations further comprise

determining whether to duplicate the second anchor to create a copy of the compressed second anchor;

duplicating the compressed second anchor;

73. The computer program product according to claim 72 , wherein the first anchor is stored in a first storage location and the duplicated compressed second anchor is stored in a second storage location.

74. The computer program product according to claim 72 , wherein the operations further comprise

determining whether the second cluster is corrupted; and

preventing duplication of the second cluster.

75. The computer program product according to claim 72 , wherein the duplicating further comprises

performing a checksum of the second cluster by

splitting the second cluster into a plurality of data segments;

performing a checksum of at least one data segment in the plurality of data segments;

storing checksummed data segments; and

logically aggregating the checksummed data segments into a third anchor for replacing the compressed second anchor.

76. The computer program product according to claim 55 , wherein the operations further comprise

storing the cluster anchored by the compressed second anchor at a first storage location; and

storing the cluster anchored by the compressed second anchor at a second storage location without re-computing the second cluster.

77. The computer program product according to claim 76 , wherein the second storage location is a cloud storage.

78. The computer program product according to claim 76 , wherein the storing at the second storage location further comprises

79. The computer program product according to claim 78 , wherein the update includes at least one of the following: deletion of the at least one delta-compressed version dependent on the compressed second anchor, addition of a new delta-compressed version to be dependent on the compressed second anchor, deletion of the compressed second anchor, and changing the second cluster.

80. The computer program product according to claim 78 , wherein the metadata includes at least of the compressed second anchor and the delta-compressed versions dependent on the compressed second anchor;

81. The computer program product according to claim 80 , wherein the catalog file is a most recent catalog file containing a list of all active tapefiles representing data stored at the first storage location;

wherein the most recent catalog file is referenced when recreating at least one version of data at the second storage location in the event of an unavailability of the first storage location.

Assignments (6)

RELEASE OF SECURITY INTEREST Recorded Jun 3, 2021

From: COMERICA BANK

To: EXAGRID SYSTEMS, INC.

Reel/Frame 056425/0108 →

SECURITY INTEREST Recorded May 27, 2021

From: EXAGRID SYSTEMS, INC.

To: SILICON VALLEY BANK, AS ADMINISTRATIVE AGENT

Reel/Frame 056372/0929 →

CORRECTIVE ASSIGNMENT TO CORRECT THE APPL. NOS. 10303656, 10114831, 10073855 AND 10067946 BY REMOVING THEM FOR THE PATENT NOS. PREVIOUSLY RECORDED ON REEL 049619 FRAME 0342. ASSIGNOR(S) HEREBY CONFIRMS THE SECURITY INTERESTS. Recorded Feb 9, 2021

From: EXAGRID SYSTEMS, INC.

To: ORIX GROWTH CAPITAL, LLC

Reel/Frame 056399/0163 →

SECURITY INTEREST Recorded Jun 28, 2019

From: EXAGRID SYSTEMS, INC.

To: ORIX GROWTH CAPITAL, LLC

Reel/Frame 049619/0342 →

SECURITY INTEREST Recorded Oct 1, 2018

From: EXAGRID SYSTEMS, INC.

To: COMERICA BANK

Reel/Frame 047172/0685 →

ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Aug 7, 2013

From: VANDERSPEK, ADRIAN, MS.; POIRIER, JAMEY C., MR.; MAKOSKY, LUCAS H., MR.; RAMU, ASHOK T., MR.; HECKER, MARK BENNETT, MR.; HANSEN, THOMAS G., MR.; THERRIEN, DAVID G., MR.

To: EXAGRID SYSTEMS, INC.

Reel/Frame 030961/0950 →

Continuity (2)

Provisional Application 62683791 · Aug 16, 2012

Related Publication 20140052700A1 · Feb 20, 2014

Cited By (3)

US 12,204,890 US 12,373,411 US 12,561,256