System and method for disk mapping and data retrieval6185653Abstract An apparatus and method for disk mapping and data retrieval includes a data storage medium on which has been stored a plurality of data records. Each record includes at least a record identification portion, for uniquely identifying each record from among the plurality of data records. The apparatus builds a record locator table in high speed semiconductor memory which comprises the unique record identifiers for the records on the storage medium as well as a record locator index generated by the apparatus, which indicates the address of the data record on the storage medium. Data retrieval is facilitated by first searching the record locator table in high speed semiconductor memory for a requested data record. Utilizing the record locator index associated with the requested data record, the system directly accesses the requested data record on the storage medium thereby minimizing storage medium search time. Also disclosed is an apparatus and method for converting CKD formatted data records to FBA formatted disk drives and for building and compressing the "count" portion of the CKD data formatted record into a record locator table. Claims What is claimed is: Description FIELD OF THE INVENTION
TABLE 1
DEVICE ID TABLE HEADER BUFFER AND FLAG OFFSETS
1. DV HEADER SIZE $1000 LENGTH OF DV HEADER
AT THE ID TABLE
2. DV SCRATCH OFFSET DV HEADER DV SCRATCH START
ADDRESS
3. DV HEADER LENGTH SIZE $10000 LENGTH OF DV HEADER
AT THE ID TABLE
INCLUDING THE SCRATCH
AREA
DV HEADER BUFFERS OFFSETS
4. DV FLAGS OFFSET 0 DV TABLE FLAGS
5. DV STATISTICS OFFSET 4
STATISTICS/RESERVED BYTES
6. DV READ TASK OFFSET $40 READ TASK (ONLY
ONE)
7. DV SENSE INFO OFFSET $60 SENSE INFO FOR
THIS DV
8. DV TABLE SELECT BUFFER OFFSET $80 $40 BYTES SELECTION BUFFER
FOR THE DEVICE
9. RW COUNT BUFFER OFFSET $C0 8 BYTES R/W COUNT COLIMAND
DATA BUFFER
10. DV WR PEND FLAGS OFFSET $100 $140 BYTES WR PENDING
BIT PER CYLINDER
11. DV WR FEND GROUPS OFFSET $240 $20 BYTES WR PENDING BIT
FOR 8 CYLINDERS
12. DV FLAGS SELECT BUFFER OFFSET $280 $40 BYTES SELECTION BUFFER
FOR UPDATES
13. DV FMT CHANGED FLAGS OFFSET $300 $140 BYTES FMT CHANGED
BIT FOR CYLINDER
14. DV FMT CHANGED GROUPS OFFSET $440 $20 BYTES FMT CHANGED BIT
FOR 8 CYLINDERS
15. DV TEMP BLK OFFSET $400 $200 BYTES TEMP BLK FOR
RECOVERY
16. TEMP CYL ID SLOT OFFSET $600 $A00 BYTES TEMP ID FOR
RBCOVERY
Such flags include a write pending flag which is set if one or more records on the device are temporarily stored in cache memory awaiting writing and storing to the disk drive, as well as an in-cache bit indicating that at least one record on the device is located in cache memory to speed up access to the record, line 4. Other bytes of the device header provide various informational, operational, or statistical data to the system. For example, the write pending group flags shown at line 11 include one bit indicating a write pending on any one record on any of the 64 preselected consecutive cylinders comprising a cylinder group. Similarly, each cylinder has a write pending flag bit in the device header as shown at line 10. The various write pending flags form a "pyramid" or hierarchy of write pending flags which the system may search when no access to records stored on disks is requested for handling write pending requests. Such a hierarchy structure allows the system to inquire level by level within the structure whether any records on the device; any records within a group of cylinders; any records on a, given cylinder; any records on a track; and record by record, whether any write pending flags are set or whether any records are located in cache memory. Such information is useful when processing data such as writing data to disk after a power failure as more fully described in U.S. application Ser. No. 07/586,254 filed concurrently herewith and incorporated herein by reference. U.S. application Ser. No. 07/586,254 was continued in U.S. application Ser. No. 156,394 filed Nov. 22, 1993, which issued on Aug. 23, 1994 as U.S. Pat. No. 5,341,493. The "last track" header is a header of a fictitious or non-existent track and serves to indicate that the record locator table was itself modified and must also be written to disk. A more detailed description of the cylinder header portions 82a-82c of the device record identification and locator table 70 of FIG. 4 is shown in Table 2 wherein any given cylinder header includes such information as the length of the cylinder header, line 1; cylinder write pending flags, line 4; the physical address of the cylinder line 6; and the CRC error check byte of the cylinder, line 7.
TABLE 2
CYLINDER ID TABLE HEADER BUFFERS AND FLAGS OFFSETS
LENGTH OF CYL HEADER
1. CYL_HEADER_LENGTH SIZE $A0 AT ID TABLE
2. CYL_FLAG OFFSET 0 CYL FLAGS
3. CYL_FLAG_AUX OFFSET 1 ADD ON TO THE ABOVE
4. CYL_WR_PEND_FLAGS OFFSET 2 WR PENDING BIT PER TRACK
5. CYL_STATISTICS OFFSET 4 STATISTICS/RESERVED BYTES
6. CYL_PH_ADD OFFSET 16 PH ADD OF CYL
7. CYL_SLOT_CRC OFFSET 23 CRC OF CYL
Each track entry in the record identification and locator table is shown in greater detail in FIG. 5 and comprises a track header portion 84 and a track body portion 86. The track header portion 84 includes information as shown in Table 3 below, including a track flag byte, line 1; record-count bytes, line 2,; the track CRC check byte, line 3; track compress patterns line 4; and cache address pointer, line 5. The body 86, FIG. 5 of the track portion of the record identification and locator table includes a plurality of record flags 83, (line 6, Table 3,) beginning at byte 20 and record modifiers 85 (line 7, Table 3) beginning at byte 159 and extending sequentially backward as necessary or until a collision with the record flags 83 ocurr.
TABLE 3
ID TABLE TRACK HEADER AND BODY OFFSETS
1. TRACK_FLAG OFFSET 0 TRACK FLAGS
2. RECORD_COUNT OFFSET 1 NUMBER OF RECORDS AT
THIS TRACK
3. TRACK_CRC OFFSET 5 CRC BYTE FOR TRACK
4. COMPRESS_PATTERNS OFFSET 6 TRACK COMPRESS
PATTERNS
5. CACHE_TRACK_POINTER OFFSET 14 POINTER TO CACHE
6. RECORD_FLAGS OFFSET 20 .fwdarw. 159 COMMON FLAG
POINTER
7. TRACK_TABLE_BODY OFFSET 159 .fwdarw. 20 TRACK BODY
(MODIFIER)
TRACK COMMON FLAG BITS
8. DEFECTTVE BIT 7 DEFECTIVE TRACK
9. ALT BIT 6 ALTERNATE TRACK
10. EX_TRACK_TABLE BIT 5 EXTENDED TRACK TABLE
SLOT
11. WRT_PEND BIT 4 WRITE PENDING IN TRACK
12. DIAG_CYL BIT 3 DIAGNOSTICS CYL (`CE`,
`SA`)
13. NOT_USED BIT 2 NOT USED
14. INVALID_ID BIT 1 ID SLOT DEFECTWE AND
INVALID
15. IN_CACHE BIT 0 TRACK IN CACHE FLAG
RECORD FLAGS BITS
16. COMPRESS_CODE BITS 0-3 COMPRESS ALGO' FOR
THIS
RECORD
17. KEY_IN_CACHE BIT 4 KEY FIELD IN CACHE
18. DATA_IN_CACHE BIT 5 DATA FIELD IN CACRE
19. KEY_W_PEND BIT 6 KEY FTELD WRITE
PENDING
20. DATA_W_PEND BIT 7 DATA FIELD WRiTE
PENDING
The track flags shown on line 1 in table 3 are described in detail on lines 8-15 and include such bits indicating a defective track bit, line 8; a write pending bit, line 11; and a track in cache bit, line 15. Similarly, the record flag bits of line 6 are shown in greater detail in lines 16-20 including bits comprising the compression algorithm for this record, line 16; key and data fields in cache, lines 17 and 18; and key field and data field write pending bits, lines 19 and 20. The channel adapters 12a-12d, FIG. 1, receive data and read/write commands from one or more hosts over its respective channels. The data records are provided by the host in CKD format and are stored in cache memory 16 in CKD format. All records stored in cache whether temporarily while awaiting writing to disk, or records which have been read from the disk to be stored in cache for quicker access, are stored in CKD format. When the record is to be written to the disk drive, one of disk adapters 20 reads the data from cache memory over bus 18 and converts the CKD formatted data to the format of the present invention including a record identifier and locator table all of which can be stored in a plurality of fixed blocks before outputting the data over the disk adapters' SCSI interface to one or more of disk drives 22. The present method for mapping CKD formatted data into fixed block disk drives is, in part, based on the recognition that under usual conditions, a sequence of CKD formatted records will include the "R" portion of the count identifying the record number from among a number of sequentially numbered data records of the same length. Further, the records are generally stored on the same device cylinder and accessed by the same device head. Additionally, the key length will generally be zero or some predetermined generally constant number. Thus, the method for disk mapping 100, FIG. 6 of the present invention includes establishing the profile of an expected record, step 110. In the preferred embodiment, the expected record is established with the count CCHH code as the physical cylinder and head identification, as well as the key length (K.sub.1)=0, data length (D.sub.1)=8 and the "R" byte of the count assigned as record number (n)=0. Further, the record flags are set to 00. During step 112, the system employing the method of the present invention obtains the first CKD formatted record and compares the CKD record with the previously established expected record step 114. At step 116, a determination is made as to whether or not the CKD formatted record including the "count" and record flags match those of the expected data record. If the CKD formatted record and the expected record match, the method proceeds to step 118 wherein the body of the track portion of the record identification and locator table previously discussed in conjunction with FIG. 5 and table 3 is built. Since the CKD formatted record matched the previously established expected data record, the record flag is set to 00 and no entry is made in the record modifier portion of the track ID cable. Subsequently, the "R" byte for the record number of the next expected data record is incremented by one, step 120, before returning to the step of obtaining the next CKD formatted data record at step 112. If the results of the comparison at step 116 indicate that the CKD formatted record does not match the expected data record, the method proceeds to step 122 wherein a change format code (see Table 5) and record modifier, as required, are prepared. Next, the record format code and, if required, record modifier are inserted into the track identification table, step 124. If the track ID table is not full as determined at step 126, processing continues to step 128 wherein the current CKD count becomes the next expected count. Processing then returns to step 120 where the "R" byte is incremented by one before getting the next CKD record at step 112. If, as indicated at step 126, the track identification table is full, meaning that the record flag portion of the ID table has collided with the record modifier portion of the ID table, the method of the instant invention will attempt to compress or shrink the body of the track ID table as shown in flowchart 130, FIG. 7. During the compression process of the instant invention, the system and method of the present invention attempt to define from one to eight data lengths which are repeated within this track. Such repeating data lengths are then classified as "patterns" and are thereafter referred to by a pattern "code" in the track header as shown on line 4 of Table 3, thus saving up to 2 bytes in the modifier portion of the track ID table for each repeated data length. The method of the present invention first reads the ID table, step 132, searching for ID's with format code 03 for repeating values of data lengths, step 134. From those repeating values, the system and method of the present invention build a data length pattern table beginning with the data length that is most frequently repeated, and continuing on to find the seven most repeated data lengths and replaces the old 8 byte pattern with the new 8 byte pattern, step 136. The method then proceeds to compare the data lengths of all the CKD records of the current track which have previously been read to determine whether or not any of the data lengths match the data patterns loaded in the pattern table, step 138. If any data lengths match the data patterns in the pattern table, the method proceeds to insert the data pattern code for the data length in a temporary ID table. Thus, the replaced record modifiers which previously contained the changed or modified data lengths are now unnecessary and eliminated, thus compressing or shrinking the size of the record identification and locator table and therefore allowing more room for the system to complete reading the CKD records for a given track. The system verifies at step 140, that the ID table was in fact compressed. If no ID table compression was achieved, the system reports an error, step 142. If ID table compression was achieved, the method replaces the old ID table with the temporary ID table with compressed counts, step 144, before returning to step 120, FIG. 6. Although this count compression routine somewhat reduces system performance, the time to compute repeating data patterns and thus, to compress the "count" information in a record identification and locator table is minimal when compared to the tremendous savings of time which results from the ability to search the record locator table containing the count information in semiconductor memory instead of searching the disk drives for the requested record given the respective access times. An example of a record identification and locator table for track 0 of a representative disk drive along with decoded information of each record is reproduced below as Table 4. This track identification and record locator table forms part of the device record identification and locator table as discussed previously in conjunction with FIG. 4. Line 2 of Table 4 corresponds to the track header portion 84, FIG. 5 of the track identification table also previously discussed in conjunction with table 3. The second byte of the header, the number "5" indicates that there are five records on this track.
TABLE 4
1. TRACK NUMBER 0
2. FLAGS/COUNT/H/W/R/S/PAT/CACHE PTR: 00 5 00 00 00 00 0000000000000000
00000000
3. FLAGS 00 01 03 03 01
4. BODY: 0000000000000000 0000000000000000 0000000000000000
0000000000000000
5. 0000000000000000 0000000000000000 0000000000000000
0000000000000000
6. 0000000000000000 00000000000000O0 0000000000000000
0000000000000000
7. 0000000000000000 0000000000000000 0000000000000000
000000000000000F
3. B0E050900418A0
RECORD FLAGS
REC ID KEY DATA WR IN NON PHYSICAL
ADDRESS
# CCHHR LENGTH LENGTH PEND CACHE STD BLOCK
TRACK CACHE ADD
9. 00 0000000000 00 0008 . .. 00 00000000
02E0
10. 01 0000000001 04 0018 .. .. 01 00000001
04E0
11. 02 0000000002 04 0090 .. .. 03 00000002
0800
12. 03 0000000003 04 0050 .. .. 03 00000003
0B80
13. 04 0000000004 00 OFBO .. .. 01 00000004
0EC0
Line 3 begins the record flag portion of the track identification table and is comprised of five record flags namely, flags: 00; 01; 03; 03; and 01. Each of the record flags is associated with a corresponding record, in ascending order. Thus, record flag 00 is associated with data record 0; record flag 01 is associated with data record 1; and record flag 03 is associated with data record 2 and so forth. A representation of a record modifier portion of the track identification and locator table is shown at lines 4-8 of Table 4. As discussed in conjunction with FIG. 5, the record modifier portion of the track identification and record locator table is read backwards beginning with the byte, "A0" of line 8. The track identification and record locator table of Table 4 may be further understood in conjunction with lines 9-13. As shown on line 9, which identifies record 0 of this track, the second, third and fourth columns comprise the original "count" information of the CKD record. It should be noted that this record matches the description of the "expected" record utilized in the example, associated with the method of FIG. 6 since the first record on the track is record 0, the key length is 0, and the data length is 8 bytes. Thus, the record locator flag associated with that record, "00" is the first record flag byte encountered on line 3. Proceeding to line 10, record number 1 on the track has a key length of 04 and a data length of 18 and thus, deviates from the previously established "expected" data record and thus is assigned a record flag of 01. Various codes which comprise the record flags are reproduced in Table 5 below wherein as shown in line 1, the code 00 means no change to the previously established "expected" record. As shown in line 2 of the table, record flag format 01 indicates that the first byte of the record modifier is the change flag byte, indicating that every bit flagged with a "1" points to the byte in the record identifier that should be replaced by the following bytes in the record modifier. The order of the record identifier is shown in line 7 of table 5 and begins with the key length, followed by data length (high), data length (low) and the first byte of the cylinder.
TABLE 5
RECORD FORMAT CHANGE CODES
1. ID FLAG FORMAT CODE 0: NO CHANGE
2. ID FLAG FORMAT CODE 1: 1ST BYTE OF MODIFIER IS THE CHANGE FLAG BYTE
3. EVERY BIT FLAGGED POINTS TO BYTE IN THE
4. ID THAT SHOULD BE REPLACED BY THE NEXT INFO
BYTES.
5. NUMBER OF EXTRA INFO BYTES IS THE NUMBER OF
`1`S
6. IN THE 1ST BYTE. THIS CODE IS USED IF WE
CAN'T USE
ANY OTHER CODE.
7. :K.sub.L D.sub.LH D.sub.LL C CHHR
8. ID FLAG FORMAT CODE 2: ONE BYTE LNFO TO DL L + DL H = 2
9. ID FLAG FORMAT CODE 3: ONE BYTE INFO TO DL L + DL H = 0
10. ID FLAG FORMAT CODE 4: ONE BYTE INFO TO DL L DL H UNCHANGED
11. ID FLAG FORMAT CODE 5: TWO BYTES INFO TO DL
12. ID FLAG FORMAT CODE 6: ONE BYTE INFOR TO DL L + DL H = 1
13. ID FLAG FORMAT CODE 7: ONE BYTE INFO TO DL L + DL H = PATT FROM ID
TABLE HEADER
14. ID FLAG FORMAT CODE 8: DL L = PATT #0 FROM ID TABLE HEADER + DL H =
0
15. ID FLAG FORMAT CODE 9: DL L = PATT #1 FROM ID TABLE HEADER + DL H =
0
16. ID FLAG FORMAT CODE A: DL L = PATT #2 FROM ID TABLE HEADER + DL H =
0
17. ID FLAG FORMAT CODE B: DL L = PATT #3 FROM ID TABLE HEADeR + DL H =
0
IS. ID FLAG FORMAT CODE C: DL L = PATT #4 FROM ID TABLE HEADER + DL H =
0
19. ID FLAG FORMAT CODE D: DL L = PATT #5 FROM ID TABLE HEADER + DL H =
0
20. ID FLAG FORMAT CODE E: DL L = PATT #6 FROM ID TABLE HEADER + DL H =
0
21. ID FLAG FORMAT CODE F: DL L = PATT #7 FROM ID TABLE HEADER + DL H =
0
Thus, returning now to line 10 of table 4, the flag code 01 indicates that the first byte of the modifier namely, "A0" indicates the bits that are to be changed in the record identifier. Reading change byte A0 in conjunction with line 7 of Table 5 discloses that the successive bytes in the record modifier will modify the key length and data length (low) of the data record. The record modifier bytes in the track identification table modify the record identifier in reverse order as that shown in line 7 of Table 5 that is, from record number to key length. Thus, the second byte, "18" of the record modifier at line 8 of table 4 indicates that the previously expected data length is to be replaced with a data length (low) of "18", while the next byte of the record modifier, "04" is to replace the previously expected key length. It is in this manner that the system "reconstructs" the count portion of a CKD record from the "encoded" record identification and locator table. Record number 2, line 11 of Table 4 also has a key length of "04" but the data length changes to "90". Thus, a flag of 03 is entered. The record flag of 03, as shown at line 9, Table 5. indicates that the next sequential byte of information in the record modifier is to be used as the data length (low) and the data length (high) will equal 0. Thus, the next consecutive entry of "90" in the record modifier portion of the track identification table body is accounted for. Similarly, the next byte of the modifier portion of the track identification table is "50" which is the changed data length of record 3 read in conjunction with a record flag of "03" at line 12 of Table 4. The final record flag "01" in the record flag portion of this track indicates that the next sequential byte namely, "E0" in the record modifier portion of the table is the changed flag byte pointing to the bytes in the record identifier that are to be changed or modified by the subsequent bytes in the record modifier portion of the table. Code E0 indicates that the key length, data length (high) and data length (low) are to be changed by the three bytes which follow as indicated by line 7, table 5. Thus, byte "B0" of the record modifier is used as the data length (low); byte "0F" is used as the data length (high) byte, and byte 00 modifies the former key length entry. The building of a record identification and locator table in accordance with the present invention greatly reduces the amount of fixed block disk space required to store the "count" portion of a CKD formatted data record. An additional example of a track level record identification and locator table is reproduced in table 6 below and is useful in showing an entry in the data pattern table previously described in conjunction with FIG. 7. Table 6 is a representation of a track identification table for an exemplary
TABLE 6
1. TRACK NUMBER D00
2. FLAGS/COUNT/H/W/R/S/PAT/CACHE PTR: 11 81 00 00 00 C7 3e14131500FB9024
03FDE000
3. FLAGS 00A320 28 202020XX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
4. XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
5. XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XX
6. BODY: XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
7. XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXX28
RECORD FLAGS
REC ID KEY DATA WR IN FORMAT
PHYSICAL ADDRESS
# CCHHR LENGTH LENGTH PEND CACHE CODE BLOCK
TRACK CACHE ADD
8. 00 00D0000000 00 0008 .. .. 0
00047DB0 02E0
9. 01 00D0000001 00 0028 D. D. 3
00047DB1 04E0 03FDE118
10. 02 00D0000002 00 0028 .. D. 0
00047DB2 0700 03FDE150
11. 03 00D0000003 00 003E .. D. 8
00047DB3 0920 03FDE188
12. 04 00D0000004 00 003E .. D. 0
00047DB4 0B60 03FDE1D0
13. 05 00D0000005 00 003E .. D. 0
00047DB5 0DA0 03FDE218
14. 06 00D0000006 00 003E .. D. 0
00047DB6 0FEO 03FDE260
On line 2 of table 6, the track "header" information is presented including the first byte "11" indicating that on this track, there is at least one record which is in cache, and at least one record which has a write pending, as previously explained in conjunction with Table 3. The second byte of the track header, "81" indicates there are 81 records in this track, while byte 5, "C7" is the CRC byte for this track. The next byte of the header, "3E" is the first byte of the data pattern table which extends for 8 bytes ending with "24". In this example, bytes 1-7 of the pattern table are not used, but are merely shown for illustrative purposes only. The last four bytes of the track header, "03 FD E0 00" is the cache beginning memory address at which any records from this track which are stored in cache are located. Of particular interest in Table 6 is record 03 located at line 11. Since the data length, "3E" of record 3 is a deviation from the previously established data length "28", a record flag of other than 00 is expected, and thus the record flag "08" is entered. As can be compared from line 14 of the record flag codes in Table 5, record flag code "08" indicates that the data length (low) of this record identifier is to be loaded with pattern 0, the first pattern from the identification table header and thus, the "3E" pattern from line 2 of Table 6 is used as the data length for record number 3 when the system reconstructs the data record. The record flag, "28" which is shown and underlined on line 3 of table 6 also indicates that the data of this record is stored in cache. The cache address is ascertained by adding up the cache memory starting address (line 2) contained in the header of the track identification table along with the length of any intervening data or key information stored in cache. Modifications and substitutions of the present invention by one of ordinary skill in the art are considered to be within the scope of the present invention, which is not to be limited except by the claims which follow.
|
Same subclass Same class Consider this |
||||||||||