System Design Interview – An insider's guide

1. Scaling Systems from Zero to Millions of Users

Designing a system that supports millions of users is challenging, and it is a journey that requires continuous refinement and endless improvement.

Start Small, Scale Incrementally. Building a system for millions of users begins with a simple, single-server setup. This initial architecture handles all components—web app, database, and cache—on one machine. As the user base grows, the system evolves through strategic scaling techniques.

Key Scaling Techniques. The transition from a single server to a large-scale system involves several critical steps:

• Separating the web and data tiers to allow independent scaling.
• Implementing horizontal scaling by adding more servers to a pool of resources.
• Introducing load balancers to distribute incoming traffic evenly.
• Employing database replication for failover and redundancy.
• Adding a cache layer to improve response times and reduce database load.
• Using a Content Delivery Network (CDN) to serve static content efficiently.

Statelessness and Multi-Data Centers. Achieving horizontal scalability requires a stateless web tier, where user session data is stored in a persistent data store. Supporting multiple data centers improves availability and user experience across geographical areas. Message queues decouple system components, allowing them to scale independently and enhancing failure resilience.

2. Back-of-the-Envelope Estimation for System Design

Back-of-the-envelope calculations are estimates you create using a combination of thought experiments and common performance numbers to get a good feel for which designs will meet your requirements.

Importance of Estimation. In system design interviews, back-of-the-envelope estimations are crucial for assessing system capacity and performance requirements. These calculations help determine the feasibility of different design choices and identify potential bottlenecks. Understanding scalability basics, such as powers of two, latency numbers, and availability numbers, is essential for effective estimation.

Key Concepts and Numbers. Essential knowledge includes:

• Understanding data volume units using powers of two (e.g., KB, MB, GB, TB, PB).
• Knowing typical latency numbers for computer operations (e.g., memory access, disk seek, network transfer).
• Understanding availability numbers and their corresponding downtime (e.g., 99%, 99.9%, 99.99%).

Estimation Tips and Techniques. Effective back-of-the-envelope estimation involves:

• Rounding and approximation to simplify calculations.
• Writing down assumptions to maintain clarity and reference later.
• Labeling units to avoid ambiguity.
• Practicing common estimations such as QPS, peak QPS, storage, and cache requirements.

3. A Structured Framework for System Design Interviews

The system design interview simulates real-life problem solving where two co-workers collaborate on an ambiguous problem and come up with a solution that meets their goals.

The Collaborative Nature of System Design. System design interviews are not about finding the "right" answer but about demonstrating problem-solving skills, communication abilities, and the capacity to collaborate. The process involves analyzing a vague problem, proposing solutions, defending design choices, and responding constructively to feedback.

A Four-Step Process. A structured approach to system design interviews includes:

1. Understanding the problem and establishing the design scope.
2. Proposing a high-level design and getting buy-in from the interviewer.
3. Conducting a deep dive into specific components.
4. Wrapping up with follow-up questions and potential improvements.

Key Skills and Considerations. Success in system design interviews requires:

• Asking clarifying questions to understand requirements.
• Collaborating with the interviewer as a teammate.
• Suggesting multiple approaches and evaluating tradeoffs.
• Identifying potential bottlenecks and proposing improvements.
• Communicating your thought process clearly and effectively.

4. Designing a Robust Rate Limiter

In a network system, a rate limiter is used to control the rate of traffic sent by a client or a service.

Purpose of Rate Limiting. Rate limiters are essential for controlling traffic, preventing resource starvation, reducing costs, and protecting servers from being overloaded. They limit the number of client requests allowed over a specified period, blocking excess calls.

Implementation Approaches. Rate limiters can be implemented on the client-side, server-side, or as a middleware component. Server-side and middleware implementations are more reliable due to the potential for malicious actors to bypass client-side controls. API gateways often include rate-limiting functionality as part of their broader set of services.

Rate Limiting Algorithms. Common algorithms include:

• Token bucket: Allows bursts of traffic while maintaining an average rate.
• Leaking bucket: Processes requests at a fixed rate, suitable for stable outflow.
• Fixed window counter: Simple but can allow more requests than the quota at window edges.
• Sliding window log: Accurate but memory-intensive.
• Sliding window counter: A hybrid approach that balances accuracy and memory usage.

5. Consistent Hashing for Distributed Systems

Consistent hashing is a special kind of hashing such that when a hash table is re-sized and consistent hashing is used, only k/n keys need to be remapped on average, where k is the number of keys, and n is the number of slots.

Addressing the Rehashing Problem. Traditional hashing methods suffer from significant redistribution when servers are added or removed, leading to cache misses and performance degradation. Consistent hashing minimizes this issue by ensuring that only a small fraction of keys need to be remapped.

Hash Space and Hash Ring. Consistent hashing involves mapping servers and keys onto a hash ring using a uniformly distributed hash function. To determine which server a key is stored on, one moves clockwise from the key's position until a server is found.

Virtual Nodes and Improved Distribution. To address issues of non-uniform key distribution and varying partition sizes, virtual nodes (or replicas) are used. Each server is represented by multiple virtual nodes on the ring, leading to a more balanced distribution of keys and reduced standard deviation.

6. Building a Scalable Key-Value Store

A key-value store, also referred to as a key-value database, is a non-relational database.

Key-Value Store Fundamentals. Key-value stores are non-relational databases that store data as key-value pairs, offering high scalability and low latency. They are well-suited for applications requiring fast access to data without complex relationships.

CAP Theorem and Consistency Models. Designing a distributed key-value store involves understanding the CAP theorem, which states that a distributed system can only provide two of the following three guarantees: consistency, availability, and partition tolerance. Consistency models, such as strong consistency, weak consistency, and eventual consistency, define the degree of data consistency.

Core Components and Techniques. Key components and techniques include:

• Data partitioning using consistent hashing.
• Data replication for high availability and reliability.
• Quorum consensus to guarantee consistency for read and write operations.
• Versioning and vector clocks to resolve inconsistencies.
• Failure detection and resolution strategies, such as gossip protocol and hinted handoff.

7. Unique ID Generation in Distributed Environments

In this chapter, you are asked to design a unique ID generator in distributed systems.

Challenges of Distributed ID Generation. Generating unique IDs in a distributed system is challenging due to the limitations of traditional auto-increment features in databases. The requirements for unique IDs typically include uniqueness, sortability, numerical values, and fitting within a 64-bit format.

Approaches to Unique ID Generation. Several approaches can be used:

• Multi-master replication: Uses database auto-increment but faces scalability and time-ordering issues.
• Universally Unique Identifier (UUID): Simple but generates 128-bit non-numeric IDs.
• Ticket server: Uses a centralized auto-increment feature but introduces a single point of failure.
• Twitter snowflake approach: Divides an ID into sections for timestamp, datacenter ID, machine ID, and sequence number.

Twitter Snowflake Approach. The Twitter snowflake approach divides a 64-bit ID into sections for timestamp (41 bits), datacenter ID (5 bits), machine ID (5 bits), and sequence number (12 bits). This design ensures uniqueness, sortability, and scalability.

8. URL Shortener Design and Implementation

In this chapter, we will tackle an interesting and classic system design interview question: designing a URL shortening service like tinyurl.

Core Functionality and API Design. A URL shortener service converts long URLs into shorter aliases, enabling easy sharing and tracking. The primary API endpoints include:

• URL shortening: Accepts a long URL and returns a short URL.
• URL redirecting: Accepts a short URL and redirects to the original long URL.

URL Redirecting and HTTP Status Codes. URL redirecting can be implemented using 301 (permanent) or 302 (temporary) redirects. A 301 redirect reduces server load by caching the response in the browser, while a 302 redirect allows for tracking click rates and sources.

Hash Function Design. The hash function maps a long URL to a short alias. Two common approaches are:

• Hash + collision resolution: Uses a hash function like CRC32, MD5, or SHA-1, and resolves collisions by appending a new string until no collision is found.
• Base 62 conversion: Converts a unique ID to a base 62 representation using characters [0-9, a-z, A-Z].

9. Web Crawler Architecture and Techniques

In this chapter, we focus on web crawler design: an interesting and classic system design interview question.

Web Crawler Fundamentals. A web crawler, or spider, discovers new or updated content on the web by following links on web pages. It is used for search engine indexing, web archiving, web mining, and web monitoring.

Key Components and Workflow. A web crawler typically includes the following components:

• Seed URLs: Starting points for the crawl process.
• URL Frontier: Stores URLs to be downloaded.
• HTML Downloader: Downloads web pages.
• DNS Resolver: Translates URLs into IP addresses.
• Content Parser: Parses and validates HTML content.
• Content Seen?: Detects duplicate content.
• URL Extractor: Extracts links from HTML pages.
• URL Filter: Excludes unwanted content types and URLs.
• URL Seen?: Tracks visited URLs.
• URL Storage: Stores visited URLs.

Politeness and URL Prioritization. A well-designed web crawler should be polite by avoiding excessive requests to the same website and prioritize URLs based on usefulness. The URL frontier manages politeness by mapping website hostnames to download threads and prioritizes URLs based on PageRank, website traffic, and update frequency.

10. Notification System Design for Scalability

A notification system has already become a very popular feature for many applications in recent years.

Notification System Overview. A notification system alerts users with important information via mobile push notifications, SMS messages, and email. It is a crucial feature for many applications, requiring scalability and reliability.

Notification Types and Third-Party Services. Different notification types require different services:

• iOS push notifications: Use Apple Push Notification Service (APNS).
• Android push notifications: Use Firebase Cloud Messaging (FCM).
• SMS messages: Use third-party SMS services like Twilio or Nexmo.
• Email: Use commercial email services like Sendgrid or Mailchimp.

System Architecture and Components. A scalable notification system includes:

• API servers: Provide APIs for services to send notifications.
• Cache: Stores user info, device info, and notification templates.
• Database: Stores data about users, notifications, and settings.
• Message queues: Decouple system components and buffer notification events.
• Workers: Pull notification events from message queues and send them to third-party services.

11. News Feed System Architecture and Design

In this chapter, you are asked to design a news feed system.

News Feed System Fundamentals. A news feed system aggregates and displays content from friends, pages, and groups that a user follows. Key features include feed publishing and news feed building.

Feed Publishing and Fanout Models. Feed publishing involves writing data to cache and database and populating the news feed. Fanout models include:

• Fanout on write (push model): Pre-computes news feed during write time, offering fast retrieval but potential hotkey problems.
• Fanout on read (pull model): Generates news feed during read time, conserving resources for inactive users but slowing down retrieval.

Hybrid Approach and News Feed Retrieval. A hybrid approach combines push and pull models, using push for most users and pull for celebrities or users with many followers. News feed retrieval involves fetching news feed IDs from the cache and constructing the fully hydrated news feed with user and post objects.

12. Designing a Real-Time Chat System

In this chapter we explore the design of a chat system.

Chat System Essentials. A chat system facilitates real-time communication between users, supporting one-on-one and group chats. Key features include online presence indicators, multiple device support, and push notifications.

Communication Protocols and High-Level Components. Communication between clients and servers can be implemented using various protocols:

• Polling: Client periodically asks the server for new messages.
• Long polling: Client holds the connection open until new messages are available or a timeout occurs.
• WebSocket: Provides bidirectional and persistent connections.

System Architecture and Data Storage. A chat system typically includes:

• Stateless services: Manage login, signup, and user profiles.
• Stateful services: Handle real-time messaging and maintain persistent connections.
• Third-party integration: Provides push notifications.
• Key-value stores: Store chat history data.

Last updated: April 7, 2025