l|||||||||||||||||||||||||||||||||||||||||llllll||||||||||||||||l||||||||||
`
`US0084?8799'B2
`
`[[2 ..r
`
`United States Patent
`Beaverson et al.
`
`(10) Patent No.:
`(45; Date of Patent:
`
`US 8,478,799 B2
`Jul. 2., 2013
`
`-.’N'AlV[ESPACE FILE SYSTEM A(.'Cl£SSIl'|iG AN
`OBJECT STORE
`
`inventors: Arthur J. lleaversnn. l3oxhort*n1gl1. MA
`{US}: Paul Bowden. Berlin. MA {US}
`
`(73)
`
`.L\:ssig.nr.-e: SimpliVit_v Corporation. Weslborough.
`MA (US)
`
`l.*)
`
`Notice:
`
`Subject to any disclaimer. the term oflhis
`patent is extended or adjusted under 35
`U.S.(‘. 154-[bl by 360 days.
`
`App1.No.: 121023.922
`
`Filed:
`
`Jun. 25. 2010
`
`Prior Publication Data
`
`US 201 HODZZSGGAI
`
`Jan. 27. 201]
`
`Related U.S. Application Data
`
`7.454.592 Bl
`7.377.426 132*
`8.l95.636 B2“
`20040148305 :\l
`20l]fi.'0036S‘}3 Al "
`30D.‘«':'0228l5‘.-ll Al
`2l)0§l-t}2'.I'0-'<l-36 AI
`2(l09-0037455 Al
`
`II-"2008: Shah
`J-"2011 Gnibbs etal.
`672012 Stager eta].
`T-"2004 Motllton
`2.-‘E006 Doering
`‘J"2t]0S Sltavit el Ell.
`l0'2{l0S Fineberg
`2-2Dl}‘J K.lt‘.'sl'tct'tl:I:tttt1t
`
`............
`
`T0’.-"-""830
`?07"?'07
`
`'i"l4.'5
`
`O‘l'l-IF.R PUl3LlC'.ATlONS
`
`Steve Best 8: Dave Klelkamp. "J1-"S l_ii.)«'D1ll! [low the Journaled File
`System Handles the U11-Disk I_+zyoul“. May 2000. pp. I-.10."
`“AIR 5L Version 5.2 System Managetncnl Concepts: Upemting Sys-
`tem .-ind Devices". May 2004. 7th ed.. IBM. pp. l-190.‘
`“AIX 51 Version 5.2 Uencml Programming Concepts: Writing and
`Debugging Pmgrztms", Aug. 2004. Eilh ed.. IBM, pp. I-filfi.’
`International Search Rt.‘|JDI'I and Wrlden Opinion in related
`US$010-'039966 dated Nov. 10. 30l0.
`lnlentnlional Seaxch Report and \7l"ntten Opinion in related PCT‘
`[E52010-040058 dated Attg. 26. 3010.
`
`[('ootinuedl
`
`(31)
`
`(33)
`
`(65)
`
`(63)
`
`{'60}
`
`(511-
`
`(52)
`
`(53)
`
`(55)
`
`Coltlinuation-in-part of application No.
`tiled on Jun. 25. 2010.
`
`I2t'9.23.-452.
`
`.-".-'hmur_t- !:'.\m:ii::c=r — Rehana Perveen
`zlss."3ru:IlE.\'u»rfn('r
`— Scott. AW:tldro1J
`
`Pmvisiomil application No. tSi;'269,ti33. liied on Jun.
`26. 2009.
`
`.-Igem‘. or Firru —Novak Druee ClCll1.L'llCIll_V
`(74) .-l!!r)rn(4_r,
`Bove & Quigg LLP
`
`Int. C I.
`G06F )7/30
`U.S. Cl.
`
`[}_‘U0tu_(ll )
`
`Field of Classification Search
`7073323. 825, 327
`US-PC
`See application lile for complete search l1istory.
`
`7ll'H823
`
`References (Tiled
`
`ll .5. P.’-\T'l'€NT DOC UM li-HTS
`6.912.045 B2‘
`552005 Dorw.'t.rd clad.
`7.266.555 BI "‘
`90007 Coateset .1].
`7.338.217 B-2*
`2.'.'Itl(l$\‘- Borthnktir eta].
`
`?ll'2lfi
`T07-S27
`707.323
`
`{S7}
`
`ABSTRACT
`
`Method and apparatus for pnwiding it digitally signed tile
`system wherein a nzlrnespaee file system accesses an object
`store in which data. metadata and files are objects. each object
`having 3 globally unique and eonteut—derived fingerprint and
`wherein object references are ntnppcrl by the lingerprints: the
`tile system has at root object comprising -.1 ntoppiug. of all
`object lingerprints in the file systettt. such that a eltunge to the
`lile systeln results in a change in the root object. and tracking
`changes in the root object provides a history of file system
`activity.
`
`36 Claims.. 24 Drawing Sheets
`
`Allocation H «-
`
`
`3°’
`
`2"
`210
`SPRINGPATH
`SPRINGPATH
`EXHIBIT 1001
`EXHIBIT 1001
`
`

`
`US 3,473,799 B2
`Page 2
`
`OTHER PUBLICPLFIONS
`
`Rah Fl. er al.. "Art Flfficienl Hash Index Structure for Solid State
`Disks". Proceedings of 2003 International (”onI'. on ]J1fiil'IT!:lliOl1 and
`Knowledge Engineering IKE 2008. Jul. l-4-l'f. 2008. Las\"e-gas. NV
`pp. 256-261.
`(jai E. :1 al.. "fklgorilhms and Dala Strucmres for Flash Memories."
`ACM Computing Surveys. vol. 37. No.2. Jun. l. 2005, pp. 138-153.
`XI‘-0(}2453‘J'35.
`Wu C‘. :1 al.. “An Efficient B-Tree Layer for Flash-Mclnoxy Storage
`Syslems". Rea]-Titnc and Iirnhedded Cornpuljng Syslerns and
`
`Applicaljnns [Lecture Notes in Computerscience; LNCS]. Springer-
`Verlng. Berlin-"Heidelberg. Apr. 8. 2004. pp. 40*)-43!]. KPH IFJIIU5-‘I07.
`Quinlan 3 ct aI.: “Verlli: it new ap1:Im:u:h to au'cl1iv.1l sioragc" I’m—
`ceedings of Fast. Conference on File and Storage 'l'ech::-ol-agies. Jan.
`28. 2002. pp. 1-13. XT’00.‘.3S5754.
`Inlernalioual Preliminary Repori on Palenlahilily in cnntspnngfing
`PCT-'US'.?.0lO..'U4UOSS mailed Nov. 3. 201 l.
`
`* cited by exannincr
`
`

`
`U.S. Patent
`
`m
`
`Bm
`
`hS
`
`W...
`
`0
`
`
`
`am..5:
`
`J32
`
`ro
`
`
`
`Mm.HEo>tn_xoo_m
`
`
`
`c..u.__.l..\ova:gum:
`
`mQ».I....\0.32_0..C0v_
`
`
`
`
`
`no.Efimxmu__..__u3._S
`
`US 8,478,799 B2
`
`..3P_m_uuo<
`
`nun0.0m-h.:I1...\
`
`cu.
`
`92
`
`23m.830
`
`nun.
`
`an.
`
`we
`.
`
`D9.
`
`D
`
`2%
`
`83
`
`N9
`
`m.._z
`
`._m__:om
`
`NE
`
`+9.
`
`.09.
`
`xuflmvcossz
`
`«.2
`
`an...
`
`D_u_._o_o
`
`a:
`
`
`

`
`U.S. Patent
`
`3
`
`.42fl.02mEnflS
`
`US 3,478,799 B2
`
`m:_:o_m_>o._n_
`
`mno
`
`nun.
`
`own5AND“
`
`n2\
`
`1\HmnewA«Hm.33manJ#830
`
`.53mewguanoua~ aH|
`
`
`
`
`

`
`U.S. Patent
`
`Jul. 2, 2013
`
`Sheet 3 of 24
`
`US 8,478,799 B2
`
`9.T.s.\.8.Eu_ouu<
`
`
`
`M..03
`
`QR.
`
`8.
`
`own.
`
`
`
`.CE.___._ou_n_
`
`:o_mmo._.E00
`
`E2539.30
`
`
`

`
`U.S. Patent
`
`Jul. 2, 2013
`
`Sheet 4 of 24
`
`US 8,478,799 B2
`
`
`
`m_6_l\\.tmaoN2.
`
`Scum
`
`Eoummm
`
`
`
`
`
`w__.._wuonmoEDZ
`
`u9\
`
`§_.\~l
`
`EE
`
`
`
`
`
`3&5:u_uu_.noKIND».
`
`

`
`U.S. Patent
`
`Jul. 2, 2013
`
`Sheet 5 of 24
`
`US 8,478,799 B2
`
`._.9::yoauE_
`
`
`
`Tonsamomfi
`
`35EaIasI
`
`a.nx\
`
`
`
`_m._3uE..m\C3uo.__o
`
`3:_hmVmEu:o__.._
`
`
`xou:_....uo:_
`
`Commune
`
`
`
`8.1.\.\6930
`
`9.3m
`
`MGE
`
`
`
`no“1x.\w_:uuuamucbz
`
`Eoamxm
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Jul. 2, 2013
`
`Sheet 6 of 24
`
`US 8,478,799 B2
`
`
`
`-509.wmun._n_
`
`93$.85
`
`
`
`mootamua_n_
`
`N9.\
`
`uuan_noEoz
`
`Efimam2:.
`
`Ev...
`
`gnu
`
`
`
`moot~.o.om_o
`
`Eouoobumomfi$
`
`/
`
` ;EsEnvEBIIIIBIEEo»35.8.3.EIEHEE:o\mummumRmonemm....5.mm...wonanawnIUIEE
`
`
`
`
`
`.0GE
`
`
`

`
`U.S. Patent
`
`Jul. 2, 2013
`
`Sheet 7 of 24
`
`US 8,478,799 B2
`
`an
`
`hon252#0030
`
`
`
`nzum+ucoucoocoo_uvumom_n_oEnEm3n__,Co
`
`
`
`E3._oo.830:85
`
`
`
`
`
`ucoucoouoomnouommo.aEoo
`
`
`
`E3.coouuu.:.ouo...nS._ucu
`
`KGE
`
`uouefocm+uommm:n_Eoo
`
`
`
`uounefocm
`
`
`
`.6_23930_.23m
`
`.uomwo..n_Eoo
`
`£520
`
`
`

`
`U.S. Patent
`
`Jul. 2, 2013
`
`Sheet 8 of 24
`
`US 3,478,799 B2
`
`.m.:I..\.
`._3Eo_ouo<
`
`
`
`one:_oEuv_
`
`
`
`uuoz.__flmD
`
`mm.
`
`OR...
`
`mus
`
`%._nEn__4
`
`.8:
`
`3.
`
`
`
`23m50.30..cEa_._8.
`
`mmi
`
`mm.
`
`mom
`
`8.2
`
`
`
`omncfimac3m_m._on_
`
`Rm.mz352...£23
`
`mGE
`
`
`
`u_:_uos_mmfiEm.
`
`Euim«E_2.t_>
`
`
`
`
`

`
`U.S. Patent
`
`Jul. 2, 2013
`
`Sheet 9 of 24
`
`US 8,478,799 B2
`
`.2»\\gbu_.
`ozone3o>o_2
`
`.m
`
`
`-«Eco8.m..,o_2mEmov_oo:_$0
`
`
`
`
`
`mflzav_uo_m.m.n.x.\H$_o:mBaum:hm.
`
`
`/NM.“Emma.oh5::comm
`
`___u__o>..e_§m
`.RN
`.3EE23
` awn/.VNAEFC..uEo__u><..LN3mfioum
`
`.u.ww35£5
`
`
`
`IE25n.E: .n__NN._uo_m
`
`.u“N
`
`.9
`
`.2
`
`.2
`
`£___2omBonn:
`
`
`
`xwv...o+Eon
`
`Eo3o::u_n_:v_oo._
`xmu:_HQ€xV_
`
`
`
`
`
`Eo:o_.=..n_:o:o_m.._E._.
`
`:o_.._uuo....n?u_uc_¥
`
`
`
`
`
`03o..._._oBa_m:ob.uoxuam
`
`..w__
`
`Rh
`
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Jul. 2, 2013
`
`Sheet 10 of 24
`
`US 3,478,799 B2
`
`uouzoea
`
`33mEuam
`
`
`
`fixuam_3_aEn_:3:
`
`mmE_uu<
`
`HR.hon.Em.
`
`<2GE
`
`
`
`
`
`E3use»cozaacut.9_2_m
`
`muhauzhmBoo
`
`xuu:_uoxuam_au_mo._
`
`9.9;J"
`
`
`
`
`
`
`
`
`
`E3o.%._.u__a>.9_u=m
`
`me“at
`
`ban
`
`
`
`.96am_._u_m...§_fin:
`
`mmm._Pu<
`
`
`
`
`

`
`U.S. Patent
`
`Jul. 2, 2013
`
`Sheet 11 of 24
`
`US 8,478,799 B2
`
`Data Structures
`
`Flash Bucket
`
`/3
`
`09'
`
`Valid
`Record,
`
`Valid
`Record"
`
`.310’
`
`Valid
`Rscardm
`
`Reverse BTT
`Painter
`
`
`
`311'
`
`.312’
`
`31.3’
`
`FIG. 700
`
`SLC NAND Flash Organization E:-campie —-— Bucket.
`Page, (Erase) Block. Device
`
`315'
`
`NAND Flash Device
`
`Erase Black 1
`
`318'
`
`Erase Block M
`
`1KBytes
`
`1|-(Bytes
`
`F/G. 70D
`
`

`
`U.S. Patent
`
`Jul. 2, 2013
`
`Sheet 12 of 24
`
`US 8,478,799 B2
`
`
`
`
`
`no.3.
`
`
`
`
`
`¢mu0v_O3mCmflie0_u_w{v_OOI_.
`
`.an»
`/
`
`.£w.nnN
`
`2GE
`
`Eo_~o::.._azxonjA3
`xvuEHQ8vE
`
`
`
`Eo_..oE._.._:ozu_m:E._.any
`_oo_m.?_n_Hmxuuc_¥
`
`
`
`
`
`co=uoo..auxuam
`
`n__..xoo.._Avg
`
`mc_mmouncn_
`
`
`
`cosnzuaon___d__oo._
`
`mmwuoi
`
`
`
`
`
`298.co..fi..._m:n...._.yuxuzm
`
`
`
`
`
`

`
`U.S. Patent
`
`US 8,478,799 B2
`
`J..nK
`
`
`
`.._0@5000E0:anew.AC
`
`_._o_tu_mcnrFAmyam.mom._uo_w\?_n_Hnxmn:C..BEM.”co_.»u_.=...._
`
`
`
`
`
`
`_._o:a.....o\_fifiam:o:%co._._.xouc.Batu:93fiuxuam.2B.Ecouummmon3§.m_Rh..5...mcozuofl302..._t:058N\2_8oin:ADC
`
`
`nm\.,/zXKua__,o2
`
`fl£5.umfuos.mouxuoo9.eat;one\.umK
`
`
`
`
`
`3yuxusmo..mmw§:m_Eoommfimmc_wn.E90canRN1.hum.M¢y%?4Easgga\\h.
`c_mmmoEn_mo:cm36>2%.»
`
`xut:_flmxuv_¥
`
`
`
`awnEo:oc_...._n_.§oo._ASK.
`
`
`
`
`
`u_nnF:o_uo_mcn:._.woxozm
`
`.\.mm.v._tame.CVRco$o..w....otmm:_
`
`mmmocgm
`
`
`
`
`
`EN.//zmo_.._3oconoEat
`
`
`mu__umohm;mu...._
`nmfioxozm.
`
`EL:\..m/
`
`
`
`
`
`
`
`.£9.03Bebe:o_2:3.,_R:R.._mo
`
`.EN&.0._ENW\..w~.IIIIIIFaim r_mU_|._
`
`ILx8_m
`
`
`

`
`U.S. Patent
`
`US 8,478,799 B2
`
`
`
`msouoEotvoomAC
`
`
`.mucosocam_._o:n._m:E._.any
`.89...\co_uooo._umxozm\\H.9:_ou_m:EnoaE5.
`
`
`
`
`._<N9.05.t_u_..._85co=o_m:E.rxw_u:_33%nmv
`nwx/,2mago:39.0.5
`
`
`
`
`
`
`..om._2.23.8337$.A3.__w_u_.._{.22CCno.3//smutBosuaoE9:AEIC\.::/B8_o=m3_.___3z..”.._m._:_=..,_Euo.n.:.._wenwvumxozmLNE..om.//.9_%m
`
`3o_on_mmuE9.00:"mmthamham.,m$5omE_uo.2momcuoo3m:._>.__can\,\.ummM#a.,._o:m_Bc_hamEooom
`
`
`.mn¢//boomo_$93uoomAmy\S§2_2.m_._m2..cmflmmuxmmamcamouoi«sham.26>man»
`
`
`
`
`
`
`
`
`mzuco2m_oa“.3..m..._o:m390.:m_u__o>..3_o=m_
`KEN\.mw.amh.IE25
`
`
`[1[tr_mo_n_ Lv_uo_m
`
`_lomemsmut
`
`hm
`
`
`
`
`
`.Nm
`
`:3
`
`
`..co:o::.._n3_oo._nmv
`xwt:_Ho.€v_¥
`
`
`
`
`
`
`
`o_nu._.cozflmcut.yoxozm
`
`
`
`
`
`A3.3o_onCVhm:o_«c._oao3203
`
`wmuuoi
`
`
`

`
`U.S. Patent
`
`Jul. 2, 2013
`
`Sheet 15 of 24
`
`US 8,478,799 B2
`
`
`
`
`%l»__..ovcmmmonwvCu_._m.|1
`
`ofiuo58.,nuwmE,/..B
`
`ocouo
`
`
`
`Amumxozmzwofiv
`
`.o.%m.
`
`1/comm
`
`ucuoomnv
`
`
`
`ou_m<v_oo._
`
`£23.:3
`
`m.c_wmooEn_
`
`
`
`aoxuam3:_1>...|wcm__u._ooum.255dm
`
`
`
`
`
`.mn/
`
`abcmuE_uos_mumgoau3out;use
`
`.u.N.
`
`zmui\\awnswam.3.mcuouEathe__.wmncm
`
`E/wyogmcacao:o_n__:a,_25?._.E\\/3:...mommroxuzm.E.
`
`
`
`
`....:%mBEEu£.aE52_§EU_I
`
`
`
`
`.._m_u_n_v_..c_2T5
`
`an.5GEE.
`
`I.23.
`[1;mu_:._R._uo_m
`
`
`
`newmac:E9;mous"
`.098vuumA3\\.£..m.
`
`
`
`
`
`matteE...)m_n_o._.
`
`10.0
`
`\\2_...6o{oz85
`
`..m.h
`
`H:o:o..=._n_:o=u_mcn:._.Amv
`_ou_mEn_n?%é..
`
`
`
`
`
`_._o:uoo._umxozm
`
`.o%\\
`
`
`
`co_:u_m:E._.xwnE_323.:C3
`
`AuxBaum:AC
`
`Eo:uE...,_n_:xoo._A3
`xm_uc_H9mx¥
`
`
`
`
`
`_.._o:o._un_OBaum:
`
`wmoonca
`
`
`
`
`
`u_....._c._.:o_«o_m:n_.:.uuxozm
`
`
`
`3m.._o._m.._._oZuuo._zwz:2:v_n_uh
`
`
`
`
`
`
`‘|[,I.u....>o:floxuzm__<
`
`aoxuzm3on5m36>Euzm
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Jul. 2, 2013
`
`Sheet 16 of 24
`
`US 8,478,799 B2
`
`
`.n.N.m_:..m.:3..m:o:_cuo._3025:3038.
`
`LN._ou_m.?_n_flnxo_u_._c..
`
`
`
`
`
`
`mwwuxusmsmoguauoonew._.._wmuuo..n_mmeaomxuo_m:_muuxuzm_u_._u>ewxozm
`AwvCu:ml:I.1.]\2.0.5{oz9.5:o_«uoo..wmxuzm
`
`3:0vnmmmo
`2.......22;2...was5£523;.2.3.E\.8~_
`
`
`M:s.nw,.%mumoo4..§_..5mBummw33.232.
`
`
` umflora:E//x1?3:8.6....fluxogm__<]tJ
`
`
`co5u_ma~o.:.xovc.u..o_ua3A05
`
`3.5m.35.5..2.552Q3.5...£2.25
`
`.u_wN./fio_.._3ofiuoE9.fi2mfin:{m"M,_o_mw_._Vmu..._so:333m
`
`
`
`
`1...9:||.lT..oflfiuam=3.....ma
`
`
`
`
`
`
`.5:/525an.53%3..:_.__..wEI.Euamv.._.u.._£uoomA3/,r.um:
`
`
`Eoxozmm.oEno:mnfin_n_::nan:_v__a>=4use:3:E0:
`
`
`AEICeat\.N.wH"N
`
`
`
`
`
`$5523>
`
`_£/
`
`umncm53......
`
`xuoa
`
`uvxozm
`
`
`
`LmD_u._/IJNN
`
`
`
`E03922...:oSc_mc_u._._.A3
`
`.82\
`
`..n.2
`
`
`
`..3v_utu_u...._...CV3.
`
`
`
`amen.fig...£3Bonn...
`
`
`
`
`
`mwmuogm:o5o._eaOmE.m.u>oum
`
`ucofiucaun_3__oo:_ANV
`xou_.._HQ?3_¥
`
`
`
`12
`
`
`
`
`
`u_hE.co_uo.m:nc._.ymxuam
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Jul. 2. 2013
`
`Sheet 17 of 24
`
`US 8,478,799 B2
`
`.2:\\w2:._..§m
`
`
`
`omnzu.3..._Em
`
`.m.N.
`
`
`
`m..__cmoI«:oEouu_amE
`
`
`
`E£_._oo_4xouc_
`
`.633.._o:._
`lm
`
`
`
`6:000xuo_m
`
`
`
`{oio>_«u_uomm<2......
`
`an.\\«.\uuomucoEon_
`EEEEEEEEE
`
`xfi.\
`Eoucam
`
`mfldt
`
`
`
`

`
`U.S. Patent
`
`Jul. 2, 2013
`
`Sheet 18 of 24
`
`US 8,478,799 B2
`
`§E.:%_Eoam_oo_m.o.._
`
`c_UuomEmxuzm
`
`Rm.
`
`
`
`233.t:U>..$_o:m
`
`annoxwvs
`
`
`
`amxozm_uo_m.o._
`
`..m_.5cmE
`
`
`
`..QNN
`
`.bNN
`
`co5mtaom
`
`xoo_mmmo._m_
`
`
`
`mwouoiom:._m>oom
`
`{.3GE
`
`
`

`
`U.S. Patent
`
`wwhS
`
`US 8,478,799 B2
`
`IE.HBanon...
`
`uguoo
`
`2IL.M..3
`
`
`
`mmmuuoimmcmzfium
`
`Mfluxuzm
`
`
`.m82...._uo_m.E.....
`
`
`
`DHInulIHIDHD
`
`o__ogaxuam
`
`mm:GE
`
`o_n__u._.23>
`
`\RN
`
`
`

`
`U.S. Patent
`
`Jul. 2, 2013
`
`Sheet 20 of 24
`
`US 8,478,799 B2
`
`Dictionary of Records. Records
`Can be Inserted, Deleted,
`Looked Up and Modified.
`
`Implements
`Indexing Algorithm.
`the Dictionary. Multiple Algorithms
`Could be Used. Cuckoo Hashing
`Would be One Example.
`
`indexing
`Index Persistence Layer.
`Algorithms View of How Keys Are
`Stored.
`A Logical View. Assumes
`Uniform Access with Respect to
`Size, Alignment and Timing.
`Mutable Storage.
`
`Flash Adaptation Layer. Adapts the
`View and 10 Usage Profile Desired
`by the indexing Algorithm.
`to the
`View Naturally Desired by the
`Physical Media (FLASH in this
`
`example).
`
`Device Management. Tracks and
`Coordinates Resources on the
`
`Physical Device
`
`
`Physical Device (FLASH). Characterized
`by its Non—Uniforrn Read, Write and
`
`lmmutability with Respect to Size.
`
`Alignment and Timing. Examples
`
`include Raw FLASH, an SSD. or FLASH
`with a "Flash File System‘ on it.
`
`
`
`
`
`
`
`FIG. 17
`
`201'
`
`J‘/20-4'
`interface is Lookup.
`Delete. Insert.
`Modify a record
`
`20.3’
`
`205'
`
`/206'
`Logical Bucket
`Operation s
`(Read/Write a Bucket).
`
`207’
`
`/203'
`Physical Bucket Operations
`(Random Read. Aggregated
`Writes. Trim Commands).
`At this Level We're Modeling
`Non-—unifor‘m Access
`209,
`of Buckets.
`
`210'
`
`/
`Physical Device Operations.
`Random Reads. Large
`Black Sequential Writes,
`Trim Commands.
`
`211'
`
`K 202'
`
`

`
`U.S. Patent
`
`Jul. 2, 2013
`
`Sheet 21 of 24
`
`US 8,478,799 B2
`
`Mao
`
`\
`
`Record Format
`
`%
`
`141'
`
`142'
`
`145'
`
`144'
`
`145'
`
`FIG. 78
`
`150'E‘
`
`Buckets
`
`X
`‘O’ T 72‘ T 34' E F
`L__l L___J L__J L__l
`B0
`B1
`B2
`B3
`
`FIG. 20
`
`15a':\
`
`Bucket Format
`
`E
`
`161'
`
`162'
`
`163'
`
`FIG. 27
`
`

`
`U.S. Patent
`
`Jul. 2, 2013
`
`Sheet 22 of 24
`
`US 8,478,799 B2
`
`Displacement Hashing (Cuckoo Hashing)
`
`H00‘)
`
`2
`
`1
`
`P
`
`Q
`
`H100
`
`5
`
`FIG. 79A
`
`0 Moves
`
`_
`0
`
`E f.’
`1
`2
`
`2
`3
`
`_. _ ..
`4
`5
`6
`
`

`
`U.S. Patent
`
`Jul. 2, 2013
`
`Sheet 23 of 24
`
`US 8,478,799 B2
`
`E:
`
`.89
`
`
`
`96N.9335:m<._..__8_a:_n_
`
`NNGE
`
`955so
`
`265so
`
`.2:
`
`Amy.3Exuam
`
`8..i«won.Amy.a«man.
`
`..m.©__
`
`ExEVx8_m«mam82+8._uo_m3.5
`
`
`
`
`

`
`U.S. Patent
`
`Jul. 2. 2013
`
`Sheet 24 of 24
`
`US 8,478,799 B2
`
`Device Management
`
`[:| E] El -0- El
`O
`1
`1
`0
`
`O
`
`1
`
`O on 1
`
`I70’
`
`Pages (Buckets)’Z
`Page Allocation MM
`Indicates Which
`
`171’
`
`Pages are Valid
`Pending Trim Map X’
`(Pages to be Trimmed
`but not Dane 80 Yet).
`
`172'
`
`F/6‘. 23A
`
`175'
`
`Erase Biock E
`Descriptor
`
`176"
`
`:77‘
`
`Erase Black [
`Descriptor Table
`
`
`
`# Full Writes
`
`FIG. 2.38
`
`173'
`
`
`179’
`
`780'
`
`by Erase
`Block Index
`
`
`151'
` 182'
`
`

`
`US 8,478,799 B2
`
`1
`NAM ESPACE FILE SYSTEM ACCTESSING AN
`OBJECT STORE
`
`FIELD OF Tl-IE INVENTION
`
`The present inventiort relates to computer file system data
`structures and to methods and apparatus for the naming and
`storing of tiles.
`
`IBACECGROLJND
`
`A fully featured storage solution may include raw disks. a
`file system. snapshots, file versioning. compression, encryp-
`tion. built—in capacity optimization (e.g.. data deduplication ).
`other security features such as auditing and tamper resistance,
`cflicient replication to an off-site location for disaster recov-
`ery purposes. and so forth. Many of these featttres are deliv-
`ered in separate appliances that then have to be connected by
`highly experienced technicians.
`C'onsLrL:cting such a storage solution with today’s technol-
`ogy. tor many terabytes {TBs) of data. often results in a
`multi—box solution that can easily exceed costs of S] 00.000.
`making such a fully featured storage solution not available to
`many businesses and customers.
`This mnlti-box. ad-hoe solution is not a ftnidzunctital aspect
`o I" storage, but rather that file system architectures and imple-
`mentations have not kept up with other technology develop-
`ments. For example. most file system architectures have not
`evolved to fully leverage the faster computer processing units
`[('PUs}. flash memory. and the different balance between
`network bandwidth. disk density and disk access rates.
`If one defines data accessibility as the ratio ofaccess band-
`width to addressable storage.
`the accessibility of data is
`decreasing. Storage densities are increasing faster than the
`access to the disks. so fora given data set size, the time needed
`to access the data is increasing (and thus causing reduced
`accessibility"). The eflect on storage architectures is as lol-
`lows: once one stores the data, one should not move it unless
`absolutely necessary. This simple observation is violated
`many times in current storage architectures where data is
`constantly being read in and written out again. The result is
`significant extra expense (e.g., 10 channels, CPU, power.
`time, management).
`
`SUMMARY O1’ 'l"l-ll;-' INVENTION
`
`lit
`
`15
`
`Ztri
`
`40
`
`-'13
`
`In accordance with one embodiment ofthe invention. there
`
`is provided a tile system comprising:
`a digitally signed file system in which data. metadata and
`files are objects. each object having a globally unique
`and content-derived fingerprint and wllerein object ref-
`erences are mapped by the fingerprints:
`the file system having a root object comprising a mapping
`of all object fingerprints in the tile system;
`J: ‘J:
`wherein a change to the tile system results in a change in ..
`the root object. and tracking changes in the root object‘
`provides a history of file system activity.
`In one embodiment:
`the file :fi'Slt)t1'l includes an inode map object comprising a
`mapping ofinode numbers to file object fingerprints and
`wherein the lingerprint ofthe inode map object com-
`prises a snapshot of the file system.
`In accordance with another embodiment of the invention.
`there is provided a computer
`readable medium containing executable program instructions
`fora method ofindexing stored objects. the method compris-
`mg:
`
`6|]
`
`2
`
`providing data. metadata and tiles as objects;
`providing a fingerprint for each object which is globally
`unique and derived from the content of the object: and
`wherein a file system root object is provided comprising a
`mapping o fall object fingerprints in the file system. such
`that it change to the file system results in a change in the
`root object. and tracking changes in the root object pro-
`vides a history of tile system activity.
`ln one embodiment, the method includes:
`providing a file system inode map object comprising a
`mapping of inode numbers to file object fingerprints.
`wherein the fingerprint of the inode map object comprises
`a snapshot of the file system.
`In one embodiment. the method includes:
`
`publishing the inode map fingerprint to another computer
`systcnr on a distinct object store.
`in one embttdiment, the method includes:
`using the inode map fingerprint as a snapshot of the tile
`system for disaster recovery.
`In one embodiment:
`the inode map object contains a fingerprint of a previous
`inode map.
`In one embodiment:
`
`the previous inode map fingerprints comprise a history of
`snapshots of the file system.
`in one embodiment:
`
`the objects have reference counts; and
`upon a change to the tile system. adjusting the object ref-
`erence counts of every object beneath the inode map
`object.
`ln one embodiment:
`
`the adjusting is performed on every 10 transaction to pro-
`vide continuous data protection.
`in one embodiment:
`the adjusting is performed periodically, on demand. or on
`particular events to generate snapshots.
`in one embodiment:
`the objects have reference counts; and
`adjustments to the reference counts are utilized for data
`deduplication such that only new data content is stored.
`In accordance with another embodiment ofthe invention.
`there is provided a computer file system for naming and
`storing of files on one or more computer storage devices. the
`system comprising:
`a namespace file system wherein tiles. data and metadata
`are objects. each object having a globally unique finger-
`print derived fi'oru the content of the object. cach file
`object comprising a mapping o l’ object fingerprints for
`the data objects andfor metadata objects of the file and
`the file object having its own objcct fingerprint derived
`from the fingerprints of the objects in the file, and
`wherein the system includes a mapping of inode num-
`bers to the file object fingerprints.
`in one embodiment:
`
`object references are defined by the object fingerprints.
`in one embodiment:
`
`the file object mapping comprises a linear list. a tree struc-
`ture or an indirection table.
`ln one embodiment:
`
`the tile objects include a root object having its own object
`fingerprint derived from all of the objects in the file
`system such that every object in the file system is acces-
`sible through the root object.
`In one embodiment:
`
`the namespace file system is provided as a layer in a storage
`stack between at virtual file system layer and a block
`storage abstraction layer.
`
`

`
`3
`
`4
`
`US 8,478,799 B2
`
`111 one emboditnent. the system funher comprises:
`an object store containing an index of object fingerprints.
`object locations and object reference counts.
`in one embodiment:
`
`the object store index is stored in non-volatile memory.
`In one cmbodirncntt
`
`tlte fingerprint is an cryptograpliic hash digest ofthe object
`content.
`In one embodiment:
`
`the object size is variable.
`In one embodiment:
`
`the file system is a POSIX compliant file system.
`In accordance with another embodiment of the invention.
`there is provided a trtelhod conlprisingz
`tile
`generating object fingerprints for data objects in .1
`system. the data objects comprising data or metadzttn.
`and the object fingerprints comprising a globally unique
`fingerprint derived from the data object content:
`generating object lingerprinls ii-r lilo objects, wherein each
`file object comprises the fingerprints ofa plurality ofthe
`data objects in the file and the file object fingerprint‘
`comprises a globally unique fingerprint derived from the
`file object content; and
`generating, a root object comprising a mapping ofall the
`object fingerprints in the lile system.
`In one embodiment. Lhe niethod comprises:
`maintaining ti reference cottnt for each object. and updating
`the object's reference count when references to the
`object are added or deleted.
`lt‘l one embodiment. the method comprises:
`generating a transaction log of object activity, including
`reads. writes, deletes and reference count updates.
`In one embodiment. the method comprises:
`adding. modifying or deleting a data object in a file and
`gencmtittg a new lile object fingerprint.
`In one embodiment:
`
`when the content o.f :1 file object or data object is changed.
`propagating the change up to the root object".
`In one embodiment. the method comprises:
`performing the propagating step at one of:
`every IEO transaction;
`periodically:
`on demand:
`at a particular event.
`In accordance with another embodiment of the invention.
`
`there is provided a method comprising:
`providing a plurality olidala objects. each data object corn-
`prising data or tnetadata. and each data object having a
`fingerprint whichis globally unique and derived from its
`content; and
`generating a file object comprising a plurality of data
`object fingerprints for a plurality of associated data
`objects. and generating at file object fingerprint which is
`globally unique and derived from the content of the file
`object; and
`maintaining an index of inodc numbers to tile object tin-
`gcrprints.
`In one embodiment, the method comprises:
`maintaining a location index for mapping object linger-
`prints and physical locations of the objects.
`In one embodiment:
`
`the location index includes reference counts for the objects.
`In one enlbodililetllr
`the fingerprints and indices comprise a file system.
`
`1U
`
`15
`
`3t
`
`40
`
`-'13
`
`St‘:
`
`fill
`
`ti.‘-
`
`In accordance with one embodiment, there is provided:
`a computer program product comprising progtm code
`means winch. when executed by a process. performs the
`steps of method claim 2'7.
`In accordance with another embodiment of the invention.
`
`there is provided:
`a cotnpttter-readable ntediutn containing executable pro-
`gram instructions [or a method of indexing stored
`objects. the method comprising:
`generating fingerprints which are globally unique and
`derived from the content of data and meladata objects:
`generating file objects comprising a plurality of linger-
`prints of data andfor metadata objects and generating
`fingerprints of the file objects which are globally unique
`and derived for the content of the file object; and
`generating a root object comprising a mapping of all the
`fingerptints of the data, metadata and file objects.
`In accordance with another embodiment of the invention.
`
`Iltere is provided:
`physical processor and storage devices providing access to
`data. metadata and files: and
`wherein the data. mctadata and tiles are objects. each
`object having a globally unique and content-derived lin-
`gerprint and wherein object‘ references are indexed by
`the fingerprints: and
`the indexing includes mapping o finode numbers to the tile
`object fingerprints.
`In accordance with another embodiment of the invention.
`there is provided:
`a processing and storage apparatus for naming and storing
`data objects and collections of data objects comprising
`file objects. each data ob_iect comprising data or meta-
`data and each object having a content-based globally
`unique fingerprint as its object name, the lilo object
`being a collection of data object names and having its
`own content-based globally unique lingerprint as its file
`object name;
`a file system having two layers including:
`an object store layer including a mapping index ofobject
`names and physical object locations: and
`31 namespace layer including a mapping index of data
`object names liar each file object.
`In one embodiment:
`the namespace layer includes a mapping index of inode
`numbers to the tile object names.
`In one embodiment:
`
`the object stone layer includes reference counts for each
`object.
`In one embodiment:
`
`the object name is a cryptographic hash digest ofthe object
`l'.'-l"‘lEl[i3l‘ll..
`In one embodiment:
`
`the system includes hardware acceleration apparatus to
`perform for one or more to fobjecl naming. cornpressi-on
`and encryption.
`In one embodiment:
`
`the object store layer includes a global index ofall objects
`in the file system. wherein the primary key for the global
`object index is the object name. and the object name is n
`cryptographic hash digest‘ of the object content.
`
`BRIEF DESCRIPTION OF TI-IE DRAWINGS
`
`The invention will be more iitlly understood by reference
`to the detailed description. in conjunction with the 1'ollowing
`figures. wherein:
`
`

`
`5
`
`US 8,478,799 B2
`
`6
`
`is at schematic block diagram illustrating one
`1
`FIG.
`embodiment of the invention integrated into an operating
`system kernel space:
`FIG. 2 is a schematic block diagram of the major compo-
`nents of one ernhoditnent ofan ohjmt store. enabling the
`object store to be hosted on a variety of physical media;
`FIG. 3 is a schematic block diagram ofone embodiment of
`an object store that can abstract out key functionality.
`enabling said Iiinctionnlity to be implemented in a variety of
`ways without impacting the object store design: implemen-
`tations may range from a pure soltware solution. to one using
`hardware acceleration;
`FIG. 4 is a schematic block diagram ofone embodiment of
`a set of objects grouped together into a construct ("bnode'"] as
`a basic building block ofan integrated file system:
`FIG. 5 is a schematic block diagram of one ernbodirnentot‘
`a.n h.nodc tliat't:nr_1 be specialized into other data strtlctttres as
`needed by the tile system. such as files. directories and imaps;
`FIG. 6 is a schematic block diagram ol‘ one embodiment
`illustrating how changes to the file system are tracked and
`maintained overtime. and how the techniques used naturally
`result in space efiiciency. itnmutabiiity and security:
`FIG. 7 is a schematic block diagram ofone embodiment of
`an object that can transparently handle compression. encryp-
`tion and location independence while providing a globally
`unique name liar the object‘; and
`FIG. 8 is a schematic block diagram of an alternative
`embodiment of the invention implemented in user space with
`FUSE, File System in User Space; FUSE is an open source set
`oflibraries and lo:
`-‘I modules that enable the construction of
`File systems in user space.
`FIG. 9 is a schematic block diagram illustrating various
`indexing operations performed in accordance with one
`einbodiment of an l]](.ll3.Xll'lg invention;
`FIGS. IIIA through 10D illustrate various ernbodiments of
`data structures which may he used in the invention:
`FIG. 11 is a schematic block diagram illustrating a lookup
`operation according to one embodiment ofthe invention:
`FIG. 12 is a schematic block diagram illustrating an insen
`operation according to one embodiment of the invention;
`FIG. 13 is a schematic block diagram olia delete operation
`according to one embodiment of the invention:
`FIG. 1-1 is a schematic block diagram of an update opera-
`tion according to one embodiment‘ of the invention;
`FIGS. ISA and [SB are schematic block diagrams illus-
`trating a random read process tor generating free erase blocks
`according to one embodiment of the invention;
`FIGS. IISA and I613 are schematic block diagrams illus-
`trating another method of generating tree erase blocks
`according to a scavenging process:
`FIG . I7 is a schematic block diagram illustrating a six layer
`view or stack For ill ttstrating on iniplcrnentation ofthc inven-
`tion:
`FIG. 18 is a schematic diagram ola record entry as used iti
`one embodiment of the invention:
`FIGS. 19A-I913 illustrate schematically an implementa-
`tion of cuckoo hashing according to one embodiment of the
`invention:
`FIG. 29 is a schematic illustration ofmu] tiplc buckets. each
`bucket holding multiple records according to one embodi-
`ment of the invention:
`FIG. 21 is :1 schematic diagram of the contents of a bucket
`according to one embodiment of the invention:
`FIG. 22 is a schematic block diagram illustratiiig one
`example of a physical flash chip having multiple dies, erase
`blocks. pages. and buckets according to one embodiment of
`the invention; zuid
`
`IIJ
`
`IS
`
`3U
`
`40
`
`-“I3
`
`=1: ‘J:
`
`EIIJ
`
`ti?-
`
`FIGS. 23A-2313 illustrate certain components of a device
`management
`layer according to one embodiment of the
`invention.
`
`[)Ii’|'./\ll-IiI) I)l-_iSCRII’T[ON
`
`A. Traditional File System Data Structures and
`[.imitations of Prior Art (Legacy) File Systems
`
`A traditional file system has several basic data structures.
`In addition to user visible directories and files. internal su'uc-
`
`lures include superblocks, inodes. allocation maps. and trans-
`action logs.
`Allocation maps are data structures that denote which
`blocks on a disk are in use or not. These data structttres can be
`as simple as a bitmap. or as complicated as a htree. Allocation
`maps can be large. and almost never lit in memory. Naive
`allocation of new blocks results in low disk pert'oi-rnancc. but
`optimal placement requires sophisticated allocation algo-
`rithms given the aloreincntioncd memory limitations.
`Directories are lists ofnames of files and other directories.
`and in many file systems. are treated as another file type that
`is just interpreted differently. Internally a directory is a list of
`lilenamefinode number pairs. When the tile system wants
`access to a filenatne, it must find the filename in a directory.
`and the corresponding inodc number.
`Files
`named collections ofdata. A file name. along with
`the "mode it references. is stored in a directory structure. Many
`file systems support the concept of links. where different file
`names can point to tile same data (made).
`Transaction logs are used to keep the file system consistent
`in accordance with Atomic. Consistent. Independent and
`Durable (ACID) properties. Many lile systems will guanuttee
`metadata consistency. but have dillerent service level agree-
`ments (SI As] For data.
`A superblock is a small data structure that resides at a
`l-uiown location on a disk or persistent niediurn. From the
`supcrblock. all other data structures relevant to the tile system
`can be found. such as the size and location of the inode table.
`allocation maps. the root directory. and so Forth. When a lile
`system is mounted. it is the superblock that is lirst accessed.
`For sa fety reasons, supcrblocks are often replicated. at various
`points on a disk.
`Perhaps the most fundamental data stnicture is the mode
`(“index node"). Cornnion to many file systems. it is a data
`structure that is the basic container for content. such as a file.
`The inode itsclldocs not contain a filcname: that is stored in
`
`the directory. An inode is identilied by an integer that denotes
`an index into a disk resident data structure (the in-ode table].
`Each inode entry in the table describes where on the disk the
`content can be lbund for this file. This “map” can take various
`forms. including linear lists. indirection tahlcs, various tree
`types. each of which have various speedfspace tradeolfs.
`Important is that the map uses physical or logical addressing.
`such as a logical block number (I. BN1. An Ll?-N only makes
`sense if you know which disk it is intended for.
`From the above description, it should be clear that legacy
`file systems have tight control of the what (content) and the
`where [placement of data). This co-mingling of what and
`where. largely an artifact o fhistory. results in an architecture
`that is ditficult to extend to modern storage needs.
`
`13. Novel Data Structures and Feantres ofthe File
`Systems of the Invention
`
`In accordance with various embodiments of the invention.
`new data structtu-cs arcprovidcd for implaiiting a new type of
`
`

`
`US 8,478,799 B2
`
`i
`
`It:
`
`15
`
`8
`These and other benetit