《数据密集型应用系统设计》第五章数据复制笔记
主从复制
集群中有一个主节点，写操作都必须经过主节点完成，读操作主从节点都可以处理。
同步复制和异步复制
同步复制
数据在副本上落盘才返回。
- 优点：保证在副本上的数据是最新数据。
- 缺点：延迟高，响应慢。
异步复制
数据不保证在副本上落盘。
- 优点：延迟低
- 不能保证在副本上的数据最新。
不能把集群中所有节点设置为同步节点，因为这样的话任何一个节点的停滞都会导致整个集群的不可用。像Paxos、Raft算法，都要求集群中大多数节点返回就可以了。部分同步、部分异步的集群配置成为半同步（semi-sync）的集群配置。
新增新的从节点
- 主节点生成快照数据
- 主节点将快照数据发送到从节点。
- 从节点请求主节点快照数据之后的数据。
- 重复上面三步直到从节点追上主节点的进度。
处理节点失效
从节点失效
从节点崩溃恢复之后按照前面新增新的从节点的步骤来追上主节点的数据进度。
主节点失效
主节点失败时需要提升某个从节点为新的主节点，同时需要通知客户端新的主节点。
自动切换主节点的步骤通常如下：
- 确认主节点失效。大部分系统采用基于超时的机制，主从节点直接发送心跳消息，主节点在某个时间内都没有响应，则认为主节点已经失效。
- 选举新的主节点。通过选举的方式（超过半数以上的从节点达成共识）来选举新的主节点，新的主节点是与旧的主节点数据差异最小的一个，最小化数据丢失的风险。
- 重新配置使新的主节点上线。
除了以上步骤之外，还有以下问题需要考虑：
- 如果使用异步复制机制，而且在失效之前，新的主节点并没有收到旧的主节点的所有数据，那么在旧的主节点重新上线之后，未完成复制的数据将被丢弃。
- 可能会出现集群同时存在两个主节点的情况，也就是所谓的脑裂（split brain）现象，此时两个主节点都认为自己是主节点并且都能接收客户端的写数据请求，会导致数据丢失或者破坏。
- 如何设置合理的超时时间来判断主节点失效？如果太大意味着总体恢复时间长，如果太小意味着某些情况下可能主节点并未失效但是被误判为失效了，比如网络峰值导致延迟高等原因，这样会导致很多不必要的主节点切换。
上述的问题，包括节点失效、网络不可靠、副本一致性、持久性、可用性与延迟之间的各种细微的权衡，正是分布式系统核心的基本问题。
复制日志的实现
基于语句的复制
主节点记录所执行的每个写请求并将该语句做为日志发送给从节点。但是有些场景并不适合这么做，比如：
- 调用任何非确定函数的语句，比如NOW()获得当前时间，RAND()返回一个随机数。
- 语句中使用了自增列，或者依赖于当前数据库的数据。
- 有副作用的语句，在每个副本上面执行的效果不一样。
基于预写日志(WAL)
将对数据库的操作写入日志，传送到从节点上然后执行，得到与主节点相同的数据副本。
基于行的逻辑日志复制
所谓的逻辑日志，就是复制与存储引擎采用不同的日志格式，这样复制与存储逻辑剥离，这种日志称为逻辑日志，与物理存储引擎的数据区分开。由于逻辑日志与存储引擎逻辑上解耦，因此可以更好的向后兼容，也更好的能被外部程序解析。
对于关系型数据库，其逻辑日志是一系列用来描述数据表行级别的写请求：
- 插入行：日志包括所有相关列的新值。
- 删除行：日志中保证要有足够的信息来唯一标识待删除的行，通常是主键。
- 更新行：日志中保证要有足够的信息来唯一标识待更新的行，同时也有所有列的新值。
复制滞后（replication lag）问题
如果一个应用正好从一个异步复制的从节点上读取数据，则可能读取不到最新的数据，这是因为主从节点的数据不一致导致的。理论上不一致状态在时间上并没有上限。以下描述几个复制滞后导致的问题。
读自己的写（reading your own writes）
用户在写入数据不久就马上查看数据，而新数据并未到达从节点，这样在用户看来可能读到了旧的数据。这样情况需要“写后读一致性（read-after-write consistency）”，该机制保证每次用户读到的都是自己最近的更新数据，但是对其他用户则没有任何保证。
在上图中，用户1234首先向主节点写入数据，SQL执行成功之后返回，而此时用户再次向从节点2发起读刚才写入数据的请求，但是却读到了旧的数据。
有以下方案实现写后读一致性。
- 如果用户访问可能会被修改的内容，从主节点读取。比如社交网络的本用户首页信息只会被本人修改，访问用户自己的首页信息通过主节点，而访问其他用户的首页信息则走的从节点。
- 如果应用大部分内容都可能被所有用户修改，则上述方法不太适用。此时需要其他机制来判断哪些请求需要走主节点，比如更新后一分钟之内的请求都走的主节点。
- 客户端可以记住自己最近更新数据的时间戳，在请求数据时带上时间戳，如果副本上没有至少包含该时间戳的数据则转发给其他副本处理，直到能处理为止。但是在这里，“时间戳”可以是逻辑时钟（比如用来指示写入数据的日志序列号）或者实际系统时钟（而使用系统时间又将时间同步变成了一个关键点）。
- 如果副本分布在多数据中心，必须将请求路由到主节点所在的数据中心。
单调读（monotonic reads）
单调读一致性保证不会发生多次读同一条数据出现回滚（moving backward）的现象。这个是比强一致性弱，但是比最终一致性强的保证。
在上图中，用户2345发起了两次读请求，第一次向从节点1发起的请求拿到了最新的数据，但是第二次向从节点2发起的请求得到了旧的数据，这在用户看来，数据发生了“回滚”。
单调读一致性可以确保不会发生这种异常。当读取数据时，单调读保证：如果某个用户进行多次读取，则绝对不会看到数据回滚现象，即在读取到新值之后又发生读取到旧值的情况。
实现单调读一致性的一种方式每个用户的每次读取都从固定的同一副本上进行读取。
前缀一致读（consistent prefix reads）
前缀一致性读保证，对于一系列按照某个顺序发生的写请求，读取这些内容时也会按照当时写入的顺序来。
例如，正常情况下，是如下的对话：
- poons先生：cake小姐，您能看见多远的未来？
- cacke小姐：通常约10秒，poons先生。
但是在上图中，从观察者角度，数据的先后顺序发生了混淆，导致了逻辑上的混乱。
这种问题是分区情况下出现的特殊问题，在分布式数据库中，不同的分区独立运行，因此不存在全局写入顺序，这就导致用户从数据库中读取数据时，可能看到数据库某部分的旧值和一部分的新值。
实现前缀一致性的一种方案是确保任何具有因果顺序关系的写入都交给一个分区来完成，但是该方案真实实现起来效率不高。
复制滞后的解决方案
多主节点复制
适用场景
多数据中心
为了容忍整个数据中心级别故障或更接近用户，可以把数据库的副本横跨多个数据中心。在每个数据中心内，采用常规的主从复制方案；而在数据中心之间，由各个数据中心的主节点来负责同其他数据中心的主节点进行数据的交换、更新。
主从复制的优缺点：
-
优点
- 性能：每个写操作可以在本地数据中心就近快速响应，采用异步复制方式将变化同步到其他数据中心。
- 容忍数据中心失败：单个数据中心失败，不影响其他数据中心的继续运行。
- 容忍网络问题：主从复制模型中写操作是同步操作，对数据中心之间的网络性能和稳定性等要求更高。多主节点模型采用异步复制，可以更好的容忍这类问题。
-
缺点：多个数据中心可能同时修改同一份数据，造成写冲突。
离线客户端操作
每个客户端可以认为是一个独立的数据中心，这样用户就可以在离线的状态下使用客户端，而在网络恢复之后再将数据同步到服务器。
协作编辑
允许多个用户同时编辑文档，如google docs。这样每个用户就是一个独立的数据中心了。
处理写冲突
多主复制最大的问题就是要解决写冲突，如下图所示。
两个用户同时编辑wiki页面，发生了写冲突。
同步与异步冲突检测
如果是主从复制数据库，第二个写请求会被阻塞到第一个写请求完成。而在多主从复制模型下，两个写请求都是成功的，并且只有在之后才能检测到写冲突，而那时候要用户来解决冲突已经为时已晚了。
如果要多主从复制模型来做到同步检测冲突，又失去了多主节点的优势：允许每个主节点接受写请求。
因此如果确实想要做到同步检测写冲突，应该考虑使用单主节点的模型而不是多主从节点模型。
避免冲突
如果应用层能保证针对特定的一条记录，每次修改都经过同一个主节点，就能避免写冲突问题。
但是，在数据中心发生故障，不得不路由请求到另外的数据中心，或者用户漫游到了另一个位置，更靠近另一个数据中心等场景下，冲突避免不再有效。
收敛于一致状态
有以下方式解决冲突的收敛：
- 给每个写入分配唯一的ID，如时间戳、足够长的随机数、UUID等，规定只有高ID的写入做为胜利者。如果是基于时间戳的对比，这种技术被称为后写入者获胜（last write win），但是很容易造成数据丢失。
- 给每个副本分配一个唯一的ID，并制定规则比如最高ID的副本写入成功，这种方式也会导致数据丢失。
- 以某种方式将这些值合并在一起。
- 使用预定义的格式将这些冲突的值返回给应用层，由应用层来解决。
自定义冲突解决逻辑
解决冲突最合适的方式还是依靠应用层，可以在写入或者读取时执行。
拓扑结构
无主节点复制
放弃主节点，允许所有节点处理来自客户端的写请求，如Dynamo、Riak等。
节点失效时写入数据库
对于无主节点复制的集群而言，当向有三个副本的集群写入数据时，只要其中有两个副本写入完成则认为写入成功，而可以容忍其中一个节点的失效。那么当这个失效节点重新上线时，则可能读到已经过期的数据。为了解决这个问题，当客户端从集群中读取数据时，并不是只向一个副本发起请求，而是并行地发送到多个副本，客户端可以根据数据版本号来确定哪个数据最新。
读写quorum
在有三个副本的情况下，如果有两个副本写入成功，那么意味着最多有一个副本可能包含旧的值，此时如果向至少两个副本发起读请求，通过版本号可以确定至少有一个包含新的值。
推而广之，如果有n个副本，写入需要w个节点确认，读取必须至少查询r个节点，则只需要w+r>n，那么读取的节点中一定包含新值。
上述参数通常是可以配置，比如n取奇数值，而r、w去(n+1)/2。也可以根据业务需求灵活配置，比如对于读多写少的业务，设置w=n或者r=1，这样读取速度更快，但是只要一个节点的写入失败而导致quorum写入失败。
quorum一致性的局限性
检测并发写
请求在不同节点上可能会呈现出不同的顺序，如下图所示：
客户端A和B同时发起向主键X的写请求：
- 节点1收到客户端A的写请求，但是由于节点紧接着就失效了，没有收到客户端B的写请求。
- 节点2首先收到A的写请求，接着才收到B的写请求。
- 节点3与2相反，先收到B再收到A的写请求。
如果处理方式仅仅是每次收到新的写请求就简单覆盖原来的值，那么这些节点永远也无法达成一致。
所以需要一种更合理的方式来解决并发写冲突。
最后写入者胜出（Last Write Win，简称LWW）
为每个写请求附件一个时间戳，然后选择最新即最大的时间戳，丢弃较早时间戳的写入，这种方案称为Last Write Win。
这种方案的问题在于：物理时间本身就不可信任，一个机器上的时间到了另一个机器上并不就精准。另外，牺牲了部分的写入数据，比如某客户端写入时返回成功，但是会被后面并发写入但是被认为更晚时间的写入给覆盖掉，这样这部分认为写入成功的数据就丢失了。
要确保LWW无副作用的唯一办法是：之写入一次然后写入值视为不可变。这样就能避免对同一个主键的覆盖。例如，cassandra的推荐使用方式是使用UUID做为主键，这样每个写操作都针对不同的、系统唯一的主键。
Happen-before关系与并发
两件事情A、B只有三种可能存在的关系：
- A在B之前发生。
- B在A之前发生。
- A、B并发进行。
一件事情在另一件事情之前发生，说明两者之间存在依赖关系。比如A说了一句话，而B需要对这句话进行回应，回应这个事件就依赖于A说话这个事件，此时B的回应依赖于A的话，因此B的回应肯定发生A说话之后。
如果两件事情之间没有依赖关系，那么先后顺序是无所谓的，即并发进行。
来看一个实际的例子，两个客户端同时向一个购物车添加物品：
流程如下：
- 客户端1首先将牛奶放入购物车，服务器分配版本号1，将值与版本号一起返回给客户端。
- 客户端2将鸡蛋放入购物车，因为此时客户端2并不知道客户端1已经放入了牛奶，因此认为鸡蛋是购物车中的唯一物品。服务器写入并分配版本号2，将鸡蛋和牛奶存储为两个单独的值，最后将版本号2和值返回给客户端2。
- 同理，客户端1再次写入时也没有意识到2已经修改了购物车，此时它想继续添加免费，认为此时购物车的内容应该是[牛奶,面粉]，因此将这个值与版本号1一起发给服务器。服务器收到之后，意识到是针对版本号1做的修改，即将[牛奶]修改成[牛奶面粉]，但是另一个值[鸡蛋]则是新的并发操作。因此，服务器分配了一个新的版本号3，版本号3的值[牛奶,面粉]覆盖版本1的[牛奶]，同时保留版本号2的值[鸡蛋]，一起返回给客户端1。
- 客户端2想加入火腿，而它也不知道客户端1添加了面粉。其收到的最后一个响应中服务器给的值是[牛奶]和[鸡蛋]，因此进行了合并并且加入自己要添加的火腿，向服务器发送了版本号2以及新的值[鸡蛋,牛奶,火腿]。服务器检测到版本号2将覆盖原来的值[鸡蛋]，但是与[牛奶,面粉]是同时发生，所以设置了版本号4并将这些值一起返回给客户端2。
- 最后，客户端1想添加培根，在以前的版本3中从服务器收到了值[牛奶,面粉]和[鸡蛋]，所以进行了合并，将添加了培根以及合并之后的值[牛奶,面粉,鸡蛋,培根]和版本号3来覆盖[牛奶,面粉]，但是由于与[鸡蛋，牛奶，火腿]并发，所以服务器会保留这些值。
服务器判断操作是否并发的依据主要依靠版本号：
- 服务器为每个主键维护一个版本号，每当主键新值写入时递增版本号，并将新版本号与写入的值一起保存。
- 当客户端读取主键时，服务器将返回所有（未被覆盖）当前值以及最新的版本号，且要求写入之前，客户端必须先发送读请求。
- 客户端写主键，写请求必须包含之前读到的版本号、读到的值和新值合并后的集合。写请求的响应可以像读请求一样，返回所有值，这样就可以像购物车例子那样一步步链接起多个写入的值。
- 当服务器收到带有特定版本的写入时，覆盖该版本号或更低版本的所有值（因为知道这些值已经被合并到新传入的值集合中），但必须保留更高版本号的所有值（因为这些值与当前的写操作属于并发）。
这种方案不会让写入的值丢失，但是需要在客户端做合并操作，将多个写入的值进行合并。