Go 实现一个支持多种过期、淘汰机制的本地缓存的核心原理

Golang
144
0
0
2024-03-27
Gin CORS 跨域请求资源共享与中间件
上一篇
完善 Golang Gin 框架的静态中间件：Gin-Static
下一篇

前言

相信大家对于缓存这个词都不陌生，但凡追求高性能的业务场景，一般都会使用缓存，它可以提高数据的检索速度，减少数据库的压力。

本文旨在探讨实现一个支持多种 过期、淘汰 机制的本地缓存的核心原理，我将重点讲解如何支持多样化的过期和淘汰策略。如果需要查看完整的代码设计，请前往以下链接：

https://github.com/chenmingyong0423/go-generics-cache

准备好了吗？准备一杯你最喜欢的咖啡或茶，随着本文一探究竟吧。

过期机制和淘汰机制的区别

如果分不清过期机制和淘汰机制的读者，可以先看看下面的描述：

1、过期机制：

  • 目的：确保数据的时效性和有效性。
  • 实现方式：通过设置固定过期时间或基于最后访问时间的过期机制，确保数据保持最新。

2、淘汰机制

  • 目的：控制缓存的大小，避免缓存占用过多的内存。
  • 实现方式：使用如 LRU（最近最少使用）或 LFU（最不经常使用）等策略，在达到最大容量时移除部分缓存项。

ICache 接口定义

type ICache[K comparable, V any] interface {

	Set(ctx context.Context, key K, value V) error

	Get(ctx context.Context, key K) (V, error)

	Delete(ctx context.Context, key K) error

	Keys() []K
}

在实现本地缓存之前，首先定义一个 ICache[K comparable, V any] 泛型接口，该接口作为多种本地缓存实现的 API 标准，确保不同本地缓存的实现都有相同的基本操作。

本地缓存适配器的实现

Cache 结构体

// https://github.com/chenmingyong0423/go-generics-cache/blob/master/cache.go
type Cache[K comparable, V any] struct {
	cache ICache[K, *Item[V]]
	mutex sync.RWMutex

	janitor *janitor
}

type Item[V any] struct {
	value      V
	expiration time.Time
}

func (c *Cache[K, V]) Get(ctx context.Context, key K) (v V, err error) {
	c.mutex.RLock()
	defer c.mutex.RUnlock()
	item, err := c.cache.Get(ctx, key)
	if err != nil {
		return
	}
	if item.Expired() {
		return v, cacheError.ErrNoKey
	}
	return item.value, nil
}

func (c *Cache[K, V]) Set(ctx context.Context, key K, value V, opts ...ItemOption) (err error) {
	c.mutex.Lock()
	defer c.mutex.Unlock()
	item := newItem[V](value, opts...)
	return c.cache.Set(ctx, key, item)
}

// 省略其余方法

上述代码定义了一个泛型的 Cache[K comparable, V any] 缓存结构体实现。该结构体并非实际的本地缓存的实现，而是一个适配器。该结构体有三个字段：

1、cache ICache[K, *Item[V]]：

  • 底层实现缓存操作的接口。该接口定义了缓存的基本行为，如设置、获取和删除键值对。
  • *Item[V] 是值的类型，这里使用了指针，指向一个 Item 结构，Item 结构体包含了实际的值和过期时间。

2、mutex sync.RWMutex：

  • 读写互斥锁，用于避免并发读写时数据不一致性的问题。

3、janitor *janitor：

  • 一个用于处理后台任务的结构体，例如定时清理过期数据，单独提出一个结构体是为了解耦。

实现支持多种淘汰机制的本地缓存原理

如果要支持多种淘汰机制，最佳的做法是不应集中在一个本地缓存的具体实现里去应用，这会导致代码复杂和难以维护，同时违反了软件设计的开闭原则。

我们应该设计成 → 一个 淘汰机制对应 一个 策略（本地缓存的具体实现）。回想上面的代码定义，Cache 是一个适配器结构体，它有一个 ICache 类型的字段 cache，通过引入该接口字段，遵循了 依赖倒置原则 和 策略模式，从而可以根据不同需求选择合适的缓存实现。

不同的缓存实现有着不同的缓存淘汰机制，例如 最近最少使用（LRU）缓存实现、最不经常使用（LFU）的缓存实现，基于这个接口字段，我们就可以设置对应的淘汰机制。

下面是创建 simple 和 LRU 本地缓存的函数：

// https://github.com/chenmingyong0423/go-generics-cache/blob/master/cache.go
func NewSimpleCache[K comparable, V any](ctx context.Context, size int, interval time.Duration) *Cache[K, V] {
	cache := &Cache[K, V]{
		cache:   simple.NewCache[K, *Item[V]](size),
		janitor: newJanitor(ctx, interval),
	}
	cache.janitor.run(cache.DeleteExpired)
	return cache
}

func NewLruCache[K comparable, V any](ctx context.Context, cap int, interval time.Duration) *Cache[K, V] {
	cache := &Cache[K, V]{
		cache:   lru.NewCache[K, *Item[V]](cap),
		janitor: newJanitor(ctx, interval),
	}
	cache.janitor.run(cache.DeleteExpired)
	return cache
}

在这两个构造函数中，Cache 结构体的 cache 字段初始化为不同的本地缓存实现。这种设计允许根据具体需求选择相应的淘汰机制，例如使用 LRU 本地缓存来淘汰元素。这样，我们就可以灵活应对不同的缓存场景，确保缓存策略的适用性和高效性。

如果想了解 lru 本地缓存如何实现，可前往 → https://github.com/chenmingyong0423/go-generics-cache/blob/master/lru/lru_cache.go 进行查看。

实现支持多种过期机制的本地缓存原理

// https://github.com/chenmingyong0423/go-generics-cache/blob/master/cache.go
type ItemOption func(*itemOptions)

type itemOptions struct {
	expiration time.Time
}

func WithExpiration(exp time.Duration) ItemOption {
	return func(o *itemOptions) {
		o.expiration = time.Now().Add(exp)
	}
}

type Item[V any] struct {
	value      V
	expiration time.Time
}

func newItem[V any](value V, opts ...ItemOption) *Item[V] {
	var item = &itemOptions{}
	for _, opt := range opts {
		opt(item)
	}
	return &Item[V]{
		value:      value,
		expiration: item.expiration,
	}
}

func (i *Item[V]) Expired() bool {
	return !i.expiration.IsZero() && i.expiration.Before(time.Now())
}

func (c *Cache[K, V]) Get(ctx context.Context, key K) (v V, err error) {
	c.mutex.RLock()
	defer c.mutex.RUnlock()
	item, err := c.cache.Get(ctx, key)
	if err != nil {
		return
	}
	if item.Expired() {
		return v, cacheError.ErrNoKey
	}
	return item.value, nil
}

func (c *Cache[K, V]) Delete(ctx context.Context, key K) (err error) {
	c.mutex.Lock()
	defer c.mutex.Unlock()
	return c.cache.Delete(ctx, key)
}

func (c *Cache[K, V]) Keys() []K {
	return c.cache.Keys()
}

func (c *Cache[K, V]) DeleteExpired(ctx context.Context) {
	c.mutex.RLock()
	keys := c.Keys()
	c.mutex.RUnlock()
	i := 0
	for _, key := range keys {
		if i > 10000 {
			return
		}
		c.mutex.Lock()
		if item, err := c.cache.Get(ctx, key); err == nil && item.Expired() {
			_ = c.cache.Delete(ctx, key)
		}
		c.mutex.Unlock()
		i++
	}
}

func (c *Cache[K, V]) SetNX(ctx context.Context, key K, value V, opts ...ItemOption) (b bool, err error) {
	c.mutex.Lock()
	defer c.mutex.Unlock()
	_, err = c.cache.Get(ctx, key)
	if err != nil {
		if errors.Is(err, cacheError.ErrNoKey) {
			item := newItem[V](value, opts...)
			return true, c.cache.Set(ctx, key, item)
		}
		return false, err
	}
	return false, nil
}

func (c *Cache[K, V]) Set(ctx context.Context, key K, value V, opts ...ItemOption) (err error) {
	c.mutex.Lock()
	defer c.mutex.Unlock()
	item := newItem[V](value, opts...)
	return c.cache.Set(ctx, key, item)
}

我们重点关注 Set 方法，其第三个参数为 ItemOptions 类型，它是一个可选参数，意味着我们可以选择性地去设置 Item 的某些属性值。目前 ItemOption 只有一个 expiration 过期时间的可选参数，因此我们可以根据不同情况，决定是否使用 WithExpiration 函数设置过期时间。

这种设计，使得元素支持多种过期机制（固定时间过期和永久不过期的机制）。当然我们还可以添加其他的过期机制，例如 滑动过期时间（缓存项的过期时间会根据最后一次访问时间进行更新），那么就需要对 Item 结构体和 itemOptions 以及 Cache 结构体的 Get 和 Set 方法进行修改。例如 Item 的一个修改案例：

type Item[V any] struct {
	value             V
	fixedExpiration   time.Time // 固定过期时间
	slidingExpiration time.Duration
	lastAccessed      time.Time // 记录最后访问时间
}

相应的，itemOptions 和关联代码也要修改。

小结

本文探讨了实现一个支持多种 过期、淘汰 机制的本地缓存的核心原理。

为了实现多种淘汰机制，我们可以采用不同的策略（也称为本地缓存的具体实现）来实现各种淘汰机制，然后，通过一个本地缓存适配器结合策略模式，根据不同需求选择合适的缓存实现（淘汰机制）。

至于实现多种过期机制的实现，我们可以将设计重点放在缓存项 Item 和 Set 方法上。例如，在 Item 项中，如果需要支持多种过期机制，我们可以根据需求设计其属性，并使用选项模式，有选择地设置属性的值。最终，将可选参数传递给 Set 方法来实现不同的过期策略。

本文提到的设计是基于个人理解去实现的，可能会有不妥之处。如果有错误的地方，欢迎指出！
Gin CORS 跨域请求资源共享与中间件
上一篇
完善 Golang Gin 框架的静态中间件：Gin-Static
下一篇