# aswinkm-tc/go-lru-cache architecture

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

- Interactive diagram: https://gitdiagram.com/aswinkm-tc/go-lru-cache
- Repository: https://github.com/aswinkm-tc/go-lru-cache

## Overview

##### 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

## Diagram (Mermaid)

```mermaid
flowchart TD
    %% =======================
    %% External Consumers
    %% =======================
    Client["Client Code\n(Imports library)"]:::external

    %% =======================
    %% Module Boundary
    %% =======================
    subgraph "Go Module: go-lru-cache"
        GoMod["go.mod\n(Module boundary)"]:::meta

        subgraph "Library Package (in-process)"
            CacheAPI["Public API Surface\nGet / Set / Delete / Len / Keys"]:::api
            CacheCore["Thread-safe LRU Cache\n(Core implementation)"]:::core

            subgraph "Internal State (owned by Cache)"
                Lock["Lock\nsync.Mutex or sync.RWMutex\n(guards all fields)"]:::concurrency
                Capacity["Capacity / Max Entries"]:::core
                IndexMap["Index\nmap[key]*list.Element\n(O(1) lookup)"]:::datastructure
                RecencyList["Recency Ordering\ncontainer/list.List\n(MRU=front, LRU=back)"]:::datastructure
                Element["list.Element\n(node in list)"]:::datastructure
                Entry["Entry Payload\n{key, value}\n(stored in Element.Value)"]:::datastructure
            end

            subgraph "LRU Pattern & Invariants"
                Pattern["Pattern:\nHash Map + Doubly Linked List\nO(1) Get/Set/Delete\nEvict LRU at capacity"]:::note
            end

            subgraph "Operation Flows (inside lock)"
                subgraph "Get(key)"
                    G1["1) Lock"]:::step
                    G2["2) Lookup in Index map"]:::step
                    G3["3) If found: Move element to MRU (front)"]:::step
                    G4["4) Read value from entry"]:::step
                    G5["5) Unlock & return (value, ok)"]:::step
                end

                subgraph "Set(key, value)"
                    S1["1) Lock"]:::step
                    S2["2) Lookup key in Index map"]:::step
                    S3["3a) If exists: Update entry value"]:::step
                    S4["3b) Move element to MRU (front)"]:::step
                    S5["4a) Else: Create entry + PushFront to list"]:::step
                    S6["4b) Save map[key] = *list.Element"]:::step
                    S7["5) If len > capacity: Evict LRU (back)"]:::step
                    S8["6) Unlock"]:::step
                end

                subgraph "Eviction (LRU tail)"
                    E1["A) Identify LRU element at back"]:::step
                    E2["B) Read evicted key from entry payload"]:::step
                    E3["C) Remove element from list"]:::step
                    E4["D) Delete key from map"]:::step
                end
            end
        end

        subgraph "Tests & Documentation"
            TestSuite["Test Suite\n(correctness / eviction / thread-safety)"]:::test
            Docs["Readme.md\n(Design notes & documented API)"]:::doc
        end
    end

    %% =======================
    %% External Dependencies
    %% =======================
    subgraph "Go Standard Library"
        DepList["container/list"]:::externaldep
        DepSync["sync"]:::externaldep
        DepTesting["testing"]:::externaldep
    end

    %% =======================
    %% Relationships (Structure)
    %% =======================
    Client -->|"calls"| CacheAPI
    CacheAPI -->|"implemented_by"| CacheCore

    CacheCore -->|"owns"| Lock
    CacheCore -->|"owns"| Capacity
    CacheCore -->|"owns"| IndexMap
    CacheCore -->|"owns"| RecencyList

    IndexMap -.->|"values_are_ptrs_to"| Element
    RecencyList -->|"contains_nodes"| Element
    Element -->|"Value_stores"| Entry

    Pattern -->|"describes"| CacheCore

    %% =======================
    %% Relationships (Operation Flows)
    %% =======================
    CacheAPI -->|"Get()"| G1
    G1 -->|"guarded_by"| Lock
    G1 --> G2 --> G3 --> G4 --> G5
    G2 -->|"uses"| IndexMap
    G3 -->|"mutates_ordering"| RecencyList
    G4 -->|"reads"| Entry

    CacheAPI -->|"Set()"| S1
    S1 -->|"guarded_by"| Lock
    S1 --> S2 --> S3 --> S4 --> S8
    S2 --> S5 --> S6 --> S7 --> S8
    S2 -->|"uses"| IndexMap
    S4 -->|"mutates_ordering"| RecencyList
    S5 -->|"creates"| Entry
    S5 -->|"push_front(MRU)"| RecencyList
    S6 -->|"stores_ptr"| IndexMap
    S7 -->|"triggers"| E1
    E1 --> E2 --> E3 --> E4
    E3 -->|"removes_from"| RecencyList
    E4 -->|"deletes_from"| IndexMap
    E2 -->|"reads_key_from"| Entry

    %% =======================
    %% Dependencies
    %% =======================
    CacheCore -->|"depends_on"| DepList
    CacheCore -->|"depends_on"| DepSync
    TestSuite -->|"uses"| DepTesting
    TestSuite -->|"validates"| CacheCore
    Docs -->|"documents"| CacheAPI
    Docs -->|"explains"| Pattern

    %% =======================
    %% Click Events (from component_mapping)
    %% =======================
    click GoMod "https://github.com/aswinkm-tc/go-lru-cache/blob/main/go.mod"
    click CacheCore "https://github.com/aswinkm-tc/go-lru-cache/blob/main/main.go"
    click CacheAPI "https://github.com/aswinkm-tc/go-lru-cache/blob/main/main.go"
    click IndexMap "https://github.com/aswinkm-tc/go-lru-cache/blob/main/main.go"
    click RecencyList "https://github.com/aswinkm-tc/go-lru-cache/blob/main/main.go"
    click Entry "https://github.com/aswinkm-tc/go-lru-cache/blob/main/main.go"
    click Capacity "https://github.com/aswinkm-tc/go-lru-cache/blob/main/main.go"
    click Lock "https://github.com/aswinkm-tc/go-lru-cache/blob/main/main.go"
    click TestSuite "https://github.com/aswinkm-tc/go-lru-cache/blob/main/main_test.go"
    click Docs "https://github.com/aswinkm-tc/go-lru-cache/blob/main/Readme.md"

    %% =======================
    %% Styles
    %% =======================
    classDef external fill:#0b1220,stroke:#60a5fa,color:#e5e7eb,stroke-width:1.5px
    classDef externaldep fill:#111827,stroke:#93c5fd,color:#e5e7eb,stroke-width:1.2px
    classDef meta fill:#0f172a,stroke:#38bdf8,color:#e2e8f0,stroke-width:1.5px
    classDef api fill:#052e16,stroke:#34d399,color:#ecfdf5,stroke-width:1.5px
    classDef core fill:#1f2937,stroke:#22c55e,color:#f9fafb,stroke-width:1.5px
    classDef datastructure fill:#1e293b,stroke:#a78bfa,color:#f1f5f9,stroke-width:1.3px
    classDef concurrency fill:#3f1d1d,stroke:#fb7185,color:#fff1f2,stroke-width:1.5px
    classDef test fill:#312e81,stroke:#818cf8,color:#eef2ff,stroke-width:1.5px
    classDef doc fill:#3b2f1b,stroke:#f59e0b,color:#fffbeb,stroke-width:1.5px
    classDef note fill:#262626,stroke:#fbbf24,color:#fafafa,stroke-dasharray: 5 3
    classDef step fill:#0b1f3a,stroke:#60a5fa,color:#e5e7eb,stroke-width:1px
```
