forget

README

Forget

Forget is a Go library for in-memory caching. It can be used as a safe, in-process cache for storing binary data:

• supports use cases with different characteristics: key store, cache for small and large binary data;
• has a simple get/set/delete interface;
• implements TTL based expiration;
• implements LRU style eviction optimized with keyspaces;
• allocates the predefined maximum used memory in advance, on startup;
• supports streaming style read/write IO, with seeking and immediate read access to items being filled;
• protects busy items from delete, reset and eviction;
• all its operations are ready for concurrent access, and, as much as possible, accessible in parallel;
• supports monitoring with detailed statistics and continuous notifications;

Documentation:

The detailed description of the library and its usage can be found in Godoc:

https://godoc.org/github.com/aryszka/forget

Example:

// intialize a cache with 1MB cache size and 1KB chunk size
c := forget.New(forget.Options{CacheSize: 1 << 20, ChunkSize: 1 << 10})
defer c.Close()

// store a cache item
if !c.SetBytes("foo", []byte("bar"), time.Minute) {
	log.Println("failed to set cache item")
	return
}

// retrieve a cache item
b, ok := c.GetBytes("foo")
if !ok {
	log.Println("failed to get cache item")
	return
}

Installation:

go get github.com/aryszka/forget

Documentation

Overview

Package forget provides an in-memory cache for arbitrary, binary data.

Caching

The cache identifies items by their keys. It stores them with individual expiration time (TTL). The associated content is stored in binary format. Storing a new item with the same key, overrides the previous one. A cached item can be retrieved or deleted with its key. As a special use case, it is possible to store only keys, where the useful information is whether a key exists or not. If a new item doesn't fit in the free space, the least recently used item is evicted (LRU).

Keyspaces

Keyspaces, when used (see NewCacheSpaces()), allow some optimization of the LRU eviction mechanism. Items that are more expensive to produce but less frequently accessed than others, can be stored in different keyspaces. When eviction is required, the cache tries to evict enough items from the same keyspace as the one currently being filled. When using keyspaces, the same key can appear in different keyspaces pointing to different items.

Memory

The cache allocates all the used memory on start. To support parallel access, it splits the allocated memory into segments. There are typically as many segments as the maximum of NumCPU() and GOMAXPROCS(). The maximum size of a stored item is the total cache size divided by the number of segments.

The segments are split into chunks. One cached item can span over multiple chunks, but the chunks cannot be shared between the items. This means that the cache is almost never fully utilized. The chunk size is an initialization option, it typically should be a 'couple of times' smaller than the expected size of the 'bulk' of the cached items.

The cache counts the size of the item keys in the used space, but there is some lookup metadata that is not counted: ~24 bytes for each chunk and ~120 bytes for each item.

IO

The associated data of the keys can be accessed for read, seek and write through the standard Go interfaces. As a shortcut, the data can be retrieved or set as a single byte slice, too. When using the IO interfaces, the item data can be accessed concurrently, and reading from an item can be started before the write has finished. When the reader reaches a point that was not yet filled by the writer, it blocks, and continues only when more data was written, or returns with EOF once the write has finished.

While writing an item, chunks are continuously assigned to the item from the free range of the allocated memory. If there are no free chunks, the cache evicts enough of the least recently used items. The cache doesn't evict those items that are currently being read by an unclosed reader. Similarly, when deleting an item or overwriting one, if it has active readers associated with it, the item is only marked for delete, but the active readers can finish reading from it.

Monitoring

The cache provides statistics about its internal state, including metrics like item count, effective and used size, active readers and writers. When configured, it also provides change notifications. Depending on the configured notification mask, it can send events about: cache hit/miss, evictions, allocation failures, etc.

Example

package main

import (
	"fmt"
	"log"
	"time"

	"github.com/aryszka/forget"
)

func main() {
	// intialize a cache with 1MB cache size and 1KB chunk size
	c := forget.New(forget.Options{CacheSize: 1 << 20, ChunkSize: 1 << 10})
	defer c.Close()

	// store a cache item
	if !c.SetBytes("foo", []byte("bar"), time.Minute) {
		log.Println("failed to set cache item")
		return
	}

	// retrieve a cache item
	b, ok := c.GetBytes("foo")
	if !ok {
		log.Println("failed to get cache item")
		return
	}

	fmt.Printf("Item from the cache: %s.\n", string(b))

}

Output:

Item from the cache: bar.

Example (Io)

package main

import (
	"fmt"
	"io"
	"io/ioutil"
	"log"
	"time"

	"github.com/aryszka/forget"
)

func main() {
	c := forget.New(forget.Options{CacheSize: 1 << 20, ChunkSize: 1 << 10})
	defer c.Close()

	// set an item and receive a writer
	w, ok := c.Set("foo", time.Minute)
	if !ok {
		log.Println("failed to set cache item")
		return
	}

	// get three readers before the item data has been written
	var r []io.Reader
	for i := 0; i < 3; i++ {
		ri, ok := c.Get("foo")
		if !ok {
			log.Println("failed to get cache item")
			return
		}

		defer ri.Close()
		r = append(r, ri)
	}

	// start filling the cache item in the background
	go func() {
		if _, err := w.Write([]byte("foobarbaz")); err != nil {
			log.Println("failed to write item")
		}

		// closing the writer indicates that the item is filled
		w.Close()
	}()

	// read from the readers, not necessarily after the cache item was filled:
	for _, ri := range r {
		p, err := ioutil.ReadAll(ri)
		if err != nil {
			log.Println("failed to read item")
			return
		}

		fmt.Println(string(p))
	}

}

Output:

foobarbaz
foobarbaz
foobarbaz

Example (Keyspaces)

package main

import (
	"fmt"
	"time"

	"github.com/aryszka/forget"
)

func main() {
	c := forget.NewCacheSpaces(forget.Options{CacheSize: 1 << 9, ChunkSize: 1 << 6})
	defer c.Close()

	// store items with different keyspaces
	c.SetBytes("pages", "/home", []byte("Hello, world!"), time.Minute)
	c.SetBytes("pages", "/article-one", []byte("This is cached."), time.Minute)
	c.SetBytes("ajax-data", "/article-one", []byte(`{"data": 42}`), 12*time.Minute)

	// retrieve an item
	if d, ok := c.GetBytes("pages", "/article-one"); ok {
		fmt.Println(string(d))
	} else {
		fmt.Println("article not found in cache")
	}

}

Output:

This is cached.

Example (Proxyfill)

package main

import (
	"bytes"
	"fmt"
	"io"
	"io/ioutil"
	"net/http"
	"net/http/httptest"
	"sync"
	"time"

	"github.com/aryszka/forget"
)

func main() {
	// The following example shows a backend server and a caching proxy in front of it. The backend produces
	// an expensive resource. The proxy caches it, it prevents multiple requests reaching the backend in
	// case of a cache miss, and serves any data to multiple clients in parallel as soon as it is available.
	// (See the order of the output.)

	// create a test backend server
	testContent := []byte{1, 2, 3}
	backend := httptest.NewServer(http.HandlerFunc(func(w http.ResponseWriter, _ *http.Request) {
		// send slow content
		for _, b := range testContent {
			time.Sleep(12 * time.Millisecond)
			w.Write([]byte{b})
		}

		fmt.Println("backend done")
	}))
	defer backend.Close()

	// create a caching proxy
	c := forget.New(forget.Options{CacheSize: 1 << 20, ChunkSize: 1 << 10})
	cacheServer := httptest.NewServer(http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
		// check if it is a hit
		if r, ok := c.Get(r.URL.Path); ok {
			fmt.Println("hit")
			defer r.Close()

			// make a preread to know that the backend responded with success
			// during cache filling
			b := make([]byte, 1<<10)
			n, err := r.Read(b)
			if err != nil && err != io.EOF {
				fmt.Println("cache fill failed", err)
				w.WriteHeader(http.StatusNotFound)
				return
			}

			w.Write(b[:n])

			// copy the rest of the cached content to the response
			io.Copy(w, r)
			return
		}

		// if it is a miss, optimistically create a cache item
		fmt.Println("miss")
		cacheItem, itemCreated := c.Set(r.URL.Path, time.Minute)
		if itemCreated {
			defer cacheItem.Close()
		}

		// initiate the streaming of the actual content
		rsp, err := http.Get(backend.URL + r.URL.Path)
		if err != nil {
			// if the request fails, we can discard the invalid cache item
			c.Delete(r.URL.Path)
			w.WriteHeader(http.StatusInternalServerError)
			return
		}
		defer rsp.Body.Close()

		// initiate the outgoing response
		w.WriteHeader(rsp.StatusCode)
		if !itemCreated {
			io.Copy(w, rsp.Body)
			return
		}

		// for this example, cache only the responses with status 200
		var body io.Reader = rsp.Body
		if rsp.StatusCode == http.StatusOK {
			body = io.TeeReader(body, cacheItem)
		} else {
			c.Delete(r.URL.Path)
		}

		// send the response to the client and, on success, to the cache through the tee reader.
		// if it fails, delete the invalid cache item
		if _, err := io.Copy(w, body); err != nil {
			c.Delete(r.URL.Path)
		}
	}))
	defer c.Close()
	defer cacheServer.Close()

	// make multiple requests faster than how the backend can respond
	var wg sync.WaitGroup
	for i := 0; i < 3; i++ {
		wg.Add(1)
		go func(delay int) {
			time.Sleep(time.Duration(3*delay) * time.Millisecond)
			rsp, err := http.Get(cacheServer.URL + "/test-item")
			if err != nil {
				fmt.Println("request error", err)
				wg.Done()
				return
			}
			defer rsp.Body.Close()

			if content, err := ioutil.ReadAll(rsp.Body); err != nil || !bytes.Equal(content, testContent) {
				fmt.Println("error reading response content", err)
			}

			fmt.Println("request done")
			wg.Done()
		}(i)
	}

	wg.Wait()

}

Output:

miss
hit
hit
backend done
request done
request done
request done

Index

• Constants
• Variables
• type Cache
  • func New(o Options) *Cache
  • func (c *Cache) Close()
  • func (c *Cache) Delete(key string)
  • func (c *Cache) Get(key string) (*Reader, bool)
  • func (c *Cache) GetBytes(key string) ([]byte, bool)
  • func (c *Cache) GetKey(key string) bool
  • func (c *Cache) Set(key string, ttl time.Duration) (io.WriteCloser, bool)
  • func (c *Cache) SetBytes(key string, data []byte, ttl time.Duration) bool
  • func (c *Cache) SetKey(key string, ttl time.Duration) bool
  • func (c *Cache) Stats() *CacheStats
• type CacheSpaces
  • func NewCacheSpaces(o Options) *CacheSpaces
  • func (c *CacheSpaces) Close()
  • func (c *CacheSpaces) Delete(keyspace, key string)
  • func (c *CacheSpaces) Get(keyspace, key string) (*Reader, bool)
  • func (c *CacheSpaces) GetBytes(keyspace, key string) ([]byte, bool)
  • func (c *CacheSpaces) GetKey(keyspace, key string) bool
  • func (c *CacheSpaces) Set(keyspace, key string, ttl time.Duration) (*Writer, bool)
  • func (c *CacheSpaces) SetBytes(keyspace, key string, data []byte, ttl time.Duration) bool
  • func (c *CacheSpaces) SetKey(keyspace, key string, ttl time.Duration) bool
  • func (c *CacheSpaces) Stats() *CacheStats
• type CacheStats
• type Event
• type EventType
  • func (et EventType) String() string
• type Options
• type Reader
  • func (r *Reader) Close() error
  • func (r *Reader) Read(p []byte) (int, error)
  • func (r *Reader) Seek(offset int64, whence int) (int64, error)
• type Stats
• type Writer
  • func (w *Writer) Close() error
  • func (w *Writer) Write(p []byte) (int, error)

Examples

• Package
• Package (Io)
• Package (Keyspaces)
• Package (Proxyfill)

Constants

const (
	// DefaultCacheSize is used when CacheSize is not specified in the initial Options.
	DefaultCacheSize = 1 << 30

	// DefaultChunkSize is used when ChunkSize is not specified in the initial Options.
	DefaultChunkSize = 1 << 15
)

Variables

var (
	// ErrItemDiscarded is returned by IO operations when an item has been discarded, e.g. evicted, deleted or
	// the discarded due to the cache was closed.
	ErrItemDiscarded = errors.New("item discarded")

	// ErrWriteLimit is returned when writing to an item fills the available size.
	ErrWriteLimit = errors.New("write limit")

	// ErrReaderClosed is returned when reading from or closing a reader that was already closed before.
	ErrReaderClosed = errors.New("writer closed")

	// ErrWriterClosed is returned when writing to or closing a writer that was already closed before.
	ErrWriterClosed = errors.New("writer closed")

	// ErrInvalidSeekOffset is returned by Seek() when trying to seek to an invalid position.
	ErrInvalidSeekOffset = errors.New("invalid seek offset")

	// ErrCacheClosed is returned when calling an operation on a closed cache.
	ErrCacheClosed = errors.New("cache closed")
)

Types

type Cache

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

Cache provides an in-memory cache for arbitrary binary data identified by keys.

func New

func New(o Options) *Cache

New initializes a cache.

Forget creates internally multiple independent cache segments, as many as the maximum of the reported CPU cores or the GOMAXPROCS value. These segments can be accessed in parallel without synchronization cost. This internal split of the cache affects the maximum size of a single item: ~ CacheSize / NumCPU.

func (*Cache) Close

func (c *Cache) Close()

Close shuts down the cache and releases resources.

func (*Cache) Delete

func (c *Cache) Delete(key string)

Delete deletes an item from the cache with a key.

func (*Cache) Get

func (c *Cache) Get(key string) (*Reader, bool)

Get retrieves a reader to an item in the cache. The second return argument indicates if the item was found. Reading can start before writing to the item was finished. The reader blocks if the read reaches the point that the writer didn't pass yet. If the write finished, and the reader reaches the end of the item, EOF is returned. The reader returns ErrCacheClosed if the cache was closed and ErrItemDiscarded if the original item with the given key is not available anymore. The reader must be closed after the read was finished.

func (*Cache) GetBytes

func (c *Cache) GetBytes(key string) ([]byte, bool)

GetBytes retrieves an item from the cache with a key. If found, the second return argument will be true, otherwise false.

It is equivalent to calling Get, copying the reader to the end and closing the reader. It is safe to modify the returned buffer.

func (*Cache) GetKey

func (c *Cache) GetKey(key string) bool

GetKey checks if a key is in the cache.

It is equivalent to calling Get, and closing the reader without reading from it.

func (*Cache) Set

func (c *Cache) Set(key string, ttl time.Duration) (io.WriteCloser, bool)

Set creates a cache item and returns a writer that can be used to store the associated data. The writer returns ErrItemDiscarded if the item is not available anymore, and ErrWriteLimit if the item reaches the maximum item size of the cache. The writer must be closed to indicate that no more data will be written to the item.

func (*Cache) SetBytes

func (c *Cache) SetBytes(key string, data []byte, ttl time.Duration) bool

SetBytes sets an item in the cache with a key.

It is equivalent to calling Set, writing the complete data to the item and closing the writer. It is safe to modify the buffer after SetBytes returned.

func (*Cache) SetKey

func (c *Cache) SetKey(key string, ttl time.Duration) bool

SetKey sets only a key without data.

It is equivalent to calling Set, and closing the writer without writing any data.

func (*Cache) Stats

func (c *Cache) Stats() *CacheStats

Stats returns approximate statistics about the cache state.

type CacheSpaces

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

CacheSpaces is equivalent to Cache but it supports multiple keyspaces. Keyspaces are used to identify cache items in addition to the keys. Internally, when the cache is full, the cache tries to evict items first from the same keyspace as the item currently requiring more space.

func NewCacheSpaces

func NewCacheSpaces(o Options) *CacheSpaces

NewCacheSpaces is like New() but initializes a cache that supports keyspaces.

func (*CacheSpaces) Close

func (c *CacheSpaces) Close()

Close shuts down the cache and releases resources.

func (*CacheSpaces) Delete

func (c *CacheSpaces) Delete(keyspace, key string)

Delete is like Cache.Delete but with keyspaces.

func (*CacheSpaces) Get

func (c *CacheSpaces) Get(keyspace, key string) (*Reader, bool)

Get is like Cache.Get but with keyspaces.

func (*CacheSpaces) GetBytes

func (c *CacheSpaces) GetBytes(keyspace, key string) ([]byte, bool)

GetBytes is like Cache.GetBytes but with keyspaces.

func (*CacheSpaces) GetKey

func (c *CacheSpaces) GetKey(keyspace, key string) bool

GetKey is like Cache.GetKey but with keyspaces.

func (*CacheSpaces) Set

func (c *CacheSpaces) Set(keyspace, key string, ttl time.Duration) (*Writer, bool)

Set is like Cache.Set but with keyspaces.

func (*CacheSpaces) SetBytes

func (c *CacheSpaces) SetBytes(keyspace, key string, data []byte, ttl time.Duration) bool

SetBytes is like Cache.SetBytes but with keyspaces.

func (*CacheSpaces) SetKey

func (c *CacheSpaces) SetKey(keyspace, key string, ttl time.Duration) bool

SetKey is like Cache.SetKey but with keyspaces.

func (*CacheSpaces) Stats

func (c *CacheSpaces) Stats() *CacheStats

Stats returns approximate statistics about the cache state.

type CacheStats

type CacheStats struct {

	// Total contains statistics about the cache.
	Total *Stats

	// AvailableMemory tells how much memory is available in the cache for new items or for further writing.
	AvailableMemory int

	// Keyspaces contain statistics split by keyspaces in the cache.
	Keyspaces map[string]*Stats
}

CacheStats objects contain statistics about the cache including the keyspaces.

type Event

type Event struct {

	// Type indicates the reason of the event.
	Type EventType

	// Keyspace contains the keyspace if an event can be related to one.
	Keyspace string

	// Key contains the key of the item if an event is related to a single item.
	Key string

	// EffectiveSizeChange contains the net size change caused by the event.
	EffectiveSizeChange int

	// UsedSizeChange contains the size change caused by the event, calculated based on the freed or
	// allocated chunks.
	UsedSizeChange int
}

Event objects describe an internal change or other event in the cache.

type EventType

type EventType int

EventType indicates the nature of a notification event. It is also used to mask which events should trigger a notification.

const (

	// Hit events are sent when a cache item was hit.
	Hit EventType = 1 << iota

	// Miss events are sent when a cache item was missed.
	Miss

	// Set events are sent when a cache item was stored.
	Set

	// Delete events are sent when a cache item was deleted (explicitly calling Delete() or overwritten by
	// Set(), or as part of eviction caused by a Write() operation on an item).
	Delete

	// WriteComplete events are sent when a cache item's write is finished.
	WriteComplete

	// Expire events are sent when a cache item was detected to be expired. Always together with Miss, and
	// if delete is not blocked due to active readers, also with Delete.
	Expire

	// Evict events are sent when a cache item was evicted from the cache. Always together with Delete.
	Evict

	// AllocFailed events are sent when allocation for a new item or when writing to an item couldn't complete.
	AllocFailed

	// Normal mask for receiving moderate level of notifications.
	Normal = Evict | AllocFailed

	// Verbose mask for receiving verbose level of notifications.
	Verbose = Miss | Normal

	// All mask for receiving all possible notifications.
	All = Hit | Set | Delete | WriteComplete | Expire | Verbose
)

func (EventType) String

func (et EventType) String() string

String returns the string representation of an EventType value, listing all the flags that are set.

type Options

type Options struct {

	// CacheSize defines the size of the cache.
	CacheSize int

	// ChunkSize defines the chunk size in the memory.
	ChunkSize int

	// Notify is used by the cache to send notifications about internal events. When nil, no notifications are
	// sent. It is recommended to use a channel with a small buffer, e.g. 2. Make sure that the channel is
	// continuously consumed when set. Be aware that when the channel is not nil, and the mask is 0, the
	// default mask is applied.
	Notify chan<- *Event

	// NotifyMask can be used to select which event types should trigger a notification. The default is Normal,
	// meaning that evictions and allocation failures will trigger a notification.
	NotifyMask EventType
	// contains filtered or unexported fields
}

Options objects are used to pass in parameters to new Cache instances.

type Reader

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

Reader objects are used to read data from a cache item.

func (*Reader) Close

func (r *Reader) Close() error

Close releases the reader. When there are items marked internally for delete, and no more readers are attached to them, those items will become available for delete at the time of the next cache eviction of the same segment.

func (*Reader) Read

func (r *Reader) Read(p []byte) (int, error)

Read reads from an item at the current position. If 0 bytes were read and the item is still being written, it blocks.

func (*Reader) Seek

func (r *Reader) Seek(offset int64, whence int) (int64, error)

Seek moves the current position of the reader by offset counted from whence, which can be io.SeekStart, io.SeekCurrent or io.SeekEnd. When the write to the item is incomplete, it is an error to use io.SeekEnd. When the targeted position is beyond the current size of the item, and the write is incomplete, Seek blocks, while if the write is complete, it returns an error.

type Stats

type Stats struct {

	// ItemCount indicates the number of stored items.
	ItemCount int

	// EffectiveSize indicates the net size of the stored items.
	EffectiveSize int

	// UsedSize indicates the total size of the used chunks.
	UsedSize int

	// Readers indicates how many readers were creaetd and not yet finished (closed).
	Readers int

	// MarkedDeleted indicates how many readers were created whose items were deleted since then but the
	// readers are still not done.
	MarkedDeleted int

	// Writers indicates how many writers were created and not yet completed (closed).
	Writers int

	// WritersBlocked indicates how many writers were created whose write is blocked due to active readers
	// preventing eviction.
	WritersBlocked int
}

Stats objects contain statistics about the cache and keyspaces.

type Writer

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

Writer objects are used to fill cache items.

func (*Writer) Close

func (w *Writer) Close() error

Close releases the writer signaling write done internally. Readers, that attached to the same cache item and blocked by trying to read beyond the available item size, get unblocked at this point.

func (*Writer) Write

func (w *Writer) Write(p []byte) (int, error)

Write fills a cache item. If the writer was closed or the max item size was reached, it returns an error. If the last chunk of the item is full, it tries to allocate a new chunk. If allocation fails due to too many active readers, the write blocks until allocation becomes possible.