11111111111111111111111111111111 111111111111111111111111111111111111111111
`US008447762 8 2
`
`(12) United States Patent
`Brendel
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8,447,762 B2
`May 21 , 2013
`
`(54)
`
`STORING LOSSY IlAS IJ ES O F FIJ_E NAMES
`ANI) PARENT IIA NDU:S RATlU :R T HAN
`F ULL NAMES USL"G A C OMPAC T TABLE
`FOR NETWOR K-ArrAC B EJ)-STORAC .. :
`(NAS)
`
`(75)
`
`Inventor: Juc rgc II IJrcndc\, Allck]<lnd (NZ)
`
`(73)
`
`Assignee: SlIllwork Data MGM°': L.L.c.,
`Wilmington, DE (US)
`
`( . )
`
`Notice:
`
`SubjCC1IO any discl~imer, the term oflms
`palenl is extended or adjllsloo under 35
`U.s.c. IS4(b) by 1221 d1YS.
`
`(21)
`
`App!. No.: Il f83 8,628
`
`(22) Filed:
`
`Aug. 14, 2007
`
`5.5[1.19O A
`5,542.087 A
`5,960.434 A
`6.289.375 131
`6.308.320 13[
`6,3 [4.460 B[
`6.330.709 B[
`6.356.915 BI·
`6.393.544 BI
`6.484.250 H[
`6.606.690 132
`6.658.526 B2
`
`4/ [996 Sharma ct al.
`7/ [996 Neimal el aI
`9/ [999 Schimmel
`9/200 I Knight ct al
`1012001 Burch
`111200 I Knighl ct al
`121200 1 Johnson ct aJ
`)12002 Chrchetkine et al.
`512002 Bryg el al
`1112002 Mei el al.
`312003 Padovano
`1212003 Nguyen ct al
`(Continued)
`
`OTHER PUBLICATIONS
`
`707182)
`
`Microsoft Press Computer Dictionary. third edition. pp. 395. 423.
`Copyright 1997.·
`
`(Continued)
`
`(65)
`
`P rio r Publicat ion n a tll
`us 2007f0277227 Al
`Nov. 29, 2007
`
`{'rimary Examiller - Wilso n Lec
`(74) Alforney, Agent, or Firm - Schwabe, Willimmon &
`Wyan , P.e.
`
`Rl'la tcd U.S. Application n ata
`
`(57)
`
`AnSTRACT
`
`(62) Division of application No. 101708,457, filed on Mar.
`4, 2004, nuw Pal. No. 7,272,654.
`
`(51)
`
`(2006.01)
`
`Illt. C! .
`G06F 17130
`(52) U.S. CI.
`USPC
`.......................................... 7071736; 7071770
`(58) Field of C lass ificat ion Search
`USI'C
`707/ 1- 10, 200--203, 713- 718, 736-738,
`707i754- 770, 78 1- 788; 7091200- 203, 214,
`709/229
`Sec application file for complete iiCacch history.
`
`(56)
`
`Rl'fi'"n'nc('s Cit('d
`
`U.S. PATENT DOCUMENTS
`6/ 1992 Nemes
`5,121.495 A
`21 1994 Nemes
`5,287.499 A
`
`Multiple Network Attached SIOr:Jge (NAS) appliances arc
`pooled logether by a virt ual NAS lr:Jnslalor, forming one
`common name space visible 10 clienlS. Clienls scnd messages
`10 Ihe virtual NAS trnnslator wilh a filc namc and a virtual
`handle of lhe parenl dif(."clory lhal are concaienaied 10 a full
`filc-path namcand compressed by a cryptographic hash flUlC'
`lion to gcncrntc a hashed·namc key. The hashcd-namc key is
`malched to a sloragc key in a lablc. Thc full file. palh name is
`nOI slored, reducing Ihe lable size. A uniq ue enlry number is
`relurned 10 Ihe clienl as Ihe virtual file handle lhal is also
`Slored in anOlher lable wilh one or more native file handk'$,
`allowing virtual handles 10 be Irnnslaled 10 native handk'S Ihal
`Ihe N AS :rpp liilnCC scrvers use to rei riwe files. File movemeni
`among NAS scrvcrs alters nativc filc handles but not virtual
`handlcs, hiding NAS dctails from clicnts.
`
`II C la ims, 8 I)rawing Sheets
`
`. ~
`FUN.\IIf. I PATH
`
`'.,
`
`.-,..-
`\ CR?TOII'ASHA.. "
`
`•
`
`•
`
`~K£I ""
`
`'0 ~,
`
`Page 1 of 19
`
`Sl<fJ(l'
`
`_~Kr't' .. ?
`
`51
`
`NETWORK-1 EXHIBIT 2002
`Google Inc. v. Network-1 Technologies, Inc.
`I PR20 15-00345
`
`..
`
`.~. _E)..IIOJ,I(~!y
`
`•
`
`OM.
`
`NASliIXORA. !oI
`
`!.OO'Jl)OIo;EY
`
`~. I>l.J - .'
`.~ - .,
`K ' ~ ..
`...
`." -.-
`I ~ IOJ(>::ITN
`10 -,
`K -." - ,
`~ ~~I
`, .......
`t.I.J> <;jY"
`"''''
`
`

`
`US 8,447,762 82
`Page 2
`
`707/ to
`726127
`
`U.S. PATENT DOCUMENTS
`6,937.612 B l
`~2005 Mauger cl a1
`112006 Luke c[ al.
`6.985.956 B2
`7.428540 Bl '
`9/2008 COllIes cl al.
`7,8 [4.554 Bl' 10/10 10 Ragner
`8.04l.761 Bl
`10120 11 Banga cl nl
`200110037323 Al
`11/ 2001 M""l1on C! al.
`200110037406 Al
`11/ 2001 Philbrick cl al.
`1112002 Fran k
`200210178341 Al
`2003/0028587 Al
`li2003 Driscoll d a1
`200310031176 Al +
`212003 Sim
`.................. 3701392
`2003/0039362 Al
`212003 Califanod al.
`312003 Grnhrun ct al
`200310043805 Al
`312003 Satyanarayanan ct al.
`200310046260 Al
`2003/0046369 A 1
`3/ 2003 Sim et al
`312003 Mani-Mcilav cl al.
`200310050974 Al
`............... 7071200
`200310110188 AI· 612003 Howard Cl al.
`2003/0140051 Al
`7/2003 Fujiwara Cl al.
`2003/0158839 Al
`~2003 Faybishcnko L'I al.
`2003/0187885 Al
`1012003 Miyazaki cl a1
`1012003 MuhlcSlcin cl al.
`2003/0195942 A l
`1112003 Davis Cl aI
`2003/0210689 Al
`200310220985 Al
`1112003 KawanlOlO cI at.
`
`200410078542 AI' 412004 Fuller l'l at.
`2004/0117600 Al
`&1004
`lJodas ct al.
`2004/0133652 AI' 7/2004 Miloushev ~~ al
`2004/0221128 A I
`1112004
`1)..,e~rofl. et at.
`5/2005 McGovern c! :II
`200510097260 A I
`612005 Aishab ct al
`2005/0138081 Al
`20061003 1407 Al
`2/2006 Oispcnsa ct aI .
`
`aTHER PUBLICATIONS
`
`711fJ72
`
`7(Y:)1214
`
`IUM [)idi onary ofCompu(inl!- pp. 455. 683. Copyr iyll 1994.·
`Die! ionary of Computer Sciencc. Engin~"Crin s and Te<:hnology. CRC
`Press. p. 184. Copyright 2001."
`Wdx.>pedia.com. file handle. one page. Copyright 2012.(cid:173)
`Non-Fina l OffiecAetion for U.S. A(lJt. No. 12/833.527. mailed Dc\:
`6.2011.
`Notice of Allowance for U.S. Appl. No. 121833.527. mailed Mar. 16.
`2012.
`Office Ad ion mailed Jun. 30. 2006 for U.s. Appl. 101708.457.
`NotieeorAl1owance maikdMay 17. 2007 for U.S.AppI. 101708.457
`
`.. cited by examiner
`
`Page 2 of 19
`
`

`
`u.s. Patent
`
`May 21 , 2013
`
`Sheet 1 of 8
`
`US 8,447,762 B2
`
`10
`
`12
`
`14
`
`16
`
`"'"
`APPLN
`o/s
`"'"
`"'" FILE SYS
`"'"
`FIB CHAN
`I
`
`FIG. 1
`
`PRIOR ART
`
`22 ?
`
`SAN
`
`(BLK ADDR)
`
`18 "\,..
`
`20 "\,..
`
`RAID
`
`DISKS
`
`18' "\,..
`
`20'"\,..
`
`RAID
`
`18" "'" RAID
`
`DISKS
`
`20" "'" DISKS
`
`"\,..
`
`10
`
`"\,..
`
`12
`
`"\,..
`
`28
`
`APPLN
`o/s
`NFS
`I
`
`FIG.2
`
`PRIOR ART
`
`32 ~ NETWORK (FILE NAME/HANDLE)
`I 521 '
`
`521
`
`26 "'" NFS
`
`14 "'" FILE SYS
`SCSI
`
`24 "'"
`18 "'" RAID
`20 "'" DISKS
`
`26' "'" NFS
`
`14' "'" FILE SYS
`
`24' "'" SCSI
`
`18' "'" RAID
`20' "'" DISKS
`
`Page 3 of 19
`
`

`
`u.s. Patent
`
`May 21 , 2013
`
`Sheet 2 of 8
`
`US 8,447,762 B2
`
`10
`
`12
`
`28
`
`"'"
`"'"
`"'"
`
`APPLN
`
`O/S
`
`NFS
`I
`
`26 "'"
`
`NFS
`
`14 "'"
`
`FILE SYS
`
`16 "'"
`
`FIBR CHAN
`I
`
`32 ?
`
`NETWORK
`(FILE NAME/HANDLE)
`
`22 ?
`
`SAN
`
`(BLK ADDR)
`
`18 "'"
`
`20 "'"
`
`RAID
`
`DISKS
`
`18' "'" RAID
`
`18" "'"
`
`RAID
`
`20' "'" DISKS
`
`20" "'"
`
`DISKS
`
`PRIOR ART
`
`FIG.3
`
`Page 4 of 19
`
`

`
`u.s. Patent
`
`May 21, 2013
`
`Sheet 3 of 8
`
`US 8,447,762 B2
`
`10 "'" APPLN
`O/S
`
`12 "'"
`28 "'" NFS
`
`FIG.4
`
`34 2 NETWORK A
`(VIRTUAL NFS NAMES/HANDLES)
`
`30 "'" VNAS
`
`(NATIVE NFS NAMES/HANDLES)
`NETWORKS
`
`36 ~
`
`<: 21
`26 "'" NFS
`14 "'-' FILE SYS
`
`24 "'" SCSI
`18 "'-' RAID
`
`20 "'" DISKS
`
`<: 21'
`26''''-' NFS
`
`14''''-' FILE SYS
`
`24''''-'
`
`SCSI
`
`18''''-' RAID
`
`20''''-' DISKS
`
`VIRTUAL NFS
`FILE NAME
`
`CLIENT
`
`34
`
`VIRTUAL NFS
`FILE HANDLE
`
`Page 5 of 19
`
`NATIVE NFS
`FILE NAME
`
`30
`VNAS
`
`~
`
`37
`
`FIG.5
`
`36
`
`DISK (NAS)
`SERVERS
`
`NATIVE NFS
`FILE HANDLE
`
`

`
`u.s. Patent
`
`May 21 , 2013
`
`Sheet 4 of 8
`
`US 8,447,762 B2
`
`IDENVERIPROJSINEXTYRIBUDGETIDEPTSIENGIDESIGNIDES_BUDGET _REV5.XLS
`
`46 J'
`
`FIG. 6
`
`10 BYTES
`
`42
`
`M_DATA
`
`- 256 BYTES
`
`46
`
`FILENAME & PATH
`
`.
`
`.
`
`CRPTO I HASH
`
`44
`
`6 BYTES
`
`10 BYTES
`
`FIG. 7
`
`Page 6 of 19
`
`

`
`u.s. Patent
`
`May 21 , 2013
`
`Sheet 5 of 8
`
`US 8,447,762 B2
`
`HASHED-NAME KEY ~41
`
`NAME (1ST)
`LOOKUP
`
`40 ~
`50 "'" STORAGE KEY
`6 BYTES
`
`UNIQUE ID -
`FROM VIRTUAL
`HANDLE
`
`,
`
`UJD (LATER)
`LOOKUPS
`
`~42
`
`48 ~ 49 ~
`
`M_DATA
`
`TBL MAINT UNIQUUD
`
`10 BYTES
`
`8 BYTES
`
`6-18 BYTES
`
`PARENT_UID
`PREV_UID
`NEXT _UID."
`
`38
`
`UNIQUEJ D
`
`FIG.8
`
`Page 7 of 19
`
`

`
`u.s. Patent
`
`May 21 , 2013
`
`Sheet 6 of 8
`
`US 8,447,762 B2
`
`-256 BYTES
`
`46
`
`FILENAME & PATH
`
`..•....
`. ........
`
`38'
`
`......
`' . .......
`
`CRPTO I HASH
`
`44
`
`6 BYTES
`
`LK_N-1
`
`HASH I XOR
`
`54
`
`52
`
`10 BITS
`
`LOCATOR KEY
`
`LK_N
`
`BUCKET_N-1
`SK_1 ENTRY_1
`SU ENTRY_2
`SK_3 ENTRY_3
`SK_4 ENTRY_4
`
`40
`
`BUCKET_N
`SK_5 ENTRY_5
`SU ENTRY_6
`SK_7 ENTRY_7
`SK_8 ENTRY_8
`
`FIG.9
`
`55
`
`COUNTER
`
`UNIQUEJ D
`(HANDLE)
`
`Page 8 of 19
`
`SK_5 SK_7
`SK_6
`SK_8
`
`MUX
`BKTJNDX
`~~
`
`HASHED-NAM E KEY
`
`ENTRY FOUND
`
`

`
`u.s. Patent
`
`May 21 , 2013
`
`Sheet 7 of 8
`
`US 8,447,762 B2
`
`VIRTUAL_FILE_HANDLE
`(UNIOUUD)
`
`UNIOUEjD
`(2ND+)
`LOOKUPS
`
`82?
`
`,
`
`C; 88
`
`C; 86
`
`C; 84
`
`UNIOUEJD
`
`FILE_NAME
`
`SVR_A NA T1VEJILCHANDLE_A
`
`8 BYTES
`
`SVR_B NATIVEJILCHANDLE_B
`
`8/
`
`85'>
`
`80
`
`FIG. 10
`
`NATIVEJILE_HANDLE
`
`Page 9 of 19
`
`

`
`u.s. Patent
`
`May 21 , 2013
`
`Sheet 8 of 8
`
`US 8,447,762 B2
`
`COLLISION-RESOLUTION BLOCK (CRB)
`
`60
`
`66 ~
`UID_X
`
`68 ~
`MAINT X
`
`64 ~
`FILE NAME X
`
`-
`
`-
`
`FILE_NAME3
`
`UID3
`
`MAINT_Y
`
`74 )
`
`76 )
`
`78 )
`
`FIG. 11
`
`62 ~
`STOR_KEY_X
`
`Page 10 of 19
`
`

`
`US 8,447,762 82
`
`STORING LOSSY IIASIJES OF FltE NAi\U:S
`ANI) PARENT HANDLES RATIJER THAN
`FULL NAMES US I NG A COMPACT TAIJL£
`FOil NETwORK-ArrACIIED-STQIUGE
`(NAS)
`
`RELATED APPUCATION
`
`Thi~ application is a divisional of "Virluali;dng Network(cid:173)
`AU3chcd-SlOrngc (NAS) wilh 11 Camp"c! Table Ihal Stores
`Lossy Hashes ofFilc Names and Parent Handles Rather than
`Full Names", U.S. Scr. No. 101708,457 filed Mar. 4, 2004,
`now U.S. Pat. No. 7,272,654.
`
`FIELD OF THE INVENTION
`
`'Jhi~ invention relates to network storage systems, and
`more particularly 10 l:ompad-silC Iransillli()1l 11lbks for vir(cid:173)
`tualized network-attached storage.
`
`BACKGROUND OF THE INVENTION
`
`Bolh supply and demand for campUler disk storage have
`increased sharply in the last decade. Com puler hard·disk
`technology and the resulting stomge densities have grown
`even faster than in the semiconductor field, "t times exceeding
`Moore's Law proj(:ct ions. Despite application-program blo..1.t
`and wider usc of large Ulllhim(.:dia files. disk drive stomge
`densities h"ve been able to keep up.
`Widespread usc o f networking has allowed for grc"ter file
`sharing. Rather than store data fi](.:s on individual user' per(cid:173)
`son,,1 compmers (PCs), m"ny companies and org"nizmions
`prefer to have important files stort..<J in a centmlizcd d;tla
`storogc. Imponant data can be regularly maintained and
`archivL.<J while being available for sharing among many users
`when stored in central stornge.
`Storage Area Networks (SANs) are widely used by large
`corpor.ations "s such a centrnlized d"ta store. FIG. I shows"
`SAN. SAN bus 22 is a high-spc<.-d bus such as a FibrcChannei
`that connects to many disk arrays 20, 20" 20". Often Rcdun(cid:173)
`d"nt Arr"y of Independent Disks (RAID) is used to mirror
`d"ta stored on the disks for gre"ter reli"bility. RAID control(cid:173)
`lers 18, 18', 18" can be inscned between disk arrays 20. 20',
`20" "nd SAN bus 22 .
`Clients such as "pplicm ion I"yer 10 gellernte disk "ccesscs
`through client opcrrlli ng system 12, which in tum usC!; file
`system 14 to access stored data. FibrcChanncl controller 16
`receives requests and pcrfomIs physic"ltrnnsfers of block
`data over SAN bus 22.
`SAN bus 22 transfers d.1.ta as blocks rdtherthLm as fik'"S. File
`system 14 convens requests for d"ta files into the block
`addr(:sscs nceded foracc(:ssing the data on disk arrays 20. 20'.
`20". An individual file can be stort:d on several blocks of data
`that are stored on any of disk arrays 20, 20', 20".
`Since SAN bus 22 pcrfonlls block transfers, there is no
`high-level file-system controller on disk aTr<lyS 20, 20', 20".
`[nste"d, disk arrays 20, 20', 20" "ct "s network,collllected disk
`driv(:s. SAN bus 22 canopernte with special protocols that arc
`designed to n}.1.ximizc da ta transfer rotesoflower-Ievcl blocks 00
`of d"ta. llms SAN bus 22 is a specialilcd bus. SANs tend to
`be very expensive and are usually not cost-effective for
`sm"ller orgmliz"tions.
`is Network
`Another widespre"d stornge technology
`Auachcd Stornge (NAS). NAS is less expensive than SAN 65
`and uses sl;tndard Transporl·Control-Protocolintemet Proto(cid:173)
`col (TePIl!') network buscs rather than a sp("Cializ(:d SAN
`Page 11 of 19
`
`2
`bus. NAS appliances arc usually single·box devices such 3S
`L1NUX or Windows systems that can easily be COIllK'ctcd to
`a TCPIlP network.
`FIG. 2 shows usc of NAS and the NAS creep problem.
`Network bus 32 is " stand"rd TCrnp network bus. Client
`"pplicmionl"yer 10 requests file "ccesses through opcrnting
`system 12 , which uses network-file-system (NFS) 28 to gen(cid:173)
`ernte file request messages thm "re enc"psul"ted by TCPt lP
`and any 10wcr·IC\'cl network protocols and sent over network
`10 bus 32 to NAS appliancc 21.
`NAS <lppliaucc 21 proccsses the message reccivr..-d over
`network bus 32 using server NFS 26, which sends the request
`to file system 14 . File system 14 looks up the file name "nd
`tS finds the file handle, which is returned to "pplication I"yer 10.
`Future requests for the cL1.t.a c"n be made by using this file
`handle.
`File system 14 can acc('Ss requested data tbrough small(cid:173)
`computer system interface (SCSI) controller 24 or another
`:10 kind of controller to access disk arrays 20. RA 10 controllers
`18 may be used for redundant data storage,ormay beomined.
`NAS appliance 21 is easy to install and maintain, since it is
`connected to network bus 32 much like any otber ndworkcd
`Pc. Network bus 32 carries NFS messages enc"psul",ed by
`25 st"nd"rd TCI'III' p"ckets, which can be the "lre"dy-cxisting
`network in an organization that the client PCs arc already
`"'t"ched to. File mmes and file h"ndles Me transferred over
`network bus 32 in the NFS messages mther than block
`addresses.
`One problem with NAS "ppliance 21 is upgrading to I"rger
`storage or faster processing capacities. As its workload
`increases, the processor on NAS appliance 21 may no longer
`be "ble to handle all requests. Addition,,1 d isks m"y initi"lly
`be added to NAS appliance 21 , but once all disk bays are
`H populated, no morc disks ean be added. Instead, a second
`NAS appliance 21 ' may need to be inswllcd o n network bus
`32. New d.1.t" could be storcdon NAS "ppliance 21 '. However,
`it is dinlcult to move data among NAS appliance 21 and NAS
`"ppli"llce 21 '. TItis is bcc"use clients lwve to mount to NAS
`40 ;tppliance 21 ' as wcll as to NAS appliance 21' . Additional
`mount requests to NAS appliance 21 ' have to be added to
`stm1up scripts for "II clients. Dat" moved to NAS "ppliance
`21 ' is fo und on adiffercnt mount point, so clients have to use
`the n(:w location to find the data. NAS appliance 21 and NAS
`45 "ppli"llce 21 ' "ppe"r "s two different file systems, with dil~
`ferent mount names. Blch NAS appliance 21, 21 ' has its own
`name space.
`It is very undesirable to have to change client software to
`retlectthe new path to NAS appliance 21 ' when.a file is moved
`50 from NAS appliance 21 to NAS appliance 2:1 '. Users may
`havc to know that the file is now acc(:ssiblc under a different
`mOlllll-point. Applications, scripts, "nd shortcuts must be
`edited to refer to the new mount-point. It can be an adminis(cid:173)
`trative n.ightmare to not ify users and change exi st ing software
`55 <lnd scripts when a file is moved from one name ~pace to
`another. Thus moving the file is not transparent to the client
`users.
`TIlis is known "s the NAS creep problem. h occurs when
`the NAS appliance 21 fills up and files have to be moved to a
`different NAS <lppliance 21 ', or when all additional server is
`installed for perfomwnce or other re"sons.
`FIG. 3 shows SAN combined with NAS. Client "pplic"tion
`I"yer 10 still sends NFS messages over network bus 32 to the
`NAS server, which has NFS 26 decode the messages "nd use
`file system 14 to look up ftle handles. Data rcqlll:sts for file
`data arc converted to block addn.'SSL'"S and sent over SAN bus
`22 by Fibn:C hanncl controller 16. '111e data is accessed by
`
`

`
`US 8,447,762 8 2
`
`3
`disk armys 20, 20', 20" aud rctumt"<ias block dlla Ihal must be
`fe-arranged 10 gcucrdtc Ihe data file.
`While using a SAN with a NAS could <lUOW for expand(cid:173)
`ability, SAN bus 22 is o ften 11 FibrcClwllue1 or Olher vcry
`expensive bus, negating the cost advan1<lgcof NAS. Protocols
`such as FibrcChaJUlcl or iSCSI lllay be u>ed. FibreChaJUlcl
`Hardware lends to be expensive, while iSCSI lends 10 be
`expensive to maintain with the required drivers, Cle. A SAN
`vinualizalion switch may also be needed.
`Somcclicnt file systems m:ly allow for directories to reside
`on different servers in one virtual space. The client file system
`lransp<lfcnlly redirects cl ient acc(:sscs 10 different physical
`servers when moving 10 a directory on a different server.
`However, thcjifallularilyof rc-din.'Clion is the dirt:ctory rathcr
`than the file. File granularity rather than dirt.'Ctory granularity
`i~ preferahle for most filc-sy~tem~.
`Whm is desired is a Network A\lached Storage (NAS)
`system thm is expandable and upgradeable and docs nm use a
`SAN bus. File -level granulari ty and virtuali7.ation is desirable
`without ahering file systems on existing NAS servers. A
`virtual NAS is desired lhat has a compact table storing meW(cid:173)
`data on a per-file basis.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 shows a SAN.
`FIG. 2 shows usc ofNAS and the NAS creep problem.
`FIG. 3 shows SAN combined with NAS.
`FlU. 4 is a block diagram of a system using virtual Network
`Auachcd Storage (vNAS).
`FIG. 5 highlights a virtual NAS translator.
`FIG. 6 shows a 10 llg path and file name.
`FIG . 7 highlights hashing of a long file and pmh name to
`generate a name key for storing in a translation table.
`FIG. 8 shows a translation table indexed by a hashed stor(cid:173)
`age key.
`FIG.9 is a diagram showing succeHive has hing to access a
`translation table that stores a hash of the file-path namc.
`FIG. 10 shows an open-file translmion table.
`FIG. II shows a collision-resolution table,
`
`DETAILE D DESCRIPTION
`
`'Ihe present invention rclaK'S to an improvement in Net(cid:173)
`work Attached Storage (NAS). The following description is
`presented toenableone of ordinary skill in the art to make and
`usc the invention n~ provided in the context of 11 pllrticular
`applicatioll and its requirements. Various modifications to the
`preferred embodiment will be apparent to those with skill in
`the an, and the general principles defined herein may be
`applied to other embodiments. Therefore, the present inven(cid:173)
`tion is not intended 10 be limited to the particular embodi(cid:173)
`ments shown and descrilx:o. but is to be llccQrded the widlc'St
`scope consistent with the principles and novel features herein
`disclosed.
`FIG. 4 is a block diagram of a system using virtual Network
`Auachcd Storage (vNAS). Client applicatioll layer 10 uses
`operat ing system 12 and NFS 28 to send NFS requests over
`front network 34 to virtual NAS translHtor 30 .
`Virtual NAS translator 30 receives the NFS request from
`clients, and perfomls name tran~lation from virtual names
`and file handles on front network 34 to native names and file
`handles on back network 36. Names translated can include
`server names and share names.
`Someclient requests aretranslat(:o to files that arc storcdon
`disk array 20 on NAS appliance 2 1, while other requests are
`translated to filL'S that are stort..J on disk array 20' on NAS
`Page 12 of 19
`
`25
`
`4
`appliance 21 '. NAS appliance 21 processes the translated
`mCSSil)!:c fL"Ccivl.J uvcrb<lck nctwork 36 u~ing scrvcr NFS 26,
`which sends the reques t to file system 14. File system 14
`looks up the native file name and finds the file handle. NFS 26
`generates the native NFS file handle, which can reference the
`file handle from file system 14. TIte native NFS file handle is
`returned over back network 36 to virtual NAS translator 30.
`The native NFS file handle is translated to a virtual file handle
`by virtual NAS translator 30 and the virtual file handle
`to returned to the client. Later requests from the cliem include
`the virtual file handle, which is translated back to the native
`NFS file handle by virtual NAS translator 30. Using the
`returned native NFS file handle, file sySIi.'m 14 can quickly
`access l"t.'quested data through small-computer system inter~
`I S face (SCSI) controller 24 or another ki nd of controller 10
`access d isk armys 20 . RAI D controllers 18 may be used for
`redundam data storage, or may be omitted.
`Translated NFS requests from virtual NAS translator 30
`arc sent over back network 36 to one or more NAS appliances
`:10 or serve.rs. Some client requests Illay be sen1 to NAS appli(cid:173)
`ance 21 while other client requests are sent to NAS appliance
`21 '. ·Ihe client is unaware which of physical NAS appliance
`21 , 21 ' fl'Sponds to each request, since names alld handles are
`intercepted and translated by virtual NAS translator 30. Thus
`the specific details of where physical files are stored among
`NAS appliances 21 , 21' arc hidden from the clients. The
`clients sec one name-space for all files accessed through
`vNAS.
`If the data is moved from NAS appliance 21 to NAS appli-
`30 ance 2 1', virtual NAS translator 30 simply translates the same
`virtual fi le handle to a different native file handle lhat poinls to
`NAS appliance 21 ' rather than to NAS appliance 21 . Virtual
`NAS translator 30 can move files and directories from one
`NAS appliance 21 to another NAS appliance 21 ' by changing
`H native c.mries in its translation table, and by $Cnding NFS
`commands 10 the NFS servers to physically move the file data.
`The virtual names and handles do not change, only the native
`server mtmlc'S and handles.
`NAS appliance 21 and NAS appliance 21 ' appear a~ one
`40 single (virtual) file systelll, with a single server name. 801h
`NAS appliance 21 , 21 ' appear as one common name space,
`even though they have different native name spaces.
`Rather than translate file names and directory name~, only
`the share nanK'S arc translated. The virtual file names and
`45 directory structures are replicated on NAS appliance 21 and
`NAS appliance 21' as exported paths and files. Thus the file
`names and dir(:ctory n;lmcs below the mOlmt -poinl do nol
`have to be stored in translation tables in virtual NAS translator
`30, since the virtual file and lower-level directory names are
`50 already stored inlhe file syslcmsofNAS appliance 21 or NAS
`appliance 21 '.
`NAS appliances 21 , 21' are easy 10 install and maintain,
`since each is connected to back network 36 much like any
`other net worked PC. Both front network 34 and back network
`55 36 carry NFS messages ellcapsulaled by slalldard TCI'/ ]]'
`packets and can be the already-existing network in an orga(cid:173)
`nizat ion that the client PCs a rc already attached to. File names
`and file handles are translated by virtual NAS translator 30
`and directed to the appropriate destination server or client.
`00 Front network 34 and b.1.ck network 36 could be the same
`network, such as a local intranet that carries all traffic offront
`network 34 and back network 36.
`When storage space on NAS appliance 21 fills up, an
`additional NAS appliance 21' can be added bYColUlecting it to
`65 back network 36 and informing virtual NAS translator 30 of
`the addition.al NAS ric 'Source. Otber NAS appliances can be
`added to back network 36 once NAS appliances 21 , 21 ' fill up
`
`

`
`US 8,447,762 8 2
`
`I S
`
`:10
`
`5
`[hcir disk arrays 20, 20'. "l1ll1s additional NAS SIOr<lgC can be
`added, solving the NAS CfCL'P problem. Files Cilll be moved
`aillong the available NAS appliances 10 L'Vcn storage and
`pcoc<."Ssing loads. New files can be created o n the n<::w NAS
`sen"crs by including the new server address orthe new NAS
`server in the translation table cll1rics for the ncw files, while
`entries for older files still poill1 10 the old NAS server.>.
`FIG. 5 highlights 11 virtual NAS trnns1<ltor. Vimml NAS
`translator 30 contain;; translation tables 37 Ihal perform vir(cid:173)
`tual-Io -native translation of names and handles. When a client
`mount!; 10 an exported directory on a NAS server through
`virtual NAS translator 30, the client gelS 11 virtual file handle
`for the root din:ctory of the export share. When using NFS,
`the client may initially open a file wilhin thm expon share by
`performing lookups of handles for intervening directories and
`then sending a vinual file name and the export root virtual file
`handle and names o f the p arent directory in an NFS request
`message sent over front network 34 to vinual NAS translator
`30 . The virtual NFS file name combin(.J with its parent
`handle is looked up in translation tables 37 to find a virtlk11
`NFS file handle w hich is relUrned to the client over front
`network 34 .
`-lhe client can use this virtual NFS me handle in future
`requests to aceess d.1ta in the file. For example, the client Ihen
`pUIS tile vinual NFS file handle in a read-request NFS mes(cid:173)
`sage sent to virtual NAS translator 30. ·I11e virtual NFS me
`handle is looked up in translation table~ 37 to find a nmive
`NFS file handle. ·I11e native NFS me h,mdle is sent in a NFS
`message over back uetwork 36 to the NAS appliance or disk
`server, which locme;; and retum~ the dma 10 vir1lk11 NAS
`translator 30 using the native NFS filc handlc.
`When creating a new entry in Irdnslation ta bk·s 37 or when
`performing maintenance, vinual NAS tran~lator 30 may send
`a native NFS me Wlme over back network 36 to ,I NAS
`appliance, which uses its native file system to find the native
`file handle, which is ret urned as a native NFS file Illlndleover
`back network 36 to vinual NAS tran~lator 30. The nmive NFS
`file handle and na tive name can then be stored with the virtlk11
`NFS file handle in translation tab l e~ 37.
`-lhu$ virtual NFS me names and virtual NFS file handles
`are exchanged betwccn the client :llld virtual NAS transi::ltor
`30 over front network 34, while nmive NFS file name;; and
`native NFS file handles are exchanged betwccn the NAS
`appliance servers and virtual NAS translator 30 ovcr back
`network 36 .
`Nmive File Handles Hidden from Clie1l1
`In a typical NFS system, the native NFS fi le handle~ can
`differ from the (k1tive file-system handles, but o ften the NFS
`layer llSes the nmive file-system handle 10 create Ihe nmive
`NFS file handle, such as by embedding the native file-system 50
`handle within the native NFS file handle. The native me(cid:173)
`system handle often contains physical information used by
`the disk system to locate the data. such as a d isk-block num(cid:173)
`ber or address.
`Virtual NAS trnnslator 30 does not interpret the Jl1ltive NFS
`file ha ndle, but merdy stores it in transla tion tablcs 37 for
`later usc. Likewise, the vi rtual NFS me handle generated by
`vinual NAS trnns!mor 30 is not i1l1erpreted by Ihe client, but
`is Illerdy stored aud later re-sen t w ith fu ture NFS request
`messages. Since the client docs not interpret the vinual NFS
`file handle, virtlk1! NAS translator 30 can arbitrarily generate
`it , such as by using a counter.
`The vinual NFS file handle canlmve no relmionship to the
`physical NFS file handle to allow for complele transparency
`to the dient. This allows for a file to be mOv(.J among NAS
`applianc(""S, which causes its physical NFS me handle to
`change, while kccping the same virtual NFS me handle.
`Page 13 of 19
`
`6
`When the native file handle;; arc hiddeu from the cl ient,
`virtual NAS translator 30 clln pcrfonn a variety of file Operd(cid:173)
`tions and maintenance on files stored on the NAS appl iance
`servers without being visible to the client. For example, files
`can be load·balanced and moved from one NAS appliance to
`another NAS appliance. The vinua! file and directory names
`are not changed but are replicated on the new NAS servers.
`The native file handles and server names are changed by the
`file movemelll to another server. Virtual NAS translator 30
`to simply replaces the old native NFS file handles or server
`names with the ncw native NI~·S file handles or server names
`without clmnging the virtual NFS file handles in tran~lation
`tables 37 . More complex data mirroring and redundancy can
`also be perfomlCd on the native files without changing the
`virtual file names and handles.
`Long File·Name Problem-
`flO. 6
`FIO. 6 shows a long path and me n.1!ne. A file is identified
`by its name and the folder or directory tb.1t the file is stoJ\..J in.
`The parent directory can be identified by its path name, which
`may comainnames of many directories between the root and
`the parent directory.
`file
`spreadsheet
`the
`For
`example,
`DES_BUDGET_REV5XLS is in the DESIGN direc tory.
`25 The grand-parent directory tlmt the DESIGN parent directory
`is in is the ENG directory. The ENG dircctory is in the DEl'TS
`directory, which is in the BUDGET directory, e tc. There are 7
`directories in the p..1th name, including the parent directory.
`File and directory names are variable-leugth strings. The
`30 file name itself may be up to 256 bytes, depending on the
`server. TIte parent directory Wlme may be tip to 256 bYles
`long. Each of the 7 directory namCS in the (lath may be a
`character string up 10 256 bytes 10ng."IllC total length ofnrune
`H 46 may be up to 8 times 256 bytes, or 2K bytes. Other path~
`may be longer or shoner, but there is a potential for very long
`names when the di rectory path is concatenated wi th the file
`name.
`A file system may conta in hundreds of mi11ions o f file;:.
`40 Storing.1ll entry with the path and file uaIlle for each file in a
`large file system in translatio n tables 37 (FIG . S)could rl'<juire
`an enormous amoullI of memory. For example, a 4 Giga-Byte
`memory C()!lld store 100 million elllries for 100 million file;;,
`but with only 42 bytes per entry. Since each path component-
`45 name can be 256 bytes long" and the complete path may have
`many path componellls, this 4 GB memory is insufficielllto
`~tore ma ny long file names or long path nam(""S.
`Solution to Long File Name Problem- H ash(.J-Name
`Entries
`TIte invelllor has realized that storing long file Ilanles and
`paths in translation table;; is not practical even for modest(cid:173)
`sized tables. Rather than store the file name and path, a Imsh
`of the file name and path is stored in the translation tabk·;:.
`1·lashingcompress(""S the variable-length file and path name to
`55 produce 11 smaller, fixed·sized value tha t is stored iuthe table.
`FIG. 7 highlights hashing o f a long file and path name to
`generate a name k('Y for slOring in a transi3t iou table. The file
`name is concatenated with its path name to generate filii
`file-path name 46. File-path name 46 is variable length and
`00 can be well in excess o f256 bytcs as each diR.-ctOIY nrullc in
`the pmh c.1n be 256 bytes.
`Hash engine 44 compresses file-path name 46 to generme
`name key 4 1. Regardless of the size of file-path name 46,
`name key 41 can be a fixed-size value such as 6 byte;;. Mela-
`65 data 42 can be appcnded to name kcy 4 1 to generate an entry
`in the translation tables. Forexample, w hcn 10 bytesof mei<l(cid:173)
`data are stored for each entry, only 16 bytes is u("('"<icd per
`
`

`
`US 8,447,762 8 2
`
`IS
`
`:10
`
`7
`entry, d(.'Spilc the presence of very long file names and paths.
`Thi5 allows milJion~ u fclllric~ 10 be kepI in iC<lsun<lbly-sizcd
`translation tables.
`'·[ash cnginc 44 may usc a cryptographic hash function 111.11
`produces a seemingly random resul1 compared with its input.
`Even a small change to the input value produces" large
`change in the hash output value when a cryplogrnphic hash
`function is used. For example, 11 small change in the inplII
`value can produce changes in about half of the output bils in
`some cryptogrnphic hash functions. lbis is ideal when using
`file-path name 46, since file systems often have many files in
`a very similar directory with the same path name. Files such
`as filc4.xls and file5.xls can have largely different storage
`keys 40 even though their file-pmh nallles 46 differ by only
`one character. 1·laving largely dificring stomge h.')'s mini-
`mizcs collisions in the translation wbles.
`FIG. 8 shows a translation table indexed by n hnshed stor(cid:173)
`nge key. Hnshed-key translation table 38 contains entries for
`files that arc physically stored on NAS appliances but arc
`referenced by virtual names. ·Ibere may be hundreds of mil-
`lions of such entries.
`Each entry 50 is also identified by a unique identifier.
`Unique ID 49 is a val ue generall:d by the virtual NAS trans(cid:173)
`Intor 111m is unique for each entry. Unique ID 49 cnn be
`generated by nn8.byte up or down cOUlller. Iflhe counter ever
`rolls over, an error is sigll<lltd, but this is lUllikcly sillce there
`would need to be nOOm 264 entries. Unique ID 49 is retumed
`to the dient as part of the virtual NFS file handle. The virtu."!.l
`NFS file handle can contain o ther clements in ;lddition to
`unique ID 49.
`Entries in table 38 can bc quickly located using unique ID
`49, which is useful when the virtual NFS file handle is pre(cid:173)
`sented or known, such as for