Sharding My Go Cache: Global Locks Are CIA Bloat

Sharding My Go Cache: Global Locks Are CIA Bloat

I was working on one of those projects that will never see the light of day, a Go caching library. I won't get into the details of that project, but I will eventually release the library. Eventually.

It started like any other project, very simple and naive. I had a Cache struct with a hash map of items, each item having a next and prev pointer to also act as a doubly linked list. A very clever idea, I thought, but I later found that this is a trivial technique used in caching to support both expiration-based evictions and to help the most relevant data survive by moving it to the head of the list.

The Problem

Here is a simplified version of the Cache struct. Given that this has Get, Set, Delete, and also a routine running on a ticker, see if you can foresee the issue I encountered.

type Cache struct {
    mu    sync.RWMutex
    items map[string]*Item
    head  *Item
    tail  *Item
    count uint64
    size  uint64
}

In case you didn't figure it out (same as I didn't think about this being an issue until I thought the project was almost ready), the problem is that we have a single map and a lot of operations performed on this map with a single lock.

Having one single lock guarding the entire map for every operation is a huge bottleneck and a concurrency performance issue because every operation has to wait for the lock to be released by other operations.

So, if somebody wants to write item_A and somebody else wants to read item_Z, they would have to wait for each other, even though there would be no data inconsistency if we just let them do it at the same time.

The Solution

This is the kind of issue sharding helps resolve. Instead of having one single map with one single lock, we are "sharding" or splitting the map into multiple shards, each with its own map and its own lock, hashing the key of the item into a shard index.

Here is the new structure of my data:

type shard struct {
    mu    sync.RWMutex
    items map[string]*Item
    head  *Item
    tail  *Item
    count uint64
    size  uint64
}

type Cache struct {
    shards []*shard
    size   uint64
}

func hashKey(key string) uint64 {
    // blablabla divide by the number of shards
}

This way, each shard has its own lock. So, for example, if you read, write, or do whatever on item_A which is in shard_X, you can still read, write, or do whatever on item_B which is in shard_Y.

That's pretty much it. It's as simple as it sounds, but it does have some trade-offs.

The Trade-offs

I did some reading online and saw a lot of people say a lot of things that I don't really care about. So, if you want to read about those, you are not in the right place.

I will, however, detail two issues that add unexpected complexity (skill issue on my end) that I had to deal with.

Initially, my cache had a map of maps of empty structs, I know... The purpose of this map was a reverse index for surrogate key associations. The use case would be when you cache a full HTTP response that contains item_A, and item_A is invalidated somewhere else; you want to evict the HTTP response since the data is no longer valid.

So, because this is again one map with one lock, if I keep it, I'll have the same performance bottleneck. We have to shard it as well:

type surrogateShard struct {
    mu    sync.RWMutex
    index map[string]map[string]struct{}
}

type Cache struct {
    itemShards      []*itemShard
    surrogateShards []*surrogateShard
    size            uint64
}

...which leads us to the next issue.

Because of this added complexity, we introduce a use case where both the item shards and the surrogate shards will have to lock at the same time for an operation. What can happen is that we lock shard_A and surrogateShard_X, and at the same time, in a different operation, we lock surrogateShard_X and shard_A in reverse order. So, what we have is two operations waiting on each other to release the lock, creating a deadlock.

To fix this, we need to make sure that we lock and unlock entities in a specific order every time. So, we can compare the two hashes and lock the smaller one first. This way, if we have the same use case, they will never be locked in reverse by other operations. This adds complexity to every operation performed by the cache that requires both locks, but it's necessary to avoid deadlocks.

h1 := getHash(key1)
h2 := getHash(key2)

var first, second *sync.Mutex

if h1 < h2 {
    first, second = mu1, mu2
} else {
    first, second = mu2, mu1
}

first.Lock()
second.Lock()

// Process whatever (e.g., update LRU, invalidate surrogate keys)

second.Unlock()
first.Unlock()

Conclusion

Sharding my cache map was fun, and it got me out of the monotony of a project that you think is almost done, where there's no more fun to be had because all that's left to do is refactoring and testing.

It is a very simple solution, but it adds a lot of complexity to your operations. I think it was worth it, not even for the performance boost. Let's be real: I'll be the only user of that library, and I don't need to create such performant solutions; I could've just used an existing caching library. But I'm glad I didn't (lying).

Thank you for sticking through!