ABCDEFGHIJKLMNOPQRSTUVWXYZ
1
Lecture
(green = most important for quick revision)
NotesMandatory Readings
(for SDE-2 & higher)
Topics Covered
2
1System Design and Computer Networks 101HLD 1 - System Design 101 • High Level Design (HLD) - what & why • Case Study - bookmarking website • DNS, IP Addresses, Domains (how internet works) • Horizontal vs Vertical Scaling • Load Balancing - what & why • Heartbeat & HealthCheck • Scaling Mindset
3
2Load Balancing and Consistent Hashing
HLD - 2 - Load Balancing & Consistent Hashing
Load Balancer• Load Balancing Techniques • Horizontal vs Vertical Partitioning • Sharding • Routing Algorithms • Round Robin • Consistent Hashing • Stateless Servers
4
3Caching: CDN + Backend Caches, Cache InvalidationHLD - 3 - Caching• Memory Hierarchy • In-Browser caches • Content Delivery Networks (CDN) • Backend Caching • Local vs Global Cache • Single vs Distributed Cache • Cache Invalidation & Eviction Algorithms • Write Around / Write Through / Write Back / TTL • Cache Consistency
5
4Case Study: Caching Scaler Code Judge & Contest LeaderboardHLD - 4 - Caching Case Studies - ScalerScaling with Redis - Eviction policies and cluster mode• Designing a Cache • Caching testcases in Scaler Code Judge • Global vs Local Cache • LRU Eviction • CPU vs I/O bound processes • Ranklist Computation • Caching Leaderboard in Scaler Contests • Redis Overview
6
5Case Study: Caching Facebook News Feed
HLD - 5 - Caching Case Studies - Facebook News feed
• Caching NewsFeed in Facebook • Scale Estimation • Newsfeed Computation • Fan-out reads • Database Sharding • Read Replicas • Cron Job
7
6CAP / PACELC theorem + Master Slave Replication
HLD - 6 - CAP / PACELC theorem + Master Slave Replication
Master Slave: MySQL• Consistency, Availability, Network Partitions & Partition Tolerance • CAP & PALEC theorem • Proof by example • A+P / C+P / A+C systems • Database Replication • Replication vs Sharding • Master-Slave Replication • Eventual Consistency, Immediate Consistency, Data Loss • Quorum, Tunable Consistency • Multi-Master Replication
8
7SQL vs NoSQL + ShardingHLD - 7 - SQL vs NoSQL + Sharding1. Redis
- Redis Online Editor
- Getting Started
- Eviction policies and cluster mode
2. MongoDB
- Mongo playground
- Getting Started with MongoDB
- MongoDB Docs
• Relational Databases • Pros & Cons of SQL • Normalization • ACID transactions • ACID consistency vs CAP consistency • Database Schema • Unstructured Data • Sharding • Choosing a good Sharding Key • Fanout queries • NoSQL Databases • SQL vs NoSQL • ACID vs BASE • Denormalization & Replication • Key-Value databases (Redis) • Document Databases (Mongodb) • Wide Column Databases (Cassandra) • Large File Storage (S3) • Other database types (graph, vector, ..) • Choosing the correct database • Row wide vs Column wide storage
9
8Database Orchestration & Shard Creation
HLD - 8 - Database Orchestration & Shard Creation
• Sharding without Replication • Sharding with Master-Slave Replication • Database Orchestrator • Adding / Removing Servers • Extra Replicas • Replication Factor • Seamless Shard Creation (Simulation & Real Phase) • Multi-Master Replication
10
9Case study: Typeahead (Google, Amazon)
HLD - 9 - Case Study: Typeahead (Google, Amazon)
• HLD Interviews • 5 step process to Approaching a Design Problem • Problem Statement • Functional Requirements • MVP Features • Features to avoid during interviews • Non-Functional Requirements • Scale Estimation • Pareto Principle (80-20 rule) • Avg. vs Peak Load • Read vs Write heavy systems • Tries • Hashtables • Optimizing Writes - Batching & Sampling • Recency & Personalization
11
10NoSQL Internals - LSM Tree + Bloom Filter + Sparse Index
HLD - 10 - NoSQL Internals - LSM Tree + Bloom Filter + Sparse Index
• Data storage in SQL vs NoSQL • Log Structured Merged (LSM) Trees • Write Ahead Log (WAL) Files • MemTable & Caching • Sorted String (SS) Tables • Visualization of LSM trees • Compaction Process • Compaction Strategies • Sparse Index vs Full Index • Deletion & Tombstones • Bloom Filters • Sequential vs Random reads in HDD
12
11Case Study: Messaging Apps (FB Messenger, Whatsapp, Slack)
HLD - 11 - Case Study: Messaging Apps (FB Messenger, Whatsapp, Slack)
• Message Ordering • Automatic Retries & API Idempotency • Scale Estimation • 1-1 messages • Group messages • Illusion of Consistency with High Availability & Low Latency • Database choice • Caching messages
13
12Messaging Queues - Apache Kafka & Zookeeper
HLD - 12 - Messaging Queues - Apache Kafka & Zookeeper
• Publisher Subscriber • Message Queue • Decoupling, Load Leveling, Buffering • Async Task Processing • Event Driver Architectures • Pros & Cons of message queues • Apache Kafka • Event Schema • Producers & Consumers • Pull vs Push • Consumer Groups • Topics & Partitions • Message Retention • Message Ordering • Partition Key • Partition Mapping & Consumer Offsets • Consumer Rebalancing • Delivery Guarantees - At most once, At least once, Exactly once • Message Brokers • Fault Tolerance • Apache ZooKeeper • Distributed Configuration Management • KRaft • Persistent vs Ephemeral nodes • Master election via Zookeeper
14
13Case Study: ElasticSearch (Full Text Search)
HLD - 13 - Case Study: ElasticSearch (Full Text Search)
1. Elasticsearch Tutorial | Getting Started Guide for Beginners - Sematext
2. Elasticsearch text analysis and full text search - a quick introduction
3. Search Playground
• Full Text Search • Why SQL is suboptimal for text search • Usecases • Inverted Index • Text Preprocessing pipeline - Parsing, Tokenization, Normalization, Stop Word Removal, Reduction, Stemming, Lemmatization • Indexing • Term Frequence, Document Frequency, TF-IDF score • Apache Lucene • Sharding by Key, by Document ID • Elasticsearch • Fan-out reads • Sharding & Replication in ElasticSearch • B+Trees • Binary vs Ternary vs k-ary
15
14Case Study: S3, HDFS (Large File Storage)
HLD - 14 - Case Study: S3, HDFS (Large File Storage)
• Large File Storage (S3, HDFS) • Log Aggregation • Multimedia uploads • File chunking • Ideal Chunk Size • Name Nodes & Data Nodes • Hadoop Distributed File System • Replication • Rack aware algorithms • File uploads & downloads • Bittorrent
16
15Case Study: Uber (Nearest Neighbor Search)
HLD - 15.1 - QuadTrees - Nearest Neighbor Search
HLD - 15.2 - Case Study: Uber
Assignment: Construct Quad Tree - LeetCode • k-Nearest Neighbor (kNN) search • Grid based approach • Dynamic Grid Sizing • QuadTrees • Nearest Restaurant in Zomato/Swiggy • Space Requirements for storing Quadtrees • Nearest Drivers in Uber • Ride booking request flow • Optimizing Quadtree writes • Optimizing movement within node boundary • Quadtree location vs structure updates • Notification Systems crash course • Uber H3 (Hexagonal Hierarchical Spatial Index)
17
16Rate Limiter + Unique ID GeneratorHLD - 16.1 - Unique ID Generator
HLD - 16.2 - Rate Limiters
• ID generation @ Scale • Universal Uniqueness • Strictly Increasing, Lexicographically Sortable • Roughly Sortable • Enumeration Attacks • Randomness & Sparsity • Decentralization • Autoincrement integers in SQL • UUIDv4 • Timestamp • Network Time Protocol (NTP) • Twitter Snowflake • ULID, UUIDv6
18
17Case Study: Hotstar, Google Meet, Netflix/Youtube, Scaler Live Classes, Whatsapp Video/Voice calls (Video Streaming)
HLD - 17 - Case Study: Video Streaming - Hotstar, Google Meet, Netflix/Youtube, Scaler Live Classes, Whatsapp Video/Voice calls
• Challenges with Video Streaming • Adaptive Bitrate Streaming (ABS) • Resolution vs FPS • User Agent Detection • Video buffering • Chunking • Just in Time downloads • HTTP Live Streaming (HLS) • m3u8 format • Streaming Pre-recorded videos (youtube, netflix, jio cinema) • CDNs for video serving • Streaming Live Videos (hotstar, twitch) • Video Streaming Latency • Auto Scaling challenges • Ideal Chunk Size • Scaler Live Classes • Google Meet • Whatsapp video calls
19
18Microservices - 1 - Monolith vs Microservices vs SOA
HLD - 18 - Monolith vs Microservices vs SOA
• Types of Scale • Monolithic Architecture • Scaling a Monolith • Pros & Cons of Monoliths • Modular Monolith • Microservices Architecture • Pros & Cons of Microservices • Typical Backend Architecture • Untrusted vs Trusted Layer • Service vs Server • API Gateway • Reverse Proxy • Load Balancers • Trusted Virtual Private Cloud (VPC) • Authentication vs Authorization • When to use a Monolith vs Microservices • Breaking a Monolith into Microservices • Hybrid Architecture • Handling Cross Cutting Dependencies • Service Oriented Architecture
20
19Microservices - 2 - Communication, Observability, Resilience
HLD - 19 - Microservices - Communication, Observability
• Monolith Communication • Client to Microservices Communication • API Gateway • GraphQL • Backend for Frontend • Microservice to Microservice communication • Synchronous Communication • RESTful APIs • SOAP • Remote Procedure Calls (gRPC) • Inter Process Communication (IPC) • Asyncronous Communication • Message Queues, Event Driven, Event Streaming • Observability • Metrics & Monitoring • Alerts • Logging • ELK Stack • Distributed Tracing • Traces & Spans • Correlation ID • Resilience • Common Failure Types • Cascading Failures • Thundering Herd • Basic Defenses • Circuit Breaker • Bulkhead • Graceful Degradation • Chaos Engineering • Sidecar
21
20Microservices - 3 - Data Management, Consistency & Distributed Transactions
HLD - 20 - Microservices - Data Management, Consistency & Distributed Transactions
• Managing Data • Command Query Responsibility Segregation (CQRS) • API Composition / Aggregation • Consistency in Microservices • Two Phase Commit (2PC) • Saga Patterns • Orchestration • Choreography • When to choose what • Event Sourcing
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100