区块链和CAP定理

微软首席架构师Yaron Goland发表文章解释了一个区块链客户端是如何基于其实现在CAP的AP或CP之间进行选择的。一个交易发生后有多少数据块记录了这项交易,越多表示系统达到广泛共识,一致性越强,从最终一致性到高一致性。

首先,需要了解一下区块链是通过共识机制实现一致性的,无论是最终一致还是强一致性。在传统分布式系统中,Paxos是实现一致性的经典算法,但是这是一种需要协调者的机制,只有大多数法定人数quorum接受读写操作才会确认,这是一种确定性强一致性(Deterministic strong consistency);但是区块链是完全非集中化的,没有中央组织来决定哪些机器有权维护区块链,这样依靠法定人数的强一致性机制无法正常工作,因为无法指定法定人数。

区块链是依靠概率强一致性(Probabilistic strong consistency)实现一致性共识的,称为Nakamoto共识(Consensus),是比特币创始人中本聪提出的。

我们知道区块链大概每10分钟会分配出一个新的区块,这是靠很多机器不断地进行哈希计算出来的,如果两组机器算力相同,它们就会创建两个不同版本的新区块,然后就各自将这10分钟内自己知道的所有交易加入到这个区块中,并且广播到自己周围,周围的节点在这区块以后再增加新的区块,形成了两条新的区块链,也就是分叉,各自有各自的树型结构,但是区块链内部机制有一个原则,选择最长的那条区块链,丢弃其他的。这个机制其实非常类似现实自由选举制,选举人在各个州获得支持,最后获得越多人支持的获胜。

Goland 在文章中解释了等待时间长度决定了是最终一致性还是强一致性,等待时间越长,一致性越高,通常是等待比特币支付24小时后再发货是稳妥的办法。

当区块链客户端在交易一加入区块链就立即接受,好处是不依赖其他节点,能够立即可用,是CAP的AP,但是风险是可能丧失强一致性,其他节点可能会丢弃这笔交易,因为其所在的区块链分叉在竞争性的选举中失败了。

为了获得CP,客户端应该等待区块链大多数节点接受了这笔交易再真正接受它,说明这笔交易所在分叉已经选举胜利,获得大部分共识,获得了强一致性,但是风险是可能不可用unavailable ,丧失CAP的A,因为网络分区通信等问题可能阻止这种共识。


The block chain and the CAP Theorem – Stuff Yaron