book

Acing the System Design Interview

by zhiyong tan

January 2024

Intermediate to advanced

472 pages

15h 11m

English

Manning Publications

Read now

Unlock full access

forewordprefaceacknowledgmentsabout this bookWho should read this bookHow this book is organized: A roadmapliveBook discussion forumOther online resourcesabout the authorabout the cover illustration
1.1 A discussion about tradeoffs1.2 Should you read this book?1.3 Overview of this book1.4 Prelude: A brief discussion of scaling the various services of a system1.4.1 The beginning: A small initial deployment of our app1.4.2 Scaling with GeoDNS1.4.3 Adding a caching service1.4.4 Content distribution network1.4.5 A brief discussion of horizontal scalability and cluster management, continuous integration, and continuous deployment1.4.6 Functional partitioning and centralization of cross-cutting concerns1.4.7 Batch and streaming extract, transform, and load (ETL)1.4.8 Other common services1.4.9 Cloud vs. bare metal1.4.10 Serverless: Function as a Service (FaaS)1.4.11 Conclusion: Scaling backend servicesSummary
2.1 Clarify requirements and discuss tradeoffs2.2 Draft the API specification2.2.1 Common API endpoints2.3 Connections and processing between users and data2.4 Design the data model2.4.1 Example of the disadvantages of multiple services sharing databases2.4.2 A possible technique to prevent concurrent user update conflicts2.5 Logging, monitoring, and alerting2.5.1 The importance of monitoring2.5.2 Observability2.5.3 Responding to alerts2.5.4 Application-level logging tools2.5.5 Streaming and batch audit of data quality2.5.6 Anomaly detection to detect data anomalies2.5.7 Silent errors and auditing2.5.8 Further reading on observability2.6 Search bar2.6.1 Introduction2.6.2 Search bar implementation with Elasticsearch2.6.3 Elasticsearch index and ingestion2.6.4 Using Elasticsearch in place of SQL2.6.5 Implementing search in our services2.6.6 Further reading on search2.7 Other discussions2.7.1 Maintaining and extending the application2.7.2 Supporting other types of users2.7.3 Alternative architectural decisions2.7.4 Usability and feedback2.7.5 Edge cases and new constraints2.7.6 Cloud-native concepts2.8 Post-interview reflection and assessment2.8.1 Write your reflection as soon as possible after the interview2.8.2 Writing your assessment2.8.3 Details you didn’t mention2.8.4 Interview feedback2.9 Interviewing the companySummary
3.1 Scalability3.1.1 Stateless and stateful services3.1.2 Basic load balancer concepts3.2 Availability3.3 Fault-tolerance3.3.1 Replication and redundancy3.3.2 Forward error correction and error correction code3.3.3 Circuit breaker3.3.4 Exponential backoff and retry3.3.5 Caching responses of other services3.3.6 Checkpointing3.3.7 Dead letter queue3.3.8 Logging and periodic auditing3.3.9 Bulkhead3.3.10 Fallback pattern3.4 Performance/latency and throughput3.5 Consistency3.5.1 Full mesh3.5.2 Coordination service3.5.3 Distributed cache3.5.4 Gossip protocol3.5.5 Random Leader Selection3.6 Accuracy3.7 Complexity and maintainability3.7.1 Continuous deployment (CD)3.8 Cost3.9 Security3.10 Privacy3.10.1 External vs. internal services3.11 Cloud native3.12 Further readingSummary

4.1 Brief prelude on storage services4.2 When to use vs. avoid databases4.3 Replication4.3.1 Distributing replicas4.3.2 Single-leader replication4.3.3 Multi-leader replication4.3.4 Leaderless replication4.3.5 HDFS replication4.3.6 Further reading4.4 Scaling storage capacity with sharded databases4.4.1 Sharded RDBMS4.5 Aggregating events4.5.1 Single-tier aggregation4.5.2 Multi-tier aggregation4.5.3 Partitioning4.5.4 Handling a large key space4.5.5 Replication and fault-tolerance4.6 Batch and streaming ETL4.6.1 A simple batch ETL pipeline4.6.2 Messaging terminology4.6.3 Kafka vs. RabbitMQ4.6.4 Lambda architecture4.7 Denormalization4.8 Caching4.8.1 Read strategies4.8.2 Write strategies4.9 Caching as a separate service4.10 Examples of different kinds of data to cache and how to cache them4.11 Cache invalidation4.11.1 Browser cache invalidation4.11. 2 Cache invalidation in caching services4.12 Cache warming4.13 Further reading4.13.1 Caching referencesSummary
5.1 Event Driven Architecture (EDA)5.2 Event sourcing5.3 Change Data Capture (CDC)5.4 Comparison of event sourcing and CDC5.5 Transaction supervisor5.6 Saga5.6.1 Choreography5.6.2 Orchestration5.6.3 Comparison5.7 Other transaction types5.8 Further readingSummary
6.1 Common functionalities of various services6.1.1 Security6.1.2 Error-checking6.1.3 Performance and availability6.1.4 Logging and analytics6.2 Service mesh/sidecar pattern6.3 Metadata service6.4 Service discovery6.5 Functional partitioning and various frameworks6.5.1 Basic system design of an app6.5.2 Purposes of a web server app6.5.3 Web and mobile frameworks6.6 Library vs. service6.6.1 Language specific vs. technology-agnostic6.6.2 Predictability of latency6.6.3 Predictability and reproducibility of behavior6.6.4 Scaling considerations for libraries6.6.5 Other considerations6.7 Common API paradigms6.7.1 The Open Systems Interconnection (OSI) model6.7.2 REST6.7.3 RPC (Remote Procedure Call)6.7.4 GraphQL6.7.5 WebSocket6.7.6 ComparisonSummary
7.1 User stories and requirements7.2 API7.3 SQL database schema7.4 Initial high-level architecture7.5 A monolith architecture7.6 Using an SQL database and object store7.7 Migrations are troublesome7.8 Writing and reading posts7.9 Functional partitioning7.10 Caching7.11 CDN7.12 Scaling reads with a SQL cluster7.13 Scaling write throughput7.14 Email service7.15 Search7.16 Removing old posts7.17 Monitoring and alerting7.18 Summary of our architecture discussion so far7.19 Other possible discussion topics7.19.1 Reporting posts7.19.2 Graceful degradation7.19.3 Complexity7.19.4 Item categories/tags7.19.5 Analytics and recommendations7.19.6 A/B testing7.19.7 Subscriptions and saved searches7.19.8 Allow duplicate requests to the search service7.19.9 Avoid duplicate requests to the search service7.19.10 Rate limiting7.19.11 Large number of posts7.19.12 Local regulationsSummary
8.1 Alternatives to a rate-limiting service and why they are infeasible8.2 When not to do rate limiting8.3 Functional requirements8.4 Non-functional requirements8.4.1 Scalability8.4.2 Performance8.4.3 Complexity8.4.4 Security and privacy8.4.5 Availability and fault-tolerance8.4.6 Accuracy8.4.7 Consistency8.5 Discuss user stories and required service components8.6 High-level architecture8.7 Stateful approach/sharding8.8 Storing all counts in every host8.8.1 High-level architecture8.8.2 Synchronizing counts8.9 Rate-limiting algorithms8.9.1 Token bucket8.9.2 Leaky bucket8.9.3 Fixed window counter8.9.4 Sliding window log8.9.5 Sliding window counter8.10 Employing a sidecar pattern8.11 Logging, monitoring, and alerting8.12 Providing functionality in a client library8.13 Further readingSummary
9.1 Functional requirements9.1.1 Not for uptime monitoring9.1.2 Users and data9.1.3 Recipient channels9.1.4 Templates9.1.5 Trigger conditions9.1.6 Manage subscribers, sender groups, and recipient groups9.1.7 User features9.1.8 Analytics9.2 Non-functional requirements9.3 Initial high-level architecture9.4 Object store: Configuring and sending notifications9.5 Notification templates9.5.1 Notification template service9.5.2 Additional features9.6 Scheduled notifications9.7 Notification addressee groups9.8 Unsubscribe requests9.9 Handling failed deliveries9.10 Client-side considerations regarding duplicate notifications9.11 Priority9.12 Search9.13 Monitoring and alerting9.14 Availability monitoring and alerting on the notification/alerting service9.15 Other possible discussion topics9.16 Final notesSummary
10.1 Why is auditing necessary?10.2 Defining a validation with a conditional statement on a SQL query’s result10.3 A simple SQL batch auditing service10.3.1 An audit script10.3.2 An audit service10.4 Requirements10.5 High-level architecture10.5.1 Running a batch auditing job10.5.2 Handling alerts10.6 Constraints on database queries10.6.1 Limit query execution time10.6.2 Check the query strings before submission10.6.3 Users should be trained early10.7 Prevent too many simultaneous queries10.8 Other users of database schema metadata10.9 Auditing a data pipeline10.10 Logging, monitoring, and alerting10.11 Other possible types of audits10.11.1 Cross data center consistency audits10.11.2 Compare upstream and downstream data10.12 Other possible discussion topics10.13 ReferencesSummary
11.1 Possible uses of autocomplete11.2 Search vs. autocomplete11.3 Functional requirements11.3.1 Scope of our autocomplete service11.3.2 Some UX details11.3.3 Considering search history11.3.4 Content moderation and fairness11.4 Non-functional requirements11.5 Planning the high-level architecture11.6 Weighted trie approach and initial high-level architecture11.7 Detailed implementation11.7.1 Each step should be an independent task11.7.2 Fetch relevant logs from Elasticsearch to HDFS11.7.3 Split the search strings into words and other simple operations11.7.4 Filter out inappropriate words11.7.5 Fuzzy matching and spelling correction11.7.6 Count the words11.7.7 Filter for appropriate words11.7.8 Managing new popular unknown words11.7.9 Generate and deliver the weighted trie11.8 Sampling approach11.9 Handling storage requirements11.10 Handling phrases instead of single words11.10.1 Maximum length of autocomplete suggestions11.10.2 Preventing inappropriate suggestions11.11 Logging, monitoring, and alerting11.12 Other considerations and further discussionSummary
12.1 User stories and functional requirements12.2 Non-functional requirements12.3 High-level architecture12.4 SQL schema12.5 Organizing directories and files on the CDN12.6 Uploading a photo12.6.1 Generate thumbnails on the client12.6.2 Generate thumbnails on the backend12.6.3 Implementing both server-side and client-side generation12.7 Downloading images and data12.7.1 Downloading pages of thumbnails12.8 Monitoring and alerting12.9 Some other services12.9.1 Premium features12.9.2 Payments and taxes service12.9.3 Censorship/content moderation12.9.4 Advertising12.9.5 Personalization12.10 Other possible discussion topicsSummary
13.1 Advantages and disadvantages of a CDN13.1.1 Advantages of using a CDN13.1.2 Disadvantages of using a CDN13.1.3 Example of an unexpected problem from using a CDN to serve images13.2 Requirements13.3 CDN authentication and authorization13.3.1 Steps in CDN authentication and authorization13.3.2 Key rotation13.4 High-level architecture13.5 Storage service13.5.1 In-cluster13.5.2 Out-cluster13.5.3 Evaluation13.6 Common operations13.6.1 Reads: Downloads13.6.2 Writes: Directory creation, file upload, and file deletion13.7 Cache invalidation13.8 Logging, monitoring, and alerting13.9 Other possible discussions on downloading media filesSummary
14.1 Requirements14.2 Initial thoughts14.3 Initial high-level design14.4 Connection service14.4.1 Making connections14.4.2 Sender blocking14.5 Sender service14.5.1 Sending a message14.5.2 Other discussions14.6 Message service14.7 Message-sending service14.7.1 Introduction14.7.2 High-level architecture14.7.3 Steps in sending a message14.7.4 Some questions14.7.5 Improving availability14.8 Search14.9 Logging, monitoring, and alerting14.10 Other possible discussion topicsSummary
15.1 Requirements15.2 Design decisions15.2.1 Replication15.2.2 Data models for room availability15.2.3 Handling overlapping bookings15.2.4 Randomize search results15.2.5 Lock rooms during booking flow15.3 High-level architecture15.4 Functional partitioning15.5 Create or update a listing15.6 Approval service15.7 Booking service15.8 Availability service15.9 Logging, monitoring, and alerting15.10 Other possible discussion topics15.10.1 Handling regulationsSummary
16.1 Requirements16.2 High-level architecture16.3 Prepare feed in advance16.4 Validation and content moderation16.4.1 Changing posts on users’ devices16.4.2 Tagging posts16.4.3 Moderation service16.5 Logging, monitoring, and alerting16.5.1 Serving images as well as text16.5.2 High-level architecture16.6 Other possible discussion topicsSummary
17.1 Requirements17.2 Initial thoughts17.3 Initial high-level architecture17.4 Aggregation service17.4.1 by product ID17.4.2 Matching host IDs and product IDs17.4.3 Storing timestamps17.4.4 Aggregation process on a host17.5 Batch pipeline17.6 Streaming pipeline17.6.1 Hash table and max-heap with a single host17.6.2 Horizontal scaling to multiple hosts and multi-tier aggregation17.7 Approximation17.7.1 Count-min sketch17.8 Dashboard with Lambda architecture17.9 Kappa architecture approach17.9.1 Lambda vs. Kappa architecture17.9.2 Kappa architecture for our dashboard17.10 Logging, monitoring, and alerting17.11 Other possible discussion topics17.12 ReferencesSummary
A.1 Advantages of monolithsA.2 Disadvantages of monolithsA.3 Advantages of servicesA.3.1 Agile and rapid development and scaling of product requirements and business functionalitiesA.3.2 Modularity and replaceabilityA.3.3 Failure isolation and fault-toleranceA.3.4 Ownership and organizational structureA.4 Disadvantages of servicesA.4.1 Duplicate componentsA.4.2 Development and maintenance costs of additional componentsA.4.3 Distributed transactionsA.4.4 Referential integrityA.4.5 Coordinating feature development and deployments that span multiple servicesA.4.6 InterfacesA.5 References
B.1 Authorization vs. authenticationB.2 Prelude: Simple login, cookie-based authenticationB.3 Single sign-onB.4 Disadvantages of simple loginB.4.1 Complexity and lack of maintainabilityB.4.2 No partial authorizationB.5 OAuth 2.0 flowB.5.1 OAuth 2.0 terminologyB.5.2 Initial client setupB.5.3 Back channel and front channelB.6 Other OAuth 2.0 flowsB.7 OpenID Connect authentication