bluele / gcache Goto Github PK
View Code? Open in Web Editor NEWAn in-memory cache library for golang. It supports multiple eviction policies: LRU, LFU, ARC
License: MIT License
An in-memory cache library for golang. It supports multiple eviction policies: LRU, LFU, ARC
License: MIT License
I know this is probably a pretty big feature req, but it looks like the current implementation works based on the number of objects in the cache. It would be extremely useful to have a size based cache, which didn't care about the number of objects, but would start expiring things after a specified memory capacity was exceeded.
Apologies upfront for a possible misunderstanding of some fundamental concept, but I just couldn't figure out why not to return len(items) instead?
Or in other words, why to create a full copy of the cache when the only thing that is required to know is it's size?
2017/04/11 15:08:16 http: panic serving 127.0.0.1:59608: interface conversion: interface {} is string, not *gcache.arcItem goroutine 130 [running]: net/http.(*conn).serve.func1(0xc420192000) /usr/local/Cellar/go/1.8/libexec/src/net/http/server.go:1721 +0x183 panic(0x4909480, 0xc420162900) /usr/local/Cellar/go/1.8/libexec/src/runtime/panic.go:489 +0x2f0 github.com/redsift/flexo-botfwk/vendor/github.com/bluele/gcache.(*ARC).remove(0xc42032c210, 0x48cd620, 0xc42058ef30, 0x480a963) /Users/dmotylev/Workshop/go/src/github.com/redsift/flexo-botfwk/vendor/github.com/bluele/gcache/arc.go:258 +0x9f9 github.com/redsift/flexo-botfwk/vendor/github.com/bluele/gcache.(*ARC).Remove(0xc42032c210, 0x48cd620, 0xc42058ef30, 0xc42058ef00) /Users/dmotylev/Workshop/go/src/github.com/redsift/flexo-botfwk/vendor/github.com/bluele/gcache/arc.go:244 +0x9c
I'm using simple gcache. I've implemented LoaderFunc and addedFunc using a database as a store.
When gcache loads a new value using LoaderFunc and set new one to a cache. Set function will call addedFunc if it exists. But the new value already exists in a db. So call "addedFunc" is redundantly in that case.
Is it expected behaviour? Does any workaround exist in such case?
I want to get the TTL of a key, but there's no available method?
The current behavior of Purge()
is such that the EvictedFunc()
is not called when items are removed from the cache (the cached items lists are just replaced and handed off to the GC). Without a higher-level locking primitive, there is not a way to purge a cache and call the evict handler.
It would be nice if the interface was updated to include PurgeExpire()
that would take c.mu.Lock()
and, if evictedFunc()
is not nil
, call GetALL()
+ evictedFunc()
on each of the items while c.mu
held and before c.init()
is called.
Or Purge()
could be updated to implicitly call evictFunc()
on each item. Without this change to make Purge()
symmetric w/ calls to LoaderFunc()
, it is difficult to use this cache for finite resources (e.g. file descriptors). Resorting to finalizers used in the LoaderFunc()
feels very distasteful and like a hack.
I'm happy to PR this change but want to inquire re: the API first before submitting a PR.
Manually set a key-value pair, with an expiration time.
value, err = gc.Get("key")
should be
value, err := gc.Get("key")
问下啊,初始化的size参数单位是缓存个数还是容量啊
Hi, would you consider taking a patch that threads context through the Get -> load -> LoaderFunc call chain? We've patch the library already, and would be happy to upstream.
Or simply leave it to GC?
Thanks.
Just discovered this library and seems useful for what I'd like to do.
I noticed in #25 , functionality was added to allow user defined expiry per item. The SetWithExpire
methods. Can we extend this to LoaderFunc
?
type LoaderFuncWithExpire func(interface{}) (interface{}, time.Duration, error)
Unrelated question: If my LoaderFunc
is very slow, and there are multiple Get
for same key, will gcache run the LoaderFunc
multiple times, or only once and send same output to all callers?
Panicking in a library is an anti-pattern in Go. It results in indeterministic and unpredictable code. The caller has no idea when a library is going to panic unless they are experts in the library's codebase.
Currently, this is being done in several places:
Line 70 in bbe6d2a
Line 163 in bbe6d2a
I believe a better option would be to allow for any size in the New()
function, but then checking it in the Build()
and returning an error. This makes it more idiomatic and removes the possibility that the caller's program crashes unexpectedly because of a bad input.
Hi,
thanks for the caching library. While trying to integrate this into a project I work on I receive the following panick reproducibly(after a variable time of 20sec~1min):
[signal SIGSEGV: segmentation violation code=0x1 addr=0x20 pc=0x625f06]
goroutine 36 [running]:
panic(0x7ba5a0, 0xc42000c0c0)
/usr/local/go/src/runtime/panic.go:500 +0x1a1
github.com/bluele/gcache.(*arcItem).IsExpired(0x0, 0x0, 0xc43612dd30)
/src/github.com/bluele/gcache/arc.go:311 +0x26
github.com/bluele/gcache.(*ARC).get(0xc4200ab9a0, 0x7979c0, 0xc429f6a680, 0xc4438e5c00, 0x88, 0x822d00, 0xc43612de08, 0x411d05)
/src/github.com/bluele/gcache/arc.go:178 +0x22f
github.com/bluele/gcache.(*ARC).getValue(0xc4200ab9a0, 0x7979c0, 0xc429f6a680, 0xc43612de30, 0x40dfbb, 0x7979c0, 0xc429f6a680)
/src/github.com/bluele/gcache/arc.go:205 +0x48
github.com/bluele/gcache.(*ARC).GetIFPresent(0xc4200ab9a0, 0x7979c0, 0xc429f6a680, 0x7979c0, 0xc429f6a680, 0x0, 0xc421373540)
/src/github.com/bluele/gcache/arc.go:142 +0x43
...
I tried replacing all locks within the function with a RW lock that wraps the function but this also yields the same panick. So I guess the error is somewhere else.
My code has about 10 workers that share the cache. I could probably make the cache only available to one worker at a time but I guess that wouldn't solve the root of the problem.
I only call the cache in two different places:
cache := gcache.New(1000).ARC().Build()
cache.Set(domain,robotsTxt)
and cache.GetIFPresent(domain)
Do you have any idea what causes this?
Best
Niels-Ole
Not sure if there any plan to support generics, I made one at https://github.com/szyhf/go-gcache, just simply replace the implement.
Really thanks for this awsome lib, if there any plan I really like to make a pr.
`type Cache interface {
Set(key, value interface{}) error
SetWithExpire(key, value interface{}, expiration time.Duration) error
Get(key interface{}) (interface{}, error)
GetIFPresent(key interface{}) (interface{}, error)
GetALL(checkExpired bool) map[interface{}]interface{}
get(key interface{}, onLoad bool) (interface{}, error)
Remove(key interface{}) bool
Purge()
Keys(checkExpired bool) []interface{}
Len(checkExpired bool) int
Has(key interface{}) bool
statsAccessor
}`
like BatchSet and BatchGet
I found that the get
function in LRU
may be not proper implemented.
c.mu.RLock()
item, ok := c.items[key]
c.mu.RUnlock()
if ok {
it := item.Value.(*lruItem)
if !it.IsExpired(nil) {
c.mu.Lock()
defer c.mu.Unlock()
c.evictList.MoveToFront(it)
return it.value, nil
}
c.mu.Lock()
c.removeElement(item)
c.mu.Unlock()
}
I think LRU
should move the accessed item when getting to the front of the access tracking list, not just when setting.
Hello @bluele
What's the status of gcache
? There hasn't been any updates in over a year, and several PR's would help add functionality to this library.
Thanks!
Hi, gcache developers!!
I hope to use a gcache in multiprocesses.
By the way, I'm thinking about how I can share a cache store in every process (there is a single parent process and multiple child processes).
When I wrote C++ before, I used shared memory to share it between processes, and I'm working on a project to move to Golang, and I'm thinking about a good way.
I'm thinking about gcache, is there an appropriate way?
Hi,
Do you plan to add, in the near future, support for expirable entries?
e.g:
expiration := time.Now().Add(24 * time.Hour) // Now + 24h
gc := gcache.New(10).LRU().Build()
gc.Set("key", "value", expiration)
If you don't, would you be interested in a PR that extends the current implementation to support that feature?
Consider this modified test:-
gc := buildLoadingARCacheWithExpiration(20, 1*time.Second)
gc.Get("test1")
gc.Get("test2")
length := gc.Len()
expectedLength := 2
if length != expectedLength {
t.Errorf("Expected length is %v, not %v", expectedLength, length)
}
time.Sleep(2 * time.Second)
length = gc.Len()
expectedLength = 0
if length != expectedLength {
t.Errorf("Expected length is %v, not %v", expectedLength, length)
}
gc.Get("test1")
length = gc.Len()
expectedLength = 1
if length != expectedLength {
t.Errorf("Expected length is %v, not %v", expectedLength, length)
}
gc.Get("test2")
length = gc.Len()
expectedLength = 2
if length != expectedLength {
t.Errorf("Expected length is %v, not %v", expectedLength, length)
}
}
Adding back test1 and test2 after they have expired doesn't return a length of 2 as expected. It looks like there is an issue with adding an entry that has expired.
There is a fairly severe memory leak in the implementation of the LFU cache. This leak may also manifest itself in the other algorithms, although I haven't checked yet.
Here is what my main function looks like to produce this leak.
func main() {
defer profile.Start(profile.MemProfile).Stop()
gc := gcache.New(10).
LFU().
Build()
gc.Set("key0", "ok0")
gc.Set("key1", "ok1")
gc.Set("key2", "ok2")
gc.Set("key3", "ok3")
for i := 0; i < 400000; i++ {
v, err := gc.Get("key0")
if err != nil {
panic(err)
}
if i == 399999 {
fmt.Println("value:", v)
}
}
}
As you can see in the function above. We first initialize a new LFU cache that can hold 10 items. We then set 4 of these items to key:value pairs. Finally we read the first item 400,000 times, and print it's value on the last run.
Below is the output of the memory profiler looking at the functions making the most memory allocations.
$ go tool pprof ~/test /tmp/profile958427541/mem.pprof
File: test
Type: inuse_space
Time: Dec 4, 2020 at 12:38pm (EST)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top5
Showing nodes accounting for 14MB, 100% of 14MB total
Showing top 5 nodes out of 8
flat flat% sum% cum cum%
10.58MB 75.53% 75.53% 14MB 100% github.com/bluele/gcache.(*LFUCache).increment
3.43MB 24.47% 100% 3.43MB 24.47% container/list.(*List).insertValue (inline)
0 0% 100% 3.43MB 24.47% container/list.(*List).InsertAfter (inline)
0 0% 100% 14MB 100% github.com/bluele/gcache.(*LFUCache).Get
0 0% 100% 14MB 100% github.com/bluele/gcache.(*LFUCache).get
This immediately indicates that somehow, the 4 key value pairs placed into the cache, along with the 400,000 reads performed, required an allocation of 14MB of memory. As we can see, the majority of all the allocations came from inside the github.com/bluele/gcache.(*LFUCache).increment frunction.
If we take a look at this function we see the following:
func (c *LFUCache) increment(item *lfuItem) {
currentFreqElement := item.freqElement
currentFreqEntry := currentFreqElement.Value.(*freqEntry)
nextFreq := currentFreqEntry.freq + 1
delete(currentFreqEntry.items, item)
nextFreqElement := currentFreqElement.Next()
if nextFreqElement == nil {
nextFreqElement = c.freqList.InsertAfter(&freqEntry{
freq: nextFreq,
items: make(map[*lfuItem]struct{}),
}, currentFreqElement)
}
nextFreqElement.Value.(*freqEntry).items[item] = struct{}{}
item.freqElement = nextFreqElement
}
At first glance, it becomes obvious that the frequency list inside the cache struct (c.freqList) is growing quite large. If we trace the increment function upwards we can see it is called every time we request an item from the cache, as long as we did not set a timeout on our items (in this case we did not).
The result of this is that c.freqList grows by one list entry every time we request an item from the cache. We can see this behavior in the Devel debugger:
(hits goroutine(1):1 total:1) (PC: 0x4f9225)
179:
180: func (c *LFUCache) increment(item *lfuItem) {
181: currentFreqElement := item.freqElement
182: currentFreqEntry := currentFreqElement.Value.(*freqEntry)
183: nextFreq := currentFreqEntry.freq + 1
=> 184: delete(currentFreqEntry.items, item)
185:
186: nextFreqElement := currentFreqElement.Next()
187: if nextFreqElement == nil {
188: nextFreqElement = c.freqList.InsertAfter(&freqEntry{
189: freq: nextFreq,
(dlv) continue
(dlv) continue // We skip ahead now 40 calls to increment()
(dlv) continue
.
.
.
.
(hits goroutine(1):40 total:40) (PC: 0x4f9225)
181: currentFreqElement := item.freqElement
182: currentFreqEntry := currentFreqElement.Value.(*freqEntry)
183: nextFreq := currentFreqEntry.freq + 1
184: delete(currentFreqEntry.items, item)
185:
=> 186: nextFreqElement := currentFreqElement.Next()
187: if nextFreqElement == nil {
188: nextFreqElement = c.freqList.InsertAfter(&freqEntry{
189: freq: nextFreq,
190: items: make(map[*lfuItem]struct{}),
191: }, currentFreqElement)
(dlv) print c.freqList
*container/list.List {
root: container/list.Element {
next: *(*"container/list.Element")(0xc000078750),
prev: *(*"container/list.Element")(0xc0000795f0),
list: *container/list.List nil,
Value: interface {} nil,},
len: 40,}
The above steps were as follows. Set a breakpoint on line 186, in the middle of the increment function. Run continue to skip to the next time we hit the break point. Do this 39 more times to allow 40 consecutive reads from the cache. At this point, we print the frequency list in the cache with (dlv) print c.freqList. This shows us that the list is of length 40, even though there are only 4 items in the cache.
If we follow the debugger further this pattern continues and the list grows linearly. This is obviously unacceptable behavior and ends up consuming large amounts of memory for operations that should consume none.
Sir, what is the unit of size?
c.items = make(map[interface{}]*lfuItem, c.size+1)
I think following interface may be better.
type LoaderFunc func(key interface{}) (value interface{}, canAdd bool)
Being forced to provide a cache size during construction of the cache doesn't work well for our particular use case. The size of our cache is bounded in other more real-world ways and we don't need to worry about the cache growing out of control. To that end, I'd like to request a new function on the cache builder to allow for no max cache size. The New()
method could be changed such that it allows for <=0 size that is interpreted as unbounded.
Do you support go mod?
It would be great that instead of a Get+Set that there was an Increment operator, ideally goroutine safe.
examples causing redefine main function error with go get
github.com/bluele/gcache/examples
# github.com/bluele/gcache/examples
..\Go\src\github.com\bluele\gcache\examples\custom_expiration.go:9:6: main redeclared in this block
previous declaration at ..\Go\src\github.com\bluele\gcache\examples\autoloading_cache.go:8:6
..\Go\src\github.com\bluele\gcache\examples\example.go:8:6: main redeclared in this block
previous declaration at ..\Go\src\github.com\bluele\gcache\examples\custom_expiration.go:9:6
Hi! Would it be possible to add a method to change the cache size after it's created?
Thanks!
I see there is a stats.go file with a (private) statsAccessor
interface, but I don't see any way to access these stats in the API? Is this just incomplete work?
Line 123 in ecee3be
The ARC does not work if keys expire. I haven't looked into the implementation, but here's how to trigger the bug:
cache := gcache.New(1000).ARC().Expiration(0).Build()
cache.Set("foo", "bar")
cache.Get("foo")
cache.Set("foo", "bar")
I'll also file a pull request that adds this as a test.
see title, thank u. @bluele
Currently, the cache doesn't evict an object when the expiration of that object passes but rather waits until the next Get()
call before evicting it. This is problematic when the object in the cache has connections/goroutines/etc. that should be closed when not in use. I propose restructuring the expiration code such that it evicts the object upon expiration rather than waiting for a subsequent Get()
call.
I want to use this package to ARC cache for some massive read/write app but value in my case is big > 4M does it possible to store values in files and keys in memory?
First, thanks for the contributors to provide expirable cache on LRU/LFU/ARC.
Here's an issue I encounter while using ARC cache:
After items in ARC cache being all expired (confirmed that Get() cannot get any value), Len() still returns the length as if items weren't expired.
Same as GetAll(), it returns a map containing items that are supposed to be all expired.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.