DDIA 读书分享 第五章：Replication，多主模型
DDIA 读书分享会，会逐章进行分享，结合我在工业界分布式存储和数据库的一些经验，补充一些细节。每两周左右分享一次，欢迎加入，网站在这里[1]。我们有个对应的分布式&数据库讨论群，每次分享前会在群里通知。
单主模型一个最大问题：所有写入都要经过它，如果由于任何原因，客户端无法连接到主副本，就无法向数据库写入。
于是自然产生一种想法：多主行不行？
多主复制（multi-leader replication）：有多个可以接受写入的主副本，每个主副本在接收到写入之后，都要转给所有其他副本。即一个系统，有多个写入点。
多主模型应用场景
单个数据中心，多主模型意义不大：复杂度超过了收益。总体而言，由于一致性等问题，多主模型应用场景较少，但有一些场景，很适合多主：
- 数据库横跨多个数据中心
- 需要离线工作的客户端
- 协同编辑
多个数据中心
假设一个数据库的副本，横跨多个数据中心，如果使用单主模型，在写入时的延迟会很大。那么每个数据中心能不能各配一个主副本？
multi-leader across multiple data centers
单主和多主，在多数据中心场景下的对比：
对比项 | 单主模型 | 多主模型 |
|---|---|---|
性能 | 所有写入都要路由到一个数据中心 | 写入可以就近 |
可用性 | 主副本所在数据中心故障，需要有个切主的过程 | 每个数据中心可以独立工作 |
网络 | 跨数据中心，写入对网络抖动更敏感 | 数据中心间异步复制，对公网容错性更高 |
但是多主模型在一致性方面有很大缺陷：如果两个数据中心同时修改同样的数据，必须合理解决写冲突。另外，对于数据库来说，多主很难保证一些自增主键、触发器和完整性约束的一致性。因此在工程实践中，多主用的相对较少。
离线工作的客户端
离线工作的一个应用的多个设备上的客户端，如果也允许继续写入数据。如：日历应用。在电脑上和手机上离线时如果也支持添加日程。则在各个设备联网时，需要互相同步数据。
则离线后还继续工作的多个副本，本质上就是一个多主模型：每个主都可以独立的写入数据，然后在网络连通后解决冲突。
但，如何支持离线后正常地工作，联网后优雅的解决冲突，是一个难题。
Apache CouchDB 的一个特点便是支持多主模型。
协同编辑
Google Docs 等类似 SaaS 模式的在线协同应用越来越流行。
这种应用允许多人在线同时编辑文档或者电子表格，其背后的原理，与上一节离线工作的客户端很像。
为了实现协同，并解决冲突，可以：
- 悲观方式。加锁以避免冲突，但粒度需要尽可能小，否则无法允许多人同时编辑一个文档。
- 乐观方式。允许每个用户无脑写入，然后如果有冲突，交由用户解决。
git 也是一个类似的协议。
处理写入冲突
多主模型最大的问题是：如何解决冲突。
write conflict
考虑 wiki 一个页面标题的修改：
- 用户 1 将该页面标题从 A 修改到 B
- 用户 2 将该页面标题从 A 修改到 C
两个操作在本地都修改成功，然后异步同步时，会出现冲突。
冲突检测
有同步或者异步的方式进行冲突检测。
对于单主模型，当检测到冲突时，由于只有一个主副本，可以同步的检测冲突，从而解决冲突：
- 让第二个写入阻塞，直到第一个写完成。
- 让第二个写入失败，进行重试。
但对于多主模型，两个写入可能会在不同主副本立即成功。然后异步同步时，发现冲突，但为时已晚（没有办法简单决定如何解决冲突）。
虽然，可以在多主间使用同步方式写入所有副本后，再返回请求给客户端。但这会失掉多主模型的主要优点：允许多个主副本独立接受写入。此时，蜕化成单主模型。
冲突避免
解决冲突最好的方式是在设计上避免冲突。
由于多主模型在冲突发生后再去解决会有很大的复杂度，因此常使用冲突避免的设计。
假设你的数据集可以分成多个分区，让不同分区的主副本放在不同数据中心中，那么从任何一个分区的角度来看，变成了单主模型。
举个栗子：对于服务全球用户的应用，每个用户就近固定路由到附近的数据中心。则，每个用户信息都有唯一的主副本。
但如果：
- 用户从一个地点迁移到了另一个地点
- 某个数据中心损坏，导致路由变化
就会对该设计提出一些挑战。
冲突收敛
在单主模型中，所有事件比较容易进行定序，因此我们总可以用后一个写入覆盖前一个写入。
但在多主模型中，很多冲突无法定序：从每个主副本来看，事件顺序是不一致的，并且没有哪个更权威一些，那么就无法让所有副本最终收敛（convergent）。
此时，我们就需要一些规则，来让其收敛：
- 给每个写入一个序号，并且后者胜。本质上是使用外部系统对所有事件进行定序。但可能会产生数据丢失。举个例子，对于一个账户，原有 10 元，客户端 A - 8，客户端 B - 3，任何一个单独成功都有问题。
- 给每个副本一个序号，序号更高的副本有更高的优先级。这也会造成低序号副本的数据丢失。
- 提供一种自动的合并冲突的方式。如，假设结果是字符串，则可以将其排序后，使用连接符进行链接，如在之前 Wiki 的冲突中，合并后的标题为 “B/C”
- 使用程序定制一种保留所有冲突值信息的冲突解决策略。也可以将这个定制权，交给用户。
自定义解决
由于只有用户知道数据本身的信息，因此较好的方式是，将如何解决冲突交给用户。即，允许用户编写回调代码，提供冲突解决逻辑。该回调可以在：
- 写时执行。在写入时发现冲突，调用回调代码，解决冲突后写入。这些代码通常在后台执行，并且不能阻塞，因此不能在调用时同步的通知用户。但打个日志之类的还是可以的。
- 读时执行。在写入冲突时，所有冲突都会被保留（如使用多版本）。下次读取时，系统会将所有数据本版本返回给用户，进行交互式的或者自动的解决冲突，并将结果写回系统。
上述冲突解决只限于单个记录、行、文档层面。
TODO（自动冲突解决）
界定冲突
有些冲突显而易见：并发写同一个 Key。
有些冲突则更隐晦，考虑一个会议室预订系统。预定同一个会议室不一定会发生冲突，只有预定时间段有交叠，才会有冲突。
多主复制拓扑
复制拓扑（replication topology）描述了数据写入从一个节点到另一个节点的传播路径。
在只有两个主副本时，拓扑是确定的，如图 5-7。Leader1 和 Leader 都得把数据发给对方。但随着副本数的增多，数据复制拓扑就会有多种选择，如下图：
multi-leader topologies
上图表示了 ≥ 4 个主副本时，常见的复制拓扑：
- 环形拓扑。通信跳数少，但是在转发时需要带上拓扑中前驱节点信息。如果一个节点故障，则可能中断复制链路。
- 星型拓扑。中心节点负责接受并转发数据。如果中心节点故障，则会使得整个拓扑瘫痪。
- 全连接拓扑。每个主库都要把数据发给剩余主库。通信链路冗余度较高，能较好的容错。
对于环形拓扑和星型拓扑，为了防止广播风暴，需要对每个节点打上一个唯一标志（ID），在收到他人发来的自己的数据时，及时丢弃并终止传播。
全连接拓扑也有自己问题：尤其是所有复制链路速度不一致时。考虑下面一个例子：
writes wrong order
两个有因果依赖的（先插入，后更新）的语句，在复制到 Leader 2 时，由于速度不同，导致其接收到的数据违反了因果一致性。
要想对这些写入事件进行全局排序，仅用每个 Leader 的物理时钟是不够的，因为物理时钟：
- 可能不能够充分同步
- 同步时可能会发生回退
可以用一种叫做版本向量（version vectors）的策略，对多个副本的事件进行排序，解决因果一致性问题。下一节会详细讨论。
最后忠告：如果你要使用基于多主模型的系统，一定要知晓上面提到的问题，多做测试，确保其提供的保证符合你的使用场景。
我是青藤木鸟，一个喜欢摄影的分布式系统程序员。欢迎关注我的公众号：木鸟杂记。如果觉得不错，就点个在看分享一下吧。如果想找人交流分布式系统和数据库，欢迎来论坛：https://distsys.cn/ 提问，点击下方阅读原文可直达。
参考资料
[1]
DDIA 读书分享会: https://docs.qq.com/sheet/DWHFzdk5lUWx4UWJq
题图故事
阿二线上的白桦林，上过白漆一样的枝干，清冷的天气