TheAlpinefilesystemMarkR.Brown,KarenKolling,andEdwardA.TaftFebruary,1984Abstract:Alpineisafilesystemthatsupportsatomictransactionsandisdesignedtooperateasaserviceonacomputerinternet.Alpine'sprimarypurposeistostorefilesthatrepresentdatabases;animportantsecondarygoalistostoreordinaryfilesrepresentingdocuments,programmodules,andthelike.Unlikeotherfileserversdescribedintheliterature,Alpineusesalog-basedtechniquetoimplementatomicfileupdate.AnotherunusualaspectofAlpineisthatitperformsallcommunicationviaageneral-purposeremoteprocedurecallfacility.Bothofthesedecisionshaveworkedoutwell.ThispaperdescribesAlpine'sdesignandimplementation,andevaluatesthesysteminlightofourexperiencetodate.AlpineiswritteninCedar,astrongly-typedmodularprogramminglanguagethatincludesgarbage-collectedstorage.ThispaperreportsonusingtheCedarlanguageandprogrammingenvironmenttodevelopAlpine.XEROXXeroxCorporationPaloAltoResearchCenter3333CoyoteHillRoadPaloAlto,California94304p^{ cqX co$'. 0BrSu sK tKfa!>$*&. 7/:;|ACrI  (r$d*/]5!68p<.?FB=GT Kd#'5(*.48 @ E iAD ezx#%h(' .37u8@G? %K!'-o249;g>@QF< W$)039<>KBH: ,?V!j'-~2!4?BH8r 6) $+%4 zD^JN )/ 9?B2b  $)+/2S6<? 0. 'yu t*. *. 17 V*.J3T5 "*. 1{ 8'TVm$TheAlpinefilesystem11.IntroductionThesystemwedescribehereisknownwithinXeroxas"ResearchAlpine"or"RAlpine".Toaidreadabilityweshallcallit"Alpine"inthispaper.Alpineisafilesystemthatsupportsatomictransactionsandisdesignedtooperateasaserviceonacomputerinternet.(Svobodova'ssurveyarticle[Svobodova,1984]describestheconceptofatomictransactionsandthenotionoffileserviceonacomputerinternet.)Alpine'sprimarypurposeistostorefilesthatrepresentdatabases;animportantsecondarygoalistostoreordinaryfilesrepresentingdocuments,programmodules,andthelike.Today(inFebruary,1984)anAlpineserverstoresthepersonalandshareddatabasesuseddailybyabout45peopleatXeroxPARC;ithasbeenavailableasaservicefor10months.Thesystemdoesnotyetmeetallofitsgoals,andisstillbeingdeveloped.Thispaperisorganizedasfollows.Section2describeswhywebuiltAlpine.Asonemightexpect,ourrationaleforbuildinganewfileserverhadalargeimpactonitsdesigngoals.Section3detailsAlpine'saspirationlevelalongmanydimensions:concurrency,reliability,availability,andsoforth.WetrytojustifythesegoalsintermsofthemotivationsfromSection2.Section4discussesthetwodesigndecisionsthathadthegreatestimpactontheAlpinesystem:theuseoflogsinsteadofshadowpagestoimplementatomicfileupdate,andtheuseofremoteprocedurecallsinsteadofstreamsormessagepassingforcommunication.Itmayseemunnaturaltodiscussanimplementationtechnique,likelogging,beforethedesignofAlpinehasbeendescribedinmoredetail.ButbothofthedecisionshighlightedinSection4weremadeveryearlyinthedesignofAlpine,andhavehadalargeimpactontherestofthedesign.InSection5wepresentthedesignindetail,explainingthebasicabstractionsthataprogrammerseeswhenusingAlpine.Section6discussesourimplementationoftheseabstractions.Section7evaluatesAlpine.WedescribetheexperiencegainedfromAlpineapplications,givethecurrentstatusandplansforthesystem,andpresenttheresultsofrunningsomesimplebenchmarks.AlpineiswrittenintheCedarlanguage[Lampson,1984],usingtheCedarprogrammingenvironment[Teitelman,1984].Section8ofthepaperreportsourexperiencesinusingCedartodevelopAlpine.Atthispointinthepaper,onlyafewfactsaboutCedararerelevant.TheCedarlanguageevolvedfromMesa[Mitchelletal,1979],aprogramminglanguagefeaturinginterfaceandimplementationmodules,strongtypechecking,andinexpensiveconcurrentprocesses.(AdaissimilartoMesainmanyrespects.)TheCedarlanguage'smostsignificantextensionsofMesaaregarbagecollectionandtheoptionofruntime,ratherthancompile-timeorbind-time,typediscriminationandchecking.TheCedarnucleusisabasicenvironmentforrunningCedarprograms.Itincludesapagedvirtualmemory,theruntimesupportforincrementalgarbagecollection,andasimplefilesystemwitharead-writeinterface.ThereisnoprotectionboundarybetweenotherCedarprogramsandtheCedarnucleus;theCedarlanguage'stypecheckingmakesitveryunlikelythatanon-maliciousprogramwillcorruptthenucleus.vg"%*,tgGw^  v[mU "0&+/M1 7<> FYt  1#%(HW?mgT$)h 035:<AxC*DXU  : $)-d 5`98?PAG%R  B "$)t+q,2 9>oCP  WF\ &5(e/58:<@"ENn   \&8(+OL9m" %L)U-2/57<#B?EwJ  "$7&* /127h9;ADcG Q Z#$}'* Em/c%7*5+146:P?BDCf O ,!Q$9&*-X.|16`8a:7>BGA2 j "& .Z 6{ = D]G> [!#='(+! 25:<mMIV#),Q/ 1i6u:=?cC: .rN!f%T'%.-25X:f=A?B[D78_ (0 }";',Y. 9:=@G06+ \` R #%+/16U8"<?CB3  FG$ +-2L3n6:X=T@BCD1  X)0#%'*,8.35_:2;Z=uB<D/  y  &;))*r 2t5l9@= BG-Y r # +$mZ "(* 1n59a= E(  })'9 m%',I.}24.9:<@ &mQ,8#k)059;@L $  /$&8( *.3J5 =l?6BG0"R  m_)#4$'T*.25};x>  ?Cv @&Nx E!v"$'(*P 3a9@F' q5J"A(=* 27 9 ?CDY  i! W >$e +. 5) ;=A[CK +"a&e) 13 :(=/ F' xv @!%' -[/59V@B,G m`"P') 16 =@AFu &@i  !u%v&( /s5;>By ?zn &q)].3 4;7&? D :% TVm$22.MotivationforbuildingAlpineAmongtheresearchtopicsbeinginvestigatedinXeroxPARC'sComputerScienceLaboratory(CSL)aredatabasemanagementsystemsandtheirapplicationtoinformationmanagement.Wefeelthatinthefuture,databaseswillsupplementorreplacehierarchicaldirectorysystemsastheprimarytoolfororganizingcomputerfilesandthatmoreandmoreinformationwillmigrateawayfromfileswithspecializedformatsintowell-integrateddatabases.Inourenvironment,allsharedfiles,includingfilesthatrepresentdatabases,arestoredonfileservers,soresearchinvolvingshareddatabasesrequiresanappropriatefileserver.Earlyin1981,whentheAlpineprojectbegan,wehadtwofileserversavailabletous,IFSandXDFS[Israeletal,1978,MitchellandDion,1981].IFS(InterimFileServer)storesnearlyallofourlaboratory'ssharedfiles.IFSwasdevelopedin1977andisdesignedfortransferringentirefilestoandfromapersonalworkstation'slocalfilesystem.Itdoesnotsupportrandomaccesstofiles;thismakesitinappropriateforstoringdatabases.IFSiswritteninBcplfortheAltoandwouldnotbeeasytomodify.XDFS(XeroxDistributedFileSystem,alsoknownasJuniper)isafileserverwithmoreambitiousgoals.XDFSsupportsrandomaccesstofilesandprovidesatomictransactions.Weconstructedasimpledatabasemanagementsystem[Brownetal,1981]andseveralapplicationsthatusedXDFStostoreshareddatabases.WefoundthatusingXDFScrippledsomeimportantapplications.Thebasicoperationsofcreatingatransaction,readingandwritingfilepages,andcommittingatransactionweredisappointinglyslow.Theservercrashedfrequently,andrecoveryfromanycrashtookoveranhour.Andtheserverallowedonlyasmallnumberofrandomlydistributedfilepagestobeupdatedinasingletransaction(althoughamuchlargernumberofsequentiallyclusteredpagescouldbeupdated).AtthattimetheCedarprogrammingenvironmentprojectwaswellunderwayandXDFS,writteninMesafortheAlto,wasanunattractivebasisforfurtherdevelopment.SinceneitherIFSnorXDFSmettheneed,wedecidedtobuildanewCedar-basedfileserver,Alpine,tosupportourdatabaseresearch.ThisserverwouldsubsumethefunctionsofXDFS,whichcouldbedecommissioned.Giventhatwewerebuildinganewfileserver,weconsideredmakingitgoodforstoringordinaryfilesaswellasdatabases.OnereasonforthisisthatCedarrunsonapersonalworkstationthatisseveraltimesfasterthantheAlto,andthetimespentwaitingforIFStodoitswork(orretryingwhentheserverwasrejectingconnections)wasincreasinglynoticeable.ACedar-basedAlpineservercouldusethesamehardwareasthefastestCedarworkstation.Also,Cedarplannedtoincludealocalfilesystemthatsupportedtransparentcachingofremotefiles.WeexpectedthatthemoreconvenientaccesstoremotefileswouldincreasetheloadonourIFSservers,makingtheperformancemismatchbetweenworkstationandserverevengreater.WealsoknewthatextensionstoIFSinsupportoftransparentfilecachingwouldbedesirable.Forallofthesereasons,wehopedthatAlpinecouldreplaceIFSaswellXDFS.Thiswasdefinitelyasecondarygoal,becausethedeficienciesofIFSwerenotasseriousasthoseofXDFS.tg/ w^  v[mhOY#5 *,06<A Yt  $'\* 13J : CF3W@ ss ' (- 4:?AOCU w j #6&),K/ 7f:?BER  tW&R -.17 9;V?BP x% Y#%r',.%3h9N=CNn  ( {"@%),505:<>? ADML: f<x#(L:L:#$v%L:L:&*E/2v6WJm2h"V&(*V, 4p8<?BFG  pE $(+-0a35 : CFuE _" &'+-13+ ;=Bg Cg b/`!#'*q,b/f1A2m "(+%/179h:=AEK> ;!e&+,038= FT<  =O &r*x/<<0m1kv2~<<3d79>p F: 8G %(-0=488>B}8a / "#)c* 2D7j:S?7AF'6, d (-0439V @uCO3 I!H#[&)B-26"7;W@B1 x{b#%&e* 18+9=AG%/ L* ")+.u1482 @ -Z _"&a$+(*.y03D69; C.F+& T (m%! #D%)]+02]57,: BDz& ~!"2%Z(i,k0638>{@)D$ wh"Sm9I #&*j,y 3G89V<>CO  b] /@#%(*,14D6W7= DGs Z"D!R$'&)-2479;=AWC P5 %(B / 78 @]D &<b -"&+* 37M;@BGM OF 'B,j.L3759?BEK {#(+-/2U49>@   %"&1)/\2 48; BDUG0 p  ! %<'- zmC]@T % (,058s:K=cBF3 F ")$ , -0368E<>BbD, TVm$TheAlpinefilesystem3Forinstance,bypartitioningourlaboratory'sfilesbetweentwoIFSserverswesignificantlyimprovedfileserverresponsetoCedarworkstations.WewouldnothaveconsideredbuildingAlpineonanAlto.IFSseemstorepresentthelimitofwhatwecanbuildonacomputerwith16-bitaddressingfordataandnohardwaresupportforvirtualmemory.ManyoftheproblemswithXDFScanbetracedbacktoAltolimitations.Cedar'slargevirtualandrealmemoryarewhatallowedAlpine'sgoalstobeamoreambitiousthanthoseofIFS.3.DesigngoalsWerequirethefollowingterminologyforthediscussionthatfollows,andintheremainderofthepaper.Auserisahumanbeingwhousesacomputerservice,saybymakingmouseclicksortypingcommandstoacommandinterpreter.Aclientisaprogramthatusesacomputerservice,saybymakinglocalorremoteprocedurecalls.ThepurposeofAlpinewastosupportotherCSLresearchprojects;Alpinewasnotanendinitself.Thishadsomenoticeableeffects.Itencouragedaconservativedesignwewishedtouseproventechniquesfromthepublishedliteraturewherepossible,andtouseexistingcodewherepossible.(IFS,ourmodelofasuccessfulfileserver,wasbuiltusingmanyexistingAltopackages.)Italsoencouragedadecompositionoftheprobleminawaythatallowsthesystemtobeginsupportingitsprimaryclients,databasesystems,withoutrequiringthattheentirefilesystembecomplete.Wehavealottolearnaboutsystemsupportfordatabases,andourclientshavealottolearnaboutusingshared,remotedatabases;thesoonerwecouldbegintoprovidedatabasestorageservice,thesoonerbothpartiescouldgetonwiththelearning.Atthesametime,Alpinewasitselfaresearchprojectthatpermittedustotryoutasetofideasonwhatfunctionsshouldbeincludedinafileserver,andhowthesefunctionsarebestimplemented.Anyprojecttobuildafileservermustarriveatdecisionsaboutawidevarietyofissues,includingconcurrency,reliability,availability,fileaccess,distributionoffunction,capacity,accesscontrol,andaccounting.WesetthefollowingdesigngoalsforAlpine:Concurrencyandreliability.WedecidedthatAlpineshouldimplementatomictransactionsonfiles.Alpine'saspirationlevelforconcurrencyshouldbetoallowconcurrentupdateofonefilebyseveraltransactions.Alpine'saspirationlevelforreliabilityshouldbetosupportconfigurationsthatsurviveanysinglefailureofthediskstoragemediumwithoutlossofcommittedinformation,butthisdegreeofredundancyshouldnotberequiredinallAlpineconfigurations.Providingatomictransactionsattheleveloffileactionslike"readapage"and"writeapage"isunusual.Atypicaldatabasesystemimplementsasetofaccessmethodsasalayerontopofaconventionalfilesystem.(Examplesofaccessmethodsincludedatabaserecordsaccesiblebysequentialorhashedsearching,B-Treeindicesonrecords,anddirectpointerchainslinkingrecords.)Mostdatabasesystemsimplementtransactionsattheaccessmethodlevel.Wecanidentifythreevg"%*,tgGv_/ E & ')/;14{8; B\ !u Zm !' +-/m3P59;ACG%X ~  '#.' -/25}7o=cB[DV]   8 K#p'*k,f0358 @xEwT( t5 %+ .052%3O6=8@^CEwL  vImRu &1(~* 14a9 @}G%G| xG|G|WvG|I"%(*:0v5f79>CIGEH i '}x)EHEH)vEH,. /+47w:g;AFC  A"@mTl!x&*@-~28=.?BkDjG0> + 0%z' .c/ 7w;=@DFiOA 5  h"e'v-y0L269=?FT3 ^` %(( .14E8<=\?A^D1o b. !&r(,0W27+<AF/; 'p ,#T%, .047<$>BEC{- fQs"K#%'+>-a06;=CbE.Fu* US!$ (mUjK"=%)Z*04_5m8=>B&i  I !$(n /17f= AF'$4 x  $(^*xm d v "'*/H3:?K F  F (-!/04| ;i@ADsFa ;  $L') /4q6a8= F- Y !&+035-; CF=  V F"7')u+e/mE "p$('),\1378<?}CD  2r\# +x,.04:C: T/!5 (*- 1;6g:=s@EU YTVm$_4potentialadvantagesforimplementingtransactionsatthefilelevel.First,solvingconcurrencycontrolandrecoveryproblemsinafilesystemsimplifiesanydatabasesystemthatusesit.Withoutfile-leveltransactions,eachaccessmethodmustimplementtransactionsbyexplicitlysettinglocks,writingrecoveryinformationonthedisk,andinterpretingthisinformationincaseofbothsoftandhardfailures.Thebasicatomicactionavailabletotheaccessmethodimplementoriswritingasinglepagetodisk.Simplifyingthedatabasesystemisespeciallyimportantifthedatabasesystemitselfisanobjectofresearch.Databasesystemsthatwereorignallydesignedforbusinessapplicationsarenowbeingtriedinnewdomainssuchasofficesystemsandcomputer-aideddesign.Thisexperiencehassuggestedwaystomakedatabasesystemsmoreusefulinthesenewdomains,butthecomplexityofrealdatabasesystemshashinderedexperimentationwiththem.Second,file-leveltransactionsprovidetheoptionofrunningthedatabasesystemonaseparatemachinefromthefilesystem.Thismovesprocessingloadawayfromthemachinethatissharedbyallusersofaparticulardatabase.Mostdatabasemanagementsystemsareprocessor-bound,soitisworthconsideringtheoptionofmovingsomeprocessingloadfromthefileservertotheworkstation,orfromthefileservertoaclosely-coupleddatabaseserver.Runningthedatabasesystemonaseparatemachinefromthefileservermayalsohavesomedrawbacks.Itdoesnotminimizecommunication,becauseittransmitsfilepagesratherthandatabaserecordsoruserkeystrokesanddisplayupdates.Thiswouldcertainlybeaproblemonalow-speedcommunicationsnetwork.Ifthedatabasesystemrunsintheworkstation,itisunlikelytobesecure,andhenceitcanonlyprovideironcladaccesscontrolattheleveloffiles,notdatabaserecordsetsorfields.InCSL,neitherofthesefactorsrulesoutlocatingthefilesystemanddatabasesystemondifferentmachines.Third,providingtransactionsatthefilelevelensuresthatanapplicationcanusethesametransactionabstractiontodealconsistentlywithalldatastoredinthefilesystem.Areasonableapplicationmaywellwishtomanipulatedatastoredbothinarawfileandinsomedatabaseusedtoindexthisfile,ortomanipulatedatastoredinseveralspecializeddatabasesystems.Itispossibletocreateseveraldatabasesystemsthatsharethesametransactionabstraction,butitseemsmorelikelytooccurifthetransactionimplementationisshared,asitcanbewithfile-leveltransactions.Accompanyingthethreepotentialadvantagesoffile-leveltransactionsisonepotentialdisadvantagealossofconcurrencyduetolockingofunitssuchasfilesorpagesthatareunrelatedtothesemanticsofthedatabase.Adatabasesystemthatperformsitsownconcurrencycontrolandrecoverycansetlocksonlogicalunits,andavoidsomeartificialconflictsthatarisefromfileorpagelocking.Ourintuitionisthatthelossofconcurrencywouldbeunacceptablein,say,anonlinebankingapplication,butwouldnotbenoticeableinmanyoftheapplicationsthatwefindmostinteresting,suchasofficesystems,programmingenvironments,andcomputer-aideddesign.Ifthisprovesfalse,thenwehavenochoicebuttomovetheresponsibilityforconcurrencycontrolintothedatabasesystem.Eveninthiscasenotmuchislostaslongasmostoftheimplementationoffile-leveltransactionscarriesovertothedatabasesystem.tg/ v_/ g c #` *,x.1A\m S"%+1236+: @CCZ !o # *. 27:~A^ X  p 0% -+/"1r47Q >AT V]  @-%%(1+04:<?CT( <"J#Qm 2"E# )0B139>AmBDO  j!$*0^28 ?B EM :0e1#), 6+;?G FiKV H X%](-.2W5K;-=@ G%I" br!D+p.Fm O %(R,.w36;@EBTCD +K!% ,/36x8>RABFB  & S $f* 2(7/9DKFGs@P  *v $' .)1*469.=,>A >  o6Z&,+;m?f #$S)/]25O7;? AEK9  )/0K6!8y<2@.CC7} QQ #})~,06v8n9?)A7Bg5I %q),.0 8: ;q@BaDL3 ZI*,#|',+-03O48<:@;DG0 r] G$(K*0#25"9<BBF. Q,wm\ !"%()+036 =P@BEa*B   &),/C35t8:@SB (  %(',Z/1c25X7:AvCEj 53!$& .{24 =h?BD6 " a"W$r +)-025a =!@BjE  ! ) 25u ?dDF=  "Z$&*<, 57> >CF {:"%z)+%-/358:= G% d P * D!$R) TVm$TheAlpinefilesystem5Availability.Sincestoragemediumfailureisrare,wedecidedthatAlpineshouldbeallowedtorecoverfromitslowly(inafewhours);crashescausedbysoftwarebugsortransienthardwareproblemsmaybemorefrequent,andrecoveryshouldthereforebemuchfaster(5-10minutes).Itshouldbepossibletomoveadiskvolumefromonefilesystemtoanotherandtostoreavolumeoffline.Ourenvironmentdidnotdemandcontinuousavailabilityofafileserver;wecouldtoleratescheduleddowntimeduringoffhoursandsmallamountsofdowntimeduetocrashesduringworkinghours.Ifbetteravailabilityhadsignificantcost,wedidn'twantit.Fileaccess.Alpineshouldbeefficientatbothrandomandsequentialaccesstofiles.Accessatthegranularityofpages(fixed-lengthalignedbytesequences)seemedsufficientfordatabases;itisnogreatadvantagetoprovideaccesstoarbitrarybytesequences.Thegoalisgoodaverage-caseperformanceforfileaccess,nottheguaranteedreal-timeresponsethat,forinstance,avoicefileservermustprovide.Distributionoffunction.WedecidedthatmovinganAlpinevolumefromoneservertoanothershouldbetransparenttoclients,andthatasingletransactionshouldbeabletoincludefilesfromseveraldifferentAlpineservers.Avolume-locationserviceseemedeasytoimplementusingtheGrapevineregistrationdatabase,whereasafile-locationservicebasedonGrapevinewouldbetooslow.Multi-machinetransactionsarenowsupportedbyseveralcommercialdatabasesystems,andadequateimplementationtechniquesarewellunderstood.Capacity.WethoughtitwouldbeniceifoneAlpineservercouldmaintainhundredsofsimultaneousworkstationconnections;thecostofaninactiveconnectionshouldbelowattheserverend.Accesscontrol.WedecidedthatAlpineshouldimplementsimplecontrolsoveraccesstofiles.Ouraspirationsforaccesscontrolwerelowbecausewefeltthatdatabasesystemswillimplementtheirownaccesscontrolpolicies;inthissituation,itisthedatabasesystem,nottheuserofthedatabasesystem,thatrequiresauthenticatedaccesstofiles.Accounting.WedecidedthatAlpineshouldimplementsimplecontrolsovertheallocationofdiskspacetovarioususersandprojects.ThisiswhatIFSprovided,anditwasacceptable.Usingthefileservertostoredatabasesdoesnotcreatenewproblemsinthisarea.BecauseourCedarworkstationsarepowerfulpersonalcomputerswiththeirownrigiddisks,theissuearoseofwhetherAlpineshouldbeabletorunonaCedarpersonalworkstation.Thissupportsthestorageoflocaldatabases,andsmallsystemconfigurationsthatdonotcontainadedicatedfileserver.WedecidedthatthisisusefulandAlpineshouldallowit.Alpinewillnotserveastheonlyfilesystemontheworkstation;thestandardfilesystemisstillrequiredforperformingspecialfunctionssuchasstoringbootfiles.Asaresult,allowingthisconfigurationaddsalmostnothingtoAlpine'simplementation.Aworkstation-basedAlpinefilesystemmaybelimitedinsomewayswhencomparedwithaserver,forinstancebythelackofindependentdiskvolumestoimproveperformance,reliability,andavailability.WeexcludedseveralthingsfromAlpine,decidingthattheywerebestregardedasclientsofvg"%*,tgGx_,m v_,_,u&$?()-*/N4l77;@1BG0\ _\ %*/17:<BZ  x#A(-m3f5g9O= @GgX >Da7v!{&z),/935:=~?BBCVZ  W & -$ 4579n=@CT& ]"%>(.D/6B8:?*CQ ]  &")H+o/r2xOm+vOO  &H'+022 9d=m?BGFM  ) #'+ 27 =?` F GsKT  q#H%*. 58;=c@ I Ky " )/59;AYBFuF  xDm vLDD %5',.3I8);>*B.CB >E T "%&* 268;=}BsEw@M j> "u,1m69;BF>  %[& .]379.@DcFu;  ; #9&R,.3 ; @F'9  h "D$' x7{mv7{7{uCA#%)*-2r6:@G%5F  K #=%(Z* +1 7Q@BzD3 x0mv00X "',27e<?CE.   8! $~'?,.1`4P: ?-A,t  Qk!"% +-T.1z7BArDF*@ G5 &*,qx( m v( ( 4j!L%*u1n5;1>_@ G%% g"D%Y()-a0$6[9:=9 D#  t/"%P)S,A2I369m$1 "$\*#/6?9O<?BF 5y"f$L';(+k-g.28 @>CN  !K$) 25j7:>@.Fu 4#%*R.2p49;>8AChEg W] $"(+N0 14:o< Dc2 6n"E$]%)/B1 :d=BG0 (0,.3^6M8*<>bAE) &?!h#@%{(:) 14e9;8@ - `m #(.V1K47;@BG% TVm$6AlpineratherthanpartofAlpineitself:Adirectorysystem(mappingtextnamesforfilesintointernalfilesystemnames)isrequiredinordertomakeAlpineuseable,butadirectorysystemsupportingdatabasesneednotaspiretoreplaceIFS.Atsomefuturetime,wemaywishtobuildadistributeddirectorysystemtosupportlocation-independentfileaccessandperhapssomeformoffilereplication.SothereareadvantagesinavoidingastrongcouplingbetweenAlpineanditsdirectorysystem.APup-FTPserver[Boggsetal,1980]isaclientofthedirectorysystemandofAlpine.TheFTPserverisnotrequiredfordatabaseaccess,butisnecessarytoreplaceIFS.AsystemforarchivingfilesfromtheprimarydiskstorageofafileserverandforbringingbackarchivedfilesisaclientofthedirectorysystemandofAlpine.IFSdoesnothaveanarchivingsystem,either.4.Twomajordesigndecisions4.1ImplementatomicfileupdateusingalogThetwotechniquesmostoftendiscussedforimplementingatomicfileupdatearelogsandshadowpages.ApaperontheSystemRrecoverymanager[Grayetal,1981]arguesthatlargeshareddatabasesarebestupdatedusingthelogtechnique,andmanydatabasesystemsuseit.WechosethelogtechniquefortheAlpinefileserver.Butthepublishedliteratureshowsthatalltransaction-basedfileservershavechosentheshadow-pagetechnique[Svobodova,1984].Whatarethetradeoffsbetweenshadowpagesandlogs?Todescribetheshadowpagetechnique,wemustclarifysometerminologyconcerningfiles.Tous,afilepageissimplyafixed-lengthalignedbytesequenceinafile;ifthepagesizeis512bytes,thenbytes[0..511]areonepage,andbytes[512..1023]arethenext.Adisksectorisaregionofadiskthatiscapableofstoringapagevalue.Afilesystemimplementsfilesusingdisksectors.Theshadowpagetechniqueisbasedontheobservationthatthesectorsofadiskarealwaysreferencedthroughalevelofindirectioncontainedwithinthefilesystem.Toreadafilepage,theclientpresentsafileIDandpagenumber,andthefilesystemreadssomedisksectorandreturnsitscontents.Thefilesystemcontrolsthemappingfromthepair[fileID,pagenumber]todisksector;callthisthefilemap.Thefilemapmustberepresentedonthediskinsomerecoverableway,i.e.itmustsurvivefilesystemcrashes.Usingthisobservation,onetechniquethatthefilesystemmayusetoupdateapageistoallocateanewsector,writethenewpagevaluethere,andmodifythefilemapsothatreadsgotothenewsectorratherthantotheoriginal.Iftheclientcommitsthetransactioncontainingthepageupdate,thischangetothefilemapmustbemadepermanentonthedisk,andthesectorcontainingthepreviousvaluemustbefreed.Iftheclientabortsthetransaction,thennopermanentchangetothefilemapneedstobemade,andthenewsectormustbefreed.tg/ v_/ 1?eI \mG |#4'x),/|46;w@4AG0Z P = !'+ 28<*>BD X H5! $k')-/| 6<ACV] 3B!')*.'/2L 9<?A T)  YK#_'*,w2IQm,SxQQx vQ"&U'),.1H74;>@oFO HM$%(+ ,x24:8Mmg{"%4*d-K1347.;3=@EKV jn,%,),.4c7I:=L@BI" wA  AyBEw4 I $' ) 0;26<}AD FT2 Rx %T'-`0?29q ?CF0[  %k' 06c >5BF.'  5*!$+mB0 p ')9,04X ; BF)  xw))'v) #u(N+d1R34578:>5@BWD' o C@H #'@*=+u/#1{379dx),30 8;>A# mar I!%'*l 147M;=?B Dz y< $+L/24u9<?2@dBF e<]  M%({*-715C8;?BXG : #N) ,r.14x6:@?ADnO 2x,OO|vOOK!%& .S0U257E: B$EPG :m\ &%k(&*s,114"68 <=@BCC / e$(*/14f79W<.?ACE}  "p$(."0 7 >D@CH sA*k #&.0.268;? F  :J9 ("&F*i, 47@9E@*DF /!$(,,. TVm$TheAlpinefilesystem7Therearemanyvariationsoftheshadowpageidea.Theylargelyconcernthemanagementoftwopermanentdatastructures:thefilemapandtheallocationmap,whichrepresentsthefreeoroccupiedstatusofeachdiskpage.Variousrepresentationsofthefileandallocationmapsarepossible,andforeachrepresentationtherearemanydifferentalgorithmsthatmaybeusedforupdatingthemapsinawaythatisconsistentwiththeoutcomeoftransactions.Thelogtechnique,ontheotherhand,representseachfileasafileinasimplefilesystemthatdoesnotsupporttransactions.Arequesttoupdateafilepageisrepresentedbyarecordinalog,generallycommontoallfilesinasinglefilesystem.Inonevariation,calledtheredolog,alogrecordcontainsthefileIDandpagenumberofthepagebeingupdated,plusthenewvalueofthepage.Thenewvalueofthepageisnotwrittentotheunderlyingfilebeforetransactioncommit;instead,avolatileversionofthefilemapisupdatedtosaythatthecurrentvalueofthepageresidesinaspecificlogrecord.Tocommitatransaction,writeacommitlogrecordforthetransaction,thenwaitinguntilalllogrecordsforthetransactionhavereachedthedisk.(Somethinganalogoustothiscommitrecordisalsorequiredintheshadowpagetechnique,butwedidnotpointthisoutabove.)Afteratransactioncommits,abackgroundprocesscopiesthenewpagevaluefromthelogtotheunderlyingfileanderasesthevolatilefilemapupdate.Arequesttoabortatransactionisimplementedbyerasingthevolatilefilemapupdate.Therearemanyvariationsofthelogideainadditiontotheredolog;Lampson'spaper[Lampson,1983]containsamoregeneralviewoflogsandtheiruses.Thelogitselfisrepresentedasafixed-lengthfile,andthisfileismanagedasaqueueofvariable-lengthrecords.Thestoragefortheoldestlogrecordmaybereusedwhenthereisnovolatilefilemapentrypointingtoit,thatis,whenitstransactioneitherhasabortedorhascommittedandwrittenthecontentsofthelogrecordtothefileupdatedbythetransaction.Toillustratethedifferencesbetweenthetwotechniques,weconsideraclientthatcreatesatransaction,writes10pagestoanexistingfileunderthistransaction,andfinallycommitsthetransaction.ComparetheI/Oactivityrequiredinashadowpageimplementationwiththatinalogimplementation:Beforecommit,theshadowpageimplementationallocates10disksectorsandwritesnewpagevaluestothem.Italsowritesenoughadditionalinformationtodisksothatthecorrectchangescanbemadeinthefileandallocationmapsregardlessofwhetherthetransactioncommitsoraborts.Afterthetransactioncommitsthenewsectorsareincorporatedintotheexistingnon-volatilefilemapandthe10existingsectorsarefreed.Beforecommit,thelogimplementationwrites10logrecords,eachslightlylargerthanafilepage,tothelog,andforcesthelogtodisk.Aftercommit,itreadsdatafromthelogandwritesittotheunderlyingfile.(Infactthefilewritesarebuffered,andareonlyforcedtodiskperiodically,unlikelogwritesthatareforcedforeachtransaction.)Whichtechniqueispreferable?TheshadowpageimplementationseemstorequirelessI/O,vg"%*,tgGv_/mx  #(+h/O27d<? G%\ w| {!$'*x-\\-3lv5\\6; AD.GZ 3^"(M2369><2 BFX qT #'I)-3 :=AC+FV] sqI!![ '*-+24 T(mK Zg"q&N ,0 2}415a79:?AFQ h  %k'$+,/m247 ;=>CDDF3O Vhx H!%(--/2 8<x?WOO?B}vDAOOE?FM lDr1"')r+/&28;>ADFKW !R"%`**+.e 5l7+-7/2T49n=>ADXF  Je@!" )-f.3q59<#>s ED {!\ (T+036 >+DF=B h5 s"'+ 14A6i8;T>AD @P a  &+x/255:8 uG"["$I'=,]-2p37p8s ?H@ ;  Jn$B(=*.L 4658:=?qDF9 n#2&,>-h059 :=@QC7~mU "$N ,8/62+5 79Y?rA]BG%5J z;!#&D*/,k035j9=V@BD 3 #Ku1 "&_(H /R3L5:<?>F'0 ^-E"$&)_.03 .m & Q%(}+X 25:<@BG,x M"$'|*4.1t 9<@F*C }x#e(*+03 =@CEdF( #+p # -347<(>BE!qt!&h , 4358:C<?;C<UAf! 'T* 1J28H: AGI% "(+\.3A5 > A6C c!#(-h/jJ{ (g,u.g069>>B E>Fu5Si!$&q(<,=/5l6:=A<CF'L  #&J) +|-24t:{=E?BG0 !%'*8.}03 ck #.&+.v 8f9CE TVm$8becauseeachpageiswrittenjustonce,whereasthelogimplementationwritesdatafirsttothelog,thenlaterreadsdatafromthelogandwritestotheunderlyingfile.Itistruethattheshadowpageimplementationmustalsoupdatethenon-volatilefilemap,whichisnotnecessaryinthelogimplementation,butthisshouldrequirefewerthan10pagewritesbecausemanydatapagesarereferencedbyeachfilemappage.Nowconsiderthefollowingsixadvantagesofthelogimplementation.Theyconsistoffourreasonswhythelogimplementationmightperformbetter,oneaddedfunctionitprovides,andoneimplementationadvantage.Thefirstperformanceadvantageisthatitallowsanextent-basedfilestructure,thatis,afilestructurethatattemptstoallocatelogicallysequentialpagesinaphysicallysequentialmanneronthedisk.Anextent-basedfilestructurehasperformanceadvantagesforbothsequentialandrandomaccess.Theadvantageforsequentialaccessisobvious:theextent-basedfilestartscontiguousandstaysthatway,whiletheshadowpagefilelosesitscontiguitywhenitisupdated.Theadvantageforrandomaccessderivesfromthefactthatthefilemapissmallerinanextent-basedfilestructurethaninashadowpagefilestructure.Thefilemapissmallerbecauseitonlyneedstorepresentthelocationofafewlongrunsofpages,ratherthanrepresentingthelocationofeachpageindividually.Withasmallerfilemap,itislessoftenthecasethanafilereadcausesextraI/Ostoreadthefilemap.ThesecondperformanceadvantageisthatmanyoftheI/Osinthelogimplementationarecheap.Thelogisimplementedasasinglefileandlogwritesarestrictlysequential.Existingdatabasesystemsshowhowtooptimizelogwrites[PetersonandStrickland,1983].Manyclientswillcommitatransactionshortlyafterperformingallofthetransaction'swrites.Inthiscase,thelogrecordscontainingthenewvaluesoftheupdatedpageswillstillresideinthebufferpoolafterthetransactioncommits.Thismeansthatreadingtheselogrecords,whichisnecessaryinordertowritethedatatotheunderlyingfile,usesnoI/Os.Soundertheseassumptions,eachupdatedpageiswrittenoncetothelog(asequentialI/O)andoncetotheunderlyingfile(asequentialorrandomI/Odependingupontheclient'saccesspattern).Thethirdperformanceadvantageisthatthelogimplementationperformsfewerdiskallocations.Logrecordsareallocatedsequentiallyfromaboundedfile;thisinvolvesasimplepointerincrementandtest.Shadowpages,incontrast,areallocatedusingthegeneraldiskallocatorforfilepagesafterall,ashadowpagebecomespartofafilewhenthetransactioncommits.Sotheallocationofashadowpageismorecomplexandexpensivethantheallocationofalogrecord.Therequirementthatdiskstorageallocatedtoshadowpagesnotbelostinasystemcrashincreasesthecomplexityandexpense.Thefourthperformanceadvantageisthatthelogimplementation(atleasttheredologwehavedescribed)defersmoreworkuntilaftercommit.Thisimprovesaverageresponsetimeforupdatesifthesystemislightlyloaded,orheavilyloadedwithaburstypatternofupdaterequests.Iftheloadissteadyandheavy,thereisstillaperformanceadvantageifpartoftheupdateloadisconcentratedonasmallsetofpages.Withtheredologimplementation,aheavilyupdatedpageistg/ v_/ l S#)M+. 8<?&B CF3\ ` #k'l)+z 2j57&8;u>C@EZ !$? ,#.268;|ACFX  0%%),n.16;m?cBFV] pl T(m U" )+.#0;?WCEQ H "+&'+/26<0=CwF3O  Mmga #$')-d/v 7: @TCDE)FuKV _%R I% ,'/12 9 ?DFI" + F"%E -j 46:B @CF 9 ##'E(.u0 8;x?! F'D # %j(* 0457A=d@3FB b !$m&),&-2>35 =@ E@P  m #&)+g0[57*:o>{@UF> Pdy-"J&R)s 1E38:=@ ; 9sJF' $p&)-.M038:;?@DFu9 7~mt4 g% &)-/257n9<~ F5I K B  ^!n%?'*+,d0L26 >CC3 26 $*- 4v8<A4C0 # #v%'a) 168;?AD . Nm'o$(f*-1o35O9gdAD2G0*C  !a#x'+& 3R6;?W@E(  Q A#-$') .0p2 8:>?VB% @<I#m5 "$B')O+ 5`;+>A !q Pe "&\'-G0&289?=Bg= m+Y"$*.058>h@C$F Cvu j#W%&N(,. 5s@ G% ^e"(X+v- 4569$>@A  bA#&)+.;01C59?`A k c6m>p m#%A(*`, 68;>A,CxE _*!$Y*U-38>EAzC  &6 %*S-.3 79>zDF :: "X%A& /57i:<??DGs d #1&),J.8: >D(Gs NTVm$TheAlpinefilesystem9writtentoitsunderlyingfileonlywhennecessarytoreclaimlogspace;otherwiseitscurrentvalueresidesinthebufferpoolandinthelog.Theaddedfunctionthatthelogimplementationsupportsisfilebackup.Backupprotectsagainstfailureofthediskstoragemedium,e.g.duetoaheadcrash,bykeepingaredundantcopyofallcommitteddata.Thewholepointoftheshadowpageschemeistowritethenewdatajustonce,butthisisnotconsistentwithadesiretomaintainabackupcopy.Inalog-basedfileimplementation,backupcanbeimplementedbytakingaperiodicdumpofthefilesystemandsavingalllogrecordswrittenafterthemostrecentdump.Itisevenpossibletotakeadumpconcurrentlywithfileupdateactivity,sothatbackupisnotdisruptive.Themajorimplementationadvantageofthelog-basedapproachtoatomicfileupdateisthatitcanbelayeredonanexistingsimplefileimplementation.Thisistruebecausethelogapproachdoesnotrelyonanyspecialpropertiesofhowfilesareimplemented;itsimplyreadsandwritesfiles.Thefastertheunderlyingfilesystem,thebetterthelog-basedimplementationperforms.Thelog-basedtransactionimplementationcanbestructuredsothatmostofitdoesnotdependondetailsoftheunderlyingfilesystem,andiseasytomovefromonefilesystemtoanother.Addingtransactionloggingtoagoodexistingfilesystemismuchlessworkthanwritinganewfilesystemfromscratch,includingallofitsassociatedutilityprograms.4.2CommunicateusingremoteprocedurecallsManyspecializedprotocolshavebeendesignedforaccesstoafileonaremoteserver.Forinstance,XDFSincludedaspeciallytailoredprotocolbuiltdirectlyuponthePuppacketlevel[Boggsetal,1980].Inprinciple,clientsofXDFSviewedinteractionswiththefileserverintermsofthesequenceofrequestandresultmessagesexchanged.Inpractice,clientsofXDFSusedastandardpackagetoprovideaprocedure-orientedinterfacetothefileserver.Oneoftheusualargumentsinfavorofmessage-orientedcommunicationisthatmessagesprovideparallelism:aclientprogramcansendamessageandthendomorecomputation,perhapsevensendmoremessages,beforewaitingforareply.IntheMesaenvironmentparallelismcanbeobtainedbyforkingprocesses,andtheseprocessesarequiteinexpensive[LampsonandRedell,1980].SointheMesaenvironmentitwasnaturaltoviewinteractionswithXDFSasremoteprocedurecalls.Unfortunately,theimplementationofXDFSitselfdidnotreflectthisview(perhapsbecausetheMesaprocessfacilitieswereaddedaftertheprojectwaswellunderway).Inparticular,therewasnocleanseparationbetweenthefilesystemanddatacommunicationscomponentsofXDFS.Forinstance,adatatypedefiningthepacketformatwasknowntothefilesystemcomponentofXDFS.Asaresult,changesinthecommunicationscomponentcouldforcerecompilationoftheentiresystem.InAlpineweenforceacleanseparationbetweenthefilesystemanddatacommunicationscomponents.Thisisdonebydefiningthesystem'sbehaviorintermsofasmallsetofCedarinterfaces,notintermsofanyspecificnetworkprotocol.Theinterfacesareusableeitherbyaclientvg"%*,tgGv_/ s6% * $*,1~38)>g@VE5\ 2?nJ"XZm/<X! +1 2u4:L?+DBX "tN"2$')w*.82A4Z9:AEFV] !r#B%*.!346]9Q ~ F?#k$)-/14f8;?AD O S)A" #v$(-H.126 >ADKM _4 KVmKH ,%'i)/67<9>CBDGI" &!$I.13H6;-=}?EF G !$') 2387;>lB]FD t F ""&(/$ 9 ?BB  R!Y '),0#13]69.>/@KDF@P D6 !#'g*-0A46<A > ,O$"#'*_-0569<@C; hC !y6i  .%v3m #&,w.3 46-8:<5AF30 C'B!&,/X4?7:<A8Dox.  Nv.R  k"8&+a 268u:?@DF, M!$ *Km> #X$*"/f16$7PC9(  fHIZ"7(*.L0: DF%  F# (+1.r/47:<@ # V!%i*;,w-236.9 A !y b "R$(Z.;0r3 ;7AD!D w #%_(M-A/12 :N=BGD7 .m  #%t)-/z168;AjF Q"  $(&+-0 8T: @D0Fr | Q!@%(,/ 6 >@F3> Py} X$)-+0]2 4j6;MBtD,  R %,0g3 <_=@=D mx;*! (.y138r;f> W%9'-h3T5>9D;9<@yBD l x& l lv l)7#(j.1w 79>"BCE TVm$10thatneedsallthefeaturesofAlpinefileserviceorbyonethatimplementsasimplifiedfileaccessprotocollikePup-FTP.Wewerequitefortunatethataprojecttoproduceageneral-purposeremoteprocedurecallfacility[BirrellandNelson,1983]wascarriedoutconcurrentlywiththedesignandimplementationofAlpine.Oneresultofthisprojectisacompiler,calledLupine,thattakesaCedarinterfaceasinputandproducesserverandclientstubmodulesasoutput.TheclientstubmoduleexportstheCedarinterface,translatinglocalcallsintoasuitablesequenceofpacketsaddressedtoaserver;theserverstubimportstheCedarinterface,receivingpacketsandtranslatingthemintolocalcalls.(WediscussthismorefullyinSection5.1below.)Lupineimposessomerestrictionsoninterfacedesign;itwillnottransmitarbitrarydatastructuresfromonemachinetoanother.Evenso,Lupinedidnotinhibitthedesignofourfilesysteminterfaces.LupinehasmadetheevolutionofAlpinemuchsimpler,becausewecanbuildanewversionofthesystemwithoutinvestingalotofefforttokeepthecommunicationscomponentconsistentwiththefilesystemcomponent.Lupinegeneratesabout6000linesofcodeforusewithAlpine.ItispossiblethatwecouldhavemaintainedthecleanseparationbetweencommunicationsandfilesystemwithoutLupine,andevenwithoutadoptinganRPC-styleinterface,buttheexistenceofLupinereducedthepossibilityofgettingthiswrong.Isageneral-purposeRPClessefficientthanaprotocolthatisspecializedtothetaskathand?Notnecessarily.BirrellandNelsontakeadvantageoftheassumptionthatRPCisthestandardmodeofcommunicationbyoptimizingthepathofaremotecallandreturnthroughthelayersofcommunicationsoftware.Itwouldnotbefeasibletooptimizemorethanafewprotocolsinthisway,soitfollowsthattheprocessoroverheadforanRPCcanbelessthanforthemorespecializedprotocol.Afternormalizingfortheeffectsofusingdifferentprocessors,CedarRPCisaboutfourtimesfasterthanXDFSinmakingasimpleremoteprocedurecall.Withsomespecializedmicrocodeorhardware,thegeneral-purposeRPCcanstillbespeededupbyafactorofthreeormore.5.DesignAnAlpinefilesystemexportsfourpublicinterfaces:AlpineTransaction,AlpineVolume,AlpineFile,andAlpineOwner.ThemosteffectivewayofdescribingAlpine'sdesignisintermsoftheseinterfaces.InmostrespectsthedescriptionsbelowmatchtheCedarinterfacesactuallyexportedbyAlpine.Wehavechosentoomitsomefeaturesoftheactualinterfacesthatareunimplemented,orareimplementedbuthavenotbeenexercisedbyanyclient.OurnotationforproceduredeclarationsisProcName[arg1,arg2,...,argN]>[result1,result2,...,resultM]!exception1,exception2,exceptionK.Normallyanargumentorresultconsistsofasimplename;whenthetypefortheargumentorresultisnotobvious,thenameisfollowedby":"andthetype.Anexceptionisanameoptionallytg/ v_/ ~."% )+x-0B3" :; BVD\ Zm*j!"')/*0:?FSX < x#.'*S 2W5|7<>? V]  3#^$&(,Ux0gV]V]1Zv4V]V]5z8b;=>ApG0T( n>3X'x#T(T(#%vT(+P-259]<{AFQ   "%&,2 38? @AFO 4 $0* .1 8S;>AEM Gy` >"y',15r qDKW  $ ( &h),x139=?.CFiI" B=\" *O/=158C>}@\EF H"'q)0+05);<0>H@CED  Cl %(+?-2% :*>DB oO ;%')8.137;g BEJ@P M "$';+068<A(F> - + "$)j.1 79H=@{;m C^!o&* +G035 <=@AC(D9 i )!p$V*,`. 58;=4?E7~   !P$')+036:@)BG%5J !$&+-3V7 :P;>[DnF=3 "'*4,&/2469<>dA 0  o"0&(\,1 8<@iAE. CM !&)*1/4q7;] B0,x  o0 :#&"(*024599%:>h@,w%M  v"mDM:9#'+ 2?N   (" %t+-/ 6S;@ACNG% 5 dm5 "&*-1% 7H@G y_< l&(*r-,/3~5< =z>Bh  TVm$7TheAlpinefilesystem11followedby"{",thenalistofthepossibleerrorcodesfortheexception,andthen"}".5.1CedarRPCbackgroundTheGrapevinesystem[Birrelletal,1982]providesanamespaceforusersofthePupinternet.AGrapevinenameforanindividual,suchas"Schroeder.pa",orforagroup,suchas"CSL^.pa",iscalledanRName.Cedar,andinparticulartheCedarRPCmachinery,usesRNamestonameindividualsandgroups.ACedarinterfaceisessentiallyarecordtypewhosenamedcomponentsareprocedures.Aninterfaceinstanceisarecordvaluecontainingnamedprocedurevalues.SotoobtainthevalueofprocedurePininterfaceinstanceIonewritesI.P,andtoapplythisproceduretoparametersargsonewritesI.P[args].Normally,aCedarprogrammodulegetsaninterfaceinstancebybeinglinkedtogetherwithanotherprogrammodulethatproducesthevalue.TheCedarRPCsystemallowsaclientprogramononemachinetoobtainaninterfaceinstanceonanothermachine,oftenaserver.Tomakethishappen,theserverfirstcallstheRPCsystemtodeclarethatitsinterfaceinstanceisavailabletoremoteclients.Thisgivestheinterfaceinstanceaname(anRName),whichisgenerallyjusttheserver'sname.Forexample,aninstanceofanAlpineinterfaceisnamedbyanRNameinthe"alpine"registry,suchas"Luther.alpine".AclientprogramthencallstheRPCsystem,specifyingtheboththeinterface(typeofservice)andinstancename(server)desired.Theclientprogramcanmakecallsthroughthisinterfaceinstanceusingthesamesyntaxasforlocalcalls.Sointhisstyleofcommunicationtheidentityoftheserverisimplicitintheinterfaceinstance,andisnotspecifiedasaparametertoeachprocedure.AclientmustcalltheRPCsystemtoestablishconversationwithaserverbeforeitcanmakeauthenticatedcallstotheserver.Theconversationembodiestheauthenticatedidentitiesofboththeclientandtheserver,andthesecuritylevel(encryptedorunencrypted)oftheircommunication.Byconvention,aconversationisthefirstparametertoallserverprocedures.InourdescriptionsofAlpinepublicproceduresbelowweshallomittheconversationparameter.5.2AlpineTransactioninterfaceTheAlpineTransactioninterfacecontainsproceduresforthecreationandmanipulationoftransactions.AllAlpineproceduresthatmanipulatedatarequireatransaction.TherearetwodistinctservicesbehindtheAlpineTransactioninterface:thetransactioncoordinatorandthetransactionworker.ThecoordinatormanufacturestransactionIDsandplaystheroleofmasterintwo-phasecommit.Theworkerperformsdatamanipulationunderatransactionandplaystheroleofslaveintwo-phasecommit.Ideallythislevelofdetailwouldbehiddenfromclients,buttodothisrequiresthataworkerbeabletocommunicatewithacoordinatorofatransaction,giventhetransactionID.WewerenotwillingtoimplementthisaspartofAlpine,soclientsofmulti-servertransactionsmustdomorework;seeCreateWorkerbelow.vg"]%5),%tgFv_' PL K!d&*-0 2 9 ;>yY  G vV\mHx!6V\V\!"v#V\V\$(g-/%268@CeT( 9 "%'13o56;3>e@ GsQ x QQv|QQR! (J*/82 :=QC5EO iMmxUMMvM "<#'+*/z4" ;>e FxKV KvKV _! (Q,38:<@CfG%I! xAI!vI!8x I!vI!!$x(I!I!)7v*vI!I!+e.//36=> xEI!I!FvF WxYFFvyFF^ $*./.139>@DD 'Z~%$='#-/4F77;g>CoGB y)s!/%'~-1249?CCDz@O  j8 [#I&n(,V027:c ^#.%+"0g15@7=AB; SO"$*"+-2c89> @BG09  Uz!'),225;8.:q=Bg 7~ NZ#&`+/t4v:"<@FS5I Ya-%(+ .24h69=?AaCG%3 ` $&g+t-$/5-:=>ArG00 W7 .mu $&px,'.., v.4788~<ABE*,w $+* " *03@ ; ACJF*C iy"&A -. 7@8<: F( < @ #*n,D.[2 :<?h G%% 1l s!$(*} 2v y [  Rvmg#c) 0y3 5;Z>h G% Z !$ +.34 mFp $'42 8w: A r  2! ( 1* 8M;=AD2G%= 2 %j+>.: 6:; BEV ~#(^*.9/379>fAF]  _kc7f "%& /12Q3 :<= E*  L$%,t.03Z49;h?A3 k ,- $"w +b TVm$k12AtransactionIDcontainsenoughunpredictablebitssothatitisextremelydifficulttoforge,andcanbetreatedasacapability.AnyclientthatknowsthetransactionIDmayparticipateinthetransaction.Itisusefulforaserveradministratortobeabletobypassaccesscontrolchecksinsomesituations,whileobeyingtheminnormalsituations.Weallowanadministratortoexplicitly"enable"aspecifictransactionforaccesscontrolbypassing.Create[createLocalWorker:BOOLEAN]>[transID]!OperationFailed{busy};Calltocoordinator;requeststhecoordinatortocreateanewtransaction.IfcreateLocalWorker,thecoordinatorcallsCreateWorker[transID,RName-of-this-server].RaisesOperationFailed[busy]iftheserverisoverloaded.CreateWorker[transID,coordinator:RName]!Unknown{coordinator,transID};Calltoworker;informstheworkerthattransactiontransIDisbeingcoordinatedbytheAlpineinstancecoordinator.RaisesUnknown[coordinator]iftheworkercannotcommunicatewithcoordinator,andUnknown[transID]iftransIDisunknowntocoordinator.Ifthisprocedurereturnswithoutanexception,theworkeriswillingtoperformAlpinedatamanipulationproceduresusingthistransaction.Finish[transID,requestedOutcome:{abort,commit},continue:BOOLEAN]>[outcome:{abort,commit,unknown},newTransID];Calltocoordinator;requeststhecoordinatortocompletethetransaction.WhenaclientusingatransactionhascompleteditscallstotheAlpinedatamanipulationprocedures,itcallswithrequestedOutcome=committocommitthetransaction.Togiveuponatransactionandundoitseffects,aclientcallswithrequestedOutcome=abort.Ifthetransactionhasalreadycommittedoraborted,thisproceduresimplyreturnstheoutcome,whichisunknownifthetransactionhasbeenfinishedformorethanafewminutes.Acallwithcontinue=TRUEcommitstheeffectsofatransaction,thencreatesandreturnsanewtransactionthatholdsthesamedatastate(locks,openfiles,andsoforth)astheprevioustransaction.SystemRcallsthisasavepoint[Grayetal,1981].Thisfeatureencouragesaclientthatismakingmanyupdatestocommitperiodically,wheneverithasmadeaconsistentsetofchanges.AssertAlpineWheel[transID,enable:BOOLEAN]!OperationFailed{grapevineNotResponding,notAlpineWheel},Unknown{transID};Calltoworker.Whencalledwithenable=TRUE,causessubsequentAlpineprocedurecallsforthis(conversation,transID)pairtopassaccesscontrolcheckswithoutactuallyperformingthechecks;raisesOperationFailed[notAlpineWheel]ifthecallerisnotamemberoftheAlpineWheelsgroupforthisserver.Whencalledwithenable=FALSE,causesnormalaccesscontrolcheckingtoresumeforthis(conversation,transID)pair.tg/ v_/m_/ 2_/y$ ,/1p4\57\=C&D\ f;i !$(W+(/o1 8:> DFZ Xm ,7% $y& '*,F049=c>Bg V] TQ %4'+Q-5 57? =BCT) #yQ! zQ!-{Q!Q!z$xQ!{Q!%Ez'VQ!Q!'N Lj B!# +Y-1 235! <xJzJJ &~x)JJ*z7JJ8xDJzJEHOxHOHOzHO"P#&*+ yEG zEGy $QC7 @j %(s x/o@@/z@459 AKCG>&xt>> z!>>"{x&>>'z>4t585<Bh.fJt p%'n*~,,.36 >~ E,2x,2,2O!#z,2(*U/U1 9;>@B) T$k%)U,dx/~))0:<z?))@Bs' %',/6 :|?/A%x%%z%V &)',147:;>#`Zx#`#`w|\#`#`z#`"').7/1 8n;@BG!, Y!#m&)- 1o48(:<@B=0 "$S'b*x+-+.z1x5~67 z8!8=@ j %).0O5O =CPDa y z6{$$z)R +7= j!x%%)S|+8+z.[/73q :? E xJz"#&(d+]/k48= 2x"#z78i:>}?B^ ' #' )F+048x; <z @7{B BzE L"W().03i <3A jTVm$qTheAlpinefilesystem13RaisesUnknown[transID]iftransIDisnotknowntotheworker.ThismightbebecausetheclienthasnotcalledCreateWorker,orbecausethetransactionisalreadyfinished.5.3AlpineVolumeinterfaceAvolumeisanabstractionofaphysicaldiskvolume.Thereareseveralreasonsforhavingavolumeabstraction.Ifavolumecorrespondstoadiskarm,thenclientshavetheabilitytoimproveperformancebydistributingthemost-frequentlyaccessedfilesacrossseveraldiskarms.Avolumemayalsobetheunitofscavenging,solimitingthesizeofvolumessetsanboundsthetimetorestartifasinglevolumeneedstobescavenged.Alpinedoesnothaveanyambitionsofitsownforvolumes;itjustuseswhatevervolumestructureisprovidedbytheunderlyingsimplefilesystem.AlpinedoesassumethatvolumeIDsaregloballyunique.Aserveroftencontainsseveralvolumesthatareequivalentfromthepointofviewofitsusers.Inparticular,ausermaynotcarewhichvolumehecreatesafileon.Forthisreason,anAlpinefilesystem'svolumesarepartitionedintooneormorevolumegroups.Agroupcontainsoneormorevolumes,andeveryvolumebelongstoexactlyonegroup.Diskspacequotasforownersaremaintainedforvolumegroupsratherthanindividualvolumes;seetheAlpineOwnerinterfacebelow.Whencreatingafileaclientmayspecifyavolumegroup,ratherthanaspecificvolume.Alpinethenselectssomevolumeinthegroupandcreatesthefilethere;seeAlpineFile.Createbelow.AnyprocedurethattakesantransIDparameterraisestheexceptionUnknown[transID]ifthetransIDisnotknowntotheworker.ThismightbebecausetheclienthasnotcalledAlpineTransaction.CreateWorker,orbecausethetransactionisalreadyfinished.Weshallnotmentionthisexceptionintheindividualproceduredescriptionsforanyoftheproceduresinthisorthenexttwosections.GetNextGroup[transID,previousVolumeGroupID]>[volumeGroupID]!Unknown{volumeGroupID};Statelessenumeratorfortheon-linevolumegroupsofthisAlpineinstance.CallingwithpreviousGroup=nullVolumeGroupIDstartsanenumeration,andvolumeGroupID=nullVolumeGroupIDisreturnedattheendofanenumeration.GetGroup[transID,volumeGroupID]>[volumes:LISTOFVolumeID]!Unknown{volumeGroupID};Returnsthelistofvolumesbelongingtothespecifiedvolumegroup.5.4AlpineFileinterfaceAfileisasetofpropertyvaluesandasequenceof512bytepages,indexedfromzero.Eachfileiscontainedinasinglevolume.AfileisnamedbyafileIDthatisuniquewithinthecontainingvolume.AUniversalFileisaglobally-uniquefilename:a[volumeID,fileID]pair.vg"]%5),%tgFz_,x_,_,z_, x!_,_,"Zz_,'(p*/j13x8<@ A\5 (*/2* 9&:?eyWy  vT-mxT-T-vT-DI Z!("g'*047:;@C$GQ  g ')B*j-V037;/=ACqO  >)/@2?6\:=BWCM gM|* !h#!(7*--.4?68=?CDK[  A ',/26 8?kAYChFI' &$)+h1X3s5 =AD F 1b*"$*Dm!'),E 26e8,AlC*E B  u   i$q)U+?/03G68;_@ AFu@T  &#%'x+\@T@T+0v3@T@T5x7;4@CpEK> #W%T*?-926G:K>AF; T"W%r +146c >Dz9 0u=!7%'2,60489Y>^DX7 A#&Z*-@/35A5Mm-x 5M5M!0v%5M5M&,0r2x9@5M5M:Tv5MEFx3 v3VQVk ';*/l17:>AD0  !&( /15;>ACp. P: "% -A/2&36E =O?AClE,| Wy)s z)s{)s- z/)s)s/ '>7% S !N&*/p1)38P=Bx" hz"'+- 5x8""9. B z 3$:%(2*,. y z2 {$z&':{-!-0 z2:b7.e[ ')(+705y  vcmx ccwvcl L"%&,.1_4~8=AmEk. `9S.!#O%'+z-e.0257 ;?B% p '*V./579 Ex\ v\\xK\\v \\x!\\"G v(\\x)\\*v/Z\\x00\\0v3\\x4{\\4 v=\\x=\\?vH\Z xcZZ vZZXm0W"%*/Q247]<@ FVT }0,p(#)+T mxOT T vT >] $O&A(-/`0467<>CQ  ._+ $x'QQ'+#v0$QQ12 9  .h; /%)/0E49;x>'>>>B7FGvH>; J QL"G$&+.2q486:>A:B9 kJ7umKDc!$b(-00 7 =?|D5A H|:"4(.1O5678:@Bg 3 m0h"7(d-0 57>JCETFu0  *4x!00Fv00 $'4*l.?13d59/>n@:BE. [!%u) -=13x9!>;?BP,o iH3l"?%'d / 7%94=?ClE8Fu*;  sM!$'*.a 5 <>vAEK(  A&$&B(*d+.4B68< %m *K #ax&/%%&v%)e+1 2@4 <@^E@#  ~}q ;&2+p01 78<<A xCW##D!h v Z!h!h4Mu aj!!$P'(+-/46:<>sDE4 AO &t',05)78|<?LCD S"&,. 5G6:<@F G ."&1'\+,1_46k< CCEJFu Rr :!%['*$,abmE L %#l')H+/f25:<?A - =w &'+s.7038:4<?C.F' \/tf!l ' .W/2x40 ;?N@F 6` p $ m  !%)+[0 7;<?C9 [   #> ),e/5b8<+ABnEG TTVm$TheAlpinefilesystem15file,thefilepropertiesarelockedasaunit.Insteadofhidingthesefactsfromclients,weallowclientstoinfluencethelocking.Thechoicebetweenwhole-filelocking(thedefault)andpagelockingismadebytheclientatthetimeafileisopened.Lockingisalsoperformedimplicitlyasasideeffectofreadandwriteoperations.Areadaccesslockstheobjectinreadmode(thedefault)orwritemode,whileamodifyaccesslockstheobjectinwritemode.Aclientwhoissatisfiedwiththedefaultbehaviorneednotbeconcernedfurtherwithlocks.Butmoreambitiousclientsmayspecifypagegranularitylocking,mayexplicitlysetlocksinordertoreserveresources,andmayexplicitlyreleasereadlocksbeforetheendofatransactiontoreduceconflicts.AnumberoftheAlpineprocedurestakealockOptionparameter,whichisusedtospecifythedesiredlockmodeandtoindicatewhatAlpineshoulddoincaseofaconflictintryingtosetthelock.IfthereisaconflictandlockOption.ifConflictisfail,theprocedureraisestheexceptionLockFailed.IflockOption.ifConflictiswait,theproceduredoesnotreturnuntileitherthelockissetorthetransactionisaborted.Alpineplacesfewrestrictionsuponitsclientswhenitcomestoconcurrentoperationswithinasingletransaction.Locksdonotsynchronizeconcurrentprocedurecallsforthesametransaction;thisistheclient'sresponsibility.Itisperfectlyoktohave,say,7ReadPagesand2WritePagescallsinprogressatthesametimeforonetransaction.Itisprobablynotusefulforareadtobeconcurrentwithawriteofthesamepage;theresultofthereadwillbeeithertheoldvalueorthenewvalueofthepage,butthereadercannottellwhich.ArequesttocommitatransactionwhileanotherAlpineoperationisinprogressforthetransactionisaclienterrorandabortsthetransaction.AnyprocedurethattakesanownerorvolumeIDparameterraisestheexceptionUnknown{owner,volumeID}ifthecorrespondingargumentdoesnotidentifyanexistingobject.AnyprocedureraisestheexceptionStaticallyInvalidifitdetectsanoutofrangeargumentvaluebysomestatictest,forinstanceaninvalidvaluefromanenumeratedtype.AnyprocedurewithalockOptionparameterraisestheexceptionLockFailediflockOption.ifConflictisfailandthelockcannotbeset.Weshallnotmentiontheseexceptionsintheindividualproceduredescriptionsinthissectionorthenext.Create[transID,volumeID,owner:RName,initialPageCount,referencePattern:{random,sequential}]>[openFileID,universalFile]!AccessFailed{ownerCreate,spaceQuota},OperationFailed{insufficientSpace}.CreatesandopensthenewfileuniversalFilewithinitialPageCountpagesundertransID.volumeIDmaybeeitheraspecificvolumeIDoravolumegroupID;inthelattercase,theserverchoosesamongthevolumesofthegroup.Theclientmustbeamemberofowner'screateaccesslist,andtheallocationmustnotexceedowner'squotaorthecapacityoftheserver.Allfilepropertiesaresettodefaultvalues:byteLengthandhighWaterMark:0,createdTime:now,readAccess:"World",modifyAccess:"Owner"plusowner'screateaccesslist,owner:owner,andtextName:emptystring.Ifthecallissuccessful,thenewfileislockedinwritemode,andtheclienthasread-writevg"]%5),%tgFv_/  9!8# $V([-R/.37M:>+BE5\ ZmV+ !&)u.1o49;'>ACuGFX &f/"#&-e 35g69=?YBEaV] #0!%';*L.067;0?UCD!T) H#%j)4,A-3 608=JCFiQ  N* #K&-M149X< CO  a /!& -303" 9$=@DM  { O KWm>o %(x)OKWKW)vKW0[ 7A;[<@AFI" zD!D$)L-/1467<>zBDOFF Bx FF!8v'PFxF' vF-x/FF0 v1FF25A<@BxD vDDxDDvvDxD vD!x#?DD$&v%DD&|(/J2p48<;@BrE`FB  o 6@Pm! $r&X*.g/45 < CeG>   (4 /558;V=Ai ; L!v"(*,9/2x3;;4v;:=]x>;;?v;E9  F$p! )\*,1468;:d;z>@A 7  YN!%_'$),/o1l5e7:G=?B:E55J  t"$)+02[78 ?C3 1[u!# *{+-04B6;=} 0mUnx00 Uv0#x%+00%v+^00,%15h7x=00>v0CxD00E=vH0x. vv..I 4%S(x*/16;>E,x xg,x,xDv,x !&&()*,0]6:W@ CE%   ! (a. 6z8(:?fA*Cy" z"-#(3>~ S j  " *z45of x#55# z5+x.)55.z58 & '*#.}1U58}:n;AxBCozF4FG ] &*,zx11z4v459;}=C*Dc/! Uq! %x*p//+ z/1~x46//4 z=//>x@>//@ zG_//xzSQx!Y"o z)*0x23z6q67;?Bxx z x za _" P: U #& 'w+x- .rz 057:.=@c  TVm$16accesstothefileusingopenFileID.AlpineusesthereferencePatternparametertocontrolread-aheadandbufferreplacementstrategiesforthefile.Open[transID,universalFile,access:{readOnly,readWrite},lock,referencePattern:{random,sequential}]>[openFileID,fileID]!AccessFailed{fileRead,fileModify}.OpensanexistingfileuniversalFileforaccessundertransID.Thefile'saccesslistsarecheckedtoensurethattheclientisallowedtousethefileasspecifiedbyaccess.Ifaccess=readOnly,theclientisrestrictedtoreadoperationsonopenFileID,eveniftheclientpassesthechecksforread-writeaccess.Theentirefileislockedinlock.mode;lock.ifConflictisalsorememberedandisusedwhenperformingcertainfileactions(e.g.,Delete)thatdonotallowaLockModespecification.AlpineusesthereferencePatternparametertocontrolread-aheadandbufferreplacementstrategiesforthefile.AfileIDconsistsofboththefileidentifier,whichispermanentlyunique,andsomelocationinformation,whichistreatedasahint[Lampson,1983]andissubjecttochangeduringthelifetimeofthefile.OpenreturnsafileIDwhoselocationhintmaydifferfromthehintinthefileIDthatiscontainedinuniversalFile.WhenthefileIDchanges,theclientshouldstoreitinitsowndataordirectorystructuressothatsubsequentOpencallswillbemoreefficient.Close[openFileID].BreakstheassociationbetweenopenFileIDanditsfile.ThenumberofsimultaneousopenfilespermittedononeAlpinefilesystemislargebutnotunlimited;clientsareencouragedtoclosefilesthatarenolongerneeded,particularlywhenreferencingmanyfilesunderonetransaction.Closingafiledoesnotterminatethetransactionanddoesnotreleaseanylocksonthefile;nordoesitrestricttheclient'sabilitytolaterre-openthefileunderthesametransaction.Delete[openFileID]!AccessFailed{handleReadWrite};Firstlockstheentirefileinwritemode;thendeletesthefile.openFileIDmustallowread-writeaccess.DeletemakesopenFileIDinvalidforsubsequentoperations.Theowner'sallocationiscreditedwiththereleasedpageswhenthetransactioncommits.ReadPages[openFileID,pageRun,resultPageBuffer,lockOption]!OperationFailed{nonexistentFilePage}.ReadsdatafromthepagesdescribedbypageRunofthefileassociatedwithopenFileID,andputsitcontiguouslyintoclientmemoryintheblockdescribedbyresultPageBuffer.AResultPageBufferconsistsofapointerintovirtualmemoryandawordcount;Lupineunderstandsthatthecontentsoftheblock(notthepointerandcount)istherealvalue,andthatthisvalueisreallyaprocedureresult(notanargument).tg/ z_,]%x_,_,z%u_,_,&+[.Tx0_,_,18z_,:ALB\ j &[ ,N.0yY zYr8 $F +W 26(@W {W8zIWW nU   SP xSPSP> zSP%s'+x/SPSP01z4WSPSP58;?BQ!0$&\+r- /14^6 ;x=QQ>tzAMQQBxD/QQDNzNN H &G'+ 1x3NN4tz:jNN;F>?BML# $T)=,02j38;x9LL:Mz?LLxJ~zJ~q %(e)- 0 7CHJNU s!( 1W58x;5HJHJ;zF# $'M+| 3> 91;n=CZ"@$ */0n 8g=h@A !#3')*-4P7:<@Bs?wq{4 x#?w?w$z?w'z,--W/16;M>1A5E=C[!Q")x*=C=C+s z2$=C=C379D;a9=!$'!(. 469 x@;;Az;DT8L= y5 z5 3H x"33#z3*&,.1x4Q9};6 C|1h#%{)+b.1J3 :y>A /3Or$)1 0z4/ ;a?,BF, xw! $;&,/9 658<>C*$f!!"w' )i.2?37<)>@D( y% z%! #X !#F $r(+0y2x6!#!#6z!#=H@ .x+z Sx$%<z+0G2 9 A7 V"%(-k1647K >Fy z #- | G] &x(GG)^zG.W02o4 ;Ex>`GG?zEGGE #)*-06x89~zBxZXz!"#(+/5f89G<A  N{"$'*-047;=M?Bc tX&q!")T-0 1  TVm$PTheAlpinefilesystem17WritePages[openFileID,pageRun,valuePageBuffer,lockOption]!AccessFailed{handleReadWrite},OperationFailed{nonexistentFilePage}.WritesdatafromclientmemoryintheblockdescribedbyvaluePageBuffertothepagesdescribedbypageRunofthefileassociatedwithopenFileID,whichmustallowread-writeaccess.AValuePageBufferhasthesamerepresentationasaResultPageBuffer,butLupineunderstandsthatinthiscasethevalueisreallyaprocedureargument(notaresult).LockPages[openFileID,pageRun,lockOption].Explicitlysetslocksonthespecifiedpagesofthefile.UnlockPages[openFileID,pageRun].Ifthespecifiedpagesofthefilearelockedinreadmode,thenremovesthoselocks.Itistheclient'sresponsibilitytoassureconsistencyofanysubsequentoperationswhosebehaviordependsonthedatathatwasreadunderthoselocks.LockrequestsarecountedandthelockisnotremoveduntiloneUnlockPageshasbeendoneforeachLockPagesorReadPagespreviouslyperformedonthesamepages.Attemptstoremovenonexistentlocksorlocksotherthanreadareignoredwithouterrorindication.GetSize[openFileID,lockOption]>[size:PageCount].Returnsthefile'ssize,aftersettingalockonthesizeproperty.SetSize[openFileID,newPageCount,lockOption]!AccessFailed{handleReadWrite,spaceQuota},OperationFailed{insufficientSpace}.Setsawritelockonthefileproperites,thenchangesthefile'ssizetonewPageCount.Decreasingafile'ssizelockstheentirefileinwritemode.openFileIDmustallowread-writeaccess;theclientneednotbeamemberoftheowner'screateaccesslist.Ifthefilesizeisbeingincreased,theowner'sallocationischargedforthenewpagesimmediately,butifthesizeisbeingdecreased,theowner'sallocationiscreditedwhenthetransactioncommits.ReadProperties[openFileID,desiredProperties:PropertySet,lockOption]>[properties:LISTOFPropertyValuePair];ThetypePropertySetrepresentsasetoffileproperties,forexample{createdTime,textName}.ThetypePropertyValuePairrepresentsaproperty,pairedwithalegalvalueforthatproperty,forexample[createdTime,February12,198411:46:52amPST]or[textName,"/Luther.alpine/MBrown.pa/Walnut.segment"].ReadPropertiesreturnsalistofthepropertyvaluesspecifiedbydesiredProperties,orderedasinthedeclarationofProperty.WriteProperties[openFileID,properties:LISTOFPropertyValuePair,lockOption]!AccessFailed{handleReadWrite,ownerCreate,spaceQuota},OperationFailed{insufficientSpace,unwritableProperty};Writesthesuppliedproperties,whichmaybeorderedarbitrarily.vg"]%5),%tgFy_, z_,% I#. \ %/Z38_#%z'+1x3ZZ4[ zZ=?AXxXXwzXp )"$ +^x.yXX/)z5XX5: =rA VZT%Z^ $; -2.0 ;I=Q Nk"Z$(c)-.5E;o>^?yN zN # L  {&7*+.yI zI 0GwPk6!N#& *qx,GwGw,zGw/#3Q6w;?CETEC !% -.1m 8 ?DCQ &#+%(+/3a7;7@B@X"A%(4 0c2659;?E> 3$&)],17t9#> E`?C+x#U# +137 <>zBx *z3x45 z>TCD1Foy"x$yy%1z.ayy/=4^6 7: A,xByyCzGyyyp zp  {&pp'p)zp+7 < % -i 5 E 3" "'*+1  TVm$18TowritethebyteLength,createdTime,highWaterMark,andtextNamepropertiesrequiresthattheopenFileIDhaveaccess=readWrite.TowritereadAccessormodifyAccessrequiresthattheclientbethefile'sowneroramemberoftheownercreatelistforthefile'sowner,butdoesNOTrequirethatopenFileIDhaveaccess=readWrite.Towriteownerrequiresthatboththeaboveconditionsbesatisfied,andadditionallyrequiresthattheclientbeamemberoftheownercreatelistforthenewowner;thediskspaceoccupiedbythefileiscreditedtotheoldownerandchargedtothenewone.Ifthereisinsufficientspaceintheleaderpagetorepresentthenewproperties,theexceptionOperationFailed[insufficientSpace]israised.Ifmultiplepropertiesarewrittenbyonecallandanerroroccurs,someofthepropertiesmayneverthelesshavebeenwrittensuccessfully.5.5AlpineOwnerinterfaceTheownerdatabase,adatabaseindexedbythesetofvalidownernames,isassociatedwitheachvolumegroup.Thesetofentriesinanownerdatabaserecordisfixed,andisdescribedbytheenumeratedtypeOwnerProperty,withelementsspaceInUse,quota,rootFile,createAccessList,andmodifyAccessList.Anowner'sspaceInUseisthetotalnumberofpagesinallownedfiles,plusafixedoverheadchargeperownedfile.HencespaceInUseischangedasasideeffectofAlpineFile.Create,Delete,SetSize,andWriteProperties(writingtheowner)calls.Anowner'squotaisanupperboundonspaceInUse,enforcedbyAlpineFile.CreateandSetSizecalls.Creationoffilesforanownerisgovernedbytheownercreateaccesslist,asdescribedabove.TheownerrootfileisaUniversalFilethatcanbereadandwrittenbyclients.Itisintendedforusebyadirectorysystem.Thecreationoffilesforanownerisgovernedbytheownercreateaccesslist,asdescribedintheprevioussection.Modificationoftheownercreateaccesslistiscontrolledbytheownermodifyaccesslist.Thisallowsforalimitedamountofdecentralizedadministrationoftheownerdatabase.Alpineallowsotherupdatestotheownerdatabase,suchascreatingownersandchangingspacequotas,onlyfortransactionswithwheelstatusenabled.Weomittheproceduresthatperformtheseadministrativeupdates.ReadProperties[transID,volumeGroupID,owner:RName,desiredProperties:OwnerPropertySet]>[properties:LISTOFOwnerPropertyValuePair];ReadsthepropertiesspecifiedbydesiredProperties,orderedasinthedeclarationofOwnerProperty.WriteProperties[transID,volumeGroupID,owner:RName,properties:LISTOFOwnerPropertyValuePair]!AccessFailed{alpineWheel,ownerEntry},OperationFailed{ownerRecordFull,tg/ z_,rx_,_,z\_,_,x9_,_, z&Z_,_,x'7_,_,' z0_,_,1x4H_,_,4z_,: @\ox\\z\x ?\\ $M&2z,\\-f/x3 \\3z\9x;\\< zZ #,&r*,c-247;A?DACXl!&x)WXX*zX0x3XX4x79z?XX@CxVZzVZ"R&S ,. 47D >DT&I!#a'+-0 2l5Z:<`?NCQe"-$(+|02W47OPE m!""%/)R,.G4E69 @bMxMM!zM+,13T8 ?DAFKKSL"&!'*9 03 ;k>BI yC  #v@Tmx9@T@T'v(@T@T!&(+-%.2-6N:<> BE> &!#o%)/459<{> D]F; c $x);;*{v0;;x1;;2Vv4;;x5;;6qv:;;x;;;<"vE;;F'x9 v997mx77{v77!/$j)+|/\1 3'7; >?XB5N '9 &q'-x/<0|3k7Mx95N5N:vCX5N5NxDJ5N5NE^vH5Nx3 v33x33[ v3#:x%33&yv)>33*k.16x6p337 v3:a;>BNF0 x00v0&x)00*v0.3E9+;%>T@CGs. x.."v#..$&J,u,{m@xh,{,{<v,{x,{,{) v,{%X(!*,/2Y78>?@F*G  F(m[$!%+-x0<((04L8[<v>:((?,@G0% ' !]#%)-145 <>x@m%%ADl# vt##Y"5'@( 1V :n<'>B!tm!p#'-127<?PE)? g} 4 L$@(.0361 =5@EU y zW ',2 {z {"#%z(Q "x$%0z.`/<4]6 7: A+xd z{ddy\ z\ (]-2 {9q\\:*\@ DT% N6 $'e)-269<Q`xQQz,QQ-g3d5:W?BEOlx"6OO"z&OOMTU" *".P2]59>cDIKRkJ")&(j*Z.247xIz$II%)+@-}/3wA  v>m  % ') 157:=_AE BDz5 QI !&,h0548;J>D?DM3 tbax"%%* .X24Z8:H?BD,1k  9 !&L(|*- 147;;>CGs/7  es![+B05s8;??@C1F'- d #W% /14I AB ( G"&* 14\7_:>D&emm$v ')H*.L268V9CcGg$0 X@#&)+.. !m  "%+048G<CZG rk#$(*1@45d9m ~ $ +1x78~9v<)Au ] |  ')/337: D) B #i ^!$P),./ 69K?ACo M "(+-247:?GDF  m1 * $' 1k37y9>ND"W &oDC$'+(-238;>@Fu" S" )~,58 @C G = TVm$20Alpinedeviatesfromthepureredologschemeinthefollowingimportantrespect:actionsthatallocatediskspace,suchascreate-fileorextend-file,arenotdeferreduntilaftertransactioncommit.Instead,Alpinewritesalogrecordthatissufficienttoundotheaction,thenperformsit.Shouldthetransactionabort,theundoisperformed.Onereasonthatwedonotdeferdiskallocationsisthatwiththeunderlyingfilesystemsweexpecttouse,thereisnopracticalwaytocommittoadiskallocationwithoutactuallydoingit.Andunlikeafilepagewrite,verylittleinformationneedbewrittenintotheloginordertomakeadiskallocationundoable.Anotherdeviationfromthepureredologschemeisthefilehighwatermarkoptimization.Pagewritespastthehighwatermarkaremadedirectlytothefileandnotlogged,andthehighwatermarkisadvanced.Allfileupdatesmustbeforcedtodiskbeforeatransactioncommits.Ifatransactionabortsthehighwatermarkmustnotbeadvanced.OwnerDBimplementstheownerdatabaseandaccesscontrols.TheownerdatabaseisrepresentedasanormalAlpinefile;toreadandwritetheownerdatabase,OwnerDBcallsFilethroughtheAlpineFileinterface.Forinstance,whenaclientcallsAlpineFile.Createtocreatea10pagefileforaparticularownerunderatransaction,CreatecallsOwnerDBtoreadtheownerdatabaseunderthistransactionandverifythattheclientisauthorizedtocreatethefileandthatthe10additionalpageswillnotexceedthelimitfortheowner.ToreducecontentionOwnerDBbuildsavolatilerepresentationofthequotaandreleasesthereadlockontheownerdatabasefilepage.Justbeforethetransactioncommits,OwnerDBupdatestheownerdatabaseunderthetransactiontoshow10morepagesinusebytheowner.Hencethetransactionmechanismguaranteestheconsistencyoftheownerdatabase.Theownerdatabasefileisorganizedasanopen-addresshashtablewithonerecordperpage;whenitfillsup,theadministratorcallsaproceduretoexpandandreorganizetheownerdatabase,againusingthetransactionfacilitytocovertheupdate.OwnerDBtestsmembershipinaccesscontrollistsbycallingGrapevine.Theefficiencyofthisismadeacceptablebycachingtheresultsofthesecalls.InordertotrackGrapevineupdatesitsufficestodiscardoldcacheentries,sinceGrapevine'sownconsistencyguaranteesarenotstrong.7.ExperienceandevaluationByearly1983,wehadcodedandstartedtotestanAlpineimplementationthatlackedtwo-copyloggingandincrementalbackup(bothareneededtomeetthegoalofnotlosingdatainadiskfailure),andwaslimitedtoasinglediskvolume,butwasotherwisecomplete.Wedecidedthatitwasmoreimportanttogetsomeexperiencewithwhatwehadimplementedthantoimplementtherestofthedesign.7.1SupportingfacilitiesTomakeAlpineusablefromCedar,threeadditionalcomponentswererequired:adirectorytg/ v_/m= !K$&+-k/5$c(*]-(0249 CDET) +\ W"%*E+. 1n5^8; CvFQ ^7L"#& -OmR"{%',-0I259_< EM Gf "&b+t-?/2A57<?`AEKV sn"&|(-.2!68 ?4EGI" *P #' )+qFm M"T'*X.?46:@/At D  qX #'(). 4):>AFxB vBF !F%&<*x-"BB.vB79=>@D,F@P $B x#@P@P$v@P'*1s36.8<BAF=> [Ep".# *g,02r47:\<> E; T"q(K*/ 6=ByD 9 aa$m&),.1R5; =AD7~ - JH!'/)-37:a ACOF5I U7!F%($ /66 =f? G%3 [ %(D)013 <@?CF30 Su, # +./6j8$=? F. v &{+,0d2,wm !%*-J/L3 ;c>B D}F=*C  ?' #K!&J(++0257;]BIG( Dl8"%s -0 7J >@mBw  ' vmxH N"'s)+-2 ;>Bb  J M$1&+-1368;Z?BDE. k-&""% *q-/5<?wDG ^ag  &*-i/2V :=?F MeyF   v mK!I%) 06 8 ;AC  TVm$5TheAlpinefilesystem21system,animplementationofCedaropenfiles,andauserinterfacetosomeoftheserver'sadministrativefunctions.AdirectorysystemmapsthetextnameforafileintoaUniversalFile.SincewewishtoreplaceIFS,wemusteventuallyimplementahierarchicaldirectorysystemwhosefunctionalityincludesthecommonly-usedIFSfunctions,suchasfileversionnumbers,asasubset.Asatemporaryexpedient,weimplementedaverysimpledirectorysystemthatprovidesaflatnamespacetoeachfileowner.Thesimpledirectorysystemisnotsuitableforstoringalargenumberoffiles,aswouldberequiredofanIFSreplacement,buthasbeensufficienttosupporttheuseofAlpinefordatabaseapplications.ACedaropenfileisanobjectthatimplementsoperationssuchasRead(pagesfromfiletovirtualmemory)andWrite(pagesfromvirtualmemorytofile).InCedar,allbutafewlow-levelclientsoffilesaccessthemviaopenfiles,soimplementingthisabstractionintegratesAlpinewithCedartoaconsiderabledegree.Forinstance,filestreamsareimplementedusingopenfiles,soanyprogramthattakesastreamasinputcanbepassedastreamforanAlpinefile.ACedarusersometimesneedstodealwithanAlpineserverdirectly,aswhencheckingadiskquotaorchangingafileaccesslist.Cedarprovidestheuserwithanexpressioninterpreter,soinprincipleausercanqueryandmanipulateanAlpineserverbymakingcallstothevariousAlpineinterfaces.Thisisinconvenientbecauseofthelargeamountof"boiler-plate"codethatittakestobindtotheserver,createatransaction,andsoforth.Soweimplementedasetofprocedures,analogoustotheadministrativeproceduresexportedfromtheAlpineserver,suchthateachprocedurecallrunsasanewtransaction.This"Alpinecommandspackage"runsoneachuserworkstationasanordinaryAlpineclient,andanyCedaruserisfreetomodifythepackageasheseesfit.Inadditiontothesenewcomponents,theexistingdatabasemanagementsystemwasmodifiedtouseAlpinefilesaswellasXDFSfiles.Andtomakeitsensibleforuserstotryourfilesystem,weimplementedatrivialbackupsystemthatcopiedchangedfilesfromanAlpineservertoanIFSserverduringoffhours.7.2ApplicationsCypress[Cattell,1983]isanentity-relationshipdatabasemanagementsystemthatevolvedfromDBTuples[Brownetal,1981].CypressnowusesonlyAlpinefilestorage.SeveralapplicationsofCypresshavebeenwritten,includingasystemforstoringelectronicmailmessages,ageneral-purposedatabasebrowser,asimpleillustrator,andadatabasecontainingrelationshipsbetweenCedarmodules.Themessagefilingsystem,calledWalnut,isbyfarthemostheavilyusedapplicationofCypressandAlpine.Walnutrepresentsitsdataastwofiles:aWalnutlogfileandaCypressdatabase.TheWalnutlogfilecontainsthemessagesthemselvesandarecordofallupdates,whiletheCypressdatabaseisusedasanindex.TheWalnutlogfilecanbestoredineitheraworkstation'sfilesystemoranAlpinefilesystem.BecauseofthevariousshortcomingsofXDFSdiscussedinSection2,itwasneverpracticaltostoreWalnutlogsanddatabasesonXDFS.Instead,WalnutusedtheCedarworkstation'sPilotfilevg"]%5),%tgFv_/ # [n#'+L.^/3494;<?)A<C\  Zm/ "&(),>/01 9=2?QBzD X Z !# *0X49 AFV] M !#s%*02G3l8l:x;B; T(  7i$)N,%125n97<>ADYQ )!&(Q,.1i68H;=6AaCNO  R/ I! ')|.v03$49>;h@ Mm#xeMMvML">%6 , 368<A DG0KV !$).0@4!6:<?@QCI" %-"&&( 03 : AEF p "y(*/y1 :=A6D{F=D : "y%&+Z,0325"9Bm  !#}&})+0#479;@>DE@P v9_"&,.25;7D > ETG0> hg0 &j(l-1#308+;L= ?~DX; k $&(,s13Q <?gBBCG09 $Y %<(&*.1 3c ;=D?A 7~   %+4.0509z<?EB[5I =]B6 ";'x.c4\7}9<? G03  +!!%9(2),k.256:x<&>@0mO/1 &H(-3 ;@CC.  dsk#"9&);*.05H7;<?AD ,w  2c` <$', 14v79>gB{D0F'*C )[y$  v!xm+E0 9=@\EwD Gx)DDvDDh$'*-2z4:? G% C;"=#T').f 47=> " "D$%+R 1 9?Cm:"()g+W-t/37: BCr a (!$%([+,14#69@:h?F= <]# +-/;357=KA)C As %(*y-.3 489 ADc  o`O m %*&+W1m3'89;=AG0 k  !',114`6: C*Fu TVm$22system[Redelletal,1980],whichprovidedtransactions.Later,WalnutusersweregiventheoptionofstoringtheirfilesonanAlpineserver,andalmostallofthemdid.AlpinegavethemanoticeableperformanceimprovementoverPilot,butthemainreasonforitspopularitywasthatitallowedausertoaccesshisfiledmessagesfromanyCedarworkstation,notjusthispersonalworkstation.Luther,thepublicAlpineserver,hasbeeninservicesinceMarch1983.(LutherpassislocatedinAlpinecounty,California.)SinceJuly1983theAlpinecoderunningonLutherhasnotbeenchangedinasignificantway,andLutherhasaveragedabouttworestartsperweek.About40%oftherestartswereduetohardwareproblemsandamicrocodebug,and10%weretoinstallsoftwarechanges.AllbutafewoftheremainingrestartswerecausedbythreespecificAlpinebugsthathavebeenfixed,orthefixisunderstood.Arestartgenerallytookabouttwominutes;ontwooccasions,restartfailedandthesystemwascold-started(ignoringthestateofthelog).LutheristhefirstserveratPARCtousetheDorado[Clarketal,1981]asitsprocessor.SomeflawsthatareacceptablewhentheDoradoisusedasaworkstationareintolerablewhenitisusedasaserver.OnetwooccasionsLutherhasbeenunavailableformorethanadayduetoproblemswithDoradohardware.Wearenowconsideringaconfigurationwithawarmspareprocessortoreducethisproblem.Alpineusershaveseveralcomplaintswiththesystemthatareunrelatedtothehardware.ThemostoftenheardcomplaintisthatAlpineabortstransactionstoofrequently.ClientsusethefeatureofAlpineTransaction.Finishthatallowsthemtocommitupdatesbutimmediatelycreateanewtransaction,maintainingtheconsistencyoftheirapplicationdatastructuresbynotreleasinglocksonAlpine.Thisworksfinewhenthelocksareonaprivatedatabase,butisabadideawhenthelocksareonashareddatabasebecauseitleadstolockconflictordeadlock.Recallthatextendingafilerequiresawritelockonapageoftheownerdatabase.ThislockisnotreleasedbyAlpineTransaction.Finishwithcontinue=TRUE.Wearenowconsideringwhethertofixthisspecificproblemortoprovideageneralfacilitytoidentifylockrequestsasbeingofshortorlongduration.Therearetwootheraspectsofthetoo-frequenttransactionabortproblem.First,Alpineprovidestheuserwithnowayoffindingoutwhyatransactionhasaborted.Thisisclearlyamistake;itwillnotbehardtologabitmoreinformationaboutthecauseoftransactionabort,andletaclientreadthisinformationfromthelog.Second,applicationslikeWalnutweredevelopedusingPilottransactionsinalocalfilesystem.Thesetransactionsabortedonlyduetospecificrequestorduetoaworkstationcrash.Soapplicationswerenotstructuredwithsmoothrecoveryfromtransactionabortinmind.Thenextgenerationofapplicationswillhidethelow-leveltransactionconceptfromusers.Inspiteofthesedeficiencies,Alpinehassucceededinitsprimarygoal:supportingresearchindatabasemanagementsystemsandapplications.7.3PerformanceWehavedonenoperformancetuningofAlpine;noneofourusershasaskedforit.Weareintg/ v_' 'x_'_'v_'_'qs &T .27;>oB$D\  Z _$'f+-/U26:=A1BQ Z  U#A%(U+0_24 ;h>-ABGX Sa#%) 1368>N VTmUl"%@(*E.296:?BD T  {#$ 3# &&),049x;@TBEQ #  %?'-1u4*8;m?D/G%O 1 &)*1l47M:B=?QCeM Sp$w)(,l026F;$?BEKN     "$2(n.X15d8=?B~ I rM 'n-`/247 FmkH#%['*0/;x3hFF44v6 FF6: ED B >!n&(+K-.@ 58 ?BD(EB|  fez$&* 1X37A:s;>WAB@H 5 R#v *,3 479I=>@G0> (;mt %o(*/2_4:<? F9 d, %p) 13d :?rAD67v x 7v7vv7v3 L$(*/5?8 @.D{E5A   $%) 03 9H;>=CaF3  $$!$~&().47 8w9E@Fu. J\A#%i(]-48l;=AFx,o v,ox,o,o|#J|% ,o,o%v(C,o,o),.F1; 8=?_AaC*; 0$0%*-3F48:x=?B(mR( # * 15<;d>CO%  p!$& ,/n5Q8i9>6?]DF3#  FBj %)|+/1B 8<<1>@BE!i M >4m @"&=,03 ;e=>LAD   !#4(,.t123 ;?WAH    H 5%)G 0P35:P=6@T G% Bg!C (?-V0bmJd %R'.f0!2 7M: AG0- G ``! y  v cm3 !%',014G7:.=@6B]DG0 TVm$TheAlpinefilesystem23thefortunatepositionofrunningthesystemonaDorado,whichisroughly10timesasfastastheAltoforexecutingMesacode.(ThisfactorisnoteasytoevaluatesinceCedarprogramstendtousemore32-bitquantitiesthanAlto/Mesaprogramsdid,andtheDoradohas16-bitdatapaths.)AsimpleMesainstructiontakes125nanoseconds,andaprocedurecallandreturntakes5microseconds.WedesignedAlpinetohavegoodperformanceonslowermachines,buthaveneverrunitonone.OurDoradocomeswith2mbytesofmainstore,theminimumconfiguration,andLutherarbitrarilyuses200kbytesofvirtualmemoryforfilebuffers.Priortowritingthispaper,wehadtworatheroffhandsourcesofperformanceinformation.First,wenoticedthetimetocopylargefilesbetweenaworkstationandAlpine,usingtheCopyprocedureincludedintheAlpinecommandspackage.ThiscopyprocedureusesasingleprocessthatloopscallingAlpineFile.ReadPagesorWritePagesasappropriate,transferring12pagesineachcall.Forlargefiles,copyingproceedsat450kbit/sec.Thisincludesdatatransportovera3mbit/secexperimentalEthernet.Second,wenoticedthestatisticsthatarekeptbytheCypressdatabasemanagementsystem.Cypressmaintainstheaveragetimepercallforseveralinternalprocedures,includingeachAlpineprocedurethatituses.CypressusesAlpineFile.ReadPagesandWritePagestotransferasinglepagepercall.WhencalledfromWalnut,theaveragetimeCypressseesforAlpineFile.ReadPagesisvariesbetween20and40msec,andtheaveragetimeforWritePagesisabout10msec.WhenpreparingthispaperweranthefilesystembenchmarksusedbyMitchellandDionintheircomparisonofXDFSandtheCambridgeFileServer[MitchellandDion,1981].Theirbenchmarkusesasingle256kbytefile.Thefirsttestmeasuresthetimetakenrequiredforanullremoteprocedurecall,andthesecondmeasuresthetimeforanulltransaction.Thethirdtestmeasurestheaveragetimeperreadwhenperforming100randomreadsinasingletransaction,andthefourthtestmeasuresthetimeperwritewhenperforming100randomwritesinasingletransaction.Thefifthtestmeasuresthetimetowritetheentirefilesequentially.Theresults:1.Remotecall,noparameters,noresults:1msec[BirrellandNelson,1983]2.AlpineTransaction.Create;AlpineTransaction.Finish:10msec3.Averageof100randomreads:25msec4.Averageof100randomwrites:8.9msec5.Write256kbytestoexistingfile(writing512bytespercall):4.8secWrite256kbytestoexistingfile(writing2048bytespercall):2.6secWrite256kbytestoexistingfile(writing8192bytespercall):3.2secTest2shouldinvolvenoI/O,butdoesinvolveapotentiallyremotecallfromthecoordinatortotheworker(thecallturnsouttobelocalinthetest),andthiscallisdonefromaseparateprocesssothatmultipleworkerscanbecalledinparallel(thereisonlyoneworkerinthetest).Intests3and4,thegoodrelativeperformanceofrandomwritesversusrandomreadsdemonstratestheadvanatageofconvertingrandomI/Ointosequential(log)I/O.Test5showsthatgiventhesmallpagesusedinAlpine,itisimportanttobeabletosendarunofpagesinasinglecall.Thepeakperformanceof800kbits/secondforsequentialwritingcansurelybeimprovedbysomeworkonvg"]%5),%tgFv_/ c' j"'\)n*04+5:<@jB#DF\ "^&C'*-.47;ADFiZ e C$Y*-0f28:>BGRX  B  (_*, 2p47{;>@ V] B U!& )6+H/68;?BgCET) !"&3),22} ;>=Bs Q :z!!#&5Om "u%^(;,z168 @ M pHh!%l(./d 69>BE*KW LZ (.Z15;>@D I" 4$F& -M/ 6 >6@#CEF LE$%()/28D;fA`DEG0D > yBm! #;&4(+.06; D @P F"$'A).?3l :ADX> .Q%P"H/2 9;z@AE; OT9!$ (,1!36CD9 f }%|(* 23}7^9C7~m!$u&)n. 59;.@CG05I C  #^*-28;?E3  !%P(0+-3691<BDF0 :O9$*-D03 4g7r ?BFS. +!%v ,/B4e89:> F',x  m>}!%2( /2K7J;+<=A *C q!D$'"+-w 58(m% !m#s(<)q,14A9O%m !0(2 #m["$!pm[#E%;moC!$e),&/2057pD!$f),0l26^8pD!$f),0l26^8mQ3I!}$'N,0-i 4H8;?A h  QF!,#&R'*O-0R25m6:;=>D 4  }Y#%r*i.z/35:BDG - $_&b+049= F  c #d&F ,0"368*[AC\ Bm!>#%+.0O26>:d=? F'Z /q]!q#&*,0608:>?+X ^ yS  vOm0!a%'.27y:>%@LD!M ]i$'4,!0<2 ;=A"DFK^ A["0%B&)*.-140 G0F # +.90359L;>DD  !#&'),1O4:9b; FB  "0%(J-0379(>CFEK@X 3B"%*# 13:z=?F>$ x",#v&y(+?,/2C48:A2 ; Y m$&)/2[5 =A CF9 7 f"-(",t/:9<@]E7  > #%)+.03L8q:$=B5R  V:x",$D*,0S36<"=@(DF_3mi (,/d1.5X8:p=BE0 :f "m%+' ,1x2003v068+9q:=?D.  s qx ..!:v$x..%(.378| ?}A:F, i"i(m ("&2(%m %,r W#m#"&2(CmC,r Wm"&2(m#'(m"&2(pmp"&2(;m;"&2(m #&(p m]!r$*,14 7%:5=A h Wp6{TVm$ZTheAlpinefilesystem25ACedarworkstationaccessingAlpineruns8500linesofCedarcodeforthistask.About4000linesaremanuallywrittencodenotalsousedintheserver,and3200linesareLupine-generatedcodenotusedintheserver.Theworkstationalsoruns18000linesofCypresscodefordatabaseaccess.DuringtheprojectweweresurprisedbytherelativedifficultyoftheOwnerDBcomponent.Thepresentdesignisamajorsimplificationofouroriginalscheme,yetitisstillthesecond-largestcomponentinAlpine.Asecondsurpriseistheamountofeffortrequiredforworkstationcode.Thisisnotdifficultprogramming,butthereisasignificantamountofittodo.Workstationcodedependsuponhigher-levelCedarfacilitiesthantheserverdoes.Henceitisinherentlylessstable,andthecostofmaintainingitduringtheprojectishigherperline.Oftheservercomponents,FileandOwnerDBwouldbechangedifwedecidedtoturnAlpineintoadatabaseserverthatdidnotsupporttheintermediateabstractionofanunstructuredfilewithtransactions.OfcoursesomethingequivalenttoOwnerDBwouldstillberequired,butitwouldpresumablybebuiltusingahigher-levelaccessmethod.Thiswouldnotactuallysimplifyitverymuch.SoevenifweeventuallydecidetobuildotheraccessmethodsintoAlpine,wehavenotwrittenmuchextracode,andinthemeantimewewereabletouseCypresscodeverylittlemodification.7.5StatusandObservationsAlpinestilllackstwo-copyloggingandincrementalbackup,andislimitedtoasinglediskvolume.AhierarchicaldirectorysystemandaPup-FTPserverforAlpinehavebeencodedbutnotyetintegratedwiththerestofthesystem.WehavenoticedafewfeaturesthatseemusefulandfitinwellwithAlpine'sdesign.Oneistheabilitytoaddablocksizepropertytoeachfile.Theblocksizeisanumberofpages,defaultone,andrepresentstheunitoffine-grainedlockingonafile.Inthiswayclientsthatprefertodealin2048bytepagesarenotpenalizedbyhavingtosetfourlocksoneachpageaccess.Anothereasyfeatureistheabilitytoperformdirtyreads,i.e.toreadwithoutsettingareadlock.Theincrementalbackupsystemwouldliketousethisfeature,andwecanimagineotherclients.Wehaveconsideredthepossibilityofprovidingunloggedudpates,asintheCambridgeFileServer'sstandardfiles.Weneedtoevaluatetheeffectivenessofthehighwatermarkoptimizationbeforemakingadecision.Atpresent,everytransactionwritesonelogrecordwhenthetransactioniscreated,andthissetsanultimatelimittothedurationofatransaction:whenthispartofthelogfileneedtobereused,thetransactionmustgoaway.Weshouldeitherimplementamoreelaborateloggingscheme,orweshouldallowspecialreadonlytransactionsthatwritenologrecords,orboth.Oneofthedisadvantagesofasystemstructurewithasinglevirtualaddressspaceisthatitbecomesdifficulttocircumscribetheresourcesusedbyatransaction.Sofarwehavenotadoptedanysystematicapproachtothisproblem,whichmeansthatanerranttransactioncancrashthesystemvg"]%5),%tgFv_/m !l%),Y/1R5l8:=AQE\ !;#'(+ /\2558_:EZ  \ jR* $'`*z.q13e8;>CXm] n&(+006 6E8%:A_ V] m<qq '(+h0|589r:=? T( Qms#$(.V0 8$D\E@P F %]'2*.28;@BFi> !$N+-|1 4l6m94>BLE; y6h  7 v3m,$' /479>@hAE0 k \ ,$'Y(.z249B<?CFi.  l@ ,m_O;"x%W(-/13u6s9?D^Gs*J j+x1*J*Jv*J$P&)U,/3}6;78>4@D6( c A# &+a-e.136<9=U@"D8E%  YzC"l$h(*,/30568g;#mb#B$x*/##*-Uv0Y##1)3Y48 = AbBE!x  S#&-'*P,1469\>B1Cm  $&,38:uF q r".'* 236E9x=E@   mc9 0$,&)!-k13u :l;@CF=q  h" (!#" *.c1358/:=@jB$D =  ]F!%)t0S1w5:?DF 'L %|(J+-0!5M7m  "&&,01Y5q9?BDG QO _"(,."/W 7F9X;=AC k 7 3$(,/h1D5< <#>BDc TTVm$26by,say,openingahugenumberoffiles.Asimpleinteractivedatabaseapplicationtendstoholdatransactionopenforlongperiodsoftime.Thiswouldnotbenecessaryiftherewereanefficientwayofvalidatingaworkstation'scacheofdatafromtheremoteserver.Thisshouldbepossibleatthelevelofcachedfilepages,butnogeneralcachepackageofthisformhasbeenimplementedforAlpine.Sadlyforus,theexperimentsindatabaseaccessmethodsthatwethinkaresoeasytoperformwithAlpinehavenothappenedyet,sowecannotreportonhowdifficultoreasytheseexperimentswere.Somesourcesofunnecessarycontentioninadatabasesystemwithphysicallockingareevident.Oneistheallocationoffreestorageinadatabase.Ifthereisasinglefreelistanditismodifiedoneachallocation,thenallallocationsareserialized.Perhapsbybuildingafewprimitivesofthissortintothefilemodelitispossibletoreducecontentionwithoutbuildingaccessmethodsintotheserver.8.UsingCedarTheAlpineprojectisdistinctfromtheCedarproject,butthetwoprojectshavecloseties.Cedar'sdatabaseapplicationsneedAlpinefordatabasestorage;AlpineneedstheCedarlanguageandCedarnucleus,andwasdevelopedusingthetoolsfromtheCedarprogrammingenvironment.AstheimplementorsofanambitiousCedarapplication,weareinagoodpositiontocommentonthesystem'sstrengthsandweaknesses.8.1GarbagecollectionandfinalizationCedarhasastoragemanagementsystem[Rovner,1984]thatisfullyintegratedwiththelanguage'stypesystemandhasautomaticreclaimationofunusedstorage,i.e.garbagecollection.Cedar'sautomaticstoragemanagementexistsatanunusuallylowlevelinthesystem,anditisusedbyallthemainoperatingsystemcomponentsexceptforthevirtualmemorymanager.(ThisstructureisnotuniquetoCedar;LispMachineLisp[WeinrebandMoon,1978]andInterlisp-D[TeitelmanandMasinter,1981]arebuiltinthisway.)Automaticstoragereclaimationisobviouslyaconveniencetotheprogrammer,andisconsideredanabsolutenecessityinsomeprogrammingcommunities.ButotherprogrammersconsiderlanguageslikeBliss,C,andPascaltobethehighest-levellanguagessuitablefor"systemsprogramming";oneoftenhearsconcernsaboutthecostorunpredictableperformanceofgarbagecollection.Sinceafileserverisclearlyasystemsprogrammingproject,ourexperienceinbuildingAlpineusingCedar'sautomaticstoragemanagementsystemshouldbeofinterest.Cedar'sgarbagecollectorisincrementalandoperatesasabackgroundactivity.Withoutthisproperty,wewouldnotbeabletousegarbage-collectedstorage,becausewecannotregularlyrefuseservicetoclientsforthetensecondsorsoittakesatrace-and-sweepgarbagecollectortodoitswork.tg/ v_/  ,!z\m  H (+-02 9.<?B3G%Z ZH!X"&<)+w035W ;< EX  |K b#(&*./1737 8=@D@FV] ~JF!N#' /r1T(mA "(;,Q146:<>ACQ M b"#%*l.038:=A' O MmA j '8(* /479<AVCKU o `)!#$+,01269X;>E?@FI!   !n# */17w8;N ACF'F m ,l $ +059?oB1Dzw?  HvBiF:A { 2!&U(.m38_<`>C8 t$5'*`-1;37 @x 5  6 #'9 .03F5689?@F3  c5 y.% m 9 v*mbL "C&,/2P36 =?B< ( l  (*/&4s6@ADF$;  w $9(*-e17X=AGs" g!$*-|158; ?H F' s ]m !")* 13z5 =@A i   & .1\4 =2B4 a (/I4j6E  `TVm$TheAlpinefilesystem27Inexchangefortheconvenienceofanincrementalgarbagecollector,wemustbecarefultoavoidcirculardatastructures,ortobreakupthecircularitiesbeforereleasingsuchstructures.ThiswasnotaprobleminAlpine.InimplementingAlpineweconsciouslyminimizedtheallocationofnewstorageinplaceswhereweexpectedperformancetomattermost,forexampleinthemain-lineoperationsforreadingandwritingindividualfilepages.Wellundertenpercentofthecodefallsintothiscategory.Elsewhereintheimplementationweallocatestorageasseemsconvenient;thisdefinitelymakesthecodeeasiertowriteandtounderstand.ButtherearequalitativedifferencesevenbetweenthecodethatminimizesallocationsandcodethatwehavepreviouslywritteninstandardMesa,whichlacksgarbagecollection.ThedifferencesareknowntoimplementorsofproductionLispprograms,whoalsomustminimizestorageallocationinsomesituations.First,alldebuggingisdoneatalevelthathidestheformatofobjectsinmemoryandthedetailsofthestorageallocator.ThisispossiblebecauseessentiallyallofAlpineiswritteninasubsetoftheCedarlanguagethatallowsthecompilertocheckthattheprogramcannotdestroythegarbagecollector'sinvariants.OnlythecallontheCedarnucleusthatreadsfromthediskintovirtualmemorybufferscannotbecheckedbythecompiler.InMesa,danglingreferencesoccurandaprogrammermustsometimesdebugattheleveloftheunderlyingmachine.Aseconddifferenceisthatcleanupinexceptionalconditionhandlingneednotbeperformedsocarefully.IfaMesaaprogramcleansupbyfreeingsomesetofallocatedobjects,thecorrespondingCedarprogramhasnoexplicitcleanupatall.Themostimportantadvantageofautomaticallymanagedstorageisthatitsimplifiesthedesignofinterfacesbetweenmodulesandsimplifiesthedesignofdatastructuresthataresharedbetweenprocesses.Procedurescanacceptreferencestoarbitrarydatastructuresorcomputeandreturnsuchobjectswithoutconcernoverwhetherthecallerorthecallee"owns"thestorage.Thisisespeciallyimportantwhentheproceduresarepossiblyremote.Sometimesthereisanexplicitactionthatmustbeperformedwhenacollectibleobjectistobereclaimed.Forexample,thereisahashtablethatmapsfileidentifierstothevolatileobjectsrepresentingfilesactivelyinuse.Whenafileobjectceasestobereferencedfromanywhereinthesystem,weneedtoremoveitfromthehashtable.ToaccomplishthisweuseCedar's"finalization"mechanism,whichpermitsarbitraryprogrammer-providedcodetobeexecutedwhenanobjectisabouttobegarbagecollected,orwhenaspecifiednumberofreferencestotheobjectremain.Inthisway,Cedar'sautomaticstoragemanagementfacilityhelpsustotakecareofataskthatwouldotherwisehavetobedonebymanualreferencecounting.WhiledevelopingAlpine,weidentifiedseveraldeficienciesinCedar'simplementationofautomaticstoragemanagement.Mostnotablewasalimitonthenumberofsimultaneousreferencestoanobject;exceedingthislimitwouldmaketheobject'sreferencecountbecome"pinned,"causingitnottobereclaimeduntilatrace-and-sweepgarbagecollectionwasinvoked.OurexperiencewithAlpineandotherCedarapplicationsledtoasignificantreengineeringoftheCedarautomaticstoragemanagementfacilitytoeliminateallthearbitrarylimitationsthathadexisted.vg"]%5),%tgFv_/  m P"$& +0 69.<>CZE\  f-"$G& .,28g; CF3Z  J|Xm/ Ys &-e/ 57:u?@DV]   !%(-/`18 >AF'T( Y :!"%'y,_.0m369k<BRQ  V  %Z'+ 2r5 ;+?_ADO  hh_ !%(L /O 6:!?BFM  ]!9#E&o ,138<@sCKW  t#?$ -/; 6<9O?BEvI" e S! FmV "%9'+-2P38:0?B<DD  y R %W* 1.3259;?ABG%B =%!'Z)-/2L7OAuD> H+"u$'0.&0%4W:+ @DG; !#v%)*-4 4$9mw E $ % ,3 8<>z@aG7~ Qq#% &+/&1928=? 5I R#%\3mJ!#L +16]7:; B+D0  t +! '*-.0T3i 9<>Cp.   S &(."1% 7d9&>AE,w N_#%i)#*-Q1,68>A8B *C  ! (!|&(mkgZ!2%N(+-~4F79+ ?CE<F% R>O !#.&*R-`1?3 :<?.DA# > $%(b,02Y4Q ;>DF!q  !l#' *, 468;_@W < W"b0,35c7t=RA(C9Gs ad  $]%+i02s 9:=;AgG ] ! ).2>458;=>AD -)#)jm T"# (- 5v7< G%6  # '*+.03H8m: B\   M0 #').48=C  w%`'- 3=5<> E  TZ !$"%& -^ 579=D, d L!$G) 03~66 TVm$288.2LightweightprocessesWithAlpine,wereaffirmedourbeliefinthevalueoflightweightprocessmachinery,alegacyofMesathathasbeencarriedoverintoCedar[LampsonandRedell,1980].InCedar,asystemcanhavehundredsofprocessesifnecessary.Thecostofswitchingbetweenprocessesisnegligible,andtheyusethesameaddressspacesodatasharingischeap.Thisleadstoaprogrammingstyleinwhichseparateprocessesareusedforseparateactivities,howeversmall.Theprocessmachineryeliminatestheneedtoexplicitlymultiplexorscheduleactivities(exceptwhereshareddatamustbereferenced)andimprovesconcurrency.Theremoteprocedurecallmechanismexploitslightweightprocessestothefullest.Ontheserver,eachincomingprocedurecallcausesaprocesstocomeintoexistence;whentheprocedurereturns,theprocessterminates.Aremoteprocedurecallcanbeofarbitraryduration,sinceitexecutesconcurrentlywithotherprocedurecallsandactivities.8.3LupineandCedarRPCAspreviouslydiscussed,theRPCfacilityenablesinter-machinecommunicationtobeexpressedasordinaryCedarprocedurecalls,withtheactualdatarepresentationsandnetworkprotocolstakencareofautomatically.Theremoteprocedurecallsemanticsresemblethelocalonesveryclosely,andthereareonlyafewdifferencesthatclientprogrammersneedbeawareof.WhileimplementingAlpine,twoinconvenientaspectsofRPCweremostnoticeable.First,onesemanticdifferencebetweenremoteandlocalcallsisthatintheremotecasethecallerandcalleedonotsharethesameaddressspace.ForAlpine,thismeansthatthecallercannotrefertoanobjectsuchasanopenfileoratransactionsimplybypresentingapointertothatobject,butmustinsteadpresentsomeidentifierthatnamestheobject.Thecalleemustmaintainadatastructurethatmapsidentifierstoobjects,andthecallermustmanagethesetofactiveidentifierssomehow.Itseemspossiblethatinsomecases,theRPCsystemcouldmanagesurrogateobjectsfortheclient,sendtheobjectidentifierdownthewire,andmakethecallintermsoftherealobjectattheserver.Second,Cedarprovidesnoconvenientwaytomanageandrefertoadynamicallyvaryingcollectionofinstancesofthesameinterface,eachlocatedatadifferentserver.Thisproblemseldomarisesinthestrictlylocalcase,sinceitisrarefortheretobemorethanoneinstanceofanygiveninterface,andthereforethebindingcanbespecifiedbyastaticconfiguration(forwhichCedar'sfacilitiesarewelldeveloped).Toovercometheseinconveniences,weconstructedan"Alpineobjectpackage"thatresidesontheclientmachineandisolatesclientprogramsfromdirectaccesstoAlpine'sremoteinterfaces.Thispackagemaintainssurrogateobjectscorrespondingtoservers,transactions,andopenfiles.Aclientcanthereforedealwithanopenfileratherthanwithan[open-fileID,server]pair.Remoteproceduresarethencalledbyinvokingthecorrespondingoperationsontheappropriatelocalobjects.Theobjects,beingallocatedfromautomaticallymanagedstorage,arereclaimedwhennolongerinuse,andanydesirableremoteside-effects(e.g.,closingopenfiles)aretriggeredbymeansofthefinalizationtg/ y_, m v[m' "&(B*.p0; 7k? F'UC v ~"e%*,1,4i8 9;' CG0S l!#)o /5K:=$B%P 6 %'-] 3 7;@nC|FN  LqmzW'8, 3:;>CFJ= &m $"'(T-=/25 <?B[H   N$+<-0139 >B,CdE _ #& y@V mv= m{  y#/', 5V ?@B:  ]  $&*-79?(E8 8 m8 'H)/58;<>_AaF'6m 5l h"6% .]13749m < " */1947;7 BF32 S &!$r'*,.027v:[<@]C F/ .G!u$.)+025b9$=A BD- |YH "D&( /_05R79>A@D++g  !.#(+m/G28s9<BmE?)3 ? n"?%*-s/15 < CHD& m."'*/5:<?(CBF$  H!%(*,L014/6:<>"m= ^ '*,2 5 8:< C a HI &).01/6;>D!, z70"\#%<(#*o./15f8;V@BzE* >"z%*'A-"/C04B <?C bP m$g& -/5A9h?hBDFZ  ~".(1+/Z3W4:H> E& >D! *,1 9s<3?CE m!$'*, 259d<A  1 P )y 0X25! <@*F c &],J1e3:#=?DSF T =e !%),02I79=?}A  TVm$VTheAlpinefilesystem29mechanismmentionedearlier.Theremoteprocedurecallmodel(incontrasttothemessagepassingmodel)potentiallypermitsstraightforwardon-linedebuggingofanapplicationprogramthatprovokesanerrordetectedduringacalltoanAlpineserver.Whentheexception(anordinaryCedarsignal)israised,theserverprocessexecutingtheprocedureissuspended(alongwiththecaller'sprocess,whichisalreadysuspendedwaitingforthecalltocomplete);buttherestoftheserver,includinganyothercalltothesameprocedure,proceedsunhinderedsinceeachremoteprocedurecallisexecutedbyaseparateprocessontheserver.Conceptually,thecallstackextendsfromthedebuggerontheclientmachine,throughachainofproceduresontheservermachine,andthenbacktothesiteoftheoriginalcallontheclientmachine.Unfortunately,theCedardebuggerpresentlylacksfacilitiesfortracingthecallstackacrossmachineboundaries;sothepartofthestacklocatedontheserver(includingtheactualcontextinwhichtheexceptionwassignalled)isnotvisibletothedebugger.Suchacapabilitywouldbeausefuladdition.OverallwefeelthatLupineandRPCwereaboontoAlpine.Lupinetranslatesroughly600linesofAlpinepublicinterfacesintoroughly7000linesofbug-freeCedarcodethatperformswell.LupineandRPCdonotcompletelysolvetheproblemofprotocolevolution,butwethinktheywillhelp.Withsuchassmallusercommunity,wehaveneverattemptedtosupporttwoversionsoftheAlpinepublicinterfacesatonetime.ItisworthreemphasizingthepointthatRPCdoesnotmakearemotecalllookexactlylikealocalcall.RPCdoesnotattempttohidethefactthattheaddressspacesaredifferentintheremotecase,orthattheremotecallistoamachinethathasfailuresindependentofyouroriginatingmachine.ThegreatthingaboutRPCisthattheremotecallstakeafamiliarform,andthatyouarenottemptedtocallinadifferentwayinthelocalcaseoutoflazinessortomakethelocalcallmoreefficient.RPCallowslocalcallstolookremote,nottheotherwayaround.8.4ModulesInSection4wenotedthatalog-basedtransactionimplementationcanbestructuredsothatmostofitdoesnotdependondetailsoftheunderlyingfilesystem,andiseasytomovefromonefilesystemtoanother.WerecentlytestedthishypothesisintheAlpineprojectbyconvertingthesystemtouseanewCedarfilesystemthatborenoresemblancetothepreviousfilesystem.EssentiallytheentireworkoftheconversionwasconfinedtotheBuffercomponent,asexpected.TheinterfacemoduleconstructofCedar(borrowedfromMesa)encouragesthissortofcleandecompositionofalargesystem.Wefeelthattheinterfacemodule,includingthetypecheckingacrossmoduleboundariesthatitmakespossible,isthestrongestfeatureoftheCedarlanguage.AlpineusedthefeatureofCedar(andMesa)interfacesthatallowsthemtobeparameterizedatcompiletime;thisisanalogoustogenericpackageinstantiationinAda.Unfortunatelythisfeatureisdifficulttouse;oftenaprogrammermustdefineanewinterfacejusttotransmitafewparametersvg"]%5),%tgFv_/ \m>[#%2*X+.X38u=! CZ < "]$M +^039;>DnX o!$*-3E7< =BCDV] 1 "J)H-1"38> B[D T( {d+ '~*,/?137>%@DG0Q  q A %F(+0o69f:@wBgCO Mm +&$(*025 8>CE)KV  f#&w)-./14,6 8=@nBEI"  !p!x'r-J0 58"<>AnDF ?  !$C',.150 ;>;BMG0D a !#s& *,Q.69: AMEGB @PmcgM ."&s)+.06: AFI> %_ "b'w*-/569N<?cE?;m3AD $((*017' =@B2E9 UI@!8 (*.828x:%?0AG%7}   !95Imrz !$'+.F045:= @JDG3 J= D!%'^*,/*48D:@3AD70 2vrU d%(*/ 7p9<. C. mHZ g"'A*:-.13;69<=>ACz,w  nx#G&I(*/13P79<?C. *B 5{9R#R%(&+.y$ mv!xm`c !M' . 8;l= D(FD >{#d%*' .1 58:'=7>BF3 )|+"w&): 014J8=? F ">$') 135Q:=B  Y _ ;"(**,0 8>9@iC9r g#?&* 147^9< EG= W#:(k.X03y9<A  zn#4')+0 m$~!"&*1 0U37F:_ GF D1 %+ 248 AD6 k  >Uv #P&*,.478>?@A  TVm$30tothepackage,andlatermustdealwithseveralfilesgeneratedbythecompilerintheinstantiationprocess.TheCedarsystemmodeller[LampsonandSchmidt,1983]isdesignedtosolvetheseproblems.Withoutthemodeller,wefounditmoreconvenienttoinstantiateasmallpackagebycopyingitssourcecodeinastylizedway.Thisworksfineaslongasthepackageisstable.8.5BeingpartofalargesystembuildingprojectThedecisiontobuildAlpineontopoftheCedarsystem(ratherthanfromscratch)wasmaderelativelyearlyinthelifetimeoftheCedarproject.ThishadtheinevitableconsequenceoftyingAlpinetotheevolutionandfortunesofCedar,acomplexandambitiousundertakingwhoseultimateoutcomewasnotyetcompletelyunderstood.Wasthisagooddecision?ThereisnoquestionthatAlpinederivedsubstantialbenefitfromusingCedarasabase.Inparticular,theautomaticstoragemanagementandremoteprocedurecallfacilitiesweresourcesofleverage,thoughRPCprobablywouldhavebeendevelopedanyway.Later,whenCedarreimplementeditsvirtualmemoryandfilesystem,wewereabletosuggestfeaturesthatmadethesemoreusabletoAlpine,withoutbuildingthemourselves.Ontheotherhand,usingCedarhadconsiderablecostsaswell.Earlyon,wespentagreatdealofdesigntimeconsideringhowtoadapttoaspectsofCedarthatwerelessthanidealforAlpine'spurposes;thiswasparticularlytrueofthePilotfilesystemandvirtualmemorythatCedarusedinitially.WeexperimentedwithwaystotakeadvantageofnewCedarlanguagefeaturesastheybecameavailable,suchasopaquetypesandobjectnotationforprocedurecalls,andtheseexperimentsdidnotcontributemuchtoAlpine.AsCedarevolved,Alpinerepeatedlyhadtobeconvertedtonewerversions.However,therewerepleasinglyfewsituationsinwhichshortcomingsorbugsintheCedarsystemheldupprogressontheAlpineproject.Actually,themostseriousdiversionoftimeandeffortwasduetotheAlpinedevelopersalsobeingactiveparticipantsintheCedarproject.WeoftendecidedtopursueactivitiesofultimatebenefittobothCedarandAlpineratherthanfocusingexclusivelyonAlpine.Ofcourse,allthisisreallyaprojectmanagementissue;andtheconsequencesareareflectionoftheinformalprojectorganizationthatistypicalofourresearchenvironment.ConsideringbothAlpineandCedarinthatcontext,weareverypleasedwiththeoutcome.AcknowledgementsManypeoplecontributedinonewayoranothertotheAlpineproject.ButlerLampsonandForestBaskettgaveussomegoodideasandencouragementduringtheearlygoing.AndrewBirrellandBruceNelsonproducedtheCedarRemoteProcedureCallfacility,whichallowedustoconcentrateonprovidingfileservicewhiletheywereprovidingdatacommunication.ThemembersoftheDoradoandCedarprojectshelpedcreateaproductiveprogrammingenvironmentthatwasthebasistg/ v_/  ah&R!$)z,n247)<>A \ g*$7*-379?AEUZ d!%#o'), 35 B2G%B 1!w&1*-5;@D@W &Y #|%*,0/3'49>AEU># ?1$( ;m /"B$ ,0)1594;=ASBxE9  w u!L%*&+-p14{7:=A,C|7  2"B$'&*$,1a4D8>dA^E5P  C $%(/1o48>CE3  ,#f&)/N1o7; =A' 0 ; ~n7"$)*.3Q :<>@G0. " ).+ 137 ?ADF, ?Zl #?'*JmU?$&*,03z6H8:?! F(  @#),L05N7#; AC{% \Xx8 $( - 46<> BDGs#  !$'V 023 :;>DA!x w; /% .\ 699=@`DmFC SbL g"w vm  ^#%&'- .1f6;@F' P $=& 047Q:?[Dc 9"'.059s>_@A /  f #&- 0I ;L>_DF f{!%&A - 5 =@~C&E TVm$TheAlpinefilesystem31forAlpine.References[Birrelletal,1982]AndrewD.Birrell,RoyLevin,RogerM.NeedhamandMichaelD.Schroeder,"Grapevine:anexerciseinDistributedComputing,"CommunicationsoftheACM25,4,April1982.[Birrell,1984]AndrewD.Birrell,"SecureCommunicationUsingRemoteProcedureCalls,"submittedtoACMTransactionsonComputerSystems.[BirrellandNelson,1983]AndrewD.BirrellandBruceJayNelson,"ImplementingRemoteProcedureCalls,"ACMTransactionsonComputerSystems2,1,February1984(toappear).[Boggsetal1980]DavidR.Boggs,JohnF.Shoch,EdwardA.Taft,andRobertM.Metcalfe,"Pup:AnInternetworkarchitecture,"IEEETransactionsonCommunicationsCom-28,4,April1980.[Brownetal,1981]MarkR.Brown,RodericG.G.Cattell,andNorihisaSuzuki,"TheCedarDBMS:apreliminaryreport,"ProceedingsofACM-SIGMOD1981,April1981,p205211.[Cattell,1983]R.G.G.Cattell,"DesignandImplementationofaRelationship-Entity-DatumDataModel,"XeroxPARCtechnicalreportCSL-83-4,May1983.[Clarketal,1981]DouglasW.Clark,ButlerW.Lampson,GeneA.McDaniel,SeveroM.Ornstein,andKennethA.Pier,"TheDorado:AHigh-PerformancePersonalComputer,"XeroxPARCtechnicalreportCSL-81-1,January1981.[Gray,1978]JamesGray,"NotesonDatabaseOperatingSystems,"OperatingSystemsanAdvancedCourse,SpringerLectureNotesinComputerScience60,1978,p393481.AlsoappearedasIBMResearchReportRJ2188,February1978.[Grayetal,1981]JimGrayetal,"TherecoverymanageroftheSystemRdatabasemanager,"ACMComputingsurveys13,2,June1981,p223242.[Israeletal,1978]JayE.Israel,JamesG.Mitchell,andHowardE.Sturgis,"Separatingdatafromfunctioninadistributedfilesystem,"XeroxPARCtechnicalreportCSL-78-5,September1978.[Lampson,1983]vg"]%5),%tgFv_/  wX vT xRTTvTTRjC<!%'.$06)8% ? FPOjD  x$POPO% /#03yPO6v8GPOPO9$:>OM Kj % )(-208=CnxKE Ikj _Rv#CIkIkF R Dj:" $* 39o@FxE DDFBj _RyB#v$wBB%T&,0$2L@ x@ @ v@ B=jh'eE!&(`+.24:>v@ ;j x;; "$ y;/#v3;;4699' x~9'9' v!9'9'6j!&)C.373;@@VAu 4jx44~  &v)44*.+132C 0jm! ,-/?Cq-j 'i*+^ x+^+^thv|+^+^X)*jBx '$*,38/:h@mC+&jFxt)r. 6:>D$j#"F  jf)"w(x.  05=:P<=CvH j3lp&,y+O,v,-12:>=CEjR<$:- x--2&v:--j"ZK!z'(+O017Yx>?AjyvtQ0H xHHi]vqHHMj&@#'%+V-.28 9<@cEG j \J!l%+/6H=/ d o0TVm$32ButlerLampson,"HintsforComputerSystemDesign,"ProceedingsoftheNinthACMSymposiumonOperatingSystemPrinciples,October1983,p3348.[Lampson,1984]ButlerLampson,"CedarLanguageReferenceManual,"XeroxPARCtechnicalreport,toappear.[LampsonandSchmidt,1983]ButlerW.LampsonandEricE.Schmidt,"PracticalUseofaPolymorphicApplicativeLanguage,"ProceedingsoftheTenthACMSymposiumonPrinciplesofProgrammingLanguages,January1983,p237255.[LampsonandRedell,1980]ButlerW.LampsonandDavidD.Redell,"ExperiencewithProcessesandMonitorsinMesa,"CommunicationsoftheACM23,2,February1980,p105117.[Lindsayetal,1979]B.G.Lindsay,P.G.Selinger,C.Galtieri,J.N.Gray,R.A.Lorie,T.G.Price,F.Putzolu,I.L.Traiger,andB.W.Wade,"NotesonDistributedDatabases,"IBMResearchReoprtRJ2571,July1979.[MitchellandDion,1981]JamesMitchellandJeremyDion,"AComparisonofTwoNetwork-BasedFileServers,"CommunicationsoftheACM25,4,April1982,p233245.[Mitchelletal,1979]JamesG.Mitchell,WilliamMaybury,andRichardSweet,"MesaLanguageManual,Version5.0,"XeroxPARCtechnicalreportCSL-79-3,April1979.[PetersonandStrickland,1983]R.J.PetersonandJ.P.Strickland,"Logwrite-aheadprotocolsandIMS/VSlogging,"ProceedingsoftheSecondACMSIGACT-SIGMODSymposiumonPrinciplesofDatabaseSystems,March1983,p216243.[Redelletal,1980]DavidD.Redelletal,"Pilot:anOperatingSystemforaPersonalComputer,"CommunicationsoftheACM23,2,February1980,p8192.[Rovner,1984]PaulRovner,"OnAddingGarbageCollectionandRuntimeTypestoaStrongly-Typed,Statically-Checked,ConcurrentLanguage,"XeroxPARCtechnicalreport,toappear.[Svobodova,1984]LibaSvobodova,"FileServersforNetwork-BasedDistributedSystems,"ACMComputingsurveys,toappear.AdraftappearedasanIBMResearchReport.[TeitelmanandMasinter,1981]WarrenTeitelmanandLarryMasinter,"TheInterlispprogrammingenvironment,"Computer14,4,April1981,p.2534.[Teitelman,1984]tg/ v_,j!(-x3_,_,4 ;=@E \j" v(X\\)5.2 3kZ} oXHj~q#* 0 48^> BlDU Sjuq!m' --/1k2q :g A xQdj 0B"5)+ 23 C?3jd< ? :j! %O' 0205 ?Cx8Pj \y8P |v!8P8P"$F'+,5 !3j %&)l.3O7>9C1lj7$"*.L. ` F,j*|] #& -360;xAg,,BN *j!H/ '.0 7,8>vC**Dy(SjT% xt%%v%%#jx##~v##n ")F.0A1k6 x>##? !ojZy!o.v!o!ok#$ Pj k&k -i06;=.>jQ ! (-1t7<;=f xj "%j /o 7x=>Ajvl} f%Z'(,>2&, Gfj:! 'P+0 9[ xBCy jv 4q I TVm$.TheAlpinefilesystem33WarrenTeitelman,"TheCedarprogrammingenvironment:amidtermreportandexamination,"ProceedingsoftheSeventhInternationalConferenceonSoftwareEngineering,March1984,toappear.AlsotoappearasaXeroxPARCtechnicalreport.[WeinrebandMoon,1978]DanielWeinrebandDavidMoon,"LispMachineManual,"MITArtificialIntelligenceLaboratory,November1978.vg"]%5),%tgFv_/j[ &! *, 239L=a@ x\j 8w ' .16 v=\\>CpG0Zj2 $,(.XXK kVje!c&R*07j;/ Au Sj VTVm$ TIMESROMAN TIMESROMAN LAUREL TIMESROMAN TIMESROMAN TIMESROMANY TIMESROMANLOGO HELVETICA HELVETICA HELVETICA HELVETICAY HELVETICA   s# t. 9 C N Y c m w z & 4  C   7" 4, 5<TCEj/H#FY9&Tuesday, February 14, 1984 7:04 pm PST