ARC cache does not work as expected (when used with expiry) about gcache HOT 6 CLOSED

I think @bluele must be very busy at the moment. I'm not clear on whether he plans to keep maintaining this project going further.

FTR: I thought this issue was introduced by b9993a9 but it seems to have been present for much longer. We need way better testing coverage to prevent this from happening in the future.

@skurfuerst I will fix that this week. I need some time to draft a correct implementation and then implement the expirable entries features, write more extensive tests etc.

from gcache.

Looks like the ARC cache completely falls apart when expirable entries are enabled.

https://github.com/bluele/gcache/blob/master/arc.go#L122

if elt := c.b2.Lookup(key); elt != nil {
	c.part = maxInt(0, c.part-maxInt(c.b1.Len()/c.b2.Len(), 1))
	c.replace(key)
	c.b2.Remove(key, elt)
	c.t2.PushFront(key)
	return item, nil
}

Zooming on c.replace(key) (https://github.com/bluele/gcache/blob/master/arc.go#L40):

func (c *ARC) replace(key interface{}) {
	var old interface{}
	if (c.t1.Len() > 0 && c.b2.Has(key) && c.t1.Len() == c.part) || (c.t1.Len() > c.part) {
		old = c.t1.RemoveTail()
		c.b1.PushFront(old)
	} else if c.t2.l.Len() > 0 {
		old = c.t2.RemoveTail()
		c.b2.PushFront(old)
	} else {
		return
	}

        // old = "test1" <----- Here
	item, ok := c.items[old]
	if ok {
		delete(c.items, old)
		if c.evictedFunc != nil {
			c.evictedFunc(item.key, item.value)
		}
	}
}

Zooming further down that execution path:

else if c.t2.l.Len() > 0 {
    old = c.t2.RemoveTail()
    c.b2.PushFront(old)
}

I'm not clear on whether the t2 sub-ARC cache should be filled up at all (before entries become eligible for eviction) in which case the logic fails in the way data is balanced/distributed among the sub-caches or if (c.t1.Len() > 0 && c.b2.Has(key) && c.t1.Len() == c.part) || (c.t1.Len() > c.part) should evaluate to true.

@bluele can you look into this or give me a high-level overview of the right behavior for ARC internals? thanks!

from gcache.

I believe we are also hit by this. Anything we can do to have this fixed? :)

from gcache.

Thanks for reporting, I was able to reproduce it on my machine. I will investigate this.

from gcache.

Thanks @aaronwinter @bluele for looking into this.

from gcache.

Sorry for very late response.
This issue is solved by #58.

from gcache.