Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 15712fc

Browse filesBrowse files
SnailclimbSnailclimb
committed
[docs add]paxos算法
1 parent ff9efdd commit 15712fc
Copy full SHA for 15712fc
Expand file treeCollapse file tree

18 files changed

+84
-11
lines changed
Open diff view settings
Collapse file

‎docs/distributed-system/theorem&algorithm&protocol/gossip.md‎

Copy file name to clipboardExpand all lines: docs/distributed-system/theorem&algorithm&protocol/gossip.md
+10-6Lines changed: 10 additions & 6 deletions
  • Display the source diff
  • Display the rich diff
Original file line numberDiff line numberDiff line change
@@ -2,21 +2,25 @@
22

33
在分布式系统中，不同的节点进行数据/信息共享是一个基本的需求。
44

5-
比较简单粗暴的方法集中式发散消息，简单来说就是一个主节点同时共享最新信息给其他所有节点。但是，这种方法缺陷太多，节点多的时候不光同步消息的效率低，还太依赖与主节点，存在单点风险。
5+
一种比较简单粗暴的方法就是 **集中式发散消息**，简单来说就是一个主节点同时共享最新信息给其他所有节点，比较适合中心化系统。这种方法的缺陷也很明显，节点多的时候不光同步消息的效率低，还太依赖与中心节点，存在单点风险问题。
66

7-
于是，分散式发散消息的 Gossip 协议就诞生了。
7+
于是，**分散式发散消息** 的 **Gossip 协议** 就诞生了。
88

99
## Gossip 协议介绍
1010

11-
Gossip 直译过来就是闲话、流言蜚语的意思。流言蜚语有什么特点呢？容易被传播，你传我我传他，然后大家都知道了。
11+
Gossip 直译过来就是闲话、流言蜚语的意思。流言蜚语有什么特点呢？容易被传播且传播速度还快，你传我我传他，然后大家都知道了。
1212

13-
Gossip 协议也叫 Epidemic 协议（流行病协议）或者 Epidemic propagation 算法（疫情传播算法），别名很多。不过，这些名字的特点是都具有 **随机传播特性** 的特点（联想一下病毒传播、癌细胞扩散等生活中常见的情景），这也正是 Gossip 协议最主要的特点。
13+
![](./images/gossip/gossip.png)
14+
15+
Gossip 协议也叫 Epidemic 协议（流行病协议）或者 Epidemic propagation 算法（疫情传播算法），别名很多。不过，这些名字的特点都具有 **随机传播特性** （联想一下病毒传播、癌细胞扩散等生活中常见的情景），这也正是 Gossip 协议最主要的特点。
1416

1517
Gossip 协议最早是在 ACM 上的一篇 1987 年发表的论文 [《Epidemic Algorithms for Replicated Database Maintenance》](https://dl.acm.org/doi/10.1145/41840.41841)中被提出的。根据论文标题，我们大概就能知道 Gossip 协议当时提出的主要应用是在分布式数据库系统中各个副本节点同步数据。
1618

17-
正如其名一样，这是一种随机且带有传染性的方式将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致。
19+
正如 Gossip 协议其名一样，这是一种随机且带有传染性的方式将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致。
20+
21+
在 Gossip 协议下，没有所谓的中心节点，每个节点周期性地随机找一个节点互相同步彼此的信息，理论上来说，各个节点的状态最终会保持一致。
1822

19-
下面我们来对 Gossip 协议的定义做一个总结： **Gossip 协议是一种允许在分布式系统中共享状态的通信协议，通过这种通信协议，我们可以将信息传播给网络或集群中的所有成员。**
23+
下面我们来对 Gossip 协议的定义做一个总结： **Gossip 协议是一种允许在分布式系统中共享状态的去中心化通信协议，通过这种通信协议，我们可以将信息传播给网络或集群中的所有成员。**
2024

2125
## Gossip 协议应用
2226

Collapse file

‎docs/distributed-system/theorem&algorithm&protocol/images/gossip/gossip.png‎

Copy file name to clipboard
9.56 KB
  • Display the source diff
  • Display the rich diff
Loading
Collapse file

‎docs/distributed-system/theorem&algorithm&protocol/images/gossip/redis-cluster-gossip.png‎

Copy file name to clipboard
-775 Bytes
  • Display the source diff
  • Display the rich diff
Loading
Collapse file

‎docs/distributed-system/theorem&algorithm&protocol/images/gossip/反熵-闭环.png‎

Copy file name to clipboard
-1.1 KB
  • Display the source diff
  • Display the rich diff
Loading
Collapse file

‎docs/distributed-system/theorem&algorithm&protocol/images/paxos/paxos-made-simple.png‎

Copy file name to clipboard
5.12 KB
  • Display the source diff
  • Display the rich diff
Loading
Collapse file

‎docs/distributed-system/theorem&algorithm&protocol/paxos-algorithm.md‎

Copy file name to clipboardExpand all lines: docs/distributed-system/theorem&algorithm&protocol/paxos-algorithm.md
+74-1Lines changed: 74 additions & 1 deletion
  • Display the source diff
  • Display the rich diff
Original file line numberDiff line numberDiff line change
@@ -5,5 +5,78 @@ tag:
55
- 分布式协议&算法
66
---
77

8-
Paxos 算法诞生于 1990 年，这是一种解决分布式系统一致性的经典算法 。但是，由于 Paxos 算法在国际上被公认的非常难以理解和实现，因此不断有人尝试简化这一算法。到了2013 年才诞生了一个比 Paxos 算法更易理解和实现的分布式一致性算法—[Raft 算法](https://javaguide.cn/distributed-system/theorem&algorithm&protocol/raft-algorithm/)。
8+
## 背景
99

10+
11+
12+
## Paxos 算法介绍
13+
14+
Paxos 算法是 Leslie Lamport（[莱斯利·兰伯特](https://zh.wikipedia.org/wiki/莱斯利·兰伯特)）在 **1990** 年提出了一种分布式系统共识算法。
15+
16+
> 很多人会误把 Paxos 看作是一致性算法。
17+
>
18+
> ⚠️注意：**Paxos 不是一致性算法而是共识算法，一致性和共识并不是一个概念。**
19+
20+
为了介绍 Paxos 算法，兰伯特专门写了一篇幽默风趣的论文。在这篇论文中，他虚拟了一个叫做 Paxos 的希腊城邦来更形象化地介绍 Paxos 算法。不过，审稿人可不觉得论文太幽默是一件好事，他们就给兰伯特说：“如果你想要成功发表这篇论文的话，必须删除所有 Paxos 相关的故事背景”。兰伯特一听就不开心了：“我凭什么修改啊，你们这些审稿人就是缺乏幽默细胞，发不了就不发了呗！”。
21+
22+
于是乎，提出 Paxos 算法的那篇论文在当时并没有被成功发表。
23+
24+
直到 1998 年，系统研究中心 (Systems Research Center，SRC）的两个大佬需要找一些合适的算法来服务他们正在构建的分布式系统，Paxos 算法刚好可以解决他们的部分需求。因此，兰伯特就把论文发给了他们。在看了论文之后，这俩大佬觉得论文还是挺不错的。于是，兰伯特在 **1998** 年重新发表论文 [《The Part-Time Parliament》](http://lamport.azurewebsites.net/pubs/lamport-paxos.pdf)。
25+
26+
论文发表之后，各路学者直呼看不懂，言语中还略显调侃之意。这谁忍得了，在 **2001** 年的时候，兰伯特又写了一篇 [《Paxos Made Simple》](http://lamport.azurewebsites.net/pubs/paxos-simple.pdf) 的论文来简化对 Paxos 的介绍，主要讲述两阶段共识协议部分。
27+
28+
这篇论文就 14 页，相比于 《The Part-Time Parliament》的33 页精简了不少。最关键的是这篇论文的摘要就一句话：
29+
30+
![](./images/paxos/paxos-made-simple.png)
31+
32+
> The Paxos algorithm, when presented in plain English, is very simple.
33+
34+
翻译过来的意思大概就是：当我用无修饰的英文来描述时，Paxos 算法真心简单！
35+
36+
有没有感觉到来自兰伯特大佬满满地嘲讽的味道？
37+
38+
兰伯特当时提出的 Paxos 算法主要包含 2 个部分:
39+
40+
- **Basic Paxos 算法** ： 描述的是多节点之间如何就某个值(提案 Value)达成共识。
41+
- **Multi-Paxos 思想** ： 描述的是执行多个 Basic Paxos 实例，就一系列值达成共识。Multi-Paxos 说白了就是执行多次 Basic Paxos ，核心还是 Basic Paxos 。
42+
43+
由于 Paxos 算法在国际上被公认的非常难以理解和实现，因此不断有人尝试简化这一算法。到了2013 年才诞生了一个比 Paxos 算法更易理解和实现的共识算法—[Raft 算法](https://javaguide.cn/distributed-system/theorem&algorithm&protocol/raft-algorithm.html) 。更具体点来说，Raft 是Multi-Paxos的一个变种，其简化了 Multi-Paxos 的思想，变得更容易被理解以及工程实现。
44+
45+
Paxos是第一个被证明完备的共识算法（前提是不存在拜占庭将军问题，也就是没有恶意节点），除了 Raft 算法之外，当前最常用的一些共识算法比如 ZAB 协议、 Fast Paxos 算法都是基于 Paxos 算法改进的。
46+
47+
针对存在恶意节点的情况，一般使用的是工作量证明（POW，Proof-of-Work）、权益证明（PoS，Proof-of-Stake ）等共识算法。这类共识算法最典型的应用就是区块链，就比如说前段时间以太坊官方宣布其共识机制正在从工作量证明(PoW)转变为权益证明(PoS)。
48+
49+
区块链系统使用的共识算法需要解决的核心问题是 **拜占庭将军问题** ，这和和我们日常接触到的 ZooKeeper、Etcd、Consul 等分布式中间件不太一样。
50+
51+
下面我们来对 Paxos 算法的定义做一个总结：
52+
53+
- Paxos 算法是兰伯特在 **1990** 年提出了一种分布式系统共识算法。
54+
- 兰伯特当时提出的 Paxos 算法主要包含 2 个部分:Basic Paxos 算法和Multi-Paxos 思想。
55+
- Raft 算法、ZAB 协议、 Fast Paxos 算法都是基于 Paxos 算法改进而来。。
56+
57+
## 一致性（Consistency）与共识（Consensus）
58+
59+
60+
61+
## Basic Paxos 算法
62+
63+
Basic Paxos 中存在 3 个重要的角色：
64+
65+
1. **提议者（Proposer）**：也可以叫做协调者（coordinator），提议者负责接受客户端发起的提议，然后尝试让接受者接受该提议，同时保证即使多个提议者的提议之间产生了冲突，那么算法都能进行下去；
66+
2. **接受者（Acceptor）**：也可以叫做投票员（voter），负责对提议者的提议投票，同时需要记住自己的投票历史；
67+
3. **学习者（Learner）**：如果有超过半数接受者就某个提议达成了共识，那么学习者就需要接受这个提议，并就该提议作出运算，然后将运算结果返回给客户端。
68+
69+
![](https://img-blog.csdnimg.cn/20210603145613753.png)
70+
71+
## Multi Paxos 思想
72+
73+
因为兰伯特提到的 Multi-Paxos 思想，缺少代码实现的必要细节(比如怎么选举领导者)，所以在理解上比较难。
74+
75+
⚠️**注意** ： Multi-Paxos 只是一种思想，这种思想的核心就是通过多个 Basic Paxos 实例就一系列值达成共识。
76+
77+
二阶段提交是达成共识常用的方式，Basic Paxos 就是通过二阶段提交的方式来达成共识。Basic Paxos 还支持容错，少于一般的节点出现故障时，集群也能正常工作。
78+
79+
## 参考
80+
81+
- https://zh.wikipedia.org/wiki/Paxos
82+
- 分布式系统中的一致性与共识算法：http://www.xuyasong.com/?p=1970
Collapse file

‎docs/java/basis/images/checked-exception.png‎

Copy file name to clipboard
-1.91 KB
  • Display the source diff
  • Display the rich diff
Loading
Collapse file

‎docs/java/basis/images/image-20211213102222601.png‎

Copy file name to clipboard
-64 Bytes
  • Display the source diff
  • Display the rich diff
Loading
Collapse file

‎docs/java/basis/images/java-se-specifications.png‎

Copy file name to clipboard
-12.2 KB
  • Display the source diff
  • Display the rich diff
Loading
Collapse file

‎docs/java/basis/images/java-value-passing-01.png‎

Copy file name to clipboard
-654 Bytes
  • Display the source diff
  • Display the rich diff
Loading

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.