2. 单机并发缓存

https://github.com/dreamjz/golang-notes/tree/main/books/7-days-golang/GeeCache/day2-concurrency

DAY2-CONCURRENCY
│  byteview.go
│  cache.go
│  geecache.go
│  geecache_test.go
│  go.mod
│  
└─lru
        lru.go
        lru_test.go

1. 支持并发读写

1.1 byteview

抽象出一个只读的数据结构ByteView，用于表示缓存值。

// ByteView holds an immutable view of bytes
type ByteView struct {
	b []byte
}

• b []byte：存储真实的缓存值；byte类型能够支持所有的数据类型

// Len returns the view's length
func (v ByteView) Len() int {
	return len(v.b)
}

// ByteSlice returns a copy of the data as byte slice
func (v ByteView) ByteSlice() []byte {
	return cloneBytes(v.b)
}

// String returns the data as a string
func (v ByteView) String() string {
	return string(v.b)
}

func cloneBytes(b []byte) []byte {
	c := make([]byte, len(b))
	copy(c, b)
	return c
}

• Len：实现lru.Value接口
• ByteSlice：返回数据的拷贝，因为b是只读的，防止外部程序意外修改缓存数据

1.2 cache

type cache struct {
	mu         sync.Mutex
	lru        *lru.Cache
	cacheBytes int64
}

func (c *cache) add(key string, val ByteView) {
	c.mu.Lock()
	defer c.mu.Unlock()

	if c.lru == nil {
		c.lru = lru.New(c.cacheBytes, nil)
	}
	c.lru.Add(key, val)
}

func (c *cache) get(key string) (ByteView, bool) {
	c.mu.Lock()
	defer c.mu.Unlock()

	if c.lru == nil {
		return ByteView{}, false
	}

	if v, ok := c.lru.Get(key); ok {
		return v.(ByteView), ok
	}

	return ByteView{}, false
}

• cache：封装 lru的方法，为其添加互斥锁
• add中若lru为空才创建lru的对象，被称为延迟初始化（Lazy Initialization），对象的创建延迟至第一次使用，可用于提高性能

2. 核心数据结构

核心数据结构Group用于和用户交互，控制缓存值的存储和获取。

2.1 Getter 接口

// Getter loads data for a key
type Getter interface {
	Get(key string) ([]byte, error)
}

var _ Getter = GetterFunc(nil)

// GetterFunc implements Getter with a function
type GetterFunc func(key string) ([]byte, error)

// Get implements Getter interface
func (f GetterFunc) Get(key string) ([]byte, error) {
	return f(key)
}

• 接口Getter定义回调函数Get，当缓存数据不存在，可以调用回调函数从数据源中获取
• GetterFunc：函数类型，实现了Getter接口

接口型函数

若函数实现了某个接口，那么此函数被称为接口型函数。

此时即可以将接口型函数作为参数，也可以将实现了接口的结构体作为参数，使得函数的使用变得更加灵活多变。

func TestGetter(t *testing.T) {
	var f Getter = GetterFunc(func(key string) ([]byte, error) {
		return []byte(key), nil
	})

	want := []byte("key")
	if v, _ := f.Get("key"); !reflect.DeepEqual(v, want) {
		t.Errorf("callback failed")
	}
}

2.2 Group

// Group is a cache namespace and associated data loaded spread over
type Group struct {
	name      string
	getter    Getter
	mainCache cache
}

var (
	mu     sync.RWMutex
	groups = make(map[string]*Group)
)

// NewGroup create a new instance of group
func NewGroup(name string, cacheBytes int64, getter Getter) *Group {
	if getter == nil {
		panic("nil Getter")
	}

	mu.Lock()
	defer mu.Unlock()

	g := &Group{
		name:      name,
		getter:    getter,
		mainCache: cache{cacheBytes: cacheBytes},
	}
	groups[name] = g
	return g
}

func GetGroup(name string) *Group {
	mu.RLock()
	defer mu.RUnlock()
	g := groups[name]
	return g
}

• 一个 Group表示一个缓存的命名空间：
  1. name：Group 的名称
  2. getter：缓存未命中时获取源数据的回调(callback)
  3. maincache：并发缓存
• NewGroup：创建新的Group实例，添加到全局变量groups中
• GetGroup：获取指定的 Group实例，此处使用了读锁
• mu：全局变量，读写锁
• groups：全局变量，哈希表存储所有的Group实例

func (g *Group) Get(key string) (ByteView, error) {
	if key == "" {
		return ByteView{}, fmt.Errorf("key is required")
	}

	if v, ok := g.mainCache.get(key); ok {
		log.Println("[GeeCache] hit")
		return v, nil
	}

	return g.load(key)
}

func (g *Group) load(key string) (ByteView, error) {
	return g.getLocally(key)
}

func (g *Group) getLocally(key string) (ByteView, error) {
	bytes, err := g.getter.Get(key)
	if err != nil {
		return ByteView{}, err
	}

	val := ByteView{b: cloneBytes(bytes)}
	g.populateCache(key, val)
	return val, nil
}

func (g *Group) populateCache(key string, val ByteView) {
	g.mainCache.add(key, val)
}

Get流程如下：

1. 从缓存中获取数据，若存在则返回，否则继续 步骤 2）
2. 从数据源中获取数据，getLocally调用回调函数g.getter.Get获取源数据
3. 将数据添加至缓存中
4. 返回数据

3. 测试

使用哈希表模拟数据库：

var db = map[string]string{
	"Tom":  "630",
	"Jack": "589",
	"Sam":  "567",
}

func TestGet(t *testing.T) {
	loadCount := make(map[string]int, len(db))
	gee := NewGroup("scores", 2<<10, GetterFunc(
		func(key string) ([]byte, error) {
			log.Println("[SlowDB] search key", key)
			if v, ok := db[key]; ok {
				if _, ok := loadCount[key]; !ok {
					loadCount[key] = 0
				}
				loadCount[key] += 1
				return []byte(v), nil
			}
			return nil, fmt.Errorf("%s not exist", key)
		},
	))

	for k, v := range db {
		if view, err := gee.Get(k); err != nil || view.String() != v {
			t.Fatal("failed to get val from cache")
		}

		if _, err := gee.Get(k); err != nil || loadCount[k] > 1 {
			t.Fatalf("cache %s miss", k)
		}
	}

	if view, err := gee.Get("unknown"); err == nil {
		t.Fatalf("want empty val, got %s", view)
	}
}

 16:27:13 [SlowDB] search key Tom
 16:27:13 [GeeCache] hit
 16:27:13 [SlowDB] search key Jack
 16:27:13 [GeeCache] hit
 16:27:13 [SlowDB] search key Sam
 16:27:13 [GeeCache] hit
 16:27:13 [SlowDB] search key unknown

Reference

1. https://geektutu.com/post/geecache-day2.html