Method for on-line reorganization of the data on a RAID-4 or RAID-5 array in the absence of one disk and the on-line restoration of a replacement disk

A method of on-line reorganization of data in a storage system having n+1 disks arranged in a RAID array when one of said disks fails while preserving concurrent access to said array by a user application, each of said disks in said storage system having a plurality of data blocks, a plurality of data block state bits, each data block state bit associated with one of said data blocks, and having a first state indicating that said associated data block may contain invalid information and a second state indicating that said associated data block contains valid information, a plurality of parity blocks, each parity block associated with n data blocks, a plurality of groups of parity block state bits, each group of parity block state bits indicating that said associated parity block contains parity information or data or the contents are undefined, and a group of array state bits indicating the condition of the array as "normal," "folding," "fully folded" or "unfolding," said method comprising the steps of:

• (a) receiving a read request from said user application to read a targeted data block;
• (b) inserting a replacement disk;
• (c) interrogating said array state bits to determine the state of said array;
• (d) if said array state bits indicate said array is in said "unfolding" state, then proceeding with an "unfolding" read operation and proceeding with a deliberate process to complete said reorganization concurrently with user application access to said array.

A method of on-line reorganization of data in a storage system having n+1 disks arranged in a RAID array when one of said disks fails while preserving concurrent access to said array by a user application, each of said disks in said storage system having a plurality of data blocks, a plurality of parity blocks, each parity block associated with n data blocks, a plurality of groups of parity block state bits, each group of parity block state bits indicating that said associated parity block contains parity information or data or the contents are undefined, and a group of array state bits indicating the condition of the array as "normal," "folding," "fully folded" or "unfolding," said method comprising the steps of:

• (a) receiving a write request from said user application to write to a targeted data block;
• (b) interrogating said array state bits to determine the condition of said array;
• (c) if said array state bits indicate said array is in said "normal" state, then proceeding with a write operation;
• (d) if said array state bits indicate said array is in said "folding" state, then proceeding with a "folding" write operation;
• (e) if said array state bits indicate said array is in said "fully folded" state, then proceeding with a "fully folded" write operation;
• and
• (f) if said array state bits indicate said array is in said "folding" state, then also proceeding with a deliberate process to complete said reorganization concurrently with user application access to said array.

A method of on-line reorganization of data in a storage system having n+1 disks arranged in a RAID array when one of said disks fails while preserving concurrent access to said array by a user application, each of said disks in said storage system having a plurality of data blocks, a plurality of data block state bits, each data block state bit associated with one of said data blocks, each data block state bit having a first state indicating that said associated data block may contain invalid information and a second state indicating that said associated data block contains valid information, a plurality of parity blocks, each parity block associated with n data blocks, a plurality of groups of parity block state bits, each group of parity block state bits indicating that said associated parity block contains parity information or data or the contents are undefined, and a group of array state bits indicating the condition of the array as "normal," "folding," "fully folded" or "unfolding," said method comprising the steps of:

• (a) receiving a write request from said user application to write to a targeted data block;
• (b) inserting a replacement disk;
• (c) interrogating said array state bits to determine the state of said array;
• (d) if said array state bits indicate said array is in said "unfolding" state, then proceeding with an "unfolding" write operation and proceeding with a deliberate process to complete said reorganization concurrently with user application access to said array.

A method for the replacement of a recently failed disk in a storage system having n+1 disks arranged in a RAID array, each of said disks in said storage system having a plurality of data blocks, a plurality of data block state bits, each data block state bit associated with one of said data blocks, and having a first state indicating that said associated data block may contain invalid information and a second state indicating that said associated data block contains valid information, a plurality of parity blocks, each parity block associated with n data block, a plurality of groups of parity block state bits, each group of parity block state bits indicating that said associated parity block contains parity information or data or the contents are undefined, and a group of array state bits indicating the condition of the array as "normal," "folding," "fully folded" or "unfolding," said method comprising the steps of:

• (a) detecting a failed disk;
• (b) removing said failed disk from the array;
• (c) setting all parity block status bits to said undefined state on said failed disk;
• (d) setting to said invalid state all status bits of data blocks having associated parity block status bits in said data or undefined state on said failed disk;
• (e) inserting said failed disk into said array;
• and
• (f) setting said array state bits from folding to unfolding state.