Tuesday, April 18, 2017

System Design Interview Misc


https://www.zhihu.com/question/26312148
很多考察内容
比如面向对象,接口设计,设计模式,数据库表,分布式。

这里就针对Scalability,有一些常见的优化技术,我就把他们列出 7脉神剑。
  1. Cache:缓存,万金油,哪里不行优先考虑
  2. Queue:消息队列,常见使用Linkedin的kafka
  3. Asynchronized:批处理+异步,减少系统IO瓶颈
  4. Load Balance: 负载均衡,可以使用一致性hash技术做到尽量少的数据迁移
  5. Parallelization:并行计算,比如MapReduce
  6. Replication:提高可靠性,如HDFS,基于位置感知的多块拷贝
  7. Partition:数据库sharding,通过hash取摸
https://zhuanlan.zhihu.com/p/20347666
我们面试时,我们希望看到面试者表现出基本的系统知识,同时了解一些设计的技巧。这与算法面试和程序面试有什么不同呢,那就是,我们在整个过程中,其实主要看中的是你思考论述的过程,而不是你最后提出的解决方案(当然如果你提出的解决方案实在太挫……)。
也就是说,系统设计面试最重要的一点是“沟通”(communication)。
这也正体现了Palantir的企业文化。在Palantir,工程师们有着充分的自由。Palantir不会要求工程师一下子就开发出非常完美的功能。相反地,我们的工程师对于这些开放性问题有着充分的自主权。而且,我们的工作就是各自去为这些问题提出最佳的解决方案我们希望寻找的是那些我们可以完全信任的人。这样,他们自己就可以做出非常棒的方案,而不需要我们的监管。也就是说,我们需要的工程师,是那些可以管理一个很大项目,同时保持项目持续朝正确方向发展的人。这意味着,你必须可以高效地与身边的同时进行沟通。因为“闭门造车”在我们的大规模项目中是不可能的。

开放式面试

通常,我们会先让你按给定的题目设计一个系统。面试官给你的提示往往很简单 ——但你千万不要太天真,这些题目往往都是“深不可测”的,面试官们想要看的是在45分钟内,你可以解决掉多少问题。
大多数时候,我们会把握谈话的方向。不过你可以按照自己的理解去解答面试题。
也就是说,你可以提问、在白板上画示意图,甚至可以激发出面官的想法。这道问题的限制条件是什么?系统设计时需要什么输入?这些都是你在展开思考时所需要先向面试官澄清的。一定要记住,现实生活中的问题,都不是只有一个答案的哦。任何事情都是一个博弈。

考察内容

系统是非常复杂的。当你在设计一个系统时,你必须直面所有的复杂性。基于这一点,你必须熟知以下内容:
  • 并发性(concurrency)。你知道线程(threads)、死锁(deadlock)和starvation吗?你知道如何并行化算法吗?你了解一致性(consistency)和连贯性(coherence)吗?你大概了解IPC和TCP/IP吗?你知道吞吐量(throughput) 和延迟(latency)的区别吗?
  • 现实表现(real-word performance)。你应当熟悉你电脑的速度和性能,包括RAM、硬盘、SSD以及你的网络状况。
  • 估计(estimation)。估计在帮助你缩小可能性解决方案的范围时起到了重要的作用。这样,你就只需写少数几个原型或微基准。
  • 可用性和可靠性(availability and reliability)。你是否考虑过系统什么时候会出现bug无法运行吗(特别是在分散式的环境中)?你知道如何设计一个系统以应当网络故障吗?你了解持久性吗?切记,我们并不是要寻找一个熟悉以上所有的问题的“全才”。我们想衡量的是你的熟练程度。我们只需要你对系统设计方面有一定的基础,并且知道什么时候应该寻求专家的帮助。

如何准备

就像你在准备算法面试和程序面试时一样,你必须刷无数的题,系统设计同样需要练习。以下提供一些可以帮助你提高的建议:
  • 模拟系统设计面试。邀请一个工程师帮你模拟面试。让他提出一个系统设计问题,如果正好是他正在做的项目那就再好不过了。不要把它当成是一个面试,而是放轻松地去思考问题,并提出你能想到的最佳解决方案。
  • 在实际的系统中去实践。你可以在既有的OSS中去练习,也可以与朋友合作搭建一个系统。对于课堂中的系统设计作业,不再把它仅仅当成一个学术训练,而是把它当成实际问题,思考系统设计过程中的架构和博弈。正如我们生活中遇到的大多事情一样,只有做了才知道其中会遇到什么问题,从而真正学到东西。
  • 深挖开源系统的运行特点。例如,你可以看看levelDB。这是一个干净、小、且编写良好的系统。你可以读读执行命令,了解它是如何在硬盘中存储数据的,如何将数据压缩成不同的层?你也可以多多反思一下的博弈问题:哪种数据和大小是最优的?什么情况下会降低读写速度?(提示:比较一下随机写和顺序写)
  • 多了解一下系统中数据库和操作系统是如何运行的。这些技术并不只是你口袋中的工具,它们往往会在你设计系统的时候给你带来启发。如果你经常像DB或OS一样思考它们如何处理各自的问题,你也会把这些思考方式应用到其它的系统设计中去。

最后,放轻松,表现出你的创造力

系统设计或许比较难,但它也是可以让你表现自己创造力的地方。在面试时,注意聆听问题,确保你了解该问题,并且直接、清晰地向面试官表达你的想法,你的表现肯定会得到面试官的认可。
https://www.jiuzhang.com/qa/627/
设计一个只读的lookup service. 后台的数据是10 billion个key-value pair, 服务形式是接受用户输入的key,返回对应的value。已知每个key的size是0.1kB,每个value的size是1kB。要求系统qps >= 5000,latency < 200ms.
server性能参数需要自己问,我当时只问了这些,可能有需要的但是没有问到的……
commodity server
8X CPU cores on each server
32G memory
6T disk
使用任意数量的server,设计这个service。
Google 有一个基础的数据结构 SSTable(Sorted String Table), 是一个简单的抽象,用来高效地存储大量的键-值对数据,同时做了优化来实现顺序读/写操作的高吞吐量。SSTable 就是用来支持大量的读操作。这个设计题就是让你设计SSTableService。:)

given 10 billion key-value pair
=> total key size ~ 10 billion * 0.1kB = 1T
=> total value size ~ 10 billion * 1kB = 10T
Since it's read only, so SSTable is suitable in this case rather than NoSQL. 
with 6T disk , a server with two disks will be enough.
For every request, 1 value, which is 1kB needs to be returned.
According to https://fusiontables.google.com/DataSource?snapid=S523155yioc
total time for reading one value will be 10ms(disk seek) + 1kB/1MB * 30ms(reading 1kB sequentially from disk) = 10ms. 
QPS on 1 server will be 1s/10ms * 2 disk = 200
required QPS support is 5000. So we need 5000/200 = 25 servers.
And for latency, there are several things need to be considered: finding the key, read the value, return the value.
Using binary search, we need log(n) times to find the key. For each time, the disk latency is 1 seek plus 1 read, reading key is really small, so can be ignored. So total time for find the key is log(10billion) * 10ms = 100ms.
Reading a key will take another disk seek , 10ms.
1 round trip in the same data center is 0.5ms.
Assume network bandwidth is 1Gbps, sending 1kB will take very short time, so it's ignored.
so total latency is 100 + 10 + 0.5 = 110.5ms.

Labels

Review (551) System Design (282) System Design - Review (188) Java (177) Coding (75) Interview-System Design (65) Book Notes (59) Coding - Review (59) Interview (59) to-do (45) Knowledge (39) Linux (38) Interview-Java (35) Knowledge - Review (32) Database (29) Design Patterns (29) Product Architecture (28) Big Data (26) Miscs (25) Concurrency (24) Cracking Code Interview (24) MultiThread (24) Soft Skills (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Distributed (20) Interview Q&A (20) OOD Design (20) System Design - Practice (19) How to Ace Interview (15) Security (15) Brain Teaser (14) Algorithm (13) Linux - Shell (13) Spark (13) Spring (13) Code Quality (12) How to (12) Interview-Database (12) Interview-Operating System (12) Tools (12) Architecture Principles (11) Company - LinkedIn (11) Google (11) Redis (11) Resource (10) Testing (10) Amazon (9) Search (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cache (8) Company - Uber (8) Interview - MultiThread (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Scalability (8) Solr (8) Git (7) Interview Corner (7) JVM (7) Java Basics (7) Machine Learning (7) NoSQL (7) C++ (6) Design (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) Trouble Shooting (6) CareerCup (5) Cassandra (5) Code Review (5) Company - Facebook (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Kafka (5) Leetcode (5) Must Known (5) Be Architect (4) Big Fata (4) C (4) Company Product Architecture (4) Design Principles (4) Facebook (4) GeeksforGeeks (4) Generics (4) Google Interview (4) Hardware (4) JDK8 (4) Optimization (4) Product + Framework (4) Shopping System (4) Source Code (4) Web Service (4) node.js (4) Back-of-Envelope (3) Company - Pinterest (3) Company - Twiiter (3) Company - Twitter (3) Consistent Hash (3) Data structures (3) GOF (3) Game Design (3) GeoHash (3) Growth (3) Guava (3) Interview-Big Data (3) Interview-Linux (3) Interview-Network (3) Java EE Patterns (3) Javarevisited (3) Map Reduce (3) Math - Probabilities (3) Performance (3) Puzzles (3) Python (3) Resource-System Desgin (3) Scala (3) UML (3) geeksquiz (3) AI (2) API Design (2) AngularJS (2) Behavior Question (2) Bugs (2) Coding Interview (2) Company - Netflix (2) Crawler (2) Cross Data Center (2) Data Structure Design (2) Database-Shard (2) Debugging (2) Docker (2) Elasticsearch (2) Garbage Collection (2) Go (2) Hadoop (2) Html (2) Interview - Soft Skills (2) Interview-Miscs (2) Interview-Web (2) JDK (2) Logging (2) POI (2) Papers (2) Programming (2) Project Practice (2) Random (2) Software Desgin (2) System Design - Feed (2) Thread Synchronization (2) Video (2) ZooKeeper (2) reddit (2) Ads (1) Advanced data structures (1) Algorithm - Review (1) Android (1) Approximate Algorithms (1) Base X (1) Bash (1) Books (1) C# (1) CSS (1) Chrome (1) Client-Side (1) Cloud (1) CodingHorror (1) Company - Yelp (1) Counter (1) DSL (1) Dead Lock (1) Difficult Puzzles (1) Distributed ALgorithm (1) Eclipse (1) Facebook Interview (1) Function Design (1) Functional (1) GoLang (1) How to Solve Problems (1) ID Generation (1) IO (1) Important (1) Internals (1) Interview - Dropbox (1) Interview - Project Experience (1) Interview Tips (1) Interview-Brain Teaser (1) Interview-How (1) Interview-Mics (1) Interview-Process (1) Jeff Dean (1) Joda (1) LeetCode - Review (1) Library (1) LinkedIn (1) Mac (1) Micro-Services (1) Mini System (1) MySQL (1) Nigix (1) NonBlock (1) Process (1) Productivity (1) Program Output (1) Programcreek (1) Quora (1) RPC (1) Raft (1) RateLimiter (1) Reactive (1) Reading (1) Reading Code (1) Resource-Java (1) Resource-System Design (1) Resume (1) SQL (1) Sampling (1) Shuffle (1) Slide Window (1) Spotify (1) Stability (1) Storm (1) Summary (1) System Design - TODO (1) Tic Tac Toe (1) Time Management (1) Web Tools (1) algolist (1) corejavainterviewquestions (1) martin fowler (1) mitbbs (1)

Popular Posts