Method of hashing address space to storage servers

• US 7,823,156 B2
• Filed: 02/03/2005
• Issued: 10/26/2010
• 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.
• Primary Examiner(s): Bullock, Jr.; Lewis A
• Assistant Examiner(s): LEE, TAMMY EUNHYE
• Application Number:
  US11/051,436
• Publication Number:
  US 20060236073A1
• Time in Patent Office: 2,091 Days
• Field of Search: 711/114, 711/202, 711/216, 709/223, 718/105, 718/104
• US Class Current: 718/105
• 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;

measuring a load on each of the storage servers, wherein measuring the load on each of the storage servers comprises computing a weighted aggregate of outstanding read and write requests, wherein the load comprises a cumulative load which comprises an aggregate of an instantaneous load taken at time intervals over a time period;

adjusting data shares assigned to the storage servers to approximately balance the loads on the storage servers while maintaining the base address for each data segment on a corresponding originally assigned storage server, wherein adjusting the data share for each of the storage servers comprises calculating an adjusted data share for each of the storage servers based on an existing data share of the corresponding storage server, and on the load of the corresponding storage server; and

moving at least a portion of at least one of the data segments between the storage servers in response to adjusting the data shares.

2. The method of claim 1 further comprising repeatedly 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 moving comprises moving 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 at least one data segment.

7. The method of claim 6 wherein a remainder of the at least one 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 at least one data segment.

8. The method of claim 4 wherein the moving comprises moving 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 further comprises measuring a response time of each of the storage servers.

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

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

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

dividing the address space into the data segments;

assigning the data segments;

measuring the load on each of the storage servers; and

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.

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 a 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, and a first-in-first-out 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 an assignment sequence;

measuring a load on each of the storage servers, wherein measuring the load on each of the storage servers comprises computing a weighted aggregate of outstanding read and write requests, wherein the load comprises a cumulative load which comprises an aggregate of an instantaneous load taken at time intervals over a time period;

for each of the storage servers, determining whether a data share for the corresponding 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;

for each of the storage servers for which the data share is to be decreased or increased, calculating the decreased or increased data share based on an existing data share for the corresponding storage server and the load of the corresponding storage server; and

proceeding through the storage servers according to the assignment sequence and for each over-utilized storage server reassigning a portion of a particular data segment on the over-utilized storage server to at least one sequentially available under-utilized storage server while maintaining the base address of the particular data segment on a corresponding 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 assignment sequence and for each over-utilized storage server reassigning the portion of the particular 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 particular data segment.

24. The method of claim 23 wherein a remainder of the particular 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 particular data segment.

25. The method of claim 21 wherein the step of proceeding through the storage servers according to the assignment sequence and for each over-utilized storage server reassigning the portion of the particular 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 aggregate of the instantaneous load comprises an averaged sum of an instantaneous load taken at time intervals over the time period.

29. The method of claim 19 wherein calculating the decreased or increased data share comprises:

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

summing the load difference and the existing data share.

30. The method of claim 19 wherein calculating the decreased or increased data share comprises:

subtracting a storage server load from an 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 the 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

calculating the decreased or increased 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.

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 a 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 non-transitory computer readable storage media comprising computer code that upon execution by a computer is 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;

measuring a load on each of the storage servers, wherein measuring the load on each of the storage servers comprises computing a weighted aggregate of outstanding read and write requests, wherein the load comprises a cumulative load which comprises an aggregate of an instantaneous load taken at time intervals over a time period;

adjusting data shares assigned to the storage servers to approximately balance the loads on the storage servers while maintaining the base address for each data segment on a corresponding originally assigned storage server, wherein adjusting the data share for each of the storage servers comprises calculating an adjusted data share for each of the storage servers based on an existing data share of the corresponding storage server, and on the load of the corresponding storage server; and

moving at least a portion of at least one of the data segments between the storage servers in response to adjusting the data shares.

37. A non-transitory computer readable storage media comprising computer code that upon execution by a computer is 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 an assignment sequence;

measuring a load on each of the storage servers, wherein measuring the load on each of the storage servers comprises computing a weighted aggregate of outstanding read and write requests, wherein the load comprises a cumulative load which comprises an aggregate of an instantaneous load taken at time intervals over a time period;

for each of the storage servers, determining whether a data share for the corresponding 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;

for each of the storage servers for which the data share is to be decreased or increased, calculating the decreased or increased data share based on an existing data share for the corresponding storage server and the load of the corresponding storage server; and

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