（计算机应用技术专业论文）基于chord的邮件nilsimsa摘要处理平台的设计与实现.pdf

摘要 摘要 传统的垃圾邮件过滤技术利用邮件过滤器独立工作，所能获得的垃圾邮件 信息较少，效率较低。分布式垃圾邮件过滤技术通过网络交换邮件信息来更加 准确地识别垃圾邮件，能够很好地利用垃圾邮件分布的全局特性。该技术对垃 圾邮件具有较好的识别能力，正逐渐成为研究热点。 n i l s i m s a 摘要算法在分布式垃圾邮件过滤技术中占有重要地位。传统的基于 n i l s i m s a 摘要的邮件过滤系统主要采用集中存储和查询的方式来处理n i l s i m s a 摘要数据。这种方式带来了单点失效的问题，导致系统的健壮性和可扩展性不 高。d h t n i l 提供了一种在基于d h t 的结构化p 2 p 网络上进行n i l s i m s a 摘要发 布和相似性查询的方法。该方法突破了传统的n i l s i m s a 摘要总是集中处理的缺 陷，使得系统更具扩展性，为构建全分布式的邮件过滤系统提供了理论支持。 论文在d h t n i l 的研究基础上，首先详细分析了结构化网络c h o r d 的相关路 由算法，并对基于c h o r d 的协作文件系统c f s 进行了研究，然后设计了基于c h o r d 的分布式n i l s i m s a 摘要数据处理平台，实现了n i l s i m s a 摘要在全分布式网络上 的发布和相似性查询，为实现分布式邮件过滤系统提供了底层框架。 最后，论文进一步设计并实现了摘要数据的持久化存储和摘要数据的动态 维护，通过冗余数据的存储在一定程度上解决了p 2 p 网络中节点抖动性带来的 影响，保证了系统的正确性和健壮性。 关键词：n i l s i m s a ，c f s ，d h t ，c h o r d ，分布式邮件过滤系统 a b s t r a c t ab s t r a c t m o s to ft h et r a d i t i o n a ls p a mf i l t e r sf u n c t i o no nas i n g l ec o m p u t e r , s ot h e yc a l l o n l yo b t a i n l i m i t e di n f o r m a t i o na n dt h e e f f i c i e n c yi sq u i t el o w e r d i s t r i b u t e d a n t i s p a mt e c h n i q u ee x c h a n g e sm e s s a g e st h r o u g ht h eo v e r a l ln e t w o r ki n f o r m a t i o nt om o r e a c c u r a t e l yi d e n t i f ys p a m ，c a nm a k eg o o du s eo ft h eo v e r a l ld i s t r i b u t i o no fj u n ke - m a i lf e a t u r e s ， t h i st e c h n i q u eh a sab e t t e ra b i l i t yt oi d e n t i f ys p a m ，a n di ti sg r a d u a l l yb e c o m i n gar e s e a r c h h o t s p o t n i l s i m s ad i g e s ta l g o r i t h mp l a y sa ni m p o r t a n tr o l e i nd i s t r i b u t e da n t i s p a m t e c h n i q u e t r a d i t i o n a le - m a i lf i l t e r i n gs y s t e mb a s e do nn i l s i m s ad i g e s ta l g o r i t h m m a i n l yu s e sac e n t r a l i z e da p p r o a c ht op r o c e s s i n gn i l s i m s ad i g e s t s t 1 1 i sa p p r o a c h h a s b r o u g h tt h ei s s u eo fs i n g l ep o i n to ff a i l u r e ，t h es y s t e mr o b u s t n e s sa n ds c a l a b i l i t yi s p o o r d h t n i li sa na p p r o a c ht op u b l i s ha n dl o o k u pf o rn i l s i m s ad i g e s t si nd h t t l l i s m e t h o db r e a k t h r o u g h st h es h o r t c o m i n g s ，a n dm a k et h es y s t e mm o r es c a l a b l e b a s e d o nt h i sa p p r o a c h ，w ec a nd e s i g nd i s t r i b u t e ds p a mf i l t e r i n gs y s t e mo ns t r u c t u r e dp 2 p n e t w o r k s i nt h i sp a p e r , b a s e do nt h er e s e a r c ha b o u td h t n i l ，w ea n a l y z e dt h er o u t i n g a l g o r i t h mo fc h o r da n dt h em e c h a n i s m so fc f si nd e t a i l t h e nw ed e s i g n e da d i s t r i b u t e dd a t a p r o c e s s i n gp l a t f o r mb a s e do nn i l s i m s ad i g e s t w ea c h i e v e dt h e r e l e a s ea n ds i m i l a r i t yq u e r yo fn i l s i m s ad i g e s to nd i s t r i b u t e dn e t w o r k , p r o v i d e dt h e u n d e r l y i n gf r a m e w o r kf o rt h er e a l i z a t i o no ft h ed i s t r i b u t e de - m a i lf i l t e r i n gs y s t e m f i n a l l y , w ed e s i g na n dr e a l i z ep e r s i s t e n t d a t a s t o r a g e a n dt h ed y n a m i c m a i n t e n a n c eo fd a t a b a s e do nr e d u n d a n td a t as t o r a g es o l u t i o n , w es o l v e dt h ei m p a c t o f j i r e ri nt h ep 2 pn e t w o r kt oe n s u r et h es y s t e m sc o r r e c t n e s sa n dr o b u s t n e s s k e yw o r d s ：n i l s i m s a ，c f s ，d h t ，c h o r d ，d i s t r i b u t e ds p a mf i l t e r i n gs y s t e m i i 南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位获 得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文( 包 括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论文， 并编入南开大学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可以将公开 的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检索、文 摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开大学向教育部 指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息研究所和中国学 术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文数据库， 通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h t m 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答辩； 提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字： 2 0年月日 南开大学研究生学位论文作者信息 论文题目 姓名学号答辩日期年月日 论文类别博士口学历硕士口 硕士专业学位口高校教师口 同等学力硕士口 院系所专业 联系电话e m a i l 通信地址( 邮编) ： 备注： 是否批准为非公开论文 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外；本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年月日 第一章引言 第一章引言弟一早i 苗 第一节研究背景 根据中国互联网络信息中心( c n n i c ) 0 9 年1 月发布的第2 3 次中国互联 网络发展状况统计报告i t 】，我国网民规模已经接近3 亿，较2 0 0 7 年增长4 1 9 ， 互联网普及率达到2 2 6 ，略高于全球平均水平( 2 1 9 ) 。这是继2 0 0 8 年6 月中国网民规模超过美国，一举成为全球第一之后，中国的互联网普及再次实 现飞跃，赶上并超过了全球平均水平。从以上数据可以看出，我国上网用户增 长迅速，互联网正日益成为社会生活中不可缺少的组成部分。 随着互联网的快速发展和普及，电子邮件( e m a i l ) 也因为它方便、快捷和 低成本等特点而深入人们的生活，成为人们互相交流、获取信息的重要渠道。 然而，人们在享受电子邮件带来的极大方便的同时，也在不断忍受垃圾邮件的 骚扰。根据中国互联网协会反垃圾邮件中心公布的2 0 0 8 年第三次反垃圾邮件 报告 2 1 ，中国网民平均每周收到垃圾邮件的数量为1 7 8 6 封，与去年同期相比， 增加1 1 7 封，增幅为7 0 ；中国网民平均每周收到垃圾邮件的比例为5 7 8 9 ， 与去年同比上升了2 0 4 个百分点。垃圾邮件内容主要涉及到零售业推销、旅游 交通业推销、违法出售票据证件等方面。 垃圾邮件的发送是低成本的，但给人们带来的危害却是巨大的，主要表现 在以下几个方面：占用网络带宽，造成邮件服务器拥塞，降低整个网络的运行 效率；侵犯收件人的隐私权，侵占收件人的信箱空间，耗费收件人的时间、精 力和金钱；被黑客利用，成为攻击工具，垃圾邮件还可以被病毒利用，成为它 们的传播途径；使国际形象受损，如2 0 0 1 年，国外邮件服务商封杀中国邮件服 务器i p 地址事件；对网络安全形成威胁，扰乱社会秩序。 虽然传统的反垃圾邮件技术包括客户端过滤、服务器端过滤和防火墙等技 术方案在一定程度上遏制了垃圾邮件的传播。但是，它们都是一种独立工作方 式，不能通过互联网与其他邮件过滤器共享垃圾邮件信息，因此所能获得的垃 圾邮件信息较少，效率较低。同时，随着垃圾邮件发送技术的发展，垃圾邮件 内容不断变化，传统的垃圾邮件识别方法存在着适应性差、准确性低、灵活性 第一章引言 差和资源消耗大等缺陷。因此如何将各种邮件过滤技术的优点结合起来，特别 是研究一种具有自适应、主动性和分布式的邮件过滤技术具有重要的意义和实 用价值。 第二节当前的解决方案 随着垃圾邮件问题的日趋严重，垃圾邮件过滤技术也在不断发展并在一定 程度上有效地遏制了垃圾邮件泛滥的趋势。这些技术按照过滤方法的不同，可 分为基于黑名单白名单的邮件过滤、基于规则的邮件过滤、基于邮件行为的邮 件过滤和分布式邮件过滤。 黑名单过滤技术【3 】是将那些垃圾邮件服务器i p 地址( 通过技术或人工手段 经过确认的) 列入一个黑名单，通过定期或实时发布这种黑名单、并提供黑名 单查询服务，让合法的邮件服务器知道应当拒收那些邮件源所发来的邮件。这 种技术在某种程度上可以减少垃圾邮件的危害，但很难达到时效性，是一种“亡 羊补牢”的被动防御方法。 白名单过滤与黑名单过滤相反，是指收录了邮件接收者确信的邮件地址信 息，凡是属于白名单的邮件都被判定为合法邮件。但是这些方法的主观性会造 成大量合法邮件的误判和垃圾邮件的漏判。 基于规则的过滤方法1 4 通过训练得到显式规则，其训练学习的过程实际上是 归纳总结的过程，通过考查每个训练样本，归纳总结出其中规律性的东西来形 成规则，然后设置一些规则，只要符合这些规则的一条或几条，就认为是垃圾 邮件。这些规则通常有信头分析、群发过滤、关键词精确匹配以及邮件内容中 的其它特征。规则方法的主要优点是可以生成人类理解的规则，缺点是需要人 们不断去发现和总结、更新规则，人为因素较多，一些没有经验的用户可能很 难提供有效的规则。而且，手工制定规则比较耗时，准确率也受到了限制。随 着时间的变化，垃圾邮件的特征也在变化，让用户维护这些规则也不是一件易 事。另外，这种过滤方法在规律性不明显的应用领域效果较差。 基于邮件内容过滤是指对邮件内容进行扫描，采用自然语言理解相关技术 对邮件进行分类，即将待过滤的邮件分为垃圾邮件或正常邮件，这就是将垃圾 邮件过滤与文本分类和信息过滤等技术结合起来，基于概率理论相关技术，将 文本分类和信息过滤中常用的方法引入到垃圾邮件过滤t 3 j 。目前，在邮件分类 2 第一章引言 领域中使用的分类算法主要有贝叶斯方法【5 1 、k 近邻方法 6 1 、支持向量机川、神 经网络【8 j 等。其中，贝叶斯方法以其良好的分类准确性，分类速度成为应用最为 广泛的方法。 基于邮件内容的过滤技术由于其对文本的良好处理效果在反垃圾邮件领域 发挥着重要作用，但其过滤的准确性主要依赖先期收集的垃圾邮件和正常邮件 样本集，因此该技术具有滞后性特征，新的垃圾邮件很容易突破过滤规则的检 测。此外该技术受训练数据集的限制，在准确率和查全率方面也难以达到令人 满意的程度。 基于邮件行为的过滤技术是指根据邮件发送的行为特征判断该邮件合法性 的过滤技术，这是一项比较新的邮件过滤技术。s t o l f oa 1 通过研究实现了e m a i l m i n i n gt o o l k i t 9 1 ，通过利用社会网络分析以及结合用户行为特征来检测病毒或蠕 虫型电子邮件。s t e v e m a r t i n 1 0 1 和p r a s a n n ad e s i k a n u 1 提出了通过分析邮件服务器 端发送出去的电子邮件流的行为特征来过滤垃圾邮件的方法。 目前国内有些安全厂商相继推出了基于行为识别技术的防垃圾邮件网关。 北京天融信公司针对大量的垃圾邮件样本进行了统计分析，并根据r f c 8 2 2 标 准建立了垃圾邮件发送的行为识别模型，能够在m t a ( m a i lt r a n s f e r a g e n t ) 通 信阶段就判断所接收的邮件是否为垃圾邮件，不需要接收全部的邮件内容进行 相应的内容匹配i l2 。 分布式垃圾邮件过滤技术是由多个垃圾邮件过滤器组成的垃圾邮件过滤网 络，各个过滤器之间通过网络交换邮件数据以更加准确地识别垃圾邮件。由于 通过多个过滤器所积累的垃圾邮件数据非常丰富，能够很好地利用垃圾邮件分 布的全局特性。因此，分布式邮件过滤技术对垃圾邮件的识别能力比较高。目 前，分布式邮件过滤技术正是研究热点，许多学者和反垃圾邮件研究机构已参 与到此研究领域中【1 3 - 1 9 1 。 由于垃圾邮件总是具有大量的副本或变体，分布式过滤方法利用这一特征， 在邮件服务器处将收到的新邮件作摘要并与已知垃圾邮件的摘要作比较，如果 与已知垃圾邮件( 通过某种自动检测机制或用户的反馈行为来获得) 的摘要相同 或者高度相似，则标识其为垃圾邮件，否则为合法邮件。 m e t ( 1 3 j ( m a l i c i o u se m a i lt r a c k i n g ) 项目属于c s 框架，它由哥伦比亚大学 创建。它包含m e t 客户端和m e t 服务器，其中客户端运行在邮件服务器上， 提取邮件的附件信息，并为该邮件计算一个唯一的校验和，最后形成报告并发 3 第一章引言 送给m e t 服务器。m e t 服务器接收m e t 客户端发送的报告，并对报告进行统 计，如果该校验和在一定时间内超过某一个阈值，则将相应的记录发送给客户 端。m e t 缺点在于缺乏全局统计功能，而且不能识别相似邮件。s p a m n e t t l 4 】使 用一个中心目录服务器储存和共享已知垃圾邮件的摘要，它的中心服务器有可 能成为系统的单点失效点。d c c ( d i s t r i b u t e dc k e c k s u mc l e a r i n g h o u s e ) 工程【1 5 】 开始于2 0 0 0 年，d c c 服务器统计各个客户端提交的校验和，并应答该校验和在 整个系统中出现的频率；d c c 客户端工作在邮件服务器上，它负责提交校验和， 同时查询该校验和出现的频率，如果该校验和超过某个阈值，则判定当前邮件 为垃圾邮件。d c c 的缺点是通讯开销大、客户可以干扰系统运行。 m e t z g e r ”】等人与z h o u 1 6 】等人提出的分布式垃圾邮件过滤器都是基于p 2 p 网络。m e t z g e r 等人将单机的文本分类过滤器与m u l t i a g e n t 系统结合起来提出了 一种新的垃圾邮件过滤器，在该过滤器中，客户端( a g e n t ) 接收到的邮件被支 持向量机( s v m ) 分为垃圾邮件和正常邮件两类，然后各个客户端之间互相交 换这些邮件的序列号( i d e n t i f i c a t i o n n u m b e r s ) ，使得垃圾邮件数据可以被其他客 户端利用。该方法最主要的缺点在于垃圾邮件数据必须被存放在各个客户端上， 因此，垃圾邮件数据的数量受到限制，并且垃圾邮件数据的传输效率也非常低。 z h o u 等人提出的方法是基于a p p r o x i m a t ed o l r 工作的，a p p r o x i m a t ed o l r 提 供了在p 2 p 网络上查找最相近数据的功能。该过滤器储存用户对垃圾邮件的反 馈，并将这些数据在p 2 p 网络上共享，通过查找与要辨别的邮件最相近的垃圾 邮件数据便可以辨别该邮件是否为垃圾邮件。由于需要用户的反馈，该过滤器 不是自动化的，并且a p p r o x i m a t ed o l r 中相近对象的大小与它所包含的垃圾邮 件数据有关，可能在某些情况下急剧增加，因而该过滤器的数据传输效率较低。 e d a m i a n i 在文章【r 7 l 中提出了n i l s i m s a 1 8 j 摘要算法，n i l s i m s a 是一种本地敏 感的哈希函数，它以一个文档作为输入，输出一个n 比特的摘要值。e d a m i a n i 详细分析了n i l s i m s a 在反垃圾邮件应用中的参数选择、准确性、安全性等具体 问题，并证实了它的有效性。在文章【l 刿中e d a m i a n i 提出了一种基于n i l s i m s a 摘要算法的分布式垃圾邮件处理系统。 相关的研究和实践【2 0 】 2 1 1 已经证实了n i l s i m s a 算法在垃圾邮件识别中的有效 性。但n i l s i m s a 摘要的发布仍存在问题，由于n i l s i m s a 摘要的特殊性，n i l s i m s a 摘要主要采用集中存储与查询的方式，即使采用分布式处理的反垃圾邮件系统， 其n i l s i m s a 摘要的存储与查询也需要集中处理。另一方面，邮件的n i l s i m s a 摘 4 第一章引言 要的数量非常庞大，而查询与比对方法又不能采用排序等简单的处理方式，因 此，n i l s i m s a 摘要集中处理方式的可扩展性很差。 d h t n i l 2 2 1 是一种基于d h t 网络的邮件n i l s i m s a 摘要发布与查询方法，它可 以比较简单的将n i l s i m s a 摘要发布在对等d h t 网络的节点之上，并可以进行有 效的查询。d h t n i l 使用摘要向量空间划分的方法将摘要简单地发布到各个节点 上，使得摘要在系统中的发布、查询、和存储都是分布式的。d h t n i l 突破了传 统的n i l s i m s a 摘要总是集中处理的缺陷，使得系统具有更大的扩展性。仿真实 验验证了d h t n i l 的发布和查询方法的有效性。针对随机数据，d h t n i l 可以保证 每组相似邮件的发布只涉及不超过3 的子空间，近似查询中搜索3 5 的子空间 就可以查询到8 0 以上的相似邮件；而针对i n t e m e t 上采集的数据，搜索1 的 子空间就可以查询到8 5 以上的相似邮件。 第三节本文研究内容 目前应用广泛的垃圾邮件过滤技术始终没有跳出对邮件内容进行检查与分 析，仅仅是对孤立的词语进行匹配，抛弃了连贯性，从而会造成邮件的大量误 判，同时，基于邮件内容的过滤技术需要进行大量的匹配运算，对c p u 和内存 的占用极高，这样就很容易成为处理瓶颈。为了解决此问题，国内外许多反垃 圾邮件厂商推出了垃圾邮件行为识别技术。虽然能够获得较好的效果，但是他 们都是单机工作，所能获得的垃圾邮件信息较少，效率较低。分布式垃圾邮件 过滤技术正成为目前研究热点，国外在这方面已有比较深入的研究，并且取得 了不少的研究成果，而国内在这方面的研究还相对较少。 d h t n i l 在理论上证明了在d h t 网络上进行n i l s i m s a 摘要处理的可行性和邮 件过滤的效率。d h t n i l 将n i l s i m s a 摘要直接分发在整个网络上，采用多维空间 划分的方法，使得相似的摘要数据在d h t 上呈现聚集态，并通过查询相似摘要 的数目是否大于某个阈值来判断邮件是否为垃圾邮件。 本文主要是依据d h t n i l 中提出的理论，利用c h o r d 作为底层d h t 网络结 构，设计并实现了适合n i l s i m s a 摘要数据分发的p 2 p 数据处理系统，即d h t n i l 数据处理平台。该平台主要实现了n i l s i m s a 摘要处理的存储，聚类和相似性查 询等功能，并为上层邮件服务器提供了相应接口，方便调用。为了保证系统的 健壮性和数据查询的正确性，我们利用c f s l 3 3 j 相关技术实现了摘要数据的动态 5 第一章引言 维护。本系统平台的实现可以为后续对d h t n i l 方法的网络开销、负载均衡、系 统效率等方面的研究提供平台，同时还可以为基于n i l s i m s a 摘要技术的分布式 邮件处理系统提供底层架构支持。系统设计和实现充分利用l i n u x 平台上的开源 技术资源，如提供远程过程调用的r p c 服务、用于简化事件驱动网络编程的 s f s l i t e 库【2 3 1 、提供高效存储的嵌入式d b 数据库等。 本系统平台作为基于信誉机制的分布式垃圾邮件过滤方法研究项目的一部 分，在前期项目组成员提出的d h t n i l 理论的研究基础上，对构建分布式的 n i l s i m s a 数据处理平台的原型系统进行了设计和实现，为后期项目组成员对系统 进行邮件处理的效率等性能分析提供了基础平台。目前项目组成员正逐步将从 互联网采集的邮件数据应用到该数据平台，以验证其处理垃圾邮件的有效性并 对系统性能进行分析。 第四节论文结构 本文共分为六个部分，具体结构如下： 第一章介绍了垃圾邮件泛滥的现状，已有垃圾邮件过滤技术的优缺点，以 及本文的研究内容和意义。 第二章首先介绍了p 2 p 的相关技术，主要介绍d h t 网络相关知识。然后对 c h o r d 路由算法进行了详细的分析和研究，接着对基于c h o r d 的文件存取系统 c f s 的架构和数据冗余方案进行了分析。c h o r d 和c f s 是本文系统实现的主要 基础。 第三章介绍了d h t n i l 的理论基础，详细介绍了d h t n i l 发布和相似性查询 方法的实现和相关的技术特点。然后对d h t n i l 数据平台的特性进行了分析。 第四章详细介绍了数据平台的设计目标，系统的应用环境以及系统总体结 构和各层的主要功能模块。 第五章首先分析了系统的部署和启动过程，接着对系统各层次模块的设计 和实现进行了描述，并对系统进行了测试和分析。本系统主要包括业务逻辑层、 c h o r d 服务层、数据库服务层和数据动态维护功能模块。 第六章对论文进行了总结，分析了本系统的特点，并提出了今后的研究方 向。 6 第二章p 2 p 相关技术 第二章p 2 p 相关技术 本文所设计的n i l s i m s a 摘要数据处理平台将建立在d h t 网络结构之上。多 篇文章对d h t 网络的可靠性、可用性、安全性进行了深入的研究，d a v i d 等在 文章 2 4 】中评估了d h t 网络的性能，e m i l 等在文章 2 5 】中探讨了d h t 网络的安 全问题和保护方法，j o s h 在文章 2 6 】中研究了d h t 的可靠性和健壮性问题。本 系统平台基于结构化的p 2 p 网络，采用了c h o r d 路由协议，系统的实现以c h o r d 和c f s 相关技术为基础。本章首先介绍了基于d h t 结构的p 2 p 网络，然后重点 分析了c h o r d 路由算法和c f s 文件协作系统。 2 1 1p 2 p 网络基础 第一节d h t 网络 p 2 p 网络，也称为对等网络( p e e rt op e e r , 简称p 2 p ) 。p 2 p 弱化了中心服务 器的概念，以用户为中心，使得客户机和服务器的功能同时出现在用户计算机 上。它是网络计算的一种新技术，p 2 p 将网络中不同的计算机系统连接起来，以 达到充分利用网络上存在的各种资源的目的。网络的参与者共享他们所拥有的 一部分硬件资源( 处理能力、存储能力、网络连接能力、打印机等) ，这些共享 资源需要由网络来提供服务和内容，能被其它对等节点直接访问而无需经过中 间实体。在此网络中的参与者既是资源提供者，又是资源获取者。 p 2 p 改变了传统的网络模式，它使用户积极地参与到网络中来，发挥用户计 算机的计算能力，为整个网络系统做出贡献。相比传统的c l i e n t s e r v e r 模式而言， p 2 p 具有良好的可扩展性、健壮性和高性价比等优点。 但是p 2 p 也有不足。首先，p 2 p 网络节点比较分散，不易管理。其次，p 2 p 网络中数据的安全性难以保障。另外，对等节点可以随意的加入或退出，会造 成网络带宽和信息存在的不稳定。因此在安全策略、备份策略等方面，p 2 p 的实 现要复杂一些。 7 第二章p 2 p 相关技术 根据拓扑结构的不同可以将p 2 p 网络分为四类：集中式拓扑( c e n t r a l i z e d t o p o l o g y ) 、分布式无结构拓扑( d e c e n t r a l i z e du n s t r u c t u r e dt o p o l o g y ) 、半分布式 拓扑( p a r t i a l l yd e c e n t r a l i z e dt o p o l o g y ) 、分布式结构化拓扑( d e c e n t r a l i z e d s t r u c t u r e dt o p o l o g y ) 2 7 1 。表2 1 中对这四种拓扑结构的优缺点进行了比较。 表2 1p 2 p 网络拓扑结构的性能比较 2 1 2d h t 网络特性 分布式结构化拓扑的p 2 p 网络都是在d h t e 2 8 1 ( d i s t r i b u t e dh a s ht a b l e ，简 称d h t ) 一维空间的基础上引入更多的拓扑结构图来反映底层网络的结构。每 个节点在系统中都有着唯一的节点标识。d h t 结构能够自适应节点的动态加入 和退出，有着良好的可扩展性、健壮性、节点i d 分配的均匀性和自组织能力。 d h t 提供精确的发现，发现的准确性得到了保证，其主要代表是c h o r d 2 9 1 、 c a n 3 0 1 、p a s t r y 3 1 1 和t a p e s t r y 3 2 1 。分布式结构化拓扑p 2 p 网络最大的问题是维护 机制较为复杂，尤其是节点频繁加入退出造成的网络波动会极大地增加d h t 的 维护代价。这种拓扑结构所面临的另一个问题是d h t 仅支持精确关键词匹配查 询，无法支持内容、语义等复杂查询。 分布式结构化拓扑结构的优势在于其搜索机制只需要较小的通讯开销，因 而在理论上有更好的可扩展性，但其最大的弱点是不支持模糊匹配和文本匹配 等复杂的文件查询方式。并且，基于d h t 的拓扑维护和修复算法比无结构p 2 p 的系统要复杂得多。目前，结构化p 2 p 的文件共享系统缺乏在i n t e m e t 中大规模 真实部署的实例，且鲜有成功应用的案例。即使是c h o r d 、c a n 、p a s t r y 等项目 也更多地用于动态性更低的大规模网络存储应用上，下面对这几个典型的d h t 路由算法做简要的介绍。 本文的系统基于分布式结构化拓扑网络c h o r d 来实现。c h o r d 在2 0 0 1 年由 8 第二章p 2 p 相关技术 麻省理工学院提出，其核心思想就是要解决在p 2 p 应用中遇到的基本问题：如 何在p 2 p 网络中找到存有特定数据的节点。c h o r d 协议中规定使用的散列函数是 s h a 1 ，它在此基础上提供了优化的路由算法。c h o r d 中每个关键字和节点都分别 拥有m 比特的标识符。关键字标识符k 通过哈希关键字本身得到，而节点标识 符n 则通过哈希节点的i p 地址得到。这些关键字和节点标识符排列成一个圆环 ( 从0 到2 m 1 ) ，如图2 1 所示。这个环是一个虚拟的一次空间，c h o r d 中的路 由就在这个虚拟标识空间中进行。 s u c c e s s o r ( 6 ) = 0 固 图2 1 一个m = 3 ，包括3 个节点的c h o r d 环 2 ) = 3 2 0 0 1 年加州大学伯克利分校提出了内容寻址网络c a n ( c o n t e n t a d d r e s s a b l e n e t w o r k ) ，它也是基于d h t 的一个变种。c a n ( c o n t e n t a d d r e s s a b l en e t w o r k ) 类似于一张大哈希表，c a n 的基本操作包括插入、查找和删除 对。 c a n 由大量自治的节点组成，每个节点保存哈希表的一部分，称为一个区 ( z o n e ) 。此外，每个节点还保存少量的邻接区的信息。对每个特定关键字的插 入( 或者查找、删除) 请求由中间的c a n 节点进行路由直到到达包括该关键字 的c a n 节点所在的区。c a n 的设计完全是分布式的，它不需要任何形式的中央 控制点。c a n 具有很好的可扩展性，节点只需要维护少量的路由信息，且路由 信息的数量独立于系统中的节点数量。c a n 支持容错特性，节点可以绕过错误 节点进行路由。c a n 基于虚拟的d 维笛卡尔坐标空间来实现其数据组织和查找 9 第二章p 2 p 相关技术 功能。 另外一种典型的d h t 路由是p a s t r y 。p a s t r y 网络中的每个节点都有一个唯 一的节点号( n o d e i d ) 。当给定条消息和一个关键字时，p a s t r y 节点将会把这 条消息路由到在当前所有的p a s t r y 节点中n o d e i d 和关键字最接近的那个节点。 路由过程的时间复杂度是o ( 1 0 9 n ) ，这里n 表示网络中p a s t r y 节点的总数。p a s t r y 考虑了网络的位置信息，它的目标是使消息传递的距离最短。距离采用类似于 i p 路由的h o p 数的标量距离来进行度量。每个p a s t r y 节点记录在节点空间中和 它直接相邻的邻居节点，当新节点加入、原有节点失效和恢复时通知上层应用。 由于节点号是随机分配的，那么在节点空间中相邻的节点很可能在地理位置上 是分散的，或者根本就属于不同的组织。上层应用可以利用这一点，因为p a s t r y 可以把关键字路由到和它最接近的k 个节点的任何一个。p a s t r y 采用了启发式算 法可以使关键字首先路由到在节点空间中和消息产生的节点距离最近的包括查 找关键字的节点。 以上介绍了三种典型的d h t 的查找路由算法，它们有很多相似的特点，比 如都采用s h a 1 哈希函数来获得标识符，都采用路由表机制来进行转发，在处 理节点的加入和退出是都采用了相似的步骤等。但是在路由机制方面，各类网 络采用了不同的算法，从而导致了不同的网络特性。表2 2 给出了这几种路由机 制的比较，n 为节点总数，d 为c a n 的维度。 表2 2 典型d h t 路由性能比较 2 2 1c h o r d 理论基础 第二节c h o r d 路由算法 c h o r d 通过使用相容哈希函数( c o n s i s t e n th a s h ) 把关键字存储在c h o r d 中 的相应节点上。相容哈希函数通过使每个节点存储数量大概相等的关键字来平 l o 第二章p 2 p 相关技术 衡负载，并且使得当节点加入或退出的时候关键字的相对移动比较小。由于 c h o r d 中的路由表是分散的，每个节点仅仅需要知道其他少数节点的路由消息来 获取路径信息。 一个n 个节点的系统在稳定状态的时候，每个节点仅仅保持o ( 1 0 9 n ) 个 其他节点的信息，查询操作也仅仅需要发送o ( 1 0 9 n ) 条消息到其他节点。当有 节点加入和离开操作发生时所产生的消息量大多数情况下不超过0 ( 1 0 9 2 n ) 。 在c h o r d 中，每个关键字都保存在它的后继( s u c c e s s o r ) 节点中，后继节点 是节点标识符大于等于关键字k 的第一个节点，将其记为s u c c e s s o r ( k ) 。每个 节点需要维护一个路由表，称为指针表( f i n g e rt a b l e ) ，指针表中最多含有m 个 表项，如表2 3 所示。路由表保存标识符空间中顺时针与当前节点的距离为2 “ ( 1 i m ) 的标识符及该标识符的后继节点。 表2 3c h o r d 指针表表项 符号定义 f i n g e r r k l s t a r t( n + 2 k 1 ) m o d2 4 ，l k m f i n g e r n , 1 i n t e r v a l【f i n g e r r k l s t a r t ，f i n g e r r k + 1 1 s t a l l t 】 f i n g e r r k l n o d e第一个大于等于n f i n g e r t k l s t a r t 的节点 s u c c e s s 0 r 标识符环中的下一个节点，等于f i n g e r h l n o d e ，称为后继 p r e d e c e s s o r 标识符环中的前一个节点，称为前继 c h o r d 协议具有以下几个方面的优点： 1 ) 可扩展性：c h o r d 协议的开销随着系统规模( 节点总数n ) 的增加而按 d ( 1 0 9 2 n ) 的比例增加，因此可以应用到大规模系统。 2 ) 命名的灵活性：c h o r d 并未限制查询结构，因此应用层可以灵活地将内 容映射到名字空间，而不受底层协议的限制。 3 ) 负载平衡：c h o r d 采用一致性散列算法，该算法本身保证了其平衡性。 所有节点以同等的概率分担系统的负载，从而可以避免某些节点负载过大的情 况。 4 ) 有效性：c h o r d 自动调整它其中的路由表来反映新节点的加入或者节点 的失效，确保只要下层网络不发生错误，管理某个关键字的节点总是能够被找 到的。即使系统的状态在不停的变化，这种有效性也是能够保证的。 第二章p 2 p 相关技术 2 2 2c h o r d 算法过程 2 2 2 1 节点定位( a s k ) 算法 此过程是用来查找某个关键字( 也许不存在) 的后继节点和前继节点，该 算法是整个查找和节点加入退出等算法的基础，在c h o r d 协议提供的算法中起 到了相当关键的作用。 定位算法的具体过程如下： 1 ) 定位过程可以是在其他函数调用时发生，或接受到定位消息( 可以定位 前继或者后继节点) 时发生，首先检查待定位关键字是否等于定位过程发生节 点的节点值。如果等于则向原函数或者信息发出者返回本节点值( 如果定位前 继) 或者返回后继( 如果定位后继) ，否则转下一步。 2 ) 检查待定位关键字是否在过程发生节点的后继之上，即关键字是否大于 过程发生节点值却小于过程发生的节点的后继。如果关键字并不在后继之上就 转向下一步，否则，向调用过程返回( 如果是本地调用) 或者远程节点返回本 节点值( 如果定位前继) 或者返回后继( 如果定位后继) 。 3 ) 检查f m g e r 表中的n o d e 是否有处于待定位关键字和本身节点值之间的节 点值( 注意：不能取f i n g e r 中n o d e 等于关键字的节点值) 。如果存在这种节点值 就向这些值中最接近关键字的节点发定位消息，否则从中找到最接近被定位关 键字的节点值，并向这个节点发送消息。接受消息的节点再重新开始这个流程。 2 - 2 2 2 关键字数据对查询( q u e r y ) 算法 根据c h o r d 环的关键字分配方法，某个关键字以及关键字数据对只能出现 在相应的后继节点上，这个后继节点是唯一的。该查询算法就是用来查询某个 关键字是否存在于c h o r d 环中的某个特定节点之上，这个特定节点上如果存在 某个关键字就返回找到消息并得到关键字数据对。如果没有就返回环中无这个 关键字的消息。查询 对算法具体过程如下： 1 ) 调用查询过程，首先要查询关键字是否在本地，如果在就返回原调用程 序关键字数据对，否则转向下一步。 2 ) 在本地调用节点定位过程，定位待查询关键字的后继节点。 3 ) 向此后继节点发送查询消息，在节点上找到所需关键字就返回查询命中 ( q u e r y h i t ) 消息，并返回与关键字相对应的关键字数据对，未找到就直接返 1 2 第二章p 2 p 相关技术 回查询失败消息。 具体查找过程示例如图2 2 ，要在节点n 8 上查找关键字为k 5 3 的资源，首 先在节点n 8 查找资源是否存在本节点。如果不存在，则在节点n 8 的指针表中 去查找适合的后继节点，找到里面最大的但是不大于资源关键字的后继节点转 发查询请求，这里是节点n 4 2 ，在n 4 2 上可以找到下一跳的节点是n 5 1 ，依次 查找，直到找到节点n 5 6 ，发现目的资源，返回节点n 5 6 的信息给查询节点n 8 。 n 5 6 + ln 5 9 n 5 6 + 2n 5 9 n 5 6 + 4n 6 3 n 5 6 + 8n 1 n 5 6 + 1 6n 8 n 5 6 + 3 2n 1 4 囹 f m g e r - - 表 n 4 2 + ln 4 8 n 4 2 + 2n 4 8 n 4 2 + 4n 4 8 n 4 2 + 8n 5 l n 4 2 + 1 6n 5 9 n 4 2 + 3 2n 1 4 f i n g e r 表 n 8 + ln 1 4 n 8 + 2n 1 4 n 8 + 4n 1 4 n 8 + 8n 1 8 n 8 + 1 6n 2 7 n 8 + 3 2n 4 2 图2 2c h o r d 结构查询示例图 2 - 2 - 2 3 节点加入或退出