README
¶
cache/lru
Update
This readme refers to v1 of this package. V2 on the master branch is still a work in progress and should not be used yet
v2 features:
- generic type LRU[K comparable, V any] with a leaner API to be used as a building block for more specialized caches
- faster implementation (hopscotch hash table) with improved CPU cache locality.
- fast concurrent implementation (with partial locking of the table), but the LRU property is only statistically correct.
- Requires user provided hash functions, but the package provides decent ones for integers and strings (pulled from Go std).
about v1
Package lru implements an LRU cache with variable item size and automatic item eviction.
For performance reasons, the lru list is kept in a custom list implementation, it does not use Go's container/list.
The cache size is determined by the actual size of the contained items, or more precisely by the size specified in the call to Set() for each new item. The Cache.Size() and Cache.Len() methods return distinct quantities.
The default cache eviction policy is cache size vs. capacity. Users who need to count items can set the size of each item to 1, in which case Len() == Size(). If a balance between item count and size is desired, another option is to set the cache capacity to NoCap and use a custom eviction function. See the example for EvictToSize().
Item creation and removal callback handlers are also supported. The item creation handler enables a pattern like
value, err = cache.Get(key)
if value == nil {
// no value found, make one
v, size, _ := newValueForKey(key)
cache.Set(key, v, size)
value = v
}
to work as an atomic cache operation via a single Get() call.
The package has built-in support for concurrent use. Callers must be aware that when handlers configured with NewValueHandler and EvictHandler are called, the cache may be in a locked state. Therefore such handlers must not make any direct or indirect calls to the cache.
Installation
go get -u github.com/db47h/cache/lru
Usage & examples
Read the API docs.
A quick example demonstrating how to implement hard/soft limits:
// Using EvictToSize to implement hard/soft limit.
func ExampleCache_EvictToSize() {
// Create a cache with a capacity of 1GB. This will be our hard limit. When
// the cache size will reach it, evictions will happen synchronously with
// Set()/Get().
c, _ := lru.New(1<<30, lru.EvictHandler(
// This eviction handler is just here for debugging purposes.
func(v lru.Value) {
fmt.Printf("Evicted item %v\n", v)
}))
// start a goroutine that will periodically evict items from the cache to
// keep the cache size under 512MB. This is our soft limit.
var wg sync.WaitGroup
var done = make(chan struct{})
wg.Add(1)
go func(wg *sync.WaitGroup, done <-chan struct{}) {
defer wg.Done()
t := time.NewTicker(time.Millisecond * 20)
for {
select {
case <-t.C:
c.EvictToSize(512 << 20)
case <-done:
t.Stop()
return
}
}
}(&wg, done)
// do stuff..
c.Set(13, "Value for key 13", 600<<20)
// Now adding item "42" with a size of 600MB will overflow the hard limit of
// 1GB. As a consequence, item "13" will be evicted synchronously with the
// call to Set.
c.Set(42, "Value for key 42", 600<<20)
// Give time for the background job to kick in.
fmt.Println("Asynchronous evictions:")
time.Sleep(60 * time.Millisecond)
close(done)
wg.Wait()
// Output:
//
// Evicted item Value for key 13
// Asynchronous evictions:
// Evicted item Value for key 42
}
Specializing the Key and Value types
The Key and Value types are defined in types.go as interfaces. Users who need to use concrete types instead of interfaces can easily customize these by vendoring the package then redefine Key and Value in types.go. This file is dedicated to this purpose and should not change in future versions.
Documentation
¶
Overview ¶
Package lru provides a generic LRU hashmap for use as the core of a LRU cache. Size and eviction policy are controlled by client code via an OnEvict() callback called whenever an entry is updated or a new one inserted.
INternals: http://people.csail.mit.edu/shanir/publications/disc2008_submission_98.pdf
Example (File_cache) ¶
package main
import (
"encoding/base64"
"io"
"net/http"
"os"
"path/filepath"
"time"
"github.com/db47h/cache/v2/lru"
)
type CachedFile struct {
Expires time.Time
URL string
Path string
Size int64
}
type HttpCache struct {
lru lru.Map[string, CachedFile]
size int64
cap int64
}
func NewHttpCache(capacity int) *HttpCache {
c := new(HttpCache)
c.cap = int64(capacity)
return c
}
func (c *HttpCache) onEvict(url string, cf CachedFile) bool {
return false
}
func (c *HttpCache) Get(url string) ([]byte, error) {
cf, ok := c.lru.Get(url)
if ok {
// cached entry found, read it from disk
// note that we should check if cf has expired
f, err := os.Open(cf.Path)
if err != nil {
return nil, err
}
defer f.Close()
return io.ReadAll(f)
}
// fetch from url
resp, err := http.Get(url)
if err != nil {
return nil, err
}
defer resp.Body.Close()
data, err := io.ReadAll(resp.Body)
if err != nil {
return nil, err
}
// create cache entry
cf = CachedFile{
URL: url,
Path: filepath.Join(os.TempDir(), base64.URLEncoding.EncodeToString([]byte(url))),
Size: int64(len(data)),
Expires: time.Now().Add(time.Hour * 24 * 7), // expire in one week
}
// write file
of, err := os.Create(cf.Path)
if err != nil {
return nil, err
}
defer of.Close()
_, err = of.Write(data)
if err != nil {
os.Remove(cf.Path)
return nil, err
}
c.lru.Set(url, cf)
return data, nil
}
func main() {
}
//
//
// // // We're caching files
// type cachedFile struct {
// name string
// fd int
// size int64
// }
// var lastFd = -1 // dummy, predictable simulation of the next file descriptor
// // newHandler will be called to atomically create new items on cache misses.
// // Here we suppose that the files are fetched remotely and that in a real usage
// // scenario the fd would be an *os.File or an io.Reader, not some dummy fd. The
// // file would even be fetched asynchronously since this function should return
// // as quickly as possible.
// func newHandler(k string) (*cachedFile, int64, error) {
// fmt.Printf("NewHandler for key %s\n", k)
// lastFd++
// sz := rand.Int63n(1 << 10)
// return &cachedFile{k, lastFd, sz}, sz, nil
// }
// // evictHandler will be called upon item eviction from the cache.
// func evictHandler(v *cachedFile) {
// f := v
// fmt.Printf("Evicted file: %q, fd: %v\n", f.name, f.fd)
// // here we'd delete the file from disk
// }
// func cacheSet(c *lru.Cache[string, *cachedFile], f *cachedFile) bool {
// return c.Set(f.name, f, f.size)
// }
// // A file cache example.
// func Example_file_cache() {
// // create a small cache with a 100MB capacity.
// cache, err := lru.New[string, *cachedFile](100<<20,
// lru.EvictHandler[string, *cachedFile](evictHandler),
// lru.NewValueHandler[string, *cachedFile](newHandler))
// if err != nil {
// panic(err)
// }
// // auto fill
// v, err := cache.Get("/nfs/fileA")
// if err != nil {
// panic(err)
// }
// // we have configured a NewValueHandler, v is guaranteed to be non-nil if err is nil.
// fmt.Printf("Got file %s, fd: %d\n", v.name, v.fd)
// // manually setting an item
// cacheSet(cache, &cachedFile{"/nfs/fileB", 4242, 16 << 20})
// v, _ = cache.Get("/nfs/fileB")
// fmt.Printf("Got file %s, fd: %d\n", v.name, v.fd)
// // evict file A
// fmt.Println("Manual eviction")
// cache.Evict("/nfs/fileA")
// // Add some huge file that will automatically evict file B to make room for it.
// fmt.Println("Auto-eviction")
// if !cacheSet(cache, &cachedFile{"/nfs/fileC", 1234, 100 << 20}) {
// panic("fileC should fit!")
// }
// // Add a few files more (fileC will be evicted)
// fmt.Println("More files")
// _, _ = cache.Get("/nfs/fileX")
// _, _ = cache.Get("/nfs/fileY")
// _, _ = cache.Get("/nfs/fileZ")
// // redresh fileX
// _, _ = cache.Get("/nfs/fileX")
// // force a cache flush. fileX was used last, so it should be evicted last.
// fmt.Println("Flush")
// cache.EvictToSize(0)
// // Output:
// //
// // NewHandler for key /nfs/fileA
// // Got file /nfs/fileA, fd: 0
// // Got file /nfs/fileB, fd: 4242
// // Manual eviction
// // Evicted file: "/nfs/fileA", fd: 0
// // Auto-eviction
// // Evicted file: "/nfs/fileB", fd: 4242
// // More files
// // NewHandler for key /nfs/fileX
// // Evicted file: "/nfs/fileC", fd: 1234
// // NewHandler for key /nfs/fileY
// // NewHandler for key /nfs/fileZ
// // Flush
// // Evicted file: "/nfs/fileY", fd: 2
// // Evicted file: "/nfs/fileZ", fd: 3
// // Evicted file: "/nfs/fileX", fd: 1
// }
Output:
Index ¶
- type Map
- func (m *Map[K, V]) All() func(yield func(K, V) bool)
- func (m *Map[K, V]) Capacity() int
- func (m *Map[K, V]) Delete(key K) (V, bool)
- func (m *Map[K, V]) DeleteLRU() (key K, value V)
- func (m *Map[K, V]) Get(key K) (V, bool)
- func (m *Map[K, V]) Init(opts ...Option)
- func (m *Map[K, V]) Keys() func(yield func(K) bool)
- func (m *Map[K, V]) LRU() (K, V)
- func (m *Map[K, V]) Len() int
- func (m *Map[K, V]) Load() float64
- func (m *Map[K, V]) MRU() (K, V)
- func (m *Map[K, V]) Set(key K, value V) (prev V, replaced bool)
- func (m *Map[K, V]) Values() func(yield func(V) bool)
- type Option
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Map ¶
type Map[K comparable, V any] struct { // contains filtered or unexported fields }
Map represents a Least Recently Used hash table.
func (*Map[K, V]) Delete ¶
Delete deletes the given key and returns its value and true if the key was found, otherwise it returns the zero value for V and false.
type Option ¶
type Option interface {
// contains filtered or unexported methods
}
func WithCapacity ¶
func WithHasher ¶
func WithHasher[K comparable](hasher func(K) uint64) Option
Source Files