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.

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

• 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.

• 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.

• 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]any
 expiry    time.Duration
 evictPool chan struct{} // we don't want infinite goroutines
 mutex     sync.RWMutex
}

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

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

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

func (c *Cache) Get(key string) (any, 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
 }

 // start eviction goroutine
 go func() {
  c.evict(key)
  <-c.evictPool // free the pool, so more eviction can be scheduled
 }()
}

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.

An important note

This program is still far from perfect, the idea was to show you use of channels for creating a goroutine pool, but this won't work in case of high throughput system, we will design a better system for that in the next post.

Claps Please!

If you found this article helpful I would appreciate some claps 👏👏👏👏, it motivates me to write more such useful articles in the future.

Follow me for regular awesome content and insights.
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/
Dev.to: https://dev.to/dsysd_dev/