GeeCache概述
模仿goroupcache
,考虑:
- 资源控制、淘汰策略、并发、分布式节点通信
- 缓存更新、缓存淘汰之前是否允许改变
特性:
- 单机缓存和基于 HTTP 的分布式缓存
- 最近最少访问(Least Recently Used, LRU) 缓存策略
- 使用 Go 锁机制防止缓存击穿
- 使用一致性哈希选择节点,实现负载均衡
- 使用 protobuf 优化节点间二进制通信
常见缓存淘汰算法
FIFO
创建队列,新增记录添加到队尾,内存不够时淘汰队首
缺点:
- 早入队的数据若被常访问,导致频繁被添加缓存又被淘汰——>缓存命中率低
LFU
淘汰缓存汇总的访问访问频率最低的记录,维护按照访问次数排序的队列
缺点:
- 维护每个记录的访问次数消耗内存高
- LFU 算法手历史数据影响大
LRU
最近最少使用策略
LRU
核心数据结构

- map 存储字典映射,按key查找value 复杂度 O(1)
- 双向链表实现队列,将移动到队尾的复杂度是 O(1),在队尾新增记录和删除记录的复杂度均为 O(1)
结构体
包含字典和双向链表的结构体 Cache
type (
Cache struct {
// 允许使用的最大内存
maxBytes int64
// 当前使用的内存
nbytes int64
ll *list.List
cache map[string]*list.Element
// 某条记录删除时候的回调函数 可为 nil
OnEvicted func(key string, value Value)
}
entrty struct {
key string
value Value
}
// 值实现 Len() 方法则均可视为 value
Value interface {
Len() int
}
)
Get 移至队首
-
map 查找
c.cache[key]
-
调用
c.ll.MoveToFront(ele)
将所得封装为 entrykv:=ele.Value.(*Entry)
,返回kv.value
RemoveOldest 删除队尾和缓存 map
- 取出队尾
ele:=c.kll.Back()
- 存在则删除
c.ll.Remove(ele)
delete(c.cache,kv.key)
- 更新使用内存
c.nbytes-=int64(len(kv.key))+int64(kv.value.Len())
nbytes 前移偏移量为 kv 的大小(key+value.Len()) - 回调函数非空则使用回调函数
Add(更新、新增、越界)
-
添加节点已存在——>更新结点
- 缓存map存在则移至队首再更新结点值,
- 使用内存偏移量同步更新
c.nbytes+=int64(value.Len())-int64(kv.value.Len())
多使用新加入结点的 value 比原 value 大的部分
-
添加节点不存在——新增结点
- 移至队首
ele:=c.ll.MoveToFront(&entry{key,value})
- 新增缓存
c.cache[key]=ele
- 更新已使用内存
c.nbytes+=int64(len(key))+int64(value.Len())
- 移至队首
-
判定新增结点是否超容
for c.maxBytes!=0&&c.maxBytes<c.nBytes{ c.RemoveOldest()}
越界则移出队尾
00-概述
- 实现
LRU
缓存的并发控制 - 实现 Cache的核心数据结构
Group
,当缓存不存在时使用回调函数
01-并发 lru 读写
1.1 ByteView 缓存值只读
b []byte
存储真实的缓存值,支持任意数据类型存储(byte)- 实现
Len()
方法,支持 lru 的缓存对象的Value
接口 ByteSlice()
返回缓存 b 的复制,防止外部程序修改缓存

1.2 Cache 并发
- 实例化
lru
,封装get
和add
方法,添加互斥锁Mutex
type cache struct {
lru *lru.Cache
mu sync.Mutex
cacheBytes int64
}
add
方法使用 延迟初始化(lazy initialization) 在判读c.lru==nil
后再创建实例,使得对象的创建会延迟至第一次使用该对象时,提高程序性能,减少内存要求
02 主体 Group
2.1 逻辑
与用户之间的交互,控制缓存值的存储和获取
是
接收 key --> 检查是否被缓存 -----> 返回缓存值 ⑴
| 否 是
|-----> 是否应当从远程节点获取 -----> 与远程节点交互 --> 返回缓存值 ⑵
| 否
|-----> 调用`回调函数`,获取值并添加到缓存 --> 返回缓存值 ⑶
2.2 代码结构
step2/
|--lru/
|--lru.go // lru 缓存淘汰策略
|--byteview.go // 缓存值的抽象与封装
|--cache.go // 并发控制
|--geecache.go // 负责与外部交互,控制缓存存储和获取的主流程
2.3 回调 Getter
对于多种数据源(文件、数据库)缓存不存在时,使用回调函数获得源数据(将如何从源头获取数据交给用户)
type (
Getter interface {
Get(key string) ([]byte, error)
}
// GetterFunc 函数类型的参数和返回值与 Getter 接口内的 Get 方法一致
GetterFunc func(key string) ([]byte, error)
)
// GetterFunc 含有 Get 方法,在方法内调用自身,实现了接口 Getter
// 通过函数实现 Getter接口的 Get 方法,接口型函数
// 接口型函数只应用于接口内部之定义一个方法的接口
func (f GetterFunc) Get(key string)([]byte,error) {
return f(key)
}
#接口函数
接口函数:
- 将普通的函数类型(类型转换 GetterFunc(test)作为函数参数
- 将结构体作为参数
eg:
GetterFunc 类型的函数作为参数,支持匿名函数、普通函数(类型转换)
实现了 Getter 接口的结构体可作为函数参数
接口函数使用场景:
-
net/http
中的Handler
和HandlerFunc
type Handler interface { ServeHTTP(ResponseWriter, *Request) } type HandlerFunc func(ResponseWriter, *Request) func (f HandlerFunc) ServeHTTP(w ResponseWriter, r *Request) { f(w, r) }
-
http.Handle
和http.ListenAndServe
的第二个参数即为接口类型Handler
-
传入实现
Handler
接口的结构体则可以托管所有的 HTTP 请求,可扩展为 Web 框架 -
Java
中 lambda 表达式函数式编程可认为是接口函数- 自定义排序时,需要实现匿名的 Comparator 类,重写 Compare 方法
Collertions.sort(list,new Comparator<Integer>(){ @Override public int compare(Integer o1,Integer o2) { return 02-01; } });
- 1.8之后
lambda
从匿名对象简化为 lambda 表达式
Collections.sort(list,(Integer o1,Integer o2)->o2-o1);
-
定义
Getter
接口和回调函数Get(key string)([]byte,error)
-
定义函数类型
GetterFunc
实现Getter
接口内的Get
方法 -
定义函数类型 F,并实现接口 A 的方法,在方法中调用自身使得其他函数(参数与返回类型与 F一致)转化为接口 A
2.4 Group 定义
结构体
type Group struct {
name string
// 缓存未命中时回调函数
getter Getter
// 并发缓存
mainCache cache
}
- 视为缓存的命名空间,每个
Group
有唯一的name
getter Getter
为缓存未命中时的数据回调(callback)NewGroup
用于实例化 Group 并存储在全局变量groups
内GetGroup
获取特定名称的 Group 无写入操作,使用mu.RLock()
Get 方法
mainCache
查找缓存,log 内写入缓存命中- 缓存不存在
load
——>getLocally
(分布式场景下调用getFromPeer
从其他节点获取)——>g.getter.Get
回调函数获取源数据,通过g.populateCache
添加到缓存内
geecache/
|--lru/
|--lru.go // lru 缓存淘汰策略
|--byteview.go // 缓存值的抽象与封装
|--cache.go // 并发控制
|--geecache.go // 负责与外部交互,控制缓存存储和获取的主流程
|--http.go // 提供被其他节点访问的能力(基于http)
分布式缓存:
- 通过
HTTP
的通信机制实现节点间的通信
GeeCache HTTP 服务端
HTTPPool 数据结构
承载节点间 HTTP 通信的核心数据结构
type HTTPPool struct {
self string
basePth string
}
func NewHTTPPool(self string) *HTTPPool {
return &HTTPPool{self: self, basePth: defaultBasePath}
}
HTTPPool
内 self 存储主机名/IP 和端口- basePath 作为节点间通信的前缀,默认
/_geecache/
ServerHTTP 方法
-
判断前缀是否是
basePath
if !strings.HasPrefix(r.URL.Path, p.basePth) { panic("HTTPPool serving unexpected path: " + r.URL.Path) }
-
约定访问路径格式
/basePath/groupName/key
通过groupName
获得 group 实例,再使用group.Get(key)
获得缓存数据 -
w.Write()
将缓存值作为httpResponse
的body
返回
01 概述
单节点走向分布式节点通信
1.1 hash 算法保证 key 存储在同一节点
随机节点获取数据,若不存在从数据源获取数据并缓存;
再次随机节点获取数据具有不确定性
1.2 节点数量变化
缓存雪崩
:某节点失效后在收到请求时,均需要从数据源重新获取数据
1.3 一致性 hash 算法
将key
映射到2^32空间内,形成环
-
节点/机器的 hash 值放在环上
-
计算
key
的哈希值,放置在环上,顺时针找到的第一个节点即为应选择的节点/机器 -
数据倾斜问题
- 引入虚拟节点,一个真实结点对应多个虚拟节点
- 计算虚拟节点的 hash 值放置在环上
- 计算 key的 hash 值在环上顺时针寻找应该选取的虚拟节点
虚拟节点有效扩充了及诶单的数量解决节点数量较少情况下的数据倾斜问题;
只需增加
map
维护真实节点与虚拟节点之间的关系即可
02 语言实现
2.1 consistenthash
type (
Hash func(data[]byte) uint32
Map struct {
hash Hash
replicas int
keys []int
hashMap map[int]string
}
)
func New(replicas int, fn Hash) *Map {
m:=&Map{
hash: fn,
replicas: replicas,
hashMap: make(map[int]string),
}
if m.hash == nil {
m.hash=crc32.ChecksumIEEE
}
return m
}
- 定义函数类型
Hash
依赖注入的方式,默认为crc32.ChechsumIEEE
- 构造函数
New()
允许自定义虚拟节点和 Hash 函数
2.2 Add 真实节点/机器
- 传入多个真实节点的名称
- 对应每个真实节点
key
,创建m.replicas
个虚拟节点,虚拟节点名称为strconv.Itoa(i)+key
,通过编号区分; m.hash()
计算虚拟节点的 hash 值——>添加到环上append(m.keys,hash)
hashMap
添加虚拟和真实节点之间的映射- 环上哈希值排序
func (m *Map) Add(keys ...string) {
for _, key := range keys {
for i := 0; i < m.replicas; i++ {
hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
m.keys = append(m.keys, hash)
m.hashMap[hash] = key
}
}
sort.Ints(m.keys)
}
2.3 选择节点 Get 方法
func (m *Map) Get(key string) string {
if len(m.keys) == 0 {
return ""
}
hash := int(m.hash([]byte(key)))
// func Search(n int, f func(int)bool) int
// 在[0,n)内二分查找满足 f 条件的最小下标
index := sort.Search(len(m.keys), func(i int) bool {
return m.keys[i] >= hash
})
return m.hashMap[m.keys[index%len(m.keys)]]
}
- 计算 key 的哈希值
hash:=int(m.hash([]byte(key)))
- 顺时针查找第一个匹配的虚拟节点的下标
index
,使用sort.Search(len(环长,fn))
- 由于 keys为环状,故取余
- 在
m.keys[]
找到对应的哈希值,通过哈希值在hashMap
中的映射得到真实节点
- 注册节点 register peers,通过一致性哈希算法选择节点
- 实现
HTTP
客户端与远程节点的服务端通信
00 概述
对于未被缓存的 key 从远程节点调用
使用一致性哈希选择节点 是 是
|-----> 是否是远程节点 -----> HTTP 客户端访问远程节点 --> 成功?-----> 服务端返回返回值
| 否 ↓ 否
|----------------------------> 回退到本地节点处理。
01 抽象PeerPicker
- 抽象接口,对 PeerPicker 的
PickPeer()
方法参考传入key 选择相应的结点PeerGetter
- 接口
PeerGetter
的Get()
方法从group
查找缓存值,PeerGetter
即为HTTP 客户端