system design key word

https://github.com/checkcheckzz/system-design-interview#intro 很好的全面资料
https://github.com/donnemartin/system-design-primer/blob/master/README-zh-Hans.md#nosql

http://www.learn4master.com/interview-questions/system-design/system-design%E9%9D%A2%E8%AF%95 好的资料
SQL vs. NoSQL 
Structured Query Language
Not only SQL 

SQL vs NoSQL

• 是否需要支持 Transaction（事务）？NoSQL不支持Transaction
  • 是否需要丰富的 SQL Query？NoSQL的SQL Query不是太丰富, 也有一些NoSQL的数据库提供简单的SQL Query支持
• 是否想偷懒？
  • 大多数 Web Framework 与 SQL 数据库兼容得很好
  • 用SQL比用NoSQL少写很多代码
• 是否需要Sequential ID？
  • SQL 为你提供了 auto-increment 的 Sequential ID。也就是1,2,3,4,5 …
  • NoSQL的ID并不是 Sequential 的
• 对QPS的要求有多高？
  • NoSQL 的性能更高
• 对Scalability的要求有多高？
  • SQL 需要码农自己写代码来 Scale
  • 还记得Db那节课中怎么做 Sharding，Replica 的么？NoSQL 这些都帮你做了

SQL优点: 

1, 事务处理 保持数据的一致性；（是指访问并可能更新数据库中各种数据项的一个程序执行单元(unit)）

2，由于以标准化为前提，数据更新的开销很小（相同的字段基本上只有一处）；

3，可以进行Join等复杂查询。
缺点：
扩展困难：由于存在类似Join这样多表查询机制，使得数据库在扩展方面很艰难;
读写慢：这种情况主要发生在数据量达到一定规模时由于关系型数据库的系统逻辑非常复杂
成本高：企业级数据库的License价格很惊人，并且随着系统的规模，而不断上升
有限的支撑容量：现有关系型解决方案还无法支撑Google这样海量的数据存储;
NoSQL优点：
1.简单的扩展：典型例子是Cassandra，由于其架构是类似于经典的P2P，所以能通过轻松地添加新的节点来扩展这个集群;
2.快速的读写：主要例子有Redis，由于其逻辑简单，而且纯内存操作，使得其性能非常出色，单节点每秒可以处理超过10万次读写操作;
3.低廉的成本：这是大多数分布式数据库共有的特点，因为主要都是开源软件，没有昂贵的License成本;
缺点：
1. 不提供对SQL的支持：如果不支持SQL这样的工业标准，将会对用户产生一定的学习和应用迁移成本;
2. 支持的特性不够丰富：现有产品所提供的功能都比较有限，大多数NoSQL数据库都不支持事务，也不像MS SQL Server和Oracle那样能提供各种附加功能，比如BI和报表等;
3. 现有产品的不够成熟：大多数产品都还处于初创期，和关系型数据库几十年的完善不可同日而语;

NoSQL

redis vs memcached
redis的基本应用模式和上图memcached的基本相似，不难发现网上到处都是关于redis是否可以完全替代memcached使用的问题。
redis内部的数据结构最终也会落实到key-value对应的形式，不过从暴露给用户的数据结构来看，要比memcached丰富，除了标准的通常意义的键值对，redis还支持List，Set， Hashes，Sorted Set等数据结构。
memcached和redis都属于内存(memory)键-值(key-value)数据库，在设计和思想上有许多相同之处，功能和应用在很多场合(如分布式缓存服务)也相似。它们都从属于数据库解决方案中的nosql家族，由于两者都将数据存储在内存中，自然而然，它们都是非常理想的缓存实现方案。

Database VS file system 
文件系统把数据组织成相互独立的数据文件，实现了记录内的结构性，但整体无结构;而数据库系统实现整体数据的结构化，这是数据库的主要特征之一，也是数据库系统与文件系统的本质区别。
数据库系统主要管理数据库的存储、事务以及对数据库的操作。文件系统是操作系统管理文件和存储空间的子系统，主要是分配文件所占的簇、盘块或者建立FAT、管理空间空间等

Kafka
https://www.cnblogs.com/BYRans/p/6054930.html

Apache Kafka是一个分布式的发布-订阅消息系统，能够支撑海量数据的数据传递。在离线和实时的消息处理业务系统中，Kafka都有广泛的应用。Kafka将消息持久化到磁盘中，并对消息创建了备份保证了数据的安全。Kafka在保证了较高的处理速度的同时，又能保证数据处理的低延迟和数据的零丢失。
pache Kafka是一个快速、可扩展的、高吞吐、可容错的分布式发布订阅消息系统
Kafka的优势在于：

可靠性：Kafka是一个具有分区机制、副本机制和容错机制的分布式消息系统
可扩展性：Kafka消息系统支持集群规模的热扩展
高性能：Kafka在数据发布和订阅过程中都能保证数据的高吞吐量。即便在TB级数据存储的情况下，仍然能保证稳定的性能。

Kafka工作流程
 
Kafka将某topic的数据存储到一个或多个partition中。一个partition内数据是有序的，每条数据都有一个唯一的index，这个index叫做offset。新来的数据追加到partition的尾部。每条数据可以在不同的broker上做备份，从而保证了Kafka使用的可靠性。

生产者将消息发送到topic中，消费者可以选择多种消费方式消费Kafka中的数据。下面介绍两种消费方式的流程。

一个消费者订阅数据：
生产者将数据发送到指定topic中
Kafka将数据以partition的方式存储到broker上。Kafka支持数据均衡，例如生产者生成了两条消息，topic有两个partition，那么Kafka将在两个partition上分别存储一条消息
消费者订阅指定topic的数据
当消费者订阅topic中消息时，Kafka将当前的offset发给消费者，同时将offset存储到Zookeeper中
消费者以特定的间隔（如100ms）向Kafka请求数据
当Kafka接收到生产者发送的数据时，Kafka将这些数据推送给消费者
消费者受到Kafka推送的数据，并进行处理
当消费者处理完该条消息后，消费者向Kafka broker发送一个该消息已被消费的反馈
当Kafka接到消费者的反馈后，Kafka更新offset包括Zookeeper中的offset。
以上过程一直重复，直到消费者停止请求数据
消费者可以重置offset，从而可以灵活消费存储在Kafka上的数据
消费者组数据消费流程
Kafka支持消费者组内的多个消费者同时消费一个topic，一个消费者组由具有同一个Group ID的多个消费者组成。具体流程如下：

生产者发送数据到指定的topic
Kafka将数据存储到broker上的partition中
假设现在有一个消费者订阅了一个topic，topic名字为“test”，消费者的Group ID为“Group1”
此时Kafka的处理方式与只有一个消费者的情况一样
当Kafka接收到一个同样Group ID为“Group1”、消费的topic同样为“test"的消费者的请求时，Kafka把数据操作模式切换为分享模式，此时数据将在两个消费者上共享。
当消费者的数目超过topic的partition数目时，后来的消费者将消费不到Kafka中的数据。因为在Kafka给每一个消费者消费者至少分配一个partition，一旦partition都被指派给消费者了，新来的消费者将不会再分配partition。即一个partition只能分配给一个消费者，一个消费者可以消费多个partition。

Single point of failure 
A single point of failure (SPOF) is a part of a system that, if it fails, will stop the entire system from working. SPOFs are undesirable in any system with a goal of high availability or reliability.



CAP theorem 
Consistency
Availability
Partition tolerance

REST

URL定位资源，用HTTP动词（GET,POST,DELETE,DETC）描述操作。
--- 简洁版 ---
0. REST不是"rest"这个单词，而是几个单词缩写。但即使那几个单词说出来，也无法理解在说什么 -_-!! （不是要贬低人，是我自己也理解困难）；
1. REST描述的是在网络中client和server的一种交互形式；REST本身不实用，实用的是如何设计 RESTful API（REST风格的网络接口）；
2. Server提供的RESTful API中，URL中只使用名词来指定资源，原则上不使用动词。“资源”是REST架构或者说整个网络处理的核心。比如：
http://api.qc.com/v1/newsfeed: 获取某人的新鲜;
http://api.qc.com/v1/friends: 获取某人的好友列表;
http://api.qc.com/v1/profile: 获取某人的详细信息;
3. 用HTTP协议里的动词来实现资源的添加，修改，删除等操作。即通过HTTP动词来实现资源的状态扭转：
GET 用来获取资源，
POST 用来新建资源（也可以用于更新资源），
PUT 用来更新资源，
DELETE 用来删除资源。比如：
DELETE http://api.qc.com/v1/friends: 删除某人的好友 （在http parameter指定好友id）
POST http://api.qc.com/v1/friends: 添加好友
UPDATE http://api.qc.com/v1/profile: 更新个人资料
禁止使用： GET http://api.qc.com/v1/deleteFriend 图例：

4. Server和Client之间传递某资源的一个表现形式，比如用JSON，XML传输文本，或者用JPG，WebP传输图片等。当然还可以压缩HTTP传输时的数据（on-wire data compression）。
5. 用 HTTP Status Code传递Server的状态信息。比如最常用的 200 表示成功，500 表示Server内部错误等。
主要信息就这么点。最后是要解放思想，Web端不再用之前典型的PHP或JSP架构，而是改为前段渲染和附带处理简单的商务逻辑（比如AngularJS或者BackBone的一些样例）。Web端和Server只使用上述定义的API来传递数据和改变数据状态。格式一般是JSON。iOS和Android同理可得。由此可见，Web，iOS，Android和第三方开发者变为平等的角色通过一套API来共同消费Server提供的服务。

HDFS
Hadoop Distributed File System
分布式文件系统 -- HDFS是可靠度最高的文件存储系统。HDFS是为存储在集群上运行的的文件存储系统。它设计的原则是更趋向于少量的大文件，而不是大量的小文件。Hadoop HDFS同时提供容错存储层和其他的组件。HDFS复制数据可以帮助我们去实现这个特点。即是硬件失败，它也可以可靠地存储数据。它为应用数据平行提供高吞吐量的数据访问。
当任何文件写入HDFS中时，它都会被打散分成小块儿存储，这就是所谓的Block. HDFS给block设置了默认大小为128MB，同时这个大小可以根据需求而增加。这些blocks以分布式的方式存储在HDFS系统中的不同节点上。这样的就为MapReduce提供了一种机制，可以在集群中平行的产生数据。

对于每个block的多重复制是横跨集群在不同节点下的复制。这些复制都是重复的数据。在默认情况下，HDFS的默认因子为3。这样的设置为系统提供了容错性，可靠性和高可依赖性。

总结一下，大文件在HDFS中被分解成n个小的blocks.每个block以分布式的方式实现在集群上的存储，同时每个block对于自身的复制是夸集群进行的。

Replication:

Master-Slave

Master: the main database that you write/read data to/from.
Slave: anytime a query is executed on the
master that same query is copied down to one or more slaves and they do the exact same thing

Advantages:

If the master is down, promote one of the slaves and do some configuration. (redundacy)
If there are a lot queries, you could just load balance across database servers
For read heavy websites, any select can go to all four databases, while any insert/update/delete has to go to server master

Mastter-Master
you could write to either server one or two and if you happen to write to server1 that query gets replicated on server2 and vice versa so now you could keep it simple

Load balancing + Replication

active + active pair of load balancers
active + passive pair of load balancers, passive promote itself when receives no more packets from the active one.
and send packets to each other

Partitioning
A-M cluster and O-Z cluster

High Availability
One load balancer, two master replicating each other

Shard
一个shard里可以有多个machine。machine之间的架构有master-slave, multi masters, peer to peer(high availability)


How do we store redundant data?


Deadlock
In concurrent computing, a deadlock is a state in which each member of a group is waiting for another member, including itself, to take action, 

CAP theorem 
Partition Tolerance In the context of a database cluster, cluster continues to function even if there is a “partition” (communications break) between two nodes (both nodes are up, but can’t communicate).
MongoDB
https://www.jianshu.com/p/b4233105ff60
NoSQL,

MongoDB使用C++语言编写的非关系型数据库。特点是高性能、易部署、易使用，存储数据十分方便
主要特性：

面向集合存储，易于存储对象类型的数据
模式自由
支持动态查询
支持完全索引，包含内部对象
支持复制和故障恢复
使用高效的二进制数据存储，包括大型对象
文件存储格式为BSON(一种JSON的扩展)

QPS

屏幕快照 2019-04-23 上午12.04.20副本

schema 表单

结构化信息

RabbitMQ vs Kafka

RabbitMQ is a solid, general purpose message broker that supports several protocols such as AMQP, MQTT, STOMP etc. It can handle high-throughput and common use cases for it is to handle background jobs or as message broker between microservices. Kafka is a message bus optimized for high-ingress data streams and replay.

Kafka can be seen as a durable message broker where applications can process and re-process streamed data on disk. Kafka has a very simple routing approach. RabbitMQ has better option if you need to route your messages in complex ways to your consumers. Use Kafka if you need to supporting batch consumers that could be offline, or consumers that want messages at low latency. 

ZooKeeper

Role of ZooKeeper. A critical dependency of ApacheKafka is Apache Zookeeper, which is a distributed configuration and synchronization service. Zookeeperserves as the coordination interface between theKafka brokers and consumers. The Kafka servers share information via a Zookeeper cluster.
Zookeeper manages and coordinates the Kafka server (broker). Kafka cluster is a set of servers, each is called broker. 

MapReduce

MapReduce讲的就是分而治之的程序处理理念，把一个复杂的任务划分为若干个简单的任务分别来做。另外，就是程序的调度问题，哪些任务给哪些Mapper来处理是一个着重考虑的问题。MapReduce的根本原则是信息处理的本地化，哪台PC持有相应要处理的数据，哪台PC就负责处理该部分的数据，这样做的意义在于可以减少网络通讯负担。

JSON

In computing, JavaScript Object Notation is an open-standard file format that uses human-readable text to transmit data objects consisting of attribute–value pairs and array data types

Replica 和 Backup

这是一个很好的问题，首先解释这个问题之前，我们必须要区分这两个东西 Replica 和 Backup:
Replica 是为了提高系统的可用性
Backup 是用于灾难恢复，容灾。

Replica中，每个节点成员将会保持同步。所有数据库写操作将会在 Primary 节点上操作，同时同步到其他的replica节点。当 Primary 节点挂掉以后，将会在Replica节点中选取出新的 Primary 节点。一旦这个节点成为Primary节点后，我们也可以增加一台新的节点成为新的Replica。
Replica保证了你的系统的可用性，至少单机出问题后你可以迅速转移到另外一台机器，虽然可能仍旧有几秒系统是处于不可用的状态。

Backup主要处理容灾的情况，这个灾难分为两部分自然灾害和人为灾难。

自然灾害主要是火灾和地震，你的replica可能会全部挂了，或者所有的Replica出现磁盘故障，最终你需要靠Backup来恢复。

人为灾难，不小心删除了重要数据，或者黑客攻击，删除了所有数据，看我们上面的Replica的解释，这个操作会立即

同步到其他的Replica的节点中，也就是说这种错误，我们是不可能通过Replica去做恢复的，因为Replica和我们的Primary的数据是一致的，此时我们可以通过Backup去恢复，比如我们每小时生成一个backup，那么恢复之后，最多也就丢失了1h小时内的数据（当然大家都有不同的backup策略）

https://www.cnblogs.com/bonelee/p/6295656.html
Samza vs spark 

Apache Samza

Samza处 理数据流时，会分别按次处理每条收到的消息。Samza的流单位既不是元组，也不是Dstream，而是一条条消息。在Samza中，数据流被切分开来， 每个部分都由一组只读消息的有序数列构成，而这些消息每条都有一个特定的ID（offset）。该系统还支持批处理，即逐次处理同一个数据流分区的多条消 息。Samza的执行与数据流模块都是可插拔式的，尽管Samza的特色是依赖Hadoop的Yarn（另一种资源调度器）和Apache Kafka。

CDN is short for content delivery network. A content delivery network (CDN) is a system of distributed servers (network) that deliver pages and other Web content to a user, based on the geographic locations of the user, the origin of the webpage and the content delivery server.

This service is effective in speeding the delivery of content of websites with high traffic and websites that have global reach. The closer the CDN server is to the user geographically, the faster the content will be delivered to the user. CDNs also provide protection from large surges in traffic.

How CDNs Work

Servers nearest to the website visitor respond to the request. The content delivery network copies the pages of a website to a network of servers that are dispersed at geographically different locations, caching the contents of the page. When a user requests a webpage that is part of a content delivery network, the CDN will redirect the request from the originating site's server to a server in the CDN that is closest to the user and deliver the cached content. CDNs will also communicate with the originating server to deliver any content that has not been previously cached.

SERVER和SERVER如何COMMUNICATION

首先看看以下问题：

1. Node.js是什么。search engine说：Node.js is a JavaScript runtime built on Chrome's V8 JavaScript engine。
2. backend是什么：backend指database and python。
3. server：我理解是服务提供方，比如server提供网页浏览服务
4. client：我理解是服务接受方，比如用户通过浏览器访问网站

那么：server直接进行通信，如何进行？
1.这里的server理解为服务进程，因此题目问的是服务进程之间如何通信。
2.一般进程间通信使用IPC技术（IPC，Interprocess communication）
search engine 告诉我们，IPC一般有以下几种技术：
1） 管道( pipe )：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
2）有名管道 (named pipe) ： 有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。
3） 信号量( semophore ) ： 信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
4）消息队列( message queue ) ： 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
5）信号 ( sinal ) ： 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
6）共享内存( shared memory ) ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号两，配合使用，来实现进程间的同步和通信。
7） 套接字( socket ) ： 套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同主机间的进程通信。
3.因此，如果server进程处于同一主机的话，可以使用如下IPC技术：named pipe， semophore， message queue， sinal， shared memory，socket。如果server进程处于不同主机的话，可以使用socket。

（socket是在应用层和传输层之间的一个抽象层，它把TCP/IP层复杂的操作抽象为几个简单的接口供应用层调用，从而实现进程在网络中通信。 

在设计模式中，Socket其实就是一个门面模式，它把复杂的TCP/IP协议族隐藏在Socket接口后面，）4. 下面这个问题我暂时没有想明白：把JDBC和ODBC都理解成使用socket封装好的API是否正确？

以上是个人理解，请高手指正

远程过程调用协议（RPC）

Source: Crack the system design interview

在 RPC 中，客户端会去调用另一个地址空间（通常是一个远程服务器）里的方法。调用代码看起来就像是调用的是一个本地方法，客户端和服务器交互的具体过程被抽象。远程调用相对于本地调用一般较慢而且可靠性更差，因此区分两者是有帮助的。热门的 RPC 框架包括 Protobuf、Thrift 和 Avro。

数据库的几个概念：主键，外键，索引，唯一索引

https://blog.csdn.net/xrt95050/article/details/5556411

主键 primary key：唯一性，ID

外键 foreign key：一个table受另一个table的一个key约束或者元素是另一个table的key对应元素，该key是foreign key。比如computer table 里的cpu必须从 parts table里的cpu中选择。

索引：可以对每个column items建立索引，也就是把column item排序，binary search tree，快速查找。比如：有一个table，student Id 和 student name。可以把student name建立index。这样可以快速通过student name查询student Id。SELECT peopleid FROM people WHERE name='Mike';

唯一索引：索引列的所有值都只能出现一次，即必须唯一。主键对应唯一索引。