第二部分
将数据库分布到多台机器上的原因：
- 可扩展性：数据量、读取负载、写入负载超出单台机器的处理能力
- 容错/高可用性：你的应用需要在单台机器（或多台机器，网络或整个数据中心）出现故障的情况下仍然能继续工作，则可使用多台机器，以提供冗余。
- 延迟：如果在世界各地都有用户，你也许会考虑在全球范围部署多个服务器，从而每个用户可以从地理上最近的数据中心获取服务，避免了等待网络数据包穿越半个世界。
系统扩展能力
当负载增加需要更强的处理能力时，最简单的方法就是购买更强大的机器，也叫垂直扩展或向上扩展。
- 共享内存架构：由一个操作系统管理更多的CPU、内存、磁盘，通过总线使每个CPU都可以访问所有的内存和磁盘。这样的结构问题在于扩展成本增长过快甚至超过了线性，而且提供的容错能力有限。
- 共享磁盘架构：拥有多态服务器，各个服务器有独立的CPU和内存，数据存储在可共享访问的磁盘阵列上。这种架构用于某些数据仓库，但竞争和锁定的开销限制了共享磁盘方法的可扩展性
无共享架构
无共享架构也叫水平扩展或向外扩展。在这种架构中，运行数据库软件的每台机器/虚拟机都称为节点（node）。每个节点只使用各自的处理器，内存和磁盘。节点之间的任何协调，都是在软件层面使用传统网络实现的。
复制VS分区
复制
在几个不同的节点上保存数据的相同副本，可能放在不同的位置。 复制提供了冗余：如果一些节点不可用，剩余的节点仍然可以提供数据服务。 复制也有助于改善性能。
分区
将一个大型数据库拆分成较小的子集（称为分区（partitions）），从而不同的分区可以指派给不同的节点（node）（亦称分片（shard））。
第五章 数据复制
我们将讨论三种流行的变更复制算法：主从复制（single leader），多主节点复制（multi leader）和无主节点复制（leaderless）。几乎所有分布式数据库都使用这三种方法之一。
主节点与从节点
如何保证所有副本之间数据一致：
客户端写入数据时先将数据写入主副本，然后将数据更改作为复制的日志或更改流发送给所有从副本，客户端从数据库中读数据时，可以从主副本或者从副本副本上执行查询（只有主副本才可以接收写请求）
同步复制与异步复制
同步复制优点是确保从节点与主节点数据更新同步，万一主节点附身股占可以从从节点继续访问最新数据。
同步复制缺点是如果从节点发生故障或网络故障写入失败，则会阻塞主节点其他操作。
实践中通常将一个从节点同步，而其他是异步的，一旦同步的从节点不可用，则将另一个异步的从节点转化为同步的，这种配置称为半同步
全异步模式如果主节点发生失败则所有未复制的请求都会丢失，优点是不管从节点数据多么滞后，主节点总是可以继续相应写请求，系统的吞吐性能更好
配置新的从节点
可以将主节点进行快照保存，然后新的从关节点根据快照内容进行复制，结束后再次对主节点进行快照，并将上一个快照复制阶段时主节点中新增加的内容进行复制，一直重复这个些步骤直到追赶上新的数据变化。
处理结点失效
从节点失效：追赶式恢复
根据副本的复制日志就可以知道在发生故障之前所处理的最后一笔事务，然后连接到主节点，请求那笔事务之后中断期间内所有的数据变更，并进行追赶式恢复。
主节点失效：结点切换
自动切换步骤：
- 确认主节点失效，通常发送基于超时机制的心跳存活消息
- 选举新的主节点，候选节点最好和原来的主节点的数据差异最小
- 重新配置系统使新主节点生效，并将原来的主节点降级为从节点
问题：
- 如果使用异步复制，新的主节点并未受到原主节点的所有数据，则原主节点中的那些数据只能丢掉
- 如果有其他系统依赖数据库内容并在一起协同使用，则丢弃数据会很危险
- 有时出现故障会出现两个主节点的情况，这种情况没有很好的解决方法
- 如何设置合适的超时时间，也就是怎么判断主节点失效，时间过长会导致总体恢复时间变长，时间过短会导致不必要的切换。
这些问题会在第8、9章讨论
复制日志的实现
基于语句的复制
主节点记录所执行的每个操作语句作为日志发送给从节点
不适用的场景：
- 非确定性函数的语句：如NOW（）获取当前时间，RAND（）获取随机数
- 语句中使用了自增列，或者依赖于数据库的现有数据，所有副本必须按完全相同的顺序执行，否则会带来不同的结果。
- 有副作用的语句：如触发器，存储过程，用户定义的函数等，可能会在每个副本上产生不同的副作用。
可以采取一些手段避免这些问题，但目前首选的还是其他复制实现方案
基于预写日志（WAL）传输
通常每个写操作都是以追加写的方式写入到日志中，因此可以用完全相同的日志在另一个节点上构建副本。
缺点是日志描述的数据结果非常底层，似的复制方案和存储引擎紧密耦合，如果数据库的存储格式版本变化，那么系统通常无法支持主从节点上运行不同版本的软件。
基于行的逻辑日志复制
复制和存储引擎采用不同的日志格式
关系数据库的逻辑日志通常是以行的粒度描述对数据库表的写入的记录序列：
- 对于插入的行，日志包含所有列的新值。
- 对于删除的行，日志包含足够的信息来唯一标识已删除的行。通常是主键，但是如果表上没有主键，则需要记录所有列的旧值。
- 对于更新的行，日志包含足够的信息来唯一标识更新的行，以及所有列的新值（或至少所有已更改的列的新值）。
逻辑日志与存储日志解耦，可以实现更好的兼容，对于外部应用程序来说逻辑日志格式也更容易解析。
基于触发器的复制
基于触发器的复制通常比其他复制方法具有更高的开销，并且比数据库的内置复制更容易出错，也有很多限制。然而由于其灵活性，仍然是很有用的。
复制滞后的问题
当应用程序从异步从库读取时，如果从库落后，它可能会看到过时的信息。这会导致数据库中出现明显的不一致
虽然在主节点停止写入一段时间后会达到一致，这叫“最终一致性”。
读自己的写
用户写数据后立刻去读自己刚写的数据，由于读数据可能是在从节点上读取的，可能导致读不到
对于这种情况需要“写后读一致性”，也叫“读写一致性”。
实现写后读一致性有以下方法：
- 读用户可能已经修改过的内容时，都从主库读
- 跟踪上次更新的时间，在上次更新后的一分钟内，从主库读。
- 客户端可以记住最近一次写入的时间戳，系统需要确保从库为该用户提供任何查询时，该时间戳前的变更都已经传播到了本从库中。
- 如果副本分布在多数据中心，则必须先把请求路由到主节点所在的数据中心
如果用户写入数据后使用不同的设备读取，则会变得更复杂
单调读
用户两次从不同的从节点读取数据，可能出现第一次访问到了数据，而第次访问的从节点同步较慢导致第二次没有读到数据。此时需要“单调读一致性”。
实现单调读的一种方式是确保每个用户总是从固定的同一副本执行读取。例如基于用户ID的哈希方法选择副本，而不是随机选择副本。
前缀一致读
一前一后的两条消息到达从节点的顺序可能会颠倒。此时需要“前缀一致读”。
一种解决方案是，确保任何因果相关的写入都写入相同的分区。
在本章的“关系与并发”会继续该问题的探讨。
复制滞后的解决方案
交给数据库来做
多主节点复制
系统只有一个主节点时如果主节点失效会带来很大的问题，因此可以配置多个主节点，每个主节点都接受写操作，每个处理写的主节点都必须将该数据更改转发到所有其他节点，此时，每个主节点还同时扮演其他主节点的从节点。
适用场景
多数据中心
与单主节点之间的差异：
- 性能：多主节点每个写操作都可以在本地数据中心快速响应，然后采用异步复制的方式将变化同步到其他数据中心，使用户体验到的性能更好
- 容忍数据中心失效：多主节点可以在发生故障后恢复到最新状态
- 容忍网络问题：数据中心之间的通信通常经由广域网，它往往不如数据中心内的本地网络可靠
缺点：
不同的数据中心可能会同时修改相同的数据，因而必须解决潜在的写冲突
在数据库中多主复制时使用自增主键、触发器、完整性约束等功能时可能会出现副作用
离线客户端操作
把每个客户端都当做是一个数据中心，每个设备都有一个本地数据库，网络断开时各个设备依旧可以读写本地数据，在下次联网后即可同步到服务器上。
这是一个比较极端的情况，此时每个客户端和服务器都处于平等的地位，而且他们之间的网络连接非常不可靠。
协作编辑
多个用户同时编辑文档，一个用户编辑文档时所作的更改会立即应用到本地副本，然后异步复制到服务器以及编辑同一文档的其他用户。
要保证不会发生编辑冲突，则需要给文档上锁，为了加快协作编辑的效率，可以减小锁的粒度。
处理写冲突
不同用户往不同主节点提交修改数据，节点之间同步时会发现存在冲突。
同步与异步冲突检测
可以等写请求完成对所有副本的同步，再通知用户写入成功，但这样会失去多主节点的优势。
如果您想要同步冲突检测，那么您可以使用单主程序复制。
避免冲突
如果应用程序可以确保特定记录的所有写入都通过同一个主节点，那么冲突就不会发生。
有时可能是因为一个数据中心出现故障，您需要将流量重新路由到另一个数据中心，或者可能是因为用户已经迁移到另一个位置，现在更接近不同的数据中心。在这种情况下，冲突避免会失效，你必须处理不同主库同时写入的可能性。
收敛于一致状态
本来可以根据时间顺序，将新的数据直接覆盖旧的数据来解决冲突，但是多主节点中不同的结点判断顺序的结果可能不同，因此这个方法无效
实现收敛的冲突解决有以下可能的方式：
- 为每个写入分配唯一的ID，ID高的写入者作为胜利者，但可能造成数据丢失
- 为每个副本分配一个唯一的ID，序号高的副本写入始终优先于序号低的副本，也会导致数据丢失。
- 以某种方式将这些值合并在一起。
- 记录冲突信息然后以应用层逻辑解决或者提示用户解决
自定义冲突解决逻辑
解决冲突最合适的方式可能还是依靠应用层
- 在写入时执行：在写入时发现冲突后调用应用层的冲突处理程序。
- 在读取时执行：所有冲突写值都会暂时保存下来，下一次读取数据时将多个版本返回应用层提示用户解决。
什么是冲突
不同的应用逻辑会有不同的冲突，例如数值的冲突，例如预定会议室的时间冲突。
拓扑结构
最常见的是全部到全部的拓扑。
为了防止数据在多个节点中无限循环，需要为每个写请求标记已通过的节点标识符。
环形和星型的问题是如果一个结点发生了故障，会影响其他节点之间的转发。
全链接拓扑会导致复制日志之间的覆盖。
由于无法保证时钟同步，所以无法使用时间戳来保证日志的顺序，可以使用后面提到的版本向量的技术
无主节点复制
无主节点复制：放弃主节点，允许任何副本直接接受来自客户端的写请求。或者会有一个一个协调者节点代表客户端写入。
节点失效时写入数据库
用户发送的请求不再只发送给主节点，而是同时发送给多个节点，当大多数节点有效并且返回成功信息，则表示写入成功。
当失效的副本重新上线时，节点中的数据会比其他节点中的数据更旧，用户从节点读取信息时，会并行地发送到多个副本，客户端可以采取版本号技术确定哪个值更新。
读修复与反熵
读修复：
当客户端读取多个副本检测到过期的值时，将新的值写会到该副本。
适合那些频繁被读取的场景。
反熵过程：
后台有进程查找旧的数据，并从其他副本复制数据进行更新。
此反熵过程不会以任何特定的顺序复制写入，并且在复制数据之前可能会有显著的延迟。
读写quorum
如果有n个副本，写入需要w个节点确认，读取必须至少查询r个节点，则只要w+r>n，读取的节点中一定会包含最新值。
满足上述这些r,w值的读写操作称之为法定票数读（仲裁读）或法定票数写（仲裁写）。
这里的w和r可以灵活配置，比如对于读多写少的负载，设置w=n，r=1比较合适，这样读取速度更快，但是一个失效的节点就会使得数据库所有的写因为无法完成quorum而失败。
如果可用节点数小于所需的w或r，则写入或读取就会返回错误。
quorum一致性的局限性
quorum不一定非的是多数，只要保证读节点和写节点有一个是重合的即可，因此可以使用w+r<=n的方式，可以容忍更多的副本失效，但是也可能出现正好没有包含新值的节点。
尽管法定人数似乎保证读取返回最新的写入值，但在实践中并不那么简单。 Dynamo风格的数据库通常针对可以忍受最终一致性的用例进行优化。允许通过参数w和r来调整读取陈旧值的概率，但把它们当成绝对的保证是不明智的。
监控旧值
对与主从复制的系统，主节点和从节点都遵从相同的顺序写入，每个节点都维护了复制日志执行的当前偏移量，通过对比主节点和从节点当前偏移量的差值，即可衡量该从节点落后于主节点的程度。
如果数据库只支持读时修复（不支持反熵）那么旧值的落后就可能没有上限。
宽松的quorum与数据回传
quorum并不总如期待的那样提供高容错能力，一个网络中断可以很容易切断一个客户端到多数数据库节点的链接，尽管这些集群节点是活着的，这种情况下可能无法满足最低的w和r所要求的的节点数。
此时宽松的quorum会接受写请求，只是将他们暂时写入一些可访问的节点中，这些节点可能不在n个节点集合中。写入和读取仍然需要w和r个成功的响应，一旦网络问题得到解决，临时节点需要把接收到的写入全部发送到原始主节点上，这就是所谓的数据回传（或暗示移交）。
可以看出宽松的quorum对于提高写入可用特性也别有用，只要有任何w个节点可用，数据库就可以接收新的写入。
多数据中心操作
无主复制还适用于多数据中心操作，因为它旨在容忍冲突的并发写入，网络中断和延迟尖峰。
无论数据中心如何，每个来自客户端的写入都会发送到所有副本，但客户端通常只等待来自其本地数据中心内的法定节点的确认，从而不会受到跨数据中心链路延迟和中断的影响。对其他数据中心的高延迟写入通常被配置为异步发生。
检测并发写
如果允许多个客户端对相同的主键同时发起写操作，但即使使用严格的quorum机制也会发送写冲突，
如果节点每当收到新的写请求时就简单的覆盖原有的主键，那么由于到达的时间不同，那么这些节点将永远无法达成一致。
最后写入者获胜（丢弃并发写入）
由于客户端是并行写入的，因此无法确定请求的自然顺序，但可以强制对其排序，例如为每个请求附加一个时间戳，选择最新即最大的时间戳，丢弃较早的时间戳的写入。这个算法称为最后写入者获胜（LWW）
但是这个方法会将旧值覆盖和丢弃，如果覆盖丢弃不可接受，则LWW并不是解决冲突很好的选择。
与LWW一起使用数据库的唯一安全方法是确保一个键只写入一次，然后视为不可变，从而避免对同一个主键进行并发更新。
Happens-before关系和并发
只要有两个操作A和B，就有三种可能性：A在B之前发生，或者B在A之前发生，或者A和B并发。我们需要的是一个算法来告诉我们两个操作是否是并发的。如果一个操作发生在另一个操作之前，则后面的操作应该覆盖较早的操作，但是如果这些操作是并发的，则存在需要解决的冲突。
确定前后关系
- 服务器为每个键保留一个版本号，每次写入键时都增加版本号，并将新版本号与写入的值一起存储。
- 当客户端读取键时，服务器将返回所有未覆盖的值以及最新的版本号。客户端在写入前必须读取。
- 客户端写入键时，必须包含之前读取的版本号，并且必须将之前读取的所有值合并在一起。 （来自写入请求的响应可以像读取一样，返回所有当前值，这使得我们可以像购物车示例那样连接多个写入。）
- 当服务器接收到具有特定版本号的写入时，它可以覆盖该版本号或更低版本的所有值（因为它知道它们已经被合并到新的值中），但是它必须保持所有值更高版本号（因为这些值与传入的写入同时发生）。
合并同时写入的值
如果同时写入的值只是在增加数据，则可以使用union操作即可知道最终值，但如果是在删除数据，则需要使用一个保留一个版本号进行删除标记，这种删除标记被称为墓碑。
版本矢量
当多个副本并发接受写入时，除了对每个键使用版本号之外，还需要在每个副本中使用版本号。每个副本在处理写入时增加自己的版本号，并且跟踪从其他副本中看到的版本号。这个信息指出了要覆盖哪些值，以及保留哪些值作为兄弟。
当读取值时，版本向量会从数据库副本发送到客户端，并且随后写入值时需要将其发送回数据库。版本向量允许数据库区分覆盖写入和并发写入。