VWGoA - Ex. 1010
`Case No. IPR2015-01613
`Volkswagen Group of America, Inc. - Petitioner
`Joao Control & Monitoring Systems, LLC - Patent Owner
`
`1
`
`

`
`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 1 of 6
`
`5,404,361
`
`Emmam
`
`.V35
`
`mama
`
`mamaxma
`
`mmo<z<s_
`
`
`
`
`
`s_Em»mm5mmoqmobm.<.:..3
`
`
`
`:2:.6528
`
`OO_
`
`mo<mO._.m
`
`OI._..<n_
`
`
`
`mosh.O._.m
`
`N_._._.<m
`
`mo<mo.5
`
`nI._.<n_
`
`$9..
`
`mowmmoomm
`
`.So:
`
`.mommmooE
`
`2
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 2 of 6
`
`5,404,361
`
`3
`
`

`
`U
`
`9
`
`4
`
`11
`
`
`
`ML>E.zm..o<u_._>Ezmn93:
`
`
`
`
`
`Sm.+|%»Ezmoem:mommom..m._m<.rmo_>mo._<2.m_>
`
`mm.mIbfizmNEm...»Ezm_om..
`
`.V:m.cIA»m._.zmNSm:
`
`.m0ias3.): .&.:,_mE»E.zuoo<m.._..<:.E__>iE5.._%m.mm._.z_on_»m2.omm_oV65:
`
`
`
`
`§E,_aas:._§,__>
`
`
`
`
`
`
`
`
`
`%_mm_..;._on_»mo5m.m_oxo<E.._§._.m_>
`
`6_%mI._.mm.._n_omosmm%mmmmooqmmoz..c6
`
`
`
`._<o_oo._momg._Nam.mmmm.mmmm%..
`
`
`59.9.3“.52.5.
`
`.V845.._<:E.>ms=..._o>._<o_oo._
`.m~.muoz&.mz_vommmmssz
`
`
`
`%a.m.0_n_2.:uxué2.M3.:mumaom
`
`4
`
`
`

`
`LlHetaP.&U
`
`Apr. 4, 1995
`
`Sheet 4 of 6
`
`5,404,361
`
`:2%Eos_m_s_
`
`—2.5Eosmz
`
`.9.
`
`
`
`$595.8Eozmz
`
`:3
`
`N5.
`
`3:.
`
`2.5Eofis
`
`3858BE
`
`«$52
`
`Es.
`
`$5gaze
`
`.mac
`
`rv:
`
`34.
`
`_._.¢
`
`V.6?‘
`
`<55.5..I¢m¢
`.5$88..Ell
`u<S
`,_%m._I2A1-Efillulllnl
`.I582$Io<au
`xfllnfiu
`
`-I.<53
`
`
`55.8..
`
`
`
`
`
`N3.
`
` m.aEz8oom<o>mos_m_2«SE28m=§§m._Essa:.5528
`
`
`
`
`
`mmanfi1wm_w.~__>n__ma<«mm_E2
`
`5
`
`
`
`
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Apr. 4, 1995
`
`Sheet 5 of 6
`
`5,404,361
`
`SETUP FOR READ?
`
`50.
`
`605
`
`
`
`IS
`
`VIRTUAL
`TRACK IN
`CACHE MEMORY
`?
`
`
`
`
`NO
`
`
`
`RETURN
`success
`
`
`LOOK UP
`VIRTUAL TRACK
`
`ADDRESS IN
`VIRTUAL T0
`LOGICAL MAP
`
`
`
`
`
`
`MAP LOGICAL
`DEVICE TO PHYSI-
`
`CAL DEVICEISI
`
`—
`
`602
`
`
`
`AssuRE VIRTUAL
`TRACK OF
`
`
`
`
`
`INFORMATION IN
`CACHE MEMORY
`
`
`
`
`TRANSFER DATA
`FROM STAGED VIRTUAL
`TRACK INSTANCE
`
`-
`
`.
`
`5|?
`
`CLEANUP READ
`
`6'8
`
`RETURN
`
`6'9
`
`
`
`
`'
`
`SCHEDULE
`
`PHYSICAL READ(8)
`
`CLEAR ERRORS
`FOR OPERATION
`
`
`
`ALL READS
`COMPLETED
`?
`
`
`
`609
`
`6 I4
`
`63
`I
`
`"0
`
`RETURN
`ERROR
`
`WAIT FOR NEXT
`COMPLETION
`
`6'2
`
`6|5
`
`GI6
`
`ANY
`ERRoRs
`7
`ygs '
`
`MARK ERRORS
`
`F|G.5.
`
`
`
`
`FIXED ?
`
`EY s
`
`FIX ERRoR(s)
`
`
`
`
`
`
`
`ANY
`ERRORS
`
`YE
`
`I
`
`S
` ERRORS BE
`
`6
`
`

`
`US. Patent
`
`Apr. 4, 1995
`
`I Sheet 6 of 6
`
`5,404,361
`
`SETUP FOR WRITE
`
`7o|
`
`
`
`ASSURE VIRTUAL TRACK OF
`INFORMATION IN CACHE
`
`MEMORY
`
`‘
`
`TRANSFER DATA INTO STAGED
`VIRTUALTRACK INSTANCE
`
`_ STEPS 603 - 6l6
`
`702
`
`703
`
`
`
`704
`
`
`
`
`SCHEDULE MODIFIED
`VIRTUAL TRACK TO
`
`BE WRITTEN
`
`
`
`
`
`
`DOES
`VIRTUAL
`
`CURRENT OPE
`
`
`
`,
`
`-
`
`CLEANUP WRITE
`
`7:2
`
`UPDATE FREE
`SPACE DIRECTORY
`
`713
`
`.
`
`RETURN
`
`7I4
`
`
`
`WW5 OPEN
`CYEINDER
`
`L G|cAL
`
`TRACK F". m”
`L°°'°"'-
`
`
`CYLINDER
`
`
`
`
`
`
`SELECT
`NEW EMPTIED
`LOGICAL CYLINDER
`FROM MOST FREE
`LOGICAL DEVICE _
`
`
`YES
`
`
`
`PLACE VIRTUAL
`TRACK IN
`LOGICAL CYLINDER
`
`
`
`
`
`
`ADDRESS IN VIRTUAL
`TO LOGICAL MAP
`
`
`UPDATE VIRTUAL TRACK
`
`
`
`
`
`
`MARK VIRTUAL TRACK
`INSTANCE OBSOLETE ON
`LOGICAL DEVICE
`
`RETURN
`
`F|G.6.
`
`7
`
`

`
`1
`
`5,404,361
`
`METHOD AND APPARATUS FOR ENSURING
`DATA INTEGRITY IN A DYNAMICALLY MAPPED
`DATA STORAGE SUBSYSTEM
`
`FIELD OF THE INVENTION
`
`This invention relates to dynamically mapped data
`storage subsystems and, in particular, to a method and
`apparatus for confirming the integrity of data and its
`corresponding address.
`
`PROBLEM
`
`It is a problem in dynamically mapped data storage
`subsystems to maintain accurate mapping information
`to denote the correspondence between data records
`received from a host computer and identified by a vir-
`tual address and the physical memory location in which
`the data is stored. This problem is particularly relevant
`with regard to the address information that is used to
`control the physical. storage of data on the data storage
`devices used within the dynamically mapped data stor-
`age subsystem. A failure to accurately identify the phys-
`ical storage location of the data results in the loss of the
`data since it cannot be properly retrieved by the data
`storage subsystem from the data storage devices.
`One example of a dynamically mapped data storage
`subsystem is a disk array system which stores data on a
`plurality of small form factor disk drives while present-
`ing the image of a large form factor disk drive to the
`host computer. A plurality of the small form factor disk
`drives are dynamically interconnected to form a redun-
`dancy group to store the data records received from the
`host computer. The control unit for the disk array sys-
`tem allocates the physical memory locations on the
`small form factor disk drives in the redundancy groups
`to store data records that are received from the host
`computer. The control unit also maps the virtual ad-
`dress for each data record received from the host com-
`puter to physical memory location addresses on the
`plurality of small form factor disk drives in a selected
`redundancy group that are used to store the received
`data record. Therefore, a failure of the controller to
`properly note the correspondence between the? data
`record virtual address and the physical memory loca-
`tions on the plurality of disk drives that contain the data
`records results in the loss of the data. Furthermore, the
`data records and the physical memory location address
`information are concurrently transmitted from the con-
`troller and its associated cache memory to the disk
`controllers that interface the plurality of small form
`factor disk drives to a storage control unit that functions
`to interface with the host computer. Any errors in the
`transmission of the physical memory location address
`information from the disk storage controller to the disk
`controller would also result in the loss of the data since
`the disk controller would store the data records in the
`improper physical memory location on the plurality of
`small form factor disk drives. Therefore, when the stor-
`age control unit requests access to the data records
`using the address information from the mapping tables,
`the disk controller would retrieve data other than that
`requested by the storage control unit since the original
`data records were placed in memory locations other
`than that indicated by the address information con-
`tained in the mapping memory. It is therefore essential
`to ensure that no errors in the address information occur
`in either the mapping tables or in the transmission of
`address information within the data storage subsystem
`
`2
`itself, such as between the storage control unit and the
`disk controller. There presently exists no method or
`apparatus to prevent the occurrence of errors within the
`data storage subsystem, such as in the transmission of
`address information from the storage control unit to the
`disk controllers.
`
`SOLUTION
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`The above described problems are solved and a tech-
`nical advance achieved in the field by the method and
`apparatus for ensuring data integrity in a dynamically
`mapped data storage subsystem. This is accomplished
`by making use of an error correcting code generated
`across the data as well as the associated address infor-
`mation for each data transfer within the data storage
`subsystem between a storage control unit and the mem-
`ory controller for the data storage devices. The error
`correcting code that is used to safeguard the data is
`selected to have additional error detection and correc-
`tion capacity above that needed for that purpose. This
`additional capacity is used to also protect the address
`information transmitted with the data record to ensure
`that the address information is also error free. The stor-
`age control unit, upon the initiation of a data record
`transfer to the memory controller, creates the error
`correcting code across the data record that is being
`transferred. The physical memory storage location ad-
`dress, assigned by the storage control unit, to store this
`particular data record is also input to the error correct-
`ing algorithm to provide address error protection. The
`memory controller, upon receipt of the data transmis-
`sion from the storage control unit, recomputes the error
`correcting code across the received data and address
`information and compares the newly computed error
`code with that transmitted by the storage control unit to
`identify whether any errors occurred in the transmis-
`sion of the data from the storage control unit to the
`memory controller. In this manner, not only the data
`but the address information is protected internal to the
`dynamically mapped data storage subsystem to provide
`a level of data integrity heretofore not available in data
`storage subsystems.
`
`BRIEF DESCRIPTION OF THE DRAWING
`
`FIG. 1 illustrates in block diagram form the architec-
`ture of a disk drive array data storage subsystem;
`FIG. 2 illustrates the cluster control of the data stor-
`age subsystem;
`FIG. 3 illustrates the format of the virtual track direc-
`tory;
`FIG. 4 illustrates additional details of the cache mem-
`ory; and
`FIGS. 5 and 6 illustrate, in flow diagram form, the
`operational steps taken to perform a data read and write
`operation, respectively.
`
`DETAILED DESCRIPTION OF THE DRAWING
`
`A dynamically mapped virtual memory data storage
`subsystem is used to illustrate‘ the data integrity feature
`of the present invention. This data storage subsystem
`uses a plurality of small form factor disk drives in place
`of a single large form factor disk drive to implement an
`inexpensive, high performance, high reliability disk
`drive array memory that emulates the format and capa-
`bility of large form factor disk drives (DASD). The
`plurality of disk drives in the disk drive array data stor-
`age subsystem are configured into a plurality of variable
`
`8
`
`

`
`5,404,361
`
`4
`rate performance of the data storage subsystem by
`transferring these overhead tasks to background pro-
`cesses.
`
`3
`size redundancy groups of N+M connected disk drives
`to store data thereon. Each redundancy group, also
`called a logical disk drive, is divided into a number of
`logical cylinders, each containing i logical tracks, one
`logical track for each of the i physical tracks contained
`in a cylinder of one physical disk drive. Each logical
`track is comprised of N+M physical tracks, one physi-
`cal track from each disk drive in the redundancy group.
`' The N+M disk drives are used to store N data seg-
`ments, one on each of N physical tracks per logical
`track, and to store M redundancy segments, one on each
`of M physical tracks per logical track in the redundancy
`group. The N+M disk drives in a redundancy group
`have unsynchronized spindles and loosely coupled actu-
`ators. The data is transferred to the disk drives via inde-
`pendent reads and writes since all disk drives operate
`independently.
`.
`The disk drive array data storage subsystem includes
`a data storage management system that provides im-
`proved data storage and retrieval performance by dy-
`namically mapping between virtual and physical data
`‘storage devices. The disk drive array data storage sub-
`system consists of three abstract layers: virtual, logical
`and physical. The virtual layer functions as a conven-
`tional large form factor disk drive memory. The logical
`layer functions as an array of storage units that are
`grouped into a plurality of redundancy groups, each
`containing N+M physical disk drives. The physical
`layer functions as a plurality of individual small form
`factor disk drives. The data storage management system
`operates to effectuate the dynamic mapping of data
`among these abstract layers and to control the alloca-
`tion and management of the actual space on the physical
`devices. These data storage management functions are
`performed in a manner that renders the operation of the
`disk drive array data storage subsystem transparent to
`the host processor which perceives only the virtual
`image of the disk drive array data storage subsystem.
`The performance of this system is enhanced by the
`use of a cache memory with both volatile and nonvola-
`tile portions and “backend” data staging and destaging
`processes. No data stored in a redundancy group is
`modified. A virtual track is staged from a redundancy
`group into cache. The host then modifies some, perhaps
`all, of the records on the virtual track. Then, as deter-
`mined by cache replacement algorithms such as Least
`Recently Used, etc, the modified virtual track is se-
`lected to be destaged to a redundancy group. When
`thus selected, a virtual track is divided (marked off) into
`several physical sectors to be stored on one or more
`physical tracks of one or more logical tracks. A com-
`plete physical track may contain physical sectors from
`one or more virtual tracks. Each physical track is com-
`bined with N—l other physical tracks to form the N
`data segments of a logical track.
`The original, unmodified data is simply flagged as
`obsolete. Obviously, as data is modified, the redun-
`dancy groups increasingly contain numerous virtual
`tracks of obsolete data. The remaining valid virtual
`tracks in a logical cylinder are read to the cache mem-
`ory in a background “free space collection” process.
`They are then written to a previously emptied logical
`cylinder and the “collected” logical cylinder is tagged
`as being empty. Thus, all redundancy data creation,
`writing and free space collection occurs in background,
`rather than on—demand processes. This arrangement
`avoids the parity update problem of existing disk array
`systems and improves the response time versus access
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`In this data storage subsystem, memory storage loca-
`tion addresses are dynamically assigned to the data as it
`is transferred into cache memory and between the
`cache memory and the backend data storage devices.
`Any corruption of these dynamically assigned addresses
`results in the loss of the data within the data storage
`subsystem. Therefore, the address information must be
`protected from errors as well as the data itself.
`Data Storage Subsystem Architecture
`FIG. 1 illustrates in block diagram form the architec-
`ture of the preferred embodiment of the disk drive array
`data storage subsystem 100. The disk drive array data
`storage subsystem 100 appears to the associated host
`processors 11-12 to be a collection of large form factor
`disk drives with their associated storage control, since
`the architecture of disk drive array data storage subsys-
`tem 100 is transparent to the associated host processors
`11-12. This disk drive array data storage subsystem 100
`includes a plurality of disk drives (ex 122-1 to 125-r)
`located in a plurality of disk drive subsets 103-1 to 103-i.
`The disk drives 122-1 to 125-r are significantly less
`expensive, even while providing disk drives to store
`redundancy information and providing disk drives for
`backup purposes, than the typical 14 inch form factor
`disk drive with an associated backup disk drive. The
`plurality of disk drives 122-1 to 125-r are typically the
`commodity hard disk drives in the 5?; inch form factor.
`The architecture illustrated in FIG. 1 is that of a
`plurality of host processors 11-12 interconnected via
`the respective plurality of data channels 21, 22-31, 32,
`respectively to a data storage subsystem 100 that pro-
`vides the backend data storage capacity for the host
`processors 11-12. This basic configuration is well
`known in the data processing art. The data storage
`subsystem 100 includes a control unit 101 that serves to
`interconnect the subsets of disk drives 103-1 to 103-i and
`their associated drive managers 102-1 to 102-i with the
`data charmels 21-22, 31-32 that interconnect data stor-
`age subsystem 100 with the plurality of host processors
`11, 12.
`Control unit 101 includes typically two cluster con-
`trols 111, 112 for redundancy purposes. Within a cluster
`control 111 the multipath storage director 110-0 pro-
`vides a hardware interface to interconnect data chan-
`nels 21, 31 to cluster control 111 contained in control
`unit 101. In this respect, the multipath storage director
`110-0 provides a hardware interface to the associated
`data channels 21, 31 and provides a multiplex function
`to enable any attached data channel (such as 21) from
`any host processor such as 11) to interconnect to a
`selected cluster control 111 within control unit 101. The
`cluster control 111 itself provides a pair of storage paths
`201-0, 201-1 which function as an interface to a plurality
`of optical fiber backend channels 104. In addition, the
`cluster control 111 includes a data compression function
`as well as a data routing function that enables cluster
`control 111 to direct the transfer of data between a
`selected data channel 21 and cache memory 113, and
`between cache memory 113 and one of the connected
`optical fiber backend channels 104. Control unit 101
`provides the major data storage subsystem control func-
`tions that include the creation and regulation of data
`redundancy groups, reconstruction of data for a failed
`disk drive, switching a spare disk drive in place of a
`failed disk drive, data redundancy generation, logical
`
`9
`
`

`
`5
`device space management, and virtual to logical device V
`mapping. These subsystem functions are discussed in
`further detail below.
`
`5,404,361
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`Disk drive manager 102-1 interconnects the plurality '
`of commodity disk drives 122-1 to 125-r included in disk
`drive subset 103-1 with the plurality of optical fiber
`backend channels 104. Disk drive manager 102-1 in-
`cludes an input/output circuit 120 that provides a hard-
`ware interface to interconnect the optical fiber backend
`channels 104 with the data paths 126 that serve control
`and drive circuits 121. Control and drive circuits 121
`receive the data on conductors 126 from input/output
`circuit 120 and convert the form and format of these
`signals as required by the associated commodity disk
`drives in disk drive subset 103-1. In addition, control
`and drive circuits 121 provide a control signalling inter-
`face to transfer signals between the disk drive subset
`103-1 and control unit 101. The data that is written onto
`the disk drives in disk drive subset 103-1 consists of data
`that is transmitted from an associated host processor 11
`over data channel 21 to one of cluster controls 111, 112
`in control unit 101. The data is written into, for exam-
`ple, cluster control 111 which stores the data in cache
`113. Cluster control 111 stores N physical tracks of data
`in cache 113 and then generates M redundancy seg-
`ments for error correction purposes. Cluster control 111
`then selects a subset of disk drives (122-1 to 122-n+m)
`to form a redundancy group to store the received data.
`Cluster control 111 selects an empty logical track, con-
`sisting of N+M physical tracks, in the selected redun-
`dancy group. Each of the N physical tracks of the data
`are written onto one of N disk drives in the selected
`data redundancy group. An additional M disk drives are
`used in the redundancy group to store the M redun-
`dancy segments. The M redundancy segments include
`error correction characters and data that can be used to
`verify the integrity of the N physical tracks that are
`stored on the N disk drives as well as to reconstruct one
`or more of the N physical tracks of the data if that
`physical track were lost due to a failure of the disk drive
`on which that physical track is stored.
`Thus, data storage subsystem 100 can emulate one or
`more large form factor disk drives (such as an IBM
`3390-3 type of disk drive) using a plurality of smaller
`form factor disk drives while providing a high reliabil-
`ity capability by writing the data across a plurality of
`the smaller form factor disk drives. A reliability im-
`provement is also obtained by providing a pool of R
`backup disk drives (125-1 to 125-r) that are switchably
`interconnectable in place of a failed disk drive. Data
`reconstruction is accomplished by the use of the M
`redundancy segments, so that the data stored on the
`remaining functioning disk drives combined with the
`redundancy information stored in the redundancy seg-
`ments can be used by control software in control unit
`101 to reconstruct the data lost when one or more of the
`plurality of disk drives in the redundancy group fails
`(122-1 to 122-n+m). This arrangement provides a reli-
`ability capability similar to that obtained by disk shad-
`owing arrangements at a significantly reduced cost over
`such an arrangement.
`Control Unit
`
`45
`
`50
`
`55
`
`6
`201-0 are output on either of the corresponding control
`and data buses 206-C, 206-D, or 207-C, 207-D, respec-
`tively,
`to either storage path 200-0 or storage path
`200-1. Thus, as can be seen from the structure of the
`cluster control 111 illustrated in FIG. 2, there is a signif-
`icant amount of symmetry contained therein. Storage
`path 200-0 is identical to storage path 200-1 and only
`one of these is described herein. The multipath storage
`director 110 uses two sets of data and control busses
`206-D, C and 207-D, C to interconnect each channel
`interface unit 201-0 to 201-7 with both storage path
`200-0 and 200-1 so that the corresponding data channel
`21 from the associated host processor 11 can be
`switched via either storage path 200-0 or 200-1 to the
`plurality of optical fiber backend channels 104. Within
`storage path 200-0 is contained a processor 204-0 that
`regulates the operation of storage path 200-0. In addi-
`tion, an optical device interface 205-0 is provided to
`convert between the optical fiber signalling format of
`optical fiber backend charmels 104 and the metallic
`conductors contained within storage path 200-0. Chan-
`nel interface control 202-0 operates under control of
`processor 204-0 to control the flow of data to and from
`cache memory 113 and one of the channel interface
`units 201 that is presently active with storage path
`200-0. The charmel interface control 202-0 includes a
`cyclic redundancy check (CRC) generator/checker to
`generate and check the CRC bytes for the received
`data. The channel interface circuit 202-0 also includes a
`buffer that compensates for speed mismatch between
`the data transmission rate of the data channel 21 and the
`available data transfer capability of the cache memory
`113. The data that is received by the channel interface
`control circuit 202-0 from a corresponding channel
`interface circuit 201 is forwarded to the cache memory
`113 via channel data compression circuit 203-0. The
`channel data compression circuit 203-0 provides the
`necessary hardware and microcode to perform com-
`pression of the channel data for the control unit 101 on
`a data write from the host processor 11. It also performs
`the necessary decompression operation for control unit
`101 on a data read operation by the host processor 11.
`As can be seen from the architecture illustrated in
`FIG. 2, all data transfers between a host processor 11
`and a redundancy group in the disk drive subsets 103 are
`routed through cache memory 113. Control of cache
`memory 113 is provided in control unit 101 by proces-
`sor 204-0. The functions provided by processor 204-0
`include initialization of the cache directory and other
`cache data structures, cache directory searching and
`management, cache space management, cache perfor-
`mance improvement algorithms as well as other cache
`control functions. In addition, processor 204-0 creates
`the redundancy groups from the disk drives in disk
`drive subsets 103 and maintains records of the status of
`those devices. Processor 204-0 also causes the redun-
`dancy data across the N data disks in a redundancy
`group to be generated within cache memory 113 and
`writes the M segments of redundancy data onto the M
`redundancy disks in the redundancy group. The func-
`tional software in processor 204-0 also manages the
`mappings from virtual to logical and from logical to
`physical devices. The tables that describe this mapping
`are updated, maintained, backed up and occasionally
`recovered by this functional software on processor
`204-0. The free space collection function is also per-
`formed by processor 204-0 as well as management and
`scheduling of the optical fiber backend channels 104.
`
`FIG. 2 illustrates in block diagram form additional
`details of cluster control 111. Multipath storage director
`110 includes a plurality of channel interface units 201-0
`to 201-7, each of which terminates a corresponding pair
`of data channels 21, 31. The control and data signals
`received by the corresponding channel interface unit
`
`65
`
`10
`
`10
`
`

`
`5,404,361
`
`7
`Many of these above functions are well known in the
`data processing art and are not described in any detail
`herein.
`
`Dynamic Virtual Device to Logical Device Mapping
`With respect to data transfer operations, all data
`transfers go through cache memory 113. Therefore,
`front end or channel transfer operations are completely
`independent of backend or device transfer operations.
`In this system, staging operations are similar to staging
`in other cached disk subsystems but destaging transfers
`are collected into groups for bulk transfers. In addition,
`this data storage subsystem 100 simultaneously per-
`forms free space collection, mapping table backup, and
`error recovery as background processes. Because of the
`complete front end/backend separation, the data stor-
`age subsystem 100 is liberated from the exacting proces-
`sor timing dependencies of previous count key data disk
`subsystems. The subsystem is free to dedicate its pro-
`cessing resources to increasing performance through
`more intelligent scheduling and data transfer control.
`The disk drive array data storage subsystem 100 con-
`sists of three abstract layers: virtual, logical and physi-
`cal. The virtual layer functions as a conventional large
`form factor disk drive memory. The logical layer func-
`tions as an array of storage units that are grouped into a
`plurality of redundancy groups (such as 122-1 to 122-
`n+m), each containing N+M disk drives to store N
`physical tracks of data and M physical tracks of redun-
`dancy information for each logical track. The physical
`layer functions as a plurality of individual small form
`factor disk drives. The data storage management system
`operates to effectuate the mapping of data among these
`abstract layers and to control the allocation and man-
`agement of the actual space on the physical devices.
`These data storage management functions are per-
`formed in a manner that renders the operation of the
`disk drive array data storage subsystem 100 transparent
`to the host processors (11-12).
`A redundancy group consists of N+M disk drives.
`The redundancy group is also called a logical volume or
`a logical device. Within each logical device there are a
`plurality of logical tracks, each of which is the set of all
`physical tracks in the redundancy group which have the
`same physical track address. These logical tracks are
`also organized into logical cylinders, each of which is
`the collection of all logical tracks within a redundancy
`group which can be accessed at a common logical actu-
`ator position. A disk drive array data storage subsystem
`100 appears to the host processor to be a collection of
`large form factor disk drives, each of which contains a
`predetermined number of tracks of a predetermined size
`called a virtual track. Therefore, when the host proces-
`sor 11 transmits data over the data channel 21 to the
`data storage subsystem 100, the data is transmitted in
`the form of the individual records of a virtual track. In
`order to render the operation of the disk drive array
`data storage subsystem 100 transparent to the host pro-
`cessor 11, the received data is stored on the actual phys-
`ical disk drives (122-1 to 122-n+m) in the form of vir-
`tual track instances which reflect the capacity of a track
`on the large form factor disk drive that is emulated by
`data storage subsystem 100. Although a virtual track
`instance may spill over from one physical track to the
`next physical track, a virtual track instance is not per-
`mitted to spill over from one logical cylinder to an-
`other. This is done in order to simplify the management
`of the memory space. In addition, virtual track instances
`are padded out if necessary to fit into an integral num-
`
`5
`
`l0
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`8
`ber of physical device sectors. This is to insure that each
`virtual track instance starts on a sector boundary of the
`physical device.
`Mapping Tables
`It is necessary to accurately record the location of all
`data within the disk drive array data storage subsystem
`100 since the data received from the host processors
`11-12 is mapped from its address in the virtual space to
`a physical location in the subsystem in a dynamic fash-
`ion. A virtual track directory is maintained to recall the
`location of the current instance of each virtual track in
`the disk drive array data storage subsystem 100. The
`virtual track directory consists of an entry for each
`virtual track which the associated host processor 11 can
`address. The entry usually contains the logical sector
`address at which the virtual track instance begins. The
`virtual track directory entry also contains data indica-
`tive of the length of the virtual track instance in sectors.
`The virtual track directory is stored in noncontiguous
`pieces of the cache memory 113 and is addressed indi-
`rectly through pointers in a virtual device table. The
`virtual track directory is updated whenever a new vir-
`tual track instance is written to the disk drives.
`Virtual Track Directory
`FIG. 3 illustrates the format of the virtual track direc-
`tory 900 that is contained within cache memory 113.
`The virtual track directory 900 consists of the tables
`that map the virtual addresses as presented by host
`processor 11 to the logical drive addresses that is used
`by control unit 101. There is another mapping that takes
`place within control unit 101 and this is the logical to
`physical mapping to translate the logical address de-
`fined by the virtual track directory 900 into the exact
`physical location of the particular disk drive that con-
`tains data identified by the host processor 11. The vir-
`tual track directory 900 is made up of two parts: the
`virtual track directory pointers 901 in the virtual device
`table 902 and the virtual track directory 903 itself. The
`virtual track directory 903 is not contiguous in cache
`memory 113 but is scattered about the physical extent of
`cache memory 113 in predefined segments (such as
`903-1). Each segment 903-1 has a virtual to logical map-
`ping for a predetermined number of cylinders, for exam-
`ple 102 cylinders worth of IBM 3390-3 type DASD
`tracks. In the virtual device table 902, there are pointers
`to as many of these segments 903 as needed to emulate
`the number of cylinders configured for each of the
`virtual devices defined by host processor 11. The vir-
`tual track directory 900 is created by control unit 101 at
`the virtual device configuration time. When a virtual
`volume is configured, the number of cylinders in that
`volume is defined by the host processor 11. A segment
`903-1 or a plurality of segments of volatile cache mem-
`ory 113 are allocated to this virtual volume defined by
`host processor 11 and the virtual device table 902 is
`updated with the pointers to identify these segments 903
`contained within cache memory 113. Each segment 903
`is initialized with no pointers to indicate that the virtual
`tracks contained on this virtual volume have not yet
`been written. Each entry 905 ‘in the virtual device table
`is for a single virtual track and is addressed by the vir-
`tual track address. As shown in FIG. 3, each entry 905
`is 40 bits long. If the Format Flag is clear the entry 905
`contents are as follows starting with the high order bits:
`Bit 39: Format Flag: When set this flag indicates that
`this entry contains format information.
`Bit 38: Source Flag.
`Bit 37: Target Flag.
`
`11
`
`11
`
`

`
`9
`Bits 36-33: Logical volume number.
`Bits 32-22: Logical cylinder address. This data entry is
`identical to the physical cylinder number.
`Bits 21-7: Sector offset. This entry is the offset to the
`start of the virtual track instance in the logical cylin-
`der, not
`including the redundancy track sectors.
`These sectors typically contained 512 bytes.
`Bits 6-0: Virtual track instance size. This entry notes the
`number of sectors that are required to store. this vir-
`tual track instance.
`If the Format Flag is set, then the Virtual Track Direc-
`tory Entry contains format information as follows:
`Bit 39: Format Flag
`Bits 38-32: Number of Records per Track ,
`Bits 31-24: Encoded Data Record Size
`Bits 23-16: Key Field Length
`Bits 15-0: Relative Cylinder Address
`Data Read Operation
`FIG. 5 illustrates in flow diagram form the opera-
`tional steps taken by processor 204 in control unit 101 of
`the data storage subsystem 100 to read data from a data
`redundancy group 122-1 to 122-n+m in the disk drive
`subsets 103. The disk drive array data storage subsystem
`100 supports reads of any size. However, the logical
`layer only supports reads of virtual track instances. In
`order to perform a read operation, the virtual track
`instance that contains the data to be read is staged from
`the l