cache

README

Cache

Thread safety and LRU eviction are two basic things we wanted from a cache system. As we require an open-source solution – HashiCorp’s golang-lru looked like a good fit. It’s an open source cache library which implements a fixed-size thread-safe LRU cache.

We mapped following concerns we wanted to address, building on top of golang-lru:

1. Concurrent misses (i.e. “Thundering Herd”)

   If we miss the cache we must hit the database

   Since we know many concurrent requests will likely be made by the same user, this means a cache miss will trigger many concurrent DB round-trips, adversely affecting our overall tail latency.

   We wanted to reduce the load on the database in this case, so we implemented a locking mechanism where for a given key, only one Goroutine will acquire the data from the database while the rest will simply block and wait for that request to return and populate the cache.

2. Eviction time

   If a user suddenly generates high load on the system, we don’t want a fixed expiry duration since all servers are likely to evict that user at the same time, which will in turn cause a spike in DB reads (see “thundering herd” above).

Risks we mapped and considered as a non-issue for our usage:

1. When DB lookup fails or returns a Not Found Error, we do not set any state into the cache, which will make the rest of the routines report that the item was not found.
2. Cache thrashing: If the LRU cache is too small, there’s a race condition here: it is possible to successfully add a key to the cache that will be immediately evicted, causing the subsequent lookup to fail.

Features

• Thread safe
• LRU eviction
• Eviction time

Usage

see cache test-case

func TestCatalogService_Cache(t *testing.T) {
	log.Info().Msg("called TestCatalogService_Cache")
	catSrv := NewCatalogService(ServiceCache{Enabled: true, Size: 5})
	gotProduct, err := catSrv.GetProductByID("abc")
	gotProduct2, err2 := catSrv.GetProductByID("abc")

	assert.NoError(t, err)
	assert.NoError(t, err2)
	assert.Equal(t, "abc", gotProduct.id)
	assert.Equal(t, gotProduct, gotProduct2)
}

Reference

• In-process caching in Go: scaling lakeFS to 100k requests/second
• sync.Map
• lakeFS's cache

Documentation

Index

• Variables
• type Cache
• type ChanLocker
  • func NewChanLocker() *ChanLocker
  • func (c ChanLocker) Lock(v interface{}, onAcquireFn func()) (acquired bool)
• type GetSetCache
  • func NewCache(size int) *GetSetCache
  • func (c *GetSetCache) GetOrSet(k interface{}, setFn SetFn) (v interface{}, err error)
• type Locker
• type SetFn

Variables

var (
	ErrCacheItemNotFound = errors.New("cache item not found")
)

Types

type Cache

type Cache interface {
	GetOrSet(k interface{}, setFn SetFn) (v interface{}, err error)
}

type ChanLocker

type ChanLocker struct {
	// contains filtered or unexported fields
}

func NewChanLocker

func NewChanLocker() *ChanLocker

func (ChanLocker) Lock

func (c ChanLocker) Lock(v interface{}, onAcquireFn func()) (acquired bool)

type GetSetCache

type GetSetCache struct {
	// contains filtered or unexported fields
}

func NewCache

func NewCache(size int) *GetSetCache

func (*GetSetCache) GetOrSet

func (c *GetSetCache) GetOrSet(k interface{}, setFn SetFn) (v interface{}, err error)

type Locker

type Locker interface {
	Lock(v interface{}, onAcquireFn func())
}

type SetFn

type SetFn func() (v interface{}, err error)