ttlcache

README

ttlcache

ttlcache is a distributed cache heavily influenced by groupcache. The primary difference is ttlcache supports providing a TTL when loading a value, and will lazily refetch values when their TTL expires. It was created to avoid thundering herds when a key's value is not yet known. An early incarnation involved an embargo period on failed loads, however it turned out to be both more useful and easier to implement to have a generic TTL on every key, and return a special value to indicate a lack thereof. All the usual groupcache conveniences are maintained.

• Per-key time-to-lives, specified when the value is provided.
• Only memberlist is supported for cluster membership.
• All keys are string, and all values are []byte. We assume values are only useful in their entirety.
• Native Prometheus metrics following conventions.
• Dynamic reloading of the key retriever, peer loader, and TTL override list.

Motivation

groupcache is excellent if we can guarantee that only keys that exist are requested. This is enforceable for dl.google.com, however we wanted to be able to handle keys that gradually come into existence over time. ttlcache assumes it is just as expensive to find out whether a value exists as it is to retrieve it. It avoids thundering herds both when the key exists, but also when we are sure it does not (as opposed to a load error). The only option in this situation with groupcache is to return an error, which causes a thundering herd of retries.

Documentation

Overview

Package ttlcache implements a distributed cache with support for TTLs.

Index

• type Base
  • func NewBase(opts *BaseOpts) *Base
  • func (b *Base) Configure(opts *ConfigureOpts) *Cache
• type BaseOpts
• type Cache
  • func (c *Cache) Get(ctx context.Context, key string) ([]byte, lifetime.Lifetime, error)
• type ConfigureOpts
• type OriginLoader
• type OriginLoaderFunc
  • func (f OriginLoaderFunc) Load(ctx context.Context, key string) ([]byte, lifetime.Lifetime, error)
• type PeerLoader
• type PeerLoaderFunc
  • func (f PeerLoaderFunc) Load(ctx context.Context, from *memberlist.Node, cache *Cache, key string) ([]byte, lifetime.Lifetime, error)
• type PeerPicker
• type TTLOverrides

Types

type Base

type Base struct {
	Name string
	// contains filtered or unexported fields
}

Base contains the non-reloadable parts of a cache that last for its entire lifetime, including peer selection and internal LRU caches. It must be .Configure()d with the reloadable parameters to be useful.

func NewBase

func NewBase(opts *BaseOpts) *Base

NewBase creates a new primed but not yet usable cache. This allocates the underlying LRU caches. This function should only be called once for a given cache name.

func (*Base) Configure

func (b *Base) Configure(opts *ConfigureOpts) *Cache

Configure combines reloadable config with a base cache to form a useable one. See ConfigureOpts's documentation for a description of each field. This method can be called multiple times for a given base; all created caches remain valid.

type BaseOpts

type BaseOpts struct {

	// Name is like a namespace for the cache. It allows multiple instances
	// within a single program. This may be passed to other peers during peer
	// loads, so must be consistent within a given cluster.
	Name string

	// PeerPicker will tell the cache who is authoritative for a given key, so
	// it knows where to attempt an origin load in the first instance.
	PeerPicker PeerPicker

	// AuthoritativeCacheCapacity is the max number of entries to allow in the
	// LRU map for keys we own. It is implemented as an LRU for safety, however
	// should be sized appropriately to hold everything. Note the consistent
	// hash can be some way off, so it is recommended to allow 1.5x the
	// allocation if keys were perfectly distributed. Keys that we were
	// previously authoritative for, but no longer due to membership changes,
	// are expected to expire over time due to TTLs.
	AuthoritativeCacheCapacity uint

	// HotCacheCapacity is the max number of entries to allow in the LRU map for
	// keys we do not own, but see frequent requests for. This is purely an
	// optimisation; keys expiring from this map is not the end of the world, as
	// they are likely only one hop to a peer away. However, being generous here
	// reduces the effects of cluster resizes, and makes us more resilient to
	// failure of an origin, as keys are stored in more places. This should be
	// large enough to avoid thrashing, but small enough that all instances do
	// not have to have unreasonable amounts of memory.
	HotCacheCapacity uint

	// ParallelRequests is the anticipated number of concurrent gets to the
	// cache. This is used for initial sizing of a data structure in an
	// internal duplicate call suppression package.
	ParallelRequests uint
}

BaseOpts contains parameters when creating a new base cache. All are required, as there is no standard configuration.

type Cache

type Cache struct {
	*Base
	// contains filtered or unexported fields
}

Cache represents a named cache instance, from which values can be retrieved.

func (*Cache) Get

func (c *Cache) Get(ctx context.Context, key string) ([]byte, lifetime.Lifetime, error)

Get retrieves an element from the cache, returning the data along with its TTL. The TTL is checked before handing the value back, and the key reloaded if it has expired. Due to thread scheduling, we cannot promise to never return a TTL that has expired. When retrieving a fresh value, the expiry is not checked again to avoid going into a loop. Internal processing time is not deducted from the TTL. It is not possible for the caller to know whether the value was fetched or already cached; that is only exposed in metrics in aggregate. Zero-length data is returned as nil; a non-nil value will have a length of at least 1.

type ConfigureOpts

type ConfigureOpts struct {

	// OriginLoader is used to load values from the original source. This is
	// equivalent to Getter in groupcache, and is the user's responsibility to
	// implement.
	OriginLoader

	// OriginLoadTimeout is the time to allow on the context provided when
	// loading from the origin.
	OriginLoadTimeout time.Duration

	// PeerLoader is used to load values from peers. An reference implementation
	// of this is provided in the rpc package.
	PeerLoader

	// PeerLoadTimeout is the time to allow on the context provided when loading
	// from a peer. This is important, as we want to eventually fall back to a
	// local origin load.
	PeerLoadTimeout time.Duration

	// TTLOverrides is the set of key => TTL mappings to overlay onto keys. See
	// the type's documentation for more details.
	TTLOverrides

	// HotAddProbability is the likelihood of a value retrieved from a peer
	// being added to the hot LRU cache.
	HotAddProbability float64
}

ConfigureOpts contains reloadable configuration. It is passed to a Base cache to turn it into a useable one. Later, the original base can be reconfigured with new values for these parameters.

type OriginLoader

type OriginLoader interface {

	// Load produces the value for a key, along with its lifetime. Zero-length
	// data must be returned as nil. This method may be called for any key on
	// any instance in the cluster at any time, so should return a
	// deterministic, consistent value. This is similar to Sink in groupcache.
	//
	// Note the expiry of the context is defined when configuring a base cache,
	// not by incoming external requests. We deduplicate loads, so want to avoid
	// the situation where one one impatient client causes everyone waiting on
	// the same key to receive an error.
	//
	// It is strongly recommended to stagger TTL expiration to avoid a
	// thundering herd on the origin, especially if it is remote. To achieve
	// this, add some jitter to the TTL to spread them over the longest period
	// that can be tolerated. Remember the jitter must be deterministic, so use
	// a value derived from the key, e.g. crc32, rather than math/rand.
	//
	// Values are cached amongst peers, and not reloaded until their TTL has
	// been reached. The TTL returned can be retrospectively modified via an
	// override, which allows decreasing the value, however this is only
	// intended for emergencies in very limited scenarios. Infinite TTLs can be
	// emulated by returning lifetime.New(lifetime.MaxDuration), however if you
	// do not want TTLs, you may want to consider another library.
	//
	// Excluding failure scenarios, this will only be called once for a given
	// key, by the cluster member that owns that key. If that cluster member
	// dies, its keys will be lazily re-retrieved as necessary. Concurrent
	// requests for a given key will only occur if the request to the owning
	// cluster member fails, in which case the requesters affected will each
	// retry this locally, possibly causing a small thundering herd. Due to
	// this, an error should only be returned when the key could not be
	// retrieved due to a transient error - not because they key does not (yet)
	// exist. In this case, it is recommended to return a static value with a
	// short TTL, which will prevent the cache from retrying for a period of
	// time. This method is responsible for implementing its own retries as
	// appropriate.
	Load(ctx context.Context, key string) ([]byte, lifetime.Lifetime, error)
}

OriginLoader knows how to retrieve the values for keys unknown to the cache, from the original source. This is the key interface implemented by users of the library. An instance is provided when configuring a particular base, so the cache name is not passed. Implementations must be safe for concurrent use.

type OriginLoaderFunc

type OriginLoaderFunc func(ctx context.Context, key string) ([]byte, lifetime.Lifetime, error)

OriginLoaderFunc simplifies implementation of stateless OriginLoaders.

func (OriginLoaderFunc) Load

func (f OriginLoaderFunc) Load(ctx context.Context, key string) ([]byte, lifetime.Lifetime, error)

type PeerLoader

type PeerLoader interface {

	// Load requests a key from the specified peer, which will currently always
	// be the authoritative peer. This peer should call cache.Get(), which may
	// result in a load via the OriginLoader. Zero-length data must be returned
	// as nil.
	Load(ctx context.Context, from *memberlist.Node, cache *Cache, key string) ([]byte, lifetime.Lifetime, error)
}

PeerLoader knows how to retrieve values of keys unknown to the local instance from a peer. This is conceptually an intra-cache version of OriginLoader. An instance must be provided when configuring a base; a reference implementation is available in the rpc package. Instances are scoped to a cache, but the implementation is provided with the cache object, so in practice they can be shared amongst multiple caches. Implementations must be safe for concurrent use.

type PeerLoaderFunc

type PeerLoaderFunc func(ctx context.Context, from *memberlist.Node, cache *Cache, key string) ([]byte, lifetime.Lifetime, error)

PeerLoaderFunc simplifies implementation of stateless PeerLoaders.

func (PeerLoaderFunc) Load

func (f PeerLoaderFunc) Load(ctx context.Context, from *memberlist.Node, cache *Cache, key string) ([]byte, lifetime.Lifetime, error)

type PeerPicker

type PeerPicker interface {

	// PickPeer returns the cluster node that is authoritiative for key. If the
	// current node is authoritative, the cluster contains no members, or we are
	// the only member, it returns nil.
	PickPeer(key string) *memberlist.Node
}

PeerPicker knows which member of a cluster owns a given key. It is used to find the authoritative node for a given key so origin loads are co-ordinated to avoid a thundering herd.

type TTLOverrides

type TTLOverrides map[string]time.Duration

TTLOverrides represents the lifetimes to overlay onto a set of keys. Current lifetimes, including those already in local caches, will be capped at these values. Note this mechanism does not allow increasing TTLs, and LRU caches are unaffected - TTLs are only modified ephemerally after retrieval.

Note, overriding a TTL to 0 will cause every non-concurrent get to hit the origin. To prematurely flush values representing unknown keys, it is instead recommended to set the TTL to a number of seconds, wait for all nodes with the key to reload it, then remove the override. As key payloads are opaque, we do not have the ability to only expire values that do not represent the desired value - everything for that key is affected.

This type must not be modified once used to configure a base cache.