gw_cache

README

A cache for API gateways

• A cache for API gateways
  • Installation
  • Declaration
  • Usage
    • Example
  • Notes on its implementation
    • Parameters selection
    • Liveness danger
    • Possible performance issue with internal hash Table
    • Possible problem with ttl

Gateway_cache implements a simple cache from HTTP requests to their responses. An essential quality is that the cache can receive repeated requests before computing the first one. In such a case, the repeated requests will wait without contention for other different requests until the response is ready.

Once the response is ready, the runtime will free the retained repeated requests, and the flow will continue in a usual way.

Installation

 go get -U github.com/geniussportsgroup/gateway_cache

Declaration

The user can use the cache from any GO HTTP middleware.

To use it, declare something like that:

var cache *Cache.CacheDriver = Cache.New[T,K](cacheCapacity, capFactor, cacheTTL,mapper)

• T: This is the request type. This type will be receive to execute the request.
• K: The response type. This type will be the type that the request will response.
• cacheCapacity: The maximum number of entries that the cache can store. Once this limit reaches and one wants to insert a new entry, the runtime selects the LRU entry for eviction.
• capFactor: A multiplicative factor for increasing the physical size of the internal hash table. Using a physical size larger than the logical size reduces the possibility of an undesired table resizing when a new request arrives.
• cacheTTL: A soft duration time for the cache entry. By soft, we mean that the duration does not avoid eviction.
• processor: Is an interface with this contract

type ProcessorI[T, K any] interface {
	ToMapKey(T) (string, error)
	CacheMissSolver(T) (K, *models.RequestError) 
}

• T and K: Are the same defined in cache's creation

• ToMapKey is a function used for transforming the request to a string. This function is used for mapping request to cache entries, which at the end contain the response.

• CacheMissSolver: this is the core function in charge of calling the microservices, gathering the request, assembly them in an HTPP response, and eventually compressing it. The result is store in the cache entry.

Usage

In your request handler, you should put a line like this one:

    gzipResponse, predictError := cache.RetrieveFromCacheOrCompute(request)  

The first result is the request itself already prepared by the CacheMissSolver function. The second result is an error indication. If its value is not nil, then the first parameter is nil.

If it is the first request, then the flow blocks, but the process coded in CacheMissSolver is triggered. The following repeated requests before to get the result block too, but they do not cause contention on other requests that are not related to the original one.

Once the result is gotten (by CacheMissSolver function), all the retained requests are unblocked, and the flow continues as usual.

If the result is already in the cache, then the cache retrieves the result, return it, and the flow continues in a usual way without blocking.

Example

Here is an complete example

Notes on its implementation

Parameters selection

The most important thing to know is the maximum number of simultaneous request that a gateway could receive. Once this number is known, the cache recommended cache capacity should be at least 30 % larger. The larger the capacity is, the more performant the cache should be.

Liveness danger

The cache could start to reject requests if it receives more different requests in a short time than its capacity.

Possible performance issue with internal hash Table

Internally, the cache handles a GO map from a string version of a request to a cache entry containing control information and the request and its response. The GO maps are implemented through a hash table that eventually could require a resize when the load factor becomes high (about 80 % of occupation). A new request arrival could cause, since this the only moment when caching insertions occur. Consequently, this could slow down the response time. The proper way for avoiding this event is to ensure that the table size is always enough. That implies that the size should always be greater than the number of inserted entries. This is the reason for the capFactor parameter received by the constructor.

We advise using a capFactor of at least 0.5 or more.

Possible problem with ttl

If, within a short interval of time shorter than the TTL, several different keys are added, exceeding the cache's capacity, it will cause the removal of keys that are still available, even if their TTL has not expired. This is because the cache will replace them with the new keys. Avoiding this situation is the responsibility of the client, who should choose the appropriate TTL based on the number of requests that the application expects to receive.

Documentation

Overview

This is an implementation of a cache system for the Go language.

It allows you to cache any type of data, as long as it is serializable.

It is based on the idea of a processor, which is the one that will be in charge of generating the key and solving the cache miss. also uses a map under the hood to store the data, it is recommended give a cap factor big enough to avoid resize.

Here is an example of the usage of this package to implement a cache that will use an int as a key and a string as a value:

package main

import (

	"fmt"
	"time"

	gw_cache "github.com/geniussportsgroup/gateway_cache"
	"github.com/geniussportsgroup/gateway_cache/models"

)

type Processor struct {}

// receive the key defined as int and return a string
func (p *Processor) ToMapKey(someValue int) (string, error) {
	return fmt.Sprint(someValue), nil
}

// receive the value that will be used as a key and return a string, that will be used as a value
func (p *Processor) CacheMissSolver(someValue int) (string, *models.RequestError) {
	return fmt.Sprintf("%d processed", someValue), nil
}

func main() {
	//create the cache
	capacity := 10
	capFactor := 0.6
	ttl := time.Minute * 5
	p := &Processor{}

	cache := gw_cache.New[int, string](
		capacity,
		capFactor,
		ttl,
		p,
	)

	//compute and set the value
	value, err := cache.RetrieveFromCacheOrCompute(3)
	fmt.Println(value, err) // 3 processed <nil>
}

The above example is present in the main folder of this repository.

Index

• Constants
• Variables
• type CacheDriver
  • func New[K any, T any](capacity int, capFactor float64, ttl time.Duration, ...) *CacheDriver[K, T]
  • func NewWithCompression[T any, K any](capacity int, capFactor float64, ttl time.Duration, ...) (cache *CacheDriver[T, K])
  • func (cache *CacheDriver[T, K]) Capacity() int
  • func (cache *CacheDriver[T, K]) Clean() error
  • func (cache *CacheDriver[T, K]) Contains(keyVal T) (bool, error)
  • func (cache *CacheDriver[T, K]) ExtendedCapacity() int
  • func (cache *CacheDriver[T, K]) GetState() (string, error)
  • func (cache *CacheDriver[T, K]) HitCount() int
  • func (cache *CacheDriver[T, K]) LazyRemove(keyVal T) error
  • func (cache *CacheDriver[T, K]) MissCount() int
  • func (cache *CacheDriver[T, K]) NewCacheIt() *CacheIt[T, K]
  • func (cache *CacheDriver[T, K]) NumEntries() int
  • func (cache *CacheDriver[T, K]) RetrieveFromCacheOrCompute(request T, other ...interface{}) (K, *models.RequestError)
  • func (cache *CacheDriver[T, K]) RetrieveValue(keyVal T) (K, error)
  • func (cache *CacheDriver[T, K]) Set(capacity int, ttl time.Duration, ttlForNegative time.Duration) error
  • func (cache *CacheDriver[T, K]) SetReporter(reporter Reporter)
  • func (cache *CacheDriver[T, K]) StoreOrUpdate(keyVal T, newValue K) error
  • func (cache *CacheDriver[T, K]) TTLForNegative() time.Duration
  • func (cache *CacheDriver[T, K]) Touch(keyVal T) error
  • func (cache *CacheDriver[T, K]) Ttl() time.Duration
• type CacheEntry
• type CacheIt
  • func (it *CacheIt[T, K]) GetCurr() *CacheEntry[K]
  • func (it *CacheIt[T, K]) HasCurr() bool
  • func (it *CacheIt[T, K]) Next() *CacheEntry[K]
• type CacheState
• type CompressorI
• type DefaultTransformer
  • func (_ *DefaultTransformer[T]) BytesToValue(in []byte) (T, error)
  • func (_ *DefaultTransformer[T]) ValueToBytes(in T) ([]byte, error)
• type Options
• type ProcessorI
• type Reporter
• type TransformerI

Constants

const (
	AVAILABLE models.EntryState = iota
	COMPUTING
	COMPUTED
	FAILED5xx
	FAILED4xx
	FAILED5XXMISSHANDLERERROR
)

State that a cache entry could have

const (
	Status4xx models.CodeStatus = iota
	Status4xxCached
	Status5xx
	Status5xxCached
	StatusUser
)

Variables

var (
	ErrCantCastOutput                 = errors.New("can't cast output to desired type")
	ErrEntryExpired                   = errors.New("entry expired")
	ErrEntryAvailableState            = errors.New("entry is in available state")
	ErrEntryComputingState            = errors.New("entry is in computing state")
	ErrLRUComputing                   = errors.New("LRU entry is in COMPUTING state. This could be a bug or a cache misconfiguration")
	ErrNumOfEntriesBiggerThanCapacity = errors.New("number of entries in the cache is greater than given capacity")
)

Types

type CacheDriver

type CacheDriver[K any, T any] struct {
	// contains filtered or unexported fields
}

CacheDriver The cache itself.

K represents the request's type this will be used as key.

T the response's type this will be used as value.

func New

func New[K any, T any](
	capacity int,
	capFactor float64,
	ttl time.Duration,
	ttlForNegative time.Duration,
	processor ProcessorI[K, T],
	options ...Options[K, T],
) *CacheDriver[K, T]

func NewWithCompression

func NewWithCompression[T any, K any](
	capacity int,
	capFactor float64,
	ttl time.Duration,
	ttlForNegative time.Duration,
	processor ProcessorI[T, K],
	compressor TransformerI[K],
	options ...Options[T, K],
) (cache *CacheDriver[T, K])

NewWithCompression Creates a new cache with compressed entries.

The constructor is some similar to the version that does not compress. The difference is that in order to compress, the cache needs a serialized representation of what will be stored into the cache. For that reason, the constructor receives two additional functions. The first function, ValueToBytes transforms the value into a byte slice (type []byte). The second function, bytesToValue, takes a serialized representation of the value stored into the cache, and it transforms it to the original representation.

The parameters are:

capacity: maximum number of entries that cache can manage without evicting the least recently used

capFactor is a number in (0.1, 3] that indicates how long the cache should be oversize in order to avoid rehashing

ttl: time to live of a cache entry

processor: is an interface that must be implemented by the user. It is in charge of transforming the request into a string and get the value in case that does not exist in the cache

type ProcessorI[K any, T any] interface {
	ToMapKey(keyVal T) (string, error) //Is the function in charge of transforming the request into a string
	CacheMissSolver(K) (T, *models.RequestError)  //Is the function in charge of getting the value in case that does not exist in the cache
}

transformer: is an interface that must be implemented by the user. It is in charge of transforming the value into a byte slice and vice versa

type Transformer[T any] interface {
	ValueToBytes(T) ([]byte, error)
	BytesToValue([]byte) (T, error)
}

it is a default implementation of the transformer interface that you can use

type DefaultTransformer[T any] struct{}

func (_ *DefaultTransformer[T]) BytesToValue(in []byte) (T, error) {
	var out T
	err := json.Unmarshal(in, &out)
	if err != nil {
		return out, err
	}
	return out, nil
}

func (_ *DefaultTransformer[T]) ValueToBytes(in T) ([]byte, error) {
		return json.Marshal(in)
	}

func (*CacheDriver[T, K]) Capacity

func (cache *CacheDriver[T, K]) Capacity() int

func (*CacheDriver[T, K]) Clean

func (cache *CacheDriver[T, K]) Clean() error

Clean Try to clean the cache. All the entries are deleted and counters reset. Fails if any entry is in COMPUTING state.

Uses internal lock

func (*CacheDriver[T, K]) Contains

func (cache *CacheDriver[T, K]) Contains(keyVal T) (bool, error)

Contains returns true if the key is in the cache

func (*CacheDriver[T, K]) ExtendedCapacity

func (cache *CacheDriver[T, K]) ExtendedCapacity() int

func (*CacheDriver[T, K]) GetState

func (cache *CacheDriver[T, K]) GetState() (string, error)

GetState Return a json containing the cache state. Use the internal mutex. Be careful with a deadlock

func (*CacheDriver[T, K]) HitCount

func (cache *CacheDriver[T, K]) HitCount() int

func (*CacheDriver[T, K]) LazyRemove

func (cache *CacheDriver[T, K]) LazyRemove(keyVal T) error

LazyRemove removes the entry with keyVal from the cache. It does not remove the entry immediately, but it marks it as removed.

func (*CacheDriver[T, K]) MissCount

func (cache *CacheDriver[T, K]) MissCount() int

func (*CacheDriver[T, K]) NewCacheIt

func (cache *CacheDriver[T, K]) NewCacheIt() *CacheIt[T, K]

func (*CacheDriver[T, K]) NumEntries

func (cache *CacheDriver[T, K]) NumEntries() int

func (*CacheDriver[T, K]) RetrieveFromCacheOrCompute

func (cache *CacheDriver[T, K]) RetrieveFromCacheOrCompute(request T,
	other ...interface{}) (K, *models.RequestError)

RetrieveFromCacheOrCompute Search Request in the cache. If the request is already computed, then it immediately returns the cached entry. If the request is the first, then it blocks until the result is ready. If the request is not the first but the result is not still ready, then it blocks until the result is ready

func (*CacheDriver[T, K]) RetrieveValue

func (cache *CacheDriver[T, K]) RetrieveValue(keyVal T) (K, error)

func (*CacheDriver[T, K]) Set

func (cache *CacheDriver[T, K]) Set(capacity int, ttl time.Duration, ttlForNegative time.Duration) error

func (*CacheDriver[T, K]) SetReporter

func (cache *CacheDriver[T, K]) SetReporter(reporter Reporter)

func (*CacheDriver[T, K]) StoreOrUpdate

func (cache *CacheDriver[T, K]) StoreOrUpdate(keyVal T, newValue K) error

testing Add other in retrieve from cache or compute

func (*CacheDriver[T, K]) TTLForNegative

func (cache *CacheDriver[T, K]) TTLForNegative() time.Duration

func (*CacheDriver[T, K]) Touch

func (cache *CacheDriver[T, K]) Touch(keyVal T) error

func (*CacheDriver[T, K]) Ttl

func (cache *CacheDriver[T, K]) Ttl() time.Duration

type CacheEntry

type CacheEntry[K any] struct {
	// contains filtered or unexported fields
}

CacheEntry Every cache entry has this information

type CacheIt

type CacheIt[T any, K any] struct {
	// contains filtered or unexported fields
}

CacheIt Iterator on cache entries. Go from MUR to LRU

func (*CacheIt[T, K]) GetCurr

func (it *CacheIt[T, K]) GetCurr() *CacheEntry[K]

func (*CacheIt[T, K]) HasCurr

func (it *CacheIt[T, K]) HasCurr() bool

func (*CacheIt[T, K]) Next

func (it *CacheIt[T, K]) Next() *CacheEntry[K]

type CacheState

type CacheState struct {
	MissCount      int
	HitCount       int
	TTL            time.Duration
	TTLForNegative time.Duration
	Capacity       int
	NumEntries     int
}

type CompressorI

type CompressorI interface {
	Compress([]byte) ([]byte, error)
	Decompress([]byte) ([]byte, error)
}

CompressorI is the interface that wraps the basic Compress and Decompress methods.

Compress is used to compress the input

Decompress is used to decompress the input

type DefaultTransformer

type DefaultTransformer[T any] struct{}

func (*DefaultTransformer[T]) BytesToValue

func (_ *DefaultTransformer[T]) BytesToValue(in []byte) (T, error)

func (*DefaultTransformer[T]) ValueToBytes

func (_ *DefaultTransformer[T]) ValueToBytes(in T) ([]byte, error)

type Options

type Options[K, T any] func(*CacheDriver[K, T])

type ProcessorI

type ProcessorI[K, T any] interface {
	ToMapKey(K) (string, error)
	CacheMissSolver(K, ...interface{}) (T, *models.RequestError) //we will leave the pre process logic for this function
}

ProcessorI is the interface used to map the key and get the value in case it is missing.

ToMapKey: is used to convert the input to a string key

CacheMissSolver: is used to call the upstream services

K represents the input's type to get a value, this will be used as a key T represents the value's type itself, this will be used as a value

type Reporter

type Reporter interface {
	ReportMiss()
	ReportHit()
}

Reporter is the interface that wraps the basic ReportMiss and ReportHit methods

ReportMiss is used to report a cache miss

ReportHit is used to report a cache hit

type TransformerI

type TransformerI[T any] interface {
	BytesToValue([]byte) (T, error)
	ValueToBytes(T) ([]byte, error)
}

TransformerI is the interface that wraps the basic BytesToValue and ValueToBytes methods.

BytesToValue is used to convert the input to a value

ValueToBytes is used to convert the value to a byte array

T represents the value's type