Documentation
¶
Overview ¶
Package cache provides a lock-free adaptive in-memory cache implementation. CloxCache uses protected-freq eviction: items with high frequency are protected, with LRU as a tiebreaker among same-frequency items.
Boundary conditions on the policy's edge over plain LRU (measured against offline Belady replay; see trace_replay_test.go): the win lives at cache-size/working-set ratios of roughly 0.3–0.8. Below ~0.25 every policy produces near-identical contents (the cache fully flushes each cycle); above ~1 plain recency already retains the working set. Any hot tier above this cache (a client cache, CDN, an L1) skims precisely the frequency skew protection feeds on, so the policy's value concentrates in whatever skew the residual traffic still carries and shrinks toward LRU-parity as upper tiers deepen. Benchmark claims should state these conditions.
Index ¶
- func FormatMemory(bytes uint64) string
- func GetAvailableMemory() uint64
- func GetProcessRSS() uint64
- func HashKey[K Key](key K) uint64
- type AdaptiveStats
- type Cache
- type CloxCache
- func (c *CloxCache[K, V]) AverageK() float64
- func (c *CloxCache[K, V]) AverageLearnedThresholds() (rateLow, rateHigh float64)
- func (c *CloxCache[K, V]) Bytes() int64
- func (c *CloxCache[K, V]) Capacity() int
- func (c *CloxCache[K, V]) Close()
- func (c *CloxCache[K, V]) CompareAndSwap(key K, expected, new V) (swapped bool, current V, exists bool, offset uint64)
- func (c *CloxCache[K, V]) EnforceAbsoluteMemoryLimit(targetBytes, avgItemSize int64)
- func (c *CloxCache[K, V]) EnforceMemoryCapacity(memoryLimit, avgItemSize int64)
- func (c *CloxCache[K, V]) EnforceMemoryTarget(targetPercent float64, avgItemSize int64)
- func (c *CloxCache[K, V]) EntryCount() int
- func (c *CloxCache[K, V]) Evict(key K) bool
- func (c *CloxCache[K, V]) Get(key K, offset uint64) (V, bool)
- func (c *CloxCache[K, V]) GetAdaptiveStats() []AdaptiveStats
- func (c *CloxCache[K, V]) MemoryLimit() int64
- func (c *CloxCache[K, V]) Put(key K, value V) (success bool, evictedKey K, evictedOffset, putOffset uint64)
- func (c *CloxCache[K, V]) PutBack(key K, value V, oldSize int64) (success bool, offset uint64)
- func (c *CloxCache[K, V]) SetCapacity(totalCapacity int)
- func (c *CloxCache[K, V]) SetEvictDecider(fn func(key K, value V) bool)
- func (c *CloxCache[K, V]) SetEvictNotify(fn func(key K, value V))
- func (c *CloxCache[K, V]) SetSizeFunc(fn func(key K, value V) int64)
- func (c *CloxCache[K, V]) StartGhostSweeper(interval time.Duration)
- func (c *CloxCache[K, V]) Stats() (hits, misses, evictions uint64)
- type Config
- type Key
- type SizeFunc
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func FormatMemory ¶
FormatMemory formats bytes as human-readable string
func GetAvailableMemory ¶
func GetAvailableMemory() uint64
GetAvailableMemory returns the total memory available to this process. It checks (in order):
- Cgroup v2 memory limit (containers)
- Cgroup v1 memory limit (older containers)
- Total system RAM via /proc/meminfo (Linux)
- Fallback: estimate from runtime (all platforms)
func GetProcessRSS ¶
func GetProcessRSS() uint64
GetProcessRSS returns the current resident set size (actual physical memory used) of this process. Falls back to runtime.MemStats.Sys if /proc is unavailable.
Types ¶
type AdaptiveStats ¶
type AdaptiveStats struct {
ShardID int
K int32 // current protection threshold for this shard
GraduationRate float64 // fraction of items whose freq crossed the shard's k
EvictedUnprotected uint64 // items evicted with freq <= k
EvictedProtected uint64 // items evicted with freq > k (fallback)
ReachedProtected uint64 // items whose freq crossed the shard's current k
// Learned thresholds (self-tuning)
LearnedRateLow float64 // learned low threshold (rate below which k decreases)
LearnedRateHigh float64 // learned high threshold (rate above which k increases)
WindowHitRate float64 // current window hit rate
GhostCount int64 // soft-deleted leaves retained for warm restart (keytrie only; 0 for CloxCache)
}
AdaptiveStats returns per-shard adaptive threshold statistics
type Cache ¶
type Cache[K Key, V any] interface { // Get retrieves a value by key Get(key K, offset uint64) (V, bool) // Put stores a value by key Put(key K, value V) (success bool, evictedKey K, evictedOffset, putOffset uint64) // PutBack updates an existing value that was modified in place. // Unlike Put, it skips eviction logic since the item already exists. // oldSize is the size of the value before modification (for accurate byte tracking). // Returns (success, offset) - offset is the L2 storage location. PutBack(key K, value V, oldSize int64) (success bool, offset uint64) // CompareAndSwap atomically swaps the value if it matches expected (pointer equality). // Returns (swapped, currentValue, exists, offset). CompareAndSwap(key K, expected, new V) (swapped bool, current V, exists bool, offset uint64) // Stats returns hit, miss, and eviction counts Stats() (hits, misses, evictions uint64) // GetAdaptiveStats returns per-shard adaptive statistics GetAdaptiveStats() []AdaptiveStats // EntryCount returns the number of entries in the cache EntryCount() int // Bytes returns the current memory usage in bytes (requires SetSizeFunc) Bytes() int64 // MemoryLimit returns the configured memory limit in bytes (0 = unlimited) MemoryLimit() int64 // Evict removes an entry from L1 cache only. // The entry is tombstoned in place (not unlinked) for efficiency. // Returns true if the key was found and evicted. Evict(key K) bool // Close releases resources Close() }
Cache is the common interface for cache implementations.
type CloxCache ¶
CloxCache is a lock-free adaptive in-memory cache. It stores generic keys of type K (string or []byte) and values of type V.
func NewCloxCache ¶
NewCloxCache creates a new cache with the given configuration
func (*CloxCache[K, V]) AverageK ¶
AverageK returns the average protection threshold across all shards
func (*CloxCache[K, V]) AverageLearnedThresholds ¶
AverageLearnedThresholds returns the average learned rate thresholds across all shards
func (*CloxCache[K, V]) Bytes ¶
Bytes returns the current estimated bytes used by cached entries. Returns 0 if no SizeFunc was set.
func (*CloxCache[K, V]) Capacity ¶
Capacity returns the current total capacity (sum of all shard capacities).
func (*CloxCache[K, V]) Close ¶
func (c *CloxCache[K, V]) Close()
Close stops background goroutines and waits for them to exit. Safe to call multiple times.
func (*CloxCache[K, V]) CompareAndSwap ¶
func (c *CloxCache[K, V]) CompareAndSwap(key K, expected, new V) (swapped bool, current V, exists bool, offset uint64)
CompareAndSwap atomically swaps the value if it matches expected. Returns (swapped, currentValue, exists, offset). If swapped is false and exists is true, currentValue contains the actual value so the caller can retry.
func (*CloxCache[K, V]) EnforceAbsoluteMemoryLimit ¶
EnforceAbsoluteMemoryLimit starts a background goroutine that keeps the process's total memory usage at approximately targetBytes. Uses process RSS to drive capacity adjustments, sets GOMEMLIMIT, and starts the ghost sweeper.
Use this when the caller knows an exact byte budget (e.g. --maxmemory 1gb) rather than a fraction of available memory.
func (*CloxCache[K, V]) EnforceMemoryCapacity ¶
EnforceMemoryCapacity starts a background goroutine that periodically adjusts cache capacity to stay within the specified memory limit. The avgItemSize is the estimated average memory usage per item (including overhead like keys and cache node metadata). The goroutine runs every second and stops when Close() is called.
This approach avoids cache-line ping-pong that would occur if memory were tracked on every Put operation.
func (*CloxCache[K, V]) EnforceMemoryTarget ¶
EnforceMemoryTarget starts a background goroutine that keeps the process's total memory usage at approximately targetPercent of available system memory.
targetPercent is a fraction (0.0 to 1.0), e.g., 0.9 means 90%. avgItemSize is the estimated average memory per cache entry (used when sizeFunc is not set).
This also configures GOMEMLIMIT (runtime/debug.SetMemoryLimit) to the target bytes if it hasn't been explicitly set, so the Go GC cooperates with the memory target.
Designed for nearcache deployments where the cache sits beside an application and must share available memory without knowing the exact budget at startup.
func (*CloxCache[K, V]) EntryCount ¶
EntryCount returns the current number of live entries in the cache.
func (*CloxCache[K, V]) Evict ¶
Evict removes an entry from L1 cache by tombstoning it in place. The entry is made unfindable (null-prefixed key), set to low priority (freq=1), and its value is cleared. This avoids expensive chain unlinking while maintaining eviction pressure so the slot gets reclaimed. Returns true if the key was found and evicted.
func (*CloxCache[K, V]) GetAdaptiveStats ¶
func (c *CloxCache[K, V]) GetAdaptiveStats() []AdaptiveStats
GetAdaptiveStats returns adaptive threshold stats for all shards
func (*CloxCache[K, V]) MemoryLimit ¶
MemoryLimit returns the configured memory limit in bytes. Returns 0 if no limit was set via EnforceMemoryCapacity.
func (*CloxCache[K, V]) Put ¶
func (c *CloxCache[K, V]) Put(key K, value V) (success bool, evictedKey K, evictedOffset, putOffset uint64)
Put inserts or updates a value in the cache
func (*CloxCache[K, V]) PutBack ¶
PutBack updates an existing value that was modified in place. Unlike Put, it skips eviction logic since the item already has a slot. oldSize is the size of the value before modification (for accurate byte tracking). Returns (success, slot, offset) - for CloxCache, slot/offset are always 0 (no L2).
func (*CloxCache[K, V]) SetCapacity ¶
SetCapacity adjusts the total cache capacity. The new capacity is distributed evenly across shards. Reducing capacity may trigger evictions on subsequent operations.
func (*CloxCache[K, V]) SetEvictDecider ¶
SetEvictDecider installs an optional veto for eviction victim selection. The function is called under the shard mutex during evictFromShard for each candidate. Return true to allow eviction, false to pin (the scan will try a different victim within the same maxScan budget). If every candidate in a sweep is pinned, the eviction returns no victim and the caller's "couldn't evict" path runs. Keep the function cheap — no I/O, no locks that could re-enter the cache.
func (*CloxCache[K, V]) SetEvictNotify ¶
func (c *CloxCache[K, V]) SetEvictNotify(fn func(key K, value V))
SetEvictNotify installs an optional post-eviction callback, invoked once per evicted entry after the victim is unlinked from its chain or converted to a ghost. The callback is called under the shard mutex; it must return promptly and must not re-enter the cache. Callers that need to do real work (broadcast, take other locks) should dispatch the work on a goroutine.
func (*CloxCache[K, V]) SetSizeFunc ¶
SetSizeFunc sets the function used to calculate byte size of entries. When set, the cache tracks total bytes and updates on Put/eviction. Must be called before any Put operations for accurate tracking.
func (*CloxCache[K, V]) StartGhostSweeper ¶
StartGhostSweeper starts a background goroutine that periodically scans all shards and unlinks ghost entries. While the CLOCK hand does eventually sweep the entire shard, with large shards and small sweep percentages it can take many eviction cycles before the hand rotates back to a ghost's slot. During that time, ghosts hold their values in memory unnecessarily.
The sweeper respects ghost capacity under normal conditions, keeping useful ghosts for frequency-boosted re-insertion. Under memory pressure (when EnforceMemoryTarget is active and process memory exceeds the target), it culls ALL ghosts to reclaim memory immediately rather than waiting for the CLOCK hand to reach them naturally.
interval controls how often the sweeper runs. A typical value is 1-5 seconds. The goroutine stops when Close() is called.
type Config ¶
type Config struct {
NumShards int // Must be power of 2
SlotsPerShard int // Must be power of 2
Capacity int // Max entries (0 = use SlotsPerShard * NumShards as default)
CollectStats bool // Enable hit/miss/eviction counters
// (recommend: 15 for temporal workloads and low latency)
SweepPercent int // Percentage of shard to scan during eviction
// DecayInterval is the number of evictions (per shard) between
// eviction-driven frequency decay steps: 0 auto-scales with per-shard
// capacity (max(8, capacity/2) — forget-from-saturation ≈ 7 capacity
// turnovers), negative disables decay. Without decay, an entry that
// saturated freq while hot squats on a slot after the workload moves on
// (measured on a sliding-window trace: 50.8% hit rate vs plain LRU's
// 89.9%).
DecayInterval int
}
Config holds CloxCache configuration
func ConfigFromCapacity ¶
ConfigFromCapacity creates a CloxCache config for a specific entry capacity. Automatically configures optimal shard count and slot sizing.
func ConfigFromMemorySize ¶
ConfigFromMemorySize creates a CloxCache config for a specific memory budget. Estimates how many entries fit in the given memory and configures accordingly.
func (Config) EstimateMemoryUsage ¶
EstimateMemoryUsage estimates total memory usage for a given configuration
Source Files