7天用Go从零实现分布式缓存GeeCache（学习）（3）

目录结构

├── geecache
│   ├── byteview.go
│   ├── cache.go
│   ├── consistenthash
│   │   ├── consistenthash.go
│   │   └── consistenthash_test.go
│   ├── geecache.go
│   ├── go.mod
│   ├── http.go
│   ├── lru
│   │   └── lru.go
│   ├── peers.go
│   └── singleflight
│       └── singleflight.go
├── go.mod
└── main
    └── main.go

在这里插入图片描述

文件分析

1. `lru/lru.go`

1.1 结构体定义

Cache
```
type Cache struct {
    maxBytes  int64
    nbytes    int64
    ll        *list.List
    cache     map[string]*list.Element
    OnEvicted func(key string, value Value)
}
```
- 字段解释
  - maxBytes：缓存的最大容量（字节数）。
  - nbytes：当前已使用的缓存大小（字节数）。
  - ll：双向链表，*list.List，用于记录元素的访问顺序。
  - cache：字典（哈希表），map[string]*list.Element，键为字符串，值为链表元素的指针，方便快速查找。
  - OnEvicted：可选的回调函数，当元素被移除时调用。
entry
```
type entry struct {
    key   string
    value Value
}
```
- 字段解释
  - key：缓存项的键。
  - value：缓存项的值，实现了 Value 接口。
Value 接口
```
type Value interface {
    Len() int
}
```
- 方法
  - Len()：返回值所占的字节数。

1.2 函数签名

构造函数

func New(maxBytes int64, onEvicted func(string, Value)) *Cache

方法

添加元素：

func (c *Cache) Add(key string, value Value)

获取元素：

func (c *Cache) Get(key string) (value Value, ok bool)

移除最久未使用的元素：
```
func (c *Cache) RemoveOldest()
```
获取缓存中元素的数量：
```
func (c *Cache) Len() int
```

1.3 函数调用关系

Cache.Add 方法：
- 检查键是否存在于缓存中。
  - 如果存在，更新值，移动元素到链表头部。
  - 如果不存在，创建新的元素，添加到链表头部。
- 更新已使用的缓存大小 nbytes。
- 调用 Cache.RemoveOldest，在超过容量时移除最久未使用的元素。
Cache.Get 方法：
- 在 cache 字典中查找键。
  - 如果找到，移动元素到链表头部，返回值。
  - 如果未找到，返回 nil。
Cache.RemoveOldest 方法：
- 从链表尾部获取最久未使用的元素。
- 从链表和 cache 字典中移除该元素。
- 更新已使用的缓存大小 nbytes。
- 如果设置了 OnEvicted 回调函数，调用该函数。

2. `consistenthash/consistenthash.go`

2.1 结构体定义

Hash 类型
```
type Hash func(data []byte) uint32
```
- 定义哈希函数类型，接收 []byte，返回 uint32。
Map
```
type Map struct {
    hash     Hash
    replicas int
    keys     []int
    hashMap  map[int]string
}
```
- 字段解释
  - hash：哈希函数，类型为 Hash，用于计算键的哈希值。
  - replicas：每个真实节点的虚拟节点数。
  - keys：哈希环，存储所有虚拟节点的哈希值（已排序）。
  - hashMap：虚拟节点哈希值与真实节点名称的映射表。

2.2 函数签名

构造函数
```
func New(replicas int, fn Hash) *Map
```

方法

添加节点：
```
func (m *Map) Add(keys ...string)
```
获取节点：
```
func (m *Map) Get(key string) string
```

2.3 函数调用关系

Map.Add 方法：
- 对于每个真实节点，创建 replicas 个虚拟节点。
- 计算每个虚拟节点的哈希值，添加到 keys 切片中。
- 更新 hashMap 映射表。
- 调用 sort.Ints(m.keys) 对哈希环进行排序。
Map.Get 方法：
- 计算给定 key 的哈希值。
- 使用 sort.Search 在 keys 切片中查找第一个大于等于该哈希值的虚拟节点索引。
- 通过 hashMap 获取对应的真实节点。

3. `singleflight/singleflight.go`

3.1 结构体定义

call
```
type call struct {
    wg  sync.WaitGroup
    val interface{}
    err error
}
```
- 字段解释
  - wg：同步等待组，用于等待请求完成。
  - val：请求的结果。
  - err：请求的错误信息。
Group
```
type Group struct {
    mu sync.Mutex
    m  map[string]*call
}
```
- 字段解释
  - mu：互斥锁，保护对 m 的并发访问。
  - m：存储进行中的请求，键为请求的 key。

3.2 函数签名

方法

func (g *Group) Do(key string, fn func() (interface{}, error)) (interface{}, error)

3.3 函数调用关系

Group.Do 方法：
- 检查请求的 key 是否正在进行中。
  - 如果是，等待已有的请求完成，返回结果。
  - 如果不是，创建新的 call，添加到 m 中。
- 执行传入的函数 fn，获取结果。
- 从 m 中删除已完成的请求。

4. `byteview.go`

4.1 结构体定义

ByteView
```
type ByteView struct {
    b []byte
}
```
- 字段解释
  - b：存储实际数据的字节切片。

4.2 函数签名

方法

获取长度：
```
func (v ByteView) Len() int
```
返回数据的拷贝：
```
func (v ByteView) ByteSlice() []byte
```
返回字符串表示：
```
func (v ByteView) String() string
```

辅助函数
```
func cloneBytes(b []byte) []byte
```

4.3 函数调用关系

ByteView.Len 方法：
- 返回 b 的长度。
ByteView.ByteSlice 方法：
- 调用 cloneBytes 返回 b 的拷贝。
ByteView.String 方法：
- 将 b 转换为字符串。
cloneBytes 函数：
- 创建新的字节切片，复制 b 的内容。

5. `cache.go`

5.1 结构体定义

cache
```
type cache struct {
    mu         sync.Mutex
    lru        *lru.Cache
    cacheBytes int64
}
```
- 字段解释
  - mu：互斥锁，保护对 lru 的并发访问。
  - lru：指向 lru.Cache 的指针，实际的缓存实现。
  - cacheBytes：缓存的最大容量。

5.2 函数签名

方法

添加缓存项：

func (c *cache) add(key string, value ByteView)

获取缓存项：

func (c *cache) get(key string) (value ByteView, ok bool)

5.3 函数调用关系

cache.add 方法：
- 加锁保护。
- 检查 lru 是否为 nil，如果是则初始化。
- 调用 lru.Add 方法添加缓存项。
cache.get 方法：
- 加锁保护。
- 检查 lru 是否为 nil。
- 调用 lru.Get 方法获取缓存项。

6. `geecache.go`

6.1 结构体和接口定义

Group
```
type Group struct {
    name      string
    getter    Getter
    mainCache cache
    peers     PeerPicker
    loader    *singleflight.Group
}
```
- 字段解释
  - name：缓存组名称。
  - getter：数据加载接口，实现 Getter 接口。
  - mainCache：主缓存，类型为前述的 cache。
  - peers：节点选择器，实现 PeerPicker 接口。
  - loader：单次请求防护，使用 singleflight.Group。

Getter 接口

type Getter interface {
    Get(key string) ([]byte, error)
}

GetterFunc 类型

type GetterFunc func(key string) ([]byte, error)

方法

func (f GetterFunc) Get(key string) ([]byte, error)

6.2 函数签名

构造函数

func NewGroup(name string, cacheBytes int64, getter Getter) *Group

全局函数
```
func GetGroup(name string) *Group
```

Group 方法

获取缓存项：

func (g *Group) Get(key string) (ByteView, error)

注册节点选择器：

func (g *Group) RegisterPeers(peers PeerPicker)

内部方法

加载数据：

func (g *Group) load(key string) (value ByteView, err error)

本地加载数据：

func (g *Group) getLocally(key string) (ByteView, error)

从远程节点加载数据：

func (g *Group) getFromPeer(peer PeerGetter, key string) (ByteView, error)

填充缓存：

func (g *Group) populateCache(key string, value ByteView)

6.3 函数调用关系

NewGroup 函数：
- 创建 Group 实例，初始化 mainCache 和 loader。
Group.Get 方法：
- 调用 mainCache.get 获取缓存项。
- 如果缓存未命中，调用 g.load 加载数据。
Group.load 方法：
- 使用 g.loader.Do 确保并发情况下对相同的 key 只会加载一次。
- 优先调用 g.peers.PickPeer 选择远程节点，调用 g.getFromPeer 从远程获取数据。
- 如果远程获取失败或没有远程节点，调用 g.getLocally 本地加载数据。
Group.getLocally 方法：
- 调用 g.getter.Get 从本地数据源获取数据。
- 调用 g.populateCache 将数据填充到缓存中。
Group.getFromPeer 方法：
- 调用 peer.Get 从远程节点获取数据。
Group.populateCache 方法：
- 调用 mainCache.add 将数据添加到缓存中。

7. `http.go`

7.1 结构体和接口定义

HTTPPool
```
type HTTPPool struct {
    self        string
    basePath    string
    mu          sync.Mutex
    peers       *consistenthash.Map
    httpGetters map[string]*httpGetter
}
```
- 字段解释
  - self：当前节点的地址。
  - basePath：处理请求的基础路径。
  - mu：互斥锁，保护并发访问。
  - peers：一致性哈希环，类型为 *consistenthash.Map。
  - httpGetters：远程节点的 httpGetter 映射。
httpGetter
```
type httpGetter struct {
    baseURL string
}
```
- 字段解释
  - baseURL：远程节点的基础 URL。

7.2 函数签名

构造函数

func NewHTTPPool(self string) *HTTPPool

HTTPPool 方法

日志记录：

func (p *HTTPPool) Log(format string, v ...interface{})

处理 HTTP 请求：

func (p *HTTPPool) ServeHTTP(w http.ResponseWriter, r *http.Request)

设置远程节点：

func (p *HTTPPool) Set(peers ...string)

选择远程节点：

func (p *HTTPPool) PickPeer(key string) (PeerGetter, bool)

httpGetter 方法

func (h *httpGetter) Get(group string, key string) ([]byte, error)

7.3 函数调用关系

NewHTTPPool 函数：
- 创建 HTTPPool 实例，初始化 self 和 basePath。
HTTPPool.ServeHTTP 方法：
- 解析请求路径，获取 group 和 key。
- 调用 GetGroup 获取对应的 Group。
- 调用 group.Get 获取缓存项。
- 将结果写入响应。
HTTPPool.Set 方法：
- 创建一致性哈希环 consistenthash.Map。
- 调用 p.peers.Add 添加节点。
- 为每个节点创建对应的 httpGetter。
HTTPPool.PickPeer 方法：
- 调用 p.peers.Get 根据 key 选择远程节点。
- 返回对应的 httpGetter。
httpGetter.Get 方法：
- 构造请求 URL。
- 发送 HTTP GET 请求获取数据。

8. `peers.go`

8.1 接口定义

PeerPicker 接口

type PeerPicker interface {
    PickPeer(key string) (peer PeerGetter, ok bool)
}

PeerGetter 接口

type PeerGetter interface {
    Get(group string, key string) ([]byte, error)
}

8.2 接口关系

HTTPPool 实现了 PeerPicker 接口。
httpGetter 实现了 PeerGetter 接口。

总体调用关系和结构体组合

1. 结构体组合情况

Group
- 包含 mainCache，类型为 cache。
- 包含 loader，类型为 *singleflight.Group。
- 包含 peers，接口类型为 PeerPicker。
cache
- 包含 lru，类型为 *lru.Cache。
lru.Cache
- 使用 Go 标准库的 container/list 作为底层实现。
HTTPPool
- 包含 peers，类型为 *consistenthash.Map。
- 包含 httpGetters，存储 httpGetter。
consistenthash.Map
- 包含 hashMap，映射虚拟节点哈希值到真实节点。

2. 函数调用关系概览

客户端请求数据：
- 调用 Group.Get 方法。
  - 尝试从本地缓存 mainCache 获取数据。
  - 如果缓存未命中，调用 Group.load 加载数据。
    - 使用 singleflight.Group 确保并发情况下只加载一次。
    - 如果设置了 peers，调用 PeerPicker.PickPeer 选择远程节点。
      - 如果找到远程节点，调用 PeerGetter.Get 从远程获取数据。
    - 如果未找到远程节点或远程获取失败，调用 Group.getLocally 本地加载数据。
      - 调用 Getter.Get 从数据源获取数据。
      - 调用 Group.populateCache 将数据添加到缓存。
HTTPPool 处理 HTTP 请求：
- 调用 ServeHTTP 方法。
  - 解析请求，获取 group 和 key。
  - 调用 Group.Get 获取数据。
  - 将数据返回给客户端。
httpGetter 作为远程节点的客户端：
- 实现 PeerGetter 接口。
- 调用 Get 方法，通过 HTTP 请求从远程节点获取数据。

详细说明组合部分

总体概览

主要结构体及其关系：

Group：缓存的核心，代表一个命名空间，负责处理缓存的获取和加载。
- 包含一个 cache 实例（mainCache），用于存储本地缓存数据。
- 使用 Getter 接口定义的 getter 来从数据源加载数据。
- 使用 singleflight.Group（loader）防止缓存击穿时的并发重复请求。
- 可选地包含一个 PeerPicker 接口（peers），用于在分布式环境中选择节点。
cache：缓存的具体实现，内部使用 LRU 算法管理数据。
- 包含一个 lru.Cache 实例（lru），负责存储缓存数据和 LRU 淘汰策略。
- 使用互斥锁 sync.Mutex（mu）确保并发安全。
lru.Cache：LRU 缓存的实现，使用双向链表和字典存储数据。
- 包含一个双向链表 *list.List（ll）和一个字典 map[string]*list.Element（cache），实现 O(1) 的访问和淘汰。
- 每个缓存项是一个 entry，包含键和值。
ByteView：表示缓存值的不可变视图，实现了 lru.Value 接口。
- 内部存储一个字节切片 []byte（b）。
consistenthash.Map：一致性哈希的实现，用于在多个节点间分配键。
- 维护了一个哈希环（keys）和虚拟节点到真实节点的映射（hashMap）。
HTTPPool：实现了 PeerPicker 接口，管理节点间的 HTTP 通信。
- 包含一个一致性哈希的 consistenthash.Map（peers）和节点到 httpGetter 的映射（httpGetters）。
httpGetter：实现了 PeerGetter 接口，用于通过 HTTP 从远程节点获取数据。
singleflight.Group：用于防止并发请求相同的键时，重复加载数据。

下面，我们将逐一介绍各个结构体的定义、它们之间的组合关系，以及它们在系统中的角色。

结构体组合详情

1. `Group` 结构体

文件：geecache/geecache.go

type Group struct {
    name      string              // 缓存的命名空间
    getter    Getter              // 缓存未命中时获取源数据的回调
    mainCache cache               // 并发安全的本地缓存
    peers     PeerPicker          // 分布式场景下的节点选择器
    loader    *singleflight.Group // 防止缓存击穿的请求合并
}

组合关系

包含 cache 实例：Group 内嵌了一个 cache 类型的字段 mainCache，用于管理本地的缓存数据。
使用 Getter 接口：Group 通过 getter 字段持有一个实现了 Getter 接口的实例，用于在缓存未命中时加载源数据。
持有 PeerPicker 接口：Group 通过 peers 字段持有一个实现了 PeerPicker 接口的实例（如 HTTPPool），用于在分布式环境中根据键选择远程节点。
使用 singleflight.Group：Group 使用 loader 字段来持有一个 singleflight.Group 实例，防止并发请求相同的键时重复加载数据。

功能描述

Group 是缓存的核心结构，负责提供缓存的获取、加载以及与其他节点的交互。

2. `cache` 结构体

文件：geecache/cache.go

type cache struct {
    mu         sync.Mutex // 互斥锁，保护并发访问
    lru        *lru.Cache // LRU 缓存的实例
    cacheBytes int64      // 最大缓存字节数
}

组合关系

包含 lru.Cache 实例：cache 结构体内部持有一个指向 lru.Cache 的指针 lru，用于实际存储缓存数据和执行 LRU 淘汰策略。
使用互斥锁：cache 使用互斥锁 mu 来保护对 lru 的并发访问，确保线程安全。

功能描述

cache 是对 lru.Cache 的封装，增加了并发控制，并提供了延迟初始化的机制。

3. `lru.Cache` 结构体

文件：geecache/lru/lru.go

type Cache struct {
    maxBytes  int64                    // 最大缓存容量
    nbytes    int64                    // 当前已使用的缓存容量
    ll        *list.List               // 双向链表，记录访问顺序
    cache     map[string]*list.Element // 键到链表节点的映射
    OnEvicted func(key string, value Value) // 可选的回调函数
}

entry 结构体：

type entry struct {
    key   string // 键
    value Value  // 值，实现了 `Value` 接口
}

组合关系

使用标准库的 list.List：lru.Cache 使用双向链表 ll 来记录缓存项的访问顺序，以便实现 LRU 淘汰策略。
使用字典存储缓存项：cache 字段是一个字典，映射键到链表节点，方便快速查找缓存项。
定义了 Value 接口：缓存项的值需要实现 Value 接口，该接口定义了 Len() 方法，用于计算值的大小。

功能描述

lru.Cache 实现了基本的 LRU 缓存功能，提供了添加、获取和移除缓存项的方法。

4. `ByteView` 结构体

文件：geecache/byteview.go

type ByteView struct {
    b []byte // 存储实际的数据
}

组合关系

实现了 lru.Value 接口：ByteView 实现了 Len() 方法，满足 lru.Cache 对值类型的要求。
不可变性：ByteView 通过只暴露数据的拷贝，确保了数据的不可变性，防止外部修改缓存中的数据。

功能描述

ByteView 是缓存值的载体，封装了字节切片，提供了只读的方法访问数据。

5. `consistenthash.Map` 结构体

文件：geecache/consistenthash/consistenthash.go

type Map struct {
    hash     Hash           // 哈希函数
    replicas int            // 每个节点的虚拟节点数
    keys     []int          // 哈希环，存储所有虚拟节点的哈希值
    hashMap  map[int]string // 虚拟节点与真实节点的映射
}

组合关系

使用哈希函数：Map 通过 hash 字段持有一个哈希函数，用于计算键和节点的哈希值。
维护虚拟节点和真实节点的映射：hashMap 字段存储了虚拟节点的哈希值与真实节点名称的映射关系。

功能描述

consistenthash.Map 实现了一致性哈希算法，用于在分布式环境中根据键选择节点，确保数据分布的均衡性和稳定性。

6. `HTTPPool` 结构体

文件：geecache/http.go

type HTTPPool struct {
    self        string                 // 本机地址
    basePath    string                 // HTTP 路径前缀
    mu          sync.Mutex             // 互斥锁
    peers       *consistenthash.Map    // 一致性哈希环，存储所有节点
    httpGetters map[string]*httpGetter // 远程节点的 HTTP 客户端
}

组合关系

实现 PeerPicker 接口：HTTPPool 实现了 PeerPicker 接口中的 PickPeer 方法，能够根据键选择远程节点。
使用 consistenthash.Map：HTTPPool 使用一致性哈希环 peers 来管理所有的节点，并根据键选择对应的节点。
维护节点到 httpGetter 的映射：httpGetters 字段存储了远程节点地址到 httpGetter 的映射，用于与远程节点进行通信。

功能描述

HTTPPool 负责处理 HTTP 请求，并管理节点间的通信，在分布式缓存中扮演重要角色。

7. `httpGetter` 结构体

文件：geecache/http.go

type httpGetter struct {
    baseURL string // 远程节点的地址
}

组合关系

实现 PeerGetter 接口：httpGetter 实现了 PeerGetter 接口中的 Get 方法，能够通过 HTTP 从远程节点获取数据。

功能描述

httpGetter 是一个 HTTP 客户端，用于向远程节点发送请求并获取数据。

8. `PeerPicker` 和 `PeerGetter` 接口

文件：geecache/peers.go

type PeerPicker interface {
    PickPeer(key string) (peer PeerGetter, ok bool)
}

type PeerGetter interface {
    Get(group string, key string) ([]byte, error)
}

组合关系

Group 使用 PeerPicker：Group 通过持有 PeerPicker 接口的实例，能够在分布式环境中根据键选择远程节点。
HTTPPool 实现 PeerPicker：HTTPPool 实现了 PickPeer 方法，能够根据键选择合适的远程节点。
httpGetter 实现 PeerGetter：httpGetter 实现了 Get 方法，能够从远程节点获取数据。

功能描述

这两个接口定义了节点选择和数据获取的行为，使得 Group 能够在本地和远程之间灵活地获取数据。

结构体之间的交互关系

下面，我们将以数据获取的流程为例，详细说明各个结构体是如何交互的。

数据获取流程

客户端请求数据：客户端调用 Group.Get(key) 方法，尝试获取指定键的数据。
Group 检查本地缓存：Group 调用 mainCache.get(key) 方法，尝试从本地缓存中获取数据。
- cache.get(key) 方法内部加锁，确保线程安全。
- 如果 lru 未初始化，则返回未命中。
- 如果缓存命中，返回数据。
缓存未命中，使用 singleflight 防止并发请求：
- Group 调用 loader.Do(key, func() (interface{}, error)) 方法，确保相同的键在并发情况下只会请求一次。
尝试从远程节点获取数据：
- Group 检查是否配置了 peers（PeerPicker 接口的实现）。
- 如果配置了，调用 peers.PickPeer(key) 方法，选择远程节点。
- 如果成功选择到远程节点，调用 getFromPeer(peer, key) 方法，从远程节点获取数据。
  - getFromPeer 调用 peer.Get(group.Name, key) 方法。
  - peer 是一个实现了 PeerGetter 接口的实例，如 httpGetter。
  - 远程节点处理请求，返回数据。
从本地数据源获取数据：
- 如果未配置远程节点，或者从远程节点获取失败，Group 调用 getLocally(key) 方法，从本地数据源加载数据。
  - getLocally 调用 getter.Get(key) 方法，从本地数据源获取数据。
  - getter 是一个实现了 Getter 接口的实例，由用户提供。
将数据添加到缓存：
- 无论数据是从远程节点还是本地数据源获取的，Group 都会调用 populateCache(key, value) 方法，将数据添加到本地缓存。
  - populateCache 调用 mainCache.add(key, value) 方法。
  - cache.add 方法内部加锁，确保线程安全。
  - 如果 lru 未初始化，进行初始化。
  - 调用 lru.Add(key, value) 方法，将数据添加到缓存中。
返回数据给客户端：Group 将获取到的数据返回给客户端。

结构体交互图示

Client
   |
   v
Group
   |-- mainCache (cache)
   |       |-- lru (lru.Cache)
   |
   |-- peers (PeerPicker)
   |       |-- HTTPPool
   |               |-- consistenthash.Map
   |               |-- httpGetters (map[string]*httpGetter)
   |
   |-- getter (Getter)
   |
   |-- loader (*singleflight.Group)