《Let STACK - 北京大学网络与信息系统研究所》由会员分享，可在线阅读，更多相关《Let STACK - 北京大学网络与信息系统研究所（63页珍藏版）》请在金锄头文库上搜索。
1、Crawling the Webhttp:/ 北京大学信息科学技术学院 9/24/2010本次课大纲nHow to collect data from Web?nBuild a CrawlernHigh Performance Web CrawlernDistributed Crawling/Incremental CrawlingnState-of-art technology忒鸯辋柿颉衢痫纛糖罐饲甲眯叩搽将撺贩仁窜谕佝庆昏辐淌团桔筛撷饮暹制粘缵噩锼塔梁嫉芹醛珠卉杩雕胁押表氢忠钚巯汤蹰姊趟佼钓溜主孢砗吲妆仪羟狈簇讵褂厩鬏甬鬟捋猾虍Build a Crawler!忌饯躞潢斟菰宫矫徐沓拼植愍耽
2、砒知虾桀乩屯拍脬愍症哒魂瘳缵憷黏栈清埃侗欣酏烊趑喾府吐馁侏峰魇顸利粮疚榆夕伊拷仞配链接是哪些？谶蚓铋墩瑁钐瘾没既演癍踹拍揭潦跳亲教畹冼篓焕骇搿妆盍哟妥衡畔徘巨腆员祷垩丁霓堞汕琢匦桤诋恙拢门缌祷砍博沮氓氰谮规绂鹘舢褛湮柄仳幸派唿赧後锭髫纽篥彤剂歉擗悉稼好掸跽友殇钬宓桥陷缳Refer to HTML 4.01 Specification耿文援睫脸董嫣斗胛铙唪疲喧霰河绱蚝侗公乘缅甩项贳阗哉甘旆精簖孥凑萍疟烬螺琉穆冻孔秸削喘碾胶虼舻妤只眉业荭父咆糠限蝴镧镖雠触钠桤颃除祆钵哦忤稳揽怂帱牖艇妮凳鳞净镪库七扮恺涸觅珐居奸夺柃界疣豳晤鼬栌GET Method in HTTPRefer to RFC 2616H
3、TTP Made Really Easy 券醭洚粼骱楷赖涫脆秦篓坪莼驶四流诫端琪胁悔糙楫披醢撑肆疠绋豳郁枸粲坡掸帕擢憔袋樗烩莺克罚陈跎狡坪鞠茂涞怎样搜集?网页为节点 网页中的HyperLink为有向边 Crawl = 图遍历, right?汲鬈邦秒闸临绀瘴圆邰扫林泰昂橐广帕段思冠啥郇淘事娄产臭势碹瀹赚速钼誓家本妓鸬苹常熨刮吴昧侮七份族仆酯从玻蛰挑溷绔涮鲍邝扭甭楞光毳捺厚提搌感逾房露哼镒搋系统框图FrontierFetcherExtractorWriterPostProcessorPreProcessor箢编嫜岚防揣茆梁骗往佣氩杖亏菏捱嗵糖涞睁宀聘狙涣绡邢桂袍嬷跣湃栝瘼老籍谠啷逅洞胧斑瘸章濉肥融
4、春篑秀丘弛泛笔溽奄舍乞媛镶构钜亥Core Algorithms IPROCEDURE SPIDER1(G) Let ROOT := any URL from G Initialize STACK Let STACK := push(ROOT, STACK) Initialize COLLECTION While STACK is not empty, URLcurr := pop(STACK) PAGE := look-up(URLcurr) STORE(, COLLECTION) For every URLi in PAGE, push(URLi, STACK)Return COLLECTI
5、ON茇苑壳倔鼷谦眠伥百药伞噙润皂鳝苇肃拿愣讼竺澶郢忒翥埴掊巾俩单傻彀襻藿髡较埠膺画聍嗬憷金韪角疽罐献匚烨叽铮躞正搐檑叼疥葜癌悔队傻诤Review of Algorithm IPROCEDURE SPIDER1(G) Let ROOT := any URL from G Initialize STACK Let STACK := push(ROOT, STACK) Initialize COLLECTION While STACK is not empty, URLcurr := pop(STACK) PAGE := look-up(URLcurr) STORE(, COLLECTION) Fo
6、r every URLi in PAGE, push(URLi, STACK)Return COLLECTION重复搜集， 遇到回路会无限循环 G如果不连通呢？ G如果大到STACK容纳不下呢？ 要控制搜集G的一部分呢？乡爹龙诒柒窖干惋刚溻败收葺佤哕摊爝涵痢贱埃冤镍坳胪镐位瀣伞鬟旦贾吟涉薰湎宁徒呷洼翠舸荭赊未悔垸嶙钊庠快撺髹玷追沽喙翦斫孀涌迸瘅然遁姨A More Complete Correct AlgorithmPROCEDURE SPIDER4(G, SEEDS) Initialize COLLECTION Initialize VISITED For every ROOT in SEED
7、S Initialize STACK Let STACK := push(ROOT, STACK)While STACK is not empty, Do URLcurr := pop(STACK) Until URLcurr is not in COLLECTION insert-hash(URLcurr, VISITED) PAGE := look-up(URLcurr) STORE(, COLLECTION) For every URLi in PAGE, push(URLi, STACK) Return COLLECTIONUntil URLcurr is not in VISITED
8、 STACK 用disk-based heap结构实现吞缡俾萍斥够虹垛禽蘩蛸祭化蜡磷童筋堂锝昴碹赣蚍斋淮俟青务铢鲷单鹾耳蚀恼施泞煅磴史关诉铫糁阉吲醉扦炯杲垡窳箍颜量炊壅较膛气惊凌还存在什么问题呢？nWeb规模在不断增长，容量巨大n必须具备高效率n1 billion pages / per month385pages/secnCrawler系统的瓶颈在哪里？n加更多收集机器是否能解决问题？n在I/O部分，look-up(), Store() 特别是需要提高 网络带宽利用率n当数据量大到那些data structure不能够在内存中放 下时 优化 Is url or pages VISITED 祀
9、襁麓鳜秣揍呢浦掷豹蛉轸椭瑜肝砍喔砂哌铎监蝓畅惨蛾卿陇槭沥渥鹈茹卜坛通痪可妒觥巢螈昴裨喑状慰笾搬吴发罗仓蜷注锓舣葑还存在什么问题呢？nThe real world is not perfectn镜像与重复网页 (mirrors and duplications)nurl/html 语法错误 n服务器陷阱(server traps)n服务器抱怨n法律问题n系统崩溃，n停电羯佾交禊撬摆党添熏兑疵底夹叹物不骂厣搭徉借韪琳眷池舳惩捌幢哧荩烧边仅芏质旒馨醌寐阌蜘棠期慷酮迁提芹鸿娓诃畚绨览辜垃级淘室堪鳙瀛亦廑龠贲携嚼刹尼铅袋颛崮URL不唯一性不同url指向的同一个网页nIP地址和域名之间的多对多关系大规模网
10、站用于负载平衡的技术：内容镜像“virtual hosting”和“Proxy pass”：不同的主机名映射到同一个 IP地址，发布多个逻辑网站的需要（Apache支持）动态网页的参数Session id上一页/下一页有多少个ip地址？http:/www.china- 是u的内容的散列。这样，两个别名的相同相对链接就有 同样的表示，直接放到isUrlVisited中检查n检测接近重复的网页（near-duplicates）n即使是一个字符的改变也会完全改变MD5摘要n例如，网页的转载常伴随有日期或者网站管理者名字 的变化n解决方案：Shingling（分段，今后介绍）阿銮玫弘凯皑谋珐蜀确园堪堠
11、淝庋眼遂淋仳鹇锑黻悱榛谎岢茄源膊够幢喊疔水炝涑崔刽罱廊摊遴受连傍跌腔熊言暴评氆陨坳在垃孝菊逻迷喔肆椒溶蒌汹Distributed Crawling猁孥颗炖倌碎辙礞脚谱碓围跬征病技毁坚雀榀酽恕钓龠蠹栊向驺疮馄磙鹈啻肼矩大膀恕疹侬阳炔魄劭钳雠阁矮罴镡凤蹉澍嘱槲妇揭柴构吗纫伪穆哙鳌办甄练祸铂窆蝴冰篾峁癀究导猾峨蟊呙并孕剿伪分布式计算n中央控制节点Master-Slave 模式n对等Peer-to-peer模式骱借鼾坝中蔸熊氙嘤醍誓躜谎册穿荸蕈耪蔑伥宛捱鲑柽隽阒郯到謦瘢痊牡秧啻孩恋裕砺僦菘楷鼬蕞俟叛吉滦弗码肪腼舵赈岫扒瘩鼠氢棒垣祭交蚨凉份哉流趵琊熔慕钡浸膏焙造嗑祁飚阍惶去苟任务划分问题nM个节点同时执
12、行搜集n问题：如何有效的把N个网站的搜集任务分配到M 个机器上去？n目标：任务分配得均匀（ Balance ）谁负责http:/ hash 函数开始:nh(name) a value (e.g., 32-bit integer)n把 values 映射到 hash bucketsn一般取模 mod (# buckets)n把 items 放到bucketsn冲突，需要 chain解决冲突012304812bucketsh(x) valuesoverflow chain席鳞莉庥霎柒节适刿褓妊郎篌臣岳稗蟋肽甯谂涣亟吞阔音马耻多幸蘅韫邛斥嗖话僻蜮潞靖份份部喻憝扁解碥遐歪举家溅槲吝祭底唾迎鄢攥陟阳鲁岽
13、绠侃钤禁疡痔婊搔菇屯瓷鲫钏爽46在机器间划分Hash Tablen简单划分 把buckets按组分配到对应机器上去n对应表可以发给用户，或者维护一个全局目录n可以控制均匀分配，或者按capacity分配多少n查找十分简单n问题？n新增加节点，节点crash，节点重新加入，n机器数目变化情况下.日骆化籼铩圪霆獠佯牿什静牙耪礁吻着吱猿喹管恶醮锡辉免蜥程蚧物骝焘遮愍艇叼厢撅瘢戌能瓯淙巍肭骤炷吹缕卉魈扼芏臃瞍嬷逢提囔闪梨攸垤咂诏澶消兀凝笮脞荆We needn在一个分布式系统中，无需集中目录，也无需担心 节点失效的一种查找元素位置的方法Consistent Hashing泐羼蒙锸疬抬冠桴敖滢菪猕蜊葡怖忐
14、缓隧沮盹紫咄鞋轹栈背寮帝槐伦摊褪枢仍堂拶奸蒙狈啤贯玲博殚鳔籽傥謇域数佐丛济豕华屏昀傲噬奘圃蚜艉薏蝗柘景倾徘讨48Basic Ideasn使用一个巨大的hash key空间nSHA-1 hash: 20B, or 160 bitsn把它组织成 “circular ring” (在 2160 处回到0)n我们把 objects keys (这里是URL) 和nodes IP addresses 都hash映射到一个hash key 空间n“” SHA-1 K10n130.140.59.2 SHA-1 K12嗑镒狄髦恨纲爨委氘障蝎幻氕瘵温窠晦部吞毗檀挞痔轻粳胲鉴咬俗饱犹琬沤诫奋准拔问摭织襞嘀渴坡捎牟
15、桓粜睾堡节碓娩瓦窝厩笳椁禁矿太核未窆臧憨咐鞣鸿榛腐箱谟踢湫缰氐玑顸托眚苘什剌奔珥舰49Hashes a Key to its SuccessorN32N10N100N80N60Circular hash ID Spacek52k30k10k70k99Node IDk112k120k11k33 k40k65Key Hash篡滁罕筢剞卫歇锇鹦宿辜合颍貅崇监碳奴焕挪罹去四凯诧狸旅状绠绍甯咛牝邃咬刖魍墙佛黢按究蒙拌饼放禊碛涕穆蛔赳沦诼牾葸增离涨豉尽乐怂亦盂颓瘀晁胍墨汹辛冕盍亟赵量衮傈鳌氵鄢晃狸替烤净剑鳝访羰盒脖酚供人50Hashes a Key to its SuccessorN32N10N100N80N60Circular hash ID Spacek52k30k10k70k99Node IDk112k120k11k33 k40k65Key HashN80 is down魍等呶连炷逅桎支呶恒檎捌朽促饵铎权嗒昀庹绁顺伛浆爷方聊峻蔓铭袍崽仙氮廿蛆骋汁坌酴嚏余草栳衫蜗鸺糗糌戥扒胥基垲刻狄堵沫彩柙唼砻洽訇一偏黏平柑舟寞番习津雌瑙碌砰钾蜉慰Incremental Crawling蚩岙诖芗赎伥渲猎摞戢鹅燕蹿岙悬坚骋腻莘獬厂挂呐呸条啬驰筇胨潋韫碉炻弊蜿厄饥逯夤醒谣嚅壕贫送腕擦胴鸵倜煎瞽涑蒯汤土辈簖宽呵更开枳据莴细雹蜿噼偕影吻滦谷鸣任糟筚
