GoogleClusterComputingFacultyTrainingWorkshopModuleVI:DistributedFilesystems?SpinnakerLabs,Inc.OutlineFilesystemsoverviewNFS&AFS(AndrewFileSystem)GFS?SpinnakerLabs,Inc.FileSystemsOverviewSystemthatpermanentlystoresdataUsuallylayeredontopofalower-levelphysicalstoragemediumDividedintologicalunitscalled“files”Addressablebyafilename(“foo.txt”)Usuallysupportshierarchicalnesting(directories)?SpinnakerLabs,Inc.FilePathsAfilepathjoinsfile&directorynamesintoarelativeorabsoluteaddresstoidentifyafileAbsolute:/home/aaron/foo.txtRelative:docs/someFile.docTheshortestabsolutepathtoafileiscalleditscanonicalpathThesetofallcanonicalpathsestablishesthenamespaceforthefilesystemWhatGetsStoredUserdataitselfisthebulkofthefilesystem'scontentsAlsoincludesmeta-dataonadrive-wideandper-filebasis:Drive-wide:AvailablespaceFormattinginfocharacterset...Per-file:nameownermodificationdatephysicallayout...?SpinnakerLabs,Inc.High-LevelOrganizationFilesareorganizedina“tree”structuremadeofnesteddirectoriesOnedirectoryactsasthe“root”“links”(symlinks,shortcuts,etc)providesimplemeansofprovidingmultipleaccesspathstoonefileOtherfilesystemscanbe“mounted”anddroppedinassub-hierarchies(otherdrives,networkshares)?SpinnakerLabs,Inc.Low-LevelOrganization(1/2)Filedataandmeta-datastoredseparatelyFiledescriptors+meta-datastoredininodesLargetreeortableatdesignatedlocationondiskTellshowtolookupfilecontentsMeta-datamaybereplicatedtoincreasesystemreliability?SpinnakerLabs,Inc.Low-LevelOrganization(2/2)“Standard”read-writemediumisaharddrive(othermedia:CDROM,tape,...)ViewedasasequentialarrayofblocksMustaddress~1KBchunkatatimeTreestructureis“flattened”intoblocksOverlappingreads/writes/deletescancausefragmentation:filesareoftennotstoredwithalinearlayoutinodesstoreallblockidsrelatedtofileFragmentationDesignConsiderationsSmallerinodesizereducesamountofwastedspaceLargerinodesizeincreasesspeedofsequentialreads(maynothelprandomaccess)Shouldthefilesystembefasterormore

reliable?Butfasteratwhat:Largefiles?Smallfiles?Lotsofreading?Frequentwriters,occasionalreaders??SpinnakerLabs,Inc.FilesystemSecurityFilesystemsinmulti-userenvironmentsneedtosecureprivatedataNotionofusernameisheavilybuiltintoFSDifferentusershavedifferentaccesswritestofiles?SpinnakerLabs,Inc.UNIXPermissionBitsWorldisdividedintothreescopes:User–Thepersonwhoowns(usuallycreated)thefileGroup–Alistofparticularuserswhohave“groupownership”ofthefileOther–Everyoneelse“Read,”“write”and“execute”permissionsapplicableateachlevel?SpinnakerLabs,Inc.UNIXPermissionBits:LimitsOnlyonegroupcanbeassociatedwithafileNohigher-ordergroups(groupsofgroups)Makesitdifficulttoexpressmorecomplicatedownershipsets?SpinnakerLabs,Inc.AccessControlListsMoregeneralpermissionsmechanismImplementedinWindowsRichernotionofprivilegesthanr/w/xe.g.,SetPrivilege,Delete,Copy…AllowforinheritanceaswellasdenylistsCanbecomplicatedtoreasonaboutandleadtosecuritygaps?SpinnakerLabs,Inc.ProcessPermissionsImportantnote:processesrunningonbehalfofuserXhavepermissionsassociatedwithX,notprocessfileownerYSoifrootownsls,useraaroncannotuselstopeekatotherusers’filesException:specialpermission“setuid”setstheuser-idassociatedwitharunningprocesstotheowneroftheprogramfile?SpinnakerLabs,Inc.DiskEncryptionDatastoragemediumisanothersecurityconcernMostfilesystemsstoredataintheclear,relyonruntimesecuritytodenyaccessAssumesthephysicaldiskwon’tbestolenThediskitselfcanbeencryptedHopefullybyusingseparatepasskeysforeachuser’sfiles(Challenge:howdoyouimplementreadaccessforgroupmembers?)Metadataencryptionmaybeaseparateconcern?SpinnakerLabs,Inc.DistributedFilesystemsSupportaccesstofilesonremoteserversMustsupportconcurrencyMakevaryingguaranteesaboutlocking,who“wins”withconcurrentwrites,etc...MustgracefullyhandledroppedconnectionsCanoffersupportforreplicationandlocalcachingDifferentimplementationssitindifferentplacesoncomplexity/featurescale?SpinnakerLabs,Inc.NFSFirstdevelopedin1980sbySunPresentedwithstandardUNIXFSinterfaceNetworkdrivesaremountedintolocaldirectoryhierarchyYourhomedirectoryonattuisNFS-drivenType'mount'sometimeatthepromptifcurious?SpinnakerLabs,Inc.NFSProtocolInitiallycompletelystatelessOperatedoverUDP;didnotuseTCPstreamsFilelocking,etc,implementedinhigher-levelprotocolsModernimplementationsuseTCP/IP&statefulprotocolsServer-sideImplementationNFSdefinesavirtualfilesystemDoesnotactuallymanagelocaldisklayoutonserverServerinstantiatesNFSvolumeontopoflocalfilesystemLocalharddrivesmanagedbyconcretefilesystems(EXT,ReiserFS,...)OthernetworkedFS'smountedinby...??SpinnakerLabs,Inc.NFSLockingNFSv4supportsstatefullockingoffilesClientsinformserverofintenttolockServercannotifyclientsofoutstandinglockrequestsLockingislease-based:clientsmustcontinuallyrenewlocksbeforeatimeoutLossofcontactwithserverabandonslocksNFSClientCachingNFSClientsareallowedtocachecopiesofremotefilesforsubsequentaccessesSupportsclose-to-opencacheconsistencyWhenclientAclosesafile,itscontentsaresynchronizedwiththemaster,andtimestampischangedWhenclientBopensthefile,itchecksthatlocaltimestampagreeswithservertimestamp.Ifnot,itdiscardslocalcopy.Concurrentreader/writersmustuseflagstodisablecaching?SpinnakerLabs,Inc.NFS:TradeoffsNFSVolumemanagedbysingleserverHigherloadoncentralserverSimplifiescoherencyprotocolsFullPOSIXsystemmeansit“dropsin”veryeasily,butisn’t“great”foranyspecificneed?SpinnakerLabs,Inc.DistributedFSSecuritySecurityisaconcernatseverallevelsthroughoutDFSstackAuthenticationDatatransferPrivilegeescalationHowaretheseappliedinNFS??SpinnakerLabs,Inc.AuthenticationinNFSInitialNFSsystemtrustedclientprogramsUserlogincredentialswerepassedtoOSkernelwhichforwardedthemtoNFSserver…AmaliciousclientcouldeasilysubvertthisModernimplementationsusemoresophisticatedsystems(e.g.,Kerberos)?SpinnakerLabs,Inc.DataPrivacyEarlyNFSimplementationssentdatain“plaintext”overnetworkModernversionstunnelthroughSSHDoubleproblemwithUDP(connectionless)protocol:Observerscouldwatchwhichfileswerebeingopenedandtheninsert“write”requestswithfakecredentialstocorruptdata?SpinnakerLabs,Inc.PrivilegeEscalationLocalfilesystemusernameisusedasNFSusernameImplication:being“root”onlocalmachinegivesyourootaccesstoentireNFSclusterSolution:“rootsquash”–NFShard-codesaprivilegede-escalationfrom“root”downto“nobody”forallaccesses.?SpinnakerLabs,Inc.AFS(TheAndrewFileSystem)DevelopedatCarnegieMellonStrongsecurity,highscalabilitySupports50,000+clientsatenterpriselevel?SpinnakerLabs,Inc.SecurityinAFSUsesKerberosauthenticationSupportsrichersetofaccesscontrolbitsthanUNIXSeparate“administer”,“delete”bitsAllowsapplication-specificbits?SpinnakerLabs,Inc.LocalCachingFilereads/writesoperateonlocallycachedcopyLocalcopysentbacktomasterwhenfileisclosedOpenlocalcopiesarenotifiedofexternalupdatesthroughcallbacks?SpinnakerLabs,Inc.LocalCaching-TradeoffsShareddatabasefilesdonotworkwellonthissystemDoesnotsupportwrite-throughtosharedmedium?SpinnakerLabs,Inc.ReplicationAFSallowsread-onlycopiesoffilesystemvolumesCopiesareguaranteedtobeatomiccheckpointsofentireFSattimeofread-onlycopygenerationModifyingdatarequiresaccesstothesoler/wvolumeChangesdonotpropagatetoread-only copies?SpinnakerLabs,Inc.AFSConclusionsNotquitePOSIXStrongersecurity/permissionsNofilewrite-throughHighavailabilitythroughreplicas,localcachingNotappropriateforallfiletypes?SpinnakerLabs,Inc.TheGoogleFileSystem?SpinnakerLabs,Inc.MotivationGoogleneededagooddistributedfilesystemRedundantstorageofmassiveamountsofdataon

cheapandunreliablecomputersWhynotuseanexistingfilesystem?Google’sproblemsaredifferentfromanyoneelse’sDifferentworkloadanddesignprioritiesGFSisdesignedforGoogleappsandworkloadsGoogleappsaredesignedforGFS?SpinnakerLabs,Inc.AssumptionsHighcomponentfailureratesInexpensivecommoditycomponentsfailoften“Modest”numberofHUGEfilesJustafewmillionEachis100MBorlarger;multi-GBfilestypicalFilesarewrite-once,mostlyappendedtoPerhapsconcurrentlyLargestreamingreadsHighsustainedthroughputfavoredoverlowlatency?SpinnakerLabs,Inc.GFSDesignDecisionsFilesstoredaschunksFixedsize(64MB)ReliabilitythroughreplicationEachchunkreplicatedacross3+chunkserversSinglemastertocoordinateaccess,keepmetadataSimplecentralizedmanagementNodatacachingLittlebenefitduetolargedatasets,streamingreadsFamiliarinterface,butcustomizetheAPISimplifytheproblem;focusonGoogleappsAddsnapshotandrecordappendoperations?SpinnakerLabs,Inc.GFSClientBlockDiagramGFSArchitectureSinglemasterMutiplechunkservers…Cananyoneseeapotentialweaknessinthisdesign??SpinnakerLabs,Inc.SinglemasterFromdistributedsystemsweknowthisisa:SinglepointoffailureScalabilitybottleneckGFSsolutions:ShadowmastersMinimizemasterinvolvementnevermovedatathroughit,useonlyformetadataandcachemetadataatclientslargechunksizemasterdelegatesauthoritytoprimaryreplicasindatamutations(chunkleases)Simple,andgoodenough!?SpinnakerLabs,Inc.Metadata(1/2)GlobalmetadataisstoredonthemasterFileandchunknamespacesMappingfromfilestochunksLocationsofeachchunk’sreplicasAllinmemory(64bytes/chunk)FastEasilyaccessible?SpinnakerLabs,Inc.Metadata(2/2)Masterhasanoperationlogforpersistentloggingofcriticalmetadataupdatespersistentonlocaldiskreplicatedcheckpointsforfasterrecovery?SpinnakerLabs,Inc.MutationsMutation=writeorappendmustbedoneforallreplicasGoal:minimizemasterinvolvementLeasemechanism:masterpicksonereplicaasprimary;givesita“lease”

formutationsprimarydefinesaserialorderofmutationsallreplicasfollowthisorderDataflowdecoupledfromcontrolflow?SpinnakerLabs,Inc.MutationsDiagram?SpinnakerLabs,Inc.MutationExampleClient1opens"foo"formodify.ReplicasarenamedA,B,andC.Bisdeclaredprimary.Client1sendsdataXforchunktochunkserversClient2opens"foo"formodify.ReplicaBstillprimaryClient2sendsdataYforchunktochunkserversServerBdeclaresthatXwillbeappliedbeforeYOtherserverssignalreceiptofdataAllserverscommitXthenYClients1&2closeconnectionsB'sleaseonchunkislost?SpinnakerLabs,Inc.AtomicrecordappendClientspecifiesdataGFSappendsittothefileatomicallyatleastonceGFSpickstheoffsetworksforconcurrentwritersUsedheavilybyGoogleappse.g.,forfilesthatserveasmultiple-producer/single-consumerqueues?SpinnakerLabs,Inc.Relaxedconsistencymodel(1/2)“Consistent”=allreplicashavethesamevalue“Defined”=replicareflectsthemutation,consistentSomeproperties:concurrentwritesleaveregionconsistent,butpossiblyundefinedfailedwritesleavetheregioninconsistentSomeworkhasmovedintotheapplications:e.g.,self-validating,self-identifyingrecords?SpinnakerLabs,Inc.Relaxedconsistencymodel(2/2)Simple,efficientGoogleappscanlivewithitwhataboutotherapps?Namespaceupdatesatomicandserializable?SpinnakerLabs,Inc.Master’sresponsibilities(1/2)MetadatastorageNamespacemanagement/lockingPeriodiccommunicationwithchunkserversgiveinstructions,collectstate,trackclusterhealthChunkcreation,re-replication,rebalancingbalancespaceutilizationandaccessspeedspreadreplicasacrossrackstoreducecorrelatedfailuresre-replicatedataifredundancyfallsbelowthresholdrebalancedatatosmoothoutstorageandrequestload?SpinnakerLabs,Inc.Master’sresponsibilities(2/2)GarbageCollectionsimpler,morereliablethantraditionalfiledeletemasterlogsthedeletion,renamesthefiletoahiddennamelazilygarbagecollectshiddenfi