Sunday, June 28, 2015

How to Ace a Systems Design Interview | Palantir

How to Ace a Systems Design Interview | Palantir
this third installment in our series on doing your best in interviews. Previously: How to Ace an Algorithms Interview and The Coding Interview.

What makes it interesting, though, and sets it apart from a coding or an algorithms interview, is that whatever solution you come up with during the interview is just a side effect. What we actually care about is the process.
In other words, the systems design interview is all about communication.
We aren’t asked to implement fully-specced features. Instead we take ownership of open-ended problems, and it’s our job to come up with the best solution to each. We need people we can trust to do the right thing without a lot of supervision—people who can own large projects and take them consistently in the right direction. Invariably, this means being able to communicate effectively with the people around you. Working on problems with huge scope isn’t something you can do in a vacuum.

For the most part, you’ll be steering the conversation. It’s up to you to understand the problem. That might mean asking questions, sketching diagrams on the board, and bouncing ideas off your interviewer. Do you know the constraints? What kind of inputs does your system need to handle? You have to get a sense for the scope of the problem before you start exploring the space of possible solutions. And remember, there is no single right answer to a real-world problem. Everything is a tradeoff.

Given this, there are many topics you should be familiar with, such as:
  • Concurrency. Do you understand threads, deadlock, and starvation? Do you know how to parallelize algorithms? Do you understand consistency and coherence?
  • Networking. Do you roughly understand IPC and TCP/IP? Do you know the difference between throughput and latency, and when each is the relevant factor?
  • Abstraction. You should understand the systems you’re building upon. Do you know roughly how an OS, file system, and database work? Do you know about the various levels of caching in a modern OS?
  • Real-World Performance. You should be familiar with the speed of everything your computer can do, including the relative performance of RAM, disk, SSD and your network.
  • Estimation. Estimation, especially in the form of a back-of-the-envelope calculation, is important because it helps you narrow down the list of possible solutions to only the ones that are feasible. Then you have only a few prototypes or micro-benchmarks to write.
  • Availability and Reliability. Are you thinking about how things can fail, especially in a distributed environment? Do know how to design a system to cope with network failures? Do you understand durability?
     Do mock design sessions.
     Work on an actual system.
  • Do back-of-the-envelope calculations for something you’re building and then write micro-benchmarks to verify them. If your micro-benchmarks don’t match your back-of-the-envelope numbers, some part of your mental model will have to give, and you’ll learn something in the process.
  • Dig into the performance characteristics of an open source system. For example, take a look at LevelDB. It’s new and clean and small and well-documented. Read about the implementation to understand how it stores its data on disk and how it compacts the data into levels. Ask yourself questions about tradeoffs: which kinds of data and sizes are optimal, and which degrade read/write performance? (Hint: think about random vs. sequential writes.)
  • Learn how databases and operating systems work under the hood. These technologies are not only tools in your belt, but also a great source of design inspiration. If you can think like a DB or an OS and understand how each solves the problems it was designed to solve, you’ll be able to apply that mindset to other systems

這篇文章主要是把所有手上資源照priority順序加上一些自己的整理 用簡單的方式介紹怎麼Ace system design 依照priority順序分成
明天面 下禮拜面 下個月面 跟明年面

迷途書僮:誒jyt0532 我明天就要面試了 沒空讀那麼多你給的文章 該怎麼辦?
jyt0532: 很好 今天幸好你遇到我 我用最少的時間讓你知道明天面試的時候大方向怎麼走
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: 既然你都這麼說了 今天幸好你遇到我 把這個看完你就通透了
迷途書僮: 喔原來是這個 那這4個step 你這樣講真的很抽象 可不可以舉個例子 我可以apply到所有system design的題目
jyt0532: 光說不練假把戲 我帶你手把手跑一次system design process

來個基本的 假設現在要design一個cache
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

算一下你需要多大的machine多少台 這裡面的數字要有點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: 畫出大架構
這時候就必須推薦 這根本太精采
什麼你又沒時間 好啦別說我虧待你 有人把重點整理好給你了

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)
這些也不是一時半刻講得完的 有需要的話我再補充 打到這邊有點累了

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



  1. 并发性(concurrency)。你知道线程(threads)、死锁(deadlock)和starvation吗?你知道如何并行化算法吗?你了解一致性(consistency)和连贯性(coherence)吗?你大概了解IPC和TCP/IP吗?你知道吞吐量(throughput) 和延迟(latency)的区别吗?
  2. 现实表现(real-word performance)。你应当熟悉你电脑的速度和性能,包括RAM、硬盘、SSD以及你的网络状况。
  3. 估计(estimation)。估计在帮助你缩小可能性解决方案的范围时起到了重要的作用。这样,你就只需写少数几个原型或微基准。
  4. 可用性和可靠性(availability and reliability)。你是否考虑过系统什么时候会出现bug无法运行吗(特别是在分散式的环境中)?你知道如何设计一个系统以应当网络故障吗?你了解持久性吗?切记,我们并不是要寻找一个熟悉以上所有的问题的“全才”。我们想衡量的是你的熟练程度。我们只需要你对系统设计方面有一定的基础,并且知道什么时候应该寻求专家的帮助。
  • 在实际的系统中去实践。你可以在既有的OSS中去练习,也可以与朋友合作搭建一个系统。对于课堂中的系统设计作业,不再把它仅仅当成一个学术训练,而是把它当成实际问题,思考系统设计过程中的架构和博弈。正如我们生活中遇到的大多事情一样,只有做了才知道其中会遇到什么问题,从而真正学到东西。

  • 深挖开源系统的运行特点。例如,你可以看看levelDB。这是一个干净、小、且编写良好的系统。你可以读读执行命令,了解它是如何在硬盘中存储数据的,如何将数据压缩成不同的层?你也可以多多反思一下的博弈问题:哪种数据和大小是最优的?什么情况下会降低读写速度?(提示:比较一下随机写和顺序写)

  • 多了解一下系统中数据库和操作系统是如何运行的。这些技术并不只是你口袋中的工具,它们往往会在你设计系统的时候给你带来启发。如果你经常像DB或OS一样思考它们如何处理各自的问题,你也会把这些思考方式应用到其它的系统设计中去。


Read full article from How to Ace a Systems Design Interview | Palantir


Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts