Method and system for storing data

• US 20070198659A1
• Filed: 01/24/2007
• Published: 08/23/2007
• Est. Priority Date: 01/25/2006
• Status: Abandoned Application

• Current Assignee: Falconstor Software Incorporated (Hale Capital Management LP)
• Original Assignee: Falconstor Software Incorporated (Hale Capital Management LP)
• Inventors: Lam, Wai
• Application Number:
  US11/657,283
• Publication Number:
  US 20070198659A1
• Time in Patent Office: Days
• US Class Current: 709/219
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1461 Backup scheduling policy
• CPC Class Codes: G06F 16/2255 Hash tables

Abstract

In an example of an embodiment of the invention, a data set is stored in a database, at a first moment in time, at least first and second segments of data within the data set are defined, and a portion of a selected one of the at least two segments is stored in association with the database. A location of a third segment of data is identified within the data set, at a second moment in time subsequent to the first moment, based, at least in part, on the portion. In one example, a determination is made whether the selected segment has been altered between the first and second moments in time, by generating a second digest representing the third segment, and comparing the second digest to the stored digest. A digest representing the selected segment may be generated and stored in association with the portion.

Claims

1. A method of backing up data, comprising:

storing a data set in a database, at a first moment in time;

defining at least first and second segments of data within the data set;

storing, in association with the database, a portion of a selected one of the at least two segments; and

identifying a location of a third segment of data within the data set, at a second moment in time subsequent to the first moment, based, at least in part, on the portion.

2. The method of claim 1, further comprising:

determining whether the selected segment has been altered between the first and second moments in time.

3. The method of claim 2, further comprising:

generating a digest representing the selected segment; and

storing the digest in association with the portion.

4. The method of claim 3, comprising:

determining whether the selected segment has been altered by;

generating a second digest representing the third segment;

comparing the second digest to the stored digest; and

determining that the selected segment has been altered, if the second digest and the stored digest are not the same.

5. The method of claim 4, wherein the portion comprises a predetermined quantity of data selected from a corresponding segment.

6. The method of claim 5, wherein the portion comprises eight bytes of data selected from the corresponding segment.

7. The method of claim 6, wherein the eight bytes are selected from a beginning of the corresponding segment.

8. The method of claim 1, wherein the digest comprises a hash value.

9. The method of claim 8, wherein the hash value is generated using a message digest 5 algorithm.

10. The method of claim 8, wherein the hash value is generated using a secure hash algorithm.

11. The method of claim 4, further comprising:

storing, in the database, a second portion retrieved from the third segment and a digest representing the third segment;

if the selected segment has been altered.

12. The method of claim 11, further comprising:

storing, in a second database, the second portion of the third segment and the second digest representing the third segment;

if the selected segment has been altered.

13. The method of claim 12, further comprising:

storing, in the second database, an identifier of the third segment.

14. The method of claim 13, comprising:

identifying the location of the third segment within the data set, at the second moment in time subsequent to the first moment, by;

searching within the data set for the portion, starting at a beginning of the data set.

15. The method of claim 13, comprising:

identifying the location of the third segment within the data set, at the second moment in time subsequent to the first moment, by;

searching within the data set for the portion, starting at an end of the data set.

16. The method of claim 1, comprising:

identifying the location of the third segment within the data set, at the second moment in time subsequent to the first moment, by;

searching within the data set for the portion, starting at a beginning of the data set.

17. The method of claim 1, comprising:

identifying the location of the third segment within the data set, at the second moment in time subsequent to the first moment, by;

searching within the data set for the portion, starting at an end of the data set.

18. A method for backing up data, comprising:

storing a data set in a database, at a first moment in time;

defining at least two segments of data in the data set;

storing, in association with the first database, at least one digest representing a selected one of the at least two segments;

retrieving, at a second moment in time subsequent to the first moment in time, the at least one digest; and

determining whether a the selected segment has been altered since the first moment in time, based at least in part on the retrieved digest.

19. The method of claim 18, wherein the digest comprises a hash value.

20. The method of claim 19, wherein the hash value is generated using a message digest 5 algorithm.

21. The method of claim 19, wherein the hash value is generated using a secure hash algorithm.

22. The method of claim 19, comprising:

determining whether the selected segment has been altered since the first moment in time by;

identifying a second segment from the data set;

generating a second digest based on the second segment;

comparing the second digest to the first digest; and

determining that the selected segment has been altered, if the second digest and the first digest are not the same.

23. The method of claim 22, wherein the second digest comprises a second hash value.

24. The method of claim 23, wherein the second hash value is generated using a message digest 5 algorithm.

25. The method of claim 23, wherein the second hash value is generated using a secure hash algorithm.

26. The method of claim 22, further comprising:

storing the selected segment in a second database.

27. The method of claim 26, further comprising:

storing the second segment in the second database, if the selected segment has been altered.

28. The method of claim 27, comprising:

storing the selected segment in a first location in the second database; and

storing the second segment in a second location in the second database.

29. The method of claim 27, further comprising:

storing, in association with the first database, a portion representing a third segment selected from among the at least two segments; and

identifying a location of a fourth segment within the data set, at a third moment in time subsequent to the first moment in time, based on the portion.

30. The method of claim 29, comprising:

identifying the location of the fourth segment within the data set, at the third moment in time subsequent to the first moment in time, by;

searching within the data set for the portion, starting at a beginning of the data set.

31. The method of claim 29, comprising:

identifying the location of the fourth segment within the data set, at the third moment in time subsequent to the first moment in time, by;

searching within the data set for the portion, starting at an end of the data set.

32. The method of claim 29, wherein the portion comprises a predetermined quantity of data selected from a the third segment.

33. The method of claim 32, wherein the portion comprises eight bytes of data selected from the third segment.

34. The method of claim 33, wherein the eight bytes of data are selected from a beginning of the third segment.

35. A method for storing data, comprising:

storing a first version of a data file in a first database and in a second database;

defining at least two first segments within the first version;

storing a second version of the data file in the first database;

determining whether the second version contains all of the at least two first segments;

defining one or more second segments within the second version different from any of the at least two first segments, if the second version does not contain all of the at least two first segments; and

storing the one or more second segments in the second database.

36. The method of claim 35, further comprising:

defining one or more additional segments within the second version, if the second version does contain all of the at least two first segments; and

storing the one or more additional segments in the second database.

37. The method of claim 35, further comprising:

storing, in association with the first database, digests representing the respective first segments; and

determining whether the second version contains all of the at least two first segments, based, at least in part, on the digests.

38. The method of claim 37, further comprising:

storing, in association with the first database, portions of respective first segments; and

defining the one or more second segments within the second version, based, at least in part, on the portions.

39. The method of claim 38, further comprising:

storing, in association with the first database, digests representing the one or more second segments.

40. The method of claim 39, wherein the digests comprise hash values.

41. The method of claim 40, wherein the hash values are generated using a message digest 5 algorithm.

42. The method of claim 40, wherein the hash values are generated using a secure hash algorithm.

43. The method of claim 40, wherein the at least one portion comprises a predetermined quantity of data selected from a corresponding first segment.

44. The method of claim 43, wherein the at least one portion comprises eight bytes of data selected from the corresponding segment.

45. The method of claim 44, wherein the eight bytes of data are selected from a beginning of the corresponding segment.

46. A system to back up data, comprising:

a memory configured to;

store a database comprising one or more data sets; and

a processor configured to;

store a data set in the database, at a first moment in time;

define at least first and second segments of data within the data set;

store, in association with the database, a portion of a selected one of the at least two segments; and

identify a location of a third segment of data within the data set, at a second moment in time subsequent to the first moment, based, at least in part, on the portion.

47. The system of claim 46, wherein the processor is further configured to:

determine whether the selected segment has been altered between the first and second moments in time.

48. The system of claim 47, wherein the processor is further configured to:

generate a digest representing the selected segment; and

store the digest in association with the portion.

49. The system of claim 48, wherein the processor is further configured to:

determine whether the selected segment has been altered by;

generating a second digest representing the third segment;

comparing the second digest to the stored digest; and

determining that the selected segment has been altered, if the second digest and the stored digest are not the same.

50. The system of claim 49, wherein the portion comprises a predetermined quantity of data selected from a corresponding segment.

51. The system of claim 50, wherein the portion comprises eight bytes of data selected from the corresponding segment.

52. The system of claim 51, wherein the eight bytes are selected from a beginning of the corresponding segment.

53. The system of claim 46, wherein the digest comprises a hash value.

54. The system of claim 53, wherein the processor is further configured to:

generate the hash value using a message digest 5 algorithm.

55. The system of claim 53, wherein the processor is further configured to:

generate the hash value using a secure hash algorithm.

56. The system of claim 49, wherein the processor is further configured to:

store, in the database, a second portion retrieved from the third segment and a digest representing the third segment;

if the selected segment has been altered.

57. The system of claim 56, further comprising:

a second processor configured to;

store, in a second database, the second portion of the third segment and the second digest representing the third segment;

if the selected segment has been altered.

58. The system of claim 57, wherein the second processor is further configured to:

store, in the second database, an identifier of the third segment.

59. The system of claim 58, wherein the processor is further configured to:

identify the location of the third segment within the data set, at the second moment in time subsequent to the first moment, by searching within the data set for the portion, starting at a beginning of the data set.

60. The system of claim 58, wherein the processor is further configured to:

identify the location of the third segment within the data set, at the second moment in time subsequent to the first moment, by searching within the data set for the portion, starting at an end of the data set.

61. The system of claim 46, wherein the processor is further configured to:

identify the location of the third segment within the data set, at the second moment in time subsequent to the first moment, by searching within the data set for the portion, starting at a beginning of the data set.

62. The system of claim 46, wherein the processor is further configured to:

identify the location of the third segment within the data set, at the second moment in time subsequent to the first moment, by searching within the data set for the portion, starting at an end of the data set.

63. A system to back up data, comprising:

a memory configured to;

store a database comprising one or more data sets; and

a processor configured to;

store a data set in the database, at a first moment in time;

define at least two segments of data in the data set;

store, in association with the first database, at least one digest representing a selected one of the at least two segments;

retrieve, at a second moment in time subsequent to the first moment in time, the at least one digest; and

determine whether a the selected segment has been altered since the first moment in time, based at least in part on the retrieved digest.

64. The system of claim 63, wherein the digest comprises a hash value.

65. The system of claim 64, wherein the processor is configured to:

generate the hash value using a message digest 5 algorithm.

66. The system of claim 64, wherein the processor is further configured to:

generate the hash value using a secure hash algorithm.

67. The system of claim 64, wherein the processor is further configured to:

determine whether the selected segment has been altered since the first moment in time by;

identifying a second segment from the data set;

generating a second digest based on the second segment;

comparing the second digest to the first digest; and

determining that the selected segment has been altered, if the second digest and the first digest are not the same.

68. The system of claim 67, wherein the second digest comprises a second hash value.

69. The system of claim 68, wherein the processor is further configured to:

generate the second hash value using a message digest 5 algorithm.

70. The system of claim 68, wherein the processor is further configured to:

generate the second hash value using a secure hash algorithm.

71. The system of claim 67, further comprising a second processor configured to:

store the selected segment in a second database.

72. The system of claim 71, wherein the second processor is further configured to:

store the second segment in the second database, if the selected segment has been altered.

73. The system of claim 72, wherein the second processor is further configured to:

store the selected segment in a first location in the second database; and

store the second segment in a second location in the second database.

74. The system of claim 72, wherein the processor is further configured to:

store, in association with the first database, a portion representing a third segment selected from among the at least two segments; and

identify a location of a fourth segment within the data set, at a third moment in time subsequent to the first moment in time, based on the portion.

75. The system of claim 74, wherein the processor is further configured to:

identify the location of the fourth segment within the data set, at the third moment in time subsequent to the first moment in time, by searching within the data set for the portion, starting at a beginning of the data set.

76. The system of claim 74, wherein the processor is further configured to:

identify the location of the fourth segment within the data set, at the third moment in time subsequent to the first moment in time, by searching within the data set for the portion, starting at an end of the data set.

77. The system of claim 74, wherein the portion comprises a predetermined quantity of data selected from a the third segment.

78. The system of claim 77, wherein the portion comprises eight bytes of data selected from the third segment.

79. The system of claim 78, wherein the eight bytes of data are selected from a beginning of the third segment.

80. A system to store data, comprising:

a memory configured to;

store a database comprising one or more data sets;

a first processor configured to;

store a first version of a data file in a first database; and

a second processor configured to;

store the first version of the data set in a second database;

wherein the first processor is further configured to;

define at least two first segments within the first version;

store a second version of the data file in the first database;

determine whether the second version contains all of the at least two first segments; and

define one or more second segments within the second version different from any of the at least two first segments, if the second version does not contain all of the at least two first segments; and

wherein the second processor is further configured to;

store the one or more second segments in the second database.

81. The system of claim 80, wherein the first processor is further configured to:

define one or more additional segments within the second version, if the second version does contain all of the at least two first segments; and

wherein the second processor is further configured to;

store the one or more additional segments in the second database.

82. The system of claim 80, wherein the first processor is further configured to:

store, in association with the first database, digests representing the respective first segments; and

determine whether the second version contains all of the at least two first segments, based, at least in part, on the digests.

83. The system of claim 82, wherein the first processor is further configured to:

store, in association with the first database, portions of respective first segments; and

define the one or more second segments within the second version, based, at least in part, on the portions.

84. The system of claim 83, wherein the first processor is further configured to:

store, in association with the first database, digests representing the one or more second segments.

85. The system of claim 84, wherein the digests comprise hash values.

86. The system of claim 85, wherein the first processor is further configured to:

generate the hash values using a message digest 5 algorithm.

87. The system of claim 85, wherein the first processor is further configured to:

generate the hash values using a secure hash algorithm.

88. The system of claim 85, wherein the at least one portion comprises a predetermined quantity of data selected from a corresponding first segment.

89. The system of claim 88, wherein the at least one portion comprises eight bytes of data selected from the corresponding segment.

90. The system of claim 89, wherein the eight bytes of data are selected from a beginning of the corresponding segment.