谈谈系统设计的面试 - 迷思 - 知乎专栏



谈谈系统设计的面试 - 迷思 - 知乎专栏

这个题目我一直在考虑要不要写,因为有一天也许我们彼此会坐在一方小桌的两端,聊聊系统设计,而我这么做有泄题兜底之嫌。不过,考虑到不是所有的读者都会来 TubiTV 这座小庙面试,而这个方面的确是很多朋友的弱项,我就略说几句。

请听题:一个使用 rail(或者 django,或者 express,...)和 MySQL 做的 API 系统,最近流量从 6,000 RPM 激增至 20,000 RPM,整个系统的压力骤升,现在需要在应用层设计一套缓存方案来降低整个系统的负荷。要求是:缓存方案不能在 web 层(包括 proxy)做,也不能使用 framework 自带的,或者第三方的缓存模块。

大部分的面试者一看,这问题简单啊,使用 redis(或者 memcached),加在应用服务器和数据库服务器之间,读取数据的时候如果没有命中缓存,则读取数据库并写入缓存,下次再读相同的数据时就能命中缓存,大大减轻数据库的压力了。

这回答对么?不好说。也许对,也许不对。但你要这么快抢答的话基本上就会被面试官毙了。

系统设计的面试重在讨论和交流,厘清一切限制条件,然后在这些限制条件下面找到一个比较合理的解决方案。它不是编程题或者算法题,弄清楚题目的要求就可以写开始答案的。

好的面试者应该主动发问,来尽量找全限制条件,而不是直接假设。拿上述回答来说,面试者还没开始认真分析问题所在,就想当然认为压力在数据库一侧(是的,流量激增之后 90% 的可能性都是数据库先扛不住压力,但这是假设,不能化作前提),从可能错误的前提出发,必然会得出一个很可能错误的解决方案。

所以比较对路的思考过程是:

现有系统的架构是什么样子?

作为一个已有系统的优化项目,不了解现有系统的架构,历史(演变的过程和演变的原因,当然,在面试中这个可以省去)而立刻上手设计都是在耍流氓。

  • web 服务器,应用服务器,数据库服务器等之间的关系以及数量?
  • 现在有没有使用类似于 redis / memcached 的缓存服务器?如果有,它们用来处理什么任务?(如果有人问道这个,会有大大的加分)

目前哪个部分在系统中压力最大?

这个问题非常重要,你得需要先知道问题在哪再考虑优化。如果问题出在应用服务器,那么,可能需要做页面级的缓存;如果问题出在数据库服务器上,可以做数据级或者页面级的缓存。

我们希望达到一个什么样的 capacity?

很多有多年一线工作经验的面试者在这样一个系统设计中竟然不去考虑究竟需要一个什么样的 capacity,就进入到具体的解决方案,这样是不妥的。capacity 因问题而异,在这例子中,起码要考虑 1) 缓存系统每秒的处理能力 2) 缓存系统的容量。对于一个 20k PRM 的请求数量,缓存系统应该能承受 50k,100k,甚至 200k PRM 的请求。至于容量,应该考虑假设所有不同的请求都被缓存(worst case),需要多大的容量,在限定的软硬件条件下,是否能达到这个容量,达不到的话,什么样的上限比较合理。

有了这样一个目标后,你还需要对你要使用的工具有个谱。有一个面试者说用 redis 做缓存,因为 redis 很快。「很快」是个很虚的概念,我于是问这个面试者你觉得 redis 对于 1k 大小的value,在 commodity hardware 上做 GET 操作每秒钟的 QPS 是多少?对此,面试者一点概念也没有,我让他猜,他竟然给了个 3-5k QPS 的估值。我自己印象中 redis benchmark GET 操作大概是 100k 这个数量级,当然,每次返回 1k 大小的数据会拖累这个结果,但绝不会差出来两个数量级。

有了设计容量的概念后,我们需要知道要缓存数据的大小,这其中,median size,average size,max size 都需要了解一下,起码知道是什么量级。返回 2k 大小的数据和 200k 大小的数据的处理方式可能是完全不同的,假设你的缓存系统的容量是 1M,2k 数据大小的缓存直接占用的内存是 2G,而 200k 则是 200G,后者显然不能使用内存来做缓存,只能用文件系统缓存。

讲到文件系统,多说两句。用文件系统做缓存则需要注意 unix 的目录实际上是一个记录文件名和 inode 对应关系的 map(你可以 ls -ai1 . 查看)。单个目录下的文件越多,这个 map 越大,需要的读取次数就越多(一般系统调用会每次读 32k 或者类似的量级),所以当一个目录下的文件特别多时,访问效率会急剧下降。这是为什么常见的文件缓存系统都是用两级甚至多级目录,1M 个文件,一级目录使用两个字母或数字,可以有 (26 + 10) 平方个二级目录,也就是 1296 个目录,每个目录名两个字节,加上 inode 和其他一些消耗, 10-20 字节完全够用,一次读取就能获得所有二级目录,而二级目录平均是 772 个文件,一次读取也能完成,总共两次读取,找到缓存文件,而如果把 1M 个文件放在一个目录下,如果每个记录 32 字节,需要 1000 次读取。这种分级缓存的思路在很多系统中都能见到,比如 TLB(不过多级 TLB 主要是为了节省内存)。

设计是否有优化的地方?


Read full article from 谈谈系统设计的面试 - 迷思 - 知乎专栏


No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts