Leaderless的复制方式，抛弃了之前leader和follower的概念。数据写请求可以由客户端直接发送给多个数据副本，或者发送给coordinator节点，由coordinator节点发送给所有服务器。coordinator节点并不会强制数据写入的顺序。
下面我们介绍leaderless模型的一些细节点。
当节点故障时写数据
假设系统中包含三个节点，当一个节点故障时，对于leaderless模型来说并不需要进行处理，有两个节点在线已经是足够的。此时会通知客户端该数据写入成功。
Quorum读，Quorum写和节点故障恢复时的读恢复
当故障的节点恢复时，如果读取该节点的数据，将得到过期的错误数据。解决方法是当客户端访问数据库时，将读请求并发发送给该恢复节点和其他节点，此时得到过期的数据和最新的数据，通过版本号判断哪个数据是最新的，并返回该数据。
读修复和反熵（anti-entropy）
当故障的节点恢复时，如何使该节点的数据追上最新进度？这里有两种方式：
- 读修复：读取多节点的数据，并用最新的数据更新过期的数据，这种方法适合写频繁的系统。
- 反熵进程：存在一个后台进程不停地扫描数据replica之间的差异，并复制缺失的数据。该过程并不能保证数据复制的顺序性，因此可能存在较长的延迟。
读写仲裁（Quorum for reading and writing）
这是一种分布式系统一致性的投票算法。假设有n个数据副本，每个写请求在w个节点上执行成功，读取时读取n个节点的数据，则必须保证：，才能确保读取到最新数据，这里n和w分别是读和写的最小投票数。
一个常见的配置方式是，n为奇数，设置向上取整。然而可以根据系统的情况进行调整，比如对于读多写少的系统，可以设置
，
，好处是提高读取的性能，但当任意一个节点故障时，数据库的写请求将失败。
如果w+r>n，r中的至少一个数据副本是最新的
仲裁一致性的限制
仲裁的基本要求是读写的节点必须有一个是重叠的，这样就可以保证一定读取到最新的数据。如果将w和r的取值变小，将有可能读取到过期数据，但会换来更低的延迟和更高的可用性。
即使在的情况下，也有可能读取到过期的数据，可能的场景是：
- 草率的仲裁（sloppy quorum），可能会使w个写入的节点和r个读取的节点完全不同，无法保证读写节点有至少一个重叠。
- 两个写请求同时发生，安全的处理方式是合并两个写请求。如果使用基于时间戳的LWW（Last write win），可能由于时钟偏移等问题导致数据丢失。
- 读写同时发生，写请求只在某些节点生效，无法确定读取的是新数据还是旧数据。
- 写请求在小于w个节点成功时，数据副本不能回滚到之前成功的状态，后续读取的数据可能是新的或者旧的。
- 带有新值的节点故障，从带有旧值的数据副本恢复，存储新值的节点小于w个，破坏了仲裁条件。
- 即使一切正常，也有可能由于时序关系满足一些边缘条件。
因此仲裁一致性并不能保证完全的一致性，w和r的值可能调整过期数据读取的概率。如果想要保证强一致性，还必须实现事务的机制。
监控过期数据
在实际应用时，系统需要监控一些运行指标。对于Single-leader模型，需要监控的是副本延迟，由于数据的顺序修改的，可以通过计算follower的数据位置和leader的数据位置之差得到这个指标。
但在leaderless模型中，由于写请求没有固定的处理顺序，监控会比较困难。此外，如果使用了读修复的过期数据处理方式，对于从未读取的数据，过期数据的保留时间可能是很长的。
已经有一些研究，可以通过n，w和r的值，预测过期数据的期望比例，但还并不成熟。
Sloppy Quorums和Hinted Handoff
仲裁一致性使得leaderless模型的数据库可以实现高可用和低延迟，偶尔会读取到过期数据。由于网络连接情况比较复杂，可能有些客户端能连接到一些节点，其他客户端连接不到，因此可能导致小于w和r的可用节点存在，使客户端无法实现仲裁。
针对这种场景，有两种解决方式供选择：
- 如果达不到仲裁需要的w和r个节点，请求返回失败。
- 接收写请求，并把数据写到客户端能够连接的，在n个节点范围以外的其他节点。
后者成为Sloppy Quorum（草率仲裁），也就是读和写仍然需要w和r个节点的响应，但其中包括n个节点范围以外的其他节点。
这种方法有点类似，比如我们家门锁坏了外，可以先临时在邻居家呆一会，等家里的门锁修好了再回家。这被称为Hinted Handoff（隐含移交）。
该方法可以提高写的可用性，任意w个节点，包括n个节点范围以外的其他节点，能够响应写请求，就可以成功写入。然后，可能由于数据不在n个节点上，读取是取不到最新的数据。
多数据中心操作
可以很容易的将Leaderless模型应用到多数据中心，每个写请求在本地的数据进行仲裁一致性的判断，然后将数据异步复制到其他数据中心。
检测并发写
即使使用Quorom一致性，Leadless模型同样存在并发写的问题，核心问题是不同节点接收到写请求的顺序可能不一致。
并发写的问题
并发写的处理为了实现最终一致性，所有数据副本朝着相同的值变化。之前在Multiple-leader中介绍过关于处理并发写冲突的问题，这里再进一步详细介绍一下。
Last write wins
和之前讨论的类似，使用一个标记，比如时间戳，判断写请求的先后顺序，处理最新的写请求，丢弃它之前的所有写请求。该方法可能会导致数据丢失，因此在不允许数据丢失的场景是不合适的，而对于数据只写入一次，并且在写入后就不再变化的情况，使用该方法是合适的。
happens-before关系和并发
如何定义happens-before关系？比如有两个写操作，分别为INSERT一行数据和UPDATE该行数据的值，UPDATE命令就依赖INSERT命令，存在因果关系，这里称INSERT happens-before UPDATE。两个写操作也可能完全没有因果关系，就不存在happens-before关系。
以下两个图的写操作分别存在和不存在happens-before关系。
存在happens-before关系
不存在happens-before关系
捕捉happens-before关系
如何判断两个写操作之间是否存在happens-before关系？以下举一个示例，两个客户端同时修改同一个购物车：
两个客户端并发修改同一个购物车
- 客户端1在购物车中添加milk，服务端保存为版本1，并返回客户端版本号1；
- 客户端2在购物车中添加eggs，并且不知道客户端1已经添加milk，服务端保存eggs和milk为版本2，返回[milk]和[eggs]给客户端，以及版本号2；
- 客户端1想在购物车中添加flour，由于它不知道客户端2已经添加了eggs，因此它期望添加后的数据为[milk, flour]，它将milk和flour和版本号1发送给服务端。服务端接收到之后，从版本号判断出该请求的顺序是在版本号1的请求之后的，并且中间有一个并发的请求写入了eggs，因此服务端用[milk, flour]覆盖了版本号1的milk，并分配版本号3，同时保留版本号2的eggs，把[milk, flour]、[eggs]和版本号3返回给客户端1；
- 与此同时，客户端2想在购物车中添加ham，它并不知道客户端1添加了flour。客户端2之前接收到[milk]和[eggs]，它合并所有数据，并添加ham，得到[milk, eggs, ham]，和版本号2一起发送给服务端。服务端接收到后，覆盖了版本号2的数据[eggs]为[milk, eggs, ham]，分配版本号4，保持版本号3的数据不变，返回给客户端2[milk, eggs, ham]和[milk, flour]，以及版本号4；
- 最终，客户端1想在购物车中添加bacon，和上述过程类似，它整合上次接收到的所有数据，和本次要添加的数据，得到[milk, flour, eggs, bacon]，和版本号3一起发送给服务端。
该过程的数据流如下图所示：
因果关系依赖图
这种方法的核心是分别记录各客户端的数据，并增加版本标记，通过版本号判断写请求之间是否存在依赖关系。该方法下客户端保存的并不是和客户端相同的最新数据，但旧版本的数据最终会被覆盖，并且没有写请求丢失。
合并并发写请求
上述针对happens-before的处理方法，需要客户端进行一些额外的工作，其中包括对于同辈数据的合并。
比如上面的例子中，客户端接收到两个同辈数据[milk, flour, eggs, bacon]和[eggs, milk, ham]，如果处理这两份数据呢？
可以考虑进行去重合并，得到的结果为[milk, flour, eggs, bacon, ham]。但如果购物车允许删除物品，采用这种方法会使得被删除的物品重新出现的购物车中。解决方法是不直接删除物品，而且加上一个删除标记，在合并时优先处理删除标记。
合并的逻辑是很复杂，并且容易出错的，可以使用一些已有的自动合并算法。
版本向量
上面的例子是针对只有一个数据副本的情况，如果是多数据副本的情况，所有数据副本的版本组成一个向量。
网友评论