ddia阅读笔记(六)

Posted on |

写在前面的话

本章是ddia的第九章，一致性与共识

主要讨论了线性一致新保证，目标是让所有副本看起来就像一个副本一样。

接下来讨论了因果顺序，允许一些并发发生

再之后讨论了共识，所有节点一致同意所做决定，且这一决定不可撤销。在讨论共识的路上发现了其实很多问题都能等价为共识问题。

最末对ZooKeeper这类工具的应用进行了简单介绍，毕竟，自己做一个共识是一个很困难的事情。

共识其实在区块链也是个老生常谈的问题了，各种卖点都是基于拜占庭容错的共识，从PBFT,SBFT到POW,POS,DPOS等，都有点接近于玄学了。我个人对共识是不怎么看好的，可能再怎么提升，共识的效率也不会超过RAFT，如果是那样，最终的问题还是回到了网络通信上，而不是所谓的吹嘘的优化的共识算法。

一致性与共识

构建容错系统的最好方法，是找到一些带有实用保证的通用抽象，实现一次，然后让应用依赖这些保证。

例如通过使用事务

  • 应用可以假装没有崩溃(原子性)
  • 没有其他人同时访问数据库(隔离)
  • 存储设备是完全可靠的(持久性)

因此：首先需要探索分布式系统中提供的保证和抽象的范围

一致性保证

大部分复制的数据库提供了最终一致性

如果你停止向数据库写入数据并等待一段不确定的时间，那么最终所有的读取请求都会返回相同的值

分布式一致性主要是为了：对延迟和故障时，如何协调副本间的状态

线性一致性

基本的想法是让一个系统看起来好像只有一个数据副本，而且所有的操作都是原子性的

如下图所示是一个非线性一致系统的例子

非线性一致性

A获取了比赛的比分后告诉了B，B再去查询时因为不同的副本，导致看上去的比分不太一样，违背了线性一致性

什么使系统线性一致性

  • 如果与写入同时发生的读取可以返回旧值或新值，那么读者可能会在写入期间看到数值在旧值和新值之间来回翻转，这就不是线性一致性

通过记录所有请求和响应的时序，并检查它们是否可以排列成有效的顺序，测试一个系统的行为是否线性一致性是可能的(尽管在计算上是昂贵的)

非线性一致性2

如上图所示：

  • write(a, b) => result：在a寄存器中写入值b，并返回写入结果
  • read(a) => b: 从a寄存器中读取值，返回读取结果
  • cas(a, b, c) => result：在a寄存器中读取当前值，如果当前值==b，那么将当前值替换为c，并且返回替换结果。
  • 线条所在的是该事件的实际发生时刻。

可以看到，最后的read(x) => 2并不是线性发生的，因此这个系统不是线性一致性的。

依赖线性一致性

锁定和领导选举

单主复制的系统，需要确保这个锁是线性一致的：所有节点必须就哪个节点拥有锁达成一致，否则就没用了。

例如：

  • Zookeeper、etcd使用容错一致性算法实现线性一致的操作
  • Apache Curator在Zookeeper之上提供更高级别的配方来提供帮助
  • Oracle Real Application Clusters上也在使用分布式锁

约束和唯一性保证

唯一性约束在数据库中很常见：例如用户名唯一，电子邮件地址唯一等等。

这种约束也需要线性一致性，类似于一个锁：当一个用户注册你的服务时，可以认为他们获得了所选用户名的“锁定”。

跨信道的时序依赖

时序依赖

如上图所示，流程如下：

  1. 用户上传图片到服务器
  2. 服务器存储全尺寸图片到文件服务器
  3. 服务器发送命令到消息队列
  4. 消息队列发送信息到文件压缩命令
  5. 文件压缩后台从文件服务器中取全尺寸文件
  6. 存储压缩后的文件到文件服务器中

如果该架构不是线性一致的，那么3、4可能比2更快，这时候就会处理到旧版本或者没有图像

实现线性一致的系统

  • 只用一个数据副本：不能容错
  • 单主复制：可能线性一致
    • 并发错误
    • 具有错觉的领导者
    • 以上均会导致线性不一致
  • 共识算法：线性一致
  • 多主复制：非线性一致
  • 无主复制：可能非线性一致
    • 基于失踪的最后写入胜利是非线性一致的
    • 法定人数读写可以获得强一致性

线性一致性和法定人数

在Dynamo风格的无主复制中，严格的法定人数应该是线性一致的，但是在可变的网络延迟情况下，可能存在竞争条件，如下图所示：

非线性一致性

可以看到由于延迟，B在A的后面进行读取，然而A获取到了新值，但是B获取到了旧值

总之，可以假设采用Dynamo风格无主复制的系统不能提供线性一致性

线性一致性的代价

线性一致性和可用性之间会做选择

CAP定理

所有线性一致的数据库在不可靠的网络上，都可能发生如下问题：

  • 如果要保持线性一致性，且某些副本因为网络问题与其他副本断开连接，那么这些副本掉线时不能处理请求，必须等到网络问题解决或者返回错误
  • 如果不需要保持线性一致性，那么即使某个副本与其他副本断开连接，也可以独立处理。

P.S. CAP只考虑了线性一致性与网络故障，目前其实已经没什么卵用了

线性一致性和网络延迟

线性一致的系统在实际上惊人的少。线性一致性的速度很慢。

顺序保证

顺序，线性一致性和共识之间有着深刻的联系

顺序与因果

因果关系对事件施加了一种顺序：

  • 因在果之前
  • 消息发送在消息收取之前

这些因果依赖的操作链定义了系统的因果顺序，即，什么在什么之前发生

如果一个系统服从因果关系所规定的顺序，我们说它是因果一致的。

因果顺序不是全序的

全序允许任意两个元素进行比较

  • 线性一致性：操作是全序的，对任何两个操作，我们总能判定哪个操作先发生
  • 因果性：定义了一个偏序，一些操作相互之间是有顺序的，有些则无法比较

线性一致的数据存储中是不存在并发操作

并发意味着时间线会分岔然后合并

线性一致性强于因果一致性

任何线性一致的系统都能正确保持因果性

在许多情况下，看上去需要线性一致性的系统，实际上需要的只是因果一致性，因果一致性可以更高效地实现

捕获因果关系

为了维持因果性：

  • 如果一个操作发生在另一个操作之前，那么必须在所有副本上以这个顺序被处理
  • 并发操作可以以任意顺序进行

序列号顺序

可以使用序列号/时间戳来排序事件

典型的实现是使用一个每次操作自增的计数器

例如：

单主复制的数据库中，复制日志定义了与因果一致的写操作，主库可以简单的为每个操作自增一个计数器，从而为复制日志中的每个操作分配一个单调递增的序列号

非因果序列号生成器

无主库下，很难为操作生成序列号，可以有如下方法：

  • 每个节点都可以生成自己独立的一组序列号，如A节点只生成奇数，B节点只生成偶数
  • 将时钟时间戳附加到每个操作上
  • 预先分配序列号区块，例如A是1到1000区块，B是1001到2000区块

然而面临问题：生成的序列号与因果不一致。

兰伯特时间戳

如下图所示：

兰伯特时间戳

每个节点都有一个唯一标识符，和一个保存自己执行操作数量的计数器。兰伯特时间戳就是两者的简单组合：(计数器，节点ID)

兰伯特时间戳提供了一个全序：如果你有两个时间戳，则计数器值大者是更大的时间戳。如果计数器值相同，则节点ID越大的，时间戳越大

关键思想如下所示：
每个节点和每个客户端跟踪迄今为止所见到的最大计数器值，并在每个请求中包含这个最大计数器值。当一个节点收到最大计数器值大于自身计数器值的请求或响应时，它立即将自己的计数器设置为这个最大值

  • A从节点2获得计数器值5，然后将最大值5发送到节点1
  • 节点1的下一个操作计数器值为6
  • 兰伯特时间戳无法分辨两个操作是并发的还是因果依赖的

光有时间戳排序不够

以创建用户名为例，如果创建了两个具有相同用户名的账户，选择时间戳小的那个作为胜者，让更大的那个失败

  • 这种仅仅适用于事后确定胜利者：需要收集系统中所有的用户名创建操作，才可以比较，无法处理实时请求。

P.S. 为了实诸如如用户名上的唯一约束这种东西，仅有操作的全序是不够的，你还需要知道这个全序何时会尘埃落定

全序广播

单CPU上的全序：CPU执行这些操作的顺序
分布式系统的全序：单主复制通过选择一个节点作为主库来确定操作的全序,并在主库的单个CPU核上对所有操作进行排序

全序广播：被描述为在节点间交换消息的协议

  • 可靠交付：没有消息丢失，如果消息被传递到一个节点，它将被传递到所有节点
  • 全序交付：消息以相同的顺序传递给每个节点

使用全序广播

状态机复制:

如果每个消息都代表一次数据库的写入，且每个副本都按相同的顺序处理相同的写入，那么副本间将相互保持一致(除了临时的复制延迟)

表现：

顺序在消息送达时被固化:如果后续的消息已经送达，节点就不允许追溯地将(先前)消息插入顺序中的较早位置

方式：

传递消息就像附加写入日志。由于所有节点必须以相同的顺序传递相同的消 息，因此所有节点都可以读取日志，并看到相同的消息序列

使用全序广播实现线性一致的存储

全序广播：

  • 异步
  • 保证消息以固定的顺序可靠的传送
  • 不能保证消息何时被送达

线性一致性：

  • 新鲜性的保证
  • 读取一定能看到最新的写入值

通过全序广播，就能构建线性一致的存储，例如确保用户名能唯一标识用户账户

  • 在日志中追加消息，试探性指明需要声明的用户名
  • 读取日志，并等待附加消息被回送
  • 检查目标用户名所有权消息，如果第一条就是你自己的消息，那么就成功，否则就中止。

P.S.
写入过程是线性一致，并不代表读取过程也是线性一致，要保证读取线性一致，可以考虑：

  • 追加消息，当消息回送时读取，消息在日志中的位置定义了读取发生的时间点(etcd的法定人数读取)
  • 如果日志允许以线性一致的方式获取最新日志消息的位置，则可以查询该位置，等待直到该位置前的所有消息都传达到你，然后执行读取(如ZooKeeper的sync()操作)
  • 可以从同步更新的副本中进行读取，因此可以确保结果是最新的(链式复制)

使用线性一致存储实现全序广播

每个要通过全序广播发送的消息首先对线性一致寄存器执行自增并返回操作。然后将从寄存器获得的值作为序列号附加到消息中。然后你可以将消息发送到所有节点(重新发送任何丢失的消息)，而收件人将按序列号连续发送消息。

可以证明：线性一致的CAS(或自增并返回)寄存器与全序广播都都等价于共识问题

分布式事务与共识

原子提交与二阶段提交(2PC)

从单节点到分布式原子提交

单节点

  • 客户请求数据库节点提交事务
  • 数据库将事务写入持久化
  • 提交记录追加到磁盘的日志中
    • 如提交记录在崩溃前写入磁盘，重启后可以恢复
    • 如提交记录在崩溃后写入磁盘，重启后不能恢复

仅向所有节点发送提交请求并独立提交每个节点的事务是不够的。这样很容易发生违反原子性的情况:提交在某些节点上成功，而在其他节点上失败

  • 约束冲突或冲突
  • 网络中丢失请求
  • 节点崩溃后回滚

两阶段提交简介

两阶段提交

角色介绍：

  • 协调者：在请求事务的相同进程中以库的形式实现，也可以是单独的服务或进程，如Narayana，JOTM，BTM或MSDTC
  • 参与者：数据库节点

过程：

  • 协调者发送准备(prepare)请求到每个节点，询问是否能够提交
  • 如所有参与者都回答”是”，那么协调者将发起提交(commit)请求，然后提交发生
  • 如任一参与者回答”否”，那么协调者将会发起中止(abort)请求

系统承诺

对2PC的过程进行详细分解：

  • 启动分布式事务时，向协调者请求一个全局唯一的事务ID
  • 应用在每个参与者上启动单节点事务，并在单节点上捎带上这个事务ID
  • 应用提交时，协调者向所有参与者发送一个准备请求，并打上全局事务ID的标记
  • 参与者向协调者回应“是”时，就保证了这个事务可以被不出差错的提交
  • 收到所有请求的答复，协调者就会提交或中止事务做出明确决定(必须将决定写入到磁盘上的事务日志)
  • 协调者决定落盘后，会保持重试，直到成功为止，如果参与者崩溃，事务将在恢复后提交

2PC有两个点保持原子性：

  • 参与者回答“是”：保证稍后肯定能提交
  • 协调者做出决定：这一决定是不可撤销的

协调者失效

参与者失效

  • 任何准备请求失败/超时，协调者会中止事务
  • 任何提交或中止请求失败，协调者将无条件重试

协调者失效

  • 在发送准备请求之前失败，参与者可以安全中止事务
  • 参与者收到了准备请求并且回应“是”，此时需要等待协调者，如果此时协调者失效，参与者会进入存疑或不确定状态

两阶段提交失败

如图所示，参与者1并不知道最终协调者的结果是如何，参与者2收到了提交但是无法等到完成消息

完成2PC的唯一办法是等待协调者恢复

三阶段提交

3PC需要假定网络延迟有界，节点响应时间有限，在实际系统中不能保证原子性

实践中的分布式事务

目前的现状：

  • 重要：难以实现的重要的安全性保证
  • 麻烦：会导致运维问题，性能下降

精确说明分布式事务：

  • 数据库内部的分布式事务
  • 异构分布式事务

恰好一次的消息处理

只有当所有受事务影响的系统都使用同样的院子提交协议时，才能满足所有的副作用都在事务中止时回滚。

  • 例如，副作用是发送一封邮件，而邮件不支持两阶段提交，所以当重试时，就可能需要发送多次的邮件。

XA事务

X/Open XA(扩展架构(eXtended Architecture))是跨异构技术实现两阶段提交的标准。

XA不是一个网络协议，只是一个用来与事务协调者连接的C API。

  • JAVA EE中，XA事务是使用Java事务API(JTA)实现的
  • JDBC，JMS都支持JAVA事务API

怀疑时持有锁

在使用两阶段提交时，事务必须在整个存疑期间持有这些锁。

从协调者故障中恢复

理论上，协调者崩溃并重新启动应该干净的从日志中恢复状态，并解决存疑事务，然而实践中孤立的存疑事务确实会出现，无法自动解决，永远待在数据库中，持有锁并阻塞其它事务。

唯一的出路是让管理员手动决定提交还是回滚事务。(危险，压力，不可靠)

XA实现的启发式决策：允许参与者单方面决定放弃或提交一个存疑事务，而无需协调者做出最终决定。(破坏了两阶段的系统承诺)

分布式事务的限制

  • 如果协调者没有复制，而是只在单台机器上运行，那么它是整个系统的失效单点
  • 当协调者成为应用服务器的一部分时，协调者的日志成为持久系统状态的关键部分
  • 由于XA需要兼容各种数据系统，因此它必须是所有系统的最小公分母。如：它不能检测不同系统间的死锁(需要标准协议让系统交换每个锁的信息)，而且它无法与SSI协同工作(需要跨系统定位冲突的协议)
  • 对于数据库内部的分布式事务(不是XA)，限制没有这么大

容错共识

形式化：

一个或多个节点可以提议(propose)某些值，而共识算法决定(decides)采用其中的某个值

性质：

  • 一致同意：没有两个节点的决定不同
  • 完整性：没有节点决定两次
  • 有效性：如果一个节点决定了值v，则v由某个节点所提议。
  • 终止：由所有未崩溃的节点来最终决定值

核心思想：
所有人都决定了相同的结果，一旦决定了，你就不能改变主意

容错思想：
一个共识算法不能简单地永远闲坐着等死，即使部分节点出现故障，其他节点也必须达成一项决定。

终止属性假设：
不超过一半的节点崩溃或不可达

拜占庭容错：
只要少于三分之一的节点存在拜占庭故障

共识算法和全序广播

  • 视图戳复制(VSR,viewstamped replication)
  • Paxos
  • Raft
  • Zab

全序广播相当于重复进行多轮共识：

  • 一致性：所有节点以相同顺序传递相同的消息
  • 完整性：消息不会重复
  • 有效性：消息不会损坏，也不会凭空编造
  • 终止：消息不会丢失

VSR，Raft，Zab直接实现了全序广播。
Paxos这种被称为Multi-Paxos

单领导复制和共识

区别在于如何选择领导者

  • 主库是手动选择和配置：独裁类型的“共识算法”
  • 自动执行领导者选举和故障转移。

鸡蛋矛盾：
要选出一个领导者，我们首先需要一个领导者

时代编号和法定人数

协议定义了时代编号(epoch number):并确保每个时代中，领导者都是唯一的。

  • 在Paxos中称为投票编号(ballot number)
  • 视图戳复制中的视图编号(view number)
  • Raft中的任期号码(term number)

每次当现任领导被认为挂掉的时候，节点间就会开始一场投票，以选出一个新的领导。如果不同时代的领导者之间冲突，那么带有更高时代编号的领导说了算

两轮投票：

  • 第一次是为了选出一位领导者
  • 第二次是对领导者的提议进行表决
  • 这两次投票的法定人群必须相互重叠：如果一个提案的表决通过，则至少得有一个参与投票的节点也必须参加过最近的领导者选举

与2PC的区别：

  • 2PC中协调者不是由选举产生的，而且2PC则要求所有参与者都投赞成票
  • 容错共识算法只需要多数节点的投票

共识的局限性

优点：

  • 为其他充满不确定性的系统带来了基础的安全属性(一致同意，完整性和有效性)
  • 保持容错(只要多数节点正常工作且可达，就能取得进展)
  • 提供全序广播，实现了线性一致的原子操作

缺点：

  • 节点在做出决定之前对提议进行投票的过程是一种同步复制
  • 共识系统总是需要严格多数来运转，网络故障会导致只有多数节点所在的网络可以继续工作
  • 大多数共识算法假定参与投票的节点是固定的集合，不能简单的在集群中添加或删除节点。
  • 共识系统通常依靠超时来检测失效的节点，频繁的领导者选举会导致糟糕的性能表现
  • 共识算法对网络问题特别敏感
    • Raft：如果整个网络工作正常，但只有一条特定的网络连接一直不可靠，Raft可能会进入领导频繁二人转的局面，或者当前领导者不断被迫辞职以致系统实质上毫无进展

成员与协调服务

ZooKeeper和etcd：

被设计为容纳少量完全可以放在内存中的数据，实现了全序广播，还构建了一些其他的特性

  • 线性一致性的原子操作
  • 操作的全序排序
  • 失效检测
  • 变更通知

将工作分配给节点

  • 选择几个进程实例作为主库或首选服务
  • 分配分区资源到现有节点或者新节点

服务发现

ZooKeeper，etcd和Consul也经常用于服务发现

可以配置你的服务，使其在启动时注册服务注册表中的网络端点，然后可以由其他服务找到它们

成员服务

成员资格服务确定哪些节点当前处于活动状态并且是群集的活动成员