Method and apparatus for the on-line restoration of a disk in a RAID-4 or RAID-5 array with concurrent access by applications

• US 5,522,031 A
• Filed: 06/29/1993
• Issued: 05/28/1996
• Est. Priority Date: 06/29/1993
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Rollow, Alan, Ellis, Robert A., Malan, Steven J., Thiel, David W., Wells, Richard B.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): HUA, LY
• Application Number:
  US08/085,018
• Time in Patent Office: 1,064 Days
• Field of Search: 395/575, 395/425, 395/182.04, 395/182.05, 371/10.2, 371/13, 371/38, 371/10.1, 371/38.1, 371/40.2
• US Class Current: 714/6.22
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 2211/104 Metadata, i.e. metadata associated with RAID systems with parity
• CPC Class Codes: G11C 29/74 using duplex memories, i.e. using dual copies

Abstract

A storage system having a plurality of disks arranged in a RAID array with one of said disks being a replacement disk. A method and apparatus for restoring the contents of the replacement disk without interrupting concurrent access to the RAID array. An access request by a user application to a data block in the replacement disk results in regeneration and reconstruction of the accessed data block. In addition, the systematic reconstruction of data or parity blocks not yet accessed by the user application occurs by locating status bits associated with each data and parity block of the new disk.

Claims

1. In a storage system having n+1 disks arranged in a RAID array, a plurality of data blocks, a plurality of parity blocks, each parity block associated with n data blocks, a plurality of status bits, each status bit associated with one of said data blocks or said parity blocks, each status bit having a first state indicating that said associated block may contain invalid information and a second state indicating that said associated block contains valid information, a method of on-line reconstruction of a new disk replacing a failed disk in said array while preserving concurrent access to said array by a user application, comprising the steps of:

detecting a failed disk in said array;

removing said failed disk from said array;

preparing a new disk by setting all status bits to said first state;

adding said new disk to said array;

systematically reconstructing data or parity blocks with associated status bits in said first state and after each reconstruction of a data block or parity block, setting said associated status bit to said second state;

continuing said systematic reconstruction until all blocks on said new disk have been reconstructed;

receiving requests to access data blocks in said new disk from said user application;

writing data to said accessed data blocks in said new disk and setting said associated status bits to said second state whereby the most active portions of said new disk are reconstructed before other portions.

2. The method as set forth in claim 1 wherein said step of systematic reconstruction comprises the steps of:

(a) locating a status bit in said first state associated with a data or parity block on said new disk;

(b) reading the corresponding data or parity blocks from surviving disks need for regeneration;

(c) regenerating data or parity information for said new disk;

(d) writing said regenerated data or parity information to a block on said new disk;

(e) setting the status bits of said block containing said regenerated information to said second state;

(f) determining if all status bits associated with a data or parity block on said new disk have been processed;

(g) if a status bit remains unprocessed then repeating steps (a) through (g);

(h) if all said status bits have been processed terminating said method.

3. In a storage system having n+1 disks arranged in a RAID array, a plurality of data blocks, a plurality of parity blocks, each parity block associated with n data blocks, and status information associated with each of said data blocks or said parity blocks indicating that said associated block may contain invalid information or indicating that said associated block contains valid information, a method of on-line reconstruction of a new disk replacing a failed disk in said array while preserving concurrent access to said array by a user application, comprising the steps of:

detecting a failed disk in said array;

removing said failed disk from said array;

preparing a new disk by setting all status information to indicate that said associated block may contain invalid information;

adding said new disk to said array;

systematically reconstructing data or parity blocks with associated status information indicating that said associated block may contain invalid information and after each reconstructing of a data block or parity block, setting said associated status information to indicate that said associated block contains valid information;

continuing said systematic reconstruction until all blocks on said new disk have been reconstructed;

receiving requests to access data blocks in said new disk from said user application;

writing data to said accessed data blocks in said new disk and setting said associated status information to indicate that said associated blocks contain valid information whereby the most active portions of said new disk are reconstructed before other portions.

4. The method as set forth in claim 3 wherein said step of systematic reconstruction comprises the steps of:

(a) locating a data or parity block on said new disk with status information indicating that said associated block may contain invalid information;

(b) reading the corresponding data or parity blocks from surviving disks need for regeneration;

(c) regenerating data or parity information for said new disk;

(d) writing said regenerated data or parity information to a block on said new disk;

(e) setting the status information of said block containing said regenerated information to indicate that said associated block contains valid information;

(f) determining if all data or parity blocks on said new disk have been processed;

(g) if a data or parity block remains unprocessed then repeating steps (a) through (g);

(h) if all said data or parity blocks have been processed terminating said method.

5. In a storage system having n+1 disks arranged in a RAID array, a plurality of data blocks, a plurality of parity blocks, each parity block associated with n data blocks, a plurality of status bits, each status bit associated with one of said data blocks or said parity blocks, each status bit having a first state indicating that said associated block may contain invalid information and a second state indicating that said associated block contains valid information, one of said disks being a new disk replacing a failed disk, said new disk having all of said status bits associated with the data and parity blocks in said first state, apparatus for on-line reconstruction of a new disk replacing a failed disk in said array while preserving concurrent access to said array by a user application comprising:

read/write control logic for providing an interrogate output signal;

a status network coupled to said read/write control logic, said status network responsive to said interrogate output signal for locating a status bit in said first state, said status network for providing a signal for identifying the data block or parity block associated with said status bit in said first state;

regeneration logic coupled to said read/write control logic, said regeneration logic responsive to said identifying signal for regenerating said identified data or parity block;

said read/write control logic coupled to said regeneration logic and providing a clear output signal, said read/write control logic for writing said data or parity block regenerated by said regeneration logic and asserting said clear output signal, said status network responsive to said clear output signal for setting said status bit associated with said regenerated data or parity block to said second state;

RAID control logic for receiving a request from said user application to access any data block on said new disk; and

said read/write control logic also coupled to said RAID control logic for writing data to said accessed data block on said new disk, and, if the status bit associated with said accessed data block is in said first state, asserting said clear output signal, said status network responsive to said clear output signal for setting said status bit associated with said accessed data block to said second state.

6. In a storage system having n+1 disks arranged in a RAID array, a plurality of data blocks, a plurality of parity blocks, each parity block associated with n data blocks, one of said disks being a new disk replacing a failed disk, apparatus for on-line reconstruction of a new disk replacing a failed disk in said array while preserving concurrent access to said array by a user application comprising:

read/write control logic for providing an interrogate output signal;

a status network coupled to said read/write control logic, said status network having a plurality of status bits, each status bit associated with one of said data blocks or said parity blocks, each status bit having a first state indicating that said associated block may contain invalid information and a second state indicating that said associated block contains valid information, said status network responsive to said interrogate output signal for locating a status bit in said first state, said status network for providing a signal for identifying the data block or parity block associated with said status bit in said first state;

regeneration logic coupled to said read/write control logic, said regeneration logic responsive to said identifying signal for regenerating said identified data or parity block;

said read/write control logic coupled to said regeneration logic and providing a clear output signal, said read/write control logic for writing said data or parity block regenerated by said regeneration logic and asserting said clear output signal, said status network responsive to said clear output signal for setting said status bit associated with said regenerated data or parity block to said second state;

RAID control logic for receiving a request from said user application to access any data block on said new disk; and

said read/write control logic also coupled to said RAID control logic for writing data to said accessed data block on said new disk, and, if the status bit associated with said accessed data block is in said first state, asserting said clear output signal, said status network responsive to said clear output signal for setting said status bit associated with said accessed data block to said second state.

7. A storage system as set forth in claim 6 wherein said status network comprises:

cache for storing said plurality of status bits;

status control logic responsive to said interrogate signal and coupled to said cache for locating a status bit in said first state;

set control logic coupled to said cache for providing a signal identifying the data block or parity block associated with said status bit in said first state; and

clear control logic responsive to said clear output signal and coupled to said cache for setting said status bit to said second state.