（计算机软件与理论专业论文）基于全局索引表的网络缓存结构研究.pdf

摘要 随着宽带网的发展和用户数量急剧增加，w 曲服务器成为访 问的瓶颈。b ，s 模式中的w 曲服务器单点失效可能影响整个网络 的可靠性。利用现有的w 曲缓存服务器和w 曲缓存服务器机群 方案可以有效解决这个问题。但是传统w 曲缓存结构还存在明显 不足，必须在原有技术基础上寻找一种更好的方案来解决这个问 题。 现阶段存在两种缓存结构一一集中式缓存结构和分散式缓存 结构。实践证明，集中式w 曲缓存结构存在严重缺陷：管理服务 器成为整个系统的瓶颈，b s 模式中驻留服务器的瓶颈效应漂移 到管理服务器上；管理服务器的负荷可能增加用户的访问延迟； 整个系统的灵活性差；管理服务器的配置费用高；系统鲁棒性弱。 而分散结构的缺陷有：用户访问的延迟不可预计；单个缓存的命 中率并没有提高；信息冗余严重；l c p 的请求、相应信息是基于 u d p 协议，所以此结构安全性较差；试验数据表明：结构中添加 成员时，系统开销加速增加。 本论文基于前两种缓存结构的缺陷，提出以下解决方案：在所 有成员服务器上构造一张全局索引表，表中保留所有成员存放 w 曲对象的u i 也信息和位置信息；当客户端发出h 兀甲g e t 请 求后，到指定的缓存服务器中的全局索引表查找；若存在请求对 象则返回用户；否则向驻留服务器提出对象申请，得到服务器响 应后，更新所有成员的全局表并等待新的请求。利用m d 5 算法 以优化全局索引表；缓存服务器间通信机制：分析出i p 层组播运 用于此结构的缺陷，提出一种基于应用层的组播构造弱同步方案 参考文献 来解决全局索引表更新问题；同时，在众多的替换策略中挑选、 并根据优化后的全局索引表项构造一个最适合本系统的替换算 法；由于系统采用协作方式，系统中不存在主攻击点，鲁棒性能 得到一定保证。但是在通信过程中，同样存在类似i c p 协议报文 的可攻击性问题，还需深入研究、解决。 关键词：源服务器，i c p ，全局索引表，双索引表 a b s t r a c t a b s t i 甚c t w i t ht h ei n c f e a s eo fi n t e m e tl l s e lt h ew 曲s e r v e rh a sb e c o m et h e b o t t l e n e c ko fi i i t e m e t t h es e r v e ro fb sm o d e lh a sb e c o m eat 1 1 r e a t t ot h ew h o l ei m 锄e t n ew 曲c a c h et c c l l l l o l o g yc a ns o l v et h i s p m b l e me 眠t i v e l y w l i i l et h e r cc x i s t ss o m em 锄i 胁td e f e d si n 仃a d i t i a lw 曲c a c h e 咖d u f et h a tr e q u i r e sab e t t e rm e t i l o dt os o l v e n o w a d a y st h e f e 盯et w os o n so fw 曲c a c h es n l l c t l i r 髂，t h o s ea r c m 锄g e m e n ts t n l d u r e 卸dl ( ，s t m c t u r c ，w h i c hw a sp r o v e dt h a t s o m ed e f c c tc o u l db e1 0 u n d 妯t h o s es t r u c t u r e f o ri n s t 刁i i l c e j nt h e m 卸a g e m e n t - b a s e dm o d e l ，t h eb o n l e n e c ka p p e a r sa g a i l ii nt h e m a l l a g e m e ts e e r t h ei c p b 勰e dm o d e l h a sg r e a tr i s ki i ls e c i l r i t y a s p c c t 1 1 l i st h e s i sp u t so u ts o m cr c s o l v i n gs c h e m aa o c o r d i n gt ot h e f o 册e r 咐os t n l c t l l r e s n a ti st h ew h o l cs y s t c mi sb 舔e do nag l o b a l i n d e xt a b l eo nw h i c ht h c w 曲o b j e c t s u r l4 d 出e 鼹a n d i p j f m m a t i 仰a r c 佗c o r d e d s i n o et h ed i e n t ss e do u th r l l p g e t “i s i t e r o e p t e db yt h cb o u n dg a t e w a y 如dr c d i r c d e dt ot h ew 曲c a c h e s e n ，e r w h i c hi sf o u o w e db yh 埘n gf o r t h ew e bo b j e di l it h ew 曲 c a c b et h m u 曲o u tt h e 西o b a li n d e xt a b l e s l 赋e 鹞，t h ew 曲c a c h e s e n d sb a c kt h ed i e n tw j t ht h er c q u i r c do b j e d ，o t h e r w i ，t h ew 曲 ( 二a c h cw i l lg e t t h ew e b0 b j 。c tw h i c hi sn o to nt h ei n d e xt a b l ef 如m t h e 嘶g i n a ls e r v e r ，t l l t h e 觚s ho b j e dw i l lb ee l i s t e di nc v e r yw 曲 c a c h e si n d e xt a b l e t l l i st l l e s j sj d u d e sa l s ot h eo p t i m i z i l l go ft h e 班o b a li n d e xt a b l eb a s e d 叫t l l em d 5a 1 9 0 d t h l n ，t h ec 0 衄u n i c a t i o 参考文献 o ft h cw 曲c a c h ei s0 0 n s i d e f c d m 髓n w l l i l e ，t h e na r cm 锄ya s p e c t r e q u j r i n g t o b er c s o l v e d i n t h e f l i c u r e w o r k 皿y w o r d s ：o r l g 枇髭r v 既，i c 只g l o b a l n 掀t 阻e d o u b 址啪e x n y8 78 3 7 7 独创性声明 本人声明，所呈交的学位论文是我个人在导师 指导下进行的研究工作及取得的研究成果。尽本人 所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得北京交通大学或其他教学机构的学 位或证书而使用过的材料。与我一起工作的同志对 本研究所做的任何贡献已在论文中作了明确的说明 并表示了谢意。 本人签名：墟 日期：止年立一月互日 关于论文使用授权的说明 本人完全了解北京交通大学有关保留、使用学 位论文的规定，即：学校有权保留送交论文的复印 件，允许论文被查阅和借阅；学校可以公布论文的 全部或部分内容，可以采用影印、缩印或其他复制 手段保存论文。论文中所有创新和成果归北京交通 大学计算机与信息技术学院所有。未经许可，任何 单位和个人不得拷贝。版权所有，违者必究。 本人签名： 日期： 亚蔓 1 概述 1 。1 课题背景 随着h i t e m e t 应用迅速普及，人们对i n t e m e t 的服务提出了更 高的要求：更快的传输速率，更短的等待延迟和更可靠的服务。 这就要求在传统网络技术的基础上进行调整和改进。研究表明： i n t e m e t 上2 0 的资源被访问的概率占总访问率的8 0 ，这也符 合常规的2 ：8 理论【l l 。在h n e m e t 中引入c a c h e 技术能够很好地 解决这个问题，即：将用户经常访问的w 曲对象存放在某一处的 w 曲c a c h e 中，当其他用户对此对象提出访问的l t p 请求的时 候，不从源服务器( o r i 百n a ls e r v e r ) 取得该w 曲对象，而是找寻 合适的w 曲c a c h e 后，从该c a c h e 中取得要访问的资源。在i n t e m e t 中应用c a c h e 技术，能够有效地将源服务器的访问负担分散到各 级c a c h e 部署中，从而减少源服务器的访问负担，而且能够减少 网络拥塞的可能性；用户方面，由于用户请求的w c b 对象可能 分布在各个级别的c a c h e 中，所以访问响应延迟现象就能大大减 少。 根据w 曲c a c h e 分布的位置，可以将w 曲c a c h e 技术分为： 客户端的缓存技术 服务器端的缓存技术 代理端的缓存技术 北京交通大学硕士学位论文 1 1 1 客户端缓存技术 w i n d o w s 操作系统的l e 浏览器将用户近期访问过的w e b 对 象根据页面的缓冲要求( “n oc a c h e ”等) ，放到c ：、d 0 c i l m e n t sa n d s e t t i n g s a d m i n i s t r a t o r h c a ls e t t i n g s 1 b m p o m f yi n t e m e tf i l e s 目录 中( 默认系统安装在c 盘上) ：如图1 1 所示，若用户对该w 曲 对象再次提出访问申请，则先在客户端的c a c h e 中寻找这个w 曲 对象，若存在且没有过期，则直接从本机调取w c b 对象，而不从 源服务器取得。 图1 1客户端的缓存技术 使用客户端的缓存技术，虽然能减少个体用户的访问等待时 概述 间，但是对于h l t c r i l e t 这种群体结构，特别当用户并发量很大的 时候，并不能有效的解决访问延迟，同时也不可能解决网络拥塞 的整体负效应。 1 1 2 服务器端缓存技术 与客户端缓存技术类似，服务器端的缓存技术将c a c h e 部署 在源服务器上，即在面g i l l a ls e e r 上开辟一合理的高速存储空 间。当源服务器收到用户的m 1 甲访问请求后，首先比较在源服 务器c a c h e 中所缓存的w 曲对象，若此对象存储在告诉c a c h e 中 则直接将此对象发布给用户，如图1 2 所示。否则，再从磁盘中 寻找该w 曲对象。 图1 2服务器端的缓存技术 使用服务器端的缓存技术，虽然能够加速源服务器的查找对象 北京交通大学硕士学位论文 的速度，但是还存在一下的缺陷： 没有减轻源服务器的被访问负担； 由于带宽的限制，完全可能使服务器端成为瓶颈而造成拥塞。 1 1 3 代理端缓存技术 在客户端和源服务器端之间增设一代理服务器，是早有的解 决网络拥塞的技术。w 曲c a c h e 技术就是将c a c h e 部署在代理服 务器端，而不是仅仅在客户端或源服务器端开辟缓存空间。如图 1 3 所示。当用户提出h 1 ，1 1 p 请求以后，可以直接将请求向代理 服务器发出；代理服务器为用户寻找w 曲对象：若找到，则直接 从代理端发送w 曲对象到客户端；否则，代理服务器向源服务器 提出请求，并将该w 曲对象保存到本c a c h e 中。 图1 3代理端的缓存技术 使用代理缓存技术，可以从根本上减轻源服务器的负担。由 4 于，各个代理服务器将用户的要求分散开，所以能够缓解网络拥 塞的问题。 1 2 课题研究内容 通常，将一个代理缓存部署在一个企业或学校。然后企业或 学校间将各自的代理c a c h e 服务器进行统一部署、管理，就可使 各个c a c h e 服务器可以共享各自的w 曲对象。这种各个w e bc a c h e 之间的合作、协调就更能够减轻源服务器的负担。根据代理c a c h e 服务器部署结构和管理方式不同，可以将现阶段的代理c a c h e 服 务器划分成两种结构： 集中式管理的代理c a c h e 结构； 分散式管理的代理c a c h e 结构。 应用这两种结构，各个代理c a c h e 服务器能够相互配合通信、 共享存储w 曲对象，很大程度上的提高代理c a c h e 服务器的利用 率，从而在更大程度上了解决网络拥塞的问题。然而，这两种结 构在实施的过程中也暴露出很多缺陷( 详见第二章的讨论) ，基于 此，本论文提出一种基于全局索引表的代理c a c h e 结构，这种结 构具有集中式和分散式结构共同特点，综合的利用两种结构各自 优点，回避了各自由于集中得过严、分散得过宽的缺陷。从而更 加有效地将各个代理c a c h e 服务器整合起来。 1 3 课题的主要研究内容 本课题的主要研究内容是如何综合集中式代理巳c h e 和分散 式代理c a c h e 结构各自的优点。研究后发现，构造一张全局的索 北京交通大学硕士学位论文 引表结构可以保留集中式代理c a c h e 结构的统一管理、集中调度 的优点：同时将此索引表部署在各个代理c a c h e 中进行同步的更 新管理保证了分散式的优点。如何构造这张全局索引表是本课题 研究的首要任务，同时，这也是最关键的。在全局索引表构造好 以后，还需要解决各个代理c a d i e 服务器之间的通信来保持全局 索引表的一致性。 1 4 论文的编排结构 本论文首先在第二章介绍了现阶段广泛应用的两种代理缓存 结构，并分析了这两种结构的缺陷。论文的第三章，对全局索引 表进行了设计，说明了基于全局索引表代理缓存结构的工作原理， 并对此全局索引表的结构进行了最大的优化，保证了系统的低存 储空间和高效率性。第四章中，对缓存问的通信方式进行了设计， 分析了现有的基于i p 层的组播方式，分析了应用在此系统中的缺 陷性。系统中采用了基于应用层的组播方式来解决代理缓存之间 的通讯问题，并分析了采用这种通讯方式的合理性。论文第五章 对代理缓存的替换算法进行了分析，并根据本系统设计的全局索 引表构造了一种新的替换算法，同时对为了保证系统信息一致性， 引入了一个双索引表的机制，并对侦听模块和加入模块的执行流 程进行了描述。第七章对系统测试的指标和系统测试的环境和数 据进行了讨论，证明了系统的可推广性。 6 集中式和分散式缓存结构 2 集中式管理结构和分散式结构 根据代理c a c h e 服务器部署结构和管理方式不同，可以将现 阶段的代理c a c h e 服务器划分成丽种结构：集中式管理的代理 c a c h e 结构和分散式管理的代理c a c h e 结构。 2 1 集中式管理的代理c a c h e 结构 2 1 1 集中式管理的代理c a c h e 结构的工作原理 集中式管理的代理c a c h e 结构，将所有代理c a c h e 分成两个 层次的结构： 普通代理c a c h e 层； 管理服务器层( m s ) 。 层次结构如图2 1 所示： 图2 - l集中式缓存技术的逻辑结构图 网络中所有客户端的哪请求都由一个管理服务器 北京交通大学硕士学位论文 ( m a n a g e rs e r v e r ) 来统一调配管理。 豳2 - 2 集中式代理缓存 当客户a 请求服务器1 上的一个文档时，它向代理管理器发 送一个 r r r p 请求，请求由u r l 方法和请求头组成。代理管理器 收到请求后，解析地址，不妨设为u r u ；然后计算u r l 的哈希 值，确定代理，不妨设为代理3 ；最后将请求转往代理3 ，代理3 如果没有请求的文档，则由代理3 负责从服务器取回文档，如果 8 集中式和分散式缓存结构 代理3 上已有备份，则由代理3 直接将文档传给客户a 。同一服 务器上的不同文档经哈希运算后将由系统的不同代理处理，比如 服务器2 的两个文档地址为u r u 和u r l 4 ，经过m s 解析后分 别由代理2 和代理3 处理，从而避免了某些代理负荷过重、某些 代理则负荷少的缺陷。 从请求回答过程可以看到，缓存系统的代理之间的通信被代 理和代理管理器的通信取代。代理管理器负责维护代理的状态及 分发请求。代理管理器负责维护一张代理表，代理表由0 到( m m 1 ) 个连续表项组成，每个表项包括代理标识、活动标志。m s 与代 理的通信如下：当增加一个代理时，新代理向管理器发送一个 a d d 请求，请求里包含了代理标识。管理器收到a d d 请求后， 在代理表中将相应代理的非活动标志改为活动标志，最后向代理 发送一个确认消息。在平时，管理器通过向代理周期地发送 a c n v e 消息并维护来自代理的响应。对超时无响应的代理，相 应表项中的活动标志改为非活动标志。代理和管理器之间的通信 ( n ) 比代理和代理之间的通信( n ( n 一1 ) ) 大大减少了通信量。使用集 中式管理的代理c a c h e 结构，用户请求都可以在各个代理缓存中 取得，从而减少源服务器的访问负担，减少网络拥塞时用户访问 的延迟时间。 2 1 2 集中式管理的代理c a c h e 结构局限 以上分析可以看出，集中式管理的代理c a c h e 结构存在很多 缺陷： l _ 管理服务器成为瓶颈 9 北京交通大学硕士学位论文 当不采用管理服务器时，用户提出访问请求后，直接在指定 的代理c a c h e 中找寻该w 曲对象。而采用管理服务器以后，所有 的h 1 t r p 请求都将提交给管理服务器m s ，由m s 经过求模运算 以后，决定目标代理c a c h e 。当用户请求数目相当大时，源服务 器的“瓶颈效应”将漂移到该m s 上。m s 配置的高低、用户请 求的并发量将直接影响到整个c a c h e 群的工作性能、成为影响整 个集群正常工作的中心。 2 鲁棒性差 m s 是整个集中式管理代理c a c h e 结构的心脏，同时也是最容 易受攻击的部位。当m s 遭攻击或者断电时，整个代理c a c h e 群 也将瘫痪以至无法正常工作。 3 服务器负荷重时增加用户访问的延迟 m s 是整个代理c a c h e 群被访问的唯一入口，所有h t r p 请求 都将由m s 分析、计算、分配目标c 托h e 地址。由于管理服务器 根据客户请求的通过哈希运算，再求模得到相应的缓存服务器， 该缓存服务器还必须将检查该请求是否保存在缓存中，才决定向 源c a c h e 服务器发出请求，或将缓存的内容返回给客户，从而增 加了客户访问的延迟。当用户访问并发量大时，m s 要处理的请 求队列也会增长。当服务器负荷重时，对于用户来说，必将增加 用户的访问延迟。特别地，在这种时候，用户几乎感觉不到使用 这种缓存结构给他们带来的切实的利益。 4 灵活性差 当整个代理c a c h e 群中需要增添新的代理c a c h e ，或者有代理 c a c h e 退出的时候，都需要在m s 中修改整个配置表。群中每个 代理c a c h e 都不可能主动和管理服务器进行联系，所以若当其中 1 0 集中式和分散式缓存结构 某个代理c a c h e 失效的时候，m s 不能及时修改其配置表。这个 时候，当用户的请求没有在整个系统中得到响应，整个系统则失 效。 s 配置费用高 整个系统增加了m s 硬件配置，必然会增加整个集中式管理 代理c a c h e 结构的运行费用，同时，m s 需要专门的配置、管理， 也会增加开销。 北京交通大学硕士学位论文 2 2 分散式缓存结构 2 2 1 分散式缓存结构工作原理 分散式缓存结构又称作是基于i c p 协议的w 曲缓存集群。l c p ( h t e m e tc a c h ep m t o c 0 1 ) 协议是轻量缓存通信协议，广泛用于s q u i d 和n e t c a c h e 中。 同集中式管理的代理c 知b e 结构相比较，分散式缓存结构中没有 单独的管理服务器层次，但是所有的c a c h e 形成个父子节点关系的 层次结构。 其组织结构如图2 3 所示： 图2 - 3 分散式代理缓存逻辑结构图 网络中客户端的h t l 甲请求可以传递给任何一个代理c a c h e 节点， 当代理节点收到请求后，首先查找本代理中是否存在该w c b 对象，若 存在，则将该对象传递给客户端：若不存在则将用户的要求传递到其 集中式和分散式缓存结构 他节点中继续循环查找，直到查询成功或遍历失败为止整个过程仅仅 由各个代理c a c h e 相互基于i c p 协议进行协调，而不采用统一管理的 措施。 l c p 协议的工作原理如图2 _ 4 所示，p r o x y 2 ，p r o x y 4 和p r o x y 5 是 同胞节点，p r o x y 3 是它们的父节点。c 】i e n t a 和p m x y 4 直接相连， 当c 1 i e n t a 请求源服务器( 鲥鹰n a ls e e r ) 上的某个w 如对象时， c l i e n n 首先向p m x y 2 发请求，p r o x y 2 收到请求后，检查u r l 是否在 其的缓存中，如果在，则回复a i e n 魄；如果u r l 不在缓存服务器中， p m x y 2 向它的同胞节点p m x y 4 通过u d p 发送i c p 请求，同胞节点 斟复是否有u r l 信息；如果有，则从同胞节点拷贝w 曲对象，并传 给c ! o n t a ；所有的同胞节点回复没有或超过规定时间后，则p m x y 2 向父节点p r o x y 3 发i c p 请求，p m x y 3 有对应的文档，刚传送给 c l i e n 蚺，如果父节点也没有，则由父节点再向父节点p r o x y l 发送i c p 请求，p m x y l 查找自己c a c b e 空间，若找到该u r l 的w e b 对象，则 将该w 曲对象拷贝给a i c n t a 。若此过程失败，则从源服务器取得文 档，传送给c l i e d t a ，由p r o x y 2 发送给a i e n 峨。i c p 通信是建立在查 询和应答基础上的，可以减少到外部网络的通信量，然而代理之间通 信开销却很大，当代理没有用户要求的文档时，它必须向它的同胞有 限广播l c p 请求，当同胞数增多时，通信量的开销和处理能力的开销 也随着增加。由于必须等待所有的同胞都回答没有相应的u r l ，才能 向服务器发送请求，网络延迟也相应增加。 北京交通大学硕士学位论文 图2 4分散式代理缓存实例 2 2 2 分散式结构应用现状 s a u i d ，n e - c a c h c 和h a e s t 系统现在已经广泛的应用到了各个企 业和校园里。如图2 5 所示，为每一个企业或学校配置一台代理c a c h e ， 不仅能够改观用户访问的延迟现象，而且可以节省用户访问的费用。如 果说某c a c l l e 的命中率是6 4 ，就意味着c a c h e 可以满足6 4 的数据 请求，而只有3 6 数据需要去原始服务器取。从这个角度看，使用 c a c h e 意味着节约了带宽，因而提高了性能和响应速度，如果需要按 字节流量计费，w 曲高速缓存在相对较短的时间内可以节省一笔可观 的费用。 1 4 集中式和分散式缓存结构 f o 丌a r dp r 。x vc a c h e 图2 - 5 分散式代理缓存的应用 将各个企业或校园的代理c 丑c h es e e r 组织起来，则形成了基于 i c p 协议的代理缓存结构。此结构现在已经被广泛的使用。 2 2 3 分散式结构局限 1 用户访问延迟增加 分析分散式管理结构的工作过程：当客户端向特定的代理c a c h e 提出访问要求以后，该代理首先在本机搜索请求的w 曲对象；若查找 失败则需要在其兄弟节点中寻找；再次失败以后还要返溯到其父节点 寻找；一直到失败或找到为止。这样用户就可能等待和代理层次 数n 相同的访问周期t ( 用户的等待时间为n t ) ，这个等待时间在各 级c a c h e 命中率低的时候可能远远大于用户直接访问源服务器的等待 延迟时间。所以基于1 c p 协议的分散式缓存结构只适合那些c a c h e 构 造数目比较小的集群中，当代理c a c h e 数目庞大以后，各个代理c a c h e 之间互相的询问、传递u d p 的i c p 请求，这必然会增大用户的访问 延迟时间。 假设：c a c h e 集群中共有n 台代理c a c h e ，每台代理c a c h e 的命中 北京交通大学硕士学位论文 率为p 1 ，p 2 p n ，各台c a c h e 之间传送u d p 报文的时间开销为t ， 则可以计算用户延迟的期望 = t ( 卜p 1 ) + t ( 卜p 2 ) + t ( 卜p n ) = t ( n 一( p l + p 2 + + p n ) ) 可以 看出访问延迟时间为o ( n ) ，访问延迟随n 线性增长。 2 成员通信量和系统开销增加 当用户指定的代理c a c h e 中不存在欲取的w 曲对象的时候，源代 理c a c h e 必须遍历访问所有代理c a c h e 。代理c a c h e 之间互相的通信 是发送基于u d p 的1 c p 请求，来通知其他的代理c a c h e 是否命中 ( i c p0 ph 1 1 r 标志位为1 ) ，这样的交流信息就会存在在代理c a c h e 集 群中。如果在本代理c a c h e 中查找失败( i c p 一0 p m i s s ) 而在兄弟节 点或是父节点中查找到u r l 对象，那么，l c p 的做法是；将这个w 曲 对象拷贝到最初查找失败的那个代理c a c h e 节点中。当各个代理c a c h e 的命中率p 差异很大时，就会在代理c a c h e 问出现w 曲对象重复0 0 p y ， 重复传递的现象。不能够起到充分、综合地承j 用了各自的缓存内容： 同时可能在传递的过程中使网络拥塞情况更加严重。 3 单缓存的命中率并未提高 因为客户端在指定代理c a c h e 中查询失败以后，转到其他的代理 c a c h e 中查找。所取得的w 曲对象并不是在本c a c h e 中取得，所以对 于单个的代理c a c h e 而言，其命中率并没有得到提高。 4 信息冗余 如2 ) 所述，用户请求失效后，最后查找到的代理c a c h e 将用户请 求的w 曲对象重复的c o p y 到第次失效的代理q i c h e 中。这样同一 个u r l 的w 曲对象就会在整个集群中存在多个副本，由于各个代理 c a c h e 都是被动的等待访问，不仅浪费了存储空间而且造成了信息的 集中式和分散式缓存结构 冗余。 5 增加、减少成员信息管理复杂 当新增加新代理c a c h e 的时候，在整个集群系统中必须指定配置 “兄弟”，“父子”关系。所以在新成员加入的时候要为每一台代理 c a c h e 配置关系表。同样，当有代理c a c h e 退出的时候，也必须将其 他所有的代理c a c h e 指向关系表进行更改，这无疑增加了配置的复杂 度。 6 安全性差； 首先，由于i c p 协议是基于u d p 报文传送的，而u d p 报文本身 就是一种不可靠的协议，在传输的过程中，极易丢失。 其次，i c p 的请求报文本身存在很多缺陷，r f c 2 1 8 7 【1 7 】中就指出 了很多l c p 自身的缺陷： 第三方插入伪请求( b o g u sr e q u e s t ) ； 第三方插入伪响应( b o g t l sr e p l y ) 可能导致邻节点完全可用或 不可用 从而导致代理c a c h e 节点被污染的情况； 第三方侦听； 封锁或延迟i c p 请求； 第三方篡改i c p 各个域e l d s ) 。 2 3 小结 本章重点分析了当今流行的两种代理c a c h e 结构：即集中管理 c a c h e 结构和分散管理的c a c h e 结构。首先介绍了其工作原理，然后 分析了两者在应用中的优点和不足。 1 7 北京交通大学硕士学位论文 3 基于全局索引表缓存结构的设计和优化 3 1 基于全局索引表的设计思想 在前一章里，我们分析了集中式代理c a c h e 结构和分散式代 理c a c h e 结构各自的优点和缺陷。我们发现：集中式代理c a c h c 结构是把所有的h 唧请求分配任务都交给了管理服务器 ( m a m 龋rs e r v e r ) ，这种代理结构所出现瓶颈效应的症结也就是 存在于此。分散式代理c a c h e 结构与集中式结构正好相反，所有 的i c p 请求信息在c a c b e 节点中流动，缺乏统一的管理约束机制。 其安全、性能等方面的缺陷都是因为过于分散而导致。考虑采取 一种折中的办法，来汲取集中式和分散式结构的优点，同时避免 二者的缺陷。采用集中管理，有两种方案：采用硬件管理服务器 或采用“软管理”方案。研究后发现，整个代理c a c h e 集群采用 一张统一的全局索引表( 以下称u r l 资源索引表) 就能够实现这 种软管理的办法：整个系统的每一个c a c i l e 节点都拥有一张相同 的u r l 资源索引表，该索引表中应该完整的记录着自身和其他所 有c a c h e 节点上u r l 指明的w c b 对象。大致的指向关系如表3 1 有c a c h e 节点上u r l 指明的w c b 对象。大致的指向关系如袁3 1 所示： 表3 1 u r l 表 u r l 存储c k h e h n p ：，e w s i n a m c n 伽d e x h t n l i 节点1 b n p 洲钾w 吼b j t u e d u c 曲d e l b 玎岫 节点2 h n p 卅d e w s h u c o m n d e x h i m i节点n 基于全局索引表的缓存结构 当用户端产生的h t r p 请求到达其指定的代理c a c h e 节点以 后，代理c a c h e 查找u r l 资源索引表，当表中的u r l 项有和用 户端h t r p 请求的g e t 项有匹配，则取出表中的第二项“存储 c a c h e 节点”：若该节点就是本机则直接从本机的存储空间中取得 w e b 对象发送给用户；若取出的存储c a c h e 节点不是本机，则就 道该项所指出的节点取得该w 曲对象发送给用户端；若整张u r l 资源表都没有用户请求的w 曲对象，本节点通知用户端代理 c a c h e 查找失败，则用户直接向源服务器( o f i 西n a ls e r v e r ) 直接 取得w 曲对象，同时第一个代理c a c h e 还要预取这个w 曲对象， 并同步的更新所有c a c h e 的u r l 资源索引表。 3 2 工作原理 如图3 1 所示，假设工作群中共有代理缓存服务器c a c h e 一 共五台：p r o x y l ，p f o x y 2 ，p r o x y 3 ，p r o x y 4 ，p i o x y 5 ，每一台代理 c a c h e 中都存储p m x y l 5 中所有w 曲对象的u r l 信息一u r l 资 源信息表( 在图3 1 中由a 表示) 。 客户端( d i e m a ) 在某一时刻向p r o x y 2 发出w e b 对象请求， p f o x y 2 查找本机的u r l 资源信息表，这时存在两种情况： ( 1 ) 当用户请求的w 曲对象存在p m x y 2 中，则将该w e b 对象直接 从p r o x y 2 传递给c l i e n t a ； ( 2 ) 当用户请求的w 曲对象不存在p r o x y 2 中，则将在u r l 资源索 引表中查询到的u r l 对象存在节点作为目的节点，p r o x y 2 替 c l i e n 俄传送w 曲对象请求，若此时查询到的目的地址为p m x y l ， 当p r o x y l 收到p t o x y 2 发出的请求以后，将用户所请求的w 曲对 1 9 北京交通大学硕士学位论文 象p y 到用户端。 ( 3 ) 当用户请求的w 曲对象在u r l 资源索引表中不存在对应的索 引项，则这时候p m x y 2 至少应当做三件事情： 向a i e n t a 发出匹配失败信息( f e t c hf a j i u 陀) c l i e n 晴，a j e n t a 收到p m x y 发出的失败信息以后，直接向源服务器( o r i 西n a ls e r v e r ) 提取该w 曲对象。 p r o x y 2 本身向源服务器提出该w 曲对象请求，p m x y 2 在源服务 器上取得w 曲对象以后，首先应该修改自己本机的u r l 资源索 引表，这是应该在索引表中增加一项，这一项记录了刚才查找失 败的w 曲对象现在存储在p m x y 2 上。 p r o x y 2 在更新了自己的u r l 资源索引表以后，必须通知群中 其他各个c a c h e 节点修改索引表，以达到u r l 资源索引表的同步 更新，这样才不至于客户端在访问其他代理c a c h e 而不知道该 w c b 对象已经存在于p m x y 2 中。这个更改信息的传递一般采取组 播的方式，具体的实现将在第六章节中描述。 这个分散协作的代理c a c h e 结构中，每一台c a d 他所维护的 u r l 资源索引表应该是同步的更新和修改的。只有保证了同步， 才算具备统一管理的特点，否则，也只有象基于i c p 协议的分散 代理结构一一缺乏一种统一的管理机制。 基于全局索引表的缓存结构 图3 1基于全局索引表的代理缓存结构实例 北京交通大学硕士学位论文 3 。3 全局索引表的设计和优化 3 3 1u r l 资源定位表结构 索引表结构的设计分析： h r r p 的请求格式： 响应头( r e s p o i l s eh e a d e f ) 响应头也和请求头一样包含许多有 用的信息，例如服务器类型、日期时间、内容类型和长度等： 正确合理的u r l 资源定位表关系到整个系统运行的正确性和 效率。通过第l 节和第二节的分析，可以设计如表3 2 格式的表 基于全局索引表的缓存结构 结构： 表3 2 全局索引表的初步设计 w 曲u r l存放代理i p失效时间访问 对象地址 次数 i d l h t t p ：，n e 砒s i n a c o m c n i n d e x h t m l 2 0 2 1 0 2 5 0 2 t h u ，2 9 d e c 6 5 7 8 8 2 0 0 51 8 ：0 0 ：0 0 h t t p ：加e a l t h b o a r d s _ b b s c o m 6 9 1 0 2 1 1 9 f r i ，2 1 d e c 8 8 9 2 2 51 9 ：o o ：0 0 表3 2 是u r l 资源定位表的初步设计方案： 缓存w e b 对象i d ：为代理c a d l c 群中所有的缓存的w c b 对象编 号； u r l ：缓存w 曲对象的u r l 地址； 存放代理i p 地址：实际存放w 曲对象的代理c a c h e 的i p 地址； 失效时间：每一个w 曲对象有应该有一个订l ，本项记录的是 此w 曲对象的生存周期。每一个代理c a c h e 服务器在从w e b 对 象源服务器获得请求访问的响应时，在r e s p o n s eh c a d e r 中就有 a g e 项，a g e 的值就应该时此项的值。 访问次数；本项记录了群中每一个w 曲对象被访问的次数，设 计这一项的目的是定时的让整个u r l 资源索引表按照“被访问次 数”这个字段进行排序( b y0 r d e ra s c ) ，因为下一个用户所 提出的访问请求很有可能是被访问次数字段非常高的那些对象 ( 由于整个u r l 资源索引表记载的并非单个代理h e 中的w c b 页面，而是群中所有代理c a c h e 的w 曲项，所以全局索引表会非 常庞大，如果不设置本项，则在查询u r l 资源索引表就应该顺序 匹配，这种匹配是相当耗时的，如果这种延迟使得用户不可承受， 北京交通大学硕士学位论文 那么本系统结构的以下设计工作将是徒劳的，所以对查询方式和 表结构的优化非常重要) 。若是增加此项，所有的记录都将按照被 访问的次数排序( 这个过程可以放到每一台代理c a c h e 中定时完 成) ，用户h 1 t r p 请求来到时，代理c a c h e 顺序搜寻u r l 资源索 引表，若请求的w 曲对象u r l 信息确实存在表中，则查询的时 间将会节省许多。 3 3 2 全局索引表的优化 表3 2 中是u r l 资源索引表的初步设计结果。之上我们提到： u r l 资源索引表设计和优化的好坏将关系到整个代理c a c h e 结构 的性能。所以，我们有必要对本表结构进行优化： 1 缓存w 曲对象i d 我们发现在整个表结构中，u r l 地址可以唯一的确定一行记录， 所以使用第一项w 曲对象i d 并没有起到作用，仅仅作为一个直 观的序列号( 驼q u e n c e ) 存在而已，当记录数目相当庞大的时候， l d 号也相当消耗存储空间，为了降低u r l 资源索引表的冗余程 度，本字段可以取消。 2 u r l 本字段记录着w 曲对象的u r l 地址。通常，u r l 地址的长度不 定，当表中记录相当多的时候，所占存储空问庞大。所以必须对 2 4 基于全局索引表的缓存结构 这一字段进行优化，目的是减少全局索引表消耗的存储空间。 由于u r l 字段的作用仅仅是和请求u r l 地址进行匹配，以得到 请求w c b 对象的目标缓存l p 地址。所以我们可以对u r l 字段进 行变型、压缩。我们可以利用当今网络应用上比较流行的几种字 段的加密压缩算法一m d 5 和s h a 来达到这个目的。 m d 5 的全称是m e s s a g ed i g e s t ( 信息一摘要算法) ，它的作用 是让大容量信息在用数字签名软件签署私人密匙前被”压缩”成一 种保密的格式( 就是把一个任意长度的字节串变换成一定长的大 整数) 。获得一个随机长度的信息并产生一个1 2 8 位的信息摘要。 虽然这些算法的结构有些相似。l l d 5 的典型应用是对一段信息 ( m e s s a g e ) 产生信息摘要( m e s s a g e d i g e s t ) ，以防止被篡改。 比如，在u n i x 下有很多软件在下载的时候都有一个文件名相同， 文件扩展名为m d 5 的文件，在这个文件中通常只有一行文本，大 致结构如： m d 5 ( n e w s s i n a c o m c n ) = o c a l 7 5 b 9 c o f 7 2 6 a 8 3 l d 8 9 5 e 2 6 9 3 3 2 4 6 l 这就是n e w s s i na c 伽c n 文件的数字签名。m d 5 将整个文件当作 一个大文本信息，通过其不可逆的字符串变换算法，产生了这个 唯一的m d 5 信息摘要。如果在以后传播这个文件的过程中，无论 文件的内容发生了任何形式的改变( 包括人为修改或者下载过程 中线路不稳定引起的传输错误等) ，对这个文件重新计算m d 5 时 就会发现信息摘要不相同，由此可以确定这是一个不正确的文件。 m d 5 还广泛用于加密和解密技术上。 m d 5( ”) = d 4 1 d 8 c d 9 8 f 0 0 b 2 0 4 e 9 8 0 0 9 9 8 e c f 8 4 2 7 e m d 5 ( ”a ”) = o c c l 7 5 b 9 c o f l b 6 a 8 3 1 c 3 9 9 e 2 6 9 7 7 2 6 6 1 m d 5 ( ”a b c ”) ：9 0 0 1 5 0 9 8 3 c d 2 4 f b o d 6 9 6 3 f 7 d 2 8 e 1 7 f 7 2 北京交通大学硕士学位论文 当每一台代理c a c h e 端收到源服务器传送过来的w e b 对象时， 就利用m d 5 算法将任意长度的u r l 地址转换成1 2 8 b i t 的信息摘 要。将这1 2 8 b i t 转换成3 2 位的十六进制以后，就可以统一的采 用3 2 位字符串( c h a r ( 3 2 ) ) 的固定长度存储在代理c a c h e 中， 这样固定长度的u r l 地址减少了存储空间的冗余，同时，在检索 的过程中也容易改进程序的检索方案从而提高效率。 由于m d 5 算法必须经过四轮算法产生出3 2 位的十六进制散列 值，对于每一台代理c a c h e 而言，当代理c a c h e 收到源服务器传 给的w e b 对象以后，从本机h t t p 请求g e t 后提取出w e b 对象的 u r l 地址，若成功的从源服务器取得欲取对象，则将本u r l 进行 m d 5 运算将3 2 位v a r c h a r 填入表中；当用户的请求到来的时候， 首先从h 1 u r p 请求中解析出用户g e t 请求中的