ristretto: github.com/dgraph-io/ristretto Index | Files | Directories

package ristretto

import "github.com/dgraph-io/ristretto"

Ristretto is a fast, fixed size, in-memory cache with a dual focus on throughput and hit ratio performance. You can easily add Ristretto to an existing system and keep the most valuable data where you need it.

This package includes multiple probabalistic data structures needed for admission/eviction metadata. Most are Counting Bloom Filter variations, but a caching-specific feature that is also required is a "freshness" mechanism, which basically serves as a "lifetime" process. This freshness mechanism was described in the original TinyLFU paper [1], but other mechanisms may be better suited for certain data distributions.

[1]: https://arxiv.org/abs/1512.00727

Index

Package Files

cache.go policy.go ring.go sketch.go store.go ttl.go

type Cache Uses

type Cache struct {

    // Metrics contains a running log of important statistics like hits, misses,
    // and dropped items.
    Metrics *Metrics
    // contains filtered or unexported fields
}

Cache is a thread-safe implementation of a hashmap with a TinyLFU admission policy and a Sampled LFU eviction policy. You can use the same Cache instance from as many goroutines as you want.

func NewCache Uses

func NewCache(config *Config) (*Cache, error)

NewCache returns a new Cache instance and any configuration errors, if any.

func (*Cache) Clear Uses

func (c *Cache) Clear()

Clear empties the hashmap and zeroes all policy counters. Note that this is not an atomic operation (but that shouldn't be a problem as it's assumed that Set/Get calls won't be occurring until after this).

func (*Cache) Close Uses

func (c *Cache) Close()

Close stops all goroutines and closes all channels.

func (*Cache) Del Uses

func (c *Cache) Del(key interface{})

Del deletes the key-value item from the cache if it exists.

func (*Cache) Get Uses

func (c *Cache) Get(key interface{}) (interface{}, bool)

Get returns the value (if any) and a boolean representing whether the value was found or not. The value can be nil and the boolean can be true at the same time.

func (*Cache) MaxCost Uses

func (c *Cache) MaxCost() int64

MaxCost returns the max cost of the cache.

func (*Cache) Set Uses

func (c *Cache) Set(key, value interface{}, cost int64) bool

Set attempts to add the key-value item to the cache. If it returns false, then the Set was dropped and the key-value item isn't added to the cache. If it returns true, there's still a chance it could be dropped by the policy if its determined that the key-value item isn't worth keeping, but otherwise the item will be added and other items will be evicted in order to make room.

To dynamically evaluate the items cost using the Config.Coster function, set the cost parameter to 0 and Coster will be ran when needed in order to find the items true cost.

func (*Cache) SetWithTTL Uses

func (c *Cache) SetWithTTL(key, value interface{}, cost int64, ttl time.Duration) bool

SetWithTTL works like Set but adds a key-value pair to the cache that will expire after the specified TTL (time to live) has passed. A zero value means the value never expires, which is identical to calling Set. A negative value is a no-op and the value is discarded.

func (*Cache) UpdateMaxCost Uses

func (c *Cache) UpdateMaxCost(maxCost int64)

UpdateMaxCost updates the maxCost of an existing cache.

func (*Cache) Wait Uses

func (c *Cache) Wait()

type Config Uses

type Config struct {
    // NumCounters determines the number of counters (keys) to keep that hold
    // access frequency information. It's generally a good idea to have more
    // counters than the max cache capacity, as this will improve eviction
    // accuracy and subsequent hit ratios.
    //
    // For example, if you expect your cache to hold 1,000,000 items when full,
    // NumCounters should be 10,000,000 (10x). Each counter takes up 4 bits, so
    // keeping 10,000,000 counters would require 5MB of memory.
    NumCounters int64
    // MaxCost can be considered as the cache capacity, in whatever units you
    // choose to use.
    //
    // For example, if you want the cache to have a max capacity of 100MB, you
    // would set MaxCost to 100,000,000 and pass an item's number of bytes as
    // the `cost` parameter for calls to Set. If new items are accepted, the
    // eviction process will take care of making room for the new item and not
    // overflowing the MaxCost value.
    MaxCost int64
    // BufferItems determines the size of Get buffers.
    //
    // Unless you have a rare use case, using `64` as the BufferItems value
    // results in good performance.
    BufferItems int64
    // Metrics determines whether cache statistics are kept during the cache's
    // lifetime. There *is* some overhead to keeping statistics, so you should
    // only set this flag to true when testing or throughput performance isn't a
    // major factor.
    Metrics bool
    // OnEvict is called for every eviction and passes the hashed key, value,
    // and cost to the function.
    OnEvict func(item *Item)
    // OnReject is called for every rejection done via the policy.
    OnReject func(item *Item)
    // OnExit is called whenever a value is removed from cache. This can be
    // used to do manual memory deallocation. Would also be called on eviction
    // and rejection of the value.
    OnExit func(val interface{})
    // KeyToHash function is used to customize the key hashing algorithm.
    // Each key will be hashed using the provided function. If keyToHash value
    // is not set, the default keyToHash function is used.
    KeyToHash func(key interface{}) (uint64, uint64)
    // Cost evaluates a value and outputs a corresponding cost. This function
    // is ran after Set is called for a new item or an item update with a cost
    // param of 0.
    Cost func(value interface{}) int64
    // IgnoreInternalCost set to true indicates to the cache that the cost of
    // internally storing the value should be ignored. This is useful when the
    // cost passed to set is not using bytes as units. Keep in mind that setting
    // this to true will increase the memory usage.
    IgnoreInternalCost bool
}

Config is passed to NewCache for creating new Cache instances.

type Item Uses

type Item struct {
    Key        uint64
    Conflict   uint64
    Value      interface{}
    Cost       int64
    Expiration int64
    // contains filtered or unexported fields
}

Item is passed to setBuf so items can eventually be added to the cache.

type Metrics Uses

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

Metrics is a snapshot of performance statistics for the lifetime of a cache instance.

func (*Metrics) Clear Uses

func (p *Metrics) Clear()

Clear resets all the metrics.

func (*Metrics) CostAdded Uses

func (p *Metrics) CostAdded() uint64

CostAdded is the sum of costs that have been added (successful Set calls).

func (*Metrics) CostEvicted Uses

func (p *Metrics) CostEvicted() uint64

CostEvicted is the sum of all costs that have been evicted.

func (*Metrics) GetsDropped Uses

func (p *Metrics) GetsDropped() uint64

GetsDropped is the number of Get counter increments that are dropped internally.

func (*Metrics) GetsKept Uses

func (p *Metrics) GetsKept() uint64

GetsKept is the number of Get counter increments that are kept.

func (*Metrics) Hits Uses

func (p *Metrics) Hits() uint64

Hits is the number of Get calls where a value was found for the corresponding key.

func (*Metrics) KeysAdded Uses

func (p *Metrics) KeysAdded() uint64

KeysAdded is the total number of Set calls where a new key-value item was added.

func (*Metrics) KeysEvicted Uses

func (p *Metrics) KeysEvicted() uint64

KeysEvicted is the total number of keys evicted.

func (*Metrics) KeysUpdated Uses

func (p *Metrics) KeysUpdated() uint64

KeysUpdated is the total number of Set calls where the value was updated.

func (*Metrics) LifeExpectancySeconds Uses

func (p *Metrics) LifeExpectancySeconds() *z.HistogramData

func (*Metrics) Misses Uses

func (p *Metrics) Misses() uint64

Misses is the number of Get calls where a value was not found for the corresponding key.

func (*Metrics) Ratio Uses

func (p *Metrics) Ratio() float64

Ratio is the number of Hits over all accesses (Hits + Misses). This is the percentage of successful Get calls.

func (*Metrics) SetsDropped Uses

func (p *Metrics) SetsDropped() uint64

SetsDropped is the number of Set calls that don't make it into internal buffers (due to contention or some other reason).

func (*Metrics) SetsRejected Uses

func (p *Metrics) SetsRejected() uint64

SetsRejected is the number of Set calls rejected by the policy (TinyLFU).

func (*Metrics) String Uses

func (p *Metrics) String() string

String returns a string representation of the metrics.

Directories

PathSynopsis
sim
z

Package ristretto imports 10 packages (graph) and is imported by 48 packages. Updated 2020-10-23. Refresh now. Tools for package owners.