Scaling Memcached to 1,000,000,000 QPS - Replication vs. Data Sharding

This blog answers one question: When forced to scale, should data be sharded or replicated?

Facebook faced this challenge in 2010, building their distributed caching system. They had petabytes of data to store, and a single instance couldn't manage the heat.

As they added new instances, they had to decide if they wanted to replicate existing instances, or split data amongst them.

The image below speaks a thousand words.

Figure 1 - Replication vs. Sharding

For small systems, this question is immaterial. At InterviewReady, we could load our entire database into memory and still not feel a pinch 😛

But Facebook handled billions of queries per second, even back in 2010!

And the decision to shard or replicate data, helped them scale their cache servers.

Data sharding

In this approach, we assign unique key ranges to every server. This effectively shards the data (imagine a glass window being broken into shards).

Since the key ranges don't overlap, we have unique data in every shard. None of the caches duplicate keys, meaning we can completely fill all of the cache servers with unique data.

The result is high cache hit rates.

Figure 2 - Ideal effect of Data Sharding.

Such routing also allows all requests to a shard to have read-after-write consistency. Requests for keys in a shard are processed sequentially, avoiding concurrency issues.

Scaling into unique shards is a good approach in most cases, but not for Facebook.

To understand this, think of how an Instagram app loads. It fetches various details like recommended posts, likes, comments, replies, notifications, etc… in one query.

Your access pattern is going to look like this.

Figure 3 - The actual effect of Data Sharding on Facebook.

Each user query hits multiple shards. This is called read amplification.

When a server managing 100k requests is split into different shards, each shard must now serve 100k requests.

Data Replication

If data is replicated across servers, then every user query can be served using a single server. As we scale out, requests will be distributed evenly, leading to reduced average load.

Figure 4 - Replication lets requests be answered in a single server.

This approach is simpler, and more suitable for fetching multiple keys per query. Facebook decided to use data replication for Memcached.

They traded off data consistency and cache hit rates for high scalability. In the cache of Memcached, the trade-off was worth it.

Final Thoughts

If you are tasked with making this choice, here are some points to keep in mind.

If you like system design and software engineering, check out our detailed System Design Course.

Thanks for reading!