Abstract:
A system for mapping between logical addresses and storage units of a plurality of storage volumes which comprise a storage system. For each volume, logical addresses are mapped to storage units using a volume mapping table. Each volume mapping table is comprised of a plurality of segments. Each segment need not be contiguously allocated to another segment of the same table. Thus, each volume mapping table can be independently expanded or reduced without affecting other volume mapping tables. A hash function, a hash table, a segment table, and a redundancy group descriptor table may also be used to help manage the segments of the volume mapping tables.

Description:
This application claims the benefit of U.S. Provisional Application No. 60/497,933, filed Aug. 27, 2003, the disclosure of which is herein incorporated by reference in its entirety. 

   FIELD OF INVENTION 
   The present invention relates to a load balancing storage system which optimizes storage volume and communication channel utilization. 
   BACKGROUND OF THE INVENTION 
   In conventional RAID storage systems, redundancy groups are established for any RAID type (i.e., RAID 0, RAID 5, “just a bunch of disks”(JBOD), etc.). Redundancy groups typically contain from one to sixteen drives and are chosen from the set of all available drives. The drives associated with a particular redundancy group need not be contiguous or in any special order. The stripe size for a particular redundancy group is configurable, and there may be an optional per drive logical block address (LBA) offset available. Redundancy groups may be linked to support mirroring to any other drive in the system, also known as N-way mirroring. Fixed cluster sizes enable mapping templates for the entire drive LBA space. In this manner, any physical drive LBA may be addressed by selecting the correct redundancy group and cluster to access. Furthermore, a single drive may belong to more than one redundancy group. Firmware resolves potential mapping conflicts by allocating clusters in one redundancy group that do not conflict with previously allocated clusters from another redundancy group. 
     FIG. 1  illustrates a flat system mapping table  100 , including a system mapping table  110  which holds cluster descriptors. Each cluster descriptor includes a pointer  150   a ,  150   b , . . . ,  150   c  to a particular redundancy group and a cluster number  160   a ,  160   b , . . . ,  160   c  corresponding to the cluster allocated to that redundancy group. Each volume is defined by a set of sequential cluster descriptors. The volume LBA contains a volume map pointer and a cluster offset. The volume map pointer, contained in the upper bits of the volume LBA, gives an offset from the base of the flat volume map to the correct volume cluster descriptor. The volume cluster descriptor contains the redundancy group pointer and the corresponding cluster number. The redundancy group pointer points to the correct redundancy group descriptor in the redundancy group descriptor table. Thus, for a flat map, the redundancy group descriptor, the cluster number, and cluster offset are all fed into a mapping engine to arrive at the physical drive address. 
   In a flat volume map, each volume map entry must reside within a contiguous block of memory; it is therefore difficult to expand a particular volume map. Expanding a volume map requires moving all subsequent volume maps farther down the table to accommodate the new, larger map. Defragmentation is then required to realign the memory table. Large volume maps may require pausing volume activity during the move, which creates system latency. Additionally, volume map table manipulation may require large metadata update operations, which are processor intensive and adversely affect system performance. 
   U.S. Pat. No. 5,546,558, entitled, “Memory System with Hierarchic Disk Array and Memory Map Store for Persistent Storage of Virtual Mapping Information,” hereinafter the &#39;558 patent, describes a data memory system that has a hierarchical disk array of multiple disks, a disk array controller for coordinating data transfer to and from the disks, and a RAID management system for mapping two different RAID areas onto the disks. The RAID management system stores data in one of the RAID areas according to mirror redundancy, and stores data in the other RAID area according to parity redundancy. The RAID management system then shifts or migrates data between the mirror and parity RAID areas on the disks in accordance with a predefined performance protocol, such as data access recency or access frequency. The data memory system also includes a memory map store embodied as a non-volatile RAM. The memory map store provides persistent storage of the virtual mapping information used by the RAID management system to map the first and second RAID areas onto the disks within the disk array. The RAID management system updates the memory map store with new mapping information each time data is migrated between mirror and parity RAID areas. 
   The method described in the &#39;558 patent uses the conventional flat volume mapping approach and therefore does not offer a solution to the latency problems caused by manipulating the memory map store each time data migrates in the system. The &#39;558 patent does not address defragmentation or system memory resource issues. Finally, the method described in the &#39;558 patent does not offer a mechanism for reducing the amount of data required in the memory map stores. 
   Therefore, it is an object of the present invention to provide a method of mapping volume tables that allows expandable volume maps with no system performance impact. 
   It is another object of this invention to provide a method of expanding volume maps without requiring defragmentation. 
   It is yet another object of this invention to provide a method of mapping volume tables such that large volume maps may be reduced in size in order to improve system performance. 
   It is yet another object of this invention to provide a method of mapping volume tables such that minimal metadata updates are required and system performance is not adversely impacted. 
   SUMMARY OF THE INVENTION 
   The present invention is directed to an apparatus and method for providing an efficient mechanism for mapping between logical addresses and storage units of a plurality of storage volumes which comprise a storage system. For each volume, logical addresses are mapped to storage units using a volume mapping table. Each volume mapping table is comprised of a plurality of segments. Each segment need not be contiguously allocated to another segment of the same table. Thus, each volume mapping table can be independently expanded or reduced without affecting other volume mapping tables. A hash function, a hash table, a segment table, and a redundancy group descriptor table may also be used to help manage the segments of the volume mapping tables. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The foregoing and other advantages and features of the invention will become more apparent from the detailed description of exemplary embodiments of the invention given below with reference to the accompanying drawings, in which: 
       FIG. 1  is a diagram of a conventional flat system volume mapping table.; 
       FIG. 2  is a diagram of a segmented system volume mapping table; 
       FIG. 3  is a diagram of the preferred embodiment segmented mapping function; and 
       FIG. 4  is a flow diagram of a method of using a segmented system mapping table. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   Now referring to the drawings, where like reference numerals designate like elements, there is shown in  FIG. 1  a diagram of a flat system mapping table  100  used in conventional storage controller architectures. Flat system mapping table  100  includes a system mapping table  110  that further includes a volume  1  map  120 , a volume  2  map  130 , and a volume n map  140 . (In general, “n” is used herein to indicate an indefinite plurality, so that the number “n” when referred to one component does not necessarily equal the number “n” of a different component). A detail  135  of volume  2  map  130  includes a redundancy group pointers  150   a    150   b , and  150   c , a cluster number  160   a , a cluster number  160   b , and a cluster number  160   c.    
   As mentioned previously, each volume map entry of flat system mapping table  100  is contiguous in memory. Therefore, in order to expand volume  2  map  130 , for example, all subsequent volume map entries including volume n map  140  must be shifted the required number of memory addresses, a new redundancy pointer must be added after redundancy group pointer  150   c , and a new cluster number must be added after cluster number  160   c  in volume  2  map  130 . The number of system processor cycles required to perform manipulations of flat system mapping table  100  is proportional to the number and size of volume map entries it contains. Therefore, the greater the number of entries and the larger each entry, the more processing time is required, leading to more system latency and lower system performance. 
     FIG. 2  shows a segmented system mapping table  200  that includes a system mapping table  210 . System mapping table  210  further includes a volume  1  map segment  9   220   a , a volume  2  map segment  3   220   b , a volume  6  map segment  6   220   c , a volume  2  map segment  2   220   d , a volume  2  map segment  1   220   e , and a volume n map segment m  220   n . These entries are shown as examples only and may have any label. A detail  230  of volume  2  map segment  2   220   d  includes a redundancy group pointer  240   a  with a corresponding cluster number  250   a , a redundancy group pointer  240   b  with a corresponding cluster number  250   b , and so on until volume  2  map segment  2   220   d  entry concludes with a redundancy group pointer  240   n  and a corresponding cluster number  250   n.    
   Because volume map segments need not be contiguous in system mapping table  210 , new volume map segment entries may be added to the end of system mapping table  210 . A hash function is used to correlate the new volume map entry with its associated volume number; thus, volume map segments need not be collocated in memory according to volume number. Furthermore, segmented mapping requires that no system mapping table  210  volume map segments need to be moved in memory in order to expand volume maps. 
   Each volume map segment is of a predetermined size and has a fixed number of entries. For example, in one exemplary embodiment, each volume map segment is 4 Kbyte in size. The size of each volume map segment may be any logical value depending on system needs and optimization. Because each volume map segment is the same size and holds the same number of entries, volume map segments may be deleted and reallocated without moving any other volume map segment. Therefore, no defragmentation is required and the processor does not need to perform any additional manipulation of system mapping table  210 . Additionally, segmented system mapping table  200  provides a means for processing smaller amounts of data, thus increasing system performance over the conventional method. That is, since new volume map segments are only created when required and deleted when no longer required, only those segments of a volume map table which correspond to allocated storage units need to be maintained in the storage system. Thus, for segmented approach of the invention requires a storage system to manage a lesser amount of volume mapping data as long as the storage units are not full. 
     FIG. 3  is a preferred embodiment of a volume mapping function  300  that includes a volume number  310  and a volume LBA  320 . Volume LBA  320  further includes a plurality of volume LBA upper bits  322 , a volume map segment offset  324 , and a cluster offset  326 . Volume mapping function  300  further includes a hash function  330  and a hash table  335 . The hash table  335  include entries comprising forward links  331   a ,  331   b , . . . ,  331   n . The hash table  335  is addressed by using a hash function  330  upon the volume number  310  and volume LBA upper bits  332 . The forward links  331   a ,  331   b , . . . ,  331   n  of the hash table  335  point to different entries of a system map segment table  340 . 
   The system map segment table  340  is another component of the volume mapping function  300 . Each entry of the system map segment table  340  includes a volume map segment pointer  341   a ,  341   b , . . . ,  341   n , a forward link  331   a ,  331   b , . . . ,  331   n , and a volume hash key  342   a ,  342   b , . . . ,  342   n . Each volume map segment pointer  341   a ,  341   b , . . . ,  341   n points to a segment of a volume mapping table. For example, volume map segment pointer  341   b  points to the segment  2  of the volume mapping table for volume  2   220   d . The volume map segment offset  342  is used to address a particular entry in a given segment of a volume mapping table. Each forward link  331   a ,  331   b ,. . . ,  331   n  points to another entry in the system map segment table  340  which corresponds to a next segment of the same volume mapping table. If there is no next segment, the forward link  331   a ,  331   b , . . . ,  331   n  is set to a predetermined value. The volume hash key  342   a ,  342   b , . . . ,  342   n  is used to store a same hash key produced by hash function  330  when addressing the corresponding entry in hash table  335 . 
   Each segment of a volume mapping table include entries each of which includes a redundancy group pointer  240   a ,  240   b , . . . ,  240   n  and a respective cluster number  250   a ,  250   b , . . . ,  250   n . The volume mapping function  300  further include a redundancy group descriptor table  350 . Each entry of the redundancy group descriptor table  350  includes a redundancy group descriptor  351   a ,  351   b , . . . ,  351   n . Additionally, volume mapping function  300  includes a mapping engine  365  and a plurality of disk drive commands  370 . 
   When a volume expands, a new segment is added to system map segment table  340 , including volume map segment pointer  341   n , forward link  331   n , and volume hash key  342   n . The corresponding forward link  331   n  to the new entry is added to hash table  335 . As segments are deleted, hash table  335  deletes the corresponding forward link. 
   System map segment table  340  holds volume segment map pointers to specific volume map segments, as well as forward links and volume hash keys. In this example, volume map segment pointer  341   b  points to volume  2  map segment  2   220   d . Using volume map segment offset  324 , the controller is able to find redundancy group pointer  240   b  and cluster number  250   b . Redundancy group pointer  240   b  points to redundancy group descriptor  351   n  in redundancy group descriptor table  350 . 
   Mapping engine  365  resolves redundancy group descriptor  351   n , in combination with cluster number  250   b  and cluster offset  326 , into disk drive commands  370 , which are in turn sent to the storage element controllers. 
     FIG. 4  is a flow diagram of a segmented volume mapping method  400 . 
   Step  410 : Receiving volume LBA and volume number 
   In this step, the system controller (not shown) resolves a host request into volume number  310  and volume LBA  320 . Method  400  proceeds to step  420 . 
   Step  420 : Performing Hash Function 
   In this step, the hash function  330  is applied to the volume number  310  and volume LBA upper bits  322  of volume LBA  320 . The result of the hash function  330  is used as an index to locate an entry in the hash table  335  having a forward link  331   n  which points to the correct volume map segment pointer  341   b  in system map segment table  340 . It should be noted that in large storage systems may have large volume mapping tables. In such systems, the volume mapping table may be implemented as a swappable table, that is, if the volume mapping table is sufficiently large, only a portion of the volume mapping table is resident and the remainder of the table may be swapped to another storage medium, where it can be retrieved when needed. Under such circumstances, when a new segment is created, an existing segment of the volume mapping table will need to be swapped out to the another storage medium. A least recently used (LRU) technique may be used to govern which portion of the volume mapping table is swapped to the another storage medium when required. Method  400  proceeds to step  430 . 
   Step  430 : Resolving Volume Map Segment 
   In this step, volume map segment pointer  341   b  points to the correct volume map segment, which is volume  2  map segment  2   220   d  in this example. Cluster offset  326  from volume LBA  320  is used to find redundancy group pointer  240   b  and cluster number  250   b . Method  400  proceeds to step  440 . 
   Step  440 : Resolving Redundancy Group Descriptor 
   In this step, redundancy group pointer  240   b  links to redundancy group descriptor  351   n  in redundancy group descriptor table  350 . Redundancy group descriptor  351   n  is fed to mapping engine  365 . Method  400  proceeds to step  450 . 
   Step  450 : Resolving Physical Address for Disk Drive(s) 
   In this step, mapping engine  365  uses information from redundancy group descriptor  351   n , cluster number  250   b  from volume  2  map segment  2   220   d , and cluster offset  326  from volume LBA  320  to resolve the physical disk address and commands. Mapping engine  365  then sends disk drive commands  370  to the corresponding drive(s). Method  400  ends. 
   Thus, the present invention provide for an apparatus and mechanism for efficiently mapping between logical addresses and storage units in a storage system. The invention may be practiced in any storage system having a plurality of storage volumes, including, for example, stand alone disk array storage systems, network attached storage (NAS) systems, storage area networks (SANs), and storage routers. 
   While the invention has been described in detail in connection with the exemplary embodiment, it should be understood that the invention is not limited to the above disclosed embodiment. Rather, the invention can be modified to incorporate any number of variations, alternations, substitutions, or equivalent arrangements not heretofore described, but which are commensurate with the spirit and scope of the invention. Accordingly, the invention is not limited by the foregoing description or drawings, but is only limited by the scope of the appended claims.