精华内容
下载资源
问答
  • 区块链首先是一个分布式系统,中央式结构改成分布式系统,碰到的第一个问题就是一致性的保障。很显然,如果一个分布式集群无法保证处理结果一致的话,那任何建立于其上的业务系统都无法正常工作。 一致问题 在...

    区块链首先是一个分布式系统,中央式结构改成分布式系统,碰到的第一个问题就是一致性的保障。很显然,如果一个分布式集群无法保证处理结果一致的话,那任何建立于其上的业务系统都无法正常工作。

  • 一致性问题
  • 在分布式系统中,一致性是指:对于系统中的多个服务节点,给定一系列操作,在协议(往往通过某种共识算法)保障下,试图使得他们对处理结果达成某种程度的一致。
    注意:一致性并不代表结果正确与否,而是系统对外呈现的状态一致与否,例如,所有节点都达成失败状态也是一种一致

    挑战:

    1. 节点之间的网络通讯是不可靠的,包括任意延迟和内容故障
    2. 节点的处理可能是错误的,甚至节点自身随时可能宕机
    3. 同步调用会让系统变得不具备可扩展性

    要求
    理想的分布式系统一致性应该满足:

    1. 可终止性(Termination):一致的结果在有限时间内能完成
    2. 共识性(Consensus):不同节点最终完成决策的结果应该相同
    3. 合法性(Validity):决策的结果必然是其它进程提出的提案

    带约束的一致性
    做过分布式系统的应该能意识到,绝对理想的一致性很难达成,越强的一致性要求往往意味着越弱的性能,很多时候,人们发现对一致性可以适当放宽一些要求,在一定约束下实现一致性,从弱到强有一下几种:

    1. 顺序一致性
    2. 线性一致性

  • 共识算法
    实际上,要保障系统满足不同程度的一致性,往往需要通过共识算法来达成。共识算法解决的是对某个提案,大家达成一致意见的过程。
  • 问题挑战
    实际上,如果分布式系统中各个节点都能保证以十分强大的性能(瞬间响应,高吞吐)无故障的运行,则实现共识过程并不复杂,简单通过多播过程投票即可。
    但是,现实中完美的系统不存在,如响应请求往往存在延时,网络会发生中断,节点发生故障,甚至存在恶意节点故意要破坏系统。
    一般把故障(不响应)的情况称为“非拜占庭错误”,恶意响应的情况称为拜占庭错误

    常见算法
    针对非拜占庭错误的情况,一般包括Paxos,Raft及其变种,对于要能容忍拜占庭错误的情况,一般包括PBFT系列,POW系列等等。

  • FLP不可能性原理
  • 不可能性原理:在网络可靠,存在节点失效(即便只有一个)的最小化异步模型系统 中,不存在一个可以解决一致性问题的确定性算法。
    FLP不可能原理告诉人们,不要浪费时间去为异步分布式系统设计在任意场景下都能实现共识的算法。

  • CAP原理
    分布式系统不可能同时确保一致性(Consistency),可用性(Availablity),和分区容忍性(Partition)
    1. 一致性:任何操作应该都是原子的,发生在后面的事件能看到前面事件发生导致的结果
    2. 可用性:在有限时间内,任何非失败节点都能应答请求
    3. 分区容忍性:网络可能发生分区,即节点之间的通信不可保障

    比较直观的理解,当网络可能出现分区时候,系统是无法同时保证一致性和可用性的。要 么,节点收到请求后因为没有得到其他人的确认就不应答,要么节点只能应答非一致的结 果。好在大部分时候网络被认为是可靠的,因此系统可以提供一致可靠的服务;当网络不可靠 时,系统要么牺牲掉一致性(大部分时候都是如此),要么牺牲掉可用性。

    应用场景
    既然CAP不可能同时满足,则设计系统的时候必然要弱化对某个特性的支持。

    1. 不保证一致性:对结果一致性不敏感的应用,可以允许在新版本上线后过一段时间才更新成功,期间不保证 一致性。例如网站静态页面内容、实时性较弱的查询类数据库等
    2. 不保证可用性:对结果一致性很敏感的应用,例如银行取款机,当系统故障时候会拒绝服务。Paxos、Raft 等 算法,主要处理这种情况
    3. 不保证分区容忍性:现实中,网络分区出现概率减小,但较难避免。网络通过双通道等机制增强可靠性,达到高 稳定的网络通信

  • ACID原则
    即原子性(Atomicity),一致性(Consistency),隔离性(Isolation),持久性(Durability).
    ACID原则描述了对分布式数据的一致性需求,同时付出了可用性代价。
    1. Atomicity:每次操作是原子的,要么成功,要么不执行
    2. Consistency:数据库的状态是一致的,无中间状态
    3. Isolation:各种操作彼此互相不影响
    4. Durability:状态的改变是持久的,不会失效

    一个与之相对的原则是 BASE(Basic Availiability,Soft state,Eventually Consistency), 牺牲掉对一致性的约束(最终一致性),来换取一定的可用性。

  • Paxos
    Paxos 问题是指分布式的系统中存在故障(fault),但不存在恶意(corrupt)节点场景(即 可能消息丢失或重复,但无错误消息)下的共识达成(Consensus)问题。
  • Raft
    是对Paxos的重新设计和实现,包括三种角色:leader、candiate 和 follower,其基本过程为:
    1. Leader 选举:每个 candidate 随机经过一定时间都会提出选举方案,最近阶段中得票最 多者被选为 leader;
    2. 同步 log:leader 会找到系统中 log 最新的记录,并强制所有的 follower 来刷新到这个记 录;注:此处 log 并非是指日志消息,而是各种事件的发生记录。

  • 拜占庭问题与算法
    拜占庭问题更为广泛,讨论的是允许存在少数节点作恶(消息可能被伪造)场景下的一致性 达成问题。拜占庭算法讨论的是最坏情况下的保障。
  • 又叫拜占庭将军(Byzantine Generals Problem)问题,是 Leslie Lamport 1982 年提出用来 解释一致性问题的一个虚构模型。拜占庭是古代东罗马帝国的首都,由于地域宽广,守卫边 境的多个将军(系统中的多个节点)需要通过信使来传递消息,达成某些一致的决定。但由 于将军中可能存在叛徒(系统中节点出错),这些叛徒将努力向不同的将军发送不同的消 息,试图会干扰一致性的达成。

    拜占庭问题即为在此情况下,如何让忠诚的将军们能达成行动的一致。

    Byzantine Fault Tolerant 算法
    面向拜占庭问题的容错算法,解决的是网络通信可靠,但节点可能故障情况下的一致性达成。

    新的解决思路:拜占庭问题之所以难解,在于任何时候系统中都可能存在多个提案(因为提案成本很低), 并且要完成最终的一致性确认过程十分困难,容易受干扰。但是一旦确认,即为最终确认。

    比特币的区块链网络在设计时提出了创新的 PoW(Proof of Work) 算法思路。一个是限制一 段时间内整个网络中出现提案的个数(增加提案成本),另外一个是放宽对最终一致性确认 的需求,约定好大家都确认并沿着已知最长的链进行拓宽。系统的最终确认是概率意义上的 存在。这样,即便有人试图恶意破坏,也会付出很大的经济代价(付出超过系统一半的算 力)。
    后来的各种 PoX 系列算法,也都是沿着这个思路进行改进,采用经济上的惩罚来制约破坏 者。

    OK,以上就是一些纯理论性的概念,这些也帮助我们理解区块链技术

    展开全文
  • 影响力:承诺与一致原理

    千次阅读 2014-05-20 16:55:40
    通过赌马比赛这个例子引出承诺和一致的重要性。当我们做出了某种决定的时候,往往...一个在信仰,言辞或者行为上前后矛盾的,很有可能被看做优柔寡断,是非不分,两面三刀的,高度的一致则是和坚强的个性,超凡的智

    通过赌马比赛这个例子引出承诺和一致的重要性。当我们做出了某种决定的时候,往往会倾向性的采取与我们所做的决定保持一致的行动。保持一致的愿望是我们行动的一个强大驱动力,为什么呢?在大多数的情况下,保持一致都是一种最具有适应性,最受尊重的行为,前后不一致通常被认为是一种不良的品行。一个在信仰,言辞或者行为上前后矛盾的人,很有可能被看做优柔寡断,是非不分,两面三刀的人,高度的一致则是和坚强的个性,超凡的智力联系在一起,代表逻辑性强,理性,坚定和城市。有时候保持一致的认同度比正确的认同度更高。


    来看承诺的例子:玩具商店就是用了承诺的例子来很好的保持其销售量,因为父母对孩子有承诺,因此会尽量满足这个承诺,因此即使过了圣诞节也会采取同样的措施来保证其行为和承诺一致。即使是对一些看起来微不足道的请求,我们也要保持警惕,答应这种小小的请求不仅会使我们更容易答应相似的,更大的请求,而且也会使得我们更愿意答应那些更大的,与之前小的请求无关的请求。


    关于行为的魔力:

    一个人的行为比言语更能暴漏他的真实想法,因为人们经常通过观察一个人的行为来对这个人做出判断,也会用同样的依据来判断自己是什么样的人。行为是人们用来判断自己的信仰,价值观和态度的主要依据。


    上面摘自书中的一些观点,这一章是个人觉得比较绕不太好理解的一章。先谈谈个人的理解,所谓承诺一致性就是你做出了某种承诺,并且是在没有压力没有威胁和压迫的情况下做出的承诺,那么你会尽量使得自己的行动去维护这一承诺。

    举几个日常生活中简单的例子:

    1)你谈恋爱了,家里人反对,但你不顾死活坚持自己的额想法,于是家里人让步。那么在以后的婚姻生活中你对对方的容忍和包容可能会比较多,为什么呢?因为你做了选择,这是一种承诺,你会尽量维护这种承诺,会用各种例子去证明你的选择是对的,即使有可能不对,不到万不得已,你不会承认;

    2)你买了一个东西,虽然事后证明这个东西可能不好,你心里也许这么认为,但当别人这么说的时候,你就会出来反对,或者尽量证明你当初的选择是对的;

    3)有的人很固执,一旦决定了很难回头,这也是承诺一致性的一个例子;

    因此这个原则实际上是承认人都是倾向实现承诺,言行一致的,但言行不一致的时候,其内心可能会有一种负债感。在实际生活中,你费劲千辛万苦得来的东西可能更加珍惜,同时给别人的书面承诺可能会比口头来的更有效果


    承诺一致其效果的两个条件:书面无压力情况下承诺,


    通过赌马比赛这个例子引出承诺和一致的重要性。当我们做出了某种决定的时候,往往会倾向性的采取与我们所做的决定保持一致的行动。保持一致的愿望是我们行动的一个强大驱动力,为什么呢?在大多数的情况下,保持一致都是一种最具有适应性,最受尊重的行为,前后不一致通常被认为是一种不良的品行。一个在信仰,言辞或者行为上前后矛盾的人,很有可能被看做优柔寡断,是非不分,两面三刀的人,高度的一致则是和坚强的个性,超凡的智力联系在一起,代表逻辑性强,理性,坚定和城市。有时候保持一致的认同度比正确的认同度更高。


    来看承诺的例子:玩具商店就是用了承诺的例子来很好的保持其销售量,因为父母对孩子有承诺,因此会尽量满足这个承诺,因此即使过了圣诞节也会采取同样的措施来保证其行为和承诺一致。即使是对一些看起来微不足道的请求,我们也要保持警惕,答应这种小小的请求不仅会使我们更容易答应相似的,更大的请求,而且也会使得我们更愿意答应那些更大的,与之前小的请求无关的请求。


    关于行为的魔力:

    一个人的行为比言语更能暴漏他的真实想法,因为人们经常通过观察一个人的行为来对这个人做出判断,也会用同样的依据来判断自己是什么样的人。行为是人们用来判断自己的信仰,价值观和态度的主要依据。


    上面摘自书中的一些观点,这一章是个人觉得比较绕不太好理解的一章。先谈谈个人的理解,所谓承诺一致性就是你做出了某种承诺,并且是在没有压力没有威胁和压迫的情况下做出的承诺,那么你会尽量使得自己的行动去维护这一承诺。

    举几个日常生活中简单的例子:

    1)你谈恋爱了,家里人反对,但你不顾死活坚持自己的额想法,于是家里人让步。那么在以后的婚姻生活中你对对方的容忍和包容可能会比较多,为什么呢?因为你做了选择,这是一种承诺,你会尽量维护这种承诺,会用各种例子去证明你的选择是对的,即使有可能不对,不到万不得已,你不会承认;

    2)你买了一个东西,虽然事后证明这个东西可能不好,你心里也许这么认为,但当别人这么说的时候,你就会出来反对,或者尽量证明你当初的选择是对的;

    3)有的人很固执,一旦决定了很难回头,这也是承诺一致性的一个例子;

    因此这个原则实际上是承认人都是倾向实现承诺,言行一致的,但言行不一致的时候,其内心可能会有一种负债感。在实际生活中,你费劲千辛万苦得来的东西可能更加珍惜,同时给别人的书面承诺可能会比口头来的更有效果。这就是里面提到的一个条件:书面自愿的承诺。


    第二个条件是公开承诺,因此你把一个想法埋在心里和把一个想法对你认为很重要的人先说出来之后再同时去实现这个想法,后者行动的可能性更大。


    承诺一致原理常用的一些手段:

    1)虚报低价:例如在某些购物的过程中,先虚报一个较低的价格,然后引导你填写一大推表格什么的,这实际就是承诺的一个过程,但你实现了这个承诺,然后再加上一些附加条件,通过巧妙的方式,这样,你很有可能仍然接收;


    2)登门槛原则



    展开全文
  • 另外,将从区块链中一致问题的全新视角“的可信”出发,重点阐述公有链领域中的共识算法与机制。引言分布式一致性是一个很“古典”的话题,即在分布式系统中,如何保证系统内的各个节点之间数据的一致性或能...

    摘要: 本文将从传统的分布式一致性问题说起,再次重温我们需要面对的问题挑战、已有的理论研究、以及相应的一致性算法,并简要分析这些一致性算法的适用性与局限性,以及这些传统一致性算法与崭新的区块链技术的结合。另外,将从区块链中一致性问题的全新视角“人的可信”出发,重点阐述公有链领域中的共识算法与机制。

    引言

    分布式一致性是一个很“古典”的话题,即在分布式系统中,如何保证系统内的各个节点之间数据的一致性或能够就某个提案达成一致。这个问题想必对于很多技术同学而言并不陌生,几乎在所有的分布式系统中都会遇到,比如hdfs、mq、zookeeper、kafka、redis、elasticsearch等。然而这个问题却历久弥新,随着分布式网络的蓬勃发展与复杂化,对于该问题解法的探索也一直在进行中。

    而近年来,随着区块链技术的兴起,特别是开放网络中的公有链与有权限网络中的联盟链的蓬勃发展,一致性问题再次得到关注,并从新的视角来审视该问题。

    本文将从传统的分布式一致性问题说起,再次重温我们需要面对的问题挑战、已有的理论研究、以及相应的一致性算法,并简要分析这些一致性算法的适用性与局限性,以及这些传统一致性算法与崭新的区块链技术的结合。另外,将从区块链中一致性问题的全新视角“人的可信”出发,重点阐述公有链领域中的共识算法与机制。因此,本文围绕“一致性”技术问题,重点从技术视角阐述传统计算机科学中的分布式一致性算法与区块链中的共识机制的关联,以及公有链对于一致性问题的重新思考。

    分布式一致性问题的挑战

    要清楚理解分布式一致性,首先需要对分布式网络的特性有清晰的认识。那么分布式网络具有哪些特点呢?或者通俗理解,在分布式网络中,可能遇到哪些问题呢?

    Crash Fault

    故障错误(Crash Fault)很好理解,就是说分布式网络中:

    • 节点或副本可能随时宕机、可能暂停运行但随后又恢复;
    • 网络可能随时中断;
    • 发送的消息可能在传递的过程中丢失,对方一直收不到;
    • 发送的消息可能出现延迟,过了很久对方才能收到;
    • 消息在传递的过程中可能出现乱序;
    • 网络可能出现分化,如中美集群因通信不畅,而导致整体网络分化为中美两个子网络;

    这些问题,其实就是我们在分布式环境中最常实际遇到的问题,这些问题实质上都是由于分布式系统中的物理硬件的不可靠、不稳定所带来的必然风险,比如:网络(信道)不可能是永远稳定可靠的、物理机磁盘或CPU等不可能是永远良好的。故障错误可以说是分布式系统中必须考虑并解决的最基本、最常见的一类错误。

    Byzantine Fault

    上文的故障错误,仍然基于一个很简单的假设:节点要么不正常工作或响应,要么能正常工作或响应,但不能口是心非、阳奉阴违、表里不一,即可以不干事、但不能干坏事。一旦网络中存在作恶节点,可能会随意篡改或伪造数据,那么一致性问题的难度就大幅增加。我们常把这类存在“捣乱者”,可能会篡改或伪造数据或响应信息的错误,称之为拜占庭错误(Byzantine Fault),而前面所说的故障类错误也称之为非拜占庭错误。

    拜占庭这一称呼,源于Lamport最初的论文,可以说是分布式领域最复杂、最严格的容错模型。简而言之,n个将军准备一起进攻某个城堡,每个将军都可以选择进攻或是撤退,但所有将军必须行动一致才能成功。各个将军之间相隔很远,不能直接通讯,必须通过信使来传递消息。但是信使并不可靠,信使可能过了很久才送到消息、可能一直也没有把消息送到、甚至可能会故意篡改消息;而将军也并不可靠,里面可能存在叛徒,并不按照提案来行动。显然,这个故事中的信使用来代表分布式网络中的不可靠信道,而将军就是各个不可靠的节点。


    拜占庭问题示意图(lisk.io/academy/blo…

    应对风险—Fault Tolerance

    如何在充满风险与不确定的分布式网络中,寻找到某种确定性与一致性,使得整个分布式网络输出稳定可靠的一致性结果,就是分布式一致性算法要解决的核心问题。显而易见,解决故障类错误更容易一些,通常把这类一致性算法叫做故障容错算法(Crash Fault Tolerance)或者非拜占庭容错算法。而拜占庭类错误,因为有恶意篡改的可能性存在,复杂性更高、解决难度更大,通常把解决这类问题的算法称作拜占庭容错算法(Byzantine Fault Tolerance)。

    那么我们忍不住要问,两类容错算法的界限在哪里?或者说两类错误都在什么样的场景下出现?恶意篡改这种情况真的需要考虑吗?问题的答案可能取决于我们所处的网络环境与业务场景。

    CFT

    通常而言,如果系统处于可信的内部网络环境中,只需要考虑故障容错(CFT)可能就足够了。比如我们经常见到的公司内的分布式存储、消息队列、分布式服务等各种分布式组件,其实只需要考虑故障容错就足够了。因为公司内整个网络是封闭的,又有多重防火墙的保护,外界很难接入或攻击;各个节点是由公司统一部署的,机器或运行的软件遭到篡改的可能性极小;此时的分布式网络环境相对“单纯”,我们唯一的敌人只是:通信网络与机器硬件。我们需要考虑的是网络的延迟、不稳定,以及机器随时可能出现的宕机、故障。

    BFT

    而拜占庭类错误(BFT),是把整个分布式网络放到了更大的环境中去看,除了物理硬件之外,还考虑了一些“人”的因素。毕竟,机器是不会作恶的,作恶的只有人。假如我们所处的分布式网络是较为开放的网络,比如行业内几十上百家公司组成的联盟网络;或者是完全开放的网络,比如任何人都可以随意接入到网络中;而节点机器和上面部署的软件也是由各个公司或个人自己提供和部署的,那么如果利益足够大,很可能会有人对网络中的某个节点发起DDoS攻击、故意篡改软件代码改变其执行逻辑、甚至可能故意篡改磁盘上持久化的数据。显然,我们此时面临的挑战更大了,我们除了要考虑通信网络和机器硬件的不可靠之外,还必须要考虑和应对系统中的“捣乱者”。

    不可能三角

    这些实践中遇到的问题,也引发了诸多计算科学家进行了非常多的理论研究。这些理论研究对于工程技术人员而言或许过于抽象繁琐,有些甚至是无趣的数学问题,但这些理论对于指导我们解决这些问题意义重大。这些理论相当于是告诉了我们这类问题解法的理论极限,以及哪些方向可以探索、哪些方向是死路一条。站在前人的肩膀上,才不至于花毕生精力去研制“永动机”。这些理论大家应该都有所了解,这里只简单回顾。

    FLP impossibility

    早在1985年,Fisher、Lynch、Paterson三位科学家就发表了关于分布式一致性问题的不可能定理:在完全异步的分布式网络中,故障容错问题无法被解决。(

    We have shown that a natural and important problem of fault-tolerant cooperative computing cannot be solved in a totally asynchronous model of computation.

    )说得更直白点:在异步网络中,不可能存在能够容忍节点故障的一致性算法,哪怕只有一个节点故障。并且这里并没有考虑拜占庭错误,而是假设网络非常稳定、所有的消息都能被正确传递、并且仅被传递一次,即便如此都不可能找到能容忍哪怕只有一个节点失效的一致性协议,可见该结论有多强。(

    In this paper, we show the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We do not consider Byzantine failures, and we assume that the message system is reliableit delivers all messages correctly and exactly once.

    当然了,这只是理论上的。它的意义在于告诉我们此类问题的理论极限,并不意味着此类问题在实践中也不可能被“解决”。如果我们愿意放宽限制、做出牺牲,在工程上是可以找到切实可行的解法的。

    FLP不可能定理的最大适用前提是异步网络模型。何为同步、异步模型呢?

    • 所谓异步模型,是说从一个节点到另一个节点的消息延迟是有限的,但可能是无界的(finite but can be unbounded)。这就意味着如果一个节点没有收到消息,它无法判断消息到底是丢失了,还是只是延迟了。也就是说,我们无法通过超时时间来判断某个节点是否故障。
    • 所谓同步模型,是说消息传递的延迟是有限的,且是有界的。这就意味着我们可以通过经验或采样精确估算消息的最大可能延迟,从而可以通过超时时间来确定消息是否丢失、节点是否故障。

    所幸的是,我们所处于的真实的网络世界更接近同步模型,在很多场景上,我们都可以通过经验或采样确定最大超时时间。举个通俗点的例子:你给朋友快递了一本书,朋友过了3天还没收到,此时朋友很难判断到底是快递延迟了,还是快递出问题送丢了。但是如果过了一个月,朋友仍没收到书,基本就可以断定快递送丢了。而背后的推论就是基于经验或统计:通常快递都能在1-2周内送达。显然,异步模型其实是反映了节点间通讯的最差情况、极端情况,异步模型包含了同步模型,即能在异步模型上有效的一致性协议,在同步模型上也同样有效。而同步模型是对异步模型做了修正和约束,从而使得更接近真实世界,也使得在实践中一致性问题有可能得到有效解。

    另外,即便是在异步网络模型下,FLP也并不意味着一致性永远无法达成,只是说无法保证在有界的时间(in bounded time)内达成。在实践上,如果放宽对bounded time的限制,仍然是有可能找到实践中的解法的。

    而根据DLS的研究(groups.csail.mit.edu/tds/papers/…),一致性算法按照网络模型可以分为三大类:

    • 部分同步网络模型(partially synchronous model)中的一致性协议可以容忍最多1/3的任意错误。这里的部分同步模型是指网络延迟是有界的,但是我们无法提前得知。这里的容错也包含了拜占庭类错误。
    • 异步网络模型(asynchronous model)中的确定性协议无法容忍错误。这里的异步模型即是前文所说的网络延迟是无界的。该结论其实就是FLP不可能定理的含义,在完全异步网络中的确定性协议不能容忍哪怕只有一个节点的错误。
    • 同步网络模型(synchronous model)可以达到惊人的100%容错,虽然对错误节点超过1/2时的节点行为有限制。这里的同步模型是指网络延迟一定是有界的,即小于某个已知的常数。

    从另一个角度来理解,FLP实际上考虑了分布式系统的3个属性:安全(safety)、活性(liveness)、容错:

    • 安全是说系统内各个节点达成的值是一致的、有效的。safety其实是保证系统一致性运行的最低要求,其核心是cannot do something bad,即不能干坏事、不能做错事。
    • 活性是说系统内各个节点最终(在有限时间内)必须能够达成一致,即系统必须能够向前推进,不能永远处于达不成一致的状态。liveness其实是更高要求,意味着不能只是不干坏事,也不能一直不干事,you must do something good,即必须使得整个系统能良好运转下去。
    • 容错是说该协议在有节点故障的情况下也必须能有效。

    FLP不可能定理其实意味着在异步网络中,不可能存在同时满足这三者的分布式一致性协议。因为分布式环境中,节点故障几乎是必然的,因此容错是必须要考虑的因素,所以FLP不可能定理就意味着一致性协议在能做到容错的情况下,没办法同时做到安全性与系统活性。通常在实践中,我们可以做出部分牺牲,比如牺牲一部分安全性,意味着系统总能很快达成结论,但结论的可靠性不足;或者牺牲一部分系统活性,意味着系统达成的结论非常可靠,但可能长时间、甚至永远都在争论中,无法达成结论。所幸的是,很多时候现实世界的鲁棒性很强,使一致性协议失效的倒霉事件发生的概率也很可能极低。



    FLP不可能定理示意图(www.slideshare.net/oryband/the…

    另外,FLP并未排除Las Vegas类随机算法,许多一致性算法采用了这种随机性来规避FLP不可能定理对于确定性异步网络的限制。此类非确定性一致性算法涉及Las Vegas规则:网络最终一定能达成一致,但是达成一致所需要的时间可能是无界的。此类算法每轮共识决策都有一定的概率,并且系统在T秒内能够达成一致的概率P随着时间T的增加而指数增长并趋近于1。事实上,该方法被许多成功的一致性算法所采用,是在FLP不可能定理笼罩下的安全地带(escape hatch),后面将会讲到比特币的共识机制就是采用了这样的方法。

    CAP theorem

    众所周知、大名鼎鼎的CAP原理,从另一个维度,简单明了、直截了当地告诉我们:可用性、一致性与网络分区容错性这三者不可能同时实现,而只能实现任意其中的两个。(

    "Of three properties of shared-data systems (data consistency, system availability and tolerance to network partitions) one can only achieve two at any given time".

    ) CAP与FLP看起来有相似之处,其实二者并不尽相同,二者是从不同的维度思考问题,另外即使是很相似的概念,内涵也并不完全一样。比如:

    • FLP面对的是分布式一致性问题,而CAP面对的是分布式网络中的数据同步与复制。
    • FLP是说在异步网络模型中,三者不可能同时实现;而CAP是说在所有场景下,三者都不可能同时实现。
    • FLP中的liveness强调的是一致性算法的内在属性;而CAP中的availability强调的是一致性算法对外呈现的外在属性。

    理论上,只能从CAP三者中选择两者,然而,这种选择的边界并非是非此即彼的(not binary),很多时候混合考虑不同程度的各个因素,结果可能是更好的。(

    The whole spectrum in between is useful; mixing different levels of Availability and Consistency usually yields a better result.


    CAP理论示意图(www.researchgate.net/figure/Visu…

    在实践中,我们通常需要根据实际业务场景做折中权衡。比如:

    • 传统的关系型数据库如mysql等多采用ACID(atomicity, consistency, isolation and durability)理论,通过同步事务操作保证了强一致性;因节点较少(一般只有主从),可用性也比较一般;网络拓扑较为简单,而弱化了分区容错性。
    • NoSQL存储系统如hbase等多采用BASE(Basically Available、Soft state、Eventually consistent)理论,通过多节点多副本保证了较高的可用性;另外因节点数增多、网络环境也更复杂,也考虑了网络分区容错性;但一致性较弱,只能保证最终一致性。

    ACID与BASE对比(people.eecs.berkeley.edu/~brewer/cs2…

    当然,这些并不是定论,各个系统都在各自不断的进化完善中,今天的结论明天可能就会被打破。更好的系统一定是不断探索适合自己的场景,找到更佳的平衡点。

    分布式一致性算法

    面对分布式环境中各种真实、复杂的问题与挑战,基于理论上的指引,各种应对现实问题的解法也被提出。我们这里不探究各类算法的实现细节与具体差异,仅做大体介绍,以便放到更大的维度,从整体上做比较。

    Paxos

    最大名鼎鼎的分布式一致性算法当属Lamport提出的paxos算法,虽然其复杂性也同样“臭名昭著”。Lamport开创性地提出了一种在工程实践上切实可行的、能够最大程度地保证分布式系统一致性的机制。paxos被广泛应用在诸多分布式系统中,如Chubby、Zookeeper等。在basic paxos(单一法令,即每次仅对一个值进行决策)中有两种角色:proposer可以处理客户端请求、主动提出某个议案值;acceptor被动响应proposer发出的信息、对提案进行投票、持久化存储决策过程中的值和状态。(为简化模型,可以忽略learner角色,不影响模型决策。)

    如图所示,共识决策过程采用了两阶段提交:

    • 第1阶段,广播Prepare RPC命令,即找出协议决定的最终值、阻断尚未完成的旧提案;
    • 第2阶段,广播Accept RPC命令,即要求acceptor接受共识协商出的特定值。而multi-paxos是由多个basic paxos实例组成,可以对一系列的值进行决议。

    Paxos之所以在实践中可行,其实也做了诸多假设和约束。从处理的问题上来看,Paxos仅能处理故障容错,并不难处理拜占庭错误,所以属于非拜占庭容错算法。从FLP的视角,Paxos做到了故障容错和安全性,但放弃了liveness(safe but not live),也就是说该算法可能永远无法结束,或者说永远无法达成共识,虽然这种可能性极小。从CAP的视角,Paxos只保证了CP,即做到了分区容错性和一致性,但弱化了可用性。有时为了增强paxos系统的可用性,可以考虑增加learner角色的数目。

    即便并不完美,Paxos在实践中仍然是可靠、有效且久经考验的。Paxos本质上是异步系统的分布式一致性协议,并且在该领域具有支配地位。Chubby之父甚至声称世界上只有一种一致性算法,那就是paxos(

    there is only one consensus protocol, and that’s Paxos

    ),其他一致性算法都是paxos的broken version。Paxos之所以在实践中有效是因为可能影响paxos系统liveness和可用性的条件并不容易被触发,即便真的出现,所带来的代价也可能并非是难以接受的。


    Basic Paxos RPC通信与决策过程(ongardie.net/static/raft…

    Raft

    有感于Paxos的晦涩难懂,Ongaro在2014年提出了更容易理解的Raft算法。Raft把易于理解、易于工程实现提到了很高的重要级别,甚至是raft的初心和存在理由,因而在不影响功能性的前提下,尽可能多地做了易于理解的精细设计。

    Raft算法是leader-based的非对称模型,系统中的任意一个节点在任意时刻,只能处于leader、follower、candidate这3种状态之一。初始状态所有节点都是follower状态,follower想变成leader必须先成为candidate,然后发起选举投票;如果投票不足,则回到follower状态;如果投票过半,则成为leader;成为leader后出现故障,若故障恢复后已有新leader,则自动下台,回归follower状态。

    Raft还引入了term的概念用于及时识别过期信息,类似于zookeeper中的epoch;term值单向递增,每个term内至多一个leader;若不同term的信息出现冲突,则以term值较大的信息为准。

    Raft还采用了心跳包和超时时间,leader为了保持自己的权威,必须不停地向集群中的其他节点发送心跳包;一旦某个follow在超过了指定时间(election timeout)仍没有收到心跳包,则就认为leader已经挂掉,自己进入candidate状态,开始竞选leader。

    不难发现,raft的leader选举是通过heartbeat和随机timeout时间来实现的;而日志复制(log replication)阶段是以强leadership来实现的:leader接收client的command,append到自身log中,并将log复制到其他follower;而raft对安全性的保证是通过只有leader可以决定是否commit来实现的。

    详细的竞选、复制等过程,这里不再赘述,有兴趣的同学可以参考笔者之前的文章(yq.aliyun.com/articles/67… )。值得一提的是,raft中的leader选举过程和leader任期内的正常运作过程都比较简单,复杂的其实是leader的变更过程。

    然而,虽然raft的原理机制与paxos不尽相同,但二者所解决的问题,以及所采取的折中权衡策略,可以认为是类似的。也就是说raft仍然只能解决故障错误,仍然强调了故障容错与安全性、一致性,弱化了liveness和可用性。


    Raft协议概览(ongardie.net/static/raft…

    PBFT

    自从1982年Lamport提出拜占庭将军问题之后,虽然有诸多关于拜占庭容错解决方案的讨论,但长期以来,此类问题的解决方案都效率低下、运行缓慢、复杂度过高,直到1999年Castro和Liskov提出实用拜占庭容错算法(Practical Byzantine Fault Tolerance),首次将此类算法的复杂度从指数级降到了多项式级,TPS可以达到几千,也使得节点故意作恶类问题在实践中找到了可行的解法。可以证明,如果系统内作恶节点数目不超过总节点数目的1/3,PBFT算法就能生效。

    在PBFT中,所有的节点被顺序编号,其中1个是leader,其余的都是backup。系统内的所有节点间都互相通讯,依据多数原则达成一致。PBFT中的每轮共识都被称为一个view,而在不同的view之间,leader都会发生变化;如果超过给定的时间,leader没有广播出消息,则leader就会通过view change协议被替换掉。通过这种replica timeout机制,保证了crashed或malicious leader会被检测出来,从而通过重新选举新的leader,而进入到新的view中。

    如图所示,从客户端发起请求到收到回复结果,可以分为5个阶段,而共识过程采用了3阶段协议。下面简要叙述5个阶段的大致过程:

    1. 发起:客户端(client c)向集群发起服务请求m;
    2. pre-prepare阶段:leader节点(replica 0)验证请求消息m的有效性,并在其view内为该请求m分配序列号n,并向所有backup节点(replica 1-3)广播关于该分配的pre-prepare消息;
    3. prepare阶段:backup节点验证请求消息m的有效性,并接受序列号n。若该节点同意该分配方案,则向其他所有节点广播出相应的prepare消息;这一阶段其实是要求所有replica达成全局一致的顺序。
    4. commit阶段:所有节点(包含主备)一旦收到来自集群的同意分配消息,则向其他所有节点广播出commit消息;这一阶段,所有replica已经对顺序达成一致,并对收到请求已做确认。
    5. 执行并返回:节点收到来自集群的commit消息后,执行请求m,并返回消息给客户端;客户端等到接收到来自f+1个不同节点的相同回复,则认为请求已成功执行;其中f表示集群中潜在故障节点的最大数目。这里所有节点都向client直接返回消息也是为了避免主节点在请求期间出问题。

    PBFT算法正常运作过程(www.pmg.csail.mit.edu/papers/bft-…

    PBFT基于异步网络模型做到了安全性,但需要依赖消息超时时间来做周期性的同步。因为采用了leader-based方案,消息同步过程很快,也做到了完全的顺序写入。但是leader的重新选举过程很困难,某些恶意leader可以在临近timeout窗口期时才发送消息,这样会导致系统严重缓慢。而利用这一不利特点,可以攻击网络使正确的leader看起来也出问题,从而导致无穷无尽的leader选举过程。

    PBFT与Paxos、Raft相比,所能处理应对的问题更为完备,除了能应对故障崩溃类错误之外,还能处理存在“捣乱者”的恶意篡改类拜占庭错误。然而,从所采取的折中权衡策略来看,PBFT仍然与Paxos、Raft很类似。从FLP的视角来看,PBFT同样更关注容错性和安全性,而弱化了liveness。从CAP的角度,PBFT同样强调网络分区容错与一致性,而弱化了可用性。

    即便如此,只要故障或作恶节点不超过总节点数的1/3,PBFT在实践中还是有效可行的。而拜占庭容错算法(BFT)也不止PBFT一种,BFT类算法也在不断进化,如Lamport就提出过改进版的Paxos算法BFT Paxos以处理拜占庭错误,近来也有人结合PBFT与Raft提出了 BFT Raft 算法。但从问题领域与原理机制上来说,仍然与原有的思路和框架较为类似,不再一一赘述。

    适用场景

    从Paxos、Raft到PBFT,再到目前层出不穷的Paxos变种、Raft变种、BFT类混合新算法,分布式一致性算法在不断发展、完善、进化。甚至各大公司也在结合自己的业务实际,研发各种适合自己场景的分布式一致性算法。这些算法虽然并不完美,但都在适合自己场景的业务实践中发挥着重大作用。那么这些算法的适用场景到底是什么?自身又有哪些局限性呢?

    对于Paxos、Raft这类非BFT算法而言,只能处理机器硬件故障,而无法处理存在作恶节点的情况。显然,这类非BFT算法只能运行在非常可信的网络环境中,比如公司内部网络中,在这样的较为封闭的网络中,访问需要严格授权,从而保证各个节点的身份是已知的、可信的,基本排除了节点作恶的可能性,这类算法才能有效运行。

    而BFT类算法,对于网络环境的要求不再那么苛刻,即使存在作恶节点,只要作恶节点数目不超过总节点数的1/3,整个系统依然是安全的。但问题就在于,你怎么知道网络中到底有多少作恶节点?作恶节点占总节点的比例到底有多高?显然,如果网络的接入是需要权限控制的,那么这个问题就相对容易解决。比如10家业务关联公司组成的联盟网络,只有这10家授权的公司才能访问,即便里面有个别公司(少于3家)蓄意作恶、妄图篡改数据,整个系统仍然是安全可靠的。在这种permissoned网络中,隐含着对于网络中可能作恶节点数目的预估,即便真的作恶了,也能方便快速地定位出其真实身份,间接提高了网络的安全性。

    局限性

    然而,在permissonless(开放权限、无权限控制)的公有网络中,BFT类算法很可能会有问题。因为,如果分布式网络是开放的,谁都能进进出出,而接入网络系统的成本又很低,那么没人知道网络中到底可能有多少作恶节点,即便真有作恶,也很难定位出真实身份。比如,一种比较典型的女巫攻击(Sybil attack)场景,作恶者可以通过大量伪造身份来控制集群中的大量节点,从而控制整个分布式网络。

    另外,BFT类算法最大的局限性还在于仅能协调少量的节点,如几个到几十个,若节点数目成千上万,整个系统的性能将会非常低下,甚至可能无法达成共识,从而影响系统的liveness和可用性。想必大家已经注意到,在PBFT的三阶段协议中,都需要多点广播(multicast):在pre-prepare阶段,主节点向所有备节点广播;在prepare节点,备节点向其他所有节点广播;在commit阶段,各个节点向其他所有节点广播。由此可见,通讯次数的数量级是节点数目的平方,当节点数目庞大时,这种两两广播的机制将会是灾难,系统几乎不可能在较短时间内达成一致。

    综上可知,这些传统的分布式一致性算法,无论是Paxos、Raft,还是PBFT,通常适用于存在权限控制的、节点数目较少的、较为可信的分布式网络环境中。

    在联盟链中的应用

    事实上,这些传统的一致性算法在区块链时代也焕发了新的活力,得到了进一步的认识和使用。在网络环境较为可信的联盟链场景中,这些一致性算法得到了大量的应用。联盟链因如下特点而被业内看好其应用前景:

    • 接入需授权:联盟链并不完全对外开放,一般只有几家或几十家企业组成,只有经过授权的公司或组织才能加入到网络中,并且一般是实名认证参与。
    • 数据保护:联盟链信息数据并不完全对外开放,而只有授权方可见。这对于保护行业或公司的数据安全比较重要,如跨境转账中的交易信息等对于银行业至关重要、链上税务系统中的税务信息也很敏感。
    • 可监管:联盟链中一般可以设立监管观察节点,对于敏感信息进行审计与监管,满足合法性要求。

    在当前阶段,联盟链不失为快速落地、解决行业痛点的不错选择,也是对区块链后续发展的积极探索。因为联盟链需要授权才能参与,这其实相当于已经提前建立了相当程度的信任,网络环境较为可信,网络中的恶意行为和攻击行为发生的可能性都非常低,并且即便发生也很容易快速追责。因此在这样的场景下,传统的一致性算法也可以得到应用。比如:

    Permissionless网络的挑战

    那么我们忍不住要问,如果网络是完全开放的、无需权限许可的(permissionless),谁都可以随时进出,那么整个系统还能在有限的时间内达成一致吗?如果网络中的节点数目不再是几十个,而是一万个,那么又该如何协调这些数量庞大的节点呢?

    在回答这些问题之前,其实更应该反问:为什么需要网络是完全开放、无需许可的?什么场景会需要一万个节点?这到底是伪需求,还是真实存在的场景?这个问题的答案直接关系到区块链中公有链的存在意义,而要回答这个问题,我们需要回到分布式系统的初心和目的。

    去中心化的意义

    我们为什么需要分布式系统?显然,这个问题不难回答,通常的理解,分布式系统可以增强容错能力(Fault tolerance),毕竟系统依赖众多不同的节点,而众多节点同时失败的可能性远低于一个节点发生故障的可能性;另外,分布式系统还可以抵御攻击(Attack resistance),毕竟攻击或摧毁众多节点的难度远大于攻击单点的难度。

    然而,以上这些依然是局限在物理硬件的维度,都是用来降低机器物理硬件发生故障的可能性,而没有考虑“人”的因素。如果一个系统足够重要,比如电子货币系统等,除了考虑机器故障之外,更多需要考虑的是人的因素。部署节点的人会不会故意作恶呢?如何防止系统内不同节点间的腐败串通呢?

    如下图所示,以太坊创始人Vitalik Buterin曾经深入地探讨过去中心化的含义。如果说传统的分布式系统做到了architectural decentralization(系统有多少物理机器构成?系统能够容忍最多多少台机器同时故障?),考虑的是fault tolerance和attack resistance;那么现在我们需要考虑的是如何做到political decentralization,如何能够collusion resistance? 到底有多少人或组织最终控制了系统内的节点?如何防止这些人之间的腐败串通?如果说传统的分布式系统考虑的问题是网络或机器硬件的可信,那现在我们想考虑的是“人的可信”:是否存在这样的技术手段来防范人的作恶?如何确保重要网络中的大部分节点不被一个人或一个组织恶意控制?


    去中心化的三个维度(medium.com/@VitalikBut…

    值得一提的是,这个问题的必要性依然充满争议,很多人根本不曾想过、或者认为根本没有必要考虑人的腐败串通,也可能认为对于这个问题技术也无能为力,毕竟这与我们生活的真实世界相去甚远。我们生活在一个中心化平台拥有极高声誉、提供信用背书、控制一切规则流程的世界,比如极少有人担心银行会故意做假账,侵吞你在银行的资产,毕竟大家普遍认为银行是值得信赖的。如果认为银行都不可信,那很可能一切商业活动都无法开展。

    然而,我们只是“假设”银行是可信的,在“信任”与“怀疑”之间,我们只是被迫选择了信任,毕竟不信任银行,商业活动无法开展,经济也将停滞。然而实际上,并没有切实可行的措施来向所有人“证明”银行是可信的。

    如果你认为这个问题是必要的、有意义的,那么能否找到一种解决方案,可以让这个世界变得更可信,让你不再需要“被迫相信”某个陌生人,而是提供一种“证明”,足以确保与你交易的某个陌生人是可信的?Don’t Trust, Please Verify. 你不需要相信我,你也不必相信我,你只需要去验证我。

    如果要解决这个问题,所有人的身份应该是对等的,每个人都可以平等、自由地参与决策过程,每个人都可以自由地进出“议会”,这事实上是一种技术上的democracy,隐含的技术要素是:网络必须是permissonless的,谁都可以随时加入随时离开;节点之间必须是对等的,可以直接通讯;无任何中间人,无任何中心权威存在,完全的点对点(peer to peer);每个节点都有希望成为记账者。

    因为网络无权限控制,完全的开放、透明、民主,所以参与的节点数目很可能非常众多,节点作恶的可能性也很高。那如何在这种permissionless的、节点数目众多、存在较大作恶可能的分布式网络环境中,通过某种机制协调节点间的行为,保证整个系统的一致性呢?显然,如前所述的一致性算法并不能做到这一点,我们需要寻求新的解法。

    另外,去中心化可能是区块链领域最充满争议的词汇。一些人认为去中心化是区块链的价值观和公有链的灵魂与存在前提,应该尽可能地保证系统的去中心化程度;而另一些人认为完全的去中心化过于理想、不太可能实现,应该结合实际场景,在兼顾效率的情况下考虑弱中心化或多中心化。这里抛开价值判断,单纯从技术角度理性分析,去中心化程度越高确实系统的安全性会越高,所以在公有链的系统设计中确实应该尽可能地保证系统的去中心化程度。不过,结合Vitalik Buterin对于去中心化含义的诠释,在追求去中心化的过程中,我们不应该停留在单纯的表面上看起来的去中心化,而应该综合考虑去中心化的各个维度,结合实际情况,做出必要的trade-off。

    PoW

    对开放网络中的分布式一致性问题比较创新的解法当属比特币中的Proof-of-work(PoW、工作量证明)机制。

    不得不提的Bitcoin

    2008年10月31日,中本聪发表了比特币白皮书《Bitcoin: A Peer-to-Peer Electronic Cash System》,天才般地为此类问题提供了创造性的解决思路,使得协调复杂网络环境中的成千上万节点成为可能。事实上,中本聪并不是为了解决这个技术问题而发表了比特币白皮书。相反,中本聪想象的更加宏大,他创造性地发明了比特币这种完全点对点的电子现金系统,以消除传统支付中需要依赖的可信第三方中间人,而在实现的过程中恰好依赖并解决了开放网络中众多节点间的一致性问题。也可以说,比特币所解决的最核心问题是点对点网络中电子货币的双花问题。然而,比特币的实现机制绝不仅仅是分布式网络技术问题,还结合了密码学、经济学、博弈论等思想,并以一种非确定性的概率方式实现了节点间的一致性。因此,单纯地称为算法已不太能准确表达其含义,可能叫作共识机制(consensus mechanism)更为恰当,因为其实现的确依赖了一整套的完整策略与制度。这里我们不过多阐述比特币的思想意义与实现细节,而仅聚焦在其共识机制的实现上。

    比特币实际上是电子签名链,币的owner可以通过对前一个交易的哈希值和下一个owner的公钥进行签名,并将签名添加到币的末尾,从而实现转账。接受者通过校验签名来验证币的owner构成的链。然而,问题是币的接受者没有办法确保币的owner没有进行双花(double-spend),即有可能某个币的owner将同一个币先后转给了两个人。因此我们需要一种机制来让接收者确保币的前一个owner并没有在此之前将币转给其他人,为了确保这一点,唯一的办法就是让所有人知晓所有的交易。而在无可信第三方的情况下,想实现这一点,所有的交易必须广播给所有人。因此我们需要一个系统,其中的所有参与者对他们接收币的顺序达成一致,形成唯一的顺序记录历史。不难发现,这其实就是分布式一致性问题。

    而比特币提供的方案就是需要一个由所有节点组成的时间戳服务器(timestamp server),时间戳服务器可以对交易区块的哈希加盖时间戳,并将该哈希广播出去。每一个时间戳都在其哈希中包含了前一个时间戳,从而形成一条链,而每一个新的时间戳都是对其之前所有时间戳的确保与强化。为了在点对点的网络中实现分布式的时间戳服务器,比特币采用了工作量证明机制(proof-of-work,PoW)。PoW涉及在做哈希运算时,需要寻找某个值,使得总体哈希值的开头前几位都为零,而所需要的平均工作量随着零位数目的增多而指数增加。另外,该哈希没有任何规律,为了保证开头前几位为零,只能通过暴力的方法不断地随机试错。一旦消耗了足够的CPU的算力,找到了符合条件的哈希值,则该区块就无法变更,除非再耗费CPU重做一遍。

    另外,PoW也解决了大多数决策问题。在比特币中,最长的那条链就代表了大多数的决策。因为如果诚实的节点控制了大部分的算力,则诚实的链就会快速增长并超过其他链。如果想篡改某个过去的区块,攻击者必须重做相应的区块和其后面所有区块的PoW任务,然后追赶并赶超诚实的节点。这种难度是非常巨大的,从数学上不难证明,随着后续节点数目的增多,较慢的攻击者想追赶上来的概率指数下降,一般认为经过6个区块之后,想追赶上来几乎是不可能的。另外,PoW任务的难度并不是固定的,而是用移动平均的方法动态调整的,这主要是考虑到硬件运算速率的提高和挖矿人数的增减变化,算的快就加大难度、算的慢就减小难度,通过动态调节难度使得比特币的出块时间大致稳定在10分钟左右。

    整个网络的运行过程如下:

    1. 新交易广播到所有节点。
    2. 每个节点都将收到的交易打包到一个区块内。
    3. 每个节点都为该区块不断尝试改变nonce,做PoW任务,以使得该区块的哈希符合指定条件。
    4. 一旦某个节点完成了PoW任务,则它将该区块广播给其他所有节点。
    5. 其他节点收到该区块后,验证区块内交易的有效性,验证通过则接受该区块。
    6. 节点如何表达自己接受了该区块呢?那就在添加下一个区块的时候,将该已接受区块的哈希值作为下一个区块的前一个哈希值(previous hash)。

    比特币交易过程(www.giottus.com/Bitcoin

    关于交易、挖矿等细节,这里不过多阐述,有兴趣的同学可以参考笔者之前的入门介绍文章(www.atatech.org/articles/12… )。简而言之,在比特币中总是以最长链的信息为准,若某个节点发现了比自己更长的链会自动切换到最长的链工作。

    我们忍不住要问,既然PoW成本如此之高,那如何激励大家贡献算力、成为节点,以保证整个比特币网络的安全呢?比特币中提供了两种激励策略:

    1. 挖出某个区块的节点会得到一定量的比特币,这其实也是比特币唯一的发行机制(一级市场),所有的比特币都只能通过挖矿的形式被挖出然后进入流通领域;
    2. 矿工处理交易信息可以得到一定量的手续费,这其实是存量比特币的流通(二级市场),而当比特币的2100万枚被完全挖出后,激励策略就只能依靠手续费这种方式了。

    这些激励策略也隐含地鼓励了节点保持诚实,若某个贪婪的攻击者真的拥有了过半的CPU算力,他不得不做出选择:到底是篡改交易记录,把他已经花出去的比特币再转回来呢?还是老老实实地挖矿赚钱新币和手续费呢?很可能,老老实实地挖矿是更有利的,毕竟能赚到的币比其他所有节点加起来都要多;而破坏比特币体系也将会破坏自身财富的有效性,毕竟若比特币不再可靠,其价值也会迅速崩溃。这里多提一点,攻击者并不像一般人想象的那样可以为所欲为、任意篡改或伪造交易记录,他能做的只可能是将其最近花出去的比特币偷回来。

    PoW为什么有效?

    比特币在没有任何组织或团体维护的情况下,仅仅依靠社区志愿者自发维护,稳定运行了10年之久,期间从未发生过重大问题,这不能不说是个奇迹,也足以证明了比特币背后共识机制的有效性。我们忍不住要问,为什么比特币能够做到?为什么比特币背后的共识机制能够如此有效?bitnodes数据显示目前比特币节点数目超过1万(比特币节点类型较多,不同口径数量可能不一致,这里仅考虑全节点)。为什么比特币能够在permissionless的网络环境中,协调上万的节点保持一致性?

    笔者粗浅的认为,可能有以下几个原因:

    • 有效的激励策略:通过激励策略有效地激励了更多节点参与到比特币的点对点网络中,节点越多比特币网络越安全。
    • PoW:挖矿出块需要消耗CPU算力,人为地制造障碍、增加成本,提高了攻击者的作恶成本。
    • 博弈论思想:激励策略也考虑了博弈平衡,理性节点保持诚实的收益更大。
    • 通讯效率:比特币节点间的通讯效率并不低效,大家可能注意到其中也涉及到了交易和区块的广播,不过这种广播并非是两两广播,而是由某个节点(发生交易或算出PoW的节点)将信息广播到其他所有节点。另外,交易广播并不要求触达所有节点,只要有许多节点接受,不久之后就会被打包。2014年也有Miller等人(Anonymous Byzantine Consensus from Moderately-Hard Puzzles: A Model for Bitcoin)严格证明,消息复杂度并不随网络大小而增大,而是一个常数。另外,区块广播也容许消息丢失,若某个节点未收到某个区块,则当它接收到下个区块时,会意识到自己遗漏了上个区块,而主动向其他节点请求该区块。
    • 概率性的一致性:相比其他一致性算法,比特币的共识机制最特别的是不再追求确定性的一致性,而是追求概率性的一致性。当某个区块刚被挖出的时候,其包含的交易信息并非被所有节点最终确认、其包含的数据并非是最终一致性的结果,还是有可能被攻击者篡改的;但是随着后续节点数目的增多,这种被篡改的可能性指数下降,最终一致性的概率显著增大;一旦后续节点超过6个(也就是经过约60分钟),这种一致性就可以被认为是确定的、最终的。

    显然,比特币的共识机制不再拘泥于分布式算法层面,而是包含了更多经济学、博弈论、概率论等思想,因此可能叫作共识机制更为恰当。不过,我们仍然可以将比特币的PoW共识机制放到一致性问题的框架内来思考,从FLP和CAP的角度来看:

    1. 比特币最大程度地考虑了故障容错和网络分区容错,这也是对网络openness的必要要求,因为开放网络环境极其复杂,谁都可以随时进出,节点遍布全球各地,机器故障、网络分化、系统攻击随时可能发生,容错是必须需要考虑应对的。而利用PoW机制,比特币不仅做到了故障容错,而且结合密码学非对称加密技术,也可以做到拜占庭容错,抵御恶意篡改与攻击。
    2. 比特币尽可能地保证了liveness和availability,比特币的出块时间总是在10分钟左右,这也就意味着系统总可以在10分钟内达成一致;比特币网络十年来不曾瘫痪,从这个角度来讲确实将可用性做到了极致。然而,我们必须指出,比特币的可用性与我们通常理解的互联网领域的可用性是有很大差异的。互联网领域的系统可用性,不仅要求系统稳定运行不宕机,还对服务体验如响应时间有明确要求。如果你用支付宝转账,不是随时可转、3秒到账,而是告诉你系统繁忙,需要等待10分钟、甚至30分钟,这显然会被认为服务不可用。然而,这一现象在比特币中一直在发生,比特币每10分钟一个区块,而区块大小只有1M,装不下太多交易,若同一时间交易过多,只能一直等待,直到能被下一个区块打包进去,所以经常可能需要等待20分钟、30分钟、甚至更久。从这一角度对比来看,其实比特币网络放宽了对响应时间的要求,做到了比较基本的可用性:读的可用性极高,而写的可用性很低。
    3. 比特币对于safety和consistency,不再追求确定性,而是采用了概率性的保障,基本可以认为保证了最终安全性和最终一致性,只不过这里的“最终”依然是有时间条件的、基于概率的。比如,如果我刚刚给你转账了一个比特币,没人敢说这个结果是确定的、最终的,但是随着时间的推移,不断有新的区块被挖出,我转账的交易信息也会被更多的节点确认、被更多的后续区块强化,这一结果确定性的概率不断增大,一旦过了足够的时间(如1个小时),我们从概率角度可以认为结果被篡改的可能性极低,系统达成最终一致性的概率极高,从实践上就可以认为系统保证了最终的一致性。

    综合来看,不难看出,比特币的PoW共识机制在FLP和CAP的限制下,做到了比较好的折中权衡,在实践中确实提供了开放复杂网络中分布式一致性问题的可行解法,比特币近十年来的稳定可靠运行也有力地证明了这一点。

    另外,比特币的PoW算法也被Miller等人(socrates1024.s3.amazonaws.com/consensus.p…:Anonymous Byzantine Consensus from Moderately-Hard Puzzles: A Model for Bitcoin)严谨地分析并证明:

    • 比特币网络可以看作是由近似无穷节点组成的,每个节点贡献一小部分算力,并且相应地每个节点都有较小概率可以创造区块。
    • PoW算法依赖于同步网络模型。在该模型中,若网络延迟为0,则算法可以容忍50%错误;而以目前真实观测的网络延迟来看,比特币可以容忍49.5%的错误;若网络延迟等于区块时间(即10分钟),则只能容忍33%的错误;若网络延迟接近无穷,则算法的容错也趋近于0。
    • 比特币PoW算法具有扩展性(scalable),这是因为共识时间和消息复杂度都与网络大小(网络中的节点数目)无关,而只与错误节点的相应算力有关,可以认为是一个无量纲常数。

    可见,PoW算法不仅在实践中可靠,在理论上也能经受考验。PoW算法采用了同步模型与随机概率来规避FLP的确定性异步模型不可能定理。而PoW独立于网络大小的可扩展性,与PBFT算法O(n2)复杂度相比优势巨大:节点越多,系统效率并未降低,而系统却更安全。

    PoW到底是什么?

    我们忍不住要问,PoW机制到底有何神奇之处呢?

    其实,大家可能也意识到了,PoW的思想并不高深,事实上也并非是中本聪首创。早在1993年这一思想就被提出用于对抗垃圾邮件(Pricing via Processing or Combatting Junk Mail),但直到中本聪创造比特币之前,这一思想都尚未得到广泛应用。PoW思想的精髓就在于故意制造障碍、增加参与者的成本,以尽量降低参与者的恶意企图。比如要求请求者做些额外的工作以检测DDoS攻击、垃圾邮件等,也比如最常见的登录网站需要输入验证码,也是为了增加登录成本,防止网站被攻击。这类任务最核心的特征是非对称:对于服务请求者来说,完成任务必须有一定难度;而对服务提供者来说,验证任务必须很简单快速。对于比特币PoW而言,显然符合非对称性:不断试错,寻找使哈希符合条件的nonce(随机数)需要消耗大量算力,而验证寻找到的nonce是否符合条件只需要做一次简单的哈希运算验证即可。

    比特币的PoW本质上是one-CPU-one-vote,一个CPU投一票。为什么选择CPU,而不是IP地址呢?这仍然是基于任务难度考虑,若是one-IP-one-vote,则系统可以被拥有大量IP地址的人(如ip供应商)轻易控制。相对而言,至少在当时(尚未出现ASIC和FPGA)CPU仍然是比较昂贵的硬件,想拥有大量的算力(CPU+电力)并不容易。当然,这其实也隐含地为比特币的价值提供了现实锚定:虚拟的货币体系通过算力找到了现实物理世界的价值锚定,虽然在很多人看来这种算力的消耗是毫无意义、浪费能源的。

    也有很多人提出如何降低比特币的挖矿成本,当然这种思考尝试有其积极意义,这种工作量证明的成本需要适宜:难度过大、成本过高确实浪费能源较多,不过比特币网络的安全性也得到了提高;难度过小、成本过低则会起不到防攻击的目的,进而也会降低比特币网络的安全性。这其实是一个需要做tradeoff的问题,也是一个偏主观的价值判断,取决于大众对比特币的认识和定位。价值判断总是充满了主观偏见,目前对于比特币的争论如此之大,其实也正是因为社会大众尚未达成共识,尚未构建出对于比特币未来共同一致的想象。

    简言之,比特币的PoW是一整套的机制,包含了技术上的权衡、经济和博弈的考量,这一整套的策略和机制共同保障了比特币网络的安全可靠。

    PoW机制的局限性

    凡事没有完美,PoW机制也不可例外地存在局限,其实从大家对比特币的诸多批评也可见一二,通常地大家认为PoW机制存在以下局限性:

    1. 成本过高、浪费能源:大家对比特币浪费能源的批评声不绝于耳,digiconomist数据显示,比特币的全年电力消耗基本与新西兰相当,也相当于澳大利亚用电量的1/5;而每笔比特币转账交易的成本是每10万笔visa转账交易的3倍。虽然有时候这种对比有失公允(比特币交易即清算,而visa除交易成本之外还有额外的清算成本),也有不少人并不以为然。前文也提到这其实也是一种主观价值判断,但这毕竟是一种声音,有时候也是切实的痛点,比如恐怕没人愿意用比特币买杯咖啡,毕竟手续费可能会比咖啡还贵。而罪魁祸首当然是PoW机制所需要的CPU算力消耗,因此不断有人尝试改进,甚至提出新的解决思路。
    2. 效率低下:大家习惯了互联网的便捷,习惯了秒级到账和百万级别的TPS,对于比特币交易动辄需要等待几十分钟,每秒钟仅能支持7笔交易,显然不太满意。虽然这种对比也并不公正,毕竟银行系统后台只有几个机房、最多百台机器,并且交易只进入到了其中某台机器,事后的清算环节才保证了最终一致性;而比特币无任何单点,协调的是上万台机器,并且交易即清算。不过这种效率的低下也确实是事实,也不断有人尝试改进,如把比特币每个区块的size limit调大,让其每个区块能打包更多的交易,bitcoin cash就是这么干的;再如把比特币的出块时间改小,让其更快出块,litecoin就是这么干的。但即便如此,PoW为了保证网络安全性而要求的巨大的工作量证明成本,也注定了网络的效率很难有质的提升。
    3. 中心化风险:随着ASIC和FPGA等特制挖矿芯片的出现,普通个人PC想挖出比特币几乎是天方夜谭。挖矿越来越集中到有实力研发芯片的巨头企业上,而矿池(为了平滑收益大量节点组成联盟共同挖矿、平分收益)的出现也加剧了这一趋势。另外,对比特币block size limit的调大,也会导致运行比特币全节点需要庞大的存储空间,以至于无法在普通PC上运行,而只能运行在特制的大型计算机上。这些中心化的倾向无疑都会损害比特币网络的安全性,毕竟由全世界各个角落的普通PC构成的比特币网络的安全性远远高于由几个巨头公司直接或间接控制的比特币网络。虽然这一问题的争议更大,仁者见仁,但仍然有很多人在尝试寻求新的解决思路。

    PoS

    在这些新的解决思路中,无疑最引人注目的就是Proof-of-stake(PoS、权益证明),同样面对开放复杂网络中的一致性问题,提出了全新的解决方案。

    基本思想

    2011年在bitcointalk论坛一个名为QuantumMechanic的用户率先提出了proof-of-stake的思想(bitcointalk.org/index.php?t… ),而后不断发展完善,得到越来越多人的信赖。

    PoS的基本思想大致如下:

    • 所有节点不再同时竞争挖矿,而是每次仅有1个节点做验证者:在比特币网络中,所有节点都需要做PoW任务,也就是说都需要做复杂的哈希运算而消耗大量CPU算力,而只有最先找到答案的节点才能获得奖励。这种所有节点间的同时竞争挖矿无疑需要消耗大量资源,那么是否可以每次只有一个节点工作呢?如果可以,那怎么选定这个幸运儿呢?PoS中不再需要挖矿,不再有miner,而是每次只需要选出一个节点作为validator去验证区块的有效性。如果某个节点被选为validator来验证下一个区块,它将验证该区块内的所有交易是否有效。如果所有交易都验证有效,则该节点对该区块进行签名,并添加到区块链上。作为回报,该validator将会收到这些交易相关的交易费用。显然,在PoS中每次共识只有一个节点付出了劳动,且该劳动非常轻松,从而达到了节约资源的目的。
    • 想成为validator必须提供保证金:为了防止validator作恶,想成为validator必须提前往指定账户存入代币作为保证金或抵押担保金,一旦被发现作恶,则保证金即会被罚没,而诚实工作将会得到激励。显然,只要作恶带来的收益不超过保证金额度,节点就会老老实实地保持诚实。
    • 被选为validator并不是完全随机的,而是被选定概率与提供的保证金金额成正比:例如Alice提供100个币的保证金,而Bob提供500个币的保证金,则Bob被随机选为validator从而产出下一个区块的概率是Alice的5倍。这其实就类似于股份制公司,按照出资比例来划分发言权、最终受益权等,大股东出资多、承担责任大、相应的回报也大。

    PoW与PoS对比图(hackernoon.com/consensus-m…

    不难发现,PoS也是采用了经济和博弈的思想,通过激励策略和惩罚机制来确保了网络的安全可靠。

    PoS为什么有效?

    PoS协议仍然符合传统的拜占庭容错算法研究的结论。目前围绕PoS的研究可以分为两条主线:一条围绕同步网络模型、一条围绕部分异步网络模型。而基于链的PoS算法几乎总是依赖于同步网络模型,并且其有效性与安全性可以像PoW算法一样被严格证明(nakamotoinstitute.org/static/docs… )。

    另外,从CAP的角度来看,基于链的PoS算法与PoW算法类似,也是尽可能地做到了容错性,另外在可用性与一致性之间,更多地保证了可用性。

    如果说传统的一致性算法(Paxos、Raft和PBFT)实现的是确定性的最终性(finality)或一致性,那么PoS与PoW类似,转而寻求概率性的最终一致性。从传统CAP的视角,这其实是对一致性的弱化,然而从实践可行性的视角来看,也是一种全新的思维和突破。

    而从PoS的设计策略来看,也可以分为两大阵营(arxiv.org/pdf/1710.09… ):

    • 一类是如前所述的chain-based PoS,主要是模仿PoW机制,通过伪随机地把区块创造权分配给stakeholders来模拟挖矿过程,典型代表如PeerCoin、Blackcoin等。其安全性与有效性可以参考类比pow来看。
    • 另一类是BFT based PoS,基于近30年来的BFT类一致性算法研究。基于BFT算法来设计PoS的思想最初在Tendermint中提出,以太坊2.0中的Casper也遵从了这一传统并做了一些修改完善。这类PoS的安全性与有效性可以参考BFT类算法来看,如可以从数学上证明,只要协议参与者的2/3以上节点都诚实地遵照协议,不管网络延迟有多大,算法都能保证最终状态不会出现冲突区块。不过此类算法也并不完美,特别是针对51%攻击问题,也尚未完全解决,目前该领域仍然处于开放探索阶段。

    PoS的争论

    PoS的思想并不复杂,而其中比较容易被诟病的恰恰就是这种与现实世界类似的按出资比例获取收益的制度。大家对现实世界的马太效应已经非常警惕,这种制度显然容易带来富者越富、穷者越穷的结果:拥有更多代币的人,将会有更多机会成为validator,从而参与网络并获得更多收益。

    然而,对这一问题的看法争议很大,很多人提出了完全不同的看法,认为PoS相比PoW更公平、更有助于对抗中心化趋势。理由主要是:PoW挖矿依赖现实世界的物理硬件和电力资源,而这很容易带来规模经济(Economies of scale)优势。购买10000台矿机的公司相比购买1台矿机的个人更有议价权,甚至可以自主研发成本更低的矿机;而拥有10000台矿机的矿场,对电费的议价权也更高,甚至可以搬迁到电费便宜的国家和地区的电站旁边,甚至可以自建成本更低的电站。由此带来的后果就是越庞大的组织的综合挖矿成本越低,而这正是现实世界真实已经发生的事实。相比之下,PoS不需要依赖现实硬件,不存在规模经济优势,在不考虑价格操纵的情况下,买1个币的价格和买10000个币的价格是线性增加的,从这个角度理解,PoS可能更公平,更有助于去中心化。

    对PoS的另一个担忧是其安全性,毕竟PoS不再像PoW那样做复杂的CPU运算以证明自己。在PoW中,若想发动攻击,需要控制51%的算力(近来也有研究发现只需25%算力即有可能攻击成功),这也就意味着需要拥有大部分的矿机和算力资源。而在PoS中,若想控制整个体系,需要拥有51%的代币。究竟哪个更安全?其实也不太好讲,不过可以从现实世界的例子来看,如果比特币算法切换为PoS,则控制比特币体系需要大约比特币市值的一半,大概是4001600亿美金(比特币价格区间500020000美金),显然这一数字远远高于矿机成本,想拥有这么大资金量发动攻击几乎是不可能的,从这个角度来讲,PoS可能更安全。

    除此之外,PoS因为部署成本很低(对硬件要求很低),在真实世界中会导致代币非常容易分叉,从而产生一堆山寨币,而PoW不存在这个问题。因为PoW依赖硬件挖矿,若想把比特币的某个参数改改,这很容易;但真想跑起来,则需要大量算力的支持,需要争取大量miner的支持,比如bitcoin cash从bitcoin中分叉出来就历经波折。而PoS完全没这个顾虑,随便某个人都可以下载开源代码、随意改下,拉几个节点就可以声称自己创造了一种全新的代币,比如从EOS(代币名)中可以轻易分叉出几十上百个山寨兄弟币,每个都声称自己很独特。这确实是事实,不过也不太容易说孰好孰坏。

    PoS的改进优化

    PoS机制中最关键的当属下一个区块validator或creator的选择机制,究竟谁来做这个幸运儿?前文所说的根据账户资金按比例按概率选择其实是最简单的一种方式,这种方式确实容易导致有钱人获得一劳永逸的收益,从而损害网络中其他参与者的积极性。目前有很多种思路来改善这一问题,其中比较有意思的是coin age-based方法,在选择creator的时候,除了考虑资金量,还会考虑coin age(币龄)。所谓的coin age指的是币在某个账户上的停留时间,比如1个币转入指定账户经过10天,可以认为币龄是10,而每次币发生变动币龄都会从0开始重新计算。通过这样,可以限制大资金量节点频繁成为creator,比如可以设定币龄达到30才有机会成为creator,而成为creator之后币龄立即清零。这其实是限制了大参与者的利益,为其他中小参与者提供了更多的参与机会。

    基于PoS改进的比较有名的方案当属Delegated Proof-of-Stake(DPoS),其中采用了代理人委托机制。在DPoS中不再是所有节点都有可能成为creator,而是节点间相互投票,只有得票最高的一些节点才可能参与区块创造过程。具体如下:

    • 代理人的职责包含保证自身节点持续运行、收集交易信息并打包到区块中、签名验证并广播区块、解决网络中可能存在的一致性问题。
    • 对于大多数DPoS链来说,网络中的所有持币人(token holders)都可以向代理人投票,且投票权与持币数量成正比。用户也可以不直接投票,而把投票权委托给其他人来代表他们投票。
    • 投票是动态的、可变的,意味着某个代理人随时可能被选进来或选出去。而一旦某个代理人被发现作恶或欺诈,就将失去收入和名誉,这就起到了激励代理人保持诚实、保证网络安全的目的。代理人可以将收到的区块奖励按比例分给向他投票的用户(这其实相当于贿选,在有些方案中不被允许)。
    • 不像传统的PoS,代理人不再需要持有大量的代币,而是必须相互竞争从持币者那里争取投票。
    • DPoS限制了交易区块的验证者人数,这相当于牺牲了一定程度的去中心化,但却带来了效率的提升,因为网络达成共识所需的工作量大幅降低。

    DPoS选举validator/witness过程(www.nichanank.com/blog/2018/6…

    不难发现,DPoS通过引入投票机制,尽可能地保证了节点的广泛参与;而对validator数目的限制(一般是21-101个),尽可能地提高了系统的运行效率。虽然充满很大争议,DPoS仍然不失为一种可行的解法,越来越多的区块链系统也在尝试对其进行改进和探索。

    在公有链中的应用

    在公有链中,众多项目都采用了PoS机制,比较有名的有:

    • 以太坊(Ethereum:www.ethereum.org/ ):目前阶段以太坊仍然采用的是PoW挖矿机制,不过作为以太坊的创始人和公有链领域的领军人物Vitalik Buterin对于PoS机制显然更为青睐,也多次阐述过PoS的设计哲学(medium.com/@VitalikBut… ),以及PoS相比PoW的优势(github.com/ethereum/wi… )。目前以太坊正在开发基于PoS的Casper协议(arxiv.org/pdf/1710.09… ),预计将于今年下半年发布,这种从PoW到PoS的转变也标志着以太坊进入2.0时代。如下图所示,在以太坊2.0 phase0阶段,将会发布采用Casper协议的PoS beacon chain,作为coordination layer(github.com/ethereum/wi… )。

    以太坊2.0 layers和phases(docs.ethhub.io/ethereum-ro…)

    • EOS(eos.io/ ):作为DPoS思想的提出者Daniel Larimer发起了EOS公有链项目,其中众多节点会一起竞争,期望成为拥有记账权的21个Supernodes中的其中一员。这种类似现实世界议会制度的设计引起了非常大的争议,而超级节点的竞选也可能蕴含着巨大的商业利益,这些都已经超越了技术讨论的范畴,在此不做过多讨论。

    Proof of X?

    其实,PoS机制的兴起除了其本身具备的低成本、高效率、去中心化等特点之外,还在于它打开了一扇新的大门——基于博弈论机制来设计如何降低中心化风险的一系列技术,如何预防中心化垄断巨头的形成,以及在已有巨头的情况下如何防范它们损害网络(

    Proof of stake opens the door to a wider array of techniques that use game-theoretic mechanism design in order to better discourage centralized cartels from forming and, if they do form, from acting in ways that are harmful to the network

    )。

    而随着近年来区块链(特别是公有链)的蓬勃发展,其他各种Proof of机制也层出不穷。从这里面的诸多机制中都可以看到PoS思想的影子,即如何从经济角度和博弈视角来设计制度尽可能地保证去中心化、安全性与高效率。下面对这些机制做简要说明:

    • Leased Proof of Stake:持币量非常低的众多节点可以将代币出租给其他节点,从而形成合力,增加成为validator的几率;而一旦选举胜出得到奖励,则按比例分配手续费,其实与矿池的思想比较类似。
    • Proof of Elapsed Time:所有节点都必须等待一定的时间才能成为记账者,而等待时间是完全随机的。而要想保证公平,核心的两个问题是:如何保证等待时间确实是完全随机的?如何保证某个节点真的等待了指定的时间?目前的解法依赖于Intel的特殊CPU硬件Intel SGX 系统,目前通常也仅能应用在permissioned网络环境中,如前所述的以太坊企业联盟EEA中。
    • Proof of Activity:PoA同时结合了PoW和PoS的思想。在PoA中,起始过程与PoW类似,仍然是miners间竞争解题挖矿,只不过所挖的区块仅仅包含头信息和矿工地址。而一旦区块被挖出,则系统自动切换成PoS模式,区块头信息指向一个随机的持币者(stakeholder),由该持币者来验证该pre-mined区块。
    • Proof of Importance:有感于PoS机制倾向于鼓励人持币而不是流通、也容易导致富者越富的问题,PoI在计算节点对系统的重要性上吸纳了更多的维度:除了考虑币的数量、币在账户上的停留时间之外,还考虑了交易对手(与其他账户的净交易越多分数越高)以及最近30天交易数目和大小(交易越频繁、数额越大分数越高)。
    • Proof of Capacity:也称作Proof of Space,思想与PoW类似,只是不再以CPU算力为衡量标准,而是以存储空间来衡量。
    • Proof of Burn:矿工必须烧毁一定量的代币,即将一定量的代币转入eater address(黑洞地址,只进不出,即私钥未知的地址),以此来证明自己。本质上与PoW的思想接近,只是工作量证明消耗了算力资源,而PoB直接消耗了代币本身。
    • Proof of Weight:PoWeight是在PoS考虑代币量的基础之上,增加考虑了更多的权重因子。比如FileCoin(IPFS分布式文件系统上的代币)考虑了你拥有的IPFS数据大小;其他的一些权重因子也包含但不限于Proof-of-Spacetime、Proof-of-Reputation等。

    一致性算法概览(101blockchains.com/consensus-a…

    不难发现,虽然这些Proof-of机制层出不穷、不尽相同,但其要解决的核心本质问题是相同的,即:让谁来成为能够记账的幸运儿?这些Proof-of机制只不过是采取了各种不同的策略来制定游戏规则,让各个节点尽可能公平地证明自己,从中公平地选出幸运儿。所有这些策略,包括基于CPU算力、持有代币数量、存储空间大小、随机等待时间、销毁代币数量、节点活跃度、节点贡献度等,都是在特定的场景下对于开放网络中一致性问题的探索。

    一切关乎信任

    从PoW到PoS,再到Proof of "Everything you can think",对于permissionless网络中的一致性问题一直在探索中。“一致性”的内涵也在发生变化,从传统的如何防范网络与机器硬件的故障,保证网络节点间的数据一致性,到开放网络中,如何防范网络中人的作恶,保证网络中节点数据间的真实一致。可以说是从硬件的可信,迈进了“人的可信”,公有链技术也被视为“信任的机器”。不过显然,人的可信问题过于复杂,甚至也超越了单纯的技术范畴。目前阶段所能做到的也远远未能保证“人的可信”,更多的仍停留在人对于机器的信任、人对于“协议”的信任。不过可喜的是,我们终于迈出了这一步,开始直面这个棘手的问题,探索创新性的解法。


    信任的机器(www.economist.com/leaders/201…

    总结

    这个世界充满了不确定性,计算机科学也一样。从计算机出现开始,我们就不得不面对机器硬件的不确定性:意外故障可能带来的问题。从互联网兴起开始,我们就不得不面对网络的不确定性:通讯消息可能的延迟、乱序、丢失。而应对不确定性问题最自然的解法就是冗余,通过大量节点来实现系统整体的安全性,避免单点故障,增强容错能力和抵御攻击的能力。正是基于此,才带来了大型分布式网络的蓬勃发展,而如何在不确定的网络和节点间寻找到某种确定性,协调众多节点间的一致性,正是分布式一致性算法需要解决的问题。能够应对故障类错误的CFT算法包括最经典的Paxos算法和更简单的Raft算法,可以在网络中正常节点超过一半的情况下保证算法的有效性。这类算法通常应用在环境可信的封闭网络中,协调几个到几十个节点间的一致性,如公司内部的分布式存储、分布式服务协议、分布式消息系统等。另外,也可以应用于由少数机构组成的需要授权才能访问的联盟链网络中。

    然而,不确定的不止是网络与机器本身,还有控制网络中各个节点的人的行为。如何在可能存在捣乱者恶意篡改数据或攻击网络的情况下,保证分布式网络的一致性,正是拜占庭容错类算法BFT需要考虑的问题。BFT类算法中最常见的就是PBFT算法,可以在网络中正常节点超过1/3的情况下保证算法的有效性。即便如此,PBFT对于网络中恶意行为的应对能力仍然是有限的,另外其性能也会随着网络中节点数目的增多而显著下降。这些局限性也导致PBFT算法仅能用于环境较为可信的、有权限控制的网络中,协调几个到几十个节点间的一致性,比如联盟链场景中。

    而在无权限控制的permissionless开放网络中,不确定性更加严峻,特别是网络节点背后的人的行为的不确定性。如何防止网络中的控制人之间通过腐败串通组成寡头,从而控制网络中的过半节点,达到控制、损害、攻击网络的目的,即是开放网络需要考虑的问题。从这一角度看,开放网络中的一致性还隐含了安全性的前提:即不仅要求节点间能够达成共识,还要求该共识确实是由节点众多控制人真实表达而形成的。而为了达到这种一致性与安全性,不仅需要实现物理硬件节点在结构上的decentralization,还需要尽可能地保证节点背后实际控制人的decentralization。为了实现这一点,需要保证任何人都可以随时部署运行网络协议而成为网络中的节点、可以随时进出网络;节点之间点对点通讯,无任何中心化控制节点;节点的角色是完全对等的,按照规则有公平的可能性参与记账。而如何协调开放网络中数量庞大的上万个节点间的行为,保证网络的一致性与安全性,即是公有链共识机制要解决的问题。其中,最典型的当属比特币首创的基于工作量证明的PoW共识机制,以及随后兴起的基于权益证明的PoS共识机制。这些共识机制不再局限于技术上的一致性本身,而是更多地引入了经济学和博弈论的思想,从经济和博弈的角度尽可能保证网络的一致性与安全性。

    从传统的封闭分布式网络环境中的一致性,到有权限控制的联盟链场景中的一致性,再到无权限控制的公有链开放网络环境中的共识机制,面对的问题越来越复杂,应对的挑战也越来越严峻。从单纯的技术视角来看,其中对于consensus的研究是一脉相承的,这些一致性算法或共识机制同样也都受到传统分布式一致性理论研究中FLP impossibility和CAP theorem的制约。Paxos、Raft和PBFT都强调了fault tolerance与safety/consistency,而弱化了liveness与availability。而PoW与PoS则采用了全新的视角来考虑该问题,尽可能地保证了fault tolerance,以及liveness与availability,放弃了对于安全性与一致性确定性的追求,而仅仅以概率性的方式追求最终的safety与consistency。

    另外,对于consensus的思考,也在不断深入,从单纯的节点间的数据一致性,到强调节点背后的人之间的共识与认同;从保证网络与硬件的可信,到尽可能地确保组成网络的节点背后的人的可信。虽然人与人之间的可信非常复杂,也超越了单纯的技术范畴,可喜的是我们已经走在路上,而目前在该领域正在进行的创新性的积极探索,也必将让世界变得更加可信。

    注:本文篇幅较长、写作时间跨度较长、本人水平也有限,所参考资料可能有疏漏或个人理解偏差,欢迎大家指正、讨论、交流、建议,后续将进行更新。

    参考资料

    1. An Overview of Blockchain Technology: Architecture, Consensus, and Future Trends
    2. 101blockchains.com/consensus-a…
    3. Comparative Analysis of Blockchain Consensus Algorithms
    4. draveness.me/consensus
    5. yeasy.gitbooks.io/blockchain_…
    6. citeseerx.ist.psu.edu/viewdoc/dow…
    7. dba.stackexchange.com/questions/1…
    8. www.quora.com/What-is-the…
    9. ug93tad.github.io/flpcap/
    10. ramcloud.stanford.edu/~ongaro/use…
    11. en.wikipedia.org/wiki/Paxos_…
    12. www.pmg.csail.mit.edu/papers/bft-…
    13. www.youtube.com/watch?v=M4R…
    14. medium.com/codechain/s…
    15. www.cs.utexas.edu/~lorenzo/co…
    16. disi.unitn.it/~montreso/d…
    17. eprints.soton.ac.uk/415083/2/it…
    18. www.scs.stanford.edu/14au-cs244b…
    19. people.cs.umass.edu/~emery/clas…
    20. lamport.azurewebsites.net/tla/byzsimp…
    21. blockonomi.com/practical-b…
    22. medium.com/@VitalikBut…
    23. bitcoin.org/bitcoin.pdf
    24. en.wikipedia.org/wiki/Proof-…
    25. bitnodes.earn.com/
    26. Data Consistency and Blockchain
    27. www.mangoresearch.co/understandi…
    28. cryptographics.info/cryptograph…
    29. paulkernfeld.com/2016/01/15/…
    30. digiconomist.net/bitcoin-ene…
    31. www.economist.com/the-economi…
    32. www.youtube.com/watch?v=M3E…
    33. www.wisdom.weizmann.ac.il/~naor/PAPER…
    34. bitcointalk.org/index.php?t…
    35. lisk.io/academy/blo…
    36. medium.com/loom-networ…
    37. www.youtube.com/watch?v=Qfm…
    38. lisk.io/academy/blo…
    39. www.slideshare.net/oryband/the…
    40. www.slideshare.net/sharkag/con…
    41. fenix.tecnico.ulisboa.pt/downloadFil…
    42. people.eecs.berkeley.edu/~brewer/cs2…
    43. www.infoq.com/news/2008/0…
    44. www.giottus.com/Bitcoin
    45. www.nichanank.com/blog/2018/6…
    46. en.bitcoinwiki.org/wiki/DPoS
    47. cryptographics.info/cryptograph…
    48. tokens-economy.gitbook.io/consensus/c…
    49. www.investopedia.com/terms/p/pro…
    50. www.investopedia.com/terms/p/pro…
    51. www.mycryptopedia.com/proof-of-im…
    52. en.wikipedia.org/wiki/Proof-…
    53. en.bitcoin.it/wiki/Proof_…
    54. hackernoon.com/a-hitchhike…
    55. github.com/ethereum/wi…
    56. socrates1024.s3.amazonaws.com/consensus.p…
    57. groups.csail.mit.edu/tds/papers/…
    58. en.wikipedia.org/wiki/Las_Ve…
    59. bitcoinmagazine.com/articles/se…
    60. medium.com/mechanism-l…
    61. medium.com/@marchionni…
    62. pdfs.semanticscholar.org/da8a/37b10b…
    63. www.infoq.cn/article/5-c…
    64. medium.com/@micobo/tec…
    65. medium.com/newcryptobl…
    66. docs.corda.net/design/kafk…
    67. hyperledger-fabric.readthedocs.io/en/release-…
    68. www.hyperledger.org/wp-content/…
    69. medium.com/coinmonks/h…
    70. medium.com/kokster/und…
    71. fenix.tecnico.ulisboa.pt/downloadFil…
    72. hyperledger-fabric.readthedocs.io/en/release-…
    73. entethalliance.org/wp-content/…
    74. medium.com/@VitalikBut…
    75. github.com/ethereum/wi…
    76. docs.google.com/presentatio…
    77. arxiv.org/pdf/1710.09…
    78. arxiv.org/pdf/1607.01…
    79. en.bitcoinwiki.org/wiki/DPoS
    80. amplab.github.io/cs262a-fall…
    81. www.the-paper-trail.org/post/2012-0…


    本文作者:海阔 山遥

    原文链接

    本文为云栖社区原创内容,未经允许不得转载。


    转载于:https://juejin.im/post/5cd91fbff265da03555c9e65

    展开全文
  • 分布式一致性协议

    千次阅读 2015-04-21 15:17:20
    分布式一致性协议 Amir H. Payberah 《Distributed Systems Consensus》 amir@sics.se  Amirkabir University of Technology 问题是什么? 为保证分布式系统的高可靠和高可用性,数据在系统中一般存储多个...
    分布式一致性协议
    
    Amir H. Payberah  《Distributed Systems Consensus》
    amir@sics.se 
    Amirkabir University of Technology

    问题是什么?
    为保证分布式系统的高可靠和高可用性,数据在系统中一般存储多个副本。当某个副本所在的节点出现故障时,分布式系统能够自动将服务切换到其他的副本,从而实现自动容错。同一份数据的多个副本中往往有一个副本为主副本,其他为备副本。从一份数据的角度讲,主副本所在的节点为主节点,备副本所在的节点为备节点。但在整个系统范围上看,每个节点即是主节点,也是备节点。

                     
    由于同一份数据在整个系统中存在多个副本,因此需要解决如何保证多个副本的一致性问题,以及当主节点出现故障时,如何从多个备节点中选举新主节点的问题。
    为解决这些问题,需要做到:
    • 使主副本数据状态是确定的(状态机)
    • 复制主副本数据到其他备节点
    • 确保数据状态的改变以相同的顺序被复制到备节点上,保证得到正确的数据副本。
    采用什么协议成了关键点。

    一致性协议问题
    多个节点间的一致性协议过程,简单来讲就两步:
    • 某些节点提出建议值( 或者行动),并发送给其他节点;
    • 所有节点必须决定接受还是拒绝这个建议。
    但是,理解是丰满地现实却是骨感......:
    • 并发进程时间、事件和输入的不确定性;
    • 机器/进程的故障与恢复,通讯渠道的故障与恢复。

    一致性协议要求
    1. 安全性
    • 有效性:在被提出的建议值中,只有一个可以被选定
    • 一致性: 没有任何两个确定的节点选择不同的值
    • 完整性:一个节点最多只能选择一次
    2. 存活性
    • 可终止性: 每个确定的节点,最终都会选择一个值

    分布式系统协议:可能的解决方案
                
    • 两阶段提交(2PC)协议
    • Paxos协议
    (最近Raft协议又在坊间流传、使用,据传说比Paxos协议简单,当然有效是必须地。具体情况,我们接下来再聊。)


    两阶段提交(2PC:The Two-Phase Commit)

    两阶段提交(2PC)问题
    • 此问题首先是在数据库系统遇到;
    • 假设数据库系统正在更新某些复杂的数据结构,此数据结构由保存在多台机器上的多个部分组成;
    • 系统模型:
      • 并发进程时间、事件和输入的不确定性(异步系统);
      • 机器/进程的故障与恢复,通讯渠道的故障与恢复。

    一个直观的例子
                   
    • 你想跟三个朋友星期二下午6点组织郊游, 只有所有人都同意才能出行
    • 你怎么做呢?
      • 打电话给每个人,问他们星期二下午6点是否可行?(投票阶段voting phase
      • 如果所有人都觉得时间可以,打电话给每个人,告诉他们事已确定;(提交commit
      • 如果有人说没时间去不了,打电话给其他三人,告诉他们出行取消。(中止abort
    • 关键细节:
      • 当你打电话给每个人询问时,凡是承诺promised)周二下午6点能行的人,必须留出时间must reserve that slot);  
      • 你需要记下这些决定remember the decision),然后在提交/中止阶段告诉每个人 tell anyone):谁哪没有达成。
    • 这正是两阶段提交是如何工作的。

    两阶段提交(2PC)中的角色
    • 协调者Coordinator(事务管理器Transaction Manager
      • 开始事务;
      • 负责提交/中止(commit/abort)事务。
    • 参与者Participants(资源管理器Resource Managers)
      • 分布式事务中的数据服务器。

    两阶段提交(2PC)算法
    阶段1 - 准备prepare阶段
    • 协调者Coordinator) 询问每个参与者participant能否提交canCommit)?
    • 参与者Participants) 必须为提交commit) 数据修改到持久化存储storage)做好准备,然后才能回复“yes“。
      • 锁定Lock) 涉及到的数据对象。
      • 参与者在对协调者Coordinator) 能否提交canCommit)询问回复“ yes”后,不允许not allowed)引发事务中止abort)。
    • 这时事务的结果还是不确定的uncertain) ,这种状态一直持续到最终事务提交doCommit)或者事务中止doAbort)。
      •  其他参与者Other participants) 仍有可能引发中止abort)。   
    阶段2 - 提交commit阶段
    • 协调者coordinator 汇集所有投票all votes)。
      • 如果全体一致地投票“ yes”(unanimous yes), 则引发提交。
      • 如果任一参与者投票 no”(any participant voted no), 则引发中止。
    • 一旦所有参与者participants)全部投票完毕,事务的命运由协调者 coordinator自动atomically)决策。
      • 协调者使用持久化存储permanent storage)记录最后决策。
      • 然后向参与者广播broadcasts)决策:事务提交 doCommit) 或者事务中止doAbort)。
    两阶段提交(2PC)事件时序
                

    两阶段提交(2PC)的恢复
    主要的恢复类型
    • 在处理超时后恢复。
    • 在系统崩溃重启后恢复。
    • 在一个弹性的异步网络环境中,不能区分上面的这两个情况。

    超时处理
    • 避免进程永久阻塞情况发生
    • 两种阻塞场景:
      •  协调者Coordinator ) 等待参与者 participants的投票。
      • 参与者Participant)等待最终决策  final decision)。

    协调者超时处理
         
    • 如果B投票no”,协调者能否单方面中止事务?
    • 如果B投票yes“,协调者能否单方面中止/提交事务?
      • 协调者等待参与者投票
      • 参与者等待最后的决策
      • 协调者超时后中止,并且发送事务中止doAbort)给参与者。

    参与者超时处理
                
    • 如果B与事务管理器(协调者)间超时,并且已经回复协调者投票” yes“,那么执行终止协议
    • 简单终止协议Simple protocol): 参与者保持阻塞remained blocked) ,直到与协调者重新建立通讯。
    • 协作终止协议Cooperative protocol): 参与者发送一个决策请求decision-request)消息给其他参与者other participants)。比如:
      • B发送状态消息给A
      • 如果A已经从事务管理器(协调者)收到事务提交/事务中止(commit/abort)指令, ...    
      • 如果A还未投票给事务管理器,A如果还没决定,那它也没法帮到B,A如果单方面决定abort,那它可以回复B一个aboort,B执行相应操作。
      • 如果A已经投了yes,但还未收到事务管理器的决定,那A无法帮到B;
        如果A已经投了no,那A可以回复B一个abort,B执行相应操作。

    崩溃处理与恢复
    • 所有节点必须把协议进展记入日志log protocol progress)。
      •  参与者Participants):prepared->uncertain->committed/aborted
      •  协调者Coordinator):prepared->committed/aborted->done 
    • 如果已经决策提交事务commit is decided),所有节点不能再退出( cannot back out )
    • 协调者Coordinator)崩溃,恢复时: 
      • 如果从磁盘日志中未找到提交no commit ),那么进行事务中止过程aborts)。
      • 如果从磁盘日志中找到提交( commit),  那么进行事务提交过程(commits)。 
    • 参与者Participant) 崩溃: 
      • 如果找到事务提交commits)或者事务中止aborts)记录,表明在崩溃前已经达成决策,进行相应处理即可。
      • 如果从磁盘日志中未找到yes投票no yes),那么进行事务中止过程(aborts)。
      • 如果从磁盘日志中找到yes投票 yes),那么运行终止协议(termination protocol )来达成决策。  

     2PC容错局限性
    • 即使启用了恢复机制,两阶段提交也达不到真正的容错fault-tolerant),因为当有一个(或几个)机器故障fail),可能会被阻塞blocked )
    • 阻塞意味着故障期间处理不会有进展。(not make progress during the failures)。
    • 来个场景秀一下? 

    2PC阻塞场景
               
    • 事务管理器发达事务提交doCommit决策到A,A收到后进行提交处理,然后事务管理器和A都死掉(both TM and A die)。
    • B、C、D同样也已经回复投票yes, 并且锁定了locked)它们本身的一些互斥锁,那么现在需要等待事务管理器或A活过来。
    • 没有确定的决策,他们不能进行恢复动作(cannot recover),直到事务管理器或者A重新在线。
    • 这就是为何两阶段提交(2PC)被叫做阻塞式协议(blocking protocol):2PC是安全的,但不是具有活性的。 

    Paxos协议

    唯一已知完全安全(completely-safe) 巨大活性largely-live)的一致性协议.

    Paxos协议中的角色
    • 提议者(Proposers
      • 提出提案值供投票者考虑。
    • 投票者(Acceptors) 
      • 考虑提议者提出的提案值。
      • 回复一个批准/拒绝决策。
    • 学习者(Learners  
      • 学习已经通过的提案值。
    • 一个节点能扮演一个以上的角色

    单个提案Proposal,单一投票者(Acceptor)
               
    • 只使用一个投票者acceptor)。
      • 收集多个提议者Proposers提案 proposals 
      • 决定通过的值,告知其他所有人。
    • 听起来熟悉吗?
      • 两阶段提交2PC)。
      • 投票者(acceptor)故障 协议阻塞

    单个提案(Proposal),多个投票者(Acceptor)
               
    • 单一投票者不能充分地容错
    • 让我们设置多个投票者acceptor)。
    • 必须达成一个决策,如何做
    • 决策 = 被大多数批准的值
    • 原则1:一个投票者(acceptor)必须批准所收到的第一个提案(proposal)
      • 原则1a:当且仅当投票者(Acceptor)没有收到编号大于n的Prepare请求时,投票者(Acceptor)批准编号为 n的提案(Proposal)。

      多个提案Proposal,多个投票者(Acceptor)                  
              
    • 如果有多个提案multiple proposals没有提案no proposal能得到多数票majority
    • 如图,3个提案,每个可能获得1/3的投票者。
    • 解决方案:投票者能批准多个提案accept multiple proposals,通过一个唯一的提案编号unique proposal number区分。

    多个提案Proposal的处理
    • 所有被通过的提案chosen proposals)必须是相同的提案值the same value)。
    • 原则2:如果一个提案的值v被通过,那么之后被通过的每个更高编号的提案,必须具有相同的提案值
      • P2a:一旦一个值v被通过,那么之后任何投票者(Acceptor)再批准的值必须是v。
      • P2b:一旦一个值v被通过,那么以后提议者(Proposer)提出的新提案必须具有值v。
      • P2c:如果一个编号为 n 的提案具有值v,那么存在一个多数派,要么他们中没有人批准过编号小于 n的任何提案,要么他们进行的最近一次通过具有值v。

    Paxos算法
    • 阶段1a - 准备(Prepare)
      提议者(Proposer) 选择一个提案编号 N,并将包含了该编号的Prepare(N)请求,发送给所有投票者(Acceptor) 中的一个多数派(majority);
    • 阶段1b - 承诺(Promise)
      投票者(Acceptor) 收到 Prepare (N)消息后,当N大于所有它以前承诺过(promise)或收到Preapare请求的编号
      •  承诺不再批准编号小于N的提案,
      • 发送响应promise(N,U)U是上次批准的最大编号提案(如果有的话)。
    • 阶段2a - 请求批准(Accept!)
      如果提议者(Proposer) 收到了多数派的响应,向这些回复 Prepare(N) 请求的投票者(Acceptor),发送Accept(N,V)请求,V是收到的promise响应中最大编号提案的值,如果没有promise包含提案,那么可自由定值。
    • 阶段2b - 批准(Accepted)
      如果N大于等于任何已经承诺过(proimise)的提案编号
      • 批准这个提案
      • 发送一个accepted通知给提议者或学习者。



    Paxos示例





    Paxos安全性
             
    • 如果编号为n的提案包含的值v已经被通过,在第二轮(2a、2b)发出的后续更大编号提案,必须包含相同的值v
    • 决策 = 多数派 (任意两个派至少共享一个成员)。
    • 因此,第一轮(1a、1b)有了决策后, 随后的一轮(2a、2b)中至少有一个投票者已经批准过值v
    • 现在假设我们的说法是不正确的,在后面第二轮(2a、2b)中有一个编号为m首次提案(m晚于n),提议中的值是w等于v
    • 这是不可能的,因为如果这个提议者P可以用值w启动第二轮(2a、2b),说明它已经让多数派批准过一轮提案mm>n)。所以,会有矛盾的结论:
      • v 未被决策通过,与
      • v 被P提案过
    • 因此,一旦有多数派批准过值v ,就不会被改变。


    Paxos活性
    ............


    Paxos的实现
    • Google:Chubby
    • Yahoo:Zookeeper
    • .........

    原文来自于:www.slideshare.net 《Distributed Systems Consensus》 PPT
    译          者:歪脖大肚子Q
    展开全文
  • 2021年度HW行动碎言碎语(一)

    千次阅读 热门讨论 2021-03-28 16:28:46
    红队正在招兵买马、摩拳擦掌,是是鬼都在秀;蓝队正在积极防御,断网断电,努力将攻击扼杀在萌芽当中。HW行动对于腿哥已经不陌生,但是今年第一次作为蓝方参加,还是大姑娘上花轿——头一回。所以就想借着这个机会...
  • 首先是红翼行动行动战斗视频链接地址(塔X班拍摄) http://www.liveleak.com/view?i=c62091316c (需 f 墙) 由于下面那些照片上的队员在阿富汗被埋伏,基本都挂了,所以脸上没必要马赛克了,也算是第一支世界...
  • 微信小程序已刷爆朋友圈,围绕它的讨论也是形形色色。然而你知道吗?有关它的很多消息都不准确。本文作者王安将带你理理大家都误解的八个问题
  • 但凡要给自己定目标,考虑时间管理、效能提升的,都绕不开这三个概念:任务、目标和计划。 弄不清楚三者关系并且各种混用的大有人在,比如说:周计划和周任务、月目标和月计划、年目标和年计划的区别是什么?你...
  • 【并发编程】CPU cache结构和缓存一致性(MESI协议)

    万次阅读 多人点赞 2016-01-03 06:29:21
    一、cache cpu cache已经发展到了三级缓存结构,基本上现在买的个人电脑都是L3结构。 1. cache的意义 ...所以cache的出现,是为了缓解CPU和内存之间速度的不匹配问题(结构:cpu -> cache -> memory...
  • 的思维谬误与心理学效应

    千次阅读 多人点赞 2020-01-24 09:56:52
    这个容易的问题的答案就是对真正问题的启发,但启发经常和真正的答案差得很远,而却往往把启发当成了真正问题的答案。 接下来介绍和启发法相关的心理效应和谬误。每一个谬误都会注明真正的问题是什么,而用以启发...
  • 试论and连接并列主语时的主谓一致

    千次阅读 2018-06-14 20:08:24
    弄清楚这个问题,不仅有利于学生理顺主语与谓语的关系,更好的理解句子,而且有助于学生提高英语成绩。 中国论文网 /4/view-3039634.htm  关键词:英语语法;连词and;主谓一致 中图分类号:H31 文献标识码:...
  • 备注:原内容来自互联网,最开始出处未知,认领请留言。...如果要问一个在而紧随而来的第二个问题则是一旦开始行动,却无法将行动进行到底。 改善自己生活时面临的最大问题是什么,许多会说是缺乏行动
  • 高光的问题,在计算的时候,treyarch试下来把specular power除以4是一个比较好的能够让indirect specular lighting和direct specular lighting在高光上保持一致: BRDF 这部分不知道怎么写blog好了,black ops1的...
  • 这是我自己做的一个多人联机游戏中网络部分的总结。全部为自己全新做的,没用开源软件(有一个网络游戏开源软件Raknet)。目的是写一个属于自己的可靠网络...这里把设计和遇到的问题跟大家分享。   1 设计、实现 1
  • 过河问题详解

    千次阅读 2019-04-13 15:45:17
    1.问题描述 在漆黑的夜里,N位...而如果两同时过桥,所需要的时间就是走得比较慢的那个单独行动时所需的时间。问题是,如何设计一个方案,让这N尽快过桥。 或许还有类似的问题问题的描述可能不尽完全相...
  • 作者:李海翔,腾讯TDSQL专家工程师“在分布式背景下,怎么实现双一致性(事务一致性、分布式一致性),并提高分布式事务型集群的处理效率?”腾讯TDSQL数据库长期致力于基础研究创新,并持...
  • 转载: 转载:分布式消息队列RocketMQ–事务消息–解决分布式事务的最佳实践 转载:如何用消息系统避免分布式事务? ...因此对一致性的研究一般假设信道是可靠的,或不存在本问题。 拜占庭位于
  • VS下 debug与release运行结果不一致

    千次阅读 2015-04-21 21:50:47
    摘要 VS中遇到 debug与release下运行结果不一致,太疼了 VS debug release 网罗了大量文章,主要说变量未初始化的较多,代码量较大,着实不好搞,依次排查,但凡涉及的都已经初始化,无果... eggs hurt~~~...
  • 第三章承诺和一致   赛马场上的奇妙心理:...在这样的压力下,我们想方设法地以行动证明自己先前的决定是正确的。我们要努力要自己相信,我们做出了正确的选择。   一旦做出了艰难的选择,人们就很乐意相信自己
  • 思想上移,行动下移

    千次阅读 2016-04-15 19:36:45
    我 跟大家讲,只要超过两万的公司和组织,不管谁来运营,都会碰到这样的问题:协同的问题、新老的问题等,因为这是组织本身的问题。你想单干,只管一个吃 饱,灵活性一定很大的;你要团伙,五六个人喊一声,大家...
  • 基本面分析昨日市场静待欧元区财长会议,亚欧盘波幅受限,尽管本次会议依然在诸多问题上存在分歧,但最终就西班牙问题达成了一致性意见,欧元引领非美货币小幅反弹。 昨日欧洲央行(ECB)行长德拉基(Mario Draghi)...
  • 这次创业惨淡收场,最主要的原因是没有选择一个合适的创业方向,没有找到合适的创业合伙。 首先要说到创业方向,因为不同的创业方向需要组建不同的创业团队。我个人比较偏好,软件、网络、互联网等有一定科技水平...
  • 消息队列中间件是分布式系统中重要的组件,主要解决应用解耦,异步消息,流量削锋等问题,实现高性能,高可用,可伸缩和最终一致性架构。目前使用较多的消息队列有ActiveMQ,RabbitMQ,ZeroMQ,Kafka,MetaMQ,...
  • 分布式系统的事务处理-- 一致

    千次阅读 2014-02-10 15:53:12
    当我们在生产线上用一台服务器来提供数据服务的时候,我会遇到如下的两个问题: 1)一台服务器的性能不足以提供足够的能力服务于所有的网络请求。 2)我们总是害怕我们的这台服务器停机,造成服务不可用或是...
  • 做人,做事,观念改变人生,行动改变未来
  • 看伟大的领袖如何激励行动有感

    千次阅读 2016-05-26 12:52:54
    中午翻看 TED 网站的时候,发现一个排行——最受欢迎的TED视频。在里面看到(How great leaders inspire action),于是...最先说出why,是为了吸引那部分与你信仰相一致。中午时间不多就写这么多,当做一个记录。
  • AIX常见问题

    万次阅读 2012-05-19 21:05:37
    问题怎样在AIX 5.1中建立热后备(hot spare)磁盘? 解答 在AIX 5.1中可以在操作系统的级别上建立hot spare磁盘。 如需要在某一卷组(VG)中建立hot spare磁盘,必须满足如下条件: 1. 逻辑卷(LV)在此卷组中必须进行镜像...
  • 而对这个问题有深思熟虑答案的,一定是行业的佼佼者。 再来,第四个问题, 别人需要你为他干吗? 能回答这个问题,少之又少。一旦回答得出,他就一定做成了一番事业。 但是,很多事业有成的仍然被第5个...
  • 从“双方理解一致”谈有效沟通

    千次阅读 2007-08-13 11:44:00
    SMART原则中的“A”指的是“双方理解一致的”,这是各种计划、评估、日常沟通中沟通是否有效的主要标尺。记得多年前有一位新任秘书,经理对他说:“请你告诉×××我让他×××”。新员工的热情真是可嘉,经理的话音...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 46,413
精华内容 18,565
关键字:

一致行动人问题