类redis分布式缓存

实现一个分布式缓存，功能有：LRU淘汰策略，http调用，并发缓存，一致性哈希，分布式节点，防止缓存击穿

1.实现LRU淘汰策略

map
maxSize

img

代码实现

具体代码实现看：本人GitHub上给出的代码

定义了三个数据结构

Value
entry
Cache
type Value interface {

	//返回占用的内存大小
	Len() int
}

type entry struct {
	key string
	value Value
}

type Cache struct {
	//允许使用的最大内存
	maxBytes int64

	//当前已使用的内存
	nbytes int64


	ll *list.List

	cache map[string] *list.Element

	//某条记录被移除时的回调函数，可以是nil
	OnEvicted func(key string, value Value)

}

OnEvictedOnEvicted

2.实现单机并发

sync.Mutex
type cache struct {
	mu sync.Mutex
	lru *lru.Cache
	cacheBytes int64
}

cache并没有new方法，因为采用的是延迟初始化 在add方法中，判断c.lru是否为nil，如果等于nil再创建 这种方法称为延迟初始化，一个对象的延迟初始化意味着该对象的 创建将会延迟至第一次使用该对象时。 这个方法在redis中很常见，因为能一定程度上提高性能

func (c *cache) add(key string, value ByteView){
	c.mu.Lock()
	defer c.mu.Unlock()
	if c.lru == nil{
		c.lru = lru.New(c.cacheBytes,nil)
	}
	c.lru.Add(key,value)
}

3.主体结构

本质上是再进行一次封装

难道一台机器就只有一个缓存表吗？你打开redis的可视化工具，能看到redis还有16个池呢，所以我们要实现多个缓存表。怎么做？再加一层。试想一下：

//groups 实例集合表
groups = make(map[string]*Group)

img

并发cache
//这里的group是实例
type Group struct {
	name string
	getter Getter
	mainCache cache
}

4.http服务调用

/_mycache/
http://XXX.com/_mycache//
groupnamegroupsnamekeykey
groups[groupname][key]

5.一致性哈希

一致性哈希抽象的解释就是一个很大的环，但是在实现的时候，我们总不可能声明一个有个成千链表节点的环吧，何况其中大多节点还是闲置节点，没有实际的作用，所以我们需要在逻辑上去声明哈希环。

6.数据结构

img

（真实节点就是指机器，虚拟节点相反）

type Map struct {
	hash Hash
	virMpl int
	keys []int
	hashMap map[int]string
}

hashvirMplkeys[int]stringkeyvalue

7.添加真实节点

代码注释写的很详细了，就不多说了。

缺点是，当有一个真实节点添加进来的时候，所有值都要重新计算一遍。这在并发情况下，会造成一定拥塞。因为在重新计算期间，不能进行正确的访问操作。

欢迎提供解决思路。

func (m* Map) Add(keys ...string){
	for _,realNodeKey:=range keys{
		for i:=0;i<m.virMpl;i++{
			/*
				keys中的每个真实节点都对映着virMpl个虚拟节点
				每个虚拟节点的key（即virNodeKey）为 i+realNodekey
				（即一个“不定数”，这里用i值，加上真实节点key
			*/
			virNodeKey := []byte(strconv.Itoa(i)+realNodeKey)
			/*
				对虚拟节点做哈希
			*/
			virNodeHash:= int(m.hash(virNodeKey))
			/*
				添加进哈希环，所以虚拟节点也存在于哈希环中
			*/
			m.keys = append(m.keys,virNodeHash)
			/*
				虚拟节点的hash对映某个真实节点的key
			*/
			m.hashMap[virNodeHash] = realNodeKey
		}
	}
	sort.Ints(m.keys)
}

访问真实节点:

get

分为三个步骤

virNodeHashkeysvirNodeHashindexkeys[index]hashMapkeys[index]
get

8.分布式节点设计

这一章涉及的东西有点多，在代码中给出了详细的注释，

主要是下面几个文件：

定义了两个抽象接口，用于远程节点的获取

peer.gohttpGetter

集成了一致性哈希表，使用http访问各个节点