System and method for relating files in a distributed data storage environment

• US 6,615,225 B1
• Filed: 04/27/2000
• Issued: 09/02/2003
• Est. Priority Date: 04/27/2000
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Smith, James P., Cannon, David M., Dawson, Colin S., Haye, Mark A.
• Primary Examiner(s): LIANG, GWEN
• Application Number:
  US09/561,252
• Time in Patent Office: 1,223 Days
• Field of Search: 707/1, 707/10, 707/203, 707/204, 707/100, 707/101, 707/8, 707/202, 709/246, 709/236, 709/217, 709/224, 711/112, 711/115, 700/181, 379/114.14, 705/2, 714/47, 345/716, 345/723, 345/502, 370/426, 717/172, 715/511
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• 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/152 using file content signatures, e.g. hash values
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 2201/83 the solution involving signatures
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

A system and method for relating files in a distributed data storage environment allows for positive identification of membership of a file within a group, even in a loosely coupled environment where files are not available for comparison in real time. In disclosed embodiments, base files of a client are stored on a server and are accompanied by tokens uniquely identifying the base files. The tokens are generated on the client and may be derived from the contents of the base file using a digital signature. Each file transmitted to the server is accompanied with a token. Incremental backups may be used, and may employ file differencing. Accordingly, sub-files related to the base files may be transmitted to the server for backup. The sub-files are related to their respective base files using the tokens and are cross-linked to the base files so that any sub-files can be retrieved together with the base file from which the sub-file was derived.

Claims

1. A method for relating groups of files in a distributed data storage system having a primary storage site and a remote storage site, the method comprising:

assigning a token to a file of the primary storage site;

passing a copy of the file from the primary storage site to the remote storage site;

passing a copy of the token from the primary storage site to the remote storage site;

assigning membership of the file to at least one of a plurality of groups of files residing on the remote storage site by comparing the token with other tokens on the remote storage site without retrieving the group of files corresponding thereto; and

in response to a request from the primary storage site, returning a sub-file and a corresponding base file to the primary storage site from the remote storage site, the relationship of the base file and the sub-file established with use of the token.

2. The method of claim 1, wherein the token uniquely identifies a base file.

3. The method of claim 2, wherein the token is comprised of two components, a file identifier comprising attributes of the base file and an identification key derived from the contents of the base file.

4. The method of claim 1, wherein the file comprises a sub-file derived from a base file, the token is at least partially derived from the base file, and wherein the base file is not immediately available for comparison to the sub-file to determine relation of the sub-file to the base file.

5. The method of claim 1, wherein the file is a base file and the token is generated from the contents of the base file.

6. The method of claim 5, further comprising deriving a sub-file from the base file, assigning a second token based upon the token of the base file to the sub-file, and passing the sub-file together with the second token to the remote storage site.

7. The method of claim 1, wherein the file is a sub-file derived from a base file and the token is derived from the contents of the base file.

8. The method of claim 1, wherein determining membership comprises comparing the token to a listing of tokens, each token uniquely identifying a base file stored within the remote storage site.

9. The method of claim 1, wherein the plurality of groups comprise a plurality of base files grouped together with sub-files of each base file.

10. The method of claim 1, further comprising creating a cross-linking between a sub-file and a base file that have been related as a result of the step of determining membership of the file within one of a plurality of groups.

11. The method of claim 1, further comprising determining by comparison of tokens at the remote storage site that a file transmitted to the remote storage site as a sub-file does not have a corresponding base file at the remote storage site and returning a message to the primary storage site to notify the primary storage site that the sub-file will not be stored by the remote storage site.

12. The method of claim 11, further comprising, in response to the receipt of the message, retransmitting a backup of a file of the primary storage site as a base file rather than as a sub-file.

13. A method for relating groups of files in a distributed data storage system having a primary storage site and a remote storage site, the method comprising:

assigning a token to a base file of the primary storage site, the token uniquely identifying the base file and comprised of two components, a file identifier comprising attributes of the base file and an identification key derived from the contents of the base file;

passing a copy of the base file from the primary storage site to the remote storage site;

transferring the base file to a storage medium attached to the remote storage site;

passing a copy of the token from the primary storage site to the remote storage site;

storing the token in a token listing of the remote storage site;

deriving a sub-file from the base file, assigning a second token based upon the token of the base file to the sub-file, and passing the sub-file together with the second token to the remote storage site;

determining at the remote storage site the relation of the sub-file to the base file by comparing the second token to the token listing and matching the token of the base file;

creating a cross-linking between the sub-file and the base file; and

in response to a request from the primary storage site, returning the sub-file and the base file substantially together to the primary storage site from the remote storage site.

14. A system for relating groups of files in a distributed data storage system having a primary storage site and a remote storage site, the system comprising:

a token generation module within the primary storage site, the token generation module configured to generate tokens uniquely identifying files transmitted from the primary storage site to the remote storage site;

a token listing within the remote storage site;

a token comparison module within the remote storage site, the token comparison module configured to receive tokens passed in conjunction with transmission of a file from the primary storage site to the remote storage site and compare the tokens to one or more tokens within the token listing to establish a relationship of the file with other files previously transmitted from the primary storage site to the remote storage site without retrieving the other files; and

more storage devices of the remote storage site, each of the plurality of sub-files cross-linked with a base file resident within the storage devices after grouping the sub-files with the base files with use of the token comparison module.

15. The system of claim 14, further comprising a plurality of base files resident within storage devices of the remote storage site, a unique token corresponding to each of the base files stored within the token listing.

16. The system of claim 14, further comprising a plurality of tokens stored within the token listing, each of the plurality of tokens uniquely identifying a base file resident within a storage device of the remote storage site.

17. The system of claim 14, further comprising a backup determination module resident within the primary storage site, the backup determination module configured to select files for storage on the remote storage site and determine whether the files should be stored as base files or sub-files.

18. The system of claim 14, further comprising a repository within the primary storage site, the repository containing a representation of each of a plurality of base files stored on the remote storage site and also containing a plurality of tokens, each token unique to one of the base files stored on the remote storage site.

19. The system of claim 14, wherein the token generation module is configured to generate tokens at least partially indicative of the contents of base files.

20. The system of claim 19, wherein the token generation module is configured to generate tokens comprising two components, a file identifier comprising attributes of a base file and an identification key derived from the contents of a base file.

21. The system of claim 14, further comprising a hierarchy of storage devices connected to the remote storage site, a plurality of base files stored within the storage hierarchy, and a plurality of tokens stored within the token listing, each of the plurality of tokens uniquely identifying one of the base files stored within the storage hierarchy.

22. The system of claim 14, wherein the token comparison module is further configured to note a lack of establishment of a relationship of the file with other files previously transmitted from the primary storage site to the remote storage site and in response initiate the transmission of a message to the primary storage site that the file will not be stored at the remote storage site.

23. The system of claim 22, wherein the primary storage site is configured, in response to the receipt of the message, to retransmit a backup of a file of the primary storage site as a base file rather than as a sub-file.