Abstract:
A system and method for allocating storage devices within a database system including fast solid state storage devices (SSDs) and traditional hard drive storage device (HDDs). The method repetitively collects temperature and queue depth data for each storage device, and determines from the collected data points a service time for each storage device. The method then selects, in response to an allocation request, a storage device having a minimum total wait time determined from the current queue depth and service time for each storage device.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This application claims priority under 35 U.S.C. §119(e) to the following commonly-assigned patent applications, which are incorporated herein by reference: 
     Provisional Patent Application Ser. No. 61/582,280, entitled “IMPROVED SYSTEM AND METHOD FOR ALLOCATING RESOURCES IN A MIXED SSD AND HDD STORAGE ENVIRONMENT,” filed on Dec. 31, 2011, by Paul Rubio. 
    
    
     FIELD OF THE INVENTION 
     The present invention relates to data warehouse systems, and more particularly, to an improved system and method for allocating resources in a mixed SSD and HDD storage environment 
     BACKGROUND OF THE INVENTION 
     Solid state storage, in particular, flash-based devices either in solid state drives (SSDs) or on flash cards, is quickly emerging as a credible tool for use in enterprise storage solutions. Ongoing technology developments have vastly improved performance and provided for advances in enterprise-class solid state reliability and endurance. As a result, solid state storage, specifically flash storage deployed in SSDs, are becoming vital for delivering higher performance to servers and storage systems, such as the data warehouse system illustrated in  FIG. 1 . 
     The system illustrated in  FIG. 1 , a product of Teradata Corporation, is a hybrid data warehousing platform that provides the capacity and cost benefits of hard disk drives (HDDs) while leveraging the performance advantage of solid-state drives (SSDs). As shown the system includes multiple physical processing nodes  101 , connected together through a communication network  105 . Each processing node may host one or more physical or virtual processing modules, such as one or more access module processors (AMPs). Each of the processing nodes  101  manages a portion of a database that is stored in a corresponding data storage facility including SSDs  120 , providing fast storage and retrieval of high demand “hot” data, and HDDs  110 , providing economical storage of lesser used “cold” data. 
     Teradata Virtual Storage (TVS) software  130  manages the different storage devices within the data warehouse, automatically migrating data to the appropriate device to match its temperature. TVS replaces traditional fixed assignment disk storage with a virtual connection of storage to data warehouse work units, referred to as AMPs within the Teradata data warehouse.  FIG. 2  provides an illustration of allocation of data storage in a traditional Teradata Corporation data warehouse system, wherein each AMP owns the same number of specific disk drives and places its data on those drives without consideration of data characteristics or usage. 
       FIG. 3  provides an illustration of allocation of data storage in a Teradata Corporation data warehouse system utilizing Teradata Virtual Storage (TVS). Storage is owned by Teradata Virtual Storage and is allocated to AMPs in small pieces from a shared pool of disks. Data are automatically and transparently migrated within storage based on data temperature. Frequently used hot data is automatically migrated to the fastest storage resource. Cold data, on the other hand, is migrated to slower storage resources. 
     Teradata Virtual Storage allows a mixture of different storage mechanisms and capacities to be configured in an active data warehouse system. TVS blends the performance-oriented storage of small capacity drives with the low cost-per-unit of large capacity storage drives so that the data warehouse can transparently manage the workload profiles of data on the storage resources based on application of system resources to the usage. 
     Systems for managing the different storage devices within the data warehouse, such as TVS, are described in U.S. Pat. No. 7,562,195; and United States Patent Application Publication Number 2010-0306493, which are incorporated by reference herein. 
     Many of the prior systems for managing storage devices within a data warehouse were homogenous with respect to configured storage devices, e.g., HDDs, and allocations were placed on devices with the smallest queue depth. With the inclusion of SSDs and HDDs in the data warehouse, some of these systems may over-utilize the SSDs, while at the same time under utilize HDDs. A new method of answering allocation placement questions in systems comprised of different classes of SSD and HDD devices with devices shared amongst AMPs is desired. Described below is an improved system and method for allocating resources in a mixed SSD and HDD storage environment. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is an illustration of a multiple-node database system employing SSD storage devices and conventional disk storage devices. 
         FIG. 2  is a simple illustration of the allocation of data storage in a traditional Teradata Corporation data warehouse system. 
         FIG. 3  is a simple illustration of the allocation of data storage in a Teradata Corporation data warehouse system utilizing Teradata Virtual Storage (TVS). 
         FIG. 4  provides a flowchart illustrating background processes for allocating resources in a mixed SSD and HDD storage environment in accordance with the present invention. 
         FIG. 5  provides a flowchart illustrating extent allocation processes in accordance with the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The techniques described below provide a means for allocating a data extent having a temperature r n  to a storage device whose performance is impacted the least after the extent is allocated. Given a set of devices, each with a distinct service time (T ser ), arrival rate or temperature (r), and queue depth (L Q ), the next allocation with temperature (r n ) is placed on the device with the smallest amount of wait time. 
     The Teradata Virtual Storage (TVS) device allocation decision process described in U.S. Pat. No. 7,562,195 uses the following data which is collected by TVS:
         1. Response time—the amount of time between when an IO request enters a device&#39;s queue and when the request is answered. This is equivalent to the sum of the device queue wait time and the device&#39;s service time; and   2. Temperature—the number of access to a particular piece of data in a specific amount of time. This is equivalent to the arrival rate of requests for that data (assuming system equilibrium).       

     The TVS system currently doesn&#39;t update response metrics. Therefore, in order to make decisions, information must be derived based upon data that is updated in real-time. 
     On homogenous systems of the past, placing allocations on devices with the smallest queue depth would be sufficient. However, more recent systems comprised of different classes of SSD and HDD devices with devices shared amongst AMPs require better methods of answering allocation placement questions. To this end, the service time (T ser ) for each device is used to determine allocations. 
     The TVS system periodically collects queue depths about each device as well as the temperature, or arrival rate, that is allocated to each device. Given the collected set of data points (r i , L Q ), service time (T ser ) can be derived by the following method. 
     Beginning with the following equation from queuing theory:
 
 L   Q   ,=r*T   ser .
 
     This equation is of the form:
 
 y=bx+a.  
 
     Utilizing the mathematical procedure known as the method of least squares: 
     
       
         
           
             
               b 
               = 
               
                 
                   r 
                   PC 
                 
                 * 
                 
                   
                     σ 
                     
                       L 
                       Q 
                     
                   
                   
                     σ 
                     r 
                   
                 
               
             
             ; 
           
         
       
     
                 r   PC     =       Σ   ⁢           ⁢     Z     L   Q       ⁢     Z   r       n       ,         
or the Pearson correlation of r i , L Q , where Z L     Q    and Z r  are the standard scores of r i  and L Q ;
 
 a =  L Q   − b  r ;  
         σ r  and σ L     Q    are the standard deviations of r i  and L Q ; and     L Q    and  r  are the means.       

     The value of b in the above is of interest as it represents the value of T ser . 
     In addition to a device&#39;s service time, T ser , the device&#39;s current queue depth, as well as the impact to a device&#39;s queue depth of adding r 0  (placing an extent with temperature r 0  on the given device) must be included in allocation decisions. 
     If the average wait time of an IO at the end of a device&#39;s queue is T L     Q   =L Q T ser , then the additional amount of wait time as a result of allocating an extent to the device is: 
     
       
         
           
             
               
                 
                   
                     
                       
                         ⅆ 
                         
                           ⅆ 
                           r 
                         
                       
                       ⁢ 
                       
                         T 
                         
                           L 
                           Q 
                         
                       
                     
                     = 
                       
                     ⁢ 
                     
                       
                         ⅆ 
                         
                           ⅆ 
                           r 
                         
                       
                       ⁢ 
                       
                         ( 
                         
                           
                             L 
                             Q 
                           
                           ⁢ 
                           
                             T 
                             se 
                           
                         
                         ) 
                       
                     
                   
                   , 
                 
               
             
             
               
                 
                   
                     = 
                       
                     ⁢ 
                     
                       
                         ⅆ 
                         
                           ⅆ 
                           r 
                         
                       
                       ⁢ 
                       
                         ( 
                         
                           rT 
                           se 
                         
                         ) 
                       
                       ⁢ 
                       
                         T 
                         se 
                       
                     
                   
                   , 
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     Δ 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       rT 
                       ser 
                       2 
                     
                   
                 
               
             
           
         
       
     
     Therefore, an extent with Δr allocated to a device would cause the IO at the end of the queue to experience a total wait time of: 
                 ⇒       T     L   Q       +       ⅆ     ⅆ   r       ⁢     T     L   Q             =         L     Q   0       ⁢     T   ser       +     Δ   ⁢           ⁢     rT   ser   2           ,         
where L Q     o    is the device&#39;s current queue depth, and T ser  is the device&#39;s service time derived by least squares above.
 
     Given this derived data, an extent&#39;s allocation destination is determined by selecting the device that minimizes the above equation. 
     The improved method for allocating resources in a mixed SSD and HDD storage environment includes background processes, illustrated in  FIG. 4 , and allocation processes, illustrated in  FIG. 5 . These processes are outlined below. 
       FIG. 4  provides a flowchart illustrating background processes for allocating resources in a mixed SSD and HDD storage environment. As shown in step  410 , at very specific periods of time, the queue depths of every device on the system are reported to the TVS system. For each device, the data point (queue depth, temperature) is added to the global data set  430 . 
     Every new data point makes derivation more accurate. It is recommended that a new calculation be performed each time queue depths are reported. As shown in step  420 , the service time for each device is re-calculated each time queue depths are reported. 
     For each device, the TVS background process:
         Calculates the mean and then standard deviation of all queue depths;   Calculates the mean and the standard deviation of all temperatures; and   Calculates the Pearson correlation.       

     And for each data point the background process, the TVS background process:
         Calculates the standard score of queue depth and temperature given the means calculated above; and   Multiplies the standard scores together and adds it to the global standard score sum.       

     Finally, the background process divides the global standard score sum by the total number of data points collected, and divides the queue depth standard deviation by the temperature standard deviation and multiple by the Pearson correlation above. The result of this is the average service time, T ser . 
       FIG. 5  provides a flowchart illustrating the extent allocation process. As shown in step  510 , an allocation request is received with associated temperature. In step  520 , the allocation process will lookup Δr temperature from bookmarked temperatures based upon it&#39;s allocation characteristics, e.g., static hot would derive the ultra hot temperature value. 
     As shown in step  530 , for each device the allocation process:
         Calculates L Q0 T ser +ΔrT ser   2 , if the cache is spoiled; and   Selects the device if it has a lower value than previously discovered devices.       

     In step  540 , the selected device for allocation placement is returned. 
     The figures and specification illustrate and describe a new method for allocating resources in a mixed SSD and HDD storage environment. Data placement based upon real-time collected temperature and queue depth allows for improved utilization of storage resources. 
     Another use of the system and method described herein is for placement of data with very short longevities, such as spool. Currently spool is placed on SSDs by default. Production systems may encounter customer queries that consume large amounts of spool, overburdening SSD storage while leaving HDD storage idle, and thus hampering performance. This method can guard against this misallocation or storage resources by diverting spool allocations to alternate devices until it becomes beneficial again to use SSDs. 
     Additionally, future systems may contain different performance classes of SSD storage devices. The method of the present invention can insure workloads are distributed evenly among these devices of different sizes and performances. 
     On systems with shared devices, the method described herein can detect devices experiencing high loads, and begin placing new allocations on alternate devices. Additionally, this method can initiate migrations of data from devices identified as overburdened. 
     The foregoing description of the invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. 
     Additional alternatives, modifications, and variations will be apparent to those skilled in the art in light of the above teaching.