Next-Level Multi-Level Deduplication

• US 20170212907A1
• Filed: 04/07/2017
• Published: 07/27/2017
• Est. Priority Date: 02/18/2015
• Status: Active Grant

• Current Assignee: ExaGrid Systems, Inc.
• Original Assignee: ExaGrid Systems, Inc.
• Inventors: VanderSpek, Adrian T., Martinelli, Daniel P., Therrien, David G.
• Granted Patent: US 10,067,946 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• 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 program product for performing next level multi-level deduplication. A first zone stamp for a first data zone is generated and compared to a second zone stamp representing a second data zone, where the zones are first level data zones. The first and second data zones are deduplicated when the first zone stamp matches the second zone stamp. A second-level first zone stamp is selected when there is no match between first and second zone stamps. The second-level first zone stamp, representing a second-level first data zone in the first data zone, is compared to the second zone stamp and/or a second-level second zone stamp representing a second-level second data zone. The second-level first zone and one of the second data zone and the second-level second zone are deduplicated when the second-level first zone stamp matches one of the second zone stamp and the second-level second zone stamp.

Claims

1. A computer implemented method, comprising:

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

comparing the first zone stamp to a second zone stamp, wherein the second zone stamp represents a second data zone, wherein the first and second data zones are first level data zones, and deduplicating the first data zone and the second data zone upon determination that the first zone stamp matches the second zone stamp;

selecting a second-level first zone stamp upon determination that the first zone stamp does not match the second zone stamp, wherein the second-level first zone stamp represents a second-level first data zone contained with the first data zone; and

comparing the second-level first zone stamp to at least one of the second zone stamp and a second-level second zone stamp, wherein the second-level second zone stamp represents a second-level second data zone, and deduplicating the second-level first zone and at least one of the second data zone and the second-level second zone based on a determination that the second-level first zone stamp matches at least one of the second zone stamp and the second-level second zone stamp.

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

delta-compressing a zone in the plurality of zones;

and

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

3. The method according to claim 1, wherein upon determination that a zone stamp of a zone does not match any other zone stamp, further comprising

data-compressing the zone;

and

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

4. 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.

5. 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.

6. The method according to claim 1, wherein upon determination that the first zone stamp matches the second zone stamp,

delta-compressing the first zone;

and

storing the delta-compressed first zone.

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

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

9. A system comprising:

at least one programmable processor; and

a non-transitory 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 first zone stamp for a first data zone in a plurality of data zones contained in at least one data stream;

comparing the first zone stamp to a second zone stamp, wherein the second zone stamp represents a second data zone, wherein the first and second data zones are first level data zones, and deduplicating the first data zone and the second data zone upon determination that the first zone stamp matches the second zone stamp;

selecting a second-level first zone stamp upon determination that the first zone stamp does not match the second zone stamp, wherein the second-level first zone stamp represents a second-level first data zone contained with the first data zone; and

comparing the second-level first zone stamp to at least one of the second zone stamp and a second-level second zone stamp, wherein the second-level second zone stamp represents a second-level second data zone, and deduplicating the second-level first zone and at least one of the second data zone and the second-level second zone based on a determination that the second-level first zone stamp matches at least one of the second zone stamp and the second-level second zone stamp.

10. The system according to claim 9, wherein the deduplicating further comprises

delta-compressing a zone in the plurality of zones;

and

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

11. The system according to claim 9, wherein upon determination that a zone stamp of a zone does not match any other zone stamp, further comprising

data-compressing the zone;

and

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

12. The system according to claim 9, 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.

13. The system according to claim 9, 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.

14. The system according to claim 9, wherein upon determination that the first zone stamp matches the second zone stamp,

delta-compressing the first zone;

and

storing the delta-compressed first zone.

15. The system according to claim 9, wherein each zone has a fixed length.

16. The system according to claim 9, wherein each zone has a variable length.

17. A computer program product comprising a non-transitory 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 first zone stamp for a first data zone in a plurality of data zones contained in at least one data stream;

comparing the first zone stamp to a second zone stamp, wherein the second zone stamp represents a second data zone, wherein the first and second data zones are first level data zones, and deduplicating the first data zone and the second data zone upon determination that the first zone stamp matches the second zone stamp;

selecting a second-level first zone stamp upon determination that the first zone stamp does not match the second zone stamp, wherein the second-level first zone stamp represents a second-level first data zone contained with the first data zone; and

comparing the second-level first zone stamp to at least one of the second zone stamp and a second-level second zone stamp, wherein the second-level second zone stamp represents a second-level second data zone, and deduplicating the second-level first zone and at least one of the second data zone and the second-level second zone based on a determination that the second-level first zone stamp matches at least one of the second zone stamp and the second-level second zone stamp.

18. The computer program product according to claim 17, wherein the deduplicating further comprises

delta-compressing a zone in the plurality of zones;

and

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

19. The computer program product according to claim 17, wherein upon determination that a zone stamp of a zone does not match any other zone stamp, further comprising

data-compressing the zone;

and

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

20. The computer program product according to claim 17, 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.

21. The computer program product according to claim 17, 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.

22. The computer program product according to claim 17, wherein upon determination that the first zone stamp matches the second zone stamp,

delta-compressing the first zone;

and

storing the delta-compressed first zone.

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

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