Data sharing and recovery within a network of untrusted storage devices using data object fingerprinting

• US 8,121,993 B2
• Filed: 10/28/2009
• Issued: 02/21/2012
• Est. Priority Date: 10/28/2009
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Binford, Charles, Maydew, Stacy Lee, Blount, Joseph
• Primary Examiner(s): Vy, Hung T
• Assistant Examiner(s): Cao, Phuong Thao
• Application Number:
  US12/607,583
• Publication Number:
  US 20110099200A1
• Time in Patent Office: 846 Days
• Field of Search: 707/699, 707/609, 707/698, 707/828
• US Class Current: 707/698
• CPC Class Codes: G06F 16/152 using file content signatures, e.g. hash values
• CPC Class Codes: G06F 21/16 Program or content traceability, e.g. by watermarking
• CPC Class Codes: G06F 21/32 using biometric data, e.g. fingerprints, iris scans or voiceprints
• CPC Class Codes: G06F 2221/2145 Inheriting rights or properties, e.g., propagation of permissions or restrictions within a hierarchy
• CPC Class Codes: H04L 1/0061 Error detection codes
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity

Abstract

A data sharing method using fingerprinted data objects for sharing data among untrusted network devices. Each peer device is adapted for storing a plurality of data objects, and a fingerprint generator is used to generate a fingerprint for each stored data object available for sharing or for recovery. The fingerprints are stored in a local data store, and a data manager running on one of the computer devices retrieves from another of the computer devices a copy of one of its data objects through the use of the associated fingerprints. The fingerprints include a hash value output from a strong hashing algorithm. The retrieving includes transmitting query messages with the fingerprints of the needed data objects to the networked, peer devices and then verifying the integrity of received data objects by generating a fingerprint of the received data objects that can be compared with the ones provided in the queries.

Claims

1. A data sharing method, comprising:

communicatively linking a plurality of computer devices via a communications network, wherein each of the computer devices includes a data storage storing a plurality of data objects;

providing a fingerprint generation module on each of the computer devices;

with each of the computer devices, processing each data object of at least a portion of the data objects in the data storage with the fingerprint generation module to generate a fingerprint for the data object, wherein the fingerprints are stored in a searchable manner in a data store, wherein each fingerprint comprises a hash value that is output from a hashing algorithm run on an associated one of the data objects, wherein the fingerprint generation module parses the hash value into a plurality of sub-strings, wherein each of the plurality of sub-strings defines a corresponding sub-directory in a directory structure of a data storage, and wherein the sub-directories define a location for an instance of the associated one of the data objects; and

with a data manager on one of the computer devices, retrieving from another one of the computer devices a copy of one of the data objects in the data storage associated with the one of the computer devices using the fingerprint generated for the one of the data objects.

2. The method of claim 1, wherein a hash value is a first component of each of the fingerprints, and wherein each fingerprint further comprises a second component generated by performing a cyclic redundancy check (CRC) function on the associated data object.

3. The method of claim 1, wherein the retrieving of one of the data objects comprises transmitting a query providing the fingerprint for the one of the data objects to the computer devices over the communications network.

4. The method of claim 3, wherein the retrieving of one of the data objects further comprises receiving a message from a particular one of the computer devices indicating the provided fingerprint matches one of the fingerprints generated by the particular one of the computer devices and, in response, sending a retrieve message with the fingerprint for the one of the data objects to the particular one of the computer devices.

5. The method of claim 4, wherein the retrieving of one of the data objects further comprises receiving a data object from the particular one of the computer devices and verifying integrity of the received data object by using the fingerprint generation module to generate a new fingerprint and comparing the new fingerprint with the fingerprint provided to the particular one of the computer devices.

6. The method of claim 1, wherein a hash value is a location component of each of the fingerprints.

7. The method of claim 1, wherein the fingerprint generation modules of first and second of the plurality of computer devices generate a same hash value for a first data object, wherein the fingerprint generation module of the first computer device parses the hash value into a first number of sub-strings, wherein the fingerprint generation module of the second computer devices parses the hash value into a second number of sub-strings, and wherein the first number is different than the second number.

8. The method of claim 2, wherein the second component of each fingerprint comprises a name component of a file that is located in the directory structure by the sub-directories of an associated data object.

9. A data recovery method, comprising:

with at least one microprocessor, executing at least one fingerprint generation module to process a plurality of data objects to define a fingerprint for each of the data objects, wherein each of the fingerprints comprises a hash value for an associated one of the data objects, wherein the fingerprint generation module is executed to parse the hash value into a plurality of sub-strings, wherein each of the plurality of sub-strings defines a corresponding sub-directory in a directory structure of a data storage device, and wherein the sub-directories define a location for an instance of the associated one of the data objects;

storing the data objects in a distributed manner in data storage devices of a plurality of peer devices linked to a network, wherein each of the data storage devices stores a subset of the data objects with at least some of the subsets storing differing ones of the data objects;

storing the fingerprints associated with each of the subsets of the data objects in memory accessible by one of the peer devices associated with one of the data storage devices storing one of the subsets of the data objects;

responsive to a loss of at least a portion of one of the data object subsets from one of the data storage devices, operating a data manager at an associated peer device to recover the portion of the one of the data object subsets, wherein the operating comprises;

retrieving, from the memory, the fingerprints associated with the portion of the one of the data object subsets to be recovered; and

transmitting query messages to the peer devices to locate the portion of the one of the data object subsets to be recovered, wherein each query message includes the retrieved fingerprints.

10. The method of claim 9, wherein each of the peer devices receiving the query messages compares the fingerprints in the query messages with the fingerprints stored in its associated accessible memory and provides a responsive message indicating located ones of the data objects.

11. The method of claim 10, further comprising:

operating the data manager, for each of the data objects being recovered, to direct a retrieve message with one of the fingerprints of the data objects being recovered to one of the peer devices providing the responsive messages.

12. The method of claim 11, further comprising:

with the data manager, receiving the data objects being recovered from the peer devices and, prior to storing the received data objects,

verifying integrity by using one of the fingerprint generation modules to generate a fingerprint for each received data object and comparing the generated fingerprints with the fingerprints stored in the memory.

13. The method of claim 9, wherein the fingerprint generation module comprises a strong hashing algorithm producing the hash value.

14. A data sharing and recovery system comprising:

a communications network; and

a plurality of peer systems each including a processor providing a data manager with a fingerprint generation module, wherein each of the peer systems is linked to the communications network for communicating with other ones of the peer systems;

wherein each of the peer systems includes a repository storing a number of data objects; and

wherein each of the peer systems includes a data store storing a fingerprint generated by the fingerprint generation module for each of the data objects in the associated peer system repository, wherein each fingerprint comprises a location component generated based on an output of a hash function applied to an associated one of the data objects, wherein the hash function output is parsed to divide it into a number of segments, and wherein the number of segments are used to define a respective number of nodes in the repository which collectively represent a file path for the associated one of the data objects.

15. The system of claim 14, wherein the fingerprint generation modules each utilize the same hash function.

16. The system of claim 14, wherein the data objects stored differ for at least some of the peer systems.

17. The system of claim 14, wherein at least one of the data managers operates to initiate data sharing by transmitting a query over the communications network to other ones of the peer systems, the query comprising the fingerprint of one of the data objects in the peer systems repository associated with the one of the data managers.

18. The system of claim 17, wherein the one of the data managers further operates to poll a first of the peer systems with the fingerprint of the one of the data objects to retrieve a copy of the one of the data objects.

19. The system of claim 18, wherein the one of the data managers further operates to operate the fingerprint generation module to generate a fingerprint of the received copy of the one of the data objects and further operates to verify integrity by comparing the fingerprint of the received copy with the fingerprint used in the polling step.