Data storage system and method of routing or assigning disk write requests among a set of disks using weighted available disk space values

• US 6,317,808 B1
• Filed: 03/26/1999
• Issued: 11/13/2001
• Est. Priority Date: 03/26/1999
• Status: Expired due to Term

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: ADC Telecommunications Incorporated (TE Connectivity Limited)
• Inventors: Berenshteyn, Yevgeniy
• Primary Examiner(s): Gossage, Glenn
• Application Number:
  US09/277,051
• Time in Patent Office: 963 Days
• Field of Search: 711/112, 711/114, 711/170, 710/39
• US Class Current: 711/112
• CPC Class Codes: G06F 3/0607 by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0674 Disk device

Abstract

A data storage system receives multiple data streams, such as a telephone messages, each of which are to be stored in a multidisk array. The data storage system generates a disk write request for each data stream. The disk write request is allocated to a disk in the multidisk array that has the highest weighted available space. The weighted available space of each disk is determined by the space availability of the disk and the load on the disk relative to other disks in the multidisk array. Optionally, the method used to allocate the disk space availability is dependent upon the disk write request load level. Thus, if the request load level is in a first load range, a least full assignment method is used, if the request load level is in a second range, a round robin method is used and if the request level is in a third range the weighted available space method is used.

Claims

1. A method of assigning a disk write request among a set of disks, comprising:

ranking each disk x_i in the set of disks by a number of disk write requests received since disk x_i was last assigned a disk write request;

assigning a weight factor to each disk x_i based upon the rank of disk x_i;

storing for each disk in the set of disks a respective available space value that is determined by an available disk space in that disk;

receiving a disk write request;

generating a weighted available space value for each disk in accordance with a predefined function of the respective available space value and the weight factor for the disk; and

assigning the disk write request to the disk having the highest associated weighted available space value.

2. The method of claim 1 wherein the Nth ranked disk is assigned a weight of (N−

1).

3. A method of assigning a disk write request among a set of disks, comprising:

associating a weight factor with each disk in the set of disks wherein a weight factor of zero is associated with disks that fall below a minimum threshold capacity available;

storing for each disk in the set of disks a respective available space value that is determined by an available disk space in that disk;

receiving a disk write request;

generating a weighted available space value for each disk in accordance with a predefined function of the respective available space value and the weight factor for the disk; and

assigning the disk write request to the disk having the highest associated weighted available space value.

4. A method of assigning a disk write request among a set of disks, comprising:

associating a weight factor with each disk in the set of disks wherein the weight factor associated with each disk is assigned according to the formula W_i=α

X_i+β

, wherein W_i is the weight factor assigned to the i^th disk in the set of disks, X_i is the total number of disk write requests that have been received since disk i last received a write request, and α and

β

are predefined, constant value coefficients;

storing for each disk in the set of disks a respective available space value that is determined by an available disk space in that disk;

receiving a disk write request;

generating a weighted available space value for each disk in accordance with a predefined function of the respective available space value and the weight factor for the disk; and

assigning the disk write request to the disk having the highest associated weighted available space value.

5. A method of assigning a disk write request among a set of disks, comprising:

associating a weight factor with each disk in the set of disks wherein the weight factor associated with each disk in the set of disks is assigned according to the formula;

6. The method of claim 5, further comprising:

after the assigning step, associating a new weight factor with each disk in the set of disks and then performing the receiving, generating and assigning steps for a next disk write request.

7. A method of assigning disk write requests to disks selected from a set of disks, comprising:

generating a disk request load value that corresponds to a quantity of disk write requests;

storing for each of the disks in the set of disks a respective available space value associated with available disk space in that disk;

selecting a first protocol for assigning disk write requests to disks in the set of disks when the disk request load value is below a first load threshold, the first protocol preferentially allocating disk write requests to disks solely in accordance with which disk in the set of disks has a highest respective available space value;

selecting a second protocol for assigning disk write requests to disks in the set of disks when the disk request load value is above a second load threshold, the second protocol allocating disk write requests to disks in round robin order; and

selecting a third protocol for assigning disk write requests to disks in the set of disks when the disk request load value is between the first and second load thresholds, the third protocol allocating disk write requests to disks in accordance with a predefined weighted available space function.

8. The method of claim 7, wherein each disk in the set of disks that is below a minimum threshold capacity of available space is removed from the set of disks.

9. The method of claim 7, wherein each disk in the set of disks that is below a minimum threshold capacity of available space is given a weight of zero.

10. The method of claim 7 wherein the predefined weighted available space function further comprises:

determining an available space of each disk in the set of disks;

allocating a disk access rank to each disk x in the set of disks based upon a number of disk write requests that have been received since a disk write request was last queued to disk x;

associating a weighted available space with each disk in the set of disks by multiplying the available space by the disk access rank; and

selecting the disk that has the highest weighted available space.

11. The method of claim 7, wherein the disk request load value is determined by an average number of requests received in a predetermined time interval over a predetermined number of such time intervals.

12. The method of claim 7, wherein the disk request load value is determined by a number of open message sessions that are being serviced by the set of disks.

13. The method of claim 7, wherein the disk request load is determined by a number of write requests that have been queued to the set of disks.

14. A data storage system, comprising:

a set of disks;

a control system for allocating disk write requests to a disk in the set of disks, the control system including;

a disk space monitor for determining storage space available on each of the disks in the set of disks and for storing, for each of the disks in the set of disks, a respective available space value associated with available disk space in that disk; and

a request router that;

receives a disk write request;

associates a weight factor with each disk in the set of disks, wherein the weight factor associated with each disk is determined by ranking each disk x_i in the set of disks by a number of disk write requests received since disk x_i was last assigned a disk write request and associating a weight factor to each disk x_i based upon the rank of disk x_i;

generates a weighted available space value for each disk in accordance with a predefined weighted available space function of (a) the available space on the disk and (b) the weight factor associated with the disk; and

assigns the disk write request to the disk having the highest weighted available space value.

15. A data storage system, comprising:

a set of disks;

a control system for allocating disk write requests to a disk in the set of disks, the control system including;

a disk space monitor for determining storage space available on each of the disks in the set of disks and for storing, for each of the disks in the set of disks, a respective available space value associated with available disk space in that disk; and

a request router that;

receives a disk write request;

associates a weight factor with each disk in the set of disks, wherein the request router ranks each disk x in the set of disks based upon a number of disk write requests that have been generated by the data storage system since a disk write request was last queued to disk x_i and associates a weight with each disk x_i based upon the rank of disk x_i;

generates a weighted available space value for each disk in accordance with a predefined weighted available space function of (a) the available space on the disk and (b) the weight factor associated with the disk; and

assigns the disk write request to the disk having the highest weighted available space value.

16. A data storage system, comprising;

a set of disks;

a control system for allocating disk write requests to a disk in the set of disks, the control system including;

a disk usage load monitor for generating a disk request load value that corresponds to a quantity of disk write requests being serviced by the set of disks; and

a request router that;

receives a disk write request;

assigns the disk write request according to a first protocol if the disk request load value is below a first load threshold, wherein the first protocol comprises assigning the disk write request in accordance with which disk in the set of disks has a highest respective available space value;

assigns the disk write request according to a second protocol if the disk request load is above a second load threshold, wherein the second protocol comprises assigning the disk write request in round robin order; and

assigns the disk write request according to a third protocol if the disk request load is above a first load threshold and below a second load threshold, wherein the third protocol comprises allocating the disk write request in accordance with a predefined weighted available space function.

17. A computer program product for use in conjunction with a computer system having a set of disks, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

a disk space monitoring module for determining an available space value for each of the disks in the set of disks and for storing for each of the disks in the set of disks a respective available space value that is determined by an available disk space in that disk; and

a request router module including instructions for;

receiving a disk write request;

ranking each disk x_i in the set of disks by a number of disk write requests received since disk x_i was last assigned a disk write request;

assigning a weight factor to each disk x_i based upon the rank of disk x_i;

generating a weighted available space value for each disk in accordance with a predefined function of (a) the available space value and (b) the weight factor for the disk; and

assigning the disk write request to the disk in the set of disks having the highest associated weighted available disk value.

18. A computer program product for use in conjunction with a computer system having a set of disks, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

a disk space monitoring module for determining an available space value for each of the disks in the set of disks and for storing for each of the disks in the set of disks a respective available space value that is determined by an available disk space in that disk; and

a request router module including instructions for;

receiving a disk write request;

ranking each disk x in the set of disks based upon a number of disk write requests that have been generated by the data storage system since a disk write request was last queued to disk x_i;

assigning a weight factor to each disk x_i based upon the rank of disk x_i;

generating a weighted available space value for each disk in accordance with a predefined function of (a) the available space value and (b) the weight factor for the disk; and

assigning the disk write request to the disk in the set of disks having the highest associated weighted available disk value.

19. The computer program product of claim 18, wherein a weight factor of zero is assigned to disks that fall below a minimum threshold capacity available.

20. A computer program product for use in conjunction with a computer system having a set of disks, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

a disk space monitoring module for determining an available space value for each of the disks in the set of disks and for storing for each of the disks in the set of disks a respective available space value that is determined by an available disk space in that disk; and

a request router module including instructions for;

receiving a disk write request,

assigning a weight factor to each disk in the set of disks;

generating a weighted available space value for each disk in accordance with a predefined function of (a) the available space value and (b) the weight factor for the disk; and

assigning the disk write request to the disk in the set of disks having the highest associated weighted available disk value;

wherein each disk is assigned a weight factor according to the formula W_i=α

X_i+β

, wherein W_i is the weight factor assigned to the ith disk in the set of disks, X_i is the total number of disk write requests that have been received since disk i last received a write request, and α and

β

are predefined, constant value coefficients.

21. A computer program product for use in conjunction with a computer system having a set of disks, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

a disk space monitoring module for determining an available space value for each of the disks in the set of disks and for storing for each of the disks in the set of disks a respective available space value that is determined by an available disk space in that disk; and

a request router module including instructions for;

receiving a disk write request,

assigning a weight factor to each disk in the set of disks;

generating a weighted available space value for each disk in accordance with a predefined function of (a) the available space value and (b) the weight factor for the disk; and

assigning the disk write request to the disk in the set of disks having the highest associated weighted available disk value;

wherein the weight factor assigned to each disk in the set of disks is assigned according to the formula;