分布式理论经典论文集合：从一致性到Paxos

5星 · 超过95%的资源需积分: 10 182 浏览量更新于2024-07-24 收藏 1.91MB PDF 举报

"这篇资源是关于分布式理论的一系列论文汇总，涵盖了从历史到现代的分布式系统中的关键概念和算法。主要包括一致性、两阶段提交（2PC）、事务提交、时间顺序、FLP不可能性、拜占庭将军问题、租约机制、Paxos算法及其应用。这些论文对于理解分布式系统的运作原理和一致性问题是至关重要的。" 在这份论文集中，我们可以深入探讨以下几个核心知识点： 1. **一致性**：一致性是分布式系统中保证数据在多个节点间同步的关键概念。它涉及到如何确保所有节点看到的数据状态是一致的，即使在面临网络故障或节点故障的情况下。一致性通常与CAP定理相关，即在分布式系统中无法同时保证一致性、可用性和分区容忍性。 2. **2PC（两阶段提交）**：这是一种经典的分布式事务提交协议，旨在确保跨多个节点的事务原子性。分为准备阶段和提交阶段，但在网络延迟或故障情况下可能会导致阻塞。 3. **事务提交**：事务处理是数据库系统中的重要部分，分布式环境中事务的提交需要解决并发控制和恢复等问题，以确保数据的正确性。 4. **时间、时钟与事件顺序**：Leslie Lamport的这篇文章阐述了在分布式系统中如何定义事件的时间顺序，因为节点间的时钟可能不同步，这对于理解和解决因果关系至关重要。 5. **FLP不可能性**：1983年的FLP（Fischer-Lipton-Paterson）定理证明，在存在网络延迟或故障的分布式系统中，无法保证总是能够达成一致性决策。 6. **拜占庭将军问题**：由Leslie Lamport提出的著名问题，探讨了在不可靠通信环境下，如何确保多组件系统的一致性决策。这个问题的解决方案对后来的容错算法设计产生了深远影响。 7. **租约机制**：1989年提出的租约机制是一种在分布式缓存中实现一致性的方式，通过设定时间限制来管理节点间的协作，防止过期信息的使用。 8. **Paxos算法**：Leslie Lamport在2001年的《Paxos Made Simple》中描述的算法，是解决分布式一致性问题的一种简化方法，广泛应用于构建高可用系统。 9. **Paxos的应用**：文中提到Paxos因Butler W. Lampson的文章而受到关注，并在Google的实际项目如GFS和Chubby中得到应用。 10. **两阶段提交实战**：来自经典书籍的介绍，详细解释了2PC在实际分布式数据库系统中的操作流程和挑战。这个论文集为深入理解分布式系统理论和实践提供了丰富的资源，对于研究和开发分布式应用的专业人士来说是宝贵的参考资料。

必须晚于 Tm。更准确地说，我们需要如下规则：

IR2.(a)

如果事件

代表了进程

发送消息

的事件，那么消息

包含的时间戳

Tm=Ci(a).(b)

在收到消息

后，进程

会设置

的值使得它大于等于它的当前值

并大于

Tm.

在条件 IR2(b)中，我们认为代表消息 m 被接收的事件发生在 Cj 被设置之后{!原文

是：“In IR2(b) we consider the event which represents the receipt of the message m

to occur after the setting of C j. (This is just a notational nuisance, and is irrelevant in

any actual implementation.”这一段应该这样理解，消息 m 被接收与 Cj 被设置是

两个独立的事件，这里只是在概念上定义消息接收事件发生在进程设置 Cj 值之

后，这样的话因为已经设置完 Cj 了，就肯定能保证消息接收事件的 Cj(b)<Ci(a)

即 Tm}。很明显，IR2 保证了条件 C2 的满足。因此，IR1 和 IR2 保证了 Clock Condition

的满足，这样它们就保证了得到的是一个正确的逻辑时钟系统。

Ordering The Events Totally

我们可以使用一个满足 Clock Condition 的时钟系统来获取系统中所有事件的一个

全序关系。我们只是简单地根据事件发生的时间来对它们进行排序。为了打破平

局的情况，我们使用了进程间的任意的一个全序关系“<”。具体来说，我们定义

一个新的关系“=>”如下：假设 a 是进程 Pi 中事件，b 是进程 Pj 中的事件，那

么当且仅当满足如下条件之一时:(1)Ci(a)<Cj(b);(2)Ci(a)=Cj(b)且 Pi<Pj，那么我们就

认为“a=>b”。容易看出这样就定义了一个全序关系，同时 Clock Condition 意味

着：如果 a->b 那么 a=>b。换句话说，关系“=>”是将”happen before”偏序关系

扩展成全序关系的一种方式。

“=>”所依赖的时钟系统并不是唯一的。不同的满足 Clock Condition 的时钟系统

选择将会产生不同的关系“=>”。给定任意一个全序关系“=>”，都会有一个满足

Clock Condition 的时钟系统可以用来产生该关系。只有偏序关系“->”是由系统

中的事件唯一确定的。

能够对事件进行全排序在实现分布式系统时是非常有用的。实际上，实现一个正

确的逻辑时钟系统的原因就是为了获取这样的一个全序关系。我们将会通过解决

如下版本的互斥问题来展示这个事件间全序关系的使用方法。考虑一个由固定进

程集合组成的系统，这些进程需要共享一个资源。同时该资源一次只能由一个进

程使用，因此为避免冲突进程间必须进行同步。我们希望可以找到一个满足如下

三个条件的算法：

(1)已经获得资源授权的进程，必须在资源分配给其他进程之前释放掉它；

(2)资源请求必须按照请求发生的顺序进行授权；

(3)在获得资源授权的所有进程最终释放资源后，所有的资源请求必须都已经被

授权了。

我们假设初始时刻资源只授权给了一个进程。

这些都是非常自然的需求。它们准确地描述了正确的解所需要满足的条件。注意

一下这些条件是如何与事件排序产生联系的。首先条件(2)并没有说明对于两个

concurrently 的事件应该首先为哪一个进行授权。

意识到这个问题的不平凡性是非常重要的。除非进行一些额外的假设，否则使用

一个中央调度进程按照资源请求被收到的顺序来为它们进行授权是不可行的。为

了说明这一点，令 P0 代表该调度进程。假设 P1 发送一个请求给 P0，然后又发

送了一个消息给 P2。一旦收到后面的这个消息，P2 就会发送一个请求给 P0。P2

的请求有可能在 P1 的请求到达 P0 之前就到达了。这样就违背了条件(2)，因为

P2 的请求会首先被授权。{!根据条件(2)，应该按照请求发生的顺序进行，很明显

P1 的请求发生在 P2 请求之前，简单的按照请求被接收的顺序进行授权是很难满

足这个条件的}

为解决该问题，我们实现一个满足了规则 IR1 和 IR2 的时钟系统，同时利用它们

来定义一个所有事件的全序关系“=>”。这样就为所有的资源请求和释放事件提

供了一个全序关系。利用这种顺序关系，就可以比较容易地找到一个解。它只需

要确保每个进程知道所有其他进程的操作。

为简化这个问题，首先我们需要进行一些假设。这些假设不是必需的，但是引入

它们有助于避免陷入细节的讨论中。首先我们假设，对于任意的两个进程 Pi 和

Pj，它们之间传递的消息是按照发送顺序被接收到的。此外，我们还假设所有的

消息最终都会被接收到。(这些假设可以通过引入消息序号和确认机制来消除)。

同时我们假设每个进程都可以直接向其他进程发送消息。

每个进程会维护一个它自己的对其他所有进程都不可见的请求队列。我们假设该

请求队列初始时刻只有一个消息 T0:P0 资源请求，P0 代表初始时刻获得资源授权

的那个进程，T0 小于任意时钟初始值。

算法是由如下 5 个规则定义的。方便起见，每条规则定义的行为会被做为一个独

立事件。

1. 为请求该项资源，进程 Pi 发送一个 Tm:Pi 资源请求消息给其他所有进程，并

将该消息放入自己的请求队列，在这里 Tm 代表了消息的时间戳

2. 当进程 Pj 收到 Tm:Pi 资源请求消息后，将它放到自己的请求队列中，并发送

一个带时间戳的确认消息给 Pi。(注：如果 Pj 已经发送了一个时间戳大于 Tm

的消息，那就可以不发送)

3. 释放该项资源时，进程 Pi 从自己的消息队列中删除所有的 Tm:Pi 资源请求，

同时给其他所有进程发送一个带有时间戳的 Pi 资源释放消息

4. 当进程 Pj 收到 Pi 资源释放消息后，它就从自己的消息队列中删除所有的 Tm:Pi

资源请求

5. 当同时满足如下两个条件时，就将资源分配给进程 Pi：

a) 按照“=>”关系排序后，Tm:Pi 资源请求排在它的请求队列的最前面

b) Pi 已经从所有其他进程都收到了时间戳>Tm 的消息(注：如果 Pi<Pj，那么

Pi 只需要收到一个>=Tm 的消息即可)

需要注意的是，规则 5 中的条件 a),b)都只需要由进程 Pi 自己在本地进行判断。

可以很容易地验证由这些规则所定义的该算法满足上面的条件(1)(2)(3)。首先，

可以看到，规则 5 的条件 b)，加上消息按序接收的假设，就可以保证 Pi 已经收

到了所有排在它的当前请求之前的所有请求。因为只有规则 3 和 4 会从请求队列

中删除消息，因此可以很容易看出条件(1)是满足的。条件(2)可以通过如下事实

得出：“=>”是对偏序关系“->”的扩展。规则 2 保证了在 Pi 发出资源请求后，

规则 5 的条件 b)最终一定会成立。规则 3 和 4 意味着如果获取了资源授权的所有

进程最终释放掉资源后，那么规则 5 的条件 a)最终也一定会成立，这就证明了条

件(3)。

{!重新整理下上面的证明过程，规则 5 的条件 b)+消息按序传输的假设，可以推

出 Pi 已经接收了在它的资源请求之前的那些请求，因为 Pi 已经从其他所有进程

都收到了晚于 Tm 的消息，对于其他进程来说，根据消息按序传输的假设，那些

早于 Tm 的消息肯定也已经被进程 Pi 接收到了。然后又由于规则 3,4 是唯一会从

请求队列中删除消息的地方，就可以得出条件(1)成立。

我们可以这样证明条件 1 的成立：假设条件(1)不成立，则意味着在资源分配给

某进程后，假设该进程为 Pm，还有其他进程未释放该资源，假设为 Pn，那么对

于这个进程来说，意味着它还未释放资源，根据规则 3,4，也就意味着它还未将

该请求从自己的队列中删除，其他进程也还未将其删除。而进程 Pm 之所以能获

取资源，说明它满足了规则 5 的两个条件，但是根据条件 a)说明进程 Pm 的资源

请求是最早的，但是实际上 Pn 的请求要更早，因为它比 Pm 更早获得授权，但

是该请求还未从 Pm 的队列中删除，因此规则 5 的条件 a)就不可能满足，这样就

找到了矛盾的地方。

规则 5 的条件 a),b)保证了最先发出的资源请求必然先获得授权，由此可以推出

条件(2)成立。但是还需要证明的是，这两个条件最终一定会被满足。首先规则 2

保证了规则 5 的条件 b)最终会成立，因为其他进程一定会发出一个晚于 Tm 的消

息，而根据假设消息最终会被收到，因此条件 b)最终一定会成立。规则 3,4 意味

着如果获取资源的进程最终释放了资源，那么规则 5 的条件 a)最终一定会满足，

因为请求是按序被分配的，如果排在前面的资源请求在授权之后会再释放，那么

后面的请求就能被授权，如此循环，最终一定会轮到 Tm:Pi 资源请求。由于规则

5 的条件 a),b)最终一定会被满足，因此对于每个进程来说，它们的资源请求最终

一定会被授权，因此条件(3)就满足了。}

这是一个分布式算法。每个进程各自独立地遵从这些规则，同时没有中央同步进

程或者是中央存储。该方法可以被通用化，来实现分布式的多进程系统所需要的

任意同步机制。同步过程可以通过状态机来描述，该状态机包含一个命令集合 C，

一个可能的状态集合 S，以及一个函数 e：C×S->S。关系 e(C,S)=S’的含义是，在

处于状态 S 的状态机执行命令 C，将会使状态机转移到状态 S’。在我们的例子中，

C 包括所有的 Pi 资源请求和资源释放命令，状态包括一个处于等待状态的请求命

令队列，同时处于队列顶端的那个请求就是要被授权的那个。请求命令的执行将

会将该请求添加到队列末尾，释放命令的执行将会从队列中删除一个命令。

每个进程独立地通过使用所有进程产生的命令来驱动该状态机的执行。所有的进

程通过根据时间戳来对命令进行排序来达到同步(使用关系“=>”)，因此所有进

程将会使用相同的命令序列。当一个进程发现它已经收到了所有时间戳小于等于

T 的命令之后，它就可以执行时间戳为 T 的命令了。具体的算法已经很明了了，

因此我们不再进行描述。

该方法使得我们可以实现分布式系统中任何形式的进程同步需求。但是，该算法

需要所有进程都必须参与其中，同时进程必须要了解所有其他进程产生的命令，

因此只要有一个进程出错，都会使得其他进程无法执行状态机命令，从而导致系

统运行停滞。

错误处理是一个很困难的问题，同时对它进行细节性的讨论已经超出了本篇文章

的范围。只是需要指出的是，failure 这个概念只有在物理时间上下文中才有意义。

如果没有物理时间，就没有办法去区分进程是出错了还是只是处于事件之间的间

歇。用户只能通过系统很长时间都没有响应来判断系统出了问题。在进程或通信

线路出错时也能正常工作的方法，我们将会在[3]中进行描述。

Anomalous Behavior

我们的资源调度算法是根据全序关系“=>”来对请求进行排序的。这就允许下面

这种异常行为(Anomalous Behavior)的发生。考虑一个由相互连接的计算机组成的

全国性系统。假设某人在计算机 A 上产生了一个请求 A，然后他打电话告诉住在

另一个城市里的朋友 B，让它在计算机 B 上产生一个请求 B。对于请求 B 来说很

有可能会获得一个更小的时间戳然后被排在 A 前面。这是有可能发生的，因为系

统没有办法知道 A 实际上发生在 B 之前，因为该信息是基于位于系统外部的消

息的。

让我们更深入地考察下该问题产生的根源。令∮代表所有系统事件组成的集合，

然后我们再引入一个包含了∮中的事件以及所有其他外部事件(比如上面例子中

的打电话)的集合∮’。令->{!注意这个是加粗的->,与前面的->不同}表示∮’中的 happen

before 关系。在上面的例子中，有 A->B,但是 A!->B。很明显一个完全基于∮中的

事件，而对的∮’中的其他事件没有任何联系的算法，是无法保证请求 A 会被排

在请求 B 前面的。

有两种可能的方式可以避免这种异常行为。第一种方式是将关于->顺序的必要信

息显式地引入到系统中。比如在上面的例子中，该用户在产生请求 A 时可以获取

它在系统中的时间戳 T，然后他可以在打电话通知他朋友的时候，告诉他这个时

间戳，然后在他朋友产生请求 B 的时候，告知系统产生一个晚于 T 的时间戳。这

样就将这种异常行为交给用户自己来负责。

第二种方法就是构造一个满足如下条件的时钟系统：

Strong Clock Condition.对于∮’中的任意两个事件，如果 a->b，那么 c(a)<c(b)。

该条件要比之前的 Clock Condition 强，因为->比->要强。通常我们的逻辑时钟无

法满足该条件。

如果我们令∮’表示物理时空中真实事件的集合，令->代表由狭义相对论所定义的

事件偏序关系。在我们所在的宇宙中，是有可能构造出一个由相互之间独立运行

的多个物理时钟构成的满足 Strong Clock Condition 的时钟系统的。因此我们可以

使用物理时钟来避免这种异常行为。下面我们就将注意力转移到这类时钟之上。

Physical Clocks

现在我们将物理时间引入到我们的时空图中，令 Ci(t)表示在物理时间 t 所读取到

的时钟 Ci 的值(注：我们现在假设是在一个牛顿绝对时空中。如果时钟的相对运

动或者重力效应无法忽略，那么 Ci(t)必须要把实际读取的时间转换成选定的时间

坐标系中的时间)。为了方便数学表述，我们假设时钟是以连续而非离散的滴答

走动的。更准确地说，我们假设 Ci(t)是一个在时间 t 上的连续的可微分函数，除

了那些时钟被重置时的孤立突变点之外。dCi(t)/dt 代表了时钟在时间 t 时的速率。

如果将时钟 Ci 作为一个真实的物理时钟，那么它还必须以一个近似正确的速率

来运行。也就是说，必须要保对于所有的 t，dCi(t)/dt≈1。更准确地说，我们要

保证满足如下条件：

PC1.存在一个常数 k，对于所有的 i：| dCi(t)/dt -1|<k

对于典型的由晶体控制的时钟来说，k<=10^-6.

如果时钟只是单单地以近似正确的速率运行是不够的。它们还必须是同步的，即

对于所有的 i,j,t 来说，Ci(t)≈Cj(t)。更准确地说，必须存在一个足够小的常数 e，

满足如下条件：

PC2.对于所有的 i,j：| Ci(t)-Cj(t)|<e.

如果我们让图 2 中的垂直距离来表示物理时间的话，那么 PC2 意味着单个滴答线

上的高度差异要小于 e。

由于两个不同的时钟永远都不会以相同的速率走动，这意味着它们之间的偏差会

越来越大。因此我们必须要设计一种算法来保证 PC2 总是成立。但是，首先我们

来看一下 k 和 e 要多小才能避免异常行为。我们必须要保证系统∮’中的所有相

关事件都满足 Strong Clock Condition。首先我们假设我们的时钟满足普通的 Clock

Condition，那么只需要保证∮’中那些不满足 a->b 的事件满足 Strong Clock

Condition。因此我们只需要考虑发生在不同进程中的事件。

令 u 表示满足如下条件的值：如果事件 a 发生在物理时间 t，同时 b 是发生在另

一个进程中的满足 a->b 事件，那么 b 肯定发生在物理时间 t+u 之后。换句话说，

u 需要小于进程间消息传输的最短时间。我们可以用进程间的距离除以光速的值

作为 u 的值。当然，这取决于∮’中消息是如何传输的，u 的值也可以很大。

剩余157页未读，继续阅读

青鸟闲居

粉丝: 0
资源: 3

分布式理论经典论文集合：从一致性到Paxos

分布式系统理论基石：Google三驾马车论文解析

论文研究-分布式环境下基于信誉和群组的信任模型研究 .pdf

读完这100篇论文 就能成大数据高手(论文汇总前40篇)

大规模分布式并行信息检索技术

PayPal高级工程总监：读完这100篇论文 就能成大数据高手（论文汇总51-100篇）

2019-2021数学中国网络挑战赛优秀论文-2019-2021数学中国网络挑战赛优秀论文汇总-特等奖32738B.pdf

2019-2021数学中国网络挑战赛优秀论文-2019-2021数学中国网络挑战赛优秀论文汇总-特等奖34768B.pdf

基于双重权值优化的分布式定位算法.pdf

基于分布式的K-prototypes算法设计.pdf

基于分布式的频繁闭合模式挖掘算法.pdf

最新资源

读完这100篇论文就能成大数据高手(论文汇总前40篇)

PayPal高级工程总监：读完这100篇论文就能成大数据高手（论文汇总51-100篇）