`
`(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
`
`Sep. 4, 2007
`
`Sheet 2 of 32
`
`US 7,266,555 B1
`
`
`
`so1asaBesojs
`
`OeL
`
`OSL
`
`
`
`a101$B1eq Janes
`
`
`
`ulBbucCjuaju04
`
`sjsonbaydilH
`
`
`
`salyalqc4104
`
`sjsonboydilH
`
`
`
`SOl!4TWWLH404
`
`00l
`
`Zzainbi4
`
`Petitioners Microsoft Corporation and HPInc.- 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
`
`DiskId2
`
`710
`
`DiskId"n"
`
`DiskId3
`
`o2- oO
`av
`xs2
`Oo
`
`Figure7
`
`Oow
`nN
`
`Petitioners Microsoft Corporation and HPInc.- Ex. 1007, p. 9
`
`v6
`oO
`
`D£w
`
`n g2
`
`°a
`
`700
`
`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
`
`Sheet 10 of 32
`
`US 7,266,555 B1
`
`
`
`
`
`
`
`ZJaddiuscapi,O|JuawasipaapyMAIAQIqWil|MAN
`
`
`
`MAIAVWIIMONZsoq}oudgJaddiuso=pi~A
`
`
`
`peojumog/peoidyalld
`
`suojeiado
`
`
`
`
`
`ouge4Bulouejegpeo
`
`Ole
`
`
`
`MIABIqWIIMON
`
`MAIAQIWilMON
`
`xgO1E
`
`AS0}0Ud
`
`
`
`
`
`
`
`ul,BYDEDEyed€ayoeyeyeg
`
`
`
`Zayoegeyeq
`
`
`
`|ayoesDeyeq
`
`v4,NSO€WSOd¢WSOd
`
`LWSoQa
`
`OLainbig
`
`Petitioners Microsoft Corporation and HPInc.- Ex. 1007, p. 12
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 12
`
`
`
`
`
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 11 of 32
`
`US 7,266,555 B1
`
`uojeiadoO
`
`
`
`s}sonbayuoneiedo
`
`
`
`MoyaidditH
`
`MoyoaldditH
`
`
`
`
`
`
`
`OL}si@BeveWAsojangpaynquisiq
`
`paynquysig sjsanbay
`
`
`
`
`
`aU,saGeueypALopaig
`
`
`
`
`
`Zsabeue-Aoyoaigpanquysiq
`
`painquysiq
`
`
`
`wu,MoyapayNquysiq
`
`
`
`zMopaigpainquisig
`
`|Atoyaug
`
`
`
`
`
`OZL}SaNOpaNGpainquysiq
`
`beainbiy
`
`
`
`sjsonbayuoijeisdo
`
`AsoyaulddH
`
`
`
`
`
`|JaBeueyAopaiigpaynquisig
`
`Petitioners Microsoft Corporation and HPInc. - Ex. 1007, p. 13
`
`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 of 32
`
`US 7,266,555 B1
`
`wadajepdny
`
`
`
`SyJUlEJepejayy
`
`[lJ104a1geL
`
`Ayjug
`
`PGE
`
`agebanbi4
`
`céela
`
`
`
`éalldQepdyiJapjo4eyepdn
`
`
`
`
`
`é8ll4ayeary2Al!4239199Lsapio422189
`
`
`
`(WELaun6i4wor)
`
`Aug
`
`gel
`
`P8El
`
`gaze
`
`
`
`daysanbayofsjyuswunBiywinjey
`
`96EL
`
`USDayepdy)
`
`Japio4103ajqey
`
`SqeLa4ul
`
`Japjoguyeyepejoyy
`alld104Augppy
`
`Ajuyallyaya79q
`BIELSjWoy
`JapjolwosAjug
`
`
`
`4eplore9/9Q
`
`aqeL
`
`pel
`
`Petitioners Microsoft Corporation and HPInc.- 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
`
`Sheet 17 of 32
`
`US 7,266,555 B1
`
`OzSt
`
`peojumog/peojd7)
`
`
`
`s\senbayJauagabei0)$
`
`
`
`uojesedoAopanig
`
`sjsonbay
`
`
`
`OLS}
`
`
`
`
`
`sjsanbays91Ue9abe10)Ssjsenbay
`
`
`
`
`
`peojumog/peojde)ualjeJedgAuo}2a11q
`
`
`
`
`
`ouqe4Bulouejegpeo
`
`
`
`
`
`ouge.jBulsuejegpeoq
`
`ole
`
`OLe
`
`
`
`wayskgali[ENUIA
`
`0s
`
`Wa}SKSaI4[ENLIA
`
`as
`
`
`
`
`
`
`
`suabeueyya6e10)5Joalqopainquysiq
`
`PRYdl
`
`
`
`
`
`ongeypeuucse}U
`
`oce
`
`Appdi
`
`«LIPPYdi
`
`
`
`abeoisabeoys
`
`
`
`J,@3PONot@PON
`
`tSpon
`
`aheoys
`
`
`
`
`
`OESePONaBe0)gJUAby|]U}
`
`
`
`Ooze
`
`
`
`
`
`abelojsabesojs
`
`wl,qapon@poN
`
`Ooze
`
`SugeyyOaUUCDAIU;
`
`Oce
`
`“1ppVdl
`
`“PPVdi
`
`
`
`
`
`OreSePONabes0}gyuasy]21U)
`
`Petitioners Microsoft Corporation and HPInc.- Ex. 1007, p. 19
`
`
`
`9,aunbig
`
`
`
`
`
`
`
`suaBeuewaBesojsyoalqgpaynquysiq
`
`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 HTTPFile
`Request To Content Delivery Network
`
`i 1825
`Cache?
`
`File In CDN
`
`
` Storage Center Downloads File To CDN Cache
`
`
`
`CDN Generates An HTTP File Requestto
`Storage Center
`
`1830
`
`1840
`
`CDN Delivers File To End-User Computer
`
`1850
`
`Cm)
`
`Figure 18
`
`Petitioners Microsoft Corporation and HPInc.- 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
`
`Client Site
`1910
`
`Content Web Server
`
`
`
`
`
`
`Storage Port
`
`
`
`Storage Center
`1950
`
`Figure 19
`
`Petitioners Microsoft Corporation and HPInc.- 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 HPInc. - Ex. 1007, p. 23
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 23
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 22 of 32
`
`US 7,266,555 B1
`
`
`
`J9]U99)9621035
`
`suoyeiedgKoad
`
`
`
`suoneledyayiaHode6e01s
`
`osiz/
`
`epzainbiy
`
`OOLe
`
`
`
`
`
`OLLeJOABSGenjus}u0D
`
`
`
`J9]U94a6eu0}S
`
`o9Le
`
`
`
`suoneiedgA0paiq
`
`
`
`suojyessdoally
`
`booco30)
`
`
`
`
`
`£42SidWa}sksgs6e10}¢|]25-
`
`gizainbig
`
`0812}oviz
`
`
`
`JBAIaSGavJusUOD
`
`
`
`scheAseiqiywaysksaBbesojs-
`
`
`
`
`
`(sled
`
`Petitioners Microsoft Corporation and HPInc.- Ex. 1007, p. 24
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 24
`
`
`
`
`
`
`
`
`
`
`
`
`nU,,PAUASIAL8Aug¥sIG
`
`Zeainbi4
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 23 of 32
`
`US 7,266,555 B1
`
`WOMJON
`
`
`
`2109Buissasolg
`
`OL?
`
`yoge6e10j}$
`©
`
`00zz
`
`Hode6es0jS
`
`aoysejeg
`
`O”cz
`
`
`
`(s)soepequ]WOMaN
`
`0222
`
`
`
`SOBPS}U]JIOMJON
`
`SOe}HO]U]MOMJON
`
`SORNaIU]
`
`NpIeED
`
`Zzpeg
`
`Lpueg
`
`Petitioners Microsoft Corporation and HPInc. - 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
`
`2310
`
`Client Local
`File System
`
`Local File System
`Operation
`
`Operating System Kernel
`2360
`
`Information
`
`Directory Cache
`2370
`
`XML Requests
`
`Storage System Access
`Processes
`2330
`
`To
`VFS
`
`Directory
`
`
`
`2320
` File System
`Translator
` Local File System
`2340
`
`Interception
`
`
`Storage System Kernel
`Processes
`2350
`
`
`Storage System
`Requests
`
`Figure 23
`
`Petitioners Microsoft Corporation and HPInc.- 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
`
`Dispatch File System Requestto File System Translator
`2420
`
`2435
`
`No
`Data
`
`
`Required
`
`
` Additional Directory
`
`
`Information Required?
`2450
`
`
`Return Directory
`Information
`2437
`
`
`
`Is File in Data
`Cache?
`
`Generate SRL Request To Download
`File From Storage Cluster
`
`Generate Request to VFS for File
`and Directory Information
`2470
`
`
`
`Receive and Cache ObjectFile
`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 HPInc.- 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 HPInc.- 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
`
`
`
`2700
`
`Content Web Server Generates Local File
`System Request for SRL(s) for File(s)
`
`
`Storage Port Generates SRL(s)for File(s)
`2710
`
`Time Out ParameterIs Added to SRL
`2720
`
`SRL Is Embedded In HTML Web Page
`2730
`
`2740
`
`End-User Issues Web Page Request
`
`Content Web Server Downloads HTML With
`Embedded SRL
`2745
`
`
`
`
`End-User Generates HTTP Requestto Storage
`Center With SRL
`2750
`
`
`
`
`
`?
`
`No
`SRL
`
`
`Authenticate
`
`
`
`Storage Center Downloads
`Object File To End-User
`
`2770
`
` Figure 26
`
`Petitioners Microsoft Corporation and HPInc.- Ex. 1007, p. 29
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 29
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 28 of 32
`
`US 7,266,555 B1
`
`2800
`
` Ss)
`
`
`=) Bae)
`ule
`
`End-User
`Computer
`2810
`
`
`
`
`
`URL
`
`Request
`HTML With
`
`
`Embedded SRL
`
`
`Client Site 2820
`
`Content Web Server
`2830
`
`File
`
`Location
`Request
`
`Private File Manager
`2840
`
`SRL
`
`
`Object File
`Served
`Request
`
`
`
`
`
`
`Storage Center
`2850
`
`Figure 27
`
`Petitioners Microsoft Corporation and HPInc.- 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
`Requestto 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
` C 2945
`
`No
`
`
` SRL
`
`Authenticate
`?
`
`Storage Center Generates MD5 Hash on “SRL”
`and Identifies File
`2947
`
`Storage Center Downloads Object File To End-
`User
`2950
`
`Co)
`
`Figure 28
`
`Petitioners Microsoft Corporation and HPInc.- 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
`
`JIOMJON
`
`090¢_/
`
`
`
`SYSWSIDsoepeyu|
`
`OMION
`
`WNEeH
`
`Buyoyuoyy
`
`020€
`
`APPYdl
`
`WOMEN
`
`SOLO}
`
`Hogabeiojs
`
`OLO0€
`
`sAlIpy
`
`HOMON
`
`aoeyaju]
`
`OMEN
`
`soRpayuy
`
`JOAOE
`
`Buyoyuoy
`
`LOMON
`
`SOepayuy
`
`yyeay
`
`BuuoUoyy
`
`o80¢c
`
`OAISSEd
`
`HOYabe10}S
`
`0z0¢e
`
`OMION
`
`enepayu;
`
`
`
`A6zaunBi4
`
`Petitioners Microsoft Corporation and HPInc.- Ex. 1007, p. 32
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1007, p. 32
`
`
`
`
`
`
`
`
`
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 31 of 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 VFSfor 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 HPInc. - 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
`
`3220
`
`DOSMs Updates State Table For Storage
`Node Failover
`
`3225
`
`NO
`
`f
` File
`
`Requested
`
`?
`
`Yes
`
`3230
`
`
`DOSMissues Multi-cast Protocol Request
`To Storage Nodes
`
` Each Storage Node Determines Whether tt
`Contains The RequestedFile
`3240
`
`
`
`
`
`
`
`
`DOSMSelects Different
`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 HPInc.- 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 U.S. patent appli-
`cation Ser. No. 09/695,499, filed Oct. 23, 2000, entitled “A
`Network Storage System.”
`The application also claimsthe benefit of U.S. Provisional
`Application No. 60/186,693, filed Mar. 3, 2000, entitled
`“Method and Apparatus for Implementing A Network-Based
`Storage Service”, and U.S. 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 demandis 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 numberof personal computers, digital camcorders,
`digital cameras, and personal digital audio players grow,
`demand for Internet bandwidth to store, share and retrieve
`mediafiles 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 numberof 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 becomesreadily available, more people will
`use the Internet to catalog, store, and access their rich media
`objects (e.g., digital photographs of family members).
`
`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 Website
`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 (1.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 downloadsat 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 Websites. Growth
`rates are measured in terabytes per month. Quickly bringing
`new capacity online becomesa 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 demandis
`one tactic to deal with unpredictable demandspikes, butthis
`approach is prohibitively expensive.
`Traditional storage architectures have been optimized for
`database andfile 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 comingtitle wave of rich content will surpass the
`capabilities of even the most robust enterprise storage archi-
`
`Petitioners Microsoft Corporation and HPInc. - 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 subsetof 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 thefile 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
`whetherthe 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 virtualfile 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,