Repeat:

OLTP online transaction processing联机事务处理过程，面向交易的处理过程。主要是执行基本日常的事务处理，比如数据库记录的增删查改。比如在银行的一笔交易记录，就是一个典型的事务。实时性要求高。数据量不是很大。交易一般是确定的。高并发。

OLAP online analytical processing联机分析处理

QPS query per second每秒查询率。

CAP理论。Consistency一致性，数据更新一致。Availability可用性，好的响应性能；Partition tolerance分区容忍性，可靠性。任何分布式系统只能同时满足两点，没法三者兼顾。 关系型数据库的ACID模型，拥有高一致性和可用性，很难进行分区。ACID,指数据库事务正确执行的四个基本要素的缩写。包括原子性（Atomicity）、要么全完成，要么不完成。一致性（Consistency）、开始或结束时，数据库状态应该一致。在事务隔离性（Isolation）、事务只有自己在操作数据库，彼此不知晓。持久性（Durability），一旦事务完成，就不能返回。

New:

一、Quorum机制：是一种权衡机制，一种将“读写转化”的模型。

WARO（Write All Read One）是一种简单的副本控制协议，当Client请求向某副本写数据时，更新数据时，只有当所有的副本都更新成功了，这次写操作才算成功，否则视为失败。

从这里可以看出两点：写操作很脆弱，因为一个副本更新失败，此次写操作就视为失败。读操作很简单，因为所有副本更新成功，才视为更新成功，从而保证所有副本一致。这样，只需要读任意副本上的数据即可。假设有N个副本，N-1个都当即了，剩下的副本仍能提供度服务。但是只要有一个副本当即了写服务就不会成功。

WARO牺牲了更新服务的可用性，最大程度地增强了读服务的可用性。而Quorum就是更新服务和读服务之间进行一个折中。

Quorum机制是“抽屉原理”的一个应用。定义如下：假设有N个副本，更新操作wi在W个副本中更新成功之后，才任务此次更新操作wi成功。称成功提交的更新操作对应的数据为“成功提交的数据”。对于读操作而言，至少需要读R个副本才能读到此次更新的数据。其中W+R>N，即W和R有重叠。一般，W+R=N+1.

二、Quorum机制分析

Quorum机制无法保证强一致性

所谓强一致性就是：任何时刻任何用户或节点都可以读到最近一次成功提交的副本数据。强一致性程度最高的一致性要求，也是时间中最难以实现的一致性。

因为仅仅通过Quarum机制无法确定最新已经成功提交的版本号。

比如V2成功添加后，已经写入3份，尽管读取3个副本是一定能读到V2，如果刚好读到的是V2,V2,V2则此次读取的数据时最新成功提交的数据，因为W=3，而此时刚好读到了3份V2。如果读到的是V2,V1,V1则无法确定是一个成功提交的版本，还需要基础再读，知道读到V2的到达3份为止，这是才能确定V2及时已经成功的最新的数据。

Q：如何读取最新的数据？

在已经知道最近成功提交的数据版本号的前提下，最多读R个副本就可以读到最新的数据了。

Q：如何确定最高版本号的数据是一个成功提交的数据？

继续读其他的副本，直到读到的最高版本号出现了W次。

基于Quorum机制选择Primary

中心节点（服务器）读取R个副本，选择R个副本中版本号最高的副本作为新的Primary。

新选出的Primary不能立即提供服务，还需要与至少W个副本完成同步后，才能提供服务。为了保证Quorum机制的规则：W+R>N，至少如何处理同步过程中冲突的数据，则需要视情况而定。

至于如何处理同步过程中冲突的数据，则需要视情况而定。

比如V2,V2,V1,V1,V1，R=3，如果读取的3个副本是V1,V1,V1则高版本的V2需要丢弃。如果读取的3个副本是V2,V1,V1则低版本的V1需要同步到V2。

三、Quorum机制应用实例

HDFS高可用性实现

HDFS的运行依赖于NameNode，如果NameNode挂了，name整个HDFS就用不了了，因此，就存在单点故障（Single point of failure）;其次，如果需要升级或者维护停止NameNode,整个HDFS也用不了。为了解决这个问题，采用QJM机制。（Quorum Journal Manager）实现HDFS的HA（High availability）。注意，一开始采用的“共享存储”机制，共享存储机制的不足。

In a typical HA cluster, two separate machines are configured as NameNodes.At any point in time, exactly one of the NameNodes is an Active state,and the other is in a Standby state.The Active NameNode is responsible for all client operations in the cluster,while the Standby is simpliy acting as a slave,maintaining enough state to provide a fast failover if necessary.

为了实现HA，需要两台NameNode机器，一台是Active NameNode,负责Client请求。另一台是StandByNameNode,负责与Active NameNode同步数据，从而快速failover。

那么这里有个问题，StandBy NameNode是如何同步Active NameNode上的数据的呢？主要同步的是哪些数据呢？同步数据就用到了Quorum机制。同步的数据主要是EditLog。

In order for the Standby node to keep its state synchronized with the active node,both nodes communicate with a group of separate daemons called "JournalNodes"（JNs）。

数据同步用到了一个第三方“集群”：Journal Nodes。Active NameNode和StandBy NameNode都与JournalNodes通信，从而实现同步。

每次NameNode写EditLog的时候，除了向本地磁盘写入EditLog之外，也会并行地向JournalNode集群之中的每一个JournalNode发送写请求，只要大多数（majority）的JournalNode节点返回成功就认为像JournalNode集群写入EditLog成功。如果有2N+1台JournalNode，那么根据大多数原则，最多可以容忍有N台JournalNode节点挂掉。

这就是Quorum机制。每次写入JournalNode的机器数目大多数W时，就认为本次写操作成功了。

这样，每次对Active NameNode中的元数据进行修改时，都会将该修改写入JournalNode集群的大多数机器中，才认为此次修改成功。

当Active NameNode宕机时，Standby NameNode向JournalNode同步EditLog，从而保证了HA。

Active NameNode向JournalNode集群提交EditLog是同步的，但Standby NameNode采用的是定时从JournaNode集群上同步EditLog的方式，那么StandBy NameNode 内存中的文件系统镜像有很大可能是落后于Active NameNode的，所以StandBy NameNode在转换为Active NameNode 的时候需要把落后的EditLog补上来。

为了实现快速的failover，Standby NameNode 需要实时地与各个DataNode通信以获得每个数据块的地址信息。为啥要这样了？

因为每个数据块的信息不属于“元信息”，并没有保存在FSImage、CheckPoint....,这是因为地址信息变化比较大。比如说，一台DataNode下线了，其上面的数据块地址信息就全无效了，而且为了达到指定的数据块“复制因子”，还需要在其他机器上复制该数据块。

快速failover，是指Active NameNode宕机后，StandBy NameNode立即就能提供服务。因此，DataNode也需要实时向StandBy NameNode发送block report。

另外，还有手动failover和自动failover,自动failover需要Zookeeper的支持。

如何避免“Split Brain"脑裂问题

Split Brain是指同一时刻有两个认为自己处于Active状态的NameNode。

When a NameNode sends any message(or remote procedure call)to a JournalNode,it includes its epoch number as part of the request.Whenever the JournalNode recerves such a message,it comprass the epoth number against a locally stored value called the promised epoch.If the request is coming from a newer epoch,then it records that new epoch as its promised epoch.If instead the request is coming from an older epoch,then it rejects the request.This simple policy avoides split-brain.

每个NameNode与JournalNodes通信时，需要带一个epoch number（唯一且只增不减）。而每个JournalNode都有一个本地的Promise epoch。拥有值大的epoch numbers的NameNode会使得JournalNode提升自己的promised epoch,从而占大多数，而epoch number较小的那个NameNode就成了少数派（Paxos协议思想）。

从而epoch number值大的NameNode才是真正的ActiveNameNode，有用写JournalNode的权限。注意：任何时刻只允许一个NameNode拥有写JournalNode权限。

redundant多余的，累赘的