for last one week, i spent my time learning and coding in Go.
i wouldn't call myself an expert yet, or even good at it, but i can now read, understand, and write Go to quite an extent.
i have spent the last 2 years writing backend systems in JavaScript and Node.js, over a year for startups as an intern and another year for my personal projects. but the primary reason i decided to learn and build backends in Go is in read this post about why i decided to learn Go.
so i did that.
i learnt the basics of Go, made one small project, and then started looking for projects that actually involved backend concepts, something new for me to learn, and something i could use Go to build.
i came across a blog from Allegro where they used Go to build a fast cache system for an API, and i decided, yes, this is what i want to build as my first backend project in Go.
before building the project, i started with a blank .md file in Zed and noted down everything i thought was needed and whatever i understood from that blog, from requirements to implementation, bottlenecks, the approach to get over those bottlenecks, etc.
based on my notes, i drew up a diagram, a flow diagram of how the whole thing should work.
i decided to name the project ShardCache, which literally means sharded cache. why it's sharded will make more sense going forward, when we get to concurrency, goroutines, and the problem with having one big cache.
what this is looking to solve
the cache service should be able to handle 10,000 requests per second, split evenly between 5,000 reads and 5,000 writes. each cache entry should have a minimum lifetime of 10 minutes.
the average response time should stay around 5ms, with the 99th percentile below 10ms.
the service should also support POST requests with JSON payloads up to 500KB, where each entry follows a simple {key: value} structure.
finally, once an entry is added through a POST request, it should be possible to immediately fetch that same entry through a GET request.
before we go further, we need to look at a few things like what concurrency is and what Go features like goroutines mean.
what is concurrency?
concurrency is the ability of a program to work on multiple tasks during the same period of time.
it doesn't necessarily mean that all tasks are executing at the exact same moment. instead, the program can switch between tasks and make progress on multiple things without waiting for one task to completely finish before starting another.
for a cache server, this matters because multiple clients can send requests at the same time. one request might be reading a value while another is writing a different value.
if the cache can safely handle these operations concurrently, it can serve more requests without making every request wait for the previous one to finish.
what are goroutines?
a goroutine is a lightweight unit of execution managed by the Go runtime.
you can start one by simply using the go keyword before a function call:
go handleRequest()
goroutines are much cheaper than traditional OS threads, so a Go application can have thousands of them running concurrently.
this makes goroutines a natural fit for a server like ShardCache. multiple requests can be handled concurrently, while synchronization mechanisms like mutexes make sure multiple goroutines accessing the same data don't cause race conditions or corrupt the cache.
how the cache should work
the cache should remain fast even with millions of entries and support concurrent access, allowing multiple goroutines to read from and write to the cache safely without unnecessarily blocking each other or enforcing a certain access order.
it should also handle automatic expiration, removing cached entries after a fixed amount of time so that stale data does not remain in memory indefinitely.
why shard the cache instead of one big cache?
the issue here is that, based on our requirements, we do need concurrency to perform well.
our service will receive many requests concurrently, and we need to provide concurrent access to the cache.
now, to make access to the cache safe, we need some kind of synchronization mechanism. one simple approach would be to have a single mutex protecting the entire cache.
but if every write has to acquire the same lock, only one goroutine can modify the cache at a time. even if two goroutines are trying to modify completely different keys, they would still have to wait for each other.
this creates a bottleneck because the lock is protecting the entire cache instead of just the part of the cache that is actually being modified.
so the question becomes:
can we split the cache into smaller parts and have each part manage its own lock?
that's where sharding comes in.
implementing shards to get over the bottleneck
the way to get over this bottleneck is by implementing shards of the cache.
we split the cache into N shards. this is a fixed number in my implementation, and each shard has its own lock.
now, if two goroutines are working with keys that belong to different shards, they can acquire the locks for those different shards and modify them at the same time.
this reduces lock contention because we are no longer protecting the entire cache with one lock.
the way a key gets assigned to a shard is through hashing and modulo partitioning.
what i basically do is take the key and hash it using New32a, which gives me a 32-bit FNV-1a hash. then i take that hash and perform modulo N, where N is the number of shards.
this gives me the index of the shard where that key should live.
func (c *Cache) GetShard(key string) *Shard {
h := fnv.New32a()
h.Write([]byte(key))
index := h.Sum32() % uint32(len(c.shards))
return &c.shards[index]
}
this returns the shard from the shards slice, which belongs to the Cache struct. all the shards belong to the same cache, but each shard manages its own data and lock.
writing into the shard
when a key-value pair is passed to the Set function, the key is first used to determine which shard it belongs to through the GetShard function.
once the shard is identified, we acquire its mutex lock so that the data can be modified safely while other goroutines are prevented from modifying that same shard at the same time.
the value is then stored in the shard's map.
we also check whether the key already exists in the shard's eviction queue. if it does, we update its creation time and run the eviction handler.
if the key doesn't exist, we create a new eviction entry and add it to the queue.
finally, the eviction handler checks for expired entries while the shard lock is still held, ensuring that the cache and eviction queue remain consistent throughout the operation.
// passing key and value to set function
// then the key is used to get the shard on which the value is to be set , using the GetShard function
// once the shard is obtained , we lock it and set the value
// then unlock it
func (c *Cache) Set(key, value string) {
shard := c.GetShard(key)
shard.mu.Lock()
defer shard.mu.Unlock()
shard.data[key] = value
// for shards eviction queue if key already exists in the queue then pick it and update its creation time
for _, eviction := range shard.evictions {
if eviction.key == key {
eviction.creationTime = time.Now()
HandleEviction(shard, shard.evictions)
return
}
}
// if the key does not exist in the eviction queue, add it
shard.evictions = append(shard.evictions, NewEviction(key))
// handles evictions while setting the value , because lock is held
HandleEviction(shard, shard.evictions)
}eviction mechanism
eviction flow
whenever a new entry is added to the cache, its key and creation timestamp are stored in a FIFO eviction queue.
an eviction entry looks like this:
type Eviction struct {
key string
creationTime time.Time
}during the next cache write, the cache checks the oldest entry in the queue and compares its creation time with the current time.
if the entry has exceeded the configured TTL, it is removed from both the eviction queue and the cache.
the process continues with the next oldest entry until it reaches an entry that hasn't expired yet.
func HandleEviction(shard *Shard, evictions []*Eviction) {
for {
// check if the oldest eviction is expired
oldest := evictions[0]
// if not expired, break the loop because ofc newer ones are not expired yet
if !oldest.IsExpired() {
break
}
// if the oldest eviction is expired, delete it and move to the next one
delete(shard.data, oldest.key)
evictions = evictions[1:]
}
}eviction is handled during writes because the cache lock is already acquired, so we can safely modify both the cache and the eviction queue without introducing another synchronization mechanism.
for an existing key, the cache treats the new value as an update rather than creating another entry.
the value is replaced with the new one, and its creation timestamp is refreshed so that the updated entry gets a new TTL.
this keeps the eviction queue consistent while ensuring that overwriting a key effectively resets its expiration time.
diagram
the eviction flow looks like this:
you can access the codebase here:
https://github.com/anshumancodes/ShardCache
i will soon be publishing a YouTube video building this project end to end.
thanks for reading the blog.