DOCSEARCHbyAlgolia
Submit Docs

System Design Primer

repository·master·Indexed 32 days ago

https://github.com/donnemartin/system-design-primer

A comprehensive guide for learning to design scalable, highly available distributed systems. Includes structured methodologies, architectural patterns, real-world case studies, and interview preparation resources such as Anki flashcards and practice questions for system and object-oriented design.

Tokens
65.8K
Snippets
38
Records
216
Agent score
98%

What's inside system-design-primer

  1. Overview of the System Design Primer

    master
    The System Design Primer is an organized collection of resources designed to help engineers learn how to design large-scale systems and prepare for technical system design interviews. It provides a structured way to learn system design principles through an index of topics, study guides, and practice interview questions with sample solutions (discussions, code, and diagrams).

  2. Overview of System Design topics

    master

    The repository provides a structured index of system design topics, emphasizing that every architectural choice involves trade-offs. Key areas covered include:

    • Scalability & Performance: Performance vs Scalability, Latency vs Throughput.
    • Availability & Consistency: CAP Theorem (CP vs AP), Consistency patterns (Weak, Eventual, Strong), and Availability patterns (Failover, Replication).
    • Networking: DNS, CDN (Push vs Pull), Load Balancers (L4 vs L7, Active/Passive, Active/Active), and Reverse Proxies.
    • Application Layer: Microservices and Service Discovery.
    • Databases: RDBMS (Master/Slave, Master/Master, Federation, Sharding, Denormalization, SQL Tuning) and NoSQL (Key/Value, Document, Wide Column, Graph).
    • Caching: Client, CDN, Web Server, Database, and Application caching; Caching strategies (Cache-aside, Write-through, Write-behind, Refresh-ahead).
    • Asynchronous Processing: Message Queues, Task Queues, and Backpressure.
    • Communication Protocols: TCP, UDP, RPC, and REST.
    • Security.

  3. Design a Pastebin-like service

    master

    A Pastebin-like service allows users to input text and receive a unique, randomly generated link to access that content later. Key requirements include support for expiration settings (defaulting to no expiration), anonymous usage, page view analytics, and automated deletion of expired pastes.

    Core Workflow for Creating a Paste:

    1. Client sends a request to the Web Server (acting as a reverse proxy).
    2. Web Server forwards the request to a Write API server.
    3. Write API server:
      • Generates a unique URL (e.g., using MD5 hash of IP + timestamp, then Base 62 encoding).
      • Checks the SQL Database to ensure the URL is unique.
      • Stores the URL and metadata in a pastes table.
      • Stores the actual text content in Object Storage (e.g., Amazon S3).
    4. Write API returns the generated URL to the client.

  4. Design a Web Crawler architecture

    master

    A web crawler system designed to handle 1 billion links and 100 billion searches per month. The architecture follows a decoupled pattern:

    Core Components

    • Crawler Service: Processes links in a loop, manages crawling priority, and handles page signatures.
    • NoSQL Database: Stores links_to_crawl (using Redis sorted sets for ranking) and crawled_links (storing page signatures to prevent cycles).
    • Reverse Index Service: Generates a reverse index of words to pages via a job queue.
    • Document Service: Generates static titles and snippets via a job queue.
    • Query API: Handles user search requests, parses queries (typo fixing, normalization), and interacts with the Reverse Index and Document services.

    Scaling Strategy

    To scale from a basic design to a high-load system, implement:

    • Load Balancers: Distribute traffic across multiple Web Servers.
    • CDNs: Cache static content closer to users.
    • Master-Slave Replicas: Scale database read capacity.
    • Iterative Approach: Benchmark, profile for bottlenecks, address them, and repeat.

  5. System Design Case Study: Designing Mint.com

    master

    This document provides a comprehensive system design walkthrough for a service similar to Mint.com. It covers the end-to-end process of defining requirements, estimating scale, designing high-level architecture, and detailing core components like account linking, transaction extraction, and budget recommendations.

    Core Use Cases

    • Account Linking: Users connect financial accounts.
    • Transaction Extraction: The service extracts transactions daily, categorizes them (supporting manual overrides), and analyzes monthly spending by category.
    • Budgeting: Users set manual budgets, and the service sends notifications when they approach or exceed them.
    • High Availability: The service must remain highly available.

    Scale and Constraints (Assumptions)

    • Users: 10 million users.
    • Accounts: 30 million financial accounts.
    • Transactions: 5 billion transactions per month.
    • Read/Write Ratio: 10:1 (Read-heavy, but with significant daily transaction writes).
    • Data Volume: ~250 GB of new transaction data per month.

  6. Design a Category Sales Rank System for Amazon

    master

    This design solves the problem of calculating and displaying the most popular products within specific categories over a rolling one-week period.

    Core Use Cases

    • Service: Calculate the most popular products per category for the past week.
    • User: Browse the most popular products per category for the past week.
    • Availability: The service must maintain high availability.

    Constraints and Assumptions

    • Scale: 10 million products, 1,000 categories, 1 billion transactions/month, and 100 billion read requests/month.
    • Read/Write Ratio: 100:1.
    • Data Characteristics: Network traffic is non-uniform; a product can exist in multiple categories; products cannot change categories; no sub-categories (e.g., foo/bar/baz).
    • Update Frequency: Results are updated once per hour.

  8. Design Mint.com: Requirements and Constraints

    master

    A system design case study for building a financial management service similar to Mint.com.

    Core Use Cases

    • Account Connection: Users connect financial accounts.
    • Transaction Extraction: The service extracts transactions daily, categorizes them (allowing manual overrides), and analyzes monthly spending by category.
    • Budget Recommendations: The service provides budget templates based on income, allows manual overrides, and sends notifications when users approach or exceed budgets.
    • High Availability: The system must remain highly available.

    Scale and Constraints

    • Users: 10 million users.
    • Accounts: 30 million financial accounts.
    • Transactions: 5 billion transactions per month.
    • Read/Write Ratio: 10:1 (Read-heavy, but with high write volume from daily transactions).
    • Throughput: ~2,000 transactions per second (TPS) and ~200 read requests per second.

  9. Understand fundamental system design trade-offs

    master

    System design is centered around managing trade-offs. Key concepts to master include:

    Performance vs. Scalability

    • Performance: How fast a system is for a single user (latency/speed).
    • Scalability: How well the system handles increased load (throughput/capacity).
    • Rule of thumb: A performance problem means the system is slow for one user; a scalability problem means it is fast for one user but slow under heavy load.

    Latency vs. Throughput

    • Latency: The time taken to perform a single action.
    • Throughput: The number of actions performed per unit of time.
    • Goal: Aim for maximal throughput with acceptable latency.

    Availability vs. Consistency (CAP Theorem)

    In a distributed system, you can only guarantee two of the following three:

    • Consistency: Every read receives the most recent write or an error.
    • Availability: Every request receives a response (without guarantee it's the latest version).
    • Partition Tolerance: The system continues to operate despite network failures.

    Common Trade-off Patterns:

    • CP (Consistency + Partition Tolerance): Best for business needs requiring atomic reads/writes. May result in timeouts during partitions.
    • AP (Availability + Partition Tolerance): Best for highly available systems that can tolerate eventual consistency.

  10. Choose between SQL and NoSQL

    master

    Deciding between SQL and NoSQL depends on your data structure and scaling requirements.

    Choose SQL when:

    • You have structured data with a strict schema.
    • You have relational data requiring complex JOIN operations.
    • You require ACID transactions.
    • You need a clear, well-established scaling pattern.
    • You want to leverage a vast ecosystem of tools and developers.
    • You need fast queries via indexes.

    Choose NoSQL when:

    • You have semi-structured or unstructured data.
    • You need a dynamic or flexible schema.
    • You do not require complex joins.
    • You need to store massive amounts of data (TB/PB scale).
    • You have high-throughput, data-intensive workloads (high IOPS).

    Typical NoSQL Use Cases:

    • Event tracking and log data.
    • Leaderboards or scoring data.
    • Temporary data (e.g., shopping carts).
    • "Hot" tables that are frequently accessed.
    • Metadata or lookup tables.

  11. Use asynchronous patterns and microservices

    master

    To decouple components and handle load spikes, consider these patterns:

    • Message Queues: For asynchronous communication between services.
    • Task Queues: For offloading background processing.
    • Back-pressure: Mechanisms to prevent a system from being overwhelmed by too many requests.
    • Microservices: Breaking a monolithic application into smaller, independent services.

  12. Understand Availability Patterns: Failover and Replication

    master

    Availability can be managed through two primary patterns: Failover and Replication.

    Failover Patterns

    • Active-to-Standby (AP Mode): Heartbeat signals are sent between active and standby machines. If the heartbeat is interrupted, the standby machine takes over the active machine's IP address. The downtime depends on whether the standby is in a "hot" or "cold" state. Only the active machine handles user traffic.
    • Active-to-Active (AA Mode): Both servers handle traffic, and load is distributed between them. For external networks, DNS must know both IPs; for internal networks, the application logic must be aware of both machines.

    Failover Drawbacks

    • Increases hardware requirements and complexity.
    • Risk of data loss if the system fails before new writes are replicated to the standby machine.

    Replication Mechanisms

    Replication involves moving data between nodes, categorized into:

    • Active-to-Standby Replication
    • Active-to-Active Replication