Patent Publication Number: US-8527467-B2

Title: Compression-aware data storage tiering

Description:
FIELD OF THE INVENTION 
     This invention relates generally to computer storage, and specifically to using file compressibility as a factor for data storage tiering. 
     BACKGROUND OF THE INVENTION 
     Data storage tiering (also referred to herein as data tiering) is a technique used to improve performance in storage systems comprising multiple tiers of storage devices. In data tiering, the storage devices can be assigned to different tiers based on performance of the storage devices (e.g., faster storage devices can be assigned to a first tier and slower devices can be assigned to a second tier). 
     Typically, frequently used data is migrated to tiers comprising faster storage devices, and infrequently used data is migrated to tiers comprising slower storage devices. Examples of storage devices for faster storage tiers include solid state disks (SSDs), faster (e.g., 15,000 revolutions per minute) rotating disks such as Serial Attached Small Computer System Interface (SAS) and Fibre Channel (FC) drives, and outer tracks of a rotating disk (On a rotating disk, the outer tracks of the disk typically access data faster than the inner tracks of the disk.) Examples of storage devices for slower storage tiers include slower (e.g., 7,500 revolutions per minute) rotating disks such as SATA drives, and the inner tracks of rotating disks. 
     Migrating frequently used data files to faster storage tiers can help reduce input/output (I/O) bottlenecks that may occur due to contention (e.g., for the data file, the storage device, or an I/O bus coupled to the storage device). Likewise, migrating less frequently used data files to slower tiers may not significantly impact performance, since there is typically no simultaneous contention for the file. Therefore, data tiering can help increase the performance of storage systems, while having a minimal cost impact. 
     The description above is presented as a general overview of related art in this field and should not be construed as an admission that any of the information it contains constitutes prior art against the present patent application. 
     SUMMARY OF THE INVENTION 
     There is provided, in accordance with an embodiment of the present invention a method, including assigning, to each tier in a storage system comprising multiple tiers, a respective range of priority scores, calculating a compression ratio for a file stored on one of the multiple tiers, calculating, using the compression ratio, a priority score for the file, and migrating the file to the tier whose assigned range of priority scores includes the calculated priority score. 
     There is also provided, in accordance with an embodiment of the present invention an apparatus, including a storage system comprising multiple tiers, and a processor configured to assign, to each of the tiers, a respective range of priority scores, to calculate a compression ratio for a file stored on one of the multiple tiers, to calculate, using the compression ratio, a priority score for the file, and to migrate the file to the tier whose assigned range of priority scores includes the calculated priority score. 
     There is further provided, in accordance with an embodiment of the present invention a computer program product, the computer program product including a non-transitory computer readable storage medium having computer readable program code embodied therewith, the computer readable program code including computer readable program code configured to assign, to each tier in a storage system comprising multiple tiers, a respective range of priority scores, computer readable program code configured to calculate a compression ratio for a file stored on one of the multiple tiers, computer readable program code configured to calculate, using the compression ratio, a priority score for the file, and computer readable program code configured to migrate the file to the tier whose assigned range of priority scores includes the calculated priority score. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The disclosure is herein described, by way of example only, with reference to the accompanying drawings, wherein: 
         FIG. 1  is a schematic pictorial illustration of a system configured to perform compression-aware data storage tiering, in accordance with an embodiment of the present invention; and 
         FIG. 2  is a flow diagram that schematically illustrates a method of performing compression-aware data storage tiering, in accordance with an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS 
     Overview 
     Data compression is a technique used to reduce the space required to store data files on storage devices. Data compression can help reduce the consumption of expensive resources, such as disk space (on devices such as solid state disks and rotating disks) and input/output (I/O) bandwidth. The design of data compression schemes can involve trade-offs among various factors, including the degree of compression, and the computational resources required to compress and uncompress the data. 
     In some instances (especially for files that can be compressed to a small fraction of their original size), data compression can increase the I/O performance of a storage device. The increased performance is due to the fact that the time required to retrieve uncompressed data from a storage device is typically greater than the time required to retrieve and uncompress compressed data. Likewise, the time required to store uncompressed data to a storage device is typically greater than the time required to compress and store the data. 
     Embodiments of the present invention provide methods and systems for including the compressibility of data as a factor when implementing data storage tiering in a storage system. In some embodiments, a priority score is calculated for each file in the storage system, and each of the storage tiers is assigned a respective range of priority scores. Based on their respective calculated priority scores, the files can be migrated (if necessary) to the appropriate storage tier. 
     In some embodiments, the priority score can be calculated based on the file&#39;s compressibility and usage frequency. As described supra, compressed data having a smaller storage footprint (i.e., than the corresponding uncompressed data) typically enjoys faster storage access times than non-compressed data. Therefore, migrating compressed data to faster storage may penalize less compressible data (typically having slower access times) that was migrated to slower storage tiers. Embodiments of the present invention can provide a level of fairness to less compressible data in the context of storage tiering by introducing a tunable parameter that enables storage tiering behavior to be based solely on usage frequency, solely on compressibility, or a combination of the two. 
     System Description 
       FIG. 1  is a schematic pictorial illustration of a storage system  20  configured to perform compression-aware data storage tiering, in accordance with an embodiment of the present invention. System  20  comprises a processor  22 , a memory  24 , and storage devices  26  and  28 , all coupled via a bus  30 . 
     The storage devices in system  20  are divided into two storage tiers, where each storage device is assigned to a tier based on the performance of the storage device. For example, tier  1  may comprise the faster storage devices and tier  2  may comprise the slower storage devices. Continuing the example, storage device  26  (i.e., tier  1 ) may comprise a solid state disk (SSD), and storage device  28  (i.e., tier  2 ) may comprise a rotating disk drive. While the configuration system  20  in  FIG. 1  shows a single storage device in each of the two storage tiers, a typical implementation of system  20  may include more than two storage tiers, with multiple storage devices in each of the storage tiers. 
     Processor  22  executes a storage tiering application  32  and a compression application  34  from memory  24 . Data stored on the storage devices can be stored as either compressed or non-compressed data. As described supra, in addition to typically requiring less space on the storage devices, storing compressed data can increase the performance of system  20 . Compression application  24  is configured to compress data to be written to a file  36 , and to uncompress data read from the file. In alternative configurations, the functionality of compression application  34  may be integrated into a hardware module (not shown) in system  20 . 
     In operation, storage tiering application  32  (discussed in further detail hereinbelow) calculates a priority score P for file  36  (plus any other files stored on storage devices  26  and  28 ), and compares the calculated priority score to a respective range of priority scores assigned to each of the storage tiers. In the example shown in  FIG. 1 , file  36  is initially stored in tier  1  (i.e., on storage device  26 ). If the calculated priority score within the range of priority scores assigned to tier  2  (i.e., storage device  28 ), then storage tiering application  32  can migrate file  36  to storage device  28  (as indicated by the arrow). 
     Processor  22  typically comprises a general-purpose computer configured to carry out the functions described herein. Software operated by the processor may be downloaded to the memories in electronic form, over a network, for example, or it may be provided on non-transitory tangible media, such as optical, magnetic or electronic memory media. Alternatively, some or all of the functions of the processor may be carried out by dedicated or programmable digital hardware components, or by using a combination of hardware and software elements. 
     As will be appreciated by one skilled in the art, aspects of the present invention may be embodied as a system, method or computer program product. Accordingly, aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit,” “module” or “system”. Furthermore, aspects of the present invention may take the form of a computer program product embodied in one or more computer readable medium(s) having computer readable program code embodied thereon. 
     Any combination of one or more computer readable medium(s) may be utilized. The computer readable medium may be a computer readable signal medium or a computer readable storage medium. A computer readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the computer readable storage medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device. 
     A computer readable signal medium may include a propagated data signal with computer readable program code embodied therein, for example, in baseband or as part of a carrier wave. Such a propagated signal may take any of a variety of forms, including, but not limited to, electro-magnetic, optical, or any suitable combination thereof. A computer readable signal medium may be any computer readable medium that is not a computer readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus, or device. 
     Program code embodied on a computer readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, or any suitable combination of the foregoing. 
     Computer program code for carrying out operations for aspects of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, Smalltalk, C++ or the like and conventional procedural programming languages, such as the “C” programming language or similar programming languages. The program code may execute entirely on the user&#39;s computer, partly on the user&#39;s computer, as a stand-alone software package, partly on the user&#39;s computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user&#39;s computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider). 
     Aspects of the present invention are described herein with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. These computer program instructions may also be stored in a computer readable medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks. 
     The computer program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus or other devices to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. 
     Data Storage Tiering 
     As described supra, embodiments of the present invention use compressibility as a parameter for a priority score for file  36 . Storage tiering application  32  can then use the calculated priority score to determine the appropriate storage tier for file  36 . Storage tiering application  32  can calculate the compressibility as a compression ratio C for file  36  as follows:
 
 C =(Compressed Size)/(Uncompressed Size)  (1)
 
     For example, if file  36  comprises  10  megabytes (MB) of uncompressed data that can be compressed to 2 MB, then C=0.2. The compression ratio of the file has a negative correlation to the compressibility of the file. In other words, higher calculated values of C for a given file item indicate lower compressibility, and vice versa. 
     Another parameter that can be used when calculating the priority score is a normalized usage frequency F (typically between 0 and 1) for file  36 . Storage tiering application  32  can calculate F from usage statistics that are regularly collected for file  36 , and for other files (not shown) in system  20 , over an observation period. 
     For example, if Max is the maximal number of times system  20  accesses any file (i.e., including file  36 ) over the observation period, Min is the minimal number of times system  20  accesses any file over an observation period, and Times is the number of times system  20  accesses file  36  over the observation period, then storage tiering application  32  can calculate the usage frequency F for file  36  as follows:
 
 F =(Times−Min)/(Max−Min)  (2)
 
     Higher values of F for a particular file indicate that during the observation period, system  20  accessed the particular file more frequently than other files in the system. Likewise, lower values of F for a particular file indicate that during the observation period, system  20  accessed the particular file less frequently than the other files in the system. 
     After calculating C and F, storage tiering application  32  can calculate a priority score P as follows:
 
 P=α*C +(1−α)* F   (3)
 
where α is a tunable parameter, (0≦α≦1), that sets a calculation weight for C and F. For example, If α=0, then P=F, and storage tiering application  32  can therefore determine the appropriate tier for file  36  solely based on usage statistics. On the other hand, if α=1, then P=C, and storage tiering application  32  therefore ignores all usage statistics, and can determine the appropriate tier for file  36  solely based on the compressibility of the file. If α is between 0 and 1, then data tiering application  32  can determine the appropriate tier for file  36  based on a combination of compressibility and usage frequency.
 
     Although Equation (3) shows a particular calculation for P using C and F, other calculations for a priority score based on the compressibility of file  36  can also be employed to implement embodiments of the present invention, and are thus considered to be within the spirit and scope of the present invention. 
       FIG. 2  is a flow diagram that schematically illustrates a method of performing compression-aware data storage tiering, in accordance with an embodiment of the present invention. In a first initialization step  40 , system  20  sets ranges of priority scores for storage device  26  (i.e., tier  1 ) and storage device  28  (i.e., tier  2 ). The ranges of priority scores for the storage devices are typically contiguous and non-overlapping numeric ranges. For example, the system  20  can set the priority score range for storage device  28  to between 0 and 0.30, and the priority score range for storage device  26  to between 0.31 and 1. 
     The system  20  can be adapted to utilize a default value or values for the priority score, or in an additional embodiment, the priority score may not be initially set. The system  20  can dynamically (automatically) calculate appropriate priority score ranges, or the system  20  may adjust the priority score ranges over time, for example as data compressibility and usage frequency may vary. In this manner, the applicable priority score or priority score range may also vary over time. As one of ordinary skill in the art will appreciate, various additional factors may be brought to bear in determining an appropriate priority score range by the system  20 . In an additional embodiment, a system administrator (not shown) may set ranges of priority scores. 
     In one embodiment, the system  20  assigns lower priority score ranges to lower performance storage tiers (e.g., tier  2 ), and higher priority score ranges to higher performance storage tiers (e.g., tier  1 ). In the configuration shown in  FIG. 1 , storage device  26  (i.e., tier  1 ) may comprise a solid state disk (SSD), and storage device  28  (i.e., tier  2 ) may comprise a rotating disk drive. Therefore (depending on α), storage tiering application  32  may store more highly compressed files (i.e., files with lower values of C) and/or less frequently used files (i.e., files with lower values of F) to storage device  28 , and less highly compressed files (i.e., files with higher values of C) and/or more frequently used files (i.e., files with higher values of F) to storage device  26 . 
     Including the compressibility of data as a factor in the calculation for P enables embodiments of the present invention to provide a level of fairness to less compressible data. Since more highly compressed data typically enjoys faster storage access times than less highly compressed data, storage tiering application  32  can store less compressible data in a higher performance storage tier (e.g., storage device  26 ), thereby providing faster storage access time to the less compressible data. 
     In a second initialization step  42 , the system sets a in order to control the behavior of storage tiering application  32 . In some configurations, as in previous step  40 , storage tiering application  32  can be configured to optimize the overall performance of system  20  by dynamically setting the priority score ranges and/or dynamically setting a value for α. In an additional embodiment, the system administrator may also set α. 
     In a first calculation step  44 , storage tiering application  32  calculates a compression ratio for file  36  using Equation (1). In a second calculation step  46 , storage tiering application  32  calculates usage frequency for file  36  using Equation (2), and in a third calculation step  48 , the storage tiering application calculates a priority score for the file, using the calculated compression ratio, usage frequency, and α as parameters for Equation (3). In a comparison step  50 , if file  36  is currently stored in the correct tier (i.e., the calculated priority score for the file is within the priority score range assigned to storage device currently storing the file), then the method terminates. However, if file  36  is not currently stored in the correct tier (i.e., the calculated priority score for the file is not within the priority score range assigned to storage device storing the file) then the method concludes with a migration step  52 , where data tier application  32  migrates the file to the correct tier (i.e., the storage tier whose assigned priority score range includes the calculated priority score). In the example shown in  FIG. 1 , storage tiering application  32  migrates file  36  from storage device  26  to storage device  28 . 
     The flowchart and block diagrams in the figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions. 
     It will be appreciated that the embodiments described above are cited by way of example, and that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the scope of the present invention includes both combinations and subcombinations of the various features described hereinabove, as well as variations and modifications thereof which would occur to persons skilled in the art upon reading the foregoing description and which are not disclosed in the prior art.