Acing the System Design Interview

contents
foreword
preface
acknowledgments
about this book
	Who should read this book
	How this book is organized: A roadmap
	liveBook discussion forum
	Other online resources
about the author
about the cover illustration
Part 1
	1 A walkthrough of system design concepts
		A discussion about tradeoffs
		Should you read this book?
		Overview of this book
		Prelude: A brief discussion of scaling the various services of a system
			The beginning: A small initial deployment of our app
			Scaling with GeoDNS
			Adding a caching service
			Content distribution network
			A brief discussion of horizontal scalability and cluster management, continuous integration, and continuous deployment
			Functional partitioning and centralization of cross-cutting concerns
			Batch and streaming extract, transform, and load (ETL)
			Other common services
			Cloud vs. bare metal
			Serverless: Function as a Service (FaaS)
			Conclusion: Scaling backend services
	2 A typical system design interview flow
		Clarify requirements and discuss tradeoffs
		Draft the API specification
			Common API endpoints
		Connections and processing between users and data
		Design the data model
			Example of the disadvantages of multiple services sharing databases
			A possible technique to prevent concurrent user update conflicts
		Logging, monitoring, and alerting
			The importance of monitoring
			Observability
			Responding to alerts
			Application-level logging tools
			Streaming and batch audit of data quality
			Anomaly detection to detect data anomalies
			Silent errors and auditing
			Further reading on observability
		Search bar
			Introduction
			Search bar implementation with Elasticsearch
			Elasticsearch index and ingestion
			Using Elasticsearch in place of SQL
			Implementing search in our services
			Further reading on search
		Other discussions
			Maintaining and extending the application
			Supporting other types of users
			Alternative architectural decisions
			Usability and feedback
			Edge cases and new constraints
			Cloud-native concepts
		Post-interview reflection and assessment
			Write your reflection as soon as possible after the interview
			Writing your assessment
			Details you didn’t mention
			Interview feedback
		Interviewing the company
	3 Non-functional requirements
		Scalability
			Stateless and stateful services
			Basic load balancer concepts
		Availability
		Fault-tolerance
			Replication and redundancy
			Forward error correction and error correction code
			Circuit breaker
			Exponential backoff and retry
			Caching responses of other services
			Checkpointing
			Dead letter queue
			Logging and periodic auditing
			Bulkhead
			Fallback pattern
		Performance/latency and throughput
		Consistency
			Full mesh
			Coordination service
			Distributed cache
			Gossip protocol
			Random Leader Selection
		Accuracy
		Complexity and maintainability
			Continuous deployment (CD)
		Cost
		Security
		Privacy
			External vs. internal services
		Cloud native
		Further reading
	4 Scaling databases
		Brief prelude on storage services
		When to use vs. avoid databases
		Replication
			Distributing replicas
			Single-leader replication
			Multi-leader replication
			Leaderless replication
			HDFS replication
			Further reading
		Scaling storage capacity with sharded databases
			Sharded RDBMS
		Aggregating events
			Single-tier aggregation
			Multi-tier aggregation
			Partitioning
			Handling a large key space
			Replication and fault-tolerance
		Batch and streaming ETL
			A simple batch ETL pipeline
			Messaging terminology
			Kafka vs. RabbitMQ
			Lambda architecture
		Denormalization
		Caching
			Read strategies
			Write strategies
		Caching as a separate service
		Examples of different kinds of data to cache and how to cache them
		Cache invalidation
			Browser cache invalidation
			Cache invalidation in caching services
		Cache warming
		Further reading
			Caching references
	5 Distributed transactions
		Event Driven Architecture (EDA)
		Event sourcing
		Change Data Capture (CDC)
		Comparison of event sourcing and CDC
		Transaction supervisor
		Saga
			Choreography
			Orchestration
			Comparison
		Other transaction types
		Further reading
	6 Common services for functional partitioning
		Common functionalities of various services
			Security
			Error-checking
			Performance and availability
			Logging and analytics
		Service mesh/sidecar pattern
		Metadata service
		Service discovery
		Functional partitioning and various frameworks
			Basic system design of an app
			Purposes of a web server app
			Web and mobile frameworks
		Library vs. service
			Language specific vs. technology-agnostic
			Predictability of latency
			Predictability and reproducibility of behavior
			Scaling considerations for libraries
			Other considerations
		Common API paradigms
			The Open Systems Interconnection (OSI) model
			REST
			RPC (Remote Procedure Call)
			GraphQL
			WebSocket
			Comparison
Part 2
	7 Design Craigslist
		User stories and requirements
		API
		SQL database schema
		Initial high-level architecture
		A monolith architecture
		Using an SQL database and object store
		Migrations are troublesome
		Writing and reading posts
		Functional partitioning
		Caching
		CDN
		Scaling reads with a SQL cluster
		Scaling write throughput
		Email service
		Search
		Removing old posts
		Monitoring and alerting
		Summary of our architecture discussion so far
		Other possible discussion topics
			Reporting posts
			Graceful degradation
			Complexity
			Item categories/tags
			Analytics and recommendations
			A/B testing
			Subscriptions and saved searches
			Allow duplicate requests to the search service
			Avoid duplicate requests to the search service
			Rate limiting
			Large number of posts
			Local regulations
	8 Design a rate-limiting service
		Alternatives to a rate-limiting service and why they are infeasible
		When not to do rate limiting
		Functional requirements
		Non-functional requirements
			Scalability
			Performance
			Complexity
			Security and privacy
			Availability and fault-tolerance
			Accuracy
			Consistency
		Discuss user stories and required service components
		High-level architecture
		Stateful approach/sharding
		Storing all counts in every host
			High-level architecture
			Synchronizing counts
		Rate-limiting algorithms
			Token bucket
			Leaky bucket
			Fixed window counter
			Sliding window log
			Sliding window counter
		Logging, monitoring, and alerting
		Providing functionality in a client library
		Further reading
		Employing a sidecar pattern
	9 Design a notification/alerting service
		Functional requirements
			Not for uptime monitoring
			Users and data
			Recipient channels
			Templates
			Trigger conditions
			Manage subscribers, sender groups, and recipient groups
			User features
			Analytics
		Non-functional requirements
		Initial high-level architecture
		Object store: Configuring and sending notifications
		Notification templates
			Notification template service
			Additional features
		Scheduled notifications
		Notification addressee groups
		Unsubscribe requests
		Handling failed deliveries
		Client-side considerations regarding duplicate notifications
		Priority
		Search
		Monitoring and alerting
		Availability monitoring and alerting on the notification/alerting service
		Other possible discussion topics
		Final notes
	10 Design a database batch auditing service
		Why is auditing necessary?
		Defining a validation with a conditional statement on a SQL query’sresult
		A simple SQL batch auditing service
			An audit script
			An audit service
		Requirements
		High-level architecture
			Running a batch auditing job
			Handling alerts
		Constraints on database queries
			Limit query execution time
			Check the query strings before submission
			Users should be trained early
		Prevent too many simultaneous queries
		Other users of database schema metadata
		Auditing a data pipeline
		Logging, monitoring, and alerting
		Other possible types of audits
			Cross data center consistency audits
			Compare upstream and downstream data
		Other possible discussion topics
		References
	11 Autocomplete/typeahead
		Possible uses of autocomplete
		Search vs. autocomplete
		Functional requirements
			Scope of our autocomplete service
			Some UX details
			Considering search history
			Content moderation and fairness
		Non-functional requirements
		Planning the high-level architecture
		Weighted trie approach and initial high-level architecture
		Detailed implementation
			Each step should be an independent task
			Fetch relevant logs from Elasticsearch to HDFS
			Split the search strings into words and other simple operations
			Filter out inappropriate words
			Fuzzy matching and spelling correction
			Count the words
			Filter for appropriate words
			Managing new popular unknown words
			Generate and deliver the weighted trie
		Sampling approach
		Handling storage requirements
		Handling phrases instead of single words
			Maximum length of autocomplete suggestions
			Preventing inappropriate suggestions
		Logging, monitoring, and alerting
		Other considerations and further discussion
	12 Design Flickr
		User stories and functional requirements
		Non-functional requirements
		High-level architecture
		SQL schema
		Organizing directories and files on the CDN
		Uploading a photo
			Generate thumbnails on the client
			Generate thumbnails on the backend
			Implementing both server-side and client-side generation
		Downloading images and data
			Downloading pages of thumbnails
		Monitoring and alerting
		Some other services
			Premium features
			Payments and taxes service
			Censorship/content moderation
			Advertising
			Personalization
		Other possible discussion topics
	13 Design a Content Distribution Network
		Advantages and disadvantages of a CDN
			Advantages of using a CDN
			Disadvantages of using a CDN
			Example of an unexpected problem from using a CDN to serve images
		Requirements
		CDN authentication and authorization
			Steps in CDN authentication and authorization
			Key rotation
		High-level architecture
		Storage service
			In-cluster
			Out-cluster
			Evaluation
		Common operations
			Reads: Downloads
			Writes: Directory creation, file upload, and file deletion
		Logging, monitoring, and alerting
		Other possible discussions on downloading media files
		Cache invalidation
	14 Design a text messaging app
		Requirements
		Initial thoughts
		Initial high-level design
		Connection service
			Making connections
			Sender blocking
		Sender service
			Sending a message
			Other discussions
		Message service
		Message-sending service
			Introduction
			High-level architecture
			Steps in sending a message
			Some questions
			Improving availability
		Search
		Logging, monitoring, and alerting
		Other possible discussion topics
	15 Design Airbnb
		Requirements
		Design decisions
			Replication
			Data models for room availability
			Handling overlapping bookings
			Randomize search results
			Lock rooms during booking flow
		High-level architecture
		Functional partitioning
		Create or update a listing
		Approval service
		Booking service
		Availability service
		Logging, monitoring, and alerting
		Other possible discussion topics
			Handling regulations
	16 Design a news feed
		Requirements
		High-level architecture
		Prepare feed in advance
		Validation and content moderation
			Changing posts on users’ devices
			Tagging posts
			Moderation service
		Logging, monitoring, and alerting
			Serving images as well as text
			High-level architecture
		Other possible discussion topics
	17 Design a dashboard of top 10 products on Amazon by sales volume
		Requirements
		Initial thoughts
		Initial high-level architecture
		Aggregation service
			Aggregating by product ID
			Matching host IDs and product IDs
			Storing timestamps
			Aggregation process on a host
		Batch pipeline
		Streaming pipeline
			Hash table and max-heap with a single host
			Horizontal scaling to multiple hosts and multi-tier aggregation
		Approximation
			Count-min sketch
		Dashboard with Lambda architecture
		Kappa architecture approach
			Lambda vs. Kappa architecture
			Kappa architecture for our dashboard
		Logging, monitoring, and alerting
		Other possible discussion topics
		References
	A Monoliths vs. microservices
		Advantages of monoliths
		Disadvantages of monoliths
		Advantages of services
			Agile and rapid development and scaling of product requirements and business functionalities
			Modularity and replaceability
			Failure isolation and fault-tolerance
			Ownership and organizational structure
		Disadvantages of services
			Duplicate components
			Development and maintenance costs of additional components
			Distributed transactions
			Referential integrity
			Coordinating feature development and deployments that span multiple services
			Interfaces
		References
	B OAuth 2.0 authorizationand OpenID Connectauthentication
		Authorization vs. authentication
		Prelude: Simple login, cookie-based authentication
		Single sign-on
		Disadvantages of simple login
			Complexity and lack of maintainability
			No partial authorization
		OAuth 2.0 flow
			OAuth 2.0 terminology
			Initial client setup
			Back channel and front channel
		Other OAuth 2.0 flows
		OpenID Connect authentication
	C C4 Model
	D Two-phase commit (2PC)
index