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
直觉
安全性像交通规则里的「红灯不能闯」:只要有一次闯了,当场就能抓现行。活性像「这辆车最终会到达目的地」:它堵在路上很久,你也不能据此断定它永远到不了,也许下一分钟就通了。
一步一步看
目标:用临界区的两段执行对照,看为什么安全性一段片段就能证伪,活性却不能。
课件用临界区举例。
-
安全性要求:两个线程不能同时处于临界区。
-
看一段执行:T1 进入临界区还没出来,T2 也进去了。重叠的那一段就是一个有限的执行片段,坏事已经发生,安全性被证伪。
-
活性要求:每个线程最终都会进入临界区。
-
看另一段执行:T3 一直在门外等。不管这段观察有多长,都不能断定它永远进不去,后面它仍可能进去,活性没法被这段片段证伪。
怎么判断
拿到一条性质,问它能不能被一个有限的执行片段推翻:
| 问题 | 能 | 不能 |
|---|---|---|
| 抓到某一刻就能说它被违反了吗 | 安全性 | 活性 |
| 典型措辞 | 「绝不」「永远不会」 | 「最终」「终将」 |
| 被违反的后果 | 永久性错误,例如双花 | 暂时只是慢,网络恢复后还能补回来 |
意思是:带「永远不」的多半是安全性,带「最终」的多半是活性;最可靠的判据仍是那个问题,看有限片段能不能推翻它。
常见误解
以为只要安全性有保证,协议就算对了
一个永远不做任何决定的协议绝对安全,因为它永远不会做出错误决定,但它完全没有活性,什么事也办不成。两者都必须要,缺一不可。
以为活性要求事情「很快」发生
活性只要求「最终」发生,不规定多快。部分同步模型下活性只在 GST 之后保证,正是利用了这一点:之前慢一点不算违反活性。
试一下
判断下面两条性质各是安全性还是活性:① 区块链上同一笔钱不会被花两次;② 用户提交的每笔合法交易最终都会被打包上链。
① 是安全性:只要在某个有限片段里看到同一笔钱被花了两次,就能判定违反。② 是活性:一笔交易等了很久还没上链,不能断定它永远上不了,只能继续等。
2. CAP 里的三个字母
它解决什么问题
分布式系统的数据会复制到多台机器上,一来防止一台坏了数据就丢,二来让各地用户就近访问。复制之后就要问:各个副本的数据一样吗?出了故障还能用吗?网络断了怎么办?CAP 把这三个问题各起了一个字母。
从哪来(补充)
CAP 由 Eric Brewer(UC Berkeley)提出:想法始于 1998 年秋,1999 年以「CAP 原理」发表,2000 年在 PODC 会议上作为猜想提出。2002 年,MIT 的 Seth Gilbert 和 Nancy Lynch 给出形式化证明,它才称为定理。
直觉
两个节点各存一份数据 x。一致性要求两份永远对得上,可用性要求随便问哪个节点都有答复,分区容错要求两节点之间的线断了系统也还能正确运行。网络好的时候三样都不难,难在线断了的那一刻。
一步一步看
目标:看网络一断,N1 和 N2 手里的 x 怎样变得不一样,为下一节的二选一摆好场景。
-
网络正常:N1 和 N2 都存着 x = 1,一边写入,另一边马上同步。
-
网络断开,出现分区。客户甲把 x = 2 写到了 N1,N1 想把新值同步给 N2,可链路断了,N2 还停在 x = 1。
-
到这一步,两份数据已经不同了。下一节看有人来 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,为什么只能在一致性和可用性之间挑一样。
-
分区还在,客户乙向 N2 读 x。
-
选 CP:N2 拒绝回答,等分区恢复再说。一致性保住了,没有人读到错的数据;可用性丢了,客户乙没拿到答复。
-
选 AP:N2 照常回 x = 1。可用性保住了;一致性丢了,客户乙读到的是旧值。
-
想两样都要,就得让 N2 既回答又答对,可它根本不知道 N1 上已经写了 2,做不到。
怎么判断
课件按 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 的定义;然后把下面的「变式题」做一遍;最后回查两个最容易错的地方:真的去「三选二」、以为安全性够了就行。三步做完再往下看答案。
必背
- 安全性(safety)= 坏事不会发生,例:两个线程不能同时处于临界区;活性(liveness)= 好事终将发生,例:每个线程最终都会进入临界区。
- 安全性可以被有限的执行片段证伪,活性不能被有限片段证伪。
- 一个永远不做任何决定的协议绝对安全,却完全没有活性,所以两者都必须要。
- CAP:发生网络分区时,不能同时保证线性一致性 C 与所有非故障节点的可用性 A;CA 可在不发生分区的假设下讨论。
- 分布式系统中分区无法避免,P 必选,真正的选择在 C 和 A 之间:CP 分区时关掉不一致的节点,AP 保持可用但可能返回旧数据。
- 比特币是 AP 只是限定操作语义下的类比,PBFT 类系统偏 CP,节点数不够就停下不出块。
课件例题
本讲课件没有例题(指这一页覆盖的 p.23–26)。这部分通常考三类题:给一条性质判断是安全性还是活性;准确复述 C、A、P 的定义;解释为什么 CA 在分布式环境下不存在,或者给一个系统判断它偏 CP 还是 AP。
完整例题
题面(自编):一个两节点的键值存储,分区期间收到对 N2 的读请求。分别写出 CP 和 AP 设计下 N2 的行为,并指出每种设计违反了 CAP 里的哪一项。
- 先确认前提:分区已经发生,N1 上 x = 2,N2 上 x = 1,两边联系不上。
- CP 设计:N2 知道自己可能不是最新的,拒绝这次读请求,返回「暂不可用」。没有人读到旧值,C 保住;正常节点没有回应请求,A 被违反。
- AP 设计:N2 照常返回 x = 1。请求得到了回应,A 保住;同一时刻 N1 和 N2 给出的数据不同,C 被违反。
- 两种设计里 P 都满足:系统在分区期间还在按设计运行。
- 分区恢复后:CP 设计里 N2 重新上线并同步到 x = 2;AP 设计里两个节点重新同步,修复不一致。
变式题(先自己做)
自编情境:下面三种说法各对不对,错在哪里?
- 「我们的数据库是 CA 系统,分区时既一致又可用。」
- 「这个协议从来没有出过错,所以它满足活性。」
- 「一个线程等了十分钟还没进临界区,说明活性已经被违反了。」
提示
第 1 题看 CAP 讨论的前提是什么。第 2 题想想「从不出错」对应的是安全性还是活性。第 3 题回到活性能不能被有限片段证伪。
判分点与答案
判分点:① 第 1 题要说出分区无法避免、P 必选;② 第 2 题要分清「不出错」是安全性;③ 第 3 题要说出活性不能被有限片段证伪。
- 错。分布式系统里分区无法避免,一旦分区就要在 C 和 A 里选一个。所谓 CA 只能在「不发生分区」的假设下讨论,实际多是单机系统。
- 错。从不出错说明的是安全性。一个永远不做决定的协议也从不出错,却没有活性。
- 错。活性只要求「最终」发生,等了很久也不能断定它永远进不去,有限的观察推翻不了活性。
闪卡自测
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:没有全局时钟,就只认「沿消息链能追到」这一种先后。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。