Distributed differential store with non-distributed objects and compression-enhancing data-object routing

• US 20070250519A1
• Filed: 04/25/2006
• Published: 10/25/2007
• Est. Priority Date: 04/25/2006
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Lillibridge, Mark, Eshghi, Kave, Mehra, Pankaj, Fineberg, Samuel
• Granted Patent: US 8,190,742 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G11B 2220/412 Distributed storage methods, i.e. the system may autonomously determine for a storage device that provides enough storage capacity for recording
• CPC Class Codes: G11B 27/002 Programmed access in sequence to a plurality of record carriers or indexed parts, e.g. tracks, thereof, e.g. for editing; transfer of record carriers from magazine G11B15/68, G11B17/10; G11B17/22
• CPC Class Codes: G11B 27/11 by using information not detectable on the record carrier
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

Abstract

One embodiment of the present invention provides a distributed, differential electronic-data storage system that includes client computers, component data-storage systems, and a routing component. Client computers direct data objects to component data-storage systems within the distributed, differential electronic-data storage system. Component data-storage systems provide data storage for the distributed, differential electronic-data storage system. The routing component directs data objects, received from the clients computers, through logical bins to component data-storage systems by a compression-enhancing routing method.

Claims

1. A distributed, differential electronic-data storage system comprising:

client computers that direct data objects to data storage within the distributed, differential electronic-data storage system;

component data-storage systems that together provide data storage for the distributed, differential electronic-data storage system; and

a routing component that directs data objects, received from the clients computers, through logical bins to component data-storage systems by a data-compression-enhancing method.

2. The distributed, differential electronic-data storage system of claim 1 wherein data objects may directed through one or more logical bins to a single component data-storage system.

3. The distributed, differential electronic-data storage system of claim 1 wherein data objects may directed through a single logical bin to one or more component data-storage systems.

4. The distributed, differential electronic-data storage system of claim 1 wherein a component data-storage system may be deleted from the distributed, differential electronic-data storage system by:

redirecting logical bins initially directed to the component data-storage system to one or more other component data-storage systems within the distributed, differential electronic-data storage system; and

copying data objects stored in the component data-storage system to the one or more other component data-storage systems.

5. The distributed, differential electronic-data storage system of claim 1 wherein an efficiency-metric value for the distributed, differential electronic-data storage system can be obtained by:

generating an original data object by a random data-generation system;

generating a number n of data objects from the original data object by making the number of successive, random, one-byte changes to the original data object;

storing the n memory objects in the distributed, differential electronic-data storage system;

determining the size of the memory used to store the n data objects in the distributed, differential electronic-data storage system; and

computing the efficiency-metric value as the ratio of the determined size of the memory used to store the n data objects in the distributed, differential electronic-data storage system and the sum of the sizes of the data objects.

6. The distributed, differential electronic-data storage system of claim 1 wherein the routing component directs data objects, received from the clients computers, to component data-storage systems by a query-based compression-enhancing routing method.

7. The distributed, differential electronic-data storage system of claim 6 wherein the query-based compression-enhancing routing method comprises directs a data object, received from the clients computers, to component data-storage systems by:

selecting a set of component data-storage systems to query;

for each currently considered component data-storage system of the selected set of component data-storage systems,

directing a query to the currently considered component data-storage system to determine a level of compression that can be obtained by storing the data object in the currently considered component data-storage system, and

receiving from the currently considered component data-storage system an indication from which the level of compression that can be obtained by storing the data object in the currently considered component data-storage system can be determined; and

selecting, for storage of the data object, a component data-storage system according to component-data-storage-system-selection criteria that include a level of compression achievable by the component data-storage system.

8. The distributed, differential electronic-data storage system of claim 7 wherein the query-based compression-enhancing routing method is a trial-based query-based compression-enhancing routing method in which a currently considered component data-storage system responds to a query for a data object by:

reversibly storing the data object in order to determine the size of the memory required to store the data object; and

returning to the routing component a value based on the determined size of the memory required to store the data object.

9. The distributed, differential electronic-data storage system of claim 8 wherein the value based on the determined size of the memory required to store the data object is one of:

the determined size of the memory required to store the data object; and

the ratio of the size of the memory required to store the data object divided by the size of the data object.

10. The distributed, differential electronic-data storage system of claim 7 wherein the query-based compression-enhancing routing method is a chunk-based query-based compression-enhancing routing method in which a currently considered component data-storage system responds to a query for a data object by:

determining a first number of matches between a second number of hash values received from the routing component with hash values stored within the currently considered component data-storage system; and

returning to the routing component a value based on the determined first number of matches.

11. The distributed, differential electronic-data storage system of claim 10 wherein the value based on the determined first number of matches is one of:

the determined first number of matches;

a ratio of the determined first number of matches divided by the second number of hash values; and

one minus the ratio of the determined first number of matches divided by the second number of hash values

12. The distributed, differential electronic-data storage system of claim 7 wherein the query-based compression-enhancing routing method is a similarity-key-based query-based compression-enhancing routing method in which a currently considered component data-storage system responds to a query for a data object by:

determining whether a similarity key received from the routing component matches any similarity keys stored with the currently considered component data-storage system; and

returning to the routing component a value based on whether or not the similarity key received from the routing component matches any similarity keys stored with the currently considered component data-storage system.

13. A method for routing a data object to a component data-storage system within a distributed, differential electronic-data storage system, the method comprising:

selecting a set of component data-storage systems to query;

for each currently considered component data-storage system of the selected set of component data-storage systems,

directing a query to the currently considered component data-storage system to determine a level of compression that can be obtained by storing the data object in the currently considered component data-storage system, and

receiving from the currently considered component data-storage system an indication from which the level of compression that can be obtained by storing the data object in the currently considered component data-storage system can be determined; and

selecting, for storage of the data object, a component data-storage system according to component-data-storage-system-selection criteria that include a level of compression achievable by the component data-storage system.

14. The method of claim 13 wherein a currently considered component data-storage system responds to a query for a data object by:

reversibly storing the data object in order to determine the size of the memory required to store the data object; and

returning a value based on the determined size of the memory required to store the data object.

15. The method of claim 14 wherein the value based on the determined size of the memory required to store the data object is one of:

the determined size of the memory required to store the data object; and

the ratio of the size of the memory required to store the data object divided by the size of the data object.

16. The method of claim 13 wherein a currently considered component data-storage system responds to a query for a data object by:

determining a first number of matches between a second number of received hash values with hash values stored within the currently considered component data-storage system; and

returning a value based on the determined first number of matches.

17. The method of claim 16 wherein the value based on the determined first number of matches is one of:

the determined first number of matches;

a ratio of the determined first number of matches divided by the second number of hash values; and

one minus the ratio of the determined first number of matches divided by the second number of hash values

18. The method of claim 13 wherein a currently considered component data-storage system responds to a query for a data object by:

determining whether a received similarity key matches any similarity keys stored with the currently considered component data-storage system; and

returning a value based on whether or not the similarity key received from the routing component matches any similarity keys stored with the currently considered component data-storage system.