lru

package
v1.2.0 Latest Latest
Warning

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

 Go to latest Published: Aug 15, 2025 License: Apache-2.0 Imports: 29 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var ErrRefreshUpstreamBadStatusCode = errors.New("invalid upstream status code")

Functions

This section is empty.

Types

type Balance 

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

Balance maintains per-Shard LRUStorage lists and provides efficient selection of loaded shards for eviction. - memList orders shardNodes by usage (most loaded in front). - shards is a flat array for O(1) access by Shard index. - shardedMap is the underlying data storage (map of all entries).

func NewBalancer 

func NewBalancer(ctx context.Context, shardedMap *sharded.Map[*model.Entry]) *Balance

NewBalancer creates a new Balance instance and initializes memList.

func (*Balance) FindVictim 

func (b *Balance) FindVictim(shardKey uint64) (*model.Entry, bool)

func (*Balance) Mem added in v0.9.3 

func (b *Balance) Mem() int64

func (*Balance) MostLoaded added in v1.0.1 

func (b *Balance) MostLoaded(offset int) (*ShardNode, bool)

MostLoaded returns the first non-empty Shard node from the front of memList, optionally skipping a number of nodes by offset (for concurrent eviction fairness).

func (*Balance) Push added in v1.0.1 

func (b *Balance) Push(entry *model.Entry)

Push inserts a response into the appropriate Shard's LRUStorage list and updates counters. Returns the affected ShardNode for further operations.

func (*Balance) Rebalance 

func (b *Balance) Rebalance()

func (*Balance) Register 

func (b *Balance) Register(shard *sharded.Shard[*model.Entry])

Register inserts a new ShardNode for a given Shard, creates its LRUStorage, and adds it to memList and shards array.

func (*Balance) Remove 

func (b *Balance) Remove(shardKey uint64, el *list.Element[*model.Entry])

func (*Balance) Update 

func (b *Balance) Update(existing *model.Entry)

type Balancer 

type Balancer interface {
	Rebalance()
	Mem() int64
	Register(shard *sharded.Shard[*model.Entry])
	Push(entry *model.Entry)
	Update(existing *model.Entry)
	Remove(shardKey uint64, el *list.Element[*model.Entry])
	MostLoaded(offset int) (*ShardNode, bool)
	FindVictim(shardKey uint64) (*model.Entry, bool)
}

type Dump added in v1.1.1 

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

func NewDumper added in v1.1.1 

func NewDumper(cfg config.Config, storage Storage, backend upstream.Upstream) *Dump

func (*Dump) Dump added in v1.1.1 

func (d *Dump) Dump(ctx context.Context) error

func (*Dump) Load added in v1.1.1 

func (d *Dump) Load(ctx context.Context) error

func (*Dump) LoadVersion added in v1.1.1 

func (d *Dump) LoadVersion(ctx context.Context, v string) error

type Dumper added in v1.1.1 

type Dumper interface {
	Dump(ctx context.Context) error
	Load(ctx context.Context) error
	LoadVersion(ctx context.Context, v string) error
}

type Evict added in v0.9.8 

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

func NewEvictor added in v0.9.8 

func NewEvictor(ctx context.Context, cfg config.Config, db Storage, balancer Balancer) *Evict

func (*Evict) Run added in v0.9.8 

func (e *Evict) Run()

Run is the main background eviction loop for one worker. Each worker tries to bring Weight usage under the threshold by evicting from most loaded shards.

func (*Evict) ShouldEvict added in v0.9.8 

func (e *Evict) ShouldEvict() bool

ShouldEvict [HOT PATH METHOD] (max stale value = 25ms) checks if current Weight usage has reached or exceeded the threshold.

type EvictionStat added in v0.9.8 

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

EvictionStat carries statistics for each eviction batch.

type Evictor added in v0.9.8 

type Evictor interface {
	Run()
}

type InMemoryStorage added in v1.0.1 

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

InMemoryStorage is a Weight-aware, sharded InMemoryStorage cache with background eviction and refreshItem support.

func NewStorage 

func NewStorage(ctx context.Context, cfg config.Config, upstream upstream.Upstream) *InMemoryStorage

NewStorage constructs a new InMemoryStorage cache instance and launches eviction and refreshItem routines.

func (*InMemoryStorage) Clear added in v1.0.1 

func (s *InMemoryStorage) Clear()

func (*InMemoryStorage) Close added in v1.1.1 

func (s *InMemoryStorage) Close() error

func (*InMemoryStorage) Dump added in v1.1.1 

func (s *InMemoryStorage) Dump(ctx context.Context) error

func (*InMemoryStorage) Get added in v1.0.1 

func (s *InMemoryStorage) Get(req *model.Entry) (ptr *model.Entry, found bool)

Get retrieves a response by request and bumps its InMemoryStorage position. Returns: (response, releaser, found).

func (*InMemoryStorage) Len added in v1.0.1 

func (s *InMemoryStorage) Len() int64

func (*InMemoryStorage) Load added in v1.1.1 

func (s *InMemoryStorage) Load(ctx context.Context) error

func (*InMemoryStorage) LoadVersion added in v1.1.1 

func (s *InMemoryStorage) LoadVersion(ctx context.Context, v string) error

func (*InMemoryStorage) Mem added in v1.0.1 

func (s *InMemoryStorage) Mem() int64

func (*InMemoryStorage) Rand added in v1.0.1 

func (s *InMemoryStorage) Rand() (entry *model.Entry, ok bool)

Rand returns a random item from storage.

func (*InMemoryStorage) RealLen added in v1.0.1 

func (s *InMemoryStorage) RealLen() int64

func (*InMemoryStorage) RealMem added in v1.0.1 

func (s *InMemoryStorage) RealMem() int64

func (*InMemoryStorage) Remove added in v1.0.1 

func (s *InMemoryStorage) Remove(entry *model.Entry) (freedBytes int64, hit bool)

func (*InMemoryStorage) Run added in v1.0.3 

func (s *InMemoryStorage) Run()

func (*InMemoryStorage) Set added in v1.0.1 

func (s *InMemoryStorage) Set(new *model.Entry) (persisted bool)

Set inserts or updates a response in the cache, updating Weight usage and InMemoryStorage position. On 'wasPersisted=true' must be called Entry.Finalize, otherwise Entry.Finalize.

func (*InMemoryStorage) ShouldEvict added in v1.0.1 

func (s *InMemoryStorage) ShouldEvict() bool

ShouldEvict [HOT PATH METHOD] (max stale value = 25ms) checks if current Weight usage has reached or exceeded the threshold.

func (*InMemoryStorage) Stat added in v1.0.1 

func (s *InMemoryStorage) Stat() (bytes int64, length int64)

func (*InMemoryStorage) WalkShards added in v1.0.1 

func (s *InMemoryStorage) WalkShards(ctx context.Context, fn func(key uint64, shard *sharded.Shard[*model.Entry]))

type Refresh added in v1.0.1 

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

Refresh is responsible for background refreshing of cache entries. It periodically samples random shards and randomly selects "cold" entries (from the end of each shard's InMemoryStorage list) to refreshItem if necessary. Communication: provider->consumer (MPSC).

func NewRefresher added in v1.0.1 

func NewRefresher(ctx context.Context, cfg config.Config, storage Storage, upstream upstream.Upstream) *Refresh

NewRefresher constructs a Refresh.

func (*Refresh) Run added in v1.0.1 

func (r *Refresh) Run()

Run starts the refresher background loop. It runs a logger (if debugging is enabled), spawns a provider for sampling shards, and continuously processes shard samples for candidate responses to refreshItem.

type Refresher added in v1.0.1 

type Refresher interface {
	Run()
}

type ShardNode 

type ShardNode struct {
	Shard *sharded.Shard[*model.Entry] // Reference to the actual Shard (map + sync)
	// contains filtered or unexported fields
}

ShardNode represents a single Shard's LRUStorage and accounting info. Each Shard has its own LRUStorage list and a pointer to its element in the balancer's memList.

func (*ShardNode) LruList 

func (s *ShardNode) LruList() *list.List[*model.Entry]

func (*ShardNode) Weight 

func (s *ShardNode) Weight() int64

Weight returns an approximate Weight usage of this ShardNode structure.

type Storage 

type Storage interface {
	Run()
	Close() error

	// Get attempts to retrieve a cached response for the given request.
	// Returns the response, a releaser for safe concurrent access, and a hit/miss flag.
	Get(*model.Entry) (entry *model.Entry, hit bool)

	// Set stores a new response in the cache and returns a releaser for managing resource lifetime.
	// 1. You definitely cannot use 'inEntry' after use in Set due to it can be removed, you will receive a cache entry on hit!
	// 2. Use Release and Remove for manage Entry lifetime.
	Set(inEntry *model.Entry) (persisted bool)

	// Remove is removes one element.
	Remove(*model.Entry) (freedBytes int64, hit bool)

	// Clear is removes all cache entries from the storage.
	Clear()

	// Stat returns bytes usage and num of items in storage.
	Stat() (bytes int64, length int64)

	// Len - return stored value (refreshes every 100ms).
	Len() int64

	RealLen() int64

	// Mem - return stored value (refreshes every 100ms).
	Mem() int64

	// RealMem - calculates and return value.
	RealMem() int64

	// Rand returns a random elem from the map.
	Rand() (entry *model.Entry, ok bool)

	WalkShards(ctx context.Context, fn func(key uint64, shard *sharded.Shard[*model.Entry]))

	// Dumper functionality
	Dump(ctx context.Context) error
	Load(ctx context.Context) error
	LoadVersion(ctx context.Context, v string) error
}

Storage is a generic interface for cache storages. It supports typical Get/Set operations with reference management.

Source Files

View all Source files

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.