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

Golang
91
0
0
2024-03-27

前言

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

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

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)的缓存实现,基于这个接口字段,我们就可以设置对应的淘汰机制。

下面是创建 simpleLRU 本地缓存的函数:

// 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 结构体的 GetSet 方法进行修改。例如 Item 的一个修改案例:

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

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

小结

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

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

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

本文提到的设计是基于个人理解去实现的,可能会有不妥之处。如果有错误的地方,欢迎指出!