Distributed Systems-一致性协议背景介绍及Paxos算法的推导

Paxos算法无疑是分布式系统理论中的经典，由于很多论文、博客都没有详细分析算法的背景以及实际中应用会产生的非常多的细节问题，所以导致很难理解，或者说很难完整理解，实现和测试则是更繁杂，不过这也是这个问题有意思的原因吧:-)。读过一些论文，思考过一些问题，希望能把这个问题的背景，以及各种容错分布式一致性算法设计的逻辑和背景记录下来，当然，内容实在太多，最早得追溯到迪杰斯特拉对并发与分布式问题的讨论吧，所以这个系列准备以Paxos算法为核心，介绍其一系列的衍生算法及其相关的问题。当然，很多东西是通过一些论文结合自己的理解去推测作者当时怎么去思考设计优化这些算法的，至于形式化证明的部分就弱化了。整个系列的最大目的是希望能理清分布式共识问题的背景，主要容错分布式一致性协议的设计逻辑以及它们的联系与区别，后面有机会分析下实际工程中的实现比如ZooKeeper/Etcd/Consul等，最后如果有机会自己简单实现一下:-)

Contents:

• 并发，一致性，时序
• 分布式系统的基本概念与特点，包括系统模型／分布式共识／分布式一致性
• 容错分布式一致性协议与Paxos算法
• leader-based容错分布式一致性协议
• 选主与同步
• 日志复制，membership management，客户端交互，leader租约等等
• 其他leader-based协议Viewstamped Replication／Zab的介绍以及Paxos与各种leader-based容错一致性协议的对比
• 开源实现与分析

这一篇文章主要简单介绍一下分布式共识和一致性协议的背景和Paxos算法，以及我所理解的它的设计逻辑，并按照这个逻辑尝试非形式化地重新设计Paxos算法，并与Lamport原始论文中的描述相对应。这篇文章主要指basic Paxos，而不是其他变形比如Multi-Paxos及其他的leader-based的分布式一致算法，比如Raft/Viewstamped Replication/Zab，后续文章会着重分析leader-based的分布式一致算法。

1. 分布式系统基本概念回顾

• 分布式系统的基本特点

  • 部分故障
    
    • 容错
  • 没有全局时钟
    
    • 事件定序 : 原子时钟，Lamport Clock，Vector Clock等
    • 副本一致性问题 : 通常为了保证容错，需要使用多个副本，副本之间的复制需要保证强一致
  • 通信延时影响性能和扩展性
    
    • 保证系统正确性下较少消息传递，减少共享状态，使用缓存等等

• 系统模型

  • 同步和异步
    
    • 同步
    • 异步(执行时间和消息传递时间没有上限)
  • 网络模型
    
    • 可靠
    • 消息丢失，重复传递，消息乱序
  • 故障模型
    
    • crash-failure fault
    • byzantine fault

• 一致性

  • data-central
    
    • 严格一致性(strict consistency)
    • 线性一致性(linear consistency)
    • 顺序一致性(sequential consistency)
    • 因果一致性(casual consistency)
    • 弱一致性(weak consistency)
    • 最终一致性(eventual consistency)
  • client-central
    
    • 单调读一致性(Monotonic Reads Consistency)
    • 单调写一致性(Monotonic Writes Consistency)
    • 读写一致性(Read Your Writes Consistency)
    • 写读一致性(Write Follows Read Consistency)
  • 其他

2.分布式共识问题及容错分布式一致性协议

导致对Paxos理解困难的一个原因是对分布式共识问题本身没有较好的理解。先举个简单例子，然后再说明其需要满足的safety和liveness条件。

例子：多个人在食堂决定吃什么菜，不能事先商量好，每个人都可以同时提出一样菜，中间可能有些人临时去上厕所了，待会重新回来，要保证的是最终只有一种菜被接受，而且重新回来的人在需要的时候能够知道这次吃饭到底吃的是什么菜。这里需要注意的是：“同时”说明并发的，有些提议的值可能被覆盖的；“有人临时上厕所”说明需要容错，即在机器挂掉下的分布式一致；“重新回来”说明机器recover后能知道之前决议的结果；

分布式共识问题通常需要满足Safety和Liveness的要求，具体来说就是：

• Safety

  • 只有被提出的值才有可能通过决议
  • 最终只有一个值被接受
  • 一个参与者只有在决议达成之后才可能知道决议的值

• Liveness

  • 最终能对某个值达成决议
  • 如果有一个值达成了决议，那么这个值能最终被参与者学习到

• 对于Liveness的问题想多说点，在FLP定理中讨论的模型是完全异步，crash-failure fault但网络可靠这种假设比较严格的模型，并证明了在此系统模型下不存在完整的分布式一致性算法能解决分布式共识问题(注意是完整，如果我们放弃一些Safety或者Liveness的要求，比如保证严格的Safety而使用随机化等方法保证一定概率的Liveness，这样的算法是能实现的，而这也是Paxos一类算法的取舍，毕竟放弃了Safety没太大意义了），而通常像Paxos和类Paxos算法讨论的模型比FLP中的模型更松：完全异步，网络不可靠，crash-failure fault甚至byzantine fault，所以Paxos类算法本质上也没办法完美解决Liveness的问题，Lamport的原始论文中只提到选主(选出distinguished proposer)来解决这个问题，但是至于选主本身的Liveness和容错问题并没有详细讨论，这在后面选主相关部分还会涉及到。

3.多数派

这里把多数派拿出来的原因是因为我觉得他是设计容错分布式一致性算法的前提和基础。基于前面对分布式一致问题的说明以及其需要满足的条件，我们先来看看safety的要求，关于liveness在后面会分析。为了方便说明，我们把需要设置值的叫做一个项，比如下一个日志槽位，一次决议就是针对某个项设置值。

简单来说：
=>

• 对于某个项，在没有值时，可以从提出的多个值中任意选择一个（这里意味着多个参与者可以对同一个需要达成共识的项并发发起proposal，并且各自提出不同的值，无法保证按照提出的顺序，只是保证一旦对某个值达成决议，那么后续的proposal只能重新使用已经达成决议的值，其实这也是基本的safety要求啦，也是分布式共识问题的要求），并且保证后面的决议也只能设置同一个值。

=>

• 那么，在容错的要求下，很显然我们必须保证后续的某次决议中至少有一台存活机器知道这个项的值，而且我们允许每次决议期间有一些机器能离开(网络分区，挂掉等)

=>

• 显然多数派能满足上面的要求，在2f+1台机器下，对于每次决议都允许最多f台机器挂掉，并且能保证之前达成决议的所有项的值都至少有一台存活的机器知道

好了，我们推导出了多数派能够为分布式一致性算法提供容错的基础，下面我们基于此来尝试设计Paxos算法。

4.Paxos算法

上面多数派保证了在每次决议时都有存活机器知道之前所有达成决议的项的值。那么，怎么保证后续针对之前某个项的决议只能设置项本身的值？

先简要回顾下Paxos算法的核心部分:

• 达成一轮共识的流程

  • 对于每一轮，比如针对下一个日志槽位(其实Paxos完全可以乱序，并不一定要按照日志槽位顺序)达成某个值的共识来说，每个参与者需要记录并持久化的数据有当前已见过的最大的proposal number(last_seen_proposal_id)，已经对某个proposer投票的最近的proposal number(last_voted_proposal_id)以及对应的值(last_voted_proposal_value)。
  • 阶段1
    
    • proposer选择一个proposal number向多数派的acceptor发送prepare请求（注意可以并发）
    • acceptor接受到prepare请求后，如果请求中的poposal number大于last_voted_proposal_id，则更新last_voted_proposal_id，如果last_voted_proposal_value不为空，则带上返回prepare-ack消息；反之，则拒绝这个proposal，不返回或者带上last_voted_proposal_id返回拒绝消息，提醒proposal更新last_seen_proposal_id提高性能（原论文描述是保证不再接受比请求的proposal number小的其他决议请求，并返回已经达成的决议值，如果有的话，这里只是用具体实现描述出来了）
  • 阶段2
    
    • 如果proposer收到acceptor多数派的prepare-ack消息，则从收到的消息中找出最大的proposal id以及其对应的proposal value，如果这个value不为空，则使用这个value作为最终决议值，否则可以使用任意值（比如客户端请求的值），然后发送accept消息
    • 如果acceptor收到proposer的accept请求，则接受，除非收到新的更高proposal number的决议请求并投票了。

• 学习一个已经达成共识的值

  • 每次acceptor受到决议的时候都将决议发送给learner。这里和membership management以及日志恢复等相关联了，后面会涉及到，这里不多说

• 进展性的解决

  • Paxos算法里Lamport只是简单提到选主来解决紧张性问题，没有具体分析

OK，回到本节开始的问题
=>

• 自然而然，分两个阶段，因为我们事先不知道针对此项是否已经达成决议（这里实际上已经暗含着Paxos算法的主要设计原则之一，即给每个决议请求编号，区分已达成的决议，后发起的决议，以及过时的决议），所以需要prepare阶段询问存活的机器，如果已经达成过，那么至少会有一台机器知道这个值，那么我们就用这个值进入accept阶段，在accept阶段，如果有多数派都同意了这个值，那么决议达成。这就是Paxos的两阶段流程。另外，为了保证能正确恢复，Paxos算法的两阶段中，在请求响应的地方需要持久化某些状态值，这个可以参考原论文。

• 当然，其中采用全局递增的标识给决议编号在定义两个决议的两个阶段的互相交错时的行为上起着决定性作用(这一点实际上是由于并发提决议导致的，对于leader-based的算法比如raft实际上在一个term期间内只有一个有效的leader，所有决议只能由这个leader发出，所以不存在这个问题，对于每个“”客户端请求决议”term的值不需要增加，但是当进入选主的状态时，可能会有并发的candidate发起选主决议了，此时实际上又回到了基本的Paxos，raft采用随机timeout的简单方法来解决基本Paxos的livelock问题)这一点需要较形式化地分析，不好像上述那样以逻辑推演的方式一步一步导出，因为涉及的状态转换较多。

• 关于liveness的问题，可能存在多个proposer交替抢占导致的livelock问题，导致针对某个项无法达成某个值的决议。这个在前面也提到FLP定理所限制的。

5.leader-based容错分布式一致性算法

这一节为后面的文章做个铺垫:-)。从前面的分析可以看到，基本Paxos在面对多个proposer并发提起决议的时候可能导致livelock的问题，虽然Lamport原论文提到每一轮Paxos开始前选出一个distinguished proposer（leader/master），但是并没有详细说明与强化leader这个概念，这也是后面很多leader-based容错分布式一致性算法强调的一点，而强leader的概念能带来很多工程上实现的简化与优化。另外对于多个client的并发请求可能导致某些值的丢失，比如对于日志的replication，client1访问proposer1，client2访问proposer2，而proposer1和proposer2都同时针对当前下一个日志项，此时可能导致某个client的值的覆盖丢失。所以实际中往往会选出一个leader，唯一一个能接受客户端请求提起决议。

除了解决上面的问题，选主还能为算法优化与简化带来更大空间。比如raft对选主做限制，保证leader上的日志都是最新且连续的，在一定程度上简化了lamport在《paxos made simple》中简单提及的multi-Paxos在leader日志恢复的步骤，另外，batch决议请求，让leader保证最新日志优化读请求(leader lease/follower lease)等。

实际上选主避免并发决议的问题后一切都相对容易理解了，只是在后续leader的日志恢复以及新recover机器的日志恢复，以及整个集群的恢复方面还会走基本Paxos的两个阶段，而在这些具体的恢复方法和步骤在不同的算法中是不同的，而从Multi-Paxos/ViewStamp replication/Zab/Raft来看，尤其是近两年来的Raft，基本上是在保证基本的容错下的safety和liveness之外加上各种限制条件来简化leader选举，日志恢复，日志复制几个阶段以及其他比如membership management，snapshot等功能的。本质上在leader-based的一致性算法中，在leader选举和日志恢复可能会用到基本Paxos，选主后的log replication实际上就是仅仅用了多数派。后面会更详细讨论。

ref：
整理的一些资料