Data repository and method for promoting network storage of data

• US 7,412,462 B2
• Filed: 02/16/2001
• Issued: 08/12/2008
• Est. Priority Date: 02/18/2000
• Status: Expired due to Fees

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Burnside Acquisition, LLC
• Inventors: Margolus, Norman H., Homsy, George E. II, Floyd, Jered J., Hartman, Sam, Knight, Thomas F. Jr.
• Primary Examiner(s): Pham; Hung Q
• Application Number:
  US09/785,535
• Publication Number:
  US 20020038296A1
• Time in Patent Office: 2,734 Days
• Field of Search: 707/10, 707/204, 707/200, 713/189, 713/193, 713200-202, 713/176, 713/180, 713/181, 709/203, 705/51, 705/18
• US Class Current: 1/1
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 21/10 Protecting distributed programs or content, e.g. vending or licensing of copyrighted material protection in video systems or pay television H04N7/16 ; Digital rights management [DRM]
• CPC Class Codes: G06F 21/60 Protecting data
• CPC Class Codes: G06F 21/62 Protecting access to data via a platform, e.g. using keys or access control rules
• CPC Class Codes: G06F 21/6209 to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: G06F 21/6272 by registering files or documents with a third party
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 21/645 using a third party
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

In general, the invention features methods by which more than one client program connected to a network stores the same data item on a storage device of a data repository connected to the network. In one aspect, the method comprises encrypting the data item using a key derived from the content of the data item, determining a digital fingerprint of the data item, and storing the data item on the storage device at a location or locations associated with the digital fingerprint. In a second aspect, the method comprises determining a digital fingerprint of the data item, testing for whether the data item is already stored in the repository by comparing the digital fingerprint of the data item to the digital fingerprints of data items already in storage in the repository, and challenging a client that is attempting to deposit a data item already stored in the repository, to ascertain that the client has the full data item.

Claims

1. A method by which a plurality of client programs connected to a network deposit data items into a data repository connected to the network and avoid repeated storage of duplicated data items, the method comprising:

depositing a data item in the data repository for a depositing client program, the depositing including

determining a digital fingerprint from the data item using a hash function that produces digital fingerprints having a pseudorandom distribution;

comparing the determined digital fingerprint from the deposited data item to digital fingerprints of data items already stored in the data repository;

establishing from the comparing of digital fingerprints, without comparing the entire contents of the deposited data item to the entire contents of a data item already stored, whether a stored data item is identical to the deposited data item; and

storing the deposited data item in the data repository if the deposited data item is not identical with any stored data item;

wherein the stored data item is associated with a named object and an access authorization credential which is uniquely associated with a depositing client program or with a data repository user;

wherein the access authorization credential is associated with the named object which comprises a digital fingerprint;

wherein the named object is stored in a database;

wherein the stored data item, in response to a request by a retrieving client program, is retrieved by using the access authorization credential to select the stored named object;

retrieving the stored named object from the database; and

using the digital fingerprint from the retrieved named object to return the stored data item;

wherein the physical location or locations at which the stored data item is stored in the data repository are determined at least in part by the digital fingerprint.

2. The method of claim 1 wherein the depositing further comprises encrypting the deposited data item using a key derived from the content of the deposited data item.

3. The method of claim 2 wherein the encrypting of the deposited data item is performed by the depositing client program.

4. The method of claim 2 wherein if the deposited data item is identical to each of a plurality of data items deposited independently by a plurality of the depositing client programs and if an encryption key is independently derived from the content of each of the plurality of data items, then all of the independently derived encryption keys are the same.

5. The method of claim 2 wherein users are grouped into a plurality of families, and the depositing client program acts on behalf of a user, and the key derived from the content of the deposited data item is determined in part by which of the plurality of families the user belongs to.

6. The method of claim 1 wherein the stored data item is associated with each of a plurality of access-authorization credentials, each of which is uniquely associated with a distinct data repository user or client program.

7. The method of claim 1 wherein the stored named object is identified by information representative of the access-authorization credential.

8. The method of claim 7 wherein the information representative of the access-authorization credential is a cryptographic hash of all or part of the access-authorization credential.

9. The method of claim 8 wherein the cryptographic hash is an access identifier that uniquely identifies the stored data item for a particular user or client program.

10. The method of claim 9 wherein the data repository is the database and the physical locations at which the named-object is stored are based on an access identifier.

11. The method of claim 1 wherein the stored named object further comprises historical version information associating data items deposited at different times with different named object versions.

12. The method of claim 1 wherein named object history is preserved by creatng a new version of the named object each time that a new data item is associated with it.

13. The method of claim 12, wherein a determination of which versions of the named object to delete is based in whole or in part on the times at which the versions were created, and the intervals between these times.

14. The method of claim 1 wherein a digital time stamp hash is prepared for each of a plurality of named objects to allow a property of these named objects to be proven at a later date.

15. The method of claim 14 wherein a random or other difficult to guess element is incorporated into the digital time stamp hash for each of the plurality of named objects, to prevent the property from being proven if this element is deleted.

16. The method of claim 1 wherein it is determined that the stored data item is no longer associated with any named object and the storage space used by the stored data item is reused.

17. The method of claim 1 further comprising a challenge step to ascertain that the depositing client program has the entirety of the data item being deposited.

18. The method of claim 1 wherein user identification is required when the depositing client program is acting on behalf of a depositor user and access to the data item being deposited for the depositor user can be shared with other users.

19. The method of claim 1 wherein identity information about a depositor user associated with the depositing client program is made available to the retrieval client program, to discourage unlawful sharing of proprietary information.

20. The method of claim 19 wherein the identity information is stored in an encrypted form that users with whom the depositor has shared access to the named object can both read and decrypt.

21. The method of claim 1 wherein when the identity of a depositor user associated with the depositing client program has not been verified, restrictions are placed on the use of the access authorization credential by retrieving programs associated with other users.

22. The method of claim 21 wherein the rate of retrieving data associated with the named object is limited.

23. The method of claim 1 wherein the deposit client program runs on a client machine and is a mirroring program which determines which data items to transmit to the data repository, and wherein that determination is based at least in part on the result of a comparison of digital fingerprints establishing that certain data items are not already stored in the data repository.

24. The method of claim 1 wherein an index data item comprises fingerprints that identify a plurality of data items stored in the data repository, and the index data item is the data item that is deposited in the data repository and associated with the named object and the named object is used by the retrieving client program to retrieve one of the plurality of stored data items.

25. The method of claim 1 wherein access to the named objects can be transferred between data repository users using the access authorization credential, without communicating with the data repository.

26. The method of claim 25 wherein at least one class of data repository users is not permitted to transfer access to their named objects to other users using access-authorization credentials individually associated with their named objects.

27. The method of claim 1 wherein different physical locations comprise different hard disk drives.

28. The method of claim 1 wherein the physical locations comprise data servers linked by a network.

29. The method of claim 1 wherein establishing from the comparing of digital fingerprints, without comparing the entire contents of the deposited data item to the entire contents of a data item already stored, whether a stored data item is identical to the deposited data item comprises transmitting over the network the digital fingerprint of the deposited data item rather than the deposited data item itself.

30. The method of claim 1 wherein the depositing client program comprises a file server.

31. The method of claim 1 wherein the named objects represents a directory of a file system stored within the data repository.

32. The method of claim 1 wherein a structured item is split up into a plurality of data items with the divisions occurring at content dependent boundaries and the deposited data item is one of the plurality of data items.

33. The method of claim 1 wherein the deposited data item is one of a plurality of identical data items deposited independently by a plurality of the depositing client programs, and a corresponding plurality of retrieving client programs all share read access to the stored data item.

34. The method of claim 33 wherein a retrieving client program which does not possess an access authorization credential cannot read the stored data item.

35. The method of claim 1 wherein the data repository is the database.

36. The method of claim 1 wherein the depositing client program and the retrieving client program are the same program.

37. The method of claim 1 wherein there exists a defined protocol used by data repository client programs to communicate with the data repository and the defined protocol allows data repository clients to deposit data items without sending their full contents if identical data items are already stored in the data repository, and the defined protocol only allows data repository clients to retrieve data items indirectly, by using access authorization credentials to select named objects.