Mastering Cache Design in Go: Concepts, APIs, and Concurrency

Concept

Cache is a core computer‑science concept that stores the result of an external request locally so subsequent accesses are faster, reducing latency. Examples include memory caches, CPU caches, and server‑side caches such as Redis.

Use Cases

Web services use caching to avoid repeated database queries. Static data (e.g., monthly statistics) benefits most, while rapidly changing data (e.g., comment streams) requires careful invalidation.

Bad Design

When multiple servers maintain independent caches, updates may not propagate, leading to inconsistent data and broken integrity, as illustrated by a comment‑deletion scenario.

Better Approach

Employ a single external cache shared by all servers, ensuring consistent data across instances.

Constraints

Caches are faster but much smaller than databases because they reside in memory. They are volatile, so eviction policies such as LRU (Least Recently Used), LFU (Least Frequently Used), and FIFO (First In First Out) are needed to decide which items to discard.

Design & Implementation

Requirements

Key‑Value storage with average O(log N) read/write time.

LRU eviction when capacity is reached.

TTL (Time To Live) for each entry to expire automatically.

API Design

The cache provides simple Get and Put functions similar to a hash‑map.

func Get(key string) (hit bool, value []byte)
func Put(key string, value []byte) (hit bool)

Get returns the value if the key exists; otherwise hit is false. Access updates the LRU order.

Put inserts or updates a key; if the cache is full, the least‑recently‑used entry is evicted.

Data Structures

Two structures are combined: a hash‑map for O(1) key lookup and a doubly‑linked list to maintain LRU order.

Hash‑map: defined in Go as map[<type>]<type>.

Doubly‑linked list: stores nodes referenced from the hash‑map to implement LRU.

Get looks up the key in the hash‑map, follows the pointer to the list node, updates LRU state, and returns the value. Put either updates an existing entry or inserts a new node, evicting the LRU entry if needed.

Concurrency Control

Multiple goroutines may access the cache concurrently, risking race conditions between hash‑map and list updates. The simplest solution is to protect all operations with a mutex.

The cache is full and the LRU key is 1.

User A calls Put(101); the cache evicts key 1 and inserts 101.

Simultaneously, User B calls Put(1); the hash‑map sees key 1 and attempts to update it.

A’s operation removes node 1 from the list and deletes key 1 from the map.

B then accesses the now‑deleted node, causing a panic.

Wrapping each operation with Mutex prevents this race:

func (s *CStorage) Get(key string) (data []byte, hit bool) {
    s.mutex.Lock()
    defer s.mutex.Unlock()
    n, ok := s.table[key]
    if !ok { return nil, false }
    if n.ttl.Before(time.Now()) { s.evict(n); s.size--; return nil, false }
    return n.data, true
}

TTL (Time To Live)

TTL is checked lazily during Get/Put; expired entries remain until accessed. To proactively clean expired items, a RemoveExpired() function iterates the table and deletes stale entries.

func (s *CStorage) RemoveExpired() int64 {
    var count int64 = 0
    for key, value := range s.table {
        if value.ttl.Before(time.Now()) {
            s.Delete(key)
            count++
        }
    }
    return count
}

Result

GitHub repository: https://github.com/cocm1324/cstorage

Package documentation: https://pkg.go.dev/github.com/cocm1324/cstorage

Conclusion

Cache design offers a practical way to reduce component latency. Implemented in Go with a hash‑map and doubly‑linked list, it requires mutex protection for concurrency and combines passive TTL checks with an active cleanup routine to manage expired data.