On System Design Interviews

Here’s the question: an API system built on Rails (or Django, or Express, …) and MySQL has seen traffic surge from 6,000 RPM to 20,000 RPM, sending the whole system’s load through the roof. You now need to design an application-layer caching scheme to bring the overall load down. The constraints: the cache can’t live at the web layer (proxies included), and you can’t use the framework’s built-in caching or any third-party cache module.

Most candidates take one look and think: easy. Drop in Redis (or memcached) between the app servers and the database. On a read, if the cache misses, hit the database and write the result into the cache; the next read of the same data hits the cache, and the database’s load drops dramatically.

Is that right? Hard to say. Maybe. Maybe not. But blurt it out that fast and you will, with near certainty, be written off by the interviewer.

A system design interview is about discussion and exchange — clarifying every constraint, and then finding a reasonably sound solution within those constraints. It is not a coding problem or an algorithms problem, where nailing down the requirements lets you start writing the answer.

A good candidate should ask questions proactively, trying to surface as many constraints as possible rather than simply assuming. Take the answer above: the candidate hasn’t even begun to seriously analyze where the problem lies, yet has already taken it for granted that the pressure is on the database side (yes, after a traffic surge there’s a 90% chance the database is the first to fold — but that is an assumption, not a premise), and starting from a possibly wrong premise inevitably leads to a probably wrong solution.

So the more sensible line of thinking is:

What does the existing system’s architecture look like?

When the project is optimizing an existing system, designing before you understand that system’s architecture and its history (how it evolved and why — though in an interview you can skip this part) is plain hooliganism.

• How many web servers, app servers, and database servers are there, and how do they relate to one another?
• Is there already something like Redis / memcached in place? If so, what workloads does it handle? (Ask this and you earn a big bonus.)

Which part of the system is under the most pressure right now?

This question matters enormously — you need to know where the problem is before you can think about optimizing. If the problem is in the app servers, you may need page-level caching; if the problem is in the database servers, you can do data-level or page-level caching.

What capacity are we aiming for?

Many candidates with years of frontline experience skip straight to concrete solutions in a system design like this, without ever asking what capacity is actually needed. That won’t do. Capacity varies from problem to problem; in this case you should at minimum consider 1) the cache system’s throughput per second, and 2) the cache system’s storage capacity. For a request volume of 20k RPM, the cache system should be able to withstand 50k, 100k, or even 200k RPM. As for capacity, you should consider how much you’d need assuming every distinct request gets cached (the worst case), whether that capacity is achievable under the given hardware and software constraints, and if not, what upper bound would be reasonable.

Once you have that goal, you also need a real feel for the tools you intend to use. One candidate told me he’d use Redis because Redis is fast. “Fast” is a vaporous notion, so I asked him: for a 1k-sized value on commodity hardware, what QPS do you think Redis can handle for a GET? He had no idea whatsoever; I asked him to guess, and he actually offered an estimate of 3–5k QPS. From my own recollection, Redis benchmark GET operations land around the 100k order of magnitude — sure, returning 1k of data each time drags that number down, but it would never be off by two orders of magnitude.

With a sense of design capacity in hand, we need to know the size of the data to be cached. Median size, average size, and max size all need to be understood, at least well enough to know the order of magnitude. Handling 2k-sized responses and 200k-sized responses may be entirely different problems: if your cache capacity is 1M entries, caching 2k payloads directly consumes 2G of memory, whereas 200k payloads would consume 200G — the latter obviously can’t be cached in memory and must use the filesystem cache.

Speaking of the filesystem, let me add a couple of words. When using the filesystem as a cache, note that a Unix directory is in fact a map recording the correspondence between filenames and inodes (you can see this with ls -ai1 .). The more files there are in a single directory, the larger that map grows, and the more read operations it takes (a typical system call reads 32k or thereabouts each time), so when a directory holds a very large number of files, access efficiency degrades sharply. This is why common file-cache systems use two-level or even multi-level directories: for 1M files, use two letters or digits for the first level, giving (26 + 10) squared second-level directories — that is, 1296 directories, each directory name two bytes, plus inode and other overhead, 10–20 bytes is plenty. One read retrieves all the second-level entries, and each second-level directory holds an average of 772 files, retrievable in a single read too — two reads total to locate the cache file. Put 1M files in a single directory instead, at 32 bytes per entry, and you need 1000 reads. This tiered-caching idea shows up in many systems, TLB among them (though multi-level TLBs are mainly about saving memory).

Is there room to optimize the design?

These days memory and disks are dirt cheap, and in system design we often no longer need to shave details bit by bit or byte by byte — but that doesn’t mean better, more memory-frugal, faster-running solutions are worthless. I once discussed a system design optimization with a candidate in an interview, and he simply couldn’t understand why I was “forcing” him to optimize the algorithm. He figured computation is so cheap, money is no object, just add a few more machines and run in parallel. That’s a wrong attitude toward the craft.

Never forget that design should be future-facing: if switching to a better algorithm can save you tens of times the memory (bitmap vs. hashmap) or tens of times the computation (bloom filter pre-filter vs. raw computation), then what you save is not just resources (or money) today, but time tomorrow — because when your application sees 10x the traffic, you’ll still be able to handle it with ease.

Moreover, optimization can turn quantitative change into qualitative change. If an analytics application can only complete one analysis every five minutes, it manages just 12 analyses an hour; optimize it to 30 seconds and it could do 120 an hour, letting users grasp trends far sooner.

A designer who thinks resources are no problem and money is no problem can only ever be a mediocre designer.

Every serious programmer should see themselves this way: In me the tiger sniffs the rose.