从分布式一致性算法到区块链共识机制

引言

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

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

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

分布式一致性问题的挑战

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

Crash Fault

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

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

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

Byzantine Fault

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

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

拜占庭问题示意图

(https://lisk.io/academy/blockchain-basics/how-does-blockchain-work/byzantine-fault-tolerance-explained)

应对风险—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的研究

(http://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf ),一致性算法按照网络模型可以分为三大类:

  • 部分同步网络模型(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不可能定理示意图

(https://www.slideshare.net/oryband/the-stellar-blockchain-and-the-story-of-the-federated-consensusblockchain-academy)

另外,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理论示意图

(https://www.researchgate.net/figure/Visualization-of-CAP-theorem_fig2_282679529)

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

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

(https://people.eecs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf)

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

分布式一致性算法

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

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通信与决策过程

(https://ongardie.net/static/raft/userstudy/paxos.pdf)

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来实现的。

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

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

Raft协议概览

(https://ongardie.net/static/raft/userstudy/raft.pdf)

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算法正常运作过程

(http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf)

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,通常适用于存在权限控制的、节点数目较少的、较为可信的分布式网络环境中。

在联盟链中的应用

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

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

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

  • HyperLedger Fabric(https://www.hyperledger.org/projects/fabric ) 在v1.0中可以使用Solo和Kafka pubsub系统来实现ordering;在v1.4版本也引入了Raft算法

    (https://hyperledger-fabric.readthedocs.io/en/release-1.4/orderer/ordering_service.html );目前这些均是CFT类算法,而raft的引入主要也是为后期支持BFT类算法铺平道路( Raft is the first step toward Fabric’s development of a byzantine fault tolerant (BFT) ordering service. As we’ll see, some decisions in the development of Raft were driven by this. )。

  • R3 Corda

    (https://www.r3.com/corda-platform/ )也采用了可插拔式的共识算法设计,不仅可以选择高速度、高可信环境的Raft算法,也可以选择低速度、低可信环境的BFT类算法

    (https://docs.corda.net/key-concepts-notaries.html )。

  • 以太坊企业联盟EEA

    (https://entethalliance.org/ )也支持BFT类算法、Raft算法,以及PoET算法

    (https://entethalliance.org/wp-content/uploads/2018/05/EEA-TS-0001-0-v1.00-EEA-Enterprise-Ethereum-Specification-R1.pdf )。

  • 蚂蚁区块链BaaS平台

    (https://tech.antfin.com/blockchain )也采用了PBFT算法。

Permissionless网络的挑战

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

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

去中心化的意义

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

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

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

去中心化的三个维度

(https://medium.com/@VitalikButerin/the-meaning-of-decentralization-a0c92b76a274)

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

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

如果你认为这个问题是必要的、有意义的,那么能否找到一种解决方案,可以让这个世界变得更可信,让你不再需要“被迫相信”某个陌生人,而是提供一种“证明”,足以确保与你交易的某个陌生人是可信的?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)。
比特币交易过程

(https://www.giottus.com/Bitcoin)

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

我们忍不住要问,既然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等人(https://socrates1024.s3.amazonaws.com/consensus.pdf: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的思想

(https://bitcointalk.org/index.php?topic=27787.0 ),而后不断发展完善,得到越来越多人的信赖。

PoS的基本思想大致如下:

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

(https://hackernoon.com/consensus-mechanisms-explained-pow-vs-pos-89951c66ae10)

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

PoS为什么有效?

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

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

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

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

  • 一类是如前所述的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,则控制比特币体系需要大约比特币市值的一半,大概是400~1600亿美金(比特币价格区间5000~20000美金),显然这一数字远远高于矿机成本,想拥有这么大资金量发动攻击几乎是不可能的,从这个角度来讲,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过

(https://www.nichanank.com/blog/2018/6/4/consensus-algorithms-pos-dpos)

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

在公有链中的应用

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

  • 以太坊

    (Ethereum:https://www.ethereum.org/ ):目前阶段以太坊仍然采用的是PoW挖矿机制,不过作为以太坊的创始人和公有链领域的领军人物Vitalik Buterin对于PoS机制显然更为青睐,也多次阐述过PoS的设计哲学(https://medium.com/@VitalikButerin/a-proof-of-stake-design-philosophy-506585978d51 ),以及PoS相比PoW的优势(https://github.com/ethereum/wiki/wiki/Proof-of-Stake-FAQ#what-are-the-benefits-of-proof-of-stake-as-opposed-to-proof-of-work )。目前以太坊正在开发基于PoS的Casper协议(https://arxiv.org/pdf/1710.09437.pdf),预计将于今年下半年发布,这种从PoW到PoS的转变也标志着以太坊进入2.0时代。如下图所示,在以太坊2.0 phase0阶段,将会发布采用Casper协议的PoS beacon chain,作为coordination layer(https://github.com/ethereum/wiki/wiki/Sharding-roadmap )。

以太坊2.0 layers和phases

(https://docs.ethhub.io/ethereum-roadmap/ethereum-2.0/eth-2.0-phases/)

  • EOS(https://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等。
一致性算法概览

(https://101blockchains.com/consensus-algorithms-blockchain/)

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

一切关乎信任

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

信任的机器

(https://www.economist.com/leaders/2015/10/31/the-trust-machine)

总结

这个世界充满了不确定性,计算机科学也一样。从计算机出现开始,我们就不得不面对机器硬件的不确定性:意外故障可能带来的问题。从互联网兴起开始,我们就不得不面对网络的不确定性:通讯消息可能的延迟、乱序、丢失。而应对不确定性问题最自然的解法就是冗余,通过大量节点来实现系统整体的安全性,避免单点故障,增强容错能力和抵御攻击的能力。正是基于此,才带来了大型分布式网络的蓬勃发展,而如何在不确定的网络和节点间寻找到某种确定性,协调众多节点间的一致性,正是分布式一致性算法需要解决的问题。能够应对故障类错误的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. https://101blockchains.com/consensus-algorithms-blockchain/
  3. Comparative Analysis of Blockchain Consensus Algorithms
  4. https://draveness.me/consensus
  5. https://yeasy.gitbooks.io/blockchain_guide/content/distribute_system/consensus.html
  6. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.67.6951&rep=rep1&type=pdf
  7. https://dba.stackexchange.com/questions/18435/cap-theorem-vs-base-nosql
  8. https://www.quora.com/What-is-the-difference-between-CAP-and-BASE-and-how-are-they-related-with-each-other
  9. http://ug93tad.github.io/flpcap/
  10. https://ramcloud.stanford.edu/~ongaro/userstudy/paxos.pdf

    更多参考资料请点击阅读原文进入查看!

怎么用API网关构建微服务|架构

当选择将应用程序构建为一组微服务时,需要确定应用程序客户端如何与微服务交互。在单体应用程序中,只有一组(通常是重复的、负载均衡的)端点。然而,在微服务架构中,每个微服务都会暴露一组通常是细粒度的端点。在本文中,我们将讨论一下这对客户端与应用程序之间的通信有什么影响,并提出一种使用API网关的方法。

让我们想象一下,你要为一个购物应用程序开发一个原生移动客户端。你很可能需要实现一个产品详情页面,上面展示任何指定产品的信息。

例如,下图展示了在Amazon Android移动应用中滚动产品详情时看到的内容。

虽然这是个智能手机应用,产品详情页面也显示了大量的信息。例如,该页面不仅包含基本的产品信息(如名称、描述、价格),而且还显示了如下内容:

购物车中的件数;

订单历史;

客户评论;

低库存预警;

送货选项;

各种推荐,包括经常与该产品一起购买的其它产品,购买该产品的客户购买的其它产品,购买该产品的客户看过的其它产品;

可选的购买选项。

当使用单体应用程序架构时,移动客户端将通过向应用程序发起一次REST调用(GET api.company.com/productdetails/<productId>)来获取这些数据。负载均衡器将请求路由给N个相同的应用程序实例中的一个。然后,应用程序会查询各种数据库表,并将响应返回给客户端。

相比之下,当使用微服务架构时,产品详情页面显示的数据归多个微服务所有。下面是部分可能的微服务,它们拥有要显示在示例中产品详情页面上的数据:

购物车服务——购物车中的件数;

订单服务——订单历史;

目录服务——产品基本信息,如名称、图片和价格;

评论服务——客户的评论;

库存服务——低库存预警;

送货服务——送货选项、期限和费用,这些单独从送货方的API获取;

推荐服务——建议的产品。

我们需要决定移动客户端如何访问这些服务。让我们看看都有哪些选项。

客户端与微服务直接通信

从理论上讲,客户端可以直接向每个微服务发送请求。每个微服务都有一个公开的端点(https ://<serviceName>.api.company.name)。该URL将映射到微服务的负载均衡器,由它负责在可用实例之间分发请求。为了获取产品详情,移动客户端将逐一向上面列出的N个服务发送请求。

遗憾的是,这种方法存在挑战和局限。一个问题是客户端需求和每个微服务暴露的细粒度API不匹配。在这个例子中,客户端需要发送7个独立请求。在更复杂的应用程序中,可能要发送更多的请求。例如,按照Amazon的说法,他们在显示他们的产品页面时就调用了数百个服务。然而,客户端通过LAN发送许多请求,这在公网上可能会很低效,而在移动网络上就根本不可行。这种方法还使得客户端代码非常复杂。

客户端直接调用微服务的另一个问题是,部分服务使用的协议不是Web友好协议。一个服务可能使用Thrift二进制RPC,而另一个服务可能使用AMQP消息传递协议。不管哪种协议都不是浏览器友好或防火墙友好的,最好是内部使用。在防火墙之外,应用程序应该使用诸如HTTP和WebSocket之类的协议。

这种方法的另一个缺点是,它会使得微服务难以重构。随着时间推移,我们可能想要更改系统划分成服务的方式。例如,我们可能合并两个服务,或者将一个服务拆分成两个或更多服务。然而,如果客户端与微服务直接通信,那么执行这类重构就非常困难了。

由于这些问题的存在,客户端与微服务直接通信很少是合理的。

使用API网关

通常,一个更好的方法是使用所谓的API网关。API网关是一个服务器,是系统的唯一入口。从面向对象设计的角度看,它与外观模式类似。API网关封装了系统内部架构,为每个客户端提供一个定制的API。它可能还具有其它职责,如身份验证、监控、负载均衡、缓存、“请求整形(request shaping)”与管理、静态响应处理。

下图展示了API网关通常如何融入架构:

API网关负责服务请求路由、组合及协议转换。客户端的所有请求都首先经过API网关,然后由它将请求路由到合适的微服务。API网管经常会通过调用多个微服务并合并结果来处理一个请求。它可以在Web协议(如HTTP与WebSocket)与内部使用的非Web友好协议之间转换。

API网关还能为每个客户端提供一个定制的API。通常,它会向移动客户端暴露一个粗粒度的API。例如,考虑下产品详情的场景。API网关可以提供一个端点(/productdetails?productid=xxx),使移动客户端可以通过一个请求获取所有的产品详情。API网关通过调用各个服务(产品信息、推荐、评论等等)并合并结果来处理请求。

Netflix API网关是一个很好的API网关实例。Netflix流服务提供给数以百计的不同类型的设备使用,包括电视、机顶盒、智能手机、游戏系统、平板电脑等等。最初,Netflix试图为他们的流服务提供一个通用的API。然而他们发现,由于各种各样的设备都有自己独特的需求,这种方式并不能很好地工作。如今,他们使用一个API网关,通过运行特定于设备的适配器代码来为每个设备提供一个定制的API。通常,一个适配器通过调用平均6到7个后端服务来处理每个请求。Netflix API网关每天处理数十亿请求。

API网关的优点和不足

如你所料,使用API网关有优点也有不足。使用API网关的最大优点是,它封装了应用程序的内部结构。客户端只需要同网关交互,而不必调用特定的服务。API网关为每一类客户端提供了特定的API。这减少了客户端与应用程序间的交互次数,还简化了客户端代码。

API网关也有一些不足。它增加了一个我们必须开发、部署和维护的高可用组件。还有一个风险是,API网关变成了开发瓶颈。为了暴露每个微服务的端点,开发人员必须更新API网关。API网关的更新过程要尽可能地简单,这很重要。否则,为了更新网关,开发人员将不得不排队等待。

不过,虽然有这些不足,但对于大多数现实世界的应用程序而言,使用API网关是合理的。

实现API网关

到目前为止,我们已经探讨了使用API网关的动机及其优缺点。下面让我们看一下需要考虑的各种设计问题。

性能和可扩展性

只有少数公司有Netflix的规模,每天需要处理数十亿请求。不管怎样,对于大多数应用程序而言,API网关的性能和可扩展性通常都非常重要。因此,将API网关构建在一个支持异步、I/O非阻塞的平台上是合理的。有多种不同的技术可以用于实现一个可扩展的API网关。在JVM上,可以使用一种基于NIO的框架,比如Netty、Vertx、Spring Reactor或JBoss Undertow中的一种。一个非常流行的非JVM选项是Node.js,它是一个以Chrome JavaScript引擎为基础构建的平台。另一个选项是使用NGINX Plus。NGINX Plus提供了一个成熟的、可扩展的、高性能Web服务器和一个易于部署的、可配置可编程的反向代理。NGINX Plus可以管理身份验证、访问控制、负载均衡请求、缓存响应,并提供应用程序可感知的健康检查和监控。

使用响应式编程模型

API网关通过简单地将请求路由给合适的后端服务来处理部分请求,而通过调用多个后端服务并合并结果来处理其它请求。对于部分请求,比如产品详情相关的多个请求,它们对后端服务的请求是独立于其它请求的。为了最小化响应时间,API网关应该并发执行独立请求。然而,有时候,请求之间存在依赖。在将请求路由到后端服务之前,API网关可能首先需要调用身份验证服务验证请求的合法性。类似地,为了获取客户意愿清单中的产品信息,API网关必须首先获取包含那些信息的客户资料,然后再获取每个产品的信息。关于API组合,另一个有趣的例子是Netflix Video Grid。

使用传统的异步回调方法编写API组合代码会让你迅速坠入回调地狱。代码会变得混乱、难以理解且容易出错。一个更好的方法是使用响应式方法以一种声明式样式编写API网关代码。响应式抽象概念的例子有Scala中的Future、Java 8中的CompletableFuture和JavaScript中的Promise,还有最初是微软为.NET平台开发的Reactive Extensions(RX)。Netflix创建了RxJava for JVM,专门用于他们的API网关。此外,还有RxJS for JavaScript,它既可以在浏览器中运行,也可以在Node.js中运行。使用响应式方法将使你可以编写简单但高效的API网关代码。

服务调用

基于微服务的应用程序是一个分布式系统,必须使用一种进程间通信机制。有两种类型的进程间通信机制可供选择。一种是使用异步的、基于消息传递的机制。有些实现使用诸如JMS或AMQP那样的消息代理,而其它的实现(如Zeromq)则没有代理,服务间直接通信。另一种进程间通信类型是诸如HTTP或Thrift那样的同步机制。通常,一个系统会同时使用异步和同步两种类型。它甚至还可能使用同一类型的多种实现。总之,API网关需要支持多种通信机制。

服务发现

API网关需要知道它与之通信的每个微服务的位置(IP地址和端口)。在传统的应用程序中,或许可以硬连线这个位置,但在现代的、基于云的微服务应用程序中,这并不是一个容易解决的问题。基础设施服务(如消息代理)通常会有一个静态位置,可以通过OS环境变量指定。但是,确定一个应用程序服务的位置没有这么简单。应用程序服务的位置是动态分配的。而且,单个服务的一组实例也会随着自动扩展或升级而动态变化。总之,像系统中的其它服务客户端一样,API网关需要使用系统的服务发现机制,可以是服务器端发现,也可以是客户端发现。下一篇文章将更详细地描述服务发现。现在,需要注意的是,如果系统使用客户端发现,那么API网关必须能够查询服务注册中心,这是一个包含所有微服务实例及其位置的数据库。

处理局部失败

在实现API网关时,还有一个问题需要处理,就是局部失败的问题。该问题在所有的分布式系统中都会出现,无论什么时候,当一个服务调用另一个响应慢或不可用的服务,就会出现这个问题。API网关永远不能因为无限期地等待下游服务而阻塞。不过,如何处理失败取决于特定的场景以及哪个服务失败。例如,在产品详情场景下,如果推荐服务无响应,那么API网关应该向客户端返回产品详情的其它内容,因为它们对用户依然有用。推荐内容可以为空,也可以,比如说,用一个固定的TOP 10列表取代。不过,如果产品信息服务无响应,那么API网关应该向客户端返回一个错误信息。

如果缓存数据可用,那么API网关还可以返回缓存数据。例如,由于产品价格不经常变化,所以如果价格服务不可用,API网关可以返回缓存的价格数据。数据可以由API网关自己缓存,也可以存储在像Redis或Memcached那样的外部缓存中。通过返回默认数据或者缓存数据,API网关可以确保系统故障不影响用户的体验。

在编写代码调用远程服务方面,Netflix Hystrix是一个异常有用的库。Hystrix会将超出设定阀值的调用超时。它实现了一个“断路器(circuit breaker)”模式,可以防止客户端对无响应的服务进行不必要的等待。如果服务的错误率超出了设定的阀值,那么Hystrix会切断断路器,在一个指定的时间范围内,所有请求都会立即失败。Hystrix允许用户定义一个请求失败后的后援操作,比如从缓存读取数据,或者返回一个默认值。如果你正在使用JVM,那么你绝对应该考虑使用Hystrix。而如果你正在使用一个非JVM环境,那么你应该使用一个等效的库。

小结

对于大多数基于微服务的应用程序而言,实现一个API网关是有意义的,它可以作为系统的唯一入口。API网关负责服务请求路由、组合及协议转换。它为每个应用程序客户端提供一个定制的API。API网关还可以通过返回缓存数据或默认数据屏蔽后端服务失败。在本系列的下一篇文章中,我们将探讨服务间通信。

from:http://www.tuicool.com/articles/bMnEbmv

Must-Watch JavaScript

This is a collection of well-received talks about JavaScript, covering topics such as ES6, JavaScript frameworks, client-side apps, mobile integration, JavaScript performance, tooling, leveling up, and more.

Like CSS? Check out Must-Watch CSS! For other great lists check out @sindresorhus‘s curated list of awesome lists.

2018

  1. In the Loop: Jake Archibald, JSConf.Asia 35:11
  2. 10 Things I Regret About Node.js: Ryan Dahl, JSConf.EU 26:41
  3. Deep Learning in JS: Ashi Krishnan, JSConf.EU 31:30

2017

  1. Immutable Data Structures for Functional JS: Anjana Vakil, JSConf.EU 26:32
  2. JavaScript Engines – How Do They Even?: Franziska Hinkelmann, JSConf.EU 25:13
  3. Async + Await: Wes Bos, dotJS 15:51
  4. Advanced Async and Concurrency Patterns in JavaScript: Kyle Simpson, js.la Meetup 39:42
  5. The Browser Hackers Guide to Instantly Loading Everything: Addy Osmani, JSConf.EU 28:09

2016

  1. The Rise of Async JavaScript: Jeremy Fairbank, FluentConf 28:58
  2. Reasonable JavaScript: Preethi Kasireddy, Nodevember 50:12
  3. Learning Functional Programming with JavaScript: Anjana Vakil, JSUnconf 29:56
  4. Choosing a JavaScript Framework: Rob Eisenberg, NDC Oslo 1:01:13
  5. The Myth of The “Real JavaScript Developer”: Brenna O’Brien, Front-Trends 27:05
  6. An Angular 2 Force Awakens: John Papa, ng-conf 20:39
  7. React.js for TV UIs: Steve McGuire, Netflix JavaScript Talks 35:02
  8. The Hitchhiker’s Guide to All Things Memory in JavaScript: Safia Abdalla, JSConf Budapest 26:16
  9. SVG and GreenSock for Complex Animation: Sarah Drasner, ForwardJS Summit 40:16

2015

  1. JavaScript in 2015: Glen Maddern, (screencast) 10:32
  2. Angular + React = Speed: Dave Smith, ng-conf 19:26
  3. Parallelism Experiments in JavaScript: Naveed Ihsanullah, JSConf.US 32:39
  4. Eliminate JavaScript Code Smells: Elijah Manor, FluentConf 29:15
  5. Pocket-Sized JS: Henrik Joreteg, dotJS 18:44
  6. What the… JavaScript?: Kyle Simpson, ForwardJS 38:16
  7. Real World jQuery: Ben Foxall, jQuery UK 26:45
  8. JavaScript State of the Union: Geoff Schmidt, Meteor Devshop SF 48:47
  9. Dirty Performance Secrets of HTML5: Andreas Gal, FluentConf 14:15
  10. You Should Use <Insert Library/Framework>, It’s the Bestestest!: Paul Lewis, ffconf 33:31
  11. Async Programming in ES7: Jafar Husain, JSConf.US 35:56
  12. Live React: Hot Reloading with Time Travel: Dan Abramov, ReactEurope 30:40
  13. JavaScript Transformation: Sebastian McKenzie, JSConf.US 20:23
  14. Node.js at Netflix: Kim Trott, Node.js Interactive 25:17
  15. If You Wish to Learn ES6/2015 From Scratch, You Must First Invent the Universe: Ashley Williams, JSConf.US 25:48

2014

  1. Enemy of the State: Amy Palamountain,Forward JS 32:40
  2. Mary Live-Codes a JavaScript Game from Scratch: Mary Rose Cook, Front-Trends 32:16
  3. Unorthodox Performance: John-David Dalton, ForwardJS 43:39
  4. What the Heck Is the Event Loop Anyway?: Philip Roberts, JSConf.EU 26:53
  5. Building Isomorphic Apps: Spike Brehm, JSConf.Asia 45:01
  6. JavaScript for Everybody: Marcy Sutton, JSConf.EU 28:59
  7. JavaScript ♥ Unicode: Mathias Bynens, JSConf.EU 25:41
  8. Using AngularJS to Create iPhone & Android Applications with PhoneGap: Daniel Zen, ng-conf 21:34
  9. Virtual Machines, JavaScript and Assembler: Scott Hanselman, FluentConf 25:56
  10. User Interface Algorithms: Mark DiMarco, JSConf.US 27:41
  11. End to End Angular Testing with Protractor: Julie Ralph, ng-conf 18:46
  12. Async JavaScript at Netflix: Jafar Husain, Netflix JavaScript Talks 28:38
  13. Building Realtime Apps with Firebase and Angular: Anant Narayanan, ng-conf 21:08

2013

  1. A JavaScript Web App Deconstructed: Alex MacCaw, JSConf.Asia 36:24
  2. JavaScript in Your Native Mobile Apps: Allen Pike, JSConf.EU 25:47
  3. JavaScript Masterclass: Angelina Fabbro, JSConf.US 22:33
  4. A Comparison of the Two-Way Binding in AngularJS, EmberJS and KnockoutJS: Marius Gundersen, JSConf.EU 19:16
  5. Hacker Way: Rethinking Web App Development at Facebook: Tom Occhino, Jing Chen, and Pete Hunt, F8 44:35
  6. Promises and Generators: Control Flow Utopia: Forbes Lindesay, JSConf.EU 31:26
  7. How to Rewrite Your JS App (at Least) 10 Times: Garann Means, Fronteers 47:45
  8. Front-End Development in Node.js: Raquel Vélez, jQuery Conference Portland 34:01
  9. Front-End Tools for the Young Developer: Christian Vuerings, SF HTML5 User Group 14:16
  10. Rethinking Best Practices: Pete Hunt, JSConf.Asia 40:57
  11. Righteous Javascript, Dude!: Zach Bruggerman, Cascadia JS 18:15
  12. Transitioning Groupon to NodeJS: Sean McCullough, EmpireJS 28:23
  13. Building Modular Web Applications: How To Build a Good Component: Angelina Fabbro, jQuery Conference Portland 35:02
  14. Making JS More Learnable: Pamela Fox, dotJS 28:46
  15. The Web Experience in the Autistic Spectrum: Natalia Berdys, JSConf.EU 30:37
  16. Return of Inspector Web: Web Components a Year Later: Angelina Fabbro, Fronteers 49:44
  17. Develop High Performance Sites and Apps with JavaScript and HTML5: Dr. Doris Chen, HTML5DevConf Meetup 1:01:39
  18. Building Reflow: Kristofer Joseph, BackboneConf 45:41
  19. Levelling Up in AngularJS: Alicia Liu, HTML5DevConf 40:31

2012

  1. A Novel, Efficient Approach to JavaScript Loading: Malte Ubl and John Hjelmstad, JSConf.EU 26:36
  2. To Hell with jQuery: Karolina Szczur, JSConf.EU 20:00
  3. Is Node.js Better?: Brian Ford, JSConf.US 41:42
  4. Inspector Web and the Mystery of the Shadow DOM: Angelina Fabbro, JSConfEU 28:42
  5. Maintainable JavaScript: Nicholas Zakas, FluentConf 47:04
  6. Client Side Internationalization: Alex Sexton, JSConf.EU 24:08

from:https://github.com/AllThingsSmitty/must-watch-javascript

函数式编程术语解析

函数式编程蔚然成风,越来越多的开源项目、技术交流在使用函数式编程的术语降低开发或沟通成本,这无形中对不了解函数式编程的开发者造成了一定的学习门槛,翻译本文的初衷就是要普及函数式编程的基本知识,从新的角度扩展编程思维。至于为什么要使用 JavaScript 演示函数式编程,一方面是因为 JavaScript 的特性在很多方面与函数式编程浑然天成,另一方面是因为 JavaScript 是世界上最 XX 的语言……

Arity

指函数的参数数量,由 -ary 和 -ity 这两个英文后缀拼接而成:

const sum = (a, b) => a + b;const arity = sum.length;console.log(arity); // => 2

Higher-Order Functions

高阶函数,此类函数可以接收其他函数作为参数,也可以返回一个函数作为返回值:

const filter = (pred, xs) => {   const result = [];   for (let idx = 0; idx < xs.length; idx++) {       if (pred(xs[idx])) {            result.push(xs[idx]);        }    }   return result;};const is = (type) => (x) => Object(x) instanceof type;filter(is(Number), [0, ‘1’, 2, null]); // => [0, 2]

Partial Application

偏函数,在原函数的基础上预填充(pre-filling)部分参数并返回的新函数:

// 下面是一个创建偏函数的辅助函数const partial = (f, …args) => (…moreArgs) => f(…args, …moreArgs);const add3 = (a, b, c) => a + b + c;// 预填充 (add3, 2, 3) 三个参数,空置最后一个参数,返回一个新的函数const fivePlus = partial(add3, 2, 3); // (c) => 2 + 3 + cfivePlus(4); // => 9

JavaScript 中的 Function.prototype.bind() 函数是创建偏函数的最简单方式:

const add1More = add3.bind(null, 2, 3); // => (c) => 2 + 3 + c

Currying

柯里化,将一个接收多个参数的函数转化为单参数函数的方式,转化后的函数每次只接收一个参数,然后返回一个新函数,新函数可以继续接收参数,直到接收到所有的参数:

const sum = (a, b) => a + b;sum(2, 3)// => 6const curriedSum = (a) => (b) => a + b;curriedSum(40)(2) // => 42.const add2 = curriedSum(2); // (b) => 2 + badd2(10) // => 12

Function Composition

函数合成,接收多个函数作为参数并返回一个新函数的方式,新函数按照传入的参数顺序,从右往左依次执行,前一个函数的返回值是后一个函数的输入值:

const compose = (f, g) => (a) => f(g(a))const floorAndToString = compose((val) => val.toString(), Math.floor)floorAndToString(121.212121) // => “121”

Purity

一个纯函数需要满足两个条件,第一是函数的返回值只能由输入值(函数接收的参数)决定,也就是说纯函数接收相同的参数会返回相同的值;第二是纯函数不会对自身作用域之外的运行环境产生副作用(side effects),比如说不会改变外部环境中变量的值,这会被认为是不安全的行为:

let greeting;const greet = () => greeting = “Hi, ” + window.name;// greet() 执行时更改了外部环境的变量greet(); // => “Hi, Brianne”

纯函数示例:

const greet = (name) => “Hi, ” + name ;greet(“Brianne”) // => “Hi, Brianne”

Side effects

如果函数或表达式与其自身作用域之外的可变数据(mutable data)发生了读写操作,那么此时函数和表达式就产生了副作用:

let greeting;const greet = () => greeting = “Hi, ” + window.name;// greet() 执行时更改了外部环境的变量greet(); // => “Hi, Brianne”// new Date() 是可变数据const differentEveryTime = new Date();// 这里表示系统接收到的输入值是不确定的,是一种可变数据console.log(“IO is a side effect!”);

Idempotent

幂等,同一个函数使用相同的参数嵌套执行多次的结果与执行一次的结果相同:

$$f(…f(f(x))…)=f(x)$$

Math.abs(Math.abs(10))sort(sort(sort([2,1])))

Point-Free Style

point-free style 是一种不显式向函数传递参数的代码风格,通常需要柯里化和高阶函数来实现:

const map = (fn) => (list) => list.map(fn);const add = (a) => (b) => a + b;// Not points-free// numbers 是一个显式传递的参数const incrementAll = (numbers) => map(add(1))(numbers);// Points-free// add(1) 的返回值隐式传递给了 map,作为 map 的 list 参数const incrementAll2 = map(add(1));

point-free style 的函数看起来就像是一个赋值表达式,没有使用我们常见的 function 或 => 等来声明其接收的参数。

Predicate

断言,一个返回布尔值的函数:

const predicate = (a) => a > 2;[1, 2, 3, 4].filter(predicate); // => [3, 4]

Contracts

TODO

Guarded Functions

TODO

Categories

categories 内部都绑定了具体的函数用于约束或执行特定的逻辑,比如 Monoid。

Value

任何可以赋值给变量的值都可以称为 value:

5Object.freeze({name: ‘John’, age: 30}) // The `freeze` function enforces immutability.(a) => a[1]undefined

Constant

常量,初始化后不能再次执行赋值操作的数据类型:

const five = 5const john = { name: ‘John’, age: 30 }// 因为常量不可变,所以下面表达式一定为 truejohn.age + five === ({ name: ‘John’, age: 30 }).age + (5)

常量具有 referentially transparent 的特性,也就是说将程序中出现的常量替换为它们实际的值,并不会影响程序的结果。译者话外:实际上在 JavaScript 中的 const 所声明的常量并不是完全稳定的,使用 Immutable.js 演示更加恰当:

const five = fromJS(5);const john = fromJS({name: ‘John’, age: 30})john.get(‘age’) + five === ({ name: ‘John’, age: 30 }).age + (5)

f(g()) === g

Functor

functor 都拥有 map 函数,并且在执行 map 之后会返回一个新的 functor:

object.map(x => x) === objectobject.map(x => f(g(x))) === object.map(g).map(f)

JavaScript 中最常见的 functor 就是数组类型的实例:

[1, 2, 3].map(x => x); // => [1, 2, 3]const f = x => x + 1;const g = x => x * 2;[1, 2, 3].map(x => f(g(x))); // => [3, 5, 7][1, 2, 3].map(g).map(f);     // => [3, 5, 7]

Pointed Functor

pointed functor 都拥有 of 函数,用于接收和构建 functor。ES2015 提供了 Array.of 函数,所以数组实例就可以看成是 pointed functor:

Array.of(1) // => [1]

Lift

lift 发生在你将值放入 functor 的时候,如果你将函数 lift 进了 Applicative Functor,那么就可以使用这个函数处理传递给这个 functor 的值。某些 lift 的实现拥有 lift 或 liftA2 函数,便于在 functor 上执行相关的函数:

const mult = (a, b) => a * b;const liftedMult = lift(mult); // => this function now works on functors like arrayliftedMult([1, 2], [3]); // => [3, 6]lift((a, b) => a + b)([1, 2], [3, 4]); // => [4, 5, 5, 6]

lift 一个单参数的函数非常类似于 map 操作:

const increment = (x) => x + 1;lift(increment)([2]); // => [3][2].map(increment); // => [3]

Referential Transparency

如果一个表达式可以被替换为实际的值而不影响程序的运行结果,那么我们就说这个表达式是 referentially transparent:

const greet = () => “Hello World!”;

以上面代码为例,任何调用 greet() 的地方都可以替换为 “Hello World!” 而不影响程序的执行结果。

Equational Reasoning

如果一个应用由多个表达式组合而成,且每个表达式都没有 side effect,那么这个应用就可以由部分推导出整体。

Lambda

匿名函数,本质上是一个 value:

function(a){   return a + 1;};(a) => a + 1;// Lambda 常用语高阶函数中[1, 2].map((a) => a + 1); // = [2, 3]// Lambda 作为 value 被赋值给变量let addOne = (a) => a + 1;

Lambda Calculus

数学的分支之一,使用函数创建通用的计算模型(universal model of computation)。

Lazy evaluation

惰性求值,是一种按需执行的求值策略,只有需要某个值时才会执行相关的表达式。在函数式编程语言中,这一特性可用于构造无限列表。

const rand = function*() {   while (true) {       yield Math.random();    }}const randIter = rand();randIter.next().value; // 每次执行 next() 函数都会返回一个新的随机数// 有且只有在执行 next() 的时候才会返回新值

Monoid

Monoid,通过一个函数“合并”两个同类型数据后返回相同的数据类型。最简单的 monoid 就是两数相加:

1 + 1; // => 2

这里的 + 就是上面所说的“合并”函数。Monoid 中存在恒等式的概念:

1 + 0// => 1// 这里的 0 就是恒等式// Monoid 还必须满足结合律1 + (2 + 3) === (1 + 2) + 3; // => true// 数组的 concat() 操作可以构造一个 monoid[1, 2].concat([3, 4]); // => [1, 2, 3, 4]// 空数组可以视为是恒等式[1, 2].concat([]); // => [1, 2]

如果知道了一个函数的的恒等式和“合并”函数 compose,函数本身就是一个 monoid:

const identity = (a) => a;const compose = (f, g) => (x) => f(g(x));compose(foo, identity) ≍ compose(identity, foo) ≍ foo

Monad

Monad,是一个拥有 of 和 chain 函数的数据类型,chain 类似于 map,但它会输出非嵌套形式的结果:

[‘cat,dog’, ‘fish,bird’].chain((a) => a.split(‘,’)) // => [‘cat’, ‘dog’, ‘fish’, ‘bird’][‘cat,dog’, ‘fish,bird’].map((a) => a.split(‘,’)) // => [[‘cat’, ‘dog’], [‘fish’, ‘bird’]]

在其他函数式编程语言中,of 也被称为 return,chain 也被称为 flatmap 和 bind。

Comonad

Comonad,拥有 extract 和 extend 函数的数据类型:

const CoIdentity = (v) => ({   val: v,    extract() { return this.val },    extend(f) { return CoIdentity(f(this)) }})// extract() 可以从 functor 中取值CoIdentity(1).extract() // => 1// extend() 可以返回新的 comonadCoIdentity(1).extend(co => co.extract() + 1) // => CoIdentity(2)

Applicative Functor

Applicative Functor,是拥有 ap 函数的数据类型,ap 函数可以将 functor 中的值转化为其他 functor 中的同类型值:

[(a) => a + 1].ap([1]) // => [2]

这一特性对于多个 applicative functor 需要接收多个参数时,就显得很有用:

const arg1 = [1, 2];const arg2 = [3, 4];const add = (x) => (y) => x + y;const partiallyAppliedAdds = [add].ap(arg1); // => [(y) => 1 + y, (y) => 2 + y]partiallyAppliedAdds.ap(arg2); // => [4, 5, 5, 6]

Morphism

态射,一个转换函数。

Isomorphism

同构转换,相同数据下不同结构之间的转换。举例来说,2D 坐标既可以存储为数组 [2, 3] 也可以存储为 { x: 2, y: 3 }:

const pairToCoords = (pair) => ({x: pair[0], y: pair[1]})const coordsToPair = (coords) => [coords.x, coords.y]coordsToPair(pairToCoords([1, 2])) // => [1, 2]pairToCoords(coordsToPair({x: 1, y: 2})) // => { x: 1, y: 2 }

Setoid

Setoid,拥有 equals 函数的数据类型,可用于与其他同类型的数据进行比较。为 Array 类型添加 equals 函数使其成为 Setoid:

Array.prototype.equals = (arr) => {   const len = this.length   if (len !== arr.length) {       return false    }   for (let i = 0; i < len; i++) {       if (this[i] !== arr[i]) {           return false        }    }   return true}[1, 2].equals([1, 2]) // => true[1, 2].equals([0]) // => false

Semigroup

Semigroup,拥有 concat 函数的数据类型,可以与同类型数据进行合并:

[1].concat([2]) // => [1, 2]

Foldable

Foldable,拥有 reduce 函数的数据类型,可以将 Foldable 的实例转换为其他数据类型:

const sum = (list) => list.reduce((acc, val) => acc + val, 0);sum([1, 2, 3]) // => 6

Traversable

TODO

Type Signatures

类型签名,在 JavaScript 中通常会在注释中写明当前函数的参数类型和返回值类型,虽然各种语言的类型签名不同,但通常与以下示例相似:

// functionName :: firstArgType -> secondArgType -> returnType// add :: Number -> Number -> Numberconst add = (x) => (y) => x + y// increment :: Number -> Numberconst increment = (x) => x + 1

如果某个函数要作为参数传递给其他函数,那么在类型签名中需要使用括号包裹起这个函数的类型信息:

// call :: (a -> b) -> a -> bconst call = (f) => (x) => f(x)

上面示例中的 a、b 表示参数可以是任何数据类型的,但在下面的代码中,map 的类型签名表示: f 是一个函数,f 接收一个 a 类型的参数,返回一个 b 类型的值,同时 map 是一个柯里化的函数,其第二个接收一个列表形式的 a 类型参数,并返回列表形式的 b 类型参数:

// map :: (a -> b) -> [a] -> [b]const map = (f) => (list) => list.map(f)

Union type

联合类型,表示将多个类型信息放入一个类型变量中。JavaScript 中没有类型机制,所以让我们假设有一个类型变量 NumOrString,它表示 Number 或者 String 类型。+ 运算符在 JavaScript 中既可用于 Number,也可用于 String,所以我们使用 NumOrString 定义 + 的输入输出类型信息:

// add :: (NumOrString, NumOrString) -> NumOrStringconst add = (a, b) => a + b;add(1, 2); // => Number 3add(‘Foo’, 2); // => String “Foo2″add(‘Foo’, ‘Bar’); // => String “FooBar”

Product type

product type 同样包含多种基本类型:

// point :: (Number, Number) -> {x: Number, y: Number}const point = (x, y) => ({x: x, y: y});

Option

Option,是 union type 的特例,它只包含两种类型 Some 和 None。Option 常用于表示那些不确定是否返回值的函数:

// Naive definitionconst Some = (v) => ({   val: v,    map(f) {       return Some(f(this.val));    },    chain(f) {       return f(this.val);    }});const None = () => ({    map(f){       return this;    },    chain(f){       return this;    }});// maybeProp :: (String, {a}) -> Option aconst maybeProp = (key, obj) => typeof obj[key] === ‘undefined’ ? None() : Some(obj[key]);

使用 chain 函数执行链式调用可以返回具体的 Option:

// getItem :: Cart -> Option CartItemconst getItem = (cart) => maybeProp(‘item’, cart);// getPrice :: Item -> Option Numberconst getPrice = (item) => maybeProp(‘price’, item);// getNestedPrice :: cart -> Option aconst getNestedPrice = (cart) => getItem(obj).chain(getPrice);getNestedPrice({}); // => None()getNestedPrice({item: {foo: 1}}); // => None()getNestedPrice({item: {price: 9.99}}); // => Some(9.99)

某些语言中使用 Maybe 表示 Option,使用 Just 表示 Some,使用 Nothing 表示 Node。

查看文章…

5G入门科普

 

一个简单且神奇的公式

今天的故事,从一个公式开始讲起。

这是一个既简单又神奇的公式。说它简单,是因为它一共只有3个字母。而说它神奇,是因为这个公式蕴含了博大精深的通信技术奥秘,这个星球上有无数的人都在为之魂牵梦绕。

这个公式,就是它——

我相信很多同学都认出这个公式了,如果没认出来,而且你又是一个理科生的话,请记得有空多给你的中学物理老师打打电话!

小枣君解释一下,上面这个公式,这是物理学的基本公式,光速=波长×频率。

对于这个公式,可以这么说:无论是1G、2G、3G,还是4G、5G,万变不离其宗,全部都是在它身上做文章,没有跳出它的“五指山”。

且听我慢慢道来。。。

有线?无线?

通信技术,无论什么黑科技白科技,归根到底,就分为两种——有线通信和无线通信。

我和你打电话,信息数据要么在空中传播(看不见、摸不着),要么在实物上传播(看得见、摸得着)。

如果是在实体物质上传播,就是有线通信,基本上就是用的铜线、光纤这些线缆,统称为有线介质。

在有线介质上传播数据,速率可以达到很高的数值。

以光纤为例,在实验室中,单条光纤最大速度已达到了26Tbps。。。是传统网线的两万六千倍。。。

光纤

而空中传播这部分,才是移动通信的瓶颈所在。

目前主流的移动通信标准,是4G LTE,理论速率只有150Mbps(不包括载波聚合)。这个和有线是完全没办法相比的。

所以,5G如果要实现端到端的高速率,重点是突破无线这部分的瓶颈。

好大一个波

大家都知道,无线通信就是利用电磁波进行通信。电波和光波,都属于电磁波。

电磁波的功能特性,是由它的频率决定的。不同频率的电磁波,有不同的属性特点,从而有不同的用途。

例如,高频的γ射线,具有很大的杀伤力,可以用来治疗肿瘤。

电磁波的不断频率

我们目前主要使用电波进行通信。当然,光波通信也在崛起,例如LiFi。

LiFi(Light Fidelity),可见光通信

不偏题,回到电波先。

电波属于电磁波的一种,它的频率资源是有限的。

为了避免干扰和冲突,我们在电波这条公路上进一步划分车道,分配给不同的对象和用途。

不同频率电波的用途

请大家注意上面图中的红色字体。一直以来,我们主要是用中频~超高频进行手机通信的。

例如经常说的“GSM900”、“CDMA800”,其实意思就是指,工作频段在900MHz的GSM,和工作频段在800MHz的CDMA。

目前全球主流的4G LTE技术标准,属于特高频和超高频。

我们国家主要使用超高频:

大家能看出来,随着1G、2G、3G、4G的发展,使用的电波频率是越来越高的。

这是为什么呢?

这主要是因为,频率越高,能使用的频率资源越丰富。频率资源越丰富,能实现的传输速率就越高。

更高的频率→更多的资源→更快的速度

应该不难理解吧?频率资源就像车厢,越高的频率,车厢越多,相同时间内能装载的信息就越多。

那么,5G使用的频率具体是多少呢?

如下图所示:

5G的频率范围,分为两种:一种是6GHz以下,这个和目前我们的2/3/4G差别不算太大。还有一种,就很高了,在24GHz以上。

目前,国际上主要使用28GHz进行试验(这个频段也有可能成为5G最先商用的频段)。

如果按28GHz来算,根据前文我们提到的公式:

好啦,这个就是5G的第一个技术特点——

毫 米 波

请允许我再发一遍刚才那个频率对照表:

请注意看最下面一行,是不是就是“毫米波”?

继续,继续!

好了,既然,频率高这么好,你一定会问:“为什么以前我们不用高频率呢?”

原因很简单——不是不想用,是用不起。

电磁波的显著特点:频率越高,波长越短,越趋近于直线传播(绕射能力越差)。频率越高,在传播介质中的衰减也越大。

你看激光笔(波长635nm左右),射出的光是直的吧,挡住了就过不去了。

再看卫星通信和GPS导航(波长1cm左右),如果有遮挡物,就没信号了吧。

卫星那口大锅,必须校准瞄着卫星的方向,否则哪怕稍微歪一点,都会影响信号质量。

移动通信如果用了高频段,那么它最大的问题,就是传输距离大幅缩短,覆盖能力大幅减弱。

覆盖同一个区域,需要的5G基站数量,将大大超过4G。

基站数量意味着什么?钱啊!投资啊!成本啊!

频率越低,网络建设就越省钱,竞争起来就越有利。这就是为什么,这些年,电信、移动、联通为了低频段而争得头破血流。

有的频段甚至被称为——黄金频段。

这也是为什么,5G时代,运营商拼命怼设备商,希望基站降价。(如果真的上5G,按以往的模式,设备商就发大财了。)

所以,基于以上原因,在高频率的前提下,为了减轻网络建设方面的成本压力,5G必须寻找新的出路。

出路有哪些呢?

首先,就是微基站。

微 基 站

基站有两种,微基站和宏基站。看名字就知道,微基站很小,宏基站很大!

宏基站:

室外常见,建一个覆盖一大片

微基站:

看上去是不是很酷炫?

还有更小的,巴掌那么大

其实,微基站现在就有不少,尤其是城区和室内,经常能看到。

以后,到了5G时代,微基站会更多,到处都会装上,几乎随处可见。

你肯定会问,那么多基站在身边,会不会对人体造成影响?

我的回答是——不会。

其实,和传统认知恰好相反,事实上,基站数量越多,辐射反而越小!

你想一下,冬天,一群人的房子里,一个大功率取暖器好,还是几个小功率取暖器好?

大功率方案▼

小功率方案▼

上面的图,一目了然了。基站小,功率低,对大家都好。如果只采用一个大基站,离得近,辐射大,离得远,没信号,反而不好。

天线去哪了?

大家有没有发现,以前大哥大都有很长的天线,早期的手机也有突出来的小天线,为什么现在我们的手机都没有天线了?

其实,我们并不是不需要天线,而是我们的天线变小了。

根据天线特性,天线长度应与波长成正比,大约在1/10~1/4之间。

随着时间变化,我们手机的通信频率越来越高,波长越来越短,天线也就跟着变短啦!

毫米波通信,天线也变成毫米级。。。

这就意味着,天线完全可以塞进手机的里面,甚至可以塞很多根。。。

这就是5G的第三大杀手锏——

Massive MIMO(多天线技术)

MIMO就是“多进多出”(Multiple-Input Multiple-Output),多根天线发送,多根天线接收。

在LTE时代,我们就已经有MIMO了,但是天线数量并不算多,只能说是初级版的MIMO。

到了5G时代,继续把MIMO技术发扬光大,现在变成了加强版的Massive MIMO(Massive:大规模的,大量的)。

手机里面都能塞好多根天线,基站就更不用说了。

以前的基站,天线就那么几根:

5G时代,天线数量不是按根来算了,是按“阵”。。。“天线阵列”。。。一眼看去,要得密集恐惧症的节奏。。。

不过,天线之间的距离也不能太近。

因为天线特性要求,多天线阵列要求天线之间的距离保持在半个波长以上。如果距离近了,就会互相干扰,影响信号的收发。

你是直的?还是弯的?

大家都见过灯泡发光吧?

其实,基站发射信号的时候,就有点像灯泡发光。

信号是向四周发射的,对于光,当然是照亮整个房间,如果只是想照亮某个区域或物体,那么,大部分的光都浪费了。。。

基站也是一样,大量的能量和资源都浪费了。

我们能不能找到一只无形的手,把散开的光束缚起来呢?

这样既节约了能量,也保证了要照亮的区域有足够的光。

答案是:可以。

from:http://network.51cto.com/art/201812/589511.htm