https://www.hiredintech.com/courses/system-design
https://hackernoon.com/top-10-system-design-interview-questions-for-software-engineers-8561290f0444
1) System Design Interviews : Grokking the System Design Interview
1. Design TinyURL or bitly (a URL shortening service)
How to generate a unique ID for each URL?
How would you generate unique IDs at scale (thousands of URL shortening requests coming every second)?
How would your service handle redirects?
How would you support custom short URLs?
How to delete expired URLs etc?
How to track click stats?
2. Design YouTube, Netflix or Twitch (a global video streaming service)
Videos mean that your service will be storing and transmitting petabytes and petabytes of data.You should discuss how to efficiently store and distribute data in away that a huge number of users can watch and share them simultaneously (e.g. imagine streaming the latest episode of a hit TV show like Games of Thrones).
In addition, discuss:
How would you record stats about videos e.g the total number of views, up-votes/down-votes, etc.
How would a user add comments on videos (in realtime).
3. Design Facebook Messenger or WhatsApp (a global chat service)
Interviewers are interested in knowing:
How would you design one-on-one conversations between users?
How would you extend your design to support group chats?
What to do when the user is not connected to the internet?
When to send push notifications?
Can you provide end-to-end encryption. How?
4. Designing Quora or Reddit or HackerNews (a social network + message board service)
Users of the services can post questions or share links. Other users can answer questions or comment on the shared links. The service should be able to:
Records stats for each answer e.g. the total number of views, upvotes/downvotes, etc.
Users should be able to follow other users or topics
Their timeline will consist of top questions from all the users and topics they follow (similar to newsfeed generation).
5. Design Dropbox or Google Drive or Google Photos (a global file storage & sharing service)
How would users be able to upload/view/search/share files or photos?
How would you track persmissions for file sharing
How would you allow multiple users to edit the same document
6. Design Facebook, Twitter or Instagram (a social media service with hundreds of millions of users)
Efficient storage and search for posts or tweets.
Newsfeed generation
Social Graph (who befriends whom or who follows whom — specially when millions of users are following a celebrity)
A lot of times, interviewers spend the whole interview discussing the design of the newsfeed.
7. Design Uber or Lyft (a ride sharing service)
The most critical use case — when a customer requests a ride and how to efficiently match them with the nearby drivers?
How to store millions of geographical locations for drivers and riders who are always moving.
How to handle updates to driver/rider locations (millions of updates every second)?
8. Design a Web Crawler or Type-Ahead (search engine related services)
For Type-Ahead, as the user types in their query, you need to design a service which would suggest top 10 searched terms starting with whatever the user has typed. Discuss things like:
How to store previous search queries?
How to keep the data fresh?
How to find the best matches to the already typed string?
How to handle updates and the user is typing too fast?
For Web Crawler, we have to design a scalable service that can crawl the entire Web, and can fetch hundreds of millions of Web documents. Discuss things like:
How to find new web pages?
How to prioritize web pages that change dynamically?
How to ensure that your crawler is not infinitely stuck on the same domain?
9. Design an API Rate Limiter (e.g. for Firebase or Github)
Limit the number of requests an entity can send to an API within a time window e.g., 15 requests per second.
The rate limiting should work for a distributed setup, as the APIs are accessible through a cluster of servers.
How would you handle throttling (soft and hard throttling etc.).
consistent hash - same user, same api goes to same server
sticky session
Separate of concerns: separate rate limit server and real app server, so app server would be not overloadded
http://massivetechinterview.blogspot.com/2015/10/develop-api-rate-limit-throttling-client.html
http://massivetechinterview.blogspot.com/2015/08/rate-limiting.html
10. Design Yelp or Nearby Places/Friends (a proximity server)
This service would need to store locations for millions of people/places. Discuss things like:
How would the users of the service be able to search nearby friends or places
How to rank places (based on the distance, user reviews).
How to efficiently store location data according to the population density (e.g. a block in New York City might have more places/people than a small city).
https://segmentfault.com/a/1190000006025876
http://www.cnblogs.com/haoxinyue/p/6613706.html
http://www.raychase.net/4581
https://hackernoon.com/top-10-system-design-interview-questions-for-software-engineers-8561290f0444
1) System Design Interviews : Grokking the System Design Interview
1. Design TinyURL or bitly (a URL shortening service)
How to generate a unique ID for each URL?
How would you generate unique IDs at scale (thousands of URL shortening requests coming every second)?
How would your service handle redirects?
How would you support custom short URLs?
How to delete expired URLs etc?
How to track click stats?
2. Design YouTube, Netflix or Twitch (a global video streaming service)
Videos mean that your service will be storing and transmitting petabytes and petabytes of data.You should discuss how to efficiently store and distribute data in away that a huge number of users can watch and share them simultaneously (e.g. imagine streaming the latest episode of a hit TV show like Games of Thrones).
In addition, discuss:
How would you record stats about videos e.g the total number of views, up-votes/down-votes, etc.
How would a user add comments on videos (in realtime).
3. Design Facebook Messenger or WhatsApp (a global chat service)
Interviewers are interested in knowing:
How would you design one-on-one conversations between users?
How would you extend your design to support group chats?
What to do when the user is not connected to the internet?
When to send push notifications?
Can you provide end-to-end encryption. How?
4. Designing Quora or Reddit or HackerNews (a social network + message board service)
Users of the services can post questions or share links. Other users can answer questions or comment on the shared links. The service should be able to:
Records stats for each answer e.g. the total number of views, upvotes/downvotes, etc.
Users should be able to follow other users or topics
Their timeline will consist of top questions from all the users and topics they follow (similar to newsfeed generation).
5. Design Dropbox or Google Drive or Google Photos (a global file storage & sharing service)
How would users be able to upload/view/search/share files or photos?
How would you track persmissions for file sharing
How would you allow multiple users to edit the same document
6. Design Facebook, Twitter or Instagram (a social media service with hundreds of millions of users)
Efficient storage and search for posts or tweets.
Newsfeed generation
Social Graph (who befriends whom or who follows whom — specially when millions of users are following a celebrity)
A lot of times, interviewers spend the whole interview discussing the design of the newsfeed.
7. Design Uber or Lyft (a ride sharing service)
The most critical use case — when a customer requests a ride and how to efficiently match them with the nearby drivers?
How to store millions of geographical locations for drivers and riders who are always moving.
How to handle updates to driver/rider locations (millions of updates every second)?
8. Design a Web Crawler or Type-Ahead (search engine related services)
For Type-Ahead, as the user types in their query, you need to design a service which would suggest top 10 searched terms starting with whatever the user has typed. Discuss things like:
How to store previous search queries?
How to keep the data fresh?
How to find the best matches to the already typed string?
How to handle updates and the user is typing too fast?
For Web Crawler, we have to design a scalable service that can crawl the entire Web, and can fetch hundreds of millions of Web documents. Discuss things like:
How to find new web pages?
How to prioritize web pages that change dynamically?
How to ensure that your crawler is not infinitely stuck on the same domain?
9. Design an API Rate Limiter (e.g. for Firebase or Github)
Limit the number of requests an entity can send to an API within a time window e.g., 15 requests per second.
The rate limiting should work for a distributed setup, as the APIs are accessible through a cluster of servers.
How would you handle throttling (soft and hard throttling etc.).
consistent hash - same user, same api goes to same server
sticky session
Separate of concerns: separate rate limit server and real app server, so app server would be not overloadded
http://massivetechinterview.blogspot.com/2015/10/develop-api-rate-limit-throttling-client.html
http://massivetechinterview.blogspot.com/2015/08/rate-limiting.html
10. Design Yelp or Nearby Places/Friends (a proximity server)
This service would need to store locations for millions of people/places. Discuss things like:
How would the users of the service be able to search nearby friends or places
How to rank places (based on the distance, user reviews).
How to efficiently store location data according to the population density (e.g. a block in New York City might have more places/people than a small city).
https://segmentfault.com/a/1190000006025876
http://www.cnblogs.com/haoxinyue/p/6613706.html
http://www.raychase.net/4581
曾经写过一些系统设计方面的思考（比如这个和这个），但是最近准备面试，又接触了更多系统设计方面的问题。这里我想简单记录一些典型系统设计问题的思路。通过学习常见的系统，在心中形成一些问题解决的套路，以在思考和分析新问题的时候提供一些既定思路。很抱歉时间关系写得很简略，主要是提示一些思路和方向。
设计Tweeter
两种常见模型的trade off：
两种常见模型的trade off：
- Pull on demand: merge x timelines
- Push on change: async, read once to get them
缓存的设计，cache through
设计Web crawler
分布式queue，用来存放不断更新的需要爬虫完成的任务，典型的N个生产者+M个消费者的模型
key value storage，用来存储已经完成的网页，爬下来的数据放在S3上
Quota的使用：用来避免对某一个网站分配过多的资源
分布式queue，用来存放不断更新的需要爬虫完成的任务，典型的N个生产者+M个消费者的模型
key value storage，用来存储已经完成的网页，爬下来的数据放在S3上
Quota的使用：用来避免对某一个网站分配过多的资源
设计Type Ahead核心在于避免从磁盘中实时查询，所有查询必须最快命中内存中的数据结构，并且查询的效率必须是O(1)的
采用Trie树，并且每个节点都要有指向结果集的链接
这样的数据结构的生成和更新必须在一开始就初始化完成
采用Trie树，并且每个节点都要有指向结果集的链接
这样的数据结构的生成和更新必须在一开始就初始化完成
设计邮件系统
核心在于存储层schema的设计，user id作为range key，email id作为primary key，邮件的时间列索引化，以便查询某人最近的邮件
读写分离，收取邮件和发送邮件的服务分开
核心在于存储层schema的设计，user id作为range key，email id作为primary key，邮件的时间列索引化，以便查询某人最近的邮件
读写分离，收取邮件和发送邮件的服务分开
设计图片上传和访问系统
核心在于CDN的使用，要把静态资源的读取推送到离用户近的节点去。
处理在用户上传图片后，CDN数据还没有最新数据的情况（数据不一致的问题）
核心在于CDN的使用，要把静态资源的读取推送到离用户近的节点去。
处理在用户上传图片后，CDN数据还没有最新数据的情况（数据不一致的问题）
设计图像转换服务
典型异步系统的设计：
典型异步系统的设计：
- 一个分布式queue存放异步任务，
- 另一个key-value storage存放任务状态，用来供另外的系统查询任务状态
两个API设计：上传图像后返回上传成功和任务ID；查询当前任务状态
另外可以考虑Lambda这种serverless的方式
另外可以考虑Lambda这种serverless的方式
设计分布式文件系统核心在于怎么存放文件的meta data和实际的data从而分担读写压力，怎么处理文件的更新和删除比如master上存放粗略的meta data，知道文件的分片在哪个slave服务器上，slave上存放分片具体信息，client读写仅仅通过master定位到slave，余下的工作不通过master完成，以避免master成为瓶颈
chunk和checksum的设计和使用
chunk和checksum的设计和使用
设计Tiny URL服务
schema的设计，需要解决两个问题：short URL -> long URL（最多被使用）和 long URL -> short URL
short URL的生成，几种方法在分布式系统中生成唯一ID
读基于缓存的优化
schema的设计，需要解决两个问题：short URL -> long URL（最多被使用）和 long URL -> short URL
short URL的生成，几种方法在分布式系统中生成唯一ID
读基于缓存的优化
设计流量限制系统
- 思路1：Cache TTL on bucket level
- 思路2：Leaky Bucket / Token Bucket
设计Metrics系统
Ring Buffer，根据不同的统计粒度，设定不同的bucket size
根据不同的统计粒度，建立不同的表来持久化和供未来查询
读写模型：写多读少，汇总增量数据后再更新的优化
Ring Buffer，根据不同的统计粒度，设定不同的bucket size
根据不同的统计粒度，建立不同的表来持久化和供未来查询
读写模型：写多读少，汇总增量数据后再更新的优化
设计打车系统核心在于司机和乘客怎样更新地理位置信息，系统怎样存储地理位置信息，已经怎样为乘客寻找最近的司机（geo hash）
读写模型：写多读少，怎样优化系统来应付这种状况，一致性的牺牲
读写模型：写多读少，怎样优化系统来应付这种状况，一致性的牺牲
设计即时聊天系统
引入Channel Service，socket push的使用存储：解耦成消息表和会话表，使得用户可以单独设定每个会话的属性引入Channel Service
用户在线状态的维护：heartbeat
引入Channel Service，socket push的使用存储：解耦成消息表和会话表，使得用户可以单独设定每个会话的属性引入Channel Service
用户在线状态的维护：heartbeat
设计联机日志服务
持久化问题，日志client和日志service，减少单点故障造成的日志丢失
尽可能不影响现有业务应用，线程必须独立
引入队列，对于大量日志写入的缓冲
在网络不可用时，日志客户端可以写入本地文件，网络恢复后可以上传本地文件
持久化问题，日志client和日志service，减少单点故障造成的日志丢失
尽可能不影响现有业务应用，线程必须独立
引入队列，对于大量日志写入的缓冲
在网络不可用时，日志客户端可以写入本地文件，网络恢复后可以上传本地文件
