《DDIA》阅读笔记（五）：数据复制（无主节点）
本章结构如下：
- 数据复制
- 无主节点复制
- 节点失效时写入数据库
- 读修复与反熵
- 读写 Quorum
- Quorum 一致性的局限性
- 监控旧值
- sloppy quorum 与数据回传
- 多数据中心
- 检测并发写
- 最后写入者获胜（丢弃）
- happens-before 关系和并发
- 确定前后关系
- 合并同时写入的值
- 版本矢量
- 元数据存储
- 静态分片存储
- 哈希
- 多节点
- 无变更
- 无状态服务
- 心跳
- PD 被动接收
- 持久化
- 去中心化
- PSP 架构
- Gossip 协议
无主节点复制方案与多主节点复制方案都比单主节点复制方案更可靠，但代价也是系统的复杂性和弱一致性保证。
客户端将写请求发送到多个节点上，读取时从多个节点上并行读取，并检测和纠正某些过期数据。
对于主从复制和多主节点复制，由客户端先向主节点发送写请求，数据库将写请求复制到从节点。由主节点决定写顺序，从节点以相同顺序应用主节点发送的日志。
无主节点复制 允许任何副本接收写请求 。客户端直接将其写请求发送到多副本，在其他一些实现中，由 协调者 节点代表客户端写入，协调者不负责写入顺序的维护。
节点失效时写入数据库
在有主复制模型下，其中一个副本不可用，如果要继续处理写操作， 则需要执行切换操作。
而对于无主复制模型，客户端向数据库请求读取数据时，将请求并行发送到多个副本、得到多个不同的响应，根据版本号确定哪个值更新。
读修复与反熵
复制模型应确保所有数据最终复制到所有的副本，当节点失效、重新上线后应赶上中间错过的写请求。
读修复：适用于被频繁读取的场景。当客户端并行读取多个副本时，可检测到过期的返回值，从而判断出从某个副本的值已过期，并将新值写入到该副本。
反熵过程：后台进程不断查找副本之间数据的差异，将任何缺少的数据从一个副本复制到另一个副本。该过程不保证以特定的顺序复制写入，并且会引入明显的同步滞后。
如果缺少反熵过程，由于读修复只在发生读取时才可能执行修复，低频访问的数据可能在某些副本中已经丢失而无法检测到，从而降低了写持久性。
读写 Quorum
假设成功的写操作要求三个副本中至少两个完成，意味着最多只有一个副本可能包含旧值。因此在读取时需要至少向两个副本发起读请求，通过版本号可确定一定至少有一个包含新值。如果第三个副本出现停机或响应缓慢，则读取仍可以继续并返回最新值。
仲裁读/写：对于一般情况，如果有 n 个副本， 写入需要 w 个节点确认，读取必须至少查询 r 个节点，则只要 w + r > n，读取的节点中一定会包含最新值。
仲裁条件 w + r > n 定义了系统可容忍的失效节点数：
当 w < n，如果一个节点不可用， 仍然可以处理写入。
当 r < n，如果一个节点不可用， 仍然可以处理读取。
假定 n = 3，w = 2，r = 2，可以容忍一个不可用的节点。
假定 n = 5，w = 3，r = 3，可以容忍两个不可用的节点。
读取和写入操作并行发送到 n 个副本（all）。由参数 w 和参数 r 决定要等待的节点数（即需要有多少个节点返回结果， 才能判断出结果的正确性）。
如果可用节点数小于所需的 w 或 r 则写入或读取就会返回错误。
在 Dynamo 风格的数据库中， 参数 n、w、r 通常是可配置的。一个常见的选择是设置 n 为某奇数，w = r = (n + l) / 2。对于读多写少的负载，设置 w = n 和 r = l 则读取速度更快，但是一个节点失效就会使数据库所有写入因无法完成 Quorum 而失败。
Quorum 一致性的局限
Quorum 不一定是多数，读和写的节点集中有一个重叠的节点 才是最关键。
当 w 和 r 配置的节点数较少，读取请求当中可能没有包含新值的节点，因此最终可能会返回过期的旧值，可以获得更低的延迟、更高的可用性。只有当可用的副本数已经低于 w 或 r 时，数据库才会变得无法读/写。
即使在 w + r > n 的情况下，也可能存在返回旧值的边界条件：
采用了 Sloppy Quorum，写操作的 w 节点和读取的 r 节点可能完全不同，因此无法保证读写请求一定存在重叠的节点。
两个写操作同时发生，无法明确先后顺序。此时唯一安全的解决方案是合并并发写入，如果根据时间戳挑选胜者，则由于时钟偏差问题某些写入可能会被错误地抛弃。
写操作与读操作同时发生，写操作可能仅在一部分副本上完成。此时不确定读取的是否新值。
某些副本上已经写入成功，而其他一些副本发生写入失败，且总的成功副本数少于 w，已成功的副本上不会回滚（写入失败仍返回新值）。
有新值的节点失效，但恢复数据来自某个旧值，则总的新值副本数会低于 w，打破了之前的判定条件。
其他边界情况。
监控旧值
即使应用程序可以容忍读取旧值，也需要仔细了解复制的当前运行状态，分析出现旧值的原因。
主从复制系统可对比主从节点当前偏移量的差值衡量滞后程度。
无主复制系统没有固定写入顺序，且当数据库只支持读时修复时，旧值旧没有上限。可根据 n、w、r 预测读取的旧值期望百分比。
Sloppy Quorum 与数据回传
配置适当 Quorum 的数据库系统可以容忍某些节点故障，也不需要执行故障切换，因此对于高可用、低延迟、可容忍旧值的场景很适用。
对于大规模集群（远大于 n 个节点），客户端能在网络中断期间连接到某些不足以满足仲裁数量的节点，此时面临一个选择：
宽松仲裁（Sloppy Quorum）：如果无法达到 w 或 r 所要求 quorum，将错误明确地返回给客户端（写入和读取仍然需要 w 和 r 个成功的响应，但包含了不在先前指定的 n 个节点）？
数据回传：是否应该接收该写请求，将它们暂时写入一些可访问的节点中（当网络问题恢复，临时节点需要把这期间的写入发送到原始主节点上）？
Sloppy 对于提高写入可用性特别有用：只要有 w 个节点可用，数据库就可以接收新的写入。但即使满足 w + r > n，除非回传结束，否则无法保证客户端一定能从 r 个节点读到新值。
多数据中心
无主节点复制旨在更容忍并发写入冲突、网络中断和延迟尖峰等，因此也可适用于多数据中心操作。
Cassandra 和 Voldemort 默认配置为无主节点模型，其跨数据中心操作：副本数量 n 是 包含所有数据中心的节点总数，可以指定各数据中心副本数。客户端的写入会发送到所有副本，但通常只等待来自本地数据中心内的 Quorum 节点数确认，以避免高延迟和跨数据中心可能导致的网络异常。
Riak 则将客户端和数据库节点之间的通信限制在一个数据中心内，因此 n 表示 一个数据中心内的副本数量。集群之间跨数据中心的复制在后台异步运行，类似多主节点复制。
检测并发写
严格的 Quorum（与多主节点复制类似）或宽松的 Quorum 机制（读时修复或数据回传）都可能发生写冲突。由于网络延迟不稳定或者局部失效，请求在不同的节点上可能会呈现不同的顺序。
如节点每当收到新的写请求时就简单地覆盖原有的主键，副本则无法收敛于相同的内容、达成一致。
最后写入者获胜（丢弃）
如果每个副本总是保存最新值，允许覆盖并丢弃旧值，则关键点在于如何定义“最新”。
比如 Cassandra 和 Riak 的 LWW 最后写入者获胜算法可实现最终收敛。这种做法：
牺牲了数据持久性：如果同一个主键有多个并发写，即使这些并发写（写入 w 个副本）都向客户端报告成功，但最后只有写入值会存活下来，而且 LWW 可能删除非并发写（取决于时间戳和时间顺序）。
在一些场景如缓存系统，覆盖写可以接受，否则就不能用 LWW 解决冲突。
要确保 LWW 安全无副作用，必须只写入一次即写入值视为不可变，避免对同一个主键的并发（覆盖）写。
Happens-Before 关系和并发
并发操作：两个操作不存在因果关系（都不在另一个之前发生，比如插入 A 发生后修改 B 才能发生）、两个操作都不知道对方。
在分布式系统中由于存在时钟同步问题，很难严格判断两个操作是否同时发生，所以操作在时间上是否重叠不重要。因此并发性定义为两个操作不需要意识到对方。
确定前后关系
服务端依靠对比版本号判断操作是否并发，而并不需要解释新旧值：
服务端为每个主键维护一个版本号，每当主键新值写入时递增版本号，并将新版本号与写入的值一起保存。
当客户端读取主键时，服务端将返回所有未被覆盖的当前值以及最新的版本号，且要求写之前客户必须先发送读请求。
客户端写主键，写请求必须包含之前读到的版本号、读到的值和新值合并后的集合。写请求的响应可以像读操作一样，会返回所有当前值，就可以一步步链接起多个写入的值。
当服务端收到带有特定版本号的写入时，覆盖该版本号或更低版本的所有值（因为知道这些值已经被合并到新传入的值集合中），但必须保存更高版本号的所有值（因为这些值与当前的写操作属于并发）。
当写请求包含了前一次读取的版本号时， 意味着修改的是基于以前的状态。如果一个写请求没有包含版本号，它将与所有其他写入同时进行，不会覆盖任何已有值， 其传入的值将包含在后续读请求的返回值列表当中。
合并同时写入的值
上述算法可以保证不会发生数据丢弃，但客户端需要做一些额外的工作，如果多个操作并发发生，则客户端必须通过合并并发写入的值来继承旧值（Riak 将这些并发值称为兄弟关系）。
合并本质上与先前讨论的多节点复制冲突解决类似，一个简单的方法是基于版本号或时间戳（LWW）来选择其中的一个值，但这意味着会丢失部分数据，所以需要在应用代码做额外工作。
对于插入操作，在两个客户端中存在重复值时，可以合并并去除重复值。但如果存在删除操作，有可能导致被删除的项目在合并后再次出现。因此项目在删除时不能只从数据库中删除，系统必须保留一个对应的版本号以恰当的标记（墓碑记录）该项目需要在合并时被剔除。
考虑到在应用代码中合并复杂且容易出错，可以设计一些专门的数据结构来自动执行合并，比如 Riak 支持称为 CRDT 一系列数据结构，以合理的方式高效自动合并，包括支持删除标记。
版本矢量
当存在多个副本且没有主节点，需为每个副本和每个主键定义版本号，以比较副本状态。
每个副本在处理写入时增加自己的版本号，并跟踪其他副本的版本号。通过这些信息来指示要覆盖哪些值、该保留哪些并发值。
所有副本的版本号集合称为 版本矢量。读取数据时数据库副本会返回版本矢量给客户端，在写入时将版本信息包含在请求中一起发送到数据库（Riak 将版本矢量编码为因果上下文字符串），使数据库可区分应该覆盖写还是保留并发值。
应用程序需要执行合并操作。版本矢量可以保证从某一个副本读取值然后写入到另一个副本，这些值可能会导致在其他副本上衍生出来新的“兄弟”值，但不会发生数据丢失且可以正确合并所有并发值。