1.前言
备份，意思就是多台机器通过网络传输保存同一份数据，为什么需要备份呢
保证数据地理上离用户近，减少延迟
提高可用性，即使部分系统挂了，系统还是能够持续工作
能够水平拓展吞吐量（scale out）
如果数据没有改动，备份就简单了。
但是困难就在于应对数据的变动
本章就讲解如何对变动的数据进行备份
根据节点的不同，主要有三种算法：单leader，多leader，无leader
由于篇幅原因，本篇只讲单leader模型
2. 单leader备份模型，运行机制，实现机制等相关问题
每个存储了数据的拷贝的数据库节点称为一个备份。
有个问题就是如何保证所有数据在所有备份中
工作机制如下：
1.一个备份作为leader，处理所有写请求
2.其他备份作为follower，
每当leader写数据后，leader也把这个变动发给follower。
每个follower按顺序执行对应的更改
3.当客户端读数据的时候，随机从leader或者follower读（写时只往leader写）
典型的模型如下
这种模型应用广泛
2.1 异步备份还是同步备份
leader处理写请求传递给follower时，是同步还是异步呢
可以看到leader要等到follower1返回了之后，才能回复client
实际情况下，并不保证followerer多久能回复leader
当然也有一些场景，允许follower的数据落后leader几分钟或者更长。
同步备份的优劣
优点：保证所有follower都和leader的数据是一样的，是最新的
缺点：leader会受到follower和网络的影响，会block住
所以，让所有follower都同步备份是不现实的。
有一个“半同步”的思路，就是leader和一个follower同步备份，和其他follower异步备份。这样leader挂了，至少有一个follower数据是最新最全的。
实际上，基于leader的备份经常是完全异步的，优劣如下
优点：leader能处理写请求即使所有follower都挂了
缺点：刚向写入leader的数据后leader挂了，这份数据就丢失了，其他follower也没有
2.2 加入新的follower
加入新机器作为follower来实现scale out的时候，如何让新的follower能够有和leader一样的数据
如果简单的copy一份数据，那么此过程中leader还会被持续不断的写入，这部分数据就对follower不可见了
如果copy时禁止leader的写入，会影响可用性。
实际上有下面这个方法解决问题:
1.leader的数据进行一个快照
2.leader把快照给follower
3.follower连上leader，根据快照生成本地的备份数据（这份数据不包括leader在快照之后新写的数据）
4.follower将leader快照之后的数据变动一一获取，完成catch up
2.3 处理挂掉的节点
所有节点都可能会挂掉，如何在leader-based算法上实现高可用性呢（有机器挂了还能用）
2.3.1 follower挂了：catch-up 恢复
不管是机器挂了还是follower与leader网络暂时不通了，后续两者建立连接之后，
follower把本地记录的一个事务日志与leader传递过来的事务日志进行比较
（可以理解成各自有一个最新的commit id）
那么中间有差距的地方就是follower落后leader的进度，把这些变动都应用在follower上就能catch up了
2.3.2 leader挂了：故障转移
处理leader挂掉的方法比较tricky
让一个follower称为新的leader。
client需要重新配置，发送写请求给新的leader。
所有其他的follower也要重新和新的leader交互。
这个方式称为故障转移
故障转移可以手动也可以自动完成，自动的过程如下
1.检测leader挂掉了：挂的原因多种比如断点，网络问题等。
常见检测方法是（心跳）超时，比如超过30s没有应答则认为机器挂了
2.选举新leader。通过对剩下的节点，进行选举
一般要求数据最新的节点称为新的leader（减少丢失的数据）。
如何选举，达成一致在第9章讲解
3.重新配置系统识别新的leader。
clients要知道新的leader
其他follower也要知道这个新的leader
包括崩溃后恢复的旧的leader，也会成为follower来和新的leader交互
但是故障转移会有下述问题
1.如果用异步备份，那么旧的leader挂掉时，有可能部分数据只有本地才有而其他节点没有。
那么当它再恢复时，本地会有新的leader没有的数据。
最常见的处理方式是旧leader的未备份的数据全部丢掉，这会有一点点违背client的预期
2.丢弃部分写请求是很危险的
比如github上有个故障是mysql中旧的leader数据比新的leader要新，按照上面1的做法这些数据会被丢掉。
然后新leader写数据，由于数据落后，会重用一些已经分配过的primary key，会造成duplicate key等等
3.有些场景会出现两个自认为leader的节点
此时两个leader都能接收写请求，没有方法解决冲突。有些系统会关闭一个leader，但需要仔细设计
4.检测dead时设定的（心跳）超时时间该如何合理设置
这些问题都不简单，因此有时一些团队直接手动进行故障转移。
这些问题会在后面8,9章深入讨论
2.4 备份日志的实现
如何实现leader-based的备份工作呢，有几种方法
2.4.1 statement-based 备份
最简单的方式，就是leader记录所有他执行的写请求语句，发给follower让他们去执行。
对于DB来说，写请求你语句就是每个执行的insert，update，delete语句等。
看起来合理，但是有如下问题
1.有不确定性的语句，如NOW()以及RAND(),这个在不同辈分上获得的值可能不一样
2.如果有自增的列，或者有一些聚合信息的要求如SUM等，则要求备份执行的顺序相同
3.触发器，存储过程等在不同备份上的副作用可能不同
有些解决办法是，把不确定性的调用，换成leader本地存储的值，这样发送给follower就行。
这种方法在MySQL 的5.1版本之前这样用。
但是其他的备份方法更流行。
2.4.2 Write-ahead log(WAL) shipping
就是第三章讲索引的时候，提到了WAL即提前写的日志，里面记录的修改是还没有执行的。
leader把这个WAL转移给各个follower让他们执行。
PostgreSQL和Oracle等用这个方法。
（这个我没有看懂，没看出来怎么解决上面statment-based的不确定性问题，只不过上面是发送语句，这个是发送log）
2.4.3 逻辑（基于row）日志备份
另一种做法是用不同的存储格式。
在DB中，常常是在行的粒度来描述写入的记录:
1.对于insert，log记录所有列的数据
2.对于delete的行，log包含足够的信息来确定是哪一行，有主键就用主键，否则就记录所有列的信息
3.对于update的行，log包含足够的信息来确定是哪一行，以及所有列（或者部分更新的列）的新值
一个事务修改多行的话，日志就包含多条记录，最后跟着一个commit标识。
由于逻辑日志和存储引擎内部实现解耦，能够更好地满足向前兼容性，允许leader和follower以不同的版本甚至不同的数据库来运行。
2.4.4 基于触发器的备份
上面讲的都是DB自己实现的，有些场景只想要备份部分数据，或者一种特定的数据。
有一个方法是用DB中的特性：触发器和存储过程。
触发器能够允许数据改变时执行自己的业务代码，能够满足备份的要求。
但是基于触发器的备份开销更大，更容易有bug和限制。
尽管如此它也很常用，因为非常灵活。
2.5 备份延迟的问题
在2.1中提到异步备份时,有这个问题
在异步备份时，查询如果落到follower上，可能是老的数据（最新的数据leader还没有异步备份完成）
这导致了数据的不一致性
如果停止一会写操作，那么follower最终会catch up并且和leader的数据一致
这就是最终一致性
然后“最终”的定义很模糊：没有定义备份可以落后多少进度。一般来说一秒以内就能catch up，但是遇到网络等问题，可能需要几秒甚至几分钟。
但延迟非常大的时候，就会对应用造成严重的问题。这部分讲解延迟导致的三个问题以及提出一些解决方法。
2.5.1 读自己的写
名称有点绕，场景是这样。
比较好理解，因为目标follower机器还没有最新的数据，用户就找不到刚刚的改动。
这种场景下用户不会开心。
因此，要考虑“写后读”的一致性
就是用户写之后，总能读到自己刚刚的提交
但是不保证看到其他用户刚刚的写操作
如何保证呢：
1.用户读时，判断读到的数据是否是他能修改的。
若是，则从leader读。否则从follower读
比如个人信息这些内容，只有自己能改。
因此读自己个人信息时，每次都从leader读。
读别人的信息时，从follower读。
2.如果一个应用中，很多内容都是可以被用户写的，上述方法就不管用了
此时，可以通过last update time判断follower落后leader的进度。
比如说follower落后了1min，那么就去leader读或者禁止该follower提供读的支持。
（个人理解这里只能缓解问题，并不能一定解决问题）
3.client能够知道最后一次写的时间（时间有时不准，可以用log序列号替代）
发送到follower时，follower拿自己的时间（或者序列号）和client的比较
如果不如client的新，要么让其他follower服务，要么等自己catch up了再服务
4.如果备份在多个数据中心（地理上离用户近，减少延迟）
此时要保证每个请求都需要路由到 包含有对应的leader的数据中心
如果说需要支持 用户跨设备的写后读一致性，又要考虑如下问题
1.用户的last update时间戳（序列号）需要中心化存储（意思就是存在服务端）
2.多个数据中心的话，要保证用户的所有设备会定位到同一个数据中心
2.5.2 单调读
某些场景下，用户有可能会看到事情在倒退！如下图
这个场景就是用户读的时候，先去了数据比较新的follower，再次请求读，去了数据比较老的follower
单调读就是保证不会出现读的数据出现了倒退的情况。
它比强一致性弱，比最终一致性要强。
实现方式比较简单
用户读之后去特定一个节点读（通过userId hash），而不是随机去不同的节点
如果目标节点挂了，那么换到其他的节点上去
2.5.3 前缀一致性读
个人感觉也可以叫 拓扑一致性读
就是说在分区的数据库（每个区有一个leader）时，本来两个有拓扑顺序的写，在读的时候顺序错乱了，如下图
关于分区会在第6章讨论。解决这个问题需要前缀一致性
一系列写以某种顺序出现，
任何读这些写的行为，都应该读到一样的顺序
但是分布式db中，各分区单独工作，所有并不存在全局写的顺序，只是局部有序。
一种解决办法是，使得有拓扑关系的写，存在于同一个分区。
后面会再讨论这个问题
2.5.4 解决备份延迟的方法
总结一下各种方法，都不太实用。
最好业务代码不用管这些备份问题，相信自己的DB
所以有了 事务 的存在，分布式事务后面7,9章再介绍
3.思考
3.1.需要备份的三个理由
在1前言部分讲解
3.2.关于之前看zookeeper源码的思考
前面关于leader，follower，同步异步备份，快照的问题，崩溃恢复这些问题
在看完zookeeper源码之后都很好理解
3.3.比较statement-based和逻辑（基于row）日志备份
感觉前者更倾向于动作，记录住insert，update，delete等
后者倾向于静态的结果，只管记住新的，改动的列（针对一行）
3.4.备份延迟
通过举例描述出写后读一致性的必要性并给出办法，受益匪浅
4.问题
4.1故障转移的缺陷中，出现两个leader是什么情况
书中也没有列举论文，看zk源码也没注意到有这个问题
4.2 statment-based备份的问题
最简单的触发器和存储器的副作用是什么，暂时不清楚
4.3 WAL shipping
这个目前不懂，优缺点也没有理解，以后参照refer吧
4.4 单调读的实现
2.5.2中，说用一个节点处理读，如果这个节点挂了，就会换一个节点
那么此时换节点应该还是会有 读的数据出现倒退了 的情况
refer
WAL
https://en.wikipedia.org/wiki/Write-ahead_logging
WAL shipping
https://www.postgresql.org/docs/9.5/static/warm-standby.html
