缓存算法比较freecache lru s4lru

3190阅读 0评论2018-08-28 oxwangfeng
分类:服务器与存储

memcache:用到memcache
memcache用于存储域名,类似于lru,不过相对于lru,添加了put time和过期时间;
实现方法:
cache map[string]*list.Element
data *list.List
set: set(key,v,expires)
set的时候就会将过期时间写入到item中;key是入参key,value.v=v,value.put_time=now,value.deadline=now+expires;
get: get(key)
如果key存在并且没有过期,则返回;
memcache用的地方:
1. 用于存放域名配置;域名配置缓存一段时间;
2. 用于存放分级缓存;key是url,value是限速limit;value中包含计数器,计数器采用令牌桶实现;
lru:
有以下几部分组成:
data map[string]*list.Element
list *list.List
maxSize int64
curSize int64
注意:
1. map中key是url,或者fragment url,value是对应的object或者fragment;map中的value是一个指针,list的数据也是用这个指针,两个指向相同的数据;
2. list只包含maxSize个数据,map中也只包含maxSize个数据,当list的数据删除时,map中数据也会删除;

set: set(key,value)
1. 当map中包含key时,则说明lru已经包含这个数据,只是更新数据;
map[key] = newValue; 更新map指针;
list.MoveToFront(e); 将新插入的数据挪到list的最前面,说明这个是最近访问的;
判断是否超过了缓存空间最大值,如果超过,则从list尾部删除一个元素(map中也删除对应的元素)
2. 当map中不包含key时,则更新数据;
和上面差不多,只是map[key] = Value;
get: get(key)
1. 返回map[key] 中的内容
2. c.list.MoveToFront(e);将这个数据挪到list的最前面,说明这个是最近访问的;
delete:
将map和list的对应的数据都删除;

s4lru:
有以下几部分组成:
data map[string]*list.Element
lists []*list.List 总共四层list
maxBytes int
注意:
1. 一共四层list,最下面一层是第0层,最上面一层是第3层;
2.每个元素数据结构是cacheItem,包含idx(第几层),key,value
set: set(key,value)
1. 不管更新还是新的插入数据,都写入到第0层;// 如果是更新的话,也写在第0层,因为是新的数据;
2. 如果第0层队列不满的话,则直接放到list[0]的头部,并且更新map;
3. 如果第0层队列满的话,则list[0]尾部元素删除,然后将新的元素写入到list[0]头部,并且更新map;
get: get(key)
1. 根据map获取key对象的value(即cacheItem),里面包含idx(所在层数);
2.如果是在最上层,即第三层,则直接返回;
3.如果不在第三层,,并且所在层数的上层(idx+1)不满的话,则挪到上一层(idx+1)的头部;具体操作是indx层的这个数据删除,
4.如果不在第三层,,并且所在层数的上层(idx+1)满的话,则为了避免内存分配,需要进行空间交换;
将idx+1层的尾部元素挪到idx层的头部;
将查找的元素,挪到idx+1的头部;
delete:
将map和list的对应的数据都删除;
上一篇:traffic server笔记
下一篇:golang指针和c指针区别