《一种基于ＤＨＴ的Ｗｅｂ缓存共享方法.doc》由会员分享，可在线阅读，更多相关《一种基于ＤＨＴ的Ｗｅｂ缓存共享方法.doc（15页珍藏版）》请在三一文库上搜索。
1、一种基于的缓存共享方法?丶?词：分布式哈希表； Web缓存； 命中率； 系统响应 Web caching system based on DHT architecture LIU Jiana, b, SUN Xiaohuia,b, NI Hongb (a. Graduate School, b. Institute of Acoustics, Chinese Academy of Sciences, Beijing 100190, China) Abstract:This paper proposed a Web caching plan based on DHT, whose underly
2、ing ideology was that all the terminals in an Intranet were able to share their local caching to constitute a largescale, effective distributed Web caching system. Given the responding rapidly characteristic of Web caching, proposed a new routing scheme with a constant O(2) hop per lookup request, w
3、ith which a Web query request could reach the target node within only one transfer. Furthermore, the evaluation results prove that it achieves a satisfied performance in routing reliability, hitsratio, latency of response and caching cost. Key words：distributed hash table(DHT); Webcache; hitsratio;
4、system response ? Web缓存技术实现Web内容的关键节点存储，它能减少网络带宽的占用，改善响应时间，提高用户的访问效率。现在大多数Web缓存技术采用代理服务器和网络缓存的方式实现，即缓存内容保存在特定的缓存服务器上面，这样可能会造成缓存服务器负载过重，没有充分利用网络上大部分PC节点的带宽，距离缓存服务器很远的节点响应速度没有改善。如果让网络中的节点能够共享本地缓存，不仅可以提高用户的Web信息获取速度，而且可以大大降低该网络的外部流量。 本文提出一种基于P2P overlay结构分布式Web缓存共享方法，采用分布式哈希表(DHT)将节点和缓存目录信息均映射到同一个键值空间（
5、或者叫做标号空间）中，键值为k的缓存目录信息存储在标号为k的节点上。所有Web缓存对象目录信息均匀分布在所有节点上，节点负载小，同时采用分区域管理的方式，使得缓存目录信息查询路由最多只需要O（2）步,即查询消息最多只经过一次转发就可以定位到目标节点，大大提高了缓存响应的速度,保证缓存获取的高效性。 1 相关研究 基于DHT各种应用的区别在于路由方式的不同，每个基点上的路由表保存了不同的信息，导致路由步长不一样。一种是如Chord1、 Pastry、Tapestry、 Koorde、Viceroy采用多跳路由方式，路由表仅需要维护O(log N)或O(1)个节点的状态信息，查询步长均为O(log
6、 N)。另外一种是Kelips2系统，以及A.T.Mizrakd等人和A.Gupta等人提出的采用超级节点结构的单跳路由算法3，每个超级节点的路由表维护全局路由状态，路由表维护(O(N)或O(N)个节点的状态信息，但查询路由步长仅需要O(1)跳。 Web共享的目标是共享所有节点上的缓存信息，用户需要系统响应迅速，可以很快定位目标节点并获取缓存，同时保证节点维护代价比较小。现在提出的基于P2P的Web缓存共享方法已经有人提出： BuddyWeb4采用自适应跳步算法查询目标节点，步长27，聚类失败将会导致查询失败；Squirrel5基于Pastry构建DHT,查询路由步长为O(log N)；Kac
7、he6路由步长为O(1),但是每个节点需要保存位于当前分组的所有节点上的缓存目录信息，并采用泛洪方式进行组内信息的传递，目录信息存储和维护代价高。 本文试图找到一种查询步长短，节点负载小，缓存内容及目录信息分布存储的Web缓存共享方法。采用DHT的overlay结构，可以使节点地址和Web缓存得到统一，通过缓存对象的hash值可以查询到存储该缓存的源节点地址。考虑到chord环的抗干扰性和Kelips的分组思想，设计一种节点易于管理、抗干扰性强、常数路由步长的DHT方法,作为Web缓存共享应用的基础。 2 实现方法 2. 1 路由协议 通过一致性hash函数如SHA1将节点n映射为节点空间(k
8、m)中的一点，用hash值(k, id)来表示每一个节点。形象地说，首先将所有节点分为k个子区域，每个子区域内的所有节点均匀分布在大小为m的环形值域空间，那么在节点n的hash标号(k,id)中，k为区域标号，id为子区域环上标号。 所有Web缓存对象的目录信息分布存储在所有节点中，将缓存URL作为key并通过hash运算映射到空间(km)中的一点(k,id)，该键值为key的缓存对象的目录信息（IP，端口）就存储在节点(k,id)的后继节点上（类似chord定义节点(k,id)的后继节点(k,id)满足：首先k=k,即位于同一个子区域；其次idid，即如果节点(k,n)是活动的，那么其后继节
9、点就是它本身，否则是环上该节点后面的空间距离最近的活动节点）。图1所示为(68)个节点的子区域划分情况。 每个节点管理的信息包括本地缓存信息、缓存目录信息和路由表。 a)本地缓存信息指该节点上实际存储的各种Web缓存信息，包括URL、缓存内容、缓存大小、上次修改日期、过期日期等。 b)因为目录标号为(k,n)的缓存信息存储在节点标号为(k,n)后继节点上，所以缓存目录信息指该节点负责管理的缓存目录，包括目录标号，网络中实际存储该缓存的源节点的信息列表（IP和端口）。图2为节点(4,3)的缓存目录信息表结构图。 c)路由表包括两部分，即子区域内所有节点的路由信息和其他子区域内的邻居节点。通过前者
10、可以单跳到达本子区域内的任意节点；通过后者可以单跳到达空间内的其他任意子区域，这种结构可以保证最多两跳查询到目标节点。子区域内节点路由信息一共m项，每一项包括后继节点标号和IP。区域间路由信息包括(k-1)项，每一项保存其他子区域内物理距离较近的物理邻居节点列表，包括节点标号、节点IP和网络延时RTT值。图3表示节点(4,3)的路由表结构。 2. 2 本地缓存管理 当节点发送请求或者收到响应以后，首先应该判断请求或者响应的Web对象是否能够缓存，因为现在有越来越多的Web对象具有动态性交互性，不符合缓存的条件，没有必要向其他节点查询Web共享缓存，直接向服务器请求，可以加快用户的响应速度。判断
11、Web对象的可缓存性可以通过分析http的请求方式，http的响应状态码和URL的后缀属性等方法7来判定。节点通过解析http请求和响应的报文，通过特定的规则，来判断出对象的可缓存性。 节点为每个缓存对象建立一个结构体，保存缓存信息： typedef struct const char* url，/缓存网页的URL void*cache_data，/缓存数据的地址 size_t size，/缓存数据的大小 const char*content_type, /http响应头中的contenttype const char*response_header，/http响应头 int last_tim
12、e_modified，/上次修改时间 intlast_time_visited，/上次访问时间 int time_expired，/过期时间 int visit_times，/缓存命中次数 PriorityListNode*pnode，/优先级链表节点指针 CacheData； 节点通过URL的hash值建立本地缓存目录索引，所有的缓存对象放在一个hash表中，通过hash值可以很快查找出对应的缓存信息。 为保持缓存对象的一致性，必须对缓存作不定时更新和清除等。节点为所有缓存的引用维护一个双向列表priorityList，采用LRU(least recently used)策略对缓存进行维护，
13、如果缓存被请求命中，将该对象调整至列表首位，最新命中的缓存和命中次数多的缓存具有较高的优先级。当Web对象第一次被缓存时，该缓存引用加入列表首位，同时将该缓存目录信息通知此节点对应的目录索引节点。系统也不定期地进行缓存清理，维持缓存规模大小和最新状态，将时间过期的、命中次数低的缓存对象从hash表和priorityList中清除，同时通知保存该目录信息的节点更新其缓存目录信息，保持系统同步更新。 2. 3 节点查询 节点截获到自身的http请求以后，首先判断是否满足缓存条件，如果可缓存，向网络中其他节点查询，否则直接向Web服务器请求。向其他节点查询缓存的过程如下： a)首先计算URL的has
14、h值，得到该目录存储的目标节点(k, id)。 b)若目标节点在本子区域，直接转发给(k,id)的后继节点；否则，向路由表区域k中物理距离最近的邻居节点发送目录查询请求，邻居节点再将查询请求转发给(k,id)的后继节点，如果命中，将缓存目录信息返回，否则返回查询失败的消息。 c)发起者收到目录信息，向实际存储该缓存的节点发送缓存内容请求，在规定时间内如果收到内容，则查询结束；否则直接向Web服务器请求Web对象。 d)发起者获取了完整的Web对象以后，如果该对象可缓存，将该对象添加到本地缓存中，同时通知目标节点(k,id)的后继节点自己拥有该缓存副本。 整个查询过程最多只经过一次转发，查询步长
15、为?O(2)，考虑缓存获取高效性，根据实际响应最大延时设定查询时限，超时即认为查询失败。 消息类型和消息体的定义如下： typedef enum CACHE_DATA_REQUEST， /请求缓存对象 CACHE_IP_REQUEST，/请求缓存源节点 CACHE_DATA_RESPONSE，/响应缓存对象 CACHE_IP_RESPONSE， /响应缓存源节点 CACHE_REQUEST_FAIL，/查询请求失败 NOTIFY_HAS_URL,/通知拥有缓存副本 NOTIFY_NODE_LEAVE,/通知节点离开 NOTIFY_URLINDEX_TRANSFER,/通知缓存目录转移 MsgT
16、ype； typedef struct MsgType msg_type；/消息类型 int url_id； /URL目录的hash值 unsigned intsrc_ip；/请求发起者的IP unsigned int ip；/消息发起者的IP char* data；/消息返回内容 MsgData； 2. 4 节点的加入和离开 在一个动态网络中，节点可以在任意时刻加入和离开。为了确保系统在网络中能及时定位查找目标节点，需要及时更新相关节点的路由表信息。 节点加入时，可以通过某种方式（如广播）获得一个相同子区域内的某个邻居n，然后用n的路由表来初始化自己的路由表，并向自己的后继节点请求管理自己负
17、责的缓存目录信息，同时修改自己的区域内节点信息列表，并将自己上线的消息信息采用泛洪的方式通知子区域内的其他所有节点。 节点离开，正常退出时也只要自己负责的缓存目录信息转移到环上相邻的下一个活动节点并通知本子区域自己离开；非正常退出时，子区域内的节点信息采用被动发现的方式更新。区域内任意节点执行查询操作发现某后继节点无效后，更新自己的节点信息表，并通知大家。节点加入和退出需要发送O(m)条消息告知所属区域其他节点。 路由表中区域间邻居节点采用动态加入更新的办法，对于每个子区域均对应管理一个节点列表，只要其他子区域有节点与自己发生连接，就将该节点按照RTT值大小插入到列表中。其实每个区域内的所有节
18、点可以维护一个相同的区域间邻居节点，但是每个节点具有平等性并且RTT值不一样，所以采用独自管理的方式。在空闲期，发送测试消息维护列表最新状态，将无法响应的节点从列表中删除，当列表出现空邻居后，可以从区域内邻居节点获取。 3 性能评估 3. 1 性能分析 1）负载均衡 它是影响分布式系统性能的重要因素，本文采用一致性哈希函数保证所有的缓存以很大的概率均匀分布在系统的各个节点上。同时节点向其他节点获取缓存成功之后，缓存该Web对象，即同一对象在系统中有多个副本，对于提高获取速度和解决Web访问热点现象均有效。 2）节点代价 在这个系统中本地缓存的开销可以设定为固定大小，并定时更新维护。每个节点除了
19、本地缓存以外需要管理大量信息，在（N=km）大小的系统中内存开销可以表示为S(k,N)=AN/k+B(k-1)+C(其中：A为子区域内每个节点的路由信息;B为到达其他子区域的路由信息;C为缓存目录信息)。在系统负载均衡条件下，缓存目录信息C大小近似相等,每个子区域的路由信息对应一个节点列表，可以取B=2A，那么S(k,N)在k=N/2时取最小值。比如在N=100 000的系统中，划分k=223个子区域，每个区域有447个节点。假定每个节点路由信息需要40 Byte，每条缓存目录信息（缓存系统中可能有多项副本）需要500 Byte，每个节点管理100条目录信息，那么平均每个节点的内存开销S(22
20、3,100 000)只有 85.7 KB。 3）状态维护 当系统中的节点发生变化（包括发布缓存消息、节点加入和离开），系统必须做两件事，即更新节点自身信息和通知其他节点发生了变化。 系统发布缓存消息只需要查找到目标节点的后继，然后存储目录信息即可。系统路由查询只需要O(2)的代价，而且相当部分缓存消息发布均是副本发布，可以直接利用缓存请求得到的路由查询结果。 节点加入和离开的消息通知采用泛洪（flooding）方式，一个节点变化只需要通知该子区域内的其他节点。关于Gnutella和Napster的一项研究8表明：在100 000个节点规模的开放式网络中，平均每秒只有19个成员发生状态变化。那么
21、可以推论出在一个105106个节点的网络缓存系统中，只有20200个节点发生状态变化，平均每个子区域不到一次，而且每个子区域内的节点数目数量级在103以下，由此可知节点加入和离开的泛洪消息造成的背景带宽负载很小。节点离开时后继节点接管自己的缓存目录信息，对其他节点也无影响。 区域节点邻居的更新采用主动探测的方式。当该子区域内有节点与自己相互发生查询请求或其他连接，就将该节点作为子区域邻居候选节点，根据RTT值更新区域邻居列表。这样保持区域邻居节点均是最近活动且物理距离相对近的。同时将相互共享过缓存的节点设为物理邻居，可以增加节点按兴趣聚类的可能，提高查询速度。 4）其他 为了减轻系统的存储压力
22、，位于同一个页面下的大量不同Web对象的目录信息只存储一次，因为在同一个页面下的Web对象具有极大相关性，通常请求是连续发生，所以只需要将主页面的目录信息存储在目标节点，节点在响应用户请求时，在发送主页面对象的同时，将相关的Web对象一起响应给用户，也提高了用户的响应速度。 3. 2 仿真实验评估 本文采用NS2网络仿真软件对缓存系统进行仿真实验评估，多用户节点运行在同一台机器。仿真对象来自UC Berkeley home IP Web traces9位于proxy缓存服务器上的trace记录，一共916个节点，95 768 条请求，时间为4 h，应用proxy中心缓存方式。仿真时每个客户节点
23、对应于一个仿真节点，所有节点位于一个网关下面，节点之间的链路延时是毫秒级；网络拓扑采用GT拓扑生成器生成，节点之间采用flat模式以0.2概率互连。节点分组如下：916个节点，分成23个子区域，每个子区域40个节点。假定每个节点的默认缓存大小为1 MB，节点以指数分布概率离开网络。仿真实验主要基于以下度量指标：命中率、外部带宽、系统响应延时、缓存空间大小。 1）命中率 包括响应命中率和字节命中率。前者指网络中所有节点发出的请求被缓存命中响应的百分比；后者指缓存命中的字节数占所有请求总字节数的百分比。本地分布缓存命中字节数可以降低网络外部带宽。影响缓存命中率的因素包括节点的缓存大小、系统的动态性
24、（包括节点的加入和退出）。 图4是缓存大小变化对命中率大小的影响。原日志中记录响应命中率为0.335，字节命中率为0.258。可以看出，随着每个节点本地缓存的增加，命中率得到很大的提高，超过1 MB以后变化很缓慢，均已接近中心缓存的命中率大小，所以说在具有适当缓存空间大小条件下，本方法可以与中心缓存效果相当；同时可以看出字节命中率比响应命中率要小，这时因为缓存存储一般采用的是小文件优先的原则。 2）外部带宽 缓存可以降低网络的外部带宽，图5比较了DHT缓存、proxy中心式缓存和无缓存三种情况下网络外部带宽的变化情况。可以看出DHT分布式缓存和中心式缓存一样，都极大地降低了网络的外部带宽，降低
25、了系统对外的流量。 3）响应延时 图6、7统计所有命中记录的延时，包括目标查询延时和目标获取延时，可以看出查询目标节点延时集中在100150 ms，获取目标对象延时集中在150200 ms,因为目标对象链路传输的延时稍大。在O(2)步长DHT存储的条件下，缓存命中的总时间一般小于500 ms，具有低延时特点。 4）缓存大小 为了控制缓存的规模和实际应用的需要，设定每个节点上的最大缓存为10 MB。图8揭示了缓存大小随时间的变化趋势，可以看出节点上的平均缓存大小随时间增长而变大，在4 h以内平均缓存大小大约在500 KB以下。可以看出，本方法对缓存空间要求相对比较小，易于在内存受限的设备上使用。 4 结束语 本文设计了适用于Web缓存应用的查询路由步长为O(2)的路由方法，并提出一种查询步长短、节点负载小、缓存内容及目录信息分布存储的基于DHT的Web缓存共享方法。从仿真实验可以看出，此分布式Web缓存在命中率、内存空间成本、系统响应延时等方面均有令人满意的性能。它相对于传统proxy中心缓存，充分利用了单个节点带宽和资源，提高了http请求的响应速度，节约网络带宽，适用于构建一个高效大规模的缓存系统。