Content-based, compression-enhancing routing in distributed, differential electronic-data storage systems

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

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Lillibridge, Mark, Eshghi, Kave, Mehra, Pankaj, Fineberg, Samuel
• Granted Patent: US 8,543,782 B2
• Time in Patent Office: Days
• US Class Current: 711/154
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0635 by changing the path, e.g. traffic rerouting, path reconfiguration
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

One embodiment of the present invention includes a method for routing a data object, comprising a sequence of data units, to a particular component data-storage system, or particular group of component data-storage systems, within a distributed, differential electronic-data storage system by selecting one or more subsequences of data units from the data object, computing a characteristic value from the selected subsequences, computing an index from the characteristic value; and directing the data object to the particular component data-storage system, or to the particular group component data-storage systems, identified by the computed index.

Claims

1. A method for routing a data object, comprising a sequence of data units, to a particular component data-storage system, or particular group component of data-storage systems, within a distributed, differential electronic-data storage system, the method comprising:

selecting one or more subsequences of data units from the data object;

computing one or more characteristic values from the selected subsequences;

computing one or more indexes from the one or more characteristic values; and

directing the data object to the particular component data-storage system, or to the particular group of component data-storage systems, identified by the one or more computed indexes.

2. The method of claim 1 wherein selecting one or more subsequences of data units from the data object further includes:

selecting a window size;

selecting an offset; and

selecting window-size subsequences of data-units from the data object offset from one another by a number of data units equal to the selected offset.

3. The method of claim 2 wherein the selected offset is equal to the window size, resulting in selection of a consecutive sequence of contiguous, but non-overlapping data-unit subsequences from the data object.

4. The method of claim 2 wherein the selected offset is equal to 1, resulting in selection of a consecutive sequence of n grams from the data object, where n is equal to the window size.

5. The method of claim 2 further including:

selecting a length; and

selecting up to a number of subsequences of data units from the data object equal to the selected length.

6. The method of claim 1 wherein computing one or more characteristic values from the selected subsequences further includes:

generating one or more values for each selected subsequence of data units; and

computing one or more characteristic values from one or more of the one or more generated values.

7. The method of claim 6 wherein generating one or more values for each selected subsequence of data units further includes employing a hash function to generate a hash value from each of the selected subsequences.

8. The method of claim 6 wherein computing one or more characteristic values from one or more of the one or more generated values further includes one of:

computing one or more characteristic values by a numerical function that takes one or more generated values as arguments; and

selecting one or more of the generated values as the one or more characteristic values.

9. The method of claim 8 wherein selecting one of the one or more generated values as the one or more characteristic values includes one of:

selecting one or more of the maximum-valued generated value;

selecting one or more of the minimum-values generated value;

selecting an average value of the generated values; and

selecting a median value of the generated values.

10. The method of claim 1 wherein computing an index from the one or more characteristic values further includes combining, when there are multiple characteristic values, the two or more characteristic values to produce an integer, dividing the integer by the number of component data-storage systems, or groups of component data-storage systems, and selecting the remainder following integer division as the index.

11. Computer instructions encoded in a computer-readable medium that implement the method of claim 1.

15. The routing component of claim 2 wherein the selected offset is equal to 1, resulting in selection of a consecutive sequence of n grams from the data object, where n is equal to the window size.

16. The routing component of claim 2 further including:

selecting a length; and

selecting up to a number of subsequences of data units from the data object equal to the selected length.

12. A routing component of a distributed, differential electronic-data storage system that routes a data object, comprising a sequence of data units, to a particular component data-storage system, or particular group component data-storage systems, of the distributed, differential electronic-data storage system by:

selecting one or more subsequences of data units from the data object;

computing one or more characteristic values from the selected subsequences;

computing one or more indexes from the one or more characteristic values; and

directing the data object to the particular component of the data-storage system, or to the particular group of component data-storage systems, identified by the one or more computed indexes.

13. The routing component of claim 12 wherein selecting one or more subsequences of data units from the data object further includes:

selecting a window size;

selecting an offset; and

selecting window-size subsequences of data-units from the data object offset from one another by a number of data units equal to the selected offset.

14. The routing component of claim 13 wherein the selected offset is equal to the window size, resulting in selection of a consecutive sequence of contiguous, but non-overlapping data-unit subsequences from the data object.

17. The routing component of claim 12 wherein computing one or more characteristic values from the one or more selected subsequences further includes:

generating one or more values for each selected subsequence of data units; and

computing one or more characteristic values from one or more of the one or more generated values.

18. The routing component of claim 17 wherein generating one or more values for each selected subsequence of data units further includes employing a hash function to generate a hash value from each of the selected subsequences.

19. The routing component of claim 17 wherein computing one or more characteristic values from one or more of the one or more generated values further includes one of:

computing the one or more characteristic values by a numerical function that takes one or more generated values as arguments; and

selecting one or more of the generated values as the characteristic value.

20. The routing component of claim 12 wherein computing an index from the one or more characteristic values further includes combining, when there are multiple characteristic values, the two or more characteristic values to produce an integer, dividing the integer by the number of component data-storage systems, or groups of component data-storage systems, and selecting the remainder following integer division as the index.