55 large

关于共识机制的一些想法

rink1969 · 于 发布 · 最后由 rink1969回复 · 1492 次阅读

前言

之前搞过一段时间并行计算相关的东西,写过一些Lock-Free的代码。接触以太坊社区之后,看到了共识机制的概念。当时就感觉这两者之间一定有什么联系。
刚好没几天,就在知乎上看到有一个Lock-Free的问题,下面张德力回答里面提到了:

无锁算法 (lock-free algorithm) 和 无等待算法 (wait-free algorithm) 的近代起源可以追溯到Herlihy的论文 Wait-free synchronization,1991。论文的核心在于用解决共识协议 (consensus protocol) 的能力来衡量同步原语的同步能力。

花了周末的两天的时间看了个大概,下面大概介绍一下主要内容。考虑到有些非程序员读者,我会尽量多举例来说明。

主要内容

首先论文引入一个共识数 (consensus number) 的概念,用来衡量同步原语的能力。这个概念其实很简单,就是该原语最多能处理多少个节点的共识问题。

最简单的原语,寄存器的原子操作,其共识数为1。
因为它能解决一个节点的共识问题,这个不言自明。
而它解决不了两个节点的共识问题。
举个简单的例子,我和少平吃完饭之后,争着买单。我说:我来吧。少平一把把我推开说:还是我来吧。然后我再把他推开。。。
如此下去,如果服务员耐心足够好的话,这个争论将一直持续下去,无法就谁来买单问题达成共识。

然后是 Read-Modify-Write 原语(读取寄存器的值,对其进行修改操作,然后将结果写回去)。
其共识数是2,也就是说它可以解决两个节点的共识问题。
还用买单的例子来说明:这时两个人的做法是,先把钱拿出来,放在各自面前。然后去改账单,把账单上的金额减去自己拿出来的钱(付钱),然后把余额写回去。
比如账单是100元。我和少平各拿100元放在自己面前。少平抢先拿到账单,把账单上的100改成0,我后拿到账单,把0改成-100。
这时结果就很明显了,因为少平改之前账单上的数字是最初的100,他知道他抢到了这次付账的机会。我修改之前账单上的数字已经不是100了,所以我也知道是少平抢到了这次机会。
但是这个原语无法解决两个以上的节点的共识问题。
假如还有第三个人,无论我和少平谁先谁后,第三个人拿到账单的时候,上面的值都是-100,从而无法判断少平和我之间谁抢到了这次机会。情况就又回到第一段描述的情景中。
我们可以看到RMW之所以无法解决三个人的共识问题,是因为前两个人选择的修改函数是可交换的。
如果这两个函数是不可交换的,其实是OK的。但是理论就是理论,有一点瑕疵也不行。

其实上一段的例子中有些操作是多余的,只要稍作改变,是可以解决三个人的共识问题的。
只要把修改账单上的金额,改成在账单上签名就可以了。
最开始账单上签名栏是空白的,谁先在上面签上自己的名字,就是谁买单。其他人只要看账单的签名栏是不是已经有人签名了就可以了。
而且这个规则是可以解决任意多人抢单的问题的。
这个操作其实就是大名鼎鼎的CAS原语(compare and swap),它的共识数是无穷。也就是说它可以解决任意多个节点的共识问题。
举个应用的例子,用它来实现寄存器加一操作的流程是:
1. 先获取寄存器的值,然后把这个值加一。
2. 接着执行CAS操作时会比较当前寄存器的值是不是第一步时获取的值,如果是,则执行第三步;如果不是,说明在此期间其他节点已经修改过寄存器的值,则回到第一步,重新开始。
3. 将加一之后的值写入寄存器。

还有另外一种思路来改进RMW。
我们可以看到RMW的精髓是将我和少平的争端,在账单金额的修改上安排了一次短兵相接。
只有两个人的时候,一次短兵相接,谁胜谁负就知道了。
但是三个甚至更多人的时候就变成混战了,即便最后只有一个人站着,其他人也不一定服他是第一。
更好的方式是循环赛。每个人都跟其他人打一次。把所有场次的胜负关系整理一下,胜率最高的那个人就是第一。
论文3.6节里面就是用的这个思路。
原来我理解错了,这里并不是用n个原子寄存器,而是指同时写n个寄存器是原子操作。
实际上这里用到的寄存器数目是 1+2+...+n 个,这也是n个队伍进行循环赛需要比赛的场次。
这些寄存器摆成一个斜的三角形,通过n个寄存器同时赋值,就相当于循环赛所有的场次同时进行。
这里还是有优化的余地,m个寄存器同时赋值其实可以解决2m-2个节点的共识问题。
方法是2m-2个节点两两分组,分成m-1个组。
组内先用RMW的方式决出一个优胜者。这样就只剩下m-1个优胜者,然后采用循环赛的思路,就可以得到最终胜出的人。

两层共识

一层是在不考虑拜占庭问题时,单纯的因为多节点同时读写导致的数据一致性问题。
支持多点读写的数据库也会有这样的问题,解决方法是比较序列号,以最新的数据为准。
区块链里面则是以最长链为准。大家都选择在最长的链条后面挖矿。一旦发现有更长的链条出现,马上放弃手头的工作,转换到新的最长的链条。
这个就是上面提到的CAS的思路。

另外一层是考虑拜占庭问题,节点可能因为网络延迟或者故障,甚至是主动的恶意行为,不遵循最长链的原则,导致数据出现分叉。
这时候就靠POW或POS了,大家以算力或者股权背书,赌自己认为正确的分支。
分布式数据库一般只处理简单的fail-stop故障,剩下的恶意攻击等情况,通过对节点的强管控,在外部系统中解决。

为什么需要共识

区块链技术或者更宽泛的去中心化的技术有一个很大的优势。套用网易的广告词就是:网聚人的力量。
给我印象最深的就是预言机的概念。收集大家提交的答案,通过奖罚机制,就能得到现实世界中一个客观信息的准确数据。
但是我一直在思考,区块链技术到底能从大家身上网聚到什么有价值的东西呢?
区块链作为一个公共账本,已经得到金融业的关注。预言机可以获取客观信息。
除此之外感觉应用上很受限制,没有太多用武之地。

后来我终于觉得有点相通了。
共识问题其实有点像机器学习或者统计学。
简单的例子就是调查问卷,通过对一部分人(样本)的调查,来推断一个群体(整体空间)的真实情况。
这里很严重的两个问题就是:样本偏差和模型选择偏差。
如果样本太少,或者样本没有代表性,将无法得出正确的结论。
如果对群体的概率分布有一个事先的错误判断,即使得到翔实的数据,也会对数据进行错误的解读,得到错误的结论。

这也是区块链在应用方面面临的问题。
我看到有文章质疑augur的作用,担心落入自我预言的漩涡。
解决方法,也可以借鉴统计学的一些结论。
对于样本,肯定要尽可能的多。只能拼命抢地盘啦。
对于模型的选择,这个就要具体情况具体分析了。

更长远的来看,其实是计算机网络向现实世界全方位的渗透。
最终结局就像大家说过的那样,成为终结者中的天网。

  • 1 large
    jan

    @rink1969 引用的文章读过了,很有意思

    我觉得oracle, 预测市场等可算是“整合共识”,pow/传统的pos是“竞争共识”。矿工只要算出了pow nonce就够了,不需要”整合“其他人的意见, i.e. 交易顺序可以由自己任意确定。

  • 55 large
    rink1969

    #1楼 @jan 我重读了那个论文,之前有些理解是错的,我把文章重写了一下。
    后半段感觉有点接不上,但是我觉得是可以接上的,只不过现在还没想明白。有时间一起讨论一下?

  • 55 large
    rink1969

    对了,今天之所以突然读懂了Herlihy的论文,是因为一篇名叫《并行数据对象的无等待同步实现》的中文论文。
    这篇中文论文其实就是Herlihy论文的裁剪翻译版。
    我原来理解有误,是因为没仔细看英文论文中大段的证明过程,有中文翻译很快就理解了。
    哎,真的不知道是该高兴还是难过。。。

  • 55 large
    rink1969

    最近要在内部做一次分享,准备材料的时候又对这个话题进行了一次梳理。
    文中说的两个共识应该说是两个层次的共识。
    一个层次是在不存在恶意节点的情况下,由于多点读写导致的数据一致性问题。分布式数据库里面也有同样的问题,比如二阶段提交,也是要比较提交的序列号,以最新版本为准。类似于区块链里面的选择最长链。其原理都是CAS。
    另外一个层次是如果有节点不遵循最长链原则,憋着劲就是要搞分裂。这个时候就是pow和pos起作用了,分别以算力和股权为背书,赌自己选择的链是正确的。

  • 3 large
    tomlion

    @rink1969 第二个层次是拜占庭故障。不过最长链的原则,即便没有拜占庭节点,也有问题,作为单个节点来讲,其实很难知道自己是否在最长链上,也就没法确认某笔交易被确认了。

  • 55 large
    rink1969

    另外最近在研究GC算法。发现区块链跟GC算法也能扯上关系。
    内存管理的一大问题就是内存的ownership没有记录,指针或者变量直接就可以传递了,不需要一个类似财产转移的所有权交接过程。
    导致只能使用引用计数,或者基于trace的方法来粗略判断内存是否还在使用?哪些内存可以回收?

    一个完善的ownership管理系统,编程语言理论里面叫linear type或者session type,在理论上就是很复杂的东西。
    有少数实现(比如rust),但是也非常的难用。

    区块链从表现出来的特性上说,是一个完善的ownership管理系统。
    但是不确定是不是跟linear type是等价的。

    虽然区块链提供的编程模型也挺糟糕的,但是因为软件栈层数比较多,有腾挪的余地,感觉还有点希望。

    另外反过来,不知道区块链技术是否需要GC算法?
    IPFS里面是有GC的命令的,可以把没有使用的块释放掉,节省本地存储空间。
    不知道以太坊是不是需要对uncles block做回收?

  • 55 large
    rink1969

    @tomlion 是的,这里说恶意节点有点不妥,也有非人力可控因素。

  • 1 large
    jan

    一个完善的ownership管理系统,编程语言理论里面叫linear type或者session type

    @rinkrink1969 有相关资料吗?想学习一下

  • 55 large
    rink1969

    @jan 这块儿我现在是在看 Philip Walder 的论文,就是他在haskell中引入monad的概念。
    http://homepages.inf.ed.ac.uk/wadler/topics/linear-logic.html

    我看过的有:
    《Linear types can change the world!》主要讲Linear type在函数式编程语言里面的优化的应用。
    因为纯的函数式编程语言里变量都是不可修改的,要改的话就要新复制一份。
    如果变量都是Linear type的,就是严格的只使用一次。那么实现的时候,就可以复用内存,直接原地修改,减小内存开销以及内存管理方面的开销。

    《Propositions as Sessions》 里面提出了 session type。
    并发程序之前的模型都是进程代数,比如ccs csp之类的。
    session type是对它们做了基于类型系统的建模。
    因为作者认为lambda演算以及后续的类型系统是个好东西,对程序的可计算性提供了不同层次的模型。
    所以他觉得应该有个类型系统是描述dead lock free程序的。

    实践方面,最近有人在rust上实现了session type,用于对并发程序之间的通信协议建模。
    相关论文见《Session Types for Rust》

    可以看到这方面最近的工作都是集中在并发上面的。
    但是从原始的linear logic来说,其实是关于资源管理的。
    因为经典逻辑或者作为计算机基础的直觉逻辑,对命题中是否牵涉到资源并不敏感。
    举个例子:
    有一斤面粉 -> 可以做一个面包
    一个人很帅 -> 他有女朋友
    这两个推理在经典逻辑里面都是没有问题的。
    但是两者显然存在不同。
    前一个推理中,做了面包,面粉就没有了,两者是逻辑或的关系。
    后一个推理中,那个人有了女朋友,还是很帅,两者是逻辑与的关系。

    当然并发的主要问题也是对资源的竞争,两个问题应该是等价的。

  • 55 large
    rink1969

    https://en.wikipedia.org/wiki/Linear_logic 里面有一段 The resource interpretation
    感觉把交易当做命题套进去也解释得通。

    另外这两天在看一些集群调度的资料。
    发现集群调度系统也在往去中心化的方向发展。http://www.infoq.com/cn/articles/scheduler-architectures
    以太坊的gas和将来要做的sharding,也可以认为是集群调度领域的工作。
    现在资源调度都还是计划经济的思路,如果能做到完全的市场经济,也是挺有趣的一个题目。

    GC其实也可以归类为集群调度的范畴,只不过管理的资源是单一的内存,范围也在单机上。

    根据以上的信息,个人感觉 “以交易为基础的编程模型” 应该算是一种符合 linear logic 的模型。
    之前学术界有一些基于linear logic的编程语言,包括上面提到的rust相关的那个项目,都非常的难以理解和使用。
    但是 “以交易为基础的编程模型” 至少是非常容易被理解的。

    像以太坊的solidity,感觉是不是为了图灵完备,丢失了一些 “以交易为基础的特性” ?
    因为可以写出counter之类完全不care交易发送方的程序。
    @jan

  • 1 large
    jan

    linear logic + blockchain有人在研究

  • 55 large
    rink1969

    感谢jan提供的论文 《Linear Types Can Change the Blockchain》 http://arxiv.org/abs/1506.01001
    文章将linear logic里面的连接词和区块链上的操作对应了起来。

    这里有个观点,区块链可以由更小的区块链组合而成(直接merge在一起)。当然前提是这些区块链之间没有交集。
    PS.组合是linear logic里面非常重要的概念

    文章还解释了在这种语境里面pow的含义。
    想象两条长度相等的区块链。像前面说的,如果两者没有任何交集,可以直接把他们merge在一起。
    pow就可以保证这个前提,因为如果任何一笔交易有交集,当时就合并了,就不是两条链了。
    感觉跟雷电网络的思路有点类似。

    论文里面还提出了一个脚本语言用来描述交易(在这儿语境下交易是程序)。
    In this context it means that linear proofs provide a representation of both data (blocks) and program (executable transactions) that gives several advantages over the current choices made by the blockchain.