数据复制
date
Nov 6, 2021
slug
DDIA-chapter5
status
Published
tags
DDIA
summary
DDIA第五章读书笔记
type
Post
TOC
数据复制(Replication)的几个目的：
- 使数据在地理位置上更接近用户，从而降低访问延迟
- 当部分组件出现故障，系统依然可以继续工作，从而提高可用性
- 扩展至多台机器以同时提供数据访问服务，从而提高吞吐量
主节点与从节点
- 每个保存数据库完整数据集的节点称为副本，如何确保所有副本之间的数据是一致的？
常见的解决方案是基于主节点的复制：
- 指定一个副本是主节点，写数据库的时候，必须向主节点写，从节点不能写
- 其他的节点是从节点，主节点写完之后将数据更改发给所有从节点
- 客户读数据的时候可以从主节点或者是从节点读。
同步复制与异步复制
同步复制：主节点接收到请求，执行写操作并且将请求转发给从节点，从节点也执行完之后主节点才通知用户操作完成。
- 优点：一旦向客户确认，数据就都处于最新状态（如果主节点崩溃还可以访问从节点）
- 缺点：如果某个从节点因为什么原因无法完成确认，写入就不能视为成功，主节点就会阻塞后面的写操作。
异步复制：不同等待从节点的确认主节点就直接向用户确认。
- 优点：从节点的中断不会影响主节点的吞吐性能
- 缺点：复制滞后问题，无法保证数据的持久化（即使主节点向客户确认了写操作，但是如果主节点崩了，没有同步到从节点的写操作就没有了）
实践中有时候会采用半同步（一个主节点和一个从节点是同步复制，其他都是异步复制），也有时候采取全异步复制。
配置新的从节点
简单的复制不行（因为主节点还在源源不断写数据），锁定数据库让其不可写也不现实。
主要操作步骤如下：
1. 某个时间点对主节点的数据副本产生一个一致性快照，这样避免长时间锁定数据库。
2. 将快照拷贝给从节点
3. 从节点连接主节点并且请求快照后的更改日志
4. 获得日志之后，从节点应用快照点后的变更（catch up）
处理节点失效
从节点失效：追赶式恢复
从节点都会有数据变更日志，crash掉重启之后向主节点请求中断之间的日志然后根据日志恢复。
主节点失效：节点切换（fallover）
要选择新的主节点。
自动切换的步骤：
1. 确认主节点失效（比如未响应之类的）
2. 选举新的主节点（超过多数节点达成共识，候选节点最好和之前的主节点数据差异最小）
3. 重新配置系统使主节点生效（确保系统认为这个节点是主节点，然后当之前的主节点又生效的话要迫使其下台成为从节点并且认可新的主节点）
可能的变数：
- 如果异步复制，原主节点有没有生效的写操作，然后重新上线并没有意识到身份变化又向其他节点同步会出现冲突的写请求（解决方法是将原来主节点未完成的写请求丢弃）
- 如果数据库有其他系统依赖数据库的数据，那么丢弃数据会很危险
- 某些故障情况下，可能两个主节点都认为自己是主节点。（安全应急方法是关掉其中一个）
- 如何设置合适的时长来检测主节点失效？太长意味着恢复时间长，太短就会有不必要的fallover
复制日志的实现
基于语句
例如主节点把sql语句发送给从节点，从节点执行语句
合理简单但是有问题：
- 如果调用非确定性函数就会出问题，比如NOW()获取当前时间
- 如果自增列，或者依赖现有数据，则必须保证从节点是相同顺序
- 有副作用的语句
基于预写日志(WAL)
- 比如对于LSM结构的，日志是主要存储结构
- 对于Btree，每次修改会写入日志
缺点是太底层了，这使得复制方案和存储引擎耦合严重。这可能导致系统无法支持主从节点运行不同版本的软件。
基于行的逻辑日志
关系数据库的逻辑日志通常是一系列记录来描述数据表行级别的写请求：
- 行插入，日志包含所有相关列的新值
- 行删除，日志里有足够信息来唯一标识以删除的行
- 对于行更新，日志包含足够的信息唯一标识更新的行，以及所有列的新值。
逻辑日志和存储引擎解耦，更容易向后兼容，对于外部程序，逻辑日志也更方便解析。
基于触发器的复制
触发器支持注册自己的应用层代码，使得数据库系统发生数据更改时自动执行上述的自定义代码。
复制滞后问题
主从复制适合于读操作密集的负载（如Web），但是这种的只能用异步复制。
如果同时对主节点和从节点发起相同的查询，可能会得到不同的结果，这种不一致是一个暂时的状态，如果停止写数据库，经过一段时间后，从节点会catch up主节点保持一致，这种效应称为最终一致性(eventual consistency)
下面是复制滞后可能出现的三个问题
读自己的写
用户写数据的时候向主节点写，读数据的时候向从节点读，从节点如果存在复制滞后问题，那么用户就会发现自己刚写的东西丢掉了，这体验很糟糕。
对于这种情况我们要**写后读一致性**
解决方案：
- 如果用户想要访问可能被修改的内容就规定从主节点读，否则从从节点读（比如社交网络的主页配置文件一般都是自己改，其他人不能改，所以形成了一个简单的规则，总是从主节点读取用户自己首页配置文件，从从节点读取其他人的配置文件）
- 如果很多东西都可以编辑，就不太适用于上面的方式，可以用其他方式，比如追踪最近更新的时间，如果更新后一分钟再读就从主节点读取，监控从节点的复制滞后程度，避免从超过一分钟的从节点读
- 客户端还可以记住最近更新的时间戳，并且附在读请求中。副本在对这个用户提供读服务时要至少包含这个时间戳的更新。如果不够新就交给其他副本，要么等待该副本接受了最近的更新。时间戳可以是逻辑时间戳（用来指示写入顺序的日志序列号）或实际系统时钟（时钟同步又是另一个关键点）
- 如果副本分布在多数据中心（考虑与用户的地理接近，以及高可用性），情况会更复杂些，必须先请求路由到主节点所在的数据中心。
单调读
如果一个用户连续进行两次查询，一个是从一个较新的副本读取，第二次是从一个较旧的副本读取，就可能出现用户第一查询出来结果了，一刷新就没了。
- *单调读一致性**保证某个用户多次读取不会看到回滚的现象。
实现单调读的一种方式是，确保每个用户总是从同一个副本执行读取（而不同的用户可以从不同的副本读取），例如基于用户ID的哈希值来选择副本而不是随机选择副本。
前缀一致性读
图中的例子是两个有先后关系的对话，但是由于延迟，所以观察者收到了相反的顺序。
- 前缀一致读，该保证是说，对于一系列按照某个顺序发生的写请求，那么读取这些内容时也会按照当时写入的顺序。
多主节点复制
主从复制有一个明显的缺点，系统只有一个主节点，而所有写入都必须经由主节点。如果由于某种原因，例如与主节点之间的网络中断而导致主节点无法连接，主从复制方案就会影响所有的写入操作。
我们可以配置多个主节点，然后后面的复制流程和主从复制类似。处理写的每个主节点都必须将数据更改转发到所有其他节点。每个主节点同时也扮演其他主节点的从节点。
适用场景
多个数据中心
每个数据中心可以配置一个主节点，在数据中心内部实行主从复制方案，在数据中心之间，各个数据中心的主节点来负责同其他数据中心的主节点进行数据的交换更新。
多数据中心时多主节点相对单主节点主从复制的好处：
- 性能：主从复制，需要跨数据中心访问主节点，会有比较高的写入延迟，在多主节点中，每个写都能在当前数据中心的主节点响应，并且异步复制到其他数据中心，对于客户而言屏蔽了延迟。
- 容忍数据中心失效：每个数据中心都可以独立运行，但是主从复制的话主节点的数据中心出了问题就要切换到另一个数据中心。
- 容忍网络问题：数据中心之间的通信经由广域网没有数据中心内部的本地网络可靠。
离线客户端操作
应用与网络断开依旧可以进行工作。比如手机电脑上面的日历功能，每个设备都认为是一个充当主节点的本地数据库。
协作编辑
比如腾讯文档之类的，多人同时编辑，很像数据库复制问题，但是二者有很多相似之处，当一个用户编辑文档时所做的更改会立即应用到本地副本，然后异步复制到服务器以及编辑同一文档的其他用户。
如果为了确保不会发生编辑冲突，可以用粒度比较小的锁。
处理写冲突
避免冲突
处理冲突最理想的策略是避免发生冲突，比如应用层可以保证对特定记录的写请求总是通过同一个主节点，这样就不会发生写冲突。
收敛于一致性状态
在主从复制模型中，数据更新符合顺序性原则，如果同一个字段有多个更新，则最后一个写操作将决定该字段的最终值，由于多主节点复制模型里面，不存在这样的写入顺序，所以最终值会变得不确定。
所有的复制模型至少应该确保数据在所有副本中最终状态一定是一致的。数据库必须以一种收敛趋同的方式来解决冲突，意味着所有更改最终被复制同步之后所有版本的最终值是相同的。
实现收敛的冲突解决有以下可能的方式：
- 给每个写入分配唯一的ID，例如一个时间戳或一个UUID，挑选最高ID的写入作为胜利者，并将其他写入丢弃。（如果基于时间戳，这项技术称为最后写入者获胜）
- 为每个副本分配一个唯一ID，并制定规则，例如序号高的副本优先级高
- 以某种方式将这些值合并拼接。
- 利用预定义好的格式来记录和保留冲突相关的所有信息，然后依靠应用层的逻辑事后解决冲突（提示用户）
自定义冲突解决逻辑
依靠应用层自己定义解决冲突的逻辑
- 在写入时执行
- 在读取时执行
拓扑结构
环形结构：为了防止无限循环，每个节点需要一个唯一的标识符，在复制日志中每个写请求都标记了已通过的节点标识符，如果某个节点收到包含自身标识符的数据更改，就说明这个请求已经被处理过，因此会忽略此变更请求避免重复转发。
环形和星型拓扑如果某节点发生故障会影响其他节点之间复制日志的转发。
全链接的问题，由于链路网络速度差异，会导致复制日志之间的覆盖。
无主节点复制
一些数据存储系统采用了不同的设计思路：选择放弃主节点，允许任何副本直接接受来自客户端的写请求。
- 读修复：客户端并行读取多个副本，可以检测过期的返回值并且将新值写入该副本。
- 反熵：后台进程不断查找副本之间数据的差异，将任何缺少的数据从一个副本复制到另一个副本。
读写quorum
如果有n个副本，写入需要w个节点确认，读取必须至少查询r个节点。则只要w+r>n，读取的节点中一定会包含最新值。（因为成功写入集合和成功读取集合必然有重合）
在Dynamo风格的数据库中，这三个参数是可以自己配置。例如对于读多写少的负载，设置w=n和r=1比较合适，这样读取速度更快。
宽松的quorum
在一个大型集群中（节点数远大于n个），客户可能在网络中断期间连接到某个数据库节点，但这些节点又不是能够满足数据仲裁的那些节点。此时可以接受该写请求，只是暂时写入一些可访问的节点中（然后当网络恢复了再将这些写入发送到原始主节点上）
检测并发写
最后写入者获胜（丢弃并发写入）
一种实现方式是每个副本总是保存最新值，允许覆盖并丢弃旧值。
- 但是如何定义最新？
即使无法确定写请求的“自然顺序”，但是也可以强制对其排序，例如为每个写请求附加一个时间戳，然后选择最新即最大的时间戳，丢弃较早时间戳的写入(last write wins, LWW)
但是这种做法是牺牲了数据持久性，实现最终收敛的目标。
Happens-before关系和并发
- 如何判断两个操作是否并发？
如果两个操作A和B，B知道A或者B依赖A，或者B是以某种方式在A的基础上构建，则称操作A在操作B之前发生。这是定义并发的关键。可以简单的说，两个操作都不在另一个之前发生，我们认为这两个操作是并发的。
例如这个场景
数据#
箭头表示某个操作发生在另一个操作之前，即后面的操作“知道”或是“依赖”于前面的操作。
服务器判断是否并发的算法：
- 服务器为每个主键维护一个版本号，每当主键写入时递增版本号，并将新版本号与写入的值一起保存。
- 当客户端读取主键时，服务器将所有（未被覆盖的）当前值以及最新的版本号返回。且要求写之前，客户必须先发送读请求。
- 客户端写主键，写请求必须包含之前读到的版本号，读到的值和新值合并后的集合。写请求的相应也和读请求的响应一样。
- 当服务器收到带有特定版本号的写入时，覆盖该版本号或更低版本的所有值（因为知道这些值已经被合并到新传入值集合中），但必须保存更高版本号的所有值（因为这些值与当前的写操作属于并发）
合并同时写入的值
如果多个操作同时发生，客户端需要通过合并并发写入的值来继承旧值。risk称这些并发值为兄弟关系。
购物车这个例子合并方式是union，但是可能会丢掉重复值。
然后如果要是支持删除操作，不能在数据库里面简单的删除，如果合并两个客户端的值，被其中一个客户端删除的值可能会再次出现，系统必须保留一个对应的版本号以恰当的标记该项目需要在合并时被删除。这种删除标记称之为墓碑。
版本矢量
之前购物车的例子只有一个副本，如果有多个副本的时候需要对每个副本的每个主键均定义一个版本号。通过这些信息来指示要覆盖哪些值，该保留哪些并发值。所有副本的版本号集合称之为版本矢量。