当前位置: article > 正文

分布式基础知识

作者：从前慢现在也慢 | 2024-03-23 16:34:01

踩

分布式基础

定义

分布式：通俗点说就是一个/多个服务分散部署在不同机器，相互之间通过网络协调的一种工作方式。区别于传统的一个机器一个服务

共识算法

共识算法常常跟数据一致性算法搞混，其实两个是不同的东西。共识是Consensus，一致性是Consistency，Consistency是系统中需要保证的一个属性（即“Allowed ways”），而Consensus算法是实现Consistency的一种手段（主要是最终一致性）。以下介绍一些基本概念。

分布式一致性指集群所有节点数据完全相同并能够对某个提案（Proposal）达成一致。而达成一致性主要面临的问题有：

节点失效/故障/宕机
节点间通信干扰/篡改/失效
恶意节点

CAP原则

CAP原则定义：在异步的网络模型中，所有的节点由于没有时钟仅仅能根据接收到的消息作出判断，这时完全不能同时保证一致性、可用性和分区容错性，每一个系统只能在这三种特性中选择两种。（与数据库事务的ACID中的C完全不一样，后者指事务只能把数据库从一种合法状态到另一种）

CAP三个特征分别的解释如下：

C（Consistency，强一致性）：所有节点接收到同样的操作时会按照完全相同的顺序执行，被一个节点提交的更新操作会立刻反映在其他通过异步或部分同步网络连接的节点上。客户端无论连接哪个节点都会看到相同的数据
A（Availability，可用性）：即使一个或多个节点宕机，所有客户端的请求都还是会得到及时&合法的回应
P（Partition Tolerance，分区容错性）：指当分布式系统发生通信中断，节点间连接中断或延迟。分区容错就是指当这种节点间通信断开时，集群仍能正常工作

CAP与数据库：NoSQL相较于传统的关系型数据库，更适合分布式的网络应用，因为在连接激增时可以更好地水平扩展。可以参考https://www.ibm.com/cloud/blog/sql-vs-nosql介绍了分布式方面关系数据库和NoSQL的区别，像Citus和Vitess是通过在顶层分片这种“NewSQL”风格来实现的分布式引擎。关系数据库存在有难以水平扩展&严格的表设计等问题。

以下是CAP三种取舍方式和应用：

CP（强一致性&分区容错性）：在异步的网络中想要同时满足CP的方法就是，我们只能中心化存储所有数据，通过其他节点将请求路由给中心节点达到这两个目的。满足此特征的应用有：MongoDB、Zookeeper（对于脑裂做了限制放弃了可用性）、Redis
AP（可用性&分区容错性）：为了更好的扩展，NoSQL型数据库放弃了严格的最终一致性，使得他们相较于关系型数据库更适合分布式扩展性（当然牺牲了像外键、事务等）。满足此特征的应用有：Cassandra（他是无Master架构，多点故障还是可以提供写能力，在分区故障恢复后通过修复能力恢复一致性）、Eureka、ConfigServer
AC（可用性&强一致性）：分布式系统中分区是不可避免的，实践中基本没有基于AC的分布式数据库（并不是不能实现，关系数据库将数据复制到各个节点可以实现）

BASE理论

BASE理论定义：Basically Available（基本可用）+ Soft state（软状态）+ Eventually consistent（最终一致性）。它是对于CAP的一个扩展，强调在AP情况下可以通过放弃强一致性选择最终一致性，这样可以保证核心功能可用，而数据可用在一段时间内不一致，常见于实际生产中。满足BASE理论的事务，我们称之为柔性事务。

基本可用： 分布式系统在出现故障时，允许损失部分可用功能，保证核心功能可用。如电商网址交易付款出现问题来，商品依然可以正常浏览。

软状态： 由于不要求强一致性，所以BASE允许系统中存在中间状态（也叫软状态），这个状态不影响系统可用性，如订单中的“支付中”、“数据同步中”等状态，待数据最终一致后状态改为“成功”状态。

最终一致性： 最终一致是指的经过一段时间后，所有节点数据都将会达到一致。如订单的“支付中”状态，最终会变为“支付成功”或者“支付失败”，使订单状态与实际交易结果达成一致，但需要一定时间的延迟、等待。

拜占庭将军问题

分布式系统中节点间的通信如何让整个集群保证一致性？拜占庭将军问题是讨论分布式领域的容错问题，它是分布式领域中最复杂、最严格的容错模型。大多数分布式系统不需要满足这些容错要求，一般出现的问题是节点宕机/不响应等不会有消息不可靠问题，但是对于Bitcoin、Ethereum等分布式系统必须要考虑拜占庭容错问题

拜占庭将军问题内容：描绘了一个场景，有一组将军分别指挥一部分军队，每一个将军都不知道其它将军是否是可靠的，也不知道其他将军传递的信息是否可靠，但是它们需要通过投票（少数服从多数）选择是否要进攻或者撤退。当所有将军达成了同一致的方案，选择进攻或撤退都没有问题。但是将军中可能存在这些情况：投撤退、投进攻、不投、叛徒。当出现一个叛徒或信息在传递过程被拦截，会导致一部分将军选择进攻，剩下的选择撤退，这就是出现了不一致问题

假设有9位将军投票，其中1名叛徒。8名忠诚的将军中出现了4人投进攻，4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻，而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来，投票结果是5人投进攻，从而发起进攻；而在4名投撤离的将军看来则是5人投撤离。这样各支军队的一致协同就遭到了破坏

放在分布式系统角度可以理解为，它提出了一个可能导致系统不一致的错误模型。错误节点可以做任何事情：不响应、发送错误信息、对不同节点发送不同决定、不同错误节点联合干坏事等。这个问题直到bitcoin出来才被高度关注，因为他跟double spend问题本质是一样的

拜占庭将军问题不可解情况：在n个节点的集群内，有t个节点可能发生任意错误的情况下，如果n <= 3t，则正确的共识无法达成。即如果有3个将军，1个是叛徒，则不可能达成进攻与否的共识。

拜占庭将军问题算法有两种（需要满足n>=3t+1）：口头协议算法和书面协议算法。对于口头协议算法的推导过程可以参考这个回答 https://www.zhihu.com/question/23167269/answer/134000043，需要补充的是这个算法本质是递归的，这里回答解释了当叛徒数为2的情况，即递归两层，因为叛徒只有2个，这也就是为什么最终的结论只用majority（a2，b3，b4，b5，b6）而不用继续验证副官C的真实性

拜占庭将军问题和两将军问题区别：两者是完全不同的问题。前者问题在于信息内容自身会出现冲突，需要方法让大家达成一致；后者不会出现背叛问题，关注点在于信息的丢失和超时问题

FLP不可能定理

FLP不可能定理（FLP Impossibility）：在网络可靠并且存在节点失效（即使有一个节点失败）的异步模型系统中，没有任何算法能保证非失败节点达到一致性

首先什么是异步模型系统，同步指系统中的各个节点的时钟误差存在上限、消息传递在一定时间内完成否则失败、各个节点完成处理消息的时间是一定的。因此同步系统很容易判断消息是否丢失。异步指各个节点可能存在较大的时钟差异、信息传输时间是任意长的、处理消息时间也是任意长的，因此无法在有限时间内判断某个消息迟迟没到原因是因为响应时间长还是没有响应。像消息队列系统就是一种异步系统

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

这个定理的意义是告诉我们没必要浪费时间去为异步分布式系统设计任意场景下都能实现的共识算法。但对于同步的系统，一致性问题是可解的，比如常见的Paxos和Paft算法。

共识算法应用场景

各种共识算法根据是否存在拜占庭问题可以分为两类：

非拜占庭问题共识算法，如Paxos、Raft、Zab等，其应用则是Chubby粗粒度分布式锁、etcd高可用k-v存储系统、Zookeeper高可用分布式协调者，一般属于较为安全的内部网络；
拜占庭问题共识算法，如PBFT（拜占庭算法）、DBFT（授权拜占庭容错算法）、POW（比特币共识算法）等，应用于比特币、区块链等公共分布式网络环境

Paxos算法

它是解决分布式数据一致性问题的协议，由拜占庭将军问题提出者Leslie Lamport发明，是一种非拜占庭问题共识解决方案。它能够让分布式网络中的节点在出现错误时（前提是没有恶意节点，即不存在拜占庭问题）仍然能保持一致。由于实现和证明难以理解，所以后面出现了Raft共识算法

Paxos是一类协议，包含Basic Paxos、Multi Paxos、Cheap Paxos和其他变种

Raft算法

Raft其实是Multi Paxos的一个变种，它通过简化模型，实现了更容易理解的共识算法

Paxos算法：由拜占庭将军问题提出者Leslie Lamport发明。谷歌分布式锁服务Chubby是以Paxos算法为基础。
Raft算法：Paxos的简化版共识算法，依靠状态机&主从同步实现各个节点间的数据一致性
ZAB算法：Zookeeper所用的共识算法，在流程上与Raft接近
PBFT算法：区块链技术使用的共识算法之一，适用于私有链的共识

参考

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/296332