南京大学计算机科学与技术系主讲人：黄宜华杨晓亮 2011年春季学期 MapReduce海量数据并行处理.ppt

《南京大学计算机科学与技术系主讲人：黄宜华杨晓亮 2011年春季学期 MapReduce海量数据并行处理.ppt》由会员分享，可在线阅读，更多相关《南京大学计算机科学与技术系主讲人：黄宜华杨晓亮 2011年春季学期 MapReduce海量数据并行处理.ppt（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、南京大学计算机科学与技术系主讲人：黄宜华，杨晓亮 2011年春季学期 MapReduce海量数据并行处理 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望LOGOA Full Text Search Engine For BBS Lily 南京大学计算机科学与技术系主讲人：黄宜华、顾荣 2011年春季学期鸣谢：本课程得到鸣谢：本课程得到鸣谢：本课程得到鸣谢：本课程得到GoogleGoogleGoogleGoogle公司公司公司公司(北京）北京）北京）北京）中国大学合

2、作部精品课程计划资助中国大学合作部精品课程计划资助中国大学合作部精品课程计划资助中国大学合作部精品课程计划资助ContentsBackgroundBrief IntrotoprincipleofFullTextSearchEngineImplementofFTSEforBBSLilyMaybeGoogle&Baiduhasdonethese.Conclusion1.BackgroundWhat is a full text search engine?1.11.2Why do we need it?What is a full text search engine?Inafulltextsea

3、rch,thesearchengineexaminesallofthewordsineverystoreddocumentasittriestomatchsearchwordssuppliedbytheuser.-FromWikiWhy do we need a FTSE for BBS Lily?Totalamount:around3millionpostsOverathousandeveryday.Eachpostssize:1K4KData InBBS Lily BaseCapacityIncreasingSpeed Post GranularityContentsBackgroundB

4、rief IntrotoprincipleofFullTextSearchEngineImplementofFTSEforBBSLilyMaybeGoogle&Baiduhasdonethese.Conclusion2.Brief Intro to the Principle of Full Text Search EngineWhat happens after you press enter?Abstract IR ArchitectureDocumentsQueryHitsRepresentationFunctionRepresentationFunctionQueryRepresent

5、ationDocumentRepresentationComparisonFunctionIndexofflineonlinedocument acquisition(e.g.,web crawling)About Representation FunctionDocumentsInvertedIndexBag of Wordscase folding,tokenization,stopword removal,stemmingsyntax,semantics,word knowledge,etc.A Simple Inverted Index Demo11121111111211111112

6、3111411121121bluecateggfishgreenhamhatone11111121bluecateggfishgreenhamhatone11red11two1red1twoone fish,two fishDoc 1red fish,blue hatDoc 2cat in the hatDoc 3green eggs and hamDoc 43414432122112Map/Reduces Role1.musthavesub-second responsetime2.fortheweb,onlyneedrelativelyfew resultsIndexingIndexing

7、ProblemProblemRetrievalRetrievalProblemProblemCharacter DescriptionCharacter DescriptionSuitable?Suitable?1.scalability2.relativelyfast3.batchoperation4.updatesmaynotbeimportant5.crawlingisachallengeinitselfContentsBackgroundBrief IntrotoprincipleofFullTextSearchEngineImplementofFTSEforBBSLilyMaybeG

8、oogle&Baiduhasdonethese.Conclusion3.Implement of FTSE for Lily BBS3.4OutlineofWorkFlow3.13.23.33.5CrawlWebPages&MineInfoIndexingProcessesSetupWebRetrievalInterfaceOptimizationResponseQuery String3.1 Outline of work FlowWeb Page 0Web Page 1Web Page nCrawl&Info MiningFormated Files/Content/Vice InfoIn

9、verted Index&Ranking JSP PageSplitTerm0,Term1Term nSearch&MergeTarget DIDResult ListTitleContextAuthorURLHottoken 1token 0token nIndexForIndicesCrawlerWeb RetrivalMap/Reduce3.2 Crawl Web Pages&Mine Info3.2.1Target FrameworkofLilyBBSStrategyofCrawler StrategyofMiner3.2.53.2.43.2.23.2.3CommonissuesTar

10、get of Crawler&MinerCrawl every postFrom BBS lily Continuously.FaulttoleranceMine wanted infoFrom each post that Crawler has got from web;store the them in a designed pattern.A CrawlerB MinerFramework of BBS Lily(1)Post 0Post 1Post nTitleinhereBBSLilyTitleinheresection 12Titleinheresection0Titleinhe

11、resection2Titleinheresection1TitleinhereBoard 0Board 1TitleinhereBoard nFramework of BBS Lily(2)Strategy of CrawlerDFSPost 1Post nPost 0TitleinhereBBSLilyTitleinhereSection 12Titleinheresection0Titleinheresection2Titleinheresection1TitleinhereBoard 0Board 1TitleinhereBoard n-Traversalcataloglinkstog

12、etthecontent;-AutomaticlinktoNextPageanddotheroutinejob.tipsStrategy of MinerRegex 南京大学小百合站-文章阅读讨论区:D_ComputerNet.User.init(WHEEL:0,FACE:1,BACK:0)发信人:MSer(微软校园大使),信区:D_Computer.本篇人气:205标题:转载微软2011春夏季实习生招聘将于下周一启动！发信站:南京大学小百合站(FriMar1800:28:592011)【以下文字转载自MSer的blog】【原文由MSer所发表】抢先知道：微软2011春夏季实习生招聘将于下周一

13、启动！亲爱的同学们，微软2011春夏实习生招聘将于下周一在全国范围内全面启动！届时，JoinMS网站也将以全新的内容在同一时间与同学们见面！2011微软实习生招聘的职位数量接近200余个，工作地点分布在北京和上海，涵盖了基础研究，软件开发，销售、市场和服务，技术支持等领域。具体的职位信息和技能需求请同学们登录微软的校园招聘网站进行查看！加入微软，加入IT精英的行列！微软期待与你携手创造更加辉煌的未来！-来源:南京大学小百合站http:/FROM:180.109.95.252上一篇本讨论区下一篇主题列表同主题阅读Net.Html.show(copyright)-CopyRight(C)1997-

14、2011,NJULilyBBS-Use HtmlParserTo get Tags ContentExtract Info by regexStore in a designed pattern EachpostwillbestoredinalineasthepatternblewEachpostwillbestoredinalineasthepatternblewClicktoaddTextURL/007hot/007auhtor/007title/007content SeeDemoCommon issuesFault Tolerance Network Problems Connecti

15、onTime Out3.3 Indexing Process3.3.1TargetFilterSourceFileBuildInvertedIndex3.3.23.3.3PartitionInvertedIndexFile3.3.53.3.4Second-LevelIndex(IndexforIndices)Target of Indexing ProcessRunaseriesofMap/ReduceoperationstogenerateInvertedIndiceswithrankandpositioninfo.Indexing ProcessTxt_FilterPartitionInd

16、ex TableInverted IndexIndexForIndicesFilter Source File(1)AlthoughSourceFilestorespostsinawell-designedpattern,WestillneedtofilteritbeforewedotheInvertedIndicesjob.1.Examine and eliminate noises and duplications -“http:/ null 007 null 007 null 007 null”-About duplications2.It is natural to pre-proce

17、ss the data before we really handle it.ReasonsFilter Source File(2)-Pseudo Code(1)publicclassFilterMapperextendsMapperpublicvoidmap(LongWritablekeyin,Textvalin,Contextcontext)/If the input line is has a legal structure emit it with its URL as key and itself as valueif(IsLegal(valin.toString()Textkey

18、out=newText(GetURL(val);context.write(keyout,valin);publicbooleanIsLegal(Stringval)/check whether the input lines structure is legal;/If legal return True,else return false;PublicStringGetURL(val)/returntheURLpartoftheinputline;/splittheinputlineby007andreturnthefirstpart.publicstaticclassFilterRedu

19、cerextendsReducerpublicvoidreduce(Textkeyin,Iterablevalsin,Contextcontext)/A sign denotes whether the post with certain URL has been emittedbooleanflag=false;for(Textval:valsin)if(flag)break;elsecontext.write(NullWritable.get(),val);flag=true;Filter Source File(2)-Pseudo Code(2)Build Inverted Index

20、TheprocessofbuildingInverted Indexissmart,itwillbesmarterifwecancalculateandrecordpostinginfoatthesametime.Thepostinginfoincludesrank、positions etc.DetailsBuild Inverted IndexPosting Info1.TF-IDF(Term Frequency-Inverse Document Frequency):2.Positions info do not need any calculation,the can be recor

21、d as a Integer Pair like(StartIndex,EndIndex).Posting Info|D|:totalnumberofdocumentsinthecorpus:numberofdocumentswherethetermtiappears(thatis)Build Inverted Index-structure1.Foreachpostinfilteredsourcefile,theoffsetinthefilecanbeconsideredasitsDID;2.EachlineofInvertedIndexfilestoresatermwithitsinfo,

22、thedetailsareasblew:term infoinfo=SingleDIDInfo;SingleDIDInfo;SingleDIDInfo.SingleDIDInfo=DID:rank:positionspositions=position%position%position%position.position=IsTitle|start|endEg.黑莓48522292:162.6:1|2|4%0|804|806;42910773:106.26:0|456|458%0|560|562/weneedtocustomizeanewWritableformattorepresenta/

23、termsInfopublicclassSingleRecordWritableimplementsWritableComparableprivateLongWritableDID=newLongWritable();/DIDprivateFloatWritablerank=newFloatWritable();/RankprivateTextpositions=newText();/Positions.Build Inverted Index-Pseudo Code(1)publicclassMapperextendsMapperpublicHashMapTokenMap;/TMP Info

24、publicvoidmap(LongWritableoffset,Textval,Contextcontext)Stringstr=val.toString().split(007,5);/Split post to get title and contentHandleToken(str3,true);HandleToken(str4,false);/store lines terms in TMP Info this.EmitMapValue(key,context);/After scaned the whole text,emit key and value/Handleinputli

25、ne:segementintowords,handlethewordsonebyone.publicHandleToken(Iine,IsTitle)while(line.hasnext()if(TokenMap.contians(line.GetTerm()TokenMap.Update(line.GetTerm();/if TMP dont contains the word put in TMP elseTokenMap.Put(line.GetTerm();/Update the terms info in TMP.publicvoidEmitMapValue(LongWritable

26、key,Contextcontext)for(Map.Entryentry:TokenMap.entrySet()context.write(word,singleRecord);/emit the key/value pair one by oneBuild Inverted Index-Pseudo Code(2)publicclassLineIndexerReducerextendsReducer/reduces input key is a term,input value is a List of Infos that/contains the same term,each info

27、 represent a Doc.publicvoidreduce(Textkey,Iterablevalues,Contextcontext)StringBuilderInfo;for(SingleRecordWritableval:values)Info.append(ResetFinalRank(val,values.len)+;);out.set(info.toString();context.write(key,out);/The Num of doucment that a term shows is taken into account.publicStringResetFina

28、lRank(SingleRecordWritableVal,longTotalNum)Val.Rank=Val.Rank/TotalNum;returnVal.toString();Build Inverted Index-Pseudo Code(3)Partition Inverted Index FileAfter last step,we got the Inverted Index File.However,the file is so big.SourcefilesizeInvertedindexfilesize48M72.5M182M240M703M828MPartition In

29、verted Index File-Pseudo Code/this algorithm is simple,we just need to rewrite a/partitioner classpublicstaticclasssplitfilePartitionerextendsPartitionerpublicstaticintcount=0;OverridepublicintgetPartition(Textkey,Textvalue,intnumPartitions)intpartition=(this.count%numPartitions);this.count+;returnp

30、artition;Second-Level Index(Index for Indices)In last step,we partitioned the Inverted Index file into a certain num parts,for example 16.Each file contains some term-info pairs.So,when a term is given?How can we know which part-file is it in?which line is it in?We need an Index for Indices.Ps.This

31、really works.The second-level index files size is less than 10%of the source file.Second-Level Index(Index for Indices)SourcefilesizeInvertedindexfilesizeSecond-LevelIndexfilesize48.1M72.5M2.375M182M240M5.17M703M828M10.5M3.4 Set up Web Retrieval Interface3.4.1Target SortPagesTechnics3.4.23.4.3Target

32、 of Web Retrieval InterfaceMakeanInterfacewhichaccpetusersqueryandresponsesearchresults.1.Restrict the query string;2.Sort search result dynamically;3.Response results page by page.Web RetrievalInterfaceSort PagesTerm0Term2Term1Here is a demo.Doc1 10Doc3 90Doc7 20Text in hereQueryStringWordSegementD

33、oc2 20Doc7 80 Doc5 15Doc3 05Doc2 40Doc6 40MergeRankAgainDoc7100Doc395Doc640Doc240Doc515Doc110Merge the rank and Rank againTechnicsJavascipt+HTMLTomcat+ServletWorkinclient.restrictinput,submitform,splitpageSome technics used in Web InterfaceWorkinServer.listernforrequest,handlerequest,feedbackrespons

34、e.3.5 Optimizationa)Foreachtermonlytop1500DIDarereservedatmost.b)UseTreeMaptosort.Reduce Sort TimeReduce I/O operationsCache StrategyOptimization measures in different areas.a)ResponsePageiscreateddynamically.b)Eachtimereturn10records.a)PutsomehotInvertedIndexfileinthememory.b)Cachereplacement-LRUCo

35、ntentsBackgroundBrief IntrotoprincipleofFullTextSearchEngineImplementofFTSEforBBSLilyMaybeGoogle&Baiduhasdonethese.Conclusion4.Maybe Google&Baidu has done.ParallellyWordSegementUsers queryRank3.Abetterrankstrategy:TodescirbetherelationshipbetweenatokenandDIDprecisely4.Recordeachusersquerystring;a)fe

36、edbacktoWordSegementb)Provideremindfunction.(Byinputchangeevent)1.SearchStuffparallelly2.AnOutStandingWordSegementAlgorithm.ContentsBackgroundBrief IntrotoprincipleofFullTextSearchEngineImplementofFTSEforBBSLilyMaybeGoogle&Baiduhasdonethese.Conclusion5.ConclusionSummary5.15.25.3HighlightsAboutMap/Re

37、duceSummaryCrawlerIndexingprocessWeb retrievalA Hard Coding Crawler and Miner,aimed to get data for BBS lilyThe indexing process runs as a sequence of MapReduce operations.Set up a Web Interface for userto retrieve info.CrawlerWeb InterfaceIndexingprocessRelatedWorkhasthreepartsasblew:HighlightsThis

38、stuffisCOOLIt can provide a friendly User Experience,when we wanna search something in our BBS Lily.UseMap/Reducetoprocessdataoffline.Ithasprovidedseveralbenefitssuchas:1.The indexing code is simpler,smaller,and easier tounderstand.2.we can keep conceptually unrelated computations separate.3.The ind

39、exing process has become much easier toOperate and maintain.View of ApplicationView of Technics1Map/Reduce is not just a Programming Model,actually its also a Life ModelClick to add TextAbout Map/ReduceMany thanks toTeacher Huang;Yang Xiaoliang;Xiao Tao;Liu Yulong;Zhang Lu;Demonstrate the systemLOGO