Redundant array parity caching system

• US 5,341,381 A
• Filed: 01/21/1992
• Issued: 08/23/1994
• Est. Priority Date: 01/21/1992
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Tandem Computers Incorporated (HP Inc.)
• Inventors: Fuller, William T.
• Primary Examiner(s): ATKINSON, CHARLES
• Application Number:
  US07/823,141
• Time in Patent Office: 945 Days
• Field of Search: 371/10.1, 371/11.1, 371/51.1, 371/40.1, 395/575
• US Class Current: 714/6.12
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache

Abstract

An apparatus and method for improving the input/output performance of a redundant storage array system. The present invention provides a "special parity" cache within the controller for a redundant storage array system, and means for determining and caching a quantity known as the "remaining redundancy row parity" (RRR-parity) block. The RRR-parity block is equal to the old parity block of a redundancy row XOR'"'"'d with an old data block being read from the same redundancy row. By caching RRR-parity blocks, Write-intensive storage unit operations can be reduced by up to three input/output accesses.

Claims

1. A redundant storage array system including:

a. a plurality of failure independent data storage units for storing data and redundancy information in the form of blocks;

b. caching means for temporarily storing remaining redundancy row parity (RRR-parity) blocks derived from the plurality of data storage units;

c. storage unit controller means, coupled to the plurality of data storage units and to the caching means, for;

(1) controlling reading data and redundancy blocks from, and writing data and redundancy blocks to, the plurality of data storage units;

(2) computing RRR-parity blocks derived from the plurality of data storage units; and

(3) caching the computed RRR-parity blocks in the caching means.

2. The apparatus of claim 1, wherein the storage unit controller means further includes means for determining if an RRR-parity block corresponding to a data block is stored in the caching means.

3. The apparatus of claim 1, wherein each RRR-parity block is computed by exclusively-OR'"'"'ing:

a. a data block read from at least one data storage unit, and

b. a corresponding redundancy block read from at least one data storage unit.

4. A redundant storage array system including:

a. a plurality of failure independent data storage units for storing data and redundancy information in the form of blocks;

b. caching means for temporarily storing remaining redundancy row parity (RRR-parity) blocks derived from the plurality of data storage units;

c. a storage unit controller means, coupled to the plurality of data storage units and to the caching means, for;

(1) receiving from a processor at least one command to read an old data block from at least one data storage unit;

(2) reading the old data block from at least one data storage unit;

(3) communicating with the caching means to determine if an RRR-parity block corresponding to the previously read old data block is stored therein, and if such a corresponding RRR-parity block is not stored within the caching means, then;

(a) reading an old redundancy block, corresponding to the read data block, from at least one data storage unit;

(b) computing an RRR-parity block from the read data block and the corresponding read redundancy block;

(c) caching the computed RRR-parity block in the caching means.

5. The apparatus of claim 4, wherein an RRR-parity block is computed by exclusively-OR'"'"'ing a read data block and a corresponding read redundancy block.

6. A redundant storage array system including:

a. a plurality of failure independent data storage units for storing data and redundancy information in the form of blocks;

b. caching means for temporarily storing remaining redundancy row parity (RRR-parity) blocks derived from the plurality of data storage units;

c. a storage unit controller, coupled to the plurality of data storage units and to the caching means, comprising control means for modifying a data block including means for;

(1) receiving a new data block from a processor;

(2) communicating with the caching means to retrieve an RRR-parity block stored therein corresponding to the received new data block, and if such a corresponding RRR-parity block is not stored within the caching means, then;

(a) reading an old data block, corresponding to the new data block, from at least one data storage unit;

(b) reading an old redundancy block, corresponding to the new data block, from at least one data storage unit;

(c) computing an RRR-parity block, corresponding to the new data block, from the previously read old data block and the corresponding read redundancy block;

(d) caching the computed RRR-parity block in the caching means;

(3) generating a new redundancy block from the new data block and the RRR-parity block corresponding to the new data block;

(4) writing the new redundancy block to at least one data storage unit;

(5) writing the new data block over the previously read old data block.

7. The apparatus of claim 6, wherein an RRR-parity block is computed by exclusively-OR'"'"'ing a read data block and a corresponding read redundancy block.

8. The apparatus of claim 6, wherein a redundancy block is computed by exclusively-OR'"'"'ing a read data block, a corresponding read redundancy block, and a new data block.

9. A redundant storage array system including:

a. a plurality of failure independent data storage units for storing data and redundancy information in the form of blocks;

b. caching means for temporarily storing remaining redundancy row parity (RRR-parity) blocks derived from the plurality of data storage units;

c. a storage unit controller, coupled to the plurality of data storage units and to the caching means, comprising control means for modifying a data block including means for;

(1) receiving from a processor at least one command to read an old data block from at least one data storage unit;

(2) reading the old data block from at least one data storage unit;

(3) communicating with the caching means to determine if an RRR-parity block corresponding to the previously read old data block is stored therein, and if such a corresponding RRR-parity block is not stored within the caching means, then;

(a) reading an old redundancy block, corresponding to the read data block, from at least one data storage unit;

(b) computing an RRR-parity block from the read data block and the corresponding read redundancy block;

(c) caching the computed RRR-parity block in the caching means;

(4) transmitting the read data block to the processor;

(5) receiving a new data block from the processor;

(6) communicating with the caching means to retrieve an RRR-parity block stored therein corresponding to the received new data block, and if such a corresponding RRR-parity block is not stored within the caching means, then;

(a) reading an old data block, corresponding to the new data block, from at least one data storage unit;

(b) reading an old redundancy block, corresponding to the new data block, from at least one data storage unit;

(c) computing an RRR-parity block, corresponding to the new data block, from the previously read old data block and the corresponding read redundancy block;

(d) caching the computed RRR-parity block in the caching means;

(7) generating a new redundancy block from the new data block and the RRR-parity block corresponding to the new data block;

(8) writing the new redundancy block to at least one data storage unit;

(9) writing the new data block over the previously read old data block.

10. The apparatus of claim 9, wherein an RRR-parity block is computed by exclusively-OR'"'"'ing a read data block and a corresponding read redundancy block.

11. The apparatus of claim 9, wherein a redundancy block is computed by exclusively-OR'"'"'ing a read data block, a corresponding read redundancy block, and a new data block.

12. A redundant storage array system including:

a. a plurality of failure independent data storage units for storing data and redundancy information in the form of blocks;

b. caching means for temporarily storing remaining redundancy row parity (RRR-parity) blocks derived from the plurality of data storage units;

c. a storage unit controller, coupled to the plurality of data storage units and to the caching means, comprising control means for modifying a data block including means for;

(1) receiving from a processor at least one command to read an old data block from at least one data storage unit;

(2) reading the old data block from at least one data storage unit;

(3) transmitting the read data block to the processor;

(4) receiving a new data block from the processor;

(5) communicating with the caching means to retrieve an RRR-parity block stored therein corresponding to the received new data block, and if such a corresponding RRR-parity block is not stored within the caching means, then;

(a) reading an old data block, corresponding to the new data block, from at least one data storage unit;

(b) reading an old redundancy block, corresponding to the new data block, from at least one data storage unit;

(c) computing an RRR-parity block, corresponding to the new data block, from the previously read old data block and the corresponding read redundancy block;

(d) caching the computed RRR-parity block in the caching means;

(6) generating a new redundancy block from the new data block and the RRR-parity block corresponding to the new data block;

(7) writing the new redundancy block to at least one data storage unit;

(8) writing the new data block over the previously read old data block.

13. The apparatus of claim 12, wherein an RRR-parity block is computed by exclusively-OR'"'"'ing a read data block and a corresponding read redundancy block.

14. The apparatus of claim 12, wherein a redundancy block is computed by exclusively-OR'"'"'ing a read data block, a corresponding read redundancy block and a new data block.

15. In a redundant storage array system including a controller, a cache coupled to the controller, and a plurality of failure independent data storage units coupled to the controller for storing data and redundancy information in the form of blocks, a method for improving the input/output performance of the redundant storage array system comprising the step of:

a. caching remaining redundancy row parity (RRR-parity) blocks derived from the plurality of data storage units.

16. The method of claim 15, further including the step of determining if an RRR-parity block corresponding to a data block is stored in the cache.

17. The method of claim 15, wherein each RRR-parity block is computed by exclusively-OR'"'"'ing:

a. a data block read from at least one data storage unit, and

b. a corresponding redundancy block read from at least one data storage unit.

18. In a redundant storage array system including a controller, a cache coupled to the controller, and a plurality of failure independent data storage units coupled to the controller for storing data and redundancy information in the form of blocks, a method for improving the input/output performance of the redundant storage array system comprising the steps of:

a. receiving from a processor at least one command to read an old data block from at least one data storage unit;

b. reading the old data block from at least one data storage unit;

c. determining if an RRR-parity block corresponding to the previously read old data block is stored within the cache, and if such a corresponding RRR-parity block is not stored within the cache, then;

(1) reading an old redundancy block, corresponding to the read data block, from at least one data storage unit;

(2) computing an RRR-parity block from the read data block and the corresponding read redundancy block;

(3) caching the computed RRR-parity block in the cache.

19. The method of claim 18, wherein an RRR-parity block is computed by exclusively-OR'"'"'ing a read data block and corresponding read redundancy block.

20. In a redundant storage array system including a controller, a cache coupled to the controller, and a plurality of failure independent data storage units coupled to the controller for storing data and redundancy information in the form of blocks, a method for improving the input/output performance of the redundant storage array system comprising the steps of:

a. receiving a new data block from a processor;

b. retrieving an RRR-parity block stored in the cache corresponding to the received new data block, and if such a corresponding RRR-parity block is not stored within the cache, then;

(1) reading an old data block, corresponding to the new data block, from at least one data storage unit;

(2) reading an old redundancy block, corresponding to the new data block, from at least one data storage unit;

(3) computing an RRR-parity block, corresponding to the new data block, from the previously read old data block and the corresponding read redundancy block;

(4) caching the computed RRR-parity block in the cache;

c. generating a new redundancy block from the new data block and the RRR-parity block corresponding to the new data block;

d. writing the new redundancy block to at least one data storage unit;

e. writing the new data block over the previously read old data block.

21. The method of claim 20, wherein an RRR-parity block is computed by exclusively-OR'"'"'ing a read data block and a corresponding read redundancy block.

22. The method of claim 20, wherein a redundancy block is computed by exclusively-OR'"'"'ing a read data block, a corresponding read redundancy block, and a new data block.

23. In a redundant storage array system including a controller, a cache coupled to the controller, and a plurality of failure independent data storage units coupled to the controller for storing data and redundancy information in the form of blocks, a method for improving the input/output performance of the redundant storage array system comprising the steps of:

a. receiving from a processor at least one command to read an old data block from at least one data storage unit;

b. reading the old data block from at least one data storage unit;

c. determining if an RRR-parity block corresponding to the previously read old data block is stored within the cache, and if such a corresponding RRR-parity block is not stored within the cache, then;

(1) reading an old redundancy block, corresponding to the read data block, from at least one data storage unit;

(2) computing an RRR-parity block from the read data block and the corresponding read redundancy block;

(3) caching the computed RRR-parity block in the cache;

d. transmitting the read data block to the processor;

e. receiving a new data block from the processor;

f. retrieving an RRR-parity block stored in the cache corresponding to the received new data block, and if such a corresponding RRR-parity block is not stored within the cache, then;

(1) reading an old data block, corresponding to the new data block, from at least one data storage unit;

(2) reading an old redundancy block, corresponding to the new data block, from at least one data storage unit;

(3) computing an RRR-parity block, corresponding to the new data block, from the previously read old data block and the corresponding read redundancy block;

(4) caching the computed RRR-parity block in the cache;

g. generating a new redundancy block from the new data block and the RRR-parity block corresponding to the new data block;

h. writing the new redundancy block to at least one data storage unit;

i. writing the new data block over the previously read old data block.

24. The method of claim 23, wherein an RRR-parity block is computed by exclusively-OR'"'"'ing a read data block and a corresponding read redundancy block.

25. The method of claim 23, wherein a redundancy block is computed by exclusively-OR'"'"'ing a read data block, a corresponding read redundancy block, and a new data block.

26. In a redundant storage array system including a controller, a cache coupled to the controller, and a plurality of failure independent data storage units coupled to the controller for storing data and redundancy information in the form of blocks, a method for improving the input/output performance of the redundant storage array system comprising the steps of:

a. receiving from a processor at least one command to read an old data block from at least one data storage unit;

b. reading the old data block from at least one data storage unit;

c. transmitting the read data block to the processor;

d. receiving a new data block from the processor;

e. retrieving an RRR-parity block stored in the cache corresponding to the received new data block, and if such a corresponding RRR-parity block is not stored within the cache, then;

(1) reading an old data block, corresponding to the new data block, from at least one data storage unit;

(2) reading an old redundancy block, corresponding to the new data block, from at least one data storage unit;

(3) computing an RRR-parity block, corresponding to the new data block, from the previously read old data block and the corresponding read redundancy block;

(4) caching the computed RRR-parity block in the cache;

f. generating a new redundancy block from the new data block and the RRR-parity block corresponding to the new data block;

g. writing the new redundancy block to at least one data storage unit;

h. writing the new data block over the previously read old data block.

27. The method of claim 26, wherein an RRR-parity block is computed by exclusively-OR'"'"'ing a read data block and a corresponding read redundancy block.

28. The method of claim 26, wherein a redundancy block is computed by exclusively-OR'"'"'ing a read data block, a corresponding read redundancy block, and a new data block.