《数据密集型应用系统设计》整理08

第九章 一致性与共识

Is it better to be alive and wrong or right and dead?
—Jay Kreps, A Few Notes on Kafka and Jepsen (2013)

分布式系统最重要的抽象之一就是共识:所有节点就某一项提议达成一致。

思路:线性化是所有事件一字排开都有先后顺序,因果一致性是一个比较弱的一致性模型,允许存在某些并发事件。
然而,即使意识到因果顺序,有时我们仍然无法在实践中使用,比如用户名注册问题,如果要同意请求,则需要以某种方式查询其他节点是否存在竞争请求。
这时候就需要有共识算法,所有节点就某一项提议达成一致。
需要有一个主节点,或愿意把所有决策功能都委托给某一个主节点。
主节点发生故障的时候,XA/JTA等事务协调者采取了服务停止的方法,也可以依靠人为介入选主,但是最为可靠的是采用算法自动选主。
zk等工具以一种类似外包方式为应用提供了重要的共识服务、故障检测和成员服务。

可线性化

其基本思想是让一个系统看起来好像只有一个数据副本,且所有操作都是原子的。

在一个可线性化的系统中,所有客户端的读请求一定能看到刚刚写入的值,而不是过期的缓存。

概念:寄存器,指的是多个客户端在线性化数据库中同时读写相同的主键x,这个x就是分布式语义下的寄存器。

需要线性化的场景

  • 加锁与主节点选举:需要所有节点都同意
  • 唯一性约束:要求所有节点就某个最新值达成一致
  • 跨通道的时间依赖:通过控制某一个通信通道

实现线性化系统

  • 单主复制,部分线性化:如果从主节点或同步更新的从节点上读取,则可以满足线性化
  • 共识算法,可线性化
  • 多主复制,不可线性化:可能会产生冲突的写入
  • 无主复制,可能不可以线性化:取决于实现方式和具体配置。比如使用时钟的LWW则几乎肯定是非线性化的

线性化的代价

网络中断的情况下,具体基于多主或者单主的模型,需要在可线性化与可用性之间做出选择。

CAP理论:一致性、可用性、分区容错性只能支持其中两个

  • 如果应用要求线性化,但网络中断了,则服务不可用。
  • 如果应用不要求线性化,则网络中断后,每个副本可以单独处理请求,但是结果不符合线性化。
    现实中通常是在网络分区情况下,选择一致性还是可用性。

虽然可线性化是个很有用的保证,但是实际上很少有系统真正满足线性化。
如果要满足线性化,那么读写请求的响应时间至少要于网络中延迟程正比。

顺序保证

如果系统服从因果关系所固定的顺序,我们称之为因果一致性

因果关系不是全序的(对于任意两个元素,总是可以指出哪个更大,哪个更小),允许存在并发关系。可线性化是全序的。

可线性化保证了因果一致性,但并非是保证因果一致性的唯一途径。
因果一致性可以认为是,不会犹豫网络延迟而显著影响性能,却又能对网络故障提供容错的最强的一致性模型。

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

序列号排序

使用序列号或时间戳来排序事件,按照与因果关系一致的顺序来创建序列号。

  • 主从复制的情况下,主节点简单的为每个操作递增某计数器。
  • 不存在主节点的情况下,可以每个节点独立产生一组序列号,预先分配分区,或者使用墙上时钟

无主的解决方案都有问题:节点可能有不同的处理速度,时钟会偏移,区间分配的方式下,一个操作可能被赋予了1000-2000的某个序列号,而后发生的又被路由到1-1000的区间。

Lamport时间戳可以解决这些问题:每个节点有唯一标识,以及一个计数器来记录各自已处理的请求总数,保存为一个值对(计数器,节点ID)。每个节点以及每个客户端都跟踪迄今为止所见到的最大计数器值,并在每个请求中附带该最大计数器值。当节点收到某个请求(或回复)时,如果发现请求内嵌的最大计数器值大于节点自身的计数器值,则它立即把自己的计数器修改为该最大值。
-----2019-07-21---4.39.24

时间戳排序还是不够,在像设置用户名这种唯一性约束的场景下,系统必须访问和等到所有节点的返回。

全序关系广播

全序关系广播通常指节点之间交换消息的某种协议:

  • 可靠发送:没有消息丢失,如果消息发送到了某一节点,那么它一定要发送到所有节点
  • 严格有序:消息总是以相同的顺序发送给每个节点

全序关系广播基于异步模型:保证消息以固定的顺序可靠地发送,但是不保证消息何时发送成功。而可线性化则强调就近性:读取时保证能够看到最新的写入值。

使用全序关系广播以追加日志的方式来实现线性化的原子CAS操作:

  • 日志中追加一条信息
  • 读取日志并广播给所有节点,等待回复
  • 检测是否有冲突。如果第一条这样的回复来自于自己,则成功,可以提交并返回success给客户端。如果不是自己,则中止操作

实现线性化读取:

  • 采用追加的方式把读请求排序、广播,然后各个节点获取该日止,当本节点收到消息时才执行真正的读操作;
  • 等待直到该位置之前的所有操作都发给你
  • 从同步更新的副本上读取

与Lamport时间戳不同,通过递增线性化寄存器获得的数字不会存在任何间隙。因此,如果节点完成了消息4的发送,且接收到了序列化6的消息,那么在他对消息6恢复之前必须等待消息5。

线性化的原子CAS寄存器与全序关系广播都等价于共识问题。

分布式事务与共识

共识问题是让几个节点就某件事达成一致。

两阶段提交

是一种在多节点之间实现事务原子提交的算法,用来确保所有节点要么全部提交,要么全部中止。
-----2019-07-21---5.20.42
引入一个协调者,数据库称为参与者。该协议有两个关键的“不归路”:

  • 当参与者投票“是”,它做出了肯定提交的承诺
  • 当协调者提出了提交的决定,这个决定不可撤销

协调者必须在向参与者发送提交(或中止)请求之前将该决定写入磁盘的事务日志,以使得当协调者崩溃之后恢复的时候继续事务。

支持容错的共识

共识问题通常形式化描述:一个或多个节点可以提议某些值,由共识算法来决定最终值。
在这个描述中,共识算法必须满足以下性质:

  1. 协商一致性:所有节点接受相同决议
  2. 诚实性:所有节点不得反悔
  3. 合法性:决定了v,则v一定是由某个节点所提议的
  4. 可终止性:节点如果不崩溃则最终一定可以达成决议
    总结:决定一致的结果,一旦决定,就不能改变。

可终止性的前提是,发生崩溃或不可用的节点数必须小于半数节点。

全序关系广播相当于持续的多轮共识:

  • 由于协商一致性,所有节点决定以相同的顺序发送相同的消息
  • 由于诚实性,消息不能重复
  • 由于合法性,消息不会被破坏,也不是凭空捏造的
  • 由于可终止性,消息不会丢失

选主投票(epoch和quorum):首先投票决定谁是主节点,然后对主节点的提议进行投票。参与两轮的quorum必须有重叠:如果某个提议获得通过,那么其中参与投票的节点中必须至少有一个也参加了最近一次的主节点选举。

局限性:
节点投票是一个同步复制的过程,但是很多数据库系统为了性能而配置为异步复制。
不好动态新增删除节点
共识算法需要依靠超时机制来检测节点失效,容易受网络延迟变化影响。

成员与协调服务

Zookeeper和etcd主要针对保存少了、可完全载入内存的数据而设计,通常采用容错的全序关系广播算法在所在节点上复制这些数据从而实现高可靠。

Zookeeper还提供了:

  • 线性化的原子操作:共识算法保证了操作满足原子性和线性化。使用原子CAS操作实现加锁服务。
  • 操作全序:对所有操作执行全局排序,给每个操作赋予一个单调递增的事务ID和版本号,以避免因为发生进程暂停而引起的锁冲突。
  • 故障检测:客户端与zookeeper节点维护一个长期会话,客户端周期性的report。当会话的心跳超过了会话超时设置,则zookeeper宣布会话失败,这时会话持有的锁都自动释放。
  • 更改通知:通过监视变化,客户端可以知道其他客户端的状态(加入,故障等)。

zk不适合保存那些应用实时运行的状态数据,后者可能每秒产生数钱甚至百万次更改,使用其他工具(如BookKeeper)比较好。

用zk做服务发现和DNS的区别:DNS使用多层缓存来实现高性能与高可用性,不满足线性化。但是DNS对于网络产生中断时服务可用性和鲁棒性更为重要一些。

comments powered by Disqus