Google云计算解决方案6-分布式文件系统

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