Paxos算法——前世

博客园首页 William 77浏览 0评论

    Paxos算法是基于消息传递且具有高度容错特性的一致性算法。我们将从一个简单的问题开始,逐步的改进我们的设计方案,最终得到Paxos,一个可以在逆境下工作的协议。

一、客户端-服务器模型

    我们从最小的分布式系统开始,在这个系统中,只有两个结点,客户端结点与服务端结点,客户端结点能够操作(存储或更新)远程服务器结点上的数据。

算法1.1  朴素的客户端/服务器算法:客户端每次向服务器发送一条命令。

    在存在消息丢失的消息传递模型中,该算法却不能很好的工作,客户端不能确认消息是否正确的被服务器所接受。因此我们需要对其进行一些小的改进。

算法1.2 待确认的客户端/服务器算法

    1.客户端向服务端发送一条请求命令消息。

    2.服务端接受请求并回复确认信息。

    3.客户端在一定的时间范围内,没有收到服务器端发送的请求确认信息的回复,则重新发送命令请求信息。

  • 该算法描述了,客户端在发送一条请求命令后,在收到服务端的确认回复前,是不会发送下一条请求命令。
  • 客户端在发送的过程中消息可能丢失,服务端在回复的确认消息时,消息也可能丢失,对于服务端确认消息的丢失情况,在到达一定超时时间后,客户端未收到确认回复,会重新发送消息,此时该消息已经被服务器端处理,所以我们需要有一种机制能够保证消息的幂等性。例如给消息加上序列号。
  • 该算法可以很容易的扩展到多服务器端的场景,客户端发送命令请求给每一个服务器端,当收到所有服务器的确认消息,就可以认为这条命令执行成功。
  • 如何处理多个客户端的场景?
    基于可变消息延迟模型我们可以得出如下定理,即消息的延迟时间是不定的,同一对结点的消息发送的时间延迟也是不同的。

定理1.1  如果算法在多个客户端与服务端运行,服务器收到的命令顺序可能是不同的,这会导致不一致的状态。

    假设在如下的场景中,存在客户端c1,c2 ,服务端 s1,s2.  服务端s1,s2存在相同的值x = 0。 如果此时 c1,向服务器s1,s2 发送 x = x + 1. 在同一时刻 c2 向服务器 s1,s2 发送 x = 2*x. 假设c1 先于 c2 到达 s1 ,则此时s1的状态值x为 2, 而 c2 先于 c1 到达 s2 , 则此时 s2 的状态值x为 1. 导致集群的状态不一致。

定义1.1  (状态复制)对于一组结点,如果所有结点都以相同的顺序执行命令序列 c1,c2,c3,c4……,则这组结点实现了状态复制

  • 状态复制是分布式系统的基本特征
  • 因为单个系统天然实现状态复制,可以令单个服务器系统实现序列化器,自动对请求进行排序来分发命令,从而实现状态复制。

算法1.3 借助单一的串行化器实现状态复制

    1. 所有的客户端将请求命令发送到串行化器

    2.串行化器逐个处理客户端请求,并将客户端请求逐个发送给所有服务器

    3.当串行化器接受到所有服务器的确认消息时,它将返回给对应客户端命令执行成功的消息。

  • 这个想法有时也被成为主从复制。
  • 改算法存在单点故障。串行化器
  • 我们是否可以构造一个更分布式的方法来解决状态复制的问题。去掉串行化器。任何时刻最多只有一个结点可以发送请求命令,是否可以采用互斥或各自加锁的思想?

算法 1.4 两阶段锁

    阶段 1  :

          客户端向所有服务器请求获取锁

    阶段 2: 

          if   客户端获得所有服务器的加锁请求 

               客户端以可靠的方式向所有服务器发送命令请求,释放锁

          else 

               客户端释放已经获取的锁,休眠一段时间,进入阶段 1 

 

  • 算法 1.4 是否能够很好的应对结点崩溃呢?在该算法中要求所有的服务器结点都必须能够正常的工作
  • 如果仅获取部分服务器的锁能否工作,获得过半数服务器的锁是否就足够了?
  • 如果超过两个以上的客户端试图获取超过半数服务器的锁,怎么应对死锁的问题,是否需要释放已经获取的服务器锁,如果客户端在释放锁之前就发生了故障,怎么办,是否需要一个与锁不同的概念。

 

 

 

 

 

 

 

注:www2014.aspxhtml.com转载自cnblogs,若看不到图片,请移步来源网址查看。
via:https://www.cnblogs.com/qing1376/p/9906631.html

转载请注明:AspxHtml学习分享网 » Paxos算法——前世

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址