Published on

“System Design Interview - An Insider's Guide” notes (Chapter1-3)

Authors
  • avatar
    Name
    Gene Zhang
    Twitter

CHAPTER 1: SCALE FROM ZERO TO MILLIONS OF USERS

How we scale our system to support millions of users:

  • Keep web tier stateless
  • Build redundancy at every tier
  • Cache data as much as you can
  • Support multiple data centers
  • Host static assets in CDN
  • Scale your data tier by sharding
  • Split tiers into individual services
  • Monitor your system and use automation tools
1-1

BACK-OF-THE-ENVELOPE ESTIMATION

Power of two

2-1

Availability numbers

2-2

Latency

Latency Numbers Every Programmer Should Know

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

Notes
-----
1 ns = 10^-9 seconds
1 us = 10^-6 seconds = 1,000 ns
1 ms = 10^-3 seconds = 1,000 us = 1,000,000 ns

Google Sheet with grpah

2-32-42-5

CHAPTER 3: A FRAMEWORK FOR SYSTEM DESIGN INTERVIEWS

Step 1: Understand the problem and establish design scope

Ask questions to understand the exact requirements:

  • What specific features are we going to build?
  • How many users does the product have?
  • How fast does the company anticipate to scale up? What are the anticipated scales in 3 months, 6 months, and a year?
  • What is the company’s technology stack? What existing services you might leverage to simplify the design?

Step 2: Propose high-level design and get buy-in

Collaborate with the interviewer during the process:

  • Come up with an initial blueprint for the design. Ask for feedback. Treat your interviewer as a teammate and work together. Many good interviewers love to talk and get involved.
  • Draw box diagrams with key components on the whiteboard or paper. This might include clients (mobile/web), APIs, web servers, data stores, cache, CDN, message queue, etc.
  • Do back-of-the-envelope calculations to evaluate if your blueprint fits the scale constraints. Think out loud. Communicate with your interviewer if back-of-the-envelope is necessary before diving into it.

Step 3 - Design deep dive

Work with the interviewer to identify and prioritize components in the architecture. In most cases, the interviewer may want you to dig into details of some system components.

For URL shortener, it is interesting to dive into the hash function design that converts a long URL to a short one. For a chat system, how to reduce latency and how to support online/offline status are two interesting topics.

View on GitHub