Method and apparatus for content-aware and adaptive deduplication

• US 8,412,848 B2
• Filed: 05/29/2009
• Issued: 04/02/2013
• Est. Priority Date: 05/29/2009
• Status: Active Grant

• Current Assignee: ExaGrid Systems, Inc.
• Original Assignee: ExaGrid Systems, Inc.
• Inventors: Therrien, David G., Thompson, David Andrew
• Primary Examiner(s): Whipple, Brian P
• Assistant Examiner(s): COX, NATISHA D
• Application Number:
  US12/455,281
• Publication Number:
  US 20100306412A1
• Time in Patent Office: 1,404 Days
• Field of Search: 709/247, 709/231
• US Class Current: 709/247
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A method, a system, an apparatus, and a computer readable medium for transmission of data across a network are disclosed. The method includes receiving a data stream, analyzing the received data stream to determine a starting location and an ending location of each zone within the received data stream, based on the starting and ending locations, generating a zone stamp identifying the zone, the zone stamp includes a sequence of contiguous characters representing at least a portion of data in the zone, wherein the order of characters in the zone stamp corresponds to the order of data in the zone, comparing the zone stamp with another zone stamp of another zone in any data stream received, determining whether the zone is substantially similar to another zone by detecting that the zone stamp is substantially similar to another zone stamp, delta-compressing zones within any data stream received that have been determined to have substantially similar zone stamps, thereby deduplicating zones having substantially similar zone stamps within any data stream received, and transmitting the deduplicated zones across the network from one storage location to another storage location.

Claims

1. A method for transmission of data across a network, comprising the steps of:

receiving a data stream comprising a plurality of zones;

analyzing the received data stream to determine a starting location and an ending location of each zone within the received data stream;

based on the starting and ending locations, generating a zone stamp identifying the zone, the zone stamp includes a sequence of contiguous characters representing of at least a portion of data in the zone, wherein the order of characters in the zone stamp corresponds to the order of data in the zone, wherein said zone stamp is configured to have a length between a predetermined minimum zone stamp length and a predetermined maximum zone stamp length;

comparing the zone stamp with another zone stamp of another zone in any data stream received;

determining whether the zone is substantially similar to another zone by detecting that the zone stamp is substantially similar to another zone stamp;

delta-compressing zones within any data stream received that have been determined to have substantially similar zone stamps, thereby deduplicating zones having substantially similar zone stamps within the received data stream;

transmitting the deduplicated zones across the network from one storage location to another storage location;

wherein each zone in any data stream received is characterized by a predetermined minimum and maximum zone size and a predetermined minimum and maximum zone stamp length;

wherein zones that are to be delta-compressed have a size greater than the predetermined minimum zone size and less than the predetermined maximum size and a stamp length greater than the predetermined minimum zone stamp length.

2. The method according to claim 1, further comprising storing the zone stamp in a zone database, wherein the zone database is configured to store zone stamps of the zones within any data stream received.

3. The method according to claim 1, wherein said delta-compressing step further comprising eliminating redundant data from any data stream received.

4. The method according to claim 1, wherein said analyzing step further comprises

defining an end zone located at an end of the received data stream.

5. The method according to claim 4, wherein said generating a zone stamp step further comprises aggregating the defined end zone with a zone preceding the defined end zone for delta-compressing, when size of the defined end zone is less than the predetermined minimum zone size.

6. The method according to claim 4, wherein said generating a zone stamp step further comprises aggregating the defined end zone with a zone preceding the defined end zone for delta-compressing, when a total combined length of zone stamps for the defined end zone and a zone preceding the defined zone is less than the predetermined maximum zone stamp length.

7. The method according to claim 4, wherein said generating a zone stamp step further comprises creating a separate end zone stamp for the defined end zone for delta-compressing, when size of the defined end zone is greater than the predetermined minimum zone size and the predetermined minimum zone stamp length.

8. The method according to claim 6, wherein the zone stamp of the preceding zone remains unchanged.

9. The method according to claim 1, wherein the zone stamp has a fixed length.

10. The method according to claim 1, wherein the zone stamp has a variable length.

11. The method according to claim 1, wherein the zone is a low entropy data zone, wherein the low entropy data zone includes homogeneous data within any data stream received.

12. The method according to claim 1, wherein said comparing step further comprises

comparing zone stamps of zones having a difference in respective zone sizes that is less than or equal to a predetermined zone size difference;

wherein zones having a difference in respective zone sizes that is greater than the predetermined zone size difference are not compared to each other.

13. The method according to claim 12, further comprising upon determining that compared zones are substantially similar to one another, discontinuing comparison of at least one compared zone to other zones in any data stream received.

14. The method according to claim 13, wherein said determining step further comprises computing an edit distance score between the compared zone stamps, wherein the edit distance score is configured to reflect the number of differences between the compared zone stamps, wherein each compared zone stamp is limited by a predetermined maximum zone stamp length.

15. The method according to claim 14, wherein said determining step further comprises

comparing the computed edit distance score to a predetermined threshold distance score;

and,

determining that the compared zones are substantially similar when the computed edit distance score is less than the predetermined threshold distance score.

16. The method according to claim 15, wherein the computed edit distance score closer to zero indicates that the compared zones are substantially similar.

17. The method according to claim 16, wherein the predetermined threshold distance score is a function of a length of a shorter zone stamp of the zone stamps being compared.

18. The method according to claim 15, wherein said determining whether the zone is substantially similar to another zone step further comprises

upon comparison of zone stamps of zones, selecting a best match between a pair of zones in any data stream received for comparison with other zones in any data stream received.

42. The method according to claim 11, further comprising data compressing the low entropy data zone.

44. The method according to claim 1, wherein the zone stamp is configured to contain a predetermined number of repeating characters.

45. The method according to claim 44, wherein the zone is a low entropy data zone when the zone stamp of the zone contains a number of repeating characters that are configured to exceed the predetermined number of repeating characters.

48. The method according to claim 1, wherein the predetermined maximum size of the zone stamp length is sixty four characters.

50. The method according to claim 1, wherein the generating further comprises

generating the zone stamp identifying the zone while performing the analyzing the received data stream to determine the starting location and the ending location of the zone.

52. The method according to claim 1, wherein the comparing further comprises

comparing zone stamp of the zone and another zone stamp of another zone, wherein the zone is a most recent version of data and the another zone is a most recent version of another data.

54. The method according to claim 1, wherein the comparing step further comprises

comparing zone stamps of zones, wherein the compared zone stamps have substantially similar lengths.

19. A system for transmission of data across a network, comprising:

a processor coupled to a storage system;

said processor is configured to receive a data stream comprising a plurality of zones;

analyze the received data stream to determine a starting location and an ending location of each zone within the received data stream;

based on the starting and ending locations, generate a zone stamp identifying the zone, the zone stamp includes a sequence of contiguous characters representing at least a portion of data in the zone, wherein the order of characters in the zone stamp corresponds to the order of data in the zone, wherein said zone stamp is configured to have a length between a predetermined minimum zone stamp length and a predetermined maximum zone stamp length;

compare the zone stamp with another zone stamp of another zone in any data stream received;

determine whether the zone is substantially similar to another zone by detecting that the zone stamp is substantially similar to another zone stamp;

delta-compress zones within any data stream received that have been determined to have substantially similar zone stamps, thereby deduplicating zones having substantially similar zone stamps within any data stream received;

transmit the deduplicated zones across the network from one storage location to another storage location in the storage system;

wherein each zone in any data stream received is characterized by a predetermined minimum and maximum zone size and a predetermined minimum and maximum zone stamp length;

wherein zones that are to be delta-compressed have a size greater than the predetermined minimum zone size and less than the predetermined maximum size and a stamp length greater than the predetermined minimum zone stamp length.

20. The system according to claim 19, wherein said storage system is configured to store the zone stamp in a zone database, wherein the zone database is configured to store zone stamps of the zones within any data stream received.

21. The system according to claim 19, wherein during delta-compressing said processor is configured to eliminate redundant data from any data stream received.

22. The system according to claim 19, wherein during analyzing said processor is configured to

define an end zone located at an end of any data stream.

23. The system according to claim 19, wherein during generation of zone stamps said processor is configured to aggregate the defined end zone with a zone preceding the defined end zone for delta-compressing, when size of the defined end zone is less than the predetermined minimum zone size.

24. The system according to claim 19, wherein during generation of zone stamps said processor is configured to aggregate the defined end zone with a zone preceding the defined end zone for delta-compressing, when a total combined length of zone stamps for the defined end zone and a zone preceding the defined zone is less than the predetermined maximum zone stamp length.

25. The system according to claim 19, wherein during generation of zone stamps said processor is configured to create a separate end zone stamp for the defined end zone for delta-compressing, when size of the defined end zone is greater than the predetermined minimum zone size and the predetermined minimum zone stamp length.

26. The system according to claim 24, wherein the zone stamp of the preceding zone remains unchanged.

27. The system according to claim 19, wherein the zone stamp has a fixed length.

28. The system according to claim 19, wherein the zone stamp has a variable length.

29. The system according to claim 19, wherein the zone is a low entropy data zone, wherein the low entropy data zone includes homogeneous data within any data stream received.

30. The system according to claim 19, wherein during comparing said processor is configured to

compare zone stamps of zones having a difference in respective zone sizes that is less than or equal to a predetermined zone size difference;

wherein zones having a difference in respective zone sizes that is greater than the predetermined zone size difference are not compared to each other.

31. The system according to claim 30, wherein upon determining that compared zones are substantially similar to one another, said processor is configured to discontinue comparison of at least one compared zone to other zones in any data stream received.

32. The system according to claim 31, wherein during determining said processor is configured to compute an edit distance score between the compared zone stamps, wherein the edit distance score is configured to reflect the number of differences between the compared zone stamps, wherein each compared zone stamp is limited by a predetermined maximum zone stamp length.

33. The system according to claim 32, wherein during determining said processor is configured to

compare the computed edit distance score to a predetermined threshold distance score;

and,

determine that the compared zones are substantially similar when the computed edit distance score is less than the predetermined threshold distance score.

34. The system according to claim 33, wherein the computed edit distance score closer to zero indicates that the compared zones are substantially similar.

35. The system according to claim 33, wherein the predetermined threshold distance score is a function of a length of a shorter zone stamp of the zone stamps being compared.

36. The system according to claim 33, wherein said processor is further configured to

upon comparison of zone stamps of zones, select a best match between a pair of zones in the received data stream for comparison with other zones in any data stream received.

43. The system according to claim 29, wherein the processor is further configured to

data compress the low entropy data zone.

46. The system according to 19, wherein the zone stamp is configured to contain a predetermined number of repeating characters.

47. The system according to claim 46, wherein the zone is a low entropy data zone when the zone stamp of the zone contains a number of repeating characters that are configured to exceed the predetermined number of repeating characters.

49. The system according to claim 19, wherein the predetermined maximum size of the zone stamp length is sixty four characters.

51. The system according to claim 19, wherein the generating further comprises

generating the zone stamp identifying the zone while performing the analyzing the received data stream to determine the starting location and the ending location of the zone.

53. The system according to claim 19, wherein the comparing further comprises

comparing zone stamp of the zone and another zone stamp of another zone, wherein the zone is a most recent version of data and the another zone is a most recent version of another data.

55. The system according to claim 19, wherein the comparing further comprises

comparing zone stamps of zones, wherein the compared zone stamps have substantially similar lengths.

37. A method for deduplicating of data across a network, comprising the steps of:

receiving a data stream comprising a plurality of zones;

analyzing the received data stream to determine a starting location and an ending location of each zone within the received data stream;

based on the starting and ending locations, generating a zone stamp identifying the zone, the zone stamp includes a sequence of contiguous characters representing at least a portion of data in the zone, wherein the order of characters in the zone stamp corresponds to the order of data in the zone, wherein said zone stamp is configured to have a length between a predetermined minimum zone stamp length and a predetermined maximum zone stamp length;

comparing the zone stamp with another zone stamp of another zone in any data stream received;

determining whether the zone is substantially similar to another zone by detecting that the zone stamp is substantially similar to another zone stamp; and

delta-compressing zones within any data stream received that have been determined to have substantially similar zone stamps, thereby deduplicating zones having substantially similar zone stamps within any data stream received;

wherein each zone in any data stream received is characterized by a predetermined minimum and maximum zone size and a predetermined minimum and maximum zone stamp length;

wherein zones that are to be delta-compressed have a size greater than the predetermined minimum zone size and less than the predetermined maximum size and a stamp length greater than the predetermined minimum zone stamp length.

38. A non-transitory computer-readable medium encoded with computer program instructions for performing method for transmitting data across a network, comprising the steps of:

receiving a data stream comprising a plurality of zones;

analyzing the received data stream to determine a starting location and an ending location of each zone within the received data stream;

based on the starting and ending locations, generating a zone stamp identifying the zone, the zone stamp includes a sequence of contiguous characters representing at least a portion of data in the zone, wherein the order of characters in the zone stamp corresponds to the order of data in the zone, wherein said zone stamp is configured to have a length between a predetermined minimum zone stamp length and a predetermined maximum zone stamp length;

comparing the zone stamp with another zone stamp of another zone in any data stream received;

determining whether the zone is substantially similar to another zone by detecting that the zone stamp is substantially similar to another zone stamp;

delta-compressing zones within any data stream received that have been determined to have substantially similar zone stamps, thereby deduplicating zones having substantially similar zone stamps within any data stream received;

transmitting the deduplicated zones across the network from one storage location to another storage location;

wherein each zone in any data stream received is characterized by a predetermined minimum and maximum zone size and a predetermined minimum and maximum zone stamp length

wherein zones that are to be delta-compressed have a size greater than the predetermined minimum zone size and less than the predetermined maximum size and a stamp length greater than the predetermined minimum zone stamp length.

56. The computer-readable medium according to claim 38, further comprising instructions for

storing the zone stamp in a zone database, wherein the zone database is configured to store zone stamps of the zones within any data stream received.

57. The computer-readable medium according to claim 38, wherein said delta-compressing further comprising eliminating redundant data from any data stream received.

58. The computer-readable medium according to claim 38, wherein said analyzing further comprises

defining an end zone located at an end of the received data stream.

59. The computer-readable medium according to claim 58, wherein said generating a zone stamp further comprises aggregating the defined end zone with a zone preceding the defined end zone for delta-compressing, when size of the defined end zone is less than the predetermined minimum zone size.

60. The computer-readable medium according to claim 58, wherein said generating a zone stamp further comprises aggregating the defined end zone with a zone preceding the defined end zone for delta-compressing, when a total combined length of zone stamps for the defined end zone and a zone preceding the defined zone is less than the predetermined maximum zone stamp length.

61. The computer-readable medium according to claim 58, wherein said generating a zone stamp further comprises creating a separate end zone stamp for the defined end zone for delta-compressing, when size of the defined end zone is greater than the predetermined minimum zone size and the predetermined minimum zone stamp length.

62. The computer-readable medium according to claim 60, wherein the zone stamp of the preceding zone remains unchanged.

63. The computer-readable medium according to claim 38, wherein the zone stamp has a fixed length.

64. The computer-readable medium according to claim 38, wherein the zone stamp has a variable length.

65. The computer-readable medium according to claim 38, wherein the zone is a low entropy data zone, wherein the low entropy data zone includes homogeneous data within any data stream received.

66. The computer-readable medium according to claim 38, wherein said comparing further comprises

comparing zone stamps of zones having a difference in respective zone sizes that is less than or equal to a predetermined zone size difference;

wherein zones having a difference in respective zone sizes that is greater than the predetermined zone size difference are not compared to each other.

67. The computer-readable medium according to claim 66, further comprising instructions for

upon determining that compared zones are substantially similar to one another, discontinuing comparison of at least one compared zone to other zones in any data stream received.

68. The computer-readable medium according to claim 67, wherein said determining further comprises computing an edit distance score between the compared zone stamps, wherein the edit distance score is configured to reflect the number of differences between the compared zone stamps, wherein each compared zone stamp is limited by a predetermined maximum zone stamp length.

69. The computer-readable medium according to claim 68, wherein said determining further comprises

comparing the computed edit distance score to a predetermined threshold distance score;

and,

determining that the compared zones are substantially similar when the computed edit distance score is less than the predetermined threshold distance score.

70. The computer-readable medium according to claim 69, wherein the computed edit distance score closer to zero indicates that the compared zones are substantially similar.

71. The computer-readable medium according to claim 69, wherein the predetermined threshold distance score is a function of a length of a shorter zone stamp of the zone stamps being compared.

72. The computer-readable medium according to claim 69, wherein said determining whether the zone is substantially similar to another zone step further comprises

upon comparison of zone stamps of zones, selecting a best match between a pair of zones in any data stream received for comparison with other zones in any data stream received.

73. The computer-readable medium according to claim 65, further comprising instructions for

data compressing the low entropy data zone.

74. The computer-readable medium according to claim 38, wherein the zone stamp is configured to contain a predetermined number of repeating characters.

75. The computer-readable medium according to claim 74, wherein the zone is a low entropy data zone when the zone stamp of the zone contains a number of repeating characters that are configured to exceed the predetermined number of repeating characters.

76. The computer-readable medium according to claim 38, wherein the predetermined maximum size of the zone stamp length is sixty four characters.

77. The computer-readable medium according to claim 38, wherein the generating further comprises

generating the zone stamp identifying the zone while performing the analyzing the received data stream to determine the starting location and the ending location of the zone.

78. The computer-readable medium according to claim 38, wherein the comparing further comprises

comparing zone stamp of the zone and another zone stamp of another zone, wherein the zone is a most recent version of data and the another zone is a most recent version of another data.

79. The computer-readable medium according to claim 38, wherein the comparing further comprises

comparing zone stamps of zones, wherein the compared zone stamps have substantially similar lengths.

39. A system for storing and transmitting data, comprising

a processor communicating with a storage location, wherein said processor is configured to receive a data stream comprising a plurality of zones from a plurality of sources;

said processor is configured to

analyze the received data stream to determine a starting location and an ending location of each zone within the received data stream;

based on the starting and ending locations, generate a zone stamp identifying the zone, the zone stamp includes a sequence of contiguous characters representing a portion of data in the zone, wherein the order of characters in the zone stamp corresponds to the order of data in the zone, wherein said zone stamp is configured to have a length between a predetermined minimum zone stamp length and a predetermined maximum zone stamp length;

compare the zone stamp with another zone stamp of another zone in any data stream received;

determine whether the zone is substantially similar to another zone by detecting that the zone stamp is substantially similar to another zone stamp;

delta-compress zones within any data stream received that have been determined to have substantially similar zone stamps, thereby deduplicating zones having substantially similar zone stamps within the received data stream;

transmit the deduplicated zones to the storage device for storage;

wherein each zone in any data stream received is characterized by a predetermined minimum and maximum zone size and a predetermined minimum and maximum zone stamp length;

wherein zones that are to be delta-compressed have a size greater than the predetermined minimum zone size and less than the predetermined maximum size and a stamp length greater than the predetermined minimum zone stamp length.

40. The system according to claim 39, wherein the plurality of sources is selected from a group consisting of:

an archive location, a database, an email server, a fileserver, a backup server, a document management server, and a replication server, wherein each said source is configured to communicate with said processor.

41. The system according to claim 39, wherein said processor is configured to transmit deduplicated zones via a deduplication processor to at least one or both of a local storage location and a remote storage location.