I often tend to stumble upon a basic problem and then try to solve it with some external library. In this case I was thinking about caching some data in memory to spare some time and resources on an external API. This time I've decided to write something myself instead of using an external library. And with that you can even learn something from it.

So let's write a very basic in-memory cache in Go.

Requirements

The cache should be able to store key-value pairs. We should be able to set a key-value pair, get a value by key, and delete a key-value pair.

Each key-value pair should have a time-to-live (TTL) value and should be automatically deleted after the TTL has expired. There are different ways to achieve that, but we will come back to this later.

The interface for the cache is very simple and only contains the following 3 methods:

type Cache interface {
	Set(key string, value any)
	Get(key string) (any, bool)
    Delete(key string)
}

Implementation

We can represent the cache as a map of keys to a struct (CacheItem) that holds the value and the time when it was added or should be expiring.

type CacheItem struct {
    Value any
    Expiration time.Time
}

There are two design decisions to make here.

1. We can decide to only store specific values in the cache, e.g. only strings.
2. For the expiration we can decide to use a fixed time or a relative time. Additionally, we can decide between the time when the item was added or the time when the item should expire.

As the cache is very basic, we will use the any type for the value and the time when the item should expire. We have to keep in mind to add the expiration time when adding an item to the cache.

expiration := time.Now().Add(c.expiration).UnixNano()

As we want to have somewhat good time precision, we use the UnixNano() function to get the current time in nanoseconds. This enables us to store the time as a simple int64 value in our CacheItem.

type CacheItem struct {
    Value any
    Expiration int64
}

To enable concurrent access to the cache we have to use a mutex. Go provides a sync package that contains a Mutex and a RWMutex. With that we can easily protect our cache from concurrent access.

The Set, Get and Delete methods are straight forward:

Set locks the map and inserts the value by wrapping it in a CacheItem. We will cover the Expiration value in a second.

Get read locks the map and is checking if a value for the given key exists, if yes we return it, if not then nothing will be returned. Additionally, there is a boolean value to indicate if there was an item found. This could also return an error, but let's keep it simple for now.

Delete locks the map and deletes the key-value pair from the map.

const defaultExpirationTime = 10 * time.Second

type CacheItem struct {
	Value      any
	Expiration int64
}

type Cache struct {
	mu    sync.RWMutex
	items map[string]CacheItem
}

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

	c.items[key] = CacheItem{
		Value:      value,
		Expiration: time.Now().Add(defaultExpirationTime).UnixNano(),
	}
}

func (c *Cache) Get(key string) (any, bool) {
	c.mu.RLock()
	defer c.mu.RUnlock()

	item, ok := c.items[key]
	if !ok {
		return nil, false
	}

	return item.Value, true
}

func (c *Cache) Delete(key string) {
	c.mu.Lock()
	defer c.mu.Unlock()
	delete(c.items, key)
}

With that we have an in-memory cache that can be read or written to by multiple goroutines. But our values will be kept forever, if we don't delete them manually. So let's talk about the eviction behavior we defined earlier.

Eviction

There are multiple ways to evict items from the cache. Well, there are also multiple different algorithms to evict, but for now let's keep it simple and stick with the original requirements.

1. We can evict expired items on every access.
2. We can evict expired items in the background.

For the first option we would have to check if the item is expired every time we access the cache, which would be very inefficient. Therefor we will use the second option.

To delete expired items from the cache we can use a simple goroutine that runs in the background and checks for expired items. We can use a time.Ticker to check for expired items every second.

func (c *Cache) StartEvict() {
	ticker := time.NewTicker(time.Second)

	for {
		select {
		case <-ticker.C:
			c.evict()
		}
	}
}

The evict methods checks for expired items and deletes them from the cache. As we are just using a simple map, we can iterate over all items and check if the expiration time is in the past and call the delete function.

func (c *Cache) evict() {
	c.mu.Lock()
	defer c.mu.Unlock()

	for key, item := range c.items {
		if time.Now().UnixNano() > item.Expiration {
			fmt.Println("\tEvicting: ", key)
			delete(c.items, key)
		}
	}
}

A downside of this approach is that we have to lock the cache while we are evicting items, and we are doing this every second.

It might not be the most elegant or efficient way, but it fulfills our requirements and is only around 50 lines of code.

Improvements

There are a few improvements that can be made to this simple cache.

1. Support for different expiration times for each item.
2. Support for different eviction strategies like Least Recently Used (LRU) or First In First Out (FIFO) instead of just time based eviction.
3. Dynamic eviction times based on the size of the cache. Currently, we just check every second for expired items, but we could vary the time based on the size of the cache.
4. Persist the cache to disk. This would enable us to restore the cache after a restart of the application.
5. Properly handle shutdown.
6. There are more improvements that can be made, but these are the most obvious ones.

Conclusion

Of course this is not really production ready as it is nether very efficient nor fast. But for a hobby project that is doing a few API calls and has to spare some requests, it might be enough. And there was no need to fetch any external dependencies in our project!