Thursday, October 29, 2015

System Design Misc



http://www.1point3acres.com/bbs/thread-148865-1-1.html
4. Pirate. Design Wikipedia crawler.
                  followup 1: No global status.
                  followup 2: deal with machine failure
                  followup 3: make the wiki site unaware of this crawler.
1. distributed bfs
2. consistent hashing
3. assign task with a random delay

http://codeinterviews.com/System-Design-Preparation/

http://blog.csdn.net/longyulu/article/details/9159589

System Design

Here are some articles about system design related topics.
  • How to Rock a Systems Design Interview
  • System Interview
  • Scalability for Dummies
  • Scalable Web Architecture and Distributed Systems
  • Numbers Everyone Should Know
  • Scalable System Design Patterns
  • Introduction to Architecting Systems for Scale
  • Transactions Across Datacenters
  • A Plain English Introduction to CAP Theorem
  • The CAP FAQ
  • Paxos Made Simple
  • Consistent Hashing
  • NOSQL Patterns
  • Scalability, Availability & Stability Patterns

Hot Questions and Reference:
There are some good references for each question. The references here are slides and articles.

Design a CDN network
Reference:
Globally Distributed Content Delivery.
Design a Google document system
Reference:
google-mobwrite
Differential Synchronization.
Design a random ID generation system
Reference:
Announcing Snowflake
snowflake.
Design a key-value database
Reference:
Introduction to Redis.
Design the Facebook news seed function
Reference:
What are best practices for building something like a News Feed?
http://www.weiming.info/zhuti/JobHunting/32463885/
What are the scaling issues to keep in mind while developing a social network feed?
Activity Feeds Architecture
Design the Facebook timeline function
Reference:
Building Timeline
Facebook Timeline.
Design a function to return the top k requests during past time interval
Reference:
Efficient Computation of Frequent and Top-k Elements in Data Streams
An Optimal Strategy for Monitoring Top-k Queries in Streaming Windows
Design an online multiplayer card game
Reference:
How to Create an Asynchronous Multiplayer Game
How to Create an Asynchronous Multiplayer Game Part 2: Saving the Game State to Online Database
How to Create an Asynchronous Multiplayer Game Part 3: Loading Games from the Database
How to Create an Asynchronous Multiplayer Game Part 4: Matchmaking
Real Time Multiplayer in HTML5
Design a graph search function
Reference:
Building out the infrastructure for Graph Search
Indexing and ranking in Graph Search
The natural language interface of Graph Search and Erlang at Facebook.
Design a picture sharing system
Reference:
Flickr Architecture
Instagram Architecture.
Design a search engine
Reference:
How would you implement Google Search?
Implementing Search Engines
Design a recommendition system
Reference:
Hulu’s Recommendation System
Recommender Systems
Design a tinyurl system
Reference:
System Design for Big Data-tinyurl
URL Shortener API.
Design a garbage collection system
Reference:
Baby’s First Garbage Collector.
Design a scalable web crawling system
Reference:
Design and Implementation of a High-Performance Distributed Web Crawler
Design the Facebook chat function
Reference:
Erlang at Facebook
Facebook Chat
http://www.cnblogs.com/piaoger/archive/2012/08/19/2646530.html
Design a trending topic system
Reference:
Implementing Real-Time Trending Topics With a Distributed Rolling Count Algorithm in Storm
Early detection of Twitter trends explained
http://www.cnblogs.com/lautsie/p/3332347.html
无锁队列
CAS操作——Compare & Set,或是 Compare & Swap,现在几乎所有的CPU指令都支持CAS的原子操作。
1)无锁队列主要是通过CAS、FAA这些原子操作,和Retry-Loop实现。这些技术都可以用在其它的无锁数据结构上。
2)对于Retry-Loop,其实和锁什么什么两样。只是这种“锁”的粒度变小了,主要是“锁”HEAD和TAIL这两个关键资源。而不是整个数据结构。
数据库Sharding
Sharding的基本思想就要把一个数据库切分成多个部分放到不同的数据库(server)上,从而缓解单一数据库的性能问题。不太严格的讲,对于海量数据的数据库,如果是因为表多而数据多,这时候适合使用垂直切分,即把关系紧密(比如同一模块)的表切分出来放在一个server上。如果表并不多,但每张表的数据非常多,这时候适合水平切分,即把表的数据按某种规则(比如按ID散列)切分到多个数据库(server)上。当然,现实中更多是这两种情况混杂在一起。
http://www.jiuzhang.com/interview/42/
最后讨论了一道design,如何设计distributed key-value store,因为他们主要用HBase。
Validate Soduko Solution,从文件读solution,尽量用production标准写程序。
五轮Onsite没有coding,全是问实际问题怎么解决和design。
1. 如何设计一个priorityqueue service,client可以submit job request然后server按照priority执行
2. 需要一个key-value store with 1M qps,most read,1ms 99% latency,如果用HBase的话会有什么问题,怎么解决
3. 给很多整数,如何用mapreduce找median,如果是很多float数,可以有一定的误差,如何找
4. Programming Test的扩展,如果soduku matrix非常之大怎么做
http://myprogrammingpractices.blogspot.com/2015_06_01_archive.html
Design题一靠平常积累,二靠多看open source stack,当然要看细节和实现,光知道
大概没用的。
when a new version of API 上线,怎么和client side 协调好切换版本,出问题了rollback 怎么做。
http://myprogrammingpractices.blogspot.com/2015/06/from-mitbbs-facebooklinkedin-google.html
   4. system design: 每个record有个很大field,比如年龄,性别,爱好等。给一个
field的组合,比如小于25岁,爱好体育,query满足这些组合条件的用户个数



http://prismoskills.appspot.com/lessons/System_Design_and_Big_Data/Chapter_06_-_System_Design.jsp
When designing a complete system, we need to consider the following components' detail:
  1. Storage (Database)
  2. Cache
  3. High Availability - Have some redundant nodes running in active/active mode.
  4. Cross country replication - To serve data closer to the user-machine like Akamai
  5. Service Level Agreement (SLA): Time required to reflect the changes made in the system
  6. Use a load balancer if one server is not sufficient
  7. Try to put queuing systems for asynchronous consumption of offline loads.
  8. Find out the columns you want to index if using an RDBMS. Find out the memory required by those indexes.
    If indexes per machine are taking more than 10-100 GB per machine, then you have to shard the DB.
  9. If read traffic is very high than write traffic, it may be a good idea to increase some slaves replicas.
    Slave replicas will only respond to read traffic but will keep themselves updated by getting data from the server.
Statelessness for scalability

Make sure your servers are stateless.
That ways a load balancer can send requests to any server (maybe in a round robin fashion)
To do this, all the state information must be kept in the database.
This includes session information as well.
However, since session information must be available extremely fast, it is best to keep
this information in a distributed cache.

If servers cannot be made stateless, then the load-balancer must be made smarter.
It should route stateful requests to the proper server.
This is done by making the load balancer inspect the session-ID of each request and
matching that with the appropriate server.

Load balancer (Also called "Reverse Proxy")
RP systems hide the internal topology from outside clients and in doing so they can provide several features:
Caching static content
Load balancing
Firewalling
Compression
Logging

A load balancer is useful not only for load balancing, but it also brings:
Redundancy and tolerance to machine failures
Elastic load-balancers can shut-down some of the servers during non-peak hours.

vmtouch
vmtouch is an application to see what is currently cached by the system.
Its a very simple c program in one file only and can help to see, remove or put things into cache.
http://blog.csdn.net/sparkliang/article/details/7260267
一旦系统达到了一定的规模,很多看起来本该不是问题的问题也会一个一个接连跳出来。
而更麻烦的是这些问题在刚开始可能根本就没有被考虑过。
特别是分布式集群系统。
前面提到过系统透明度的问题,这是其中一个,另一个密切相关的就是系统日志的存储与查询问题。
小规模集群的情况下,使用一个单主机可能就够了。
大规模用户的情况下,系统产生的日志可能会把系统淹没掉。
仅仅是那些必须记录的重要性日志,其产生速度和需要的存储量,都已不是T级的存储能够解决的了。

http://zhuanlan.zhihu.com/prattle/20005177
MVP(Minimal Viable Produce)在很多团队里演化成一个形而上的图腾,于是工程师们找到了一个完美的借口:我先做个MVP,设计的事,以后再说。


设计首先得搞懂要解决的问题

工程师大多都是很聪明的人,聪明人有个最大的问题就是自负。很多人拿到一个需求,还没太搞明白其外延和内涵,代码就已经在脑袋里流转。这样做出来的系统,纵使再精妙,也免不了承受因需求理解不明确而导致的返工之苦。搞懂需求这事,说起来简单,做起来难。需求有正确的但表达错误的需求,有正确的但没表达出来的需求,还有过度表达的需求。所以,拿到需求后,先不忙寻找解决方案,多问问自己,工作伙伴,客户follow up questions来澄清需求模糊不清之处。
澄清需求的过程,就是不断驱逐无知,掌握现状,上下文和约束条件的过程。

寻找(多个)解决方案
构建灵活且有韧性的系统

分解和组合
软件设计是一个把大的问题不断分解,直至原子级的小问题,然后再不断组合的过程.
一个如此组合而成系统,是满足关注点分离(Separation of Concerns)的.

总线(System Bus)
经典的PC结构有几种总线:数据总线,地址总线,控制总线,扩展总线等;做过网络设备的同学也都知道,一个经典的网络设备,其软件系统的总线分为:control plane和data plane。
路由(routing)
队列(Queue)对于那些并非需要立即处理的数据,可以使用队列。队列也有把生产者和消费者分离的功效
Pub/Sub

透支保护(overdraft protection)
在无法auto scaling的场景最通用的做法是back pressure,把压力反馈到源头。就好像你不断熬夜,最后大脑受不了,逼着你睡觉一样。还有一种做法是服务降级,停掉非核心的service/micro-service,如analytical service,ad service,保证核心功能正常。

把设计的成果讲给别人听
要把设计在白板上画下来,讲给任何一个利益相关者听。听他们的反馈。设计不是一个闭门造车的过程,全程都需要和各种利益相关者交流。然而,很多人都忽视了设计定型后,继续和外界交流的必要性。

设计时的tradeoff
everyone says design is about tradeoffs, but you need to enumerate at least two or more possible solutions, and the attributes and deficits of each, in order to make tradeoff.
http://zhuanlan.zhihu.com/prattle/20578447
请听题:一个使用 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),需要多大的容量,在限定的软硬件条件下,是否能达到这个容量,达不到的话,什么样的上限比较合理。

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


永远不要忘了设计应该是面向未来的,如果通过更换更好的算法,能节省数十倍的内存(bitmap vs hashmap),或者数十倍的运算(bloom filter pre-filter vs raw computation),那么你省下的不仅仅是当下的资源(或者金钱),还有未来的时间 —— 因为,当你的应用有10倍的流量时,你还能够应对自如。
此外,优化可能会从量变转化为质变。一个 analytics 应用如果每五分钟才能完成一次分析,一小时仅能进行 12 次分析;如果将其优化成 30 秒完成,一个小时就可能完成 120 次,用户可以更快地掌握趋势。

Labels

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