在上一篇《分布式数据之多副本的读写流程》🔗 着重讲 Replication 的数据读写，在本篇内容中，我们将会侧重 Replication 的模型讲解。
目录
多主模型
多主模型应用场景
多个数据中心
离线工作的客户端
协同编辑
处理写入冲突
冲突检测
冲突避免
冲突收敛
自定义解决
界定冲突
多主复制拓扑
无主模型
有节点故障时的写入
读时修复和反熵
Quorum 读写
Quorum 一致性的局限
一致性监控
放松的 Quorum 和提示转交
多数据中心
并发写入检测
后者胜（Last-Write-Win）
发生于之前（Happens-before）和并发关系
确定 Happens-Before 关系
合并并发值
版本向量
单主模型一个最大问题：所有写入都要经过它，如果由于任何原因，客户端无法连接到主副本，就无法向数据库写入。
于是自然产生一种想法：多主行不行？
多主复制（multi-leader replication）：有多个可以接受写入的主副本，每个主副本在接收到写入之后，都要转给所有其他副本。即一个系统，有多个写入点。
单个数据中心，多主模型意义不大：复杂度超过了收益。总体而言，由于一致性等问题，多主模型应用场景较少，但有一些场景，很适合多主：
数据库横跨多个数据中心
需要离线工作的客户端
协同编辑
多个数据中心
假设一个数据库的副本，横跨多个数据中心，如果使用单主模型，在写入时的延迟会很大。那么每个数据中心能不能各配一个主副本？
单主和多主，在多数据中心场景下的对比：
但是多主模型在一致性方面有很大缺陷：如果两个数据中心同时修改同样的数据，必须合理解决写冲突。另外，对于数据库来说，多主很难保证一些自增主键、触发器和完整性约束的一致性。因此在工程实践中，多主用的相对较少。
离线工作的客户端
离线工作的一个应用的多个设备上的客户端，如果也允许继续写入数据。如：日历应用。在电脑上和手机上离线时如果也支持添加日程。则在各个设备联网时，需要互相同步数据。
这种离线后还继续工作的多个副本，本质上就是一个多主模型：每个主都可以独立的写入数据，然后在网络连通后解决冲突。但，如何支持离线后正常地工作，联网后优雅地解决冲突，是一个难题。
Apache CouchDB 的一个特点便是支持多主模型。
协同编辑
Google Docs 等类似 SaaS 模式的在线协同应用越来越流行。
这种应用允许多人在线同时编辑文档或者电子表格，其背后的原理，与上一节离线工作的客户端很像。
为了实现协同，并解决冲突，可以：
悲观方式：加锁以避免冲突，但粒度需要尽可能小，否则无法允许多人同时编辑一个文档。
乐观方式：允许每个用户无脑写入，然后如果有冲突，交由用户解决。
Git 也是一个类似的协议。
多主模型最大的问题是：如何解决冲突。
考虑 wiki 一个页面标题的修改：
用户 1 将该页面标题从 A 修改到 B
用户 2 将该页面标题从 A 修改到 C
两个操作在本地都修改成功，然后异步同步时，会出现冲突。
冲突检测
有同步或者异步的方式进行冲突检测。
对于单主模型，当检测到冲突时，由于只有一个主副本，可以同步地检测冲突，从而解决冲突：
让第二个写入阻塞，直到第一个写完成。
让第二个写入失败，进行重试。
但对于多主模型，两个写入可能会在不同主副本立即成功。然后异步同步时，发现冲突，但为时已晚（没有办法简单决定如何解决冲突）。
虽然，可以在多主间使用同步方式写入所有副本后，再返回请求给客户端。但这会失掉多主模型的主要优点：允许多个主副本独立接受写入。此时，蜕化成单主模型。
冲突避免
解决冲突最好的方式是在设计上避免冲突。
由于多主模型在冲突发生后再去解决会有很大的复杂度，因此常使用冲突避免的设计。
假设你的数据集可以分成多个分区，让不同分区的主副本放在不同数据中心中，那么从任何一个分区的角度来看，变成了单主模型。
举个栗子：对于服务全球用户的应用，每个用户就近固定路由到附近的数据中心。则，每个用户信息都有唯一的主副本。
但如果：
用户从一个地点迁移到了另一个地
点某个数据中心损坏，导致路由变化
就会对该设计提出一些挑战。
冲突收敛
在单主模型中，所有事件比较容易进行定序，因此我们总可以用后一个写入覆盖前一个写入。
但在多主模型中，很多冲突无法定序：从每个主副本来看，事件顺序是不一致的，并且没有哪个更权威一些，那么就无法让所有副本最终收敛（convergent）。
此时，我们就需要一些规则，来让其收敛：
给每个写入一个序号，并且后者胜。本质上是使用外部系统对所有事件进行定序。但可能会产生数据丢失。举个例子，对于一个账户，原有 10 元，客户端 A - 8，客户端 B - 3，任何一个单独成功都有问题。
给每个副本一个序号，序号更高的副本有更高的优先级。这也会造成低序号副本的数据丢失。
提供一种自动的合并冲突的方式。如，假设结果是字符串，则可以将其排序后，使用连接符进行链接，如在之前 Wiki 的冲突中，合并后的标题为“B/C”。
使用程序定制一种保留所有冲突值信息的冲突解决策略。也可以将这个定制权，交给用户。
自定义解决
由于只有用户知道数据本身的信息，因此较好的方式是，将如何解决冲突交给用户。即，允许用户编写回调代码，提供冲突解决逻。该回调可以在：
写时执行。在写入时发现冲突，调用回调代码，解决冲突后写入。这些代码通常在后台执行，并且不能阻塞，因此不能在调用时同步的通知用户。但打个日志之类的还是可以的。
读时执行。在写入冲突时，所有冲突都会被保留（如使用多版本）。下次读取时，系统会将所有数据本版本返回给用户，进行交互式的或者自动的解决冲突，并将结果写回系统。
上述冲突解决只限于单个记录、行、文档层面。
界定冲突
有些冲突显而易见：并发写同一个 Key。
有些冲突则更隐晦，考虑一个会议室预定系统。预定同一个会议室不一定会发生冲突，只有预定时间段有交叠，才会有冲突。
复制拓扑（replication topology）描述了数据写入从一个节点到另一个节点的传播路径。
在只有两个主副本时，拓扑是确定的，如图 5-7。Leader1 和 Leader 都得把数据发给对方。但随着副本数的增多，数据复制拓扑就会有多种选择，如下图：
上图表示了 ≥ 4 个主副本时，常见的复制拓扑：
环形拓扑。通信跳数少，但是在转发时需要带上拓扑中前驱节点信息。如果一个节点故障，则可能中断复制链路。
星型拓扑。中心节点负责接受并转发数据。如果中心节点故障，则会使得整个拓扑瘫痪。
全连接拓扑。每个主库都要把数据发给剩余主库。通信链路冗余度较高，能较好的容错。
对于环形拓扑和星型拓扑，为了防止广播风暴，需要对每个节点打上一个唯一标志（ID），在收到他人发来的自己的数据时，及时丢弃并终止传播。
全连接拓扑也有自己问题：尤其是所有复制链路速度不一致时。考虑下面一个例子：
两个有因果依赖的（先插入，后更新）的语句，在复制到 Leader 2 时，由于速度不同，导致其接收到的数据违反了因果一致性。
要想对这些写入事件进行全局排序，仅用每个 Leader 的物理时钟是不够的，因为物理时钟：
可能不能够充分同步
同步时可能会发生回退
可以用一种叫做版本向量（version vectors） 的策略，对多个副本的事件进行排序，解决因果一致性问题。下一节会详细讨论。
最后忠告：如果你要使用基于多主模型的系统，一定要知晓上面提到的问题，多做测试，确保其提供的保证符合你的使用场景。
有主模型中，由主副本决定写入顺序，从副本在写入上不直接和客户端打交道，只是重放其对应的主副本的写入顺序（也可以理解为主副本为从副本的客户端）。
而无主模型，则允许任何副本接受写入。
在关系数据库时代，无主模型已经快被忘却。从 Amazon 的 Dynamo 论文开始，无主模型又重新大放异彩，Riak，Cassandra 和 Voldemort 都受其启发，可以统称为 Dynamo 流（Dynamo-style）。
奇特的是，Amazon 的一款数据库产品 DynamoDB，和 Dynamo 并不是一个东西。
通常来说，在无主模型中，写入时可以：
由客户端直接写入副本。
由协调者（coordinator） 接收写入，转发给多副本。但与主副本不同，协调者并不负责定序。
基于主副本（leader-based）的模型，在有副本故障时，需要进行故障切换。
但在无主模型中，简单忽略它就行。
多数派写入，多数派读取，以及读时修复。
由于写入时，简单的忽略了宕机副本；在读取时，就要多做些事情了：同时读取多个副本，选取最新版本的值。
读时修复和反熵
无主模型也需要维持多个副本数据的一致性。在某些节点宕机重启后，如何让其弥补错过的数据？
Dynamo 流派的存储中通常有两种机制：
读时修复（read repair），本质上是一种捎带修复，在读取时发现旧的就顺手修了。
反熵过程（anti-entropy process），本质上是一种兜底修复，读时修复不可能覆盖所有过期数据，因此需要一些后台进程，持续进行扫描，寻找陈旧数据，然后更新。这个博文对该词有展开描述：https://www.influxdata.com/blog/eventual-consistency-anti-entropy/。
Quorum 读写
如果副本总数为 n，写入 w 个副本才认定写入成功，并且在查询时最少需要读取 r 个节点。只要满足 w + r > n，我们就能读到最新的数据（鸽巢原理）。此时 r 和 w 的值称为 quorum 读写。即这个约束是保证数据有效所需的最低（法定）票数。
在 Dynamo 流派的存储中，n、r 和 w 通常是可以配置的：
n 越大冗余度就越高，也就越可靠
r 和 w 都常都选择超过半数，如 (n+1)/2
w = n 时，可以让 r = 1。此时是牺牲写入性能换来读取性能。
考量满足 w+r > n 系统对节点故障的容忍性：
如果 w < n，则有节点不可用时，仍然能正常写入。
如果 r < n，则有节点不可用时，仍然能正常读取。
特化一下：
如果 n = 3，r = w = 2，则系统可以容忍最多一个节点宕机。
如果 n = 5，r = w = 3，则系统可以容忍最多两个节点宕机。
通常来说，我们会将读或者写并行的发到全部 n 个副本，但是只要等到法定个副本的结果，就可以返回。
如果由于某种原因，可用节点数少于 r 或者 w，则读取或者写入就会出错。
由于 w + r > n 时，总会至少有一个节点（读写子集至少有一个节点的交集）保存了最新的数据，因此总是期望能读到最新的。
当 w + r ≤ n 时，则很可能会读到过期的数据。
但在 w + r > n 时，有一些边角情况（corner case），也会导致客户端读不到最新数据：
使用宽松的 Quorum 时（n 台机器范围可以发生变化），w 和 r 可能并没有交集。
对于写入并发，如果处理冲突不当时。比如使用 last-win 策略，根据本地时间戳挑选时，可能由于时钟偏差造成数据丢失。
对于读写并发，写操作仅在部分节点成功就被读取，此时不能确定应当返回新值还是旧值。
如果写入节点数 < w 导致写入失败，但并没有对数据进行回滚时，客户端读取时，仍然会读到旧的数据。
虽然写入时，成功节点数 > w，但中间有故障造成了一些副本宕机，导致成功副本数 < w，则在读取时可能会出现问题。
即使都正常工作，也有可能出现一些关于时序（timing）的边角情况。
因此，虽然 Quorum 读写看起来能够保证返回最新值，但在工程实践中，有很多细节需要处理。
如果数据库不遵守之前副本滞后小节引入的几个一致性保障，前面提到的异常仍然可能会发生。
一致性监控
对副本数据陈旧性监控，能够让你了解副本的健康情况，当其落后太多时，可以及时调查原因。
基于领导者的多副本模型，由于每个副本复制顺序一致，则可以方便的给出每个副本的落后（lag）进度。
但对于无主模型，由于没有固定写入顺序，副本的落后进度变得难以界定。如果系统只使用读时修复策略，则对于一个副本的落后程度是没有限制的。读取频率很低数据可能版本很老。
最终一致性是一种很模糊的保证，但通过监控能够量化“最终”（比如到一个阈值），也是很棒的。
正常的 Quorum 能够容忍一些副本节点的宕机。但在大型集群（总节点数目 > n）中，可能最初选中的 n 台机器，由于种种原因（宕机、网络问题），导致无法达到法定读写数目，则此时有两种选择：
对于所有无法达到 r 或 w 个法定数目的读写，直接报错。
仍然接受写入，并且将新的写入暂时交给一些正常节点。
后者被认为是一种宽松的法定数目 （sloppy quorum）：写和读仍然需要 w 和 r 个成功返回，但是其所在节点集合可以发生变化。
一旦问题得到解决，数据将会根据线索移回其应该在的节点（D—> B），我们称之为提示移交（hinted handoff）。这个移交过程是由反熵 anti-entropy 后台进程完成的。
这是一种典型的牺牲部分一致性，换取更高可用性的做法。在常见的 Dynamo 实现中，放松的法定人数是可选的。在 Riak 中，它们默认是启用的，而在 Cassandra 和 Voldemort 中它们默认是禁用的。
多数据中心
无主模型也适用于系统多数据中心部署。
为了同时兼顾多数据中心和写入的低延迟，有一些不同的基于无主模型的多数据中心的策略：
其中 Cassandra 和 Voldemort 将 n 配置到所有数据中心，但写入时只等待本数据中心副本完成就可以返回。
Riak 将 n 限制在一个数据中心内，因此所有客户端到存储节点的通信可以限制到单个数据中心内，而数据复制在后台异步进行。
由于 Dynamo 允许多个客户端并发写入相同 Key，则即使使用严格的 Quorum 读写，也会产生冲突：对于时间间隔很短（并发）的相同 key 两个写入，不同副本上收到的顺序可能不一致。
此外，读时修复和提示移交时，也可能产生冲突。
如上图，如果每个节点不去检查顺序，而是简单的接受写入请求，就落到本地，不同副本间可能就会出现永久不一致：上图 Node1 和 Node3 上副本 X 的值是 A，Node2 上副本 X 的值是 B。
为了使所有副本最终一致，需要有一种手段来解决并发冲突。
后者胜（Last-Write-Win）
后者胜（LWW，last write wins）的策略是，通过某种手段确定一种全局唯一的顺序，然后让后面的修改覆盖之前的修改。
如，为所有写入附加一个全局时间戳，如果对于某个 key 的写入有冲突，可以挑选具有最大时间戳的数据保留，并丢弃较早时间戳的写入。
LWW 有一个问题，就是多个并发写入的客户端，可能都认为自己成功了，但是最终只有一个值被保留了，其他都在后台被丢弃了。即，其迅速再读，会发现不是自己写入的数据。
使用 LWW 唯一安全的方法是：key 是一次可写，后变为只读。如 Cassandra 建议使用一个 UUID 作为主键，则每个写操作都只会有一个唯一的键。
发生于之前（Happens-before）和并发关系
考虑之前的两个图：
在 5-9 中，由于 client B 的更新依赖于 client A 的插入，因此他们是因果关系。
在 5-12 中，set X = A 和 set X = B 是并发的，因为他们都互相不知道对方存在，也不存在因果关系。
系统中任意的两个写入 A 和 B，只可能存在三种关系：
A happens before B
B happens before A
A B 并发
从另外一个角度来说（集合运算）
A 和 B 并发 < === > A 不 happens-before B && B 不 happens-before A
如果两个操作可以定序，则 last write win；如果两个操作并发，则需要进行冲突解决。
Lamport 时钟相关论文中有详细推导相关概念关系。为了定义并发，事件发生的绝对时间先后并不重要，只要两个事件都意识不到对方的存在，则称两个操作“并发”。从狭义相对论上来说，只要两个事件发生的时间差，小于光在两者距离传播所用时间，则两个事件不可能互相影响。推广到计算机网络中，只要由于网络问题导致，在事件发生时间差内，两者不能互相意识到，则称其是并发的。
确定 Happens-Before 关系
我们可以用某种算法来确定系统中任意两个事件，是否存在 happens-before 关系，还是并发关系。以一个两个 client 并发添加购物车例子来看：
需要注意：
不会主动读取，只有主动写入，通过写入的返回值读取数据库当前状态。
客户端下一次写入，依赖于（因果关系）本客户端上一次写入后获取的返回值。
对于并发，数据库不会覆盖，而是保留多个并发值（每个 client 一个）。
上图中的数据流，如下图所示。箭头表示 happens-before 关系。本例中，客户端永远没办法完全获知服务器数据，因为总有另外的客户端进行并发操作。但是旧版本的值会被覆盖，并且不会丢失写入。
总结下，该算法如下：
服务器为每个键分配一个版本号 V，每次该键有写入时，将 V + 1，并将版本号与写入的值一块保存。
当客户端读取该键时，服务器将返回所有未被覆盖的值以及最新的版本号。
客户端在进行下次写入时，必须包含之前读到的版本号 Vx（说明基于哪个版本进行新的写入），并将读取的值合并到一块。
当服务器收到特定版本号 Vx 的写入时，可以用其值覆盖所有 V ≤ Vx 的值。
如果又来一个新的写入，不基于任何版本号，则该写入不会覆盖任何内容。
合并并发值
该算法可以保证所有数据都不会被无声的丢弃。但，需要客户端在随后写入时合并之前的值来清理多个值。如果简单基于时间戳进行 LWW，则有些数据又会被丢掉。
因此需要根据实际情况，选择一些策略来解决冲突，合并数据。
对于上述购物车中只增加物品的例子，可以使用“并集”来合并冲突数据。
如果购物车汇总还有删除操作，就不能简单并了，但是可以将删除变为增加（写一个 tombstone 标记）。
版本向量
上面例子只有单个副本。将该算法扩展到无主多副本模型时，只使用一个版本值显然不够，这时需要给每个副本的键都引入版本号，对于同一个键来说，不同副本的版本会构成版本向量（version vector）。
key1
A Va
B Vb
C Vc
key1: [Va, Vb, Vc]
[Va-x, Vb-y, Vc-z] <= [Va-x1, Vb-y1, Vc-z1] <==>
x <= x1 && y <= y1 && z <= z1
同系列其他文章
对图数据库 NebulaGraph 感兴趣？欢迎前往 GitHub ✨ 查看源码：https://github.com/vesoft-inc/nebula；
😍 谢谢你分享 
、点赞 
、在看 
本文~~
