Method of hashing address space to storage servers

• US 20060236073A1
• Filed: 02/03/2005
• Published: 10/19/2006
• Est. Priority Date: 02/03/2005
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company), 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: Merchant, Arif, Saito, Yasushi, Soules, Craig, Veitch, Alistair C.
• Granted Patent: US 7,823,156 B2
• Time in Patent Office: Days
• US Class Current: 711/216
• CPC Class Codes: G06F 2206/1012 Load balancing
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

An embodiment of a method of hashing an address space to a plurality of storage servers begins with a first step of dividing the address space by a number of the storage servers to form data segments. Each data segment comprises a base address. A second step assigns the data segments to the storage servers according to a sequence. The method continues with a third step of measuring a load on each of the storage servers. According to an embodiment, the method concludes with a fourth step of adjusting data shares assigned to the storage servers according to the sequence to approximately balances the loads on the storage servers while maintaining the base address for each data segment on an originally assigned storage server. According to another embodiment, the method periodically performs the third and fourth steps to maintain an approximately balanced load on the storage servers.

Claims

1. A method of hashing an address space to a plurality of storage servers comprising the steps of:

dividing the address space by a number of the storage servers to form data segments, each data segment comprising a base address;

assigning the data segments to the storage servers according to a sequence;

measuring a load on each of the storage servers; and

adjusting data shares assigned to the storage servers according to the sequence to approximately balance the loads on the storage servers while maintaining the base address for each data segment on an originally assigned storage server.

2. The method of claim 1 further comprising periodically performing the steps of measuring the load on each of the storage servers and adjusting the data shares assigned to the storage servers to maintain approximately balanced loads on the storage servers.

3. The method of claim 1 further comprising the step of permuting an initial address space to form the address space.

4. The method of claim 1 wherein each data segment further comprises a plurality of data blocks.

5. The method of claim 4 wherein the step of adjusting the data shares assigned to the storage servers reassigns first data blocks from a first over-utilized storage server to a first under-utilized storage server.

6. The method of claim 5 wherein the first data blocks comprise an upper end of the data segment.

7. The method of claim 6 wherein a remainder of the data segment comprises second data blocks and further wherein the second data blocks comprise a particular data block which resides at the base address for the data segment.

8. The method of claim 4 wherein the step of adjusting the data shares assigned to the storage servers reassigns first data blocks from a first over-utilized storage server to first and second under-utilized storage servers.

9. The method of claim 1 wherein the step of measuring the load on each of the storage servers comprises summing and weighting:

a number of outstanding cache-read requests;

a number of outstanding cache-write requests;

a number of outstanding disk-read requests; and

a number of outstanding disk-write requests.

10. The method of claim 9 wherein the step of measuring the load on each of the storage servers further comprises summing and weighting a number of outstanding time-stamp requests.

11. The method of claim 1 wherein the step of measuring the load on each of the storage servers comprises measuring a response time of each of the storage servers.

12. The method of claim 1 wherein the load comprises a cumulative load which comprises an averaged sum of an instantaneous load taken at time intervals over a time period.

13. The method of claim 1 wherein the load comprises a cumulative load which is generated through exponential averaging of instantaneous loads taken at time intervals over a time period.

14. The method of claim 1 wherein a coordinator coordinates the steps of:

dividing the address space into the data segments;

sequentially assigning the data segments;

measuring the load on each of the storage servers; and

sequentially adjusting the data shares assigned to the storage servers.

15. The method of claim 14 wherein the storage servers communicate the loads to the coordinator by appending load information onto messages.

16. The method of claim 14 wherein the storage servers communicate the loads to the coordinator by broadcasting load information periodically.

17. The method of claim 1 wherein the storage servers employ the method of hashing the address space as part of a caching technique for the storage servers.

18. The method of claim 17 wherein the caching technique further comprises caching policy selected from a least recently used caching policy, a least frequently used caching policy, a random caching policy, an adaptive replacement caching policy, a first-in-first-out caching policy, and an other caching policy.

19. A method of hashing an address space to a plurality of storage servers comprising the steps of:

dividing the address space by a number of the storage servers to form data segments, each data segment comprising a base address;

assigning the data segments to the storage servers according to a sequence;

measuring a load on each of the storage servers;

for each storage server, determining whether a data share for the storage server needs to be decreased or increased to approximately balance the loads on the storage servers in order to identify at least one over-utilized storage server and at least one under-utilized storage server; and

proceeding through the storage servers according to the sequence and for each over-utilized storage server reassigning a portion of the data segment to at least one sequentially available under-utilized storage server while maintaining the base address on an originally assigned storage server.

20. The method of claim 19 further comprising the step of permuting an initial address space to form the address space.

21. The method of claim 19 wherein each data segment further comprises a plurality of data blocks.

22. The method of claim 21 wherein the step of proceeding through the storage servers according to the sequence and for each over-utilized storage server reassigning the portion of the data segment to at least one sequentially available under-utilized storage server reassigns first data blocks from a first over-utilized storage server to a first under-utilized storage server.

23. The method of claim 22 wherein the first data blocks comprise an upper end of the data segment.

24. The method of claim 23 wherein a remainder of the data segment comprises second data blocks and further wherein the second data blocks comprise a particular data block which resides at the base address for the data segment.

25. The method of claim 21 wherein the step of proceeding through the storage servers according to the sequence and for each over-utilized storage server reassigning the portion of the data segment to at least one sequentially available under-utilized storage server reassigns first data blocks from a first over-utilized storage server to first and second under-utilized storage servers.

26. The method of claim 19 wherein the step of measuring the load on each of the storage servers comprises summing and weighting:

a number of outstanding cache-read requests;

a number of outstanding cache-write requests;

a number of outstanding disk-read requests; and

a number of outstanding disk-write requests.

27. The method of claim 26 wherein the step of measuring the load on each of the storage servers further comprises summing and weighting a number of outstanding time-stamp requests.

28. The method of claim 19 wherein the load comprises a cumulative load which comprises an averaged sum of an instantaneous load taken at time intervals over a time period.

29. The method of claim 19 wherein the step of determining whether the data share for the storage server needs to be decreased or increased to approximately balance the loads on the storage servers comprises:

subtracting a normalized storage server load from a normalized average load, thereby forming a load difference; and

summing the load difference and a normalized existing data share.

30. The method of claim 19 wherein the step of determining whether the data share for the storage server needs to be decreased or increased to approximately balance the loads on the storage servers comprises:

subtracting a normalized storage server lode from a normalized average load, thereby forming a load difference;

dividing the load difference by a factor, thereby forming a damped load difference; and

summing the damped load difference and a normalized existing data share.

31. The method of claim 19 wherein a coordinator coordinates the steps of:

dividing the address space into the data segments;

sequentially assigning the data segments;

measuring the load on each of the storage servers; and

sequentially adjusting the data shares assigned to the storage servers.

32. The method of claim 31 wherein the storage servers communicate the loads to the coordinator by appending load information onto messages.

33. The method of claim 31 wherein the storage servers communicate the loads to the coordinator by broadcasting load information periodically.

34. The method of claim 19 wherein the storage servers employ the method of hashing the address space as part of a caching technique for the storage servers.

35. The method of claim 34 wherein the caching technique further comprises caching policy selected from a least recently used caching policy, a least frequently used caching policy, a random caching policy, and an adaptive replacement caching policy.

36. A computer readable media comprising computer code for implementing a method of hashing an address space to a plurality of storage servers, the method of hashing the address space to the plurality of storage servers comprising the steps of:

dividing the address space by a number of the storage servers to form data segments, each data segment comprising a base address;

assigning the data segments to the storage servers according to a sequence;

measuring a load on each of the storage servers; and

adjusting data shares assigned to the storage servers according to the sequence to approximately balance the loads on the storage servers while maintaining the base address for each data segment on an originally assigned storage server.

37. A computer readable media comprising computer code for implementing a method of hashing an address space to a plurality of storage servers, the method of hashing the address space to the plurality of storage servers comprising the steps of:

dividing the address space by a number of the storage servers to form data segments, each data segment comprising a base address;

assigning the data segments to the storage servers according to a sequence;

measuring a load on each of the storage servers;

for each storage server, determining whether a data share for the storage server needs to be decreased or increased to approximately balance the loads on the storage servers in order to identify at least one over-utilized storage server and at least one under-utilized storage server; and

proceeding through the storage servers according to the sequence and for each over-utilized storage server reassigning a portion of the data segment to at least one sequentially available under-utilized storage server while maintaining the base address on an originally assigned storage server.