System Design Interview

Tags: sys-design

Is a kind of interview that focuses on developing a system to solve some task given a broad description of the domain. For eg. build a URL shortener? or "build a video streaming site for your mobile device?"

The approach you should take to this process should come in 2 parts.

Analysis

Break down and analyse the constraints and use cases of the system.

The goal is to see if you can gather the requirements about the problem at hand, and design a solution that covers them well. Never assume things that were not explicitly stated.

The kinds of constraints you should try to clarify includes:

The Availability of the system.
How many users (Demand) do we expect the system to recieve?
What's the expected latency or throughput?
How many times is the system expected to be used in a day?
What're the failure cases? "Can the url shortener map different URLs to the same place?"

Don't forget to state the obvious. For a URL shortener, state url => smaller url.

Abstract Design

Given the constraints and goals of the system, sketch out a general plan of how users should interact with the system. The components and services they may use and what we need to support these.

Outline the high level components of the system: For example the url shortener has:

1. Application service layer (serves the requests) - Shortening service - Redirection service 2. Data storage layer (track hash -> url mappings)

Once you've drawn these elaborate them. How does the ASL decide how to shorten a URL? does it check for copies? does it interact with the DSL? How does it generate a hash (eg. keep doing this hashed_url = base62(md5(orig_url + random_salt))[:6] until a unique hash is found). How does it redirect to a URL given a hash? What happens when the hash is not found?

Note: Try going back to system goals and mention how these services map onto them.

Bottlenecks

Given the abstract design and constraints, you should now consider the bottlenecks on the system. Things that can hamper or hinder scalability.

For example we may not receive very much traffic but we may end up with a lot of data and searching through it this many times per second may not be practical. You don't need to come up with a way to fix these bottlenecks at this point (that come in the later scalability section) but you should be considering them throughout.

Design (Scalability)

Things you should cover:

DNS (includes load balancing, caching, proxying)
CDNs (push vs pull)
Caching
Load Balancing
Server Redundancy (failover, duplication)
Database Partitioning (Sharding)

Statistics

At various stages of the interview you may be expected to infer a possible value for a constraint. For example:

Twitter has x tweets per day, that's 30x tweets per month. Assuming 1/10 tweets contains a shortened URL that's 30x / 10 per month. Assuming 80% of these are shortened by the top 3 sites, assuming we're close to this but not in the top 3 we'll get some fraction of the remaining 20%, let's says 50% to 30%. That means per month we'll be working with (30x \* 0.2 \* 0.5 / 10) URLs shortened per-day. Substituting the value for x from below we get: 150,000,000 new URLs per month. We can use this to calculate the expected number of clicks (given some assumptions on how long a shortened URL lasts and how many clicks it gets per day).

Here's some stats you may be able to use:

Facebook active users: 1.3 billion
Twitter active users: 650 Million
New Tweets per day: 500 Million