分布式系统

系统管理员 2023-06-04 02:46 21阅读 0赞

# [初识分布式系统][Link 1] #

2015-12-02 分类：[分布式][Link 2] 阅读(17583) 评论(3)

> 随着大型网站的各种高并发访问、海量数据处理等场景越来越多，如何实现网站的高可用、易伸缩、可扩展、安全等目标就显得越来越重要。为了解决这样一系列问题，大型网站的架构也在不断发展。提高大型网站的高可用架构，不得不提的就是分布式。本文主要简单介绍了分布式系统的概念、分布式系统的特点、常用的分布式方案以及分布式和集群的区别等。

### 一、集中式系统 ###

在学习分布式之前，先了解一下与之相对应的集中式系统是什么样的。

集中式系统用一句话概括就是：一个主机带多个终端。终端没有数据处理能力，仅负责数据的录入和输出。而运算、存储等全部在主机上进行。现在的银行系统，大部分都是这种集中式的系统，此外，在大型企业、科研单位、军队、政府等也有分布。集中式系统，主要流行于上个世纪。

集中式系统的最大的特点就是部署结构非常简单，底层一般采用从IBM、HP等厂商购买到的昂贵的大型主机。因此无需考虑如何对服务进行多节点的部署，也就不用考虑各节点之间的分布式协作问题。但是，由于采用单机部署。很可能带来系统大而复杂、难于维护、发生单点故障（单个点发生故障的时候会波及到整个系统或者网络，从而导致整个系统或者网络的瘫痪）、扩展性差等问题。

### 二、分布式系统(distributed system) ###

在《分布式系统概念与设计》一书中，对分布式系统做了如下定义：

> 分布式系统是一个硬件或软件组件分布在不同的网络计算机上，彼此之间仅仅通过消息传递进行通信和协调的系统

简单来说就是一群独立计算机集合共同对外提供服务，但是对于系统的用户来说，就像是一台计算机在提供服务一样。分布式意味着可以采用更多的普通计算机（相对于昂贵的大型机）组成分布式集群对外提供服务。计算机越多，CPU、内存、存储资源等也就越多，能够处理的并发访问量也就越大。

从分布式系统的概念中我们知道，各个主机之间通信和协调主要通过网络进行，所以，分布式系统中的计算机在空间上几乎没有任何限制，这些计算机可能被放在不同的机柜上，也可能被部署在不同的机房中，还可能在不同的城市中，对于大型的网站甚至可能分布在不同的国家和地区。但是，无论空间上如何分布，一个标准的分布式系统应该具有以下几个主要特征：

#### 分布性 ####

> 分布式系统中的多台计算机之间在空间位置上可以随意分布，系统中的多台计算机之间没有主、从之分，即没有控制整个系统的主机，也没有受控的从机。

#### 透明性 ####

> 系统资源被所有计算机共享。每台计算机的用户不仅可以使用本机的资源，还可以使用本分布式系统中其他计算机的资源(包括CPU、文件、打印机等)。

#### 同一性 ####

> 系统中的若干台计算机可以互相协作来完成一个共同的任务，或者说一个程序可以分布在几台计算机上并行地运行。

#### 通信性 ####

> 系统中任意两台计算机都可以通过通信来交换信息。

和集中式系统相比，分布式系统的性价比更高、处理能力更强、可靠性更高、也有很好的扩展性。但是，分布式在解决了网站的高并发问题的同时也带来了一些其他问题。首先，分布式的必要条件就是网络，这可能对性能甚至服务能力造成一定的影响。其次，一个集群中的服务器数量越多，服务器宕机的概率也就越大。另外，由于服务在集群中分布是部署，用户的请求只会落到其中一台机器上，所以，一旦处理不好就很容易产生数据一致性问题。

### 常用的分布式方案 ###

#### 分布式应用和服务 ####

> 将应用和服务进行分层和分割，然后将应用和服务模块进行分布式部署。这样做不仅可以提高并发访问能力、减少数据库连接和资源消耗，还能使不同应用复用共同的服务，使业务易于扩展。

#### 分布式静态资源 ####

> 对网站的静态资源如JS、CSS、图片等资源进行分布式部署可以减轻应用服务器的负载压力，提高访问速度。

#### 分布式数据和存储 ####

> 大型网站常常需要处理海量数据，单台计算机往往无法提供足够的内存空间，可以对这些数据进行分布式存储。

#### 分布式计算 ####

> 随着计算技术的发展，有些应用需要非常巨大的计算能力才能完成，如果采用集中式计算，需要耗费相当长的时间来完成。分布式计算将该应用分解成许多小的部分，分配给多台计算机进行处理。这样可以节约整体计算时间，大大提高计算效率。

### 分布式与集群 ###

分布式（distributed）是指在多台不同的服务器中部署不同的服务模块，通过远程调用协同工作，对外提供服务。

集群（cluster）是指在多台不同的服务器中部署相同应用或服务模块，构成一个集群，通过负载均衡设备对外提供服务。

# [关于分布式一致性的探究][Link 3] #

2015-12-03 分类：[分布式][Link 2] 阅读(21725) 评论(2)

> 随着大型网站的各种高并发访问、海量数据处理等场景越来越多，如何实现网站的高可用、易伸缩、可扩展、安全等目标就显得越来越重要。为了解决这样一系列问题，大型网站的架构也在不断发展。提高大型网站的高可用架构，不得不提的就是分布式。在[初识分布式系统][Link 4]一文中简单介绍了分布式的基本概念，本文将在上篇文章的基础上继续学习分布式的一致性问题。主要介绍分布式一致性的基本概念、重要性、一致性模型等。

## 一致性的重要性 ##

分布式领域[CAP理论][CAP]告诉我们，任何一个分布式系统都无法同时满足Consistency(一致性),Availability(可用性), Partition tolerance(分区容错性) 这三个基本需求。最多只能满足其中两项。 但是，一个分布式系统无论在CAP三者之间如何权衡，都无法彻底放弃一致性（Consistency），如果真的放弃一致性，那么就说明这个系统中的数据根本不可信，数据也就没有意义，那么这个系统也就没有任何价值可言。所以，无论如何，分布式系统的一致性问题都需要重点关注。([分布式系统的CAP理论][CAP]、[分布式系统的BASE理论][BASE])

> 这里先简单提一下，由于一个分布式系统不可能放弃一致性，那么为什么有的架构师还说在某些场景中可以牺牲一致性呢？通常这里说的放弃一致性指的是放弃数据的强一致性（后文介绍什么是强一致性）。

通常情况下，我们所说的分布式一致性问题通常指的是数据一致性问题。那么我们就先来了解一下什么是数据一致性。

## 数据一致性 ##

数据一致性其实是数据库系统中的概念。我们可以简单的把一致性理解为正确性或者完整性，那么数据一致性通常指关联数据之间的逻辑关系是否正确和完整。我们知道，在数据库系统中通常用事务（访问并可能更新数据库中各种数据项的一个程序执行单元）来保证数据的一致性和完整性。而在分布式系统中，数据一致性往往指的是由于数据的复制，不同数据节点中的数据内容是否完整并且相同。

比如在集中式系统中，有一些关键的配置信息，可以直接保存在服务器的内存中，但是在分布式系统中，如何保存这些配置信息，又如何保证所有机器上的配置信息都保持一致，又如何保证修改一个配置能够把这次修改同步到所有机器中呢？

再比如，在集中式系统中，进行一个同步操作要写同一个数据的时候，可以直接使用事务+锁来管理保证数据的ACID。但是，在分布式系统中如何保证多台机器不会同时写同一条数据呢？

除了上面提到的同一个数据的一致性，还有一种情况也可以叫做数据的一致性：比如我们在电商网站下单，需要经历扣减库存、扣减红包、扣减折扣券等一系列操作。如果库存库存扣减成功，但是红包和折扣券扣减失败的话，也可以说是数据没有保证一致性。

如何保证数据的一致性，是分布式系统中必须面对的问题。

## 为什么会有数据一致性问题 ##

在[初识分布式系统][Link 4]中我们介绍过，虽然分布式系统有着诸多优点，但是由于采用多机器进行分布式部署的方式提供服务，必然存在着数据的复制（如数据库的异地容灾，多地部署）。分布式系统的数据复制需求主要来源于以下两个原因：

> 可用性。将数据复制到分布式部署的多台机器中，可以消除单点故障。防止系统由于某台（些）机器宕机导致的不可用。
> 
> 性能。通过负载均衡技术，能够让分布在不同地方的数据副本全都对外提供服务。有效提高系统性能。

分布式系统为了提升可用性和性能，会通过复制技术来进行数据同步。复制机制的目的是为了保证数据的一致性。但是数据复制面临的主要难题也是如何保证多个副本之间的数据一致性。在分布式系统引入复制机制后，不同的数据节点之间由于网络延时等原因很容易产生数据不一致的情况。

如果上面提到的数据复制场景你不是很熟悉的话，下面这个例子你肯定遇到过。就是现在很多网站都是微服务化的，一个网站被垂直拆分成多个功能模块。各模块之间独立部署。模块间通过RPC或者HTTP交互。由于这种RPC或者HTTP的交互可能存在网络延迟导致超时的情况。甚至被调用方也有可能执行出错等情况，这时候就可能导致数据不一致。

比如下单操作要依次扣减红包、扣减折扣券、扣减库存。在下单应用的执行过程中，调用红包系统扣减红包成功了，但是再调用折扣券系统扣减折扣券的时候网络超时了。这时候下单应用根本不知道折扣券系统到底有没有执行成功。这时候他就需要一些机制来决定是要回滚红包的扣减，还是继续执行库存的扣减。这种机制，其实就是数据一致性的解决方案了。

由于应用分布式部署，就无法通过数据库事务保证多个写操作的原子性。一旦某个操作失败，其他操作如果不回滚的话就会发生数据不一致问题。

因此，如何能既保证数据一致性，又保证系统的性能，是每一个分布式系统都需要重点考虑和权衡的。一致性模型可以在做这些权衡的时候给我们很多借鉴和思考。

## 一致性模型 ##

### 强一致性 ###

当更新操作完成之后，任何多个后续进程或者线程的访问都会返回最新的更新过的值。这种是对用户最友好的，就是用户上一次写什么，下一次就保证能读到什么。

但是这种实现对性能影响较大，因为这意味着，只要上次的操作没有处理完，就不能让用户读取数据。

### 弱一致性 ###

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

### 最终一致性 ###

弱一致性的特定形式。系统保证在没有后续更新的前提下，系统最终返回上一次更新操作的值。在没有故障发生的前提下，不一致窗口的时间主要受通信延迟，系统负载和复制副本的个数影响。DNS是一个典型的最终一致性系统。

### 最终一致性模型的变种 ###

> 因果一致性：如果A进程在更新之后向B进程通知更新的完成，那么B的访问操作将会返回更新的值。如果没有因果关系的C进程将会遵循最终一致性的规则。
> 
> 读己所写一致性：因果一致性的特定形式。一个进程总可以读到自己更新的数据。
> 
> 会话一致性：读己所写一致性的特定形式。进程在访问存储系统同一个会话内，系统保证该进程读己之所写。
> 
> 单调读一致性：如果一个进程已经读取到一个特定值，那么该进程不会读取到该值以前的任何值。
> 
> 单调写一致性：系统保证对同一个进程的写操作串行化。

上述最终一致性的不同方式可以进行组合，例如单调读一致性和读己之所写一致性就可以组合实现。并且从实践的角度来看，这两者的组合，读取自己更新的数据，和一旦读取到最新的版本不会再读取旧版本，对于此架构上的程序开发来说，会少很多额外的烦恼。

为了解决分布式的一致性问题，在长期的研究探索过程中，涌现出了一大批经典的一致性协议和算法，其中比较著名的有[二阶段提交协议，三阶段提交协议][Link 5]和Paxos算法。 下一篇文章将介绍这些和[分布式一致性相关的协议][Link 5]和算法。

# [分布式系统的CAP理论][CAP 1] #

2015-12-03 分类：[分布式][Link 2] 阅读(34282) 评论(11)

> 2000年7月，加州大学伯克利分校的Eric Brewer教授在ACM PODC会议上提出CAP猜想。2年后，麻省理工学院的Seth Gilbert和Nancy Lynch从理论上证明了CAP。之后，CAP理论正式成为分布式计算领域的公认定理。

无论你是一个系统架构师，还是一个普通开发，当你开发或者设计一个分布式系统的时候，CAP理论是无论如何也绕不过去的。本文就来介绍一下到底什么是CAP理论，如何证明CAP理论，以及CAP的权衡问题。

## CAP理论概述 ##

CAP理论：一个分布式系统最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三项中的两项。

![Teorema-CAP-2][]

> 读者需要注意的的是，CAP理论中的CA和数据库事务中ACID的CA并完全是同一回事儿。两者之中的A都是C都是一致性(Consistency)。CAP中的A指的是可用性（Availability），而ACID中的A指的是原子性（Atomicity)，切勿混为一谈。

## CAP的定义 ##

### Consistency 一致性 ###

一致性指“`all nodes see the same data at the same time`”，即更新操作成功并返回客户端完成后，所有节点在同一时间的数据完全一致，所以，一致性，说的就是数据一致性。[分布式的一致性][Link 6]

对于一致性，可以分为从客户端和服务端两个不同的视角。从客户端来看，一致性主要指的是多并发访问时更新过的数据如何获取的问题。从服务端来看，则是更新如何复制分布到整个系统，以保证数据最终一致。

一致性是因为有并发读写才有的问题，因此在理解一致性的问题时，一定要注意结合考虑并发读写的场景。

从客户端角度，多进程并发访问时，更新过的数据在不同进程如何获取的不同策略，决定了不同的一致性。

三种一致性策略

对于关系型数据库，要求更新过的数据能被后续的访问都能看到，这是强一致性。

如果能容忍后续的部分或者全部访问不到，则是弱一致性。

如果经过一段时间后要求能访问到更新后的数据，则是最终一致性。

CAP中说，不可能同时满足的这个一致性指的是强一致性。

### Availability 可用性 ###

可用性指“`Reads and writes always succeed`”，即服务一直可用，而且是正常响应时间。

对于一个可用性的分布式系统，每一个非故障的节点必须对每一个请求作出响应。所以，一般我们在衡量一个系统的可用性的时候，都是通过停机时间来计算的。

<table> 
 <thead> 
  <tr> 
   <th>可用性分类</th> 
   <th>可用水平（%）</th> 
   <th>年可容忍停机时间</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>容错可用性</td> 
   <td>99.9999</td> 
   <td>&lt;1 min</td> 
  </tr> 
  <tr> 
   <td>极高可用性</td> 
   <td>99.999</td> 
   <td>&lt;5 min</td> 
  </tr> 
  <tr> 
   <td>具有故障自动恢复能力的可用性</td> 
   <td>99.99</td> 
   <td>&lt;53 min</td> 
  </tr> 
  <tr> 
   <td>高可用性</td> 
   <td>99.9</td> 
   <td>&lt;8.8h</td> 
  </tr> 
  <tr> 
   <td>商品可用性</td> 
   <td>99</td> 
   <td>&lt;43.8 min</td> 
  </tr> 
 </tbody> 
</table>

通常我们描述一个系统的可用性时，我们说淘宝的系统可用性可以达到5个9，意思就是说他的可用水平是99.999%，即全年停机时间不超过 `(1-0.99999)*365*24*60 = 5.256 min`，这是一个极高的要求。

好的可用性主要是指系统能够很好的为用户服务，不出现用户操作失败或者访问超时等用户体验不好的情况。一个分布式系统，上下游设计很多系统如负载均衡、WEB服务器、应用代码、数据库服务器等，任何一个节点的不稳定都可以影响可用性。

### Partition Tolerance分区容错性 ###

分区容错性指“`the system continues to operate despite arbitrary message loss or failure of part of the system`”，即分布式系统在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务。

分区容错性和扩展性紧密相关。在分布式应用中，可能因为一些分布式的原因导致系统无法正常运转。好的分区容错性要求能够使应用虽然是一个分布式系统，而看上去却好像是在一个可以运转正常的整体。比如现在的分布式系统中有某一个或者几个机器宕掉了，其他剩下的机器还能够正常运转满足系统需求，或者是机器之间有网络异常，将分布式系统分隔未独立的几个部分，各个部分还能维持分布式系统的运作，这样就具有好的分区容错性。

简单点说，就是在网络中断，消息丢失的情况下，系统如果还能正常工作，就是有比较好的分区容错性。

## CAP的证明 ##

![intro\_thumb][intro_thumb]

如上图，是我们证明CAP的基本场景，网络中有两个节点N1和N2，可以简单的理解N1和N2分别是两台计算机，他们之间网络可以连通，N1中有一个应用程序A，和一个数据库V，N2也有一个应用程序B2和一个数据库V。现在，A和B是分布式系统的两个部分，V是分布式系统的数据存储的两个子数据库。

在满足一致性的时候，N1和N2中的数据是一样的，V0=V0。在满足可用性的时候，用户不管是请求N1或者N2，都会得到立即响应。在满足分区容错性的情况下，N1和N2有任何一方宕机，或者网络不通的时候，都不会影响N1和N2彼此之间的正常运作。

![scenario1\_thumb][scenario1_thumb]

如上图，是分布式系统正常运转的流程，用户向N1机器请求数据更新，程序A更新数据库Vo为V1，分布式系统将数据进行同步操作M，将V1同步的N2中V0，使得N2中的数据V0也更新为V1，N2中的数据再响应N2的请求。

这里，可以定义N1和N2的数据库V之间的数据是否一样为一致性；外部对N1和N2的请求响应为可用行；N1和N2之间的网络环境为分区容错性。这是正常运作的场景，也是理想的场景，然而现实是残酷的，当错误发生的时候，一致性和可用性还有分区容错性，是否能同时满足，还是说要进行取舍呢？

作为一个分布式系统，它和单机系统的最大区别，就在于网络，现在假设一种极端情况，N1和N2之间的网络断开了，我们要支持这种网络异常，相当于要满足分区容错性，能不能同时满足一致性和响应性呢？还是说要对他们进行取舍。

![scenario2\_thumb][scenario2_thumb]

假设在N1和N2之间网络断开的时候，有用户向N1发送数据更新请求，那N1中的数据V0将被更新为V1，由于网络是断开的，所以分布式系统同步操作M，所以N2中的数据依旧是V0；这个时候，有用户向N2发送数据读取请求，由于数据还没有进行同步，应用程序没办法立即给用户返回最新的数据V1，怎么办呢？

有二种选择，第一，牺牲数据一致性，保证可用性。响应旧的数据V0给用户；

第二，牺牲可用性，保证数据一致性。阻塞等待，直到网络连接恢复，数据更新操作M完成之后，再给用户响应最新的数据V1。

这个过程，证明了要满足分区容错性的分布式系统，只能在一致性和可用性两者中，选择其中一个。

## CAP权衡 ##

通过CAP理论及前面的证明，我们知道无法同时满足一致性、可用性和分区容错性这三个特性，那要舍弃哪个呢？

我们分三种情况来阐述一下。

### CA without P ###

这种情况在分布式系统中几乎是不存在的。首先在分布式环境下，网络分区是一个自然的事实。因为分区是必然的，所以如果舍弃P，意味着要舍弃分布式系统。那也就没有必要再讨论CAP理论了。这也是为什么在前面的CAP证明中，我们以系统满足P为前提论述了无法同时满足C和A。

比如我们熟知的关系型数据库，如My Sql和Oracle就是保证了可用性和数据一致性，但是他并不是个分布式系统。一旦关系型数据库要考虑主备同步、集群部署等就必须要把P也考虑进来。

其实，在CAP理论中。C，A，P三者并不是平等的，CAP之父在《Spanner，真时，CAP理论》一文中写到：

> 如果说Spanner真有什么特别之处，那就是谷歌的广域网。Google通过建立私有网络以及强大的网络工程能力来保证P，在多年运营改进的基础上，在生产环境中可以最大程度的减少分区发生，从而实现高可用性。

从Google的经验中可以得到的结论是，无法通过降低CA来提升P。要想提升系统的分区容错性，需要通过提升基础设施的稳定性来保障。

所以，对于一个分布式系统来说。P是一个基本要求，CAP三者中，只能在CA两者之间做权衡，并且要想尽办法提升P。

### CP without A ###

如果一个分布式系统不要求强的可用性，即容许系统停机或者长时间无响应的话，就可以在CAP三者中保障CP而舍弃A。

一个保证了CP而一个舍弃了A的分布式系统，一旦发生网络故障或者消息丢失等情况，就要牺牲用户的体验，等待所有数据全部一致了之后再让用户访问系统。

设计成CP的系统其实也不少，其中最典型的就是很多分布式数据库，他们都是设计成CP的。在发生极端情况时，优先保证数据的强一致性，代价就是舍弃系统的可用性。如Redis、HBase等，还有分布式系统中常用的Zookeeper也是在CAP三者之中选择优先保证CP的。

无论是像Redis、HBase这种分布式存储系统，还是像Zookeeper这种分布式协调组件。数据的一致性是他们最最基本的要求。一个连数据一致性都保证不了的分布式存储要他有何用？

在我的[Zookeeper介绍（二）——Zookeeper概述][Zookeeper_Zookeeper]一文中其实介绍过zk关于CAP的思考，这里再简单回顾一下：

ZooKeeper是个CP（一致性+分区容错性）的，即任何时刻对ZooKeeper的访问请求能得到一致的数据结果，同时系统对网络分割具备容错性。但是它不能保证每次服务请求的可用性，也就是在极端环境下，ZooKeeper可能会丢弃一些请求，消费者程序需要重新请求才能获得结果。ZooKeeper是分布式协调服务，它的职责是保证数据在其管辖下的所有服务之间保持同步、一致。所以就不难理解为什么ZooKeeper被设计成CP而不是AP特性的了。

### AP wihtout C ###

要高可用并允许分区，则需放弃一致性。一旦网络问题发生，节点之间可能会失去联系。为了保证高可用，需要在用户访问时可以马上得到返回，则每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。

这种舍弃强一致性而保证系统的分区容错性和可用性的场景和案例非常多。前面我们介绍可用性的时候说到过，很多系统在可用性方面会做很多事情来保证系统的全年可用性可以达到N个9，所以，对于很多业务系统来说，比如淘宝的购物，12306的买票。都是在可用性和一致性之间舍弃了一致性而选择可用性。

你在12306买票的时候肯定遇到过这种场景，当你购买的时候提示你是有票的（但是可能实际已经没票了），你也正常的去输入验证码，下单了。但是过了一会系统提示你下单失败，余票不足。这其实就是先在可用性方面保证系统可以正常的服务，然后在数据的一致性方面做了些牺牲，会影响一些用户体验，但是也不至于造成用户流程的严重阻塞。

但是，我们说很多网站牺牲了一致性，选择了可用性，这其实也不准确的。就比如上面的买票的例子，其实舍弃的只是强一致性。退而求其次保证了最终一致性。也就是说，虽然下单的瞬间，关于车票的库存可能存在数据不一致的情况，但是过了一段时间，还是要保证最终一致性的。

对于多数大型互联网应用的场景，主机众多、部署分散，而且现在的集群规模越来越大，所以节点故障、网络故障是常态，而且要保证服务可用性达到N个9，即保证P和A，舍弃C（退而求其次保证最终一致性）。虽然某些地方会影响客户体验，但没达到造成用户流程的严重程度。

### 适合的才是最好的 ###

上面介绍了如何CAP中权衡及取舍以及典型的案例。孰优孰略，没有定论，只能根据场景定夺，适合的才是最好的。

对于涉及到钱财这样不能有一丝让步的场景，C必须保证。网络发生故障宁可停止服务，这是保证CP，舍弃A。比如前几年支付宝光缆被挖断的事件，在网络出现故障的时候，支付宝就在可用性和数据一致性之间选择了数据一致性，用户感受到的是支付宝系统长时间宕机，但是其实背后是无数的工程师在恢复数据，保证数数据的一致性。

对于其他场景，比较普遍的做法是选择可用性和分区容错性，舍弃强一致性，退而求其次使用最终一致性来保证数据的安全。这其实是分布式领域的另外一个理论——BASE理论。我们下一篇文章再来介绍。

## 总结 ##

无论你是一个架构师，还是一个普通开发，在设计或开发分布式系统的时候，不可避免的要在CAP中做权衡。需要根据自己的系统的实际情况，选择最适合自己的方案。

## 参考资料： ##

[CAP和BASE理论][CAP_BASE]

[CAP原理的证明][CAP 2]

[一文带你重新审视CAP理论与分布式系统设计][CAP 3]

## 拓展阅读： ##

[CAP理论][CAP 4]

# [分布式系统的BASE理论][BASE 1] #

2015-12-03 分类：[分布式][Link 2] 阅读(15906) 评论(0)

## BASE理论 ##

> eBay的架构师Dan Pritchett源于对大规模分布式系统的实践总结，在ACM上发表文章提出BASE理论，BASE理论是对CAP理论的延伸，核心思想是即使无法做到强一致性（Strong Consistency，[CAP][]的一致性就是强一致性），但应用可以采用适合的方式达到最终一致性（Eventual Consitency）。

BASE是指基本可用（Basically Available）、软状态（ Soft State）、最终一致性（ Eventual Consistency）。

### 基本可用（Basically Available） ###

基本可用是指分布式系统在出现故障的时候，允许损失部分可用性，即保证核心可用。

电商大促时，为了应对访问量激增，部分用户可能会被引导到降级页面，服务层也可能只提供降级服务。这就是损失部分可用性的体现。

### 软状态（ Soft State） ###

软状态是指允许系统存在中间状态，而该中间状态不会影响系统整体可用性。分布式存储中一般一份数据至少会有三个副本，允许不同节点间副本同步的延时就是软状态的体现。mysql replication的异步复制也是一种体现。

### 最终一致性（ Eventual Consistency） ###

最终一致性是指系统中的所有数据副本经过一定时间后，最终能够达到一致的状态。弱一致性和强一致性相反，最终一致性是弱一致性的一种特殊情况。

## ACID和BASE的区别与联系 ##

ACID是传统数据库常用的设计理念，追求强一致性模型。BASE支持的是大型分布式系统，提出通过牺牲强一致性获得高可用性。

ACID和BASE代表了两种截然相反的设计哲学

在分布式系统设计的场景中，系统组件对一致性要求是不同的，因此ACID和BASE又会结合使用。

## 参考资料 ##

[CAP和BASE理论][CAP_BASE 1]

# [关于分布式事务、两阶段提交协议、三阶提交协议][Link 7] #

2015-12-05 分类：[分布式][Link 2] 阅读(47537) 评论(7)

> 随着大型网站的各种高并发访问、海量数据处理等场景越来越多，如何实现网站的高可用、易伸缩、可扩展、安全等目标就显得越来越重要。为了解决这样一系列问题，大型网站的架构也在不断发展。提高大型网站的高可用架构，不得不提的就是分布式。在[分布式一致性][Link 6]一文中主要介绍了分布式系统中存在的一致性问题。本文将简单介绍如何有效的解决分布式的一致性问题,其中包括什么是分布式事务，二阶段提交和三阶段提交。

## 分布式一致性回顾 ##

在分布式系统中，为了保证数据的高可用，通常，我们会将数据保留多个副本(replica)，这些副本会放置在不同的物理的机器上。为了对用户提供正确的增\\删\\改\\差等语义，我们需要保证这些放置在不同物理机器上的副本是一致的。

为了解决这种分布式一致性问题，前人在性能和数据一致性的反反复复权衡过程中总结了许多典型的协议和算法。其中比较著名的有二阶提交协议（Two Phase Commitment Protocol）、三阶提交协议（Three Phase Commitment Protocol）和Paxos算法。

## 分布式事务 ##

> 分布式事务是指会涉及到操作多个数据库的事务。其实就是将对同一库事务的概念扩大到了对多个库的事务。目的是为了保证分布式系统中的数据一致性。分布式事务处理的关键是必须有一种方法可以知道事务在任何地方所做的所有动作，提交或回滚事务的决定必须产生统一的结果（全部提交或全部回滚）

在分布式系统中，各个节点之间在物理上相互独立，通过网络进行沟通和协调。由于存在事务机制，可以保证每个独立节点上的数据操作可以满足ACID。但是，相互独立的节点之间无法准确的知道其他节点中的事务执行情况。所以从理论上讲，两台机器理论上无法达到一致的状态。如果想让分布式部署的多台机器中的数据保持一致性，那么就要保证在所有节点的数据写操作，要不全部都执行，要么全部的都不执行。但是，一台机器在执行本地事务的时候无法知道其他机器中的本地事务的执行结果。所以他也就不知道本次事务到底应该commit还是 roolback。所以，常规的解决办法就是引入一个“协调者”的组件来统一调度所有分布式节点的执行。

## XA规范 ##

X/Open 组织（即现在的 Open Group ）定义了分布式事务处理模型。 X/Open DTP 模型（ 1994 ）包括应用程序（ AP ）、事务管理器（ TM ）、资源管理器（ RM ）、通信资源管理器（ CRM ）四部分。一般，常见的事务管理器（ TM ）是交易中间件，常见的资源管理器（ RM ）是数据库，常见的通信资源管理器（ CRM ）是消息中间件。    通常把一个数据库内部的事务处理，如对多个表的操作，作为本地事务看待。数据库的事务处理对象是本地事务，而分布式事务处理的对象是全局事务。   所谓全局事务，是指分布式事务处理环境中，多个数据库可能需要共同完成一个工作，这个工作即是一个全局事务，例如，一个事务中可能更新几个不同的数据库。对数据库的操作发生在系统的各处但必须全部被提交或回滚。此时一个数据库对自己内部所做操作的提交不仅依赖本身操作是否成功，还要依赖与全局事务相关的其它数据库的操作是否成功，如果任一数据库的任一操作失败，则参与此事务的所有数据库所做的所有操作都必须回滚。     一般情况下，某一数据库无法知道其它数据库在做什么，因此，在一个 DTP 环境中，交易中间件是必需的，由它通知和协调相关数据库的提交或回滚。而一个数据库只将其自己所做的操作（可恢复）影射到全局事务中。

> XA 就是 X/Open DTP 定义的交易中间件与数据库之间的接口规范（即接口函数），交易中间件用它来通知数据库事务的开始、结束以及提交、回滚等。 XA 接口函数由数据库厂商提供。

二阶提交协议和三阶提交协议就是根据这一思想衍生出来的。可以说二阶段提交其实就是实现XA分布式事务的关键(确切地说：两阶段提交主要保证了分布式事务的原子性：即所有结点要么全做要么全不做)

## 2PC ##

> 二阶段提交(Two-phaseCommit)是指，在计算机网络以及数据库领域内，为了使基于分布式系统架构下的所有节点在进行事务提交时保持一致性而设计的一种算法(Algorithm)。通常，二阶段提交也被称为是一种协议(Protocol))。在分布式系统中，每个节点虽然可以知晓自己的操作时成功或者失败，却无法知道其他节点的操作的成功或失败。当一个事务跨越多个节点时，为了保持事务的ACID特性，需要引入一个作为协调者的组件来统一掌控所有节点(称作参与者)的操作结果并最终指示这些节点是否要把操作结果进行真正的提交(比如将更新后的数据写入磁盘等等)。因此，二阶段提交的算法思路可以概括为：参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。

所谓的两个阶段是指：第一阶段：准备阶段(投票阶段)和第二阶段：提交阶段（执行阶段）。

### 准备阶段 ###

事务协调者(事务管理器)给每个参与者(资源管理器)发送Prepare消息，每个参与者要么直接返回失败(如权限验证失败)，要么在本地执行事务，写本地的redo和undo日志，但不提交，到达一种“万事俱备，只欠东风”的状态。

可以进一步将准备阶段分为以下三个步骤：

> 1）协调者节点向所有参与者节点询问是否可以执行提交操作(vote)，并开始等待各参与者节点的响应。
> 
> 2）参与者节点执行询问发起为止的所有事务操作，并将Undo信息和Redo信息写入日志。（注意：若成功这里其实每个参与者已经执行了事务操作）
> 
> 3）各参与者节点响应协调者节点发起的询问。如果参与者节点的事务操作实际执行成功，则它返回一个”同意”消息；如果参与者节点的事务操作实际执行失败，则它返回一个”中止”消息。

### 提交阶段 ###

如果协调者收到了参与者的失败消息或者超时，直接给每个参与者发送回滚(Rollback)消息；否则，发送提交(Commit)消息；参与者根据协调者的指令执行提交或者回滚操作，释放所有事务处理过程中使用的锁资源。(注意:必须在最后阶段释放锁资源)

接下来分两种情况分别讨论提交阶段的过程。

当协调者节点从所有参与者节点获得的相应消息都为”同意”时:

[![success][]][success]

> 1）协调者节点向所有参与者节点发出”正式提交(commit)”的请求。
> 
> 2）参与者节点正式完成操作，并释放在整个事务期间内占用的资源。
> 
> 3）参与者节点向协调者节点发送”完成”消息。
> 
> 4）协调者节点受到所有参与者节点反馈的”完成”消息后，完成事务。

如果任一参与者节点在第一阶段返回的响应消息为”中止”，或者 协调者节点在第一阶段的询问超时之前无法获取所有参与者节点的响应消息时：

[![fail][]][fail]

> 1）协调者节点向所有参与者节点发出”回滚操作(rollback)”的请求。
> 
> 2）参与者节点利用之前写入的Undo信息执行回滚，并释放在整个事务期间内占用的资源。
> 
> 3）参与者节点向协调者节点发送”回滚完成”消息。
> 
> 4）协调者节点受到所有参与者节点反馈的”回滚完成”消息后，取消事务。

不管最后结果如何，第二阶段都会结束当前事务。

二阶段提交看起来确实能够提供原子性的操作，但是不幸的事，二阶段提交还是有几个缺点的：

> 1、同步阻塞问题。执行过程中，所有参与节点都是事务阻塞型的。当参与者占有公共资源时，其他第三方节点访问公共资源不得不处于阻塞状态。
> 
> 2、单点故障。由于协调者的重要性，一旦协调者发生故障。参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。（如果是协调者挂掉，可以重新选举一个协调者，但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题）
> 
> 3、数据不一致。在二阶段提交的阶段二中，当协调者向参与者发送commit请求之后，发生了局部网络异常或者在发送commit请求过程中协调者发生了故障，这回导致只有一部分参与者接受到了commit请求。而在这部分参与者接到commit请求之后就会执行commit操作。但是其他部分未接到commit请求的机器则无法执行事务提交。于是整个分布式系统便出现了数据部一致性的现象。
> 
> 4、二阶段无法解决的问题：协调者再发出commit消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了。那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。

由于二阶段提交存在着诸如同步阻塞、单点问题、脑裂等缺陷，所以，研究者们在二阶段提交的基础上做了改进，提出了三阶段提交。

## 3PC ##

> 三阶段提交（Three-phase commit），也叫三阶段提交协议（Three-phase commit protocol），是二阶段提交（2PC）的改进版本。

[![3][]][3]

与两阶段提交不同的是，三阶段提交有两个改动点。

1、引入超时机制。同时在协调者和参与者中都引入超时机制。 2、在第一阶段和第二阶段中插入一个准备阶段。保证了在最后提交阶段之前各参与节点的状态是一致的。

也就是说，除了引入超时机制之外，3PC把2PC的准备阶段再次一分为二，这样三阶段提交就有`CanCommit`、`PreCommit`、`DoCommit`三个阶段。

### CanCommit阶段 ###

3PC的CanCommit阶段其实和2PC的准备阶段很像。协调者向参与者发送commit请求，参与者如果可以提交就返回Yes响应，否则返回No响应。

> 1.事务询问 协调者向参与者发送CanCommit请求。询问是否可以执行事务提交操作。然后开始等待参与者的响应。
> 
> 2.响应反馈 参与者接到CanCommit请求之后，正常情况下，如果其自身认为可以顺利执行事务，则返回Yes响应，并进入预备状态。否则反馈No

### PreCommit阶段 ###

协调者根据参与者的反应情况来决定是否可以记性事务的PreCommit操作。根据响应情况，有以下两种可能。

假如协调者从所有的参与者获得的反馈都是Yes响应，那么就会执行事务的预执行。

> 1.发送预提交请求 协调者向参与者发送PreCommit请求，并进入Prepared阶段。
> 
> 2.事务预提交 参与者接收到PreCommit请求后，会执行事务操作，并将undo和redo信息记录到事务日志中。
> 
> 3.响应反馈 如果参与者成功的执行了事务操作，则返回ACK响应，同时开始等待最终指令。

假如有任何一个参与者向协调者发送了No响应，或者等待超时之后，协调者都没有接到参与者的响应，那么就执行事务的中断。

> 1.发送中断请求 协调者向所有参与者发送abort请求。
> 
> 2.中断事务 参与者收到来自协调者的abort请求之后（或超时之后，仍未收到协调者的请求），执行事务的中断。

### doCommit阶段 ###

该阶段进行真正的事务提交，也可以分为以下两种情况。

执行提交

> 1.发送提交请求 协调接收到参与者发送的ACK响应，那么他将从预提交状态进入到提交状态。并向所有参与者发送doCommit请求。
> 
> 2.事务提交 参与者接收到doCommit请求之后，执行正式的事务提交。并在完成事务提交之后释放所有事务资源。
> 
> 3.响应反馈 事务提交完之后，向协调者发送Ack响应。
> 
> 4.完成事务 协调者接收到所有参与者的ack响应之后，完成事务。

中断事务 协调者没有接收到参与者发送的ACK响应（可能是接受者发送的不是ACK响应，也可能响应超时），那么就会执行中断事务。

> 1.发送中断请求 协调者向所有参与者发送abort请求
> 
> 2.事务回滚 参与者接收到abort请求之后，利用其在阶段二记录的undo信息来执行事务的回滚操作，并在完成回滚之后释放所有的事务资源。
> 
> 3.反馈结果 参与者完成事务回滚之后，向协调者发送ACK消息
> 
> 4.中断事务 协调者接收到参与者反馈的ACK消息之后，执行事务的中断。

在doCommit阶段，如果参与者无法及时接收到来自协调者的doCommit或者rebort请求时，会在等待超时之后，会继续进行事务的提交。（其实这个应该是基于概率来决定的，当进入第三阶段时，说明参与者在第二阶段已经收到了PreCommit请求，那么协调者产生PreCommit请求的前提条件是他在第二阶段开始之前，收到所有参与者的CanCommit响应都是Yes。（一旦参与者收到了PreCommit，意味他知道大家其实都同意修改了）所以，一句话概括就是，当进入第三阶段时，由于网络超时等原因，虽然参与者没有收到commit或者abort响应，但是他有理由相信：成功提交的几率很大。 ）

## 2PC与3PC的区别 ##

相对于2PC，3PC主要解决的单点故障问题，并减少阻塞，因为一旦参与者无法及时收到来自协调者的信息之后，他会默认执行commit。而不会一直持有事务资源并处于阻塞状态。但是这种机制也会导致数据一致性问题，因为，由于网络原因，协调者发送的abort响应没有及时被参与者接收到，那么参与者在等待超时之后执行了commit操作。这样就和其他接到abort命令并执行回滚的参与者之间存在数据不一致的情况。

--------------------

了解了2PC和3PC之后，我们可以发现，无论是二阶段提交还是三阶段提交都无法彻底解决分布式的一致性问题。Google Chubby的作者Mike Burrows说过， `there is only one consensus protocol, and that’s Paxos” – all other approaches are just broken versions of Paxos.` 意即世上只有一种一致性算法，那就是Paxos，所有其他一致性算法都是Paxos算法的不完整版。后面的文章会介绍这个公认为难于理解但是行之有效的Paxos算法。

## 参考资料： ##

[分布式协议之两阶段提交协议（2PC）和改进三阶段提交协议（3PC）][2PC_3PC] [关于分布式事务、两阶段提交、一阶段提交、Best Efforts 1PC模式和事务补偿机制的研究][Best Efforts 1PC] [两阶段提交协议与三阶段提交协议][Link 8]

# [分布式一致性算法——paxos][paxos] #

2015-12-06 分类：[分布式][Link 2] 阅读(15960) 评论(3)

> 随着大型网站的各种高并发访问、海量数据处理等场景越来越多，如何实现网站的高可用、易伸缩、可扩展、安全等目标就显得越来越重要。为了解决这样一系列问题，大型网站的架构也在不断发展。提高大型网站的高可用架构，不得不提的就是分布式。在关于分布式事务、两阶段提交协议、三阶提交协议一文中主要用于解决分布式一致性问题的集中协议，那么这篇文章主要讲解业内公认的比较难的也是最行之有效的paxos算法。

我认为对paxos算法讲解的最清楚的就是[维基百科][Link 9]了。但是要看懂维基百科中的介绍需要很强的数学思维（paxos毕竟是一个算法），而且有很多关于定理的推论、证明等过程。那么本篇文章主要站在程序的角度，通俗的，循序渐进的讲解到底什么是paxos算法。

## 背景 ##

Google Chubby的作者Mike Burrows说过， `there is only one consensus protocol, and that’s Paxos” – all other approaches are just broken versions of Paxos.` 意即世上只有一种一致性算法，那就是Paxos，所有其他一致性算法都是Paxos算法的不完整版。

Paxos算法是莱斯利·兰伯特（Leslie Lamport，就是 LaTeX 中的”La”，此人现在在微软研究院）于1990年提出的一种基于消息传递的一致性算法。为描述 Paxos 算法，Lamport 讲述了这样一个故事：

> 在古希腊有一个岛屿叫做Paxos，这个岛屿通过议会的形式修订法律。执法者（legislators，后面称为牧师priest）在议会大厅（chamber）中表决通过法律，并通过服务员传递纸条的方式交流信息，每个执法者会将通过的法律记录在自己的账目（ledger）上。问题在于执法者和服务员都不可靠，他们随时会因为各种事情离开议会大厅、服务员也有可能重复传递消息（或者直接彻底离开），并随时可能有新的执法者（或者是刚暂时离开的）回到议会大厅进行法律表决，因此，议会协议要求保证上述情况下可以能够正确的修订法律并且不会产生冲突。

## 什么是paxos算法 ##

Paxos 算法是分布式一致性算法用来解决一个分布式系统如何就某个值(决议)达成一致的问题。

人们在理解paxos算法是会遇到一些困境，那么接下来，我们带着以下几个问题来学习paxos算法：

1、paxos到底在解决什么问题？

2、paxos到底如何在分布式存储系统中应用？

3、paxos的核心思想是什么？

## paxos解决了什么问题 ##

在[关于分布式一致性的探究][Link 5]中我们提到过，分布式的一致性问题其实主要是指分布式系统中的数据一致性问题。所以，为了保证分布式系统的一致性，就要保证分布式系统中的数据是一致的。

在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。

所以，paxos算法主要解决的问题就是如何保证分布式系统中各个节点都能执行一个相同的操作序列。

[![Package Diagram(2)][Package Diagram_2]][Package Diagram_2]

上图中，C1是一个客户端，N1、N2、N3是分布式部署的三个服务器，初始状态下N1、N2、N3三个服务器中某个数据的状态都是S0。当客户端要向服务器请求处理操作序列：op1op2op3时（op表示operation）（这里把客户端的写操作简化成向所有服务器发送相同的请操作序列，实际上可能通过Master/Slave模式处理）。如果想保证在处理完客户端的请求之后，N1、N2、N3三个服务器中的数据状态都能从S0变成S1并且一致的话（或者没有执行成功，还是S0状态），就要保证N1、N2、N3在接收并处理操作序列op1op2op3时，严格按照规定的顺序正确执行opi，要么全部执行成功，要不就全部都不执行。

所以，针对上面的场景，paxos解决的问题就是如何依次确定不可变操作opi的取值，也就是确定第i个操作什么，在确定了opi的内容之后，就可以让各个副本执行opi操作。

## Paxos算法详解 ##

Paxos是一个十分巧妙的一致性算法，但是他也十分难以理解，就连他的作者Lamport都被迫对他做过多种讲解。我认为对paxos算法讲解的最清楚的就是[维基百科][Link 9]了。但是要看懂维基百科中的介绍需要很强的数学思维（paxos毕竟是一个算法），而且有很多关于定理的推论、证明等过程。那么本篇文章主要站在程序的角度，通俗的，循序渐进的讲解到底什么是paxos算法。

我们先把前面的场景简化，把我们现在要解决的问题简化为如何确定一个不可变变量的取值（每一个不可变变量可以标识一个操作序列中的某个操作，当确保每个操作都正确之后，就可以按照顺序执行这些操作来保证数据能够准确无误的从一个状态转变成另外一个状态了）。

--------------------

接下来，请跟我一步一步的学习paxos算法。

要学习paxos算法，我们就要从他要解决的问题出发，假如没有paxos算法，当我们面对如何确定一个不可变变量的取值这样一个吻问题的时候，我们应该如何解决呢？

> 这里暂不介绍paxos中的角色的概念，读者可以自行从[维基百科][Link 9]中了解。不了解的话也可以直接往下看，看着看着就了解了。

### 问题抽象 ###

我们把确定一个不可变变量的取值问题定义成：

> 设计一个系统，来存储名称为var的变量。
> 
> > var的取值可以是任意二进制数
> > 
> > 系统内部由多个Accepter组成,负责管理和存储var变量。
> > 
> > > 系统对外提供api,用来设置var变量的值  
> > > `propose(var,V) => <ok,f> or <error>`
> > > 
> > > > 将var的值设置为V，系统会返回ok和系统中已经确定的取值f，或者返回error。
> > 
> > 外部有多个Proposer机器任意请求系统，调用系统API(`propose(var,V) => <ok,f> or <error>`)来设置var变量的值。
> > 
> > > 如果系统成功的将var设置成了V，那么返回的f应该就是V的值。否则，系统返回的f就是其他的Proposer设置的值。

> 系统需要保证var的取值满足一致性
> 
> > 如果var没有被设置过，那么他的初始值为null
> > 
> > 一旦var的值被设置成功，则不可被更改，并且可以一直都能获取到这个值
> 
> 系统需要满足容错特性
> 
> > 可以容忍任意proposer出现故障  
> > 可以容忍少数acceptor故障（半数以下）
> 
> 暂时忽略网络分化问题和acceptor故障导致var丢失的问题。

到这里，问题已经抽象完成了，读者可以再仔细看看上面的系统描述。如果这样设置一个系统，是不是就可以保证变量var的不可变性了呢？

> 这里还是再简单讲解一下，上面的系统确实可以保证变量var的不可变性。
> 
> 因为var的初始值为null，当有proposer请求接口propose（var，v）设置var的值的时候，系统会将var设置为v，并返回f（f==v）。
> 
> var变量被初始化以后，再有proposer请求propose(var,v)设置var的值的时候，系统会直接返回系统中已有的var的值f，而放弃proposer提供的v。

### 系统难点 ###

要设计以上系统存在以下难点：

1、管理多个proposer并发执行

2、容忍var变量的不可变性

3、容忍任意Proposer的故障

4、容忍半数以下的acceptor的故障

### 解决方案一 ###

先考虑整个系统由单个acceptor组成。通过类似[互斥锁][Link 10]的方式来管理并发的proposer的请求。

proposer向acceptor申请acceptor的互斥访问权，当取得互斥访问权之后才能调用api给var变量赋值。  
accepter向proposer发放互斥访问权，谁取得了互斥访问权，acceptor就接收谁的请求。  
这样通过互斥访问的机制，proposer就要按照获取互斥访问权的顺序来请求系统。  
一旦acceptor接收到一个proposer请求，并成功给var变量赋值之后，就不再允许其他的proposer设置var变量的值。每当再有proposer来请求设置var变量的值的时候，acceptor就会将var里面现有的值返回给他。

基于互斥访问权的acceptor的实现

> acceptor会保存变量var的值和一个互斥锁Lock。
> 
> 提供接口prepare()
> 
> > 加互斥锁，给予var的互斥访问权，并返回当前var的取值
> 
> 提供接口release()
> 
> > 用于释放互斥访问权
> 
> 提供接口accept(var, v)
> 
> > 如果已经加锁，并且当前var没有值，则将var的值设置成v，并释放锁。

proposer采用两阶段来实现

> Step1、通过调用prepare接口来获取互斥性访问权和当前var的取值
> 
> > 如果无法获取到互斥性访问权，则返回，并不能进入到下一个阶段，因为其他proposer获取到了互斥性访问权。
> 
> Step2、根据当前var的取值f选择执行
> 
> > 1、如果f的取值为null，说明没有被设置过值，则调用接口accept(var ,v)来将var的取值设置成v，并释放掉互斥性访问权。  
> > 2、如果f的取值不为null，说明var已经被其他proposer设置过值，则调用release接口释放掉互斥性访问权。

总结：方案一通过互斥访问的方式来保证所有的proposer能够串行的访问acceptor，这样其实并没有解决多个proposer并发执行的问题。只是想办法绕开了并发执行。虽然可以在一定程度上保证var变量的取值是确定的。但是一旦获取到互斥访问权的proposer在执行过程中出现故障，那么就会导致所有其他proposer无法再获取到互斥访问权，就会发生死锁。。所以，方案一不仅效率低、而且还会产生死锁问题，不能容忍任意Proposer出现故障。  
在之前提到的四个系统难点中，方案一可以解决难点1和难点2，但是无法解决难点3和难点4。

### 解决方案二 ###

通过引入[抢占式访问权][Link 11]来取代互斥访问权。acceptor有权让任意proposer的访问权失效，然后将访问权发放给其他的proposer。

在方案二中，proposer向acceptor发出的每次请求都要带一个编号（epoch），且编号间要存在全序关系。一旦acceptor接收到proposer的请求中包含一个更大的epoch的时候，马上让旧的epoch失效，不再接受他们提交的取值。然后给新的epoch发放访问权，让他可以设置var变量的值。

为了保证var变量取值的不变性，不同epoch的proposer之前遵守`后者认同前者`的原则：

> 在确保旧的epoch已经失效后，并且旧的epoch没有设置var变量的值，新的epoch会提交自己的值。  
> 当旧的epoch已经设置过var变量的取值，那么新的epoch应该认同旧的epoch设置过的值，并不在提交新的值。

基于抢占式访问权的acceptor的实现

转载于:https://www.cnblogs.com/think90/p/11443425.html

[Link 1]: https://www.hollischuang.com/archives/655
[Link 2]: https://www.hollischuang.com/archives/category/%E5%88%86%E5%B8%83%E5%BC%8F
[Link 3]: https://www.hollischuang.com/archives/663
[Link 4]: http://www.hollischuang.com/archives/655
[CAP]: http://www.hollischuang.com/archives/666
[BASE]: http://www.hollischuang.com/archives/672
[Link 5]: http://www.hollischuang.com/archives/681
[CAP 1]: https://www.hollischuang.com/archives/666
[Teorema-CAP-2]: /images/20230601/57b1ee5dee2f46b19e9727cdf02e5720.png
[Link 6]: http://www.hollischuang.com/archives/663
[intro_thumb]: /images/20230601/16a39a913db342a69982705f1aede38b.png
[scenario1_thumb]: /images/20230601/50badaa6e2f24de088183f67192d8860.png
[scenario2_thumb]: /images/20230601/051c505d5fef4d138e673b50bfe342f7.png
[Zookeeper_Zookeeper]: http://www.hollischuang.com/archives/1275
[CAP_BASE]: http://my.oschina.net/foodon/blog/372703
[CAP 2]: http://www.xiaoyaochong.net/wordpress/index.php/2013/07/27/cap%E5%8E%9F%E7%90%86%E7%9A%84%E8%AF%81%E6%98%8E/
[CAP 3]: http://dbaplus.cn/news-159-1917-1.html
[CAP 4]: http://blog.csdn.net/chen77716/article/details/30635543
[BASE 1]: https://www.hollischuang.com/archives/672
[CAP_BASE 1]: http://my.oschina.net/foodon/blog/372703#OSC_h1_6
[Link 7]: https://www.hollischuang.com/archives/681
[success]: /images/20230601/17beaf52cfff4d04a00e384943925ca3.png
[fail]: /images/20230601/b0ed0a24180b4ac4850b47942c45b71b.png
[3]: /images/20230601/b5bff24f25254368b44aad07807d04a8.png
[2PC_3PC]: http://www.mamicode.com/info-detail-890945.html
[Best Efforts 1PC]: http://blog.csdn.net/bluishglc/article/details/7612811
[Link 8]: http://www.tuicool.com/articles/mARV3u
[paxos]: https://www.hollischuang.com/archives/693
[Link 9]: https://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95
[Package Diagram_2]: /images/20230601/9f0e709587044f2bb93c006af4722b7d.png
[Link 10]: https://zh.wikipedia.org/wiki/%E4%BA%92%E6%96%A5%E9%94%81
[Link 11]: https://zh.wikipedia.org/wiki/%E6%8A%A2%E5%8D%A0%E5%BC%8F%E5%A4%9A%E4%BB%BB%E5%8A%A1%E5%A4%84%E7%90%86