How aswinkm-tc/go-lru-cache works
Project type & purpose (what you’re diagramming)
This repo is a Go library (not a service/app) that provides a thread-safe LRU cache. The architecture is primarily in-process data structures and concurrency control, not distributed components.
From the tree:
• main.go: likely contains the cache implementation (or package entry point for the library)
• main_test.go: tests validating correctness/eviction/thread-safety
• go.mod: module boundary / dependency context (standard library + container/list)
• Readme.md: design notes (map + doubly-linked list + eviction policy + thread safety)
Public API surface (the “what”)
Cache as a component with exported operations (from README):
• Get(key) -> (value, ok)
• Set(key, value)
• Delete(key)
• Len()
• Keys()
Core data structures (the “how”)
Based on README:
Hash map index
• map[KeyType]*list.Element (README says “any type to pointer to list.Element”)
• Purpose: O(1) lookup from key → list node
Doubly linked list (container/list)
• list.List
• Purpose: maintain recency ordering
List element payload (entry)
• Each list.Element.Value typically stores an entry{key, value} struct
Capacity / max size
• capacity or maxEntries
Concurrency control
• sync.Mutex or sync.RWMutex
• Purpose: make Get/Set/Delete/Keys/Len thread-safe under concurrent access
Tests / validation (the “proof”)
• main_test.go as a separate “Test Suite” component:
• Validates ordering changes on access
• Validates eviction at capacity
• Validates thread safety / race conditions (if present)
External dependencies (the “depends on”)
• Go standard library:
• container/list
• sync (for mutex)
• possibly testing in tests
Data ownership & references
• Cache “owns”:
• map (index)
• list.List (recency ordering)
• mutex (guard)
• capacity
• map values point to *list.Element
• Each list.Element contains an entry (key/value)
• Cache → (contains) → Index map
• Cache → (contains) → Doubly Linked List
• Index map → (points to) → list.Element
• list.Element → (stores) → entry{key,value}
Behavioral flows (Get/Set/Evict)
Get(key):
If found
• Move corresponding list.Element to “most recent” position (typically front)
• Return value
Release lock
Set(key,value):
If key exists
• Update entry value in the existing element
• Move element to front (most recent)
Else
• Create new entry, push to front
• Map[key] = element
• If size > capacity:
• Evict tail element (least recent)
• Remove from list
• Delete evicted key from map
Release lock
Delete(key):
• Acquire lock → map lookup → remove element from list → delete map entry → release lock
Keys():
• Acquire lock
• Iterate list from most-recent to least-recent (or vice versa—be explicit)
• Build slice of keys
• Release lock
Architectural pattern to call out explicitly
• “LRU via Hash Map + Doubly Linked List”
• O(1) Get/Set/Delete (amortized constant time)
• Thread-safe critical section guarded by a mutex
• Eviction policy: when at capacity, evict least-recently-used (tail/back)
• go-lru-cache (module)
• depends on container/list
• depends on sync
• tests depend on testing
Inside/connected:
• Mutex/RWMutex
• Index map[key]*list.Element
• list.List (recency order)
• entry{key,value} associated with each element
• capacity
• → element
• element → entry
• Ordering semantics (MRU ↔ LRU)
Practical detail checklist (don’t overthink—just separate components)
• The two-structure approach: map + doubly linked list
• The pointer relationship: map values are *list.Element
• The entry containing key (needed for eviction cleanup in the map)
• The MRU/LRU ends of the list
• The eviction trigger (size/capacity condition) and the two-step removal (list + map)
• The mutex boundary around all public operations
• The tests as a separate consumer validating behavior