1.前言
前面两节讲了单leader模式和多leader模式，这一节讲解无leader模式
之前有leader的模型都是基于这样的假设：
一个client把写请求发送给leader，然后leader把数据备份到其他节点上。
在一些无leader的模式实现中，client把写请求发送给若干节点。
另外一些实现中，需要一个调节器节点来代表client完成。
2.当节点挂掉时的写入
在写数据时，如果有一个节点挂了怎么办。
在单leader模式下提出了故障转移，
在无leader模式下则不存在，假设一个写请求发送给所有节点，示意图如下
假设挂掉的节点回来了，client读取数据时，会从该节点读到旧的数据，怎么解决呢？
client发送读请求给若干节点,而不是一个。通过版本号等实现取出最新的一个
2.1 读修复以及anti-entropy
备份要求最终一致性，即各节点最终数据相同。但是当有一个节点挂了再恢复，如何catch up它错过的写呢。
在Dynamo形式的db中有两种机制
读修复：
如上图中，client端从节点1,2,3读取数据发现3的数据版本是旧的，则把最新的数据写进去。
Anti-entropy:
一些db有后台进程不断检测各节点的区别，把丢失的数据补上。不保证写入的书序，可能会有明显的延迟。
注意读修复相当于一种lazy的思路，如果有数据一直没有被读，那么就不会被修复。
2.2 集群的写和读
前面讲到的，写入到若干节点，从若干节点读，若干到底是多少呢？
假设n个节点，写请求必须被w个节点确认写成功，读请求必须被至少r个节点返回结果数据。
那么，只要w+r>n，读到的数据就能保证是最新的（抽屉原理）*
在Dynamo风格的数据库中，n，w，r一般满足w=r=(n+1)/2,其中n是奇数。
从下图可以看出
3.集群一致性的限制
通常，w+r都会选择“大多数”(>n/2),这样能保证w+r>n,
但是集群实际并不要求“大多数”，只要w+r>n，能够保证w，r中有重复的节点即可.
当然也可以让w+r<=n,这样更可能让client读到旧的数据，但是好处是延迟低，可用性更强了。
即使w+r>n,也会有如下的边缘case
1.sloppy quorum如果用了（后面会讲到，简单说就是有一些备用的写节点，但是不算在集群中）
那么即使w和r数量都得到了满足，也有可能两者没有重复节点（w中的一部分是sloppy中新加的备用写节点）
2.两个写同时到来，谁先谁后呢（时间戳有可能有问题），后面会讲
3.写和读同时发生，返回的数据到底是写之前还是写之后的
4.如果最后写成功的数量小于w，已经写成功的机器也不会回滚
（即使有can commit或者pre commit这类机制或者WAL，它也不知道是否该回滚，因为没有leader作为协调）
5.如果一个带有新值的节点挂掉了，再恢复的时候用的旧值。
那么真正新值的节点数就<w了
（同上，WAL也不管用）
6.各种时间戳需要小心处理
综上，w，r只是降低陈旧数据出现的可能，但是不能完全保证。更像的保证需要事务或者consensus
3.1 陈旧检测
需要检测现在db是否在返回最新的结果。
对于单leader的模式，由于写都是按顺序执行的，每个写都会有一个位置或者id，可以方便检测。
但是在无leader模式中，写不会有特定的顺序。
目前有一些研究是根据n，w，r来对陈旧数据进行测量。
但是没有普遍应用。
3.2 Sloppy quorums
由于网络原因，client可能连接不上一部分节点。这样的话，反馈读写请求的节点就会小于w和r。
因此面临下述trade off
1.面对不能达到r和w数量的集群，是否直接返回错误
2.仍然接收写请求，写入一些client可达但是不包含在n个节点中的节点（可以理解成备用的）
第二种方式就是 Sloppy quorums：读写依旧要求r，w个节点，但是这些包括了除了n个节点之外的一些备用节点。
当网络修复之后，这些备用节点会把这些数据发送给n个节点之内的挂掉的节点。
这种方式加强了写的可用性，但是也代表着即使w+r>n也不能保证会读到最新的数据，因为数据可能在n之外的备用节点中
3.3 多数据中心的操作
无leader模型也适合多数据中心，因为他被设计容忍并发写，网络中断以及延迟的。
每个写都会发送到所有备份节点，会同步发送一个本地的数据中心，然后异步发送到其他的数据中心。
4.并发写检测
Dynamo风格的db允许多个client同时对同一个key进行写，代表会发生冲突（类似于多leader时的写冲突）
这个问题可能由于网络延迟和机器挂掉等有关系，案例如下
为了达到最终一致性，节点应该收敛到同一个值。这个和多leader时讲解的“处理写冲突”类似。
这里深入一点
4.1 Last Write wins(丢掉其他并发写)
一个方法是声明：各个节点值记录最近的值，且允许老的值被覆盖和丢弃
但是“近期”这个具有误导性。因为每个client都不知道其他client的写行为，所以根本没有严格的第一个写，第二个写这种。顺序都是无序的。
即使原本写没有顺序，我们可以强加一个顺序
比如加上时间戳，称为last write wins(LWW).
LWW能够达到最终一致性，以损失持久性为代价。因为这种方法会丢弃部分写的数据（因为时间戳不是最新的）
4.2 happens-before和concurrent
这里提出一个依赖关系
操作A happens-before 操作B在以下条件下成立：
B知道A操作
B依赖A操作
如果两个操作互相没有happens-before关系，那么称为两个操作时concurrent的，而不一定要求两者的发生时间要有什么关系
4.3 定位 happens-before的关系
在单节点的模式下可以如下操作
1.server对于每个key维持一个版本，每次写的时候版本自增。版本和值一起存储
2.client读一个key的时候，server返回所有未覆盖的值以及最新的version，client再写之前一定要先读
3.client写一个key时，必须把之前所有读到记录的版本merge起来
4.当server收到一个写的时候，把写请求中包含到的各个版本的数据都覆盖掉，并且记录住最高版本
在这之后又引入了并发merge的问题，以及多节点无leader模式的处理。
通过各个节点都记录版本来实现一个version vectors来完成。
这里面有个例子，就不讲了，原书P187-190
思考
r，w节点个数的思考
r，w不一定要=(n+1).2,只要满足r+w>n即可，不要有思维定势
本文关于concurrent的定义
两个操作没有逻辑依赖关系，或者互相不知道存在，则称为concurrent的，而不是指代现实中的时间。
关于多leader的写冲突检测以及无leader模型的并发写问题
都是先提出LLW，然后说分布式时间戳不准确
加版本号等方式解决，但是又会引入merge之类同样复杂的事情。
目前来说这种冲突写，处理的方式还是非常poor的
这部分看起来也就是提出一些issue让我们注意，讲出部分的解决思路
但是看起来觉得有点重复啰嗦，而且还没有很好的解决。
