Netflix的系统设计

NETFLIX, YOUTUBE和SPOTLIGHT系统设计SNAKE分析
	宏观角度		微观角度
功 能 分 析	罗列功能 对所有功能进行排序 设计最重要的功能：播放电影		设计某个小模块 比如电影推荐 设计接口和方法
限 制 条 件 和 假 设	USER	·         Daily Active Users       ·         Average Concurrent Users       ·         Peak Users       ·         Max Peak Users in 3 month	对方法的调用频率进行计算 计算QPS 计算需要多少server达到所需QPS
	TRAFFIC	·         Traffic per user 3mpbs       ·         Max Peak Traffic in 3 month
	MEMORY	·         Memory per user 10k       ·         Max Daily Memory if double in 3 month
	STORAGE	·         Total Number of movies       ·         Calculate total storage usage considering different quality of movies
应 用 架 构 和 算 法	应用设计模式的知识设计系统Service结构 （MVC架构）		算法和数据结构
数 据 层 设 计	Model DAO不同文件不同数据库选择 （MySQL 和 MongoDB 以及 File）		改进算法和数据结构提高QPS
系 统 演 化	改进效率，扩充性，鲁棒性		改进效率，扩充性，鲁棒性

GFS阅读笔记

== 文章结构 ==
Abstract
1. Introduction
2. Design Overview
   2.1 Assumptions
   2.2 Interface
   2.3 Architecture
   2.4 Single Master
   2.5 Chunck Size
   2.6 Metadata
      2.6.1 In Memory Data Structures
      2.6.2 Chunk Locations
      2.6.3 Operation Log
   2.7 Consistency Model
      2.7.1 Guarantees by GFS
      2.7.2 Implications for Applications
3. System Interactions
   3.1 Leases and Mutation Order
   3.2 Data Flow
   3.3 Atomic Record Appends
   3.4 Snapshot
4. Master Operation
   4.1 Namespace Management and Locking
   4.2 Replica Placement
   4.3 Creation, Re-replication, Rebalancing
   4.4 Garbage Collection
      4.4.1 Mechanism
      4.4.2 Discussion
   4.5 Stale Replica Detection
5. Fault Tolerance and Diagnosis
   5.1 High Availability
      5.1.1 Fast Recovery
      5.1.2 Chunk Replication
      5.1.3 Master Replication
   5.2 Data Integrity
   5.3 Diagnostic Tools
6. Measurements
   6.1 Micro-benchmarks
      6.1.1 Reads
      6.1.2 Writes
      6.1.3 Record Appends
   6.2 Real World Clusters
      6.2.1 Storage
      6.2.2 Metadata
      6.2.3 Read and Write Rates
      6.2.4 Master Load
      6.2.5 Recovery Time
   6.3 Workload Breakdown
      6.3.1 Methodology and Caveats
      6.3.2 Chunkserver Workload
      6.3.3 Appends versus Writes
      6.3.4 Master Workload
7. Experience
8. Related Work
9. Conclusions

== 1. 背景介绍 ==

1. Component Failure are norm rather than exception.
2. Files are huge than traditional standards.
3. Most data are mutated by appending new data rather than overwriting existing data.
4. Co-designing the applications and the file system API benefits the overall system by increasing our flexibility

== 2. 设计概要 ==

1. 前提假设
   a) The system is built from many inexpensive commodity components that often fail.
   b) The system stores a modest number of large files.
   c) The workloads primarily consist of two kinds of reads:large streaming reads and small random reads.
   d) The workloads also have many large, sequential writes that append data to files.
   e) The system must efficiently implement well-defined semantics for multiple clients that concurrently append to the same file.
   f) High sustained bandwidth is more important than low latency.

2. 接口
   a) GFS provides a familiar file system interface which supports the usual operations to create, delete, open, close, read, and write files.
   b) Snapshot creates a copy of a file or a directory tree at low cost.
   c) Record append allows multiple clients to append data to the same file concurrently while guaranteeing the atomicity of each individual client’s append.

3. 架构





   a) A GFS cluster consists of a single master and multiple chunkservers and is accessed by multiple clients.
   b) Each of these is typically a commodity Linux machine running a user-level server process.
   c) Files are divided into fixed-size chunks.
       Each chunk is identified by an immutable and globally unique 64 bit chunk handle assigned by the master at the time of chunk creation.
       Each chunk is replicated by default 3 replicas on multiple chunkservers.
   d) The master maintains all file system metadata including the namespace, access control information, the mapping from files to chunks,
       and the current locations of chunks.
   e) It also controls system-wide activities such as chunk lease management, garbage collection of orphaned chunks, and chunk migration between
       chunkservers.
   f) The master periodically communicates with each chunkserver in HeartBeat messages to give it instructions and collect its state.
   g) Clients interact with the master for metadata operations, but all data-bearing communication goes directly to the chunkservers.
   h) Neither the client nor the chunkserver caches file data because most applications stream through huge files or have working sets too large to be cached.

4. 单主服务器策略

   a) Clients never read or write file data through master.
   b) Instead Clients ask the master which chunkserver it should contact.
   c) The client will cache the information until it expires.
   d) So when accessing start, client already know which chunkserver it needs to access.
   e) It will first send out request to master, master will reply with a chunk handle and location of replicas.
   f) The client will send request to 1 of the replicas which is the closest one.

5. 块大小的选择 (64MB)

优点：
   a) Reduce client's need to interact with Master.
   b) Reduce network overhead by keep a persistent TCP connection to the chunkserver over an extended period of time.
   c) Reduce size of metadata on Master.

缺点：Small file like only 1 chunk size will be hot spots if many clients are accessing the same file.
临时解决方案：多备份，默认3个备份可以提高到100等等。
长期解决方案：允许client间相互传送数据。
 

系统设计总结

转载

我的面试也结束了 因为知道FLAG这类公司都会问到System Design的问题 所以这次面试着重准备了一下 在这里分享给大家 如果有不对或者需要补充的地方 大家可以留言

这里说的System Design和OO Design不同 System Design在FLAG以及很多大公司中主要是design scalable distributed systems 这里只讨论如何准备这种题目

== 入门 ==
对于0基础的同学们 下面的资料可以按顺序开始看
1. http://www.hiredintech.com/app#system-design
这是一个专门准备面试的网站 你只用关心system design部分 有很多的link后面会重复提到 建议看完至少一遍

2. https://www.youtube.com/watch?v=-W9F__D3oY4
非常非常好的入门资料 建议看3遍以上！
这是1里面提到的资料 是Harvard web app课的最后一节 讲scalability 里面会讲到很多基础概念比如Vertical scaling, Horizontal scaling, Caching, Load balancing,Database replication, Database partitioning 还会提到很多基本思想比如avoid single point of failure
再强调一遍 非常好的资料！

3. http://www.lecloud.net/post/7295452622/scalability-for-dummies-part-1-clones
1里面提到的 Scalability for Dummies 还算不错 可以看一遍 知道基本思想

结束语：当你结束这一部分的学习的时候 你已经比50%的candidate知道的多了(因为很多人都不准备 或者不知道怎么准备system design) 恭喜

== 进阶 ==
这一部分的资料更加零散 每个看的可能不一样 但是你每多看一篇文章或者一个视频
你就比别人强一点
这部分你会遇到很多新名词 我的建议是每当你遇到一个不懂的概念时 多google一下
看看这个概念或者技术是什么意思 优点和缺点各是什么 什么时候用 这些你都知道以
后 你就可以把他运用到面试中 让面试官刮目相看了

4. http://highscalability.com/blog/ ... -coming-of-the.html
Database Sharding是一个很重要的概念 建议看一看

5. http://highscalability.com/all-time-favorites/
这个里面会讲到很多非常流行的网站架构是如何实现的 比如Twitter, Youtube,
Pinterest, Google等等 我的建议是看5-6个 然后你应该已经建立起了一些基本的意识
还有知道了某些技术和产品的作用和mapping 比如说到cache你会想到memcached和
Redis 说到
load balancer你会想到 Amazon ELB, F5一类的

6. http://www.infoq.com/
5里面很多的文章都会有链接 其中有很多会指向这个网站 这里面有很多的tech talk
很不错 可以看看

7. https://www.facebook.com/Engineering/notes
Facebook非常好的技术日志 会讲很多facebook的feature怎么实现的 比如facebook
message:https://www.facebook.com/notes/f ... ing/the-underlying-
technology-of-messages/454991608919 建议看看 尤其是准备面facebook的同学

8. 一些国内网站上的资料
http://blog.csdn.net/sigh1988/article/details/9790337
http://blog.csdn.net/v_july_v/article/details/6279498

9. 最后一些概念很有用 都是我再看这些资料的时候发现的 如果你没有遇到或者查过
建议查查
Distributed Hash Table
Eventual Consistency vs Strong Consistency
Read Heavy vs Write Heavy
Consistent Hashing

== 小结＝＝
看多了以后 你的最终目标应该是心里有了一个大框架 一个基本的distributed system
是怎么搭起来的 然后心里有很多if condition 如果要是满足这个条件 我应该用什么
技术 比如如果read heavy那么用cache会提升performance之类的 同时知道应该避免什
么东西 比如避免single point of failure 再比如时间和空间的tradeoff在read
heavy的时候应该倾向于时间 Write heavy的时候倾向于空间等等

你总结出来的和我总结出来的大框架和if conditions肯定不完全一样 但因为system
design本来就是一个open ended question 所以不用害怕 能够自圆其说 就不会有问题

最后 本文纯属抛砖引玉 如果有大牛发现有错误或者有补充 欢迎留言 大家一起讨论

== FAQ ==
1. New Grad需要看System Design么?
答案是it depends. 有的公司会考system design 有的公司只考到OO design 有的公司
压根不考 当然 考到的公司对new grad的期望值会稍微低一点 但是 你有这么一个机会
能让你gain leverage over other candidates why not? 为什么要让自己在面试前害怕
面试官出system design的题目呢?

系统设计知识考察点

比如面向对象，接口设计，设计模式，数据库表，分布式。

首先在性能耗在什么地方之前不要优化。所谓杞人忧天，你不是百度或者facebook的流量，根本考虑不到很多细节，大多数直接用云计算平台，直接帮你做了。但面试中还是会考察。

这里就针对Scalability，有一些常见的优化技术，我就把他们列出。

Cache：缓存，万金油，哪里不行优先考虑
Queue：消息队列，常见使用Linkedin的kafka
Asynchronized：批处理＋异步，减少系统IO瓶颈
Load Balance: 负载均衡，可以使用一致性hash技术做到尽量少的数据迁移
Parallelization：并行计算，比如MapReduce
Replication：提高可靠性，如HDFS，基于位置感知的多块拷贝
Partition：数据库sharding，通过hash取摸

系统设计面试题思路综述

转载

在面试的时候，偶尔也会遇到一些系统设计题，而这些题目往往只是考一下你的知识面，或者对系统架构方面的了解，不会涉及编码。很多人感觉难以应对这样的题目，也不知道从何说起，在本文中，作者总结了回答这类题目需要哪些基础知识，以及怎样使用这些知识回答这些问题。由于作者写本篇文章时仅是一个刚找完工作的研三学生，还未真正参与设计过已经投入使用的系统，因此难免写得过于片面或者肤浅，请即将找工作的师弟师妹们仅作参考。

在正式介绍基础知识之前，我先罗列几个常见的系统设计相关的笔试面试题。
(1) 要求设计一个DNS的Cache结构，要求能够满足每秒5000以上的查询，满足IP数据的快速插入，查询的速度要快。（题目还给出了一系列的数据，比如：站点数总共为5000万，IP地址有1000万，等等）
(2) 有N台机器，M个文件，文件可以以任意方式存放到任意机器上，文件可任意分割成若干块。假设这N台机器的宕机率小于1/3，想在宕机时可以从其他未宕机的机器中完整导出这M个文件，求最好的存放与分割策略。
(3) 假设有三十台服务器，每个上面都存有上百亿条数据（有可能重复），如何找出这三十台机器中，根据某关键字，重复出现次数最多的前100条？要求用Hadoop来做。
(4) 设计一个系统，要求写速度尽可能高，说明设计原理。
(5) 设计一个高并发系统，说明架构和关键技术要点。
(6) 有25T的log(query->queryinfo)，log在不段的增长，设计一个方案，给出一个query能快速反回queryinfo

以上所有问题中凡是不涉及高并发的，基本可以采用google的三个技术解决，分别为：GFS，MapReduce，Bigtable，这三个技术被称为“google三驾马车”，google只公开了论文而未开源代码，开源界对此非常有兴趣，仿照这三篇论文实现了一系列软件，如：Hadoop、HBase、HDFS、Cassandra等。

在google这些技术还未出现之前，企业界在设计大规模分布式系统时，采用的架构往往是database+sharding+cache，现在很多公司（比如taobao，weibo.com）仍采用这种架构。在这种架构中，仍有很多问题值得去探讨。如采用什么数据库，是SQL界的MySQL还是NoSQL界的Redis/TFS，两者有何优劣？ 采用什么方式sharding（数据分片），是水平分片还是垂直分片？据网上资料显示，weibo.com和taobao图片存储中曾采用的架构是Redis/MySQL/TFS+sharding+cache，该架构解释如下：前端cache是为了提高响应速度，后端数据库则用于数据永久存储，防止数据丢失，而sharding是为了在多台机器间分摊负载。最前端由大块大块的cache组成，要保证至少99%（该数据在weibo.com架构中的是自己猜的，而taobao图片存储模块是真实的）的访问数据落在cache中，这样可以保证用户访问速度，减少后端数据库的压力，此外，为了保证前端cache中数据与后端数据库中数据一致，需要有一个中间件异步更新（为啥异步？理由简单：同步代价太高。异步有缺定，如何弥补？）数据，这个有些人可能比较清楚，新浪有个开源软件叫memcachedb（整合了Berkeley DB和Memcached），正是完成此功能。另外，为了分摊负载压力和海量数据，会将用户微博信息经过片后存放到不同节点上（称为“sharding”）。
这种架构优点非常明显：简单，在数据量和用户量较小的时候完全可以胜任。但缺定早晚一天暴露出来，即：扩展性和容错性太差，维护成本非常高，尤其是数据量和用户量暴增之后，系统不能通过简单的增加机器解决该问题。

于是乎，新的架构便出现了。主要还是google的那一套东西，下面分别说一下：

GFS是一个可扩展的分布式文件系统，用于大型的、分布式的、对大量数据进行访问的应用。它运行于廉价的普通硬件上，提供容错功能。现在开源界有HDFS(Hadoop Distributed File System)，该文件系统虽然弥补了数据库+sharding的很多缺点，但自身仍存在一些问题，比如：由于采用master/slave架构，因而存在单点故障问题；元数据信息全部存放在master端的内存中，因而不适合存储小文件，或者说如果存储的大量小文件，那么存储的总数据量不会太大。

MapReduce是针对分布式并行计算的一套编程模型。他最大的优点是：编程接口简单，自动备份（数据默认情况下会自动备三份），自动容错和隐藏跨机器间的通信。在Hadoop中，MapReduce作为分布计算框架，而HDFS作为底层的分布式存储系统，但MapReduce不是与HDFS耦合在一起的，你完全可以使用自己的分布式文件系统替换掉HDFS。当前MapReduce有很多开源实现，如Java实现Hadoop MapReduce，C++实现Sector/sphere等，甚至有些数据库厂商将MapReduce集成到数据库中了。

BigTable俗称“大表”，是用来存储结构化数据的，个人觉得，BigTable在开源界最火爆，其开源实现最多，包括：HBase，Cassandra，levelDB等，使用也非常广泛。

除了google的这三家马车，还有其他一些技术：

Dynamo：亚马逊的key-value模式的存储平台，可用性和扩展性都很好，采用DHT（Distributed Hash Table）对数据分片，解决单点故障问题，在Cassandra中，也借鉴了该技术，在BT和电驴的中，也采用了类似算法。

虚拟节点技术：该技术常用于分布式数据分片中。具体应用场景是：有一大坨数据（maybe TB级或者PB级），我们需按照某个字段（key）分片存储到几十（或者更多）台机器上，同时想尽量负载均衡且容易扩展。传统的做法是：Hash(key) mod N，这种方法最大缺点是不容易扩展，即：增加或者减少机器均会导致数据全部重分布，代价忒大。于是乎，新技术诞生了，其中一种是上面提到的DHT，现在已经被很多大型系统采用，还有一种是对“Hash(key) mod N”的改进：假设我们要将数据分不到20台机器上，传统做法是hash(key) mod 20，而改进后，N取值要远大于20，比如是20000000，然后我们采用额外一张表记录每个节点存储的key的模值，比如：
node1：0~1000000
node2：1000001~2000000
。。。。。。
这样，当添加一个新的节点时，只需将每个节点上部分数据移动给新节点，同时修改一下这个表即可。

Thrift：Thrift是一个跨语言的RPC框架，分别解释一下“RPC”和“跨语言”，RPC是远程过程调用，其使用方式与调用一个普通函数一样，但执行体发生在远程机器上。跨语言是指不同语言之间进行通信，比如c/s架构中，server端采用C++编写，client端采用PHP编写，怎样让两者之间通信，thrift是一种很好的方式。

文章最前面的几道题均可以映射到以上几个系统中的某个模块中，如：

（1） 关于高并发系统设计。主要有以下几个关键技术点：缓存，索引，数据分片，锁粒度尽可能小。

（2） 问题2涉及到现在通用的分布式文件系统的副本存放策略。一般是将大文件切分成小的block（如64MB）后，以block为单位存放三份到不同的节点上，这三份数据的位置需根据网络拓扑结构配置，一般而言，如果不考虑跨数据中心，可以这样存放：两个副本存放在同一个机架的不同节点上，而另外一个副本存放在另一个机架上，这样从效率和可靠性上，都是最优的（这个google公布的文档中有专门的证明，有兴趣的可参阅一下。）。如果考虑跨数据中心，可将两份存在一个数据中心的不同机架上，另一份放到另一个数据中心。

（3）问题4涉及到BigTable的模型。主要思想是将随机写转化为顺序写，进而大大提高写速度。具体是：由于磁盘物理结构的独特设计，其并发的随机写（主要是因为磁盘寻道时间长）非常慢，考虑到这一点，在BigTable模型中，首先会将并发写的大批数据放到一个内存表（称为“memtable”）中，当该表大到一定程度后，会顺序写到一个磁盘表（称为“SSTable”）中，这种写是顺序写，效率极高。说到这，可能有读者问，随机读可不可以这样优化？答案是：看情况。通常而言，如果读并发度不高，则不可以这么做，因为如果将多个读重新排列组合后再执行，系统的响应时间太慢，用户可能接受不了，而如果读并发度极高，也许可以采用类似机制。

SDE面试技巧之一：OOA & OOD

这里不讨论OOA和OOD的具体技术，这里只是讨论面试过程中如何问、如何答。在掌握了OOD的具体技术后，要想面试成功，还需要掌握面试技巧。OOD的面试的时要特别注意Clarify the ambiguity，以避免你的设计既可以满足需求，又不会over design。

下面这一段摘自：http://www.nomachetejuggling.com/2010/04/06/avoiding-the-big-design-interview-question/，我觉得作者写的挺好的。

How To Ask This Question
If you want to know how comfortable a candidate is with OO, ask them the question in a way that resembles real-life OOP a bit more closely. Start simple, by providing a single simple requirement. Though the candidate won’t be able to write and run tests, the requirement serves as a driver for the design.
A good indicator that the question is taking you and the candidate off-track is if the boxes he or she draws on the whiteboard lack method names. If there are no methods, there are no behaviors, which means the candidate is designing first, regardless of requirements. Steer the candidate back by asking them to write method names.
For example, ask the candidate to design the object model for a simple bookshelf. A bookshelf is so simple that there’s virtually no way to overcomplicate it, so you can say that you simply need to be able to add a book to the bookshelf, nothing else. Once they have done this, give the candidate another “test”, by adding a requirement. Now say that you want the bookshelf to be a “smart” bookshelf, where you can look up a book by title and get a reference to the book. The candidate will make some changes to their design. Continue adding requirements to the thing until you’re satisfied with the evolution of the candidate’s design.

• Modify the design to allow me to search the bookshelf by Title, Author, or ISBN.
• Allow me to use the bookshelf as an ad-hoc library, so I can “check out” a book, removing it from the bookshelf. Make it possible to look up books that have been “borrowed”.
• Require a user provide their name when checking out a book. Give them a return date.
• Make it so the bookshelf can generate a list of overdue books and who has them. Where does that method belong? Should it be on its own object that Bookshelf uses?Make the bookshelf more concrete, so that there is only a certain number of books that can fit on any given shelf in the overall bookshelf. Make it possible to ask which shelf a book is on. Make it possible to add a new shelf.

You can obviously pick your own model (Car, Elevator, Fridge, etc) and drive the direction the design should go using requirements. Have the candidate write method names (but not implementations) where appropriate. Keep asking if the method is on the right object, or it belongs on another one.

How To Answer This Question
Of course, not everyone reads this blog, so if you’re in an interview you may get the “design an object model for a x” question. If you find yourself in this situation, you essentially want to ask questions of your interviewer to pull requirements out of them. The reality is, they probably DO have a particular kind of system in mind when they ask the question, so you need to find out what that is.
If you’re supposed to design the Car class, ask if there are other types of vehicles in the system. If not, don’t make a Vehicle parent class, and explain that you see no need unless the system required additional vehicles. Before you draw a box named Tire, ask if the car needs to be able to support snow tires or some other kind of interchangeable tire. If not, why would you make a class or interface for them? Start as simply as you can and only draw a new box when you’ve extracted enough information from the interviewer to deem it warranted. If you jump up to the whiteboard and draw two or three boxes before asking any questions, you’re placing your interview at risk because the interviewer may be picturing a completely different usage of this system than you are.
Of course, it’s always possible that the interviewer will keep asking for the same information, arguing that you should show your OO skills off without requirements that drive that design out. If you want the job, your best bet there is to take a random stab at the appropriate level of complexity and hope that you strike somewhere near what the interviewer wants. In that situation, however, I’d imagine your interviewer doesn’t know much about designing good software, and their codebase might be an over-engineered mess, so you may not want that job.

总体而言，我觉得面试的时候，应该是根据面试官的要求进行设计，废话？不！！！根据我个人的理解，设计是服务于特定目标的，没有哪个设计是可以满足所有场景的需要，因此在设计一个类或者考虑要不要继承时，就需要知道设计目标和场景，而这是完全来源于面试官的要求。如果面试官没有说，你想到的可以问，但不能自己进行假设。因为OOD中最主要的考察点就是看应聘者能不能发现那些不明确的、模棱两可的地方，通过问面试官的方式进行clarify。所以OOD面试题中，最重要的就是：不要自己假设，在考虑应不应该使用某种设计时，问面试官以确定各种条件是否符合！

http://www.cnblogs.com/whyandinside/archive/2012/10/26/2740612.html

100 most frequently used string in 24 hours

Design a queue using array