system_design

系统设计问题归总

Posted by YueLng Chen on 2018-01-18

重点考察内容

面向对象，接口设计，设计模式，数据库表，分布式

关于高并发系统设计。主要有以下几个关键技术点：缓存，索引，数据分片，锁粒度尽可能小。

系统设计相关

  1. Concurrency (threads, deadlock, starvation, consistency, coherence)
  2. Abstraction (understanding how OS, filesystem, and database works)
  3. Real-world performance (relative performance RAM, disk, your network, SSD)
  4. Availability and Reliability (durability, understanding how things can fail)
  5. Datastorage (RAMvs. durablestorage, compression, byte sizes)
  6. 走进系统设计 & 设计推特 Introducting System Design & Design Twitter
  7. 数据库系统 Database System
  8. 爬虫系统与搜索建议系统 Web Crawler & Google Suggestion
  9. 分布式文件系统 & 设计查询系统 Google File System & Design Lookup Service
  10. 网站系统设计 & 设计短网址系统 Web System & Design Tiny Url
  11. Big Table 原理透析
  12. Map Reduce & Design WhatsApp
  13. 基于地理位置信息的系统设计 Location Based Service
  14. Freelance.tv
    https://html5up.net/
    http://www.flaticon.com/
    [image:B622CC3B-BCC1-474F-9D36-FD8C76B3E2FD-37859-000140F96EDBCD70/524C8499-9A9A-457E-AB02-3C104DC87664.png]

问题收集

为何不找一个算法使长网址与短网址相对应？
即使我们定义短地址是100位。那么它的变化是62的100次方。62=10数字+26大写字母+26小写字母。无论这个数多么大，他也不可能大过世界上可能存在的长地址。所以实现一一对应，本身就是不可能的。
正确的做法是通过发号策略，给每一个过来的长地址，发一个号。小型系统直接用mysql的自增索引
如何处理发号器的单点问题，做成集群，分散到几台集群，例如一台机器发单号，另外一台发双号

常见分布式系统设计问题

如何设计Twitter，短网址系统设计，如何设计Uber
分布式系统
1)Inverted index
2)Anagram
3) Word Count
4) Distributed File System Design 设计
实时位置系统
1) Design Yelp
2) Design Uber
3) Design Whatsapp
搜索系统设计
1) crawler
2) typeahead
3) inverted index
failure rate, DNS, web server, file server, timeout, content delivery network, cookie, HTTP, divide and conquer, Internet service provider, hosts, hijack, retention rate, cache, lazy load, rate limiter, QPS, counter , expire, request list, token bucket
网站系统设计
1) What happend if you visit www.google.com?
2）How to design rate limiter?
3) How to design data log?
面向对象设计
数据库系统设计
database, primary/foreign key, table, row, attribute, index, transaction, log, lock, lifecycle graph, binary search tree, B+Tree, atomicity, consistency, isolation, durability, session

  1. 设计一个牌类游戏 OOD
  2. 设计一个服务监视系統。说你有一堆服务器和一堆服务，怎么监视服务状态。 系统设计。各种情况。各种要求。
  3. 设计一个企业内部用的那种日志系统。大概的用途是A发现一个什么问题，log问题，相关的人会接到通知。半系统半OOD。中间面试我的人想给我点提醒。说中间某部分可以用某种design pattern来做。不过那个design pattern不是factory singleton observer strategy等几个常见的。所以提示了和没提示一样。
  4. 设计一个和配置相关的系统。大概的功能是比如A要买你的软件，人家可能不需要把你所有的功能买走。他提出了一些他想实现的功能，然后你把你内部的一些模块啥的拼一拼然后给人家。这样一个系统怎么设计。
  5. 要求设计一个DNS的Cache结构，要求能够满足每秒5000以上的查询，满足IP数据的快速插入，查询的速度要快。（题目还给出了一系列的数据，比如：站点数总共为5000万，IP地址有1000万，等等）
  6. 有N台机器，M个文件，文件可以以任意方式存放到任意机器上，文件可任意分割成若干块。假设这N台机器的宕机率小于1/3，想在宕机时可以从其他未宕机的机器中完整导出这M个文件，求最好的存放与分割策略。
  7. 假设有三十台服务器，每个上面都存有上百亿条数据（有可能重复），如何找出这三十台机器中，根据某关键字，重复出现次数最多的前100条？要求用Hadoop来做。
  8. 设计一个系统，要求写速度尽可能高，说明设计原理。
  9. 设计一个高并发系统，说明架构和关键技术要点。
  10. 有25T的log(query->queryinfo)，log在不段的增长，设计一个方案，给出一个query能快速反回queryinfo

一些其他题目

  1. 设计文件系统
  2. 数据结构for spreadsheet
  3. 一个app需要用cache，怎么实现thread safe
  4. social network, billions id, every id has about 100 friends roughly, what is
    max connections between any two ppls. write algorithm to return min
    connections between two ids: int min_connection(id1, id2)
    you can call following functions
    expand(id) return friends list of id
    expandall(list) return friends union of all the ids in the list
    intersection(list1, list2) return intersection
    removeintersection(list1, list2)
  5. Open google.com, you type some words in the edit box to search something, it will return lots of search results. Among these returning results (that
    is, website link), you may only CLICK some results that are interesting to you. The system will record the “CLICK”action. Finally, you will have the search results (i.e. url) and “CLICK” informatin at hand.
    Question: how do you find the similarity of these searching?
  6. 如何找出最热门的话题(根据tweets)。如果一个话题一直热门，我们不想考虑怎么办
  7. Discuss design challenges of a distributed web crawler running on commercial PCs. How to utilize network bandwidth of those PCs efficiently?
  8. Design a site similar to tinyurl.com
  9. large log file,含有 customer id, product id, time stamp想得到在某一天中某个custom看网页的次数1. 足够memory 2. limited memory
  10. 设计一个actor和movie的数据库的schema, 支持从movie得到它的actors和从actor得到ta出现过的moive (Google, phone, 2006)
  11. 某建筑有五十层高,打算装俩电梯,设计该电梯系统
  12. how to design facebook’s newsfeed?
  13. 一个文件里n行m列，每行是一个record，每列一个feature，你时不时要按不同feature排序和查找。不能用数据库，文件大小内存能装下，数据结构和算法不限，语言不限，给出你最好的办法。
  14. Design online game
  15. static 变量用来在整个class中共享数据.基于此，各种synchronization技术， 以及busy waiting的优缺点，啥时候要用基于busy waiting的 spinlock主要是基于性能的探讨。 如果有一个应用程序运行时没有达到timing constraint，
    你如何去分析问题出在哪儿， 可以用什么工具或者技术。
  16. 设计题， 有一个多台机器构成的cluster。 现在有大量公司的数据文件 （并有多个备份）。 如果设计一个算法，使得每台机器尽量均衡的使用，并且 每个公司文件的不同copy不能存在于同一台机器上。主要的Idea就是用round-robin的方式assign每个公司的原数据文件到一台机器，再结合使用hashtable。
    Interviewer提到我的解法正是他现在在使用的解法。
  17. Design a class providing lock function which provide lock only if it sees there are no possible deadlocks.
  18. 设计一个分布式文件系统，给定path name，可以读写文件。具体的system design这里就不提了。其中一个细节是，给定path name，怎么知道哪个node拥有这个文件。我提出需要实现一个lookup function，它可以是一个hash function，也可以是一个lookup
    table。如果是lookup table，为了让所有client sync，可以考虑额外做一个lookup cluster。然后Interviewer很纠结，既然可以用hash function，为什么还搞得那么复杂。我就告诉他hash function的缺点。假定一开始有N个node，hash function把M个文件uniformly distribute到N个node上。某天发现capacity不够，加了一个node。首先，要通知所有的client machine，configuration 改变了。如果不想重启client
    machine的process，这不是一个trivial job。其次，文件到node的mapping也变了。比如，本来按照hash function，一个文件是放在node 1。加了一个node 后，它可能就map到node 2了。平均来说，N/(N
    +1)的文件需要move到新的node。这个data migration还是很大的。然后我就提出一些hash function的design，可以减少data migration。最后他提了一个问题，说要实现一个function，要统计distributed file system所有目录的大小。前提是，一个目录下的文件可能放在不同的node上。我说这个不就是在每个node上统计，然后发到一个merge吗。他说对，但是又问用什么data
    structure来表示。我说这就是hash table，key就是directory name，value就是大小。因为directory本身是树结构，这个hash table的key可以用tree来组织。最后让我实现一个function，把我说得这个data structure serialize成byte array。因为这个byte array就是网络传输的data。我用了depth first traverse。不过等我程序写完，才发现，用breath first traverse会更方便，code也会很简洁
  19. 超大图的存储问题
  20. 给个Lock w/ two atomic method lock() and unlock()，请用lock实现一个文件读写的系统，要求：
  • reader blocks writer;
  • writer blocks reader;
  • writer blocks writer;
    21。设计一个web cache server，假设存储网页数量是10个billion，打算怎么设计
    22.你可以得到网站访问记录，每条记录有user IP, 写一个程序，要随时能算出过去5分钟内访问次数最多的1000个IP. 这个好像跟着这个rolling window 的precision 有关，所以我们暂且定为5秒钟update 一次window
  1. Design free and malloc.
  2. how to design data structures for a facebook network and how to design an algorithm to find connection? How to optimize it if data is distributed
    into multiple computers?
  3. design a deck class and member function to randomly select a card from those cards which haven’t been selected before. (You can assume the number
    of this function call will never be larger than the number of cards) For example, we have a deck of four card: 1,2,3,4. First it may select 3, then next time it should randomly select one from 1,2,4… And design a member function to reset.
  4. google search design problem. How to distribute data and how to design backup system
  5. 设计一个online chat system
  6. design bit.ly url shortening web service。算法设计，后端存储，中间层cache，前端load balance，最后是web analytics。
  7. Design and implement an algorithm that would correct typos: for example, if an extra letter is added, what would you do?
  8. Suppose there are 2 persons A and B on FB . A should be able to view the pictures of B only if either A is friend of B or A and B have at least
    one common friend . The interviewer discussed it for nearly 30 minutes . The discussion mainly included following points：
    • How are you going to store the list of friends for a given user?
    • File system vs DB
    • Given list of friends of 2 users, how are you going to find common friends?
    • If you are going to store the friends in DB then how will the table look like?
    • How many servers do you need?
    • How are you going to allocate work to servers?
    • How many copies of data will you need?
    • What problems will you face if you are maintaining multiple copies of data.
  9. design structure for auto completion
  10. 如何实现search suggestions。
  11. 设计fb的系统支持like那个button
  12. design 股票#，time，price；
    -设计一个client side显示股票信息，给出尽可能多的user case
    -在给出的user case里面，怎么设计客户端，使得客户段性能提高
    -怎么设计server端
    -数据如何传输
    -server端如何保存数据
    -怎么设计database table保存数据
    -不用index怎么提高数据查询速度
    -database是怎么实现数据查询的（要求从database implementation角度解释）

系统设计面试总结

  1. 入门级的news feed
    http://www.quora.com/What-are-best-practices-for-building-somet
    http://www.infoq.com/presentations/Scale-at-Facebook
    http://www.infoq.com/presentations/Facebook-Software-Stack
    一般的followup question是估算需要多少server
    另外这个帖子有讨论
    http://www.mitbbs.ca/article_t/JobHunting/32463885.html
    这篇文章稍微提到要怎么approach这种题，可以稍微看看
    http://book.douban.com/reading/23757677/
  2. facebook chat,这个也算是挺常问的
    http://www.erlang-factory.com/upload/presentations/31/EugeneLet
    https://www.facebook.com/note.php?note_id=14218138919
    http://www.cnblogs.com/piaoger/archive/2012/08/19/2646530.html
    http://essay.utwente.nl/59204/1/scriptie_J_Schipers.pdf
  3. typeahead search/search suggestion，这个也常见
    https://www.facebook.com/video/video.php?v=432864835468
    问题在这个帖子里被讨论到，基本上每个问题，在视频里都有回答
    http://www.mitbbs.com/article_t/JobHunting/32438927.html
  4. Facebook Messaging System(有提到inbox search, which has been asked before）
    messaging system就是一个把所有chat/sms/email之类的都结合起来的一个系统
    http://www.infoq.com/presentations/HBase-at-Facebook
    http://sites.computer.org/debull/A12june/facebook.pdf
    http://www.slideshare.net/brizzzdotcom/facebook-messages-hbase/
    https://www.youtube.com/watch?v=UaGINWPK068
  5. 任给一个手机的位置信号(经纬度)，需要返回附近5mile 的POI
    这个这里有讨论，这题貌似nyc很爱考…
    http://www.mitbbs.ca/article0/JobHunting/32476139_0.html
  6. Implement second/minute/hour/day counters
    这题真不觉得是system design，但万一问道，还是要有准备，貌似在总部面试会被问
    道….
    这个帖子有讨论
    http://www.mitbbs.com/article_t/JobHunting/32458451.html
  7. facebook photo storage，这个不太会被问起，但是知道也不错
    https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Beaver.pdf
    https://www.facebook.com/note.php?note_id=76191543919
  8. facebook timeline,这个也不太是个考题，看看就行了
    https://www.facebook.com/note.php?note_id=10150468255628920
    http://highscalability.com/blog/2012/1/23/facebook-timeline-bro

除了这些，准备一下这些题目
implement memcache
http://www.adayinthelifeof.nl/2011/02/06/memcache-internals/

implement tinyurl（以及distribute across multiple servers)
http://stackoverflow.com/questions/742013/how-to-code-a-url-sho

determine trending topics(twitter)
http://www.americanscientist.org/issues/pub/the-britney-spears-
http://www.michael-noll.com/blog/2013/01/18/implementing-real-t

copy one file to multiple servers
http://vimeo.com/11280885

稍微知道一下dynamo key value store，以及google的gfs和big table

另外推荐一些网站
http://highscalability.com/blog/category/facebook
这个high scalability上有很多讲system design的东西，不光是facebook的，没空的
话，就光看你要面试的那家就好了..
facebook engineering blog
http://www.quora.com/Facebook-Engineering/What-is-Facebooks-arc
http://stackoverflow.com/questions/3533948/facebook-architectur

其他家的
http://www.quora.com/What-are-the-top-startup-engineering-blogs

==================================================================
在说说怎么准备这样的面试
首先如果你连availability/scalability/consistency/partition之类的都不是太有概
念的话，我建议先去wikipedia或者找一个某个大学讲这门课的网站稍微看一下，别一
点都不知道
这个链接也不错
http://www.aosabook.org/en/distsys.html

如果你这些基本的东西都还知道，那么我觉得你就和大部分毫无实际经验的人差不多一
个水平…
能做的就是一点一点去准备，如果你还有充足的时间的话，建议从你面试的那家公司的
engineering blog看起，把人家用的technology stack/product都搞清楚，然后在把能
找到的面试题都做一遍呗….我们做coding题说白了不也是题海战术…而且你如果坚
持看下去，真的会看出心得，你会发现很多地方都有相同之处，看多了就也能照葫芦画
瓢了…

再有就是面试的时候应该怎么去approach这种题，我说说我的做法

  1. product spec/usage scenario 和面试者confirm这个东西到底是做什么的
    可以先列出来几个major functionality，然后有时间的话，再补充一些不重要的
    把你想的都写下来

  2. define some major components
    就是画几个圈圈框框的，每个发表一番您的高见….然后讲他们之间怎么interact

以上是question specific的东西，
这个讲完了，我们可以讲一些每道题都是用的，比如说
怎么scale/怎么partition/怎么实现consistency，这些东西，可以套用到任何题上

系统设计丨如何设计Twitter（完整版）
Novice, http://url.cn/faa4ko
Novice, http://url.cn/1ob37A
Novice/Expert, http://url.cn/eKslaK
Novice/Expert/Master, http://url.cn/cinh36
Expert, http://url.cn/g4JSMc
Expert, http://url.cn/ayEgtO
Expert, http://url.cn/efdJnC
Expert/Master, http://urhcn/fr44T4
Expert/Master, http://url.cn/H2CLaU
Expert/Master, http://url.cn/RXRa8P
Expert/Master, http://url.cn/hWvan
Master, http://url.cn/ULnxoG

当然了，我们遇到的题和解题的方法可能都有些出入，不见得每道题有一个路数下来，
最重要的是，讲题的时候要有条理，画图要清楚，保持和面试官的交流，随时问一下人
家的意见。

参考资料

  1. 几个系统设计问题的解决思路
    10.系统设计类题目
CATALOG
    FEATURED TAGS
    system_design
    FRIENDS