浅谈 CAP 和 Paxos 共识算法作者：郑勰

作者：郑勰，腾讯 CSIG 网络产品部后台开发工程师
什么是 CAP
文章插图
关于 CAP 理论的背景介绍已经很多，这里不过多介绍，我们谈谈如何理解它的问题。
用通俗易懂的话解释三个名词：
一致性
如果刚刚向一个节点写入，那么之后，从另外一个节点读取的必须是刚刚写入的数据，不能是更老的数据。
可用性
如果请求一个节点，这个节点必须能够给予回复，如果节点挂掉了，那就谈不上可用性了。
分区容忍性
是否容忍网络分区，即可以允许节点和其它节点无法通信。
CAP 的意思就是说我们最多只能保证其中两个条件同时成立。
下面我们来看看为什么。
文章插图
如图所示，假如我们满足了分区容忍性，即虚线处表示两个节点发生了分区。

假如要满足一致性，那么，我们只能让请求另一个节点的操作暂时 hang 住，返回 client 失败或者超时的结果，这种情况多发生在银行柜台等对数据一致性要求很高的情境下，因为比起保证用户资金数目的正确性比暂时让用户无法操作要更重要一些。
假如要满足可用性，因为网络已经隔离，也就没办法达到一致性，这种情况多发生在互联网行业中，比如新闻等对数据一致性要求不高但对可用性要求高的情况下，毕竟，用户压根看不了新闻比看不到及时新闻要重要的多。

大家可以自己自由组合，最终会证明，三种条件不可能同时满足，其实大部分情况下，我们都是在一致性和可用性之间取舍而已。
Consistency = Consensus?Consistency 几乎被业界用烂，以至于当我们在讨论一致性的时候，其实我们都无法确定对方所说的一致性是不是和自己的那个一致。
【浅谈 CAP 和 Paxos 共识算法】Consistency：一致性， Consensus：协同，这两个概念极容易混淆。
我们常说的一致性（Consistency）在分布式系统中指的是对于同一个数据的多个副本，其对外表现的数据一致性，如线性一致性、因果一致性、最终一致性等，都是用来描述副本问题中的一致性的。而共识（Consensus）则不同，简单来说，共识问题是要经过某种算法使多个节点达成相同状态的一个过程。在我看来，一致性强调结果，共识强调过程。

文章插图
共识？状态机？

文章插图
Ken Thompson
共识有个更高逼格的称呼：
基于状态机复制的共识算法
那么，状态机是什么？
状态机是有限状态自动机的简称，是现实事物运行规则抽象而成的一个数学模型。
看下图，门，有两种状态，开着的和关着的。因此，在我看来状态是一种静态的场景，而转换赋予了其动态的变化。

文章插图
以此类比一下，如果一个节点当前的数据是 X ，现在有了 add+1 的操作日志来了，那么现在的状态就是 X+1 ，好了，状态（X）有了，变化（操作日志）有了，这就是状态机。
分布式共识，简单来说，就是在一个或多个节点提议了一个状态应当是什么后，系统中所有节点对这个状态达成一致意见的整个过程。
共识是过程，一致是结果。
共识模型主从同步：

文章插图
我们都知道 MySQL 等业界常见数据库的主从同步（Master-Slave Replication) ，主从同步分三个阶段：

Master 接受写请求
Master 复制日志至 Slave
Master 等待，直到所有从库返回。

可见，主从同步模型存在致命问题：只要一个节点失败，则 Master 就会阻塞，导致整个集群不可用，保证了一致性，可用性缺大大降低了。
多数派：
每次写入大于 N/2 个节点，每次读也保证从 N/2 个节点中读。多数派的模型看似完美解决了多节点的一致性问题，不就是性能差点嘛，可是在并发的情况下就不一定了，如下图：

文章插图
在并发环境下，因为每个节点的操作日志写入顺序无法保证一致，也就无法保证最终的一致性。如图，都是向三个节点inc5、set0 两个操作，但因为顺序不一样，最终状态两个是 0 ，一个是 5 。因此我们需要引入一种机制，给每个操作日志编上号，这个号从小到大生成，这样，每个节点就不会弄错。（是否想到了网络中的分包与重组？）那么，现在关键问题又来了，怎么协同这个编号？貌似这是鸡生蛋、蛋生鸡的问题。