《Paxos Replicated State Machines as the Basis of a High-Performance Data Store》 介绍了使用了paxos算法进行副本同步，这里仅总结如何保证read-only操作的linearizability

How

1. 收到read-only请求后，记录下一个slot number
2. slot number = max(已经commit的最大的operation number VS 当前节点成为leader后re-proposed最大的operation number)
3. 向所有replicas发送消息，检查是否有新leader出现（即检查当前节点是否扔是合法leader）
4. 如果加上自身有总数过半的节点仍然认为当前节点是leader则继续，否则丢弃请求
5. 将请求连同1中记录的slot number转发到任意replica（最好是3中回复确认的的replica），称之为replica A
6. replica A等待slot number被执行，之后检测是否有新的paxos configuration被选择，如果有则丢弃请求，否则执行read操作返回结果

Why

最简单的保证linearizability的read-only的方法是将read-only操作当做写操作一样走一遍paxos流程，但是这样读的性能太低了，并且会导致leader压力巨大

论文中提出的方法省去了走paxos流程的磁盘IO，仅一次广播检测确认leader角色，并将真正的读操作转移到了replica上

那么如何证明呢？

1. read-only linearizability需要保证的是在这个请求到达之前已经成功提交的写入都应该被本次读取看到
2. 我们将read-only request 到来之前已经成功提交的最后一条写入的operation number为 N，则有以下三种情况：
3. N 是前一个leader提交的
4. N 是当前节点成为leader后提交的
5. 当前节点早已经不是leader， N其实是后续leader提交的
6. 我们只需保证slot number >= N即可保证linearizability
7. N是前一个leader提交的，当前节点成为leader后re-proposed最大的operation number 一定大于等于N
8. N是当前leader提交的，那么一定有slot number >= N
9. 该情况请求会被丢弃，slot number不需要保证大于等于N

Extension

TIDB中在使用raft做数据同步的情况下，也使用了一个类似的方法来保证read-only的linearizability：

当 leader 要处理一个读请求的时候： 1. 将当前自己的 commit index 记录到一个 local 变量 ReadIndex 里面。 2. 向其他节点发起一次 heartbeat，如果大多数节点返回了对应的 heartbeat response，那么 leader 就能够确定现在自己仍然是 leader。 3. Leader 等待自己的状态机执行，直到 apply index 超过了 ReadIndex，这样就能够安全的提供 linearizable read 了。 4. Leader 执行 read 请求，将结果返回给 client。

其中：

实现 ReadIndex 的时候有一个 corner case，在 etcd 和 TiKV 最初实现的时候，我们都没有注意到。也就是 leader 刚通过选举成为 leader 的时候，这时候的 commit index 并不能够保证是当前整个系统最新的 commit index，所以 Raft 要求当 leader 选举成功之后，首先提交一个 no-op 的 entry，保证 leader 的 commit index 成为最新的。

与本文中N是前一个leader提交的，当前节点成为leader后re-proposed最大的operation number 一定大于等于N是类似的（raft毕竟是paxos的变种）

另外一种方式就是TIDB根据raft论文实现的lease的方式：

在 Raft 论文里面，提到了一种通过 clock + heartbeat 的 lease read 优化方法。也就是 leader 发送 heartbeat 的时候，会首先记录一个时间点 start，当系统大部分节点都回复了 heartbeat response，那么我们就可以认为 leader 的 lease 有效期可以到 start + election timeout / clock drift bound 这个时间点。

为什么能够这么认为呢？主要是在于 Raft 的选举机制，因为 follower 会在至少 election timeout 的时间之后，才会重新发生选举，所以下一个 leader 选出来的时间一定可以保证大于 start + election timeout / clock drift bound。

Referrence

1. TiKV 源码解析系列 - Lease Read

Introduce

所谓的linearizability其目的在于描述系统的数据，对外看起来就像只有一份，所有针对这部分数据的操作都是原子(Concurrency-atomic)的；在分布式系统领域来讲和CAP-consistent是等价的；在多核并发编程时由于存在CPU-Cache一致性问题，linearizability的概念同样适用。

What

通用的定义（分布式系统 and 多核系统）：

every read returns the latest value written into the shared variable preceding that read operation, then the shared object is linearizable

时序角度：

对于linearizability 系统，任意的两个操作的顺序都是可以比较的，即存在total order. 考虑：如果数据只有一份拷贝，同时操作又都是atomic的，那么任意两个操作总有先后关系，所以total order必然存在。

对比CAP-consistent：

任意的一条读操作R，如果发生在某条写操作W完成之后（或执行过程中），那么R读到的要么是W的内容，要么是W之后的写操作写入的内容

这里的定义与CAP-consistent略有出入，为什么放宽限制为或执行过程中呢？因为定义之中所有的之前之后是否完成都是所谓上帝视角来判定的；对于client而言只有clients之间额外的交流沟通（参考后文），而对于clients之间额外的交流沟通而言，W完成与否也是无法判定的，考虑即使是执行W的client，也只能拿到W完成的响应时间，并不能真正知道server端W完成的时间（中间有网络延迟，物理时钟有误差等），即使利用因果关系进行clients之间额外的交流沟通也无从考证真正完成的时序。因此W是否真的完成并意义不大。

结合图示来看： 一旦有client读取到了写入的值，即使这个写入操作还没有完成，那么后续的读取操作都应该能读到该值或者之后写入的值

Why

• 对于clients而言，一旦存在额外的交流沟通的渠道，linearizability问题就会凸显，例如：
  • A,B两个人去刷飞机票，A刷到了，B没有刷到（显示全部售光），如果A,B之间没有交流，即使B刷票先于A，则交易看起来也没有什么问题
  • 但如果A,B两个人存在交流，例如B没有刷到票，然后跑去隔壁房间问A，恰巧碰到A正在刷，并且刷票成功（B刷票 happened before A刷票），则交易存在问题
• 如果能够提供linearizability的分布式系统，则：
  • 可以利用该系统实现分布式锁操作
  • 利用锁操作又可以用进行leader-election
  • 利用锁操作可以达成uniqueness guarantees
  • linearizability sequence number — 可以用来解决total order问题

How

如果可以保证分布式系统的各操作时序可比较（total order），则linearizability可达成；所以linearizability的实现问题可以转换成实现fault-tolent total order

而实现fault-tolent total oerder是一个distributed consensus问题

似乎就是一个循环: 如果实现了linearizability，则实现了linearizability sequence number，从而解决了total order问题，即实现了distributed consensus；而实现linearizability 又依赖通过distributed consensus实现total order

Weakness

linearizability is slow all the time, not only during a network fault（节点间通信达成共识本身就很耗时）

References

1. Martin Kleppmann. 《Designing Data-Intensive Applications》9.Linearizability

Introduce

对于CAP而言，partition-tolerant是客观的必须要做的，不然不能称之为分布式系统；而consistent和available则是主观的， 应当根据业务需求适当调整的。相对于linearizability的强一致，其实还有多种弱一致性模型可以供系统设计时参考, 这里着重描述两种重要的一致性模型

Data-centric consistent models

Causal Consistency

与linearizability相同，causal consistency同样属于data-centric consistent models。与前者明显的区别在于，linearizability的系统的所有操作都存在total order，而causal consistency只需要partial order即可。

定义：

对于所有的进程看到的所有的写操作，都是因果相关的（causally related）且顺序相同。所有的读操作看到的结果也需要和写的因果顺序一致

如图：

两次写操作没有因果关系（concurrence），所以后续的两个client的读结果不相同，但这符合causal consistency的定义

How

实现causally related partital order即可，例如vector clock + causal order multicast protocol

Client-centric consistent models

Eventual Consistency

最终一致性比较好容易理解，很多primary-backup(asynchronous)架构的RDBMS都是使用的最终一致性模型

定义：

如果没有新的更新/写入，最终所有的clients都会看到最新的数据

最终是多久，不好说…

典型例子：

DNS系统

How

asynchronous log shipping + gossip protocal

References

1. 《Distributed Systems An Algorithmic Approach Second Edition》16.3 16.4

Summary

zab是Yahoo提出的leader-base的一致性协议，由于raft晚于该协议猜测raft中有借鉴该协议的一些思想 此文仅总结理解的一些重点，并不完整总结该算法

FLP？

zab 中使用了timeout来进行故障检测，并没有突破FLP

Zxid

• 高32位：代表epoch，与raft-term或multi-paxos的proposal number语意相同，与raft-term的不同点是自增的时机是在成为leader后
• 低32位：自增id，等同与multi-paxos的instance-id/instance-index 或 raft-log-index

BroadCast

Zab broadcast依赖与FIFO（TCP）+ zxid 来保证消息的顺序（causal order + total order）；paxos并不依赖于此而是靠proposal number来保证这一点；而raft则是通过log-index来保证的

Zab的broadcast本质就是放弃了abort动作的2PC协议,即：

• 2PC中P1阶段可以由Participant选择YES or Abort，而Zab-BroadCast的P1阶段follower只能回复YES（即ACK），或者选择放弃该leader

Recovery

recovery 需要在正确性上保证以下两点：

1. 不要忘记已经交付的消息
2. 忽视应该跳过的消息（即leader 已经 broadcast，但是未获得多数派确认，后续leader又有新的提交，则该消息应该被忽视/放弃）

方法：

• 选举leader时需保证leader拥有多数派认同的最大的zxid；与raft的log-up-to-date语意一致
• 通过epoch来避免宕机恢复的leader提交应忽略的消息；与raft的term作用一致

Reference

[1]. A simple totally ordered broadcast protocol

[2]. ZooKeeper Internals

Summary

paxos算法的的核心思想是“与其预测未来，不如限制当下”，即通过保证当前的操作，来一步一步达到预期

Theory

要求

Safety:

• 只有一个被提议的value被选定(validity)
• 两个不同的进程不能做出不一样的的选择(agreement)

Liveness

• 最终会有被提议的value被选定
• 如果一个value被选定，任意进程最终一定会得知这一结果

推导过程

首先设定三个角色 proposers，acceptors，learners。

要想有value被选定，则acceptor必须要接受proposer的提议，于是我们要求

• P1. 任意acceptor必须接受(accept)它收到的的第一个提议(proposal)

那么问题来了，多个proposers会提议多个value，无法满足safety. 于是我们考虑让acceptor可以接受（accept）多个提议，为了便于区分，我们考虑为提议增加一个total order的序号(proposal number)，即提议由proposal number + value组成 但是最终我们是要选定(chosen)一个value的, 于是我们考虑可以接受多个提议，但是我们必须保证这些提议的value都是一样的，于是我们进一步要求：

• P2. 如果value为v的提议被选定(chosen)，则所有number更大的且被选定的提议的value也必须为v

一个提议如果被选定(chosen)，那么至少被一个acceptor接受(accepted)过, 所以我们可以通过满足如下条件来达成P2

• P2a. 如果value为v的提议被选定(chosen)，那么所有number更大的且被任意acceptor接受过（accepted）的提议其value也必须是v

考虑一个acceptor c从没有收到提议，此时一个从故障中恢复的proposer发起了一个更高number的提议，且该提议与已经chosen的value不一样。按照P1，c肯定会accept该提议, 这样便违反了2a。于是我们强化一下P2a的要求

• P2b. 如果value为v的提议被选定(chosen)，那么由proposer发起的number更大的提议的value也必须是v

P2b通过限定proposer的动作来满足P2，通过归纳法我们可以得知，只要保证如下规则，就可以满足P2b

• P2c. 那么对于大多数(majority)acceptors,我们称之为集合S；如果一个提议(n，v)被发起，则要么1成立，要么2成立
  • S中不存在acceptor接受过(accepted) number 小于n的提议
  • v是S接受过的(accepted)所有提议里number小于n的提议中number最大的提议的value

只要满足P2c就可以满足P2b，进而满足P2；至此我们便有了更具体的方式来实现P2c,具体如下：

1. proposer选择一个proposal number n，然后向每个acceptors发起请求，要求acceptors：
   • 保证不再接受(accept)number小于n的提议，并且
   • 如果已经接受过(accepted)number小于n的提议，则这些提议中number小于n的最大的number以及该提议的value返回给proposer
2. 如果proposer收到大多数(majority)的acceptors的响应，则proposer可以发起一个序号为number的提议，其value是v
   • v是所有acceptor响应的(mi, vi)中最大的m对应的v
   • 如果没有acceptor响应(mi, vi)，则v由proposer自己决定

以上我们称之为PREPARE请求。利用PREPARE请求，我们完成了一个学习的过程，从而实现了P2c; proposal的具体实现我们归纳出来了，对应的acceptor的的要求也很容易得出：

• 当且仅当(iff)acceptor 没有响应number大于n的prepare请求时，才可以接受(accept)number为n的提议

由于acceptor收到prepare请求后会保证不再接受(accept) proposal number小于n的提议，则acceptor便没有必要再回复proposal number小于n的prepare请求，我们可以直接忽略，或回复error或null使proposer放弃后续提议. 于是我们可以将proposer和acceptor的动作综合起来描述如下：

• Phase 1
  • proposer生成一个proposer number n，然后发送prepare请求到所有（其实也可以是majority，但越多越能保证收到过半数的回复）acceptors
  • acceptor收到prepare请求后：
    • 如果之前有收到proposal number > n的prepare请求，则直接忽略该prepare请求，否则
    • 回复该prepare请求，同时如果之前有接受（accept）提议，则回复内容中带上接受的提议value和对应该value的最大的proposal number
• Phase 2
  • proposer收到总数过半（majority）的回复后：
    • 如果所有回复中都没有携带提议value，则proposal自己选择一个提议value
    • 否则从所有回复中选择proposal number最大的的value
    • 向所有(其实也可以是majority，但越多越能保证收到过半数的accept）acceptor发送上述得到的提议value和proposer number n
  • acceptor收到提议请求后：
    • 如果之前没有回复proposal number > n的prepare请求，则接受（accept）该请求

以上可以完成总数过半的acceptor 接受（accept）一个value，但并不代表被chosen，该value被chosen需要：

• 由learner来找出哪个提议（proposal number ＋ value）被总数过半的的acceptors接受了（accepted），方式有如下：
  • 由接受（accept）提议的acceptor向所有learner发送通知消息，开销 M＊N次通信（假设M个接受该提议的acceptor，N个learner）
  • 由接受（accept）提议的acceptor向某个learner发送通知消息，由该learner确定chosen结果后再广而告之，开销M＋N次通信
  • 扩大方法二中某个learner为多个learner，适当增加开销，但可以保证可靠性（learner单点问题）

TO BE CONTINUE!

Why

1983年由Dale Skeen 和 Michael Stonebraker提出了3PC协议来解决2PC阻塞的问题

What

3PC（two-phase-commit）其实就是将2PC的Phase 2拆分成了两个阶段：

时序图

• Phase 1:
  • Transaction coordinator(TC)首先写日志(write-ahead-log)记录事务执行状态，然后向所有Participants广播PREPARE消息，询问participant是否准备好commit（回复YES）或者选择abort（回复NO）
  • Participant收到PREPARE消息后，开始执行事务（考虑ACID-isolation，此时已经持有各种锁），如果执行中有任何问题则回复abort，如果事务执行完成则回复YES
  • TC收到所有的回复，进入Phase 2
• Phase 2:
  • 如果TC收到的响应均为YES，则向participants广播PRE-COMMIT消息，否则广播ABORT消息（广播之前需更新日志，记录事务执行状态）
  • 如果participant收到PRE-COMMIT消息，回复ACK
  • 如果participant收到ABORT消息，终止事务
• Phase 3:
  • 如果TC在超时时间内收到所有的ack，则向participants广播COMMIT消息，否则广播ABORT消息（广播之前需更新日志，记录事务执行状态）
  • Participant收到COMMIT/ABORT消息后，将事务正式commit/abort（考虑ACID-isolation，commit/abort完成后会释放所有锁）并回复ack

How

状态迁移图

来看异常处理的情况：

• Phase 1:
  • Transaction coordinator（TC）发送PREPARE之后，如果超时时间内未收到响应，则放弃该事务，进入Phase 2 向所有participants广播ABORT
    • 此时收到ABORT的participants会正常终止事务
  • 当Participant收到PREPARE后，如果回复YES的时候超时（无法确定TC是否收到消息），retry几次后进入Phase 2
  • 当Participant收到PREPARE后，如果回复NO的时候超时（无论TC是否收到，TC都会进入Phase 2然后广播ABORT消息），重试几次之后可以主动终止事务
• Phase 2:
  • TC发送了PRE-COMMIT/ABORT消息之后，如果长时间没有收到ack或者宕机重启之后都会进入Phase 3，发送ABORT消息
  • Participants如果长时间没有收到PRE-COMMIT消息，则可以主动终止事务
  • Participants如果收到PRE-COMMIT后，回复ack之前发生宕机，则可以主动终止事务
• Phase 3:
  • TC发送了COMMIT/ABORT消息之后，如果长时间没有收到ack或者宕机重启之后都会根据write-ahead-log的内容重新发送消息，重试几次后结束（如果是发送COMMIT，则意味着TC认为事务已经完成；ABORT消息同理）
  • Participants如果长时间没有收到COMMIT/ABORT消息，执行commit

Weakness

3PC是一个理想状态的协议，假设fail-stop模型，并且可以通过timeout来准确判断网络故障还是宕机的情景(synchronous systems)下的协议（上文我们是按照真实环境来分析解析的）

• 所以典型的一个3PC的冲突情景如下：  - Phase 2 TC 广播PRE-COMMIT消息，如果P1在收到消息前宕机，因而TC在Phase 3广播ABORT消息
  • 在Phase 2，P2回复ack之后进入Phase 3，并且与TC直接发生网络分区(network-partition)导致P2无法收到ABORT消息，故而自行决定commit
• 网络通信需要3 RTT，开销较大

其他:

• 标准的3PC假设的前提是理想状态，即fail-stop（the server only exhibits crash failures，且不恢复）模型
• 标准的3PC描述Phase 3时，如果TC收到多数(majority)的ack，即可广播COMMIT（没有收到ack则意味着participant宕机且不恢复）
• 根据以上两点，所以标准的3PC在synchronous systems（有限的timeout）下是可行的方案（上文的典型冲突情景不再发生）

PS：

• 根据F·L·P定理在asynchronous system 模型下实现分布式共识是不可能的，但是实践之中我们能尽可能的去达成共识

Reference

[1]. D. Skeen and M. Stonebraker, “A Formal Model of Crash Recovery in a Distributed Systems,” IEEE Transactions on Software Engineering, SE-9, 3, (May 1983), pp. 219–228.

[2]. Sukumar Ghosh. 《Distributed Systems An Algorithmic Approach Second Edition》 14.5 Atomic Commit Protocols

[3]. Three-Phase Commit Protocol

[4]. Distributed Systems W4995-1 Fall 2014 lecture17

Why

针对数据库事务ACID-Atomicity，单机可以使用write-ahead-log实现1PC（one-phase-commit）即可，但是如果是分布式环境，考虑机器故障，网络不可靠1PC无法完成ACID-Atomicity

What

2PC（two-phase-commit）是已故图灵奖得主，事务处理领域大师Jim Gray提出的，用以解决分布式数据库事务ACID-Atomicity的一种共识(consensus)算法

• Phase 1:
  • Transaction coordinator首先写日志(write-ahead-log)记录事务执行状态，然后向所有Participants广播PREPARE消息，询问participant是否准备好commit（回复YES）或者选择abort（回复NO）
  • Participant收到PREPARE消息后，开始执行事务（考虑ACID-isolation，此时已经持有各种锁），如果执行中有任何问题则回复abort，如果事务执行完成则回复YES
  • Transaction coordinator收到所有的回复，进入Phase 2
• Phase 2:
  • 如果Ttransaction coordinator超时时间内收到的响应均为YES，则向participants广播COMMIT消息，否则广播ABORT消息（广播之前需更新日志，记录事务执行状态）
  • participant收到COMMIT/ABORT消息后，将事务正式commit/abort（考虑ACID-isolation，commit/abort完成后会释放所有锁）并回复ack

How

来看异常处理的情况：

• Phase 1:
  • Transaction coordinator（TC）发送PREPARE之后，如果超时时间内未收到响应，则放弃该事务，进入Phase 2 向所有participants广播ABORT
    • 此时收到ABORT的participants会正常终止事务
  • 当Participant收到PREPARE后，如果回复YES的时候超时（无法确定TC是否收到消息），retry几次后进入Phase 2
  • 当Participant收到PREPARE后，如果回复NO的时候超时（无论TC是否收到，TC都会进入Phase 2然后广播ABORT消息），重试几次之后可以主动终止事务
• Phase 2:
  • TC发送了COMMIT/ABORT消息之后，如果长时间没有收到ack或者宕机重启之后都会根据write-ahead-log的内容重新发送消息，直到收到ack为止（无限重试）
  • 一旦进入Phase 2，Participants会失去主动终止或提交事务的权利，只能等待TC发送的COMMIT/ABORT消息，亦或者主动发送get status消息
  • 事务是有一个全局唯一的事务ID唯一确认的，这一点可以确保TC重新发送COMMIT/ABORT消息时恢复连接的participant可以识别并回复ack

Weakness

2PC is a blocking protocol

由于TC宕机或者与部分participant断开连接（或者Participant宕机），则意味着阻塞（blocking），直到宕机恢复网络恢复为止。

以TC宕机为例，考虑ACID-isolation 这会导致participant长时间持有lock而不释放，影响participant可用性

Reference

[1]. Martin Kleppmann. 《Designing Data-Intensive Applications》9.Consistency and Consensus

[2]. Sukumar Ghosh. 《Distributed Systems An Algorithmic Approach Second Edition》 14.5 Atomic Commit Protocols

[3]. Notes on Data Base Operating Systems. Jim Gray. IBM Research Laboratory. San Jose, California. 95193. Summer 1977

Introduce

一般正确性的证明标准有两个，分别是safety properties 和 liveness properites

Safety Properites

通常safety properites是指：“bad things never happen”。

举例

例如互斥操作(不管单机还是分布式)的safety properites可以是: - 最多只能有一个process or thread进入临界区 - 至少有一个process or thread有资格进入临界区

Liveness Properites

通常liveness properites是指：”good things eventually happen”。

对应现实世界的一个例子就是“正义终将来临”，至于具体什么时候，不太好说。

liveness properites的描述经常带有”eventually”字样，例如eventually consistency就是liveness properites。

举例

例如互斥操作(不管单机还是分布式)的liveness properites可以是: - 每个试图进入临界区的process or thread最终都将进入临界区 - 至少有一个process or thread有资格进入临界区

Proof

常见的证明方式暂时未做了解 ☻

Introduce

于2002年提出的CAP理论（三选二的方式来评估分布式系统）确实为分布式系统领域的发展提供了指导价值，但是就今天而言，这套理论已经意义微小了

Consistent

这里的一致性指的是强一致，又称linearizable或atomic。

论文中的描述如下：

Under this consistency guarantee, there must exist a total order on all operations such that each operation looks as if it were completed at a single instant.

简单来讲就是如果把分布式系统看做一个黑盒，在外部看起来这个系统就是和单机没有区别。

具体的来说：

任意的一条读操作R，如果发生在某条写操作W完成之后，那么R读到的要么是W的内容，要么是W之后的写操作写入的内容

更详细的描述可以参考linearizable

这里的consistent 和 ACID中的consistent是完全不同的概念： - ACID-consistent特指事务 - CAP-consistent仅仅是请求/响应操作顺序的属性

Available

论文中的定义：

For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response

这里的response是指no-error response

即使是Probabilistic availability，在任意的failures发生时也不会影响针对CAP-available的结论，但是这里为了简单起见特指100% availability。

如果专门针对partition-tolerance而言的话，available可以描述为：

even when severe network failures occur, every request must terminate.

terminate 是指任意使用该分布式系统的算法都会终止，注意是算法的终止。

Partition Tolerance

网络割接和交换机故障都会造成network partition

network partition 图示:

CAP的问题也是从这里开始体现：

• partition tolerance并非和CA对等的属性，而是一种因果的关系：partition发生时是选A还是选C，即如何去tolerant partition，
• 分布式系统需要考虑的其他网络问题也很多，包括延迟，网络不可靠等，并不仅仅是partition，所以使用CA,CP,AP去描述一个分布式系统并不完整
• 很多分布式系统可以根据业务需求降低对consistent的要求，降低对available的要求，所以根本无法用CAP来描述

Partition in practice

尽管network partition不能涵盖分布式系统所有需要面对的网络问题，但是它确实是网络问题中的一个难点和重点

single-leader-Architecture

当某个client和leader处于不同partition时，此时CAP-available丢失，如果按照CAP理论，只能称之为CP

multi-leader-Architecture

情景一

某个client和所有的leader都不在一个partition，此时CAP-available丢失，如果按照CAP理论，只能称之为CP

如果你允许（业务上允许）图示中的client2对replica进行read操作，则CAP-consistent也会丢失，只能称之为P（CAP的3选2现在成了3选1）

情景二

leaders不在一个partition，此时CAP-consistent丢失，如果按照CAP理论，只能称之为AP

dynamo-style-Architecture(no-leader)

R + W > N,但是当network partition发生时，如果某个client被划分到了节点较少的一侧，那么CAP-available丢失，只能称之为CP；

如果你允许（业务上允许）图示中的client2进行read操作，则CAP-consistent也会丢失，只能称之为P（CAP的3选2现在成了3选1）

References

1. Martin Kleppmann. please-stop-calling-databases-cp-or-ap
2. Martin Kleppmann. 《Designing Data-Intensive Applications》9.Linearizability