Method and System for Placement of Logical Data Stores to Minimize Request Response Time

Abstract

Logical data stores are placed on storages to minimize store request time. The stores are sorted. A store counter and a storage counter are each set to one. (A), (B), and (C) are repeated until the storage counter exceeds the number of storages within the array. (A) is setting a load for the storage specified by the storage counter to zero. (B) is performing (i), (ii), and (iii) while the load for the storage specified by the storage counter is less an average determined load over all the storages. (i) is allocating the store specified by the store counter to the storage specified by the storage counter; and, (ii) is incrementing the load for this storage by this storage's request arrival rate multiplied by an expected service time for the requests of this store. (iii) is incrementing the store counter by one. (C) is incrementing the storage counter by one.

1 . A method for placing a plurality of logical data stores on an array of storage devices such that store request time is minimized, comprising:
 allocating the logical data stores to the storage devices of the array such that request times of the logical data stores are minimized;   storing the logical data stores on the storage devices of the array as has been allocated,   wherein allocating the logical data stores to the storage devices of the array such that request times of the logical data stores are minimized comprises:
 determining an average load over all the storage devices within the array; 
 sorting the plurality of logical data stores; 
 setting a logical data store counter equal to one; 
 setting a storage device counter equal to one; and 
 repeating setting a load for the storage device specified by the storage device counter equal to zero; 
   while the load for the storage device specified by the storage device counter is less the average load over all the storage devices within the array:
 allocating the logical data store specified by the logical data store counter to the storage device specified by the storage device counter; 
 incrementing the load for the storage device specified by the storage device counter by a request arrival rate of the logical data store specified by the logical data store counter multiplied by an expected service time for the requests of the logical data store specified by the logical data store counter; 
 incrementing the logical data store counter by one; and 
 incrementing the storage device counter by one, until the storage device counter exceeds a number of the storage devices within the array, 
   wherein determining the average load over all the storage devices within the array comprises:
 for each logical data store, determining a product of the request arrival rate of the logical data store multiplied by the expected service time for the requests of the logical data store; 
 determining a summation of the products determined for the logical data stores; and 
 dividing the summation by a number of the logical data stores to yield the average load over all the storage devices within the array, 
   wherein the request arrival rate of a logical data store specifies a rate at which requests to the logical data store arrive at the logical data store,   wherein the expected service time for the requests of a logical data store corresponds to an expected time of delay between the request being submitted to the disk from the queue, to it being served by the disk to which the logical store is assigned,   wherein sorting the plurality of logical data stores comprises sorting the plurality of logical data stores by run length,   wherein sorting the plurality of logical data stores comprises sorting the plurality of logical data stores by disk run length,   wherein the run length of a logical data store corresponds to an expected number of consecutive requests the logical data store that are served and access locations on the storage devices that are close to one another,   wherein the expected service time of each request corresponds to an expected time of delay between the request being submitted to the disk from the queue, to it being served by the disk to which the logical store is assigned,   wherein sorting the plurality of logical data stores comprises sorting the plurality of logical data stores by expected second moment of service time,   wherein the expected second moment of service time of a logical data store corresponds to a second moment of an expected service time of each request of the logical data store, and   wherein each logical data store corresponds to an aggregated plurality of streams of requests to the logical data store.   
   
   
       2 - 20 . (canceled)