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

Concept

Cache is an important concept in computer science. When a component needs an external resource, fetching it each time is inefficient; storing the result locally allows faster reuse. Examples include memory caches, CPU caches, and server caches such as Redis.

Different Use Cases

Web services use cache to reduce data‑request latency by storing the result of the first query and reusing it without hitting the database. Depending on data characteristics, caches may hold relatively static data (e.g., statistics) or frequently changing data (e.g., comments).

Ideally, cache rarely‑changing data such as monthly statistics, which never change after generation, can be cached to avoid repeated database queries.

Stupid design: when rapidly changing data is cached across multiple servers, inconsistencies can arise. For example, if user A deletes a comment on server A while user B replies on server B, the deletion may not propagate, leading to divergent caches and broken data integrity.

Better approach: use a single external cache shared by all servers, ensuring consistent data.

Constraints

Cache is faster than a database but much smaller because it resides in memory, which is volatile. If the host stops, cached data is lost, whereas database data persists.

Limited cache space requires eviction policies such as LRU (Least Recently Used), LFU (Least Frequently Used), and FIFO (First In First Out).

Design & Implementation

Requirements

Key‑Value storage with average O(logN) read/write operations, where N is the number of keys.

LRU eviction policy to remove least‑recently used items when the cache is full.

TTL (Time To Live) for each key, after which the entry must be evicted.

API Design

The cache provides 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, marks the key as recently used for LRU, otherwise returns hit = false.

Put: inserts a new key or updates an existing one; if the cache is full, the LRU entry is evicted.

Data Structures

The implementation uses a hash‑map and a doubly‑linked list to achieve O(1) key lookup and LRU ordering.

Hash‑map stores the key and a pointer to the corresponding list node.

Doubly‑linked list maintains usage order, with the most recently used item at the front.

Get searches the hash‑map, follows the pointer to the list node, updates the LRU position, and returns the value.

Put either updates an existing entry or inserts a new node, evicting the least recently used item if necessary.

Concurrency Control

Multiple goroutines may access the cache concurrently, creating race conditions.

Wrapping each operation with a mutex prevents interference and guarantees safe data access.

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
}

Time To Live

TTL is checked lazily during Get/Put; expired entries remain until accessed.

A RemoveExpired function iterates the table and deletes keys whose TTL has passed.

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

Pkg.go.dev: https://pkg.go.dev/github.com/cocm1324/cstorage

Conclusion

Cache is a powerful tool for reducing component latency; it is fast but limited in size. The Go implementation combines a hash‑map and a doubly‑linked list, uses mutexes for thread safety, and mixes passive and active TTL eviction strategies.