Chat Email File Storage Metrics & Monitoring News Feed Notification System Peak Season Rate Limiter Typeahead Suggestion Uber URL Shortener Video Platform Web Crawler
Clarifications​
DAU : 50MMessages : 100M/dayMedia : 5% of messages Functional Requirements​
chat with one person or a group (up to 100 people)
share photos, videos, and other files
See when your messages are sent, delivered, and read
See when other users are online
Get notifications for new messages
Non-functional Requirements​
fast and reliable
handle a lot of users and traffic
Assumptions​
Core Features : Group chat, file sharingSharing & Notifications : Share files and get alerts on edits/changesFast & Efficient : Quick file sync with minimal bandwidth useRock-Solid Reliability : No data lossLoad : HA and scalability Estimations​
Traffic :
Activity: 50 M ( u s e r s ) ∗ 40  m e s s a g e s / d a y = 2 B  m e s s a g e s / d a y 50M (users) * 40\ messages/day = 2B\ messages/day 50 M ( u sers ) ∗ 40  m ess a g es / d a y = 2 B  m ess a g es / d a y
Media: 2 B / d a y  ( a c t i v i t y ) ∗ 5 % ( c o n t e n t  w i t h  m e d i a ) = 100 M  m e d i a / d a y 2B/day\ (activity) * 5\% (content\ with\ media) = 100M\ media/day 2 B / d a y  ( a c t i v i t y ) ∗ 5% ( co n t e n t  w i t h  m e d ia ) = 100 M  m e d ia / d a y
RPS: 2 B / d a y  ( a c t i v i t y ) 24 h ∗ 3600 s e c = 24 K  r e q / s e c \frac{2B/day\ (activity)}{24h * 3600sec} = 24K\ req/sec 24 h ∗ 3600 sec 2 B / d a y  ( a c t i v i t y ) ​ = 24 K  re q / sec
Storage :
Messages: 2 B / d a y  ( a c t i v i t y ) ∗ 100 b y t e ( m e s s a g e  s i z e ) = 200 G B / d a y 2B/day\ (activity) * 100byte (message\ size) = 200GB/day 2 B / d a y  ( a c t i v i t y ) ∗ 100 b y t e ( m ess a g e  s i ze ) = 200 GB / d a y
Media:
Media : 100 M / d a y ( m e s s a g e s ) ∗ 100 K B ( m e d i a  s i z e ) = 10 T B / d a y 100M/day (messages) * 100KB (media\ size) = 10TB/day 100 M / d a y ( m ess a g es ) ∗ 100 K B ( m e d ia  s i ze ) = 10 TB / d a y 10 years : ( 10 T B / d a y ( m e d i a ) + 0.2 T B / d a y ( m e s s a g e s ) ) ∗ 10 ( y e a r s ) ∗ 365 ( d a y ) = 38 P B (10TB/day (media) + 0.2TB/day (messages)) * 10 (years) * 365 (day) = 38PB ( 10 TB / d a y ( m e d ia ) + 0.2 TB / d a y ( m ess a g es )) ∗ 10 ( ye a rs ) ∗ 365 ( d a y ) = 38 PB
Bandwidth : 10 T B / d a y ( m e d i a ) + 0.2 T B / d a y ( m e s s a g e s ) 24 h ∗ 3600 s e c = 120 M B / s e c \frac{10TB/day (media) + 0.2TB/day (messages)}{24h * 3600sec} = 120MB/sec 24 h ∗ 3600 sec 10 TB / d a y ( m e d ia ) + 0.2 TB / d a y ( m ess a g es ) ​ = 120 MB / sec
Clarifications​
Features : Upload, download, sync files, get notificationsPlatform : Mobile & WebFile Types : All supportedEncryption : Encrypted storageSize Limit : Up to 10GB per fileUsers : 10M DAU Assumptions​
Core Features : Drag-and-Drop upload, download, multi-device sync, revision historySharing & Notifications : Share files and get alerts on edits/changesFast & Efficient : Quick file sync with minimal bandwidth useRock-Solid Reliability : No data lossLoad : HA and scalability Estimations​
Storage Allocation : 50M (users) * 10GB (space allocation / user) = 500 PT/monthUpload Load : 10M (users) * 2 (upload/day) 24 (hours) / 3600 (seconds) = 240 upload/sec and Peak QPS: QPS * 2 (peak ratio) = 480 upload/sec
Considerations​
Collect metrics from various sources (servers, databases)
Store and query time-series data (time-series database + Kafka)
Process and analyze data (Apache Storm, Flink, Spark)
Retrieve, visualize, and get alerted on metrics (query service, visualization system, alerting system)
Assumptions​
Functionality : Post, Get Feed, Update FeedFocus : Text and not on large mediaRanking Assumed : Existing system already ranks postsGlobal Reach : Serves 1B users worldwideShare : 500 friends per userPost Speed : Varies by location (1s - 1 minute)Availability : Ensures posts aren't lost, but not guaranteed uptimeAds (Bonus) : Optional addition of advertisements Estimations​
News Feed Size : 1K (posts) * 10Kb (post size) = 10 MB Clarifications​
Platform : Mobile & WebKey Feature : Users post and see friends' posts in a news feedFeed Order : Newest firstFriend Limit : Up to 5k friends per userTraffic : 10M DAUFeed Content : Text, images, and videos
Considerations​
Block Bots & DDoS : Use reCaptcha & rate limitingFast Loading : Minify & CDN deliver CSS/JS/ImagesScale on Demand : Spin up isolated dedicated instances & use queuesPrevent Overselling : Lock inventory on orderFast Cache : Use cache & manage inventoryMinimize & Optimize : Reduce RPC, hops, & streamline servicesIsolate Content : Separate static/dynamic & isolate uncommon itemsAccurate Confirmation : Show true stock availability
Clarifications​
Match Start Only : Autocomplete suggestions only appear at the beginning of queriesTop 5 Picks : Show 5 most popular suggestions based on past searchesNo Spell Check : Focuses on displaying popular suggestions, not correcting typosLanguage Support : English for now, multi-language can be discussed laterLowercase Letters : Search queries are assumed to be lowercase with no special charactersTraffic : Used by 10M DAUWorkflow : Each time you enter a character it'll send a request to a backend service to get suggestions: /search?q=f -> /search?q=fo -> /search?q=foo Assumptions​
Performance : Autocomplete suggestions must appear within 100ms to avoid lagRelevance : Suggestions should be related to the search termsRanked : Show more popular suggestions firstScalability : HA, scalability, and fault tolerance considerationsEncoding : UTF-8 Estimations​
Query Size : 4 (words) * 5 (characters) * 1 (byte/character) = 20 bytes/queryLoad : QPS: 10M (users) * 10 (queries/day) * 20 (characters) / 24 (hours) / 3600 (seconds) = 24K query/sec and Peak QPS: QPS * 2 (peak ratio) = 48K query/secStorage : 10M (users) * 10 (queries/day) * 20 (bytes/query) * 20% (new users) = 0.4 GB/day Improvements​
Use Bloom filter for faster empty suggestions
Choose the right data structure for storing the data in database
Trie : Search is O(n)Optimized Trie : All completions stored along with the prefix in the trie node (more space is required). Limit data by prefix size and completion count for better storage efficiencyPrefix Hash Tree : Search is O(1) but uses more space
Choose proper data structure for storing the data in cache
Redis List : Search is O(n)Redis Sorted Set : Search/Update O(log n)If number of completions reach limit, remove lowest-scoring and add a new one
Clarifications​
Shortener : Long URL (e.g. https://www.myweb.com/learn/system-design/) to short one (https://tinyurl.com/app). Clicking short link goes to the original long URLVolume : 100M shortened URLs generated dailyLength : Short as possibleCharacters : Numbers (0-9) and letters (a-z, A-Z) Assumptions​
URL shortening : given a long URL → return a much shorter URLURL redirecting : given a shorter URL → redirect to the original URLCharacters : [A-Za-z0-9]HA, scalability, and fault tolerance considerations, with distributed architecture
Estimations​
URL Shortener : 62 characters ([A-Za-z0-9]) ^ 7 (letters for short URL) = 3.5 trillion (URLs)Write operation : 100M URLs/day → 100M (URLs) / 24 (hours) / 3600 (seconds) = 1160 (URLs/sec)Read operation : assuming ratio of read operation to write operation is 10:1 → 1160 (writes/sec) * 10 (reads ratio) = 11,600 (reads/sec)Storage requirement : average URL length is 100 bytes with 10 years of data storage: 100M (URLs) * 365 (days) * 10 (years) * 100 (bytes) = 365TB
Clarifications​
Features : Upload & watch videosClients : Mobile, web, smart TVUsers : 5M DAUEngagement : 30 min/dayGlobal : Supports international usersPlayback : Accepts most resolutions/formatsSecurity : Encrypted videosUpload Limit : Max 1GB videos (focuses on smaller sizes)Cloud Storage : Consider leveraging existing services (AWS, Google Cloud, Azure) Assumptions​
Fast Uploads : Videos upload quicklySeamless Streaming : Videos play smoothly without bufferingQuality Control : Lets users adjust video qualityCost-Effective : Needs low infrastructure costsScalability : HA, scalable, and reliableMulti-Platform : Works on mobile apps, web browsers, and smart TVs Estimations​
Storage : 5M (users) * 10% (users upload 1 video/day) * 300MB (video) = 150 TB/dayCDN Costs : 5M (users) * 5 (videos) * 300MB (video) * 0.02 (CDN cost $/GB) = 750k $/day
Clarifications​
Crawling Goal : Search Engine IndexingMonthly Intake : 1B pagesContent Type : HTML onlyFreshness : Include new & edited pagesStorage : Keep crawled HTML for 5 yearsDuplicates : Ignore duplicate content Assumptions​
Scale Up : Handle billions of web pages with parallelization (running tasks simultaneously)Handle the Weird : Expect broken code, slow servers, crashes, and bad actors. The crawler must adaptBe Nice : Don't overload websites with too many requests at once based on the websiteFuture-Proof : Easily add new content types (like images) without a major overhaulCrawl : Use BFS algorithm Estimations​
Load : QPS: 1M (pages) / 30 (days) / 24 (hours) / 3600 (seconds) = 400 pages/sec and Peak QPS: QPS * 2 (peak ratio) = 800 pages/secStorage : 1B (pages) * 500kb (page size) = 500 TB/month for 5 years 500 (TB/month) * 12 (months) * 5 (years) = 30 PB Device Notifications Disney Hotstar Google Search Netflix Play API Netflix Video Stream StackOverflow Twitter (2022) Uber Live Chat 
