精华内容
下载资源
问答
  • SDN核心技术

    千次阅读 2019-01-30 17:44:35
    SDN核心技术
                   

    SDN核心技术

    SDN的架构可以与人的身体做类比:控制层就是人的大脑,负责对人身体的总体管控;转发层的设备是人的四肢,在大脑的控制下进行各种活动;应用层对应的是各种创新的想法,大脑在它们的驱动下对四肢进行指挥以达到其所需的效果;南向接口和北向接口则分别相当于人体内的神经和脑电波,负责各种信号的上传下达。从类比中可以看出:作为四肢的转发层,其处理性能一定要高,而其本身可以不做更多的思考而成为“傻”设备;作为大脑的控制层,其控制逻辑一定要周全,能够根据全局的网络视图作出合理的资源调配决策;作为创新想法的应用层,其工作是充分利用大脑提供的能力完成各种花样翻新的任务,同时针对自身需要向大脑提出新的能力需求。

    基于上述分析,SDN中引入了很多创新技术以支撑相应的需求。遵循SDN的层次架构,SDN核心技术体系如图1-6所示。


    如图1-6所示,在SDN架构的每一层次上都具有很多核心技术,其目标是有效地分离控制层面与转发层面,支持逻辑上集中化的统一控制,提供灵活的开放接口等。其中,控制层是整个SDN的核心,系统中的南向接口与北向接口也是以它为中心进行命名的。

    交换机及南向接口技术

    SDN交换机是SDN网络中负责具体数据转发处理的设备。本质上看,传统设备中无论是交换机还是路由器,其工作原理都是在收到数据包时,将数据包中的某些特征域与设备自身存储的一些表项进行比对,当发现匹配时则按照表项的要求进行相应处理。SDN交换机也是类似的原理,但是与传统设备存在差异的是,设备中的各个表项并非是由设备自身根据周边的网络环境在本地自行生成的,而是由远程控制器统一下发的,因此各种复杂的控制逻辑(例如链路发现、地址学习、路由计算等等)都无需在SDN交换机中实现。SDN交换机可以忽略控制逻辑的实现,全力关注基于表项的数据处理,而数据处理的性能也就成为评价SDN交换机优劣的最关键指标,因此,很多高性能转发技术被提出,例如基于多张表以流水线方式进行高速处理的技术。另外,考虑到SDN和传统网络的混合工作问题,支持混合模式的SDN交换机也是当前设备层技术研发的焦点。同时,随着虚拟化技术的出现和完善,虚拟化环境将是SDN交换机的一个重要应用场景,因此SDN交换机可能会有硬件、软件等多种形态。例如,OVS(OpenvSwitch,开放虚拟交换标准)交换机就是一款基于开源软件技术实现的能够集成在服务器虚拟化Hypervisor中的交换机,具备完善的交换机功能,在虚拟化组网中起到了非常重要的作用。

    SDN交换机需要在远程控制器的管控下工作,与之相关的设备状态和控制指令都需要经由SDN的南向接口传达。当前,最知名的南向接口莫过于ONF倡导的OpenFlow协议。作为一个开放的协议,OpenFlow突破了传统网络设备厂商对设备能力接口的壁垒,经过多年的发展,在业界的共同努力下,当前已经日臻完善,能够全面解决SDN网络中面临的各种问题。当前,OpenFlow已经获得了业界的广泛支持,并成为了SDN领域的事实标准,例如前文提及的OVS交换机就能够支持OpenFlow协议。OpenFlow解决了如何由控制层把SDN交换机所需的用于和数据流做匹配的表项下发给转发层设备的问题,同时ONF还提出了OF-CONFIG协议,用于对SDN交换机进行远程配置和管理,其目标都是为了更好地对分散部署的SDN交换机实现集中化管控。

    控制器及北向接口技术

    SDN控制器负责整个网络的运行,是提升SDN网络效率的关键。SDN交换机的“去智能化”、OpenFlow等南向接口的开放,产生了很多新的机会,使得更多人能够投身于控制器的设计与实现中。当前,业界有很多基于OpenFlow控制协议的开源的控制器实现,例如NOX、Onix、Floodlight等,它们都有各自的特色设计,能够实现链路发现、拓扑管理、策略制定、表项下发等支持SDN网络运行的基本操作。虽然不同的控制器在功能和性能上仍旧存在差异,但是从中已经可以总结出SDN控制器应当具备的技术特征,从这些开源系统的研发与实践中得到的经验和教训将有助于推动SDN控制器的规范化发展。另外,用于网络集中化控制的控制器作为SDN网络的核心,其性能和安全性非常重要,其可能存在的负载过大、单点失效等问题一直是SDN领域中亟待解决的问题。当前,业界对此也有了很多探讨,从部署架构、技术措施等多个方面提出了很多有创见的方法。

    SDN北向接口是通过控制器向上层业务应用开放的接口,其目标是使得业务应用能够便利地调用底层的网络资源和能力。北向接口是直接为业务应用服务的,其设计需要密切联系业务应用需求,具有多样化的特征。同时,北向接口的设计是否合理、便捷,以便能被业务应用广泛调用,会直接影响到SDN控制器厂商的市场前景。因此,与南向接口方面已有OpenFlow等国际标准不同,北向接口方面还缺少业界公认的标准,成为当前SDN领域竞争的焦点,不同的参与者或者从用户角度出发,或者从运营角度出发,或者从产品能力角度出发提出了很多方案。虽然北向接口标准当前还很难达成共识,但是充分的开放性、便捷性、灵活性将是衡量接口优劣的重要标准,例如REST API就是上层业务应用的开发者比较喜欢的接口形式。部分传统的网络设备厂商在其现有设备上提供了编程接口供业务应用直接调用,也可被视作是北向接口之一,其目的是在不改变其现有设备架构的条件下提升配置管理灵活性,应对开放协议的竞争。

    应用编排和资源管理技术

    SDN网络的最终目标是服务于多样化的业务应用创新。因此随着SDN技术的部署和推广,将会有越来越多的业务应用被研发,这类应用将能够便捷地通过SDN北向接口调用底层网络能力,按需使用网络资源。

    SDN推动业务创新已经是业界不争的事实,它可以被广泛地应用在云数据中心、宽带传输网络、移动网络等种种场景中,其中为云计算业务提供网络资源服务就是一个非常典型的案例。众所周知,在当前的云计算业务中,服务器虚拟化、存储虚拟化都已经被广泛应用,它们将底层的物理资源进行池化共享,进而按需分配给用户使用。相比之下,传统的网络资源远远没有达到类似的灵活性,而SDN的引入则能够很好地解决这一问题。SDN通过标准的南向接口屏蔽了底层物理转发设备的差异,实现了资源的虚拟化,同时开放了灵活的北向接口供上层业务按需进行网络配置并调用网络资源。云计算领域中知名的OpenStack就是可以工作在SDN应用层的云管理平台,通过在其网络资源管理组件中增加SDN管理插件,管理者和使用者可利用SDN北向接口便捷地调用SDN控制器对外开放的网络能力。当有云主机组网需求(例如建立用户专有的VLAN)被发出时,相关的网络策略和配置可以在OpenStack管理平台的界面上集中制定并进而驱动SDN控制器统一地自动下发到相关的网络设备上。因此,网络资源可以和其他类型的虚拟化资源一样,以抽象的资源能力的面貌统一呈现给业务应用开发者,开发者无需针对底层网络设备的差异耗费大量开销从事额外的适配工作,这有助于业务应用的快速创新。


    本文节选自《SDN核心技术剖析和实战指南》

    雷葆华等 编著

    电子工业出版社出版

               

    再分享一下我老师大神的人工智能教程吧。零基础!通俗易懂!风趣幽默!还带黄段子!希望你也加入到我们人工智能的队伍中来!https://blog.csdn.net/jiangjunshow

    展开全文
  • Java2核心技术第7版全两卷.pdf中文高清

    千次下载 热门讨论 2012-09-14 14:22:28
    本资源内有两本书《Java2核心技术卷I:基础知识(第7版)》和《JAVA2核心技术,卷II:高级特性(第7版)》,大小分别为 88MB 和 112 BM,均为 PDF 格式,高清影印版。两本书分别介绍如下: 《Java2核心技术卷I:基础知识...
  • 考察云计算关键核心技术发展情况

    千次阅读 2018-05-17 10:07:52
    贵州省委网信办主任谢念,贵州省政府驻广州办事处主任聂斌等一行,在广东省委宣传部副部长崔朝阳陪同下,莅临云宏参观考察云计算关键核心技术发展情况。云宏创始人张为杰、董事长涂华奇、总裁邹理贤携高管隆重接待...

    2018年5月12日,贵州省委常委、宣传部部长、省委网络安全与信息化领导小组副组长慕德贵,贵州省委网信办主任谢念,贵州省政府驻广州办事处主任聂斌等一行,在广东省委宣传部副部长崔朝阳陪同下,莅临云宏参观考察云计算关键核心技术发展情况。云宏创始人张为杰、董事长涂华奇、总裁邹理贤携高管隆重接待到访领导。



    云宏董事长涂华奇向到访领导详细汇报云宏发展情况。“八年磨一剑”,自成立以来,云宏始终专注于云计算关键核心技术——虚拟化技术的自主创新研发。虚拟化技术是云计算综合标准化体系中的关键核心技术,关系信息安全体系的本质安全。由于国内对虚拟化技术研发起步较晚,市场长期由国外厂商垄断。云宏潜心研发,不断突破,研发出国内最早在虚拟化技术层拥有自主核心技术成果的云操作系统,打破了国外行业巨头的垄断,成为国内云计算关键核心技术的领头羊。目前,云宏CNware®虚拟化平台已具备全面替换国际巨头虚拟化产品的能力,获得来自国家行业主管部门、市场、权威机构的认可,尤其在安全性、兼容性、易用性方面,已经形成对外国垄断巨头产品的竞争优势。2018年,云宏虚拟化软件产品成功通过国家保密科技测评中心的检测,云宏及控股子公司航天云宏均通过国际软件能力成熟度最高级别CMMI5认证,标志着云宏在安全性和产品质量方面再上台阶。




    听取云宏发展情况汇报后,慕德贵常委充分肯定云宏在关键核心技术方面的成果,高度赞扬云宏潜心专研底层技术、担当国家使命的情怀和精神,勉励云宏继续攻关,不断进取,加快推动国产云计算关键核心技术的创新进步,为保障国家民族信息安全重任作出更大贡献;当前,贵州省正处于大数据产业经济融合发展的重要阶段,正需要云计算大数据关键核心技术前沿力量在此汇聚。希望云宏能发挥先锋模范作用,为全国同类项目的开展树立更多标杆。

    展开全文
  • 区块链(Blockchain)-核心技术概览

    万次阅读 2017-11-26 15:05:10
    本文剖析了区块链的相关核心技术,包括其定义、工作原理、技术分类、关键问题和认识上的误区等。通过本章的学习,读者可以对区块链的相关核心技术形成整体上的认识,并对区块链在整个信息科技产业中的位置和发展趋势...

    运用之妙夺造化,存乎一心胜天工。
    有人可能会遇到这样的问题:

    • 跨境商贸合作中签订的合同,怎么确保对方能严格遵守和及时执行?
    • 酒店宣称刚打捞上来的三文鱼,怎么追踪捕捞和运输过程中的时间和卫生?
    • 现代数字世界里,怎么证明你是谁?怎么证明某个资产属于你?
    • 经典囚徒困境中的两个人,怎样才能达成利益的最大化?
    • 宇宙不同文明之间的“黑暗森林”猜疑链,有没有可能被彻底打破?

    这些看似很难解决的问题,在区块链的世界里已经有了初步的答案。本文将带领大家探索区块链的核心技术,包括其定义与原理、关键的问题等,还将探讨区块链技术的演化,并对未来发展的趋势进行展望。最后,对一些常见的认识误区进行了澄清。

    定义与原理

    1、定义

    公认的最早关于区块链的描述性文献是中本聪所撰写的文章《Bitcoin:A Peer-to Peer Electronic Cach System》,但该文献重点在于讨论比特币系统,实际上并没有明确提出区块链的定义和概念,在其中指出,区块链是用于记录比特币交易账目历史的数据结构。

    另外,Wikipedia上给出的定义中,将区块链类比为一种分布式数据库技术,通过维护数据块的链式结构,可以维持持续增长的、不可篡改的数据记录。

    区块链技术最早的应用出现在比特币项目中。作为比特币背后的分布式记账平台,在无集中式管理的情况下,比特币网络稳定运行了八年时间,支持了海量的交易记录,并且从未出现严重的漏洞,这些都与巧妙的区块链结构分不开的。

    区块链技术自身仍然在飞速发展中,目前相关规范和标准还在进一步成熟中。

    2、基本原理

    区块链的基本原理理解起来并不复杂。首先,区块链包括三个基本概念:

    • 交易(transaction):一次对账本的操作,导致账本状态的一次改变,如添加一条转账记录;
    • 区块(block):记录一段时间内发生的所有交易和状态结果,是对当前账本状态的一次共识;
    • 链(chain):由区块按照发生顺序串联而成,是整个账本状态变化的日志记录。

    如果把区块链作为一个状态机,则每次交易就是试图改变一次状态,而每次共识生成的区块,就是参与者对于区块中交易导致状态改变的结果进行确认。

    在实现上,首先假设存在一个分布式的数据记录账本,这个账本只允许添加、不允许删除。账本底层的基本结构是一个线性的链表,这也是其名字“区块链”的来源。链表由一个个“区块”串联组成(如图2-1所示),后继区块记录前导区块的哈希值(pre hash)。新的数据要加入,必须放到一个新的区块中。而这个块(以及块里的交易)是否合法,可以通过计算哈希值的方式快速检验出来。任意维护节点都可以提议一个新的合法区块,然而必须经过一定的共识机制来对最终选择的区块达成一致。


    这里写图片描述
    图2-1 区块链结构示例

    3、以比特币为例理解区块链工作过程

    以比特币网络为例,可以具体看其中如何使用了区块链技术。

    首先,比特币客户端发起一项交易,广播到比特币网络中并等待确认。网络中的节点会将一些收到的等待确认的交易记录打包在一起(此外还要包括前一个区块头部的哈希值等信息),组成一个候选区块。然后,试图找到一个nonce串(随机串)放到区块里,使得候选区块的哈希结果满足一定条件(比如小于某个值)。这个nonce串的查找需要一定的时间去进行计算尝试。

    一旦节点算出来满足条件的nonce串,这个区块在格式上就被认为是“合法”了,就可以尝试在网络中将它广播出去。其他节点收到候选区块,进行验证,发现确实符合约定条件了,就承认这个区块是一个合法的新区块,并添加到自己维护的区块链上。当大部分节点都将区块添加到自己维护的区块链结构上时,该区块被网络接受,区块中所包括的交易也就得到确认。

    当然,在实现上还会有很多额外的细节。这里面比较关键的步骤有两个:

    1. 一个是完成对一批交易的共识(创建区块结构);
    2. 一个是新的区块添加到区块链结构上,被大家认可,确保未来无法被篡改。

    比特币的这种基于算力寻找nonce串的共识机制称为工作量证明(Proof of Work,PoW)。目前,要让哈希结果满足一定条件,并无已知的快速启发式算法,只能进行尝试性的暴力计算。尝试的次数越多(工作量越大),算出来的概率越大。

    通过调节对哈希结果的限制,比特币网络控制平均约10分钟产生一个合法区块。算出区块的节点将得到区块中所有交易的管理费和协议固定发放的奖励费(目前是12.5比特币,每四年减半),这个计算新区块的过程俗称为挖矿。

    读者可能会关心,比特币网络是任何人都可以加入的,如果网络中存在恶意节点单,能否进行恶意操作来对区块链中的记录进行篡改,从而破坏整个比特币网络系统。比如最简单的,故意不承认收到的别人产生的合法候选区块,或者干脆拒绝来自其他节点的交易等。

    实际上,比特币网络中存在大量(据估计数千个)的维护节点,而且大部分节点都是正常工作的,默认都只承认所看到的最长的链结构。只要网络中不存在超过一半的节点提前勾结一起采取恶意行动,则最长的链将很大概率上成为最终合法的链。而且随着时间增加,这个概率会越来越大。例如,经过6个区块生成后,即便有一半的节点联合起来想颠覆被确认的结果,其概率也仅为(1/2)6≈1.6%,即低于1/60的可能性。

    当然,如果整个网络中大多数的节点都联合起来作恶,可以导致整个系统无法正常工作。要做到这一点,往往意味着付出很大的代价,跟通过作恶得到的收益相比,得不偿失。

    技术的演化与分类

    区块链技术自比特币网络设计中被大家发掘关注,从最初服务数字货币系统,到今天在分布式账本场景下发挥着越来越大的技术潜力。

    1、区块链的演化

    比特币区块链已经支持了简单的脚本计算,但仅限于数字货币相关的处理。除了支持数字货币外,还可以将区块链上执行的处理过程进一步泛化,即提供智能合约(smart contract)。智能合约可以提供除了货币交易功能外更灵活的合约功能,执行更为复杂的操作。

    这样,扩展之后的区块链已经超越了单纯数据记录的功能,实际上带有一点“智能计算”的意味;更进一步,还可以为区块链加入权限管理和高级编程语言支持等,实现更强大的、支持更多商用场景的分布式账本。

    从计算特点上,可以看到现有区块链技术的三种典型演化场景,如表2-1所示。

    场景功能智能合约一致性权限类型性能编程语言代表
    工信的数字货币记账功能不带有或较弱PoW公有链较低简单脚本比特币网络
    工信的交易处理智能合约图灵完备PoW、PoS公有链受限特定语言以太坊网络
    带权限的分布式账本处理商业处理多种语言,图灵完备包括CFT、BFT在内的多种机制,可插拔支持联盟链可拓展高级语言超级账本

    表2-1 区块链技术的三种典型演化场景

    2、区块链与分布式记账

    现代复式记账系统(double entry bookkeeping)由意大利数学家卢卡·帕西奥利于1494年在《Summa de arithmetica,geometrica,proportioni et proportionalità》一书中最早制定。复式记账法对每一笔账目同时记录来源和去向,首次将对账验证功能引入记账过程,提升了记账过程的可靠性。

    从这个角度来看,区块链是首个自带对账功能的数字记账技术实现。

    更广泛地看,区块链属于一种去中心化的记录技术。参与到系统上的节点,可能不属于同一组织,彼此无需信任;区块链数据由所有节点共同维护,每个维护节点都能复制获得一份完整或部分记录的拷贝。

    跟传统的记账技术相比,基于区块链的分布式账本应该包括如下特点:

    • 维护一条不断增长的链,只可能添加记录,而发生过的记录都不可篡改;
    • 去中心化,或者说多中心化,无需集中控制而能达成共识,实现上尽量采用分布式;
    • 通过密码学的机制来确保交易无法被抵赖和破坏,并尽量保护用户信息和记录的隐私性。

    3、分类

    根据参与者的不同,可以分为公开(public)链、联盟(consortium)链和私有(private)链。

    • 公有链,顾名思义,任何人都可以参与使用和维护,如比特币区块链,信息是完全公开的;

    如果进一步引入许可机制,可以实现私有链和联盟链两种类型:

    • 私有链,由集中管理者进行管理限制,只有内部少数人可以使用,信息不公开;
    • 联盟链则介于两者之间,由若干组织一起合作维护一条区块链,该区块链的使用必须是带有权限的限制访问,相关信息会得到保护,如供应链机构或银行联盟。

    目前来看,公有链更容易吸引市场和媒体的眼球,但更多的商业价值会在联盟链和私有链上落地。

    根据使用目的和场景的不同,又可以分为以数字货币为目的的货币链,以记录产权为目的的产权链,以众筹为目的的众筹链等,也有不局限特定应用场景的通用链。

    现有大部分区块链实现都至少包括了网络层、共识层、智能合约和应用层等结构,联盟链实现往往还会引入一定的权限管理机制。

    关键问题和挑战

    从技术角度讲,区块链所涉及的领域比较繁杂,包括分布式系统、存储、密码学、心理学、经济学、博弈论、控制论、网络协议等,这也就意味着大量工程实践上的技术挑战。

    下面列出了目前业内关注较多的一些技术话题。

    1、抗抵赖与隐私保护

    • 怎么防止交易记录被篡改?
    • 怎么证明交易双方的身份?
    • 怎么保护交易双方的隐私?

    密码学的发展为解决这些问题提供了不少手段。传统方案包括Hash算法、加解密算法、数字证书和签名(盲签名、环签名)等。

    随着区块链技术的应用,新出现的需求将刺激密码学的进一步发展,包括更高效的随机数产生、更高强度的加密、更快速的加解密处理等。同时,量子计算等新技术的出现,也会带来更多的挑战,例如,RSA算法等目前商用的加密算法,在未来可能无法提供足够的安全性。

    能否满足这些新的需求,将依赖于数学科学的进一步发展和新一代计算技术的突破。

    2、分布式共识

    这是个经典的技术难题,学术界和业界都已有大量的研究成果(包括Paxos、拜占庭系列算法等)。

    问题的核心在于如何解决某个变更在分布式网络中得到一致的执行结果,是被参与多方都承认的,同时这个信息是被确定的,不可推翻的。

    该问题在公开匿名场景下和带权限管理的场景下需求差异较大,从而导致了基于概率的算法和确定性算法两类思想。

    最初,比特币区块链考虑的是公开匿名场景下的最坏保证。通过引入了“工作量证明”策略来规避少数人的恶意行为,并通过概率模型保证最后参与方共识到最长链。算法在核心思想上是基于经济利益的博弈,让恶意破坏的参与者损失经济利益,从而保证大部分人的合作。同时,确认必须经过多个区块的生成之后达成,从概率上进行保证。这类算法的主要问题在于效率的低下。类似算法还有以权益为抵押的PoS、DPoS和Casper等。

    后来更多的区块链技术(如超级账本)在带权限管理的场景下,开始考虑支持更多的确定性的共识机制,包括经典的拜占庭算法等,可以解决快速确认的问题。

    共识问题在很长一段时间内都将是极具学术价值的研究热点,核心的指标将包括容错的节点比例、决策收敛速度、出错后的恢复、动态特性等。PoW等基于概率的系列算法理论上允许少于一半的不合作节点,PBFT等确定性算法理论上则允许不超过1/3的不合作节点。

    3、交易性能

    虽然一般来说,区块链不适用于高频交易的场景,但由于金融系统的需求,业界目前十分关心如何提高区块链系统交易的吞吐量,同时降低交易的确认延迟。

    目前,公开的比特币区块链只能支持平均每秒约7笔的吞吐量,一般认为对于大额交易来说,安全的交易确认时间为一个小时左右。以太坊区块链的吞吐量略高一些,但交易性能也被认为是较大的瓶颈。

    区块链系统跟传统分布式系统不同,其处理性能很难通过单纯增加节点数来进行横向扩展。实际上,传统区块链系统的性能,在很大程度上取决于单个节点的处理能力。高性能、安全、稳定性、硬件辅助加解密能力,都将是考查节点性能的核心要素。

    这种场景下,为了提高处理性能,一方面可以提升单个节点的性能(如采用高配置的硬件),同时设计优化的策略和算法;另外一方面试图将大量高频的交易放到链外来,只用区块链记录最终交易信息,如比特币社区提出的“闪电网络”等设计。类似地,侧链(side chain)、影子链(shadow chain)等思路在当前阶段也有一定的借鉴意义。类似设计可以将交易性能提升1~2个数量级。

    此外,在联盟链的场景下,参与多方存在一定的信任前提和利益约束,可以采取更优化的设计,换来性能的提升。以超级账本Fabric项目为例,在普通虚拟机配置下,单客户端交易吞吐量可达几百次每秒(transactions per second,tps);在有一定工程优化或硬件加速情况下可以达到每秒数千次的吞吐量。

    客观地说,目前开源区块链系统已经可以满足不少应用场景的性能需求,但离大规模交易系统在峰值每秒数万笔的吞吐性能还有较大差距。

    4、扩展性

    常见的分布式系统可以通过增加节点来横向扩展整个系统的处理能力。对于区块链网络系统来说,根据共识机制的不同,这个问题往往并非那么简单。

    例如,对于比特币和以太坊区块链而言,网络中每个参与维护的核心节点都要保持一份完整的存储,并且进行智能合约的处理。此时,整个网络的总存储和计算能力取决于单个节点的能力。甚至当网络中节点数过多时,可能会因为一致性的达成过程延迟降低整个网络的性能。尤其在公有网络中,由于存在大量低性能处理节点,导致这个问题将更加明显。

    要解决这个问题,根本上是放松对每个节点都必须参与完整处理的限制(当然,网络中节点要能合作完成完整的处理),这个思路已经在超级账本中得到应用;同时尽量减少核心层的处理工作。

    在联盟链模式下,还可以专门采用高性能的节点作为核心节点,相对较弱的节点仅作为代理访问节点。

    5、安全防护

    区块链目前最热门的应用场景是金融相关的服务,安全自然是讨论最多、挑战最大的话题。区块链在设计上大量采用了现代成熟的密码学算法。但这是否就能确保其绝对安全呢?

    世界上并没有绝对安全的系统。

    系统是由人设计的,系统也是由人来运营的,只要有人参与的系统,就难免出现漏洞。如下几个方面是很难避免的。

    首先是立法。对区块链系统如何进行监管?攻击区块链系统是否属于犯罪?攻击银行系统是要承担后果的。但是目前还没有任何法律保护区块链(特别是公有链)以及基于它的实现。

    其次是软件实现的潜在漏洞。考虑到使用了几十年的OpenSSL还带着那么低级的漏洞(heart bleeding),而且是源代码完全开放的情况下,让人不禁对运行中的大量线上系统持谨慎态度。而对于金融系统来说,无论客户端还是平台侧,即便是很小的漏洞都可能造成难以估计的损失。

    另外,公有区块链所有交易记录都是公开可见的,这意味着所有的交易即便被匿名化和加密处理,但总会在未来某天被破解。安全界一般认为,只要物理上可接触就不是彻底的安全。实际上,已有文献证明,比特币区块链的交易记录很大可能是能追踪到真实用户的。

    作为一套完全分布式的系统,公有的区块链缺乏有效的调整机制。一旦运行起来,出现问题也难以修正。即使是让它变得更高效、更完善的修改,只要有部分既得利益者联合起来反对,就无法得到实施。比特币社区已经出现过多次类似的争论。

    最后,运行在区块链上的智能合约应用可能是五花八门的,可能存在潜在的漏洞,必须有办法进行安全管控,在注册和运行前需要有合理的机制进行探测,以规避恶意代码的破坏。

    2016年6月17日发生的“DAO系统漏洞被利用”事件,直接导致价值6000万美元的数字货币被利用者获取。尽管对于这件事情的反思还在进行中,但事实再次证明,目前基于区块链技术进行生产应用时,务必要细心谨慎地进行设计和验证。必要时,甚至要引入“形式化验证”和人工审核机制。

    6、数据库和存储系统

    区块链网络中的大量信息需要写到文件和数据库中进行存储。

    观察区块链的应用,大量的读写操作、Hash计算和验证操作,跟传统数据库的行为十分不同。当年,人们观察到互联网应用大量非事务性的查询操作,而设计了非关系型(NoSQL)数据库。那么,针对区块链应用的这些特点,是否可以设计出一些特殊的针对性的数据库呢?

    LevelDB、RocksDB等键值数据库,具备很高的随机写和顺序读、写性能,以及相对较差的随机读的性能,被广泛应用到了区块链信息存储中。但目前来看,面向区块链的数据库技术仍然是需要突破的技术难点之一,特别是如何支持更丰富语义的操作。

    大胆预测,未来将可能出现更具针对性的“块数据库”(BlockDB),专门服务类似区块链这样的新型数据业务,其中每条记录将包括一个完整的区块信息,并天然地跟历史信息进行关联,一旦写入确认则无法修改。所有操作的最小单位将是一个块。为了实现这种结构,需要原生支持高效的签名和加解密处理。

    7、集成和运营

    即便大量企业系统准备迁移到区块链平台上,但在相当长的一段时间内,基于区块链的新业务系统必将与已有的中心化系统集成共存。

    两种系统如何共存,如何分工,彼此的业务交易如何进行合理传递?出现故障如何排查和隔离?已有数据如何在不同系统之间进行迁移和灾备?区块链系统自身又该如何进行运营(如网络的设计选择、状态监控、灾备等)?

    这些都是迫切要解决的实际问题。若解决不好,将是区块链技术落地的不小阻碍。

    趋势与展望

    关于区块链技术发展趋势的探讨和争论,自其诞生之日起就从未停息。或许,读者从计算技术的演变历史中能得到一些启发。计算技术的发展历史如图2-3所示。


    这里写图片描述
    图2-3 计算的历史

    以云计算为代表的现代计算技术,其发展历史上有若干重要的时间点和事件:

    • 1969——ARPANet(Advanced Research Projects Agency Network):现代互联网的前身,由美国高级研究计划署(Advanced Research Project Agency)提出,其使用NCP协议,核心缺陷之一是无法做到和个别计算机网络交流;
    • 1973——TCP/IP:Vinton.Cerf(文特·瑟夫)与Bob Karn(鲍勃·卡恩)共同开发出TCP模型,解决了NCP的缺陷;
    • 1982——Internet:TCP/IP正式成为规范,并被大规模应用,现代互联网诞生;
    • 1989——WWW:早期互联网的应用主要包括telnet、ftp、email等,Tim Berners-Lee(蒂姆·伯纳斯-李)设计的WWW协议成为互联网的杀手级应用,引爆了现代互联网,从那开始,互联网业务快速扩张;
    • 1999——Salesforce:互联网出现后,一度只能进行通信应用,但Salesforce开始以云的理念提供基于互联网的企业级服务;
    • 2006——AWS EC2:奠定了云计算的业界标杆,直到今天,竞争者们仍然在试图追赶AWS的脚步;
    • 2013——Cognitive:以IBM Watson为代表的认知计算开始进入商业领域,计算开始变得智能,进入“后云计算时代”。

    从这个历史中能看出哪些端倪呢?

    首先,技术领域也存在着周期律。这个周期目前看是7~8年左右。或许正如人有“七年之痒”,技术也存在着七年这道坎,到了这道坎,要么自身突破迈过去,要么就被新的技术所取代。如果从比特币网络上线(2009年1月)算起,到今年正是在坎上。因此,现在正是相关技术进行突破的好时机。

    其次,最早出现的未必是先驱。创新固然很好,但过早播撒的种子,若没有合适的土壤,往往也难长大。技术创新与科研创新很不同的一点是,技术创新必须立足于需求,过早过晚都会错失良机。科研创新则要越早越好,比如20世纪出现的物理学巨匠们,超前的研究成果奠定了后续一百多年的科技革命的基础。

    最后,事物的发展往往是延续的、长期的。新生事物大都不是凭空蹦出来的,往往是解决了前辈未能解决的问题,或是出现了之前未曾出现过的场景。而且很多时候,新生事物的出现需要长期的孵化;坚持还是放弃,故事不断重复。笔者认为,只要是朝着提高生产力的正确方向努力,迟早会有出现在舞台上的一天。

    目前,区块链在数字货币领域(以比特币为代表)的应用已经相对成熟,而在智能合约和分布式账本方向尚处于初步实践阶段。但毫无疑问的是,区块链技术在已经落地的领域,确实带来了生产力提升。因此可以相信,随着相关技术的进一步发展,区块链技术必然会在更多的领域中大放异彩,特别是金融科技相关领域。

    认识上的误区

    目前,由于区块链自身仍是一种相对年轻的技术,不少人对区块链的认识还存在一些误区。下面是需要注意的一些问题:

    首先,区块链不等于比特币。虽说区块链的基本思想诞生于比特币的设计中,但发展到今日,比特币和区块链已经俨然成为了两个不太相关的技术。前者更侧重从数字货币角度发掘比特币的实验性意义;后者则从技术层面探讨和研究可能带来的商业系统价值,试图在更多的场景下释放智能合约和分布式账本带来的科技潜力。

    其次,区块链不等于数据库。虽然区块链也可以用来存储数据,但它要解决的核心问题是多方的互信问题。单纯从存储数据角度,它的效率可能不高,也不推荐把大量的原始数据放到区块链系统上。当然,现在已有的区块链系统中,数据库相关的技术十分关键,直接决定了区块链系统的吞吐性能。

    最后,区块链并非一门万能的颠覆性技术。作为融合多项已有技术而出现的新事物,区块链跟现有技术的关系是一脉相承的。它在解决多方合作和可信处理上向前多走了一步,但并不意味着它是万能的,更不会彻底颠覆已有的商业模式。很长一段时间里,区块链所适用的场景仍需不断摸索,并且跟已有系统也必然是长期合作共存的关系。

    小结

    本章剖析了区块链的相关核心技术,包括其定义、工作原理、技术分类、关键问题和认识上的误区等。通过本章的学习,读者可以对区块链的相关核心技术形成整体上的认识,并对区块链在整个信息科技产业中的位置和发展趋势形成更清晰的认知。

    除了数字货币应用外,现在业界越来越看重区块链技术可能带来的面向商业应用场景的计算能力。开源社区发起的开放的“以太坊”和“超级账本”等项目,让用户可以使用它们来快速设计复杂的分布式账本应用。

    有理由相信,随着更多商业应用场景的出现,区块链技术将在未来金融和信息技术等领域占据越来越重要的地位。

    摘自:区块链原理、设计与应用

    展开全文
  • 区块链:分布式系统核心技术

    万次阅读 2019-05-17 18:19:48
    万法皆空,因果不空。 随着摩尔定律碰到瓶颈,分布式架构越来越常见。...本章将介绍分布式系统领域的核心技术,包括一致、共识的定义,基本的原理和常见算法,最后还介绍了评估分布式系统可靠的指...

    万法皆空,因果不空。

    随着摩尔定律碰到瓶颈,分布式架构越来越常见。

    从单点演变到分布式结构,首要问题之一就是数据一致性。很显然,如果分布式集群中多个节点处理结果无法保证一致,那么在其上的业务系统将无法正常工作。

    区块链系统是一个典型的分布式系统,必然也会碰到这些经典问题。

    本章将介绍分布式系统领域的核心技术,包括一致性、共识的定义,基本的原理和常见算法,最后还介绍了评估分布式系统可靠性的指标。

    一致性问题

    一致性问题是分布式领域最基础、最重要的问题,也是半个世纪以来的研究热点。

    随着业务场景越来越复杂,计算规模越来越庞大,单点系统往往难以满足高可扩展(Scalability)和高容错(Fault-tolerance)两方面的需求。此时就需要多台服务器通过组成集群,构建更加强大和稳定的“虚拟超级服务器”。

    任务量越大,处理集群的规模越大,设计和管理的挑战也就越高。谷歌公司的全球搜索集群系统,包括数十万台服务器,每天响应百亿次的互联网搜索请求。

    集群系统要实现一致性不是一件容易的事。不同节点可能处于不同的状态,不同时刻收到不同的请求,而且随时可能有节点出现故障。要保持对外响应的“一致性”,好比训练一群鸭子齐步走,难度可想而知。

    定义与重要性

    定义 一致性(Consistency),早期也叫(Agreement),在分布式系统领域中是指对于多个服务节点,给定一系列操作,在约定协议的保障下,使得它们对处理结果达成“某种程度”的协同。

    理想情况(不考虑节点故障)下,如果各个服务节点严格遵循相同的处理协议(即构成相同的状态机逻辑),则在给定相同的初始状态和输入序列时,可以确保处理过程中的每个步骤的执行结果都相同。因此,传统分布式系统中讨论一致性,往往是指在外部任意发起请求(如向多个节点发送不同请求)的情况下,确保系统内大部分节点实际处理请求序列的一致,即对请求进行全局排序。

    那么,为什么说一致性问题十分重要呢?

    举个现实生活中的例子,多个售票处同时出售某线路上的火车票,该线路上存在多个经停站,怎么才能保证在任意区间都不会出现超售(同一个座位卖给两个人)的情况?

    这个问题看起来似乎没那么难,现实生活中经常通过分段分站售票的机制。然而,要支持海量的用户进行并行购票,并非易事(参考 12306 的案例)。特别是计算机系统往往需要达到远超物理世界的高性能和高可扩展性需求,挑战会变得更大。这也是为何每年到了促销季,各大电商平台都要提前完善系统。

    注:一致性关注的是系统呈现的状态,并不关注结果是否正确;例如,所有节点都对某请求达成否定状态也是一种一致性。

    问题挑战

    计算机固然很快,但在很多地方都比人类世界脆弱的多。典型的,在分布式系统中,存在不少挑战:

    • 节点完成请求的时间无法保障,处理的结果可能是错误的,甚至节点自身随时可能发生故障;
    • 为了实现可扩展性,集群往往要采用异步设计,依靠网络消息交互,意味着不可预测的通信延迟、丢失或错误。

    仍以火车票售卖问题为例,愿意动脑筋的读者可能已经想到了一些不错的解决思路,例如:

    • 要出售任意一张票前,先打电话给其他售票处,确认下当前这张票不冲突。即退化为同步调用来避免冲突;
    • 多个售票处提前约好隔离的售票时间。比如第一家可以在上午 8 点到 9 点期间卖票,接下来一个小时是另外一家……即通过令牌机制来避免冲突;
    • 成立一个第三方的存票机构,票集中存放,每次卖票前找存票机构查询。此时问题退化为中心化中介机制。

    这些思路假设售票处都能保证正常工作,并且消息传递不会出现错误。

    当然,还可以设计出更多更完善的方案,但它们背后的核心思想,都是将可能引发不一致的并行操作进行串行化。这实际上也是现代分布式系统处理一致性问题的基础思路。另外,由于普通计算机硬件和软件的可靠性不足,在工程实现上还要对核心部件稳定性进行加强。

    反过来,如果节点都很鲁棒,性能足够强,同时网络带宽足够大、延迟足够低,这样的集群系统往往更容易实现一致性。

    然而,真实情况可能比人们预期的糟糕。2015年,论文《Taming Uncertainty in Distributed Systems with Help from the Network》中指出,即便部署了专业设备和冗余网络的数据中心,每个月发生的网络故障高达 12 次。

    一致性的要求

    规范来看,分布式系统达成一致的过程,应该满足:

    • 可终止性(Termination):一致的结果在有限时间内能完成;
    • 约同性(Agreement):不同节点最终完成决策的结果是相同的;
    • 合法性(Validity):决策的结果必须是某个节点提出的提案。

    可终止性很容易理解。有限时间内完成,意味着可以保障提供服务(Liveness)。这是计算机系统可以被正常使用的前提。需要注意,在现实生活中这点并不是总能得到保障的。例如取款机有时候会出现“服务中断”;拨打电话有时候是“无法连接”的。

    约同性看似容易,实际上暗含了一些潜在信息。决策的结果相同,意味着算法要么不给出结果,任何给出的结果必定是达成了共识的,即安全性(Safety)。挑战在于算法必须要考虑的是可能会处理任意的情形。凡事一旦推广到任意情形,往往就不像看起来那么简单。例如现在就剩一张某区间(如北京 --> 南京)的车票了,两个售票处也分别刚通过某种方式确认过这张票的存在。这时,两家售票处几乎同时分别来了一个乘客要买这张票,从各自“观察”看来,自己一方的乘客都是先到的……这种情况下,怎么能达成对结果的共识呢?看起来很容易,卖给物理时间上率先提交请求的乘客即可。然而,对于两个来自不同位置的请求来说,要判断在时间上的“先后”关系并不是那么容易。两个车站的时钟时刻可能是不一致的;时钟计时可能不精确的……根据相对论的观点,不同空间位置的时间是不一致的。因此追求绝对时间戳的方案是不可行的,能做的是要对事件的发生进行排序。

    事件发生的相对先后顺序(逻辑时钟)十分重要,确定了顺序,就没有了分歧。这也是解决分布式系统领域很多问题的核心秘诀:把不同时空发生的多个事件进行全局唯一排序,而且这个顺序还得是大家都认可的

    如果存在可靠的物理时钟,实现排序往往更为简单。高精度的石英钟的漂移率为 ,最准确的原子震荡时钟的漂移率为 。Google 曾在其分布式数据库 Spanner 中采用基于原子时钟和 GPS 的“TrueTime”方案,能够将不同数据中心的时间偏差控制在 10ms 置信区间。在不考虑成本的前提下,这种方案简单、有效。然而,计算机系统的时钟误差要大得多,这就造成分布式系统达成一致顺序十分具有挑战。

    注:Leslie Lamport 在 1978 年发表的论文《Time, Clocks and the Ordering of Events in a Distributed System》中将分布式系统中顺序与相对论进行对比,提出了偏序关系的观点。而根据相对论,并不存在绝对的时间。因此,先后顺序可能更有意义。

    最后的合法性看似绕口,但其实比较容易理解,即达成的结果必须是节点执行操作的结果。仍以卖票为例,如果两个售票处分别决策某张票出售给张三和李四,那么最终达成一致的结果要么是张三,要么是李四,而不能是其他人。

    带约束的一致性

    从前面的分析可以看到,要实现绝对理想的严格一致性(Strict Consistency)代价很大。除非系统不发生任何故障,而且所有节点之间的通信无需任何时间,此时整个系统其实就等价于一台机器了。实际上,越强的一致性要求往往意味着带来越弱的处理性能,以及越差的可扩展性。根据实际需求的不用,人们可能选择不同强度的一致性,包括强一致性(Strong Consistency)和弱一致性(Weak Consistency)。

    一般地,强一致性主要包括下面两类:

    • 顺序一致性(Sequential Consistency):又叫因果一致性,最早由 Leslie Lamport 1979 年经典论文《How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs》中提出,是一种比较强的约束。所有进程看到的全局执行顺序(total order)一致(否则数据副本就不一致了);并且每个进程看自身操作的顺序(local order)跟实际发生顺序一致。例如,某进程先执行 A,后执行 B,则实际得到的全局结果(其它进程也看到这个结果)中就应该为 A 在 B 前面,而不能反过来。如果另外一个进程先后执行了C、D操作,则全局顺序可以共识为 A、B、C、D 或 A、C、B、D 或 C、A、B、D 或 C、D、A、B 的一种(即 A、B 和 C、D 的组合),决不能出现 B、A 或 D、C。顺序一致性实际上限制了各进程内指令的偏序关系,但不在进程间按照物理时间进行全局排序,属于实践中可行的最强保证。以算盘为例,每个进程的事件是某根横轴上的算珠,它们可以前后拨动(改变不同进程之间先后顺序),但同一个横轴上的算珠的相对先后顺序无法改变。
    • 线性一致性(Linearizability Consistency):Maurice P. Herlihy 与 Jeannette M. Wing 在 1990 年经典论文《Linearizability: A Correctness Condition for Concurrent Objects》中共同提出,是一种更强的保证。在顺序一致性前提下加强了进程间的操作排序,形成理想化的全局顺序。线性一致性要求系统看起来似乎只有一个数据副本,客户端操作都是原子的,并且顺序执行;所有进程的操作似乎是实时同步的,并且跟实际发生顺序一致。例如某个客户端写入成功,则其它客户端将立刻看到最新的值。线性一致性下所有进程的所有事件似乎都处于同一个横轴,存在唯一的先后顺序。线性一致性很难实现,目前基本上要么依赖于全局的时钟或锁,要么通过一些复杂同步算法,性能往往不高。

    强一致的系统往往比较难实现,而且很多场景下对一致性的需求并没有那么强。因此,可以适当放宽对一致性的要求,降低系统实现的难度。例如在一定约束下实现所谓最终一致性(Eventual Consistency),即总会存在一个时刻(而不是立刻),让系统达到一致的状态。例如电商购物时将某物品放入购物车,但是可能在最终付款时才提示物品已经售罄了。实际上,大部分的 Web 系统为了保持服务的稳定,实现的都是最终一致性。

    相对强一致性,类似最终一致性这样在某些方面弱化的一致性,被笼统称为弱一致性。

    共识算法

    共识(Consensus),很多时候会见到与一致性(Consistency)术语放在一起讨论。严谨地讲,两者的含义并不完全相同。

    一致性的含义比共识宽泛,在不同场景(基于事务的数据库、分布式系统等)下意义不同。具体到分布式系统场景下,一致性指的是多个副本对外呈现的状态。如前面提到的顺序一致性、线性一致性,描述了多节点对数据状态的共同维护能力。而共识,则特指在分布式系统中多个节点之间对某个事情(例如多个事务请求,先执行谁?)达成一致看法的过程。因此,达成某种共识并不意味着就保障了一致性。

    实践中,要保障系统满足不同程度的一致性,往往需要通过共识算法来达成。

    共识算法解决的是分布式系统对某个提案(Proposal),大部分节点达成一致意见的过程。提案的含义在分布式系统中十分宽泛,如多个事件发生的顺序、某个键对应的值、谁是主节点……等等。可以认为任何可以达成一致的信息都是一个提案。

    对于分布式系统来讲,各个节点通常都是相同的确定性状态机模型(又称为状态机复制问题,State-Machine Replication),从相同初始状态开始接收相同顺序的指令,则可以保证相同的结果状态。因此,系统中多个节点最关键地是对多个事件的顺序进行共识,即排序。

    注:计算机世界里采用的是典型的“多数人暴政”,足够简单、高效。

    问题与挑战

    无论是在现实生活中,还是计算机世界里,达成共识都要解决两个基本的问题:

    • 首先,如何提出一个待共识的提案?如通过令牌传递、随机选取、权重比较、求解难题……等;
    • 其次,如何让多个节点对该提案达成共识(同意或拒绝),如投票、规则验证……等。

    理论上,如果分布式系统中各节点都能以十分“理想”的性能(瞬间响应、超高吞吐)稳定运行,节点之间通信瞬时送达(如量子纠缠),则实现共识过程并不十分困难,简单地通过广播进行瞬时投票和应答即可。

    可惜地是,现实中这样的“理想”系统并不存在。不同节点之间通信存在延迟(光速物理限制、通信处理延迟),并且任意环节都可能存在故障(系统规模越大,发生故障可能性越高)。如通信网络会发生中断、节点会发生故障、甚至存在被入侵的节点故意伪造消息,破坏正常的共识过程。

    一般地,把出现故障(Crash 或 Fail-stop,即不响应)但不会伪造信息的情况称为“非拜占庭错误(Non-Byzantine Fault)”或“故障错误(Crash Fault)”;伪造信息恶意响应的情况称为“拜占庭错误”(Byzantine Fault),对应节点为拜占庭节点。显然,后者场景中因为存在“捣乱者”更难达成共识。

    此外,任何处理都需要成本,共识也是如此。当存在一定信任前提(如接入节点都经过验证、节点性能稳定、安全保障很高)时,达成共识相对容易,共识性能也较高;反之在不可信的场景下,达成共识很难,需要付出较大成本(如时间、经济、安全等),而且性能往往较差(如工作量证明算法)。

    注:非拜占庭场景的典型例子是通过报数来统计人数,即便偶有冲突(如两人同时报一个数)也能很快解决;拜占庭场景的一个常见例子是“杀人游戏”,当参与者众多时很难快速达成共识。

    常见算法

    根据解决的场景是否允许拜占庭错误情况,共识算法可以分为 Crash Fault Tolerance (CFT) 和 Byzantine Fault Tolerance(BFT)两类。

    对于非拜占庭错误的情况,已经存在不少经典的算法,包括 Paxos(1990 年)、Raft(2014 年)及其变种等。这类容错算法往往性能比较好,处理较快,容忍不超过一半的故障节点。

    对于要能容忍拜占庭错误的情况,包括 PBFT(Practical Byzantine Fault Tolerance,1999 年)为代表的确定性系列算法、PoW(1997 年)为代表的概率算法等。确定性算法一旦达成共识就不可逆转,即共识是最终结果;而概率类算法的共识结果则是临时的,随着时间推移或某种强化,共识结果被推翻的概率越来越小,最终成为事实上结果。拜占庭类容错算法往往性能较差,容忍不超过 1/3 的故障节点。

    此外,XFT(Cross Fault Tolerance,2015 年)等最近提出的改进算法可以提供类似 CFT 的处理响应速度,并能在大多数节点正常工作时提供 BFT 保障。

    Algorand 算法(2017 年)基于 PBFT 进行改进,通过引入可验证随机函数解决了提案选择的问题,理论上可以在容忍拜占庭错误的前提下实现更好的性能(1000+ TPS)。

    注:实践中,对客户端来说要拿到共识结果需要自行验证,典型地,可访问足够多个服务节点来比对结果,确保获取结果的准确性。

    理论界限

    科学家都喜欢探寻问题最坏情况的理论界限。那么,共识问题的最坏界限在哪里呢?很不幸,在推广到任意情况时,分布式系统的共识问题无通用解。

    这似乎很容易理解,当多个节点之间的通信网络自身不可靠情况下,很显然,无法确保实现共识(例如,所有涉及共识的消息都丢失)。那么,对于一个设计得当,可以大概率保证消息正确送达的网络,是不是一定能获得共识呢?

    理论证明告诉我们,即便在网络通信可靠情况下,一个可扩展的分布式系统的共识问题通用解法的下限是——没有下限(无解)。

    这个结论,被称为“FLP 不可能原理”。该原理极其重要,可以看做是分布式领域里的“测不准原理”。

    注:不光分布式系统领域,实际上很多领域都存在类似测不准原理的约束,或许说明世界本源就存在限制。

    FLP 不可能原理

    定义

    FLP 不可能原理:在网络可靠,但允许节点失效(即便只有一个)的最小化异步模型系统中,不存在一个可以解决一致性问题的确定性共识算法(No completely asynchronous consensus protocol can tolerate even a single unannounced process death)。

    提出并证明该定理的论文《Impossibility of Distributed Consensus with One Faulty Process》是由 Fischer,Lynch 和 Patterson 三位科学家于 1985 年发表,该论文后来获得了 Dijkstra(就是发明最短路径算法的那位计算机科学家)奖。

    FLP 不可能原理告诉我们,不要浪费时间,去试图为异步分布式系统设计面向任意场景的共识算法

    如何理解

    要正确理解 FLP 不可能原理,首先要弄清楚“异步”的含义。

    在分布式系统中,同步和异步这两个术语存在特殊的含义。

    • 同步,是指系统中的各个节点的时钟误差存在上限;并且消息传递必须在一定时间内完成,否则认为失败;同时各个节点完成处理消息的时间是一定的。因此同步系统中可以很容易地判断消息是否丢失。
    • 异步,则意味着系统中各个节点可能存在较大的时钟差异;同时消息传输时间是任意长的;各节点对消息进行处理的时间也可能是任意长的。这就造成无法判断某个消息迟迟没有被响应是哪里出了问题(节点故障还是传输故障?)。不幸地是,现实生活中的系统往往都是异步系统。

    FLP 不可能性在论文中以图论的形式进行了严格证明。要理解其基本原理并不复杂,一个不严谨的例子如下。

    三个人在不同房间,进行投票(投票结果是 0 或者 1)。彼此可以通过电话进行沟通,但经常有人会时不时睡着。比如某个时候,A 投票 0,B 投票 1,C 收到了两人的投票,然后 C 睡着了。此时,A 和 B 将永远无法在有限时间内获知最终的结果,究竟是 C 没有应答还是应答的时间过长。如果可以重新投票,则类似情形可以在每次取得结果前发生,这将导致共识过程永远无法完成。

    FLP 原理实际上说明对于允许节点失效情况下,纯粹异步系统无法确保共识在有限时间内完成。即便对于非拜占庭错误的前提下,包括 Paxos、Raft 等算法也都存在无法达成共识的极端情况,只是在工程实践中这种情况出现的概率很小。

    那么,这是否意味着研究共识算法压根没有意义?

    不必如此悲观。学术研究,往往考虑地是数学和物理意义上理想化的情形,很多时候现实世界要稳定得多(感谢这个世界如此鲁棒!)。例如,上面例子中描述的最坏情形,每次都发生的概率其实并没有那么大。工程实现上某次共识失败,再尝试几次,很大可能就成功了。

    科学告诉你什么是不可能的;工程则告诉你,付出一些代价,可以把它变成可行。

    这就是科学和工程不同的魅力。FLP 不可能原理告诉大家不必浪费时间去追求完美的共识方案,而要根据实际情况设计可行的工程方案。

    那么,退一步讲,在付出一些代价的情况下,共识能做到多好?

    回答这一问题的是另一个很出名的原理:CAP 原理。

    注:科学告诉你去赌场是愚蠢的,因为最终总会输钱;工程则告诉你,如果你愿意接受最终输钱的风险,中间说不定能偶尔小赢几笔呢!

    CAP 原理

    CAP 原理最早出现在 2000 年,由加州大学伯克利分校的 Eric Brewer 教授在 ACM 组织的 Principles of Distributed Computing(PODC)研讨会上提出猜想。两年后,麻省理工学院的 Nancy Lynch 等学者进行了理论证明。

    该原理被认为是分布式系统领域的重要原理之一,深刻影响了分布式计算与系统设计的发展。

    定义

    CAP 原理:分布式系统无法同时确保一致性(Consistency)、可用性(Availability)和分区容忍性(Partition),设计中往往需要弱化对某个特性的需求。

    一致性、可用性和分区容忍性的具体含义如下:

    • 一致性(Consistency):任何事务应该都是原子的,所有副本上的状态都是事务成功提交后的结果,并保持强一致;
    • 可用性(Availability):系统(非失败节点)能在有限时间内完成对操作请求的应答;
    • 分区容忍性(Partition):系统中的网络可能发生分区故障(成为多个子网,甚至出现节点上线和下线),即节点之间的通信无法保障。而网络故障不应该影响到系统正常服务。

    CAP 原理认为,分布式系统最多只能保证三项特性中的两项特性。

    比较直观地理解,当网络可能出现分区时候,系统是无法同时保证一致性和可用性的。要么,节点收到请求后因为没有得到其它节点的确认而不应答(牺牲可用性),要么节点只能应答非一致的结果(牺牲一致性)。

    由于大部分时候网络被认为是可靠的,因此系统可以提供一致可靠的服务;当网络不可靠时,系统要么牺牲掉一致性(多数场景下),要么牺牲掉可用性。

    注意:网络分区是可能存在的,出现分区情况后很可能会导致发生“脑裂”现象。

    应用场景

    既然 CAP 三种特性不可同时得到保障,则设计系统时候必然要弱化对某个特性的支持。

    弱化一致性

    对结果一致性不敏感的应用,可以允许在新版本上线后过一段时间才最终更新成功,期间不保证一致性。

    例如网站静态页面内容、实时性较弱的查询类数据库等,简单分布式同步协议如 Gossip,以及 CouchDB、Cassandra 数据库等,都为此设计。

    弱化可用性

    对结果一致性很敏感的应用,例如银行取款机,当系统故障时候会拒绝服务。MongoDB、Redis、MapReduce 等为此设计。

    Paxos、Raft 等共识算法,主要处理这种情况。在 Paxos 类算法中,可能存在着无法提供可用结果的情形,同时允许少数节点离线。

    弱化分区容忍性

    现实中,网络分区出现概率较小,但很难完全避免。

    两阶段的提交算法,某些关系型数据库以及 ZooKeeper 主要考虑了这种设计。

    实践中,网络可以通过双通道等机制增强可靠性,实现高稳定的网络通信。

    ACID 原则与多阶段提交

    ACID 原则

    ACID,即 Atomicity(原子性)、Consistency(一致性)、Isolation(隔离性)、Durability(持久性)四种特性的缩写。

    ACID 也是一种比较出名的描述一致性的原则,通常出现在分布式数据库等基于事务过程的系统中。

    具体来说,ACID 原则描述了分布式数据库需要满足的一致性需求,同时允许付出可用性的代价。

    • Atomicity:每次事务是原子的,事务包含的所有操作要么全部成功,要么全部不执行。一旦有操作失败,则需要回退状态到执行事务之前;
    • Consistency:数据库的状态在事务执行前后的状态是一致的和完整的,无中间状态。即只能处于成功事务提交后的状态;
    • Isolation:各种事务可以并发执行,但彼此之间互相不影响。按照标准 SQL 规范,从弱到强可以分为未授权读取、授权读取、可重复读取和串行化四种隔离等级;
    • Durability:状态的改变是持久的,不会失效。一旦某个事务提交,则它造成的状态变更就是永久性的。

    与 ACID 相对的一个原则是 eBay 技术专家 Dan Pritchett 提出的 BASE(Basic Availability,Soft-state,Eventual Consistency)原则。BASE 原则面向大型高可用分布式系统,主张牺牲掉对强一致性的追求,而实现最终一致性,来换取一定的可用性。

    注:ACID 和 BASE 在英文中分别是“酸”和“碱”,看似对立,实则是对 CAP 三特性的不同取舍。

    两阶段提交

    对于分布式事务一致性的研究成果包括著名的两阶段提交算法(Two-phase Commit,2PC)和三阶段提交算法(Three-phase Commit,3PC)。

    两阶段提交算法最早由 Jim Gray 于 1979 年在论文《Notes on Database Operating Systems》中提出。其基本思想十分简单,既然在分布式场景下,直接提交事务可能出现各种故障和冲突,那么可将其分解为预提交和正式提交两个阶段,规避冲突的风险。

    • 预提交:协调者(Coordinator)发起提交某个事务的申请,各参与执行者(Participant)需要尝试进行提交并反馈是否能完成;
    • 正式提交:协调者如果得到所有执行者的成功答复,则发出正式提交请求。如果成功完成,则算法执行成功。

    在此过程中任何步骤出现问题(例如预提交阶段有执行者回复预计无法完成提交),则需要回退。

    两阶段提交算法因为其简单容易实现的优点,在关系型数据库等系统中被广泛应用。当然,其缺点也很明显。整个过程需要同步阻塞导致性能一般较差;同时存在单点问题,较坏情况下可能一直无法完成提交;另外可能产生数据不一致的情况(例如协调者和执行者在第二个阶段出现故障)。

    三阶段提交

    三阶段提交针对两阶段提交算法第一阶段中可能阻塞部分执行者的情况进行了优化。具体来说,将预提交阶段进一步拆成两个步骤:尝试预提交和预提交。

    完整过程如下:

    • 尝试预提交:协调者询问执行者是否能进行某个事务的提交。执行者需要返回答复,但无需执行提交。这就避免出现部分执行者被无效阻塞住的情况。
    • 预提交:协调者检查收集到的答复,如果全部为真,则发起提交事务请求。各参与执行者(Participant)需要尝试进行提交并反馈是否能完成;
    • 正式提交:协调者如果得到所有执行者的成功答复,则发出正式提交请求。如果成功完成,则算法执行成功。

    其实,无论两阶段还是三阶段提交,都只是一定程度上缓解了提交冲突的问题,并无法一定保证系统的一致性。首个有效的算法是后来提出的 Paxos 算法。

    Paxos 算法与 Raft 算法

    Paxos 问题是指分布式的系统中存在故障(crash fault),但不存在恶意(corrupt)节点的场景(即可能消息丢失或重复,但无错误消息)下的共识达成问题。这也是分布式共识领域最为常见的问题。因为最早是 Leslie Lamport 用 Paxos 岛的故事模型来进行描述,而得以命名。解决 Paxos 问题的算法主要有 Paxos 系列算法和 Raft 算法。

    Paxos 算法

    1988 年,Brian M. Oki 和 Barbara H. Liskov 在论文《Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems》中首次提出了解决 Paxos 问题的算法。

    1990 年由 Leslie Lamport 在论文《The Part-time Parliament》中提出的 Paxos 共识算法,在工程角度实现了一种最大化保障分布式系统一致性(存在极小的概率无法实现一致)的机制。Paxos 算法本质上与前者相同,被广泛应用在 Chubby、ZooKeeper 这样的分布式系统中。Leslie Lamport 作为分布式系统领域的早期研究者,因为相关杰出贡献获得了 2013 年度图灵奖。

    论文中为了描述问题编造了一个虚构故事:在古代爱琴海的 Paxos 岛,议会如何通过表决来达成共识。议员们通过信使传递消息来对议案进行表决。但议员可能离开,信使可能走丢,甚至重复传递消息。

    Paxos 是首个得到证明并被广泛应用的共识算法,其原理类似 两阶段提交 算法,进行了泛化和扩展,通过消息传递来逐步消除系统中的不确定状态。

    作为后来很多共识算法(如 Raft、ZAB 等)的基础,Paxos 算法基本思想并不复杂,但最初论文中描述比较难懂,甚至连发表也几经波折。2001 年,Leslie Lamport 还专门发表论文《Paxos Made Simple》进行重新解释。

    基本原理

    算法中存在三种逻辑角色的节点,在实现中同一节点可以担任多个角色。

    • 提案者(Proposer):提出一个提案,等待大家批准(Chosen)为结案(Value)。系统中提案都拥有一个自增的唯一提案号。往往由客户端担任该角色。
    • 接受者(Acceptor):负责对提案进行投票,接受(Accept)提案。往往由服务端担任该角色。
    • 学习者(Learner):获取批准结果,并帮忙传播,不参与投票过程。可为客户端或服务端。

    算法需要满足安全性(Safety) 和存活性(Liveness)两方面的约束要求。实际上这两个基础属性也是大部分分布式算法都该考虑的。

    • Safety:保证决议(Value)结果是对的,无歧义的,不会出现错误情况。
      • 只有是被提案者提出的提案才可能被最终批准;
      • 在一次执行中,只批准(chosen)一个最终决议。被多数接受(accept)的结果成为决议;
    • Liveness:保证决议过程能在有限时间内完成。
      • 决议总会产生,并且学习者能获得被批准的决议。

    基本思路类似两阶段提交:多个提案者先要争取到提案的权利(得到大多数接受者的支持);成功的提案者发送提案给所有人进行确认,得到大部分人确认的提案成为批准的结案。

    Paxos 并不保证系统总处在一致的状态。但由于每次达成共识至少有超过一半的节点参与,这样最终整个系统都会获知共识结果。一个潜在的问题是提案者在提案过程中出现故障,这可以通过超时机制来缓解。极为凑巧的情况下,每次新一轮提案的提案者都恰好故障,又或者两个提案者恰好依次提出更新的提案,则导致活锁,系统会永远无法达成共识(实际发生概率很小)。

    Paxos 能保证在超过一半的节点正常工作时,系统总能以较大概率达成共识。读者可以试着自己设计一套非拜占庭容错下基于消息传递的异步共识方案,会发现在满足各种约束情况下,算法过程总会十分类似 Paxos 的过程。这也是为何 Google Chubby 的作者 Mike Burrows 说:“这个世界上只有一种一致性算法,那就是 Paxos(There is only one consensus protocol, and that's Paxos)”。

    下面,由简单情况逐步推广到一般情况来探讨算法过程。

    单个提案者+多接受者

    如果系统中限定只允许某个特定节点是提案者,那么共识结果很容易能达成(只有一个方案,要么达成,要么失败)。提案者只要收到了来自多数接受者的投票,即可认为通过,因为系统中不存在其他的提案。

    但此时一旦提案者故障,则整个系统无法工作。

    多个提案者+单个接受者

    限定某个特定节点作为接受者。这种情况下,共识也很容易达成,接受者收到多个提案,选第一个提案作为决议,发送给其它提案者即可。

    缺陷也是容易发生单点故障,包括接受者故障或首个提案者节点故障。

    以上两种情形其实类似主从模式,虽然不那么可靠,但因为原理简单而被广泛采用。

    当提案者和接受者都推广到多个的情形,会出现一些挑战。

    多个提案者+多个接受者

    既然限定单提案者或单接受者都会出现故障,那么就得允许出现多个提案者和多个接受者。问题一下子变得复杂了。

    一种情况是同一时间片段(如一个提案周期)内只有一个提案者,这时可以退化到单提案者的情形。需要设计一种机制来保障提案者的正确产生,例如按照时间、序列、或者大家猜拳(出一个参数来比较)之类。考虑到分布式系统要处理的工作量很大,这个过程要尽量高效,满足这一条件的机制非常难设计。

    另一种情况是允许同一时间片段内可以出现多个提案者。那同一个节点可能收到多份提案,怎么对他们进行区分呢?这个时候采用只接受第一个提案而拒绝后续提案的方法也不适用。很自然的,提案需要带上不同的序号。节点需要根据提案序号来判断接受哪个。比如接受其中序号较大(往往意味着是接受新提出的,因为旧提案者故障概率更大)的提案。

    如何为提案分配序号呢?一种可能方案是每个节点的提案数字区间彼此隔离开,互相不冲突。为了满足递增的需求可以配合用时间戳作为前缀字段。

    同时允许多个提案,意味着很可能单个提案人无法集齐足够多的投票;另一方面,提案者即便收到了多数接受者的投票,也不敢说就一定通过。因为在此过程中投票者无法获知其它投票人的结果,也无法确认提案人是否收到了自己的投票。因此,需要实现两个阶段的提交过程。

    两阶段的提交

    提案者发出提案申请之后,会收到来自接受者的反馈。一种结果是提案被大多数接受者接受了,一种结果是没被接受。没被接受的话,可以过会再重试。即便收到来自大多数接受者的答复,也不能认为就最终确认了。因为这些接受者自己并不知道自己刚答复的提案可以构成大多数的一致意见。

    很自然的,需要引入新的一个阶段,即提案者在第一阶段拿到所有的反馈后,需要再次判断这个提案是否得到大多数的支持,如果支持则需要对其进行最终确认。

    Paxos 里面对这两个阶段分别命名为准备(Prepare)和提交(Commit)。准备阶段通过锁来解决对哪个提案内容进行确认的问题,提交阶段解决大多数确认最终值的问题。

    准备阶段

    • 提案者发送自己计划提交的提案的编号到多个接受者,试探是否可以锁定多数接受者的支持。
    • 接受者时刻保留收到过提案的最大编号和接受的最大提案。如果收到提案号比目前保留的最大提案号还大,则返回自己已接受的提案值(如果还未接受过任何提案,则为空)给提案者,更新当前最大提案号,并说明不再接受小于最大提案号的提案。

    提交阶段

    • 提案者如果收到大多数的回复(表示大部分人听到它的请求),则可准备发出带有刚才提案号的接受消息。如果收到的回复中不带有新的提案,说明锁定成功。则使用自己的提案内容;如果返回中有提案内容,则替换提案值为返回中编号最大的提案值。如果没收到足够多的回复,则需要再次发出请求。
    • 接受者收到接受消息后,如果发现提案号不小于已接受的最大提案号,则接受该提案,并更新接受的最大提案。

    一旦多数接受者接受了共同的提案值,则形成决议,成为最终确认。

    Raft 算法

    Paxos 算法虽然给出了共识设计,但并没有讨论太多实现细节,也并不重视工程上的优化,因此后来在学术界和工程界出现了一些改进工作,包括 Fast Paxos、Multi-Paxos,Zookeeper Atomic Broadcast(ZAB)和 Raft 等。这些算法重点在于改进执行效率和可实现性。

    其中,Raft 算法由斯坦福大学的 Diego Ongaro 和 John Ousterhout 于 2014 年在论文《In Search of an Understandable Consensus Algorithm》中提出,基于 Multi-Paxos 算法进行重新简化设计和实现,提高了工程实践性。Raft 算法的主要设计思想与 ZAB 类型,通过先选出领导节点来简化流程和提高效率。实现上分解了领导者选举、日志复制和安全方面的考虑,并通过约束减少了不确定性的状态空间。

    算法包括三种角色:领导者(Leader)、候选者(Candidate) 和跟随者(Follower),每个任期内选举一个全局的领导者。领导者角色十分关键,决定日志(log)的提交。每个日志都会路由到领导者,并且只能由领导者向跟随者单向复制。

    典型的过程包括两个主要阶段:

    • 领导者选举:开始所有节点都是跟随者,在随机超时发生后未收到来自领导者或候选者消息,则转变角色为候选者(中间状态),提出选举请求。最近选举阶段(Term)中得票超过一半者被选为领导者;如果未选出,随机超时后进入新的阶段重试。领导者负责从客户端接收请求,并分发到其他节点;
    • 同步日志:领导者会决定系统中最新的日志记录,并强制所有的跟随者来刷新到这个记录,数据的同步是单向的,确保所有节点看到的视图一致。

    此外,领导者会定期向所有跟随者发送心跳消息,跟随者如果发现心跳消息超时未收到,则可以认为领导者已经下线,尝试发起新的选举过程。

    拜占庭问题与算法

    拜占庭问题(Byzantine Problem)又叫拜占庭将军(Byzantine Generals Problem)问题,讨论的是允许存在少数节点作恶(消息可能被伪造)场景下的如何达成共识问题。拜占庭容错(Byzantine Fault Tolerant,BFT)讨论的是容忍拜占庭错误的共识算法。

    两将军问题

    拜占庭问题之前,学术界就已经存在两将军问题的讨论(《Some constraints and tradeofis in the design of network communications》,1975 年):两个将军要通过信使来达成进攻还是撤退的约定,但信使可能迷路或被敌军阻拦(消息丢失或伪造),如何达成一致?根据 FLP 不可能原理,这个问题无通用解。

    拜占庭问题

    拜占庭问题最早由 Leslie Lamport 等学者于 1982 年在论文《The Byzantine Generals Problem》中正式提出,是用来解释异步系统中共识问题的一个虚构模型。拜占庭是古代东罗马帝国的首都,由于地域宽广,假设其守卫边境的多个将军(系统中的多个节点)需要通过信使来传递消息,达成某些一致决定。但由于将军中可能存在叛徒(系统中节点出错),这些叛徒将向不同的将军发送不同的消息,试图干扰共识的达成。

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

    在大多数的分布式系统中,拜占庭的场景并不多见。然而在特定场景下存在意义,例如允许匿名参与的系统(如比特币),或是出现欺诈可能造成巨大损失的情况。

    问题的解决

    论文中指出,对于拜占庭问题来说,假如节点总数为 N,故障节点数为 F,则当 N >= 3F + 1 时,问题才能有解,由 BFT 算法进行保证。

    例如,N = 3,F = 1 时。

    若提案人不是叛变者,提案人发送一个提案出来,收到的叛变者可以宣称收到的是相反的命令。则对于第三个人(忠诚者)会收到两个相反的消息,无法判断谁是叛变者,则系统无法达到一致。

    若提案人是叛变者,发送两个相反的提案分别给另外两人,另外两人都收到两个相反的消息,无法判断究竟谁是叛变者,则系统无法达到一致。

    更一般的,当提案人不是叛变者,提案人提出提案信息 1,则对于合作者来看,系统中会有 N - F 份确定的信息 1,和 F 份不确定的信息(可能为 0 或 1,假设叛变者会尽量干扰一致的达成),N − F > F,即 N > 2F 情况下才能达成一致。

    当提案人是叛变者,会尽量发送相反的提案给 N - F 个合作者,从收到 1 的合作者看来,系统中会存在 (N - F)/2 个信息 1,以及 (N - F)/2 个信息 0;从收到 0 的合作者看来,系统中会存在 (N - F)/2 个信息 0,以及 (N - F)/2 个信息 1;

    另外存在 F − 1 个不确定的信息。合作者要想达成一致,必须进一步的对所获得的消息进行判定,询问其他人某个被怀疑对象的消息值,并通过取多数来作为被怀疑者的信息值。这个过程可以进一步递归下去。

    Leslie Lamport 等人在论文《Reaching agreement in the presence of faults》中证明,当叛变者不超过 1/3 时,存在有效的拜占庭容错算法(最坏需要 F+1 轮交互)。反之,如果叛变者过多,超过 1/3,则无法保证一定能达到一致结果。

    那么,当存在多于 1/3 的叛变者时,有没有可能存在解决方案呢?

    设想 F 个叛变者和 L 个忠诚者,叛变者故意使坏,可以给出错误的结果,也可以不响应。某个时候 F 个叛变者都不响应,则 L 个忠诚者取多数既能得到正确结果。当 F 个叛变者都给出一个恶意的提案,并且 L 个忠诚者中有 F 个离线时,剩下的 L - F 个忠诚者此时无法分别是否混入了叛变者,仍然要确保取多数能得到正确结果,因此,L - F > F,即 L > 2F 或 N - F > 2F,所以系统整体规模 N 要大于 3F。

    能确保达成共识的拜占庭系统节点数至少为 4,此时最多允许出现 1 个坏的节点。

    拜占庭容错算法

    拜占庭容错算法(Byzantine Fault Tolerant)是面向拜占庭问题的容错算法,解决的是在网络通信可靠,但节点可能故障和作恶情况下如何达成共识。

    拜占庭容错算法最早的讨论可以追溯到 Leslie Lamport 等人 1982 年 发表的论文《The Byzantine Generals Problem》,之后出现了大量的改进工作,代表性成果包括《Optimal Asynchronous Byzantine Agreement》(1992 年)、《Fully Polynomial Byzantine Agreement for n>3t Processors in t+1 Rounds》(1998 年)等。长期以来,拜占庭问题的解决方案都存在运行过慢,或复杂度过高的问题,直到“实用拜占庭容错算法”(Practical Byzantine Fault Tolerance,PBFT) 算法的提出。

    1999 年,这一算法由 Castro 和 Liskov 于论文《Practical Byzantine Fault Tolerance and Proactive Recovery》中提出。该算法基于前人工作(特别是 Paxos 相关算法,因此也被称为 Byzantine Paxos)进行了优化,首次将拜占庭容错算法复杂度从指数级降低到了多项式级,目前已得到广泛应用。其可以在恶意节点不超过总数 1/3 的情况下同时保证 Safety 和 Liveness。

    PBFT 算法采用密码学相关技术(RSA 签名算法、消息验证编码和摘要)确保消息传递过程无法被篡改和破坏。

    算法整体的基本过程如下:

    • 首先,通过轮换或随机算法选出某个节点为主节点,此后只要主节点不切换,则称为一个视图(View)。
    • 在某个视图中,客户端将请求 <REQUEST,operation,timestamp,client> 发送给主节点,主节点负责广播请求到所有其它副本节点。
    • 所有节点处理完成请求,将处理结果 <REPLY,view,timestamp,client,id_node,response> 返回给客户端。客户端检查是否收到了至少 f+1 个来自不同节点的相同结果,作为最终结果。

    主节点广播过程包括三个阶段的处理:预准备(Pre-Prepare)、准备(Prepare)和提交(Commit)。预准备和准备阶段确保在同一个视图内请求发送的顺序正确;准备和提交阶段则确保在不同视图之间的确认请求是保序的。

    • 预准备阶段:主节点为从客户端收到的请求分配提案编号,然后发出预准备消息 <<PRE-PREPARE,view,n,digest>,message> 给各副本节点,其中 message 是客户端的请求消息,digest 是消息的摘要。
    • 准备阶段:副本节点收到预准备消息后,检查消息。如消息合法,则向其它节点发送准备消息 <PREPARE,view,n,digest,id>,带上自己的 id 信息,同时接收来自其它节点的准备消息。收到准备消息的节点对消息同样进行合法性检查。验证通过则把这个准备消息写入消息日志中。集齐至少 2f+1 个验证过的消息才进入准备状态。
    • 提交阶段:广播 commit 消息,告诉其它节点某个提案 n 在视图 v 里已经处于准备状态。如果集齐至少 2f+1 个验证过的 commit 消息,则说明提案通过。

    具体实现上还包括视图切换、checkpoint 等机制,读者可自行参考论文内容,在此不再赘述。

    拜占庭容错类的算法因为要考虑最恶意的存在“捣乱”者的情况,在大规模场景下共识性能往往会受到影响。

    新的解决思路

    拜占庭问题之所以难解,在于任何时候系统中都可能存在多个提案(因为提案成本很低),并且在大规模场景下要完成最终确认的过程容易受干扰,难以达成共识。

    2014 年,斯坦福的 Christopher Copeland 和 Hongxia Zhong 在论文《Tangaroa: a byzantine fault tolerant raft》中提出在 Raft 算法基础上借鉴 PBFT 算法的一些特性(包括签名、恶意领导探测、选举校验等)来实现拜占庭容错性,兼顾可实现性和鲁棒性。该论文也启发了 Kadena 等项目的出现,实现更好性能的拜占庭算法。

    2017 年,MIT 计算机科学与人工智能实验室(CSAIL)的 Yossi Gilad 和 Silvio Micali 等人在论文《Algorand: Scaling Byzantine Agreements for Cryptocurrencies》中针对 PBFT 算法在很多节点情况下性能不佳的问题,提出先选出少量记账节点,然后再利用可验证随机函数(Verifiable Random Function,VRF)来随机选取领导节点,避免全网直接做共识,将拜占庭算法扩展到了支持较大规模的应用场景,同时保持较好的性能(1000+ tps)。

    此外,康奈尔大学的 Rafael Pass 和 Elaine Shi 在论文《The Sleepy Model of Consensus》中还探讨了在动态场景(大量节点离线情况)下如何保障共识的安全性,所提出的 Sleepy Consensus 算法可以在活跃诚实节点达到一半以上时确保完成拜占庭共识。

    2018 年,清华大学的 Chenxing Li 等在论文《Scaling Nakamoto Consensus to Thousands of Transactions per Second》中提出了 Conflux 共识协议。该协议在 GHOST 算法基础上改善了安全性,面向公有区块链场景下,理论上能达到 6000+ tps。

    比特币网络在设计时使用了 PoW(Proof of Work)的概率型算法思路,从如下两个角度解决大规模场景下的拜占庭容错问题。

    首先,限制一段时间内整个网络中出现提案的个数(通过工作量证明来增加提案成本);其次是丢掉最终确认的约数,约定好始终沿着已知最长的链进行拓展。共识的最终确认是概率意义上的存在。这样,即便有人试图恶意破坏,也会付出相应的经济代价(超过整体系统一半的工作量)。

    后来的各种 PoX 系列算法,也都是沿着这个思路进行改进,采用经济博弈来制约攻击者。

    可靠性指标

    可靠性(Availability),或者说可用性,是描述系统可以提供服务能力的重要指标。高可靠的分布式系统,往往需要各种复杂的机制来进行保障。

    通常情况下,服务的可用性可以用服务承诺(Service Level Agreement,SLA SLA)、服务指标(Service Level Indicator,SLI)、服务目标(Service Level Objective,SLO)等方面进行衡量。

    几个 9 的指标

    完美的可靠性是不存在的。很多领域里谈到服务的高可靠性,通常都会用“几个 9”的指标来进行衡量。

    “几个 9”的指标,其实是概率意义上粗略反映了系统能提供服务的可靠性指标,最初是电信领域提出的概念。

    下表给出不同指标下,每年允许服务出现不可用时间的参考值。

    指标概率可靠性每年允许不可用时间典型场景
    一个 990%1.2 个月简单测试
    二个 999%3.6 天普通单点
    三个 999.9%8.6 小时普通集群
    四个 999.99%51.6 分钟高可用
    五个 999.999%5 分钟电信级
    六个 999.9999%31 秒极高要求
    七个 999.99999%3 秒N/A

    一般来说,单点的服务器系统至少应能满足两个 9;普通企业信息系统三个 9 就肯定足够了(大家可以统计下自己企业内因系统维护每年要停多少时间),系统能达到四个 9 已经是领先水平了(参考 AWS 等云计算平台)。电信级的应用一般需要能达到五个 9,这已经很厉害了,一年里面最多允许出现五分钟左右的服务不可用。六个 9 以及以上的系统,就更加少见了,要实现往往意味着极高的代价。

    两个核心时间

    一般地,描述系统出现故障的可能性和故障出现后的恢复能力,有两个基础的指标:MTBF 和 MTTR。

    • MTBF:Mean Time Between Failures,平均故障间隔时间,即系统可以无故障运行的预期时间。
    • MTTR:Mean Time To Repair,平均修复时间,即发生故障后,系统可以恢复到正常运行的预期时间。

    MTBF 衡量了系统发生故障的频率,如果一个系统的 MTBF 很短,则往往意味着该系统可用性低;而 MTTR 则反映了系统碰到故障后服务的恢复能力,如果系统的 MTTR 过长,则说明系统一旦发生故障,需要较长时间才能恢复服务。

    一个高可用的系统应该是具有尽量长的 MTBF 和尽量短的 MTTR。

    提高可靠性

    那么,该如何提升可靠性呢?有两个基本思路:一是让系统中的单个组件都变得更可靠;二是干脆消灭单点。

    IT 从业人员大都有类似的经验,普通笔记本电脑,基本上是过一阵可能就要重启下;而运行 Linux/Unix 系统的专用服务器,则可能连续运行几个月甚至几年时间都不出问题。另外,普通的家用路由器,跟生产级别路由器相比,更容易出现运行故障。这些都是单个组件可靠性不同导致的例子,可以通过简单升级单点的软硬件来改善可靠性。

    然而,依靠单点实现的可靠性毕竟是有限的。要想进一步的提升,那就只好消灭单点,通过主从、多活等模式让多个节点集体完成原先单点的工作。这可以从概率意义上改善服务对外整体的可靠性,这也是分布式系统的一个重要用途。

    本章小结

    分布式系统是计算机学科中十分重要的一个领域。随着集群规模的不断增长,所处理的数据量越来越大,对于性能、可靠性的要求越来越高,分布式系统相关技术已经变得越来越重要,起到的作用也越来越关键。

    分布式系统中如何保证共识是个经典问题,无论在学术上还是工程上都存在很高的研究价值。令人遗憾地是,理想的(各项指标均最优)解决方案并不存在。在现实各种约束条件下,往往需要通过牺牲掉某些需求,来设计出满足特定场景的协议。通过本章的学习,读者可以体会到在工程应用中的类似设计技巧。

    实际上,工程领域中不少问题都不存在一劳永逸的通用解法;而实用的解决思路,都在于合理地在实际需求和条件限制之间进行灵活的取舍(trade-off)。

    展开全文
  • 区块链:核心技术概览

    万次阅读 2019-05-17 18:14:00
    本章将带领大家探索区块链的核心技术,包括其定义与原理、关键的问题等,还将探讨区块链技术的演化,并对未来发展的趋势进行展望。最后,对一些常见的认识误区进行了澄清。 定义与原理 定义 区块链技术自身...
  • 步态识别的核心技术介绍

    千次阅读 2019-03-25 14:26:38
    1 人形跟踪技术 人形跟踪技术使用深度卷积神经网络提取行人的表观特征,并结合行人运动轨迹的动态特征,共同得到人的运动轨迹和位置,并支持实时的多人同时跟踪,其算法实际在 GPU 上运行可达到毫秒级别。 2 基于...
  • 云计算核心技术知识体系

    万次阅读 多人点赞 2018-08-14 20:55:44
    云计算核心技术知识体系  众所周知,云计算的服务模式可以认为包括以下几个层次:基础设施即服务(IaaS),平台即服务(PaaS)和软件即服务(SaaS)。在这三层服务模式中,使用到了云计算的绝大部分核心技术。下面...
  • 让我们来看看2018人工智能标准化白皮书里面,对人工智能关键技术的定义。 人工智能技术关系到人工智能产品是否可以顺利应用到我们的生活场景中。在人工智能领域,它普遍包含了机器学习、知识图谱、自然语言处理、人...
  • 新能源汽车三大核心技术

    千次阅读 2020-04-23 22:06:00
    在新能源汽车的整个平台架构中,VCU (Vehicle Control Unit 整车控制器)、MCU (Moter Control Unit 电机控制器)和 BMS (BATTERY MANAGEMENT SYSTEM 电池管理系统)是最重要核心技术,对整车的动力、经济、...
  • 阿里“去IOE”核心技术剖析

    万次阅读 2013-09-01 23:51:03
    本次大会的主题为“软件定义未来”,阿里技术保障部DBA负责人——周宝方在大会上发表演讲,他表示,斯诺登事件让更多企业考虑去IOE的必要,但是去IOE拥有很高的技术门槛,较大的额技术风险,水很深。 他认为,...
  • 人工智能的五大核心技术

    万次阅读 2018-11-08 21:04:19
    人工智能的五大核心技术
  • 工业互联网平台需要解决多类工业设备接入、多源工业数据集成、海量数据管理与处理、工业数据建模分析、工业应用创新与集成、工业知识积累迭代实现等一系列问题,涉及七大类关键技术,分别为数据集成和边缘处理技术、...
  • 云计算的核心技术全解读

    万次阅读 2018-06-12 16:47:45
    实用:云计算的核心技术全解读云计算的“横空出世”让很多人将其视为一项全新的技术,但事实上它的雏形已出现多年,只是最近几年才开始取得相对较快的发展。与其说云计算是技术的创新,不如说云计算是思维和商业模式...
  • 大数据核心技术ETL简介

    千次阅读 2015-08-25 14:53:12
    前几篇文章都是根据自己所见所知,在前人的基础上加以整合,对大数据概念有了初步...核心技术 架构挑战: 1、对现有数据库管理技术的挑战。 2、经典数据库技术并没有考虑数据的多类别(variety)、SQL(结构化
  • 阿里云的核心技术要点

    万次阅读 2017-11-20 00:00:00
    虚拟化是云计算最重要核心技术之一,它为云计算服务提供基础架构层面的支撑,是ICT服务快速走向云计算的最主要驱动力。可以说,没有虚拟化技术也就没有云计算服务的落地与成功。随着云计算应用的持续升温,业内对...
  • 目录 一、分布式事物:本地事务和分布式事务(2PC+3PC)+传统分布式事务的问题 (一)本地事务和分布式事务(2PC+3PC) (1)两阶段提交协议2PC (2)三阶段提交协议3PC ...分区容错PartitionToler...
  • 20大5G关键技术

    千次阅读 多人点赞 2019-07-14 10:00:00
    戳蓝字“CSDN云计算”关注我们哦!来源|北京物联网智能技术应用协会5G网络技术主要分为三类:核心网、回传和前传网络、无线接入网。核心核心关键技术主要包括:网络...
  • 在近日上海举行的2019 QCon全球软件开发大会上,华为云区块链高级产品经理王磊在华为云技术专场《技术裂变中的可信软件开发》中发表演讲,分享了区块链在当前社会应用的社会价值,介绍了华为云在区块链技术方向上的...
  • 技术负责人」这一称呼其实比较泛了。往大了讲,可以指 CTO、技术VP、技术总监,往小了讲,可以指 小组Leader、技术主管、架构师 等。 这些不同岗位的「技术负责人」在工作中会处理着各不相同的问题,因此对他能力...
  • 大数据分析6个核心技术

    万次阅读 2018-08-17 16:14:07
    大数据分析6个核心技术   目前,大数据领域每年都会涌现出大量新的技术,成为大数据获取、存储、处理分析或可视化的有效手段。大数据技术能够将大规模数据中隐藏的信息和知识挖掘出来,为人类社会经济活动提供...
  • 算法的重要性

    万次阅读 2013-07-22 17:57:13
    许多学生看到一些公司在招聘时要求的编程语言五花八门就产生了一种误解,认为学计算机就是学各种编程语言,或者认为,学习最新的语言、技术、标准就是最好的铺路方法。其实大家都被这些公司误导了。编
  • 大数据方面核心技术有哪些?

    万次阅读 2019-04-18 17:42:38
    大数据技术的体系庞大且复杂,基础的技术包含数据的采集、数据预处理、分布式存储、NoSQL数据库、数据仓库、机器学习、并行计算、可视化等各种技术范畴和不同的技术层面。首先给出一个通用化的大数据处理框架,主要...
  • 论语音识别三大关键技术

    万次阅读 多人点赞 2018-05-04 07:47:07
    论语音识别三大关键技术 李...数据、算法及芯片是语音识别技术的3个关键,大量优质的数据、精准快速的算法和高性能语音识别芯片是提升语音识别的核心。语音是人工智能产品的主要入口,乃兵家必争之地也。相关算法...
  • 大数据技术十大核心原理

    千次阅读 2020-03-04 21:59:51
    究竟大数据技术核心原理是哪几方面呢? 数据即价值是目前计算机领域极其推崇的观念。数据无论多少都被归结为大数据,数据分析越来越热门,资本也对贴有大数据标签的公司趋之若鹜。如同流动的数字货币一样被一再的...
  • Java核心技术 卷1 基础知识

    万次阅读 2019-04-09 09:31:25
    网站 ...> CiCi岛 下载 电子版仅供预览及学习交流使用,下载后请24小时内删除,支持正版,喜欢的请购买正版书籍 ...购买正版 ... 根据Java SE 8全面更新,系统全面讲解Java语言的核心概念、语法...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 271,751
精华内容 108,700
关键字:

关键核心技术的重要性