DDIA 读书分享会，会逐章进行分享，结合我在工业界分布式存储和数据库的一些经验，补充一些细节。每两周左右分享一次，欢迎加入，Schedule 在这里[1]。我们有个对应的分布式&数据库讨论群，每次分享前会在群里通知。如想加入，可以加我的微信号：qtmuniao，简单自我介绍下，并注明：分布式系统群。
本书第一部分讲单机数据系统，第二部分讲多机数据系统。
冗余（Replication）是指将同一份数据复制多份，放到通过网络互联的多个机器上去。其好处有：
- 降低延迟：可以在地理上同时接近不同地区的用户。
- 提高可用性：当系统部分故障时仍然能够正常提供服务。
- 提高读吞吐：平滑扩展可用于查询的机器。
本章假设我们的数据系统中所有数据能够存放到一台机器中，则本章只需考虑多机冗余的问题。如果数据超过单机尺度该怎么办？那是下一章要解决的事情。
如果数据是只读的，则冗余很好做，直接复制到多机即可。我们有时可以利用这个特性，使用分治策略，将数据分为只读部分和读写部分，则只读部分的冗余就会容易处理的多，甚至可以用 EC 方式做冗余，减小存储放大的同时，还提高了可用性。
- 想想 EC 牺牲了什么？
以计算换存储。
但难点就在于，数据允许数据变更时，如何维护多机冗余且一致。常用的冗余控制算法有：
- 单领导者（single leader）
- 多领导者（multi-leader）
- 无领导者（leaderless）
这需要在多方面做取舍：
- 使用同步复制还是异步复制
- 如何处理失败的副本
数据库冗余问题在学术界不是一个新问题了，但在工业界，大部分人都是新手——分布式数据库是近些年才大规模的在工业界落地的。
领导者与跟随者
冗余存储的每份数据称为副本（replica）。多副本所带来的最主要的一个问题是：如何保证所有数据被同步到了所有副本上？
基于领导者（leader-based）的同步算法，是最常用解决办法。
- 其中一个副本称为领导者（leader），别称主副本（primary、master）。主副本作为写入的协调者，所有写入都要发给主副本。
- 其他副本称为跟随者（follower），也称为只读副本（read replicas）、从副本（slaves）、次副本（secondaries）、热备（hot-standby）。主副本将改动写到本地后，将其发送给各个从副本，从副本收变动到后应用到自己状态机，这个过程称为日志同步（replication log）、变更流（change steam）。
- 对于读取，客户端可以从主副本和从副本中读取；但写入，客户端只能将请求发到主副本。
主从同步，一主两从，主写从读
根据我的习惯，下面通称主副本和从副本。
有很多数据系统都用了此模式：
- 关系型数据库：PostgreSQL（9.0+）、MySQL 和 Oracle Data Guard 和 SQL Server 的 AlwaysOn
- 非关系型数据库：MonogoDB、RethinkDB 和 Espresso
- 消息队列：Kafka 和 RabbitMQ。
同步复制和异步复制
同步（synchronously）复制和异步（asynchronously）复制和关键区别在于：请求何时返回给客户端。
- 如果等待某副本写完成后，则该副本为同步复制。
- 如果不等待某副本写完成，则该副本为异步复制。
同步复制和异步复制
两者的对比如下：
- 同步复制牺牲了响应延迟和部分可用性（在某些副本有问题时不能完成写入操作），换取了所有副本的一致性（但并不能严格保证）。
- 异步复制放松了一致性，而换来了较低的写入延迟和较高的可用性。
在实践中，会根据对一致性和可用性的要求，进行取舍。针对所有从副本来说，可以有以下选择：
- 全同步：所有的从副本都同步写入。如果副本数过多，可能性能较差，当然也可以做并行化、流水线化处理。
- 半同步：（semi-synchronous），有一些副本为同步，另一些副本为异步。
- 全异步：所有的从副本都异步写入。网络环境比较好的话，可以这么配置。
异步复制可能会造成副本丢失等严重问题，为了能兼顾一致性和性能，学术界也在不断研究新的复制方法。如，链式复制（chain-replication）。
多副本的一致性和共识性有诸多联系，本书后面章节会讨论。
新增副本
在很多情况下，需要给现有系统新增副本。
如果原副本是只读（read-only）的，只需要简单拷贝即可。但是如果是可写副本，则问题要复杂很多。因此，比较简单的一种解决方法是：禁止写入，然后拷贝。这在某些情况下很有用，比如夜间没有写入流量，同时一晚上肯定能复制完。
如果要不停机，可以：
- 主副本在本地做一致性快照。何谓一致性？
- 将快照复制到从副本节点。
- 从主副本拉取快照之后的操作日志，应用到从副本。如何知道快照与其后日志的对应关系？序列号。
- 当从副本赶上主副本进度后，就可以正常跟随主副本了。
这个过程一般是自动化的，比如 Raft 中；当然也可以手动化，比如写一些脚本。
宕机处理
系统中任何节点都可能在计划内或者计划外宕机。那么如何应对这些宕机情况，保持整个系统的可用性呢？
从副本宕机：追赶恢复。
类似于新增从副本。如果落后的多，可以直接向主副本拉取快照+日志；如果落后的少，可以仅拉取缺失日志。
主副本宕机：故障转移。
处理相对麻烦，首先要选出新的主副本，然后要通知所有客户端主副本变更。具体来说，包含下面步骤：
- 确认主副本故障。要防止由于网络抖动造成的误判。一般会用心跳探活，并设置合理超时（timeout）阈值，超过阈值后没有收到该节点心跳，则认为该节点故障。
- 选择新的主副本。新的主副本可以通过选举（共识问题）或者指定（外部控制程序）来产生。选主时，要保证备选节点数据尽可能的新，以最小化数据损失。
- 让系统感知新主副本。系统其他参与方，包括从副本、客户端和旧主副本。前两者不多说，旧主副本在恢复时，需要通过某种手段，让其知道已经失去领导权，避免脑裂。
主副本切换时，会遇到很多问题：
- 新老主副本数据冲突。新主副本在上位前没有同步完所有日志，旧主副本恢复后，可能会发现和新主副本数据冲突。
- 相关外部系统冲突。即新主副本，和使用该副本数据的外部系统冲突。书中举了 github 数据库 MySQL 和缓存系统 redis 冲突的例子。
- 新老主副本角色冲突。即新老主副本都以为自己才是主副本，称为脑裂（split brain）。如果他们两个都能接受写入，且没有冲突解决机制，数据会丢失或者损坏。有的系统会在检测到脑裂后，关闭其中一个副本，但设计的不好可能将两个主副本都关闭掉。
- 超时阈值选取。如果超时阈值选取的过小，在不稳定的网络环境中（或者主副本负载过高）可能会造成主副本频繁的切换；如果选取过大，则不能及时进行故障切换，且恢复时间也增长，从而造成服务长时间不可用。
所有上述问题，在不同需求、不同环境、不同时间点，都可能会有不同的解决方案。因此在系统上线初期，不少运维团队更愿意手动进行切换；等积累一定经验后，再进行逐步自动化。
节点故障；不可靠网络；在一致性、持久化、可用性和延迟间的取舍；等等问题，都是设计分布式系统时，所面临的的基本问题。根据实际情况，对这些问题进行艺术化的取舍，便是分布式系统之美。
日志复制
在数据库中，基于领导者的多副本是如何实现的？在不同层次有多种方法，包括：
- 语句层面的复制。
- 预写日志的复制。
- 逻辑日志的复制。
- 触发器的复制。
对于一个系统来说，多副本同步的是什么？增量修改。
具体到一个由数据库构成的数据系统，通常由数据库外部的应用层、数据库内部查询层和存储层组成。修改在查询层表现为：语句；在存储层表现为：存储引擎相关的预写日志、存储引擎无关的逻辑日志；修改完成后，在应用层表现为：触发器逻辑。
基于语句的复制
主副本记录下所有更新语句：INSERT、UPDATE 或 DELETE 然后发给从库。主副本在这里类似于充当其他从副本的伪客户端。
但这种方法有一些问题：
- 非确定性函数（nondeterministic）的语句可能会在不同副本造成不同改动。如 NOW()、RAND()
- 使用自增列，或依赖于现有数据。则不同用户的语句需要完全按相同顺序执行，当有并发事务时，可能会造成不同的执行顺序，进而导致副本不一致。
- 有副作用（触发器、存储过程、UDF）的语句，可能不同副本由于上下文不同，产生的副作用不一样。除非副作用是确定的输出。
当然也有解决办法：
- 识别所有产生非确定性结果的语句。
- 对于这些语句同步值而非语句。
但是 Corner Case 实在太多，步骤 1 需要考虑的情况太多。
传输预写日志（ WAL）
我们发现主流的存储引擎都有预写日志（WAL，为了宕机恢复）：
- 对于日志流派（LSM-Tree，如 LevelDB），每次修改先写入 log 文件，防止写入 MemTable 中的数据丢失。
- 对于原地更新流派（B+ Tree），每次修改先写入 WAL，以进行崩溃恢复。
所有用户层面的改动，最终都要作为状态落到存储引擎里，而存储引擎通常会维护一个：
- 追加写入
- 可重放
这种结构，天然适合备份同步。本质是因为磁盘的读写特点和网络类似：磁盘是顺序写比较高效，网络是只支持流式写。具体来说，主副本在写入 WAL 时，会同时通过网络发送对应的日志给所有从副本。
书中提到一个数据库版本升级的问题：
- 如果允许旧版本代码给新版本代码（应该会自然做到后向兼容）发送日志（前向兼容）。则在升级时可以先升级从库，再切换升级主库。
- 否则，只能进行停机升级软件版本。
逻辑日志复制（基于行）
为了和具体的存储引擎物理格式解耦，在做数据同步时，可以使用不同的日志格式：逻辑日志。
对于关系型数据库来说，行是一个合适的粒度：
- 对于插入行：日志需包含所有列值。
- 对于删除行：日志需要包含待删除行标识，可以是主键，也可以是其他任何可以唯一标识行的信息。
- 对于更新行：日志需要包含待更新行的标志，以及所有列值（至少是要更新的列值）
对于多行修改来说，比如事务，可以在修改之后增加一条事务提交的记录。MySQL 的 binlog 就是这么干的。
使用逻辑日志的好处有：
- 方便新旧版本的代码兼容，更好的进行滚动升级。
- 允许不同副本使用不同的存储引擎。
- 允许导出变动做各种变换。如导出到数据仓库进行离线分析、建立索引、增加缓存等等。
之前分析过一种基于日志，统一各种数据系统的文章[2]，很有意思。
基于触发器的复制
前面所说方法，都是在数据库内部对数据进行多副本同步。
但有些情况下，可能需要用户决策，如何对数据进行复制：
- 对需要复制的数据进行过滤，只复制一个子集。
- 将数据从一种数据库复制到另外一种数据库。
有些数据库如 Oracle 会提供一些工具。但对于另外一些数据库，可以使用触发器和存储过程。即，将用户代码 hook 到数据库中去执行。
基于触发器的复制，性能较差且更易出错；但是给了用户更多的灵活性。
参考资料
[1]DDIA 读书分享会: https://docs.qq.com/sheet/DWHFzdk5lUWx4UWJq
[2]以日志视角对数据系统大一统: https://zhuanlan.zhihu.com/p/458683164
