干货 | 一致性算法与区块链基础设施建设(附PPT)

简介:

65901e1a89570621a0a09d6ed43934c0892ef3e4

刘运渠:要理解区块链,我们必须理解分布式系统,以及分布式系统如何保证一致性。这里的一致性指的是英语里的consistency。一致性和时间有直接逻辑和数学关系。爱因斯坦狭义相对论说没有时间,只有同步的事件。在计算机领域中,Leslie Lamport在他的著名论文里面说过,他不知道物理世界里面有没有时间,但是可以明确的说计算机系统里没有时间。FLP和CAP都表明在非同步的网络上要实现一致性技术是不可能的。 工程上在一定概率内,例如99.9%,可以实现可靠性一致性等等。

一致性在我们日常活动中例子,可以用我们几个人去哪吃饭的决策过程来举例。有几个方案来决定。一个是一人决定。第二种是一个人说的不算,需几个人投票。第一种方案是很典型的中心化权力方案,第二种方案我们用高大上投票方案,很多一致性基于多数投票(Quorum)的。比如说在比特币里是最长链说了算,DAG里面说权重最重的那部分说了算,其实都是投票制的方案。

07184dad6f1eb2e99694e7b8b65f2832f1f0156e

用计算机的术语来描述一致性。同样10台电脑,上面都有一个变量叫A,当所有变量A被赋值为1的时候,我们说是一致的。如果有9个机器赋值为1,另外一个机器赋值为0,这就是不一致。我们知道赋值不会自动发生,一般是有一个状态机给它赋值。如果多个节点的状态机里面,状态都是相同的,这就是一致的。在一个集群里面,所有状态机,输入状态机的数据是相同的,而且是同顺序的。这时候状态机就会停止在同一个状态,我们说状态机取得了一致。

在区块链场景里面一致性到底是什么意思?无非是两个问题:

 ●  每一个地址和账号里面,UTXO的数据是一致的。
 ●  谁把钱转给谁,保证这件事情一致,这是电子货币的系统的基础。

假设我们的资产不是电子货币,而是任何其他的电子数字资产,也就是说你要对数字资产的状态和交易数据一致。

4f4a3b1b8ba078d09f14bbf2b74aa2ef3308edaf

用阿里巴巴的讲法,分布式系统有两个最基本问题(一致性与唯一性),和两个最基本的技术,data replication,与一致性哈希。我今天只讲是Data Replication,状态机在它开始工作之前,我也可以当成一个数据处理。一致性问题可以转化成Data Replication问题,是因为我们可以转化成状态机一致性问题,状态机翻转问题。外部一致性的问题也可以理解为Data Replication问题。

6d381926f108a2bff43e3af5d90f945e10fc435f

假设状态机本身是运行良好,我们可以把一致性转化为广播问题。另外,很多时候前状态和后状态之间没有因果性,没有因果性的事件之间不需要顺序上一致。只有因果性事件才需要顺序上的一致。

在广播问题中,FIFO广播是指消息按照它送的顺序收到,日常交谈中这几乎显然的,那是因为我们有空气广播作为稳定的广播通道。如果你在IP网络发一个包,你先发的后收到,后发的先收到。

原子广播意思就是除非所有人都收到,否则这个消息就撤回。只要其中有一个人没有听到,就把信息撤回。

4e86ed3ff1693037f67a2993bb32f724d01fc2c8

拜占庭将军,是不确定性的通信系统。这个问题怎么解决?广播出去让所有人都知道,广播解决方案可以叫做去中心化,也可以叫多中心化。

e6bd728cd0d998314aed50a6e4f4b7d086ef9e56

广播有很多种实现。

 ●  第一种尽力实现的广播服务,网络提供广播服务,但是不保证送达。就像IPMC。
 ●  第二种保证送达广播,但不保证FIFO,也不保证原子性,例如简单的基于TCP的overlay广播。最后一种是原子广播与可靠广播。

第一层是用户层实现,好处是很容易应用,缺点就是性能比较差。第二层在物理层实现,但是还没有一种网络设备提供可靠的广播。

920eb9728f4d8eba3f35add4c8dc93d4cf238ef8

常见的交换模型如Infiniband模型,所用的方法三级multi-stage模型。大家会看到这个方法实现会有blocking。

我们的新架构,Optical Broadcast-Select Switch,里面有N的3次方的节点,实现N的N次方的任意组合,所以可以支持可靠的任意光广播(arbitrary multicast)。在加拿大做的产品原型prototype,在12个节点做到了68亿不丢包。可以用这样硬件做一个广播负荷的卸载技术。这是可以在广播上应用的高性能技术。

2cd2a44c5799a09d21f0335e3c92c80fdbcf9166

最后是区块链与基础网络的问题。区块链技术的一个重要价值是去中心化的交易,不需要第三方信任,可以支持一个完全开放的系统。区块链的不可能三角是指去中心化,性能与安全性三个不可能都同时满足。

区块链基础设施,基于现在互联网络设施的区块链,如同当年的64K拨号上网internet,不仅仅是性能问题,而是基础设施的设计原则发生了变化。它的性能里面的交易特性,跟总量、带宽、时延都有关系。

我们用一个网络路由算法Pub/Sub architecture来提升广播服务。这个网络平面在基础设施层面上提供一个广播的服务,不是简单把数据乱丢,而是知道哪个节点是我要的。

d8aeda25eb22e39c5193512c8db10ae4f2902a8a

清华数据院对区块链基础设施的想法,我们提供了广播的高速广域,不是仅仅为了支持区块链服务,而是支持整个数据服务。 我们希望做到更低的时延。


原文发布时间为:2018-11-6
本文作者:刘运渠
本文来自云栖社区合作伙伴“ 数据派THU”,了解相关信息可以关注“ 数据派THU”。
相关文章
|
8月前
|
消息中间件 算法 分布式数据库
Raft算法:分布式一致性领域的璀璨明珠
【4月更文挑战第21天】Raft算法是分布式一致性领域的明星,通过领导者选举、日志复制和安全性解决一致性问题。它将复杂问题简化,角色包括领导者、跟随者和候选者。领导者负责日志复制,确保多数节点同步。实现细节涉及超时机制、日志压缩和网络分区处理。广泛应用于分布式数据库、存储系统和消息队列,如Etcd、TiKV。其简洁高效的特点使其在分布式系统中备受青睐。
|
8月前
|
算法 分布式数据库
Paxos算法:分布式一致性的基石
【4月更文挑战第21天】Paxos算法是分布式一致性基础,由Leslie Lamport提出,包含准备和提交阶段,保证安全性和活性。通过提案编号、接受者和学习者实现,广泛应用于分布式数据库、锁和配置管理。其简单、高效、容错性强,影响了后续如Raft等算法,是理解分布式系统一致性关键。
|
8月前
|
存储 缓存 负载均衡
一致性 Hash 算法 Hash 环发生偏移怎么解决
一致性 Hash 算法 Hash 环发生偏移怎么解决
156 1
|
5月前
|
存储 算法 NoSQL
(七)漫谈分布式之一致性算法下篇:一文从根上儿理解大名鼎鼎的Raft共识算法!
Raft通过一致性检查,能在一定程度上保证集群的一致性,但无法保证所有情况下的一致性,毕竟分布式系统各种故障层出不穷,如何在有可能发生各类故障的分布式系统保证集群一致性,这才是Raft等一致性算法要真正解决的问题。
134 11
|
5月前
|
存储 算法 索引
(六)漫谈分布式之一致性算法上篇:用二十六张图一探Raft共识算法奥妙之处!
现如今,大多数分布式存储系统都投向了Raft算法的怀抱,而本文就来聊聊大名鼎鼎的Raft算法/协议!
150 8
|
5月前
|
存储 算法 Java
(五)漫谈分布式之一致性算法篇:谁说Paxos晦涩难懂?你瞧这不一学就会!
没在时代发展的洪流中泯然于众的道理很简单,是因为它们并不仅是空中楼阁般的高大上理论,而是有着完整落地的思想,它们已然成为构建分布式系统不可或缺的底层基石,而本文则来好好聊聊分布式与一致性思想的落地者:Paxos与Raft协议(算法)。
120 6
|
6月前
|
缓存 负载均衡 算法
(四)网络编程之请求分发篇:负载均衡静态调度算法、平滑轮询加权、一致性哈希、最小活跃数算法实践!
先如今所有的技术栈中,只要一谈关于高可用、高并发处理相关的实现,必然会牵扯到集群这个话题,也就是部署多台服务器共同对外提供服务,从而做到提升系统吞吐量,优化系统的整体性能以及稳定性等目的。
108 2
|
8月前
|
缓存 负载均衡 算法
C++如何实现一致性算法
一致性哈希是一种用于分布式系统的负载均衡算法,旨在减少服务器增减导致的数据迁移。当有N台服务器时,通过哈希环将请求均匀分布到每台服务器,每台处理N/1的请求。若使用缓存如Redis,可进一步处理高并发场景。算法将哈希值空间视为环形,服务器和请求哈希后定位到环上,按顺时针方向找到第一台服务器作为负载目标。提供的C++代码实现了MD5哈希函数,以及一致性哈希算法的物理节点、虚拟节点和算法本身,以实现节点的添加、删除和请求映射。
61 1
C++如何实现一致性算法
|
8月前
|
算法 程序员 分布式数据库
分布式一致性必备:一文读懂Raft算法
Raft算法是一种用于分布式系统中复制日志一致性管理的算法。它通过选举领导者来协调日志复制,确保所有节点数据一致。算法包括心跳机制、选举过程、日志复制和一致性保证。当领导者失效时,节点会重新选举,保证高可用性。Raft易于理解和实现,提供强一致性,常用于分布式数据库和协调服务。作者小米分享了相关知识,鼓励对分布式系统感兴趣的读者进一步探索。
1498 0
|
8月前
|
存储 算法 安全
5. raft 一致性算法
5. raft 一致性算法