United States Patent [19]
`Bergsten
`
`[54] DATA STORAGE CONTROLLER
`PROVIDING MULTIPLE HOSTS WITH
`ACCESS TO MULTIPLE STORAGE
`SUBSYSTEMS
`
`[75]
`
`Inventor:
`
`James R. Bergsten, Saratoga, Calif.
`
`[73] Assignee: Ark Research Corporation, San Jose,
`Calif.
`
`[21] Appl. No.: 08/828,888
`
`[22]
`
`Filed:
`
`Mar. 31, 1997
`
`[51]
`[52]
`
`[58]
`
`[56]
`
`Int. CI? ...................................................... G06F 12/02
`U.S. CI. ........................... 711/114; 7111148; 711/153;
`7111162; 707/204; 714/204
`Field of Search ............................. 707/204; 711/162,
`7111148, 114, 153; 714/6
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`3,889,237
`4,718,006
`5,155,845
`5,408,629
`5,455,932
`5,459,842
`5,459,857
`5,481,276
`5,504,882
`5,530,845
`5,588,132
`5,615,364
`5,673,381
`5,673,382
`5,675,802
`5,680,580
`5,692,147
`5,699,510
`5,708,769
`5,729,735
`5,740,433
`5,742,792
`5,765,200
`5,768,623
`
`.................... 395/182.04
`
`...................... 711/148
`6/1975 Alferness et al.
`1/1988 Nishida ................................... 711/148
`10/1992 Beal et al.
`.............................. 395/575
`4/1995 Tsuchiva et al.
`....................... 711/151
`10/1995 Major et al. ............................ 711/162
`10/1995 Begun et al. .
`10/1995 Ludlam et al.
`1/1996 Dickey et al. .
`4/1996 Chai et al. ......................... 395/182.03
`6/1996 Hiatt et al. .
`12/1996 Cardoza .................................. 711/148
`3/1997 Marks ..................................... 707/202
`9/1997 Huai et al. .............................. 395/180
`9/1997 Cannon et al.
`.................... 395/182.04
`10/1997 Allen et al. .... ... ... ... ... .... ... ... ... 395/703
`10/1997 Beardsley et al. ...................... 711/162
`11/1997 Larson et al. .
`12/1997 Petersen et al. ................... 385/185.07
`1/1998 Stallmo . ... ... ... .... ... ... ... ... ... .... ... ... 714/6
`3/1998 Mayering .................................. 707/10
`4/1998 Carr et al. .. .... ... ... ... ... .... ... ... ... 707/202
`4/1998 Yanai et al. ............................. 711/162
`6/1998 McIlvain et al. ....................... 711/170
`6/1998 Judd et al. .............................. 395/857
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US006073209A
`[11] Patent Number:
`[45] Date of Patent:
`
`6,073,209
`Jun. 6,2000
`
`5,794,013
`5,926,833
`
`8/1998 McBrearty ......................... 395/500.48
`7/1999 Rasulian et al. ........................ 711/147
`
`FOREIGN PATENT DOCUMENTS
`
`PCT/US93/
`05853
`WO 94/00816
`PCT/US94/
`01447
`WO 94/19743
`
`6/1993 WIPO.
`1/1994 WIPO.
`
`2/1994 WIPO.
`9/1994 WIPO.
`
`OTHER PUBLICATIONS
`
`Brochure, "CacheXchange: General Description, Legacy
`Series 690/9090," Andor International, Ltd., 1991.
`
`Primary Examiner-Hiep T. Nguyen
`Attorney, Agent, or Firm-Blakely, Sokoloff, Taylor &
`Zafman LLP
`
`[57]
`
`ABSTRACT
`
`A computer network comprises a number of storage
`controllers, each coupled to one of a plurality of storage
`arrays, each storage array including at least one mass storage
`device. Each storage controller may be coupled to at least
`one host processing system and to at least one other storage
`controller to control access of the host processing systems to
`the mass storage devices. Multiple copies of data are main(cid:173)
`tained in storage arrays that are geographically remote to
`each other, such that any copy can be accessed by any host.
`Each storage controllers includes an interface with a host
`that emulates a mass storage device and an interface with a
`local storage array that emulates a host. The interfaces to the
`host and local storage arrays are independent of the type of
`host or devices in the local storage array. Two or more hosts
`may be dissimilar to each other, and two or more storage
`arrays may include dissimilar mass storage devices. Hosts
`access stored data using virtual addressing. During a data
`access, the storage controller connected to the accessing host
`maps a virtual address provided by the host to a real physical
`location in any of the storage arrays, such that the actual
`location of the data is transparent to the host. The storage
`controllers provide automatic back-up and error correction
`as well as write protection of back-up copies.
`
`40 Claims, 18 Drawing Sheets
`
`I
`I
`I
`I
`I 7
`
`TO/FROM
`HOST
`
`EMULATION
`DRIVERS
`2.1
`
`i~
`:
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`lr-g
`I
`I
`I-------------t-------------~
`
`I
`I
`I
`I
`
`~ !
`
`PHYSICAL
`DRIVERS
`2Z
`
`TO/FROM
`LOCAL EXTERNAL
`STORAGE DEVICES
`
`MEMORY
`2±
`
`;
`
`OS
`2.Q
`
`;
`
`COMMUNICATION
`DRIVERS
`~
`
`TO/FROM
`OTHER STORAGE
`CONTROLLERS
`
`Oracle Ex. 1007, pg. 1
`
`

`

`u.s. Patent
`
`Jun. 6,2000
`
`Sheet 1 of 18
`
`6,073,209
`
`1--------------1
`1
`----~: ~I
`1 MSD
`MSD
`4-1-1 f-- 4-1-2 -
`1
`1
`1 ..... _ - - - - - - -
`
`1
`4-1 1
`
`____ MSD
`4-2-0
`
`1
`
`1
`1
`
`~ I
`
`1
`4-2 1
`
`1
`
`____ MSD
`4-M-P
`
`~ I
`
`1
`
`1
`
`HOST
`2:1
`
`S7
`
`S8
`
`STORAGE
`CONTROLLER
`3-1
`
`I---r' 9
`
`HOST
`2-2
`
`S7
`
`S8
`
`STORAGE
`CONTROLLER
`3-2
`
`~9
`
`-.....J' 9
`
`HOST
`2-M
`
`S7
`
`S8
`
`STORAGE
`CONTROLLER
`3-M
`
`1 - - - - - - - - -
`1
`1 MSD
`4-2-1 -
`I
`1
`1 ..... _ - - - - - - -
`
`MSD
`4-2-2 r---
`
`MSD
`4-M-2 r---
`
`FIG. 1
`
`1--------
`1
`1 MSD
`1 4-M-1 -
`1
`1
`1
`4-M 1
`..... _ - - - - - - - - - - - - - -
`
`Oracle Ex. 1007, pg. 2
`
`

`

`u.s. Patent
`
`Jun. 6,2000
`
`Sheet 2 of 18
`
`6,073,209
`
`7
`
`8
`
`STORAGE
`CONTROLLER
`3-1
`
`7
`
`STORAGE
`CONTROLLER
`3-2
`
`STORAGE
`CONTROLLER
`3-3
`
`7
`
`STORAGE
`CONTROLLER
`3-M
`
`8
`
`8
`
`8
`
`FIG. 2
`
`---.....,
`-----------------I----I--~ TORAGE
`I
`co
`NTROLLERI
`I/O
`I/O
`CPU
`RAM
`NVSF
`~
`DEVICE IIF
`DEVICE IIF
`10
`11
`12
`18
`19
`I
`
`I
`
`I
`
`I
`
`HOST
`STORAGE
`CONTROLLER
`DEVICE IIF
`DEVICE IIF
`DEVICE IIF
`15
`16
`14
`r-------- ~8 _____ J W- 9
`~
`~ -- ~7
`i----------
`"
`"
`"
`TOIFROM
`TOIFROM
`TO/FROM
`LOCAL EXTERNAL
`OTHER STORAGE
`HOST
`STORAGE DEVICES
`CONTROLLERS
`
`MSD
`13
`
`___ ...J
`
`FIG. 3
`
`I
`
`I
`
`~
`17
`
`Oracle Ex. 1007, pg. 3
`
`

`

`N = \C
`.... = ""-l
`
`~ ....
`
`0\
`
`FI G 4
`
`•
`
`CONTROLLERS
`OTHER STORAGE
`
`TO/FROM
`
`~
`
`'""'" 00
`o ....,
`~ .....
`'JJ. =(cid:173)~
`
`C
`C
`C
`N
`~~
`
`~
`
`~
`
`~ = .....
`~ .....
`~
`•
`rJl
`d •
`
`STORAGE DEVICES
`LOCAL EXTERNAL
`
`TO/FROM
`
`____ .J
`1
`I
`1
`1
`1
`1
`1
`1
`I ....
`PHYSICAL ~ S : ..
`
`~
`
`DRIVERS
`
`22
`
`8 1
`1
`1
`1
`1
`
`1
`
`_________ _ _______ _
`
`---~9
`
`-
`
`----
`1
`1
`
`COMMUNICATION
`
`DRIVERS
`
`23
`
`...
`...
`
`~
`
`....
`
`"
`
`~~
`
`OS
`
`-20
`
`...
`
`...
`.....
`
`...
`~~ EMULATION
`
`DRIVERS
`
`21
`
`1
`1
`1
`1
`1
`1
`1
`~ I
`
`TO/FROM
`
`HOST
`
`~~
`A~
`
`MEMORY
`
`24
`
`~
`
`7
`
`1
`1
`
`r--------STORAG~ONTROLLER---------I
`
`Oracle Ex. 1007, pg. 4
`
`

`

`u.s. Patent
`
`Jun. 6,2000
`
`Sheet 4 of 18
`
`6,073,209
`
`RAM
`~
`
`I
`
`NVSF
`32
`
`I
`
`CPU
`30
`
`I
`
`I
`
`MSD
`33
`
`r------------------------------~
`I
`HOST
`I
`2-R
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`j~8 ~~9 I
`h
`h
`-----------------------------~
`,'V
`~r
`"
`TO/FROM
`TO/FROM
`TO/FROM TO/FROM
`CLIENTS/OTHER
`CLiENTS/
`LOCAL OTHER
`OTHER HOSTS
`EXTERNAL STORAGE
`HOSTS
`STORAGE CONTROLLERS
`
`I
`
`STORAGE
`CONTROLLER
`36
`
`MODEM
`34
`
`NETWORK
`ADAPTER
`35
`
`FIG. 5
`
`Oracle Ex. 1007, pg. 5
`
`

`

`u.s. Patent
`
`Jun. 6,2000
`
`Sheet 5 of 18
`
`6,073,209
`
`610
`
`610
`
`612
`
`613
`
`614
`
`EXIT, NO DEVICE
`ERROR
`
`EXIT, NO DEVICE
`ERROR
`
`EXIT WITH RESET
`NOTIFICATION
`
`EXIT, NOT READY
`ERROR
`
`EXIT WITH BUSY
`CONDITION
`
`615
`
`EXIT WITH
`RESERVATION CONFLICT
`
`EXIT, ILLEGAL
`REQUEST ERROR
`
`616
`
`616
`
`YES
`
`EXIT, ILLEGAL
`REQUEST ERROR
`
`EXIT CHECKS COMPLETE
`WITHOUT ERROR
`
`FIG. 6
`
`Oracle Ex. 1007, pg. 6
`
`

`

`u.s. Patent
`
`Jun. 6,2000
`
`Sheet 6 of 18
`
`6,073,209
`
`INPUT = HOST
`INTERFACE 10, HOST
`BLOCK NUMBER
`
`701
`
`YES
`
`POINT TO TOP
`ELEMENT IN TREE
`
`POINT AT ELEMENT TO LOWER
`THE LEFT OF THIS
`ELEMENT
`
`WITHIN
`
`707
`
`HIGHER
`
`OUTPUT = LOGICAL
`DEVICE 10, LOGICAL
`BLOCK NUMBER
`
`POINT AT ELEMENT TO
`THE RIGHT OF THIS
`ELEMENT
`
`705
`
`FIG. 7
`
`Oracle Ex. 1007, pg. 7
`
`

`

`N = \C
`.... = ""-l
`
`~ ....
`
`0\
`
`'""'" 00
`o ....,
`-..J
`~ .....
`'JJ. =(cid:173)~
`
`C
`C
`C
`N
`~~
`
`~
`
`~
`
`~ = .....
`~ .....
`~
`•
`rJl
`d •
`
`FIG. 8
`
`• • •
`
`• • •
`
`• • •
`
`• • •
`
`LOGICAL DEVICE I LOGICAL BLOCK
`
`LOGICAL DEVICE I LOGICAL BLOCK
`
`RANGE
`
`43
`
`RANGE
`
`42
`
`RANGE
`
`41
`
`~40
`
`Oracle Ex. 1007, pg. 8
`
`

`

`u.s. Patent
`
`Jun. 6,2000
`
`Sheet 8 of 18
`
`6,073,209
`
`INPUT = LOGICAL
`DEVICE 10, BLOCK
`NUMBER
`
`901
`
`YES
`
`POINT TO TOP
`ELEMENT IN TREE
`
`POINT AT ELEMENT TO LOWER
`THE LEFT OF THIS
`ELEMENT
`
`WITHIN
`
`907
`
`HIGHER
`
`OUTPUT = PHYSICAL
`DEVICE 10, PHYSICAL
`BLOCK NUMBER
`
`POINT AT ELEMENT TO
`THE RIGHT OF THIS
`ELEMENT
`
`905
`
`FIG. 9
`
`Oracle Ex. 1007, pg. 9
`
`

`

`u.s. Patent
`
`Jun. 6,2000
`
`Sheet 9 of 18
`
`6,073,209
`
`CHOOSE NEAREST FREE DEVICE 14 - - - - - - - - - - - - ,
`HOUSING DATA
`
`MAP "LOGICAL TO PHYSICAL
`BLOCK ADDRESS"
`. - - -___ ----L ____ ---" 1 003
`READ BLOCK(S)
`
`....--___ ----L ____ ---" 1005
`CALL "READ ERROR RECOVERY"
`IF ANY BLOCK WAS BAD
`
`NO
`
`....--____ ~Y_E_S ___ ___. 1007
`RECONNECT AND TRANSFER BLOCK(S)
`TO THE HOST ("HOST DATA READ")
`
`~_~ DISCONNECT FROM
`THE HOST
`
`PRESENT ENDING STATUS
`TO HOST
`
`1012
`
`1009
`
`FIG. 10
`
`Oracle Ex. 1007, pg. 10
`
`

`

`u.s. Patent
`
`Jun. 6,2000
`
`Sheet 10 of 18
`
`6,073,209
`
`1101
`
`READ DATA FROM
`NEXT NEAREST
`PHYSICAL COPY
`
`WRITE AND VERIFY
`DATA TO BAD BLOCK
`
`CALL WRITE
`ERROR RECOVERY
`
`EXIT WITH
`ERROR CODE
`
`LOG AND
`EXIT
`
`FIG. 11
`
`Oracle Ex. 1007, pg. 11
`
`

`

`u.s. Patent
`
`Jun. 6,2000
`
`Sheet 11 of 18
`
`6,073,209
`
`1211
`,-----<:'--'
`NO
`EXIT COPING
`COMPLETE
`
`.---___ ----. 1213
`PRESENT ENDING
`STATUS TO HOST
`AND DISCONNECT t---~
`FROM BUS
`
`1212
`...---_L.----'"
`RECONNECT YES
`TO THE HOST
`
`MARK THIS COpy
`IDENTICAL WITH
`CACHE,DECREMENT
`SHARED LOCK
`
`PERFORM
`WRITE
`ERROR
`RECOVERY
`
`1214
`
`YES
`
`1216
`
`SUSPEND COPYING
`POSSIBLY
`ASSIGN HOT SPARE
`
`FIG. 12
`
`Oracle Ex. 1007, pg. 12
`
`

`

`u.s. Patent
`
`Jun. 6,2000
`
`Sheet 12 of 18
`
`6,073,209
`
`REASSIGN BLOCK,
`WRITE AND VERIFY
`DATA TO NEW BLOCK
`
`~------1.(LOG AND EXIT ~06
`
`1303
`
`WRITE DATA TO
`INTERNAL DISK
`
`~--------~ LOG AND EXIT
`
`1305
`
`ESTABLISH NEW
`COPY(SEEIICOPY
`ESTABLISH")
`
`FIG. 13
`
`Oracle Ex. 1007, pg. 13
`
`

`

`u.s. Patent
`
`Jun. 6,2000
`
`Sheet 13 of 18
`
`6,073,209
`
`.--____ ----''-____ ----,,'"'' 1401
`HOST PRESENTS DATA READ REQUEST
`
`1402
`
`Jr-Y_ES~ ___ ..-.t EXIT PRESENTING
`ERROR STATUS
`
`1410
`
`MAP HOST INTERFACE TO LOGICAL
`.-----I~ DEVICE (SEE "LOGICAL MAP")
`
`1403
`
`YES
`
`DISCONNECT FROM
`HOST
`
`1411
`
`r--___ -...L ____ .......,r\1406
`INCREMENT SHARED LOCK AND
`TRANSFER DATA TO THE HOST
`
`1412
`
`QUEUE "STAGING"
`TASK
`
`DECREMENT BLOCK'S SHARE LOCK
`
`YES
`
`PRESENT ENDING STATUS TO HOST
`AND DISCONNECT FROM BUS
`
`1409
`
`FIG. 14
`
`Oracle Ex. 1007, pg. 14
`
`

`

`u.s. Patent
`
`Jun. 6,2000
`
`Sheet 14 of 18
`
`6,073,209
`
`EXIT PRESENTING
`=>--~ ERROR STATUS
`
`EXIT PRESENTING
`----,.:-==--·1 ILLEGAL REQUEST
`
`EXIT PRESENTING
`~----~I ILLEGAL REQUEST
`
`MAP HOST INTERFACE
`TO LOGICAL DEVICE M--""';;;;"'"
`(SEE "LOGICAL MAP")
`
`----.~-_~
`
`ALLOCATE
`EMPTY BLOCK
`IN CACHE
`
`1520
`
`1518
`
`1522 STAGE DATA BLOCK
`FROM PHYSICAL
`STORAGE
`
`TRANSFER DATA
`FROM HOST TO BLOCK
`IN CACHE
`
`1510
`
`PRESENT ENDING
`>-Y_ES_~STATUS TO HOST AND
`DISCONNECT FROM
`BUS
`
`FIG. 15
`
`QUEUE DATA
`DESTAGING
`("DESTAGING") TASK
`
`Oracle Ex. 1007, pg. 15
`
`

`

`u.s. Patent
`
`Jun. 6,2000
`
`Sheet 15 of 18
`
`6,073,209
`
`1609
`
`SEND TEST
`~---+I MESSAGE TO
`CHECK LINE
`STATUS
`
`TRANSMIT DATA
`PACKET(S), WAIT FOR
`ACKNOWLEDGMENT
`
`CALL LINE
`ERROR RECOVERY
`
`WAIT FOR REQUEST
`COMPLETE MESSAGE
`
`NO
`
`_----..r-..1607
`CALL LINE
`ERROR RECOVERY
`
`FIG. 16
`
`Oracle Ex. 1007, pg. 16
`
`

`

`u.s. Patent
`
`Jun. 6,2000
`
`Sheet 16 of 18
`
`6,073,209
`
`1701
`
`SEND COMMUNICATIONS
`DATA PACKET TO OTHER ...... - - - - - ,
`SYSTEM
`
`YES
`
`>-_-.., EXIT WITH ERROR
`CONDITION
`
`FIG. 17
`
`Oracle Ex. 1007, pg. 17
`
`

`

`u.s. Patent
`
`Jun. 6,2000
`
`Sheet 17 of 18
`
`6,073,209
`
`PREPARE TO
`COPY ONE OR
`MORE CONTIGUOUS
`BLOCKS
`
`ATTEMPT ERROR
`RECOVERY THEN EXIT
`
`1805
`
`OBTAIN EXCLUSIVE
`>----1~ LOCK, READ BLOCKS I--~
`FROM SOURCE
`
`1808
`INCREMENT TO
`NEXT BLOCK COPY 14----1 MARK BLOCKS ..__-----.
`BOUNDARY
`IDENTICAL
`
`EXCHANGE
`EXCLUSIVE LOCK FOR
`SHARED LOCK, WRITE
`BLOCKS TO
`DESTINATION
`
`EXIT - COpy
`ESTABLISHED
`
`ATTEMPT ERROR
`RECOVERY THEN EXIT
`
`FIG. 18
`
`Oracle Ex. 1007, pg. 18
`
`

`

`u.s. Patent
`
`Jun. 6,2000
`
`Sheet 18 of 18
`
`6,073,209
`
`ATTEMPT TO READ A BLOCK
`1901
`
`NO
`
`YES
`
`CALL READ ERROR
`RECOVERY
`1905
`
`ATTEMPT TO READ
`ANOTHER BLOCK
`1904
`
`FIG. 19
`
`Oracle Ex. 1007, pg. 19
`
`

`

`6,073,209
`
`2
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`1
`DATA STORAGE CONTROLLER
`PROVIDING MULTIPLE HOSTS WITH
`ACCESS TO MULTIPLE STORAGE
`SUBSYSTEMS
`
`FIELD OF THE INVENTION
`
`The present invention is illustrated by way of example
`and not limitation in the figures of the accompanying
`5 drawings, in which like references indicate, similar elements
`and in which:
`FIG. 1 illustrates a computing system in which a number
`of storage controllers provide multiple host computers with
`access to multiple storage arrays.
`FIG. 2 illustrates a computing system according to an
`embodiment in which one storage controller is connected to
`a number of other storage controllers.
`FIG. 3 is a block diagram of a storage controller.
`FIG. 4 is a block diagram illustrating functional modules
`of a storage controller.
`FIG. 5 is a block diagram illustrating a host computer
`system including a storage controller according to the
`present invention.
`FIG. 6 is a flow diagram illustrating a check routine
`performed in response to an input/output request.
`FIG. 7 is a flow diagram illustrating a routine for mapping
`a host address to a logical address.
`FIG. 8 illustrates a tree hierarchy used by a storage
`25 controller to map a host address to a logical address.
`FIG. 9 is a flow diagram illustrating a routine for mapping
`a logical address to a physical address.
`FIG. 10 is a flow diagram illustrating a routine performed
`by a storage controller for staging data from a mass storage
`device.
`FIG. 11 is a flow diagram illustrating a read error recovery
`routine.
`FIG. 12 is a flow diagram illustrating a routine performed
`by a storage controller for destaging data to a mass storage
`device.
`FIG. 13 is a flow diagram illustrating a write error
`recovery routine.
`FIG. 14 is a flow diagram illustrating a routine performed
`by a storage controller for reading data from a mass storage
`device in response to a request from a host.
`FIG. 15 is a flow diagram illustrating a routine performed
`by a storage controller for writing data to a mass storage
`device in response to a request from a host.
`FIG. 16 is a flow diagram illustrating a routine performed
`by a storage controller for transmitting data to a remote
`storage controller.
`FIG. 17 is a flow diagram illustrating a remote commu(cid:173)
`nications error recovery routine.
`FIG. 18 is a flow diagram illustrating a routine for
`establishing copies.
`FIG. 19 is a flow diagram illustrating a routine performed
`by a storage controller for performing automatic detection
`55 and correction of data errors.
`
`The present invention pertains to the field of computer
`systems. More particularly, the present invention relates to
`devices which control data flow between one or more host
`processing systems and one or more data storage sub- 10
`systems.
`
`BACKGROUND OF THE INVENTION
`
`Computer systems sometimes handle valuable or irre(cid:173)
`placeable data. Data maintained by a computer system may 15
`be of vital importance, for example, in business applications
`such as airline reservations, bank account management,
`electronic funds transfers, shipping and receiving, and
`inventory control. Consequently, there is a need to ensure
`that valuable data is adequately protected against loss or 20
`damage.
`It is common to store large volumes of data on non(cid:173)
`volatile mass storage devices, such as magnetic or optical
`disks. Occasionally, however, a mass storage device will
`fail, resulting in the loss of stored data. Consequently, it is
`a common practice to store a back-up copy of data that is
`considered valuable on a separate, back-up storage device.
`For practical reasons, however, it is often necessary to locate
`the back-up storage device in the same geographic vicinity 30
`as the primary storage device. As a result, both the primary
`data and the back-up copy may be lost or destroyed due to
`theft, vandalism, or natural disasters, such as fires, floods,
`and earthquakes. Hence, there is a need for the capability to
`store multiple back-up copies of data in geographically 35
`separate locations, while still permitting quick and easy
`access by a host computer to any back-up copy.
`In particular, it is desirable to provide a storage controller
`which provides the above-mentioned functionality. It is
`further desirable that such a storage controller allow mul- 40
`tiple host computers at different locations to access any copy
`of stored data. It is further desirable that such a storage
`controller automatically create and manage multiple back-
`up copies while the host computers are "on line" in a manner
`that is transparent to the host computers and their users. It is 45
`further desirable that such a storage controller automatically
`detect and correct errors in stored data and automatically
`replace faulty copies. It is further desirable that such a
`storage controller not be dependent upon any particular
`hardware or software configuration of any host computer or 50
`mass storage device which it services.
`
`SUMMARY OF THE INVENTION
`
`The present invention includes a storage controller that
`includes a data interface with a host processing system and
`a data interface with at least one storage array. Each storage
`array includes at least one mass storage device. The host
`interface is independent of a device type of the host pro(cid:173)
`cessing system, and the storage interface is independent of
`the device type of the mass storage devices. The data storage 60
`controller further includes control circuitry coupled to the
`host interface and the storage interface. The control circuitry
`is configured to enable the host processing system to access
`each of the storage arrays.
`Other features of the present invention will be apparent 65
`from the accompanying drawings and from the detailed
`description which follows.
`
`DETAILED DESCRIPTION
`
`A storage controller capable of providing multiple host
`computers system with access to multiple storage arrays is
`described. In the following description, for purposes of
`explanation, numerous specific details are set forth in order
`to provide a thorough understanding of the present inven(cid:173)
`tion. It will be evident, however, to one skilled in the art that
`the present invention may be practiced without these specific
`details. In other instances, well-known structures and
`devices are shown in block diagram form in order to
`facilitate description of the present invention.
`
`Oracle Ex. 1007, pg. 20
`
`

`

`6,073,209
`
`3
`As will be described below in detail, the present invention
`includes a storage controller which allows multiple host
`computer systems at different locations to access any of
`multiple copies of stored data. The storage controller auto(cid:173)
`matically creates and manages multiple back-up copies
`while the host computer systems are "on line" in a manner
`that is both non-disruptive of, and transparent to, the host
`computer systems and their users. Further, the storage con(cid:173)
`troller automatically detects and correct errors in stored data
`and automatically replaces faulty copies. Moreover, the
`storage controller is not dependent upon any particular
`hardware or software configuration of the host computer
`system which it services or the mass storage devices which
`it accesses. The storage controller emulates a local storage
`array for the host computer system which it services and
`emulates a host computer system for the local storage array
`which it accesses. Host computer systems access stored data
`using virtual device addresses, which are mapped to real
`device addresses by the storage controller.
`FIG. 1 illustrates a computing system in which a number
`of storage controllers of the present invention provide a
`number of host computer systems with access to a number
`of storage arrays. Specifically, the computing system
`includes M storage controllers, 3-1 through 3-M; M host
`computers, 2-1 through 2-M, which are coupled to storage
`controllers 3-1 through 3-M, respectively; and M storage
`arrays, 4-1 through 4-M, which are coupled to the storage
`controllers 3-1 through 3-M, respectively. Each of the stor(cid:173)
`age arrays includes a number of mass storage devices
`(MSDs) coupled to a storage controller in a daisy chain
`configuration. Specifically, storage array 4-1 includes N
`MSDs, 4-1-1 through 4-1-N; storage array 4-2 includes 0
`MSDs, 4-2-1 through 4-2-0; and, storage array 4-M
`includes P MSDs, 4-M-l through 4-M-P.
`Each of the storage controllers is coupled to another
`storage controller via a communication link 9. A portion of
`a communication link 9 between two geographically(cid:173)
`separated storage controllers may be provided by a local
`area network (LAN). For example, in one embodiment, a
`given communication link 9 may be implemented partly on
`a Fast Ethernet; other portions of the link 9 can be imple(cid:173)
`mented as an ATM (Asynchronous Transfer Mode) link, a
`T1 or T3 link, an FDDI (Fiber Distributed Data Interface)
`link, or any other suitable type of link.
`Note that any of the data communication paths 7, 8, and
`9 may actually consist of two or more redundant, physical
`paths. Therefore, a failure of any single physical connection
`does not affect the ability to access any stored data.
`Each of the host computer systems 2 may be any con(cid:173)
`ventional computer system. For example, a host computer
`system may be a personal computer (PC), a mini-computer,
`or a mainframe. In addition, any of the host computer
`systems may function as a server for one or more client
`computer systems (not shown).
`Each MSD may be include non-volatile facility for storing
`large volumes of data, such as a magnetic disk or tape, an
`optical storage device such as CD-ROM (Compact Disk(cid:173)
`ROM), CD-R (CD-recordable), DVD (Digital Versatile
`Disk), a magneto-optical (MO) device, or the like. The
`MSDs within the computing system need not be of the same
`device type. That is, the MSDs in any given storage array
`may use a different type of storage medium from those in
`any other storage array.
`Each storage array may be located geographically distant 65
`from the other storage arrays. Multiple copies are generally
`maintained on different, geographically-separated storage
`
`4
`arrays. Hence, the loss of one or more MSDs in a given
`storage array will not result in the complete loss of data.
`With respect to a given (local) storage controller, any or all
`of the other (remote) storage controllers, host computer
`5 systems, and storage arrays may therefore be located at
`distant locations to the local storage controller.
`Storage controllers 3-1 through 3-M function coopera(cid:173)
`tively to provide any of host computer systems 2-1 through
`2-M with access to any of storage arrays 4-2 through 4-M.
`10 Each one of storage controllers 3-1 through 3-M directly
`services one local host computer system and one local
`storage array in one embodiment. For example, in the
`embodiment shown in FIG. 1, storage controller 3-1 services
`and is directly coupled to its local host computer system 2-1
`15 via a data communication path 7. Storage controller 3-1 also
`is directly coupled to its local data storage array 4-1 via
`another communication path 8.
`In one embodiment, each storage controller communi(cid:173)
`cates with its local host computer system and its local
`20 storage array using standard SCSI (Small Computer Systems
`Interface) protocols. Consequently, operation of a storage
`controller of the present invention in the manner described
`herein is not dependent upon the particular hardware or
`software configuration of any host computer or storage
`25 array, as long as those devices are SCSI-compatible. Note
`that in other embodiments, however, the data communica(cid:173)
`tion paths 7 and 8 may conform to other protocols and
`standards, such as serial SCSI, Fiber Channel, or ESCON.
`Thus, because data paths 7 and 8 are conventional interfaces,
`30 a storage controller of the present invention can be used
`concurrently with host computers and MSDs having differ(cid:173)
`ent configurations. For example, one host computer in the
`system may be a mainframe computer system while another
`host computer is a Pc. Similarly, one storage array in the
`35 system may consist of conventional magnetic hard disk
`drives while another storage array consists of CD-ROM
`drives.
`The storage controllers in the computing system cooper-
`40 ate to allow any of the host computer systems to access data
`located in any of the storage arrays. For example, host
`computer system 2-1 may access data located on any MSD
`in storage array 4-1 by communicating with storage con(cid:173)
`troller 3-1. In addition, host computer system 2-1 may
`45 access data located in remote storage array 4-M by com(cid:173)
`municating with remote storage controller 3-M via storage
`controllers 3-1, 3-2, etc. As will be explained below, data is
`accessed using virtual addressing, such that a host computer
`system has no knowledge of which physical storage device
`50 is being accessed.
`The storage controllers operate in peer-to-peer relation(cid:173)
`ships (as opposed to master-slave relationships) with each
`other when responding to remote access requests. Any
`storage controller can access data in a remote storage array
`55 serviced by any other storage controller. Communication
`between individual storage controllers takes place on com(cid:173)
`munication links 9 using a common protocol implemented
`by all storage controllers in the system. Note that various
`different protocols might be used for this purpose. Adescrip-
`60 tion of the details of such a protocol is not necessary for a
`full understanding of the present invention and is therefore
`not included herein.
`The remote access capabilities of the storage controllers
`can be used advantageously in a variety of ways. The storage
`controllers can be used to enable sharing and centralized
`control of storage media. For example, the MSDs in any of
`the storage arrays may include CD-ROM devices, so that
`
`Oracle Ex. 1007, pg. 21
`
`

`

`6,073,209
`
`10
`
`40
`
`5
`CD-ROMs in one a storage arrays may be shared by all host
`computers. Use of the devices can be recorded by one of the
`storage controllers. Access to CD-ROM data can therefore
`be monitored and controlled by a user, such as a system
`administrator, using the storage controller. The present
`invention also permits low-volume production of CD-Rs
`without specialized equipment. For example, a limited quan(cid:173)
`tity of CD-R disks can be produced by writing to a single,
`logical CD-R drive corresponding to multiple physical
`CD-R devices within one or more storage arrays.
`The present invention is not limited to the specific con(cid:173)
`figuration shown in FIG. 1. For example, the system con(cid:173)
`figuration might alternatively include only a single host
`computer which is coupled to multiple geographically(cid:173)
`separated storage arrays using multiple storage controllers. 15
`In another embodiment, a storage controller may have a
`direct interface with more than one host or may have
`redundant interfaces with the same host. Each storage con(cid:173)
`troller might also be coupled to more than one other storage
`controller, as illustrated in FIG. 2, in which storage control- 20
`ler 3-1 is connected to a number of other storage controllers,
`3-2 through 3-M.
`The storage controllers provide a number of functions and
`services to the host computer systems. In particular, the
`storage controllers automatically provide multiple back-up
`copies of stored data in a manner that is transparent to, and
`non-disruptive of, all of the host computer systems. For
`example, when a given data file is saved by a local host
`computer to its local storage array, the local storage con(cid:173)
`troller causes one or more back-up copies of the data file to
`be stored in one or more of the remote storage arrays,
`without any intervention from or interruption to the local
`host computer. The process of backing-up data can be
`initiated by any storage controller in the system. This allows
`centralized back-up of any or all of the host computers. The
`number of back-up copies to be created and the locations to
`which the back-up copies are to be stored can be configured
`in advance by a system administrator. For example, these
`parameters can be programmed into a storage controller by
`connecting a keyboard and a display to ports on the storage
`controller. Alternatively, the storage controller can be con(cid:173)
`figured by using one of the host computers to transmit
`configuration commands and data to the storage controller.
`Further, a remote storage controller can be configured via a
`local storage controller. The storage controller of the present 45
`invention also performs automatic block error detection and
`reassignment, as will be described below in detail.
`The remote data access, data mirroring, and path redun(cid:173)
`dancy provided by the present invention allow recovery
`from many possible failure modes, such as failure of com(cid:173)
`munication medium, failure a host computer, or failure of a
`storage device.
`In general, when the system of FIG. 1 is first set up, or
`when MSDs are added to the system, all data from a
`"primary" MSD are automatically copied to one or more
`newly-added MSDs. Such copying is performed while the
`host computers are operating, although the copying process
`is transparent to the host computers 2-1 through 2-M.
`Copying can be throttled to reduce the impact on system 60
`performance. Once all copies are established (brought into a
`consistent state), only changed data are subsequently written
`to the secondary MSDs in response to changes dictated by
`a host computer.
`Each of the storage controllers also provides virtualized
`data access and emulation, as mentioned above. A local
`storage controller will emulate its local storage array from
`
`6
`the viewpoint of its local host computer system; similarly,
`the local storage controller will emulate its local host
`computer system from the viewpoint of its local storage
`array. Such emulation is implemented, in part, by using a
`5 common communication interface for data communication
`paths 7 and 8, such as SCSI. Again, in other embodiments,
`the data communication paths 7 and 8 may conform to other
`protocols and standards, such as serial SCSI, Fiber Channel,
`or ESCON.
`A local host computer accesses data by transmitting a
`(virtual) host address to its local storage controller. The host
`address is then mapped to a real address representing a
`location on one or more physical MSDs, as will be described
`below in detail. The mapping is completely transparent to all
`of the host computers. To improve performance, the storage
`controller may distribute a single copy among multiple
`MSDs, which may be located in different storage arrays.
`Hence, in the above described mapping process, a single
`host address may map to multiple physical addresses, which
`may be distributed among multiple MSDs, and such MSDs
`may further be located in different storage arrays.
`FIG. 3 illustrates the hardware architecture of a storage
`controller of the present invention according to one embodi(cid:173)
`ment. The storage controller 3 includes a central processing
`25 unit (CPU) 10, random-access memory (RAM) 11, a non(cid:173)
`volatile storage facility (NVSF) 12, an MSD 13, each of
`which is coupled to a bus 17. Bus 17 may represent multiple
`physical or logical buses, which may be interconnected by
`various adapters and/or controllers. NVSF 12 may be, or
`30 may include, a programmable non-volatile storage device,
`such as flash memory or electrically erasable programmable
`read-only memory (EEPROM). MSD 13 may be any con(cid:173)
`ventional device that is suitable for non-volatile storage of
`large volumes of data, such as any of those discussed above.
`35 Also coupled to the bus 17 are a host device interface 14, a
`storage device interface 15, a controller device interface 16,
`and input/output (I/O) device interfaces 18 and 19. I/O
`device interfaces 18 and 19 are also coupled to