写在前面的话
这一部分是ddia的第五章，复制
这一部分主要讨论了复制的价值以及复制的三种方式，额外一提，其实区块链就是一种无领导型的复制方式，另外解释了一种由于复制滞后引起的奇怪效应以及解决这些效应的方法。
分布式数据概述
分布式存储的原因
- 可扩展性
- 容错/高可用
- 延迟
扩展至更高的载荷
垂直扩展：购买更强大的机器
共享架构
- 共享内存架构：任意处理器都可以访问内存或者磁盘的任意部位
- 问题：成本增长速度快于线性增长
- 共享磁盘架构：多台独立处理器和内存，但是数据存储在机器之间共享的磁盘阵列上，磁盘通过网络快速链接
- 问题：竞争和锁定的开销限制了共享磁盘方法的可扩展性
无共享架构
水平扩展：运行数据库的每台机器/虚拟机都被称为节点，每个节点只是用自己的处理器，内存和磁盘，节点之间的协调都是在软件层面是用网络实现的。
复制VS分区
复制
在不同的节点上保存数据相同的副本
- 提供了冗余
- 有助于改善性能
分区
将大型数据库拆分成较小的子集
复制
本章的基础假设：数据集不大，每台机器都可以保存整个数据集的副本
复制的困难在于处理复制数据的变更，通常有三种变更复制算法
- 单领导者
- 多领导者
- 无领导者
领导者与追随者
基于领导者的复制
工作原理如上图所示：
- 副本之一是领导者，当客户端写入数据库，必须将请求发给领导者，领导者写入本地存储
- 其他副本被称为追随者(只读副本，从库，次要，热备)，领导者写入本地存储时，也会将数据变更发给所有的追随者，称为复制日志
- 客户读取数据时可以从领导者或者追随者中获取，但是只有领导者才接受写操作
这种模式在如下地方使用：
- 大量关系型数据库的内置功能：PostgreSQL,MySQL,Oracle Data Guard和SQL Server的AlwaysOn可用性组
- 非关系数据库：MongoDB,RethinkDB和Espresso
- Kafka和RabbitMQ高可用队列
- 某些网络文件系统：DRBD
同步复制与异步复制
如上图所示，从库1是同步复制，从库2是异步复制
同步复制：
- 优点：从库保证有与主库一致的最新数据副本
- 缺点：同步从库未响应，主库就无法处理写入操作
半同步：
如果同步从库变得不可用或缓慢，则使一个异步从库同步。这保证你至少在两个节点上拥有最新的数据副本:主库和同步从库
通常情况，基于领导者的复制都配置为完全异步
P.S.
链式复制可能能解决主库故障时不丢失数据的问题。
设置新从库
过程如下：
- 从某个时刻获取主库的一致性快照：例如MySQL的innobackupex
- 将快照复制到新的从库节点
- 从库连接到主库，再哪去快照之后发生的所有数据变更：PostgreSQL将其称为日志序列号(log sequence number, LSN)，MySQL称为二进制日志坐标(binlog coordinates)
- 从库处理完快照后的数据变更后，就可以继续处理主库产生的数据变化了
处理节点宕机
从库失效：追赶恢复
从库崩溃或者重启的情况下，可以从日志上知道发生故障前的最后一个事物，从库可以连接主库，并且请求从库断开连接时发生的所有数据变更，当变更处理完成后，就赶上了主库并可以像以前一样继续接受数据变更流
主库失效：故障转移
故障转移：
- 其中一个从库需要提升为新的主库
- 重新配置客户端，将写操作发送给新的主库
- 其他从库需要开始拉取来自新主库的数据变更
通常的自动故障转移的步骤如下所示：
- 确认主库失效
- 选择一个新的主库，可以由选举过程来完成(主库由剩余副本以多数选举产生)
- 重新配置系统以启用新的主库
故障转移的麻烦：
- 异步复制可能导致新主库没有收到老主库宕机前最后的写操作，对这些写入该如何处理？最简单的处理方式是丢弃，但是会损伤数据持久化
- 如果数据库与其他外部存储相协调，丢弃写入内容是极其危险的操作，例如github的事故
- 脑裂(split brain)：两个节点都以为自己是主库，都可以接受写操作但是没有冲突解决机制，数据可能丢失或者损坏，这时候只能关闭其中一个节点(屏蔽
fencing，爆彼之头Shoot The Other Node In The Head, STONITH) - 需要设置合适的主库超时时间，超时越长，恢复时间也越长，超时太短，可能造成不必要的故障转移
复制日志的实现
基于语句的复制
主库记录下它执行的每个写入请求，并且将日志转发给从库
问题：
- 调用非确定性函数，可能在副本上生成不同的值，例如
NOW()获取当前时间或者用RAND()获取随机数 - 如果是自增列，每个副本需要按照完全相同的顺序执行，对于多并发的事物，可能会成为一个限制。
- 有副作用的语句(触发器，存储过程，用户定义函数)可能会在每个副本上产生不同的副作用
使用范围：
- 5.1版本之前的MySQL
- VoltDB，但是要求事务必须是确定性的
传输预写式日志(WAL)
日志是包含所有数据库写入的仅追加字节序列，可以使用完全相同的日志在另一个节点上构建副本，主库可以通过将日志发给从库让从库数据更新
问题：
- 日志记录的数据非常底层，使复制与存储引擎紧密耦合，如果存储格式版本变动，就会出现问题
使用范围：
- PostgreSQL和Oracle等使用了这种复制方法
逻辑日志复制(基于行)
逻辑日志
复制和存储引擎使用不同的日志格式，这样可以使复制日志从存储引擎内部分离出来，这种复制日志称为逻辑日志
特点
- 插入的行，日志包含所有列的新值
- 删除的行，日志包含足够信息来唯一标识已删除的行，通常是主键
- 更新的行，日志包含足够信息来唯一标识更新的行，以及所有列的新值
修改多行的事务会生成多个这样的日志记录，并且跟随信息，指出事务已经提交
(MySQL的二进制日志使用这种方法)
基于触发器的复制
触发器
数据库自带功能，允许注册在数据库系统中发生数据更改时自动执行的自定义程序代码
优点
- 灵活
缺点
- 更高的开销
- 比数据库的内置复制更容易出错
使用：
- Databus for Oracle
- Bucardo for Postgres
复制延迟问题
基于主库复制要求所有写入都由单个节点处理，但是只读查询可以由任何副本处理，因此在读多写少的场景中，一个好方案是创建很多的从库，将读请求分散。
从库的增加导致只能使用异步同步，这样就可能看到从库上过时的信息。
最终一致性(eventually consistency)
停止写入数据库并等待一段时间，从库最终会赶上并与主库保持一致
然而这个最终并没有明确，简单的说就是副本落后的程度是没有限制的。
读己之写
场景：
用户提交了数据后查看数据，然而数据并没有到达副本，对用户而言看起来就像是刚提交的数据丢失了
此时需要读写一致性(read-after-write consistency)，保证用户刷新页面后总会看到自己提交的任何更新。
解决方案：
- 读用户可能修改过的内容时，都从主库读：简单规则，从主库读用户自己的档案，从从库读取其他用户的档案
- 使用其它标准是否从主库读取，上次更新后的一分钟内从主库读，防止向任何滞后超过一分钟的从库发出查询。
- 客户端记录时间戳，系统确保从库提供查询时该时间戳的变更都已经传播到本从库。时间戳可以是逻辑时间戳(日志序列号)，也可以是实际系统时钟(时钟同步相当重要)
- 在副本分布在多个数据中心，会增加复杂性，如何需要由领导者提供服务的请求都必须路由到包含主库的数据中心。
更复杂的场景：
同一个用户从多个设备中请求服务
更复杂的问题：
- 记录用户上次更新时间戳变得困难，换设备之后并不知道另一台设备发生了什么，元数据需要一个中心存储
- 副本分布在不同的数据中心，很难保证不同设备的连接会路由到同一数据中心。所以可能首先需要把来自同一用户的请求路由到同一个数据中心。
单调读
场景：
时光倒流(moving backward in time)：当从不同从库进行多次读取可能发生这种情况，先从延迟小的从库读，再从延迟大的从库读，那么就可能出现问题
解决方案：
单调读(Monotonic reads),即如果嫌读取到较新的数据，后续读取不会得到更旧的数据，具体实现的一种方式是确保每个用户总是从同一个副本进行读取，例如可以基于用户ID的散列来选择副本而不是随机选择副本。
一致前缀读
场景：
一段连续的数据，前置数据从延迟较高的从库读取，后续数据从延迟较低的从库读取，导致后续数据到了前置数据前，导致了迷惑
在分布式数据库，不同的分区独立运行，不存在全局写入顺序，这时候读取数据时可能出现某些部分处于较旧的状态，而某些处于较新的状态
解决方案：
一致前缀读(consistent prefix reads)
如果一系列写入按某个顺序发生，那么任何人读取这些写入时，也会看见它们 以同样的顺序出现。
简单的方法：
确保任何因果相关的写入都写入相同的分区
复制延迟的解决方案
应用程序可以提供比底层数据更强有力的保证，但是应用程序代码中处理这些问题是复杂的，容易出错的。
多主复制
基于领导者的缺点：
只有一个主库，而所有的写入都必须通过它，如果出现任何原因无法连接到主库，就无法向数据库写入
多主复制
处理写入的每个节点都必须将该数据更改转发给所有其他节点,在这种情况下，每个领导者同时扮演其他领导者的追随者
多主复制的场景
运维多个数据中心
每个数据中心都有主库，数据中心内使用常规的主从复制，在数据中心之间，每个数据中心的主库都会将其更改复制到其他数据中心的主库中。
在多个数据中心的情况下，单主与多主场景的对比
性能
- 单主：每个写入都需要穿互联网，增加写入时间
- 多主：每个写操作可以在本地数据中心处理，并与其他数据中心异步复制
容忍数据中心停机
单主：如果主库所在的数据中心发生故障，故障转移可以使另一个数据中心里的追随者成为领导者
多主：多活配置中，每个数据中心可以独立于其它数据中心继续运行，恢复后可以自动赶上复制。
容忍网络问题
- 单主：对于互联网环境下的连接非常敏感
- 多主：异步复制的多活配置能更好的承受网络问题。
现有使用
- 用于MySQL的 Tungsten Replicator
- 用于PostgreSQL的BDR
- 用于Oracle的GoldenGate
缺点
不同的数据中心可能会修改相同的数据，导致写冲突
需要离线操作的客户端
应用程序断网后仍然需要工作
在这种场景下每个设备都有一个充当领导者的本地数据库，在所有副本之间同步时存在异步的多主复制
Couchdb就是为这种模式而设计的
协同编辑
例如Etherpad、Google Docs
用户编辑文档，将更改立即应用到本地副本，并异步复制到服务器和编辑同一文档的任何其他用户。
为了加速协作，需要将更改的单位设置得非常小，避免锁定。
处理写入冲突
场景：两个用户同时修改一个页面上的标题：
同步与异步冲突检测
可以使用单主数据库中的冲突检测同步方案，即：
等待写入被复制到所有副本，然后再告诉用户写入成功
然而这样会失去多活中每个副本独自接受写入的优势。
避免冲突
如果应用程序可以确保特定记录的所有写入都通过同一个领导者，那么冲突就不会发生。
例如，在用户可以编辑自己的数据的应用程序中，可以确保来自特定用户的请求始终路由到同一数据中心，并使用该数据中心的领导者进行读写。
但是当需要更改指定记录的主库(如数据中心故障，或者是用户迁移了为止)，这时候就需要处理不同主库同时写入的可能性了。
收敛至一致的状态
多主状态可能会有不同的写入顺序，每个复制方案都必须要保证所有的主库的写入顺序都是相同的，保证复制完成时收敛至一个相同的最终值
常见方案：
- 给每个写入一个唯一的ID(时间戳，长随机数，UUID，键值哈希)，挑选最高的ID写入，并且丢弃其他最终写入胜利(LWW，last write wins)
- 为每个副本分配一个唯一的ID，ID编号更高的写入具有更高的优先级
- 以某种方式将这些值合并
- 保留所有信息的显式数据结构中的记录冲突，并编写解决冲突的应用程序代码
自定义冲突解决逻辑
大多数复制工具允许使用应用程序代码编写冲突解决逻辑，该代码可以在写入或读取时执行
写时执行
只要数据库检测到复制更改日志中存在冲突，就会调用冲突处理程序
例如:Bucardo允许使用Perl代码进行冲突解决
这种方式在后台进程中运行，不会让用户感知到。
读时执行
当检测到冲突时会写入所有冲突，下次读取时会将多个版本的数据返回给应用程序，应用程序可能会提示用户或自动解决，并将结果写回数据库，例如CouchDB。
多主复制拓扑
最普遍的是全通的拓扑
其中循环和星形的拓扑中，为了防止无限循环复制，每个节点都会被赋予一个唯一的标识，在复制日志中每个写入都标记了所有已通过节点的标识。
循环和星型拓扑的问题是：如果只有一个节点发生故障，可能会中断其它节点之间的复制消息流，直到节点修复，而全能拓扑的容错更好。
全能拓扑的问题在于：可能在某些副本中写入错误的顺序
这里需要使用版本向量(version vectors)的技术。
然而目前这方面的支持并不是很好
- PostgreSQL BDR不提供写入的因果排序
- Tungsten Replicator for MySQL甚至不尝试检测冲突
无主复制
在之前的单主，多主复制中，整体的思路都是：客户端向一个主库发送写请求，数据库将写入复制到其他副本，主库决定写入的顺序，从库按照相同的顺序应用主库的写入
有些数据库采用了无主库的概念，允许任何副本直接接受来自客户端的写入，例如亚马逊的Dynamo系统。
在一些无领导者实现中，客户端直接将写入发送到几个副本中，另一些情况下，一个协调者(coordinator)节点代表客户端进行写入，但是协调者不执行特定的写入顺序。
节点故障时写入数据库
在无领导模式中不需要故障切换，为了解决不可用的节点恢复后获取过时信息的问题，客户端在请求数据时，不仅仅发送请求到一个副本，读请求也会被并行的发送到多个节点中，通过版本号来确定哪个值更新。
读修复与反熵
一个不可用的节点重新联机后如何赶上它错过的写入？
读修复
当客户端读取时，发现了旧版本的值，会将新值写回复制品
反熵过程
一些数据存储具有后台进程，该进程将任何确认的数据从一个副本复制到另一个副本。
如果没有反熵过程，那么某些副本中很少读取的值将会丢失，从而降低了持久性
读写的法定人数
如果有n个副本，每个写入必须由w个节点确认才能被认为是成功的，并且我们必须至少为每个读取查询r个节点。
w则被称为法定人数。
仲裁条件$w + r > n$允许系统容忍不可用的节点
- w < n：如果有节点不可用，仍然可以处理写入
- r < n: 如果有节点不可用，仍然可以处理读取
- n = 3, w = 2, r = 2，可以容忍1个不可用的节点
- n = 5, w = 3, r = 3, 可以容忍2个不可用的节点
- 通常，读写操作始终并行发送到所有n个副本，参数w和r决定我们需要等待多少个节点。
这里我们只需要关心节点是否返回了成功的响应，不需要区分不同类型的错误。
仲裁一致性的局限性
即使 w + r > n的情况下，也可能存在返回陈旧值的边缘情况
- 使用松散的法定人数，w个写入和r个读取落在完全不同的节点上
- 两个写入同时发生，唯一安全的方案是合并冰法写入，如果根据时间戳挑选胜者，写入可能丢失
- 写操作与读操作同时发生，写操作可能只反映在某些副本上，会不确定读取是返回旧值还是新值
- 写操作在某些副本上成功，但是在其它节点上失败，虽然整体判定写入失败，但是整体写入失败并没有在写入成功的副本上回滚
- 如果携带新值的节点失败，需要读取其它带有旧值副本，则新值的副本数可能会低于w打破法定人数条件
- 即使一切正常，也可能出现时序的边缘情况。
因此不能将其作为绝对的保证。
监控的陈旧度
对于基于领导者复制的场景：
数据库通常会公开复制滞后的度娘标准。，可以定量的车辆复制滞后量
对于无领导者复制的系统
没有固定的写入顺序，使监控变得更加困难。
目前有一些衡量无领导者复制陈旧度的研究，根据n,w和r来预测陈旧度读取的预期百分比，可惜这还不是很常见。
松散法定人数
当大部分节点不可用时，这时候需要权衡
- 将错误返回给无法达到w或r节点的法定数量的所有请求？
- 接受写入，将其写入一些可达节点，但数量不足n值，或者也不是通常中使用的n
后者方案即松散法定人数，写和读需要w和r成功的响应，但是可能不仅仅是原来的n个节点的值
当原来节点恢复后，临时接受的节点会发送到原本的本地节点中，这就是所谓的带提示的接力。
松散法定人数提高写入可用性，但是不能确定读取到某个键的最新的值
在常见的Dynamo实现中，松散法定人数是可选的
- Riak是默认启用
- Cassandra和Voldemort中是默认禁用的
运维多个数据中心
无主复制同样适用于多数据中心的操作
- Cassandra和Voldemort：支持多数据中心，副本n包括所有数据中心的节点
- Riak：n描述了一个数据中心内的副本数量，集群间的复制在后台异步发生
检测并发写入
可以看到，由于每个节点都可以自由的写入，无顺序的写入，这样会导致各个节点的值不一致，为了达到最终一致，副本应该趋向相同，然而复制的数据库的自动处理都很糟糕，因此需要更多的去了解数据库冲突处理的内部信息。
最后写入为准(丢弃并发写入)
允许每个副本只存储最近的值，并且允许更老的值被覆盖和抛弃，只要明确了最近的方法，那么最终写入就会被复制。
但是在并发情况下比较难以确定什么是最近的，因此可以采用任意强制排序
- 为每个写入附加时间戳，抛弃较早时间戳(LWW,最后写入为准)
- 确保每个键只写入一次，然而视为不可变
“此前发生的”关系和并发
只要有两个操作A、B，就会有3种可能，A在B之前发生，B在A之前发生或者A、B并发，需要一个算法来告诉我们是否两个操作是并发的。否则，应该后面的阿偶哦覆盖较早的操作。
为了定义并发性，确切的时间并不重要:如果两个操作都意识不到对方的存在，就称这两个操作并发，而不管它们发生的物理时间
捕获“此前发生”关系
一个在单服务器版本上的例子
- 服务器为每个键保留一个版本号，每次写入时都增加版本号，并将新版本号与写入的值一起存储
- 客户端读取时，服务器将返回未覆盖的值以及最新的版本号，客户端在写入前必须读取
- 客户端写入键，必须包含之前读取的版本号，并且必须将之前读取的所有值合并在一起。
- 当服务器接收到具有特定版本号的写入时，它可以覆盖该版本号或更低版本的所有值，但是它必须保持所有值更高版本号。
总之，当一个写入包含前一次读取的版本号时，它会告诉我们写入的是哪一种状态。如果在不包含 版本号的情况下进行写操作，则与所有其他写操作并发，因此它不会覆盖任何内容 —— 只会 在随后的读取中作为其中一个值返回。
合并同时写入的值
一种合理的合并兄弟方法就是集合求并。
Riak的数据类型支持使用称为CRDT的数据结构家族可以以合理的方式自动合并兄弟，包括保留删除。
版本向量
使用单个版本号不能解决多个副本并发接受写入的问题，因此需要在每个键使用版本号外，还需要在每个副本中使用版本号，并且跟踪从其它副本中看到的版本号，这些版本号的集合被成为版本向量
读取时，版本向量会从数据库副本发送到客户端，随后写入值时需要将其发送回数据库。