缓存系统多副本生成与最优副本查找算法

70阅读 0评论2017-12-01 oxwangfeng
分类:服务器与存储

在缓存系统中,一个资源一般都有几个副本,而如何生成这些副本以及如何从已有的副本中选择最优副本是非常重要的问题;
一般的方法如下:
1.查找当前url的副本集合,查找算法也就是选择最优副本的算法(在下面)
2.如果查找到最优副本,则读取最优副本的body,返回给client;
3.如果没有查到最优副本或者当前url没有任何副本,则只能创建一个副本,然后放到副本集合中;创建副本的办法:一般是将request header和response header作为一个集合作为副本,副本可以包含body,也可以包含body的指针;
4.如果副本集合超过了最大副本数目(一般都有设置,比如5个),则删除最久没有使用的副本。因为每个副本插入或者更新的时候都会更新update time,所以很容易得到哪个副本已经最久没有使用了;

选择最优副本的算法:
选择副本:1.quality;2.新鲜度
1.Quality:
根据这几个因素生成(Accept,Accept-Charset,Accept-Encoding,Accept-Language),这几个因素包括request和cache的
2. 新鲜度:
计算因素:副本的request time,response time,response里面的date字段,还有现在的时间(now);
针对每个副本都计算Q和current_age,然后根据
if ((Q > best_Q) || ((Q == best_Q) && (current_age <= best_age))) {best_Q = Q;best_age = current_age;best_index = i;}
best_index就是最佳副本索引
quality计算
如果vary不存在,accept-charset,accept-encoding,accept-language这些都可以忽略;Q=1.0;
如果vary存在,则根据如下规则计算Q;
accept quality计算,得出Q[1]
1.例如 Accept: q=0.5, text/html ?type是text,子类型是html?1.如果client的accept为type是*,那么直接返回q;
2.如果type不是*,子类型是*,并且子类型值与副本中的content-type相同,则直接返回q;
3.如果不是上面两种,则严格匹配accept的值和副本的content type的值了,必须严格一致,如果一致,则返回q;(优先级较高)
Content-encoding quality 计算, 得出Q[2]
1. 如果client的accept-encoding和副本的accept-encoding精确匹配啊;直接返回1.001;
2. 如果client的accept-encoding和副本的content-encoding都不存在,则返回1.0;
3. 如果副本中没有content-encoding,则设置content-encoding=identity;
4. 如果副本中有多个content-encoding,则则计算q;计算规则:如果副本”content-encoding: a, b",在client请求头有a和b的quality因子,则q=q_a * q_b;
charset quality计算;得出Q[3]
1. 如果client的Accept-Charset和副本的Accept-Charset精确匹配啊;直接返回1.001;
2. 如果client的Accept-Charset和副本的Accept-Charset都不存在,则返回1.0;
3. 如果Accept-Charset=*,则wildcard_q=q;如果不是通配符(优先级高),则计算q;
4. 默认是utf-8,即client和副本没有提示字符集,默认按照utf-8处理;
accept language和charset quality计算方式差不多,得出Q[4];
每个副本的Q=Q[1]*Q[2]*Q[3]*Q[4];
计算每个副本的Q,然后选出最大Q作为副本,如果Q相同,则比较新鲜度;

上一篇:if-range引起的cdn分片缓存问题
下一篇:缓存服务器syns to listen sockets drop导致创建socket失败