Multi-Level Deduplication

• US 20160239511A1
• Filed: 02/18/2015
• Published: 08/18/2016
• Est. Priority Date: 02/18/2015
• Status: Active Grant

• Current Assignee: ExaGrid Systems, Inc.
• Original Assignee: ExaGrid Systems, Inc.
• Inventors: Chao, Yee-ching, Martinelli, Daniel P., Smith, Stephen A., Therrien, David G., Hansen, Thomas G., Makosky, Lucas H., Hecker, Mark B., VanderSpek, Adrian
• Granted Patent: US 9,703,797 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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: G06F 16/1756 based on delta files
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries

Abstract

A method, a system, and a computer-implemented method for performing multi-level deduplication of data are disclosed. A zone stamp is generated for each zone in a plurality of zones contained in at least one data stream. The zone stamp is compared to another zone stamp. The zone stamp and another zone stamp represent zones in the plurality of zones. The comparison is performed for zones at corresponding zone levels based on a determination that a zone stamp of a zone of a preceding zone level is not similar to another zone stamp of another preceding zone level. The zone at the preceding zone level includes at least one zone of a next zone level having a size smaller than or equal to a size of the zone of the preceding zone level. The zone and another zone are deduplicated based on a determination that the zone stamp is similar to another zone stamp.

Claims

1. A computer implemented method, comprising:

generating a zone stamp for each zone in a plurality of zones contained in at least one data stream;

comparing a zone stamp to another zone stamp, the zone stamp representing a zone in the plurality of zones and the another zone stamp representing another zone in the plurality of zones, wherein the comparing is performed for zones at corresponding zone levels based on a determination that a zone stamp of a zone of a preceding zone level is not similar to another zone stamp of another preceding zone level, wherein the zone at the preceding zone level includes at least one zone of a next zone level having a size smaller than or equal to a size of the zone of the preceding zone level; and

deduplicating the zone and the another zone based on a determination that the zone stamp is similar to the another zone stamp.

2. The method according to claim 1, wherein upon determination that a zone stamp of a preceding level zone is not similar to another zone stamp of another preceding level zone, each zone stamp of a next level zone is compared another zone stamp of another next level zone, wherein both next level zones are contained within the same preceding level zone.

3. The method according to claim 1, wherein upon determination that a zone stamp of a preceding level zone is not similar to another zone stamp of another preceding level zone, each zone stamp of a next level zone is compared another zone stamp of another next level zone, wherein the next level zone and the another next level zone are contained in different preceding level zones.

4. The method according to claim 1, wherein the deduplicating further comprises

delta-compressing the zone;

and

transmitting the delta-compressed zone across a network from a storage location to another storage location.

5. The method according to claim 1, wherein upon determination that a zone stamp of a preceding level zone is not similar to any zone stamp of any other preceding level zone, further comprising

data-compressing the preceding level zone;

and

transmitting the data-compressed preceding level zone across a network from a storage location to another storage location.

6. The method according to claim 1, wherein the generating further comprises processing the at least one data stream to determine all zone levels contained within the at least one data stream;

wherein all zone levels for the at least one data stream are determined simultaneously.

7. The method according to claim 1, wherein for each zone, storing a zone entry in a table, the zone entry including

a starting location and a size of the zone,

a zone stamp identifying the zone based on the starting location and the size of the zone;

an identifier identifying location of the zone of the at least one data stream; and

a data stream identifier.

8. The method according to claim 7, wherein upon determination that a first zone stamp of a first zone is similar to a second zone stamp of a second zone,

delta-compressing the first zone;

storing the delta-compressed first zone; and

removing a first zone entry from a table corresponding to the first zone.

9. The method according to claim 7, wherein upon determination that a first zone stamp of a first zone is not similar to a zone stamp of any other zone,

data-compressing the first zone;

storing the data-compressed first zone; and

removing a first zone entry from the table corresponding to the first zone.

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

generating a container corresponding to each preceding level zone, wherein the container includes all next level zones, each next level zone being smaller than or equal to the preceding level zone;

and

searching, using a metadata associated with each zone in the container, for zones having similar zone stamps, wherein for each zone level, the metadata has a predetermined fixed size.

11. The method according to claim 1, further comprising

marking a preceding level zone for deletion;

determining whether all next level zones contained within the preceding level zone have been deleted;

deleting the preceding level zone upon determination that all next level zones contained within the preceding level zone have been deleted; and

persisting the preceding level zone upon determination that at least one next level zone in the all next level zones contained within the preceding level zone have not been marked for deletion.

12. The method according to claim 1, wherein each zone has a fixed length.

13. The method according to claim 1, wherein each zone has a variable length.

14. A system comprising:

at least one programmable processor; and

a machine-readable medium storing instructions that, when executed by the at least one programmable processor, cause the at least one programmable processor to perform operations comprising;

generating a zone stamp for each zone in a plurality of zones contained in at least one data stream;

comparing a zone stamp to another zone stamp, the zone stamp representing a zone in the plurality of zones and the another zone stamp representing another zone in the plurality of zones, wherein the comparing is performed for zones at corresponding zone levels based on a determination that a zone stamp of a zone of a preceding zone level is not similar to another zone stamp of another preceding zone level, wherein the zone at the preceding zone level includes at least one zone of a next zone level having a size smaller than or equal to a size of the zone of the preceding zone level; and

deduplicating the zone and the another zone based on a determination that the zone stamp is similar to the another zone stamp.

15. The system according to claim 14, wherein upon determination that a zone stamp of a preceding level zone is not similar to another zone stamp of another preceding level zone, each zone stamp of a next level zone is compared another zone stamp of another next level zone, wherein both next level zones are contained within the same preceding level zone.

16. The system according to claim 14, wherein upon determination that a zone stamp of a preceding level zone is not similar to another zone stamp of another preceding level zone, each zone stamp of a next level zone is compared another zone stamp of another next level zone, wherein the next level zone and the another next level zone are contained in different preceding level zones.

17. The system according to claim 14, wherein the deduplicating further comprises

delta-compressing the zone;

and

transmitting the delta-compressed zone across a network from a storage location to another storage location.

18. The system according to claim 14, wherein upon determination that a zone stamp of a preceding level zone is not similar to any zone stamp of any other preceding level zone, further comprising

data-compressing the preceding level zone;

and

transmitting the data-compressed preceding level zone across a network from a storage location to another storage location.

19. The system according to claim 14, wherein the generating further comprises processing the at least one data stream to determine all zone levels contained within the at least one data stream;

wherein all zone levels for the at least one data stream are determined simultaneously.

20. The system according to claim 14, wherein for each zone, storing a zone entry in a table, the zone entry including

a starting location and a size of the zone,

a zone stamp identifying the zone based on the starting location and the size of the zone;

an identifier identifying location of the zone of the at least one data stream; and

a data stream identifier.

21. The system according to claim 20, wherein upon determination that a first zone stamp of a first zone is similar to a second zone stamp of a second zone,

delta-compressing the first zone;

storing the delta-compressed first zone; and

removing a first zone entry from a table corresponding to the first zone.

22. The system according to claim 20, wherein upon determination that a first zone stamp of a first zone is not similar to a zone stamp of any other zone,

data-compressing the first zone;

storing the data-compressed first zone; and

removing a first zone entry from the table corresponding to the first zone.

23. The system according to claim 14, wherein the generating further comprises

generating a container corresponding to each preceding level zone, wherein the container includes all next level zones, each next level zone being smaller than or equal to the preceding level zone;

and

searching, using a metadata associated with each zone in the container, for zones having similar zone stamps, wherein for each zone level, the metadata has a predetermined fixed size.

24. The system according to claim 14, wherein the operations further comprise

marking a preceding level zone for deletion;

determining whether all next level zones contained within the preceding level zone have been deleted;

deleting the preceding level zone upon determination that all next level zones contained within the preceding level zone have been deleted; and

persisting the preceding level zone upon determination that at least one next level zone in the all next level zones contained within the preceding level zone have not been marked for deletion.

25. The system according to claim 14, wherein each zone has a fixed length.

26. The system according to claim 14, wherein each zone has a variable length.

27. A computer program product comprising a machine-readable medium storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:

generating a zone stamp for each zone in a plurality of zones contained in at least one data stream;

comparing a zone stamp to another zone stamp, the zone stamp representing a zone in the plurality of zones and the another zone stamp representing another zone in the plurality of zones, wherein the comparing is performed for zones at corresponding zone levels based on a determination that a zone stamp of a zone of a preceding zone level is not similar to another zone stamp of another preceding zone level, wherein the zone at the preceding zone level includes at least one zone of a next zone level having a size smaller than or equal to a size of the zone of the preceding zone level; and

deduplicating the zone and the another zone based on a determination that the zone stamp is similar to the another zone stamp.

28. The computer program product according to claim 27, wherein upon determination that a zone stamp of a preceding level zone is not similar to another zone stamp of another preceding level zone, each zone stamp of a next level zone is compared another zone stamp of another next level zone, wherein both next level zones are contained within the same preceding level zone.

29. The computer program product according to claim 27, wherein upon determination that a zone stamp of a preceding level zone is not similar to another zone stamp of another preceding level zone, each zone stamp of a next level zone is compared another zone stamp of another next level zone, wherein the next level zone and the another next level zone are contained in different preceding level zones.

30. The computer program product according to claim 27, wherein the deduplicating further comprises

delta-compressing the zone;

and

transmitting the delta-compressed zone across a network from a storage location to another storage location.

31. The computer program product according to claim 27, wherein upon determination that a zone stamp of a preceding level zone is not similar to any zone stamp of any other preceding level zone, further comprising

data-compressing the preceding level zone;

and

transmitting the data-compressed preceding level zone across a network from a storage location to another storage location.

32. The computer program product according to claim 27, wherein the generating further comprises

processing the at least one data stream to determine all zone levels contained within the at least one data stream;

wherein all zone levels for the at least one data stream are determined simultaneously.

33. The computer program product according to claim 27, wherein for each zone, storing a zone entry in a table, the zone entry including

a starting location and a size of the zone,

a zone stamp identifying the zone based on the starting location and the size of the zone;

an identifier identifying location of the zone of the at least one data stream; and

a data stream identifier.

34. The computer program product according to claim 33, wherein upon determination that a first zone stamp of a first zone is similar to a second zone stamp of a second zone,

delta-compressing the first zone;

storing the delta-compressed first zone; and

removing a first zone entry from a table corresponding to the first zone.

35. The computer program product according to claim 33, wherein upon determination that a first zone stamp of a first zone is not similar to a zone stamp of any other zone,

data-compressing the first zone;

storing the data-compressed first zone; and

removing a first zone entry from the table corresponding to the first zone.

36. The computer program product according to claim 27, wherein the generating further comprises

generating a container corresponding to each preceding level zone, wherein the container includes all next level zones, each next level zone being smaller than or equal to the preceding level zone;

and

searching, using a metadata associated with each zone in the container, for zones having similar zone stamps, wherein for each zone level, the metadata has a predetermined fixed size.

37. The computer program product according to claim 27, wherein the operations further comprise

marking a preceding level zone for deletion;

determining whether all next level zones contained within the preceding level zone have been deleted;

deleting the preceding level zone upon determination that all next level zones contained within the preceding level zone have been deleted; and

persisting the preceding level zone upon determination that at least one next level zone in the all next level zones contained within the preceding level zone have not been marked for deletion.

38. The computer program product according to claim 27, wherein each zone has a fixed length.

39. The computer program product according to claim 27, wherein each zone has a variable length.