Category Archives: 分布式

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

引言

分布式一致性是一个很“古典”的话题,即在分布式系统中,如何保证系统内的各个节点之间数据的一致性或能够就某个提案达成一致。这个问题想必对于很多技术同学而言并不陌生,几乎在所有的分布式系统中都会遇到,比如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

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

分布式锁

转载请务必注明原创地址为:http://www.54tianzhisheng.cn/2018/04/24/Distributed_lock/

什么是锁?

  • 在单进程的系统中,当存在多个线程可以同时改变某个变量(可变共享变量)时,就需要对变量或代码块做同步,使其在修改这种变量时能够线性执行消除并发修改变量。
  • 而同步的本质是通过锁来实现的。为了实现多个线程在一个时刻同一个代码块只能有一个线程可执行,那么需要在某个地方做个标记,这个标记必须每个线程都能看到,当标记不存在时可以设置该标记,其余后续线程发现已经有标记了则等待拥有标记的线程结束同步代码块取消标记后再去尝试设置标记。这个标记可以理解为锁。
  • 不同地方实现锁的方式也不一样,只要能满足所有线程都能看得到标记即可。如 Java 中 synchronize 是在对象头设置标记,Lock 接口的实现类基本上都只是某一个 volitile 修饰的 int 型变量其保证每个线程都能拥有对该 int 的可见性和原子修改,linux 内核中也是利用互斥量或信号量等内存数据做标记。
  • 除了利用内存数据做锁其实任何互斥的都能做锁(只考虑互斥情况),如流水表中流水号与时间结合做幂等校验可以看作是一个不会释放的锁,或者使用某个文件是否存在作为锁等。只需要满足在对标记进行修改能保证原子性和内存可见性即可。

什么是分布式?

分布式的 CAP 理论告诉我们:

任何一个分布式系统都无法同时满足一致性(Consistency)、可用性(Availability)和分区容错性(Partition tolerance),最多只能同时满足两项。

目前很多大型网站及应用都是分布式部署的,分布式场景中的数据一致性问题一直是一个比较重要的话题。基于 CAP理论,很多系统在设计之初就要对这三者做出取舍。在互联网领域的绝大多数的场景中,都需要牺牲强一致性来换取系统的高可用性,系统往往只需要保证最终一致性。

分布式场景

此处主要指集群模式下,多个相同服务同时开启.

在许多的场景中,我们为了保证数据的最终一致性,需要很多的技术方案来支持,比如分布式事务分布式锁等。很多时候我们需要保证一个方法在同一时间内只能被同一个线程执行。在单机环境中,通过 Java 提供的并发 API 我们可以解决,但是在分布式环境下,就没有那么简单啦。

  • 分布式与单机情况下最大的不同在于其不是多线程而是多进程
  • 多线程由于可以共享堆内存,因此可以简单的采取内存作为标记存储位置。而进程之间甚至可能都不在同一台物理机上,因此需要将标记存储在一个所有进程都能看到的地方。

什么是分布式锁?

  • 当在分布式模型下,数据只有一份(或有限制),此时需要利用锁的技术控制某一时刻修改数据的进程数。
  • 与单机模式下的锁不仅需要保证进程可见,还需要考虑进程与锁之间的网络问题。(我觉得分布式情况下之所以问题变得复杂,主要就是需要考虑到网络的延时和不可靠。。。一个大坑)
  • 分布式锁还是可以将标记存在内存,只是该内存不是某个进程分配的内存而是公共内存如 Redis、Memcache。至于利用数据库、文件等做锁与单机的实现是一样的,只要保证标记能互斥就行。

我们需要怎样的分布式锁?

  • 可以保证在分布式部署的应用集群中,同一个方法在同一时间只能被一台机器上的一个线程执行。
  • 这把锁要是一把可重入锁(避免死锁)
  • 这把锁最好是一把阻塞锁(根据业务需求考虑要不要这条)
  • 这把锁最好是一把公平锁(根据业务需求考虑要不要这条)
  • 有高可用的获取锁和释放锁功能
  • 获取锁和释放锁的性能要好

基于数据库做分布式锁

基于乐观锁

基于表主键唯一做分布式锁

利用主键唯一的特性,如果有多个请求同时提交到数据库的话,数据库会保证只有一个操作可以成功,那么我们就可以认为操作成功的那个线程获得了该方法的锁,当方法执行完毕之后,想要释放锁的话,删除这条数据库记录即可。

上面这种简单的实现有以下几个问题:

  • 这把锁强依赖数据库的可用性,数据库是一个单点,一旦数据库挂掉,会导致业务系统不可用。
  • 这把锁没有失效时间,一旦解锁操作失败,就会导致锁记录一直在数据库中,其他线程无法再获得到锁。
  • 这把锁只能是非阻塞的,因为数据的 insert 操作,一旦插入失败就会直接报错。没有获得锁的线程并不会进入排队队列,要想再次获得锁就要再次触发获得锁操作。
  • 这把锁是非重入的,同一个线程在没有释放锁之前无法再次获得该锁。因为数据中数据已经存在了。
  • 这把锁是非公平锁,所有等待锁的线程凭运气去争夺锁。
  • 在 MySQL 数据库中采用主键冲突防重,在大并发情况下有可能会造成锁表现象。

当然,我们也可以有其他方式解决上面的问题。

  • 数据库是单点?搞两个数据库,数据之前双向同步,一旦挂掉快速切换到备库上。
  • 没有失效时间?只要做一个定时任务,每隔一定时间把数据库中的超时数据清理一遍。
  • 非阻塞的?搞一个 while 循环,直到 insert 成功再返回成功。
  • 非重入的?在数据库表中加个字段,记录当前获得锁的机器的主机信息和线程信息,那么下次再获取锁的时候先查询数据库,如果当前机器的主机信息和线程信息在数据库可以查到的话,直接把锁分配给他就可以了。
  • 非公平的?再建一张中间表,将等待锁的线程全记录下来,并根据创建时间排序,只有最先创建的允许获取锁。
  • 比较好的办法是在程序中生产主键进行防重。

基于表字段版本号做分布式锁

这个策略源于 mysql 的 mvcc 机制,使用这个策略其实本身没有什么问题,唯一的问题就是对数据表侵入较大,我们要为每个表设计一个版本号字段,然后写一条判断 sql 每次进行判断,增加了数据库操作的次数,在高并发的要求下,对数据库连接的开销也是无法忍受的。

基于悲观锁

基于数据库排他锁做分布式锁

在查询语句后面增加for update,数据库会在查询过程中给数据库表增加排他锁 (注意: InnoDB 引擎在加锁的时候,只有通过索引进行检索的时候才会使用行级锁,否则会使用表级锁。这里我们希望使用行级锁,就要给要执行的方法字段名添加索引,值得注意的是,这个索引一定要创建成唯一索引,否则会出现多个重载方法之间无法同时被访问的问题。重载方法的话建议把参数类型也加上。)。当某条记录被加上排他锁之后,其他线程无法再在该行记录上增加排他锁。

我们可以认为获得排他锁的线程即可获得分布式锁,当获取到锁之后,可以执行方法的业务逻辑,执行完方法之后,通过connection.commit()操作来释放锁。

这种方法可以有效的解决上面提到的无法释放锁和阻塞锁的问题。

  • 阻塞锁? for update语句会在执行成功后立即返回,在执行失败时一直处于阻塞状态,直到成功。
  • 锁定之后服务宕机,无法释放?使用这种方式,服务宕机之后数据库会自己把锁释放掉。

但是还是无法直接解决数据库单点和可重入问题。

这里还可能存在另外一个问题,虽然我们对方法字段名使用了唯一索引,并且显示使用 for update 来使用行级锁。但是,MySQL 会对查询进行优化,即便在条件中使用了索引字段,但是否使用索引来检索数据是由 MySQL 通过判断不同执行计划的代价来决定的,如果 MySQL 认为全表扫效率更高,比如对一些很小的表,它就不会使用索引,这种情况下 InnoDB 将使用表锁,而不是行锁。如果发生这种情况就悲剧了。。。

还有一个问题,就是我们要使用排他锁来进行分布式锁的 lock,那么一个排他锁长时间不提交,就会占用数据库连接。一旦类似的连接变得多了,就可能把数据库连接池撑爆。

优缺点

优点:简单,易于理解

缺点:会有各种各样的问题(操作数据库需要一定的开销,使用数据库的行级锁并不一定靠谱,性能不靠谱)

基于 Redis 做分布式锁

基于 redis 的 setnx()、expire() 方法做分布式锁

setnx()

setnx 的含义就是 SET if Not Exists,其主要有两个参数 setnx(key, value)。该方法是原子的,如果 key 不存在,则设置当前 key 成功,返回 1;如果当前 key 已经存在,则设置当前 key 失败,返回 0。

expire()

expire 设置过期时间,要注意的是 setnx 命令不能设置 key 的超时时间,只能通过 expire() 来对 key 设置。

使用步骤

1、setnx(lockkey, 1) 如果返回 0,则说明占位失败;如果返回 1,则说明占位成功

2、expire() 命令对 lockkey 设置超时时间,为的是避免死锁问题。

3、执行完业务代码后,可以通过 delete 命令删除 key。

这个方案其实是可以解决日常工作中的需求的,但从技术方案的探讨上来说,可能还有一些可以完善的地方。比如,如果在第一步 setnx 执行成功后,在 expire() 命令执行成功前,发生了宕机的现象,那么就依然会出现死锁的问题,所以如果要对其进行完善的话,可以使用 redis 的 setnx()、get() 和 getset() 方法来实现分布式锁。

基于 redis 的 setnx()、get()、getset()方法做分布式锁

这个方案的背景主要是在 setnx() 和 expire() 的方案上针对可能存在的死锁问题,做了一些优化。

getset()

这个命令主要有两个参数 getset(key,newValue)。该方法是原子的,对 key 设置 newValue 这个值,并且返回 key 原来的旧值。假设 key 原来是不存在的,那么多次执行这个命令,会出现下边的效果:

  1. getset(key, “value1”) 返回 null 此时 key 的值会被设置为 value1
  2. getset(key, “value2”) 返回 value1 此时 key 的值会被设置为 value2
  3. 依次类推!
使用步骤
  1. setnx(lockkey, 当前时间+过期超时时间),如果返回 1,则获取锁成功;如果返回 0 则没有获取到锁,转向 2。
  2. get(lockkey) 获取值 oldExpireTime ,并将这个 value 值与当前的系统时间进行比较,如果小于当前系统时间,则认为这个锁已经超时,可以允许别的请求重新获取,转向 3。
  3. 计算 newExpireTime = 当前时间+过期超时时间,然后 getset(lockkey, newExpireTime) 会返回当前 lockkey 的值currentExpireTime。
  4. 判断 currentExpireTime 与 oldExpireTime 是否相等,如果相等,说明当前 getset 设置成功,获取到了锁。如果不相等,说明这个锁又被别的请求获取走了,那么当前请求可以直接返回失败,或者继续重试。
  5. 在获取到锁之后,当前线程可以开始自己的业务处理,当处理完毕后,比较自己的处理时间和对于锁设置的超时时间,如果小于锁设置的超时时间,则直接执行 delete 释放锁;如果大于锁设置的超时时间,则不需要再锁进行处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import cn.com.tpig.cache.redis.RedisService;
import cn.com.tpig.utils.SpringUtils;

//redis分布式锁
public final class RedisLockUtil {

    private static final int defaultExpire = 60;

    private RedisLockUtil() {
        //
    }

    /**
     * 加锁
     * @param key redis key
     * @param expire 过期时间,单位秒
     * @return true:加锁成功,false,加锁失败
     */
    public static boolean lock(String key, int expire) {

        RedisService redisService = SpringUtils.getBean(RedisService.class);
        long status = redisService.setnx(key, "1");

        if(status == 1) {
            redisService.expire(key, expire);
            return true;
        }

        return false;
    }

    public static boolean lock(String key) {
        return lock2(key, defaultExpire);
    }

    /**
     * 加锁
     * @param key redis key
     * @param expire 过期时间,单位秒
     * @return true:加锁成功,false,加锁失败
     */
    public static boolean lock2(String key, int expire) {

        RedisService redisService = SpringUtils.getBean(RedisService.class);

        long value = System.currentTimeMillis() + expire;
        long status = redisService.setnx(key, String.valueOf(value));

        if(status == 1) {
            return true;
        }
        long oldExpireTime = Long.parseLong(redisService.get(key, "0"));
        if(oldExpireTime < System.currentTimeMillis()) {
            //超时
            long newExpireTime = System.currentTimeMillis() + expire;
            long currentExpireTime = Long.parseLong(redisService.getSet(key, String.valueOf(newExpireTime)));
            if(currentExpireTime == oldExpireTime) {
                return true;
            }
        }
        return false;
    }

    public static void unLock1(String key) {
        RedisService redisService = SpringUtils.getBean(RedisService.class);
        redisService.del(key);
    }

    public static void unLock2(String key) {    
        RedisService redisService = SpringUtils.getBean(RedisService.class);    
        long oldExpireTime = Long.parseLong(redisService.get(key, "0"));   
        if(oldExpireTime > System.currentTimeMillis()) {        
            redisService.del(key);    
        }
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void drawRedPacket(long userId) {
    String key = "draw.redpacket.userid:" + userId;

    boolean lock = RedisLockUtil.lock2(key, 60);
    if(lock) {
        try {
            //领取操作
        } finally {
            //释放锁
            RedisLockUtil.unLock(key);
        }
    } else {
        new RuntimeException("重复领取奖励");
    }
}

基于 Redlock 做分布式锁

Redlock 是 Redis 的作者 antirez 给出的集群模式的 Redis 分布式锁,它基于 N 个完全独立的 Redis 节点(通常情况下 N 可以设置成 5)。

算法的步骤如下:

  • 1、客户端获取当前时间,以毫秒为单位。
  • 2、客户端尝试获取 N 个节点的锁,(每个节点获取锁的方式和前面说的缓存锁一样),N 个节点以相同的 key 和 value 获取锁。客户端需要设置接口访问超时,接口超时时间需要远远小于锁超时时间,比如锁自动释放的时间是 10s,那么接口超时大概设置 5-50ms。这样可以在有 redis 节点宕机后,访问该节点时能尽快超时,而减小锁的正常使用。
  • 3、客户端计算在获得锁的时候花费了多少时间,方法是用当前时间减去在步骤一获取的时间,只有客户端获得了超过 3 个节点的锁,而且获取锁的时间小于锁的超时时间,客户端才获得了分布式锁。
  • 4、客户端获取的锁的时间为设置的锁超时时间减去步骤三计算出的获取锁花费时间。
  • 5、如果客户端获取锁失败了,客户端会依次删除所有的锁。
    使用 Redlock 算法,可以保证在挂掉最多 2 个节点的时候,分布式锁服务仍然能工作,这相比之前的数据库锁和缓存锁大大提高了可用性,由于 redis 的高效性能,分布式缓存锁性能并不比数据库锁差。

但是,有一位分布式的专家写了一篇文章《How to do distributed locking》,质疑 Redlock 的正确性。

https://mp.weixin.qq.com/s/1bPLk_VZhZ0QYNZS8LkviA

https://blog.csdn.net/jek123456/article/details/72954106

优缺点

优点:

性能高

缺点:

失效时间设置多长时间为好?如何设置的失效时间太短,方法没等执行完,锁就自动释放了,那么就会产生并发问题。如果设置的时间太长,其他获取锁的线程就可能要平白的多等一段时间。

基于 redisson 做分布式锁

redisson 是 redis 官方的分布式锁组件。GitHub 地址:https://github.com/redisson/redisson

上面的这个问题 ——> 失效时间设置多长时间为好?这个问题在 redisson 的做法是:每获得一个锁时,只设置一个很短的超时时间,同时起一个线程在每次快要到超时时间时去刷新锁的超时时间。在释放锁的同时结束这个线程。

基于 ZooKeeper 做分布式锁

zookeeper 锁相关基础知识

  • zk 一般由多个节点构成(单数),采用 zab 一致性协议。因此可以将 zk 看成一个单点结构,对其修改数据其内部自动将所有节点数据进行修改而后才提供查询服务。
  • zk 的数据以目录树的形式,每个目录称为 znode, znode 中可存储数据(一般不超过 1M),还可以在其中增加子节点。
  • 子节点有三种类型。序列化节点,每在该节点下增加一个节点自动给该节点的名称上自增。临时节点,一旦创建这个 znode 的客户端与服务器失去联系,这个 znode 也将自动删除。最后就是普通节点。
  • Watch 机制,client 可以监控每个节点的变化,当产生变化会给 client 产生一个事件。

zk 基本锁

  • 原理:利用临时节点与 watch 机制。每个锁占用一个普通节点 /lock,当需要获取锁时在 /lock 目录下创建一个临时节点,创建成功则表示获取锁成功,失败则 watch/lock 节点,有删除操作后再去争锁。临时节点好处在于当进程挂掉后能自动上锁的节点自动删除即取消锁。
  • 缺点:所有取锁失败的进程都监听父节点,很容易发生羊群效应,即当释放锁后所有等待进程一起来创建节点,并发量很大。

zk 锁优化

  • 原理:上锁改为创建临时有序节点,每个上锁的节点均能创建节点成功,只是其序号不同。只有序号最小的可以拥有锁,如果这个节点序号不是最小的则 watch 序号比本身小的前一个节点 (公平锁)。
  • 步骤:
  1. 在 /lock 节点下创建一个有序临时节点 (EPHEMERAL_SEQUENTIAL)。
  2. 判断创建的节点序号是否最小,如果是最小则获取锁成功。不是则取锁失败,然后 watch 序号比本身小的前一个节点。
  3. 当取锁失败,设置 watch 后则等待 watch 事件到来后,再次判断是否序号最小。
  4. 取锁成功则执行代码,最后释放锁(删除该节点)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;

import org.apache.zookeeper.CreateMode;
import org.apache.zookeeper.KeeperException;
import org.apache.zookeeper.WatchedEvent;
import org.apache.zookeeper.Watcher;
import org.apache.zookeeper.ZooDefs;
import org.apache.zookeeper.ZooKeeper;
import org.apache.zookeeper.data.Stat;

public class DistributedLock implements Lock, Watcher{
    private ZooKeeper zk;
    private String root = "/locks";//根
    private String lockName;//竞争资源的标志
    private String waitNode;//等待前一个锁
    private String myZnode;//当前锁
    private CountDownLatch latch;//计数器
    private int sessionTimeout = 30000;
    private List<Exception> exception = new ArrayList<Exception>();

    /**
     * 创建分布式锁,使用前请确认config配置的zookeeper服务可用
     * @param config 127.0.0.1:2181
     * @param lockName 竞争资源标志,lockName中不能包含单词lock
     */
    public DistributedLock(String config, String lockName){
        this.lockName = lockName;
        // 创建一个与服务器的连接
        try {
            zk = new ZooKeeper(config, sessionTimeout, this);
            Stat stat = zk.exists(root, false);
            if(stat == null){
                // 创建根节点
                zk.create(root, new byte[0], ZooDefs.Ids.OPEN_ACL_UNSAFE,CreateMode.PERSISTENT);
            }
        } catch (IOException e) {
            exception.add(e);
        } catch (KeeperException e) {
            exception.add(e);
        } catch (InterruptedException e) {
            exception.add(e);
        }
    }

    /**
     * zookeeper节点的监视器
     */
    public void process(WatchedEvent event) {
        if(this.latch != null) {
            this.latch.countDown();
        }
    }

    public void lock() {
        if(exception.size() > 0){
            throw new LockException(exception.get(0));
        }
        try {
            if(this.tryLock()){
                System.out.println("Thread " + Thread.currentThread().getId() + " " +myZnode + " get lock true");
                return;
            }
            else{
                waitForLock(waitNode, sessionTimeout);//等待锁
            }
        } catch (KeeperException e) {
            throw new LockException(e);
        } catch (InterruptedException e) {
            throw new LockException(e);
        }
    }

    public boolean tryLock() {
        try {
            String splitStr = "_lock_";
            if(lockName.contains(splitStr))
                throw new LockException("lockName can not contains \\u000B");
            //创建临时子节点
            myZnode = zk.create(root + "/" + lockName + splitStr, new byte[0], ZooDefs.Ids.OPEN_ACL_UNSAFE,CreateMode.EPHEMERAL_SEQUENTIAL);
            System.out.println(myZnode + " is created ");
            //取出所有子节点
            List<String> subNodes = zk.getChildren(root, false);
            //取出所有lockName的锁
            List<String> lockObjNodes = new ArrayList<String>();
            for (String node : subNodes) {
                String _node = node.split(splitStr)[0];
                if(_node.equals(lockName)){
                    lockObjNodes.add(node);
                }
            }
            Collections.sort(lockObjNodes);
            System.out.println(myZnode + "==" + lockObjNodes.get(0));
            if(myZnode.equals(root+"/"+lockObjNodes.get(0))){
                //如果是最小的节点,则表示取得锁
                return true;
            }
            //如果不是最小的节点,找到比自己小1的节点
            String subMyZnode = myZnode.substring(myZnode.lastIndexOf("/") + 1);
            waitNode = lockObjNodes.get(Collections.binarySearch(lockObjNodes, subMyZnode) - 1);
        } catch (KeeperException e) {
            throw new LockException(e);
        } catch (InterruptedException e) {
            throw new LockException(e);
        }
        return false;
    }

    public boolean tryLock(long time, TimeUnit unit) {
        try {
            if(this.tryLock()){
                return true;
            }
            return waitForLock(waitNode,time);
        } catch (Exception e) {
            e.printStackTrace();
        }
        return false;
    }

    private boolean waitForLock(String lower, long waitTime) throws InterruptedException, KeeperException {
        Stat stat = zk.exists(root + "/" + lower,true);
        //判断比自己小一个数的节点是否存在,如果不存在则无需等待锁,同时注册监听
        if(stat != null){
            System.out.println("Thread " + Thread.currentThread().getId() + " waiting for " + root + "/" + lower);
            this.latch = new CountDownLatch(1);
            this.latch.await(waitTime, TimeUnit.MILLISECONDS);
            this.latch = null;
        }
        return true;
    }

    public void unlock() {
        try {
            System.out.println("unlock " + myZnode);
            zk.delete(myZnode,-1);
            myZnode = null;
            zk.close();
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (KeeperException e) {
            e.printStackTrace();
        }
    }

    public void lockInterruptibly() throws InterruptedException {
        this.lock();
    }

    public Condition newCondition() {
        return null;
    }

    public class LockException extends RuntimeException {
        private static final long serialVersionUID = 1L;
        public LockException(String e){
            super(e);
        }
        public LockException(Exception e){
            super(e);
        }
    }
}

优缺点

优点:

有效的解决单点问题,不可重入问题,非阻塞问题以及锁无法释放的问题。实现起来较为简单。

缺点:

性能上可能并没有缓存服务那么高,因为每次在创建锁和释放锁的过程中,都要动态创建、销毁临时节点来实现锁功能。ZK 中创建和删除节点只能通过 Leader 服务器来执行,然后将数据同步到所有的 Follower 机器上。还需要对 ZK的原理有所了解。

基于 Consul 做分布式锁

DD 写过类似文章,其实主要利用 Consul 的 Key / Value 存储 API 中的 acquire 和 release 操作来实现。

文章地址:http://blog.didispace.com/spring-cloud-consul-lock-and-semphore/

使用分布式锁的注意事项

1、注意分布式锁的开销

2、注意加锁的粒度

3、加锁的方式

总结

无论你身处一个什么样的公司,最开始的工作可能都需要从最简单的做起。不要提阿里和腾讯的业务场景 qps 如何大,因为在这样的大场景中你未必能亲自参与项目,亲自参与项目未必能是核心的设计者,是核心的设计者未必能独自设计。希望大家能根据自己公司业务场景,选择适合自己项目的方案。

参考资料

http://www.hollischuang.com/archives/1716

http://www.spring4all.com/question/158

https://www.cnblogs.com/PurpleDream/p/5559352.html

http://www.cnblogs.com/PurpleDream/p/5573040.html

https://www.cnblogs.com/suolu/p/6588902.html

微服务部署:蓝绿部署、滚动部署、灰度发布等部署方案对比与总结

在项目迭代的过程中,不可避免需要”上线“。上线对应着部署,或者重新部署;部署对应着修改;修改则意味着风险。

目前有很多用于部署的技术,有的简单,有的复杂;有的得停机,有的不需要停机即可完成部署。本文笔者简单讨论一下目前比较流行的几种部署方案,或者说策略。如有不足之处请指出,如有谬误,请指正^_^。

Blue/Green Deployment(蓝绿部署)

蓝绿部署无需停机,并且风险较小。

(1) 部署版本1的应用(一开始的状态)

所有外部请求的流量都打到这个版本上。

(2) 部署版本2的应用

版本2的代码与版本1不同(新功能、Bug修复等)。

(3) 将流量从版本1切换到版本2。

(4) 如版本2测试正常,就删除版本1正在使用的资源(例如实例),从此正式用版本2。

从过程不难发现,在部署的过程中,我们的应用始终在线。并且,新版本上线的过程中,并没有修改老版本的任何内容,在部署期间,老版本的状态不受影响。这样风险很小,并且,只要老版本的资源不被删除,理论上,我们可以在任何时间回滚到老版本。

rolling update(滚动发布)

滚动发布,一般是取出一个或者多个服务器停止服务,执行更新,并重新将其投入使用。周而复始,直到集群中所有的实例都更新成新版本。

这种部署方式相对于蓝绿部署,更加节约资源——它不需要运行两个集群、两倍的实例数。我们可以部分部署,例如每次只取出集群的20%进行升级。

这种方式也有很多缺点,例如:

(1) 没有一个确定OK的环境。使用蓝绿部署,我们能够清晰地知道老版本是OK的,而使用滚动发布,我们无法确定。

(2) 修改了现有的环境。

(3) 如果需要回滚,很困难。举个例子,在某一次发布中,我们需要更新100个实例,每次更新10个实例,每次部署需要5分钟。当滚动发布到第80个实例时,发现了问题,需要回滚。此时,脾气不好的程序猿很可能想掀桌子,因为回滚是一个痛苦,并且漫长的过程。

(4) 有的时候,我们还可能对系统进行动态伸缩,如果部署期间,系统自动扩容/缩容了,我们还需判断到底哪个节点使用的是哪个代码。尽管有一些自动化的运维工具,但是依然令人心惊胆战。

并不是说滚动发布不好,滚动发布也有它非常合适的场景。

灰度发布/金丝雀部署

先贴个百度百科:
灰度发布是指在黑与白之间,能够平滑过渡的一种发布方式。AB test就是一种灰度发布方式,让一部分用户继续用A,一部分用户开始用B,如果用户对B没有什么反对意见,那么逐步扩大范围,把所有用户都迁移到B上面来。灰度发布可以保证整体系统的稳定,在初始灰度的时候就可以发现、调整问题,以保证其影响度。
很多人把灰度发布与蓝绿部署混为一谈,笔者认为,与灰度发布最类似的应该是金丝雀部署。

“金丝雀部署”是增量发布的一种类型,它的执行方式是在原有软件生产版本可用的情况下,同时部署一个新的版本。同时运行同一个软件产品的多个版本需要软件针对配置和完美自动化部署进行特别设计。

我们来看一下金丝雀部署的步骤:

(1) 准备好部署各个阶段的工件,包括:构建工件,测试脚本,配置文件和部署清单文件。

(2) 从负载均衡列表中移除掉“金丝雀”服务器。

(3) 升级“金丝雀”应用(排掉原有流量并进行部署)。

(4) 对应用进行自动化测试。

(5) 将“金丝雀”服务器重新添加到负载均衡列表中(连通性和健康检查)。

(6) 如果“金丝雀”在线使用测试成功,升级剩余的其他服务器。(否则就回滚)

灰度发布中,常常按照用户设置路由权重,例如90%的用户维持使用老版本,10%的用户尝鲜新版本。不同版本应用共存,经常与A/B测试一起使用,用于测试选择多种方案。灰度发布比较典型的例子,是阿里云那个“新版本”,点击“进入新版本”,我们就成了金丝雀。

趣闻 :金丝雀部署(同理还有金丝雀测试),“金丝雀”的由来:17世纪,英国矿井工人发现,金丝雀对瓦斯这种气体十分敏感。空气中哪怕有极其微量的瓦斯,金丝雀也会停止歌唱;而当瓦斯含量超过一定限度时,虽然鲁钝的人类毫无察觉,金丝雀却早已毒发身亡。当时在采矿设备相对简陋的条件下,工人们每次下井都会带上一只金丝雀作为“瓦斯检测指标”,以便在危险状况下紧急撤离。

总结

(1) 蓝绿部署:不停止老版本,额外搞一套新版本,等测试发现新版本OK后,删除老版本。

(2) 滚动发布:按批次停止老版本实例,启动新版本实例。

(3) 灰度发布/金丝雀部署:不停止老版本,额外搞一套新版本,常常按照用户设置路由权重,例如90%的用户维持使用老版本,10%的用户尝鲜新版本。不同版本应用共存,经常与A/B测试一起使用,用于测试选择多种方案。

参考文档

(1) 《Blue-green Deployments, A/B Testing, and Canary Releases》(有图文说明,必看):http://blog.christianposta.com/deploy/blue-green-deployments-a-b-testing-and-canary-releases/

(2) Martin Fowler《BlueGreenDeployment》(必看):https://martinfowler.com/bliki/BlueGreenDeployment.html

(3) 《在生产中使用金丝雀部署来进行测试》:http://www.infoq.com/cn/news/2013/03/canary-release-improve-quality

(4) 《Using Blue-Green Deployment to Reduce Downtime and Risk(使用烂蓝绿部署降降低停机时间与风险,基于CloudFoundry)》:http://docs.cloudfoundry.org/devguide/deploy-apps/blue-green.html

(5) 《marathon:Blue-Green Deployment》:https://mesosphere.github.io/marathon/docs/blue-green-deploy.html ,译文:http://blog.csdn.net/zhuchuangang/article/details/51064974

(6) 《微服务不是免费的午餐》:http://blog.csdn.net/phodal/article/details/27098005

(7) 《蓝绿发布的整个部署过程》:http://www.tuicool.com/articles/2Iji2ue

消息队列设计精要

消息队列已经逐渐成为企业IT系统内部通信的核心手段。它具有低耦合、可靠投递、广播、流量控制、最终一致性等一系列功能,成为异步RPC的主要手段之一。

当今市面上有很多主流的消息中间件,如老牌的ActiveMQ、RabbitMQ,炙手可热的Kafka,阿里巴巴自主开发的Notify、MetaQ、RocketMQ等。

本文不会一一介绍这些消息队列的所有特性,而是探讨一下自主开发设计一个消息队列时,你需要思考和设计的重要方面。过程中我们会参考这些成熟消息队列的很多重要思想。

本文首先会阐述什么时候你需要一个消息队列,然后以Push模型为主,从零开始分析设计一个消息队列时需要考虑到的问题,如RPC、高可用、顺序和重复消息、可靠投递、消费关系解析等。

也会分析以Kafka为代表的pull模型所具备的优点。最后是一些高级主题,如用批量/异步提高性能、pull模型的系统设计理念、存储子系统的设计、流量控制的设计、公平调度的实现等。其中最后四个方面会放在下篇讲解。

何时需要消息队列

当你需要使用消息队列时,首先需要考虑它的必要性。可以使用mq的场景有很多,最常用的几种,是做业务解耦/最终一致性/广播/错峰流控等。反之,如果需要强一致性,关注业务逻辑的处理结果,则RPC显得更为合适。

解耦

解耦是消息队列要解决的最本质问题。所谓解耦,简单点讲就是一个事务,只关心核心的流程。而需要依赖其他系统但不那么重要的事情,有通知即可,无需等待结果。换句话说,基于消息的模型,关心的是“通知”,而非“处理”。

比如在美团旅游,我们有一个产品中心,产品中心上游对接的是主站、移动后台、旅游供应链等各个数据源;下游对接的是筛选系统、API系统等展示系统。当上游的数据发生变更的时候,如果不使用消息系统,势必要调用我们的接口来更新数据,就特别依赖产品中心接口的稳定性和处理能力。但其实,作为旅游的产品中心,也许只有对于旅游自建供应链,产品中心更新成功才是他们关心的事情。而对于团购等外部系统,产品中心更新成功也好、失败也罢,并不是他们的职责所在。他们只需要保证在信息变更的时候通知到我们就好了。

而我们的下游,可能有更新索引、刷新缓存等一系列需求。对于产品中心来说,这也不是我们的职责所在。说白了,如果他们定时来拉取数据,也能保证数据的更新,只是实时性没有那么强。但使用接口方式去更新他们的数据,显然对于产品中心来说太过于“重量级”了,只需要发布一个产品ID变更的通知,由下游系统来处理,可能更为合理。

再举一个例子,对于我们的订单系统,订单最终支付成功之后可能需要给用户发送短信积分什么的,但其实这已经不是我们系统的核心流程了。如果外部系统速度偏慢(比如短信网关速度不好),那么主流程的时间会加长很多,用户肯定不希望点击支付过好几分钟才看到结果。那么我们只需要通知短信系统“我们支付成功了”,不一定非要等待它处理完成。

最终一致性

最终一致性指的是两个系统的状态保持一致,要么都成功,要么都失败。当然有个时间限制,理论上越快越好,但实际上在各种异常的情况下,可能会有一定延迟达到最终一致状态,但最后两个系统的状态是一样的。

业界有一些为“最终一致性”而生的消息队列,如Notify(阿里)、QMQ(去哪儿)等,其设计初衷,就是为了交易系统中的高可靠通知。

以一个银行的转账过程来理解最终一致性,转账的需求很简单,如果A系统扣钱成功,则B系统加钱一定成功。反之则一起回滚,像什么都没发生一样。

然而,这个过程中存在很多可能的意外:

  1. A扣钱成功,调用B加钱接口失败。
  2. A扣钱成功,调用B加钱接口虽然成功,但获取最终结果时网络异常引起超时。
  3. A扣钱成功,B加钱失败,A想回滚扣的钱,但A机器down机。

可见,想把这件看似简单的事真正做成,真的不那么容易。所有跨VM的一致性问题,从技术的角度讲通用的解决方案是:

  1. 强一致性,分布式事务,但落地太难且成本太高,后文会具体提到。
  2. 最终一致性,主要是用“记录”和“补偿”的方式。在做所有的不确定的事情之前,先把事情记录下来,然后去做不确定的事情,结果可能是:成功、失败或是不确定,“不确定”(例如超时等)可以等价为失败。成功就可以把记录的东西清理掉了,对于失败和不确定,可以依靠定时任务等方式把所有失败的事情重新搞一遍,直到成功为止。
  3. 回到刚才的例子,系统在A扣钱成功的情况下,把要给B“通知”这件事记录在库里(为了保证最高的可靠性可以把通知B系统加钱和扣钱成功这两件事维护在一个本地事务里),通知成功则删除这条记录,通知失败或不确定则依靠定时任务补偿性地通知我们,直到我们把状态更新成正确的为止。
  4. 整个这个模型依然可以基于RPC来做,但可以抽象成一个统一的模型,基于消息队列来做一个“企业总线”。
  5. 具体来说,本地事务维护业务变化和通知消息,一起落地(失败则一起回滚),然后RPC到达broker,在broker成功落地后,RPC返回成功,本地消息可以删除。否则本地消息一直靠定时任务轮询不断重发,这样就保证了消息可靠落地broker。
  6. broker往consumer发送消息的过程类似,一直发送消息,直到consumer发送消费成功确认。
  7. 我们先不理会重复消息的问题,通过两次消息落地加补偿,下游是一定可以收到消息的。然后依赖状态机版本号等方式做判重,更新自己的业务,就实现了最终一致性。

最终一致性不是消息队列的必备特性,但确实可以依靠消息队列来做最终一致性的事情。另外,所有不保证100%不丢消息的消息队列,理论上无法实现最终一致性。好吧,应该说理论上的100%,排除系统严重故障和bug。

像Kafka一类的设计,在设计层面上就有丢消息的可能(比如定时刷盘,如果掉电就会丢消息)。哪怕只丢千分之一的消息,业务也必须用其他的手段来保证结果正确。

广播

消息队列的基本功能之一是进行广播。如果没有消息队列,每当一个新的业务方接入,我们都要联调一次新接口。有了消息队列,我们只需要关心消息是否送达了队列,至于谁希望订阅,是下游的事情,无疑极大地减少了开发和联调的工作量。

比如本文开始提到的产品中心发布产品变更的消息,以及景点库很多去重更新的消息,可能“关心”方有很多个,但产品中心和景点库只需要发布变更消息即可,谁关心谁接入。

错峰与流控

试想上下游对于事情的处理能力是不同的。比如,Web前端每秒承受上千万的请求,并不是什么神奇的事情,只需要加多一点机器,再搭建一些LVS负载均衡设备和Nginx等即可。但数据库的处理能力却十分有限,即使使用SSD加分库分表,单机的处理能力仍然在万级。由于成本的考虑,我们不能奢求数据库的机器数量追上前端。

这种问题同样存在于系统和系统之间,如短信系统可能由于短板效应,速度卡在网关上(每秒几百次请求),跟前端的并发量不是一个数量级。但用户晚上个半分钟左右收到短信,一般是不会有太大问题的。如果没有消息队列,两个系统之间通过协商、滑动窗口等复杂的方案也不是说不能实现。但系统复杂性指数级增长,势必在上游或者下游做存储,并且要处理定时、拥塞等一系列问题。而且每当有处理能力有差距的时候,都需要单独开发一套逻辑来维护这套逻辑。所以,利用中间系统转储两个系统的通信内容,并在下游系统有能力处理这些消息的时候,再处理这些消息,是一套相对较通用的方式。

总而言之,消息队列不是万能的。对于需要强事务保证而且延迟敏感的,RPC是优于消息队列的。

对于一些无关痛痒,或者对于别人非常重要但是对于自己不是那么关心的事情,可以利用消息队列去做。

支持最终一致性的消息队列,能够用来处理延迟不那么敏感的“分布式事务”场景,而且相对于笨重的分布式事务,可能是更优的处理方式。

当上下游系统处理能力存在差距的时候,利用消息队列做一个通用的“漏斗”。在下游有能力处理的时候,再进行分发。

如果下游有很多系统关心你的系统发出的通知的时候,果断地使用消息队列吧。

如何设计一个消息队列

综述

我们现在明确了消息队列的使用场景,下一步就是如何设计实现一个消息队列了。

 

基于消息的系统模型,不一定需要broker(消息队列服务端)。市面上的的Akka(actor模型)、ZeroMQ等,其实都是基于消息的系统设计范式,但是没有broker。

我们之所以要设计一个消息队列,并且配备broker,无外乎要做两件事情:

  1. 消息的转储,在更合适的时间点投递,或者通过一系列手段辅助消息最终能送达消费机。
  2. 规范一种范式和通用的模式,以满足解耦、最终一致性、错峰等需求。
  3. 掰开了揉碎了看,最简单的消息队列可以做成一个消息转发器,把一次RPC做成两次RPC。发送者把消息投递到服务端(以下简称broker),服务端再将消息转发一手到接收端,就是这么简单。

一般来讲,设计消息队列的整体思路是先build一个整体的数据流,例如producer发送给broker,broker发送给consumer,consumer回复消费确认,broker删除/备份消息等。

利用RPC将数据流串起来。然后考虑RPC的高可用性,尽量做到无状态,方便水平扩展。

之后考虑如何承载消息堆积,然后在合适的时机投递消息,而处理堆积的最佳方式,就是存储,存储的选型需要综合考虑性能/可靠性和开发维护成本等诸多因素。

为了实现广播功能,我们必须要维护消费关系,可以利用zk/config server等保存消费关系。

在完成了上述几个功能后,消息队列基本就实现了。然后我们可以考虑一些高级特性,如可靠投递,事务特性,性能优化等。

下面我们会以设计消息队列时重点考虑的模块为主线,穿插灌输一些消息队列的特性实现方法,来具体分析设计实现一个消息队列时的方方面面。

实现队列基本功能

RPC通信协议

刚才讲到,所谓消息队列,无外乎两次RPC加一次转储,当然需要消费端最终做消费确认的情况是三次RPC。既然是RPC,就必然牵扯出一系列话题,什么负载均衡啊、服务发现啊、通信协议啊、序列化协议啊,等等。在这一块,我的强烈建议是不要重复造轮子。利用公司现有的RPC框架:Thrift也好,Dubbo也好,或者是其他自定义的框架也好。因为消息队列的RPC,和普通的RPC没有本质区别。当然了,自主利用Memchached或者Redis协议重新写一套RPC框架并非不可(如MetaQ使用了自己封装的Gecko NIO框架,卡夫卡也用了类似的协议)。但实现成本和难度无疑倍增。排除对效率的极端要求,都可以使用现成的RPC框架。

简单来讲,服务端提供两个RPC服务,一个用来接收消息,一个用来确认消息收到。并且做到不管哪个server收到消息和确认消息,结果一致即可。当然这中间可能还涉及跨IDC的服务的问题。这里和RPC的原则是一致的,尽量优先选择本机房投递。你可能会问,如果producer和consumer本身就在两个机房了,怎么办?首先,broker必须保证感知的到所有consumer的存在。其次,producer尽量选择就近的机房就好了。

高可用

其实所有的高可用,是依赖于RPC和存储的高可用来做的。先来看RPC的高可用,美团的基于MTThrift的RPC框架,阿里的Dubbo等,其本身就具有服务自动发现,负载均衡等功能。而消息队列的高可用,只要保证broker接受消息和确认消息的接口是幂等的,并且consumer的几台机器处理消息是幂等的,这样就把消息队列的可用性,转交给RPC框架来处理了。

那么怎么保证幂等呢?最简单的方式莫过于共享存储。broker多机器共享一个DB或者一个分布式文件/kv系统,则处理消息自然是幂等的。就算有单点故障,其他节点可以立刻顶上。另外failover可以依赖定时任务的补偿,这是消息队列本身天然就可以支持的功能。存储系统本身的可用性我们不需要操太多心,放心大胆的交给DBA们吧!

对于不共享存储的队列,如Kafka使用分区加主备模式,就略微麻烦一些。需要保证每一个分区内的高可用性,也就是每一个分区至少要有一个主备且需要做数据的同步,关于这块HA的细节,可以参考下篇pull模型消息系统设计。

服务端承载消息堆积的能力

消息到达服务端如果不经过任何处理就到接收者了,broker就失去了它的意义。为了满足我们错峰/流控/最终可达等一系列需求,把消息存储下来,然后选择时机投递就显得是顺理成章的了。

只是这个存储可以做成很多方式。比如存储在内存里,存储在分布式KV里,存储在磁盘里,存储在数据库里等等。但归结起来,主要有持久化和非持久化两种。

持久化的形式能更大程度地保证消息的可靠性(如断电等不可抗外力),并且理论上能承载更大限度的消息堆积(外存的空间远大于内存)。

但并不是每种消息都需要持久化存储。很多消息对于投递性能的要求大于可靠性的要求,且数量极大(如日志)。这时候,消息不落地直接暂存内存,尝试几次failover,最终投递出去也未尝不可。

市面上的消息队列普遍两种形式都支持。当然具体的场景还要具体结合公司的业务来看。

存储子系统的选择

我们来看看如果需要数据落地的情况下各种存储子系统的选择。理论上,从速度来看,文件系统>分布式KV(持久化)>分布式文件系统>数据库,而可靠性却截然相反。还是要从支持的业务场景出发作出最合理的选择,如果你们的消息队列是用来支持支付/交易等对可靠性要求非常高,但对性能和量的要求没有这么高,而且没有时间精力专门做文件存储系统的研究,DB是最好的选择。

但是DB受制于IOPS,如果要求单broker 5位数以上的QPS性能,基于文件的存储是比较好的解决方案。整体上可以采用数据文件+索引文件的方式处理,具体这块的设计比较复杂,可以参考下篇的存储子系统设计。

分布式KV(如MongoDB,HBase)等,或者持久化的Redis,由于其编程接口较友好,性能也比较可观,如果在可靠性要求不是那么高的场景,也不失为一个不错的选择。

消费关系解析

现在我们的消息队列初步具备了转储消息的能力。下面一个重要的事情就是解析发送接收关系,进行正确的消息投递了。

市面上的消息队列定义了一堆让人晕头转向的名词,如JMS 规范中的Topic/Queue,Kafka里面的Topic/Partition/ConsumerGroup,RabbitMQ里面的Exchange等等。抛开现象看本质,无外乎是单播与广播的区别。所谓单播,就是点到点;而广播,是一点对多点。当然,对于互联网的大部分应用来说,组间广播、组内单播是最常见的情形。

消息需要通知到多个业务集群,而一个业务集群内有很多台机器,只要一台机器消费这个消息就可以了。

当然这不是绝对的,很多时候组内的广播也是有适用场景的,如本地缓存的更新等等。另外,消费关系除了组内组间,可能会有多级树状关系。这种情况太过于复杂,一般不列入考虑范围。所以,一般比较通用的设计是支持组间广播,不同的组注册不同的订阅。组内的不同机器,如果注册一个相同的ID,则单播;如果注册不同的ID(如IP地址+端口),则广播。

至于广播关系的维护,一般由于消息队列本身都是集群,所以都维护在公共存储上,如config server、zookeeper等。维护广播关系所要做的事情基本是一致的:

  1. 发送关系的维护。
  2. 发送关系变更时的通知。

队列高级特性设计

上面都是些消息队列基本功能的实现,下面来看一些关于消息队列特性相关的内容,不管可靠投递/消息丢失与重复以及事务乃至于性能,不是每个消息队列都会照顾到,所以要依照业务的需求,来仔细衡量各种特性实现的成本,利弊,最终做出最为合理的设计。

可靠投递(最终一致性)

这是个激动人心的话题,完全不丢消息,究竟可不可能?答案是,完全可能,前提是消息可能会重复,并且,在异常情况下,要接受消息的延迟。

方案说简单也简单,就是每当要发生不可靠的事情(RPC等)之前,先将消息落地,然后发送。当失败或者不知道成功失败(比如超时)时,消息状态是待发送,定时任务不停轮询所有待发送消息,最终一定可以送达。

具体来说:

  1. producer往broker发送消息之前,需要做一次落地。
  2. 请求到server后,server确保数据落地后再告诉客户端发送成功。
  3. 支持广播的消息队列需要对每个待发送的endpoint,持久化一个发送状态,直到所有endpoint状态都OK才可删除消息。

对于各种不确定(超时、down机、消息没有送达、送达后数据没落地、数据落地了回复没收到),其实对于发送方来说,都是一件事情,就是消息没有送达。

重推消息所面临的问题就是消息重复。重复和丢失就像两个噩梦,你必须要面对一个。好在消息重复还有处理的机会,消息丢失再想找回就难了。

Anyway,作为一个成熟的消息队列,应该尽量在各个环节减少重复投递的可能性,不能因为重复有解决方案就放纵的乱投递。

最后说一句,不是所有的系统都要求最终一致性或者可靠投递,比如一个论坛系统、一个招聘系统。一个重复的简历或话题被发布,可能比丢失了一个发布显得更让用户无法接受。不断重复一句话,任何基础组件要服务于业务场景。

消费确认

当broker把消息投递给消费者后,消费者可以立即响应我收到了这个消息。但收到了这个消息只是第一步,我能不能处理这个消息却不一定。或许因为消费能力的问题,系统的负荷已经不能处理这个消息;或者是刚才状态机里面提到的消息不是我想要接收的消息,主动要求重发。

把消息的送达和消息的处理分开,这样才真正的实现了消息队列的本质-解耦。所以,允许消费者主动进行消费确认是必要的。当然,对于没有特殊逻辑的消息,默认Auto Ack也是可以的,但一定要允许消费方主动ack。

对于正确消费ack的,没什么特殊的。但是对于reject和error,需要特别说明。reject这件事情,往往业务方是无法感知到的,系统的流量和健康状况的评估,以及处理能力的评估是一件非常复杂的事情。举个极端的例子,收到一个消息开始build索引,可能这个消息要处理半个小时,但消息量却是非常的小。所以reject这块建议做成滑动窗口/线程池类似的模型来控制,

消费能力不匹配的时候,直接拒绝,过一段时间重发,减少业务的负担。

但业务出错这件事情是只有业务方自己知道的,就像上文提到的状态机等等。这时应该允许业务方主动ack error,并可以与broker约定下次投递的时间。

重复消息和顺序消息

上文谈到重复消息是不可能100%避免的,除非可以允许丢失,那么,顺序消息能否100%满足呢? 答案是可以,但条件更为苛刻:

  1. 允许消息丢失。
  2. 从发送方到服务方到接受者都是单点单线程。

所以绝对的顺序消息基本上是不能实现的,当然在METAQ/Kafka等pull模型的消息队列中,单线程生产/消费,排除消息丢失,也是一种顺序消息的解决方案。

一般来讲,一个主流消息队列的设计范式里,应该是不丢消息的前提下,尽量减少重复消息,不保证消息的投递顺序。

谈到重复消息,主要是两个话题:

  1. 如何鉴别消息重复,并幂等的处理重复消息。
  2. 一个消息队列如何尽量减少重复消息的投递。

先来看看第一个话题,每一个消息应该有它的唯一身份。不管是业务方自定义的,还是根据IP/PID/时间戳生成的MessageId,如果有地方记录这个MessageId,消息到来是能够进行比对就

能完成重复的鉴定。数据库的唯一键/bloom filter/分布式KV中的key,都是不错的选择。由于消息不能被永久存储,所以理论上都存在消息从持久化存储移除的瞬间上游还在投递的可能(上游因种种原因投递失败,不停重试,都到了下游清理消息的时间)。这种事情都是异常情况下才会发生的,毕竟是小众情况。两分钟消息都还没送达,多送一次又能怎样呢?幂等的处理消息是一门艺术,因为种种原因重复消息或者错乱的消息还是来到了,说两种通用的解决方案:

  1. 版本号。
  2. 状态机。

版本号

举个简单的例子,一个产品的状态有上线/下线状态。如果消息1是下线,消息2是上线。不巧消息1判重失败,被投递了两次,且第二次发生在2之后,如果不做重复性判断,显然最终状态是错误的。

但是,如果每个消息自带一个版本号。上游发送的时候,标记消息1版本号是1,消息2版本号是2。如果再发送下线消息,则版本号标记为3。下游对于每次消息的处理,同时维护一个版本号。

每次只接受比当前版本号大的消息。初始版本为0,当消息1到达时,将版本号更新为1。消息2到来时,因为版本号>1.可以接收,同时更新版本号为2.当另一条下线消息到来时,如果版本号是3.则是真实的下线消息。如果是1,则是重复投递的消息。

如果业务方只关心消息重复不重复,那么问题就已经解决了。但很多时候另一个头疼的问题来了,就是消息顺序如果和想象的顺序不一致。比如应该的顺序是12,到来的顺序是21。则最后会发生状态错误。

参考TCP/IP协议,如果想让乱序的消息最后能够正确的被组织,那么就应该只接收比当前版本号大一的消息。并且在一个session周期内要一直保存各个消息的版本号。

如果到来的顺序是21,则先把2存起来,待2到来后,再处理1,这样重复性和顺序性要求就都达到了。

状态机

基于版本号来处理重复和顺序消息听起来是个不错的主意,但凡事总有瑕疵。使用版本号的最大问题是:

  1. 对发送方必须要求消息带业务版本号。
  2. 下游必须存储消息的版本号,对于要严格保证顺序的。

还不能只存储最新的版本号的消息,要把乱序到来的消息都存储起来。而且必须要对此做出处理。试想一个永不过期的”session”,比如一个物品的状态,会不停流转于上下线。那么中间环节的所有存储

就必须保留,直到在某个版本号之前的版本一个不丢的到来,成本太高。

就刚才的场景看,如果消息没有版本号,该怎么解决呢?业务方只需要自己维护一个状态机,定义各种状态的流转关系。例如,”下线”状态只允许接收”上线”消息,“上线”状态只能接收“下线消息”,如果上线收到上线消息,或者下线收到下线消息,在消息不丢失和上游业务正确的前提下。要么是消息发重了,要么是顺序到达反了。这时消费者只需要把“我不能处理这个消息”告诉投递者,要求投递者过一段时间重发即可。而且重发一定要有次数限制,比如5次,避免死循环,就解决了。

举例子说明,假设产品本身状态是下线,1是上线消息,2是下线消息,3是上线消息,正常情况下,消息应该的到来顺序是123,但实际情况下收到的消息状态变成了3123。

那么下游收到3消息的时候,判断状态机流转是下线->上线,可以接收消息。然后收到消息1,发现是上线->上线,拒绝接收,要求重发。然后收到消息2,状态是上线->下线,于是接收这个消息。

此时无论重发的消息1或者3到来,还是可以接收。另外的重发,在一定次数拒绝后停止重发,业务正确。

中间件对于重复消息的处理

回归到消息队列的话题来讲。上述通用的版本号/状态机/ID判重解决方案里,哪些是消息队列该做的、哪些是消息队列不该做业务方处理的呢?其实这里没有一个完全严格的定义,但回到我们的出发点,我们保证不丢失消息的情况下尽量少重复消息,消费顺序不保证。那么重复消息下和乱序消息下业务的正确,应该是由消费方保证的,我们要做的是减少消息发送的重复。

我们无法定义业务方的业务版本号/状态机,如果API里强制需要指定版本号,则显得过于绑架客户了。况且,在消费方维护这么多状态,就涉及到一个消费方的消息落地/多机间的同步消费状态问题,复杂度指数级上升,而且只能解决部分问题。

减少重复消息的关键步骤:

  1. broker记录MessageId,直到投递成功后清除,重复的ID到来不做处理,这样只要发送者在清除周期内能够感知到消息投递成功,就基本不会在server端产生重复消息。
  2. 对于server投递到consumer的消息,由于不确定对端是在处理过程中还是消息发送丢失的情况下,有必要记录下投递的IP地址。决定重发之前询问这个IP,消息处理成功了吗?如果询问无果,再重发。

事务

持久性是事务的一个特性,然而只满足持久性却不一定能满足事务的特性。还是拿扣钱/加钱的例子讲。满足事务的一致性特征,则必须要么都不进行,要么都能成功。

解决方案从大方向上有两种:

  1. 两阶段提交,分布式事务。
  2. 本地事务,本地落地,补偿发送。

分布式事务存在的最大问题是成本太高,两阶段提交协议,对于仲裁down机或者单点故障,几乎是一个无解的黑洞。对于交易密集型或者I/O密集型的应用,没有办法承受这么高的网络延迟,系统复杂性。

并且成熟的分布式事务一定构建与比较靠谱的商用DB和商用中间件上,成本也太高。

那如何使用本地事务解决分布式事务的问题呢?以本地和业务在一个数据库实例中建表为例子,与扣钱的业务操作同一个事务里,将消息插入本地数据库。如果消息入库失败,则业务回滚;如果消息入库成功,事务提交。

然后发送消息(注意这里可以实时发送,不需要等定时任务检出,以提高消息实时性)。以后的问题就是前文的最终一致性问题所提到的了,只要消息没有发送成功,就一直靠定时任务重试。

这里有一个关键的点,本地事务做的,是业务落地和消息落地的事务,而不是业务落地和RPC成功的事务。这里很多人容易混淆,如果是后者,无疑是事务嵌套RPC,是大忌,会有长事务死锁等各种风险。

而消息只要成功落地,很大程度上就没有丢失的风险(磁盘物理损坏除外)。而消息只要投递到服务端确认后本地才做删除,就完成了producer->broker的可靠投递,并且当消息存储异常时,业务也是可以回滚的。

本地事务存在两个最大的使用障碍:

  1. 配置较为复杂,“绑架”业务方,必须本地数据库实例提供一个库表。
  2. 对于消息延迟高敏感的业务不适用。

话说回来,不是每个业务都需要强事务的。扣钱和加钱需要事务保证,但下单和生成短信却不需要事务,不能因为要求发短信的消息存储投递失败而要求下单业务回滚。所以,一个完整的消息队列应该定义清楚自己可以投递的消息类型,如事务型消息,本地非持久型消息,以及服务端不落地的非可靠消息等。对不同的业务场景做不同的选择。另外事务的使用应该尽量低成本、透明化,可以依托于现有的成熟框架,如Spring的声明式事务做扩展。业务方只需要使用@Transactional标签即可。

性能相关

异步/同步

首先澄清一个概念,异步,同步和oneway是三件事。异步,归根结底你还是需要关心结果的,但可能不是当时的时间点关心,可以用轮询或者回调等方式处理结果;同步是需要当时关心

的结果的;而oneway是发出去就不管死活的方式,这种对于某些完全对可靠性没有要求的场景还是适用的,但不是我们重点讨论的范畴。

回归来看,任何的RPC都是存在客户端异步与服务端异步的,而且是可以任意组合的:客户端同步对服务端异步,客户端异步对服务端异步,客户端同步对服务端同步,客户端异步对服务端同步。

对于客户端来说,同步与异步主要是拿到一个Result,还是Future(Listenable)的区别。实现方式可以是线程池,NIO或者其他事件机制,这里先不展开讲。服务端异步可能稍微难理解一点,这个是需要RPC协议支持的。参考servlet 3.0规范,服务端可以吐一个future给客户端,并且在future done的时候通知客户端。整个过程可以参考下面的代码:

客户端同步服务端异步。

 

Future<Result> future = request(server);//server立刻返回future

synchronized(future){

while(!future.isDone()){

 future.wait();//server处理结束后会notify这个future,并修改isdone标志

}

}

return future.get();

 

客户端同步服务端同步。

Result result = request(server);

客户端异步服务端同步(这里用线程池的方式)。

Future<Result> future = executor.submit(new Callable(){public void call<Result>(){
    result = request(server);
}})
return future;

客户端异步服务端异步。

Future<Result> future = request(server);//server立刻返回future


return future

上面说了这么多,其实是想让大家脱离两个误区:

  1. RPC只有客户端能做异步,服务端不能。
  2. 异步只能通过线程池。

那么,服务端使用异步最大的好处是什么呢?说到底,是解放了线程和I/O。试想服务端有一堆I/O等待处理,如果每个请求都需要同步响应,每条消息都需要结果立刻返回,那么就几乎没法做I/O合并

(当然接口可以设计成batch的,但可能batch发过来的仍然数量较少)。而如果用异步的方式返回给客户端future,就可以有机会进行I/O的合并,把几个批次发过来的消息一起落地(这种合并对于MySQL等允许batch insert的数据库效果尤其明显),并且彻底释放了线程。不至于说来多少请求开多少线程,能够支持的并发量直线提高。

来看第二个误区,返回future的方式不一定只有线程池。换句话说,可以在线程池里面进行同步操作,也可以进行异步操作,也可以不使用线程池使用异步操作(NIO、事件)。

回到消息队列的议题上,我们当然不希望消息的发送阻塞主流程(前面提到了,server端如果使用异步模型,则可能因消息合并带来一定程度上的消息延迟),所以可以先使用线程池提交一个发送请求,主流程继续往下走。

但是线程池中的请求关心结果吗?Of course,必须等待服务端消息成功落地,才算是消息发送成功。所以这里的模型,准确地说事客户端半同步半异步(使用线程池不阻塞主流程,但线程池中的任务需要等待server端的返回),server端是纯异步。客户端的线程池wait在server端吐回的future上,直到server端处理完毕,才解除阻塞继续进行。

总结一句,同步能够保证结果,异步能够保证效率,要合理的结合才能做到最好的效率。

批量

谈到批量就不得不提生产者消费者模型。但生产者消费者模型中最大的痛点是:消费者到底应该何时进行消费。大处着眼来看,消费动作都是事件驱动的。主要事件包括:

  1. 攒够了一定数量。
  2. 到达了一定时间。
  3. 队列里有新的数据到来。

对于及时性要求高的数据,可用采用方式3来完成,比如客户端向服务端投递数据。只要队列有数据,就把队列中的所有数据刷出,否则将自己挂起,等待新数据的到来。

在第一次把队列数据往外刷的过程中,又积攒了一部分数据,第二次又可以形成一个批量。伪代码如下:

Executor executor = Executors.newFixedThreadPool(4);
final BlockingQueue<Message> queue = new ArrayBlockingQueue<>();
private Runnable task = new Runnable({//这里由于共享队列,Runnable可以复用,故做成全局的
   public void run(){
      List<Message> messages  = new ArrayList<>(20);
      queue.drainTo(messages,20);
      doSend(messages);//阻塞,在这个过程中会有新的消息到来,如果4个线程都占满,队列就有机会囤新的消息
   }
});
public void send(Message message){
    queue.offer(message);
    executor.submit(task)
}

这种方式是消息延迟和批量的一个比较好的平衡,但优先响应低延迟。延迟的最高程度由上一次发送的等待时间决定。但可能造成的问题是发送过快的话批量的大小不够满足性能的极致。

Executor executor = Executors.newFixedThreadPool(4);
final BlockingQueue<Message> queue = new ArrayBlockingQueue<>();
volatile long last = System.currentMills();
Executors.newSingleThreadScheduledExecutor().submit(new Runnable(){
   flush();
},500,500,TimeUnits.MILLS);
private Runnable task = new Runnable({//这里由于共享队列,Runnable可以复用,顾做成全局的。
   public void run(){
      List<Message> messages  = new ArrayList<>(20);
      queue.drainTo(messages,20);
      doSend(messages);//阻塞,在这个过程中会有新的消息到来,如果4个线程都占满,队列就有机会屯新的消息。
   }
});
public void send(Message message){
    last = System.currentMills();
    queue.offer(message);
    flush();
}
private void flush(){
 if(queue.size>200||System.currentMills()-last>200){
       executor.submit(task)
  }
}

相反对于可以用适量的延迟来换取高性能的场景来说,用定时/定量二选一的方式可能会更为理想,既到达一定数量才发送,但如果数量一直达不到,也不能干等,有一个时间上限。

具体说来,在上文的submit之前,多判断一个时间和数量,并且Runnable内部维护一个定时器,避免没有新任务到来时旧的任务永远没有机会触发发送条件。对于server端的数据落地,使用这种方式就非常方便。

最后啰嗦几句,曾经有人问我,为什么网络请求小包合并成大包会提高性能?主要原因有两个:

  1. 减少无谓的请求头,如果你每个请求只有几字节,而头却有几十字节,无疑效率非常低下。
  2. 减少回复的ack包个数。把请求合并后,ack包数量必然减少,确认和重发的成本就会降低。

push还是pull

上文提到的消息队列,大多是针对push模型的设计。现在市面上有很多经典的也比较成熟的pull模型的消息队列,如Kafka、MetaQ等。这跟JMS中传统的push方式有很大的区别,可谓另辟蹊径。

我们简要分析下push和pull模型各自存在的利弊。

慢消费

慢消费无疑是push模型最大的致命伤,穿成流水线来看,如果消费者的速度比发送者的速度慢很多,势必造成消息在broker的堆积。假设这些消息都是有用的无法丢弃的,消息就要一直在broker端保存。当然这还不是最致命的,最致命的是broker给consumer推送一堆consumer无法处理的消息,consumer不是reject就是error,然后来回踢皮球。

反观pull模式,consumer可以按需消费,不用担心自己处理不了的消息来骚扰自己,而broker堆积消息也会相对简单,无需记录每一个要发送消息的状态,只需要维护所有消息的队列和偏移量就可以了。所以对于建立索引等慢消费,消息量有限且到来的速度不均匀的情况,pull模式比较合适。

消息延迟与忙等

这是pull模式最大的短板。由于主动权在消费方,消费方无法准确地决定何时去拉取最新的消息。如果一次pull取到消息了还可以继续去pull,如果没有pull取到则需要等待一段时间重新pull。

但等待多久就很难判定了。你可能会说,我可以有xx动态pull取时间调整算法,但问题的本质在于,有没有消息到来这件事情决定权不在消费方。也许1分钟内连续来了1000条消息,然后半个小时没有新消息产生,

可能你的算法算出下次最有可能到来的时间点是31分钟之后,或者60分钟之后,结果下条消息10分钟后到了,是不是很让人沮丧?

当然也不是说延迟就没有解决方案了,业界较成熟的做法是从短时间开始(不会对broker有太大负担),然后指数级增长等待。比如开始等5ms,然后10ms,然后20ms,然后40ms……直到有消息到来,然后再回到5ms。

即使这样,依然存在延迟问题:假设40ms到80ms之间的50ms消息到来,消息就延迟了30ms,而且对于半个小时来一次的消息,这些开销就是白白浪费的。

在阿里的RocketMq里,有一种优化的做法-长轮询,来平衡推拉模型各自的缺点。基本思路是:消费者如果尝试拉取失败,不是直接return,而是把连接挂在那里wait,服务端如果有新的消息到来,把连接notify起来,这也是不错的思路。但海量的长连接block对系统的开销还是不容小觑的,还是要合理的评估时间间隔,给wait加一个时间上限比较好~

顺序消息

如果push模式的消息队列,支持分区,单分区只支持一个消费者消费,并且消费者只有确认一个消息消费后才能push送另外一个消息,还要发送者保证全局顺序唯一,听起来也能做顺序消息,但成本太高了,尤其是必须每个消息消费确认后才能发下一条消息,这对于本身堆积能力和慢消费就是瓶颈的push模式的消息队列,简直是一场灾难。

反观pull模式,如果想做到全局顺序消息,就相对容易很多:

  1. producer对应partition,并且单线程。
  2. consumer对应partition,消费确认(或批量确认),继续消费即可。

所以对于日志push送这种最好全局有序,但允许出现小误差的场景,pull模式非常合适。如果你不想看到通篇乱套的日志~~

Anyway,需要顺序消息的场景还是比较有限的而且成本太高,请慎重考虑。

总结

本文从为何使用消息队列开始讲起,然后主要介绍了如何从零开始设计一个消息队列,包括RPC、事务、最终一致性、广播、消息确认等关键问题。并对消息队列的push、pull模型做了简要分析,最后从批量和异步角度,分析了消息队列性能优化的思路。下篇会着重介绍一些高级话题,如存储系统的设计、流控和错峰的设计、公平调度等。希望通过这些,让大家对消息队列有个提纲挈领的整体认识,并给自主开发消息队列提供思路。另外,本文主要是源自自己在开发消息队列中的思考和读源码时的体会,比较不”官方”,也难免会存在一些漏洞,欢迎大家多多交流。

后续我们还会推出消息队列设计高级篇,内容会涵盖以下方面:

  • pull模型消息系统设计理念
  • 存储子系统设计
  • 流量控制
  • 公平调度

敬请期待哦~

作者简介

王烨,现在是美团旅游后台研发组的程序猿,之前曾经在百度、去哪和优酷工作过,专注Java后台开发。对于网络编程和并发编程具有浓厚的兴趣,曾经做过一些基础组件,也翻过一些源码,属于比较典型的宅男技术控。期待能够与更多知己,在coding的路上并肩前行~

from:https://zhuanlan.zhihu.com/p/21649950

 

大型分布式网站术语分析

1. I/O优化

  1. 增加缓存,减少磁盘的访问次数。
  2. 优化磁盘的管理系统,设计最优的磁盘方式策略,以及磁盘的寻址策略,这是在底层操作系统层面考虑的。
  3. 设计合理的磁盘存储数据块,以及访问这些数据库的策略,这是在应用层面考虑的。例如,我们可以给存放的数据设计索引,通过寻址索引来加快和减少磁盘的访问量,还可以采用异步和非阻塞的方式加快磁盘的访问速度。
  4. 应用合理的RAID策略提升磁盘I/O。

2. Web前端调优

  1. 减少网络交互的次数(多次请求合并)
  2. 减少网络传输数据量的大小(压缩)
  3. 尽量减少编码(尽量提前将字符转化为字节,或者减少从字符到字节的转化过程。)
  4. 使用浏览器缓存
  5. 减少Cookie传输
  6. 合理布局页面
  7. 使用页面压缩
  8. 延迟加载页面
  9. CSS在最上面,JS在最下面
  10. CDN
  11. 反向代理
  12. 页面静态化
  13. 异地部署

3.服务降级(自动优雅降级)

拒绝服务和关闭服务

4.幂等性设计

有些服务天然具有幂等性,比如讲用户性别设置为男性,不管设置多少次,结果都一样。但是对转账交易等操作,问题就会比较复杂,需要通过交易编号等信息进行服务调用有效性校验,只有有效的操作才能继续执行。

(注:幂等性是系统的接口对外一种承诺(而不是实现), 承诺只要调用接口成功, 外部多次调用对系统的影响是一致的. 声明为幂等的接口会认为外部调用失败是常态, 并且失败之后必然会有重试.)

5.失效转移

若数据服务器集群中任何一台服务器宕机,那么应用程序针对这台服务器的所有读写操作都需要重新路由到其他服务器,保证数据访问不会失败,这个过程叫失效转移。
失效转移包括:失效确认(心跳检测和应用程序访问失败报告)、访问转移、数据恢复。
失效转移保证当一个数据副本不可访问时,可以快速切换访问数据的其他副本,保证系统可用。

6.性能优化

根据网站分层架构,性能优化可分为:web前端性能优化、应用服务器性能优化、存储服务器性能优化。

  1. web前端性能优化
    • 浏览器访问优化:减少http请求;使用浏览器缓存;启用压缩;css放在页面最上面、javaScript放在页面最下面;减少Cookie传输
    • CDN加速
    • 反向代理
  2. 应用服务器性能优化
    • 分布式缓存(Redis等)
    • 异步操作(消息队列)
    • 使用集群(负载均衡)
    • 代码优化
  3. 存储性能优化
    • 机械硬盘vs固态硬盘
    • B+树 vs LSM树
    • RAID vs HDFS

7. 代码优化

  • 多线程(Q:怎么确保线程安全?无锁机制有哪些?)
  • 资源复用(单例模式,连接池,线程池)
  • 数据结构
  • 垃圾回收

8. 负载均衡

  • HTTP重定向负载均衡
    当用户发来请求的时候,Web服务器通过修改HTTP响应头中的Location标记来返回一个新的url,然后浏览器再继续请求这个新url,实际上就是页面重定向。通过重定向,来达到“负载均衡”的目标。例如,我们在下载PHP源码包的时候,点击下载链接时,为了解决不同国家和地域下载速度的问题,它会返回一个离我们近的下载地址。重定向的HTTP返回码是302。
    优点:比较简单。
    缺点:浏览器需要两次请求服务器才能完成一次访问,性能较差。重定向服务自身的处理能力有可能成为瓶颈,整个集群的伸缩性国模有限;使用HTTP302响应码重定向,有可能使搜索引擎判断为SEO作弊,降低搜索排名。
  • DNS域名解析负载均衡
    DNS(Domain Name System)负责域名解析的服务,域名url实际上是服务器的别名,实际映射是一个IP地址,解析过程,就是DNS完成域名到IP的映射。而一个域名是可以配置成对应多个IP的。因此,DNS也就可以作为负载均衡服务。
    事实上,大型网站总是部分使用DNS域名解析,利用域名解析作为第一级负载均衡手段,即域名解析得到的一组服务器并不是实际提供Web服务的物理服务器,而是同样提供负载均衡服务的内部服务器,这组内部负载均衡服务器再进行负载均衡,将请求分发到真是的Web服务器上。
    优点:将负载均衡的工作转交给DNS,省掉了网站管理维护负载均衡服务器的麻烦,同时许多DNS还支持基于地理位置的域名解析,即会将域名解析成举例用户地理最近的一个服务器地址,这样可以加快用户访问速度,改善性能。
    缺点:不能自由定义规则,而且变更被映射的IP或者机器故障时很麻烦,还存在DNS生效延迟的问题。而且DNS负载均衡的控制权在域名服务商那里,网站无法对其做更多改善和更强大的管理。
  • 反向代理负载均衡
    反向代理服务可以缓存资源以改善网站性能。实际上,在部署位置上,反向代理服务器处于Web服务器前面(这样才可能缓存Web相应,加速访问),这个位置也正好是负载均衡服务器的位置,所以大多数反向代理服务器同时提供负载均衡的功能,管理一组Web服务器,将请求根据负载均衡算法转发到不同的Web服务器上。Web服务器处理完成的响应也需要通过反向代理服务器返回给用户。由于web服务器不直接对外提供访问,因此Web服务器不需要使用外部ip地址,而反向代理服务器则需要配置双网卡和内部外部两套IP地址。
    优点:和反向代理服务器功能集成在一起,部署简单。
    缺点:反向代理服务器是所有请求和响应的中转站,其性能可能会成为瓶颈。
  • LVS-NAT:修改IP地址
  • LVS-TUN: 一个IP报文封装在另一个IP报文的技术。
  • LVS-DR:将数据帧的MAC地址改为选出服务器的MAC地址,再将修改后的数据帧在与服务器组的局域网上发送。

9.缓存

缓存就是将数据存放在距离计算最近的位置以加快处理速度。缓存是改善软件性能的第一手段,现在CPU越来越快的一个重要因素就是使用了更多的缓存,在复杂的软件设计中,缓存几乎无处不在。大型网站架构设计在很多方面都使用了缓存设计。

  • CDN: 及内容分发网络,部署在距离终端用户最近的网络服务商,用户的网络请求总是先到达他的网络服务商哪里,在这里缓存网站的一些静态资源(较少变化的数据),可以就近以最快速度返回给用户,如视频网站和门户网站会将用户访问量大的热点内容缓存在CDN中。
  • 反向代理:反向代理属于网站前端架构的一部分,部署在网站的前端,当用户请求到达网站的数据中心时,最先访问到的就是反向代理服务器,这里缓存网站的静态资源,无需将请求继续转发给应用服务器就能返回给用户。
  • 本地缓存:在应用服务器本地缓存着热点数据,应用程序可以在本机内存中直接访问数据,而无需访问数据库。
  • 分布式缓存:大型网站的数据量非常庞大,即使只缓存一小部分,需要的内存空间也不是单机能承受的,所以除了本地缓存,还需要分布式缓存,将数据缓存在一个专门的分布式缓存集群中,应用程序通过网络通信访问缓存数据。

使用缓存有两个前提条件,一是数据访问热点不均衡,某些数据会被更频繁的访问,这些数据应该放在缓存中;二是数据在某个时间段内有效,不会很快过期,否则缓存的数据就会因已经失效而产生脏读,影响结果的正确性。网站应用中,缓存处理可以加快数据访问速度,还可以减轻后端应用和数据存储的负载压力,这一点对网站数据库架构至关重要,网站数据库几乎都是按照有缓存的前提进行负载能力设计的。

10. 负载均衡算法

轮询 Round Robin
加强轮询 Weight Round Robin
随机 Random
加强随机 Weight Random
最少连接 Least Connections
加强最少连接
源地址散列 Hash
其他算法

  • 最快算法(Fastest):传递连接给那些响应最快的服务器。当其中某个服务器发生第二到第7 层的故障,BIG-IP 就把其从服务器队列中拿出,不参加下一次的用户请求的分配,直到其恢复正常。
  • 观察算法(Observed):连接数目和响应时间以这两项的最佳平衡为依据为新的请求选择服务器。当其中某个服务器发生第二到第7 层的故障,BIG-IP就把其从服务器队列中拿出,不参加下一次的用户请求的分配,直到其恢复正常。
  • 预测算法(Predictive):BIG-IP利用收集到的服务器当前的性能指标,进行预测分析,选择一台服务器在下一个时间片内,其性能将达到最佳的服务器相应用户的请求。(被BIG-IP 进行检测)
  • 动态性能分配算法(Dynamic Ratio-APM):BIG-IP 收集到的应用程序和应用服务器的各项性能参数,动态调整流量分配。
  • 动态服务器补充算法(Dynamic Server Act.):当主服务器群中因故障导致数量减少时,动态地将备份服务器补充至主服务器群。
  • 服务质量算法(QoS):按不同的优先级对数据流进行分配。
  • 服务类型算法(ToS): 按不同的服务类型(在Type of Field中标识)负载均衡对数据流进行分配。
  • 规则模式算法:针对不同的数据流设置导向规则,用户可自行

11. 扩展性和伸缩性的区别

扩展性:指对现有系统影响最小的情况下,系统功能可持续扩展或替身的能力。表现在系统基础设施稳定不需要经常变更,应用之间较少依赖和耦合,对需求变更可以敏捷响应。它是系统架构设计层面的开闭原则(对扩展开放,对修改关闭),架构设计考虑未来功能扩展,当系统增加新功能时,不需要对现有系统的结构和代码进行修改。

衡量网站架构扩展性好坏的主要标准就是在网站增加新的业务产品时,是否可以实现对现有产品透明无影响,不需要任何改动或者很少改动既有业务功能就可以上线新产品。不同产品之间是否很少耦合,一个产品改动对其他产品无影响,其他产品和功能不需要受牵连进行改动。

伸缩性:所谓网站的伸缩性指是不需要改变网站的软硬件设计,仅仅通过改变部署的服务器数量就可以扩大或者缩小网站的服务处理能力。

指系统能够增加(减少)自身资源规模的方式增强(减少)自己计算处理事务的能力。如果这种增减是成比例的,就被称作线性伸缩性。在网站架构中,通常指利用集群的方式增加服务器数量、提高系统的整体事务吞吐能力。

衡量架构伸缩性的主要标准就是可以用多台服务器构建集群,是否容易向集群中添加新的服务器。加入新的服务器后是否可以提供和原来服务无差别的服务、集群中的可容纳的总的服务器数量是否有限制。

12.分布式缓存的一致性hash

具体算法过程:先构造一个长度为2^32的整数环(这个环被称作一致性Hash环)根据节点名称的Hash值(其分布范围为[0,2^32 – 1])将缓存服务器阶段设置在这个Hash环上。然后根据需要缓存的数据的Key值计算得到Hash值(其分布范围也同样为[0,2^32 – 1]),然后在Hash环上顺时针查找举例这个KEY的hash值最近的缓存服务器节点,完成KEY到服务器的Hash映射查找。

优化策略:将每台物理服务器虚拟为一组虚拟缓存服务器,将虚拟服务器的Hash值放置在Hash环上,key在换上先找到虚拟服务器节点,再得到物理服务器的信息。

一台物理服务器设置多少个虚拟服务器节点合适呢?经验值:150。

13. 网络安全

  1. XSS攻击
    跨站点脚本攻击(Cross Site Script),指黑客通过篡改网页,注入恶意的HTML脚本,在用户浏览网页时,控制用户浏览器进行恶意操作的一种攻击方式。
    防范手段:消毒(XSS攻击者一般都是通过在请求中嵌入恶意脚本大道攻击的目的,这些脚本是一般用户输入中不使用的,如果进行过滤和消毒处理,即对某些html危险字符转移,如“>”转译为“& gt;”);HttpOnly(防止XSS攻击者窃取Cookie).
  2. 注入攻击:SQL注入和OS注入
    SQL防范:预编译语句PreparedStatement; ORM;避免密码明文存放;处理好相应的异常。
  3. CSRF(Cross Site Request Forgery,跨站点请求伪造)。听起来与XSS有点相似,事实上两者区别很大,XSS利用的是站内的信任用户,而CSRF则是通过伪装来自受信任用户的请求来利用受信任的网站。
    防范:httpOnly;增加token;通过Referer识别。
  4. 文件上传漏洞
  5. DDos攻击

14. 加密技术

  1. 摘要加密:MD5, SHA
  2. 对称加密:DES算法,RC算法, AES
  3. 非对称加密:RSA
    非对称加密技术通常用在信息安全传输,数字签名等场合。
    HTTPS传输中浏览器使用的数字证书实质上是经过权威机构认证的非对称加密的公钥。

15. 流控(流量控制)

  1. 流量丢弃
  2. 通过单机内存队列来进行有限的等待,直接丢弃用户请求的处理方式显得简单而粗暴,并且如果是I/O密集型应用(包括网络I/O和磁盘I/O),瓶颈一般不再CPU和内存。因此,适当的等待,既能够替身用户体验,又能够提高资源利用率。
  3. 通过分布式消息队列来将用户的请求异步化。

参考资料
1. LVS:三种负载均衡方式比较+另三种负载均衡方式
2. 《大型网站技术架构——核心原理与技术分析》李智慧 著。
3. 亿级Web系统搭建:单机到分布式集群
4. 《大型分布式网站架构设计与实现》陈康贤 著。

from:http://www.importnew.com/24198.html