什么叫顺序一致性？

假设有一个Zookeeper集群（N>=3，N为奇数），那么只有一个Leader（通过FastLeaderElection选主策略选取），所有的写操作（客户端请求Leader或Follower的写操作）都由Leader统一处理，Follower虽然对外提供读写，但写操作会提交到Leader，由Leader和Follower共同保证同一个Follower请求的顺序性，Leader会为每个请求生成一个zxid（高32位是epoch，用来标识leader选举周期，每次一个leader被选出来，都会有一个新的epoch，标识当前属于哪个leader的统治时期，低32位用于递增计数）

针对同一个Follower A提交的写请求request1、request2，某些Follower虽然可能不能在请求提交成功后立即看到（也就是强一致性），但经过自身与Leader之间的同步后，这些Follower在看到这两个请求时，一定是先看到request1，然后再看到request2，两个请求之间不会乱序，即顺序一致性

不管这多个客户端的请求顺序如何交叠，都可以，但是必须按照请求到达的顺序执行，即顺序一致性

相应的也要看是针对一个客户端达到顺序一致性还是针对所有客户端都达到顺序一致性，实现也是不同的

让我们看一下比较准确的定义

在设计和证明运行在该计算机上的多进程算法[1]-[3]的正确性时，通常基于如下假设：执行结果与这些处理器以某一串行顺序执行的结果相同，同时每个处理器内部操作的执行看起来又与程序描述的顺序一致。满足该条件的多处理器系统我们就认为是sequential consistent的"。这里的处理器就代表了一个独立的执行进程(或线程)，每个进程(线程)内部是串行执行的。如果并行执行的结果与某个合法的串行执行顺序(在这个执行顺序中每个线程内部的执行顺序要保留)的执行结果一致，我们就认为它是符合顺序一致性的。

zookeeper写请求流程.png

Leader在处理第4步Follower的ack回复时，采用过半数响应即成功原则，也就是这时候有的Follower是还没有处理或者处理成功这个请求的

那么问题来了，怎么保证顺序一致性的呢？

• FollowerRequestProcessor为Follower的首个处理器，如果是写请求，先将请求写入commitprocessor的queuedRequests（方便后续commit时判断是否本Follower提交的写请求），然后转Leader
• Leader为每个请求生成zxid，下发proposal给Follower，Follower会将请求写入到pendingTxns阻塞队列及txnLog中，然后发送ack给Leader

public void logRequest(TxnHeader hdr, Record txn) {
        Request request = new Request(hdr.getClientId(), hdr.getCxid(), hdr.getType(), hdr, txn, hdr.getZxid());
        if ((request.zxid & 0xffffffffL) != 0) {
            pendingTxns.add(request);
        }
        syncProcessor.processRequest(request);
    }

proposal这步是会发给所有的follower的（放到LearnerHandler的请求处理队列中，一个Follower一个LearnerHandler），之后Follower的ack就不一定全返回了

• ack过半，Leader发送commit请求给所有Follower，Follower对比commit request的zxid和前面提到的pendingTxns的zxid，不一致的话Follower退出，重新跟Leader同步

long firstElementZxid = pendingTxns.element().zxid;
        if (firstElementZxid != zxid) {
            LOG.error("Committing zxid 0x" + Long.toHexString(zxid)
                    + " but next pending txn 0x"
                    + Long.toHexString(firstElementZxid));
            System.exit(12);
        }

• Follower处理commit请求，如果不是本Follower提交的写请求，直接调用FinalRequestProcessor做持久化，触发watches；如果是本Follower提交，则做一些特殊处理（主要针对客户端连接断开的场景），然后调用FinalRequestProcessor等后续处理流程
• FinalRequestProcessor做持久化，返回客户端

总之：Follower通过队列和zxid等顺序标识保证请求的顺序处理，一言不合就会重新同步Leader

 

 

由于过半响应成功原则，若有接收不到的，读取到的数据可能是过期的旧数据，不是最新的数据。

在zk的官方文档中对此有解释，地址在：https://zookeeper.apache.org/doc/r3.1.2/zookeeperProgrammers.html

对于zookeeper来说，它实现了A可用性、P分区容错性、C中的写入强一致性，丧失的是C中的读取一致性。

 

Zookeeper所能保证的一致性

 

强一致性(Strong Consistency)

在分布式环境下，满足强一致性的数据储存基本不存在，它要求在更新一个节点的数据，需要同步更新所有的节点。这种同步策略出现在主从同步复制的数据库中。但是这种同步策略，对写性能的影响太大而很少见于实践。因为Zookeeper是同步写N/2+1个节点，还有N/2个节点没有同步更新，所以Zookeeper不是强一致性的。

 

弱一致性

用户的数据更新操作，不保证后续的读操作能够读到更新后的值，但是最终会呈现一致性。牺牲一致性，并不是完全不管数据的一致性，否则数据是混乱的，那么系统可用性再高分布式再好也没有了价值。牺牲一致性，只是不再要求关系型数据库中的强一致性，而是只要系统能达到最终一致性即可

 

CopyOnWriteArrayList是一个读写分离的并发ArrayList，它的遍历是弱一致性的，因为可以容忍并发修改，不会抛出ConcurrentModificationException，不像普通的集合，允许即时失败。

 

最终一致性

最终一致性本质上和弱一致性是一回事，因为一个数据存储系统满足弱一致性但是不满足最终一致性，那么这个系统的数据就是不正确，一个数据不正确的系统是一个无法交付使用的系统。Zookeeper满足最终一致性，只要数据同步到Quorum之外的节点就会达到最终一致性。

 

因果一致性

Zookeeper是否满足因果一致性，需要看客户端的编程方式。

• 不满足因果一致性的做法

1. A进程向Zookeeper的/z写入一个数据，成功返回

2. A进程通知B进程，A已经修改了/z的数据

3. B读取Zookeeper的/z的数据

4. 由于B连接的Zookeeper的服务器有可能还没有得到A写入数据的更新，那么B将读不到A写入的数据

 

• 满足因果一致性的做法

1. B进程监听Zookeeper上/z的数据变化

2. A进程向Zookeeper的/z写入一个数据，成功返回前，Zookeeper需要调用注册在/z上的监听器，Leader将数据变化的通知告诉B

3. B进程的事件响应方法得到响应后，去取变化的数据，那么B一定能够得到变化的值

4. 这里的因果一致性提现在Leader和B之间的因果一致性，也就是是Leader通知了数据有变化

 

第二种事件监听机制也是对Zookeeper进行正确编程应该使用的方法，所以，Zookeeper应该是满足因果一致性的

 

 

读你所写(写后读)一致性

严格来说，Zookeeper不满足读你所写一致性。因为在一个进程中，如下的操作序列是Zookeeper不能保证的， 会话建立->写数据->会话关闭->会话建立->读数据，最后的读数据不一定读到之前写的数据。

 

MongoDB是否满足读你所写一致性?MongoDB是满足的，因为它是连接信息跟线程绑定的，意思是说，读写线程跟MongoDB的连接信息是绑定的，读写线程获取连接优先连接到之前连接到的服务器。

 

会话一致性

在一个会话过程中，Zookeeper满足读你所写一致性。因为Zookeeper不同于MongoDB或者其它分布式系统，是读写数据结束立即释放连接。而Zookeeper是长连接的(用于监听Zookeeper的事件)。

Zookeeper提供了会话的自动重连机制，当客户端连接的Zookeeper服务器出现故障而不可达时，客户端会自动尝试重连到另外一台机器，客户端选择的那台服务器的数据状态不比之前连接的那台机器旧，因此会话重连也会保证会话一致性。

 

 

单调读一致性

严格来说，Zookeeper不满足单调读一致性。因为在一个进程中，如下的操作序列是Zookeeper不能保证的， 会话建立->写数据->读数据->会话关闭->会话建立->读数据，最后的读数据不一定是之前写到的数据

 

单调写一致性

Zookeeper满足。只要Zookeeper写成功了一个操作，那么后面的写肯定是在Zookeeper提交了前一个写之前，而不管是否在同一个会话中，因为Zookeeper的写操作是全局顺序性。

 

读后写一致性

Zookeeper满足读后写一致性。当Zookeeper读到一个数据后，那么Zookeeper在写数据时，一致性在读到的之后的值进行更新。

 

介绍下其他一致性概念

缓存一致性

cache coherence 的coherence这个词猜测是体系结构圈为了和memory consistency做区分，用了coherence这个词，但我理解缓存一致性和分布式多副本数据的一致性基本接近，只不过cache coherence是一种同步可靠通信、有全局时钟条件下的强一致(linearizability)。cache一致性协议有MSI，MESI等，虽然处理器的整个内存系统很复杂，还要考虑多层cache，但就cache一致性协议来说，比分布式环境下的数据一致要简明一些

多核处理器每个核会有私有cache，也就是内存里的一份数据在多个核上可能有了副本，这多个副本，每个核都可能会对一个内存地址有读写操作，每个核是直接读写自己私有的副本，这就要求各个副本上的读写操作顺序要一致，这和分布式环境下的数据一致性很接近。

具体的MSI，MESI协议暂不展开写。

多核缓存协同操作

假设有三个CPU A、B、C，对应三个缓存分别是cache a、b、 c。在主内存中定义了x的引用值为0。

单核读取

那么执行流程是：
CPU A发出了一条指令，从主内存中读取x。
从主内存通过bus读取到缓存中（远端读取Remote read）,这是该Cache line修改为E状态（独享）.

双核读取

那么执行流程是：
CPU A发出了一条指令，从主内存中读取x。
CPU A从主内存通过bus读取到 cache a中并将该cache line 设置为E状态。
CPU B发出了一条指令，从主内存中读取x。
CPU B试图从主内存中读取x时，CPU A检测到了地址冲突。这时CPU A对相关数据做出响应。此时x 存储于cache a和cache b中，x在chche a和cache b中都被设置为S状态(共享)。

修改数据

那么执行流程是：
CPU A 计算完成后发指令需要修改x.
CPU A 将x设置为M状态（修改）并通知缓存了x的CPU B, CPU B将本地cache b中的x设置为I状态(无效)
CPU A 对x进行赋值。

同步数据

那么执行流程是：

CPU B 发出了要读取x的指令。
CPU B 通知CPU A,CPU A将修改后的数据同步到主内存时cache a 修改为E（独享）
CPU A同步CPU B的x,将cache a和同步后cache b中的x设置为S状态（共享）。

 

内存一致性

内存一致性说的是共享内存多核处理器访存序的问题，进程对某一个内存地址(和分布式的同一数据多副本的一致性有所区别)的访问序的在多核下暴露出的问题。也就是程序中 Load Store 的(ISA)顺序(冯诺依曼架构下看可以看做内存操作请求的顺序)和Load Store实际执行完成的顺序可能相同、可能不同(这取决于微体系结构的实现)，在多核情况下，程序的正确性可能出问题。有各种一致性模型来表达各种程度的相同不同，相应的有软、硬件机制来确保多核处理器上程序的正确运行。

不管这多个处理器对同一内存的请求顺序如何交叠，都可以，但是内存必须按照请求到达的顺序执行(这里应该隐含着对同一地址先请求(指令发射)的先到达(指令执行)的假设)，这样保证上面的互斥协议正确。这样的要求称为顺序一致的要求，是很严格的，会对硬件性能造成影响，其实可以放宽，不必严格按请求顺序执行，但是必须有软件机制来提供正确的互斥协议的实现

 

数据一致性

分布式系统为了性能、容错的需要，数据进行多副本冗余是一项很基本的技术。数据一致性说的是一份数据有多个副本，在多个副本上的读写操作的顺序要达成一致，这个一致也有很多不同的强弱要求，产生了众多的强弱一致性模型，这些模型的术语和内存一致性的术语有很大的重叠，可能是历史上并行体系结构和分布式系统两个领域是一伙人在搞?

由强到弱的数据一致性模型构成了 数据一致性谱

线性一致性和顺序一致性

这两种都是称为强一致性

线性一致性和顺序一致性都是强一致性 都给客户端提供单副本的假象 Linearizability关乎时间，sequential consistency 关乎程序顺序

分布式下强一致是个困难问题，著名的paxos算法挺复杂的，Raft是2014年出的一个可以看作是改良版的算法。

内存的顺序一致性和分布式哪一种强一致性是一样的呢?是顺序一致性么?因为分布式环境下没有全局时间，所以分布式数据顺序一致性退化成较弱的一种一致性，而Linearizability和内存的顺序一致性更接近。

 

线性一致性

 

对于顺序一致性来说，它要找到一个合法的顺序执行过程(只要能找到一个即可)，该执行过程要保留线程内部原有的顺序(对应到上图就是:[Set 1]一定要在[Get 2]之前，[Set 3]一定要在[Set 2]之前)。根据这个要求我们可以发现：[Set 1] [Set3] [Set 2] [Get 2]就是一个合法的顺序执行过程。对于一个寄存器来说，合法的顺序执行过程需要满足这个条件：Get到的值一定是最近一次Set的那个值。

而对于线性一致性来说，它也是要找到一个合法的顺序执行过程(只要能找到一个即可)。但是这个顺序执行过程，不仅要保留线程内部的先后顺序，还要保留线程之间的操作的先后顺序。比如上图从时间线上看，[Set 1]是最先发生的，[Get 2]和[Set 3]时间上有交叉，在线性一致性模型中，我们认为这两个是并行的，先后顺序不定，最后的[Set 2]一定是最后发生。这样满足线程内部和线程间顺序约束的执行过程只有两种，如上图所示。但是这两种执行过程都不是合法的：对于[Set 1] [Set 3] [Get2] [Set 2]来说，Set 3之后却Get到了2；对于[Set 1] [Get 2] [Set3] [Set 2]来说，Set 1之后却Get到了2。所以不满足线性一致性。

具体为什么不满足，需要通过可线性化算法验证

 

 

 

 

 

 

参考 https://www.jianshu.com/p/8e2bfb0cb7a7

参考 https://bit1129.iteye.com/blog/2156246

参考 https://www.2cto.com/net/201806/755476.html

参考 https://www.cnblogs.com/yanlong300/p/8986041.html