GroupCache — source code reading

GroupCache 源码阅读

总述

项目地址:https://github.com/golang/groupcache

题外话,是memcached的作者写的,细节处还是很精彩的

groupcache已经在dl.Google.com、Blogger、Google Code、Google Fiber、Google生产监视系统等项目中投入使用

相对于go-cache而言,groupcache提供了分布式的缓存功能,功能复杂度降低(见制约),但是大规模的缓存能力提升。

框架灵活性强,可以灵活定制缓存策略,缓存源数据无关性

还满足多节点缓存的分布式一致性hash,以及本地缓存miss后向其他缓存查询的机制。

框架较为健壮,细节上对效率有考究,可以应对缓存击穿、缓存穿透问题以及缓存雪崩问题

Tips:看bradfitz大佬的这个源码,可以重点关注大段的注释和TODO,都是很值得思考的部分

制约

只能get、remove,不支持update,只能remove后再get

过期机制为限制cache队列长度,不能设置过期时间,只能通过内置lru淘汰过期数据;

经常变更的数据不适合groupcache作为缓存;

注意一点,groupcache的consistenhash实现只能增加节点,无法减少节点,若要实现该功能,要注意当减少节点时,如果有相同的虚拟节点映射到同一个位置,则要判断删除的数量。增加不存在问题,因为增加的时候后来的虚拟节点可以替换先设置的虚拟节点,不影响使用。

源码分析:

先说下大体文件结构:

因为groupcache是一个库性质的,所以没有main入口,但是看使用示例也知道,入口是groupcache.go的NewGroup,  所以应该从groupcache.go文件开始分析。

http.go实现了peers之间的http查询缓存的请求方法和响应服务,

groupcachepb提供了上述节点之间其消息序列化和反序列化协议,基于protobuf,在groupcache.proto中定义。

peers.go抽象了缓存节点,提供了注册、获取节点的机制

sinks.go抽象了数据容器, 可以以不同的方法初始化设置,最终以统一的字节切片读出

byteview.go封装了字节切片的多种操作方法

singleflight保证了多个相同key的请求下的加锁等待,避免了热点缓存击穿问题, waitGroup实现

lru提供了lru策略的实现,过期方式为队列长度超预期则删除。

consistenthash提供了分布式一致性hash的抽象,其本身并没有实现分布式一致性的hash,而是可以以指定的hash完成分布式一致性的key的定位和节点的增加,注意这里没有实现节点删除。

后面细说:

groupcache.go:

NewGroup提供了group的新增,内部完成了去重(重复注册则panic),并提供了两个位置的hook,一个是初次建立对等节点服务的hook(initPeerServer,其实不算hook,算是提供的初始化定制策略),另一个是新建缓存组的hook(newGroupHook)

查看group定义,getter是传入的回调函数,给出了当本地miss同时缓存节点miss,或者本地miss,但该key属于本节点维护时该如何获取数据的函数。见load

里面有两个cache,一个是mainCache,其实就是本地的cache,hotCache是当本地miss,向其他缓存请求时本地也会缓存下来,防止反复向其他对等节点的请求。

flightGroup定义了接口,用以保证对同一个key的并发请求不会引起大量的peers间的请求,用waitGroup实现,具体实现文件在singleflight.

_ int32用来在32bit平台上强制8字节对齐的(这个较少遇到)

Stats是一些统计,比如缓存请求数,hit数,peer请求数等等

重点是Get和load函数的分析

destPopulated := false   //由于load中会对并发的请求做处理,只有最先到的请求会直接向对等节点请求,执行loadGroup.Do的传入参数二的闭包函数,而该函数调用了getLocally设置了dest,其他的只会等待,所以需要这个标志,对没有直接请求的另外执行setSinkView完成值的传递。

这两个函数之后的内容就好分析了很多,只单独说下populateCache,该函数将新增的(无论从peer获取,或从数据源getter获取)key\value存入对应的缓存,peer→hotCache, 数据源获取→mainCache,

并在该函数内实现了对cache的维护,当两个cache超过总的大小限制,则根据lru删除多余的内容,并保证hotCache大小小于mainCache/8

接下来看http.go和Peer.go部分:

其中 Context可根据情况定制,主要用于服务端,将接收到的http请求转换成指定的context类型,便于进一步处理

Transport可根据情况定制,主要用于客户端,将一个向对等节点发起的请求context,转换成指定的Http访问方式,其中 RoundTripper为实现了

RoundTrip(*Request) (*Response, error)的接口,故而,HTTPPool可以实现访问方式的灵活定制

self为该节点本身的URL,为监听服务的地址

opts为HTTP池的默认选项

其余的,通过实现PickPeer函数实现了接口PeerPicker,此函数用于根据key得到对应的对等节点peer,返回的peer的表现形式为实现了

ProtoGetter接口的对象,而该接口提供了Get方法,然后于getFromPeer中被调用,用以获取peer中对应key的value值

如此一来,peer.go中的最重要的两个接口PeerPicker\ProtoGetter也都介绍了,peer.go中就剩下两个Regist函数,注册一个可以根据groupName获取PeerPicker的函数,

还有一个getPeers就是根据groupName获取PeerPicker的函数,可以继续其他文件分析。

sinks.go 和 byteview.go:

byteview很好理解,就是定义了一个新的结构体类型

其余的都是针对该类型实现的方法,read write等基本方法

重头戏是sink,

注释貌似说的很清楚,但是一看后面的实现,各种byte string sink byteview还是会有点凌乱,别急,不慌

Sink是一个接口,把它叫数据容器接口吧,这里面的方法分两部分,除了view,其余的设置方法都是将该接口对应的数据容器类型的内容用对应的类型进行设置,比如SetString就是用string进行初始化该sink

后面定义了实现该接口的多种类型

stringSink、byteViewSink、protoSink、allocBytesSink、truncBytesSink,顾名思义,不同的类型代表了其内部的存储方式的不同,

其每一种接口都实现了对应的初始化函数,比如以stringSink为例

其实就是把该类型内部用于存储的数据容器进行初始化,以便后续SetXXX的时候可以正常设置不panic,

其中byteViewSink必须用non-nil的字节slice初始化,而allocBytesSink可以传入nil自行分配内存

此外这两种byteSink还提供了setView函数,以满足一个内部接口,函数setSinkView函数的内部接口viewSetter,

可以看到通过这个内部接口可以进行sink类型的区分,如果该sink类型可以成功转换成viewSetter接口,则说明其支持直接用byteView进行内容填充,则可以避免写入和读出的两次内存拷贝。Smart!

这里提醒下golang 初学者,使用sink的地方,比如groupcache.go中的Getter接口,其方法

Get(ctx Context, key string, dest Sink),初学者会好奇,为啥sink传入的不是指针,那么如何能在函数作用域内修改其值而传递出来,其实Sink是interface,interface就包含了两个指针,

一个对象指针,一个运行时类型指针,参考https://stackoverflow.com/questions/44370277/type-is-pointer-to-interface-not-interface-confusion

所以传入的对象是可以被修改的,而且,golang 中是不提倡使用 *interface类型

lru.go:

实现了lru策略的缓存,注意,没有锁机制,所以不是线程安全 的,需要根据应用场景,在调用层进行并发读写控制, 本项目中应该是考虑缓存的应用场景不涉及key对应的value的update,而key和value作为整体放在entry

类型中,最坏的情况是cache miss, 所以没有用锁,但值得思考的是,list没有加锁的情况下进行移动和节点增删,会导致怎样的问题, TODO 需要分析汇编码,maybe crash

其他的可以简单过一下了:

singleflight.go 核心两个结构体,其用Group管理着同一个group中遇到的对相同key的访问,该访问存于Group.m中,用mu加锁保护读写,当同时有并发的请求,Group.m中会查询到该key, 于是不执行请求,进入

call.wg.Wait(), 直到最先到达的那个完成call.wg.Done(),如此减少了并发key请求下对peer网络的压力。

groupcachepb就不说了,参见protobuf相关的内容

最后就剩一个consistenthash.go,要理解这个当然要先去看下分布式一致性hash的原理,再看代码会轻松很多

另外是Get函数将指定key映射到指定group的过程

hash := int(m.hash([]byte(key)))

// Binary search for appropriate replica.
idx := sort.Search(len(m.keys), func(i intbool { return m.keys[i] >= hash })

重点是groupname的映射和key的映射是使用相同的hash算法。

参考:

https://studygolang.com/articles/6209

https://www.jianshu.com/p/f69f3a3a9a78

https://www.jianshu.com/p/fc39399a27f1

发表评论