Method and apparatus for bandwidth-efficient and storage-efficient backups

• US 7,139,808 B2
• Filed: 04/30/2002
• Issued: 11/21/2006
• Est. Priority Date: 04/30/2002
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Anderson, Andrew V., Bennett, Steven M., Robinson, Scott H.
• Primary Examiner(s): Burgess, Glenton B.
• Assistant Examiner(s): BARQADLE, YASIN M
• Application Number:
  US10/136,756
• Publication Number:
  US 20030204609A1
• Time in Patent Office: 1,666 Days
• Field of Search: 709217-219, 709229-232, 709211-212, 709/247, 711161-162
• US Class Current: 709/212
• CPC Class Codes: H04L 67/30 Profiles
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method is presented that includes generating a content identifier for at least one article. The content identifier identifies the article. Also, determining if at least a portion of the at least one article is present on at least one device based on the content identifier. The at least one portion of the at least one article is stored if the at least one portion of the at least one article is determined to be not present on the at least one device. Also presented is a method including requesting at least one article by a content identifier representing the article. The at least one article is determined if it is present on at least one device based on the content identifier. At least one portion of the at least one article is returned if the at least one portion of the at least one article is determined to be present on the at least one device.

Claims

1. A method comprising:

generating a content identifier for at least one article, the content identifier representing the at least one article, the content identifier is a hash of contents of the at least one article and at least one portion of metadata,

generating a client-invariant content descriptor including the content identifier, contents of the at least one article, commonly shared metadata between at least two clients and a content signaturing mechanism identifier,

determining if at least one portion of the at least one article is present on at least one device based on the content identifier,

generating at least one portion of at least one differential contour for a plurality of articles

storing the at least one portion of the at least one article if the at least one portion of the at least one article is determined to be not present on the at least one device, and

transmitting only an article identifier if the at least one article only has client-specific information modified from prior information.

2. The method of claim 1, wherein the content identifier is generated from one of

a hash of contents of the at least one article,

a combination of a hash of contents of the at least one article and at least one portion of metadata,

at least one content signaturing algorithm over contents of the at least one article,

at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata, and

a combination of at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata.

3. The method of claim 1, wherein the at least one portion of the at least one article includes one of a portion of contents of the at least one article, at least one portion of metadata, and a portion of contents of the at least one article and at least one portion of metadata.

4. The method of claim 3, wherein at least one portion of the at least one article is stored on the at least one device and at least two articles have the same at least one portion.

5. The method of claim 4, wherein the at least two articles reside on one of at least two separate devices and one device.

6. The method of claim 3, wherein a plurality of copies of the at least one portion of the at least one article are stored on the at least one device.

7. The method of claim 1, determining if the at least one portion of the at least one article is present on the at least one device based on the content identifier further comprising:

determining if a portion of a second article is present on the at least one device, the portion of the second article represented by a content identifier identical to the content identifier for the at least one article where the content identifier for the portion of the second article is determined using the same mechanism as the content identifier for the at least one article.

8. The method of claim 7, wherein the portion of the second article includes one of a portion of contents of the second article, at least one portion of metadata, and a portion of contents of the second article and at least one portion of metadata.

9. The method of claim 1, further comprising:

generating at least one portion of at least one contour for a plurality of articles.

10. The method of claim 9, wherein the at least one contour includes one of content identification for each of the plurality of articles, and content identification for each of the plurality of articles and metadata, wherein content identification for each of the plurality of articles is generated from one of

a hash of contents of the particular article,

a hash of contents of the particular article and at least one portion of metadata,

a combination of a hash of contents of the particular article and at least one portion of metadata,

at least one content signaturing algorithm over contents of the particular article,

at least one content signaturing algorithm over contents of the particular article and at least one portion of metadata, and

a combination of at least one content signaturing algorithm over contents of the particular article and at least one portion of metadata.

11. The method of claim 9, further including:

storing the at least one portion of the at least one contour.

12. The method of claim 11, wherein the at least one portion of the at least one contour is stored on one of the at least one device and a source device, wherein the source device is one of local and remote to the at least one device.

13. The method of claim 1, wherein the at least one article is originally stored on one of the at least one device and a source device, wherein the source device is one of local and remote to the at least one device.

14. A method comprising:

requesting at least one portion of at least one article by a content identifier representing the at least one article, the content identifier is a hash of contents of the at least one article and at least one portion of metadata,

determining if a client-invariant content descriptor is present on at least one device, the client-invariant content descriptor including the content identifier, contents of the at least one article, commonly shared metadata between at least two clients and a content signaturing mechanism identifier,

determining if the at least one portion of at least one article is present on at least one device based on the content identifier,

returning the at least one portion of the at least one article if the at least one portion of the at least one article is determined to be present on the at least one device,

determining if at least one portion of at least one differential contour for a plurality of articles exists on the at least one device, and

transmitting only an article identifier if the at least one article only has client-specific information modified from prior information.

15. The method of claim 14, wherein the content identifier is generated from one of

a hash of contents of the at least one article,

a combination of a hash of contents of the at least one article and at least one portion of metadata,

at least one content signaturing algorithm over contents of the at least one article,

at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata, and

a combination of at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata.

16. The method of claim 14, wherein the at least one portion of the at least one article includes one of a portion of contents of the at least one article, at least one portion of metadata, and a portion of contents of the at least one article and at least one portion of metadata.

17. The method of claim 14, wherein a plurality of representations of the at least one portion of the at least one article are returned.

18. The method of claim 14, wherein requesting at least one article by a content identifier representing the article further comprises:

selecting at least one portion of at least one article represented in at least one portion of at least one contour, wherein the at least one portion of the at least one contour includes one of content identification for each of the plurality of articles, and content identification for each of the plurality of articles and at least one portion of metadata, and

requesting the at least one portion of at least one article represented in at least one portion of at least one contour using the content identifier for the at least one article.

19. The method of claim 18, further including:

returning the at least one portion of at least one article represented by the at least one portion of at least one contour.

20. The method of claim 19, wherein the at least one portion of the at least one article includes one of a portion of contents of the at least one article, at least one portion of metadata, and a portion of contents of the at least one article and at least one portion of metadata.

21. The method of claim 18, wherein the at least one portion of at least one contour is originally stored on one of the at least one device and a source device, wherein the source device is one of local and remote to the at least one device.

22. The method of claim 14, wherein the at least one portion of at least one article is originally stored on one of the at least one device and a source device, wherein the source device is one of local and remote to the at least one device.

23. An apparatus comprising a machine-readable medium containing instructions which, when executed by a machine, cause the machine to perform operations comprising:

generating a content identifier for at least one article, the content identifier representing the article, the content identifier is a hash of contents of the at least one article and at least one portion of metadata,

determining if a client-invariant content descriptor is present on at least one device, the client-invariant content descriptor including the content identifier, contents of the at least one article, commonly shared metadata between at least two clients and a content signaturing mechanism identifier,

determining if at least one portion of the at least one article is present on at least one device based on the content identifier, and

generating at least one portion of at least one differential contour for a plurality of articles,

storing the at least one portion of the at least one article if the at least one article is determined to be not present on the at least one device, and

transmitting only an article identifier if the at least one article only has client-specific information modified from prior information.

24. The apparatus of claim 23, wherein the content identifier is generated from one of

a hash of contents of the at least one article,

a combination of a hash of contents of the at least one article and at least one portion of metadata,

at least one content signaturing algorithm over contents of the at least one article,

at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata, and

a combination of at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata.

25. The apparatus of claim 23, wherein the at least one portion of the at least one article includes one of a portion of contents of the at least one article, at least one portion of metadata, and a portion of contents of the at least one article and at least one portion of metadata.

26. The apparatus of claim 25, wherein at least one portion of the at least one article is stored on the at least one device and at least two articles have the same at least one portion.

27. The apparatus of claim 26, wherein the at least two articles reside on one of at least two separate devices and one device.

28. The apparatus of claim 25, wherein a plurality of copies of the at least one portion of the at least one article are stored on the at least one device.

29. The apparatus of claim 23, determining if the at least one portion of the at least one article is present on the at least one device based on the content identifier further comprising:

determining if a portion of a second article is present on the at least one device, the portion of the second article represented by a content identifier identical to the content identifier for the at least one article where the content identifier for the second article is determined using the same mechanism as the content identifier for the at least one article.

30. The apparatus of claim 29, wherein the at least one portion of the second article includes one of a portion of contents of the second article, at least one portion of metadata, and a portion of contents of the second article and at least one portion of metadata.

31. The apparatus of claim 23, further containing instructions which, when executed by a machine, cause the machine to perform operations including:

generating at least one portion of at least one contour for a plurality of articles.

32. The apparatus of claim 31, wherein the at least one contour includes one of content identification for each of the plurality of articles, and content identification for each of the plurality of articles and at least one portion of metadata, wherein content identification is generated from one of

a hash of contents of the at least one article,

a hash of contents of the at least one article and at least one portion of metadata,

a combination of a hash of contents of the at least one article and at least one portion of metadata,

at least one content signaturing algorithm over contents of the at least one article,

at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata, and

a combination of at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata.

33. The apparatus of claim 31, further containing instructions which, when executed by a machine, cause the machine to perform operations including:

storing the at least one portion of the at least one contour.

34. The apparatus of claim 33, wherein the at least one portion of the at least one contour is stored on one of the at least one device and a source device, wherein the source device is one of local and remote to the at least one device.

35. The apparatus of claim 23, wherein the at least one article is originally stored on one of the at least one device and a source device, wherein the source device is one of local and remote to the at least one device.

36. An apparatus comprising a machine-readable medium containing instructions which, when executed by a machine, cause the machine to perform operations comprising:

requesting at least one portion of at least one article by a content identifier representing the at least one article, the content identifier is a hash of contents of the at least one article and at least one portion of metadata,

determining if a client-invariant content descriptor is present on at least one device, the client-invariant content descriptor including the content identifier, contents of the at least one article, commonly shared metadata between at least two clients and a content signaturing mechanism identifier,

determining if the at least one portion of at least one article is present on at least one device based on the content identifier, and

returning at least one portion of the at least one article if the at least one portion of the at least one article is determined to be present on the at least one device,

determining if at least one portion of at least one differential contour for a plurality of articles exists on the at least one device, and

transmitting only an article identifier if the at least one article only has client-specific information modified from prior information.

37. The apparatus of claim 36, wherein the content identifier is generated from one of

a hash of contents of the at least one article,

a combination of a hash of contents of the at least one article and at least one portion of metadata,

at least one content signaturing algorithm over contents of the at least one article,

at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata, and

a combination of at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata.

38. The apparatus of claim 36, wherein the at least one portion of the at least one article includes one of a portion of contents of the at least one article, at least one portion of metadata, and a portion of contents of the at least one article and at least one portion of metadata.

39. The apparatus of claim 38, wherein a plurality of representations of the at least one portion of the at least one article are returned.

40. The apparatus of claim 36, further containing instructions which, when executed by a machine, cause the machine to perform operations including:

selecting at least one portion of at least one article represented in at least one portion of at least one contour, wherein the at least one portion of the at least one contour includes one of content identification for each of the plurality of articles, and content identification for each of the plurality of articles and at least one portion of metadata, and

requesting the at least one portion of at least one article represented in at least one portion of at least one contour using the content identifier for the at least one article.

41. The apparatus of claim 40, further containing instructions which, when executed by a machine, cause the machine to perform operations including:

returning at least one portion of at least one article represented by the at least one portion of at least one contour.

42. The apparatus of claim 41, wherein the at least one portion of the at least one article includes one of a portion of contents of the at least one article, at least one portion of metadata, and a portion of contents of the at least one article and at least one portion of metadata.

43. The apparatus of claim 41, wherein the at least one portion of at least one contour is originally stored on one of the at least one device and a source device, wherein the source device is one of local and remote to the at least one device.

44. The apparatus of claim 36, wherein the at least one portion of at least one article is originally stored on one of the at least one device and a source device, wherein the source device is one of local and remote to the at least one device.

45. A system comprising:

a plurality of devices coupled to a transmission medium, each of the plurality of devices coupled with a first process and a second process and having at least one article,

wherein the first process;

generates a content identifier for the at least one article for each of the plurality of devices, the content identifier representing the at least one article, the content identifier is a hash of contents of the at least one article and at least one portion of metadata,

generates a client-invariant content descriptor, the client-invariant content descriptor including the content identifier, contents of the at least one article, commonly shared metadata between at least two clients and a content signaturing mechanism identifier,

determines if the at least one article is present on at least one other of the plurality of devices based on the content identifier, and

generates at least one portion of at least one differential contour for a plurality of articles and

stores at least one portion of the at least one article if the at least one portion of the at least one article is determined to be not present on the at least one other of the plurality of devices,

transmits only an article identifier if the at least one article only has client-specific information modified from prior information

wherein the second process;

requests at least one portion of a second article by the content identifier representing the second article,

determines if the at least one portion of the second article is present on at least one of the plurality of devices based on the content identifier,

returns the at least one portion of the second article if the at least one portion of the second article is determined to be present on the at least one of the plurality of devices,

determines if at least one portion of at least one differential contour for a plurality of articles exists on at least one of the plurality of devices, and

transmits only an article identifier if the at least one article only has client-specific information modified from prior information.

46. The system of claim 45, wherein the content identifier is generated from one of

a hash of contents of the at least one article,

a combination of a hash of contents of the at least one article and at least one portion of metadata,

at least one content signaturing algorithm over contents of the at least one article,

at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata, and

a combination of at least one content signaturing algorithm over contents of the at least one article and at least one portion of metadata.

47. The system of claim 45, wherein the at least one portion of each of the at least one article and the second article include one of a portion of contents of the at least one article, at least one portion of metadata, and a portion of contents of the at least one article and at least one portion of metadata.

48. The system of claim 45, wherein the first process further:

generates at least one portion of at least one contour for a plurality of articles for at least one of the plurality of devices and

stores at least one portion of the at least one contour on at least one of the plurality of devices.

49. The system of claim 45, wherein the second process further:

selects at least one portion of at least one article represented in at least one portion of at least one contour, wherein the at least one portion of the at least one contour includes one of content identification for each of the plurality of articles, and content identification for each of the plurality of articles and at least one portion of metadata, and

requests the at least one portion of at least one article represented in at least one portion of at least one contour using the content identifier for the at least one article.