Method for initializing or reconstructing data consistency within an array of storage elements

• US 5,812,753 A
• Filed: 10/13/1995
• Issued: 09/22/1998
• Est. Priority Date: 10/13/1995
• Status: Expired due to Term

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: ECCS, INC.
• Inventors: Chiariotti, Enzo
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Wright, Norman M.
• Application Number:
  US08/545,430
• Time in Patent Office: 1,075 Days
• Field of Search: 395/182.04, 395/182.03, 395/441, 395/185.05, 395/185.07, 395/185.02, 395/185.01, 371/31, 371/48, 371/49.1, 371/37.7
• US Class Current: 714/6.21
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems

Abstract

A method of initializing or reconstructing data redundancy within a array of storage elements. Specifically, the method is performed by the array management software, either as part of the array controller or a host computer performing array controller functions, such that, for a new array, the data therein is made consistent (e.g., XOR consistent using parity data) and, for an array with a recently replaced storage element, data is reconstructed within the new storage element. In either case, after executing the inventive routine, the array is fault tolerant and the data is consistent in accordance with the technique used to generate fault tolerance.

Claims

1. In a storage system containing a plurality of storage elements, a method of generating data consistency throughout the storage elements while simultaneously providing access to the storage elements as data consistency generation is being accomplished comprising the steps of:

(a) selecting a storage element from said plurality of storage elements;

(b) selecting address (i) within said selected storage element;

(c) locking address (i) of the storage elements within a redundancy group of address (i), where all addresses except address (i) within the storage elements of the redundancy group can be accessed while the redundancy group is being made consistent;

(d) reading data from addresses, other than address (i) within the selected storage element, within said redundancy group of address (i) stored in said plurality of storage elements;

(e) computing a consistency value using the data from said redundancy group;

(f) writing said consistency value to said address (i) in said selected storage element;

(g) unlocking said addresses (i) of the storage elements within the redundancy group of address (i);

(h) incrementing said address (i); and

(i) repeating steps b, c, d, e, f, g and h until all addresses (i) in the selected storage element have been written with a consistency value.

2. The method of claim 1 wherein said consistency value is a parity value computed in step (e) by applying an exclusive OR function to all the data read from the addresses in the redundancy group.

3. The method of claim 1 wherein said redundancy group is a data stripe containing one address within each storage element in said plurality of storage elements.

4. The method of claim 1 wherein the method is performed to initialize said plurality of storage elements.

5. The method of claim 1 wherein the method is performed to reconstruct data for a storage element, where said selected storage element is a replaced storage element and said consistency value is reconstructed data.

6. The method of claim 1 wherein the storage system is a RAID level 5 array.

7. In a RAID level 5 storage system containing a plurality of hard disk drives forming an array, the array is partitioned into data stripes and data strips, a method of generating data consistency through the array comprising the steps of:

(a) selecting a hard disk drive from said plurality of hard disk drives;

(b) selecting address (i) within said selected hard disk drive;

(c) locking address (i) of hard disk drives within a redundancy group of address (i), where all addresses except address (i) within the hard disk drives of the redundancy group can be accessed while the redundancy group is being made consistent;

(d) reading data stored in said plurality of storage elements from addresses, other than address (i) within the selected disk drive, within a data stripe containing address (i);

(e) computing a parity value using the data from said data stripe;

(f) writing said parity value to said address (i) in said selected hard disk drive;

(g) unlocking said addresses (i) of the hard disk drives within the redundancy group of address (i);

(h) incrementing said address (i); and

(i) repeating steps b, c, d, e, f, g and h until all addresses (i) in the selected hard disk drive have been written with a parity value.

8. The method of claim 7 wherein said parity value is computed in step (e) by applying an exclusive OR function to all the data read from the addresses in the data stripe.

9. The method of claim 7 wherein the method is performed to initialize said plurality of storage elements.

10. The method of claim 7 wherein the method is performed to reconstruct data for a hard disk drive, where said selected hard disk drive is a replaced hard disk drive and said parity value is reconstructed data.

11. The method of claim 7 wherein, prior to utilizing the method, the data stored in each of said hard disk drives is inconsistent, garbage data.

12. The method of claim 7 wherein a host computer accesses the array to read or write data while said method is executing.

13. The method of claim 12 wherein said data stripe containing address (i) is temporarily locked to prevent the host computer from writing data to addresses within the locked data stripe.