Method and apparatus for reducing processor operations when adding a new drive to a raid-6 drive group

[0002] 1. Technical Field

[0003] The present invention relates in general to mapping a group of disk drives in a storage subsystem of a data processing system and in particular to the striping of data segments across individual drives. Still more particularly, the present invention relates to the method of striping data segments when a new drive is added to the drive group.

[0004] 2. Description of the Related Art

[0005] Data processing systems store critical programs and data on magnetic disk drives for use during data processing. Often, the magnetic disk drives are large and only one drive is attached to the data processing system. Multiple disk drives are used to provide a more reliable and flexible data storage subsystem. In systems that require reliable access to the disk drives, the primary purposes for using multiple disk drives are for redundancy and to back up the primary storage drives. Storage subsystems with multiple drives can be a group of disk drives with no particular arrangement, or a configuration, with a specific controller, known as a disk array.

[0006] A disk array, which may also be referred to as a Redundant Array of Independent Drives (“RAID”) device, and is used with a data processing system to increase data availability, increase storage capacity, provide performance flexibility and increase data protection. A data processing system's storage capacity is increased by installing multiple smaller form factor drives on a data processing system. A special memory subsystem controller is used that allows all the drives to appear as one drive to the data processing system.

[0007] Performance of the memory transactions may be enhanced by spreading segments of data over the multiple drives and then allowing multiple drives to work on a single request at the same time. However, as the number of drives on a system increases, the likelihood of a drive failing increases. So, copying data to multiple locations increases safety of the data. Also, disk mirroring (copying an exact copy of one disk onto another) and various encoding schemes may be used to reduce the required redundancy.

[0008] RAID drive groups that have the data segments written in “stripes” (a continuous segment of data written to multiple drives), improve performance by mapping what the system believes are contiguous data segments across several physical drives. Data Striping is a physical mapping of data that is supported by most RAID classes (RAID 0, 1, 5 and 6). For example, in a five drive RAID device, when a system requests four contiguous data segments from a drive-group that supports data striping, the four data segments may actually be written to four different physical drives. The data, resident on four different drives, may be retrieved in a parallel operation which increases access and speed between the data processing system and the RAID device.

[0009] The problem with data striping is that since striping is a physical mapping of the data segments, adding a new drive to the drive group is fairly complex. Each data segment already present on the old drives must be remapped to a new position. For example, if a new drive is added to a five drive drive-group, then data segment 6, which exists on the first drive in the drive group hierarchy, must be copied to the first stripe on the new drive. Data segment 7, which exists on the second drive, must then be copied to the second segment on the first drive. This continues until all of the segments on all of the drives have been remapped to new positions.

[0010] If the drives are 4 gigabyte drives with 256K sized data segments, then the controller managing the drive group must issue over 142,000 commands to expand the 5 drive drive-group by one drive. During this time, the processor will be consumed with handling every read and write operation, and I/O throughput will essentially halt.

[0011] It would be desirable, therefore, to provide a method for reducing the number of transactions between the controller and the connected RAID device.

[0012] It would also be desirable, to provide a method that will the reduce the time required to install a new drive to a RAID subsystem.

[0013] It would be desirable further, to provide a method that will transfer the new drive installation functions to the RAID subsystem.

[0014] It is therefore one object of the present invention to provide a method that will reduce the number of transactions that take place between the RAID subsystem controller and the RAID device during the installation of a new drive.

[0015] It is another object of the present invention to provide a method that will reduce the time required to install a new drive to a RAID device by providing a management process to allow multiple drive processors to accomplish the installation.

[0016] It is yet another object of the present invention to provide a method that will transfer installation commands to the RAID device.

[0017] The foregoing objects are achieved as is now described. A new drive installation to a multiple drive, drive group begins with a start command issued by the drive group controller to a new drive. The command is then propagated to every other drive. A successful completion reply is propagated back to the first drive and then to the controller. The controller transfers managing control to the new drive and the new drive reads the first required data segment as determined by the algorithm “AN,” where A=the number of the data segment being read and N=the total number of drives in the drive group. For example, in a sixth drive addition to a five drive group, this is data segment six on drive one (A=first data segment to be read for the new drive and N=6 drives; 1(6)=6). The segment read by the new drive (drive six) is placed in the segment stack on the first drive (segment six of Drive 1 is read and Drive 1 places segment six on its segment stack). The operation is repeated with each drive in the RAID device, in order. All drives consider their segment stack to determine if they have locations to read. As a segment is read on a drive, the segment is placed into the drive's segment stack and removed from the source drive as the segment is written to the target drive. After a few operations, multiple drives are reading and writing segments to target drives in parallel. The access to the controller is minimal and the functions are taking place in parallel, thereby reducing the drive group transactions with the controller and speeding up the installation process.

[0018] The above as well as additional objects, features, and advantages of the present invention will become apparent in the following detailed written description.

[0019] The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself however, as well as a preferred mode of use, further objects and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein:

[0020] FIG. 1 depicts a high level block diagram of a data processing system with a RAID device in which a preferred embodiment of the present invention may be implemented;

[0021] FIGS. 2A-2D illustrates a five drive RAID device, in which a new drive is added, showing several example read and write operations in accordance with a preferred embodiment of the present invention;

[0022] FIG. 3 depicts a flow diagram for startup and transfer of command function between the RAID controller and the RAID device in accordance with a preferred embodiment of the present invention;

[0023] FIG. 4 illustrates a flow diagram for a method for adding a new drive to a RAID device in a data processing system in accordance with a preferred embodiment of the present invention; and

[0024] FIG. 5 depicts a flow diagram for the completion process and return of RAID device control to the data processing system's RAID device controller in accordance with a preferred embodiment of the present invention.

[0025] With reference now to the figures, and in particular with reference to FIG. 1, a high level block diagram of a data processing system 100 is depicted, in which a preferred embodiment of the present invention may be implemented. The exemplary embodiment depicted includes a host system (“host”) 102, internal bus 104 for communication between host 102 and controller 106 for controlling Redundant Array of Independent Drives (“RAID”) device 110, external bus 108 connected to controller 106 and RAID device 110. Included in the RAID device 110 is Drive 6112, a new drive to be installed. Host 102 communicates directly with controller 104 when accessing the data processing system 100 memory subsystem; in this instance, the RAID device 110. Controller 104 communicates the host 102 transactions to RAID device 110, whereas host 102 perceives RAID device 110 as a large, single drive. Controller 106 implements commands and data transfers in RAID device 110 to install new drive 112 in RAID device 110. Controller 106 may also install new drive 112 by implementing the procedure in accordance with a preferred embodiment of the present invention, as described in further detail below.

[0026] Referring to FIGS. 2A-2D, a RAID device in which a new drive is added showing several read and write operations in accordance with a preferred embodiment of the present invention is illustrated. FIG. 1 should be read together with FIGS. 2A-2D. Drives within RAID device 110 are labeled Drive 1, Drive 2, etc., through Drive 6. Data segments are stored on the drives in contiguous stripes. The stripes are designated Stripe 1, Stripe 2, etc. through Stripe 4, there being more stripes on the drives than are depicted here. Additionally, segment stacks are shown for each drive and are called segment_stack 1, segment_stack 2, etc., through segment_stack 6.

[0027] Due to the fact that there are many different drive types and command formats, generic function calls will be used to represent a command that is passed across external bus 108. The first command will be called start( ) and it will pass a single parameter. This parameter called “drive group,” will list every drive, by its address, that belongs to the striped list of drives. The order of the list is in reverse order of the drives in RAID device 110. For example, if RAID device 110 contains 5 drives, each with a drive address ranging from 1 to 5, a new drive will be located at drive address 6. The order of the drives in the RAID device 110, beginning with the new drive, should be 6, 5, 4, 3, 2, 1. The first drive in the drive group parameter should always be the new drive. When the start( ) command is received, every drive will compare its address to the first address in RAID device 110 to determine if it is the new drive.

[0028] Once the new drive, Drive 6 receives the start(drive group) command, Drive 6 will check to determine whether it is able to properly execute a stripe expansion. If it is able to execute a stripe expansion, Drive 6 will look at the drive group parameter list, and issue a start(drive group) command to the drive following Drive 6 in the drive group address list. In the five drive RAID device 110, controller 106 issues a start(drive group) command to Drive 6. Drive 6 then issues a start(drive group) command to Drive 5. This process continues until the start(drive group) command is issued to the last drive, in this case Drive 1, in RAID device 110.

[0029] When the last drive, Drive 1 in RAID device 110 receives the start(drive group) command, and verifies that it can execute a drive expansion, it will return a successful status to the calling drive, Drive 2. The calling drive, Drive 2, will receive the status, verify that Drive 2 was successful, and then return successful to its calling drive, Drive 3. This process continues until the first drive, Drive 6, in the drive group receives a successful reply, and it then returns a successful reply to the controller. If at any time a failed reply is returned to a drive, that failure will be propagated back to the managing controller for error recovery.

[0030] Once the first device returns successful, the drive expansion can begin. The expansion is accomplished by having every drive read its new segment from every other drive in parallel. Unfortunately, if every drive instantly issued read operations to other drives and write operations to itself, much of the data would be overwritten and destroyed.

[0031] The management technique employed by the present invention is a segment stack that is stored on every drive. This segment stack represents the list of segments that have been read from the drive. For example, when Drive 5 issues a read_segment( ) operation to Drive 4, Drive 4 will return the read data, and store the segment location onto Drive 4's segment stack. The stack operates as a First In, First Out (“FIFO”) queue and the address at the top of the stack indicates the next data segment that needs to be updated.

[0032] The segment stack is important because it regulates where a drive is allowed to read data. Every drive can only update a segment that is pulled off of its own segment stack. The one exception to this is the new drive that is being added. Since it does not contain any data, it can update any of its segments. This drive controls the entire process.

[0033] FIG, 2A depicts a data transfer operation by new drive, Drive 6. Controller 106 has transferred managing control of the RAID device to Drive 6 and Drive 6 issues a read_segment(6) command to Drive 1, previously the last drive in the RAID device drive group. Data segment six, read from Drive 1, Stripe 2, is the first segment on the second stripe and contiguous to data segment 5 on Drive 5. Drive 1 returns the read data to Drive 6, Stripe 1 and stores data segment 6 onto its segment stack.

[0034] FIG. 2B illustrates the first parallel data transfer in the data transfer process. Drive 1 issues a read_segment(7) operation to Drive 2. Drive 2 returns the read data and stores segment 7 onto its segment stack. Concurrently, Drive 6 is receiving data segment 12, after a read_segment(12) operation from Drive 6 to Drive 2. Drive 2 writes segment 12 to its segment stack.

[0035] FIG. 2C depicts a parallel data transfer between Drive 2, Drive 3 and Drive 6. Drive 2 transfers data segment 7 to Drive 1 and drops that segment from its segment stack. Segment 12 moves to the top position in the segment stack for Drive 2. Drive 2 receives data segment 8 from Drive 3 and Drive 3 writes segment 8 to its segment stack. At the same time, Drive 6 is receiving data segment 18 from Drive 3. Drive 3 then adds data segment 18 to its segment_stack.

[0036] FIG. 2D illustrates the next step in the process, three parallel data transfers between drives. Concurrently, Drive 6, Drive 4 and Drive 3 are transferring data segments. Drive 4, after receiving a read_segment(9) command, writes segment 9 to its segment stack. Concurrently, Drive 4 is transferring data segment 24 to Drive 6 and writing data segment 24 to the Drive 4 segment stack. Drive 2 is receiving data segment 13 from Drive 3. Thus, three operations in parallel by three drives are taking place at the same time.

[0037] With reference to FIG. 3, a high level flow diagram for startup and transfer of command functions between the RAID controller and the RAID device in accordance with a preferred embodiment of the present invention is depicted. The transfer function begins with step 300, which depicts a start command issued by the managing controller to the new drive being added to the group, Drive 6. The process continues in step 302, which illustrates Drive 6 determining whether it is able to execute a stripe expansion. If Drive 6 cannot execute a stripe expansion, the process then proceeds to step 304 which depicts Drive 6 signalling a failure to the controller. The process then passes to step 306, which illustrates error recovery done by the controller. If Drive 6 can execute a stripe expansion, the process instead proceeds to step 308, which illustrates Drive 6, having looked at the drive group parameter list issuing a start command to the drive following Drive 6 in the drive group address list. In this case, the drive following Drive 6 is Drive 5.

[0038] The process then proceeds to step 312, which depicts Drive 5 checking to see if it is able to execute a stripe expansion. If Drive 5 cannot execute a strip expansion, the process then proceeds to step 314, which illustrates Drive 5 sending a failure signal to Drive 6. The failure signal is then propagated back through Drive 6 and on to the controller which performs error recovery and reissues the start command. If instead, Drive 5 can execute a stripe expansion, the process then passes to step 316, which depicts Drive 5 sending a start command to Drive 4.

[0039] The process continues through each drive on to step 338, repeating the combination of steps until the last drive is reached, step 334. At this point, the final drive in the RAID device, Drive 1, verifies that it can execute a stripe expansion. The process proceeds to step 340, which illustrates Drive 1 sending a verify signal to Drive 2, indicating that Drive 1 can execute a stripe expansion. The process then proceeds to step 342, which depicts Drive 2 sending a verify signal to Drive 3 indicating that Drive 1 and Drive 2 can execute a stripe expansion. The process continues in step 330, which illustrates Drive 3 sending a verify signal to Drive 4 indicating Drive 1, Drive 3, and Drive 4 are able to execute stripe expansions.

[0040] Following the verify signal being received by Drive 5 and a subsequent verify signal sent by Drive 5 to Drive 6, the process proceeds to step 334, which depicts the controller transferring managing control to the new drive, Drive 6. The process then passes to step 346, which illustrates Drive 6 beginning the drive expansion.

[0041] Referring to FIG. 4, a flow diagram for a method for adding a new drive to a RAID device in a data processing system in accordance with a preferred embodiment of the present invention is illustrated. The process begins with step 400, which illustrates the new drive, Drive 6 reading segment 6 on Drive 1. The process then proceeds to step 402, which depicts Drive 6 placing segment 6 on Drive 6. At the same time, the process passes to both step 404 and 406 which depict: in step 404 Drive 1 reading segment 7 on Drive 2 and in step 406 Drive 6 reading segment 12 on Drive 2. The process passes next to step 408, which illustrates Drive 2 placing segment 7 on Drive 2's segment stack. Concurrently, the process proceeds to step 410, which depicts Drive 2 placing segment 12 on the Drive 2 segment stack behind segment 7. The process continues to step 412, which illustrates Drive 2 removing segment 7 on the Drive 2 segment stack.

[0042] The process then proceeds to step 416, which illustrates Drive 6 reading segment 18 on Drive 3. At the same time, the process passes to step 414, which depicts Drive 3 placing segment 8 and segment 18 onto the Drive 3 segment stack. As Drive 6 reads segment 18 on Drive 3, the process passes to steps 418, 422, and 424 in parallel. The process in step 418, illustrates Drive 6 reading segment 24 on Drive 4. Occurring at the same time, step 22, depicts Drive 3 reading segment 9 on Drive 4. Additionally, step 24 illustrates Drive 2 reading segment 13 on Drive 3. The process then passes to step 426, which illustrates the individual drives, Drive 3, Drive 2, and Drive 6 posting segments that have been read to the segment stack on each drive. The process then proceeds in parallel to step 428, step 430, step 432, and step 434. In this combination of steps, step 428 illustrates Drive 2 reading segment 14 on Drive 3. At the same time, in step 430, Drive 5 reads segment 11 on Drive 4. Drive 4 reads segment 10 on Drive 5 and in conjunction with step 428, step 430, and step 432, step 434, illustrates Drive 1 reading segment 13 on Drive 2.

[0043] As illustrated by the flow diagram in FIG. 4, the read and write instructions are occurring in a parallel manner. At a point in the process, every drive is sending read and write instructions to every other drive within the RAID subsystem with an instruction cascade effect. The command functions have been transferred to the new drive, reducing the number of instructions and transactions that involve the controller. Additionally, the instructions and transactions are taking place in parallel between the 6 drives and the controller is left out of the expansion except for polling the drives periodically.

[0044] Polling takes place to determine the most recent sector that has been updated. For all host requests that are at or below the updated sector, the controller will execute the host operation as if the drive group has completed the expansion. When it does so, it will mark a bit in the operation to indicate that the controller believes the command is a post-expansion command. If a drive receives a post-expansion command to a sector that has not yet been updated and is not on the segment stack, it will return the command with an error status. If the sector is on the segment stack, then the drive will queue the command up, in its segment stack, for completion after the sector has been updated. If the controller receives a command that needs to be directed to a sector that is above the address returned during a query, it sends the command to the pre-expansion configuration and marks the drive as a pre-expansion command. When the drive receives the command, it determines whether the sector the command is directed towards has been updated. If a sector has been updated or if the sector address is on the segment stack, then the drive will forward the command to the drive that contains the proper sector and act as the second drive's interface to the host.

[0045] Referring now to FIG. 5, a flow diagram for the completion process returning RAID device control to the data processing system's RAID device controller in accordance with a preferred embodiment of the present invention is depicted. The process begins at step 500, which depicts Drive 1 completing all the updates, where Drive 1 is the last drive in the RAID device storage subsystem. The process then proceeds to step 502, which illustrates Drive 1 sending a completion signal to Drive 2. The process next passes to step 504, which depicts Drive 2 confirming completion of its updates. Process then continues to step 506, which illustrates Drive 2 sending a completion signal to Drive 3. The process then passes to step 508, 510, 512, 514, 516, 518, and 520 which illustrates the process being repeated as in step 500, step 502, step 504, and step 506. Step 520 illustrates Drive 6 confirming completion of the updates. The process then passes to step 522, which depicts Drive 6 sending a completion signal to the controller. The process then concludes in step 524, which illustrates the drive controller receiving the completion signal and control passing back to the drive controller.

[0046] The method of the present invention reduces the number of transactions that take place between the RAID device controller and a RAID device (the method works equally on a non-RAID drive group and controller storage subsystem), during the installation of a new drive. It accomplishes this reduction in transactions by transferring the installation process from the controller to the new drive. In the prior art, installation is accomplished by the controller executing all of the functions necessary to transfer specific data segments on the various current drives to the new drive. The present invention removes most of the transactions from the controller, moving those to the new drive and leaving the controller to be more or less a monitor of the installation process. The method of the present invention reduces the time to install a new drive to a RAID device by allowing the individual processes to accomplish the installation. The installation is accomplished in parallel with each drive managing the rearrangement of the data segments on every other drive. This frees the controller from managing the rearrangement of the data segments.

[0047] The start command of the present invention provides a method to transfer installation commands from the controller to the RAID device. Commands are transferred to the new drive which initiates parallel transfer of data segments by all of the drives in the device.

[0048] While the invention has been particularly shown and described with reference to a preferred embodiment, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention.