golang-lru

golang-lru is HashiCorp’s fixed-size, thread-safe LRU (Least Recently Used) cache implementation for Go, built on generics for full type safety. It began as a wrapper around Groupcache’s cache logic and now ships four interchangeable cache variants in one module: a classic LRU, a 2Q cache that resists scan pollution, an ARC (Adaptive Replacement Cache) that balances recency and frequency automatically, and an expirable LRU with per-entry TTL.

The library is used throughout HashiCorp’s own tooling, including Vault, Consul, and Nomad, as well as many other Go projects that need bounded in-memory caching without standing up an external cache server. Each variant lives as a small, dependency-light package under a shared module, so teams pick exactly the eviction strategy their workload needs.

What You Get

• A generic, thread-safe Cache[K, V] type implementing classic LRU eviction
• An expirable subpackage adding per-cache TTL expiration on top of LRU semantics
• A 2Q cache variant that resists pollution from one-time scan access patterns
• An ARC (Adaptive Replacement Cache) variant that auto-balances recency vs frequency
• Optional eviction callbacks fired outside the internal lock for safe cleanup/metrics hooks

Common Use Cases

• In-process caching of expensive API or database responses to cut redundant calls
• Bounding memory for connection or session pools inside infrastructure daemons
• Building TTL-based rate limiters or short-lived counters with the expirable variant
• Scan-resistant read-through caching where hot keys must survive occasional bulk scans

Under The Hood

Architecture The module is organized as a set of sibling packages sharing one generic doubly-linked-list implementation in internal/list.go (adapted from Go’s container/list, with an added expiry timestamp field). The root lru package wraps a non-thread-safe simplelru.LRU[K, V] behind a sync.RWMutex and an optional eviction-callback buffer that is drained outside the critical section (see Cache.Purge and Cache.onEvicted in lru.go) to avoid calling user code while holding the lock. The arc package composes four simplelru.LRUCache instances (T1/T2 for recent/frequent entries, B1/B2 as ghost eviction-history lists) to implement the ARC algorithm, while expirable reimplements the list with time-aware eviction and a background sweep goroutine. This layered composition means every variant reuses the same core list/map primitives rather than duplicating cache logic.

Tech Stack Pure Go with no third-party runtime dependencies; go.mod declares go 1.19 to use generics throughout (K comparable, V any). The arc subpackage is its own Go module with its own go.mod, isolating it for versioning. Build/test tooling is a plain Makefile plus go test; CI runs via GitHub Actions (.github/workflows/ci.yml) with Dependabot keeping the module and Actions versions current, and a HashiCorp copywrite check enforces license headers.

Code Quality Every package ships a matching _test.go file (lru_test.go, simplelru/lru_test.go, arc/arc_test.go, expirable/expirable_lru_test.go, 2q_test.go) exercising eviction order, capacity limits, callback firing, and expiry timing. Errors are returned explicitly (e.g. New returns an error for non-positive size) rather than panicking, and public types are documented with doc comments throughout. Locking is consistent: every thread-safe wrapper holds its own sync.RWMutex rather than sharing state across packages.

What Makes It Unique Rather than picking one eviction policy, the module exposes four algorithmically distinct caches behind a near-identical API, letting callers swap ARC for plain LRU or add TTL expiration without changing call sites. The ARC implementation in particular is a comparatively rare open-source instance of IBM’s patented Adaptive Replacement Cache algorithm made available under a permissive-enough license for general use, giving Go projects an alternative to manually tuning 2Q’s fixed parameters.