Giter VIP home page Giter VIP logo

go-generics-cache's Introduction

go-generics-cache

.github/workflows/test.yml codecov Go Reference

go-generics-cache is an in-memory key:value store/cache that is suitable for applications running on a single machine. This in-memory cache uses Go Generics which is introduced in 1.18.

  • a thread-safe
  • implemented with Go Generics
  • TTL supported (with expiration times)
  • Simple cache is like map[string]interface{}
  • Cache replacement policies
    • Least recently used (LRU)
      • Discards the least recently used items first.
      • See examples
    • Least-frequently used (LFU)
    • First in first out (FIFO)
      • Using this algorithm the cache behaves in the same way as a FIFO queue.
      • The cache evicts the blocks in the order they were added, without any regard to how often or how many times they were accessed before.
      • See examples
    • Most recently used (MRU)
      • In contrast to Least Recently Used (LRU), MRU discards the most recently used items first.
      • See examples
    • Clock
      • Clock is a more efficient version of FIFO than Second-chance cache algorithm.
      • See examples

Requirements

Go 1.18 or later.

Install

$ go get github.com/Code-Hex/go-generics-cache

Usage

See also examples or go playground

package main

import (
	"context"
	"fmt"
	"time"

	cache "github.com/Code-Hex/go-generics-cache"
)

func main() {
	ctx, cancel := context.WithCancel(context.Background())
	defer cancel()

	// use simple cache algorithm without options.
	c := cache.NewContext[string, int](ctx)
	c.Set("a", 1)
	gota, aok := c.Get("a")
	gotb, bok := c.Get("b")
	fmt.Println(gota, aok) // 1 true
	fmt.Println(gotb, bok) // 0 false

	// Create a cache for Number constraint. key as string, value as int.
	nc := cache.NewNumber[string, int]()
	nc.Set("age", 26, cache.WithExpiration(time.Hour))

	incremented := nc.Increment("age", 1)
	fmt.Println(incremented) // 27

	decremented := nc.Decrement("age", 1)
	fmt.Println(decremented) // 26
}

Articles

go-generics-cache's People

Contributors

chenyanchen avatar code-hex avatar hidetatz avatar mingcheng avatar moredure avatar thejerf avatar trrrrrys 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

go-generics-cache's Issues

Improved performance/memory usage for items with an expiry

Hi! Thanks for a good cache library that provides generics – it's really handy.

I've used this a bit for certain things, and found out that adding an expiry to items adds a new goroutine:

go-generics-cache/cache.go

Lines 170 to 180 in a0612be

func (c *Cache[K, V]) installExpirationWatcher(key K, exp time.Duration) {
done := make(chan struct{})
c.expirations[key] = done
go func() {
select {
case <-time.After(exp):
c.Delete(key)
case <-done:
}
}()
}

A lot of goroutines is pretty expensive, both in terms of switching and in terms of memory usage (each is 2kb in size).

Would you be open to a PR for a more performant implementation? github.com/patrickmn/go-cache uses a janitor, and I suppose this library could implement something like that -- falling back to the current behaviour if a cleanup interval isn't provided.

Panic when deleting expired items

Related codes

cacheStore := cache.New(cache.AsLFU[string, SomeStruct](lfu.WithCapacity(5)))
cacheStore.Set(someKey, someValue, cache.WithExpiration(10 * time.Second))

Logs

panic: runtime error: index out of range [-1]

goroutine 71 [running]:
github.com/Code-Hex/go-generics-cache/policy/lfu.priorityQueue[...].Swap(...)
        github.com/Code-Hex/[email protected]/policy/lfu/priotiry_queue.go:51
container/heap.Remove({0x1e0c8c0, 0xc0006982b8}, 0xffffffffffffffff)
        container/heap/heap.go:72 +0x53
github.com/Code-Hex/go-generics-cache/policy/lfu.(*Cache[...]).Delete(0xc0006982d0, {0xc000322181, 0xbf})
        github.com/Code-Hex/[email protected]/policy/lfu/lfu.go:92 +0x65
github.com/Code-Hex/go-generics-cache.(*Cache[...]).DeleteExpired(0xc0002c2a20)
        github.com/Code-Hex/[email protected]/cache.go:209 +0x158
github.com/Code-Hex/go-generics-cache.NewContext[...].func1()
        github.com/Code-Hex/[email protected]/cache.go:175 +0x25
github.com/Code-Hex/go-generics-cache.(*janitor).run.func1()
        github.com/Code-Hex/[email protected]/janitor.go:39 +0x122
created by github.com/Code-Hex/go-generics-cache.(*janitor).run
        github.com/Code-Hex/[email protected]/janitor.go:33 +0x72

Panic when delete expired items.

go env
$ go env
GO111MODULE="on"
GOARCH="arm64"
GOBIN=""
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="arm64"
GOHOSTOS="darwin"
GOINSECURE=""
GOOS="darwin"
GOPROXY="https://goproxy.cn,direct"
GOROOT="/opt/homebrew/opt/go/libexec"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/opt/homebrew/opt/go/libexec/pkg/tool/darwin_arm64"
GOVCS=""
GOVERSION="go1.20.4"
GCCGO="gccgo"
AR="ar"
CC="cc"
CXX="c++"
CGO_ENABLED="1"
GOWORK=""
CGO_CFLAGS="-O2 -g"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-O2 -g"
CGO_FFLAGS="-O2 -g"
CGO_LDFLAGS="-O2 -g"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -arch arm64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/91/6ypxbjvs1_3007pts7zflvwh0000gn/T/go-build1223268749=/tmp/go-build -gno-record-gcc-switches -fno-common"
main.go
package main

import (
	"time"

	cache "github.com/Code-Hex/go-generics-cache"
	"github.com/Code-Hex/go-generics-cache/policy/lfu"
)

func main() {
	c := cache.New(
		cache.AsLFU[string, string](lfu.WithCapacity(3)),
		cache.WithJanitorInterval[string, string](time.Second),
	)
	c.Set("key1", "value1", cache.WithExpiration(time.Second))
	c.Set("key2", "value3", cache.WithExpiration(time.Second))
	time.Sleep(time.Minute)
}
go run main.go
$ go run main.go                   
panic: runtime error: index out of range [-1]

goroutine 17 [running]:
github.com/Code-Hex/go-generics-cache/policy/lfu.priorityQueue[...].Swap(...)
        /Users/cyc/go/pkg/mod/github.com/!code-!hex/[email protected]/policy/lfu/priotiry_queue.go:53
container/heap.Remove({0x104545080, 0x140000a6018}, 0xffffffffffffffff)
        /opt/homebrew/opt/go/libexec/src/container/heap/heap.go:71 +0x54
github.com/Code-Hex/go-generics-cache/policy/lfu.(*Cache[...]).Delete(0x1045457e0, {0x1045154ce, 0x4})
        /Users/cyc/go/pkg/mod/github.com/!code-!hex/[email protected]/policy/lfu/lfu.go:95 +0x5c
github.com/Code-Hex/go-generics-cache.(*Cache[...]).DeleteExpired(0x104545660)
        /Users/cyc/go/pkg/mod/github.com/!code-!hex/[email protected]/cache.go:228 +0xf8
github.com/Code-Hex/go-generics-cache.(*janitor).run.func1()
        /Users/cyc/go/pkg/mod/github.com/!code-!hex/[email protected]/janitor.go:39 +0xe8
created by github.com/Code-Hex/go-generics-cache.(*janitor).run
        /Users/cyc/go/pkg/mod/github.com/!code-!hex/[email protected]/janitor.go:33 +0x78
exit status 2

expiration not update

		c.Set("1", 10, WithExpiration(10*time.Minute))  // queue index 0
		c.Set("2", 20, WithExpiration(20*time.Minute))  // queue index 1
		c.Set("1", 11, WithExpiration(100*time.Minute)) // must queue index 0 move to 1, check point
		nowFunc = func() time.Time {
			return now.Add(30 * time.Minute).Add(time.Minute)
		}
		maxItems = c.Len()
		c.DeleteExpired()
		got3 := c.Len()
		want3 := maxItems - 1
		if want3 != got3 {
			t.Errorf("want3 %d items but got3 %d", want3, got3)
		}
func (m *expirationManager[K]) update(key K, expiration time.Time) {
	if e, ok := m.mapping[key]; ok {
		e.expiration = expiration
		heap.Fix(&m.queue, e.index)
	} else {

fatal error: concurrent map read and map write

Problem: fatal error: concurrent map read and map write

Reproduce Code:

func BenchmarkConcurrentSet(b *testing.B) {
	cache := clock.NewCache[string, string]()
	group := sync.WaitGroup{}
	for i := 0; i < b.N; i++ {
		group.Add(1)
		var count int = 1000
		go func() {
			for count > 0 {
				cache.Set("key", "value")
				count--
				if count <= 0 {
					group.Done()
					return
				}
			}
		}()
	}
	group.Wait()
}

Result:
image

Expected: RWLocker for Set/Read.

Maybe change containers/list to implementations on generics

https://github.com/bahlo/generic-list-go - for example this looks very similar to containers/list but without empty interfaces.
I noticed what the library uses containers/list because my program sometimes crashes

panic: interface conversion: interface {} is nil, not *lru.entry[string,*github.com/Code-Hex/go-generics-cache.Item[string,int64]]

goroutine 241845 [running]:
github.com/Code-Hex/go-generics-cache/policy/lru.(*Cache[...]).delete(...)
 /go/pkg/mod/github.com/!code-!hex/[email protected]/policy/lru/lru.go:118
github.com/Code-Hex/go-generics-cache/policy/lru.(*Cache[...]).deleteOldest(0xc000234330?)
 /go/pkg/mod/github.com/!code-!hex/[email protected]/policy/lru/lru.go:113 +0xed
github.com/Code-Hex/go-generics-cache/policy/lru.(*Cache[...]).Set(0xc00023a048, {0xc0061324b0, 0x42}, 0xc007a885a0)
 /go/pkg/mod/github.com/!code-!hex/[email protected]/policy/lru/lru.go:85 +0x339
github.com/Code-Hex/go-generics-cache.(*Cache[...]).Set(0xc0002340f0, {0xc0061324b0, 0x42}, 0x48, {0x0?, 0x0, 0x0})
 /go/pkg/mod/github.com/!code-!hex/[email protected]/cache.go:158 +0x1f3

It also can be problem in logic (maybe some races)

Clock policy: Not show all the page with sequential access pattern

Example test:

cache := clock.NewCache[int, int](clock.WithCapacity(10))
for i := 0; i < 10; i++ {
cache.Set(i, i)
}
cache.Set(10, 10)

if len(cache.Keys()) != 10 {
t.Errorf("want number of keys 10, but got %d, %v", len(cache.Keys()), cache.Keys())
}

When the cache is full, and new page is set, the hand will iterate through all the element in the cache and set referenceCount = 0.
In that case, line 122 of clock.go failed to get the keys that is still in the page (but with ref count == 0).

LFU: Allow setting the frequency and update the heap

I have a dictionary in which I want to keep the 20 most frequent words / queries for example. So I make a LFU cache:

frequency = lfu.NewCache[string, int](lfu.WithCapacity(20))

and then

count, _ := frequency.Get(query)
frequency.Set(query, count+1)

on every query.
So when it exceeds 20, the least frequent query is deleted.
And I can save this to a JSON file as well.
So far so good.

But when I run the program next time and load this JSON file, and set the values, the internal frequency (heap order) is not updated (they are all one) unless I run Get() or Set() the same number of times (or at least N times for the top item, if we have N items), which is very slow.

So if I could run frequency.SetWithCount(key, value, count) for example, that is just like

for i:=0; i<count; i++ {
    frequency.Set(key, value)
}

But much faster.
That would solve the problem.

Len() method missing from common cache interface

It would be useful to have Len() method available in common interface. I would need it for getting metrics for cache usage.

It is available if the cache is created with exact policy lru.NewCache()but if you want to use context cache.NewContext() then common interface is returned. len(c.Keys())could be used but it's still not the same.

Example:

ctx := context.Background()
var myCache *cache.Cache[string, int]
myCache = cache.NewContext(ctx, cache.AsLRU[string, int](lru.WithCapacity(10)))
// myCache is LRU cache but myCache.Len() is not available

Nil panic in janitor

After updating dependencies in a project and moving from go-generic-cache 1.1.0 to 1.3.1, I had the pipeline failing with the following nil panic:

panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x1 addr=0x0 pc=0x102dffd]

goroutine 375 [running]:
github.com/Code-Hex/go-generics-cache/policy/simple.(*Cache[...]).Keys.func1(0x3)
	/home/vsts/agents/3.236.1/go/pkg/mod/github.com/!code-!hex/[email protected]/policy/simple/simple.go:53 +0x15d
sort.order2_func(...)
	/opt/hostedtoolcache/go/1.22.1/x64/src/sort/zsortfunc.go:299
sort.median_func({0xc00007bd08?, 0xc00038b290?}, 0x3, 0x6, 0x9, 0xc00007bb50)
	/opt/hostedtoolcache/go/1.22.1/x64/src/sort/zsortfunc.go:308 +0x53
sort.choosePivot_func({0xc00007bd08?, 0xc00038b290?}, 0x0, 0xf)
	/opt/hostedtoolcache/go/1.22.1/x64/src/sort/zsortfunc.go:284 +0x190
sort.pdqsort_func({0xc00007bd08?, 0xc00038b290?}, 0x0, 0xf, 0x4)
	/opt/hostedtoolcache/go/1.22.1/x64/src/sort/zsortfunc.go:89 +0x148
sort.Slice({0x15a36e0, 0xc0024d9878}, 0xc00007bd08)
	/opt/hostedtoolcache/go/1.22.1/x64/src/sort/slice.go:29 +0xab
github.com/Code-Hex/go-generics-cache/policy/simple.(*Cache[...]).Keys(0x19a8e60)
	/home/vsts/agents/3.236.1/go/pkg/mod/github.com/!code-!hex/[email protected]/policy/simple/simple.go:50 +0x3a5
github.com/Code-Hex/go-generics-cache.(*Cache[...]).DeleteExpired(0x19a99e0)
	/home/vsts/agents/3.236.1/go/pkg/mod/github.com/!code-!hex/[email protected]/cache.go:220 +0x6c
github.com/Code-Hex/go-generics-cache.(*janitor).run.func1()
	/home/vsts/agents/3.236.1/go/pkg/mod/github.com/!code-!hex/[email protected]/janitor.go:39 +0x202
created by github.com/Code-Hex/go-generics-cache.(*janitor).run in goroutine 1
	/home/vsts/agents/3.236.1/go/pkg/mod/github.com/!code-!hex/[email protected]/janitor.go:33 +0xd1

This is the code that uses the cache:

	lastHeard, found := c.lastHeardCache.Get(key)
	if found {
		return lastHeard, nil
	}
	lastHeard, err := c.getLastHeard(ctx, key)
	if err != nil {
		return 0, err
	}
	c.lastHeardCache.Set(key, lastHeard, cache.WithExpiration(c.cacheTTL))

With the cache being initialized without any option: cache.New[lastHeardKey, int64]()

I was also able to reproduce the error with 1.2.0.

The issue does not appear when running my tests locally, only in a pipeline. They use concurrency quite a lot and are significantly slower in the pipeline, possibly explaining why the error does not occur locally. From what I could find in the code, it seems a key has been deleted in the middle of a call to sort, which makes the sort func panic. I can't figure out though why this happens as everything seems protected by a mutex in cache.go.

LFU Delete/pop key take a long time

func TestLFUPop(t *testing.T) {
	const maxKeySize = 10000000
	c := New[int, int](AsLFU[int, int](lfu.WithCapacity(maxKeySize)))
	take := time.Now()
	for i := 0; i < maxKeySize; i++ {
		c.Set(i, i)
	}
	t.Log(time.Since(take))

	take = time.Now()
	for i := 0; i < 300; i++ {
		c.Delete(i * 2)
	}
	t.Log(time.Since(take))
}
=== RUN   TestLFUPop
    cache_internal_test.go:366: 7.5215588s
    cache_internal_test.go:372: 11.4654817s   // delete 300 count key...used 11sec

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.