otter

package module
v1.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 25, 2024 License: Apache-2.0 Imports: 4 Imported by: 30

README

High performance in-memory cache

Go Reference

📖 Contents

💡 Motivation

I once came across the fact that none of the Golang cache libraries are truly contention-free. All of them are just a standard map with mutex and some eviction policy. Unfortunately, these are not able to reach the speed of caches in other languages (such as Caffeine). For example, the fastest cache from Dgraph labs called Ristretto, which was faster than competitors by 30% at best (Otter is many times faster) and had a disgusting hit ratio even though README says otherwise. This can be a problem in different applications because no one wants to bump the performance of a cache library and its bad hit ratio 🙂. As a result, I wanted to get the fastest, easiest-to-use cache with excellent hit ratio and support from the authors and Otter is designed to correct this unfortunate misunderstanding.

Please leave a ⭐ as motivation if you liked the idea 😄

Otter is based on the following papers:

✨ Features

This library has lots of features such as:

📚 Usage

📋 Requirements

  • Go 1.18+

🛠️ Installation 

go get -u github.com/maypok86/otter

✏️ Examples

Otter uses a builder pattern that allows you to conveniently create a cache object with different parameters

Cache with const TTL

package main

import (
    "fmt"
    "time"

    "github.com/maypok86/otter"
)

func main() {
    // create a cache with capacity equal to 10000 elements
    cache, err := otter.MustBuilder[string, string](10_000).
        CollectStats().
        Cost(func(key string, value string) uint32 {
            return 1
        }).
        WithTTL(time.Hour).
        Build()
    if err != nil {
        panic(err)
    }

    // set item with ttl (1 hour) 
    cache.Set("key", "value")

    // get value from cache
    value, ok := cache.Get("key")
    if !ok {
        panic("not found key")
    }
    fmt.Println(value)

    // delete item from cache
    cache.Delete("key")

    // delete data and stop goroutines
    cache.Close()
}

Cache with variable TTL

package main

import (
    "fmt"
    "time"

    "github.com/maypok86/otter"
)

func main() {
    // create a cache with capacity equal to 10000 elements
    cache, err := otter.MustBuilder[string, string](10_000).
        CollectStats().
        Cost(func(key string, value string) uint32 {
            return 1
        }).
        WithVariableTTL().
        Build()
    if err != nil {
        panic(err)
    }

    // set item with ttl (1 hour)
    cache.Set("key1", "value1", time.Hour)
    // set item with ttl (1 minute)
    cache.Set("key2", "value2", time.Minute)

    // get value from cache
    value, ok := cache.Get("key1")
    if !ok {
        panic("not found key")
    }
    fmt.Println(value)

    // delete item from cache
    cache.Delete("key1")

    // delete data and stop goroutines
    cache.Close()
}

📊 Benchmarks

The benchmark code can be found here

🚀 Performance

Throughput benchmarks are a port of the caffeine benchmarks in Golang.

Read (100%)

In this benchmark 8 threads concurrently read from a cache configured with a maximum size.

Read (75%) / Write (25%)

In this benchmark 6 threads concurrently read from and 2 threads write to a cache configured with a maximum size.

Read (50%) / Write (50%)

In this benchmark 4 threads concurrently read from and 4 threads write to a cache configured with a maximum size.

Read (25%) / Write (75%)

In this benchmark 2 threads concurrently read from and 6 threads write to a cache configured with a maximum size.

Write (100%)

In this benchmark 8 threads concurrently write to a cache configured with a maximum size.

Otter shows fantastic speed under all loads except extreme write-heavy, but such a load is very rare for caches and usually indicates that the cache has a very small hit ratio.

🎯 Hit ratio

Zipf
zipf
S3

This trace is described as "disk read accesses initiated by a large commercial search engine in response to various web search requests."

s3
DS1

This trace is described as "a database server running at a commercial site running an ERP application on top of a commercial database."

ds1
P3

The trace P3 was collected from workstations running Windows NT by using Vtrace which captures disk operations through the use of device filters

p3
P8

The trace P8 was collected from workstations running Windows NT by using Vtrace which captures disk operations through the use of device filters

p8
LOOP

This trace demonstrates a looping access pattern.

loop
OLTP

This trace is described as "references to a CODASYL database for a one hour period."

oltp

In summary, we have that S3-FIFO (otter) is inferior to W-TinyLFU (theine) on lfu friendly traces (databases, search, analytics), but has a greater or equal hit ratio on web traces.

👏 Contribute

Contributions are welcome as always, before submitting a new PR please make sure to open a new issue so community members can discuss it. For more information please see contribution guidelines.

Additionally, you might find existing open issues which can help with improvements.

This project follows a standard code of conduct so that you can understand what actions will and will not be tolerated.

📄 License

This project is Apache 2.0 licensed, as found in the LICENSE.

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	// ErrIllegalCapacity means that a non-positive capacity has been passed to the NewBuilder.
	ErrIllegalCapacity = errors.New("capacity should be positive")
	// ErrIllegalTTL means that a non-positive ttl has been passed to the Builder.WithTTL.
	ErrIllegalTTL = errors.New("ttl should be positive")
)

Functions

This section is empty.

Types

type Builder 

type Builder[K comparable, V any] struct {
	// contains filtered or unexported fields
}

Builder is a one-shot builder for creating a cache instance.

func MustBuilder 

func MustBuilder[K comparable, V any](capacity int) *Builder[K, V]

MustBuilder creates a builder and sets the future cache capacity.

Panics if capacity <= 0.

func NewBuilder 

func NewBuilder[K comparable, V any](capacity int) (*Builder[K, V], error)

NewBuilder creates a builder and sets the future cache capacity.

Returns an error if capacity <= 0.

func (*Builder[K, V]) Build 

func (b *Builder[K, V]) Build() (Cache[K, V], error)

Build creates a configured cache or returns an error if invalid parameters were passed to the builder.

func (*Builder[K, V]) CollectStats 

func (b *Builder[K, V]) CollectStats() *Builder[K, V]

CollectStats determines whether statistics should be calculated when the cache is running.

By default, statistics calculating is disabled.

func (*Builder[K, V]) Cost 

func (b *Builder[K, V]) Cost(costFunc func(key K, value V) uint32) *Builder[K, V]

Cost sets a function to dynamically calculate the cost of an item.

By default, this function always returns 1.

func (*Builder[K, V]) WithTTL 

func (b *Builder[K, V]) WithTTL(ttl time.Duration) *ConstTTLBuilder[K, V]

WithTTL specifies that each item should be automatically removed from the cache once a fixed duration has elapsed after the item's creation.

func (*Builder[K, V]) WithVariableTTL 

func (b *Builder[K, V]) WithVariableTTL() *VariableTTLBuilder[K, V]

WithVariableTTL specifies that each item should be automatically removed from the cache once a duration has elapsed after the item's creation. Items are expired based on the custom ttl specified for each item separately.

You should prefer WithTTL to this option whenever possible.

type Cache 

type Cache[K comparable, V any] struct {
	// contains filtered or unexported fields
}

Cache is a structure performs a best-effort bounding of a hash table using eviction algorithm to determine which entries to evict when the capacity is exceeded.

func (Cache) Capacity 

func (bs Cache) Capacity() int

Capacity returns the cache capacity.

func (Cache) Clear 

func (bs Cache) Clear()

Clear clears the hash table, all policies, buffers, etc.

NOTE: this operation must be performed when no requests are made to the cache otherwise the behavior is undefined.

func (Cache) Close 

func (bs Cache) Close()

Close clears the hash table, all policies, buffers, etc and stop all goroutines.

NOTE: this operation must be performed when no requests are made to the cache otherwise the behavior is undefined.

func (Cache) Delete 

func (bs Cache) Delete(key K)

Delete removes the association for this key from the cache.

func (Cache) Get 

func (bs Cache) Get(key K) (V, bool)

Get returns the value associated with the key in this cache.

func (Cache) Has 

func (bs Cache) Has(key K) bool

Has checks if there is an item with the given key in the cache.

func (Cache) Range 

func (bs Cache) Range(f func(key K, value V) bool)

Range iterates over all items in the cache.

Iteration stops early when the given function returns false.

func (Cache[K, V]) Set 

func (c Cache[K, V]) Set(key K, value V) bool

Set associates the value with the key in this cache.

If it returns false, then the key-value item had too much cost and the Set was dropped.

func (Cache[K, V]) SetIfAbsent 

func (c Cache[K, V]) SetIfAbsent(key K, value V) bool

SetIfAbsent if the specified key is not already associated with a value associates it with the given value.

If the specified key is not already associated with a value, then it returns false.

Also, it returns false if the key-value item had too much cost and the SetIfAbsent was dropped.

func (Cache) Size 

func (bs Cache) Size() int

Size returns the current number of items in the cache.

func (Cache) Stats 

func (bs Cache) Stats() Stats

Stats returns a current snapshot of this cache's cumulative statistics.

type CacheWithVariableTTL 

type CacheWithVariableTTL[K comparable, V any] struct {
	// contains filtered or unexported fields
}

CacheWithVariableTTL is a structure performs a best-effort bounding of a hash table using eviction algorithm to determine which entries to evict when the capacity is exceeded.

func (CacheWithVariableTTL) Capacity 

func (bs CacheWithVariableTTL) Capacity() int

Capacity returns the cache capacity.

func (CacheWithVariableTTL) Clear 

func (bs CacheWithVariableTTL) Clear()

Clear clears the hash table, all policies, buffers, etc.

NOTE: this operation must be performed when no requests are made to the cache otherwise the behavior is undefined.

func (CacheWithVariableTTL) Close 

func (bs CacheWithVariableTTL) Close()

Close clears the hash table, all policies, buffers, etc and stop all goroutines.

NOTE: this operation must be performed when no requests are made to the cache otherwise the behavior is undefined.

func (CacheWithVariableTTL) Delete 

func (bs CacheWithVariableTTL) Delete(key K)

Delete removes the association for this key from the cache.

func (CacheWithVariableTTL) Get 

func (bs CacheWithVariableTTL) Get(key K) (V, bool)

Get returns the value associated with the key in this cache.

func (CacheWithVariableTTL) Has 

func (bs CacheWithVariableTTL) Has(key K) bool

Has checks if there is an item with the given key in the cache.

func (CacheWithVariableTTL) Range 

func (bs CacheWithVariableTTL) Range(f func(key K, value V) bool)

Range iterates over all items in the cache.

Iteration stops early when the given function returns false.

func (CacheWithVariableTTL[K, V]) Set 

func (c CacheWithVariableTTL[K, V]) Set(key K, value V, ttl time.Duration) bool

Set associates the value with the key in this cache and sets the custom ttl for this key-value item.

If it returns false, then the key-value item had too much cost and the Set was dropped.

func (CacheWithVariableTTL[K, V]) SetIfAbsent 

func (c CacheWithVariableTTL[K, V]) SetIfAbsent(key K, value V, ttl time.Duration) bool

SetIfAbsent if the specified key is not already associated with a value associates it with the given value and sets the custom ttl for this key-value item.

If the specified key is not already associated with a value, then it returns false.

Also, it returns false if the key-value item had too much cost and the SetIfAbsent was dropped.

func (CacheWithVariableTTL) Size 

func (bs CacheWithVariableTTL) Size() int

Size returns the current number of items in the cache.

func (CacheWithVariableTTL) Stats 

func (bs CacheWithVariableTTL) Stats() Stats

Stats returns a current snapshot of this cache's cumulative statistics.

type ConstTTLBuilder 

type ConstTTLBuilder[K comparable, V any] struct {
	// contains filtered or unexported fields
}

ConstTTLBuilder is a one-shot builder for creating a cache instance.

func (*ConstTTLBuilder[K, V]) Build 

func (b *ConstTTLBuilder[K, V]) Build() (Cache[K, V], error)

Build creates a configured cache or returns an error if invalid parameters were passed to the builder.

func (*ConstTTLBuilder[K, V]) CollectStats 

func (b *ConstTTLBuilder[K, V]) CollectStats() *ConstTTLBuilder[K, V]

CollectStats determines whether statistics should be calculated when the cache is running.

By default, statistics calculating is disabled.

func (*ConstTTLBuilder[K, V]) Cost 

func (b *ConstTTLBuilder[K, V]) Cost(costFunc func(key K, value V) uint32) *ConstTTLBuilder[K, V]

Cost sets a function to dynamically calculate the cost of an item.

By default, this function always returns 1.

type Stats 

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

Stats is a thread-safe statistics collector.

func (Stats) Hits 

func (s Stats) Hits() int64

Hits returns the number of cache hits.

func (Stats) Misses 

func (s Stats) Misses() int64

Misses returns the number of cache misses.

func (Stats) Ratio 

func (s Stats) Ratio() float64

Ratio returns the cache hit ratio.

type VariableTTLBuilder 

type VariableTTLBuilder[K comparable, V any] struct {
	// contains filtered or unexported fields
}

VariableTTLBuilder is a one-shot builder for creating a cache instance.

func (*VariableTTLBuilder[K, V]) Build 

func (b *VariableTTLBuilder[K, V]) Build() (CacheWithVariableTTL[K, V], error)

Build creates a configured cache or returns an error if invalid parameters were passed to the builder.

func (*VariableTTLBuilder[K, V]) CollectStats 

func (b *VariableTTLBuilder[K, V]) CollectStats() *VariableTTLBuilder[K, V]

CollectStats determines whether statistics should be calculated when the cache is running.

By default, statistics calculating is disabled.

func (*VariableTTLBuilder[K, V]) Cost 

func (b *VariableTTLBuilder[K, V]) Cost(costFunc func(key K, value V) uint32) *VariableTTLBuilder[K, V]

Cost sets a function to dynamically calculate the cost of an item.

By default, this function always returns 1.

Source Files

View all Source files

Directories

Path Synopsis
internal
core
expire
hashtable
lossy
node
queue
s3fifo
stats
unixtime
xmath
xruntime

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.