Module 7 - Other Google Technologies

©SpinnakerLabs,Inc.GoogleClusterComputingFacultyTrainingWorkshopModuleVII:OtherGoogleTechnologies©SpinnakerLabs,Inc.Overview•BigTable•Chubby©SpinnakerLabs,Inc.BigTable©SpinnakerLabs,Inc.AConventionalDatabase…•Datastructure:–arbitrary##ofrows–Fixednumberandtypeofcolumns•Supportssearchbasedonvaluesinallcells•Supportssynthesisofoutputreportsbasedonmultipletables(relationaloperators)©SpinnakerLabs,Inc.Google’sNeeds•Datareliability•Highspeedretrieval•Storageofhugenumbersofrecords(severalTBofdata)•(Multiple)pastversionsofrecordsshouldbeavailable©SpinnakerLabs,Inc.Assumptions•Manytimesmorereadsthanwrites•Individualcomponentfailurescommon•Disksarecheap•Iftheycontroldatabasedesignaswellasapplicationdesign,theinterfaceneednotbestandard©SpinnakerLabs,Inc.ReasonableQuestions•Arestructuredqueriesnecessary?•Candatabeorganizedsuchthatrelateddataisphysicallyclosebynature?•Whatistheminimumcoordinationrequiredtoretrievedata?•Canexistingcomponentsbeleveragedtoprovidereliabilityandabstraction?©SpinnakerLabs,Inc.FromNeedstoConstraints•Simplifieddataretrievalmechanism–(row,col,timestamp)valuelookup,only–Norelationaloperators•Atomicupdatesonlypossibleatrowlevel©SpinnakerLabs,Inc.ButSomeAdditionalFlexibility…•Arbitrarynumberofcolumnsperrow•Arbitrarydatatypeforeachcolumn–Newconstraint:datavalidationmustbeperformedbyapplicationlayer!©SpinnakerLabs,Inc.LogicalDataRepresentation•Rows&columnsidentifiedbyarbitrarystrings•Multipleversionsofa(row,col)cellcanbeaccessedthroughtimestamps–Applicationcontrolsversiontrackingpolicy•Columnsgroupedintocolumnfamilies©SpinnakerLabs,Inc.ColumnFamilies•Relatedcolumnsstoredinfixednumberoffamilies–Familynameisaprefixoncolumnname–e.g.,“fileattr:owning_group”,“fileattr:owning_user”,etc.•Permissionscanbeappliedatfamilyleveltograntread/writeaccesstodifferentapplications•Membersofafamilycompressedtogether©SpinnakerLabs,Inc.NoDataValidation•Anynumberofcolumnscanbestoredinarowwithinthepre-definedfamilies–Databasewillnotenforceexistenceofanyminimumsetofcolumns•Anytypeofdatacanbestoredinanycolumn–Bigtableseesonlybytestringsofarbitrarylength©SpinnakerLabs,Inc.Consistency•Multipleoperationsonasinglerowcanbegroupedtogetherandappliedatomically–Nomulti-rowmutationoperatorsavailable•UsercanspecifytimestamptoapplytodataorallowBigtabletouse‘now()’function©SpinnakerLabs,Inc.VersionControl•Cellversionsstoredmost-recentfirstforfasteraccesstomorerecentdata•Twoversionexpirationpoliciesavailable:–Retainlastncopies–Retaindataforntimeunits©SpinnakerLabs,Inc.DataAccess•Straight(row,col,ts)lookup•Alsosupports(row,col,MOST_RECENT)•Filterediteratorswithinrowwithregexovercolumnnamesoradditionalconstraintsontimestamps•StreamingaccessoflargeamountsofdatatoandfromMapReduce©SpinnakerLabs,Inc.Implementation•UsesseveralotherGooglecomponents:–GFSprovidesreliablelow-levelstoragefortablefiles,metadata,andlogs–Chubbyprovidesdistributedsynchronization–DesignedtoeasilyinterfacewithMapReduce©SpinnakerLabs,Inc.PhysicalDataRepresentation•SSTablefileprovidesimmutablekeyvaluemapwithanindexoverallkeysmappingkeydiskblock–IndexstoredinRAM;valuelookupinvolvesonlyonediskseektodiskblock©SpinnakerLabs,Inc.PhysicalRepresentation(2)•Alogical“table”isdividedintomultipletablets–EachtabletisoneormoreSSTablefiles•Eachtabletstoresanintervaloftablerows–Ifatabletgrowsbeyondacertainsize,itissplitintotwonewtablets©SpinnakerLabs,Inc.NetworkInterface•Onemasterserver–Communicatesonlywithtabletservers•Severaltabletservers–Performactualclientaccesses•“Chubby”lockserverprovidescoordinationandmutualexclusion•GFSserversprovideunderlyingstorage©SpinnakerLabs,Inc.BigtableArchitectureHeadnodeTabletserverGFSChunkserverSSTableSSTableSSTableTabletTabletTabletTabletserverGFSChunkserverSSTable(replica)SSTableSSTableTabletTabletTablet(replica)SSTableLogicalview:Physicallayout:SSTableChubbyServer©SpinnakerLabs,Inc.MasterResponsibilities•Determinewhichtabletservershouldholdagiven(new)tablet•InterfacewithGFStogarbagecollectstaleSSTablefiles•Detecttabletserverfailures/resumptionandloadbalanceaccordinglyTabletServerFailureTabletserverGFSChunkserverSSTableSSTableSSTableTabletTabletTabletTabletserverGFSChunkserverSSTable(replica)SSTableSSTableTabletTabletTablet(replica)SSTableLogicalview:Physicallayout:SSTableChubbyServerHeadnodeTabletServerFailureChubbyServerTabletserverGFSChunkserverSSTableSSTableSSTableTabletTabletTabletTabletserverGFSChunkserverSSTable(replica)SSTableSSTableTabletTabletTablet(replica)SSTableLogicalview:Physicallayout:SSTableXXXXXHeadnodeTabletServerFailureTabletserverGFSChunkserverSSTableSSTableSSTableTabletTabletTablet(replica)SSTableLogicalview:Physicallayout:Tablet(othertabletserversdraftedtoserveother“abandoned”tablets)BackupcopyoftabletmadeprimaryMessagesenttotabletserverbyheadnodeExtrareplicaoftabletcreatedautomaticallybyGFSChubbyServerHeadnodeTableAccessStructure©SpinnakerLabs,Inc.WriteProcedure•WritestoatabletarerecordedinaGFS-enabledcommitlog•Newdataisthenstoredinmemoryontabletserver–supercedesunderlyingSSTablefiles©SpinnakerLabs,Inc.MinorCompactions•Olddata