基础Paxos算法笔记(9/9)

       第九页笔记讨论Paxos算法中的主要数据结构和关键逻辑行为，是该算法进行工程化实践的思考。

       关键词：数据结构、逻辑和状态。

       在前8节的笔记中，我们讲述了异步消息是该算法的沟通方式，从Client如何发起Request开始，到Proposer收到Request将其转换为Proposal，然后将提案发给多数的Acceptor。我们详细讨论了Acceptor收到Prepare请求后的处理逻辑，并将生成的决议发给Learner的过程。在Learner收到决议后，如何能够高效的在Learner之间完成共享，并将Response发回给Client，从而完成一次Paxos算法。

       通过前面的讲述，我们应该对Paxos算法有了一个大致的了解，在开始本节的内容之前，笔者会再次罗列一下关键的功能点，这样也便于后续对该算法数据结构的讨论。以算法角色（或参与者）为视角，其功能如下表（其中顺序一栏表示该功能在算法中的使用次序，升序排列）：

       接下来需要看一下算法中的主要领域对象，在Paxos算法中，参与者包括：Client、Proposer、Acceptor和Learner。其中Client是入口，也可以作为使用算法的SDK，部署在使用方的应用中。

       Client会具有Proposer列表，在每次发起请求时，会随机选用一个Proposer发起请求。Proposer会具有Acceptor列表，每次在Prepare请求发起前会将提案发往这个列表中的多数（或者是发往多数后，停止发送）。Acceptor会具有Learner列表，在发布决议时，选择其中一个集合进行通知。Learner会根据请求中的地址发起对Client的建链，只需要确保网络可达即可。

       上述关系如下图所示：

       在Client一端，具有一个请求ID到Request的Map结构，用来在请求时将数据放置其中，当Learner发回响应时，取出其中的Request来进行应答处理。每个Client都会具有Proposer列表。

       Proposer具有提案列表，在发送Prepare请求前，需要先保存在本地。Acceptor具有提案和决议列表，用来接收Prepare请求，以及在Accept请求处理时，将提案转为决议并存储。

       Learner除了知晓其他Learner的地址，还需要保有同步其他Learner的进度记录，只有这样才能在后续的定时同步时做到有的放矢。

       除了上述参与者，算法中出现最多的就是提案、决议和请求等数据了，它们之间的关系，以及各自所具有的属性，如下图：

       从请求到最终的响应，环环相扣，最终的响应能够知晓它的决议是谁？之前的提案是什么？谁发起的？只有这样，一个响应发回才能对应的上请求，同时能够给到Client以详实的信息。

       请求中的Client关键信息，包括了Client的IP等关键信息，目的是能够在之后Learner回复响应时，找到发起的Client，也只有将响应回复到该节点，才有意义。如果回复到其他Client将没有任何效果，这是为什么呢？读者可以自行思考。

参考Client的数据结构。

       提案中的与Acceptor的关系，来自于Acceptor回复的Promise，每个Promise都会形成一条关系。决议中的新增日志，就是为了Learner之间同步数据而准备的，每条日志都会有（自增）主键，便于其他Learner掌握同步进度。

       Basic Paxos算法到这里就基本描述完了，它说起来复杂，但本质也很简单。它利用了多数原则，通过一定的冗余和决策，解决了分布式环境中的共识问题，这个思想在分布式系统中具有广泛的运用场景。