基本原理

核心的原理是双向指针连接所有被访问的item，每一个item都有一个状态表明是否被访问过，每次访问一个新的item就被放到队头，当buffer满了就从尾部开始扫描找到第一个没被访问过的item，并淘汰掉，在扫描的过程中遇到的每一个item都把其状态设置为未访问过。当访问了一个已经存在的item时，需要设置这个item的状态为true。

实现

// Cache is an Sieve cache. It is not safe for concurrent access.
type Cache struct {
	// MaxEntries is the maximum number of cache entries before
	// an item is evicted. Zero means no limit.
	MaxEntries int

	// OnEvicted optionally specifies a callback function to be
	// executed when an entry is purged from the cache.
	OnEvicted func(key Key, value interface{})

	ptr   *list.Element
	ll    *list.List
	cache map[interface{}]*list.Element
}

// A Key may be any value that is comparable. 
// See <http://golang.org/ref/spec#Comparison_operators>
type Key interface{}

type entry struct {
	key     Key
	Visited bool
	value   interface{}
}

// New creates a new Cache.
// If maxEntries is zero, the cache has no limit and it's assumed
// that eviction is done by the caller.
func New(maxEntries int) *Cache {
	return &Cache{
		MaxEntries: maxEntries,
		ptr:        nil,
		ll:         list.New(),
		cache:      make(map[interface{}]*list.Element),
	}
}

// Add adds a value to the cache.
func (c *Cache) Add(key Key, value interface{}) {
	if c.cache == nil {
		c.cache = make(map[interface{}]*list.Element)
		c.ll = list.New()
		c.ptr = nil
	}
	if ee, ok := c.cache[key]; ok {
		ee.Value.(*entry).Visited = true
		ee.Value.(*entry).value = value
		return
	}
	ele := c.ll.PushFront(&entry{key, false, value})
	c.cache[key] = ele
	if c.MaxEntries != 0 && c.ll.Len() > c.MaxEntries {
		c.RemoveOldest()
	}
}

// Get looks up a key's value from the cache.
func (c *Cache) Get(key Key) (value interface{}, ok bool) {
	if c.cache == nil {
		return
	}
	if ele, hit := c.cache[key]; hit {
		ele.Value.(*entry).Visited = true
		return ele.Value.(*entry).value, true
	}
	return
}

// Remove removes the provided key from the cache.
func (c *Cache) Remove(key Key) {
	if c.cache == nil {
		return
	}
	if ele, hit := c.cache[key]; hit {
		c.removeElement(ele)
	}
}

// RemoveOldest removes the oldest item from the cache.
func (c *Cache) RemoveOldest() {
	if c.cache == nil {
		return
	}
	ele := c.ptr
	if ele == nil {
		ele = c.ll.Back()
	}
	for ele != nil && ele.Value.(*entry).Visited {
		ele.Value.(*entry).Visited = false
		ele = ele.Prev()
	}
	if ele == nil {
		ele = c.ll.Back()
	}
	for ele != nil && ele.Value.(*entry).Visited {
		ele.Value.(*entry).Visited = false
		ele = ele.Prev()
	}
	if ele == nil {
		println("Error: RemoveOldest cannot find element")
	}
	c.ptr = ele.Prev()
	c.removeElement(ele)
}

func (c *Cache) removeElement(e *list.Element) {
	c.ll.Remove(e)
	kv := e.Value.(*entry)
	delete(c.cache, kv.key)
	if c.OnEvicted != nil {
		c.OnEvicted(kv.key, kv.value)
	}
}

// Len returns the number of items in the cache.
func (c *Cache) Len() int {
	if c.cache == nil {
		return 0
	}
	return c.ll.Len()
}

// Clear purges all stored items from the cache.
func (c *Cache) Clear() {
	if c.OnEvicted != nil {
		for _, e := range c.cache {
			kv := e.Value.(*entry)
			c.OnEvicted(kv.key, kv.value)
		}
	}
	c.ll = nil
	c.cache = nil
}

Reference

https://cachemon.github.io/SIEVE-website/blog/2023/12/17/sieve-is-simpler-than-lru/#efficiency