lru

README

lru

Package lru provides generic type and concurrent safe LRU data structures with near O(1) perf and optional time-based expiration support.

Overview

A basic least recently used (LRU) cache is a cache that holds a limited number of items with an eviction policy such that when the capacity of the cache is exceeded, the least recently used item is automatically removed when inserting a new item. The meaning of used in this implementation is accessing items via lookups, adding items, and updating existing items.

This package provides two similar full-featured implementations named Set and Map which implement the aforementioned LRU cache semantics in addition to providing optional configurable per-item expiration timeouts via a time to live (TTL) mechanism.

The primary difference between the two is that Set is tailored towards use cases that involve storing a distinct collection of items with existence testing, while Map is aimed at use cases that require caching and retrieving values by key.

Both implementations are based on type safe generics and are safe for use in multi-threaded (concurrent) workloads.

Item Expiration

Both Set and Map support optional configurable default TTLs for item expiration as well as provide the option to override the default TTL on a per-item basis.

Expiration TTLs are relative to the time an item is added or updated via Put or PutWithTTL. Accessing items does not extend the TTL.

An efficient lazy removal scheme is used such that expired items are periodically removed when items are added or updated via Put or PutWithTTL. In other words, items may physically remain in the cache past their expiration until the next expiration scan is triggered, however, they will no longer publicly appear as members of the cache. This approach allows for efficient amortized removal of expired items without the need for additional background tasks or timers.

While it is expected that most callers will typically use the automatic lazy expiration behavior, callers may optionally use EvictExpiredNow to immediately remove all items that are marked expired without waiting for the next expiration scan in cases where more deterministic expiration is required.

Creating Instances and Configuring TTLs

NewSet and NewMap create instances of the respective type that impose no item expiration by default. Alternatively, NewSetWithDefaultTTL and NewMapWithDefaultTTL create instances with the specified TTL applied to all items by default.

In all cases, Put adds or updates an item per the default TTL specified when creating the instance while PutWithTTL allows overriding the default TTL of the individual item.

Invoking PutWithTTL with a TTL of zero will disable expiration for the item. This feature is useful to disable the expiration for specific items when the instance was configured with a default expiration TTL.

Accessing and Querying Items and Values

Typically, callers will want to make use of Contains to determine set membership for Set and Get to access the value associated with a given key for Map. Both of these methods impose LRU semantics meaning they modify the priority of the accessed items so they will be evicted after less recently used items. They also both affect the hit ratio.

However, it is sometimes useful to access information without affecting any state. With that in mind, Exists, Peek, Keys, Values, and Items are also provided. Since these methods do not update any state, the priority of the items accessed via the methods is not modified and the hit ratio is unaffected.

Manually Removing Items

Delete may be used to manually remove individual items at any time and Clear completely empties all items.

Hit Ratio Reporting

A hit ratio is the percentage of overall lookups that resulted in a successful hit and is often a useful metric to measure cache effectiveness.

The hit ratio for a given instance may be obtained via HitRatio.

Benchmarks

The following results demonstrate the performance of the primary map and set operations. The benchmarks are from a Ryzen 7 5800X3D processor.

Operation	Time / Op	Allocs / Op
MapPut (no expiration)	108ns ± 2%	0
MapPut (with expiration)	110ns ± 1%	0
MapGet	40.9ns ± 1%	0
MapExists	34.2ns ± 2%	0
MapPeek	37.6ns ± 0%	0
SetPut (no expiration)	109ns ± 2%	0
SetPut (with expiration)	110ns ± 1%	0
SetContains	41.4ns ± 3%	0
SetExists	34.7ns ± 1%	0

Installation and Updating

This package is part of the github.com/decred/dcrd/container/lru module. Use the standard go tooling for working with modules to incorporate it.

Examples

• Basic Map Usage Demonstrates creating a new map instance, inserting items into the map, existence checking, looking up an item, causing an eviction of the least recently used item, and removing an item.
• Explicit Map Expiration Demonstrates creating a new map instance with time-based expiration, inserting items into it, and manually triggering removal of expired items.
• Basic Set Usage Demonstrates creating a new set instance, inserting items into the set, checking set containment, causing an eviction of the least recently used item, and removing an item.
• Per-Item Expiration Demonstrates per-item expiration by creating a new set instance with no time-based expiration, inserting items into it, updating one of the items to have a timeout, and manually triggering removal of expired item.

License

Package lru is licensed under the copyfree ISC License.

Documentation

Overview

Package lru provides generic type and concurrent safe LRU data structures with near O(1) perf and optional time-based expiration support.

Example (BasicMapUsage)

This example demonstrates creating a new map instance, inserting items into the map, existence checking, looking up an item, causing an eviction of the least recently used item, and removing an item.

package main

import (
	"fmt"

	"github.com/decred/dcrd/container/lru"
)

func main() {
	// Create a new map instance with the desired limit and no time-based
	// expiration of items.
	const maxItems = 10
	m := lru.NewMap[int, int](maxItems)

	// Insert items into the map.
	for i := 0; i < maxItems; i++ {
		m.Put(i, (i+1)*100)
	}

	// At this point, the map has reached the limit, so the first entry will
	// still be a member.
	if !m.Exists(0) {
		fmt.Println("map does not contain expected item 0")
		return
	}

	// Lookup an item.
	if v, ok := m.Get(0); !ok || v != 100 {
		fmt.Println("map does not contain expected value for item 0")
		return
	}

	// Inserting another item will evict the least recently used item, which
	// will be the item with key 1 since 0 was just accessed above.
	const oneOverMax = maxItems + 1
	numEvicted := m.Put(oneOverMax, oneOverMax)
	if numEvicted != 1 {
		fmt.Printf("expected one evicted item, but got %d", numEvicted)
		return
	}
	if m.Exists(1) {
		fmt.Println("map contains unexpected item 1")
		return
	}

	// Remove an item.
	m.Delete(3)
	if m.Exists(3) {
		fmt.Println("map contains unexpected item 3")
		return
	}

}

Example (BasicSetUsage)

This example demonstrates creating a new set instance, inserting items into the set, checking set containment, causing an eviction of the least recently used item, and removing an item.

package main

import (
	"fmt"

	"github.com/decred/dcrd/container/lru"
)

func main() {
	// Create a new set instance with the desired limit and no time-based
	// expiration of items.
	const maxItems = 10
	set := lru.NewSet[int](maxItems)

	// Insert items into the set.
	for i := 0; i < maxItems; i++ {
		set.Put(i)
	}

	// At this point, the set has reached the limit, so the first entry will
	// still be a member.  Note that Exists does not update any state so it
	// will not modify the eviction priority or the hit ratio.
	if !set.Exists(0) {
		fmt.Println("set does not contain expected item 0")
		return
	}

	// Check set containment.  This modifies the priority to be the most
	// recently used item so it will be evicted last.
	if !set.Contains(0) {
		fmt.Println("set does not contain expected item 0")
		return
	}

	// Inserting another item will evict the least recently used item, which
	// will be the item 1 since item 0 was just accessed via Contains.
	numEvicted := set.Put(maxItems + 1)
	if numEvicted != 1 {
		fmt.Printf("expected one evicted item, but got %d", numEvicted)
		return
	}
	if set.Exists(1) {
		fmt.Println("set contains unexpected item 1")
		return
	}

	// Remove an item.
	set.Delete(3)
	if set.Exists(3) {
		fmt.Println("set contains unexpected item 3")
		return
	}

}

Index

• type Map
  • func NewMap[K comparable, V any](limit uint32) *Map[K, V]
  • func NewMapWithDefaultTTL[K comparable, V any](limit uint32, ttl time.Duration) *Map[K, V]
  • func (m *Map[K, V]) Clear()
  • func (m *Map[K, V]) Delete(key K)
  • func (m *Map[K, V]) EvictExpiredNow() (numEvicted uint32)
  • func (m *Map[K, V]) Exists(key K) bool
  • func (m *Map[K, V]) Get(key K) (V, bool)
  • func (m *Map[K, V]) HitRatio() float64
  • func (m *Map[K, V]) Keys() []K
  • func (m *Map[K, V]) Len() uint32
  • func (m *Map[K, V]) Peek(key K) (V, bool)
  • func (m *Map[K, V]) Put(key K, value V) (numEvicted uint32)
  • func (m *Map[K, V]) PutWithTTL(key K, value V, ttl time.Duration) (numEvicted uint32)
  • func (m *Map[K, V]) Values() []V
• type Set
  • func NewSet[T comparable](limit uint32) *Set[T]
  • func NewSetWithDefaultTTL[T comparable](limit uint32, ttl time.Duration) *Set[T]
  • func (c *Set[T]) Clear()
  • func (c *Set[T]) Contains(item T) bool
  • func (c *Set[T]) Delete(item T)
  • func (c *Set[T]) EvictExpiredNow() (numEvicted uint32)
  • func (c *Set[T]) Exists(item T) bool
  • func (c *Set[T]) HitRatio() float64
  • func (c *Set[T]) Items() []T
  • func (c *Set[T]) Len() uint32
  • func (c *Set[T]) Put(item T) (numEvicted uint32)
  • func (c *Set[T]) PutWithTTL(item T, ttl time.Duration) (numEvicted uint32)

Examples

• Package (BasicMapUsage)
• Package (BasicSetUsage)
• Map.EvictExpiredNow
• Set.PutWithTTL

Types

type Map

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

Map provides a concurrency safe least recently used (LRU) map with nearly O(1) lookups, inserts, and deletions. The map is limited to a maximum number of items with eviction of the least recently used entry when the limit is exceeded.

It also supports optional item expiration after a configurable time to live (TTL) with periodic lazy removal. NewMap provides no item expiration by default while NewMapWithDefaultTTL provides a configurable TTL that is applied to all items by default. In both cases, callers may override the default TTL of individual items via [PutWithTTL].

Expiration TTLs are relative to the time an item is added or updated via [Put] or [PutWithTTL]. Accessing items does not extend the TTL.

An efficient lazy removal scheme is used such that expired items are periodically removed when items are added or updated via [Put] or [PutWithTTL]. In other words, expired items may physically remain in the map until the next expiration scan is triggered, however, they will no longer publicly appear as members of the map. This approach allows for efficient amortized removal of expired items without the need for additional background tasks or timers.

Callers may optionally use [EvictExpiredNow] to immediately remove all items that are marked expired without waiting for the next expiration scan in cases where more deterministic expiration is required.

NewMap or NewMapWithDefaultTTL must be used to create a usable map since the zero value of this struct is not valid.

func NewMap

func NewMap[K comparable, V any](limit uint32) *Map[K, V]

NewMap returns an initialized and empty LRU map where no items will expire by default.

The provided limit is the maximum number of items the map will hold before it evicts least recently used items to make room for new items.

See NewMapWithDefaultTTL for a variant that allows a configurable time to live to be applied to all items by default.

See the documentation for Map for more details.

func NewMapWithDefaultTTL

func NewMapWithDefaultTTL[K comparable, V any](limit uint32, ttl time.Duration) *Map[K, V]

NewMapWithDefaultTTL returns an initialized and empty LRU map where the provided non-zero time to live (TTL) is applied to all items by default.

A TTL of zero disables item expiration by default and is equivalent to NewMap.

See NewMap for a variant that does not expire any items by default.

See the documentation for Map for more details.

func (*Map[K, V]) Clear

func (m *Map[K, V]) Clear()

Clear removes all items and resets the hit ratio.

This function is safe for concurrent access.

func (*Map[K, V]) Delete

func (m *Map[K, V]) Delete(key K)

Delete deletes the item associated with the passed key if it exists.

This function is safe for concurrent access.

func (*Map[K, V]) EvictExpiredNow

func (m *Map[K, V]) EvictExpiredNow() (numEvicted uint32)

EvictExpiredNow immediately removes all items that are marked expired without waiting for the next expiration scan. It returns the number of items that were removed.

It is expected that most callers will typically use the automatic lazy expiration behavior and thus have no need to call this method. However, it is provided in case more deterministic expiration is required.

Example

This example demonstrates creating a new map instance with time-based expiration, inserting items into it, and manually triggering removal of expired items.

package main

import (
	"fmt"
	"time"

	"github.com/decred/dcrd/container/lru"
)

func main() {
	// Create a new map instance with the desired limit and a time-based
	// expiration of items for one millisecond.  Callers would typically want to
	// use much longer durations.
	const maxItems = 10
	const ttl = time.Millisecond
	m := lru.NewMapWithDefaultTTL[string, string](maxItems, ttl)

	// Insert an item, wait for the item to expire, and remove expired items.
	//
	// Ordinarily, callers do not need to explicitly call the removal method
	// since expired items are periodically removed as items are added and
	// updated.  However, it is done here for the purposes of the example.
	const key = "foo"
	m.Put(key, "bar")
	time.Sleep(ttl * 2)
	numEvicted := m.EvictExpiredNow()
	if numEvicted != 1 {
		fmt.Printf("expected one evicted item, but got %d", numEvicted)
		return
	}
	if m.Exists(key) {
		fmt.Printf("map contains unexpected expired item %q\n", key)
		return
	}

}

func (*Map[K, V]) Exists

func (m *Map[K, V]) Exists(key K) bool

Exists returns whether or not the passed item is a member. The priority and expiration time for the item are not modified. It does not affect the hit ratio.

This function is safe for concurrent access.

func (*Map[K, V]) Get

func (m *Map[K, V]) Get(key K) (V, bool)

Get returns the value associated with the passed key if it is a member and modifies its priority to be the most recently used item. The expiration time for the item is not modified.

The boolean return value indicates whether or not the item lookup was successful.

See [Peek] for a variant that does not modify the priority or update the hit ratio.

This function is safe for concurrent access.

func (*Map[K, V]) HitRatio

func (m *Map[K, V]) HitRatio() float64

HitRatio returns the percentage of lookups via [Get] that resulted in a successful hit.

This function is safe for concurrent access.

func (*Map[K, V]) Keys

func (m *Map[K, V]) Keys() []K

Keys returns a slice of unexpired keys ordered from least recently used to most recently used. The priority and expiration times for the items are not modified.

This function is safe for concurrent access.

func (*Map[K, V]) Len

func (m *Map[K, V]) Len() uint32

Len returns the number of items in the map.

This function is safe for concurrent access.

func (*Map[K, V]) Peek

func (m *Map[K, V]) Peek(key K) (V, bool)

Peek returns the associated value of the passed key if it is a member without modifying any priority or the hit ratio. The boolean return value indicates whether or not the item lookup is successful.

This function is safe for concurrent access.

func (*Map[K, V]) Put

func (m *Map[K, V]) Put(key K, value V) (numEvicted uint32)

Put either adds the passed key/value pair when an item for that key does not already exist or updates the existing item for the given key to the passed value and arranges for the item to expire after the configured default TTL (if any). The associated item becomes the most recently used item.

The least recently used item is evicted when adding a new item would exceed the max limit.

It returns the number of evicted items which includes any items that were evicted due to being marked expired.

See [PutWithTTL] for a variant that allows setting a specific TTL for the item.

This function is safe for concurrent access.

func (*Map[K, V]) PutWithTTL

func (m *Map[K, V]) PutWithTTL(key K, value V, ttl time.Duration) (numEvicted uint32)

PutWithTTL either adds the passed key/value pair when an item for that key does not already exist or updates the existing item for the given key to the passed value and arranges for the item to expire after the provided time to live (TTL). The associated item becomes the most recently used item.

The least recently used item is evicted when adding a new item would exceed the max limit.

A TTL of zero will disable expiration for the item. This can be useful to disable the expiration for specific items when the map was configured with a default expiration TTL.

It returns the number of evicted items which includes any items that were evicted due to being marked expired.

This function is safe for concurrent access.

func (*Map[K, V]) Values

func (m *Map[K, V]) Values() []V

Values returns a slice of unexpired values ordered from least recently used to most recently used. The priority and expiration times for the items are not modified.

This function is safe for concurrent access.

type Set

type Set[T comparable] struct {
	// contains filtered or unexported fields
}

Set provides a concurrency safe least recently used (LRU) set with nearly O(1) lookups, inserts, and deletions. The set is limited to a maximum number of items with eviction of the least recently used entry when the limit is exceeded.

It also supports optional item expiration after a configurable time to live (TTL) with periodic lazy removal. NewSet provides no item expiration by default while NewSetWithDefaultTTL provides a configurable TTL that is applied to all items by default. In both cases, callers may override the default TTL of individual items via [PutWithTTL].

Expiration TTLs are relative to the time an item is added or updated via [Put] or [PutWithTTL]. Accessing items does not extend the TTL.

An efficient lazy removal scheme is used such that expired items are periodically removed when items are added or updated via [Put] or [PutWithTTL]. In other words, expired items may physically remain in the set until the next expiration scan is triggered, however, they will no longer publicly appear as members of the set. This approach allows for efficient amortized removal of expired items without the need for additional background tasks or timers.

Callers may optionally use [EvictExpiredNow] to immediately remove all items that are marked expired without waiting for the next expiration scan in cases where more deterministic expiration is required.

NewSet or NewSetWithDefaultTTL must be used to create a usable set since the zero value of this struct is not valid.

func NewSet

func NewSet[T comparable](limit uint32) *Set[T]

NewSet returns an initialized and empty LRU set where no items will expire by default.

The provided limit is the maximum number of items the set will hold before it evicts least recently used items to make room for new items.

See NewSetWithDefaultTTL for a variant that allows a configurable time to live to be applied to all items by default.

See the documentation for Set for more details.

func NewSetWithDefaultTTL

func NewSetWithDefaultTTL[T comparable](limit uint32, ttl time.Duration) *Set[T]

NewSetWithDefaultTTL returns an initialized and empty LRU set where the provided non-zero time to live (TTL) is applied to all items by default.

A TTL of zero disables item expiration by default and is equivalent to NewSet.

See NewSet for a variant that does not expire any items by default.

See the documentation for Set for more details.

func (*Set[T]) Clear

func (c *Set[T]) Clear()

Clear removes all items and resets the hit ratio.

This function is safe for concurrent access.

func (*Set[T]) Contains

func (c *Set[T]) Contains(item T) bool

Contains returns whether or not the passed item is a member and modifies its priority to be the most recently used item when it is. The expiration time for the item is not modified. The hit ratio is updated accordingly.

See [Exists] for a variant that does not modify the priority of the item or update the hit ratio.

This function is safe for concurrent access.

func (*Set[T]) Delete

func (c *Set[T]) Delete(item T)

Delete deletes the passed item if it exists.

This function is safe for concurrent access.

func (*Set[T]) EvictExpiredNow

func (c *Set[T]) EvictExpiredNow() (numEvicted uint32)

EvictExpiredNow immediately removes all items that are marked expired without waiting for the next expiration scan. It returns the number of items that were removed.

It is expected that most callers will typically use the automatic lazy expiration behavior and thus have no need to call this method. However, it is provided in case more deterministic expiration is required.

func (*Set[T]) Exists

func (c *Set[T]) Exists(item T) bool

Exists returns whether or not the passed item is a member. The priority and expiration time for the item are not modified. It does not affect the hit ratio.

See [Contains] for a variant that modifies the priority of the item to be the most recently used item when it exists and updates the hit ratio accordingly.

This function is safe for concurrent access.

func (*Set[T]) HitRatio

func (c *Set[T]) HitRatio() float64

HitRatio returns the percentage of lookups via [Contains] that resulted in a successful hit.

This function is safe for concurrent access.

func (*Set[T]) Items

func (c *Set[T]) Items() []T

Items returns a slice of unexpired items ordered from least recently used to most recently used. The priority and expiration times for the items are not modified.

This function is safe for concurrent access.

func (*Set[T]) Len

func (c *Set[T]) Len() uint32

Len returns the number of items in the set.

This function is safe for concurrent access.

func (*Set[T]) Put

func (c *Set[T]) Put(item T) (numEvicted uint32)

Put either adds the passed item when it does not already exist or refreshes the existing item and arranges for the item to expire after the configured default TTL (if any). The item becomes the most recently used item.

The least recently used item is evicted when adding a new item would exceed the max limit.

It returns the number of evicted items which includes any items that were evicted due to being marked expired.

See [PutWithTTL] for a variant that allows configuring a specific TTL for the item.

This function is safe for concurrent access.

func (*Set[T]) PutWithTTL

func (c *Set[T]) PutWithTTL(item T, ttl time.Duration) (numEvicted uint32)

PutWithTTL either adds the passed item when it does not already exist or refreshes the existing item and arranges for the item to expire after the provided time to live (TTL). The item becomes the most recently used item.

The least recently used item is evicted when adding a new item would exceed the max limit.

A TTL of zero will disable expiration for the item. This can be useful to disable the TTL for specific items when the set was configured with a default expiration TTL.

It returns the number of evicted items which includes any items that were evicted due to being marked expired.

This function is safe for concurrent access.

Example

This example demonstrates per-item expiration by creating a new set instance with no time-based expiration, inserting items into it, updating one of the items to have a timeout, and manually triggering removal of expired item.

package main

import (
	"fmt"
	"time"

	"github.com/decred/dcrd/container/lru"
)

func main() {
	// Create a new set instance with the desired limit and no time-based
	// expiration of items.
	const maxItems = 10
	set := lru.NewSet[int](maxItems)

	// Insert items into the set.
	for i := 0; i < maxItems; i++ {
		set.Put(i)
	}

	// Update item 1 to expire after one millisecond, wait for the item to
	// expire, and remove expired items.  Callers would typically want to use
	// much longer durations.
	//
	// Since all of the other items are not set to expire by default, only the
	// single item updated to have a TTL will be expired.
	//
	// Ordinarily, callers do not need to explicitly call the removal method
	// since expired items are periodically removed as items are added and
	// updated.  However, it is done here for the purposes of the example.
	const ttl = time.Millisecond
	numEvicted := set.PutWithTTL(1, ttl)
	if numEvicted != 0 {
		fmt.Printf("expected no evicted items, but got %d", numEvicted)
		return
	}
	time.Sleep(ttl * 2)
	numEvicted = set.EvictExpiredNow()
	if numEvicted != 1 {
		fmt.Printf("expected one evicted item, but got %d", numEvicted)
		return
	}

}