System Design Interview
Chapter 1: Scale From Zero To Millions Of Users
Chapter 2: Back-of-the-envelope Estimation
Chapter 3: A Framework For System Design Interviews
Chapter 4: Design A Rate Limiter
Chapter 5: Design Consistent Hashing
Chapter 6: Design A Key-value Store
Chapter 7: Design A Unique Id Generator In Distributed Systems
Chapter 8: Design A Url Shortener
Chapter 9: Design A Web Crawler
Chapter 10: Design A Notification System
Chapter 11: Design A News Feed System
Chapter 12: Design A Chat System
Chapter 13: Design A Search Autocomplete System
Chapter 14: Design Youtube
Chapter 15: Design Google Drive
Chapter 16: The Learning Continues

Chapter 1: Scale From Zero To Millions Of Users

A single servers to multiple ones

Without load balancers to with ones

Vertical/Horizontal scaling

  • Vertical scaling: increase CPU, RAM, DISK
  • Horizontal scaling: add servers

Master-Slave combination of databases

  • Master Master, Master Slave, Master multiple Slaves
  • If the slave goes down, another is replaced.
  • If the master, one of the slave is promoted to master.

Cashe/CDN is a double-edged sword

geo replication


celebrity problem

celebrity problemなんてものがあるらしい。インフルエンサーがサービスの設計に影響を与える。。

2010: "At any moment, Justin Bieber uses 3% of our infrastructure.

In Twitter’s early days, only one celebrity could tweet at a time

Chapter 7: Design A Unique Id Generator In Distributed Systems

Auto-increment allows a unique number to be generated automatically when a new record is inserted into a table.


  • IDs must be unique. (ユニーク、ただひとつであること)
  • IDs are numrical values only. (数値型のみ)
  • IDs fit into 64-bit. (64bitにおさまること)
  • IDs are ordered by date.
  • Ability to generate over 10.000 unique IDs / second. (秒速10,000のIDを発行できること)

How to generate IDs in distributed systems

  • auto_inrements(DBが提供する自動採番)
  • UUID
  • Snowflake/Katsubushi


  • Hard to scale up with multiple data centers(Only writer is responsible for generating IDs)
  • IDs do not go up with time across multiple svs
  • It does not scale well when a sv is added/removed.


  • Pros: Easy to scale because each Web SV is responsible for generating IDs.
  • Cons: 128 bit long, req is 64 bit.