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

• US 8,190,742 B2
• Filed: 04/25/2006
• Issued: 05/29/2012
• 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: Fineberg, Samuel A., Eshghi, Kave, Mehra, Pankaj, Lillibridge, Mark
• Primary Examiner(s): BAYARD, DJENANE M
• Application Number:
  US11/411,386
• Publication Number:
  US 20070250519A1
• Time in Patent Office: 2,226 Days
• Field of Search: 709/226, 709/201, 709/229
• US Class Current: 709/226
• 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:

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

a routing component configured to direct data objects, received from client computers, through logical bins to the component data-storage systems by a data-compression-enhancing method,

wherein the routing component is configured to further calculate an efficiency-metric value for the distributed, differential electronic-data storage system 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 data objects in the distributed, differential electronic-data storage system;

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

computing the efficiency-metric value based on a 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 n data objects.

2. A storage system comprising:

a portal comprising a computer, wherein the portal is configured to;

map logical bins to corresponding component data-storage systems that provide distributed, differential data storage;

receive data objects from at least one client computer; and

direct the data objects through the logical bins to the component data-storage systems, wherein the portal is to direct the data objects to the component data-storage systems according to compression-enhancing routing that routes the data objects to the component data-storage systems based on determination by the portal of which of the component data-storage systems provides increased compression of each respective one of the data objects relative to another of the component data-storage systems,

wherein the compression-enhancing routing comprises;

for a particular one of the data objects, selecting a set of the 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 particular 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 is determined; and

selecting, for storage of the particular data object, a component data-storage system from among the set of component data-storage systems based on comparing the levels of compression that can be obtained by storing the particular data object in the component data-storage systems of the set, wherein the selection of the component data-storage system for storage of the particular data object is based on selecting the component data-storage system that is able to achieve a higher level of compression.

3. The storage system of claim 2, wherein the portal is configured to direct data objects through plural ones of the logical bins to a single one of the component data-storage systems.

4. The storage system of claim 2, wherein the portal is configured to direct data objects through a single one of the logical bins to plural ones of the component data-storage systems.

5. The storage system of claim 2, wherein in response to removal of one of the component data-storage systems, the portal is configured to:

redirect logical bins initially mapped to the removed component data-storage system to one or more other of the component data-storage systems; and

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

6. The storage system of claim 2 wherein the compression-enhancing routing is a trial-based query-based compression-enhancing routing in which a currently considered component data-storage system of the set of component data-storage systems, responds to the query by:

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

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

7. The storage system of claim 6, wherein the value based on the determined size of the memory required to store the particular data object is one of:

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

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

8. The storage system of claim 2, wherein the compression-enhancing routing is a chunk-based query-based compression-enhancing routing in which a currently considered component data-storage system responds to the query by:

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

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

9. The storage system of claim 8, 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.

10. The storage system of claim 2, wherein the compression-enhancing routing is a similarity-key-based query-based compression-enhancing routing in which a currently considered component data-storage system responds to the query by:

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

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

11. The storage system of claim 2 wherein the compression-enhancing routing stores groups of the data objects on respective individual ones of the component data-storage systems to allow compression of each of the groups of the data objects at the respective individual component data-storage system.

12. The storage system of claim 11, wherein the compression of each of the groups of the data objects involves differential storing of the data objects of each group that removes redundant copies of data in the data objects of the corresponding group.

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 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 is determined; and

selecting, for storage of the data object, a component data-storage system from among the set of component data-storage systems, based on comparing the levels of compression that can be obtained by storing the data object in the component data-storage systems of the set, wherein selecting the component data-storage system for storage of the data object is based on selecting the component data-storage system that is able to achieve a higher level of compression.

14. The method of claim 13, wherein a currently considered component data-storage system of the set of component data-storage systems responds to the query by:

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

returning a value as the indication 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

a 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 of the set of component data-storage systems responds to the query 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 as the indication 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 of the set of component data-storage systems, responds to the query by:

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

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

19. The method of claim 13, wherein selecting the component data-storage system is further based on selecting from among multiple data-storage systems that provide a particular level of compression using a tie-breaking procedure.