第二部分：分布式数据系统

第五章、数据复制

通过网络在多台机器上保存相同的副本。

• 多副本的目的

1. 使数据在地理位置上更接近用户，从而降低访问延迟。（CDN）
2. 当部分组件出现故障，系统依然可以继续工作，从而提高可用性。（高可用，主从）
3. 扩展至多台机器以同时提供数据访问服务，从而提高读吞吐量。（负载均衡，分布式）

主从复制

1. 指定某一个副本为主副本 （或称为主节点）。当客户写数据库时，必须将写请求首先发送给主副本，主副本首先将新数据写入本地存储。
2. 其他副本则全部称为从副本（或称为从节点）。主副本把新数据写入本地存 储后，然后将数据更改作为复制的日志或更改流发送给所有从副本。每个从副本 获得更改日志之后将其应用到本地，且严格保持与主副本相同的写入顺序。
3. 客户端从数据库中读数据时，可以在主副本或者从副本上执行查询。再次强调， 只有主副本才可以接受写请求;从客户端的角度来看，从副本都是只读的。

同步和异步

同步和异步的区别在于主节点是否需要等待从节点返回成功后才算成功。

• 同步的优点：从节点的数据是完整的，从节点随时可以作为一个可靠的节点来读取数据或者替换主节点。

• 同步的缺点：虽然节点之间复制速度特别快，但只要从节点的一环出现错误，就会导致任务失败。如果同步的从节点过多，会让故障的概率指数级增加。

• 半同步：一个主节点，一个同步从节点，多个异步的从节点。如果同步的从节点出现问题，则将一个异步的从节点升级成为同步从节点。主节点出现问题，用同步从节点替换主节点。

配置新的从节点

当添加新的从节点后，如何保证新从节点和主节点之间数据的一致性。

• 如何在不停机的情况下，保证新节点的数据追平主节点（逻辑同样可以用来做数据库迁移）

1. 在某个时间点，对主节点产出一个数据一致性快照，这样可以避免长时间锁定数据库。（MySQL的innobackupex）
2. 将此快照拷贝到新的从节点。
3. 从节点连接主节点并只请求快照点后所发生的数据修改日志（binlog）。
4. 获取日之后，从节点追平主节点数据。

处理失效的节点

即使某个节点中断，也要保证系统总体的持续运行。高可用

• 从节点失效：追赶恢复数据

根据从节点数据日志情况，与主从复制日志情况，进行数据追赶。

• 主节点失效：节点切换

需要将某个从节点提升为主节点，同时客户端更新到新的主节点

1. 确认主节点确实已失效。
2. 确认新的主节点。可能需要多数节点达成共识，或者手动选择最接近主节点数据的从节点。让所有从节点同意新的主节点。
3. 配置应用使用新的主节点。（写请求都到新的主节点）确保旧主节点已降级成从节点，且同意新的主节点。

主从切换时可能出现的一些问题：

• 异步复制，新的主节点可能没有收到所有旧主节点的数据；选举后，旧主节点又很快上线，出现旧主节点（现在的从节点）数据超过新主节点。

旧主节点未完成复制的数据丢弃掉。（会导致一部分数据丢失，违背数据持久化概念）所以应该尽量保证主节点提交的数据可以被全量同步。

如果程序依赖数据库的数据来生成主键，将直接导致业务系统出现问题。所以最好还是要保证有同步数据库。

• 超时时间设计的过短：可能导致不必要的主从切换。

应该尽量保持平衡，但其实也没有一个固定的解决方案。所以有些系统为了保证可靠，主从切换还是由运维手动操作。

复制日志的实现

• 基于语句的复制

主节点把所有写请求，都当做日志发送给从节点。（aof和增量binlog）

1. 任何非确定性的函数调用（now，随机数等）
2. 如何使用了自增id，必须保证所有库的自增键相同

可以把主节点执行后的结果当成转换成写语句同步给从库。

• 基于预写日志（WAL）传输

多数数据库都是基于WAL来做数据更新的，完全可以利用WAL，来向从库同步WAL，这样可以做到相同的写入操作。

1. WAL受限于存储引擎，如果不同的存储引擎（和版本号），采用的WAL将完全不同。（无法实现热升级，如果需要升级数据库版本，需要停机）

• 基于行的逻辑日志复制

通过自定义的逻辑日志来进行复制

新增：日志包含所有相关的列新值

删除：通过唯一标识来生成删除日志。

更新：通过唯一标识和需要更新的新列值来生成更新日志。

• 基于触发器的复制

不使用数据库本身，通过第三方工具（触发器）来实现复制。（canel：思想相同，不过实现采用的伪装成数据库从库）

Oracle的Databus、Postgres的Bucardo

1. 通常开销更高，也容易出错，但非常灵活。

复制滞后问题

主从复制要求所有写请求都经由主节点，而任何副本只能接受只读查询。如果一个应用正好从一个异步的从节点读取数据，而该副本落后于主节 点， 则应用可能会读到过期的信息。如果同时向主节点和从节点发起查询请求，可能会查到不同的值。

主要涉及讨论对于各种复制滞后的问题应该如何解决

读取自己写入的数据（读写请求一致性）

用户提交一些信息，然后查看自己刚刚提交的内容。由于主从复制滞后问题导致读取的内容不一致。

读写请求一致性：如果用户重新加载页面，总是能看到自己最近提交的更新。（其他用户读取此信息不保证最新）下面是几种实现方式

• 总是从主节点读取自己的配置信息，对于他人的配置信息从从节点读取。
• 跟踪用户的更新请求，如果最近一分钟提交了更新操作，则从主库读取，否则从库。
• 客户端本地记录最后一次更新的时间戳，保证查询的信息至少晚于或等于本地记录的时间戳。（这些请求不一定是从主库查询的，可以在多个从库之间轮询，直到查到满足条件的信息）可能由于不可靠的时钟出错
• 如果有多个数据中心，必须把用户请求路由到主节点所在的数据中心

单调读（读一致性）

第一次读取的数据与第二次读取的数据不同。比强一致性弱，比最终一致性强的保证

如果某个用户依次进行多 次读取，则他绝不会看到回滚现象，即在读取较新值之后又发生读旧值的情况。

• 确保同一个用户每次都从同一个副本查询，而不是每次请求都随机路由。（但如果被路由的节点失效，失效节点的所有用户都要重新分配）

前缀一致性读（happened-before）

对于存在因果关系的数据，必须要严格按照顺序复制。有点类似于 JIT 需要保证乱序生成的代码，单线程结果一致性。（有序性）

微信聊天记录就存在这样的问题，产生这个情况的原因通常是：分布式写请求分片有多个，不能保证全集群写入顺序的一致。就会导致从分片读到完全乱序的情况。

• 所有具有因果关系的写请求都交给同一个分片来完成。（这样做效率会大打折扣）
• 可以使用一些happened-before算法来追踪因果关系。

多主节点复制

每个节点既扮演主节点，也同时扮演者其他主节点的从节点角色。

适用场景

多主模式逻辑复杂，在同一个数据中心内部使用没有意义，通过在多数据中心场景中使用。

• 多数据中心

为了容忍数据中心级别的故障，或者更接近用户，可以把数据库的副本横跨多个数据中心。

主从和多主之间的对比

多主模式同样也带来了许多问题：

1. 不同的数据中心可能会同时修改相同的数据，因而必须解决潜在的写冲突。
2. 自增id问题：可能由于同步的不及时导致每个数据中心之间，相同数据自增id不同。（多数据中心不建议使用自增id）

• 离线客户端操作

应用在与网络断开后还需要继续工作

每个设备都有一个充当主节点的本地数据库（用来接受写请求）。

• 协作编辑

实时协作编辑应用程序允许多个用户同时编辑文档。（在线文档）

当一个用户编辑文档时 ，所做的更改会立即应用到本地副本，然后异步复制到服务器以及编辑同一文档的其他用户。

处理写冲突

• 如何避免冲突

通过应用层来指定特定记录的写请求总是通过同一个主节点，这样就不会发生冲突。（有点违背多主模式的冲突，变成了主从模式的变种）

• 收敛于一致状态

数据更新符合顺序性原则，即如果同一个字段有多个更新，则最后一个写操作将决定该字段的最终值。（可能会导致最终值的不确定性）

如何实现收敛一致

1. 最大id：所有写请求分配一个唯一的id（时间戳+uuid）所有数据同步时，只保留id最大的数据（最终一致）
2. 合并一致：让需合并的结果按照一定规则排序，只取序列最靠后的。
3. 同2，应用自定义合并规则。

一些常见的自动解决并发修改冲突算法

1. 无冲突的复制数据类型（ CRDT）：多个用户同时编写map、list等。
2. 可合并的持久数据结构（Mergeable persistent data) ：类似git跟踪变更历史，三向合并。
3. 操作转换（Operational transformation）：Etherpad和Google Docs等协作编辑应用背后的冲突解决算法。

复制的拓扑结构

不同拓扑结构对于容错、是否有中心、复制成本各有优缺点，这里就不展开说明了。

无主节点复制

放弃主节点，允许任何副本直接接受来自客户端的写请求。

节点失效时写入数据库

当节点失效时，用户不关心自己写入的节点是否发生变化，更不需要进行节点提权等操作。

用户向多个节点同时发起写请求，只有超过半数的节点写入成功，则此请求成功。

• 读修复：用户读取时决定值（通过半数以上的节点返回来确认值）
• 反熵：后台进程自动查找节点之间的差异并修复。

但上面的例子，如果有多个用户同时写入则可能出现如下问题：

处理并发写入

• 最后写入胜利法（last write wins）

由于每个客户端在写入时都不会互相感知，且由于网络关系，无法区分那个写入一定在哪个写入之后。

可以强制对所有的写入进行排序：

为所有写请求附加一个时间戳，然后选择最新即最大的时间戳，丢弃较早时间戳的写入。

以上思想，在zookeeper，raft，各种分布式一致性问题中都有借鉴。

• happens-before关系和并发

happens-before：B的操作明确依赖A，具有先后关系

并发：A和B的操作“同时”，且完全独立的，互相不感知

为更好地定义并发性，我们并不依赖确切的发生时间，即不管物理的时机如何，如果两个操作并不需要意识到对方，我们即可声称它们是并发操作。

两个客户端同时多次向一个购物车中添加值，且相互不感知。

对于单个客户端，每次添加操作是有前后依赖关系的（happened-before），对于两个客户端之间，是“同时”发起的添加操作（并发）

服务器具体处理步骤如下：

1. 服务器为每个主键维护一个版本号，当主键新值写入时，递增版本号，并将版本号和值一起保存。
2. 当客户端读取主键时，服务器将返回所有（未被覆盖的）当前值以及最新的版本号。且要求写之前， 客户必须先发送读请求。（读取最新值）
3. 客户端写主键，写请求必须包含之前读到的版本号、读到的值和新值合并后的集合。写请求的响应可以像读操作一样，会返回所有当前值，这样就可以像购物车例子那样一步步链接起多个写入的值。
4. 当服务器收到带有特定版本号的写入时，覆盖该版本号或更低版本的所有值（因为知道这些值已经被合并到新传入的值集合中），但必须保存更高版本号的所有值（因为这些值与当前的写操作属于并发）。

整体逻辑有点像kafka集群的值是否写入成功逻辑，如果同步指针追上了的值，才算写入成功。这里只不过是相反的，每次写入都删除当前写入依赖版本号之前的所有版本。（算是MVCC的一种体现）

有依赖关系的值可以覆盖，并发的值需保存多份。可以保证并发写入的数据不会丢失

第六章、数据分区

分区通常与复制结合使用，即每个分区在多个节点都存有副本。这意味着某条记录属于特定的分区 ，而同样的内容会保存在不同的节点上以提高系统的容错性。

键-值数据的分区（常见的分区方式）

分区的主要目标是将数据和查询负载均匀分布在所有节点上。如果节点平均分担负载，那么理论上10个节点应该能够处理10倍的数据量10倍于单个节点的读写吞吐量。

基于关键字分区

为每个分区分配一段连续的关键字或者关键字区间范围。

每个分区可以按照关键字排序保存（LSM-Trees）。这样可以轻松的支持区间查询。

缺点：某些访问模式会导致热点。如果数据按照每天一个分区，每天所有的写入都会在同一个分区，会导致单个分区负载过高，其他分区一直处于空闲状态。

基于关键字hash值进行分区

一个好的hash函数可以处理数据倾斜并使其均匀分布。

基于一致性hash的分区方式，可以进行高效的查询，但是却使数据丧失了有序性。

有些数据库采用hash分区的数据库直接禁用范围查询、或者把查询语句发送到所有的分区上。

• Cassandra的折中方案

声明一个由多列组成的符合主键。多列主键的第一部分用于hash分区，其他列用于对sstable的排序。（可以支持对于其他部分的区间查询）

负载倾斜和热点

基于hash的方法可以减轻热点，但无法做到完全避免热点。一个极端的情况是所有的读/写操作都针对同一个关键字，最终所有的请求都会被路由到同一个分区。

在社交媒体网站上，一个名人发布了热点事件，出现了大量相同关键字的写操作。此时hash起不到任何帮助，相同id的hash值相同。

• 一种无奈的解决方案

如果某个关键字被认定为热点，就在关键字的开头或者结尾添加一个随机数。只需一个两位数的十进制随机数就可以将关键字的写操作分布到 100 个不同的关键字上，从而分配到不同的分区上。

缺点：但之后所有的读操作都需要额外的工作，必须从所有100个关键字中读取数据然后进行合并。因此通常只对少量关键字做随机数才有意义。

分区和二级索引

二级索引通常不能唯一标记一条数据，而是用来加速特定值的查询。

二级索引不能规整的映射到分区中。

基于文档分区的二级索引

每个分区完全独立，各自维护自己的二级索引，且只负责自己分区内的文档而不关心其他分区中的数据。文档分区索引也被称为本地索引，而不是全局索引。

• 二级索引的查询

如果想要查询特定颜色的车使用二级索引，需要将查询发送的所有的分区，然后合并所有返回结果。（可以采用并行查询）

基于词条的二级索引分区

对所有的数据构建全局索引，而不是每个分区维护自己的本地索引。为了避免成为瓶颈，不能将全局索引存储在一个节点上，否则就破坏了设计分区均衡的目标。全局索引也必须进行分区，且可以使用与数据关键字不同的分区策略。

优点：查询足够高效，且不需要把查询分配给所有分区然后聚合，客户只需要向包含词条的分区发送读请求。

缺点：写入速度较慢且非常复杂，单个文档更新时，里面可能会涉及多个二级索引，二级索引的分区又可能完全不同甚至完全在不同的节点上，会引入显著的写放大。

由于二级索更新需要一个跨多个相关分区的分布式事务支持，写入速度极慢。因此大部分数据库都不支持同步更新二级索引。对全局二级索引的更新往往是异步的。

分区再平衡

当增加节点时，如何将之前的数据进行再平衡。

• 分区再平衡想要达到的效果

1. 平衡之后，负载、数据存储、读写请求等应该在集群范围更均匀地分布。
2. 再平衡执行过程中，数据库应该可继续正常提供读写服务。
3. 避免不必要的负载迁移，以加快动态再平衡，并尽量减少网络和磁盘IO影响。

动态再平衡策略

• 为什么不推荐使用取模

如果频繁的增加节点，会导致大量的数据频繁的迁移，大大增加了再平衡的成本。

• 固定数量的分区

1. 创建远超实际节点数的分区数，然后为每个节点分配多个分区。
2. 如果集群中增加了一个新节点，该新节点可以从每个分区上匀走几个分区，直到分区再次达到全局平衡。
3. 被选中的整个分区会在映射节点之间迁移，但分区的总数量仍然维持不变，也不会改变关键字到分区的映射关系。（不需要像取模一样对每个key重新计算分区值）
4. 唯一需要调整的是分区与节点的对应关系。调整可以逐步动态完成。在此期间，旧的分区仍然可以接收读取请求。

• 动态分区

当一个分区的数据量增长超过一个阈值，就会被拆分成两个分区，每个承担一半数据量。

如果大量数据被删除，且分区缩小到某个阈值，则将其相邻的分区合并。

HBase 通过HDFS分布式文件系统来实现分区文件的传输

• 按节点比例分区

使分区数与集群节点数量成正比，每个节点都有固定数量的分区。当节点数不变，每个分区的大小与数据集大小保持正比的增长关系；当节点数量增加，分区则会变小。大量的数据需要大量的节点来存储，这种方式可以使每个分区大小保持稳定。

请求路由

当客户端发送请求时，如何知道应该连接哪个节点？其实就是一个服务发现问题。

几种常见的路由策略

1. 客户端连接任意节点，有节点把这个请求转发到正确的节点，再返回给客户端。（redis）
2. 将所有客户端的请求都发送到一个路由层，路由层负责把请求转发到对应的分区节点上。路由层本身不处理请求，只负责负载均衡。（nginx）
3. 客户端感知分区和节点关系。客户端可以直接连接到目标节点，而不需要其他中介。（springcloud注册中心的做法）

做出路由的组件，需要知道分区和节点的关系，以及变化情况。

大部分数据系统通过zookeeper来维护分区和节点的映射关系。一旦分区发生变化，zookeeper主动通知路由层来保持最新状态。

关于IP地址的变化，可以借助机器自己的DNS就可以了。

并行查询执行

查询优化器会把复杂的查询分解成许多执行阶段和分区，以便在集群的不同节点上并行执行。尤其是涉及全表扫描的查询操作，可以通过并行执行获益颇多。

第七章、事务

深入理解事务

ACID的含义

我之前多次记录过关于ACID的文章，对于ACID等详细说明推荐看我在凤凰架构里记录的文章。

不符合ACID的系统被称为BASE，基本可用（Basically Available），软状态（Soft state）和最终 一致性（Eventual consistency)。

原子性

多线程编程中，如果某线程执行了原子操作，这意味着其他线程是无法看到该操作的中间结果。只能处于操作前和操作后的状态，而不是两者之间。

在ACID中，多线程访问相同变量是由隔离性来保证的

ACID的原子性：在出错时中止事务，并将部分完成的写入全部丢弃。（可随意中止性，从而达到可重试的目的。）

一致性

ACID的一致性：对数据有特定的预期状态，任何数据更改必须满足这些状态约束（或者恒等条件）。（贷款系统中，贷款余额应和借款余额保持平衡。）

原子性，隔离性和持久性是数据库自身的属性，而ACID 中的一致性更多是应用层的属性。

应用程序可能借助数据库提供的原子性和隔离性，以达到一致性，但一致性本身并不拥于数据库。

字母C其实并不应该属于ACID

隔离性

ACID的隔离性：并发执行的多个事务相互隔离，它们不能互相交叉。

相互交叉其实有两个表现，下面是mysql对于两个场景的措施

1. 读取：查询到其他事务可能在使用的变量。（通过MVCC快照读这种弱隔离性来实现）
2. 修改：修改相同的变量（通过锁机制，保证一个变量无法被两个线程修改）

持久性

对于单机程序，持久性表示数据已经写入了非易失的存储设备（如硬盘）

对于支持远程复制的数据库，持久性意味着数据已成功复制到多个节点。

数据库必须等到这些写入或者复制完成之后才能报告事务成功提交。

弱隔离级别

关于mysql不同隔离级别的实现，已经不同级别的锁实现可以看我的这篇文章。

隔离是假装没有发生并发，可串行化隔离意味着数据库保证事务的最终执行结果与串行执行结果相同。

可串行化会严重影响性能，而许多数据库却不愿意牺牲性能，因此更多倾向于采用较弱的隔离级别。它可以防止某些但并非全部的并发问题。

读-提交

1. 读数据库时，只能看到已成功提交的数据（防止脏读）
2. 写数据库时，只会覆盖已成功提交的数据（防止脏写）

• 防止脏读

脏读：一个事务看到另一个事务尚未提交的内容。

如果事务需要更新多个对象，脏读意味着另一个事务可能会看到部分更新，而非全部。

如果事务发生中止，则所有写入操作都需要回滚。

• 防止脏写

脏写：两个事务同时修改相同的值，一个事务把另一个事务未提交的值修改了。

读已提交解决脏写的方式是一个事务等待另一个事务提交后，才能修改另一个事务已经修改了的值。（利用锁）

如果事务需要更新多个对象，脏写会带来非预期的错误结果。

多事务的不同写入顺序导致结果不一致。

• 实现读-提交

防止脏写：

数据库通常采用行级锁来防止脏写：当事务想修改某个对象（例如行或文档）时，它必须首先获得该对象的锁；然后一直持有锁直到事务提交（或中止）。如果有另一个事务尝试更新同一个对象，则必须等待。

防止脏读：

不能利用锁来解决脏读，因为长时间的写事务会导致许多只读的事务等待太长时间，任何局部的写入都会扩散进而影响整个应用。

对于每个待更新的对象，数据库都会维护其旧值和当前持锁事务将要设置的新值两个版本。在事务提交之前，所有其他读操作都读取旧值；仅当写事务提交之后，才会切换到读取新值。

快照级别隔离与可重复读

表面上看读已提交已经满足事务的几个特征：

1. 支持中止（原子性）
2. 可防止读取不完整的结果（undo log）
3. 防止并发写（锁）

读倾斜：导致数据库中的数据不一致

对于Alice来说，只看到自己两个账户中一共只有900块

• 实现快照级别隔离

快照级别隔离：每个事务从数据库中的一致性快照读取，事务一开始看到的是最近提交的事务，即使数据被另一个事务更改，但保证每个事务都只看到该特定时间点的旧数据。

因为可能存在多个事务在不同的时间点查看数据库，所以数据库需要保留多个不同的提交版本，这种技术被称为：多版本并发控制MVCC

表中的每行都有一个created_by字段，包含了创建该行的事务ID，deleted_by记录删除了该行的事务ID。（仅仅标记为删除）。当确定没有其他事务引用该标记删除行后，数据库垃圾回收线程才会真正回收此行。

• 一致性快照的可见性

1. 每笔事务开始时，数据库会列出还在进行中的其他事务，这些事务涉及的行不可见。
2. 所有中止事务修改的行全部不可见。
3. 较晚事务所做的任何修改都不可见，不管这些事务是否完成了提交。
4. 所有其他的数据都可见。

• 索引和快照隔离级别

快照隔离级别如何支持索引

mysql，pgsql把同一个对象的不同版本放在一个内存页面上。

其他采用b-tree的数据库，使用写时复制技术，数据更新时，创建一个新的修改副本，然后让父节点执行新创建的节点。（copy on write）

• 可重复读情况下防止更新丢失

如果一个事务操作，是先查询，然后根据查询出的结果做修改。这中间gap的时间就可能会有另一个事务修改此值。而最后的写入会导致中间事务操作丢失。（更新丢失）

1. 原子写(最推荐）：

   更新操作和查询操作一起完成。（利用事务的游标稳定性，强制对对象加独占锁）

   1	UPDATE counters SET value = value + 1 WHERE key ＝’f00’；

2. 显示加锁：

   在操作前，先对对象加锁，但可能会导致冲突。

3. 自动检测更新丢失： 有些数据库（oracle、pgsql）可以支持自动检测是否出现更新丢失，从而中止违规操作。如果数据库不支持防止更新丢失，就说明数据库不完全支持快照隔离级别。（mysql没有完全支持快照隔离级别）

4. 原子比较和设置：

   对于不支持事务的数据库，可以使写操作必须包含即将修改的原始值的方式来进行写入，这样可以保证不出现更新丢失。

   1 2	UPDATE wiki_pages SET content =’ new content ’ WHERE id = 1234 AND content =’ old content ’;

写倾斜和幻读

两个事务更新两个不同的对象，但由于两个对象之间其实存在逻辑依赖关系。（如只有当A为1时，才能更新B）此时，在快照隔离级别下，就会导致程序出错。

目前所有的可重复读，快照隔离级别的数据库，都不支持检测写倾斜问题，自动防止写倾斜需要真正的可串行化隔离。

• 可利用手动加锁来部分解决写倾斜

1
2
3
4
5
6
7
8
9

BEGIN TRANSACTION; 
SELECT * FROM doctors
WHERE on_call=true 
AND shift_id =1234 FOR UPDATE;  
UPDATE doctors 
SET on_call=false 
WHERE name =’Alice’ 
AND shift_id =1234; 
COMMIT;

• 幻读或写倾斜产生的原因

在执行写入操作之前，需要先进行一次select查询，且本次写操作后，会影响到第一次查询的结果。这种场景就会产生幻读问题。（一个事务的写入影响到了另一个事务的查询结果）

对于幻读，看似好像可以通过手动加锁来解决，但示例中只是写入依赖一个条件的情况。如果一个写入需要依赖数据库所有数据，这时锁定整个数据库（相当于变成了可串行化）才能成功。这显然是不显示的。

快照隔离级别，可以避免只读查询的幻读，但对于读写事务，它无法解决写倾斜。

串行化

可串行化通常被认为是最强的隔离级别。保证即使事务可能会并行执行，但最终的结果与每次一个串行执行结果相同。如果事务在单独运行时表现正确，那么它在并发运行时结果仍然正确。

接下来就讨论目前市面上实现可串行化的常用三种技术手段

实际串行执行（严格串行化）

一个线程上按顺序每次只执行一个事务，这样可以完全回避检测、防止事务冲突，严格串行化。

老版本单线程redis通常采用这种方式执行。

单线程执行有时可能比并发执行效率更高，但其吞吐量上线是单个CPU核的吞吐量。下面介绍常见的单线成优化方式：

• 采用存储过程封装事务

传统事务交互方式给单线程事务带来的阻碍：

传统事务往往是交互式的，如用户输入一条指令，数据库做出反应，然后用户根据结果在执行下一条指令。这种交互会极大的拖长数据库的空白时间，在可并发事务中尚能容忍，但在单线程事务中，这就是致命的。

web应用为了避免事务跨请求，往往一个http请求代表一次事务。但一个http请求中的多条语句，还是一条一条的提供给数据库的。如果服务与数据库网络延迟极高，这在单线程事务中仍然是致命的。

由于以上原因，单线程事务往往不支持交互式的多语句事务。应用程序必须把整个事务代码作为存储过程打包发送到数据库。数据库把所有需要的数据加载到内存，使整个存储过程高效执行。

• 存储过程的优缺点

老版本的存储过程语言低效，开发效率低，难度高，可维护性差。如果存储过程算法不好，会占用大量的CPU时间，数据库是公共资源，这比单个服务执行效率低带来的影响要大得多。

（Lua就是redis的存储过程语言）

VoltDB利用存储过程来实现复制，不是将事务执行结果从一个节点复制到另一个节点，而是在每个副本上执行相同的存储过程。这样可以实现在每个节点上都能看到完整的历史信息。相当于真正意义上的镜像。

这样依赖存储过程的复制，需对特定API做出修改，如获取当前时间等）

• 分区

单线程事务，在高写入场景下，往往单核性能会成为吞吐量的瓶颈。

通过一个方法对数据集进行分区，使得每个事务只在单个分区内读写数据，这样可以让每个分区分配一个CPU，这样可以让数据库的吞吐量与分配的CPU核数成线性相关。

但如果出现跨分区事务，数据库需要对多个分区进行加锁，这种执行效率要远远低于单个分区执行。（且无法通过增加机器来扩展性能）

• 哪些事务可以使用串行化执行：

1. 事务必须简短且高效，否则一个慢事务会影响到所有其他的事务。
2. 事务所需的数据可以完全加载对内存的场景。
3. 写入吞吐量必须足够低，才能在单个CPU上执行。
4. 跨分区事务必须很小。

两阶段加锁（2PL)

近30年来，数据库唯一被广泛使用的可串行化算法

2PL两阶段加锁听起来和两阶段提交（2PC）很像，但是是完全不同的两个东西。两阶段提交很垃圾，两阶段加锁很棒。

多个事务可以同时读取同一个对象，但只要出现任何写操作，则必须加独占锁访问：

1. 如果事务A已经读取了某个对象，此时事务B想要写入该对象，事务B必须等待事务A提交或中止事务，以确保B不会被A执行过程所影响。
2. 如果事务A已经修改了某个对象，此时事务B想要读取该对象，B必须等待A提交或中止后才能读取。（对于2PL，不存在读取到旧值的情况）

所以2PL不仅在并发写入之间互斥，读取和修改也会产生互斥。

• 实现两阶段加锁

目前2PL已经在mysql和sqlserver的可串行化，以及DB2的可重复读中实现。

1. 如果事务要读取对象 ，必须先以共享模式获得锁。可以有多个事务同时获得一个对象的共享锁，但是如果某个事务已经获得了对象的独占锁，则所有其他事务必须等待。
2. 如果事务要修改对象，必须以独占模式获取锁。不允许多个事务同时持有该锁（包括共享或独占模式），换言之，如果对象上已被加锁， 则修改事务必须等待。
3. 如果事务首先读取对象，然后尝试写入对象，则需要将共享锁升级为独占锁。升级锁的流程等价于直接获得独占锁。
4. 事务获得锁之后， 一直持有锁直到事务结束（包括提交或中止）。这也是名字“两阶段”的来由，在第一阶段即事务执行之前要获取锁，第二阶段（即事务结束时）释放锁。

由于数据库中锁很多，所以很容易产生死锁，数据库会自动检测事务之间的死锁，并强行中止其中一个。

• 两阶段加锁的性能

一旦出现出现多个事务访问同一个对象，会形成一个等待队列，事务必须等待前面的事务操作完成。

每次事务操作都需要加锁，不同数据库上锁成本各不相同。

如果出现死锁，其中一个事务必须中止，这意味着应用程序要能够支持从头重试。

• 谓词锁（条件锁）

只有有了谓词锁，两阶段加锁才能实现所谓的可串行化隔离

为了解决幻读问题，有时事务需要对满足某个条件的所有对象加锁，本次加锁不一定只加锁到现有对象，同时也保证其他事务的写入也不会产生满足这个条件的对象。

与其说谓词锁是对某个对象加锁，不如说谓词锁是锁定的某个条件，保证所有满足这个条件的对象不会新增、删除或修改。

如果某个事务查询对象时，查询的条件满足其他事务的修改条件，则查询事务必须等待写入事务结束。

• 索引区间锁（next-key lock）

谓词锁的性能不佳，如果同时存在多个事务，每次匹配这些事务的所有谓词条件变得非常耗时。所以大多数数据库都采用索引区间锁（next-key lock）来实现2PL。

next-key lock往往使用将锁扩大化的方式来实现。

如在数据库的末尾插入一条数据，则会锁定所有大于目前末尾值之后的数据。

但索引区间锁如名字一样，必须对某个索引来上锁，如果写操作没有索引，则可能会对整个表加锁。

可串行化的快照隔离（SSI）乐观并发控制

2008年首次提出的新可串行化实现算法。pgsql9.1之后采用类似此方式来实现串行化。

前面的两个方式，都是一种悲观锁的方式，如果数据可能会被其他事务影响，就对数据上锁。可串行化的快照隔离SSI采用乐观锁的方式：

如果可能发生潜在冲突，事务会继续执行而不是中止，希望一些都安然无事，当事务提交时，数据库再检查是否发生了冲突。（这里违反了隔离性原则），如果发生冲突，就中止事务并重试。

乐观锁机制如果冲突很多，则性能很差，会产生大量的重试，如果没有冲突，则运行非常高效。（现代JVM和计算机等上锁成本变的越来越小，所以乐观锁使用的也越来越少。）

实现方式：

• 检测是否读取了过期的MVCC对象

两个事务，查询了相同的变量，其中一个事务提交，会让另一个事务中止。

1. 为什么要在提交时才会让另一个事务中止？

   因为每个事务开始时，不一定会执行写入操作，如果在查询时就不允许进行相同的查询，这样会导致大量的事务无限回滚。且查询操作如果 查询到快照值，也不会影响到本次查询（因为此时修改的事务可能还没有提交）。

• 性能如何？

SSI需要非常详细的追踪每个事务的操作，虽然需要大量的性能，但对比两阶段加锁，可以做到让锁的粒度非常小（只影响实际有干扰的值）大大减小了事务回滚的几率。

且可串行化的快照隔离没有锁，可以突破单个CPU的限制。让所有的查询延迟可控（不会一直阻塞等待锁）。

SSI最重要的是可以接收那些运行缓慢的事务。

总结

事务的作用：事务是一个抽象层，让应用程序可以忽略数据库内部的复杂并发问题和故障，从而简化应用层的处理逻辑，把大量的错误转换成事务中止和应用重试。

脏读：客户端读到了其他客户端尚未提交的写入。大于等于读-提交的隔离级别可以防止脏读。

脏写：客户端覆盖了另一个客户端尚未提交的写入。（几乎所有的数据库都可以防止脏写）

读倾斜（不可重复读）：客户在不同的时间看到了不同的值。快照隔离是最常用的防范手段，事务总是读取某个时间点的一致性快照。通常采用MVCC来实现。由于全量多复制，或者通过修改树的祖父节点方式来实现。

更新丢失：两个客户端同时执行 读-修改-写入操作，出现其中一个覆盖了另一个的写入，但又没有包含对方最新值的情况，最终导致部分修改数据发生了丢失。有些快照隔离级别实现会检测更新丢失，（如pgsql，oracle。）但像mysql这样的快照隔离级别需手动上锁，select for update。

写倾斜：事务首先查询数据，根据返回的结果再做出决定，然后修改数据库。当事务提交时，决定的前提条件可能已经不成立了。只有可串行化的隔离级别才能防止这种异常。

幻读：事务读取了某些符合查询条件的对象，同时另一个客户端执行写入，改变了先前的查询结果。快照隔离可以防止简单的幻读，但写倾斜情况需要特殊处理，一般是采用谓词锁或索引区间锁（next-key lock）。

只有可串行化隔离级别才能防止上面的所有问题。

第八章、分布式系统的挑战

以最悲观的角度来讨论分布式系统的问题，所有可能出现的问题一定会发生。但不考虑拜占庭将军问题。

故障与部分失效

分布式系统中，可能出现一部分功能正常，某些部分出现故障的情况。还有可能由于网络延迟造成根本不知道成功失败的情况。

云计算和超算（大规模计算系统）

关于如何构建大规模计算系统有以下几种思路：

1. 规模的极端是高性能计算，由成千上万个CPU的超级计算机构成了一个庞大的集群，通常用于计算密集型（CPU密集）的任务，天气预报、分子运动计算。

2. 另一个极端是云计算，多个租户数据中心，普通的电脑设备，用网络连接多个中心，弹性（可伸缩）/按需分配资源，按需计费。

超级计算机不是一个分布式项目，更像一个超级单机。它处理异常的方式：定时的生成系统完整快照，如果遇到异常，修复异常后，读取快照，从最近的快照开始重新执行。这样做往往让局部的异常升级为全局的异常。这种情况不再讨论范围内。

不可靠的时钟

对于计算机系统来说，在低可靠性部件上构建高可靠的系统一直是计算机领域的惯用手段。

每台计算机（甚至CPU的每个核心）都可能会存在不同的时间。

墙上时钟：2026-07-01 15:09:13，System.currentTimeMillis()，类似这样的自然时间，每个计算机都可能维护着自己的时间，且这个时间不能当做参考。因为就算是同一个计算机，随时都可能出现时钟回拨等情况。

单调时钟：指System.nanoTime()，这样的与1970-01-01起计算的时间，一般就算有统一时间管理，也只能回拨墙上时间，不会修改单调时钟。两天机器之前的单调时钟是不可靠的，也没有比较的意义。但在同一台机器上，单调时钟完全可以当做参考量。统计一个请求的处理耗时等。（因为此时间单调递增，不可回拨）

这里需要注意，System.currentTimeMillis()是墙上时钟可能出现回拨，System.nanoTime()是单调时钟，虽然不会出现回拨。但在有些可挂起虚拟机内部，可能出现单调时钟不变（不递增）的情况。

• 依赖时间的事件顺序

上图为多个节点之间，如果依赖时间戳做同步写入的先后，就可能中多个间因时间差距，导致数据错乱。

解决方式一般为引入一个递增计数器，通过递增技术来的数字来区分先后顺序。

还有一种方式是可以使用时谷歌的trueTime API，它会返回两个时间不早于，不晚于，会精确的给出当前时间的相对准确信息，但依然存在步长问题，会存在一小段的误差。

• 租赁时间问题

在redis，zookeeper等raft一致性协议下，经常出现一段时间内，master节点固定的情况。但master所持有的租约缺失基于时间来决定是否过期的，此时由于时间的不可靠，就可能出现数据混乱问题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

while (true) { 
	request = getlncomingRequest (); 
	// Ensure that the lease always has at least 10 seconds remaining 
	if (lease.expiryTimeMillis -
	System.currentTime问 ill is() < 10000) { 
		lease = lease . renew();
  }
	if (lease.isValid()) { 
    process(request); 
  }
}

上面存在两个问题：

1. 如果本次时间不可能靠，就会出现两个主节点。
2. 如果运行过程中进程暂停，由于垃圾回收器导致的(STW)，会让进程暂停，从而可能会让master在一段时间后才会去检测失效。

确定操作的有效

同样是租约系统，因GC产生的错误：

此时由于错误的令牌，导致数据被误写。

• 可以使用Fencing令牌来解决当前问题

利用zookeeper等来实现有序令牌，每次写入操作只接收最新的令牌。

这样做，每次操作都需要检测令牌是否有效，客户端和资源端都要检测。

• 拜占庭问题

对于拜占庭将军问题，可以利用BTC或Solana的方式来解决。这样的解决方式成本极高，且必须保证每个节点运行的代码不相同，否则如果可以入侵一个节点，理论上所有节点都可以入侵。

关于BTC和Solana可以看我的这篇文章;

第九章、一致性与共识

为了构建容错系统，最好先建立一套通用的抽象机制和预制对应的技术保证，这样只需实现一次，其上的应用程序都可以安全地信赖底层保证。（就想事务之于数据库一样，通过事务，应用程序不需要感知数据库的各种问题）分布式中的共识就是一种抽象机制，让应用忽略应用内部的各种故障，应用只需要关注共识的结果就好。

一致性保证

最终一致性的问题：传统的数据复制（主从、多主节点、无主节点）只要存在多个实例，就一定存在一段时间的数据不一致，但会在一段时候后变为一致；这个过程叫做收敛。在分布式应用中，这个收敛的过程将变得非常致命。会让相当多由数据做判断的业务变的不准确。

事务隔离：为了处理并发执行事务时的各种临界条件。

分布式一致性：针对延迟和故障等问题来协调副本之间的状态。

可线性化（强一致性）

最强的一致性模型

让一个系统看起来好像只有一个数据副本，且所有操作都是原子的。有了这个保证，应用程序就不用关心系统内部的多个副本。

• 非线性化的系统

非线性化的系统中，两个人同时读取数据，可能由于延迟，读取到已过期的数据。

可线性化：一旦某个客户端成功提交写请求，其他客户端的读请求，一定都能看到刚刚写入的值。

• 可线性化和可串行化的区别

可串行化：保证事务的执行结果与串行执行的结果完全相同。

可线性化：读写操作的单个值保证，并不要求操作组合到事务中，因此可能发生写倾斜。

可线性化保证从某个时刻起，读取的值固定。

实现可线性化系统

表现的好像只有一个数据副本，且所有操作都是原子的。

• 主从复制（部分支持可线性化）

主节点承担数据写入，从节点在各自节点上维护数据的备份副本。

需保证主节点定义没有问题，不会出现虚假的主节点。读取操作需要当前读，不能读取快照版本

• 共识算法（可线性化）

共识算法内置一些策略防止脑裂和过期副本。可以安全地实现线性化存储。

• 多主节点（不可线性化）

• 同时在多个节点上执行并发写入，并将数据异步复制到其他节点。因此他们可能会产生冲突的写入，需要额外处理写冲突。

• 无主节点（可能不可线性化）

• 基于墙上时钟的最后写入获胜冲突解决一定是非线性化，时间戳无法保证与实际发生顺序一致。不规范的quorum也会破坏线性化。

尽管严格把数据传给了每个副本，但由于并发问题，还是出现了不可线性化。

线性化的代价

各种场景下可能对于线性化的影响

• 网络中断

网络问题是一定会出现的问题，这种情况经常导致线性化被影响。

• CAP理论（不建议使用CAP理论）

一致性，可用性，分区容错性，系统只能支持其中两个特性。这种理解其实存在误区，网络分区是一种故障，无论如何，他都有可能发生，所以无法选择或逃避分区的问题。

在网络正常时，系统可以同时保证一致性（线性化）和可用性。而一旦发生了网络故障，必须要么选择线性（一致性），要么可用性。

更准确的称呼应该是：网络分区情况下，选择一致还是可用。

• 可线性化与延迟

现代的多核CPU上的内存就是非线性化的：某个核心上的线程修改了内存地址，另一个核心上的线程尝试读取，系统无法保证可以读取到刚刚写入的值，除非使用内存屏障或fence指令。（可见性问题）

**多核CPU放弃线性化的原因是为了性能，而不是容错。**选择不支持线性化是为了提高性能，无论是否发生网络故障，线性化对性能的影响都是非常巨大的。

顺序保证

主从复制系统：主节点的主要作用是确定复制日志中的写入顺序，这样使从节点遵从相同的顺序写入。

可串行化：确保事务的执行结果，和按照某种顺序执行的一样。实现方式：严格按照顺序，允许并发但需要某种冲突解决方案（加锁/冲突-中止）

分布式系统的时间和时钟：计算机世界的无序操作，按照“时间”顺序确认哪个先写入。

顺序与因果关系

• 因果和完全按照顺序

有因果关系的一些数据，只能在因果链内部比较顺序，但不能随便拿出任意两个节点比较顺序。（全序与偏序）

如果两个事件是因果关系（一个发生在另一个之前），那么这两个事件可以被排序；而井发的事件则无法排序比较。

在一个可线性化存储中不存在并发操作，一定有一个时间线把所有操作都全序执行。可能有多个请求处于等待执行状态，但数据库保证特定的时间点只执行特定的操作。（单个数据副本，没有并发）

• 可线性化强于因果一致性

任何可线性化的系统都将正确地保证因果关系。（但可线性化的系统会显著降低性能和可用性）

因果一致性可以认为是 ，不会由于网络延迟而显著影响性能，又能对网络故障提供容错的最强的一致性模型。

• 如何保持因果关系

如果某个副本在处理一个请求时，必须确保所有因果在前的请求都已完成处理，否则后面的请求必须等待知道前序操作处理完成。

序列号排序

虽然因果关系很重要，但实际上跟踪所有因果关系不切实际。许多应用会在写之前读取大量数据，系统无法了解之后的写入究竟依赖全部读取内容还是部分。

于是有了，我们可以使用序列号和时间戳来排序事件。时间戳不一定来自墙上时钟。他可以只是一个逻辑时钟，利用采用算法来实现一个逻辑序列。（自增ID）

这样的序列号非常紧凑，他们保证了全序关系。每个操作都有唯一的顺序，且都是可以相互比较的。

• 序列号的产生方式

1. 每个节点独立产生自己的自增序列号。需预留出表示当前序列号由哪个节点生成的位。
2. 把墙上时钟附加的操作上。墙上时钟可以有效的区分前后。
3. 按步长产生。一次性占用1k个序列号，每次只有达到步长，再重新申请序列号。这样可以使生成的序列号尽量连续，再需要将序列号作为索引的时候，可以更好的进行范围查询。

• Lamport 时间戳

上面的几种方式，都会出现因果不一致的情况。利用蓝波特时间戳，可以产生因果一致的序列号。

每个节点都有唯一的标识符和一个记录自己请求总数的计数器。Lamport时间戳是一个值对（计数器，节点ID）。两个节点可能会有相同的计数器值。

计数器较大那个时间戳大；如计数器值正好相同，则节点ID越大，时间戳越大。

Q：如何让因果保持一致？

每个节点和每个客户端都跟踪迄今为止所见到的最大计数器值，并在每个请求中附带该最大计数器值。当节点收到某个请求，如发送请求的最大计数器大于节点自身计数器，节点把自身计数器修改为该最大值。

依赖序列号来做校验，并不能避免所有的冲突，如果系统需要创建一个全局唯一的值，旧无法通过序列号来实现。因为每个序列号产生时，无法保证自己的操作是否成功，如果所有节点同时创建相同的唯一值，这将是灾难性的。

全序关系广播

如果程序只运行在一个CPU核心上，可以非常简单的定义出操作的全序关系，就是单核的执行顺序。

主从复制模型，首先在确定的主节点上执行，然后把操作按顺序给到从节点。分布式系统中，必须突破单一主节点的限制。

要想实现全序关系广播，需要满足两个基本安全属性：

1. 可靠发送：没有消息丢失，如果消息发送到了一个节点，也必须发送到所有节点。
2. 严格有序：消息总是以相同的顺序发送给每个节点。

网络中断时消息不可能发送成功，但算法需要一直重试，直到网络恢复，消息发送成功为止。

zookeeper和etcd这样的共识服务实际上就是实现了全序关系广播。

• 全序关系广播与可线性化的区别

全序关系广播是基于异步模型：保证消息以固定的顺序可靠地发送，但不保证消息何时发送成功（会出现每个接收者，收到消息时间不一致的情况）。而可线性化，强调读取时就能够看到最新的值。

分布式事务与共识

原子提交和两阶段提交

2PC是一种在多个节点之间，实现事务原子提交的算法，用来确保所有节点要么全部提交，要么全部中止。

2pc需要有一个协调者（事务管理器）。

协调者向所有参与者请求资源占用，请求成功后，提交。（TCC）

• 协调者发生故障

在资源占用阶段，协调者可以根据参与者的占用情况来决定事务的执行与否。但一旦进入提交阶段（特别是成功），则所有参与者必须保证全部成功，如果有不成功的，事务管理器需要无限重试，直到成功为止。

但如果协调者发生故障，参与者就无法知道下一步的行动。

对于2pc的协调者，应该在做确定前，先记录执行日志。如果协调者故障，恢复后可以通过执行日志恢复之前的操作。

实践中的分布式事务

• Exactly-once 消息处理

由消息队列和数据库实现，一个消息刚好由数据库的成功提交时才会被删除。如果数据库提交失败，稍后会重试。

这种实现，无法回滚，一旦发送，就会尽最大努力提交事务。

• XA交易

采用XA交易的实现：Transaction注解，消息队列JMS，PostgreSQL, MySQL 、 DB2 、SQL Server和Oracle。ActiveMQ、Horn巳tQ 、MSMQ和IBM MQ ）都支持XA。

XA本身是一个宽松的协议，只要满足XA交易的服务，都可以认为是看似线性的服务。

共识是让几个节点基于某项决议达成一致。

关于分布式事务，详细的可以看凤凰架构中的介绍。