Abstract:
The present invention provides an architecture and method for increasing the performance and resource utilization of networked storage architectures by use of hardware-based storage element mapping. The architecture utilizes a customized programmable processing element to map host read or write commands to physical storage element commands. The present invention uses a plurality of data structures, such as tables, to map host read and write commands to physical storage elements. The hardware-based storage element mapping controller uses the tables, including a mapping segment descriptor table, to map from global address space addresses to physical storage element addresses.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is related to U.S. application Ser. No. 09/716,195, filed Nov. 17, 2000, the disclosure of which is herein incorporated in its entirety by reference, and claims the benefit of U.S. Provisional Application No. 60/404,136, filed Aug. 19, 2002. 
    
    
     FIELD OF THE INVENTION 
     The present invention relates to a mapping system for networked storage systems. 
     BACKGROUND OF THE INVENTION 
     With the rapidly accelerating growth of Internet and intranet communication, high-bandwidth applications (such as streaming video), and large information databases, the need for networked storage systems has increased dramatically. Of particular concern is the performance level of networked storage, especially in high-utilization and high-bandwidth use models. A key determinant in the performance of a networked storage system is the function of mapping data to storage elements. 
     Conventional network storage system architectures rely heavily on software implementation of mapping techniques. Unfortunately, software-mapping approaches significantly limit system flexibility and performance. Hardware-mapping approaches have been developed to address these performance limitations. Such a system is described in U.S. Pat. No. 6,195,730, entitled, “Computer System With Storage Device Mapping Input/Output Processor,” which is hereby incorporated by reference. However, conventional hardware-mapping implementations such as disclosed in U.S. Pat. No. 6,195,730, do not allow for the level of complex mapping functions that can fully maximize networked storage system performance and resource utilization. 
     SUMMARY OF THE INVENTION 
     The present invention provides an architecture and method for hardware-based storage element mapping. The invention provides an increased number of networked storage system mapping functions per second and increases the flexibility of hardware-based networked storage system mapping. The invention also enables logical volumes that are independent of physical volume size. 
     The architecture of the present invention utilizes a customized programmable processing element to scan for available mapping segment descriptors (MSDs) upon receipt of a host data volume read or write request. A mapping engine then generates a set of parameters used to create a command list. Multiple logical volumes may be written across a single set of storage elements. Storage elements may include physical storage (e.g. hard disk drives) or virtualized storage. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is an exemplary architecture for a disk mapping controller (DMC) in accordance with the present invention. 
         FIG. 2  is an exemplary method for hardware-based networked storage mapping in accordance with the present invention. 
         FIG. 3  is an exemplary flow diagram of the disk mapping method of the present invention, including exemplary data structures. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The present invention is described more fully hereinafter with reference to the accompanying drawings, in which preferred embodiments of the invention are shown. The invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein; rather, these embodiments are provided so that this disclosure is thorough and complete, and fully conveys the scope of the invention to those skilled in the art. 
       FIG. 1  illustrates an exemplary networked storage mapping system architecture  100  used for hardware-accelerated storage element mapping functions. Networked storage mapping system architecture  100  includes a CPU  150  and a storage element mapping controller  110 . Storage element mapping controller  110  includes a processing element  105 , a mapping segment descriptor (MSD) scan engine  120 , a MSD memory  130  and a mapping engine  140 . 
     Networked storage mapping system architecture  100  is an element within a larger computer system typically containing memory (not shown), fixed storage (not shown), and input and output functionality (not shown). In the preferred embodiment of the present invention, the storage element is a hard disk drive in a RAID system. Accordingly, storage element mapping controller  110  is a disk mapping controller (DMC)  110  in the preferred embodiment of the present invention. To enable the flow of data within networked storage mapping system architecture  100 , CPU  150  interfaces with processing element  105  of storage element mapping controller (DMC)  110 . MSD scan engine  120  interfaces with MSD memory  130  and processing element  105 . Mapping engine  140  also interfaces with processing element  105 . 
     As described more fully hereinafter, MSDs map portions (segments or “slices”) of storage elements (e.g., disks)—up to and including entire storage elements. 
     In operation, a request to read or write a logical volume is submitted to storage element mapping controller  110  from CPU  150 . Processing element  105 , which is a customized programmable processor with a RISC-like instruction set, determines the starting MSD number for the logical volume. In the present invention, a range of one to thirty-two MSDs is allowed per logical volume. Processing element  105  accesses from MSD memory  130  a table of all MSDs available on networked storage mapping system architecture  100 , as well as the LBA range that is the target of the read or write command submitted from CPU  150 . The MSD table and LBA range are input into MSD scan engine  120 , which identifies the MSDs that contain the LBA range, in accordance with a predefined granularity, and outputs to processing element  105  all of the MSDs that contain the LBA range being sought by the read or write command. By defining two or more MSDs with overlapping LBA ranges, a mirror is created. 
     Based on the MSDs chosen above (for a read command) or the MSDs being written to (for a write command), mapping engine  140  receives from processing element  105  the LBA range, the mapping type (that is, concatenation, striping, and/or mirroring, or striping with parity), the number of available storage element partitions, and the stripe size. Concatenation indicates a group of disks/storage elements that are not set up as any type of striping or parity configuration. Striping is storage element striping only, which interleaves data across multiple storage elements for better performance. Mirroring is storage element mirroring, in which data is duplicated across two or more storage elements for redundancy. Striping with parity indicates a method in which data is striped across three or more drives for performance, and parity bits are used for fault tolerance. 
     Based on the received parameters, mapping engine  140  calculates the read or write ranges for the storage element. In other words, mapping engine  140  converts a single contiguous logical volume into multiple smaller volumes on multiple storage elements. Mapping engine  140  then outputs a set of parameters used to create specific storage element commands. Processing element  105  converts the parameters into actual storage element commands and generates a list of storage element commands and parity operations, which are then utilized to combine data on the identified storage elements. 
     The following modifiers are supported in the MSD structure: 1) a defective storage element modifier, which is used to mark individual storage elements as defective when a volume is degraded; and 2) an initialize modifier, which is used to effect integrity in the operation of read and write operations. 
       FIG. 2  illustrates a method of hardware-based networked storage mapping, including the following steps: 
     Step  210 : Receiving Read/Write Command 
     In this step, a request to read or write a logical volume is received by processing element  105  of storage element mapping controller  110  from CPU  150 . 
     Step  220 : Determining Starting MSD Number and Count 
     In this step, processing element  105  determines the starting MSD number for the logical volume. Processing element  105  also determines the MSD count from a table stored on MSD memory  130 . In the present invention, a range of up to 32 MSDs is allowed per logical volume. 
     Step  230 : Determining LBA Range 
     In this step, processing element  105  retrieves from MSD memory  130  a table of all MSDs available on networked storage mapping system  100 . Processing element  105  also determines the LBA range that is the target of the read or write request received from CPU  150 . One MSD may completely cover a given LBA range or multiple MSDs may be combined to achieve full coverage of the LBA range. 
     Step  240 : Identifying MSDs That Contain the LBA Range 
     In this step, the MSD table and the LBA range are input into MSD scan engine  120 , which identifies the MSDs that contain the LBA range determined in step  230 , in accordance with a pre-defined granularity, and outputs to processing element  105  all of the MSDs that contain the LBA range being sought by the read or write command. The granularity of each MSD (as measured with respect to the number of LBAs) is measured as power-of-two sectors. For example, an MSD may be one megabyte in size, but may not be one-half of a megabyte. In another example, an MSD may be 32 or 33 megabytes in size (but not 32½ megabytes) for a granularity of 1 megabyte. Any given volume may violate these power-of-two boundaries. When this violation occurs, the volume scan is done in two steps: the portion of the volume on one side of the power-of-two boundary is scanned first, and the portion of the volume on the other side of the power-of-two boundary is scanned second. For example, for 32½ megabytes, the 32 megabytes would be scanned first and the ½ megabyte would be scanned second. These scans are then processed separately by processing element  105 . 
     Step  250 : Inputting MSDs and Parameters to Mapping Engine 
     In this step, mapping engine  140  accepts as input from processing element  105  the LBA range determined in step  230 , the MSDs that contain the LBA range (identified in step  240 ) and the mapping type (that is, concatenation, striping, and/or mirroring, or striping with parity). 
     Step  260 : Calculating Storage Element Read or Write Ranges 
     In this step, mapping engine  140  calculates the read or write ranges for the storage element. In other words, mapping engine  140  converts a single contiguous logical volume to multiple smaller volumes on multiple storage elements. Mapping engine  140  then outputs a set of parameters used to create storage element commands. 
     Step  270 : Generating List of Storage Element Commands and Parity Operations 
     In this step, processing element  105  formats the parameters output from mapping engine  140  in step  260  into actual storage element commands and generates a list of storage element commands and parity operations, which are then utilized to combine data on the identified storage elements. This step is supported by microcode in processing element  105  of storage element mapping controller  110 . 
       FIG. 3  is an exemplary implementation of the present invention to effect mapping host read and write commands in a RAID system  400 . A read or write command is received and includes a host identification number and a logical unit number (LUN), which are used to determine, via HostToVolumeMapTable  405 , a volume number  420 . The volume number is then used as an index into another table of volume descriptors, namely VolumeInfoTable  410 . Each of the entries of the VolumeInfoTable  410  describes a volume including a starting LBA of the particular volume, the length/size/count of the particular volume in terms of logical block addresses (LBAs) and the first mapping segment descriptor (MSD)  425  associated with the particular volume. The starting LBA and the count/length map the volume to a location which starts at the starting LBA and ends at the starting LBA plus volume span/count/length. 
     The first MSD is a pointer to a MSD table  415 . Each of the entries  430  in the MSD table  415  include the segment starting LBA, the segment length/count/span, the RAID type, the number of members/drives and the starting drive physical/disk LBA offset. The segment starting LBA and the segment span/count map the segment to a location which starts at the segment starting LBA and ends at the segment starting LBA plus the segment span/count/length. 
     Two examples of the use of the above described structure follow. In the first example, assume using HostToVolumeMapTable  405  that the host identification number and LUN map to logical volume 3 (VOL 3)  420   a  where VOL3  420   a  starts at global LBA (GLBA) 2000 and has a length of 1000 LBAs. Using the Volume Info Table  410 , it is determined that VOL3  420   a  comprises MSD4  425   a , MSD5  425   b  and MSD6  425   c . MSD4  425   a  and MSD5  235   b  each span 600 LBAs and MSD6  425   c  spans 400 LBAs. Since MSD4  425   a  and MSD5  425   b  have overlapping LBAs, a mirror for these segments is created. MSD4  425   a  and MSD5  425   b  each, therefore, start at GLBA 2000 with a count/span of 600 LBAs, ending at GLBA 2599. MSD6  425   c  starts at GLBA 2600 with a span/count of 400 LBAs ending at GLBA 2999. MSD4  425   a  and MSD5  425   b  are each a RAID 0 set with four disk drives each forming a segment of size 600 LBAs. MSD6  425   c  is a RAID 5 set with three disk drives forming a segment of 400 LBAs. 
     In the second example, assume using the HostToVolumeMapTable  405  that the host identification number and the LUN map to VOL5  420   b , where VOL5  420   b  starts at GLBA 4000 and spans 1000 LBAs. Using the VolumeInfoTable  410 , it is determined that VOL5  420   b  comprises MSD7  425   d , which spans 1000 LBAs. MSD7 is a RAID 5 set with six disk drives forming a segment of 1000 LBAs. 
     Although the present invention has been described in relation to particular embodiments thereof, many other variations and modifications will become apparent to those skilled in the art. Therefore, the present invention is to be limited not by the specific disclosure herein, but only by the appended claims.