服务…

Used)实现Lru查找功能删除新增/修改测试单机并发缓存主体结构

Group回调

服务端自测一致性哈希(hash)Why一致性哈希我该访问谁节点数量变化了怎么办一致性哈希什么是一致性

hash

客户端实现主流程测试防止缓存击穿缓存雪崩、缓存击穿与缓存穿透singleflight

模仿groupcache(Go

设计一个分布式缓存系统需要考虑资源控制、淘汰策略、并发、分布式节点通信等各个方面的问题。

而且针对不同的应用场景还需要在不同的特性之间权衡例如是否需要支持缓存更新还是假定缓存在淘汰之前是不允许改变的。

不同的权衡对应着不同的实现。

groupcache

的作者。

无论是了解单机缓存还是分布式缓存深入学习这个库的实现都是非常有意义的。

支持特性有

认为最早添加的记录其不再被使用的可能性比刚添加的可能性大。

这种算法的实现也非常简单创建一个队列新增记录添加到队尾每次内存不够时淘汰队首。

但是很多场景下部分记录虽然是最早添加但也最常被访问而不得不因为呆的时间太长而被淘汰。

这类数据会被频繁地添加进缓存又被淘汰出去导致缓存命中率降低。

LFU(Least

的实现需要维护一个按照访问次数排序的队列每次访问访问次数加1队列重新排序淘汰时选择访问次数最少的即可。

LFU

算法的命中率是比较高的但缺点也非常明显维护每个记录的访问次数对内存的消耗是很高的另外如果数据的访问模式发生变化LFU

LFU

算法受历史数据的影响比较大。

例如某个数据历史**问次数奇高但在某个时间点之后几乎不再被访问但因为历史访问次数过高而迟迟不能被淘汰。

LRU(Least

算法的实现非常简单维护一个队列如果某条记录被访问了则移动到队尾那么队首则是最近最少访问的数据淘汰该条记录即可。

LRU

蓝色的是字典(map)存储键和值的映射关系。

这样根据某个键(key)查找对应的值(value)的复杂是O(1)在字典中插入一条记录的复杂度也是O(1)。

红色的是双向链表(double

linked

list)实现的队列。

将所有的值放到双向链表中这样当访问到某个值时将其移动到队尾的复杂度是O(1)在队尾新增一条记录以及删除一条记录的复杂度均为O(1)。

实现Lru

make(map[string]*list.Element),onEvicted:

onEvicted,}

map[string]*list.Element键是字符串值是双向链表中对应节点的指针。

maxBytes

int用于返回值所占用的内存大小。

只要可以调用len函数的类型都实现了len接口)方便实例化

Cache实现

个步骤第一步是从字典中找到对应的双向链表的节点第二步将该节点移动到队尾。

Get

移到队尾部c.linker.MoveToBack(val)//

将list.Element.Value类型断言为entrykv

kv.value,

}如果键对应的链表节点存在则将对应节点移动到队尾并返回查找到的值。

c.ll.MoveToBack即将链表中的节点

ele

移动到队尾c.linker.MoveToBack(ele)//

获取entry(key,val)kv

当前内存占用为旧val长度-新val长度c.currentBytes

int64(value.Len())

String(德玛西亚)c.Add(fmt.Sprintf(name_%d,

i),

类型是为了能够支持任意的数据类型的存储例如字符串、图片等。

实现

Len()

Initialization)一个对象的延迟初始化意味着该对象的创建将会延迟至第一次使用该对象时。

主要用于提高性能并减少程序内存要求。

主体结构

最核心的数据结构负责与用户的交互并且控制缓存值存储和获取的流程。

key

思考一下如果缓存不存在应从数据源文件数据库等获取数据并添加到缓存中。

GeeCache

是否应该支持多种数据源的配置呢不应该一是数据源的种类太多没办法一一实现二是扩展性不好。

如何从源头获取数据应该是用户决定的事情我们就把这件事交给用户好了。

因此我们设计了一个回调函数(callback)在缓存不存在时调用这个函数得到源数据。

Getter

方法。

函数类型实现某一个接口称之为接口型函数方便使用者在调用时既能够传入函数作为参数也能够传入实现了该接口的结构体作为参数。

借助

GetterFunc

Getter即缓存未命中时获取源数据的回调(callback)。

第三个属性是

mainCache

开头的请求就用于节点间的访问。

因为一个主机上还可能承载其他的服务加一段

Path

strings.SplitN(r.URL.Path[len(p.basePath):],

2)if

http.StatusBadRequest)return}//

parts[0]key

http.StatusInternalServerError)return}//

返回响应w.Header().Set(Content-Type,

写入val_,

并绑定getter函数Cache.NewGroup(test,

110,

Cache.NewHTTPPool(addr)log.Println(geecache

running

addr)log.Fatal(http.ListenAndServe(addr,

peers))

}访问http://127.0.0.1:9999/_generalcache/test/1

响应1

访问http://127.0.0.1:9999/_generalcache/test/Tom

响应630

对于分布式缓存来说当一个节点接收到请求如果该节点并没有存储缓存值那么它面临的难题是从谁那获取数据自己还是节点1,

个节点当一个节点接收到请求时随机选择一个节点由该节点从数据源获取数据。

1/10

的概率选择了其他节点如果选择了其他节点就意味着需要再一次从数据源获取数据一般来说这个操作是很耗时的。

这样做一是缓存效率低二是各个节点上存储着相同的数据浪费了大量的存储空间。

key每一次都选择同一个节点呢使用

值解决了缓存性能的问题但是没有考虑节点数量变化的场景。

假设移除了其中一台节点只剩下

个那么之前

9也就意味着几乎缓存值对应的节点都发生了改变。

即几乎所有的缓存值都失效了。

节点在接收到对应的请求时均需要重新去数据源获取数据容易引起

缓存雪崩缓存在同一时刻全部失效造成瞬时DB请求量大、压力骤增引起雪崩。

常因为缓存服务器宕机或缓存设置了相同的过期时间引起。

一致性哈希算法可以解决上述问题。

一致性哈希

一致性哈希算法也是使用取模的方法但是取模算法是对服务器的数量进行取模而一致性哈希算法是对

2^32

步骤一一致性哈希算法将整个哈希值空间按照顺时针方向组织成一个虚拟的圆环称为

Hash

函数进行哈希具体可以选择服务器的IP或主机名作为关键字进行哈希从而确定每台机器在哈希环上的位置步骤三最后使用算法定位数据访问到相应服务器将数据key使用相同的函数Hash计算出哈希值并确定此数据在环上的位置从此位置沿环顺时针寻找第一台遇到的服务器就是其应该定位到的服务器

算法原理

的哈希值放置在环上顺时针寻找到的第一个节点就是应选取的节点/机器。

环上有

也就是说一致性哈希算法在新增/删除节点时只需要重新定位该节点附近的一小部分数据而不需要重新定位所有的节点这就解决了上述的问题。

数据倾斜问题

为了解决这个问题引入了虚拟节点的概念一个真实节点对应多个虚拟节点。

个真实节点对应

peer1-3通常以添加编号的方式实现其余节点也以相同的方式操作。

Hash

虚拟节点扩充了节点的数量解决了节点较少的情况下数据容易倾斜的问题。

而且代价非常小只需要增加一个字典(map)维护真实节点与虚拟节点的映射关系即可。

Go语言实现

hashMap键是虚拟节点的哈希值值是真实节点的名称。

构造函数

New()

CRC32:CRC本身是“冗余校验码”的意思CRC32则表示会产生一个32bit8位十六进制数的校验值。

由于CRC32产生校验值时源数据块的每一个bit位都参与了计算所以数据块中即使只有一位发生了变化也会得到不同的CRC32值.m.hash

Add()

int(m.hash([]byte(strconv.Itoa(i)

key)))//

中增加虚拟节点和真实节点的映射关系。

最后一步环上的哈希值排序。

Get()

m.hashMap[m.keys[idx%len(m.keys)]]

key

fmt.Sprintf(%v%v/%v,h.baseURL,url.QueryEscape(group),url.QueryEscape(key),)//

发送请求res,

http://example.com/_geecache/。

使用

http.Get()

host:port/_general_cache/groupName/key

const

consistenthash.New(defaultReplicas,

nil)p.peers.Add(peers...)p.httpGetters

len(peers))for

方法实例化了一致性哈希算法并且添加了传入的节点。

并为每一个节点创建了一个

HTTP

RegisterPickerToCacheGroup(picker

NodePicker)

g.cacheGetter.Get(key)log.Printf([LOCAL

INFO]

加入缓存g.baseCache.addKeyToCache(key,

value)return

getter.GetKeyFromGetter(g.groupName,

key)if

指定三个节点并用命令行启动。

我们只在7777节点返回Tom其他节点则需要http通信去获取Tom的信息。

func

cachehttp.NewHTTPServerPool(fmt.Sprintf(127.0.0.1:%d,

port))server.AddNode(127.0.0.1:7777,

127.0.0.1:8888,

key)}))}c.RegisterPickerToCacheGroup(server)log.Println(http.ListenAndServe(fmt.Sprintf(127.0.0.1:%d,

port),

缓存雪崩缓存在同一时刻全部失效造成瞬时DB请求量大、压力骤增引起雪崩。

缓存雪崩通常因为缓存服务器宕机、缓存的

key

缓存击穿一个存在的key在缓存过期的一刻同时有大量的请求这些请求都会击穿到

缓存穿透查询一个不存在的数据因为不存在则不会写到缓存中所以每次都会去请求

singleflight

次请求。

假设对数据库的访问没有做任何限制的很可能向数据库也发起

key

发起三次请求也是没有必要的。

那这种情况下我们如何做到只向远端节点发起一次请求呢

generalcache

如果request存在,则等待执行完成g.mu.Unlock()req.wg.Wait()return

req.val,

new(singleflight.RequestGroup),}groups[groupName]

greturn

http://127.0.0.1:8888/_general_cache/score/Tomresponse

requests.get(url)print(response.text.encode(utf-8))with

ThreadPoolExecutor()

github地址https://github.com/Generalzy/GeneralCache学到了一致性哈希Lru算法