cache发现一个简单的cache项目，这里面有2q，arc cache实现,算法原理看末尾

下面是arc cache代码

go
package arc



import (
	"sync"

	"github.com/hashicorp/golang-lru/v2/simplelru"
)

// ARCCache 是一个线程安全的固定大小的自适应替换缓存（ARC）。
// ARC 是对标准 LRU 缓存的增强，它同时跟踪使用的频率和最近性。
// 这样可以避免对新条目的访问的突发情况导致频繁使用的旧条目被驱逐。
// 与标准 LRU 缓存相比，它增加了一些额外的跟踪开销，计算上大约是 2 倍的成本，
// 并且额外的内存开销与缓存大小成线性关系。
// ARC 已被 IBM 专利，但类似于 TwoQueueCache（2Q），需要设置参数。
type ARCCache[K comparable, V any] struct {
	size int // Size 是缓存的总容量
	p    int // P 是对 T1 或 T2 的动态偏好

	t1 simplelru.LRUCache[K, V]        // T1 是最近访问的项目的 LRU
	b1 simplelru.LRUCache[K, struct{}] // B1 是从 T1 驱逐的项目的 LRU

	t2 simplelru.LRUCache[K, V]        // T2 是频繁访问的项目的 LRU
	b2 simplelru.LRUCache[K, struct{}] // B2 是从 T2 驱逐的项目的 LRU

	lock sync.RWMutex
}

// NewARC 创建一个给定大小的 ARC
func NewARC[K comparable, V any](size int) (*ARCCache[K, V], error) {
	// 创建子 LRUs
	b1, err := simplelru.NewLRU[K, struct{}](size, nil)
	if err != nil {
		return nil, err
	}
	b2, err := simplelru.NewLRU[K, struct{}](size, nil)
	if err != nil {
		return nil, err
	}
	t1, err := simplelru.NewLRU[K, V](size, nil)
	if err != nil {
		return nil, err
	}
	t2, err := simplelru.NewLRU[K, V](size, nil)
	if err != nil {
		return nil, err
	}

	// 初始化 ARC
	c := &ARCCache[K, V]{
		size: size,
		p:    0,
		t1:   t1,
		b1:   b1,
		t2:   t2,
		b2:   b2,
	}
	return c, nil
}

// Get 查找缓存中键的值。
func (c *ARCCache[K, V]) Get(key K) (value V, ok bool) {
	c.lock.Lock()
	defer c.lock.Unlock()

	// 如果值包含在 T1（最近）中，则提升到 T2（频繁）
	if val, ok := c.t1.Peek(key); ok {
		c.t1.Remove(key)
		c.t2.Add(key, val)
		return val, ok
	}

	// 检查值是否包含在 T2（频繁）中
	if val, ok := c.t2.Get(key); ok {
		return val, ok
	}

	// 未命中
	return
}

// Add 向缓存中添加一个值。
func (c *ARCCache[K, V]) Add(key K, value V) {
	c.lock.Lock()
	defer c.lock.Unlock()

	// 检查值是否包含在 T1（最近）中，可能提升到频繁的 T2
	if c.t1.Contains(key) {
		c.t1.Remove(key)
		c.t2.Add(key, value)
		return
	}

	// 检查值是否已经在 T2（频繁）中并更新它
	if c.t2.Contains(key) {
		c.t2.Add(key, value)
		return
	}

	// 检查该值是否最近作为最近使用列表的一部分而被驱逐
	if c.b1.Contains(key) {
		// T1 集合太小，适当地增加 P
		delta := 1
		b1Len := c.b1.Len()
		b2Len := c.b2.Len()
		if b2Len > b1Len {
			delta = b2Len / b1Len
		}
		if c.p+delta >= c.size {
			c.p = c.size
		} else {
			c.p += delta
		}

		// 可能需要在缓存中腾出空间
		if c.t1.Len()+c.t2.Len() >= c.size {
			c.replace(false)
		}

		// 从 B1 中删除
		c.b1.Remove(key)

		// 将键添加到频繁使用的列表中
		c.t2.Add(key, value)
		return
	}

	// 检查该值是否最近作为频繁使用列表的一部分而被驱逐
	if c.b2.Contains(key) {
		// T2 集合太小，适当地减小 P
		delta := 1
		b1Len := c.b1.Len()
		b2Len := c.b2.Len()
		if b1Len > b2Len {
			delta = b1Len / b2Len
		}
		if delta >= c.p {
			c.p = 0
		} else {
			c.p -= delta
		}

		// 可能需要在缓存中腾出空间
		if c.t1.Len()+c.t2.Len() >= c.size {
			c.replace(true)
		}

		// 从 B2 中删除
		c.b2.Remove(key)

		// 将键添加到频繁使用的列表中
		c.t2.Add(key, value)
		return
	}

	// 可能需要在缓存中腾出空间
	if c.t1.Len()+c.t2.Len() >= c.size {
		c.replace(false)
	}

	// 保持幽灵缓冲区的大小
	if c.b1.Len() > c.size-c.p {
		c.b1.RemoveOldest()
	}
	if c.b2.Len() > c.p {
		c.b2.RemoveOldest()
	}

	// 添加到最近看到的列表中
	c.t1.Add(key, value)
}

// replace 用于根据当前学到的 P 值自适应地从 T1 或 T2 中驱逐。
func (c *ARCCache[K, V]) replace(b2ContainsKey bool) {
	t1Len := c.t1.Len()
	if t1Len > 0 && (t1Len > c.p || (t1Len == c.p && b2ContainsKey)) {
		k, _, ok := c.t1.RemoveOldest()
		if ok {
			c.b1.Add(k, struct{}{})
		}
	} else {
		k, _, ok := c.t2.RemoveOldest()
		if ok {
			c.b2.Add(k, struct{}{})
		}
	}
}

// Len 返回缓存中条目的数量
func (c *ARCCache[K, V]) Len() int {
	c.lock.RLock()
	defer c.lock.RUnlock()
	return c.t1.Len() + c.t2.Len()
}

// Keys 返回所有缓存的键
func (c *ARCCache[K, V]) Keys() []K {
	c.lock.RLock()
	defer c.lock.RUnlock()
	k1 := c.t1.Keys()
	k2 := c.t2.Keys()
	return append(k1, k2...)
}

// Values 返回所有缓存的值
func (c *ARCCache[K, V]) Values() []V {
	c.lock.RLock()
	defer c.lock.RUnlock()
	v1 := c.t1.Values()
	v2 := c.t2.Values()
	return append(v1, v2...)
}

// Remove 用于从缓存中清除键
func (c *ARCCache[K, V]) Remove(key K) {
	c.lock.Lock()
	defer c.lock.Unlock()
	if c.t1.Remove(key) {
		return
	}
	if c.t2.Remove(key) {
		return
	}
	if c.b1.Remove(key) {
		return
	}
	if c.b2.Remove(key) {
		return
	}
}

// Purge 用于清除缓存
func (c *ARCCache[K, V]) Purge() {
	c.lock.Lock()
	defer c.lock.Unlock()
	c.t1.Purge()
	c.t2.Purge()
	c.b1.Purge()
	c.b2.Purge()
}

// Contains 用于检查缓存是否包含键，而不更新最近性或频率。
func (c *ARCCache[K, V]) Contains(key K) bool {
	c.lock.RLock()
	defer c.lock.RUnlock()
	return c.t1.Contains(key) || c.t2.Contains(key)
}

// Peek 用于检查键的缓存值，而不更新最近性或频率。
func (c *ARCCache[K, V]) Peek(key K) (value V, ok bool) {
	c.lock.RLock()
	defer c.lock.RUnlock()
	if val, ok := c.t1.Peek(key); ok {
		return val, ok
	}
	return c.t2.Peek(key)
}

接下来是2q缓存

go

// 版权所有（c）HashiCorp，Inc。
// SPDX-License-Identifier: MPL-2.0

package lru

import (
	"errors"
	"sync"

	"github.com/hashicorp/golang-lru/v2/simplelru"
)

const (
	// Default2QRecentRatio 是 2Q 缓存中专用于最近添加的仅被访问一次的条目的比率。
	Default2QRecentRatio = 0.25

	// Default2QGhostEntries 是保存用于跟踪最近驱逐的条目的默认幽灵条目比率。
	Default2QGhostEntries = 0.50
)

// TwoQueueCache 是一个线程安全的固定大小的 2Q 缓存。
// 2Q 是对标准 LRU 缓存的增强，因为它单独跟踪频繁使用和最近使用的条目。
// 这避免了对新条目的访问的突发情况导致频繁使用的条目被驱逐。
// 它相对于标准 LRU 缓存增加了一些额外的跟踪开销，计算上大约是 2 倍的成本，并添加了一些元数据。
// ARCCache 类似，但不需要设置任何参数。
type TwoQueueCache[K comparable, V any] struct {
	size        int
	recentSize  int
	recentRatio float64
	ghostRatio  float64

	recent      simplelru.LRUCache[K, V]
	frequent    simplelru.LRUCache[K, V]
	recentEvict simplelru.LRUCache[K, struct{}]
	lock        sync.RWMutex
}

// New2Q 使用默认值为参数创建一个新的 TwoQueueCache。
func New2Q[K comparable, V any](size int) (*TwoQueueCache[K, V], error) {
	return New2QParams[K, V](size, Default2QRecentRatio, Default2QGhostEntries)
}

// New2QParams 使用提供的参数值创建一个新的 TwoQueueCache。
func New2QParams[K comparable, V any](size int, recentRatio, ghostRatio float64) (*TwoQueueCache[K, V], error) {
	if size <= 0 {
		return nil, errors.New("无效的大小")
	}
	if recentRatio < 0.0 || recentRatio > 1.0 {
		return nil, errors.New("无效的最近比率")
	}
	if ghostRatio < 0.0 || ghostRatio > 1.0 {
		return nil, errors.New("无效的幽灵比率")
	}

	// 确定子大小
	recentSize := int(float64(size) * recentRatio)
	evictSize := int(float64(size) * ghostRatio)

	// 分配 LRUs
	recent, err := simplelru.NewLRU[K, V](size, nil)
	if err != nil {
		return nil, err
	}
	frequent, err := simplelru.NewLRU[K, V](size, nil)
	if err != nil {
		return nil, err
	}
	recentEvict, err := simplelru.NewLRU[K, struct{}](evictSize, nil)
	if err != nil {
		return nil, err
	}

	// 初始化缓存
	c := &TwoQueueCache[K, V]{
		size:        size,
		recentSize:  recentSize,
		recentRatio: recentRatio,
		ghostRatio:  ghostRatio,
		recent:      recent,
		frequent:    frequent,
		recentEvict: recentEvict,
	}
	return c, nil
}

// Get 从缓存中查找键的值。
func (c *TwoQueueCache[K, V]) Get(key K) (value V, ok bool) {
	c.lock.Lock()
	defer c.lock.Unlock()

	// 检查这是否是一个频繁使用的值
	if val, ok := c.frequent.Get(key); ok {
		return val, ok
	}

	// 如果值包含在 recent 中，那么我们提升它到 frequent 中
	if val, ok := c.recent.Peek(key); ok {
		c.recent.Remove(key)
		c.frequent.Add(key, val)
		return val, ok
	}

	// 未命中
	return
}

// Add 向缓存中添加一个值。
func (c *TwoQueueCache[K, V]) Add(key K, value V) {
	c.lock.Lock()
	defer c.lock.Unlock()

	// 检查值是否已经频繁使用，并只更新值
	if c.frequent.Contains(key) {
		c.frequent.Add(key, value)
		return
	}

	// 检查值是否最近使用，并将值提升到频繁列表中
	if c.recent.Contains(key) {
		c.recent.Remove(key)
		c.frequent.Add(key, value)
		return
	}

	// 如果值最近被驱逐，将其添加到频繁使用的列表中
	if c.recentEvict.Contains(key) {
		c.ensureSpace(true)
		c.recentEvict.Remove(key)
		c.frequent.Add(key, value)
		return
	}

	// 添加到最近看到的列表中
	c.ensureSpace(false)
	c.recent.Add(key, value)
}

// ensureSpace 用于确保我们在缓存中有空间
func (c *TwoQueueCache[K, V]) ensureSpace(recentEvict bool) {
	// 如果我们有空间，什么也不做
	recentLen := c.recent.Len()
	freqLen := c.frequent.Len()
	if recentLen+freqLen < c.size {
		return
	}

	// 如果 recent 缓冲区比目标大，从那里驱逐
	if recentLen > 0 && (recentLen > c.recentSize || (recentLen == c.recentSize && !recentEvict)) {
		k, _, _ := c.recent.RemoveOldest()
		c.recentEvict.Add(k, struct{}{})
		return
	}

	// 否则从频繁列表中移除
	c.frequent.RemoveOldest()
}

// Len 返回缓存中的条目数。
func (c *TwoQueueCache[K, V]) Len() int {
	c.lock.RLock()
	defer c.lock.RUnlock()
	return c.recent.Len() + c.frequent.Len()
}

// Resize 更改缓存大小。
func (c *TwoQueueCache[K, V]) Resize(size int) (evicted int) {
	c.lock.Lock()
	defer c.lock.Unlock()

	// 重新计算子大小
	recentSize := int(float64(size) * c.recentRatio)
	evictSize := int(float64(size) * c.ghostRatio)
	c.size = size
	c.recentSize = recentSize

	// ensureSpace
	diff := c.recent.Len() + c.frequent.Len() - size
	if diff < 0 {
		diff = 0
	}
	for i := 0; i < diff; i++ {
		c.ensureSpace(true)
	}

	// 重新分配 LRUs
	c.recent.Resize(size)
	c.frequent.Resize(size)
	c.recentEvict.Resize(evictSize)

	return diff
}

// Keys 返回缓存中键的切片。
// 频繁使用的键在返回的切片中排在前面。
func (c *TwoQueueCache[K, V]) Keys() []K {
	c.lock.RLock()
	defer c.lock.RUnlock()
	k1 := c.frequent.Keys()
	k2 := c.recent.Keys()
	return append(k1, k2...)
}

// Values 返回缓存中值的切片。
// 频繁使用的值在返回的切片中排在前面。
func (c *TwoQueueCache[K, V]) Values() []V {
	c.lock.RLock()
	defer c.lock.RUnlock()
	v1 := c.frequent.Values()
	v2 := c.recent.Values()
	return append(v1, v2...)
}

// Remove 从缓存中移除提供的键。
func (c *TwoQueueCache[K, V]) Remove(key K) {
	c.lock.Lock()
	defer c.lock.Unlock()
	if c.frequent.Remove(key) {
		return
	}
	if c.recent.Remove(key) {
		return
	}
	if c.recentEvict.Remove(key) {
		return
	}
}

// Purge 用于完全清除缓存。
func (c *TwoQueueCache[K, V]) Purge() {
	c.lock.Lock()
	defer c.lock.Unlock()
	c.recent.Purge()
	c.frequent.Purge()
	c.recentEvict.Purge()
}

// Contains 用于检查缓存是否包含键，而不更新最近性或频率。
func (c *TwoQueueCache[K, V]) Contains(key K) bool {
	c.lock.RLock()
	defer c.lock.RUnlock()
	return c.frequent.Contains(key) || c.recent.Contains(key)
}

// Peek 用于检查键的缓存值，而不更新最近性或频率。
func (c *TwoQueueCache[K, V]) Peek(key K) (value V, ok bool) {
	c.lock.RLock()
	defer c.lock.RUnlock()
	if val, ok := c.frequent.Peek(key); ok {
		return val, ok
	}
	return c.recent.Peek(key)
}

1. 图解 LRU LFU ARC FIFO 缓存淘汰算法 - 掘金
2. 缓存淘汰算法（LFU、LRU、ARC、FIFO、2Q）分析 - 知乎
3. Adaptive Replacement Cache(ARC) 缓存淘汰算法 - 知乎