GeeCache概述

模仿goroupcache，考虑：

  • 资源控制、淘汰策略、并发、分布式节点通信
  • 缓存更新、缓存淘汰之前是否允许改变

特性：

  • 单机缓存和基于 HTTP 的分布式缓存
  • 最近最少访问(Least Recently Used, LRU) 缓存策略
  • 使用 Go 锁机制防止缓存击穿
  • 使用一致性哈希选择节点，实现负载均衡
  • 使用 protobuf 优化节点间二进制通信

常见缓存淘汰算法

FIFO

创建队列，新增记录添加到队尾，内存不够时淘汰队首

缺点：

  • 早入队的数据若被常访问，导致频繁被添加缓存又被淘汰——>缓存命中率低

LFU

淘汰缓存汇总的访问访问频率最低的记录，维护按照访问次数排序的队列

缺点：

  • 维护每个记录的访问次数消耗内存高
  • LFU 算法手历史数据影响大

LRU

最近最少使用策略

LRU

核心数据结构

image-20211021223546014
  1. map 存储字典映射，按key查找value 复杂度 O(1)
  2. 双向链表实现队列，将移动到队尾的复杂度是 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 移至队首

  1. map 查找 c.cache[key]

  2. 调用c.ll.MoveToFront(ele)将所得封装为 entry kv:=ele.Value.(*Entry)，返回kv.value

RemoveOldest 删除队尾和缓存 map

  1. 取出队尾ele:=c.kll.Back()
  2. 存在则删除c.ll.Remove(ele) delete(c.cache,kv.key)
  3. 更新使用内存c.nbytes-=int64(len(kv.key))+int64(kv.value.Len()) nbytes 前移偏移量为 kv 的大小（key+value.Len()）
  4. 回调函数非空则使用回调函数

Add（更新、新增、越界）

  1. 添加节点已存在——>更新结点

    • 缓存map存在则移至队首再更新结点值，
    • 使用内存偏移量同步更新c.nbytes+=int64(value.Len())-int64(kv.value.Len()) 多使用新加入结点的 value 比原 value 大的部分

  2. 添加节点不存在——新增结点

    • 移至队首ele:=c.ll.MoveToFront(&entry{key,value})
    • 新增缓存c.cache[key]=ele
    • 更新已使用内存c.nbytes+=int64(len(key))+int64(value.Len())

  3. 判定新增结点是否超容

    for c.maxBytes!=0&&c.maxBytes<c.nBytes{ c.RemoveOldest()} 越界则移出队尾

00-概述

  • 实现LRU缓存的并发控制
  • 实现 Cache的核心数据结构Group，当缓存不存在时使用回调函数

01-并发 lru 读写

1.1 ByteView 缓存值只读

  1. b []byte存储真实的缓存值，支持任意数据类型存储(byte)
  2. 实现Len()方法，支持 lru 的缓存对象的 Value接口
  3. ByteSlice()返回缓存 b 的复制，防止外部程序修改缓存
mhrcGo

1.2 Cache 并发

  1. 实例化lru，封装get和add方法，添加互斥锁Mutex
 type cache struct {
     lru        *lru.Cache
     mu         sync.Mutex
     cacheBytes int64
 }
  1. 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)
}

#接口函数

接口函数：

  1. 将普通的函数类型（类型转换 GetterFunc(test）作为函数参数
  2. 将结构体作为参数

eg:

​ GetterFunc 类型的函数作为参数，支持匿名函数、普通函数（类型转换）

​ 实现了 Getter 接口的结构体可作为函数参数

接口函数使用场景：

  1. 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)
}

  2. http.Handle和http.ListenAndServe的第二个参数即为接口类型Handler

  3. 传入实现Handler接口的结构体则可以托管所有的 HTTP 请求，可扩展为 Web 框架

  4. 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);

  5. 定义Getter接口和回调函数Get(key string)([]byte,error)

  6. 定义函数类型GetterFunc实现Getter接口内的Get方法

  7. 定义函数类型 F，并实现接口 A 的方法，在方法中调用自身使得其他函数（参数与返回类型与 F一致）转化为接口 A

2.4 Group 定义

结构体

type Group struct {
	name      string
	// 缓存未命中时回调函数
    getter    Getter
    // 并发缓存
	mainCache cache
}
  1. 视为缓存的命名空间，每个Group有唯一的name
  2. getter Getter 为缓存未命中时的数据回调(callback)
  3. NewGroup用于实例化 Group 并存储在全局变量 groups内
  4. GetGroup获取特定名称的 Group 无写入操作，使用mu.RLock()

Get 方法

  1. mainCache 查找缓存，log 内写入缓存命中
  2. 缓存不存在load——>getLocally（分布式场景下调用getFromPeer从其他节点获取）——>g.getter.Get回调函数获取源数据，通过g.populateCache添加到缓存内
geecache/
    |--lru/
        |--lru.go  // lru 缓存淘汰策略
    |--byteview.go // 缓存值的抽象与封装
    |--cache.go    // 并发控制
    |--geecache.go // 负责与外部交互，控制缓存存储和获取的主流程
	|--http.go     // 提供被其他节点访问的能力(基于http)

分布式缓存：

  1. 通过HTTP的通信机制实现节点间的通信

GeeCache HTTP 服务端

HTTPPool 数据结构

承载节点间 HTTP 通信的核心数据结构

type HTTPPool struct {
	self    string
	basePth string
}

func NewHTTPPool(self string) *HTTPPool {
	return &HTTPPool{self: self, basePth: defaultBasePath}
}
  1. HTTPPool内 self 存储主机名/IP 和端口
  2. basePath 作为节点间通信的前缀，默认/_geecache/

ServerHTTP 方法

  1. 判断前缀是否是basePath

    if !strings.HasPrefix(r.URL.Path, p.basePth) {
   panic("HTTPPool serving unexpected path: " + r.URL.Path)
}

  2. 约定访问路径格式/basePath/groupName/key 通过groupName获得 group 实例，再使用group.Get(key)获得缓存数据

  3. 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
}
  1. 定义函数类型Hash 依赖注入的方式，默认为crc32.ChechsumIEEE
  2. 构造函数New()允许自定义虚拟节点和 Hash 函数

2.2 Add 真实节点/机器

  1. 传入多个真实节点的名称
  2. 对应每个真实节点key，创建m.replicas个虚拟节点，虚拟节点名称为strconv.Itoa(i)+key，通过编号区分；
  3. m.hash()计算虚拟节点的 hash 值——>添加到环上append(m.keys,hash)
  4. hashMap添加虚拟和真实节点之间的映射
  5. 环上哈希值排序
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)]]
}
  1. 计算 key 的哈希值hash:=int(m.hash([]byte(key)))
  2. 顺时针查找第一个匹配的虚拟节点的下标index ，使用sort.Search(len(环长,fn))
  3. 由于 keys为环状，故取余
  4. 在m.keys[]找到对应的哈希值，通过哈希值在 hashMap中的映射得到真实节点
  • 注册节点 register peers，通过一致性哈希算法选择节点
  • 实现HTTP客户端与远程节点的服务端通信

00 概述

对于未被缓存的 key 从远程节点调用

使用一致性哈希选择节点        是                                    是
    |-----> 是否是远程节点 -----> HTTP 客户端访问远程节点 --> 成功？-----> 服务端返回返回值
                    |  否                                    ↓  否
                    |----------------------------> 回退到本地节点处理。

01 抽象PeerPicker

  1. 抽象接口，对 PeerPicker 的PickPeer()方法参考传入key 选择相应的结点PeerGetter
  2. 接口PeerGetter 的Get()方法从group查找缓存值，PeerGetter即为HTTP 客户端