Balancing Throughput And Fairness Of Storage Devices In A Multi-Client Environment

Abstract

In a computer system where multiple client computers share use of a storage device, submission priorities for input-output commands from the computers are adjusted when one or more of the client computers exceeds its quota of usage. The submission priorities for the client computers which are exceeding their quota are reduced relative to submission priorities for client computers which are not exceeding their quotas. This allows up to full usage of the processing capacity of the storage device, while minimizing effects such as unfairness and latency experienced by the other client computers.

1 . A method of processing requests sent by a plurality of client computers, to a shared storage device having a processing load capacity, the method comprising:
 operating the storage device to fulfill the requests at different rates so that requests having higher submission priority are fulfilled at a greater rate than requests having lower submission priorities;   monitoring a measure of processing load represented by the requests sent by each client computer;   when the measures of loads for a first set of the client computers are above the processing load quotas for those computers, and the measures of loads for a second set of the client computers are less than or equal to the processing load quotas for those computers, assigning submission priorities to the requests according to a modified assignment scheme so that, as compared with the original priority assignment scheme, submission priorities for at least some of the requests from client computers in the first set are reduced relative to submission priorities for requests from client computers in the second set.   
     
     
         2 . The method of  claim 1  wherein, in the modified assignment scheme, at least some of the requests from client computers in the first set have submission priorities lower than provided in the original assignment scheme and requests from client computers in the second set have the same submission priorities as provided in the original assignment scheme. 
     
     
         3 . The method of  claim 1 , comprising, when the sum of the measures of loads for all of the client computers exceeds a total load threshold, throttling requests from the client computers of the first set. 
     
     
         4 . The method of  claim 1 , comprising, when the measures of loads for all of the client computers are less than or equal to processing load quotas for the client computers, assigning submission priorities to the requests according to an original priority assignment scheme. 
     
     
         5 . The method of  claim 4 , wherein operating the storage device to fulfill the requests at different rates comprises maintaining a plurality of submission queues, each submission queue having a submission priority, and wherein assigning submission priorities to requests includes directing requests to the submission queues. 
     
     
         6 . The method of  claim 5 , wherein each submission queue has a weighted round robin coefficient, the method including taking requests from the submission queues for fulfillment using a cyclic weighted round robin process, such that a number of submission requests taken form fulfillment during each cycle of the process is directly related to the weighted round robin coefficient of that submission queue. 
     
     
         7 . The method of  claim 5 , wherein the same set of submission queues is used in the original priority assignment scheme and in the modified priority assignment scheme, the method including changing the submission priority for at least one of the submission queues to change from the original assignment scheme to a modified assignment scheme. 
     
     
         8 . The method of  claim 5 , wherein each client computer sends requests to one or more client queues associated with that client computer, and directing requests to the submission queues includes directing requests from each client queue to a corresponding one of the submission queues. 
     
     
         9 . The method of  claim 8 , wherein the fulfilling comprises directing completion commands from the storage device into a set of completion queues so that a completion command generated upon fulfillment of a request taken from a given submission queue is directed into a completion queue corresponding to that submission queue, whereby the completion command for a request from a given input queue will be directed into a completion queue corresponding to that input queue. 
     
     
         10 . The method of  claim 1 , wherein the requests are input/output (TO) requests. 
     
     
         11 . A computer system, comprising:
 a storage device; and   a traffic controller arranged to:   monitor a measure of processing load represented by requests sent by each of a plurality of client computers;   when the measures of loads for a first set of the client computers are above the processing load quotas for those computers, and the measures of loads for a second set of the client computers are less than or equal to the processing load quotas for those computers, assign submission priorities to the requests according to a modified assignment scheme so that, as compared with the original priority assignment scheme, submission priorities for at least some of the requests from client computers in the first set are reduced relative to submission priorities for requests from client computers in the second set; and   direct the requests to the storage device so that requests having higher submission priority are fulfilled at a greater rate than requests having lower submission priorities.   
     
     
         12 . The computer system of  claim 11 , further comprising a set of submission queues, each said submission queue having an associated submission priority, and a sampler arranged to take requests for fulfillment by the storage device from each queue at a rate directly related to the submission priority associated with that queue, the traffic controller being operative to assign submission priorities to the requests by directing the requests to the submission queue. 
     
     
         13 . The computer system of  claim 12 , wherein the sampler is a weighted round robin sampler and the submission priority associated with each queue is a weighted round robin coefficient for that queue. 
     
     
         14 . The computer system of  claim 12 , wherein the traffic controller is operative to change the submission priority associated with at least one of the submission queues to change from an original assignment scheme to the modified assignment scheme. 
     
     
         15 . The computer system of  claim 11 , wherein when the measures of loads for all of the client computers are less than or equal to processing load quotas for the client computers, the traffic controller is operative to assign submission priorities to the requests according to an original priority assignment scheme. 
     
     
         16 . The computer system of  claim 15 , wherein when the sum of the measures of loads for all of the client computers exceeds a total load threshold, the traffic controller is operative to throttle requests from the client computers of the first set. 
     
     
         17 . A non-transitory computer-readable medium storing instructions executable by one or more processors for performing a method of processing requests sent by a plurality of client computers, to a shared storage device having a processing load capacity, the method comprising:
 operating the storage device to fulfill the requests at different rates so that requests having higher submission priority are fulfilled at a greater rate than requests having lower submission priorities;   monitoring a measure of processing load represented by the requests sent by each client computer;   when the measures of loads for a first set of the client computers are above the processing load quotas for those computers, and the measures of loads for a second set of the client computers are less than or equal to the processing load quotas for those computers, assigning submission priorities to the requests according to a modified assignment scheme so that, as compared with the original priority assignment scheme, submission priorities for at least some of the requests from client computers in the first set are reduced relative to submission priorities for requests from client computers in the second set.   
     
     
         18 . The non-transitory computer-readable medium of  claim 17 , wherein, in the modified assignment scheme, at least some of the requests from client computers in the first set have submission priorities lower than provided in the original assignment scheme and requests from client computers in the second set have the same submission priorities as provided in the original assignment scheme. 
     
     
         19 . The non-transitory computer-readable medium of  claim 17 , wherein, when the sum of the measures of loads for all of the client computers exceeds a total load threshold, the instructions further comprise throttling requests from the client computers of the first set. 
     
     
         20 . The non-transitory computer-readable medium of  claim 17 , comprising, when the measures of loads for all of the client computers are less than or equal to processing load quotas for the client computers, assigning submission priorities to the requests according to an original priority assignment scheme.