Machine Coding Interview: Efficient Cache Implementation using time-based expiry and eviction

I was asked this question in one of the coding interviews for a senior golang developer role.

Photo by Allan Vega on Unsplash

This was a machine coding round, I had to design and implement an efficient cache in a programming language of my choice which should be very efficient, thread safe and shouldn’t spike the memory usage too much.

I chose golang because ..

1. Golang’s built-in support for concurrency, including lightweight goroutines and channels, make it an ideal choice for building high-performance systems with a large number of concurrent operations, such as cache management.
2. The language’s simple and consistent syntax, along with its focus on minimizing memory overhead and maximizing throughput, also make it a good fit for building scalable and efficient caching systems. Additionally, Golang’s extensive standard library includes packages for working with time-based events, such as the time package used in this example, which simplifies the implementation of cache expiration policies.
3. Overall, Golang’s combination of concurrency support, performance, and simplicity make it an excellent choice for building high-performance caching systems.

This is the code with comments, written below

package main

import (
 "fmt"
 "sync"
 "time"
)

type Cache struct {
 data      map[string]interface{}
 expiry    time.Duration
 evictPool chan struct{}
 mutex     sync.RWMutex
}

func NewCache(expiry time.Duration, evictPoolSize int) *Cache {
 return &Cache{
  data:      make(map[string]interface{}),
  expiry:    expiry,
  evictPool: make(chan struct{}, evictPoolSize),
 }
}

func (c *Cache) Set(key string, value interface{}) {
 c.mutex.Lock()
 defer c.mutex.Unlock()

 c.data[key] = value
 go c.scheduleEviction(key)
}

func (c *Cache) Get(key string) (interface{}, bool) {
 c.mutex.RLock()
 defer c.mutex.RUnlock()

 value, ok := c.data[key]
 return value, ok
}

func (c *Cache) Delete(key string) {
 c.mutex.Lock()
 defer c.mutex.Unlock()

 delete(c.data, key)
}

func (c *Cache) scheduleEviction(key string) {
 select {
 case c.evictPool <- struct{}{}:
  // Goroutine acquired from pool, proceed with eviction
 case <-time.After(c.expiry):
  // Timed out waiting for goroutine from pool, evicting from current goroutine
  c.evict(key)
  return
 }

 go func() {
  c.evict(key)
  <-c.evictPool
 }()
}

func (c *Cache) evict(key string) {
 c.mutex.Lock()
 defer c.mutex.Unlock()

 if _, ok := c.data[key]; ok {
  delete(c.data, key)
  fmt.Printf("Evicted key %s\n", key)
 }
}

func main() {
 cache := NewCache(2*time.Second, 10)

 cache.Set("key1", "value1")
 cache.Set("key2", "value2")
 cache.Set("key3", "value3")

 time.Sleep(3 * time.Second)

 // Key1 should have been evicted, key2 and key3 should still be present
 if _, ok := cache.Get("key1"); !ok {
  fmt.Println("key1 evicted")
 }
 if _, ok := cache.Get("key2"); ok {
  fmt.Println("key2 present")
 }
 if _, ok := cache.Get("key3"); ok {
  fmt.Println("key3 present")
 }
}

Explanation

We also use a buffered channel evictPool to limit the number of goroutines that can be spawned for evicting keys.

If a goroutine is available in the pool, we use it for eviction. Otherwise, we wait for the timeout specified by time.After and evict from the current goroutine.

After eviction, the goroutine is released back to the pool.

Using a thread/goroutine pool is a better choice as compared to spawning goroutines without check because that limits the memory in use, which if not checked can grow boundless.

Subscribe to my Youtube channel

Subscribe to my youtube channel if you are on the lookout for more such awesome content in video format.

https://www.youtube.com/@dsysd-dev

Subscribe to my Newsletter

If you like my content, then consider subscribing to my free newsletter, to get exclusive, educational, technical, interesting and career related content directly delivered to your inbox

https://dsysd.beehiiv.com/subscribe

Important Links

Thanks for reading the post, be sure to follow the links below for even more awesome content in the future.

twitter: https://twitter.com/dsysd_dev
youtube: https://www.youtube.com/@dsysd-dev
github: https://github.com/dsysd-dev
medium: https://medium.com/@dsysd-dev
email: dsysd.mail@gmail.com
linkedin: https://www.linkedin.com/in/dsysd-dev/
newsletter: https://dsysd.beehiiv.com/subscribe
gumroad: https://dsysd.gumroad.com/