Giter VIP home page Giter VIP logo

gcache's Introduction

GCache

Test GoDoc

Cache library for golang. It supports expirable Cache, LFU, LRU and ARC.

Features

  • Supports expirable Cache, LFU, LRU and ARC.

  • Goroutine safe.

  • Supports event handlers which evict, purge, and add entry. (Optional)

  • Automatically load cache if it doesn't exists. (Optional)

Install

$ go get github.com/bluele/gcache

Example

Manually set a key-value pair.

package main

import (
  "github.com/bluele/gcache"
  "fmt"
)

func main() {
  gc := gcache.New(20).
    LRU().
    Build()
  gc.Set("key", "ok")
  value, err := gc.Get("key")
  if err != nil {
    panic(err)
  }
  fmt.Println("Get:", value)
}
Get: ok

Manually set a key-value pair, with an expiration time.

package main

import (
  "github.com/bluele/gcache"
  "fmt"
  "time"
)

func main() {
  gc := gcache.New(20).
    LRU().
    Build()
  gc.SetWithExpire("key", "ok", time.Second*10)
  value, _ := gc.Get("key")
  fmt.Println("Get:", value)

  // Wait for value to expire
  time.Sleep(time.Second*10)

  value, err := gc.Get("key")
  if err != nil {
    panic(err)
  }
  fmt.Println("Get:", value)
}
Get: ok
// 10 seconds later, new attempt:
panic: ErrKeyNotFound

Automatically load value

package main

import (
  "github.com/bluele/gcache"
  "fmt"
)

func main() {
  gc := gcache.New(20).
    LRU().
    LoaderFunc(func(key interface{}) (interface{}, error) {
      return "ok", nil
    }).
    Build()
  value, err := gc.Get("key")
  if err != nil {
    panic(err)
  }
  fmt.Println("Get:", value)
}
Get: ok

Automatically load value with expiration

package main

import (
  "fmt"
  "time"

  "github.com/bluele/gcache"
)

func main() {
  var evictCounter, loaderCounter, purgeCounter int
  gc := gcache.New(20).
    LRU().
    LoaderExpireFunc(func(key interface{}) (interface{}, *time.Duration, error) {
      loaderCounter++
      expire := 1 * time.Second
      return "ok", &expire, nil
    }).
    EvictedFunc(func(key, value interface{}) {
      evictCounter++
      fmt.Println("evicted key:", key)
    }).
    PurgeVisitorFunc(func(key, value interface{}) {
      purgeCounter++
      fmt.Println("purged key:", key)
    }).
    Build()
  value, err := gc.Get("key")
  if err != nil {
    panic(err)
  }
  fmt.Println("Get:", value)
  time.Sleep(1 * time.Second)
  value, err = gc.Get("key")
  if err != nil {
    panic(err)
  }
  fmt.Println("Get:", value)
  gc.Purge()
  if loaderCounter != evictCounter+purgeCounter {
    panic("bad")
  }
}
Get: ok
evicted key: key
Get: ok
purged key: key

Cache Algorithm

  • Least-Frequently Used (LFU)

Discards the least frequently used items first.

func main() {
  // size: 10
  gc := gcache.New(10).
    LFU().
    Build()
  gc.Set("key", "value")
}
  • Least Recently Used (LRU)

Discards the least recently used items first.

func main() {
  // size: 10
  gc := gcache.New(10).
    LRU().
    Build()
  gc.Set("key", "value")
}
  • Adaptive Replacement Cache (ARC)

Constantly balances between LRU and LFU, to improve the combined result.

detail: http://en.wikipedia.org/wiki/Adaptive_replacement_cache

func main() {
  // size: 10
  gc := gcache.New(10).
    ARC().
    Build()
  gc.Set("key", "value")
}
  • SimpleCache (Default)

SimpleCache has no clear priority for evict cache. It depends on key-value map order.

func main() {
  // size: 10
  gc := gcache.New(10).Build()
  gc.Set("key", "value")
  v, err := gc.Get("key")
  if err != nil {
    panic(err)
  }
}

Loading Cache

If specified LoaderFunc, values are automatically loaded by the cache, and are stored in the cache until either evicted or manually invalidated.

func main() {
  gc := gcache.New(10).
    LRU().
    LoaderFunc(func(key interface{}) (interface{}, error) {
      return "value", nil
    }).
    Build()
  v, _ := gc.Get("key")
  // output: "value"
  fmt.Println(v)
}

GCache coordinates cache fills such that only one load in one process of an entire replicated set of processes populates the cache, then multiplexes the loaded value to all callers.

Expirable cache

func main() {
  // LRU cache, size: 10, expiration: after a hour
  gc := gcache.New(10).
    LRU().
    Expiration(time.Hour).
    Build()
}

Event handlers

Evicted handler

Event handler for evict the entry.

func main() {
  gc := gcache.New(2).
    EvictedFunc(func(key, value interface{}) {
      fmt.Println("evicted key:", key)
    }).
    Build()
  for i := 0; i < 3; i++ {
    gc.Set(i, i*i)
  }
}
evicted key: 0

Added handler

Event handler for add the entry.

func main() {
  gc := gcache.New(2).
    AddedFunc(func(key, value interface{}) {
      fmt.Println("added key:", key)
    }).
    Build()
  for i := 0; i < 3; i++ {
    gc.Set(i, i*i)
  }
}
added key: 0
added key: 1
added key: 2

Author

Jun Kimura

gcache's People

Contributors

aaronwinter avatar anpryl avatar bluele avatar codelingobot avatar maemual avatar pcman312 avatar sean- avatar sebastien-rosset avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

gcache's Issues

Feature Request: PurgeExpire()

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.

Put item to the front of access time tracking list when getting in LRU

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.

Access to stats?

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?

ARC.Len() and ARC.GetAll() returns expired item/count

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.

example have some wrong

Manually set a key-value pair, with an expiration time.

value, err = gc.Get("key")

should be

value, err := gc.Get("key")

LoaderFunc define expiry?

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?

Support context?

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.

size based expiry?

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.

Expirable entries

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?

Batch operations are very common. Do you consider supporting batch read and batch load interfaces?

`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

Size unit

Sir, what is the unit of size?
c.items = make(map[interface{}]*lfuItem, c.size+1)

ARC cache does not work as expected (when used with expiry)

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.

Feature Request: Eviction of an object happens immediately upon expiration

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.

ARC Get panicks

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

Redundant "addedFunc" in case "LoaderFunc" call

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?

Panic when removing item from ARC cache

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

examples causing redefine main function error with `go get`

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

Panics should never happen in a library

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:

panic("gcache: size <= 0")

gcache/cache.go

Line 163 in bbe6d2a

panic("gcache: Unknown type " + cb.tp)

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.

Bug in ARC cache

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.

Project Status

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!

how to share between multiple processes?

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?

Feature Request: Allowing for unbounded cache size

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.

Memory Leak in LFU Cache Implementation

Description

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.

Reproducing

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)
		}
	}
}

Evidence

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.

Increment operator

It would be great that instead of a Get+Set that there was an Increment operator, ideally goroutine safe.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.