System Design Misc Part 3

http://blog.gainlo.co/index.php/2015/10/22/8-things-you-need-to-know-before-system-design-interviews/

In a system design interview, the candidate is often asked to design a new system in order to solve an open-ended problem like designing the URL shortening service. Sometimes the problem can be quite general like how do you design the recommended system for Youtube.

During this process, discussion is the core. The candidate is more likely to lead the conversation and discussion high-level components, details, pros and cons, and everything with the interviewer.

Compared to coding interview, system design interview is much more similar to software engineer’s daily work.

During the interview session, your communication and problem-solving ability are mainly evaluated. Given an open-ended problem, how do you analyze the issue, how do you solve it step by step, how do you explain your idea and discuss with others, how to you evaluate your system and optimize it are what interviewers mostly care.

2. Get your hands dirty

The best way to prepare system design interview is always thru real projects and practices. Many people start their preparation process quite early like 6 months or 1 year in advance, then this is definitely the best practice for you.

A common pattern we saw is that the more practical experiences you have, the better you are at system design interview. It’s quite easy to understand because those system design questions are all from real life product and people who have worked on many projects before tend to have a better sense on these problems or it’s just one of the problem they have solved before.

When asked to design Youtube recommendation system, it’s similar to many other recommendation systems say Amazon’s system since a lot of concepts are common here.

If you have some experience with recommendation, or you’ve read some articles/books or have thought about it, you must be able to come up with some initial ideas at least.

If you don’t know what to work on, here’re some suggestions for you:

• Build a small service/product to solve a real problem you have
• Contribute to open source projects at Github
• Find a topic that interests you like machine learning, network etc. and search for some projects you can work on

What really matters is getting your hands dirty to work on some real life projects. It could take a long while before you can see your improvement, but at that point, you will notice how straightforward those interview questions are. Also, you will benefit a lot from this in the long run.

3. Be familiar with basic knowledge

• Abstraction. It’s a very important topic for system design interview. You should be clear about how to abstract a system, what is visible and invisible from other components, and what is the logic behind it. Object oriented programming is also important to know.
• Database. You should be clear about those basic concepts like relational database. Knowing about No-SQL might be a plus depends on your level (new grads or experienced engineers).
• Network. You should be able to explain clearly what happened when you type “gainlo.co” in your browser, things like DNS lookup, HTTP request should be clear.
• Concurrency. It will be great if you can recognize concurrency issue in a system and tell the interviewer how to solve it. Sometimes this topic can be very hard, but knowing about basic concepts like race condition, dead lock is the bottom line.
• Operating system. Sometimes your discussion with the interviewer can go very deeply and at this point it’s better to know how OS works in the low level.
• Machine learning (optional). You don’t need to be an expert, but again some basic concepts like feature selection, how ML algorithm works in general are better to be familiar with.

Remember, the point is here asking you to learn all these stuff from scratch, which may take you more than a year. What really matters is the basic concepts behind each topic. For instance, it’s totally okay if you can’t implement neural network in the interview, but you should be able to explain it within a sentence.

4. Top-down + modularization

This is the general strategy for solving a system design problem and ways to explain to the interviewer. The worst case is always jumping into details immediately, which can only make things in a mess.

Instead, it’s always good to start with high-level ideas and then figure out details step by step, so this should be a top-down approach. Why? Because many system design questions are very general and there’s no way to solve it without a big picture.

Let’s use Youtube recommendation system as an example. I might first divide this into front-end and backend (the interviewer may only ask for backend or a specific part, but I’ll cover the whole system to give you an idea). For backend, the flow can be 3 steps: collect user data (like videos he watched, location, preferences etc.), offline pipeline that generating the recommendation, and store and serve the data to front-end. And then, we can jump into each detailed components.

For user data, we can list features that we think are relevant to videos a user may like. For pipeline, we can discuss how to train the dataset etc.. We can go even deeper. Since Youtube has a huge dataset, the offline pipeline must run over a huge number of data, then MapReduce or Hadoop might be used.

We can continue this analysis infinitely by going deeper and deeper, but the idea I want to explain here is that you should always have a big picture.

Another tip here is modularization. Like I illustrated above, it’s better to divide a system into different components, which is also a good practice in real life projects. Modularization not only can make your design much clearer to both yourself and the interviewer, but also make testing much easier.

5. Pros & cons

System design questions are often given without much restriction. As a result, there’s no clear cut between good solutions and bad solutions. In this case, you are responsible to understand what is the best approach in different scenarios.

The most common trade off is between time and memory. You can directly tell the interviewer about the pros and cons for each solution and ask him to clarify the constraints like how much memory you have.

Also when asked to optimize the system, you can also put several common constraints there, for example, if you are designing something for driver’s license, you can tell the interviewer that it’s reasonable to assume the max length of a license is maybe 7, and in this way you might be able to store all license in memory, based on which you can further optimize your system.

6. Estimation

You’d better have a good sense of numbers when doing estimation, which is even more important in real projects. More specifically, you should have a clear estimation of how much memory your system or program would cause, how fast it runs, and based on your estimation, how would you adjust your design.

If we use the driver license example, of course you can say let’s assume the memory is enough to store all license in US. But it’ll be more impressive that you first estimate how much memory you need to store them.

To estimate the memory cost, you should count how many licenses are there if the max length is 7, and what data structure you’re gonna use to store and then figure out how much memory you need, which will give you clear idea whether this approach is feasible.

Also when deciding storage, memory of course is not the only solution. Beside storing everything in memory, you can store in disk, or store in multiple computers as well. Selecting the best approach is really a matter of estimating time and storage cost. Figuring out the bottle neck of the execution time and memory limit will give you a much clearer picture of the whole system.

7. Mock interview

Quite honestly, it’s not very easy to practice system design interview by yourself since there’s no standard answer for it. So the suggestion is always doing this in front of some experienced engineers.

Also thru this process, you’ll spend majority of your time communicating and discussing with the interviewer, which is what system design interview mostly about. So in short, we strongly encourage you to practice system design interview with others instead of by yourself.

8. Learn from existing system

This approach is what I usually suggest people to do. Whenever you are curious about some system, try to figure out how this system was designed. You can try to design by yourself first and then compare with how it is actually designed. Most importantly, try to understand why it’s designed in this way. It’s very likely that certain constraints that forced the system to be like this, like data size, speed requirement etc..

http://highscalability.com has a lot of good articles about how real world systems are designed. It might be a little overkilled for system design interview, but it’s always good to know about them.

Also you will notice that even for the same kind of system, different company may have totally different ways of designs. You’ll definitely learn a lot from exploring this.

http://www.raychase.net/2878

系统设计方面的问题问题是非常考验经验和思维过程的，而且和常见的算法问题、语言基础问题不同，涉及的面很广，还没有比较一致的判别标准。但无论如何，还是可以归纳一些常见的思路和典型问题的线索。

首先，反复沟通和澄清系统需求。只有把需求澄清清楚了，才可以开始思考并落到纸面上。但是需求的沟通应该是持续和循序渐进的，问题很难从一开始就思考全面。最重要的条目包括：

• use cases，通常问题只需要2~3个use cases需要考虑，其他的部分会晚些考虑，或者不考虑。这样就可以简化问题。
• 用户数量（用户可以是下游系统或者人）、数据数量，澄清这个事实无疑非常重要，对系统设计的决策有重大意义。
• 请求模型，比如读远大于写，比如60%的请求都访问top 20的记录。

其次，尝试抽象一个简单的模型，从简单模型开始，思考不同的场景和约束，逐步完善。落实到代码上的时候，最核心的部分包括：

• 模型的定义。
• 代码接口，API。
• 数据是怎样被存储的，比如表结构和文件结构。

在此基础上，考虑最基础的组件和架构划分，整个系统要分几层，有哪些组件，各自什么作用，可能的瓶颈是什么等等。还有前面的API、模型分别被安插到哪部分上面，同时反复比较第一步的几个use case是否都被满足。

再次，细化层结构和组件，比如：

• 存储层。是否需要持久化存储？选择文件、关系数据库，还是NoSQL数据库？
  • 如果选择关系数据库，是否需要sharding或partition？参考Quora：What’s the difference between sharding and partition?
  • 如果选择NoSQL数据库，CAP中分别牺牲和优先保证哪一个？参考：Visual Guide to NoSQL System。扩容的策略（比如一致性hash）？
  • 存储是否需要分层（比如冷层——文件、暖层——关系型数据库、热层——缓存，不同成本的存储介质，用以应付不同的数据访问频率）？
• 集群。所有节点对等还是中心节点主备？请求负载分担的策略？如何增减节点？如何判定节点健康状况？是否需要会话？会话如何同步？Scale up和Scale out的区别，参考Wikipedia：Scalability。
• 消息模型。生产者和消费者的速率？无法应付时是否需要缓冲队列？消息流量控制？速率控制的精细度？
• 缓存系统。缓存的分层？分布式部署还是集中式缓存服务？使用什么缓存淘汰算法（比如LRU）？参考：In-Process Caching vs. Distributed Caching。

其中，系统瓶颈的识别和scale是紧密联系着的两个话题。在需求驱使的基础上着手优化，比如缓存的应用，这需要建立在系统瓶颈被识别或者假定被识别的基础上，否则就是乱枪打鸟。在瓶颈解决之后再考虑scale。

最后，不断讨论和完善，每一个讨论迭代都要得出一个实际的结论，避免持续停留在过高抽象层面。这里涉及的部分可以很多，包括可扩展性、数据规模、吞吐量、可维护性、实时性、数据一致性等等。

所以，归纳起来的四部分为，先从系统外部理清楚需求，接着设计核心模型和API，再进行基本的分层和组件划分，最后才是细化每一层或者每个组件的设计。从外到内，逐层剖析。

这些点说起来容易做起来难，通过反复阅读和思考一些常见的系统设计场景，其实我们还是可以从中总结出若干规律来。

下面列出几个非常常见和典型的系统设计问题的hints：

1、怎样设计一个微博/Twitter系统（news feed系统）

• 思考读写模型，latency上看明显是读的要求明显高于写的模式。
• 转发和回复，拷贝原微博文字还是存储转发/回复树形关系？分析利弊。另外，这里涉及到产品设计，参见：Twitter Vs. Weibo: 8 Things Twitter Can Learn From The Latter。
• 区分两种典型消息传播的触发方式：push on change和pull on demand，两种方式利弊明显。参考：Why Are Facebook, Digg, And Twitter So Hard To Scale?
• 存储分级。这里CAP中A最为重要，往往C可以被牺牲，达到最终一致性。
• 缓存设计，分层的数据流动？如何识别热门？
• 删除微博功能的设计。

最后，不断讨论和完善，每一个讨论迭代都要得出一个实际的结论，避免持续停留在过高抽象层面。这里涉及的部分可以很多，包括可扩展性、数据规模、吞吐量、可维护性、实时性、数据一致性等等。

所以，归纳起来的四部分为，先从系统外部理清楚需求，接着设计核心模型和API，再进行基本的分层和组件划分，最后才是细化每一层或者每个组件的设计。从外到内，逐层剖析。

这些点说起来容易做起来难，通过反复阅读和思考一些常见的系统设计场景，其实我们还是可以从中总结出若干规律来。

下面列出几个非常常见和典型的系统设计问题的hints：

1、怎样设计一个微博/Twitter系统（news feed系统）

• 思考读写模型，latency上看明显是读的要求明显高于写的模式。
• 转发和回复，拷贝原微博文字还是存储转发/回复树形关系？分析利弊。另外，这里涉及到产品设计，参见：Twitter Vs. Weibo: 8 Things Twitter Can Learn From The Latter。
• 区分两种典型消息传播的触发方式：push on change和pull on demand，两种方式利弊明显。参考：Why Are Facebook, Digg, And Twitter So Hard To Scale?
• 存储分级。这里CAP中A最为重要，往往C可以被牺牲，达到最终一致性。
• 缓存设计，分层的数据流动？如何识别热门？
• 删除微博功能的设计。

2、怎样设计一个短网址映射系统（tiny url系统）

• 思考读写模型，明显是读优先级高于写的服务，但是通常不需要修改。读写服务分离，在写服务崩溃时保证读服务健康运行。
• 链接缩短使用的加密和映射的方式中，算法如何选择？短链接可以接受那些字符？此处可以估算特定的规则下长度为n的短链接最多可能表示多少种实际链接。
• 如果使用统一的短链接序列分配机制，如何分布式设计这个分配逻辑？它不能够成为瓶颈。例如，一种常见的思路是让关系数据库的自增长索引给出唯一id，但是如果不使用关系数据库，在分布式系统中如何产生唯一序列号且避免冲突？参考：如何在高并发分布式系统中生成全局唯一Id。
• 是否需要保留原始链接最后部分？如http://abc.def.com/p/124/article/12306.html压缩成http://short.url/asdfasdf/12306.html，以增加可读性。
• 由于协议部分可以预见或者需要支持的数量很少（比如就支持http和https），是否可以考虑把协议部分略去，以枚举方式和短链接正文放在一起？
• 由于属于web服务，考虑判定URL合法性，考虑怎样控制请求流量和应对恶意访问。

3、怎样设计一个实时聊天系统？可以是MSN、QQ这样的CS结构的，也可以是Facebook Chat或者微博私信这样的BS结构的。

• 登陆时需要获取好友状态列表，这通常也是priority 0的use case。
• 这个问题的特点是客户端和服务端已经天然地分开了，核心问题之一是把服务端和客户端的交互梳理清楚。如果是BS结构的，怎样使得从服务端到客户端的消息推送成为可能？Ajax+Comet是一个办法，hang住连接，消息推送。还有一种办法是客户端轮询，但是显然实时性无法胜任。
• 如果使用Comet，服务端将存在大量的空闲连接。参考，select、poll、epoll之间的区别总结[整理]。对于消息的处理，引入协程，减少线程调度开销，参考：Difference between a “coroutine” and a “thread”?。
• 如果是CS的，消息和状态还可以通过P2P的方式；但是如果是BS的，就必须实现一个服务端的消息系统，参考：实时通信协议XMPP。
• 存储方面，CAP怎么权衡？可以牺牲掉哪一个？
• 如果要求完成历史消息功能，那又是另一番故事了。其他值得讨论的扩展的功能包括系统消息群发、好友状态更新和消息搜索等等。

还有一些系统设计典型和经典问题，想到的先列在下面，等后续有时间总结了再补充到上面去：

• 搜索引擎设计（包括网页爬虫）
• 邮件系统设计（例如GMail）

无论如何，对于这些问题的解决，反复思考是非常有趣的。这些东西貌似可以直接拿来学习的材料比较少，而且也不像算法那样丁是丁卯是卯的，评判的标准模糊得很。

http://www.raychase.net/3165
http://www.raychase.net/1615

在系统设计阶段考虑全面很难，有许多人倾向于把整个设计分成若干阶段，在迭代中完成整个设计，这本身是非常好的，但是，就如同“先做出来，以后再优化”这样的经典谎言一样，本身并无错，只是许多程序员都不习惯于真正的迭代设计和迭代优化。举例来说，有一个日益复杂的类，每个人都修改一点点，一直到最后都没有人愿意去做重构，大家的心态都是一样的：“我只修改了一点点，为什么要我去动那么大的刀，于我没有任何好处”。我不在这里谈论这一问题的解决办法，我倒是想说，在开始阶段考虑清楚问题在多数情况下还是很有好处的，设计考虑得越是清楚，在后续阶段代码可以承受越多的变更而不腐朽。

再做系统设计的时候，我们常常会这样说：“一般情况下”、“99%”和“基本上”等等。如果你发现这是在悄悄地，或者潜意识地避谈问题，可就要小心了。有时候你可以找到根据，“事情不会那么坏吧”，“不会那么不凑巧吧”，在系统设计阶段尽把事情往好的方向想可未必是件好事；也许更多时候会觉得这是直觉，总觉得某一处设计别扭，不合理却有说不出强硬的理由来，最多只能抱怨一句“通常它不应该是这样设计的”。这种情况发生的时候，请千万不要放过它，很多次，在系统上线以后，最初的问题或者潜在的问题最终暴露出来，而这样的问题很多在系统设计阶段都是有端倪的。

例子1：用户行为记录的持久化

以前我参与做过这样一个系统，用户的行为需要被记录到数据库里去，但是每条记录发生的时候都写一次数据库觉得开销太大，于是设计了一个链表：

• 用户的行为会首先被即时记录到链表里面去；
• 每十分钟往数据库里面集中写一次数据，然后清空链表内的数据。

看起来确实可以实现需求，可是，这样的设计有什么问题？

这样的设计当时居然没有受到系统设计评审的人的质疑，我实在觉得奇怪。我想很多人都可以看得出潜在的问题：

• 清空链表数据是使用时间条件触发的任务来完成，换言之，无论这十分钟内如果事件暴增，也无法触发链表清空的行为，链表很容易变得非常大；
• 清空链表的任务如果执行过程中出了异常，甚至仅仅是处理速度受到阻塞，将直接导致链表数据无法得到清空；
• 如果往数据库里写数据和清空链表的行为需要锁定链表，倘若链表很大，或者写数据库过慢，都会导致链表写行为被阻塞。

这些问题当然在明确的情况下可以得到规避，但是毫无疑问，这样的设计充满了潜在的危险。事实上，最终这样的问题也确实发生了，导致的结果是链表巨大，撑死了整个系统，OOM，系统失去响应。

例子2：HashMap并发访问导致死循环

非常常见的并发访问HashMap的问题，我也遇到过。有潜在的危险导致HashMap死循环，表现就是CPU占用100%，而且这样的问题是不可逆的，问题的原因分析我相信大家可以在网上搜得到很多文章，我就不啰嗦了。我印象深刻的是当时定位完问题，向犯下错误的程序员解释原因的时候，他居然还说：“这个HashMap的读写很不频繁，哪有那么巧的事？”，这就是侥幸心理，即便知道了问题依然不愿意做出修正。

例子3：摘要算法的冲突问题

类似的问题还有，使用摘要算法的时候，比如MD5，我在做一个系统，使用一个中心集群缓存，使用一个巨长的字符串的MD5摘要来做key，好处在于key的长度可以大大缩短，但我们都知道，任何摘要算法都会使得结果字符串存在冲突（重复）的可能，即源字符串不同，但是摘要字符串相同，虽说用统计的话来说，单纯两个字符串发生这种情况的概率低到几乎不可能发生。但是我们依然需要谨慎，尤其是在数据量巨大的情况下，一旦发生冲突，要有解决办法（比如把源字符串放在缓存条目的结果对象中，在缓存条目命中，正式取出返回前，再进一步比较源字符串以确定100%的准确性），或者至少必须要能够承担风险。

例子4：文件处理后续流程的两个问题

最近有一位同事向我们介绍了他最近处理的一个问题，这个问题是，用户会上传一个多行的文件，比如文件有一万行，每一行都代表一条待处理的数据，在数据正确的时候，一切都正常；倘若有一行数据处理发生错误，会自动发送一封邮件通知，看起来似乎很不错的系统。但是这个时候问题来了，有一次文件的处理错误过多，导致一口气发送了几千封邮件，变成了邮件洪水。而在他介绍这个系统设计的时候，我们留意到了其中存在一个时间条件触发的任务，任务基于两个数据库的数据执行，这两个数据库的数据同步是单独完成的，因此可能存在数据不一致的情况，并且在这里假定在数据更新的一小时以后，两个库的数据就会一致了。这其实就涉及到了两个问题或者隐患，一个是邮件处理和发送的数量缺乏控制，另一个是用假定的时间来保证数据的一致性。

例子5：单点故障问题

单点故障问题也是很常见的会导致服务失去的问题，出了问题所有人都知道原因，但是有时候就是很难在系统设计阶段识别出来。以前我们给电信运营商提供服务，很多电信运营商通常有钱（比如国内的三家垄断巨头），不太在乎成本。服务器用的单板几万块钱一块，备了几十块，文件存储是一个大型的磁盘阵列，数据库是IBM小型机双机备份（PS：IBM的设备其实挺不可靠的，听维优的同学说，保修期内屁事儿没有，保修期一到一台台IBM的机器开始坏，搞得像定时炸弹似的），当时唯独忽略了单点的负载分担硬件——F5，F5挂掉的时候，工程师都傻了眼。

例子6：文件不断写入导致磁盘满的问题

文件写满磁盘导致空间不够的例子也非常常见，绝大多数写文件的场景大家都会留意到，并且在系统设计评审的时候都会有人站出来问，“xxx的文件写入是否是可控的？”。但是，由于文件写入的场景非常多，还是有很多情况被忽略。比如JVM的GC日志的打印，这样的文件可以协助定位问题，但是如果不设置文件上限大小参数，就有导致磁盘空间不足的风险；还有日志文件，绝大多数系统都有日志文件压缩或者日志文件转移的脚本，但是和前面提到的例子1一样，一方是生产者，一方是消费者，消费者出了问题，就会导致数据堆积。如果这样的文件处理脚本执行出现问题，或者在系统压力大以及系统异常情况频繁的时候，日志疯涨，来不及及时把日志文件转移出去，导致日志文件把磁盘撑满。通常对于要求比较高的服务，磁盘空间监控是必要的。

例子7：服务器掉电以后的快恢复

再说一个问题，这个问题是从一个技术分享中流传开来的。亚马逊网站的数据都是页面服务器先从缓存服务中获取数据，通常这个命中率很高，如果获取不到数据或者数据过期以后再到数据库里查询。这样的模式非常常见，我们也总能看到很多技术报告里面写平均的缓存命中率能够达到百分之九十多，可以飙到多少多少的TPS，为此可以节约多少多少硬件成本。初看这样的设计真不错，但是很容易忽视的一点是，这样的数据是建立在足够长时间，以及足够多统计数据的基础之上的，但是在单个时间段内，缓存命中率可以低到难以承受的地步，导致底层的数据服务直接被冲垮。有一次亚马逊机房突然掉电，在恢复的时候把网页服务器都通上电，这时候缓存服务还几乎没有缓存数据，缓存命中率几乎为零，于是大量的请求冲向数据库，直接把数据库冲垮。外在的表现就是，掉电导致网站无法提供服务，短期内访问恢复，随后又丧失服务能力。

-- During application startup, warm up necessary cache
-- Enable services gradually - first for 20% users, then 50% then 100%..

软件当中有些东西和经验有密切关系，不像很相对容易提高的语言技能和算法，系统设计经验，尤其是对问题的预估很需要时间和项目的磨炼。我不知道这样的系统设计经验怎样才能快速积累，但是我想还是有一些常规模式可循，我不知道是否有比较经典的资料可以学习。另一方面，系统设计真是一个细致和谨慎的活儿，不要随意放过那些潜在的问题，有时候甚至就是一点奇怪的感觉，或者是设计图看起来不那么协调和稳当，细究下去，还真能发现陷阱。如果你也有类似的经历，不妨谈一谈。

从Disucz能学到什么

3、安全存储

Discuz在用户信息存储中，在密码加密环节用了随机Salt，很多知名网站都没有意识到随机salt的意义和目的。简单重述一下，这是你数据库被扒之后仍能保证用户密码安全的有效方式。

另一个典型范例是，当时我们用到的一些缓存表最初是myqsl的heap引擎，因为这是内存引擎么，想当然很快，后来使用过程中发现存在严重问题调整为物理存储的innodb引擎。原因其实很简单，heap引擎是表级锁，大量查询请求时经常锁死，而innodb是行级锁，并发查询下执行效率更优。

那么有人会说，innodb的写入效率是灾难，哦，其实用异步机制写入，效率可以和myisam不相上下的。

此外，写入效率影响很大的一个环节是binlog文件处理，这里跟淘宝余峰学了一招，顺便分享给大家，binlog是顺序写，索引文件是随机写，顺序写比随机写效率要高一个数量级，所以正确的解决方案是，用单独的物理硬盘存储binlog，可以有效避免同时写binlog和索引文件的不必要开销。

第一呢，加缓存，也就是在常用SQL前加了一层 memcache，减少重复查询请求，减少数据库的查询压力，顺便把ip地址反查的二分处理，全部内存化了。

第二呢，异步化，一些非实时需求的数据存储请求异步处理，通过crontab设置定时任务，与memcache联动。异步处理后，数据写请求被裁减了很多，数据库写入压力极大降低。

当时比较笨，还没研究redis，其实后来发现redis的数据类型更丰富，比memcache要更灵活。

第三，摘联表，所有联表查询单表化，单表SQL完不成的设计冗余结构。

目的是为了下一步数据库的分布式。这步犯的错误最多，造成各种线上事故。

第四，分表分库，

不摘联表是做不了分表分库的。分表分库，通过中间件做数据库的请求分发和传递，整个数据支撑体系就扩展开了

http://systemdesigns.blogspot.com/2016/01/blog-post.html

本文摘取了视频课程最后的程序员能力评估标准，私以为这几方面的能力决定了未来发展的高度。

根据以下四项类别进行评分，最后进行分数累加，便能找到自己所处的Level。

面试时的结构化准备模板：