Method and means for execution of commands accessing variable length records stored on fixed block formatted DASDS of an N+2 DASD synchronous array

• US 5,506,979 A
• Filed: 04/02/1991
• Issued: 04/09/1996
• Est. Priority Date: 04/02/1991
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Menon, Jaishankar M.
• Primary Examiner(s): Harrell, Robert B.
• Application Number:
  US07/679,455
• Time in Patent Office: 1,834 Days
• Field of Search: 371/11.1, 371/40.2, 395/575, 395/500, 395/439
• US Class Current: 711/112
• 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 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G11B 20/10 Digital recording or reproducing
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence

Abstract

Variable length records can be accessed from an array of N+2 synchronous fixed block formatted DASDs in a single pass and in the presence of a single DASD failure if each record is partitioned into a variable number of K fixed length blocks, the blocks are written on the DASDs in column major order K modulo (N+1), the order is constrained such that the first block of each record resides on the (N+l)st DASD, a parity block for each column resides on an (N+2)nd DASD, and each parity block spans N blocks in the same column from the first N DASDs and one block one column offset thereto on the (N+1)st DASD.

Claims

1. A method for accessing variable length records defined over an array of (N+2) synchronized, fixed block formatted, cyclic, multi-tracked direct access storage devices DASDs e.g. DASD1--DASD(N+2)) responsive to a series of access commands (CCW'"'"'s) generated by a CPU (1) and interpreted by a control unit (2) intercoupling the CPU and the array, said control unit including access command interpreter means (501), buffer and striping logic (503), parity coding means (507), and access means (7, 9, 11, 13, 15), said buffer and striping logic partitioning each record into fixed length blocks, said parity means computing parity over a predetermined number of blocks, and said access means synchronously reading or writing the predetermined number of blocks and associated parity from or to counterpart array DASD locations, each partitioned record having at least a first block, wherein the method comprising the steps of:

(a) partitioning each variable length record into a variable number K fixed length blocks by said buffer and striping logic, and, synchronously writing said blocks in column major order K modulo (N+1) across counterpart track extents on each of said (N+1) DASDs by said access means (FIG. 4, disks 1-3), said column major order being constrained such that the first block of each record is written along a different track extent on the (N+1) st DASD (FIG. 4, disk

     3);

(b) forming and writing a parity block P(i) concurrently with step (a) along an ith track extent on an (N+2)nd DASD (FIG. 4, disk

     4) corresponding to an ith track extent on each of said (N+1) DASDs by said parity coding means, P(i) logically combining the block written along an (i-1)st track extent of the (N+1)st DASD (FIG. 4, block

     3) and N blocks from the first N other DASDs (FIG. 4, blocks 4-6) along their ith track extents; and

(c) responsive to each access (READ/WRITE) command, traversing the track extents of the array DASDs by said access means in the order defined by steps (a) and (b), whereby the blocks forming any record specified in such command and spanning parity blocks can be accessed during a single pass, a single pass being one cycle of rotational revolution of a fixed point on any DASD track extent during which a transfer of a record or portion thereof from or to the DASDs of the array is effectuated, a track extent being a circumferential distance collinear with a track.

2. The method according to claim 1, wherein the K blocks of any record occupy no more than K/(N+1) contiguous track extents on any one of the first (N+1) DASDs.

3. The method according to claim 1, wherein the logical combining referenced in step (b) includes that of performing an exclusive OR operation over N+1 blocks.

4. A method for ensuring single pass synchronous access to variable length records across ones of a fixed block formatted, cyclic, multitracked direct access storage device (DASD) array over a common path responsive to a series of access commands (CCW'"'"'s) generated by a CPU (1) and interpreted by a control unit (2) intercoupling the CPU and the array, said control unit including access command interpreter means (501), buffer and striping logic (503), parity coding means (507), and access means (7, 9, 11, 13, 15), said buffer and striping logic partitioning each record into fixed length blocks, said parity means computing parity over a predetermined number of blocks, and said access means synchronously writing the predetermined number of blocks and associated parity to counterpart array DASD locations, each record including a fixed length count field and a variable length data field, comprising the steps of:

(a) reformatting each record into a first block representing the count field and a variable number of other blocks representing the data field by said buffer and striping logic, and, synchronously writing the blocks of each reformatted record in column major order K modulo (N+1) over N+1 DASDs said access means (FIG.4, disks 1-3), said column major order being constrained such that all first blocks inclusive of the count field are recorded on the (N+1)st DASD (FIG. 4, disk

     3);

(b) forming and writing a parity block for each counterpart column order concurrent with step (a) on an (N+2)nd DASD by said parity coding means (FIG. 4, disk

     4), each parity block spanning N blocks in the same column from the first N DASDs (FIG. 4, blocks 4-6) and one block one column offset thereto on the (N+1)st DASD (FIG. 4, block

     3); and

(c) responsive to each command requesting at least one record, accessing the blocks forming the requested record and the correlated parity blocks in the order defined by steps (a) and (b) by said access means thereby ensuring access of the requested record and its parity image in a single pass, a single pass being one cycle of rotational revolution of a fixed point on any DASD track extent during which a transfer of a record or portion thereof from or to the DASDs of the array is effectuated, a track extent being a circumferential distance collinear with a track.

5. The method according to claim 4, wherein the parity block is formed by XORing of the spanned blocks.

6. A method for ensuring single pass synchronous access to variable length records across ones of a fixed block formatted, cyclic, multi-tracked direct access storage device (DASD) array over a common path responsive to a series of access commands (CCW'"'"'s) generated by a CPU (1) and interpreted by a control unit (2) intercoupling the CPU and the array, said control unit including access command interpreter means (501), buffer and striping logic (503), parity coding means (507), and access means (7, 9, 11, 13, 15), said buffer and striping logic partitioning each record into fixed length blocks, said parity means computing parity over a predetermined number of blocks, and said access means synchronously writing the predetermined number of blocks and associated parity to counterpart array DASD locations, each counterpart track on each array DASD including an indexed reference point, each record including at least a fixed length count field and a variable length data field, said array being opportunistically subject to a constitutive DASD failure, comprising the steps of:

(a) reformatting each record into a first block representing the count field and a variable number of other blocks representing the data field by said buffer and striping logic, and, synchronously writing the blocks of each reformatted record in column major order K modulo (N+1) over N+1 DASDs by said access means (FIG.4, disks 1-3), said column major order being constrained such that all first blocks are recorded on the (N+1)st DASD (FIG. 4, disk

     3);

(b) forming and writing a parity block for each counterpart column order concurrent with step (a) on an (N+2)nd DASD by said parity coding means (FIG. 4, disk

     4), each parity block spanning N blocks in the same column from the first N DASDs (FIG. 4, blocks 4-6) and one block one column offset thereto on the (N+1) st DASD (FIG. 4, block

     3); and

(c) responsive to an opportunistic DASD failure other than the (N+1)st and (N+2)nd DASDs and a command requesting at least one record, recovering each unavailable block from the correlated parity block and the remaining blocks spanned by the parity block and concurrently accessing the blocks of the requested record including any recovered blocks in the column major order defined by steps (a) and (b), a single pass being one cycle of rotational revolution of a fixed point on any DASD track extent during which a transfer of a record or portion thereof from or to the DASDs of the array is effectuated, a track extent being a circumferential distance collinear with a track.

7. The method according to claim 6, jointly responsive to an opportunistic failure of the (N+1)st DASD and a command requesting at least one record, said command being selected from the set consisting of the read, write, and write update commands, the method further comprising the steps of:

(d) recovering the first blocks of each record from the correlated parity block and the remaining blocks spanned by the parity block during a first pass; and

(e) during execution of any write update command, accessing the blocks of the requested record including any recovered blocks in the column major order defined by steps (a) and (b) during a second pass.

8. The method according to claims 6 or 7, wherein the recovering of unavailable blocks includes the XORing of the correlated parity block and the remaining blocks spanned by the parity block.

9. The method according to claim 6, wherein at least one of the DASDs of the array is reserved, whereupon, if any of the DASDs other than the spare, the (N+1)st, and the (N+2)nd is rendered unavailable for record accessing, the method further comprises the steps of:

(f) replacing the unavailable DASD by the reserved DASD; and

in a single pass

(g) recovering each unavailable block by XORing each correlated parity block and the remaining available blocks spanned by the parity block; and

(h) writing each recovered block to the spare DASD with a one block offset, and resynching the indices of the array DASDs.

10. In an external storage subsystem comprising a plurality fixed block formatted cyclic multitracked storage devices (DASDs), an array control unit (ACU) responsive to external commands for synchronously accessing said DABDs and for transferring one or more variable length records between said DASDs and a CPU coupled thereto, wherein the improvement in the ACU comprises:

(a) means (3, 501,

     503) responsive to an external write command for partitioning a variable length record into variable number of K consecutive fixed length blocks;

(b) means (7, 13,

     15) for writing said blocks in column major order over N+1 DASDs in which the first block of each record is written on the (N+1)st DASD;

(c) means (507, 511,

     513) for forming and writing a parity block for each counterpart column order concurrent with step (a) on an (N+2)nd DASD, each parity block spanning N blocks in the same column from the first N DASDs and one block one column offset thereto on the (N+l)st DASD; and

(d) means (501, 7, 503,

     507) responsive to each external command requesting at least one record, accessing the blocks forming the requested record and the correlated parity blocks in the order defined by means (a)-(c), thereby ensuring access of the requested record and its parity image in a single pass, a single pass being one cycle of rotational revolution of a fixed point on any DASD track extent during which a transfer of a record or portion thereof from or to the DABDs of the array is effectuated, a track extent being a circumferential distance collinear with a track.