TODO:
Episode 06: (No background music) Intro to Architecture and Systems Design Interviews
http://static.googleusercontent. ... anford-295-talk.pdf
http://www.cs.cornell.edu/projec ... ynote-ladis2009.pdf
https://github.com/checkcheckzz/system-design-interview
收集的Prep for Interview - System Design//OOD 资源
求问一道系统设计题，设计一个load balancer
如何设计一个load balancer。要求设计一个基于hashing的load balancer, 要求在改变hash 函数时同一个connection里不能有out of order 的message
据我所知，这种场合下常见的hash方案有两种：1. Consistent Hashing （所谓的“一致性哈希”）, 2. Rendezvous Hashing（这个我不知道怎么翻译，“交汇哈希”？）。
比如，前者的大概意思是
1. 把传统的长度可变的线性哈希空间变为一个环形的，周长==1的圆环；
2. 将“请求i”通过某个hashCode()映射到这个圆环Pi位置上；
3. 将“第j台server本身”映射到这个圆环上的k个不同位置：Sj1,Sj2...Sjk
4. 每个请求i都放入“从Pi开始，沿圆环顺时针前进遇到的第一个S所对应的Server上”。
这样，如果server j下线，则仅需将它上面的每个请求顺时针转移到下一台server上即可。由于Pi和所有的Sjk都应当是均匀分布，那么可以期望Pi上的元素会被均匀分散到另外若干台server上。
重映射以后，每台Server再把新分配来的数据和已有的数据进行一次merge操作应该就可以了。
“设计一个load balancer，将外界的请求尽量均匀地分配到N台server上。要求
1：load balancer的分配方式是通过hash运算实现的；
2：当server数目有调整时，要在server之间移动待处理请求，以使各server负载重新保持均衡。
3：每一个server内待处理的请求应总是按到达时间排序。如发生负载调整，那么调整后各server内的请求依然应保持按时间排序。
如何设计一个系统schedule meeting
微软online screen: Design API for email service怎么做？j
用熟悉的语言写一个email的api 服务。写出实现的场景以及需要用到哪些参数
系统设计题的总结！！！不信自己今年找不到工作之系列！！！
以后大家有课程project没思路，可以去实现tiny shortener哈。面试时又可以扯蛋，又可以当作课程project，一举多得哈
定义：http://en.wikipedia.org/wiki/URL_shortening 看了定义，感觉就是要设计短URL，就是长URL 关联 uniqie key , 这些key 可通过 hash 函数和随机数产生器等产生
这篇文章介绍了我们自己如何实现一个url shortener（http://www.sitepoint.com/building-your-own-url-shortener/）。该文章实现tiny url用的是php。短url一般也就是数字和大小写字母组合在一起。比如1位有62种可能性，那么2位可以组合成62*62可能性，3位有62*62*62，4位即有14776336种 combinations了。可以想象当由10位组合成tiny url， tiny url可以有多少！ 这篇文章介绍了如何设计数据库，如何创建url short code, 如何decode short code, 以及最后的如何拼接起来。
求问一道System Design设计Hangman
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=207403
这道题目是linkedin onsite的面经
设计一个上吊游戏的web应用，大家可以玩一下先：http://www.hangman.no/
需求变化：1. 用户游戏赢钱，输钱；2. 用户增加到5M+
网上没有找到很好的答案
https://www.hiredintech.com/courses
设计狗家日历
System design: 虽然某些system design我已经看完一遍，部分看了两遍。但是感觉理解不够深入。所以决定每天深入一道设计题。记录并想明白各个feature和tradeoff.
当然最重要的还是需要不断总结和深入思考，不能只追求数量。
地图上分割成不同区域这个设计题的核心是什么来着？
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=301057
记得有个什么算法为核心，就是分割成一块一块，然后有不同情况下的优化，
但是想不起来具体是什么来了。还看过一篇中文的文章讲得不错，可惜记不清细节了
在职刷题 + System Design + 面试准备的路上
1 着重在thinking process，不要想45分钟给一个完美的解决方案
2 条理要清晰，有big picture，有data modeling，有data flow
3 多从customer角度来考虑，用户要什么知道了，你才好决定你的设计中的取舍
4 不要一开始就挖大坑，从MVP开始，最后时间足够才加新的feature
5 从最开始简单的架构开始迭代，分析负载上去了之后的bottle neck在哪儿，你要怎么优化。这时候再带入一点customer最关心的是哪里，可以做哪些tradeoff。你做这个技术选型的原因是什么，因为技术mature还是没有spof6 最后一定要review一下系统的scalability，负载x10的话，你的架构是不是线性的加资源进去就好了？
7 架构确定好了之后，最好来个预估要达到这个性能指标，我们需要多少机器以及怎么部署
8 别忘了提一嘴logging monitoring
9 扯一扯service oriented architecture也是极好的
10 把qconf 2012里scaling Pinterest from 0 to billions看几遍，我看了那么多资料里面，最有启发的一篇
总的来说，我不太建议一上去就摆一个高大上的架构，从小到大循序渐进的来，你就可以展现你更多的能力，不光有breadth还有depth。系统设计都是相通的，碰到没见过没准备的不要蒙蔽，毕竟要考察的是思维过程，不是要求你设计一个完美解决方案。
System Design: 白板走了一遍Tiny URL, 并过了一遍输入url,浏览器端会发生什么的整个过程，URL->DNS resolution (IP lookup from browser, OS , router, DNS cache first, DNS query later form Domain) -> Server with TCP connection-> HTTP request -> Waiting for response -> server send request to application -> code execution and DB query -> response -> transferring data -> CDN (css, js, image, video ) -> browser presenting
System Design: Design Logging System, 这题感觉更像是OOD, 使用Observer Pattern Design或者Aspect Oriented Programming的方式去做logging
System Design: Design Typehead
此题的场景是搜索框，每输入一个单词，就会给出top k的单词推荐，这些推荐是根据用户对这些单词的点击率，需要使用Trie来解决。所以我们需要两个service，一个是DataCollectionService和QueryService, DataCollectionService会定时从Log DB中统计每个词的点击次数，然后offline跟新QueryService中Trie, 为了保证速度，Trie存入In memory中，但是为了不会是Trie丢失，还需要在disk中存一份Serialized trie.
当Trie过大无法存入一个In memory的Cache中时，我们需要多台机器，以每个prefix做consistent hashing的key来存入不同的机器中而不是以每个单词的首字母来把所有prefix存入,这样还是存在一个机器存不下，而使得同一个prefix的所有top word存入不同机器中。
另一个优化是，在浏览器端使用cache,一个是cache已经输入过的prefix，当重复删去和添加相同的prefix时可以避免request from server,
还有一个优化是每输入一个prefix，就多加一个单词在前端存储下一个prefix的前1000个word.
今天主要在看design, 看了两个design，一个是Design Google sheet, 一个是Design messager.
Design Google sheet 的主要问题是用什么数据结构来存储ceil, 并进行增删改查的操作，并且需要用判断有向图是否带环(BFS or DFS)的算法来判断是否有circular dependency。
另外多人同时操作，使用的原理是Latency compensation是先写在page上，并predict这是最终显示结果，同时server端会去sync，是否有其他人也在修改，如果有的话则需要重新根据时间顺序来覆盖操作，如果无人修改则保留原有记录。server sync的原理是一个线程锁住log，并把此次的event加入log中，然后释放log. 保证所有thread读到的都是最新的log
Design messager 的主要feature就是发信息,群聊和在线状态检查。发消息的主要问题是如何使用合理的db存储和如何即时通信，存储DB要设计好合理的table,比如message和thread table, 而通信可以分为两个service,一个message service，一个push service.
message service负责接收user的message，存储进db，并发送给push service，push service负责与user进行socket连接并发送message.
群聊需要在message 和push service中间加入channel service，这样channel service负责接收一次message service的message，然后发送给subscribe在channel service上的active user. message serveice 会帮忙subscribe，而push service会知道用户是否在线，下线的时候remove user from channel. 查在线状态通过user每4秒pull一次state of friends and tell server itself is alive. 这个方式和uber司机不断的告诉server自己的位置一样，也是heartbeat的方式来告知server是否在线
Uber 相关技术栈以及One click system的架构，workflow：sender ->send the message to Gateway -> messaging platform -> persisted in DB(Cassandra) -> local push service and remote push service -> send the message to Receiver -> respond message received to messaging platform. AI架构相关： sender -> Backend service -> ML platform (message to intent detection(simply the message) -> reply retrieval(provide response)) -> Top k suggested replies -> Receiver
目前就是对经典topic一个一个啃，然后白板画一遍全部流程，从scenario开始分析用户量,QPS多少和存储量多大，这个能决定之后会用到什么样的DB和优化方案。然后分析主要有哪些feature需要在MVP阶段实现,以及需要哪些service来构成microservice架构，每个service都作为一个独立的server再配备相应的DB,根据需求和之前对scenario的分析来决定用NoSql还是SQL。然后设计出DB schema, 画出完整workflow, 形成完整的work solution. 后续会参考多方资料来深挖多种solution以及其他细节作为follow up即为scale部分做准备。
How to design User System
接着上次的Friendship Service, 这个service最主要难点是如何存储friendship的数据，如果使用SQL, 可以把好友关系只存取一份，但是查询的时候需要查询两次，因为不确定哪一边是target id. 方法二是把好友关系存两份，查询只需一次。 如果使用NoSql,比如Cassandra, row key为user id, column key 为friend id. 在此我们分析一下数据库的优化: 对于Sql,我们可以使用index来加速查询操作,之所以速度提升是因为从以前的全表搜索变成了字段值单独提出来建立二叉树搜索。但是缺点是建立索引也需要占用空间,索引不能过多,否则在数据添加更新删除的时候会消耗更多时间,因为需要找到特定的位置以及保证有序，而不是像以前那样直接做修改。NoSql很容易horizontally scale, 通过对row key的consistent hashing即很容易实现sharding. 而Sql更容易实现vertical sharding. 对于选择NoSql还是Sql,主要取决几个方面: 1. 如果是有transaction,推荐使用Sql 2.如果data is structured and unchanging,推荐使用Sql. 3.如果想要repid development,意味着data structure经常变动,使用NoSql. 4.如果想要节省服务器资源而提高性能,选择NoSql, 也更容易scale across multiple data center
复习News Feed 以及 看OOD设计 how to design Elevator, 主要用到strategy design pattern
今天主要看了Uber tech blog, 讲了整体业务和架构方面的东西，把以前零碎掌握的东西顺了一遍。另外看了一些工作中要用到的一些前端的知识
看了另一个将messaging system的视频，有了新的角度，就是用redis来存用户最后的heartbeat的时间，用此来判断用户online还是offline
今天快速过了一下《Professional JavaScript for Web Developers 3rd Edition》的一些章节，为了工作上的项目实现树状结构的sequence创建存储进DB，并从DB拿出数据还原成树状结构，有点像Serialize and Deserialize Binary Tree，但是要实现比较美观的效果以及sequence的有序性，并保证按照sequence去执行任务，数据库的设计上还有些问题没想通，后端程序员还得搞前端，只能恶补js了
把How to design Twitter, Uber, Rate limiter, Typeahead, Tiny URL, Messaging System 全部白板过了一遍。
今天的bar raiser面试跟面试官聊嗨了，给了我很多接下来面试的tips，还说他一般面technical design的话会出how to design Netflix...哈哈 所以找时间我也来补一下这个吧
系统设计,建议基本还是和自己工作的内容相关的设计才比较有用,因为一般的书讲的都是一些general design的,简单的理解就是讲通用架构上的东西,各个子系统之间如何隔离等等,
但是和自己业务相关的系统设计才是最值得去研究的,因为哪里有坑,哪里会有设计缺陷,这些都是一次次的跳坑和填坑才总结出来的,比如哪里可能会有高并发,cache如何处理等等,这些一般书里讲不深,也讲不明白,毕竟每个系统都不一样,业务模型也不一样,所以多看看现在的公司的架构设计和系统设计才是硬道理.
刷题这个基本是保持一个手感的问题,看到题目知道他分到哪个大类里面(字符串处理,DP,搜索,数据结构,图论等),知道这个基本面试的时候不会慌就OK
如果说真正提升技术我基本赞成你的观点，只是想补充一点：并不是每个人的工作中都能接触到有高并发或者scale的情况，大部分时候还是在做很基本的CRUD,API等。所以只能靠外部资源来扩充这方面的知识。当然对自己工作中的业务熟悉和了解那是必备的，否则很多behavior就挂了
面了一圈下来感觉刷题才是王道，算法每次面的各不相同，而System Design大都是一样的套路。所以决定接下来的一个月，以刷题为主，Sysytem Design 则以grokking system design 偶尔进行复习。
今天design discussion提出了很多有价值的问题，感觉这段时间的面试准备对自己工作能力上的提升也是肉眼可见的，虽然还没拿到offer但是依旧很开心，继续坚持吧
How to design Netflix/Youtube.
主要feature有 upload video, view video, share/like/dislike video, subscribe channel, 通过video title 来搜索video, 评论和浏览评论。
主要流程为 User -> upload video -> processing queue -> Encoder -> encode into multiple formats and generate thumbnail to file storage -> store video metadata and user data.
主要存储结构为: file storage system for video and Bigtable for thumbnail, SQL DB for user(id, name, email, age, address) and video metadata (id, title, description, size, uploader, thumbnail, total number of like, total number of dislike, total number of views).
Scale and Optimize: video deduplication 为了节省资源, 把上传的重复的视频只存取一份， 如果上传的视频是其中的一部分或者延展更多的部分，则把missing的部分切成更小的chunk存储。对于popular video可以用cache来加速读取，充分利用好CDN,把视频资源放在更靠近user的地方
今天看了How to design twitter search, 即对每条twitter使用inverted index来进行关键字搜索，grokking system design 感觉更偏重于index建立所需要耗费的storage大小的计算上，对于搜索和ranking部分介绍不多，以后有时间再把search这块的design补一下
复习了一下数据库的index原理，主要利弊就是：increase read performance and decrease the write performance.
Designing Pastebin
主要功能有保存一段文本并生成一个unique URL 读取。类似于TinyURL功能，多了一个文本生成和保存。content可以使用object storage like Amazon‘s S3保存。其他信息比如Paste 和 User信息用SQL存储. Paste包含URL, ContentKey, UserId, CreationData, Expiration. URL的生成可以通过Key Generation Service. Generate random six letters strings beforehand and store them in DB. 可以 keep some keys in memory whenever a server needs them. 牢记80-20 rule, 20%的URL会产生80%的traffic。所以需要Cache这20%的paste.并可以此计算需要的space大小
Design Instagram
本来以为Instagram会有什么不一样的Design，发现Grokking上讲的就是Design Twitter的略简单版本。主要功能有upload/download/view image/video, Newsfeed/Timeline, follow and unfollow friends. 首先是分析DAU，QPS. 然后是分析存储这些image/video需要多少空间，存储1年需要多少.
然后存储就可以使用file system like S3. 而Friendship 和 User, Photo 的metadata需要使用Sql存储. 然后是News feed 的两个mode，pull and push, 最佳策略是hybrid两个，对于所有人使用push，对于hot users with lots of followings 使用pull.
对于Scalability这块，我们需要根据photo id 来做metadata的sharding，原因是如果对于userID做sharding，会导致几个问题，一是对于hot users和一些拥有大量image/video的用户，通过userID来做partitioning可能一个shard并不能存储该user的全部信息，反而会影响性能。
还有一个问题是把一个user的所有信息都放在一个shard的话，如果这个shard down了，那么他的所有信息都会unavailability。
如果这个用户是hot users那么也可能产生high latency if it's serving high load. 对于photo的ID我们可以使用Key generation service提前生成，为了避免single point failure，我们可以使用两个DB，一个放odd incrementing number一个放even incrementing number. 每个photo只需要去take一个id即可，保证了the sequence of auto incrementing ID. Then use load balancer to deal with downtime. 对于实现快速获取最新的photo，可以使用photo ID用epoch time + incrementing number. 这样的好处是能够加速数据库的查找操作，因为我们肯定会index photoID
Design Dropbox
这个设计相关的知识点对我来说比较新，所以看完一遍能掌握的部分并不多。先来第一遍吧，主要的功能有upload/download files, share files/folders with other users, support automatic synchronization between devices, support offline editing.
Files 存储在file system中，Metadata of Chunks, files, User, Devices, workspace(folders)存储在SQL中。对于files的同步操作，比如update的主要的workflow为用户A上传chunks, 更新metadata并commit changes，
A得到confirmation，并发送notification给B、C, BC接收到metadata changes并download updated chunks. 对于ABC同时更改同一个file，需要把他们更改的操作按时间顺序放入同一个request message queue中依次处理。然后分别创建response message queue给每一个client来响应。对于文件的上传，是把一整个file分为多个chunk来上传，为了节省空间避免duplicate，我们可以在上传前去hash chunks and lookup.如果发现已经含有，则only add the reference rather than the full copy
系统设计：
twitter design， whatsapp design， LRU design. Hash & consistency hash.
OOD:
设计停车场。
然后楼主刚刚上岸了，还有两个其他的面试，应该会在一周内面完。之后应该就短暂不更新了。哈哈哈。
接下来几天会写的题：
youtube设计。
Uber设计。
Expedia设计
twitter设计。
功能概述：
tweet，
timeline（home timeline, user timeline, search timeline）,
Trends （#）
数字：
300 M users
Write: 600 tweets / sec
Read: 600000 tweets/ sec
Conclusion：
Read heavy
eventual consistency(timeline 上的delay 被允许)
How to scale storage and read for users?
Redis: 使速度更快。
DB: copy data.
db:
user table| tweet table | followers table
redis:
key: user id value: tweets | followers
homeline construction：
fan out
今天做了一道expedia onsite的原题。最近在准备expedia家的final round。
题目是餐厅预订系统。我仔细想了想应该是不需要对餐厅进行组成规划的。（因为预定系统实际上并没有用到具体的餐桌 / 厨师 / 厨房设施）。
从算法角度，还可以依次检查餐桌是否可行，这样可以增加一个新的对象餐桌，从而实现每个成功的订单都有对应的桌号。也算另一种做法了。
OOD:餐厅预订系统
对象： 餐厅（不包括厨房）， 订单， 用户。
餐厅：
logic:
default： 只考虑餐桌，不考虑服务人员。
association：订单。用户。
功能： 接受订单， 根据当前点，对应人数和高峰餐厅占有，判断是否可接受，dispatch给餐桌，并反馈给用户。
取消订单，回收餐桌。notify观察者模式(提醒用户可再次发送订单)。
（synchronized）
订单：
logic：枚举状态，并将餐厅对订单的回应反馈给用户。
用户：
logic：发送订单请求。根据反馈将订单添加到失败队列或者成功队列。
当接收到餐厅的订单取消时。重新发送处在失败队列中的订单
系统设计如何准备？
最后达到“都是套路”的状态。
关于系统设计的一个忠告
题是一道经典的关于search engine设计。不过，哪道题并不重要。重要的是我要跟大家讲一下的策略问题。
千万，绝对，一定不要太早地涉及到数据结构或者任何一部分你认为复杂的部分，我的意思是尽量不要提。
到你要提的时候，你要有一直讨论到结束的觉悟。
不要觉得能一笔带过就把它提出来，想着以后再优化。因为，你是在卖，破，绽。
我就着了道。。。
面试的人是南亚你懂的国人。一开始看到题目，心里打了顿，擦，没有仔细写过这题啊。不过不怕，原理还是知道的，咱还有套路。
然后就开始做各种估算，然后又随手画了几个框框表示了一下，不过画得很不精细。想着还能回头来细化。
然后我就开始作死，要不我们先看一下该怎么存index数据，看一下容量，再回头来优化内存的存储吧。然后，就开始一条不归路。
当我写下一第一个数据结构，准备估算的时候。面试的那位就打住了我，说，你这个数据结构不是最优的，速度可能不够。然后就开始讨论起数据结构。
我以为只是他比较重视数据结构。然后开始讨论。搜索引擎实在不是很熟悉的东西，做得磕磕绊绊，不过他一直要求讨论这个，我也就只好跟着一起讨论。每次我想跳到下一步，他就说我们再看一下数据结构。
花了一些时间讨论出了一个大家都接受数据结构。然后心想，终于能往下走了。
这个时候，他突然跟我，还剩五分钟，你问问题吧。这时候，我大吃一惊。时间过的这么快。然后就匆匆忙忙的算了一下内存容量，说装不下，要不只装最hot的（还要分片，我知道，太紧张没说出来，不过不要紧，因为他已经没在听我说话）。最后我想，也差不多了吧。就说，就这样吧。问问题吧。这时他说还有三分钟。问问题这地方也可以说道说道，我感觉问问题的时间绝对不止3分钟，因为我问完一个问题，他说，还有时间你还要不要问。我又问了一个。
最后高潮来了，他就站起来准备走的时候说，虽然你没有给出一解决办法，但是我知道你懂的东西了。EXO me？！没有解决办法？我们讨论了半天的数据结构难道不是一个解决办法吗？
至此，一套组合拳打完。LZ直接GG。。。
看着满黑板的数字和几个孤零零的框框。我觉得我准备的心血，都喂了狗了。什么互相交流，什么螺旋式讨论，什么先粗后细，全是狗屁。我见识少，玩不过你。
最后再说几句。我一路面过来其实已经用自己亲身经历打破了很多关于面试的迷思，什么一轮要做几道，做不到就挂了。要bug free，有个bug就挂了。都不是一定的。最重要是要把问题说明白了。
说明白了，就算少做那么一道题，有那么一个两个小bug，其实是不影响的。毕竟对面的是个人，不是一台机器。不过人心难测，因为面试外因（对面那个）是不可控的，那归结内因（自己）就是最自然的想法了。
还有一句话，世界很小的，今天对面虐你的，明天可能就来被你虐。都很难说，最重要是记住他的名字。哈哈哈哈
多谢楼主的建议，确实应该先把大框架说完，再根据面试官的问题来优化某个部分。
分布式系统设计自学整理
一天一道系统设计/OOD
我和他聊崩主要原因是，我当时完全被算法硬思路困扰了。
我当时就是用的一个queue， 然后检查queue中最老的，pop出去。按照我的思路，这个复杂度完全应该是O（1）啊因为单位个体每个push一下，pop一下。但是他觉得就是O（n）。
后来我仔细仔细想了一下确实应该是O（n）,因为实际上对单位次呼叫的worst case实际上就是queue中所有的个体。
我查了一些资料后来，这个题思路应该是：
queue -> 按时间分区间统计个数的queue（这样就能控制复杂度为O（1）了）-> token bucket。
更深的还要谈如果数据量上涨，就要用sticky session来控制服务器分配云云。不过那里太陌生我已经记不太清了
关于 nosql , bigdata 系统设计相关的学习材料
问几个系统设计的问题
我看了一些系统设计的例子，比如说，设计一个推荐系统，这种题就让我很为难。
你看，如果是让设计一个twitter, 那很清楚，用户可以发推，follow, 更新timeline 啥的，这种推荐系统，我知道可以根据用户的search 记录，最近购买的东西，他常购买的东西，品牌，地理位置等，这些我都知道，都可以拿来作为推荐的因素。但是这个系统的输入是啥?
twitter的输入就是用户发个推，那推荐系统的输入就是用户浏览/搜索你的网站？然后你后台跑个服务把你的行为都记录下来?
https://github.com/donnemartin/system-design-primer
一般的app server也需要replication吗？
1. app server挂了怎么办？我答，没关系啊，挂了就挂了呗，反正有多个app server -_-
我只知道db server挂了需要backup replication激活，app server挂了也需要这样子吗？为了抢救app server的cache？但现在都强调api 应该stateless啊
2. loader balancer怎么知道app server挂了？我也不太懂，之前我做过一个小系统，我记得loader balancer自己会测app server挂没挂的啊
难道是用doorkeeper吗？
1. 挂了不要紧，只要你的系统能知道你的APP SERVER 挂了，能够马上起一个新的INSTANCE并且failover即可。e.g., AWS ECS检测到你的CONTAINER炸了自动回给你起一个新的并且fail over。 如果你不用container, 也不用ecs类似的服务，你自己需要实现一个有自动failover的玩意
2. app server提供一个/healthcheck的API，这个api要尽可能的低cost， 并且能较准确的反应你的app是真的healthy.
如果你的app server是负责订单处理的，在处理过程中如果server down了，订单就处于inconsistent的情况
解决方案是在处理完每一个step后，把当前的state存储的storage
server重启后可以进行恢复
https://www.jyt0532.com/2017/03/27/system-design/
https://www.jyt0532.com/2018/09/23/cache-mechanism/
=系統設計救星! 一天內手把手教你面試System design
美国CS软件求职精华汇总：简历、刷题、系统设计、面试、内推、谈工资
很多人求职会遇到system design的问题，尤其是有工作经验的人跳槽，必考。
Staycrazy点评的很到位
twosumii在ta的求职总结《说说FLAG的面试经验》里推荐了educative.io的课程：
详细情况戳这里》》》Grokking the System Design Interview 注：这家的team discount是给企业用户集体报名。
有一位谷歌招聘委员会成员（大鲲老师），也在一亩三分地开课讲系统设计。这门课举了面试题目作为例子，但是内容并非完全针对面试，而是大鲲老师在谷歌做系统设计心得的分享。课程信息：
www.1point3acres.com/system-design-courses
此外，地里还有一些很好的总结：http://www.1point3acres.com/bbs/thread-208829-1-1.html
http://www.1point3acres.com/bbs/thread-210083-1-1.html
http://www.1point3acres.com/bbs/thread-184542-1-1.html
地里系统设计精华总结
算法
API Client Design & Coding
Requirements & Data Modeling
https://github.com/FreemanZhang/system-design
https://www.mitbbs.com/article_t/JobHunting/32777529.html
这里说的System Design和OO Design不同 System Design在FLAG以及很多大公司中主要
是design scalable distributed systems 这里只讨论如何准备这种题目
== 入门 ==
对于0基础的同学们 下面的资料可以按顺序开始看
1. http://www.hiredintech.com/app#system-design
这是一个专门准备面试的网站 你只用关心system design部分 有很多的link后面会重
复提到 建议看完至少一遍
2. https://www.youtube.com/watch?v=-W9F__D3oY4
非常非常好的入门资料 建议看3遍以上！
这是1里面提到的资料 是Harvard web app课的最后一节 讲scalability 里面会讲到很
多基础概念比如Vertical scaling, Horizontal scaling, Caching, Load balancing,
Database replication, Database partitioning 还会提到很多基本思想比如avoid
single point of failure
再强调一遍 非常好的资料！
3. http://www.lecloud.net/post/7295452622/scalability-for-dummies-part-1-clones
1里面提到的 Scalability for Dummies 还算不错 可以看一遍 知道基本思想
结束语：当你结束这一部分的学习的时候 你已经比50%的candidate知道的多了(因为很
多人都不准备 或者不知道怎么准备system design) 恭喜:)
== 进阶 ==
这一部分的资料更加零散 每个看的可能不一样 但是你每多看一篇文章或者一个视频
你就比别人强一点
这部分你会遇到很多新名词 我的建议是每当你遇到一个不懂的概念时 多google一下
看看这个概念或者技术是什么意思 优点和缺点各是什么 什么时候用 这些你都知道以
后 你就可以把他运用到面试中 让面试官刮目相看了
4. http://highscalability.com/blog/2009/8/6/an-unorthodox-approach-to-database-design-the-coming-of-the.html
Database Sharding是一个很重要的概念 建议看一看
5. http://highscalability.com/all-time-favorites/
这个里面会讲到很多非常流行的网站架构是如何实现的 比如Twitter, Youtube,
Pinterest, Google等等 我的建议是看5-6个 然后你应该已经建立起了一些基本的意识
还有知道了某些技术和产品的作用和mapping 比如说到cache你会想到memcached和
Redis 说到
load balancer你会想到 Amazon ELB, F5一类的
6. http://www.infoq.com/
5里面很多的文章都会有链接 其中有很多会指向这个网站 这里面有很多的tech talk
很不错 可以看看
7. https://www.facebook.com/Engineering/notes
Facebook非常好的技术日志 会讲很多facebook的feature怎么实现的 比如facebook
message:https://www.facebook.com/notes/facebook-engineering/the-underlying-
technology-of-messages/454991608919 建议看看 尤其是准备面facebook的同学
这有一个facebook talk讲storage的https://www.youtube.com/watch?v=5RfFhMwRAic
8. 一些国内网站上的资料
http://blog.csdn.net/sigh1988/article/details/9790337
http://blog.csdn.net/v_july_v/article/details/6279498
9. 最后一些概念很有用 都是我再看这些资料的时候发现的 如果你没有遇到或者查过
建议查查
Distributed Hash Table
Eventual Consistency vs Strong Consistency
Read Heavy vs Write Heavy
Consistent Hashing
Sticky Sessions
Structured Data(uses DynamoDB) vs Unstructured Data(uses S3)http://smartdatacollective.com/michelenemschoff/206391/quick-guide-structured-and-unstructured-data http://stackoverflow.com/questions/18678315/amazon-s3-or-dynamodb
10 给有兴趣深入研究的人看的
Mining Massive Datasets --讲很多big data和data mining的东西
Big Data: Principles and best practices of scalable realtime data systems(http://www.amazon.com/gp/product/1617290343) --
twitter的前员工讲述如何处理实时数据 目前市面上讲解big data最好的一本书
10 凌乱的资料 随便看看吧
http://highscalability.com/blog/2013/10/28/design-decisions-for-scaling-your-high-traffic-feeds.html
== 小结＝＝
看多了以后 你的最终目标应该是心里有了一个大框架 一个基本的distributed system
是怎么搭起来的 然后心里有很多if condition 如果要是满足这个条件 我应该用什么
技术 比如如果read heavy那么用cache会提升performance之类的 同时知道应该避免什
么东西 比如避免single point of failure 再比如时间和空间的tradeoff在read
heavy的时候应该倾向于时间 Write heavy的时候倾向于空间等等
你总结出来的和我总结出来的大框架和if conditions肯定不完全一样 但因为system
design本来就是一个open ended question 所以不用害怕 能够自圆其说 就不会有问题
最后 本文纯属抛砖引玉 如果有大牛发现有错误或者有补充 欢迎留言 大家一起讨论
== FAQ ==
1. New Grad需要看System Design么?
答案是it depends. 有的公司会考system design 有的公司只考到OO design 有的公司
压根不考 当然 考到的公司对new grad的期望值会稍微低一点 但是 你有这么一个机会
能让你gain leverage over other candidates why not? 为什么要让自己在面试前害怕
面试官出system design的题目呢?
Design有越来越重要的趋势，如何快速提高，应对面试？
算法大家基本靠刷题可以八九不离十，这也加大了筛选人才的难度。
所以现在Design的题目比重和重要度越来越高。
大家一起来讨论下，有没有/怎样快速提高系统设计的能力，以应对面试需要？
可以看一些design pattern的书比如Design Patterns: Elements of Reusable Object-Oriented Software（我们上课用的这本）
关于系统设计，这个其实很看积累的，system本来就是考功底的地方，如果没时间上一些system的课(os, distributed system什么的），可以抽空去看下这些课的slides
另外读一些现在很成熟系统或者nosql的paper，比如
Google旧三驾马车 BigTable, GFS, MapReduce, Amazon的dynamo DB等等
最后极力推荐去看一下Google码农之神Jeff Dean的一些关于large scale system design的talk，给几个链接
http://static.googleusercontent. ... anford-295-talk.pdf
http://www.cs.cornell.edu/projec ... ynote-ladis2009.pdf
Implement an API to access a bank. Assume it will be a REST API using HTTP, but don’t worry about protocol processing. Simply write the methods corresponding to API endpoints.
Episode 06: (No background music) Intro to Architecture and Systems Design Interviews
http://static.googleusercontent. ... anford-295-talk.pdf
http://www.cs.cornell.edu/projec ... ynote-ladis2009.pdf
https://github.com/checkcheckzz/system-design-interview
收集的Prep for Interview - System Design//OOD 资源
如何设计一个load balancer。要求设计一个基于hashing的load balancer, 要求在改变hash 函数时同一个connection里不能有out of order 的message
据我所知，这种场合下常见的hash方案有两种：1. Consistent Hashing （所谓的“一致性哈希”）, 2. Rendezvous Hashing（这个我不知道怎么翻译，“交汇哈希”？）。
比如，前者的大概意思是
1. 把传统的长度可变的线性哈希空间变为一个环形的，周长==1的圆环；
2. 将“请求i”通过某个hashCode()映射到这个圆环Pi位置上；
3. 将“第j台server本身”映射到这个圆环上的k个不同位置：Sj1,Sj2...Sjk
4. 每个请求i都放入“从Pi开始，沿圆环顺时针前进遇到的第一个S所对应的Server上”。
这样，如果server j下线，则仅需将它上面的每个请求顺时针转移到下一台server上即可。由于Pi和所有的Sjk都应当是均匀分布，那么可以期望Pi上的元素会被均匀分散到另外若干台server上。
重映射以后，每台Server再把新分配来的数据和已有的数据进行一次merge操作应该就可以了。
“设计一个load balancer，将外界的请求尽量均匀地分配到N台server上。要求
1：load balancer的分配方式是通过hash运算实现的；
2：当server数目有调整时，要在server之间移动待处理请求，以使各server负载重新保持均衡。
3：每一个server内待处理的请求应总是按到达时间排序。如发生负载调整，那么调整后各server内的请求依然应保持按时间排序。
如何设计一个系统schedule meeting
微软online screen: Design API for email service怎么做？j
用熟悉的语言写一个email的api 服务。写出实现的场景以及需要用到哪些参数
系统设计题的总结！！！不信自己今年找不到工作之系列！！！
以后大家有课程project没思路，可以去实现tiny shortener哈。面试时又可以扯蛋，又可以当作课程project，一举多得哈
定义：http://en.wikipedia.org/wiki/URL_shortening 看了定义，感觉就是要设计短URL，就是长URL 关联 uniqie key , 这些key 可通过 hash 函数和随机数产生器等产生
这篇文章介绍了我们自己如何实现一个url shortener（http://www.sitepoint.com/building-your-own-url-shortener/）。该文章实现tiny url用的是php。短url一般也就是数字和大小写字母组合在一起。比如1位有62种可能性，那么2位可以组合成62*62可能性，3位有62*62*62，4位即有14776336种 combinations了。可以想象当由10位组合成tiny url， tiny url可以有多少！ 这篇文章介绍了如何设计数据库，如何创建url short code, 如何decode short code, 以及最后的如何拼接起来。
首先说数据结构。
数据结构 和数据库表可以相关的结构。
class event {
DateTime startDateTime;
DateTime endDateTime;
EventType eventType;
NotificationType notifycationType;
User creater;
List<User> viewers;
List<User> participants;
//use design pattern observer pattern
//notify all participants (subscriber)
public void notify(){
}
}
数据结构 和数据库表可以相关的结构。
class event {
DateTime startDateTime;
DateTime endDateTime;
EventType eventType;
NotificationType notifycationType;
User creater;
List<User> viewers;
List<User> participants;
//use design pattern observer pattern
//notify all participants (subscriber)
public void notify(){
}
}
| 大规模处理肯定要分布式机器 可以根據event id作hash来distribute evnets to different hosts. 可以聊聊consitent hashing |
| invoke event.的话 基本思想还是一个大while loop.然後用很细的time slice循环，evnets時間点达到后，create new thread, trigger event.然後作该作的工作，比如发邮件，push message等。 多线程方面要注意 pop event和加event的时候要保証线程安全性 |
| design google calendar . 要求分析如何存 data, 如何 invoke user events, 如何 handle 100000events per second, 然后要写了一部分 thread safe 的 code 实现如何 invoke event. |
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=207403
这道题目是linkedin onsite的面经
设计一个上吊游戏的web应用，大家可以玩一下先：http://www.hangman.no/
需求变化：1. 用户游戏赢钱，输钱；2. 用户增加到5M+
网上没有找到很好的答案
requirement:
Analysis: bandwidth, storage,
Design: DB system, High level system design
enhance: cache system, load balancer, db cluster, application server, proxy server, message server, file server.
基本就是按这个套路设计
https://github.com/FreemanZhang/system-designAnalysis: bandwidth, storage,
Design: DB system, High level system design
enhance: cache system, load balancer, db cluster, application server, proxy server, message server, file server.
基本就是按这个套路设计
https://www.hiredintech.com/courses
设计狗家日历
System design: 虽然某些system design我已经看完一遍，部分看了两遍。但是感觉理解不够深入。所以决定每天深入一道设计题。记录并想明白各个feature和tradeoff.
当然最重要的还是需要不断总结和深入思考，不能只追求数量。
地图上分割成不同区域这个设计题的核心是什么来着？
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=301057
记得有个什么算法为核心，就是分割成一块一块，然后有不同情况下的优化，
但是想不起来具体是什么来了。还看过一篇中文的文章讲得不错，可惜记不清细节了
| GeoHash算法，地理编码 |
在职刷题 + System Design + 面试准备的路上
1 着重在thinking process，不要想45分钟给一个完美的解决方案
2 条理要清晰，有big picture，有data modeling，有data flow
3 多从customer角度来考虑，用户要什么知道了，你才好决定你的设计中的取舍
4 不要一开始就挖大坑，从MVP开始，最后时间足够才加新的feature
5 从最开始简单的架构开始迭代，分析负载上去了之后的bottle neck在哪儿，你要怎么优化。这时候再带入一点customer最关心的是哪里，可以做哪些tradeoff。你做这个技术选型的原因是什么，因为技术mature还是没有spof6 最后一定要review一下系统的scalability，负载x10的话，你的架构是不是线性的加资源进去就好了？
7 架构确定好了之后，最好来个预估要达到这个性能指标，我们需要多少机器以及怎么部署
8 别忘了提一嘴logging monitoring
9 扯一扯service oriented architecture也是极好的
10 把qconf 2012里scaling Pinterest from 0 to billions看几遍，我看了那么多资料里面，最有启发的一篇
总的来说，我不太建议一上去就摆一个高大上的架构，从小到大循序渐进的来，你就可以展现你更多的能力，不光有breadth还有depth。系统设计都是相通的，碰到没见过没准备的不要蒙蔽，毕竟要考察的是思维过程，不是要求你设计一个完美解决方案。
基本就是看完一个设计的视频，就跟着逻辑白板走一遍全过程，然后有遗漏的地方再过一遍
System Design: 白板走了一遍Tiny URL, 并过了一遍输入url,浏览器端会发生什么的整个过程，URL->DNS resolution (IP lookup from browser, OS , router, DNS cache first, DNS query later form Domain) -> Server with TCP connection-> HTTP request -> Waiting for response -> server send request to application -> code execution and DB query -> response -> transferring data -> CDN (css, js, image, video ) -> browser presenting
System Design: Design Logging System, 这题感觉更像是OOD, 使用Observer Pattern Design或者Aspect Oriented Programming的方式去做logging
System Design: Design Typehead
此题的场景是搜索框，每输入一个单词，就会给出top k的单词推荐，这些推荐是根据用户对这些单词的点击率，需要使用Trie来解决。所以我们需要两个service，一个是DataCollectionService和QueryService, DataCollectionService会定时从Log DB中统计每个词的点击次数，然后offline跟新QueryService中Trie, 为了保证速度，Trie存入In memory中，但是为了不会是Trie丢失，还需要在disk中存一份Serialized trie.
当Trie过大无法存入一个In memory的Cache中时，我们需要多台机器，以每个prefix做consistent hashing的key来存入不同的机器中而不是以每个单词的首字母来把所有prefix存入,这样还是存在一个机器存不下，而使得同一个prefix的所有top word存入不同机器中。
另一个优化是，在浏览器端使用cache,一个是cache已经输入过的prefix，当重复删去和添加相同的prefix时可以避免request from server,
还有一个优化是每输入一个prefix，就多加一个单词在前端存储下一个prefix的前1000个word.
今天主要在看design, 看了两个design，一个是Design Google sheet, 一个是Design messager.
Design Google sheet 的主要问题是用什么数据结构来存储ceil, 并进行增删改查的操作，并且需要用判断有向图是否带环(BFS or DFS)的算法来判断是否有circular dependency。
另外多人同时操作，使用的原理是Latency compensation是先写在page上，并predict这是最终显示结果，同时server端会去sync，是否有其他人也在修改，如果有的话则需要重新根据时间顺序来覆盖操作，如果无人修改则保留原有记录。server sync的原理是一个线程锁住log，并把此次的event加入log中，然后释放log. 保证所有thread读到的都是最新的log
Design messager 的主要feature就是发信息,群聊和在线状态检查。发消息的主要问题是如何使用合理的db存储和如何即时通信，存储DB要设计好合理的table,比如message和thread table, 而通信可以分为两个service,一个message service，一个push service.
message service负责接收user的message，存储进db，并发送给push service，push service负责与user进行socket连接并发送message.
群聊需要在message 和push service中间加入channel service，这样channel service负责接收一次message service的message，然后发送给subscribe在channel service上的active user. message serveice 会帮忙subscribe，而push service会知道用户是否在线，下线的时候remove user from channel. 查在线状态通过user每4秒pull一次state of friends and tell server itself is alive. 这个方式和uber司机不断的告诉server自己的位置一样，也是heartbeat的方式来告知server是否在线
Uber 相关技术栈以及One click system的架构，workflow：sender ->send the message to Gateway -> messaging platform -> persisted in DB(Cassandra) -> local push service and remote push service -> send the message to Receiver -> respond message received to messaging platform. AI架构相关： sender -> Backend service -> ML platform (message to intent detection(simply the message) -> reply retrieval(provide response)) -> Top k suggested replies -> Receiver
目前就是对经典topic一个一个啃，然后白板画一遍全部流程，从scenario开始分析用户量,QPS多少和存储量多大，这个能决定之后会用到什么样的DB和优化方案。然后分析主要有哪些feature需要在MVP阶段实现,以及需要哪些service来构成microservice架构，每个service都作为一个独立的server再配备相应的DB,根据需求和之前对scenario的分析来决定用NoSql还是SQL。然后设计出DB schema, 画出完整workflow, 形成完整的work solution. 后续会参考多方资料来深挖多种solution以及其他细节作为follow up即为scale部分做准备。
How to design User System
接着上次的Friendship Service, 这个service最主要难点是如何存储friendship的数据，如果使用SQL, 可以把好友关系只存取一份，但是查询的时候需要查询两次，因为不确定哪一边是target id. 方法二是把好友关系存两份，查询只需一次。 如果使用NoSql,比如Cassandra, row key为user id, column key 为friend id. 在此我们分析一下数据库的优化: 对于Sql,我们可以使用index来加速查询操作,之所以速度提升是因为从以前的全表搜索变成了字段值单独提出来建立二叉树搜索。但是缺点是建立索引也需要占用空间,索引不能过多,否则在数据添加更新删除的时候会消耗更多时间,因为需要找到特定的位置以及保证有序，而不是像以前那样直接做修改。NoSql很容易horizontally scale, 通过对row key的consistent hashing即很容易实现sharding. 而Sql更容易实现vertical sharding. 对于选择NoSql还是Sql,主要取决几个方面: 1. 如果是有transaction,推荐使用Sql 2.如果data is structured and unchanging,推荐使用Sql. 3.如果想要repid development,意味着data structure经常变动,使用NoSql. 4.如果想要节省服务器资源而提高性能,选择NoSql, 也更容易scale across multiple data center
复习News Feed 以及 看OOD设计 how to design Elevator, 主要用到strategy design pattern
今天主要看了Uber tech blog, 讲了整体业务和架构方面的东西，把以前零碎掌握的东西顺了一遍。另外看了一些工作中要用到的一些前端的知识
看了另一个将messaging system的视频，有了新的角度，就是用redis来存用户最后的heartbeat的时间，用此来判断用户online还是offline
今天快速过了一下《Professional JavaScript for Web Developers 3rd Edition》的一些章节，为了工作上的项目实现树状结构的sequence创建存储进DB，并从DB拿出数据还原成树状结构，有点像Serialize and Deserialize Binary Tree，但是要实现比较美观的效果以及sequence的有序性，并保证按照sequence去执行任务，数据库的设计上还有些问题没想通，后端程序员还得搞前端，只能恶补js了
把How to design Twitter, Uber, Rate limiter, Typeahead, Tiny URL, Messaging System 全部白板过了一遍。
今天的bar raiser面试跟面试官聊嗨了，给了我很多接下来面试的tips，还说他一般面technical design的话会出how to design Netflix...哈哈 所以找时间我也来补一下这个吧
系统设计,建议基本还是和自己工作的内容相关的设计才比较有用,因为一般的书讲的都是一些general design的,简单的理解就是讲通用架构上的东西,各个子系统之间如何隔离等等,
但是和自己业务相关的系统设计才是最值得去研究的,因为哪里有坑,哪里会有设计缺陷,这些都是一次次的跳坑和填坑才总结出来的,比如哪里可能会有高并发,cache如何处理等等,这些一般书里讲不深,也讲不明白,毕竟每个系统都不一样,业务模型也不一样,所以多看看现在的公司的架构设计和系统设计才是硬道理.
刷题这个基本是保持一个手感的问题,看到题目知道他分到哪个大类里面(字符串处理,DP,搜索,数据结构,图论等),知道这个基本面试的时候不会慌就OK
如果说真正提升技术我基本赞成你的观点，只是想补充一点：并不是每个人的工作中都能接触到有高并发或者scale的情况，大部分时候还是在做很基本的CRUD,API等。所以只能靠外部资源来扩充这方面的知识。当然对自己工作中的业务熟悉和了解那是必备的，否则很多behavior就挂了
面了一圈下来感觉刷题才是王道，算法每次面的各不相同，而System Design大都是一样的套路。所以决定接下来的一个月，以刷题为主，Sysytem Design 则以grokking system design 偶尔进行复习。
今天design discussion提出了很多有价值的问题，感觉这段时间的面试准备对自己工作能力上的提升也是肉眼可见的，虽然还没拿到offer但是依旧很开心，继续坚持吧
How to design Netflix/Youtube.
主要feature有 upload video, view video, share/like/dislike video, subscribe channel, 通过video title 来搜索video, 评论和浏览评论。
主要流程为 User -> upload video -> processing queue -> Encoder -> encode into multiple formats and generate thumbnail to file storage -> store video metadata and user data.
主要存储结构为: file storage system for video and Bigtable for thumbnail, SQL DB for user(id, name, email, age, address) and video metadata (id, title, description, size, uploader, thumbnail, total number of like, total number of dislike, total number of views).
Scale and Optimize: video deduplication 为了节省资源, 把上传的重复的视频只存取一份， 如果上传的视频是其中的一部分或者延展更多的部分，则把missing的部分切成更小的chunk存储。对于popular video可以用cache来加速读取，充分利用好CDN,把视频资源放在更靠近user的地方
今天看了How to design twitter search, 即对每条twitter使用inverted index来进行关键字搜索，grokking system design 感觉更偏重于index建立所需要耗费的storage大小的计算上，对于搜索和ranking部分介绍不多，以后有时间再把search这块的design补一下
复习了一下数据库的index原理，主要利弊就是：increase read performance and decrease the write performance.
Designing Pastebin
主要功能有保存一段文本并生成一个unique URL 读取。类似于TinyURL功能，多了一个文本生成和保存。content可以使用object storage like Amazon‘s S3保存。其他信息比如Paste 和 User信息用SQL存储. Paste包含URL, ContentKey, UserId, CreationData, Expiration. URL的生成可以通过Key Generation Service. Generate random six letters strings beforehand and store them in DB. 可以 keep some keys in memory whenever a server needs them. 牢记80-20 rule, 20%的URL会产生80%的traffic。所以需要Cache这20%的paste.并可以此计算需要的space大小
Design Instagram
本来以为Instagram会有什么不一样的Design，发现Grokking上讲的就是Design Twitter的略简单版本。主要功能有upload/download/view image/video, Newsfeed/Timeline, follow and unfollow friends. 首先是分析DAU，QPS. 然后是分析存储这些image/video需要多少空间，存储1年需要多少.
然后存储就可以使用file system like S3. 而Friendship 和 User, Photo 的metadata需要使用Sql存储. 然后是News feed 的两个mode，pull and push, 最佳策略是hybrid两个，对于所有人使用push，对于hot users with lots of followings 使用pull.
对于Scalability这块，我们需要根据photo id 来做metadata的sharding，原因是如果对于userID做sharding，会导致几个问题，一是对于hot users和一些拥有大量image/video的用户，通过userID来做partitioning可能一个shard并不能存储该user的全部信息，反而会影响性能。
还有一个问题是把一个user的所有信息都放在一个shard的话，如果这个shard down了，那么他的所有信息都会unavailability。
如果这个用户是hot users那么也可能产生high latency if it's serving high load. 对于photo的ID我们可以使用Key generation service提前生成，为了避免single point failure，我们可以使用两个DB，一个放odd incrementing number一个放even incrementing number. 每个photo只需要去take一个id即可，保证了the sequence of auto incrementing ID. Then use load balancer to deal with downtime. 对于实现快速获取最新的photo，可以使用photo ID用epoch time + incrementing number. 这样的好处是能够加速数据库的查找操作，因为我们肯定会index photoID
Design Dropbox
这个设计相关的知识点对我来说比较新，所以看完一遍能掌握的部分并不多。先来第一遍吧，主要的功能有upload/download files, share files/folders with other users, support automatic synchronization between devices, support offline editing.
Files 存储在file system中，Metadata of Chunks, files, User, Devices, workspace(folders)存储在SQL中。对于files的同步操作，比如update的主要的workflow为用户A上传chunks, 更新metadata并commit changes，
A得到confirmation，并发送notification给B、C, BC接收到metadata changes并download updated chunks. 对于ABC同时更改同一个file，需要把他们更改的操作按时间顺序放入同一个request message queue中依次处理。然后分别创建response message queue给每一个client来响应。对于文件的上传，是把一整个file分为多个chunk来上传，为了节省空间避免duplicate，我们可以在上传前去hash chunks and lookup.如果发现已经含有，则only add the reference rather than the full copy
系统设计：
twitter design， whatsapp design， LRU design. Hash & consistency hash.
OOD:
设计停车场。
然后楼主刚刚上岸了，还有两个其他的面试，应该会在一周内面完。之后应该就短暂不更新了。哈哈哈。
接下来几天会写的题：
youtube设计。
Uber设计。
Expedia设计
twitter设计。
功能概述：
tweet，
timeline（home timeline, user timeline, search timeline）,
Trends （#）
数字：
300 M users
Write: 600 tweets / sec
Read: 600000 tweets/ sec
Conclusion：
Read heavy
eventual consistency(timeline 上的delay 被允许)
How to scale storage and read for users?
Redis: 使速度更快。
DB: copy data.
db:
user table| tweet table | followers table
redis:
key: user id value: tweets | followers
homeline construction：
fan out
今天做了一道expedia onsite的原题。最近在准备expedia家的final round。
题目是餐厅预订系统。我仔细想了想应该是不需要对餐厅进行组成规划的。（因为预定系统实际上并没有用到具体的餐桌 / 厨师 / 厨房设施）。
从算法角度，还可以依次检查餐桌是否可行，这样可以增加一个新的对象餐桌，从而实现每个成功的订单都有对应的桌号。也算另一种做法了。
OOD:餐厅预订系统
对象： 餐厅（不包括厨房）， 订单， 用户。
餐厅：
logic:
default： 只考虑餐桌，不考虑服务人员。
association：订单。用户。
功能： 接受订单， 根据当前点，对应人数和高峰餐厅占有，判断是否可接受，dispatch给餐桌，并反馈给用户。
取消订单，回收餐桌。notify观察者模式(提醒用户可再次发送订单)。
（synchronized）
订单：
logic：枚举状态，并将餐厅对订单的回应反馈给用户。
用户：
logic：发送订单请求。根据反馈将订单添加到失败队列或者成功队列。
当接收到餐厅的订单取消时。重新发送处在失败队列中的订单
系统设计如何准备？
- 看grokking http://www.1point3acres.com/bbs/thread-404097-1-1.html
- 看youtube
- 做
- 讨论。和刷题不同，系统设计没有标准答案没有完全的对错只有tradeoff。所以讨论是为数不多的练习途径。
最后达到“都是套路”的状态。
关于系统设计的一个忠告
题是一道经典的关于search engine设计。不过，哪道题并不重要。重要的是我要跟大家讲一下的策略问题。
千万，绝对，一定不要太早地涉及到数据结构或者任何一部分你认为复杂的部分，我的意思是尽量不要提。
到你要提的时候，你要有一直讨论到结束的觉悟。
不要觉得能一笔带过就把它提出来，想着以后再优化。因为，你是在卖，破，绽。
我就着了道。。。
面试的人是南亚你懂的国人。一开始看到题目，心里打了顿，擦，没有仔细写过这题啊。不过不怕，原理还是知道的，咱还有套路。
然后就开始做各种估算，然后又随手画了几个框框表示了一下，不过画得很不精细。想着还能回头来细化。
然后我就开始作死，要不我们先看一下该怎么存index数据，看一下容量，再回头来优化内存的存储吧。然后，就开始一条不归路。
当我写下一第一个数据结构，准备估算的时候。面试的那位就打住了我，说，你这个数据结构不是最优的，速度可能不够。然后就开始讨论起数据结构。
我以为只是他比较重视数据结构。然后开始讨论。搜索引擎实在不是很熟悉的东西，做得磕磕绊绊，不过他一直要求讨论这个，我也就只好跟着一起讨论。每次我想跳到下一步，他就说我们再看一下数据结构。
花了一些时间讨论出了一个大家都接受数据结构。然后心想，终于能往下走了。
这个时候，他突然跟我，还剩五分钟，你问问题吧。这时候，我大吃一惊。时间过的这么快。然后就匆匆忙忙的算了一下内存容量，说装不下，要不只装最hot的（还要分片，我知道，太紧张没说出来，不过不要紧，因为他已经没在听我说话）。最后我想，也差不多了吧。就说，就这样吧。问问题吧。这时他说还有三分钟。问问题这地方也可以说道说道，我感觉问问题的时间绝对不止3分钟，因为我问完一个问题，他说，还有时间你还要不要问。我又问了一个。
最后高潮来了，他就站起来准备走的时候说，虽然你没有给出一解决办法，但是我知道你懂的东西了。EXO me？！没有解决办法？我们讨论了半天的数据结构难道不是一个解决办法吗？
至此，一套组合拳打完。LZ直接GG。。。
看着满黑板的数字和几个孤零零的框框。我觉得我准备的心血，都喂了狗了。什么互相交流，什么螺旋式讨论，什么先粗后细，全是狗屁。我见识少，玩不过你。
最后再说几句。我一路面过来其实已经用自己亲身经历打破了很多关于面试的迷思，什么一轮要做几道，做不到就挂了。要bug free，有个bug就挂了。都不是一定的。最重要是要把问题说明白了。
说明白了，就算少做那么一道题，有那么一个两个小bug，其实是不影响的。毕竟对面的是个人，不是一台机器。不过人心难测，因为面试外因（对面那个）是不可控的，那归结内因（自己）就是最自然的想法了。
还有一句话，世界很小的，今天对面虐你的，明天可能就来被你虐。都很难说，最重要是记住他的名字。哈哈哈哈
我那么悲伤的过程，你居然只关心我的数据结构。。。
就是trie，index搞来搞去。。
我觉得楼主肯定是回答了inverted index了。我猜楼主是要用trie来存words，每个word有自己的index表。就是trie，index搞来搞去。。
多谢楼主的建议，确实应该先把大框架说完，再根据面试官的问题来优化某个部分。
这是被黑了吧，三哥看到个破绽直接搞了你。
https://www.hiredintech.com/classrooms/system-design/lesson/52
从中还看到一个建议，用一个网站找人做Mock interview，有意思的是这个不是单向的，同一个session里角色会互换，你也要作为面试官面对方。不知道有没有人用过
从中还看到一个建议，用一个网站找人做Mock interview，有意思的是这个不是单向的，同一个session里角色会互换，你也要作为面试官面对方。不知道有没有人用过
一天一道系统设计/OOD
系统设计跟算法对ratelimiter的要求不一样吧。算法是你找到一种数据结构及相应的算法去解决问题。系统设计是分析可能的feature，服务及数据库存储，然后在已经实现的基础上如何scale。
具体实现上可以考虑用cache server(比如memcached 或redis),设置ttl,然后算出在ttl内的访问次数是否超过plannex。如果，超过了，则返回4xx
个人觉得，算法侧重于你自己完全实现基础的东西。而系统设计侧重于采用工业界以后的东西去实现你的需求，进而实现整个系统的 开发
具体实现上可以考虑用cache server(比如memcached 或redis),设置ttl,然后算出在ttl内的访问次数是否超过plannex。如果，超过了，则返回4xx
个人觉得，算法侧重于你自己完全实现基础的东西。而系统设计侧重于采用工业界以后的东西去实现你的需求，进而实现整个系统的 开发
我和他聊崩主要原因是，我当时完全被算法硬思路困扰了。
我当时就是用的一个queue， 然后检查queue中最老的，pop出去。按照我的思路，这个复杂度完全应该是O（1）啊因为单位个体每个push一下，pop一下。但是他觉得就是O（n）。
后来我仔细仔细想了一下确实应该是O（n）,因为实际上对单位次呼叫的worst case实际上就是queue中所有的个体。
我查了一些资料后来，这个题思路应该是：
queue -> 按时间分区间统计个数的queue（这样就能控制复杂度为O（1）了）-> token bucket。
更深的还要谈如果数据量上涨，就要用sticky session来控制服务器分配云云。不过那里太陌生我已经记不太清了
关于 nosql , bigdata 系统设计相关的学习材料
Datastax 关于Cassandra 有不少很不错的课程。 Cassandra 是和Bigtable， Dynamo compete 的NOSQL 系统。 上面D201 D210 and D220 对 big data , nosql, CAP therom 有详尽的讲解。 GitHub 还有相关的demo training app Killrvideo. 可以作为学习Bigtable ，YouTube 相关系统设计的很好材料 https://academy.datastax.com https://github.com/KillrVideo |
1. 如果用MySQL 一般用master slave 来scale, 读在slave上，写在master上，写就成为bottleneck, 如果面试要求读写都快怎么办？ 是否可以用nosql 做sharding 这样写就快，读用cache? 还有sql nosql到底怎么选择
2. 我知道cache非常有用，比如说你的timeline，好友关系，都可以放cache里，因为经常用到，但是比如说 个人信息，profile, 用户名密码之类的，是放在cache里吗？还是实际要用的时候再从数据库里读？
3. sharding 到底怎么用，我理解sharding, load balancee 可以根据用户的某些特性引导你到某台server，某个数据库上，但是总是免不了要从别的数据库里取数据，这样就会慢一些，这时候怎么办？
2. 我知道cache非常有用，比如说你的timeline，好友关系，都可以放cache里，因为经常用到，但是比如说 个人信息，profile, 用户名密码之类的，是放在cache里吗？还是实际要用的时候再从数据库里读？
3. sharding 到底怎么用，我理解sharding, load balancee 可以根据用户的某些特性引导你到某台server，某个数据库上，但是总是免不了要从别的数据库里取数据，这样就会慢一些，这时候怎么办？
我看了一些系统设计的例子，比如说，设计一个推荐系统，这种题就让我很为难。
你看，如果是让设计一个twitter, 那很清楚，用户可以发推，follow, 更新timeline 啥的，这种推荐系统，我知道可以根据用户的search 记录，最近购买的东西，他常购买的东西，品牌，地理位置等，这些我都知道，都可以拿来作为推荐的因素。但是这个系统的输入是啥?
twitter的输入就是用户发个推，那推荐系统的输入就是用户浏览/搜索你的网站？然后你后台跑个服务把你的行为都记录下来?
| 推荐系统的输入就是你说的历史行为吧。 单纯说设计推荐系统太模糊了，感觉可以跟面试官要 clarification，比如具体化成购物网站的推荐系统，那么输入就是购买记录、搜索记录之类的。感觉这种面试不一定需要懂推荐算法，可以把简单的 Item-based 和 User-based 协同过滤讲一讲，再扯一扯计算任务设计、API 设计，扯一扯冷启动之类的具体问题，应该就够了吧 |
https://github.com/donnemartin/system-design-primer
一般的app server也需要replication吗？
1. app server挂了怎么办？我答，没关系啊，挂了就挂了呗，反正有多个app server -_-
我只知道db server挂了需要backup replication激活，app server挂了也需要这样子吗？为了抢救app server的cache？但现在都强调api 应该stateless啊
2. loader balancer怎么知道app server挂了？我也不太懂，之前我做过一个小系统，我记得loader balancer自己会测app server挂没挂的啊
难道是用doorkeeper吗？
1. app server挂了怎么办？
从load balancer的路由配置里面把挂了的节点去掉，不然这个坏了的节点还是会收到请求（然后因为不能做出回应，导致用户看到你的服务一会儿正常一会儿500/502）。然后启动新节点，注册路由，新节点接受传入请求并工作。
2. loader balancer怎么知道app server挂了？
一个是zookeeper等等工具自己会测心跳（heartbeat）。自己实现的话，app server加一个ping的function（无论你是用HTTP RESTful还是GraphQL），然后在load balancer上面定时访问它。
| 在微软, 运行在Azure cloud services的instances都应该会被要求运行一个monitoring的background job,这个job的任务就是定期向log中心发送heartbeat data, 然后又会有另外一个azure的检测service(watson)去读取该subscription下面所有instances的health的数据去判断哪些instance挂了，所以LB(ACIS service)能够从那个watson得知把traffic从挂掉的region（比如EUS）redirect到healthy的region（比如CUS）。等挂掉的region修复了，就可以重新distribute traffic了。这种failover的前提都是request 得是 stateless的 |
| 我觉得核心在于： 1. 还有很好的healthcheck API 2. 要恰当的考虑stateless， 尽量使用cache而不是stateful data 可能还要考虑log for debug。。。 实际场景中， api server 可以register to load balance， 让elb来ping。 之前实际工作中的app server挂了的实际场景解决： 如果是stateless 1. 如果是aws之类的vm， 是可以通过auto scaling group 根据预先定义的health check来自动launch新的instane的 2. 如果是container based， k8s自己回launch起pod 如果是stateful： vm很麻烦， 如果尝试去本机restart 如果是k8s， 要走statefulset， 会自动 mount之前的pv |
1. 挂了不要紧，只要你的系统能知道你的APP SERVER 挂了，能够马上起一个新的INSTANCE并且failover即可。e.g., AWS ECS检测到你的CONTAINER炸了自动回给你起一个新的并且fail over。 如果你不用container, 也不用ecs类似的服务，你自己需要实现一个有自动failover的玩意
2. app server提供一个/healthcheck的API，这个api要尽可能的低cost， 并且能较准确的反应你的app是真的healthy.
如果你的app server是负责订单处理的，在处理过程中如果server down了，订单就处于inconsistent的情况
解决方案是在处理完每一个step后，把当前的state存储的storage
server重启后可以进行恢复
https://www.jyt0532.com/2018/09/23/cache-mechanism/
=系統設計救星! 一天內手把手教你面試System design
我的所有資料來源都是地裡還有以下連結
這篇文章主要是把所有手上資源照priority順序加上一些自己的整理 用簡單的方式介紹怎麼Ace system design 依照priority順序分成
Step1: 先問所有requirement, spec 這個系統需要提供什麼功能
Step2: Constrains: 問他我們需要處理多少traffic, 多少data, latency重不重要 A和C選哪個
Step3: 計算需要多少機器 要用什麼storage
Step4: Abstract design: 先畫出大架構！ 每個會出現的component都要畫出來 再看面試官希望你深入講哪個component
Step5: Scale: 讓你的system有fault tolerance, scale成大公司的系統架構
迷途書僮: 等等step2的A和C是什麼
jyt0532: CAP的A和C 如果你明天要面試你不知道CAP是什麼 那我的建議是你今天早點休息 明天才有精神 地球是很危險的
迷途書僮: 別這樣啦 我幫你加大米拜託給我一個最簡單最好的解釋
jyt0532: 既然你都這麼說了 今天幸好你遇到我 把這個看完你就通透了http://ksat.me/a-plain-english-introduction-to-cap-theorem/
迷途書僮: 喔原來是這個 那這4個step 你這樣講真的很抽象 可不可以舉個例子 我可以apply到所有system design的題目
jyt0532: 光說不練假把戲 我帶你手把手跑一次system design process
來個基本的 假設現在要design一個hash
Step1, 2: 問requirement
多少資料需要進cache? 30TB
expected QPS? 10M
eviction strategy? LRU
Access pattern? Write back(有空的話Write through, write around, write back都要知道什麼意思 利弊)
Latency重要嗎? cache的用途就是降低latency
C or A: A
Step3:
算一下你需要多大的machine多少台
https://gist.github.com/jboner/2841832 這裡面的數字要有點sense
假設我們現在要用72GB RAM 4 core的machine
那總共以儲存data來說 需要30TB/72GB = 420台
這樣的話每台的QPS = 10M/420 = 23000, 即使所有core都用了 每個core要處理6000QPS
代表說 1/6000 = 167us 搭配上面那個link可知道即使是ram sequentially read 1MB要250M 所以我們如果用這個size的machine 會無法負荷
改變主意 假設現在用16GB RAM 4core的machine
30TB/16GB = 1875台, QPS per CPU = 10M/1875/4 = 1400QPS = 700us per queries. 這個數字負擔小多了
看完上面的流程知道我們在幹嘛了吧? 先用data constrain算出要幾台機器 再用traffic constrain算看看這樣的配置合不合理
這樣做完你就知道你的system是需要猛的機器少台一點 還是差一點的機器多台一點
Step4: 畫出大架構
這時候就必須推薦https://www.youtube.com/watch?v=-W9F__D3oY4 這根本太精采
什麼你又沒時間 好啦別說我虧待你 有人把重點整理好給你了http://ninefu.github.io/blog/Harvard_CS75_Notes/
但最後那個畫圖的地方還是要看一下
Step5: 喇賽時間
這時候小system畫完了 如果要scale的話需要什麼東西 不外乎就是load balancer啦 DB就是可能要master-slave或是multi-master 這種東西
至於怎麼fault tolerance呢 常見的處理就是replication 就是一樣的資料存很多地方 假設有P個replication
因為每次寫和讀都寫進/讀出這P個地方非常花時間 那該怎麼辦呢
假設寫的時候 只要有W個replication confirm update我就return to user
假設讀的時候 只要有R個replication給我一個一樣的value, 我就return這個value給user
depends on design的use case(這就是為什麼use case很重要) 你要看read跟write哪一個operation可以承受高一些的latency
如果要求read很快 write可以慢一點沒關係 那就可以設R = 1, W = P, 反之可以設R = P, W = 1
總之 只要R+W > N 那這database就是strong consistent! 如果真的要求高速度的話就必須犧牲consistent 那R+W就會<P(weak consistent)
=====下禮拜要面system design=====
從小公司到上億用戶公司的架構演進(非常建議讀)
InterviewBit:這是個非常好的互動式網站 他是一步一步漸進式的問你每個你在面試中該問的問題 帶你走過一遍system design interview的process 非常建議這裡面的八題都要寫過
Scalable Web Architecture and Distributed Systems
=====下個月要面=====
把這裡的文章都K過你就比大多數candidate強很多了 除非你想進的事system and data infra那就是另外一段故事了
=====明年面試=====
明年才要面你現在就開始準備的話 基本上你是個非常自律的人 你就定時follow各公司engineer寫的文章就可以了 別忘了面之前一個月再回來看我這篇
其實有工作經驗的都知道 你很常需要去design一個新的project 而釐清use case這些事情是基本 連use case都沒問那面試官根本不會覺得你是個好的工程師 主要考察的是communication and problem solving, 給你一個開放性問題 你怎麼分析step by step, 你如何跟別人討論你的idea, 如何optimize你的system 往這個方向想就覺得其實system design真的沒什麼好怕的 這篇寫了快五個小時 請各位地友不吝賞個大米吧 這篇就不設權限了 希望造福大家 如果大米超過100我再稍微寫一下怎麼design twitter吧
筆誤 example是要打造一個cache不是打造一個hash
https://www.jyt0532.com/2017/03/27/system-design/美国CS软件求职精华汇总：简历、刷题、系统设计、面试、内推、谈工资
很多人求职会遇到system design的问题，尤其是有工作经验的人跳槽，必考。
Staycrazy点评的很到位
twosumii在ta的求职总结《说说FLAG的面试经验》里推荐了educative.io的课程：
bumbing在《马克找工作第二次，万字长文慎入》里也做了推荐 - educative.io的这门课 + DDIA书籍，是地里很多人推荐的。
Grokking the System Design这门课有30节，其中六节免费：
- Load Balancing
- Caching
- Sharding or Data Partitioning
- Long-Polling vs WebSockets vs Server-Sent Events (*New*)
- Designing a URL Shortening service like TinyURL
- Designing Instagram
详细情况戳这里》》》Grokking the System Design Interview 注：这家的team discount是给企业用户集体报名。
有一位谷歌招聘委员会成员（大鲲老师），也在一亩三分地开课讲系统设计。这门课举了面试题目作为例子，但是内容并非完全针对面试，而是大鲲老师在谷歌做系统设计心得的分享。课程信息：
www.1point3acres.com/system-design-courses
此外，地里还有一些很好的总结：http://www.1point3acres.com/bbs/thread-208829-1-1.html
http://www.1point3acres.com/bbs/thread-210083-1-1.html
http://www.1point3acres.com/bbs/thread-184542-1-1.html
地里系统设计精华总结
学machine learning有cmu的10601 和10701 还有couresera 的Andrew Ng，和mit经典的ai课
学算法有leetcode lintcode hackrank
学os有berkeley 和mit的公开课
准备系统设计有那本design data intensive system的神书
database 有berkeley的186
论坛在推荐一个叫grok the interview的在线课程，个人觉得还挺不错的，很多思路可以借鉴，走路的吃饭的时候看几遍，你就发现其实都是套路
然后就是我在工作里看的各种文档，这个你没法借鉴，之后我会抽空专门写个帖子
然后还有就是自己在网上搜索system design，或者youtube有很多tech talk比如infoq的，
然后还有各大公司的tech blog，比如pinterest和uber的都挺不错的
然后我自己还读了3遍 design data intensive application这本书，这本书有助于夯实基础但是周期较长，比较着急面试的就不用看了
然后还有一些关于系统和db的名校的录像课，
然后再想深入学就可以去看paper了
如果你着急面试第一条就够你开始的了。。。
以及各大公司的技术博客和xxxx的系统设计
算法
动态规划
强烈推荐一个博客. From 1point 3acres bbs
希望你能喜欢
API Client Design & Coding
Requirements & Data Modeling
https://github.com/FreemanZhang/system-design
https://www.mitbbs.com/article_t/JobHunting/32777529.html
这里说的System Design和OO Design不同 System Design在FLAG以及很多大公司中主要
是design scalable distributed systems 这里只讨论如何准备这种题目
== 入门 ==
对于0基础的同学们 下面的资料可以按顺序开始看
1. http://www.hiredintech.com/app#system-design
这是一个专门准备面试的网站 你只用关心system design部分 有很多的link后面会重
复提到 建议看完至少一遍
2. https://www.youtube.com/watch?v=-W9F__D3oY4
非常非常好的入门资料 建议看3遍以上！
这是1里面提到的资料 是Harvard web app课的最后一节 讲scalability 里面会讲到很
多基础概念比如Vertical scaling, Horizontal scaling, Caching, Load balancing,
Database replication, Database partitioning 还会提到很多基本思想比如avoid
single point of failure
再强调一遍 非常好的资料！
3. http://www.lecloud.net/post/7295452622/scalability-for-dummies-part-1-clones
1里面提到的 Scalability for Dummies 还算不错 可以看一遍 知道基本思想
结束语：当你结束这一部分的学习的时候 你已经比50%的candidate知道的多了(因为很
多人都不准备 或者不知道怎么准备system design) 恭喜:)
== 进阶 ==
这一部分的资料更加零散 每个看的可能不一样 但是你每多看一篇文章或者一个视频
你就比别人强一点
这部分你会遇到很多新名词 我的建议是每当你遇到一个不懂的概念时 多google一下
看看这个概念或者技术是什么意思 优点和缺点各是什么 什么时候用 这些你都知道以
后 你就可以把他运用到面试中 让面试官刮目相看了
4. http://highscalability.com/blog/2009/8/6/an-unorthodox-approach-to-database-design-the-coming-of-the.html
Database Sharding是一个很重要的概念 建议看一看
5. http://highscalability.com/all-time-favorites/
这个里面会讲到很多非常流行的网站架构是如何实现的 比如Twitter, Youtube,
Pinterest, Google等等 我的建议是看5-6个 然后你应该已经建立起了一些基本的意识
还有知道了某些技术和产品的作用和mapping 比如说到cache你会想到memcached和
Redis 说到
load balancer你会想到 Amazon ELB, F5一类的
6. http://www.infoq.com/
5里面很多的文章都会有链接 其中有很多会指向这个网站 这里面有很多的tech talk
很不错 可以看看
7. https://www.facebook.com/Engineering/notes
Facebook非常好的技术日志 会讲很多facebook的feature怎么实现的 比如facebook
message:https://www.facebook.com/notes/facebook-engineering/the-underlying-
technology-of-messages/454991608919 建议看看 尤其是准备面facebook的同学
这有一个facebook talk讲storage的https://www.youtube.com/watch?v=5RfFhMwRAic
8. 一些国内网站上的资料
http://blog.csdn.net/sigh1988/article/details/9790337
http://blog.csdn.net/v_july_v/article/details/6279498
9. 最后一些概念很有用 都是我再看这些资料的时候发现的 如果你没有遇到或者查过
建议查查
Distributed Hash Table
Eventual Consistency vs Strong Consistency
Read Heavy vs Write Heavy
Consistent Hashing
Sticky Sessions
Structured Data(uses DynamoDB) vs Unstructured Data(uses S3)http://smartdatacollective.com/michelenemschoff/206391/quick-guide-structured-and-unstructured-data http://stackoverflow.com/questions/18678315/amazon-s3-or-dynamodb
10 给有兴趣深入研究的人看的
Mining Massive Datasets --讲很多big data和data mining的东西
Big Data: Principles and best practices of scalable realtime data systems(http://www.amazon.com/gp/product/1617290343) --
twitter的前员工讲述如何处理实时数据 目前市面上讲解big data最好的一本书
10 凌乱的资料 随便看看吧
http://highscalability.com/blog/2013/10/28/design-decisions-for-scaling-your-high-traffic-feeds.html
== 小结＝＝
看多了以后 你的最终目标应该是心里有了一个大框架 一个基本的distributed system
是怎么搭起来的 然后心里有很多if condition 如果要是满足这个条件 我应该用什么
技术 比如如果read heavy那么用cache会提升performance之类的 同时知道应该避免什
么东西 比如避免single point of failure 再比如时间和空间的tradeoff在read
heavy的时候应该倾向于时间 Write heavy的时候倾向于空间等等
你总结出来的和我总结出来的大框架和if conditions肯定不完全一样 但因为system
design本来就是一个open ended question 所以不用害怕 能够自圆其说 就不会有问题
最后 本文纯属抛砖引玉 如果有大牛发现有错误或者有补充 欢迎留言 大家一起讨论
== FAQ ==
1. New Grad需要看System Design么?
答案是it depends. 有的公司会考system design 有的公司只考到OO design 有的公司
压根不考 当然 考到的公司对new grad的期望值会稍微低一点 但是 你有这么一个机会
能让你gain leverage over other candidates why not? 为什么要让自己在面试前害怕
面试官出system design的题目呢?
Design有越来越重要的趋势，如何快速提高，应对面试？
算法大家基本靠刷题可以八九不离十，这也加大了筛选人才的难度。
所以现在Design的题目比重和重要度越来越高。
大家一起来讨论下，有没有/怎样快速提高系统设计的能力，以应对面试需要？
可以看一些design pattern的书比如Design Patterns: Elements of Reusable Object-Oriented Software（我们上课用的这本）
关于系统设计，这个其实很看积累的，system本来就是考功底的地方，如果没时间上一些system的课(os, distributed system什么的），可以抽空去看下这些课的slides
另外读一些现在很成熟系统或者nosql的paper，比如
Google旧三驾马车 BigTable, GFS, MapReduce, Amazon的dynamo DB等等
最后极力推荐去看一下Google码农之神Jeff Dean的一些关于large scale system design的talk，给几个链接
http://static.googleusercontent. ... anford-295-talk.pdf
http://www.cs.cornell.edu/projec ... ynote-ladis2009.pdf
Implement an API to access a bank. Assume it will be a REST API using HTTP, but don’t worry about protocol processing. Simply write the methods corresponding to API endpoints.
反正都是Simply 题目也说了不用在意协议过程
说白了就是应用层 很浅显的用一下不用理会底下怎么构成的 就是测测你懂不懂这堆@
储蓄查询用@GET 链接里上ID
存钱用@PUT 幂等的 出了错 连续提交 你存多少钱都一个结果 我猜国内银行肯定这么干
取钱用@POST非幂等你出错多次取钱肯定给你都扣掉，我们银行能吃亏？（开玩笑的 一般交易都带流程号 只有一次能用 最好都是幂等安全）
开子户 服务 新建啥玩意用@PUT
说白了就是应用层 很浅显的用一下不用理会底下怎么构成的 就是测测你懂不懂这堆@
储蓄查询用@GET 链接里上ID
存钱用@PUT 幂等的 出了错 连续提交 你存多少钱都一个结果 我猜国内银行肯定这么干
取钱用@POST非幂等你出错多次取钱肯定给你都扣掉，我们银行能吃亏？（开玩笑的 一般交易都带流程号 只有一次能用 最好都是幂等安全）
开子户 服务 新建啥玩意用@PUT
纯探讨哈。我觉得关键原则是保证没有两个线程同时操作同一块内存区域，所以如果不对整个map加锁，那么至少对每个slot加一个锁应该是必要的。还有个要注意的地方是map的长度可能会不停地扩展，扩展后可能需要移动之前放在内存区域里的内容；这个过程进行的时候应该不能有任何其他进程对内存的读写。所以这个地方需要对整个map加锁。hash function可能需要用到map的长度，所以在map的长度扩展时同时也要锁住所有hash function的计算，等长度扩展完成后再恢复
| 是在模拟的diskdrive上有很多file 每个file分散在多个disk block里面 如何能做到defragment（就是让 每个file的piece都是continuous） 楼主想到用hash table存储每个file然后再重新写入。。。 但是有RAM限制所以并不能把每个file都hash。。 |
比如这个disk使用FAT格式，那么FAT表中应该已经有以下信息：
1、每个文件的起始簇（就是你说的block）编号；
2、每个文件的大小和占用的簇个数；
3、每个簇的下一个簇的序号。
所以，这个题说白了就是每个文件都是一个链表，要把链表节点重新安排到连续空间中。
假设磁盘尾部还有足够可用空间，我想可以用这些空间当做缓存空间来进行交换：
1、每个文件的起始簇（就是你说的block）编号；
2、每个文件的大小和占用的簇个数；
3、每个簇的下一个簇的序号。
所以，这个题说白了就是每个文件都是一个链表，要把链表节点重新安排到连续空间中。
假设磁盘尾部还有足够可用空间，我想可以用这些空间当做缓存空间来进行交换：
