`
`(12)
`
`United States Patent
`Coates et a].
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 7,266,555 B1
`Sep. 4, 2007
`
`(54) METHODS AND APPARATUS FOR
`ACCESSING REMOTE STORAGE
`THROUGH USE OF A LOCAL DEVICE
`
`75
`(
`)
`
`_
`~
`_
`Inventors‘ Josh.“ L‘ Coates’ Onnda’ CA (.US)’
`Patrick E. Bozeman, San Francisco,
`CA (US)
`
`t' StCl CA
`73 A' :ItlC
`(
`)
`sslgnee (BS6) “Pom 10"’ an a am’
`
`8/1998 Davis et a1.
`5,796,952 A
`9/1998 Akiyama et a1.
`5,805,699 A
`2/ 1999 Kern et ?l~
`5,870,537 A
`7/1999 Gage et a1.
`5,923,846 A
`8/1999 Aichelen
`5,933,834 A
`8/1999 Balabine et a1. .......... .. 707/100
`5,937,406 A *
`5 978 577 A “H999 R1.
`,
`,
`erden et a1.
`
`(Continued)
`FOREIGN PATENT DOCUMENTS
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U30 154(1)) by 0 days-
`
`EP
`
`8/1994
`0646858 A1
`d
`C _
`( Ommue )
`OTHER PUBLICATIONS
`
`(21) APPL NO; 09/733,314
`
`_
`(22) Filed:
`
`Dec. 8, 2000
`
`Related US. Application Data
`
`(60) Provisional application No. 60/ 186,693, ?led on Mar.
`3, 2000, provisional application No. 60/186,774, ?led
`on Mar. 3,2000.
`
`(51) Int- Cl-
`(2006-01)
`G06F 17/30
`(52) US. Cl. ........................................... .. 707/10; 707/4
`(58) Field of Classi?cation Search ............ .. 707/ 1410,
`707/1004102, 2004206; 709/20(L203
`See application ?le for complete search history.
`_
`References Cited
`
`(56)
`
`U.S. PATENT DOCUMENTS
`
`3/1996 Tysen et a1.
`5,497,422 A
`4/1996 Miller
`5,506,984 A
`8/1996 DuLac
`5,550,986 A
`5,692,155 A 11/1997 Iskiyn et a1.
`5,708,832 A *
`1/1998 Inniss et a1. .............. .. 709/229
`5,757,920 A
`5/1998 Misra et a1.
`5,764,972 A
`6/1998 Crouse et a1.
`
`MOGUL, RFC0917: Internet Subnets, 1984, ACM, pp. 1-17.
`
`(Continued)
`Primary Examineriloon Hwan Hwang
`(74) Attorney, Agent, or F irmiCaroline M. Fleming
`
`ABSTRACT
`
`57
`(
`)
`A network storage system includes a Virtual ?le system
`(“VFS”), to manage the ?les of the network storage system,
`and a stora e center that stores the ?les. The VFS and the
`g
`storage center are separated, such that a client accesses the
`VFS to conduct ?le system operations and the client
`accesses the storage center to upload/download ?les. The
`client accesses the network storage system through one or
`more storage ports. The storage center includes a plurality of
`distributed object storage managers (DOSMs) and a storage
`cluster that includes a plurality of intelligent storage nodes.
`The network storage system includes additional storage
`centers at geographically disparate locations. The network
`storage system uses a multi-cast protocol to maintain ?le
`information at the DOSMs regarding ?les stored in the
`intelligent storage nodes, including ?les stored in disparate
`storage centers.
`
`23 Claims, 32 Drawing Sheets
`
`cum mm
`File symm
`2110
`
`mimicry cm
`1570
`
`Local Flle Symm
`opium"
`
`Opemm sysmm Kgmel
`23w
`
`XMLRaquesu
`swmsynemmsu —> To
`Pro a
`VFS
`z 0
`
`mm
`Wm 71
`
`FIIB Syslem
`mmw
`2:20
`
`Lon-I he Syslzm
`lnlemspmun
`2540
`
`1
`
`Sl?uge System mm
`Plenum:
`2am
`
`Storage mm
`Rlquuu
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 1
`
`
`
`US 7,266,555 B1
`Page 2
`
`US. PATENT DOCUMENTS
`
`6/2000 Popelka et al. ............. .. 712/28
`6,081,883 A *
`8/2000 Tanaka et 91-
`6,108,155 A
`6,128,627 A * 10/2000 Mattis et al. ............. .. 707/202
`6,148,349 A 11/2000 Chow 9t a1~
`6,170,013 B1
`V2001 Mqrata
`6,173,374 B1
`V2001 H911 er 91-
`6,236,999 B1 *
`5/2001 Jacobs et al. ............... .. 707/10
`6,256,673 B1
`7/2001 Gayman
`6,263,402 B1
`7/2001 Ronstrom et al.
`6,272,584 B1
`8/2001 Stancil
`6,304,980 B1
`10/2001 Beardsley et al.
`6,314,465 B1
`11/2001 Paul et al.
`6,324,581 B1
`11/2001 Xu etal.
`6,327,614 B1 * 12/2001 Asano et al. ............. .. 709/213
`6,351,775 B1
`2/2002 Yu
`6,356,929 B1
`3/2002 Gall et al.
`6360306 B1
`3/2002 Bergsten
`6,389,462 B1
`5/2002 Cohen et a1~
`6,393,466 B1
`5/2002 Hickman et a1~
`6,405,201 B1
`6/2002 NaZaTi
`6,438,125 B1
`8/2002 Brothers
`6,442,548 B1
`8/2002 Balabine et al.
`6,507,883 B1
`1/2003 Bello et a1~
`6,553,376 B1
`4/2003 Lewis et 31~
`6,553,389 B1
`4/2003 Golding et a1~
`6,574,641 B1
`6/2003 Dawson et al.
`6,611,869 B1
`8/2003 Eschelbeck et a1.
`6,622,247 B1
`9/2003 Isaak
`6,654,772 B1
`11/2003 CTOW et a1~
`6,704,838 B2
`3/2004 Anderson
`6,718,347 B1 *
`4/2004 Wilson ..................... .. 707/201
`6,782,389 B1
`8/2004 Chrin er al’
`6,895,418 B1
`5/2005 Crow et al.
`6,912,548 B1
`6/2005 Black
`
`6,931,450 B2
`6,948,062 B1
`2002/0010757 A1
`2002/0054114 A1
`2002/00g3120 A1
`2002/0133491 A1
`2002/0133539 A1
`2004/0078465 A1
`2004/007g466 A1
`2004/0088297 A1
`
`8/2005 Howard et al.
`9/2005 Clapper
`1/2002 Granik et 31‘
`5/2002 Shuping etal.
`6/2002 Soltis
`9/2002 Sim et a1.
`9/2002 Monday
`4/2004 Coates et a1.
`4/2004 Comes et 31‘
`5/2004 Coates
`
`FOREIGN PATENT DOCUMENTS
`
`W0
`W0
`W0
`
`WO99/45491
`WO 01/66707 A1
`WO 01/67707 A2
`
`9/1999
`9/2001
`9/2001
`
`OTHER PUBLICATIONS
`Microsoft Press, Computer Dictionary 3rd Editon, 1997, p. 337.
`Kline: Distributed File Systems for Storage Area Networks;
`Advanced Digital Info Corp; 11 pages.
`Apache-SSL: Certi?cates, Con?guration and More Information
`Systems and Technology;University ofWaterloo; Sep. 15, 1998; 16
`pages,
`Schroeder: Implementing Multi-Protocol Authentication/Security
`Systems; Grid (GSI) Secure Socket Layer (X509 Certi?cates),
`Kerberos, DCE, and Custom Systems for Secure Distributed Data
`Access; Jul, 19, 1999; 4 pages,
`BEA webLogic 55L; Server 45; 20 pages,
`Certi?cate to LDAP Mapping in Netscape Servers, Rev 1.2; Aug.
`28, 1997; Structured Arts Technical Notes.
`U.S. Appl. No. 10/367,541 Of?ce action dated Oct. 11, 2006, 1-15.
`US‘APPL NO, ()9/753332, ()f?ce action dated Oct, 19, 2006, 1.26,
`US. Appl. No. 09/695,499, Of?ce action, (Dec. 11, 2006), 1-16.
`
`* cited by examiner
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 2
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 1 0f 32
`
`US 7,266,555 B1
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 3
`
`
`
`U.S. Patent
`
`eS
`
`40.1
`
`7
`
`hS
`
`23f
`
`7SU
`
`5,66
`
`1B5
`
`29OS
`
`5N2:9".
`
`08:”.“9220Lo“.2..3:“.
`
`
`
`
`.25.:.2w3833”.at:383%at:
`
`
`
`Wof2.,92m$3
`
`835mmeBm
`
`0?
`
`
`
`
`
`LwawwEmcoEmucoo
`
`Petitioners Microsoft Corporation and HP Inc. - EX. 1007, p. 4
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 4
`
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 3 0f 32
`
`US 7,266,555 B1
`
`File Upload/Download
`Operations
`
`30o
`
`Load Balancing Fabric
`310
`
`V
`
`DOSM
`1
`
`Distributed Object Storage Managers
`
`V
`
`DOSM
`2
`
`320
`
`I I I
`
`V
`
`DOSM
`"n"
`
`Interconnect Fabric
`330
`
`V
`
`V
`
`Storage Node
`1
`
`Storage Node
`2
`
`340
`
`V
`
`Storage Node
`..n..
`
`Intelligent Storage Nodes
`
`Figure 3
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 5
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 4 0f 32
`
`US 7,266,555 B1
`
`No
`
`Receive
`Download Request
`(SRL)
`?
`
`Yes
`
`Switching Fabric Selects DOSM
`410
`
`V
`Parse SRL to Extract Certi?cate and
`Object Fingerprint
`415
`
`Error Message ls
`‘
`‘
`—_ sent toqggclplem
`
`r 420
`
`Does SRL
`Authenticate?
`
`440
`
`No
`
`Does DOSM
`Contain Location
`of object
`?
`
`Yes
`
`Storage
`Node
`Readable
`
`Figure 4
`
`;
`
`Broadcast Request To
`Storage Nodes to Locate
`Object
`450
`
`V
`
`N
`E h
`at: Storage ode
`Determines Whether It
`Stores The Object
`460
`
`DOSM Obtains Connection
`With Storage Node With
`Object
`435
`
`Ob'ect ls Transmitted From
`stolrage muster to Recipient
`495
`
`V
`End
`
`462
`
`Object Located
`'2
`
`DOSM Establishes Point to
`Point Communications With
`Each Storage Node
`464
`
`_
`Storage Node With Object
`Broadcasts object
`Identi?cation Information
`for all DOSMs
`470
`
`(K 456
`
`'
`oblectgocated
`‘
`
`V
`Perform Faiiover Operation
`to Obtain Object
`468
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 6
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 5 0f 32
`
`US 7,266,555 B1
`
`Decode SRL To Extract Client
`Identi?cation, Object Fingerprint
`And SRL Certi?cate
`500
`
`l
`
`Extract Secret For
`The Corresponding Client
`510
`
`Generate Calculated Certi?cate
`520
`
`Compare Calculated Certi?cate
`With SRL Certi?cate
`530
`
`Generate Error Message
`To Requester
`550
`
`SRL Authenticates
`560
`
`Figure 5
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 7
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 6 0f 32
`
`US 7,266,555 B1
`
`DOSM File Look-up Table
`610
`
`File Id
`
`IP Addr
`
`Disk Id
`
`3
`
`1
`
`6
`
`10.3.1001
`
`10.3.0981
`
`10.3.0501
`
`10.3.1001
`
`10.3.098.1
`
`10.3.0501
`
`Data Cache
`620
`
`Film Snippet
`
`Advertisement
`
`Film Preview
`
`State Table
`630
`
`Read - Write State of Storage Nodes
`
`Health of Storage Nodes
`
`Load of Storage Nodes
`- Storage Capacity
`- Number of 1/0 Operations
`Per Second
`
`a BMW
`El: :1:
`G c a:
`
`/ U“ \
`DOSM Server
`600
`
`Figure 6
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 8
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 7 of 32
`
`US 7,266,555 B1
`
`
`
`ProcessingCore 710
`
`700
`
`DiskId"n"
`
`DiskId3
`
`DiskId2
`
`3.2ho
`0v
`.1".9
`D
`
`Figure7
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 9
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 9
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 8 0f 32
`
`US 7,266,555 B1
`
`t
`
`Start
`
`l
`
`V
`VFS Performs Directory Operations for New
`Object File And Transmits Upload Request
`To Storage Cluster
`805
`
`7
`
`Switching Fabric Selects DOSM
`810
`
`l
`Parse Request to Extract Certi?cate, Client.
`Directory And Object Information
`820
`
`830 r
`oes Reques
`Authenticate?
`
`N0
`
`V
`DOSM Communicates Fingerprint, Folder
`Id, Client Information and Meta Data to VFS
`880
`
`‘
`v
`DOSM Verifies Upload To The Source
`895
`
`Send Error
`Message to
`Source
`s35
`
`V
`
`i
`
`DOSM Selects Destination Storage Node(s)
`To Store Object File
`840
`
`V
`DOSM Obtains Connection With
`Destination Storage Node(s)
`850
`
`V
`Object File is Transmitted to Destination
`Storage Nodets)
`860
`
`V
`Generate and Verify A Fingerprint for the
`object Fue
`870
`
`.
`
`Frgure 8
`
`ll
`End
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 10
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 9 0f 32
`
`US 7,266,555 B1
`
`Create A Temporary File With The Contents Of
`The Object At The Destination Node.
`900
`
`Compute an MD5 Hash On The Contents Of The
`Temporary File
`910
`
`i
`
`DOSM Determines Whether The MD5 Hash
`Fingerprint Currently Exists In The Storage
`System
`920
`
`K- 930
`Fingerprint
`Currently Exist
`?
`
`Yes
`
`No
`
`Convert Temporary File To
`Permanent File With MD5
`Fingerprint Identification
`960
`
`Delete Temporary F'le
`940
`
`Increment The Reference
`Count For The Existing
`Fingerprint
`950
`
`Figure 9
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 11
`
`
`
`U.S. Patent
`
`Sep.4,2007
`
`Sheet10 of32
`
`US 7,266,555 B1
`
`8255093232E
`
`mcozfimao
`
`
`
`
`
` o525m".m:_ocm_mm30..
`
`3935SE262
`
`
`
`2639i8:“.262N885aw“maqu82>
`
`
`
`N“Seam82>orEmEmmEm>u<3255SE262
`
`395.5EE262
`
`XmO._m
`
`>mouocm
`
`
`
`._c..mcomomamam280mama
`
`N208E3
`
`_.@28098
`
`..c._5500m5500N_>_mOD
`
`_‘_>_wOD
`
`
`
`E$sz
`
`Petitioners Microsoft Corporation and HP Inc. - EX. 1007, p. 12
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 12
`
`
`
`
`
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 11 0f 32
`
`US 7,266,555 B1
`
`@9095ELI
`
`
`
`98:me:26.qu
`
`
`
`bouomzfiEH:
`
`
`
`9333.5:930
`
`5395at:
`
`
`
`98:ch8:980
`
`
`
`
`
`2:gangs.E2095$5959
`
`
`
`
`
`__:...wmmcflzbouumhn.
`
`uflzezma
`
`85255
`
`
`
`:522925352:3
`
`
`
`m328.585250
`
`F22025
`
`
`
`8:3.285853an
`
`:93$
`
`Petitioners Microsoft Corporation and HP Inc. - EX. 1007, p. 13
`
`
`
`
`
`NEma—5.2ERRED859.35
`
`
`
`
`
`P63:22b203,...uanEmE
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 13
`
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 12 or 32
`
`US 7,266,555 B1
`
`Customer Table
`
`Customer Name Customer Reserved Fields
`
`Customer A
`
`[Customer stores data ...]
`
`1200
`
`Customer B
`
`[Customer stores data ...]
`
`Customer C
`
`[Customer stores data ...]
`
`Customer D
`
`[Customer stores data ...]
`
`Folder Table
`
`Customer ld
`
`Folder ld
`
`Folder Parent ld
`
`Metadata
`
`3
`3
`3
`
`3
`
`2
`100
`251
`
`166
`
`-
`
`2
`
`[Reserved]
`[Reserved]
`[Reserved]
`
`251
`
`[Reserved]
`
`1210
`
`File Table
`
`Customer Id File Handle Folder ld
`
`Folder Parent Id
`
`Metadata
`
`1220
`
`3
`
`3
`
`3
`3
`
`52.MD5
`
`55.MD5
`
`99.MD5
`67.MD5
`
`100
`
`100
`
`166
`166
`
`2
`
`2
`
`251
`251
`
`[Reserved]
`
`[Reserved]
`
`[Reserved]
`[Reserved]
`
`Figure 12
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 14
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 13 0f 32
`
`US 7,266,555 B1
`
`Receive
`Directory 0p
`Request
`7
`
`Yes
`
`Parse Request to Extract Certi?cate, Client
`Information, Operation Code and
`Arguments
`1310
`
`Send Error
`Message To
`Requester
`1 325
`
`1370
`
`Open Folder?
`
`Move Folder?
`
`Create Folder?
`
`Move File
`
`Access File And Folder
`Tables To Extract File
`ids And Sub-Folder Ids
`1345
`
`Revise Folder Table
`Entries To Re?ect New
`Location
`1355
`
`Add Em F r New
`Fold r In goldo r Tame
`8 13658
`
`Revise File Table
`Entries To Re?ect New
`Location
`1375
`
`Figure 13A
`
`V
`
`Return Arguments To Requester
`1390
`
`‘
`
`ll
`
`End
`
`it
`(To Figure 138)
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 15
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 14 0f 32
`
`US 7,266,555 B1
`
`
`
`
`
`52E2E5:$520".225352E0590NEW.£2005.620“.92mm.
`
`
`
`
`
`
`
`2,29:3Es“;
`
`m22:2".
`
`
`
`EmmacmmohmEmEamEE39”.
`
`mmmr
`
`E2622a:
`
`ofa.33.222
`
`2E8“.2%»
`
`Ecm
`
`$8
`
`E26225:
`
`.020”.E53222
`
`.mEouBumam...
`
`bEm
`
`32
`
`2an2:52E5“.Em.BE
`
`$2
`
`3cm2:.298
`
`2%»2:59“.
`
`E?
`
`
`
`520...9200
`
`.620...ES...>25.
`
`22m...
`
`:9
`
`Petitioners Microsoft Corporation and HP Inc. - EX. 1007, p. 16
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 16
`
`
`
`
`
`
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 15 0f 32
`
`US 7,266,555 B1
`
`Perform Validation Using Client Information
`and Certificate From The Request
`1405
`
`Send Error
`Message
`1415
`
`1410
`
`f
`
`Request
`Validated?
`
`Extract MD5 Handler From Database Entry
`1420
`
`l
`
`Delete File Identi?cation in File Table
`1450
`
`DDM Constructs A Delete SRL And Transmits
`The Delete SRL To The Storage Cluster
`1460
`
`Decrement Reference Count By One
`1440
`
`Storage Cluster Deletes File From Appropriate
`Storage Node
`1470
`
`1430
`
`5 Reference
`Count Greater
`Than One?
`
`Figure 14
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 17
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 16 6f 32
`
`US 7,266,555 B1
`
`2 65mm
`
`
`
`52.654 5.62
`
`o Fm?
`
`9w
`
`m0
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 18
`
`
`
`U.S. Patent
`
`Sep.4,2007
`
`Sheet17 of32
`
`US 7,266,555 B1
`
`
`
`
`
`23955.392w«3.3035235@6335.omesw.33085955
`
`
`
`atom...mEucmfimnag
`
`0:”
`
`
`
`25mmm:_u:m_mm_umog
`
`Em
`
`
`
`swim2r.52.5.8530E_m=:_>
`
`onom
`
`
`
`ommrowmw
`
`
`
`
`
`
`
`
`
`mgmozumm.2ch09.2wEmwacmm£3.33..2ch$905£3331
`
`
`
`
`
`
`
`umoEzaQumoEDcozflmno2069.532539303352330boogn.
`
`
`
`
`
`
`
`
`
`
`
`
`
`Til
`
`
`ownown
`
`
`
`
`
`
`
`25a“.«85.8.2525m“.32:83::
`
`.522a.
`
`
`
`canown
`
`$21.~62a.
`
`.23n:.62a.
`
`
`
`
`
`
`
`mmmém@92050386$905mmfism
`
`.:N252...252082$02282
`__:..NP_.c..
`
`
`
`
`
`own$82~3559:25own$qummsew39:25
`
`2$sz
`
`Petitioners Microsoft Corporation and HP Inc. - EX. 1007, p. 19
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 19
`
`
`
`
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 18 0f 32
`
`US 7,266,555 B1
`
`
`
`:25 E236
`
`8:
`
`
`
`hmamw 200
`
`o KF
`
`
`
`“@250 wmESw
`
`ESaEoQ
`
`
`0ND.
`
`
`
`62mm nm>> 596 22:00
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 20
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 19 of 32
`
`US 7,266,555 B1
`
`End-User Computer Generates HTTP Request
`To Content Origin Web Server
`1800
`
`1820
`
`Content Origin Server Returns to End-User
`Computer HTML With Embedded File URL
`1810
`
`End-User Computer Generates HTTP File
`Request To Content Delivery Network
`
`/ 1825
` File in CDN
`
`Cache?
`
` CDN Generates An HTTP File Request to
`
`Storage Center
`1830
`
`
` Storage Center Downloads File To CDN Cache
`
`1840
`
`CDN Delivers File To End-User Computer
`
`1850
`
`a Figure 18
`
`Petitioners Microsoft Corporation and HP Inc. - EX. 1007, p. 21
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 21
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 20 of 32
`
`US 7,266,555 B1
`
`
`
`End-User
`Computer
`1900
`
`
`
`
`
`
`Content Web Server
`1925
`
`Client Site
`1910
`
`Storage Port
`
`
`
`
`
`Storage Center
`1950
`
`Figure 19
`
`Petitioners Microsoft Corporation and HP Inc. - EX. 1007, p. 22
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 22
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 21 of 32
`
`US 7,266,555 B1
`
`Client Receives URL File Request From End—User
`2010
`
`
`
`
`
`Client Generates Local File System Request
`2020
`
`
`
` Retrieve Object File
`Object File
`
`
`Local?
`
`
`
`From Data Cache
`2040
`
`
`
`
`
`Request Object File From Storage Center(s)
`2050
`
`
`
`Receive Object File From Storage Center(s)
`2060
`
`Return Object File In Response To Local File System
`Request
`2070
`
`Deliver Object File To End-User In Response To URL
`File Request
`2080
`
`
`
`Figure 20
`
`Petitioners Microsoft Corporation and HP Inc. - EX. 1007, p. 23
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 23
`
`
`
`U.S. Patent
`
`eS
`
`0.1
`
`4.,
`
`7w
`
`S
`
`a
`
`0
`
`2
`
`6,
`
`1B5
`
`$EN2:3
`
`SAiUowrmmcozflmaoof.=g
`
`.250$805
`
`2EN23qu
`
`62m0hH
`
`8aK
`
`
`
`
`
`28:80235>55:Eoum>w388w-
`
`m$3mE<5296$20658-
`
`
`
`mcozmaaoE2095
`
`onE5:803905
`
`
`
`30:96.02025
`
`22.530of.
`
`tonmum—22%A\
`
`
`
`
`
` asrm9‘E.6menw>>EwEoo
`
`%85
`79x88
`
`
`
`82mmnm>>Emucoo
`
`Petitioners Microsoft Corporation and HP Inc. - EX. 1007, p. 24
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 24
`
`
`
`
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 23 of 32
`
`US 7,266,555 B1
`
`
`
`__c_.02,5x20
`
`.025fig
`
`223E
`
`éoEoz
`
`900mEmmwooi
`
`0Rm
`
`ton.$9.06
`,
`
`
`
`ooNN
`
`tonmmmhew
`
`EBwSmo
`
`
`
`Amvoumtousx8232
`
`ONNN
`
`
`
`oomtEEx5332
`
`83.25{osz
`
`momtEE
`
`z28
`
`N98
`
`F28
`
`Petitioners Microsoft Corporation and HP Inc. - EX. 1007, p. 25
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 25
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 24 of 32
`
`US 7,266,555 B1
`
`2300
`
`Client Local
`
`2310
`
`File System
`
`Directory Cache
`2370
`
`Storage System Access
`Processes
`2330
`
`XML Requests
`
`Directory
`Information
`
`To
`VFS
`
`
`
`Local File System
`Operation
`
`Operating System Kernel
`2360
`
`
`
` File System
`2320
`Translator
` Local File System
`2340
`Interception
`
`Storage System Kernel
`
`Processes
`2350
`
`
`Storage System
`
`Requests
`
`Figure 23
`
`Petitioners Microsoft Corporation and HP Inc. - EX. 1007, p. 26
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 26
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 25 of 32
`
`US 7,266,555 B1
`
`Client Issues Local File Open Request
`2400
`
`
`Import Local File Request
`2410
`
`2420
`
`Dispatch File System Request to File System Translator
`
`2435
`
`No
`Data
`
`Required
`
`
`
`
`
`
`
`
`Additional Directory
`Information Required?
`
`Return Directory
`Information
`
`Generate SRL Request To Download
`2450
`File From Storage Cluster
`
`Generate Request to VFS for File
`and Directory Information
`2470
`
`
`
`Is File in Data
`
`
`Cache?
`Receive and Cache Object File
`2460
`
`Receive Directory Information
`And Store In Directory Cache
`2480
`
`Transfer Object From Storage Port
`to Client Requester
`2490
`
`Figure 24
`
`Petitioners Microsoft Corporation and HP Inc. - EX. 1007, p. 27
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 27
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 26 of 32
`
`US 7,266,555 B1
`
`2600
`
`
`
`
`URL
`Request
`
`
`
`Computer
`2610
`
`HTML With
`
`
`Embedded SRL
`
`
`Client Site 2620
`
`Content Web Server
`2630
`
`Storage Port
`2640
`
`Served
`
`
`
`SRL
`Request
`
`Object File
`
`2650
`
`Storage Center
`
`Figure 25
`
`Petitioners Microsoft Corporation and HP Inc. - EX. 1007, p. 28
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 28
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 27 of 32
`
`US 7,266,555 B1
`
`Content Web Server Generates Local File
`
`
`System Request for SRL(s) for Fi|e(s)
`2700
`
`
`Storage Port Generates SRL(s) for File(s)
`2710
`
`Time Out Parameter ls Added to SRL
`2720
`
`SRL ls Embedded In HTML Web Page
`2730
`
`End-User Issues Web Page Request
`
`
`2740
`
`Content Web Server Downloads HTML With
`Embedded SRL
`2745
`
`
`
`
`End-User Generates HTTP Request to Storage
`Center With SRL
`2750
`
`
`
`
`
`?
`
`No
`SRL
`
`
`Authenticate
`
`
`Storage Center Downloads
`
`Object File To End-User
`
`2770
`
` Figure 26
`
`Petitioners Microsoft Corporation and HP Inc. - EX. 1007, p. 29
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 29
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 28 0f 32
`
`US 7,266,555 B1
`
`2800
`
`
`2810 HTML With
`
`Computer
`
`
`
`
`Embedded SRL
`
`
`Client Site 2820
`
`Content Web Server
`2830
`
`
`
`
`File
`
`
`Location
`Request
`
`Private File Manager
`2840
`
`
`
`Object File
`Served
`
`
`
`Storage Center
`2850
`
`Figure 27
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 30
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 30
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 29 of 32
`
`US 7,266,555 B1
`
`End-User Issues URL Request
`2900
`
`Content Web Server Generates A File Location
`Request to File Manager
`2910
`
`File Manager Retrieves File SRL for Content
`Web Server
`2920
`
`Content Web Server Transmits To End—User
`HTML With Embedded SRL
`2930
`
`
`
`
`End-User Generates HTTP Request to Storage
`Center With SRL
`2940
`
`F 2945
`
`SRL
`No
`
`
`Authenticate
`
`?
`
`Storage Center Generates M05 Hash on "SRL"
`and Identifies File
`2947
`
`Storage Center Downloads Object File To End-
`User
`2950
`
`a Figure 28
`
`Petitioners Microsoft Corporation and HP Inc. - EX. 1007, p. 31
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 31
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 30 of 32
`
`US 7,266,555 B1
`
`mamEm=o
`
`omomk{9,3sz
`
`
`
`5.me
`
`9:255.
`
`08m
`
`63‘n:
`
`«:0in
`
`83.25
`
`9:2
`
`ton.£685
`
`oEm
`
`{oéwz
`
`03:25
`
`€25.02
`
`gate:—
`
`53.5“.
`
`m:_.o=:o_>_
`
`{0252
`
`83.25
`
`{ozmz
`
`momtmE
`
`.28:
`
`9:02:22
`
`omom
`
`96me
`
`ton.$205
`
`owom
`
`£252
`
`08:25
`
`2£sz
`
`Petitioners Microsoft Corporation and HP Inc. - EX. 1007, p. 32
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 32
`
`
`
`
`
`
`
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 31 0f 32
`
`US 7,266,555 B1
`
`
`Storage Port
`
`Failover?
`
`
`3120
`
`Read File
`
`Operation
`Requested
`?
`
`
`
`
`
`Execute Open File Operation
`3140
`
`
`
`
`
`Open File
`Operation
`
`Requested?
`
`
`
`
`
`
`
`Generate XML Request To VFS for File
`Identification
`3150
`
`VFS Returns File Identification
`3160
`
`Storage Port Updates Directory Cache
`3170
`
`3190
`
`Generate SRL Request To Storage Cluster
`3180
`
`Receive File and Update Cache
`
`Figure 30
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 33
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 33
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 32 of 32
`
`US 7,266,555 B1
`
`3210
`Storage Node
`
`Fails?
`
`
`DOSMs Updates State Table For Storage
`Node Failover
`
`3220
`
`3225
`
`/
`File
`
`Requested
`
`
`
`DOSM Issues Multi-cast Protocol Request
`
`3230
`To Storage Nodes
`
` Each Storage Node Determines Whether It
`Contains The Requested File
`3240
`
`
`
`
`
`DOSM Selects leferent
`Object File
`
`
`
`Located
`Storage Center
`
`
`3247
`
`
`
`Storage Node With File Broadcasts File
`Identification Information
`3250
`
`3260
`
`DOSM Snoops, Through Multi-Cast
`Protocol, To Update File Information
`
`Petitioners Microsoft Corporation and HP Inc. - EX. 1007, p. 34
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 34
`
`
`
`US 7,266,555 B1
`
`1
`METHODS AND APPARATUS FOR
`ACCESSING REMOTE STORAGE
`THROUGH USE OF A LOCAL DEVICE
`
`CROSS-REFERENCES TO RELATED
`APPLICATIONS
`
`This application claims the benefit of US. patent appli-
`cation Ser. No. 09/695,499, filed Oct. 23, 2000, entitled “A
`Network Storage System.”
`The application also claims the benefit of US. Provisional
`Application No. 60/186,693, filed Mar. 3, 2000, entitled
`“Method and Apparatus for Implementing A Network-Based
`Storage Service”, and US. Provisional Application No.
`60/186,774, filed Mar. 3, 2000, entitled “Method and Appa-
`ratus for Establishing Control and Data Lines To A Storage
`Facility, And API For Supporting Such Lines.”
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention:
`
`invention is directed toward the field of
`The present
`storage, and more particularly toward accessing remote
`storage through use of a local device.
`2. Art Background:
`With the rapid digitization of music, film and photo-
`graphs, customer demand is driving the Internet to become
`the most preferred transport mechanism for all forms of
`digital media. Using the Internet, users have instantaneous
`worldwide access to their favorite movies, songs, or per-
`sonal memorabilia. As the producers and owners of media
`content increasingly use the Internet as a primary method for
`worldwide distribution, the aggregate amount of rich media
`content available over the Internet
`is increasing at an
`extremely rapid rate.
`Not only is the number of rich media objects available
`over the Internet growing exponentially, but the size of the
`media, generally referred to herein as objects, is also dra-
`matically increasing. A median Web object is 5 kilobytes
`(KB) in size, while the size of a rich media object may be
`100 to 1 million times larger. For example, high-resolution
`digital photographs average 500 KB per picture. Digital
`music runs 3 to 5 megabytes (“MB”) per song, and digital
`movies may reach up to 4 gigabytes (“GB”) in size.
`As the number of personal computers, digital camcorders,
`digital cameras, and personal digital audio players grow,
`demand for Internet bandwidth to store, share and retrieve
`media files across the Internet also will grow. As the use of
`high-bandwidth digital subscriber
`lines (“DSL”), cable
`modems, and digital broadcast satellite networks gain in
`popularity, which grows the infrastructure of the Internet
`backbone, the demand for using the Internet as a primary
`delivery channel for rich media objects also gains in popu-
`larity. This development causes a virtuous cycle, where the
`installation of broadband networks drives the use of rich
`media devices, which in turn, creates demand for further
`improvements in network bandwidth, and so on.
`The distribution of rich media objects across the Internet
`creates the need for increased storage capacity to store these
`rich media objects. As the number of personal media devices
`grows, and the network bandwidth expands, the amount of
`storage media required to store the various MP3 files,
`photographs, films, and video clips will also grow. Also, as
`more storage becomes readily available, more people will
`use the Internet to catalog, store, and access their rich media
`objects (e.g., digital photographs of family members).
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`To date, only traditional storage solutions from estab-
`lished enterprise vendors have been available to a Web site
`developer implementing rich media repositories. One chal-
`lenge with adopting today’s existing storage technology for
`use with the Internet is meeting current and future scalability
`requirements. Today, large scale storage systems only scale
`to a few dozen terabytes. This amount of storage space is
`inadequate for storing substantial amounts of rich media
`objects. For example, if just 10 percent of America on line
`(“AOL”) users place two 15 minute videos on a personal
`home page,
`then one petabyte (i.e., 1000 terabytes) of
`storage would be required. Today’s enterprise storage sys-
`tem architectures cannot support this level of storage capac-
`ity.
`in addition to providing mass
`In the Internet world,
`storage, it is also critically important to provide universal
`access to that storage across the wide area network. The
`content provider, regardless of the location of their content
`servers, cache servers, or stream servers, would ideally like
`to provide ubiquitous access to an entire store of rich media
`objects. Current technology, including storage area networks
`and network attached storage technologies, do not provide
`direct access to the wide area network. Only servers located
`within the same metropolitan area can directly access these
`types of storage systems.
`Since Internet users are measured in the tens of thousands
`or even millions of users,
`instead of hundreds of users,
`another challenge in mass storage is the ability to scale
`delivery of media as the demand increases. A true Internet
`based storage system must be able to handle peak loads of
`millions of simultaneous requests from all around the world.
`Traditional storage architectures are designed for supporting
`a few hundred simultaneous requests from the fastest pos-
`sible response time to match the speed of the server CPU.
`For the Internet, storage systems must be able to manage
`literally millions of simultaneous downloads at the speed of
`the wide area network. Thus, these traditional storage archi-
`tectures are not “impedance matched” with the wide area
`network because the storage devices handle far too few
`simultaneous
`transactions
`that
`far exceed the latency
`requirements of the wide area network. In addition, these
`traditional storage architectures are typically implemented
`with expensive disks and expensive connection technolo-
`gies.
`Another issue regarding storage of rich media objects is
`the time to market. The time to market is often times a
`
`crucial requirement for new rich media Web sites. Growth
`rates are measured in terabytes per month. Quickly bringing
`new capacity online becomes a strategic advantage in fast-
`moving markets. Typically, with traditional storage solu-
`tions, it takes a customer two to six months to integrate a
`fully operational multi-terabytes storage unit with the con-
`tent providers site. This start-up time is to slow to meet
`rapidly increasing business demands. Pre-building large
`amounts of excess capacity in anticipation of this demand is
`one tactic to deal with unpredictable demand spikes, but this
`approach is prohibitively expensive.
`Traditional storage architectures have been optimized for
`database and file server applications. The Internet introduces
`a whole new set of demands on storage devices, including
`scalability, global access, user accounts, and rapid deploy-
`ment. With the explosive growth in rich media served over
`the Internet over the next several years, this is coming to a
`head. The coming title wave of rich content will surpass the
`capabilities of even the most robust enterprise storage archi-
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 35
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 35
`
`
`
`US 7,266,555 B1
`
`3
`tectures. Accordingly, there is a demand to develop new
`paradigms in new ways of designing Internet ready rich
`media storage systems.
`
`SUMMARY OF THE INVENTION
`
`A storage port interfaces a client computer, such as a web
`or application server,
`to a network storage system. The
`network storage system stores files at one or more storage
`centers, remote from the client site. To gain access to content
`stored at the remote storage center,
`the client computer
`mounts the storage port as a storage device for the client
`computer. The client computer issues local
`file system
`requests to conduct network storage system operations. In
`response,
`the storage port
`translates local
`file system
`requests to network storage system requests. In one embodi-
`ment,
`the local file system and network storage system
`requests include file request and directory operations. The
`storage port processes the network storage system requests
`at the storage port, and accesses, as necessary, the remote
`storage center.
`In one embodiment, the storage port further includes a
`data cache and a directory cache. The data cache stores at
`least a subset of files of the network storage system, and the
`directory cache stores at least a subset of directory infor-
`mation for the network storage system. In operation, the
`storage port receives requests for files of the network storage
`system. In response, the network storage system determines
`whether the file resides in the storage port data cache, and
`delivers the file if the file is cached. If the file is not cached,
`then the storage port accesses the remote storage center to
`obtain the file. The storage port also receives requests for
`network storage system directory operations, and determines
`whether the directory information resides in the storage port
`directory cache. If the directory information is cached, then
`the storage port delivers it to the client computer. If the
`directory information is not cached, the storage port obtains
`the directory information from a remote virtual file system.
`The storage port has application for use in delivering
`content for a client web site. The network storage system
`stores content, including rich media files, for the client’s
`web site. For this embodiment, an end-user computer gen-
`erates requests to the client’s web server for files available
`on the client’s web site. In response to the end-user requests,
`the client web server obtains the files through the storage
`port.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram illustrating one embodiment for
`the storage system of the present invention.
`FIG. 2 illustrates one embodiment for use of the network
`
`storage system as a