lamport算法

❶ Chandy-Lamport分布式快照算法小记

前面陆陆续续写了几篇关于Flink的浅显的小文章，其中多次提到了“异步屏障快照（asychronous barrier snapshot, ABS）算法”这个词，并指出它是Flink检查点机制的基础。而ABS算法的渊源就是本文要说的Chandy-Lamport算法，它是目前在流式系统中广泛使用的分布式快照算法。

这个算法在论文 《Distributed Snapshots: Determining Global States of Distributed Systems》 中提出，并以作者的名字命名，即得州大学奥斯汀分校的K. Mani Chandy与斯坦福的Leslie Lamport（这位也是鼎鼎大名的Paxos算法的作者）。算法产生的背景有点意思，据Leslie Lamport自己说：

下面先介绍一些分布式系统中快照的前置知识，然后正式介绍Chandy-Lamport算法。

所谓分布式快照，实际上就是特定时间点记录下来的分布式系统的全局状态（global state）。分布式快照的主要指迹此用途有故障恢复（即检查点）、死锁检测、垃圾收集等。

为了方便理解，我们仍然沿用原论文中的方法，将分布式系统抽象为一张有向图：顶点称为进程（process），边称为链路（channel）。下图就示出包含3个进程和4个链路的分布式系统。

那么， 全局状态就要包含所有进程的状态以及所有链路的状态 。由于进程之间在通过链路不停地交换数据，所以以下动作都可能造成全局状态的改变：

论文中将使分布式系统状态发生变化的因素叫做事件（event），并给出了它的形式化定义，即e=<p, s, s', M, c>。p、M、c的定义上面已经提到了，而s和s'分别是进程p在事件e发生之前及发生之后的状态。

可见，进程对自己的状态是有感知的，而链路本身只负责传递消息，它们的状态不容易记录。并且我们 无法让时间静止 ，各个进程的时钟也很有可能不同步，故不能在一瞬间同时捕获所有进程和链路的状态。所以必须要曲线救国，通过 每个进程记录的与自己相关的状态合并出全局状态 ，这也是Chandy-Lamport算法的核心思想所在。

下面具体介绍算法的细节。

Chandy-Lamport算法基于如下前提：在每对进程p i 、p j 之间都存在两条单向的链路c ij 和c ji ，即对于p i 来讲，c ij 是出边，c ji 是入边。链路的网络可靠，缓存无限大，并且先进先出，即链路上的消息会不重不漏地按序到达。

算法要达到如下的终极目标：

为了保证成功取得全局快照，Chandy-Lamport算法分为3个阶段，即初始化快照、扩散快照与完成快照，并且借助一种与正常消息不同的特殊消息作为标记，英文称为marker。这3个阶段并没有直接体现在论文中，而是出自 普林斯顿大学相关课程的PPT ，但算法唯迅实际流程则是严格一致的。下面叙述3个阶段的流程。

假设进程p i 发起快照：

对于任意一个进程p j （包含发起快照的那个进程），考虑它的所有入边链路c kj 。当在c kj 上收到了marker消息时，有两种情况。

若所有进程都成功地：

则快照成功，算法流程结束。然后就可以将所有这些状态传输到一个稳定的分布式存储中心，全局快照就产生了。

全局快照的难点在于，因为系统不能停止，每个进程向下游发送的消息是源源不断的，所以必须得有个东西来划分“当前的消息”与“将来的消息”，让它们不会混淆，而marker消息就是这个界限。对进程p j 的入边链路c kj 而言，如果收到的消息序列是[a, b, c, marker, d, e, f]，那么就说明a/b/c三条消息属于当前快照，而d/e/f三条消息属于下一个快照。

另外，因为每个进程都记录自己收到的消息，所以进程最终都能持有入边链路的状态。为什么要用接收进程来记录？用两句大白话来解释：

如果不这样设计，而采用简单的单令牌系统的话，就会有问题。仍然借用论文中给出的一个例子：

进程p和q以令牌（token）的传送来标定状态，s1表示州汪持有令牌，s0表示未持有令牌。假设在“token in C”全局状态下保存快照，而q的时间戳比p早，那么就会造成两个进程都处于s0状态，而q认为令牌不在链路C中，p也认为令牌不在链路C'中，因此快照里令牌就会丢失，造成不一致。

下面的图示出有两个进程的分布式系统根据Chandy-Lamport算法生成快照的过程，其中蓝色的部分表示状态已经被保存，并且进程P 1 发起快照。

天气是真的凉了哈。

晚安晚安。

❷ 【Flink 精选】阐述 Flink 的容错机制，剖析 Checkpoint 实现流程

Flink 容错机制主要是 状态的保存和恢复，涉及 state backends 状态后端、checkpoint 和 savepoint，还有 Job 和 Task 的错误恢复 。

Flink 状态后端是指 保存 Checkpoint 数据的容器 ，其分类有 MemoryStateBackend、FsStateBackend、RocksDBStateBackend ，状态的分类有 operator state 和 keyed state 。

Flink 状态保存和恢复主要依靠 Checkpoint 机制和 Savepoint 机制，两者的区别如下表所示。

快照的概念来源于相片，指照相馆的一种冲洗过程短搜隐的照片。在计算机领域， 快照是数据存储的某一时刻的状态记录 。 Flink Snapshot 快照是指作业状态的全局一致记录 。一个完整的快照是包括 source 算子的状态（例如，消费 kafka partition 的 offset）、状态算子的缓存数据和 sink 算子的状态（批量缓存数据、事务数据等）。

Checkpoint 检查点可以自动产生快照，用于Flink 故障恢复 。Checkpoint 具有分布式、异步、增量的特点。

Savepoint 保存点是用户手动触发的，保存全量的作业状态数据 。一般使用场景是作业的升级、作业的并发度缩放、迁移集群等。

Flink 是采用轻量级的分布式异步快照，其实现是采用栅栏 barrier 作为 checkpoint 的传递信号，与业务数据一样无差别地传递下去 ，目的是使得数据流被切分成微批，进行 checkpoint 保存为 snapshot。当 barrier 经过流图节点的时候，Flink 进行 checkpoint 保存状态数据。
如下图所示，checkpoint n 包含每个算子的状态，该状态是指checkpoint n 之前的全部事件，而不包含它之后戚誉的所有事件。

针对用户作业出现故障而导致结果丢失或者重复的问题，Flink 提供3种语义：
① At-Least-Once 最少一次 ：不会丢失数据，但可能会有重复结果。
② Exactly-Once 精确一次 ：checkpoint barrier 对齐机制可以保障精确一次。

① FailureRateRestartStrategy ：允许在指定时间间隔内的最大失败次数，同时可以设置重启延时时间。
② FixedDelayRestartStrategy ：允许指定的失败次数，同时可以设置重启延时时间。
③ NoRestartStrategy ：不需要重启，即 Job 直接失败。
④ ThrowingRestartStrategy ：不需要重启，直接抛异常。
Job Restart 策略可以通过 env 设置。

上述策略的父类接口是RestartStrategy，其关键是restart（重启操作）。

① RestartAllStrategy ：重启全部 task，默认策略。
② RestartIndivialStrategy ：恢复单个 task。如果该 task 没有source，可能导致数据丢失。
③ NoOpFailoverStrategy ：不恢复 task。
上述策略的父类接口是FailoverStrategy，其关键是Factory的create（创建 strategy）、onTaskFailure（处理错误）。

如何高漏段产生可靠的全局一致性快照是分布式系统的难点，其传统方案是使用的全局时钟，但存在单点故障、数据不一致等可靠性问题 。为了解决该问题， Chandy-Lamport 算法采用 marker 的传播来代替全局时钟 。

① 进程 Pi 记录自己的进程状态，同时生产一个标识信息 marker（与正常 message 不同），通过 ouput channel 发送给系统里面的其他进程。
② 进程 Pi 开始记录所有 input channel 接收到的 message

进程 Pj 从 input channel Ckj 接收到 marker。如果 Pj 还没有记录自己的进程状态，则 Pj 记录自己的进程状态，向 output channel 发送 marker；否则 Pj 正在记录自己的进程状态（该 marker 之前的 message）。

所有的进程都收到 marker 信息并且记录下自己的状态和 channel 的状态（包含的 message）。

Flink 的分布式异步快照实现了Chandy Lamport 算法，其核心思想是 在 source 插入 barrier 代替 Chandy-Lamport 算法中的 marker，通过控制 barrier 的同步来实现 snapshot 的备份和 Exactly-Once 语义 。

Checkpoint Coordinator 向所有 source 节点 trigger Checkpoint。

source task向下游广播barrier。

当source task备份完自己的状态后，会将备份数据的地址（state handle）通知 Checkpoint Coordinator。

map和sink task收集齐上游source的barrier n，执行本地快照。下面例子是RocksDB增量Checkpoint 的流程：首先RocksDB会全量保存到磁盘上（红色大三角表示），然后Flink会从中选择没有上传的文件进行持久化备份（紫色小三角）。

map和sink task在完成Checkpoint 之后，将状态地址state handle返回通知 Coordinator。

当Checkpoint Coordinator收到全部task的state handle，就确定该Checkpoint已完成，并向持久化存储中备份一个Checkpoint Meta（元数据，包括该checkpoint状态数据的备份地址）。

❸ FLink Checkpoint 介绍

这一篇主要整理下Lightweight Asynchronous Snapshots for Distributed Dataflows 知识点。

算法的前提:

1.状态只有进程本地状态，并没有管道状态(输入档镇管道buffer数据，不作为状态一分部行唤粗)
2.由同类型进程(source节点)周期出发marker消息。

更接近Candy-Lamport的实现

这里Operator的输入分为两种

有环ABS比起无环ABS,更像是Candy-Lamport的最完整的实现。

非对齐checkpoint也是最接近Candy-Lamport的实现，状态是进程状态和管道消息。

flink的快照机制其实是参考Candy-Lamport算法实现的链滑，除了在source周期注入marker消息以外，最大的区别就是状态的组成上。
无法环ABS只有本地快照状态，有环ABS状态是本地快照状态 + 环路输入消息
非对齐checkpoint则是本地快照 + 输入消息 + 输出消息

❹ 验证lamport's algorithm算法的正确性，即该算法是否能保证

算法（Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。算法+数据结构=程序，求解一个给定的可计算或可解的问题，不同的人可以编写出不同的程序，来解决同一个问题，这里存在两个问题：一是与计算方法密切相关的算法问题；二是程序设计的技术问题。算法和程序之间存在密切的关系。

❺ 常见的共识算法介绍

在异步系统中，需要主机之间进行状态复制，以保证每个主机达成一致的状态共识。而在异步系统中，主机之间可能出现故障，因此需要在默认不可靠的异步网络中定义容错协议，以确保各个主机达到安全可靠的状态共识。

共识算法其实就是一组规则，设置一组条件，筛选出具有代表性的节点。在区块链系统中，存在很多这样的筛选方案，如在公有链中的POW、Pos、DPOS等，而在不需要货币体系的许可链或私有链中，绝对信任的节点、高效的需求是公有链共识算法不能提供的，对于这样的区块链，传统的一致性共识算法成为首选，如PBFT、PAXOS、RAFT等。

目录

一、BFT（拜占庭容错技术）

二、PBFT（实用拜占庭容错算法）

三、PAXOS

四、Raft

五、POW（工作量证明）

六、POS（权益证明）

七、DPOS（委任权益证明）

八、Ripple

拜占庭弄错技术是一类分布式计算领域的容错技术。拜占庭假设是由于硬件错误、网络拥塞或中断以及遭到恶意攻击的原因，计算机和网络出现不可预测的行为。拜占庭容错用来处理这种异常行为，并满足所要解决问题的规范。

拜占庭容错系统是一个拥有n台节点的系统，整个系统对于每一个请求，满足以下条件：

1）所有非拜占庭节点使用相同的输入信息，产生同样的结果；

2）如果输入的信息正确，那么所有非拜占庭节点必须接收这个信息，并计算相应的结果。

拜占庭系统普遍采用的假设条件包括：

1）拜占庭节点的行为可以是任意的，拜占庭节点之间可以共谋；

2）节点之间的错误是不相关的；

3）节点之间通过异步网络连接，网络中的消息可能丢失、乱序并延时到达，但大部分协议假设消息在有限的时间里能传达到目的地；

4）服务器之间传递的信息，第三方可以嗅探到，但是不能篡改、伪造信息的内容和验证信息的完整性。

拜占庭容错由于其理论上的可行性而缺乏实用性，另外还需要额外的时钟同步机制支持，算法的复杂度也是随节点的增加而指数级增加。

实用拜占庭容错降低了拜占庭协议的运行复杂度，从指数级别降低到多项式级别。

PBFT是一种状态机副本复制算法，即服务作为状态机进行建模，状态机在分布式系统的不同节点进行副本复制。PBFT要求共同维护一个状态。需要运行三类基本协议，包括一致性协议、检查点协议和视图更换协议。

一致性协议。一致性协议至少包含若干个阶段：请求（request）、序号分配（pre-prepare）和响应（reply），可能包含相互交互（prepare），序号确认（commit）等阶段。

PBFT通信模式中，每个客户端的请求需要经过5个阶段。由于客户端不能从服务器端获得任何服务器运行状态的信息，PBFT中主节点是否发生错误只能由服务器监测。如果服务器在一段时间内都不能完成客户端的请求，则会触发视图更换协议。

整个协议的基本过程如下：

1）客户端发送请求，激活主节点的服务操作。

2）当主节点接收请求后，启动三阶段的协议以向各从节点广播请求。

［2.1］序号分配阶段，主节点给请求赋值一个序列号n，广播序号分配消息和客户端的请求消息m，并将构造PRE-PREPARE消息给各从节点；

［2.2］交互阶段，从节点接收PRE-PREPARE消息，向其他服务节点广播PREPARE消息；

［2.3］序号确认阶段，各节点对视图内的请求和次序进行验证后，广播COMMIT消息，执行收到的客户端的请求并给客户端以响应。

3）客户端等待来自不同节点的响应，若有m+1个响应相同，则该响应即为运算的结果。

PBFT一般适合有对强一致性有要求的私有链和联盟链，例如，在IBM主导的区块链超级账本项目中，PBFT是一个可选的共识协议。在Hyperledger的Fabric项目中，共识模块被设计成可插拔的模块，支持像PBFT、Raft等共识算法。

在有些分布式场景下，其假设条件不需要考虑拜占庭故障，而只是处理一般的死机故障。在这种情况下，采用Paxos等协议会更加高效。。PAXOS是一种基于消息传递且具有高度容错特性的一致性算法。

PAXOS中有三类角色Proposer、Acceptor及Learner，主要交互过程在Proposer和Acceptor之间。算法流程分为两个阶段：

phase 1

a) proposer向网络内超过半数的acceptor发送prepare消息

b) acceptor正常情况下回复promise消息

phase 2

a) 在有足够多acceptor回复promise消息时，proposer发送accept消息

b) 正常情况下acceptor回复accepted消息

流程图如图所示：

PAXOS协议用于微信PaxosStore中，每分钟调用Paxos协议过程数十亿次量级。

Paxos是Lamport设计的保持分布式系统一致性的协议。但由于Paxos非常复杂，比较难以理解，因此后来出现了各种不同的实现和变种。Raft是由Stanford提出的一种更易理解的一致性算法，意在取代目前广为使用的Paxos算法。

Raft最初是一个用于管理复制日志的共识算法，它是在非拜占庭故障下达成共识的强一致协议。Raft实现共识过程如下：首先选举一个leader，leader从客户端接收记账请求、完成记账操作、生成区块，并复制到其他记账节点。leader有完全的管理记账权利，例如，leader能够决定是否接受新的交易记录项而无需考虑其他的记账节点，leader可能失效或与其他节点失去联系，这时，重新选出新的leader。

在Raft中，每个节点会处于以下三种状态中的一种：

（1）follower：所有结点都以follower的状态开始。如果没收到leader消息则会变成candidate状态；

（2）candidate：会向其他结点“拉选票”，如果得到大部分的票则成为leader。这个过程就叫做Leader选举(Leader Election)；

（3）leader：所有对系统的修改都会先经过leader。每个修改都会写一条日志(log entry)。leader收到修改请求后的过程如下：此过程叫做日志复制（Log Replication）

1）复制日志到所有follower结点

2）大部分结点响应时才提交日志

3）通知所有follower结点日志已提交

4）所有follower也提交日志

5）现在整个系统处于一致的状态

Raft阶段主要分为两个，首先是leader选举过程，然后在选举出来的leader基础上进行正常操作，比如日志复制、记账等。

（1）leader选举

当follower在选举时间内未收到leader的消息，则转换为candidate状态。在Raft系统中：

1）任何一个服务器都可以成为候选者candidate，只要它向其他服务器follower发出选举自己的请求。

2）如果其他服务器同意了，发出OK。如果在这个过程中，有一个follower宕机，没有收到请求选举的要求，此时候选者可以自己选自己，只要达到N/2+1的大多数票，候选人还是可以成为leader的。

3）这样这个候选者就成为了leader领导人，它可以向选民也就是follower发出指令，比如进行记账。

4）以后通过心跳消息进行记账的通知。

5）一旦这个leader崩溃了，那么follower中有一个成为候选者，并发出邀票选举。

6）follower同意后，其成为leader，继续承担记账等指导工作。

（2）日志复制

记账步骤如下所示：

1）假设leader已经选出，这时客户端发出增加一个日志的要求；

2）leader要求follower遵从他的指令，将这个新的日志内容追加到各自日志中；

3）大多数follower服务器将交易记录写入账本后，确认追加成功，发出确认成功信息；

4）在下一个心跳消息中，leader会通知所有follower更新确认的项目。

对于每个新的交易记录，重复上述过程。

在这一过程中，若发生网络通信故障，使得leader不能访问大多数follower了，那么leader只能正常更新它能访问的那些follower服务器。而大多数的服务器follower因为没有了leader，他们将重新选举一个候选者作为leader，然后这个leader作为代表与外界打交道，如果外界要求其添加新的交易记录，这个新的leader就按上述步骤通知大多数follower。当网络通信恢复，原先的leader就变成follower，在失联阶段，这个老leader的任何更新都不能算确认，必须全部回滚，接收新的leader的新的更新。

在去中心账本系统中，每个加入这个系统的节点都要保存一份完整的账本，但每个节点却不能同时记账，因为节点处于不同的环境，接收不同的信息，如果同时记账，必然导致账本的不一致。因此通过同时来决定那个节点拥有记账权。

在比特币系统中，大约每10分钟进行一轮算力竞赛，竞赛的胜利者，就获得一次记账的权力，并向其他节点同步新增账本信息。

PoW系统的主要特征是计算的不对称性。工作端要做一定难度的工作才能得出一个结果，而验证方却很容易通过结果来检查工作端是不是做了相应的工作。该工作量的要求是，在某个字符串后面连接一个称为nonce的整数值串，对连接后的字符串进行SHA256哈希运算，如果得到的哈希结果（以十六进制的形式表示）是以若干个0开头的，则验证通过。

比特币网络中任何一个节点，如果想生成一个新的区块并写入区块链，必须解出比特币网络出的PoW问题。关键的3个要素是 工作量证明函数、区块及难度值 。工作量证明函数是这道题的计算方法，区块决定了这道题的输入数据，难度值决定了这道题所需要的计算量。

（1）工作量证明函数就是<u style="box-sizing: border-box;"> SHA256 </u>

比特币的区块由区块头及该区块所包含的交易列表组成。拥有80字节固定长度的区块头，就是用于比特币工作量证明的输入字符串。

（2）难度的调整是在每个完整节点中独立自动发生的。每2016个区块，所有节点都会按统一的公式自动调整难度。如果区块产生的速率比10分钟快则增加难度，比10分钟慢则降低难度。

公式可以总结为：新难度值=旧难度值×（过去2016个区块花费时长/20160分钟）

工作量证明需要有一个目标值。比特币工作量证明的目标值（Target）的计算公式：目标值=最大目标值/难度值

其中最大目标值为一个恒定值：

目标值的大小与难度值成反比。比特币工作量证明的达成就是矿工计算出来的 区块哈希值必须小于目标值 。

（3）PoW能否解决拜占庭将军问题

比特币的PoW共识算法是一种概率性的拜占庭协议（Probabilistic BA）

当不诚实的算力小于网络总算力的50%时，同时挖矿难度比较高（在大约10分钟出一个区块情况下）比特币网络达到一致性的概念会随确认区块的数目增多而呈指数型增加。但当不诚实算力具一定规模，甚至不用接近50%的时候，比特币的共识算法并不能保证正确性，也就是，不能保证大多数的区块由诚实节点来提供。

比特币的共识算法不适合于私有链和联盟链。其原因首先是它是一个最终一致性共识算法，不是一个强一致性共识算法。第二个原因是其共识效率低。

扩展知识： 一致性

严格一致性，是在系统不发生任何故障，而且所有节点之间的通信无需任何时间这种理想的条件下，才能达到。这个时候整个系统就等价于一台机器了。在现实中，是不可能达到的。

强一致性，当分布式系统中更新操作完成之后，任何多个进程或线程，访问系统都会获得最新的值。

弱一致性，是指系统并不保证后续进程或线程的访问都会返回最新的更新的值。系统在数据成功写入之后，不承诺立即可以读到最新写入的值，也不会具体承诺多久读到。但是会尽可能保证在某个时间级别（秒级）之后。可以让数据达到一致性状态。

最终一致性是弱一致性的特定形式。系统保证在没有后续更新的前提下，系统最终返回上一次更新操作的值。也就是说，如果经过一段时间后要求能访问到更新后的数据，则是最终一致性。

在股权证明PoS模式下，有一个名词叫币龄，每个币每天产生1币龄，比如你持有100个币，总共持有了30天，那么，此时你的币龄就为3000，这个时候，如果你发现了一个PoS区块，你的币龄就会被清空为0。你每被清空365币龄，你将会从区块中获得0.05个币的利息(假定利息可理解为年利率5%)，那么在这个案例中，利息 = 3000 * 5% / 365 = 0.41个币，这下就很有意思了，持币有利息。

点点币（Peercoin）是首先采用权益证明的货币。，点点币的权益证明机制结合了随机化与币龄的概念，未使用至少30天的币可以参与竞争下一区块，越久和越大的币集有更大的可能去签名下一区块。一旦币的权益被用于签名一个区块，则币龄将清为零，这样必须等待至少30日才能签署另一区块。

PoS机制虽然考虑到了PoW的不足，但依据权益结余来选择，会导致首富账户的权力更大，有可能支配记账权。股份授权证明机制（Delegated Proof of Stake，DPoS）的出现正是基于解决PoW机制和PoS机制的这类不足。

比特股（Bitshare）是一类采用DPoS机制的密码货币。它的原理是，让每一个持有比特股的人进行投票，由此产生101位代表 , 我们可以将其理解为101个超级节点或者矿池，而这101个超级节点彼此的权利是完全相等的。如果代表不能履行他们的职责（当轮到他们时，没能生成区块），他们会被除名，网络会选出新的超级节点来取代他们。

比特股引入了见证人这个概念，见证人可以生成区块，每一个持有比特股的人都可以投票选举见证人。得到总同意票数中的前N个（N通常定义为101）候选者可以当选为见证人，当选见证人的个数（N）需满足：至少一半的参与投票者相信N已经充分地去中心化。

见证人的候选名单每个维护周期（1天）更新一次。见证人然后随机排列，每个见证人按序有2秒的权限时间生成区块，若见证人在给定的时间片不能生成区块，区块生成权限交给下一个时间片对应的见证人。

比特股还设计了另外一类竞选，代表竞选。选出的代表拥有提出改变网络参数的特权，包括交易费用、区块大小、见证人费用和区块区间。若大多数代表同意所提出的改变，持股人有两周的审查期，这期间可以罢免代表并废止所提出的改变。这一设计确保代表技术上没有直接修改参数的权利以及所有的网络参数的改变最终需得到持股人的同意。

Ripple（瑞波）是一种基于互联网的开源支付协议，在Ripple的网络中，交易由客户端（应用）发起，经过追踪节点（tracking node）或验证节点（validating node）把交易广播到整个网络中。

追踪节点的主要功能是分发交易信息以及响应客户端的账本请求。验证节点除包含追踪节点的所有功能外，还能够通过共识协议，在账本中增加新的账本实例数据。

Ripple的共识达成发生在验证节点之间，每个验证节点都预先配置了一份可信任节点名单，称为UNL（Unique Node List）。在名单上的节点可对交易达成进行投票。每隔几秒，Ripple网络将进行如下共识过程：

1）每个验证节点会不断收到从网络发送过来的交易，通过与本地账本数据验证后，不合法的交易直接丢弃，合法的交易将汇总成交易候选集（candidate set）。交易候选集里面还包括之前共识过程无法确认而遗留下来的交易。

2）每个验证节点把自己的交易候选集作为提案发送给其他验证节点。

3）验证节点在收到其他节点发来的提案后，如果不是来自UNL上的节点，则忽略该提案；如果是来自UNL上的节点，就会对比提案中的交易和本地的交易候选集，如果有相同的交易，该交易就获得一票。在一定时间内，当交易获得超过50%的票数时，则该交易进入下一轮。没有超过50%的交易，将留待下一次共识过程去确认。

4）验证节点把超过50%票数的交易作为提案发给其他节点，同时提高所需票数的阈值到60%，重复步骤3）、步骤4），直到阈值达到80%。

5）验证节点把经过80%UNL节点确认的交易正式写入本地的账本数据中，称为最后关闭账本（Last Closed Ledger），即账本最后（最新）的状态。

在Ripple的共识算法中，参与投票节点的身份是事先知道的。该共识算法只适合于权限链（Permissioned chain）的场景。Ripple共识算法的拜占庭容错（BFT）能力为（n-1）/5，即可以容忍整个网络中20%的节点出现拜占庭错误而不影响正确的共识。

在区块链网络中，由于应用场景的不同，所设计的目标各异，不同的区块链系统采用了不同的共识算法。一般来说，在私有链和联盟链情况下，对一致性、正确性有很强的要求。一般来说要采用强一致性的共识算法。而在公有链情况下，对一致性和正确性通常没法做到百分之百，通常采用最终一致性（Eventual Consistency）的共识算法。

共识算法的选择与应用场景高度相关，可信环境使用paxos 或者raft，带许可的联盟可使用pbft ，非许可链可以是pow，pos，ripple共识等，根据对手方信任度分级，自由选择共识机制。

❻ 面包店算法的优缺点

优点：进程之间并行，有界共享寄存器。缺点：多进程读/写原子操作寄存器；饥饿问题，无容错性（没有等待资源释放）。lamport算法又称为面包店算法，它解决了多个线程并发访问一个共享的单用户资源的互斥问题的算法。优点：进程之间并行，有界共享寄存器。缺点：多进程姿宽读/写原子操作寄存器；饥饿问题，无容错性（没有等滑册碰待资源释放）。面包信谈店算法借鉴生活中取号排队的思想，取得的号不为0，则表示想要进去，按号码从小到大授予访问权限。

❼ paxos算法是什么

Paxos算法是莱斯利·兰伯特（Leslie Lamport，就是LaTeX中的＂La"，此人现在在微软研究院）于1990年提出的一种基于消息传递的一致性算法。这个算法被认为是类似算法中最有效的。

兰伯特提出的Paxos算法包含2个部分：

一个是Basic Paxos算法，描述的是多节点之间如何就某个值（提案Value）达成共识；

另一个是Multi-Paxos思想，描述的是执行多个Basic Paxos实例，就一系列值达成共识

可因为兰伯特提到的Multi-Paxos思想，缺少代码实现的必要细节（比如怎么选举领导者），所以在理解上比较难。Basic Paxos是Multi-Paxos思想的核心。

(7)lamport算法扩展阅读

背景

Paxos算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点执行相同的操作序列，那么他们最后能得到一个一致的状态。

为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。

一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。因此从20世纪80年代起对于一致性算法的研究就没有停止过。节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。Paxos算法就是一种基于消息传递模型的一致性算法。

❽ 分布式存储中，怎样使用paxos算法保证数据的一致性

在分布式系统中，我们经常遇到多数据副本保持一致的问题，在我们所能找到的资料中该问题讲的很笼统，模模糊糊的，把多个问题或分类糅合在一起，难以理解。在思考和翻阅资料后，通俗地把一致性的问题可分解为2个问题：
1、任何一次修改保证数据一致性。
2、多次数据修改的一致性。
在弱一致性的算法，不要求每次修改的内容在修改后多副本的内容是一致的，对问题1的解决比较宽松，更多解决问题2，该类算法追求每次修改的高度并发性，减少多副本之间修改的关联性，以获得更好的并发性能。例如最终一致性，无所谓每次用户修改后的多副本的一致性及格过，只要求在单调的时间方向上，数据最终保持一致，如此获得了修改极大的并发性能。
在强一致性的算法中，强调单次修改后结果的一致，需要保证了对问题1和问题2要求的实现，牺牲了并发性能。本文是讨论对解决问题1实现算法，这些算法往往在强一致性要求的应用中使用。
解决问题1的方法，通常有两阶段提交算法、采用分布式锁服务和采用乐观锁原理实现的同步方式,下面分别介绍这几种算法的实现原理。

两阶段提交算法

在两阶段提交协议中，系统一般包含两类机器（或节点）：一类为协调者（coordinator），通常一个系统中只有一个；另一类为事务参与者（participants，cohorts或workers），一般包含多个，在数据存储系统中可以理解为数据副本的个数。两阶段提交协议由两个阶段组成，在正常的执行下，这两个阶段的执行过程如下所述：
阶段1：请求阶段（commit-request phase，或称表决阶段，voting phase）。
在请求阶段，协调者将通知事务参与者准备提交或取消事务，然后进入表决过程。在表决过程中，参与者将告知协调者自己的决策：同意（事务参与者本地作业执行成功）或取消（本地作业执行故障）。
阶段2：提交阶段（commit phase）。
在该阶段，协调者将基于第一个阶段的投票结果进行决策：提交或取消。当且仅当所有的参与者同意提交事务协调者才通知所有的参与者提交事务，否则协调者将通知所有的参与者取消事务。参与者在接收到协调者发来的消息后将执行响应的操作。
举个例子：A组织B、C和D三个人去爬长城：如果所有人都同意去爬长城，那么活动将举行；如果有一人不同意去爬长城，那么活动将取消。用2PC算法解决该问题的过程如下：
首先A将成为该活动的协调者，B、C和D将成为该活动的参与者。
阶段1：A发邮件给B、C和D，提出下周三去爬山，问是否同意。那么此时A需要等待B、C和D的邮件。B、C和D分别查看自己的日程安排表。B、C发现自己在当日没有活动安排，则发邮件告诉A它们同意下周三去爬长城。由于某种原因，D白天没有查看邮件。那么此时A、B和C均需要等待。到晚上的时候，D发现了A的邮件，然后查看日程安排，发现周三当天已经有别的安排，那么D回复A说活动取消吧。
阶段2：此时A收到了所有活动参与者的邮件，并且A发现D下周三不能去爬山。那么A将发邮件通知B、C和D，下周三爬长城活动取消。此时B、C回复A“太可惜了”，D回复A“不好意思”。至此该事务终止。
两阶段提交算法在分布式系统结合，可实现单用户对文件（对象）多个副本的修改，多副本数据的同步。其结合的原理如下：
1、客户端（协调者）向所有的数据副本的存储主机（参与者）发送：修改具体的文件名、偏移量、数据和长度信息，请求修改数据，该消息是1阶段的请求消息。
2、存储主机接收到请求后，备份修改前的数据以备回滚，修改文件数据后，向客户端回应修改成功的消息。 如果存储主机由于某些原因（磁盘损坏、空间不足等）不能修改数据，回应修改失败的消息。
3、客户端接收发送出去的每一个消息回应，如果存储主机全部回应都修改成功，向每存储主机发送确认修改的提交消息；如果存在存储主机回应修改失败，或者超时未回应，客户端向所有存储主机发送取消修改的提交消息。该消息是2阶段的提交消息。
4、存储主机接收到客户端的提交消息，如果是确认修改，则直接回应该提交OK消息；如果是取消修改，则将修改数据还原为修改前，然后回应取消修改OK的消息。
5、 客户端接收全部存储主机的回应，整个操作成功。
在该过程中可能存在通信失败，例如网络中断、主机宕机等诸多的原因，对于未在算法中定义的其它异常，都认为是提交失败，都需要回滚，这是该算法基于确定的通信回复实现的，在参与者的确定回复（无论是回复失败还是回复成功）之上执行逻辑处理，符合确定性的条件当然能够获得确定性的结果哲学原理。

分布式锁服务

分布式锁是对数据被外界修改持保守态度，在整个数据处理过程中将数据处于锁定状态，在用户修改数据的同时，其它用户不允许修改。
采用分布式锁服务实现数据一致性，是在操作目标之前先获取操作许可，然后再执行操作，如果其他用户同时尝试操作该目标将被阻止，直到前一个用户释放许可后，其他用户才能够操作目标。分析这个过程，如果只有一个用户操作目标，没有多个用户并发冲突，也申请了操作许可，造成了由于申请操作许可所带来的资源使用消耗，浪费网络通信和增加了延时。
采用分布式锁实现多副本内容修改的一致性问题， 选择控制内容颗粒度实现申请锁服务。例如我们要保证一个文件的多个副本修改一致， 可以对整个文件修改设置一把锁，修改时申请锁，修改这个文件的多个副本，确保多个副本修改的一致，修改完成后释放锁；也可以对文件分段，或者是文件中的单个字节设置锁， 实现更细颗粒度的锁操作，减少冲突。
常用的锁实现算法有Lamport bakery algorithm （俗称面包店算法）， 还有Paxos算法。下面对其原理做简单概述。

Lamport面包店算法

是解决多个线程并发访问一个共享的单用户资源的互斥问题的算法。 由Leslie Lamport（英语：Leslie Lamport）发明。
Lamport把这个并发控制算法可以非常直观地类比为顾客去面包店采购。面包店只能接待一位顾客的采购。已知有n位顾客要进入面包店采购，安排他们按照次序在前台登记一个签到号码。该签到号码逐次加1。根据签到号码的由小到大的顺序依次入店购货。完成购买的顾客在前台把其签到号码归0. 如果完成购买的顾客要再次进店购买，就必须重新排队。
这个类比中的顾客就相当于线程，而入店购货就是进入临界区独占访问该共享资源。由于计算机实现的特点，存在两个线程获得相同的签到号码的情况，这是因为两个线程几乎同时申请排队的签到号码，读取已经发出去的签到号码情况，这两个线程读到的数据是完全一样的，然后各自在读到的数据上找到最大值，再加1作为自己的排队签到号码。为此，该算法规定如果两个线程的排队签到号码相等，则线程id号较小的具有优先权。
把该算法原理与分布式系统相结合，即可实现分步锁。

Paxos算法

该算法比较热门，参见WIKI，http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95
Paxos算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。节点通信存在两种模型：共享内存(Shared memory)和消息传递(Messages passing)。Paxos算法就是一种基于消息传递模型的一致性算法。BigTable使用一个分布式数据锁服务Chubby，而Chubby使用Paxos算法来保证备份的一致性。

采用乐观锁原理实现的同步

我们举个例子说明该算法的实现原理。如一个金融系统，当某个操作员读取用户的数据，并在读出的用户数据的基础上进行修改时（如更改用户帐户余额），如果采用前面的分布式锁服务机制，也就意味着整个操作过程中（从操作员读出数据、开始修改直至提交修改结果的全过程，甚至还包括操作员中途去煮咖啡的时间），数据库记录始终处于加锁状态，可以想见，如果面对几百上千个并发，这样的情况将导致怎样的后果。
乐观锁机制在一定程度上解决了这个问题。乐观锁，大多是基于数据版本（ Version）记录机制实现。何谓数据版本？即为数据增加一个版本标识，在基于数据库表的版本解决方案中，一般是通过为数据库表增加一个 “version” 字段来实现。读取出数据时，将此版本号一同读出，之后更新时，对此版本号加一。此时，将提交数据的版本数据与数据库表对应记录的当前版本信息进行比对，如果提交的数据版本号大于数据库表当前版本号，则予以更新，否则认为是过期数据。
对于上面修改用户帐户信息的例子而言，假设数据库中帐户信息表中有一个 version 字段，当前值为 1 ；而当前帐户余额字段（ balance ）为 $100 。
操作员 A 此时将其读出（version=1 ），并从其帐户余额中扣除 $50（$100-$50 ）。
在操作员 A 操作的过程中，操作员B也读入此用户信息（ version=1 ），并从其帐户余额中扣除 $20 （ $100-$20 ）。
操作员 A 完成了修改工作，将数据版本号加一（ version=2 ），连同帐户扣除后余额（ balance=$50 ），提交至数据库更新，此时由于提交数据版本大于数据库记录当前版本，数据被更新，数据库记录 version 更新为 2 。
操作员 B 完成了操作，也将版本号加一（ version=2 ）试图向数据库提交数据（ balance=$80 ），但此时比对数据库记录版本时发现，操作员 B 提交的数据版本号为 2 ，数据库记录当前版本也为 2 ，不满足 “ 提交版本必须大于记录当前版本才能执行更新 “ 的乐观锁策略，因此，操作员 B 的提交被驳回。这样，就避免了操作员 B 用基于 version=1 的旧数据修改的结果覆盖操作员A 的操作结果的可能。
乐观锁机制与分布式系统相结合上， 我整理了伪代码如下：
obj 操作的目标
vlaue 修改的值
atom_update_ver 每个目标上的版本，每次修改该值递增
set( obj, value)
{
//从每个节点上取出修改前的对象版本
get original_ver = obj.atom_update_ver from each node;
//将值赋到每个节点的obj目标
set obj = value from each node;
//条件修改每个节点的obj版本，目标版本加一
//比较和修改操作是原子操作
result = (set obj.atom_update_ver = original_ver + 1
where original_ver + 1 > obj.atom_update_ver
for each node);
if(result == ok)
return set_ok;
else
return set(obj, value);//不成功递归修改

该算法未考虑节点下线、失效等问题，在后续我将分析采用乐观锁原理实现一致性算法，解决问题2、节点失效、通信失败等问题。