ProcessCache: In-Process LRU Cache for Go

Repository Shape

Problem & Goal

ProcessCache started from a practical backend need: keep repeated reads inside one Go process without adding Redis, Memcached, a database cache table, an HTTP sidecar, or another operational dependency. The package is intentionally local. It optimizes for fast in-process reads, bounded memory, exact LRU behavior, and a public API that can be installed from the module root.

• Expose a clean package import: github.com/tonmoytalukder/process-cache.
• Keep runtime dependencies at zero.
• Bound total memory with an approximate global byte cap.
• Support optional prefix quotas such as username: or session:.
• Keep both global and prefix eviction O(1), not scan-based.
• Remove expired entries lazily on reads and with a background sweeper.
• Provide typed reads, stats snapshots, testable clocks, custom sizing, and idempotent shutdown.

Package Layout

process-cache/├── processcache.go              # public facade: Cache, constructors, options, GetAs├── internal/│   ├── processcache/│   │   ├── memory.go            # map, LRU lists, eviction, expiration, stats│   │   ├── config.go            # defaults, options, validation│   │   ├── sizer.go             # approximate default sizing│   │   ├── clock.go             # RealClock│   │   └── types.go             # Config, Stats, sentinel errors│   └── pkg/testclock/           # deterministic clock for tests├── test/│   ├── unit/processcache/       # public behavior tests│   ├── integration/processcache/│   └── e2e/consumer/            # external consumer module├── cmd/example/                 # runnable example├── cmd/bench/                   # manual benchmark runner├── scripts/                     # test, race, bench, docker-test└── docs/                        # algorithm and design notes

The root file is deliberately a facade. Consumers import the module root, while implementation details stay under internal/processcache. That keeps the exported surface small without forcing users to import a nested internal-looking package. The published API is also browsable from pkg.go.dev for teams that want package documentation before installing it.

Architecture Overview

The algorithm combines one hash map with linked lists. The map gives average O(1) lookup by key. The global doubly-linked list gives O(1) access to the least-recently-used item. For every configured prefix, ProcessCache also keeps a dedicated prefix list, so prefix eviction is O(1) instead of scanning the global list.

Caller
  |
  v
processcache.Cache interface
  |
  v
MemoryCache
  |
  +-- items: map[string]*item
  |      key -> item pointer for average O(1) lookup
  |
  +-- globalLRU: doubly linked list
  |      front = most recently used, back = least recently used
  |
  +-- typeLRUs: map[prefix]*list.List
  |      one LRU list per configured prefix
  |
  +-- typeSizes / typeLimits
  |      approximate byte accounting per prefix
  |
  +-- sizer, clock, stats, cleanup goroutine

type MemoryCache struct {    mu sync.Mutex    items     map[string]*item    globalLRU *list.List    maxSize     int64    currentSize int64    typeSizes  map[string]int64    typeLimits map[string]TypeLimit    typeLRUs   map[string]*list.List    prefixes   []string    sizer Sizer    clock Clock    cleanupInterval time.Duration    cleanupDisabled bool    stopCleanup     chan struct{}    cleanupDone     chan struct{}    closeOnce       sync.Once    metrics bool    stats   statsCounter}type item struct {    key        string    value      any    size       int64    prefix     string    expiration time.Time    hasExpiry  bool    globalElem *list.Element    typeElem   *list.Element}

Get Algorithm

Get(key)
  |
  v
Lock cache mutex
  |
  v
items[key] exists?
  |
  +-- no --> unlock, record miss, return nil false
  |
  v
Expired according to clock.Now()?
  |
  +-- yes --> remove from map, global LRU, prefix LRU
  |           record expiration and miss
  |           unlock, return nil false
  |
  v
Move item to front of global LRU
  |
  v
If item has configured prefix, move it to front of prefix LRU
  |
  v
Copy value, unlock, record hit, return value true

A successful read mutates recency state, so the implementation uses one mutex rather than pretending reads are read-only. That is an intentional tradeoff: exact LRU ordering is more valuable here than an approximate lock-free policy.

Set Algorithm

Set(key, value, ttl)
  |
  +-- empty key? --------------------> reject false
  |
  v
size = sizer.SizeOf(key, value)
  |
  +-- size > global max? ------------> reject false
  |
  v
prefix = first configured prefix matching key
  |
  +-- size > prefix max? ------------> reject false
  |
  v
Lock cache mutex
  |
  v
Remove existing item with same key, if present
  |
  v
While prefix budget would overflow:
  |       evict tail of prefix LRU
  |
  v
While global budget would overflow:
  |       evict tail of global LRU
  |
  v
Push item to front of global LRU
  |
  v
If prefix configured, push item to front of that prefix LRU
  |
  v
Update map, size counters, stats; unlock; return true

cache, err := processcache.NewMemoryCache(    processcache.WithMaxSize(100*processcache.MB),    processcache.WithCleanupInterval(5*time.Minute),    processcache.WithTypeLimit("username:", 1*processcache.MB),    processcache.WithTypeLimit("session:", 50*processcache.MB),)if err != nil {    panic(err)}defer cache.Close()cache.Set("username:tonmoy", true, 5*time.Minute)exists, ok := processcache.GetAs[bool](cache, "username:tonmoy")

Why Prefix Eviction Is O(1)

The earlier draft of this design used one global LRU list and scanned backward to find the oldest item for a prefix. The real package improves that: configured prefixes each have their own doubly-linked list. An item with a prefix stores two list nodes, one in the global list and one in the prefix list.

item("session:123")
  |
  +-- globalElem --> globalLRU: newest <-> ... <-> oldest
  |
  +-- typeElem   --> typeLRUs["session:"]: newest session <-> ... <-> oldest session

Global pressure:
  evict globalLRU.Back() in O(1)

session: pressure:
  evict typeLRUs["session:"].Back() in O(1)

Expiration, Stats, and Shutdown

Expiration is enforced in two places. Get and Exists remove expired items lazily so an expired value is never returned. A background sweeper periodically scans for expired items that nobody reads again. Close stops that sweeper and waits for it to exit; calling Close more than once is safe.

value, ok := processcache.GetAs[string](cache, "profile:42")if !ok {    // miss, nil cache, nil value, or type mismatch}stats := cache.Stats()fmt.Println(stats.Hits, stats.Misses, stats.CurrentSize)

Complexity Summary

Key Design Decisions

When To Use ProcessCache

ProcessCache is built for cache data that belongs to one Go process, can be recomputed or fetched again, and does not need to survive deploys or restarts. The strongest fit is a service, CLI, worker, or internal tool where Redis would add more operational surface area than the hot path deserves.

• Use it when hot reads should stay inside the process and avoid repeated database, filesystem, or API calls.
• Use it when an unbounded map would be risky and you want approximate byte limits with exact LRU eviction.
• Use it when separate key families need fairness, such as username:, session:, profile:, token:, or api-response:.
• Use it when cached values can expire naturally through TTLs and be refreshed from a source of truth.
• Use it when you want zero runtime dependencies in CLIs, workers, batch jobs, HTTP services, prototypes, or internal tools.
• Use it when services can accept a process-local cache abstraction and treat nil as cache disabled.

go get github.com/tonmoytalukder/process-cacheimport processcache "github.com/tonmoytalukder/process-cache"

Practical Use Cases

Tradeoffs & When Not To Use It

• Use Redis or Memcached when many processes need the same cache state.
• Use a distributed cache when cache data must survive process restarts, support cross-service invalidation, or participate in atomic distributed operations.
• Approximate size accounting is good enough for bounded local caching, but not a replacement for process memory observability.
• Exact LRU is simpler to reason about, but the single mutex is not designed for extremely high-contention cache workloads.
• Prefix quotas give predictable namespace fairness, but overlapping prefixes are rejected so accounting stays deterministic.