Scalable Grid Deduplication

• US 20160253351A1
• Filed: 02/27/2015
• Published: 09/01/2016
• Est. Priority Date: 02/27/2015
• Status: Active Grant

• Current Assignee: ExaGrid Systems, Inc.
• Original Assignee: ExaGrid Systems, Inc.
• Inventors: VanderSpek, Adrian T., Hansen, Thomas G., Martinelli, Daniel P., Makosky, Lucas H., Hecker, Mark B., Smith, Stephen A., Therrien, David G.
• Granted Patent: US 10,387,374 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 11/1464 for networked environments
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/1756 based on delta files
• 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]
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC

Abstract

A system, a method, and a computer program product for performing deduplication of data using a scalable deduplication grid are disclosed. A listing of a plurality of zone stamps is generated, where each zone stamp represents a zone in the plurality of zones in a data stream. The listing contains a logical arrangement of the plurality of zone stamps obtained from each storage location and being accessible by a plurality of servers. A first zone stamp in the listing is compared to a second zone stamp in the listing. The first and second zones are delta-compressed based on a determination that the first zone stamp is substantially similar to the second zone stamp. A server is selected to perform the comparison and delta-compression.

Claims

1. A computer implemented method, comprising

generating a listing of a plurality of zone stamps, each zone stamp representing a zone in the plurality of zones in a data stream, the generated listing containing a logical arrangement of the plurality of zone stamps obtained from each storage location and being accessible by a plurality of servers;

comparing a first zone stamp in the plurality of zone stamps contained in the generated listing to a second zone stamp in the plurality of zone stamps contained in the generated listing, the first zone stamp representing a first zone in the plurality of zones and the second zone stamp representing a second zone in the plurality of zones;

delta-compressing the first zone and the second zone based on a determination that the first zone stamp is substantially similar to the second zone stamp; and

selecting, based on the generated listing, a server in the plurality of servers to perform the comparing and the delta-compressing.

2. The method according to claim 1, further comprising deleting at least one of the first zone stamp and the second zone stamp from the generated listing.

3. The method according to claim 2, wherein the deleted at least one first zone stamp and the second zone stamp represent at least one zone purged from the plurality of zones.

4. The method according to claim 1, wherein the logical arrangement of the plurality of zone stamps is based on at least one of the following:

a processing capability of each server in the plurality of servers, a size of each zone in the plurality of zones, a time consumed by the comparing, and availability of each server in the plurality of servers.

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

comparing the first zone stamp and the second zone stamp based on the first zone and the second zone having at least one of the following:

same starting characters and same ending characters.

6. The method according to claim 1, wherein the delta-compressing further comprises

delta-compressing the first zone and the second zone at at least one of the following:

a first server in the plurality of servers storing the first zone and a second server in the plurality of servers storing the second zone.

7. The method according to claim 1, wherein the delta-compressing further comprises

determining that a portion of the first zone is stored on a first server in the plurality of servers and another portion of the first zone is stored on a second server in the plurality of servers;

and

delta-compressing the first zone using the first server or the second server.

8. The method according to claim 1, wherein the selecting further comprises

determining that a portion of the first zone is stored on a first server in the plurality of servers and another portion of the first zone is stored on a second server in the plurality of servers;

and

selecting, based on the determining, the first server or the second server to perform the comparing and the delta-compressing.

9. The method according to claim 1, further comprising

storing a delta-compressed zone at a server in a plurality of servers that received the un-delta-compressed zone in the data stream.

10. The method according to claim 1, further comprising

deduplicating, based on delta-compressing, the first zone and the second zone.

11. The method according to claim 1, wherein each delta-compressed zone is associated with an anchor, wherein a plurality of delta-compressed zones are dependent on the anchor, the delta-compressed zone is stored at a server in the plurality of servers storing the anchor.

12. The method according to claim 11, wherein the selecting further comprises

selecting a server in the plurality of servers to perform the comparing and the delta-compressing, the selected server storing the anchor.

13. The method according to claim 1, further comprising

removing a zone stamp from the generated listing, wherein the zone stamp represents an anchor delta-compressed zone having at least one dependent delta-compressed zone.

14. The method according to claim 1, further comprising

performing at least one of the comparing, the delta-compressing, and the selecting by the plurality of servers in parallel.

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

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

17. 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 listing of a plurality of zone stamps, each zone stamp representing a zone in the plurality of zones in a data stream, the generated listing containing a logical arrangement of the plurality of zone stamps obtained from each storage location and being accessible by a plurality of servers;

comparing a first zone stamp in the plurality of zone stamps contained in the generated listing to a second zone stamp in the plurality of zone stamps contained in the generated listing, the first zone stamp representing a first zone in the plurality of zones and the second zone stamp representing a second zone in the plurality of zones;

delta-compressing the first zone and the second zone based on a determination that the first zone stamp is substantially similar to the second zone stamp; and

selecting, based on the generated listing, a server in the plurality of servers to perform the comparing and the delta-compressing.

18. The system according to claim 17, wherein the operations further comprise deleting at least one of the first zone stamp and the second zone stamp from the generated listing.

19. The system according to claim 18, wherein the deleted at least one first zone stamp and the second zone stamp represent at least one zone purged from the plurality of zones.

20. The system according to claim 17, wherein the logical arrangement of the plurality of zone stamps is based on at least one of the following:

a processing capability of each server in the plurality of servers, a size of each zone in the plurality of zones, a time consumed by the comparing, and availability of each server in the plurality of servers.

21. The system according to claim 17, wherein the comparing further comprises

comparing the first zone stamp and the second zone stamp based on the first zone and the second zone having at least one of the following:

same starting characters and same ending characters.

22. The system according to claim 17, wherein the delta-compressing further comprises

delta-compressing the first zone and the second zone at at least one of the following:

a first server in the plurality of servers storing the first zone and a second server in the plurality of servers storing the second zone.

23. The system according to claim 17, wherein the delta-compressing further comprises

determining that a portion of the first zone is stored on a first server in the plurality of servers and another portion of the first zone is stored on a second server in the plurality of servers;

and

delta-compressing the first zone using the first server or the second server.

24. The system according to claim 17, wherein the selecting further comprises

determining that a portion of the first zone is stored on a first server in the plurality of servers and another portion of the first zone is stored on a second server in the plurality of servers;

and

selecting, based on the determining, the first server or the second server to perform the comparing and the delta-compressing.

25. The system according to claim 17, wherein the operations further comprise

storing a delta-compressed zone at a server in a plurality of servers that received the un-delta-compressed zone in the data stream.

26. The system according to claim 17, wherein the operations further comprise

deduplicating, based on delta-compressing, the first zone and the second zone.

27. The system according to claim 17, wherein each delta-compressed zone is associated with an anchor, wherein a plurality of delta-compressed zones are dependent on the anchor, the delta-compressed zone is stored at a server in the plurality of servers storing the anchor.

28. The system according to claim 17, wherein the selecting further comprises

selecting a server in the plurality of servers to perform the comparing and the delta-compressing, the selected server storing the anchor.

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

removing a zone stamp from the generated listing, wherein the zone stamp represents an anchor delta-compressed zone having at least one dependent delta-compressed zone.

30. The system according to claim 17, wherein the operations further comprise

performing at least one of the comparing, the delta-compressing, and the selecting by the plurality of servers in parallel.

31. The system according to claim 17, wherein each zone has a fixed length.

32. The system according to claim 17, wherein each zone has a variable length.

33. 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 listing of a plurality of zone stamps, each zone stamp representing a zone in the plurality of zones in a data stream, the generated listing containing a logical arrangement of the plurality of zone stamps obtained from each storage location and being accessible by a plurality of servers;

comparing a first zone stamp in the plurality of zone stamps contained in the generated listing to a second zone stamp in the plurality of zone stamps contained in the generated listing, the first zone stamp representing a first zone in the plurality of zones and the second zone stamp representing a second zone in the plurality of zones;

delta-compressing the first zone and the second zone based on a determination that the first zone stamp is substantially similar to the second zone stamp; and

selecting, based on the generated listing, a server in the plurality of servers to perform the comparing and the delta-compressing.

34. The computer program product according to claim 33, wherein the operations further comprise deleting at least one of the first zone stamp and the second zone stamp from the generated listing.

35. The computer program product according to claim 34, wherein the deleted at least one first zone stamp and the second zone stamp represent at least one zone purged from the plurality of zones.

36. The computer program product according to claim 33, wherein the logical arrangement of the plurality of zone stamps is based on at least one of the following:

a processing capability of each server in the plurality of servers, a size of each zone in the plurality of zones, a time consumed by the comparing, and availability of each server in the plurality of servers.

37. The computer program product according to claim 33, wherein the comparing further comprises

comparing the first zone stamp and the second zone stamp based on the first zone and the second zone having at least one of the following:

same starting characters and same ending characters.

38. The computer program product according to claim 33, wherein the delta-compressing further comprises

delta-compressing the first zone and the second zone at at least one of the following:

a first server in the plurality of servers storing the first zone and a second server in the plurality of servers storing the second zone.

39. The computer program product according to claim 33, wherein the delta-compressing further comprises

determining that a portion of the first zone is stored on a first server in the plurality of servers and another portion of the first zone is stored on a second server in the plurality of servers;

and

delta-compressing the first zone using the first server or the second server.

40. The computer program product according to claim 33, wherein the selecting further comprises

determining that a portion of the first zone is stored on a first server in the plurality of servers and another portion of the first zone is stored on a second server in the plurality of servers;

and

selecting, based on the determining, the first server or the second server to perform the comparing and the delta-compressing.

41. The computer program product according to claim 33, wherein the operations further comprise

storing a delta-compressed zone at a server in a plurality of servers that received the un-delta-compressed zone in the data stream.

42. The computer program product according to claim 33, wherein the operations further comprise

deduplicating, based on delta-compressing, the first zone and the second zone.

43. The computer program product according to claim 33, wherein each delta-compressed zone is associated with an anchor, wherein a plurality of delta-compressed zones are dependent on the anchor, the delta-compressed zone is stored at a server in the plurality of servers storing the anchor.

44. The computer program product according to claim 33, wherein the selecting further comprises

selecting a server in the plurality of servers to perform the comparing and the delta-compressing, the selected server storing the anchor.

45. The computer program product according to claim 44, wherein the operations further comprise

removing a zone stamp from the generated listing, wherein the zone stamp represents an anchor delta-compressed zone having at least one dependent delta-compressed zone.

46. The computer program product according to claim 33, wherein the operations further comprise

performing at least one of the comparing, the delta-compressing, and the selecting by the plurality of servers in parallel.

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

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