Module 3 - google Nutch

GoogleClusterComputingFacultyTrainingWorkshopModuleIII:NutchThispresentation©MichaelCafarellaRedistributedundertheCreativeCommonsAttribution3.0license.Meta-detailsBuilttoencouragepublicsearchworkOpen-source,w/pluggablemodulesCheaptorun,bothmachines&adminsGoal:Searchmorepages,withbetterquality,thananyotherenginePrettygoodrankingHasdone~200Mpages,morepossibleHadoopisaspinoffOutlineNutchdesignLinkdatabase,fetcher,indexer,etc…HadoopsupportDistributedfilesystem,jobcontrolWebDBFetcher2ofNFetcher1ofNFetcher0ofNFetchlist2ofNFetchlist1ofNFetchlist0ofNUpdate2ofNUpdate1ofNUpdate0ofNContent0ofNContent0ofNContent0ofNIndexer2ofNIndexer1ofNIndexer0ofNSearcher2ofNSearcher1ofNSearcher0ofNWebServer2ofMWebServer1ofMWebServer0ofMIndex2ofNIndex1ofNIndex0ofNInjectMovingPartsAcquisitioncycleWebDBFetcherIndexgenerationIndexingLinkanalysis(maybe)ServingresultsWebDBContainsinfoonallpages,linksURL,lastdownload,#failures,linkscore,contenthash,refcountingSourcehash,targetURLMustalwaysbeconsistentDesignedtominimizediskseeks19msseektimex200mnewpages/mo=~44daysofdiskseeks!Single-diskWebDBwashugeheadacheFetcherFetcherisverystupid.Nota“crawler”Pre-MapRed:divide“to-fetchlist”intokpieces,oneforeachfetchermachineURLsforonedomaingotosamelist,otherwiserandom“Politeness”w/ointer-fetcherprotocolsCanobserverobots.txtsimilarlyBetterDNS,robotscachingEasyparallelismTwooutputs:pages,WebDBedits2.Sortedits(externally,ifnecessary)WebDB/FetcherUpdatesURL::NeverContentHash:NoneURL::NeverContentHash:NoneURL::4/07/05ContentHash:MD5_toewkekqmekkalekaaURL::3/22/05ContentHash:MD5_sdflkjweroiwelksdEdit:DOWNLOAD_CONTENTURL::MD5_balboglerropewolefbagEdit:DOWNLOAD_CONTENTURL::MD5_toewkekqmekkalekaaEdit:NEW_LINKURL::NoneWebDBFetcheredits1.Writedownfetcheredits3.Readstreamsinparallel,emittingnewdatabase4.RepeatforothertablesURL::Today!ContentHash:MD5_balboglerropewolefbagURL::Today!ContentHash:MD5_toewkekqmekkalekaaIndexingIteratethroughallkpagesetsinparallel,constructinginvertedindexCreatesa“searchabledocument”of:URLtextContenttextIncominganchortextOthercontenttypesmighthaveadifferentdocumentfieldsEg,emailhassender/receiverAnysearchablefieldend-userwillwantUsesLucenetextindexerLinkanalysisApage’srelevancedependsonbothintrinsicandextrinsicfactorsIntrinsic:pagetitle,URL,textExtrinsic:anchortext,linkgraphPageRankismostfamousofmanyOthersinclude:HITSOPICSimpleincominglinkcountLinkanalysisissexy,butimportancegenerallyoverstatedLinkanalysis(2)NutchperformsanalysisinWebDBEmitascoreforeachknownpageAtindextime,incorporatescoreintoinvertedindexExtremelytime-consumingInourcase,disk-consuming,too(becausewewanttouselow-memorymachines)Fastandeasy:0.5*log(#incominglinks)“britney”QueryProcessingDocs0-1MDocs1-2MDocs2-3MDocs3-4MDocs4-5MDs2.3M,2.9M1.2M,4.4M,29,…AdministeringNutchAdmincostsarecriticalIt’sahasslewhenyouhave25machinesGooglehas100k,probablymoreFilesWebDBcontent,workingfilesFetchlists,fetchedpagesLinkanalysisoutputs,workingfilesInvertedindicesJobsEmitfetchlists,fetch,updateWebDBRunlinkanalysisBuildinvertedindicesAdministeringNutch(2)Adminsoundsboring,butit’snot!ReallyIswearLarge-filemaintenanceGoogleFileSystem(Ghemawat,Gobioff,Leung)NutchDistributedFileSystemJobControlMap/Reduce(DeanandGhemawat)Pig(YahooResearch)DataStorage(BigTable)NutchDistributedFileSystemSimilar,butnotidentical,toGFSRequirementsarefairlystrangeExtremelylargefilesMostfilesreadonce,fromstarttoendLowadmincostsperGBEquallystrangedesignWrite-once,withdeleteSinglefilecanexistacrossmanymachinesWhollyautomaticfailurerecoveryNDFS(2)DatadividedintoblocksBlockscanbecopied,replicatedDatanodesholdandserveblocksNamenodeholdsmetainfoFilenameblocklistBlockdatanode-locationDatanodesreportintonamenodeeveryfewsecondsNDFSFileReadNamenodeDatanode0Datanode1Datanode2Datanode3Datanode4Datanode51.Clientasksdatanodeforfilenameinfo2.Namenoderespondswithblocklist,andlocation(s)foreachblock3.Clientfetcheseachblock,insequence,fromadatanode“crawl.txt”(block-33/datanodes1,4)(block-95/datanodes0,2)(block-65/datanodes1,4,5)NDFSReplicationNamenodeDatanode0(33,95)Datanode1(46,95)Datanode2(33,104)Datanode3(21,33,46)Datanode4(90)Datanode5(21,90,104)1.Alwayskeepatleastkcopiesofeachblk2.Imaginedatanode4dies;blk90lost3.Namenodelosesheartbeat,decrementsblk90’sreferencecount.Asksdatanode5toreplicateblk90todatanode04.ChoosingreplicationtargetistrickyMap/ReduceMap/ReduceisprogrammingmodelfromLisp(andotherplaces)EasytodistributeacrossnodesNiceretry/failuresemanticsmap(key,val)isrunoneachiteminsetemitskey/valpairsreduce(key,vals)isrunforeachuniquekeyemittedbymap()emitsfinaloutputManypro