十四个开关 · 第 12 份 · Lamport 1998 · Ongaro & Ousterhout 2014

分布式一致性开关

前十一份关掉之后,屏幕上塌的是速度或者公平。这一份关掉之后塌的是「哪个是对的」——网络一分区,两边各自选出主,各自往同一个位置写,两边都觉得自己提交成功了。开关只有一行:提交前要不要等 q 台确认

总闸

日志 · 每行一台副本,每列一个位置

一致的条目 分叉(同一位置两个值) 这台没写上(它在少数派那侧)

把 q 从 1 拖到 N · 一致性和可用性在哪儿换手

为什么是「多数」· 两个 q 元子集塞不塞得进 N 台里

关掉的是哪一行

只换一个判断:提交前等 q = ⌈(N+1)/2⌉ 台确认q = 1,本地写了就算成功。网络、分区、写入速率全不动。

⇒ N = 5、四成时间在分区、跑 4000 轮:关掉之后分叉的条目是 1597 条,占已提交条目的 39.9%——每一条都意味着同一个位置上有两个值,换成转账就是同一笔余额被两边各扣一次。用多数派:0 条。

啊哈瞬间:靠计数,不靠通信

为什么「多数」这个数是对的?因为任意两个多数派必然相交——第三屏把 N 台副本画成一条格子,两个 q 长的块想分别落在分区两侧,2q > N 时它们塞不下,必须重叠。重叠的那台副本不可能同时说两句话

N = 5、q = 3 时枚举了 55 对子集,一对不相交的都没有。⇒ 一致性不是靠消息、超时或者时钟保证的,是靠数数保证的——这一条和网络有多烂完全无关。

⚠ 我预期错了:尺子量错了对象

我原以为「可用性随 q 上升单调下降,两条线在相变点交叉」。第一次量出来的是:q = 3 时可用率还是 100.0%

因为我量的是集群可用率——只要还有一块能提交就算可用。而分区只切成两块时,多数派永远在某一侧,所以它永远是 100%。⚠ 这个数看起来完全正常,却把全部代价盖住了。换成客户端可用率(你连的那台副本所在的块能不能写)才看得见:q = 3 时是 88.1%。⇒ 问错了对象,就会量出一个漂亮的错数。

它什么时候不赢

多数派不是免费的,它拿可用性换一致性:q 从 1 到 3,分歧从 1597 掉到 0,客户端可用率从 100.0% 掉到 88.1%。⚠ 而且中间没有免费的一档:q = 2 还有 789 条分歧,可用率已经开始掉了。这就是 CAP 那句话的样子。

② 再往上更糟:q = N(等全体确认),客户端可用率掉到 60.1%——一台掉线整个集群就停写。③ 这套只挡得住网络分区和宕机;副本要是会撒谎(拜占庭故障),多数派不够用,得要 3f+1 台才能容 f 台。