Parity block configuration in an array of storage devices

• US 5,537,567 A
• Filed: 03/14/1994
• Issued: 07/16/1996
• Est. Priority Date: 03/14/1994
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Writz, Joseph T., Galbraith, Robert E.
• Primary Examiner(s): Robertson, David L.
• Application Number:
  US08/212,613
• Time in Patent Office: 855 Days
• Field of Search: 395/182.04, 395/441
• US Class Current: 711/114
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems

Abstract

In a redundant array of disk storage units which independently accesses data blocks on different units and which uses parity blocks for data protection, parity blocks are confined to specific address ranges of each respective disk unit (rows of the array), each row containing multiple parity blocks. Each parity block represents the exclusive-OR of a stripe of data blocks located on a diagonal of the array. Where data accesses exhibit locality of reference in certain rows, this arrangement distributes the burden of updating parity more equally than a conventional RAID level 5. Additionally, because a "row" corresponds to a particular annular region of a disk surface on each respective disk unit, parity blocks can be located at optimal logical addresses or physical regions of the disk surface to simplify address translation and/or further improve performance.

Claims

1. A storage subsystem for a computer system, comprising:

storage subsystem controller, said controller having a processor and a memory;

a plurality of data storage units coupled to sad controller,

a first group of at least three data storage units coupled to said controller,

wherein addressable storage space in said plurality of data storage units corresponds to a two-dimensional array of storage blocks, each column of said array representing a different one of said data storage units, and each row of said array representing a discrete range of storage locations within each storage unit;

means for computing parity blocks from data stored in data storage blocks, wherein each parity block is computed from data stored in a corresponding set of data storage blocks, each said data storage block of said set being located on a different one of said data storage units;

means for storing said parity blocks on one or more parity rows in said first group of at least three data storage units of said array, said parity rows being fewer than half of all the rows of said array, each of said parity rows comprising a plurality of storage blocks containing parity blocks, wherein each parity block is stored on a storage unit different from any of the storage units containing storage blocks of the set of storage blocks corresponding to said parity block and;

a second group of at least one data storage unit, the storage blocks of said second group containing data, each storage block containing data in said second group being associated with a parity block in said first group of said at least three data storage units.

2. The storage subsystem of claim 1, wherein said parity rows are no more than one quarter of the total number of rows of said array.

3. The storage subsystem of claim 1, wherein said array contains R/N parity rows, R/N being rounded upward to the nearest integer value, where R is the total number of rows of said array and N is the number of said data storage units in said array which contain parity blocks, N being greater than one.

4. The storage subsystem of claim 3, wherein all data storage units in said array contain parity blocks, N being the total number of data storage units in said array.

5. The storage subsystem of claim 1, wherein said data storage blocks of each respective set are stored along a respective diagonal of said array.

6. The storage subsystem of claim 1, wherein said parity rows are located in the upper range of addresses of said first group of storage units.

7. The storage subsystem of claim 1, wherein said one or more parity rows represent storage locations which are selected to maximize performance of said storage subsystem.

8. A storage subsystem for a computer system, comprising:

storage subsystem controller, said controller having a processor and a memory;

at least three data storage units coupled to said controller,

wherein addressable storage space in said data storage units corresponds to a two-dimensional array of storage blocks, each column of said array representing a different one of said data storage units, and each row of said array representing a discrete range of storage locations within each storage unit;

means for computing parity blocks from data stored in data storage blocks, wherein each parity block is computed from data stored in a corresponding set of data storage blocks, each said data storage block of said set being located on a different one of said data storage units; and

means for storing said parity blocks on one or more parity rows of said array, said parity rows being fewer than half of all the rows of said array, each of said parity rows comprising a plurality of storage blocks containing parity blocks, wherein each parity block is stored on a storage unit different from any of the storage units containing storage blocks of the set of storage blocks corresponding to said parity block, wherein said storage units are rotating magnetic disk drive storage units, and wherein said one or more parity rows represent storage locations in a plurality of middle annular regions of respective disk surfaces of said rotating magnetic disk drive storage units.

9. A controller for a storage subsystem of a computer system, comprising:

a processor;

a memory;

a first interface for communicating with a processor of said computer system;

a second interface for communicating with a plurality of data storage units,

wherein addressable storage space in said data storage units corresponds to a two-dimensional array of storage blocks, each column of said array representing a different one of said data storage units, and each row of said array representing a discrete range of storage locations within each storage unit;

means for computing parity blocks from data stored in data storage blocks, wherein each parity block is computed from data stored in a corresponding set of data storage blocks, each said data storage block of said set being located on a different one of said data storage units;

a first group of said plurality of data storage units, said first group having addressable storage blocks containing data and other addressable storage blocks storing parity information;

means for storing said parity blocks on one or more parity rows of said array, said parity rows being fewer than half of all the rows of said array, each of said parity rows comprising a plurality of storage blocks containing parity blocks, wherein each parity block is stored on a storage unit different from any of the storage units containing storage blocks of the set of storage blocks corresponding to said parity block and;

a second group of said plurality of data storage units, said second group storing data in said addressable storage blocks of said second group and being associated with addressable storage blocks of said first group that store parity information.

10. The controller for a storage subsystem of claim 9, wherein said parity rows are no more than one quarter of the total number of rows of said array.

11. The controller for a storage subsystem of claim 9, wherein said array contains R/N parity rows, R/N being rounded upward to the nearest integer value, where R is the total number of rows of said array and N is the number of said data storage units in said array which contain parity blocks, N being greater than one.

12. The controller for a storage subsystem of claim 9, wherein all data storage units in said array contain parity blocks, N being the total number of data storage units in said array.

13. The controller for a storage subsystem of claim 9, wherein said data storage blocks of each respective set are stored along a respective diagonal of said array.

14. A computer system, comprising:

a bus for communicating among components of said computer system;

at least one central processing unit communicating with said bus;

a system memory communicating with said bus;

a plurality of data storage units further including a first group of at least three data storage units communicating with said bus, and a second group of at least one data storage unit communicating with said bus;

wherein addressable storage space in said plurality of data storage units corresponds to a two-dimensional array of storage blocks, each column of said array representing a different one of said data storage units, and each row of said array representing a discrete range of storage locations within each storage unit;

means for computing parity blocks from data stored in data storage blocks, wherein each parity block is computed from data stored in a corresponding set of data storage blocks in a first group of at least three data storage units and in a second group of at least one data storage unit, each said data storage block of said set being located on a different one of said data storage units; and

means for storing said parity blocks on one or more parity rows in said first group of at least three data storage units of said array, said parity rows being fewer than half of all the rows of said array, each of said parity rows comprising a plurality of storage blocks containing parity blocks, wherein each parity block is stored on a storage unit different from any of the storage units containing storage blocks of the set of storage blocks corresponding to said parity block.

15. The computer system of claim 14, wherein said parity rows are no more than one quarter of the total number of rows of said array.

16. The computer system of claim 14, wherein said array contains R/N parity rows, R/N being rounded upward to the nearest integer value, where R is the total number of rows of said array and N is the number of said data storage units in said array which contain parity blocks, N being greater than one.

17. The computer system of claim 14, wherein said data storage blocks of each respective stripe are stored along a respective diagonal of said array.

18. A method for operating a redundant array of a plurality of data storage units, said plurality of data storage units in a first group of at least three data storage units of a data storage system and in a second group of at least one data storage unit of a data storage system, wherein addressable storage space in said data storage units corresponds to a two-dimensional array of storage blocks, each column of said array representing a different one of said data storage units, and each row of said array representing a discrete range of storage locations within each storage unit, said method comprising the machine implemented steps of:

identifying data to be written to a first data block of said array of storage blocks;

identifying a parity block associated with said data block, said parity block representing a parity function of a set of data blocks, said first data block being a member of said set of data blocks, each of said data blocks of said set and said parity block being stored on a different one of said storage devices;

writing said data to be written to said first data block in said first group of data storage units;

updating said parity block to reflect said data written to said first data block;

writing said data to be written to said second data block in said second group of data storage units;

updating said parity block to reflect said data written to said second data block;

storing said parity block in one of a plurality of party rows of said first group of storage units of said array, each said parity row containing a plurality of parity blocks,

said parity rows being fewer than half the total number of rows of said array.

19. The method for operating a redundant array of storage units of claim 18, wherein said array contains R/N parity rows, R/N being rounded upward to the nearest integer value, where R is the total number of rows of said array and N is the number of said data storage units in said array which contain parity blocks, N being greater than one.

20. The method for operating a redundant array of storage units of claim 19, wherein all data storage units in said array contain parity blocks, N being the total number of data storage units in said array.

21. The method for operating a redundant array of storage units of claim 18, wherein said data storage blocks of each respective set are stored along a respective diagonal of said array.

22. The method for operating a redundant array of storage units of claim 18, wherein said parity rows occupy a single contiguous band of addressable storage space of said first group of said array.

23. A storage subsystem for a computer system, comprising:

a storage subsystem controller, said controller having a processor and a memory;

a plurality of data storage units coupled to said controller including a first group of at least three data storage units coupled to said controller, and a second group of at least one data storage unit coupled to said controller,

wherein addressable storage space in said plurality of data storage units corresponds to a two-dimensional array of storage blocks, each column of said array representing a different one of said data storage units, and each row of said array representing a discrete range of storage locations within each storage unit;

means for computing parity blocks from data stored in data storage blocks located in data rows of said array, each of said data rows containing a plurality of storage blocks containing data blocks, wherein each said data row contains no parity blocks, wherein each parity block is computed from data stored in a corresponding set of data storage blocks, each said data storage block of said set being located on a different one of said data storage units; and

means for storing said parity blocks on one or more parity rows of said first group of said array, each of said parity rows comprising a plurality of storage blocks containing parity blocks, wherein each parity block is stored on a storage unit different from any of the storage units containing storage blocks of the set of storage blocks corresponding to said parity block, data blocks from said first and second group of data storage units being associated with at least one of said parity blocks in said first group.

24. The storage subsystem of claim 23, wherein said data storage blocks of each respective set are stored along a respective diagonal of said array.