← COMP5567 全部讲次
L02a-3 · 第 2 周

L02a-3 安全性、活性与 CAP:怎么说一个协议「对」

先学会用「坏事不发生」「好事终将发生」两句话描述协议的正确性,再一帧一帧看网络断开时,为什么一致和可用只能保一个。

一句话版

说一个协议「对」,要说两件事:坏事永远不会发生(安全性),好事最终一定发生(活性)。而在网络断成两半时,「大家看到的数据一样」和「每个请求都有回应」这两件好事只能保一个,这就是 CAP。

前一页讲了同步模型和 FLP,见 L02a-2。这一页给出全课描述正确性的两套语言。

先认识这几个词

词 全称 / 读法 一句人话
安全性 safety 坏事不会发生
活性 liveness 好事终将发生
临界区 critical section 同一时刻只许一个线程进去的代码段
分区 partition 节点之间的通信链路断了,网络分成互不相通的几块
一致性 C Consistency 所有客户端同一时刻看到相同的数据
可用性 A Availability 有故障时系统仍然响应请求
分区容错 P Partition tolerance 链路断开时系统仍能继续正确运行

一个类比:两家分店的会员卡

一家连锁店有两家分店,共用一套会员积分。平时两店的电脑随时同步,你在哪家查到的积分都一样。

某天两店之间的网线断了。你在甲店消费,积分涨了一截;你朋友拿着同一张卡去乙店查。乙店的店员只有两个选择:一是说「系统同步不上,暂时查不了」,保证不给出错误的数字;二是照常报出消费前的旧积分,服务没断,可数字是旧的。乙店没法既不拒绝你、又报出最新数字。

类比在哪里失效:

  • 真实的网络断开往往没人察觉,店员至少知道网线断了,节点常常连「断了没有」都判断不了。
  • 会员积分报旧了无伤大雅,账本报旧了可能造成同一笔钱被花两次,这时选哪边的代价差别很大。

从零讲起

1. 安全性与活性

它解决什么问题

要证明一个分布式协议是对的,先得说清「对」包含哪些要求。课件把所有要求分成两类:一类是绝不能出现的坏状态,一类是迟早得到达的好状态。后面每个协议的正确性证明都分成这两部分来写。

从哪来(补充)

safety 和 liveness 这两个词最早由 Leslie Lamport 在 1977 年一篇讨论如何证明多进程程序正确的论文里使用。1985 年,Bowen Alpern 和 Fred Schneider 在《Defining Liveness》里给出了形式化定义。

出处:Wikipedia: Safety and liveness properties

直觉

安全性像交通规则里的「红灯不能闯」:只要有一次闯了,当场就能抓现行。活性像「这辆车最终会到达目的地」:它堵在路上很久,你也不能据此断定它永远到不了,也许下一分钟就通了。

一步一步看

目标:用临界区的两段执行对照,看为什么安全性一段片段就能证伪,活性却不能。

课件用临界区举例。

  1. 安全性要求:两个线程不能同时处于临界区。

  2. 看一段执行:T1 进入临界区还没出来,T2 也进去了。重叠的那一段就是一个有限的执行片段,坏事已经发生,安全性被证伪。

  3. 活性要求:每个线程最终都会进入临界区。

  4. 看另一段执行:T3 一直在门外等。不管这段观察有多长,都不能断定它永远进不去,后面它仍可能进去,活性没法被这段片段证伪。

    上半部分是 T1、T2 两条线程的时间线,各有一段在临界区里的方块,两段重叠的部分用青绿框标出,坏事已发生,安全性当场被证伪;下半部分线程 T3 一直在等,时间线末端是虚线,只看有限的一段不能断定它永远进不了临界区

怎么判断

拿到一条性质,问它能不能被一个有限的执行片段推翻:

问题 能 不能
抓到某一刻就能说它被违反了吗 安全性 活性
典型措辞 「绝不」「永远不会」 「最终」「终将」
被违反的后果 永久性错误,例如双花 暂时只是慢,网络恢复后还能补回来

意思是:带「永远不」的多半是安全性,带「最终」的多半是活性;最可靠的判据仍是那个问题,看有限片段能不能推翻它。

常见误解

以为只要安全性有保证,协议就算对了

一个永远不做任何决定的协议绝对安全,因为它永远不会做出错误决定,但它完全没有活性,什么事也办不成。两者都必须要,缺一不可。

以为活性要求事情「很快」发生

活性只要求「最终」发生,不规定多快。部分同步模型下活性只在 GST 之后保证,正是利用了这一点:之前慢一点不算违反活性。

试一下

判断下面两条性质各是安全性还是活性:① 区块链上同一笔钱不会被花两次;② 用户提交的每笔合法交易最终都会被打包上链。

① 是安全性:只要在某个有限片段里看到同一笔钱被花了两次,就能判定违反。② 是活性:一笔交易等了很久还没上链,不能断定它永远上不了,只能继续等。

2. CAP 里的三个字母

它解决什么问题

分布式系统的数据会复制到多台机器上,一来防止一台坏了数据就丢,二来让各地用户就近访问。复制之后就要问:各个副本的数据一样吗?出了故障还能用吗?网络断了怎么办?CAP 把这三个问题各起了一个字母。

从哪来(补充)

CAP 由 Eric Brewer(UC Berkeley)提出:想法始于 1998 年秋,1999 年以「CAP 原理」发表,2000 年在 PODC 会议上作为猜想提出。2002 年,MIT 的 Seth Gilbert 和 Nancy Lynch 给出形式化证明,它才称为定理。

出处:Wikipedia: CAP theorem

直觉

两个节点各存一份数据 x。一致性要求两份永远对得上,可用性要求随便问哪个节点都有答复,分区容错要求两节点之间的线断了系统也还能正确运行。网络好的时候三样都不难,难在线断了的那一刻。

一步一步看

目标:看网络一断,N1 和 N2 手里的 x 怎样变得不一样,为下一节的二选一摆好场景。

  1. 网络正常:N1 和 N2 都存着 x = 1,一边写入,另一边马上同步。

    两个节点 N1、N2 用一条链路相连,各自存着 x 等于 1,网络正常时同步复制

  2. 网络断开,出现分区。客户甲把 x = 2 写到了 N1,N1 想把新值同步给 N2,可链路断了,N2 还停在 x = 1。

    N1 和 N2 之间的链路被打叉表示分区。客户甲把 x 等于 2 写到 N1,N1 的新值描成青绿,N2 还是旧值 1,且收不到这次更新

  3. 到这一步,两份数据已经不同了。下一节看有人来 N2 读 x 时会发生什么。

怎么判断

三个字母的定义要能准确复述:

字母 定义 判断时问
C 一致性 所有客户端在同一时刻看到相同的数据,无论连的是哪个节点 两个客户同时读,读到的一样吗
A 可用性 即使存在故障,系统仍然响应客户端请求 正常节点收到请求,会给出回应吗
P 分区容错 节点之间的通信链路断开时,系统能容忍并继续正确运行 链路断了,系统还能接着工作吗

意思是:C 看「答得对不对」,A 看「有没有答」,P 看「断网时撑不撑得住」。

常见误解

以为可用性 A 要求所有节点都不出故障

A 的定义恰好是「即使存在故障,系统仍然响应客户端请求」。它关心的是还在正常运行的节点会不会回应,已经崩溃的节点不在要求之内。准确的表述是「所有非故障节点的请求都能获得响应」。

试一下

分区期间,客户在 N2 读到 x = 1,而 N1 上已经是 x = 2。这一刻违反了 C、A、P 里的哪一个?

违反了 C:两个节点同一时刻给出的数据不同。A 没有违反,N2 给了回应;系统还在工作,P 也照样满足。这正是后面要讲的 AP 选择。

3. 分区时只能二选一:CP 还是 AP

它解决什么问题

CAP 常被说成「三个里只能选两个」。这一节把这句话拆开:分区在分布式系统里躲不掉,所以真正的选择只发生在分区那一刻,选 C 还是选 A。

直觉

回到上一节的第 2 帧:N2 手里是旧值,又联系不上 N1。这时有人来问它 x 是多少。它要么拒绝回答,要么报出旧值。两条路各丢一样东西。

一步一步看

目标:看分区时 N2 被问到 x,为什么只能在一致性和可用性之间挑一样。

  1. 分区还在,客户乙向 N2 读 x。

  2. 选 CP:N2 拒绝回答,等分区恢复再说。一致性保住了,没有人读到错的数据;可用性丢了,客户乙没拿到答复。

  3. 选 AP:N2 照常回 x = 1。可用性保住了;一致性丢了,客户乙读到的是旧值。

  4. 想两样都要,就得让 N2 既回答又答对,可它根本不知道 N1 上已经写了 2,做不到。

    分区仍在,客户乙去 N2 读 x。右边两个选项:CP 拒绝回答,保住一致丢掉可用,描成青绿;AP 回答旧值 x 等于 1,保住可用但数据旧

怎么判断

课件按 CAP 给数据库分了三类:

类型 分区时的行为
CP 关掉不一致的那个节点,使其不可用,直到分区解决
AP 所有节点保持可用,错误一侧可能返回旧数据,分区恢复后再重新同步
CA 一旦出现分区就做不到,因此无法提供容错

意思是:P 是必选的,因为分区一定会发生;判断一个系统属于哪类,只需看分区发生时它是拒绝服务(CP)还是照常服务、容忍旧数据(AP)。所谓 CA,只能在「不发生分区」的假设下讨论,实际多是单机系统。

常见误解

真的去「三选二」,以为可以挑 C 和 A、放弃 P

课件明写「在分布式系统中,分区是无法避免的」。网络断不断由不得你,P 不是一个可以放弃的选项。准确的说法是:发生网络分区时,不能同时保证一致性和所有非故障节点的可用性。

直接说「比特币就是 AP 系统」

课件拿比特币作 AP 的例子:分叉时两条链上的节点各自继续服务,账本视图暂时不一致,靠最长链规则最终收敛。这只是限定操作语义下的类比,节点暂时接受交易不等于交易已经最终确认。PBFT 类系统偏 CP,节点数不够就停下不出块,宁可不可用也不出现矛盾状态。

试一下

一个银行转账系统,分区期间宁可让用户看到「服务暂不可用」,也不允许同一笔钱在两个分区各被花一次。它是 CP 还是 AP?

CP。分区时它拒绝服务以保一致,放弃了可用性。双花是不可接受的安全性错误,所以这类系统通常选 CP。

把它们串起来

这一页给出了全课描述协议正确性的两套语言。第一套是安全性和活性:坏事不发生,好事终将发生。安全性能被一个有限片段抓现行,活性不能,所以协议可以让安全性无条件成立、把活性推迟到网络变好之后,上一页的部分同步模型正是这么做的。

第二套是 CAP,它讨论的是复制数据的系统在分区那一刻的取舍。分区躲不掉,P 必选,剩下只能在 C 和 A 之间挑一个:CP 拒绝服务保一致,AP 照常服务容忍旧数据。

到这里,本讲前半的三页讲完了「分布式系统缺什么、对网络做什么假设、怎么判断对错」。下一页回到三个「没有」的第一条:没有全局时钟,事件的先后该怎么定义。

课件里的坑

  • [说法过强] p.24 写 CAP「只能提供三个中的两个」。准确说法是:发生网络分区时,不能同时保证线性一致性 C 与所有非故障节点的可用性 A。「三选二」容易让人以为可以放弃 P。
  • [需加限定] p.26 后的讨论把比特币归为 AP,只能当作限定操作和确认语义下的类比,不能把节点暂时接受交易等同于最终确认。
  • [CA 的位置] p.26 说 CA「做不到」。更稳妥的答法:CA 只能在「不发生分区」的假设下讨论,所谓 CA 系统实际多是单机系统或假定网络永不分区的系统。

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写安全性和活性的定义各配一个例子,再默写 C、A、P 的定义;然后把下面的「变式题」做一遍;最后回查两个最容易错的地方:真的去「三选二」、以为安全性够了就行。三步做完再往下看答案。

必背

  1. 安全性(safety)= 坏事不会发生,例:两个线程不能同时处于临界区;活性(liveness)= 好事终将发生,例:每个线程最终都会进入临界区。
  2. 安全性可以被有限的执行片段证伪,活性不能被有限片段证伪。
  3. 一个永远不做任何决定的协议绝对安全,却完全没有活性,所以两者都必须要。
  4. CAP:发生网络分区时,不能同时保证线性一致性 C 与所有非故障节点的可用性 A;CA 可在不发生分区的假设下讨论。
  5. 分布式系统中分区无法避免,P 必选,真正的选择在 C 和 A 之间:CP 分区时关掉不一致的节点,AP 保持可用但可能返回旧数据。
  6. 比特币是 AP 只是限定操作语义下的类比,PBFT 类系统偏 CP,节点数不够就停下不出块。

课件例题

本讲课件没有例题(指这一页覆盖的 p.23–26)。这部分通常考三类题:给一条性质判断是安全性还是活性;准确复述 C、A、P 的定义;解释为什么 CA 在分布式环境下不存在,或者给一个系统判断它偏 CP 还是 AP。

完整例题

题面(自编):一个两节点的键值存储,分区期间收到对 N2 的读请求。分别写出 CP 和 AP 设计下 N2 的行为,并指出每种设计违反了 CAP 里的哪一项。

  1. 先确认前提:分区已经发生,N1 上 x = 2,N2 上 x = 1,两边联系不上。
  2. CP 设计:N2 知道自己可能不是最新的,拒绝这次读请求,返回「暂不可用」。没有人读到旧值,C 保住;正常节点没有回应请求,A 被违反。
  3. AP 设计:N2 照常返回 x = 1。请求得到了回应,A 保住;同一时刻 N1 和 N2 给出的数据不同,C 被违反。
  4. 两种设计里 P 都满足:系统在分区期间还在按设计运行。
  5. 分区恢复后:CP 设计里 N2 重新上线并同步到 x = 2;AP 设计里两个节点重新同步,修复不一致。

变式题(先自己做)

自编情境:下面三种说法各对不对,错在哪里?

  1. 「我们的数据库是 CA 系统,分区时既一致又可用。」
  2. 「这个协议从来没有出过错,所以它满足活性。」
  3. 「一个线程等了十分钟还没进临界区,说明活性已经被违反了。」
提示

第 1 题看 CAP 讨论的前提是什么。第 2 题想想「从不出错」对应的是安全性还是活性。第 3 题回到活性能不能被有限片段证伪。

判分点与答案

判分点:① 第 1 题要说出分区无法避免、P 必选;② 第 2 题要分清「不出错」是安全性;③ 第 3 题要说出活性不能被有限片段证伪。

  1. 错。分布式系统里分区无法避免,一旦分区就要在 C 和 A 里选一个。所谓 CA 只能在「不发生分区」的假设下讨论,实际多是单机系统。
  2. 错。从不出错说明的是安全性。一个永远不做决定的协议也从不出错,却没有活性。
  3. 错。活性只要求「最终」发生,等了很久也不能断定它永远进不去,有限的观察推翻不了活性。

闪卡自测

1. 安全性和活性各是什么?各举课件的例子。

安全性是坏事不会发生,例:两个线程不能同时处于临界区;活性是好事终将发生,例:每个线程最终都会进入临界区(p.23)。

2. 安全性和活性各自能不能被有限的执行片段证伪?

安全性能,抓到一次坏事发生就破了;活性不能,等了很久不代表永远不会发生(p.23)。

3. 为什么说「永远不做决定的协议」是一个反例?

它永远不会做出错误决定,所以绝对安全,但它什么都办不成,完全没有活性。这说明两者缺一不可(p.23)。

4. 准确复述 C、A、P 的定义。

C:所有客户端在同一时刻看到相同的数据,无论连哪个节点。A:即使存在故障,系统仍然响应客户端请求。P:节点间通信链路断开时,系统能容忍并继续正确运行(p.24)。

5. CA 系统为什么在分布式环境下不存在?

CA 要求一旦任意两节点间出现分区就得同时保住一致和可用,做不到,而分区在分布式系统中无法避免,所以所谓 CA 系统其实是单机系统或假定网络永不分区的系统(p.26)。

6. 比特币偏 CP 还是 AP?PBFT 呢?

课件把比特币作 AP 的类比:分叉时各自继续服务,靠最长链规则最终收敛;这个说法要限定操作和确认语义。PBFT 类偏 CP,节点数不够就停下不出块(p.26)。

下一讲

L02b-1 事件、割与 happens-before:没有全局时钟,就只认「沿消息链能追到」这一种先后。

下一讲 →
L02b-1 L02b-1 事件、割与 happens-before:没有统一的表,怎么排先后

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。