# phuslu/lru architecture

> Architecture diagram of the GitHub repository phuslu/lru, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2026-06-28). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/phuslu/lru
- Repository: https://github.com/phuslu/lru

## Overview

1. **What this repo is**
This is a Go library for in-memory caching, centered on two main cache flavors: a classic sharded LRU cache and a TTL cache variant. It is optimized for hot-path use in services where predictable latency, low GC pressure, and immediate consistency of cache operations matter.

2. **Public API surface**
The exported entry points are the generic `LRUCache[K,V]`, `TTLCache[K,V]`, and `BytesCache` implementations. The generic caches support normal `Get`/`Set`-style access; the TTL cache adds per-entry expiry; the bytes cache is specialized for `[]byte` keys and values and avoids string conversion and extra copying.

3. **Primary runtime boundary: sharding**
The core architectural boundary is sharding. Cache capacity is split into fixed-size shards so lookups and updates only touch one shard at a time. This is the main concurrency and scalability mechanism, and it also helps keep per-shard data structures compact and predictable.

4. **Per-shard storage model**
Each shard is built from two main pieces: a lookup table and a recency list. The table gives fast key-to-entry lookup, while the list maintains LRU order for eviction and promotion on access. The file split into `*_shard.go`, `*_shard_list.go`, and `*_shard_table.go` reflects that separation.

5. **LRU data flow**
For the non-TTL cache, a `Get` does two things: it looks up the entry in the shard table and then updates the item’s recency position in the shard list. A `Set` inserts or replaces the entry and may evict the least-recently-used entry when the shard is full. The behavior is synchronous; there is no background admission or delayed write path.

6. **TTL data flow**
The TTL cache layers expiration metadata on top of the same sharded cache shape. On access, the shard checks expiry before returning a value. Expired entries are removed lazily, either when accessed again or when capacity pressure forces eviction. The README notes TTL precision is to the nearest second, which is an intentional implementation constraint.

7. **Loader and singleflight path**
The presence of `singleflight.go` and the loader option in `options.go` indicates an optional cache-miss loading path. When enabled, concurrent requests for the same missing key are coalesced so only one load function executes, reducing duplicate backend work. This is a boundary between the cache and an upstream data source, not a separate async subsystem.

8. **Bytes-oriented fast path**
`bytes_cache.go`, `bytes_shard.go`, and related files define a separate implementation optimized for `[]byte`-heavy workloads. Its architectural goal is to keep the byte path zero-copy and avoid allocation-heavy conversions, under the assumption that stored slices are treated as immutable by the caller.

9. **Hashing and identity**
`wyhash.go` provides the hashing primitive used to map keys to shards and table slots. This is part of the performance story: fast key hashing reduces overhead on every access and supports the compact shard/table design. For generic keys, the cache relies on deterministic key hashing; for byte keys, it can stay in the byte domain.

10. **Clock and expiration support**
`ttl_clock.go` isolates time source behavior for TTL handling. This makes expiry logic a distinct subsystem rather than hard-coding time access throughout the cache. It also supports the library’s stated focus on predictable TTL behavior and testability.

11. **Stats and observability**
`stats.go` exposes counters such as set/get/miss activity, which lets users observe cache behavior without instrumenting the internals. This is lightweight observability built into the cache, not an external metrics pipeline.

12. **Options and feature toggles**
`options.go` is the configuration boundary for optional behavior such as sliding expiration and loader integration. The repository treats these as feature switches on top of the same core cache engine, rather than separate products. That keeps the architecture centered on one core LRU/TTL implementation with opt-in behaviors.

13. **GC and memory design constraints**
A major design goal is reducing GC scan cost and heap churn. The README and file layout point to array-backed lists, compact tables, low pointer density, and no per-entry allocation. The “nottl” benchmark target in the README shows the TTL feature is optional and that removing it saves memory, reinforcing that memory layout is an architectural concern, not just an implementation detail.

14. **Verification and regression workflow**
The GitHub Actions workflows are split by concern: unit tests, benchmarks, GC scan measurement, and memory profiling. That tells you the repo is treated as a performance-sensitive library where correctness, throughput, GC cost, and memory footprint are all first-class release criteria.

15. **Diagram takeaway**
If you draw the architecture, the key shape is: public cache APIs at the top; optional loader/TTL/statistics around them; a sharded core in the middle; and per-shard table/list storage plus hashing/clock helpers underneath. The main cross-cutting concern is performance under Go’s GC, which drives the choice of fixed-size shards and compact in-memory structures.

Main entry points: [`ttl_shard.go`](https://github.com/phuslu/lru/blob/master/ttl_shard.go) (TTL Shard), [`lru_cache.go`](https://github.com/phuslu/lru/blob/master/lru_cache.go) (LRU Cache), [`ttl_cache.go`](https://github.com/phuslu/lru/blob/master/ttl_cache.go) (TTL Cache), [`lru_shard.go`](https://github.com/phuslu/lru/blob/master/lru_shard.go) (LRU Shard)

## Diagram (Mermaid)

```mermaid
flowchart TD

subgraph group_public["Public API"]
  node_lru_cache["LRU Cache<br/>generic cache<br/>[lru_cache.go]"]
  node_ttl_cache["TTL Cache<br/>expiring cache<br/>[ttl_cache.go]"]
  node_bytes_cache["Bytes Cache<br/>byte cache<br/>[bytes_cache.go]"]
  node_options["Options<br/>config<br/>[options.go]"]
end

subgraph group_core["Core Engine"]
  node_lru_shard["LRU Shard<br/>[lru_shard.go]"]
  node_lru_table[("LRU Table<br/>index table<br/>[lru_shard_table.go]")]
  node_lru_list["LRU List<br/>recency list<br/>[lru_shard_list.go]"]
  node_ttl_shard["TTL Shard<br/>expiring shard<br/>[ttl_shard.go]"]
  node_ttl_table[("TTL Table<br/>index table<br/>[ttl_shard_table.go]")]
  node_ttl_list["TTL List<br/>recency list<br/>[ttl_shard_list.go]"]
  node_bytes_shard["Bytes Shard<br/>byte shard<br/>[bytes_shard.go]"]
  node_bytes_table[("Bytes Table<br/>byte index")]
  node_bytes_list["Bytes List<br/>recency list"]
end

subgraph group_support["Support"]
  node_stats["Stats<br/>metrics<br/>[stats.go]"]
  node_singleflight["Singleflight<br/>miss coalescer<br/>[singleflight.go]"]
  node_runtime["Runtime<br/>[runtime.go]"]
  node_hash{{"Wyhash<br/>hashing<br/>[wyhash.go]"}}
  node_clock["TTL Clock<br/>time source<br/>[ttl_clock.go]"]
end

node_lru_cache -->|"configured by"| node_options
node_ttl_cache -->|"configured by"| node_options
node_bytes_cache -->|"configured by"| node_options
node_lru_cache -->|"routes to"| node_lru_shard
node_ttl_cache -->|"routes to"| node_ttl_shard
node_bytes_cache -->|"routes to"| node_bytes_shard
node_lru_shard -->|"lookup"| node_lru_table
node_lru_shard -->|"evict/promote"| node_lru_list
node_ttl_shard -->|"lookup"| node_ttl_table
node_ttl_shard -->|"evict/promote"| node_ttl_list
node_bytes_shard -->|"lookup"| node_bytes_table
node_bytes_shard -->|"evict/promote"| node_bytes_list
node_lru_shard -->|"hashes with"| node_hash
node_ttl_shard -->|"hashes with"| node_hash
node_bytes_shard -->|"hashes with"| node_hash
node_ttl_shard -->|"checks"| node_clock
node_lru_cache -.->|"optional miss path"| node_singleflight
node_ttl_cache -.->|"optional miss path"| node_singleflight
node_lru_cache -.->|"records"| node_stats
node_ttl_cache -.->|"records"| node_stats
node_bytes_cache -.->|"records"| node_stats
node_runtime -.->|"supports"| node_lru_cache

click node_lru_cache "https://github.com/phuslu/lru/blob/master/lru_cache.go"
click node_ttl_cache "https://github.com/phuslu/lru/blob/master/ttl_cache.go"
click node_bytes_cache "https://github.com/phuslu/lru/blob/master/bytes_cache.go"
click node_options "https://github.com/phuslu/lru/blob/master/options.go"
click node_stats "https://github.com/phuslu/lru/blob/master/stats.go"
click node_singleflight "https://github.com/phuslu/lru/blob/master/singleflight.go"
click node_runtime "https://github.com/phuslu/lru/blob/master/runtime.go"
click node_hash "https://github.com/phuslu/lru/blob/master/wyhash.go"
click node_clock "https://github.com/phuslu/lru/blob/master/ttl_clock.go"
click node_lru_shard "https://github.com/phuslu/lru/blob/master/lru_shard.go"
click node_lru_table "https://github.com/phuslu/lru/blob/master/lru_shard_table.go"
click node_lru_list "https://github.com/phuslu/lru/blob/master/lru_shard_list.go"
click node_ttl_shard "https://github.com/phuslu/lru/blob/master/ttl_shard.go"
click node_ttl_table "https://github.com/phuslu/lru/blob/master/ttl_shard_table.go"
click node_ttl_list "https://github.com/phuslu/lru/blob/master/ttl_shard_list.go"
click node_bytes_shard "https://github.com/phuslu/lru/blob/master/bytes_shard.go"
click node_bytes_table "https://github.com/phuslu/lru/blob/master/bytes_shard_table.go"
click node_bytes_list "https://github.com/phuslu/lru/blob/master/bytes_shard_list.go"

classDef toneNeutral fill:#f8fafc,stroke:#334155,stroke-width:1.5px,color:#0f172a
classDef toneBlue fill:#dbeafe,stroke:#2563eb,stroke-width:1.5px,color:#172554
classDef toneAmber fill:#fef3c7,stroke:#d97706,stroke-width:1.5px,color:#78350f
classDef toneMint fill:#dcfce7,stroke:#16a34a,stroke-width:1.5px,color:#14532d
classDef toneRose fill:#ffe4e6,stroke:#e11d48,stroke-width:1.5px,color:#881337
classDef toneIndigo fill:#e0e7ff,stroke:#4f46e5,stroke-width:1.5px,color:#312e81
classDef toneTeal fill:#ccfbf1,stroke:#0f766e,stroke-width:1.5px,color:#134e4a
class node_lru_cache,node_ttl_cache,node_bytes_cache,node_options toneBlue
class node_lru_shard,node_lru_table,node_lru_list,node_ttl_shard,node_ttl_table,node_ttl_list,node_bytes_shard,node_bytes_table,node_bytes_list toneAmber
class node_stats,node_singleflight,node_runtime,node_hash,node_clock toneMint
```

## Components

### Public API

Exported cache entry points and configuration surface

- [LRU Cache](https://github.com/phuslu/lru/blob/master/lru_cache.go): generic cache · Sharded in-memory LRU cache API · `lru_cache.go`
- [TTL Cache](https://github.com/phuslu/lru/blob/master/ttl_cache.go): expiring cache · Sharded cache with per-entry expiry · `ttl_cache.go`
- [Bytes Cache](https://github.com/phuslu/lru/blob/master/bytes_cache.go): byte cache · []byte-specialized cache API · `bytes_cache.go`
- [Options](https://github.com/phuslu/lru/blob/master/options.go): config · Feature switches and cache settings · `options.go`

### Core Engine

Sharded cache implementations and per-shard storage

- [LRU Shard](https://github.com/phuslu/lru/blob/master/lru_shard.go): shard · Per-shard lookup and eviction unit · `lru_shard.go`
- [LRU Table](https://github.com/phuslu/lru/blob/master/lru_shard_table.go): index table · Shard key-to-entry lookup structure · `lru_shard_table.go`
- [LRU List](https://github.com/phuslu/lru/blob/master/lru_shard_list.go): recency list · Tracks access order for promotion and eviction · `lru_shard_list.go`
- [TTL Shard](https://github.com/phuslu/lru/blob/master/ttl_shard.go): expiring shard · Shard that checks expiry before serving values · `ttl_shard.go`
- [TTL Table](https://github.com/phuslu/lru/blob/master/ttl_shard_table.go): index table · Lookup structure for expiring entries · `ttl_shard_table.go`
- [TTL List](https://github.com/phuslu/lru/blob/master/ttl_shard_list.go): recency list · Maintains LRU order with expiry-aware entries · `ttl_shard_list.go`
- [Bytes Shard](https://github.com/phuslu/lru/blob/master/bytes_shard.go): byte shard · Shard optimized for []byte keys and values · `bytes_shard.go`
- [Bytes Table](https://github.com/phuslu/lru/blob/master/bytes_shard_table.go): byte index · Byte-oriented shard lookup structure · `bytes_shard_table.go`
- [Bytes List](https://github.com/phuslu/lru/blob/master/bytes_shard_list.go): recency list · Byte-path recency and eviction order · `bytes_shard_list.go`

### Support

Hashing, time, stats, and coordination helpers

- [Stats](https://github.com/phuslu/lru/blob/master/stats.go): metrics · Lightweight cache counters · `stats.go`
- [Singleflight](https://github.com/phuslu/lru/blob/master/singleflight.go): miss coalescer · Coalesces duplicate loads on cache miss · `singleflight.go`
- [Runtime](https://github.com/phuslu/lru/blob/master/runtime.go): build/runtime · Runtime-dependent support code · `runtime.go`
- [Wyhash](https://github.com/phuslu/lru/blob/master/wyhash.go): hashing · Fast key hashing for shard and slot selection · `wyhash.go`
- [TTL Clock](https://github.com/phuslu/lru/blob/master/ttl_clock.go): time source · Abstracted clock for expiry checks · `ttl_clock.go`

## Connections

- LRU Cache → Options: configured by · Cache construction uses options and feature toggles
- TTL Cache → Options: configured by · TTL behavior and loaders are enabled through options
- Bytes Cache → Options: configured by · Byte cache construction uses shared settings
- LRU Cache → LRU Shard: routes to · Operations are dispatched to a single shard
- TTL Cache → TTL Shard: routes to · Operations are dispatched to a single shard
- Bytes Cache → Bytes Shard: routes to · Operations are dispatched to a single shard
- LRU Shard → LRU Table: lookup · Shard uses table for key lookup
- LRU Shard → LRU List: evict/promote · Shard updates recency order on access
- TTL Shard → TTL Table: lookup · Shard uses table for key lookup
- TTL Shard → TTL List: evict/promote · Shard maintains recency order with expiry-aware entries
- Bytes Shard → Bytes Table: lookup · Byte shard uses a byte-oriented table
- Bytes Shard → Bytes List: evict/promote · Byte shard maintains recency order
- LRU Shard → Wyhash: hashes with · Keys are mapped to shard and table slots
- TTL Shard → Wyhash: hashes with · Keys are mapped to shard and table slots
- Bytes Shard → Wyhash: hashes with · Byte keys stay in the byte domain for hashing
- TTL Shard → TTL Clock: checks · Expiry decisions depend on the abstract clock
- LRU Cache → Singleflight: optional miss path · Concurrent misses may be coalesced into one load
- TTL Cache → Singleflight: optional miss path · Loader integration may be combined with expiry
- LRU Cache → Stats: records · Get/set/miss activity is tracked
- TTL Cache → Stats: records · Get/set/miss and expiry activity is tracked
- Bytes Cache → Stats: records · Byte cache activity can be observed
- Runtime → LRU Cache: supports · Runtime-specific support code underpins cache behavior