Go猜想录
大道至简,悟者天成
手搓缓存层 -- #1 本地缓存

楔子

业务但凡对性能有点要求,几乎都会考虑使用缓存。

缓存大体上分成两类:

  • 本地缓存
  • 分布式缓存,如 Redis、 memcached

一般在公司内部,我们都会再次封装不同缓存的 API,并且在这些 API 之上解决一些缓存问题。

cache-1.png

API 设计

API 可以认为是最关键的一个设计。我们可以参考不同的缓存中间件的 API 设计。

下边是 Beego API 的设计。主要 API 分成:

  • 单个操作
  • 批量操作
  • 针对数字的自增自减
type Cache interface {
	// Get will get cached value by key.
	Get(key string) interface{}
	// GetMulti is a batch version of Get.
	GetMulti(keys []string) []interface{}
	// Put will set cached value with key and expire time.
	Put(key string, val interface{}, timeout time.Duration) error
	// Delete will delete cached value by key.
	Delete(key string) error
	// Incr will increase cached int value by key, as a counter.
	Incr(key string) error
	// Decr will decrease cached int value by key, as a counter.
	Decr(key string) error
	// IsExist can check if cached value exists or not.
	IsExist(key string) bool
	// ClearAll will clear all cache.
	ClearAll() error
	// StartAndGC will start gc routine based on config string settings.
	StartAndGC(config string) error
}

go-cache 的 API 设计。API 都是差不多的,它的 API 分成两部分:

  • 单个操作
  • 针对数字的加减操作

V0

我们的 API 暂时设计成这样子,后面有需要的时候再继续增加 API。

需要注意到,我们依旧保持在公开方法里面接收一个 context 参数,这个参数在本地缓存实现里面可能没用,但是在接入 Redis 的时候就很有用。

// Cache 屏蔽不同的缓存中间件的差异
type Cache interface {
	// val, err := Get(ctx, key)
	// str = val.(string)
	Get(ctx context.Context, key string) (any, error)
	Set(ctx context.Context, key string, val any, expiration time.Duration) error
	Delete(ctx context.Context, key string) error
}

V1

// 值的问题
// - string: 本地缓存时结构体需要转化为 string,比如用 json 表达 User
// - []byte: 最通用的表达,可以存储序列化后的数据,也可以存储加密数据,
//           还可以存储压缩数据。用户用起来不方便
// - any:    Redis 之类的实现,要考虑序列化的问题

type Cache interface {
	Get(ctx context.Context, key string) AnyValue
	Set(ctx context.Context, key string, val any) AnyValue
}

type AnyValue struct {
	Val any
	Err error
}

func (a AnyValue) String() (string, error) {
	if a.Err != nil {
		return "", a.Err
	}
	str, ok := a.Val.(string)
	if !ok {
		return "", errors.New("无法转换的类型")
	}
	return str, nil
}

func (a AnyValue) Bytes() ([]byte, error) {
	if a.Err != nil {
		return nil, a.Err
	}
	str, ok := a.Val.([]byte)
	if !ok {
		return nil, errors.New("无法转换的类型")
	}
	return str, nil
}

func (a AnyValue) BindJson(val any) error {
	if a.Err != nil {
		return a.Err
	}
	str, ok := a.Val.([]byte)
	if !ok {
		return errors.New("无法转换的类型")
	}
	return json.Unmarshal(str, val)
}

API 为什么不用泛型

Go 1.18 之后我们可以考虑用泛型,但泛型本身是有限制的,如下面的设计。

type CacheV2[T any] interface {
	Get(ctx context.Context, key string) (T, error)
	Set(ctx context.Context, key string, val T, expiration time.Duration) error
	Delete(ctx context.Context, key string) error
}

func ExampleCacheV2() {
	var userCache CacheV2[User]
	// 下面这一行代码编译器会报错:
  // cannot use Order{} (value of type Order) 
  // as User value in argument to userCache.Set
	userCache.Set(context.Background(), "my-order-01", Order{}, time.Minute)
	userCache.Set(context.Background(), "my-user-01", User{}, time.Minute)
	var orderCache CacheV2[Order]
	orderCache.Set(context.Background(), "my-order-01", Order{}, time.Minute)
}

type User struct {
	Name string
}

type Order struct {
}

泛型设计的优缺点:

  • 优点:用户不需要做类型断言
  • 缺点:一个 CacheV2 的实例,只能存储 T 类型的数据,例如 User 或者 Order

理想版本: 即 CacheV3 本身没有类型参数,而是在具体方法里面定义,那么同样一个 CacheV3 就可以被用于缓存不同类型。

很可惜,Go 泛型是不支持这种写法的。

你们应该注意到,我们在 ORM 里面也面临这种问题。

所有类似的客户端类的中间件,都会受到这个限制。

// 编译不通过
// interface method must have no type parameters [syntax]
type CacheV3 interface {
	Get[T any](ctx context.Context, key string) (T, error)
	Set[T any](ctx context.Context, key string, val T, expiration time.Duration) error
	Delete[T any](ctx context.Context, key string) error
}

var cache CacheV3
cache.Get[User](context.Background(), "John")

本地缓存设计与实现

现在我们要为缓存 API 提供一个本地缓存实现。

要点:

  • 如何做过期时间控制?

如何处理过期时间?

  • 策略 1:每个 key 开一个 goroutine 盯着,过期了就执行删除策略。

  • 策略 2:用一个 goroutine 定时轮询,找到所有过期的 Key,然后删除。

  • 策略 3:啥也不干,用户访问 key 的时候检查过期时间。(set 多 get 少时,内存会上升,因为不会主动删除过期的 key)

策略 1:一一对应

每个 key 开一个 goroutine 盯着,过期了就执行删除策略。

可以利用 time.AfterFunc 来实现。

缺点:

  • key 多了,goroutine 也多了
  • 这些 goroutine 大部分时候都被阻塞,浪费资源
type LocalCache struct {
	m sync.Map
}

// Set(ctx, "key1", value1, time.Minute)
// 执行业务三十秒
// Set(ctx, "key1", value2, time.Minute)
// 再三十秒,第一个 time.AfterFunc 就要执行了
func (l *LocalCache) Set(ctx context.Context, key string, val any, expiration time.Duration) error {
	// 这个是有破绽的
	// time.AfterFunc(expiration, func() {
	// 	if l.m.Load(key).expiration
	// 	l.Delete(context.Background(), key)
	// })
	// 如果你想支持永不过期的,expiration = 0 就说明永不过期
	l.m.Store(key, val)
	return nil
}
type LocalCache struct {
	mu   sync.RWMutex
	data map[string]*item
}

type item struct {
	val      any
	deadline time.Time
}

func (c *LocalCache) Set(ctx context.Context, k string, v any, expiration time.Duration) {
	var dl time.Time
	if expiration > 0 {
		dl = time.Now().Add(expiration)
	}

	c.mu.Lock()
	c.data[k] = &item{
		val:      v,
		deadline: dl,
	}
	c.mu.Unlock()

	if expiration > 0 {
		time.AfterFunc(expiration, func() {
			c.mu.RLock()
			defer c.mu.RUnlock()
			v, ok := c.data[k]
			if ok && !v.deadline.IsZero() && v.deadline.Before(time.Now()) {
				delete(c.data, k)
			}
		})
	}
}

策略 2:goroutine 轮询

在创建 cache 的时候,同时创建一个 goroutine, 这个 goroutine 会检查每个 key 的过期时间,并且在过期之后执行删除。

要点:

  • 要控制住检查的间隔。间隔时间过短,影响用户,资源消耗大

  • 要控制住遍历的资源开销。如果全部 key 遍历一遍,那么可能耗时极长,影响应用

  • 可以控制遍历的时长,例如只遍历 1 ms

  • 可以控制遍历的数量,例如只遍历 100 个

策略 3:Get 检查过期时间

type LocalCache struct {
	mu   sync.RWMutex
	data map[string]*item

	closeOnce sync.Once
	close     chan struct{}
}

type item struct {
	val      any
	deadline time.Time
}

func (i *item) deadlineBeforeNow(t time.Time) bool {
	return !i.deadline.IsZero() && i.deadline.Before(t)
}

func (c *LocalCache) Set(ctx context.Context, k string, v any, expiration time.Duration) {
	var dl time.Time
	if expiration > 0 {
		dl = time.Now().Add(expiration)
	}

	c.mu.Lock()
	c.data[k] = &item{
		val:      v,
		deadline: dl,
	}
	c.mu.Unlock()
}

// Get 的时候,粗暴的做法是直接加写锁,但是也可以考虑用 double-check 写法。
// 我们使用的就是这个方案。
// 前面我们提到不能使用 sync.Map,从这里也可以看出来。
func (c *LocalCache) Get(ctx context.Context, k string) (any, error) {
	c.mu.RLock()
	i, ok := c.data[k]
	c.mu.RUnlock()
	if !ok {
		return nil, errors.New("key not found")
	}

	now := time.Now()
	// 定时轮询单独使用肯定是不行的,
	// 因为一个 key 可能已经过期了,但是还没轮到它,
	// 一般都是跟 Get 的时候检查过期时间配合使用。
	if i.deadlineBeforeNow(now) {
		c.mu.Lock()
		defer c.mu.Unlock()
		// double check
		i, ok = c.data[k]
		if !ok {
			return nil, errors.New("key not found")
		}
		if i.deadlineBeforeNow(now) {
			delete(c.data, k)
			return nil, errors.New("key expired")
		}
	}

	return i.val, nil
}

func NewLocalCache(interval time.Duration) *LocalCache {
	c := &LocalCache{
		data:  make(map[string]*item),
		close: make(chan struct{}),
	}

	go func() {
		ticker := time.NewTicker(interval)
		for {
			select {
			case t := <-ticker.C:
				c.mu.Lock()
				i := 0
				for k, v := range c.data {
					if i > 10000 {
						break
					}
					if !v.deadline.IsZero() && v.deadline.Before(t) {
						delete(c.data, k)
					}
					i++
				}
				c.mu.Unlock()
			case <-c.close:
				return
			}
		}
	}()

	return c
}

func (c *LocalCache) Close() error {
	// 方法一
	// // 要确保 cache 已启动
	// select {
	// case c.close <- struct{}{}:
	// default:
	// 	return errors.New("already closed")
	// }

	// 方法二
	c.closeOnce.Do(func() {
		c.close <- struct{}{}
	})

	return nil
}

过期处理对比

Redis

Redis 的过期处理,也是用的类似的套路:

  • get 的时候检查是否过期
  • 遍历 key 找出过期的删掉

本质上,就是因为过期这个东西没啥特别好的方案,就是我们讨论的这三种。

Redis 在考虑轮询的时候也一样,要控制住轮询的资源开销。在我们这里,则是因为轮询需要写锁,所以也需要控制。

(使用了二和三的策略)

sql.DB

另外一个特别好的例子,就是 sql.DB 中空闲连接的关闭时机。

正常来说,我们可能期望空闲连接一旦空闲的时间足够长了(例如 30s),那么连接池就帮我们把连接关掉。

很可惜,它也面临一样的问题。所以最终它采用的也是懒惰关闭,也就是在 Get 的时候才检查。

(只使用了第三种策略)

    // Prefer a free connection, if possible.
	last := len(db.freeConn) - 1
	if strategy == cachedOrNewConn && last >= 0 {
		// Reuse the lowest idle time connection so we can close
		// connections which remain idle as soon as possible.
		conn := db.freeConn[last]
		db.freeConn = db.freeConn[:last]
		conn.inUse = true
		if conn.expired(lifetime) {
			db.maxLifetimeClosed++
			db.mu.Unlock()
			conn.Close()
			return nil, driver.ErrBadConn
		}
		db.mu.Unlock()

evict 回调与关闭

部分情况下,缓存中间件还可以考虑提供 CDC (change data capture) 接口,例如 key 被更新的时候打印一些数据等。

类似于 Redis 的 subscribe。

在本地缓存实现中,这种接口主要就是缓存过期被删除的回调。

cache-6.png

控制本地缓存内存

缓存,尤其是本地缓存都会面临一个问题:我这个缓存会不会使用了太多内存?

大多数时候我们都需要考虑如何控制住内存使用量。

在考虑控制内存使用量的时候,我们就要考虑,在缓存快要满了的时候,怎么腾出空间来?

腾出空间,这就引出了我们时常遇到的 LRU、 LFU 算法。

cache-7.png

控制内存有两种策略:

  • 控制键值对数量,比如说只能允许十万个键值对
  • 控制整体内存,需要计算每个对象的大小,然后累加

我们可以尝试用装饰器模式来无侵入地支持这种功能。

cache-8.png

type MaxCntCache struct {
	*LocalCache
	cnt    int32
	maxCnt atomic.Int32
}

errKeyNotFound 和 errKeyExpired

在 key 过期时返回哪种错误呢,我倾向于只用 errKeyNotFound。

  • 对于用户来说,他不应该关心究竟是没有这个 key,还是这个 key 已经过期,反正对于他来说,值都没有。
  • 从封装的角度来说,key 过期,就应该被删除了。而 errKeyExpired 实质上是因为我们采用懒惰删除策略才搞出来的。相当于,因为我的实现是这样的,所以我会有这个错误。

知识共享许可协议

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。