黄振业

摘  要：Paxos算法是被广泛使用的分布式一致算法，为了保障Paxos算法的正确性和高性能，需要配合使用高性能、高可用、全局唯一自增序列号的生成系统。为此，该文提出了一种全局唯一自增ID的生成方法，该方法以物理机器时钟频率不会产生大波动的特性为前提，并在实现上采用多种高性能、高可用技术。最后构建了测试环境，通过实验证明了该方案在正常态和异常态时，都能正确产生全局唯一自增ID，同时整个系统也达到了预期的高性能要求。

关键词：一致性  唯一自增ID生成  高性能  高可用

中图分类号：TP301                          文献标识码：A文章编号：1672-3791（2021）03（c）-0001-06

Generation Method of Global Unique Auto Increment ID Generation for Paxos Algorithm

HUANG Zhenye

（School of Information Technology， Zhejiang Financial College， Hangzhou， Zhejiang Province， 310018 China）

Abstract： Paxos is a protocol for solving consensus in a distribution system. Paxos can work in a network with fail-ures， and all processors in the network could be unreliable. While Paxos protocol has a precondition step： generat-ing the unique version numbers for Paxos protocol. This paper proposes a method to generate the unique version numbers for Paxos protocol. And this method should be high available and should have high performance. Aiming to this object， the method utilizes the stability of machine timestamp， and uses high available techniques on imple-mentation. Finally， a test environment is constructed. Experiments show that the method can generate the unique version numbers correctly in normal and abnormal conditions， and the whole system also achieves the expected high performance requirements.

Key Words： Consensus; Unique auto increment ID generation; High performance; High available

目前，有很多分布式一致性算法來解决分布式系统的一致性问题，而Paxos算法是其中重要的一种算法，它已经被应用到多种系统中[1]。Paxos算法又分为Basic Paxos算法和Multi-Paxos算法[2]。在这两种算法之上又有一些改进的算法[3-6]，但这些算法都需要有一个机制来生成全局唯一自增ID。如果不能保障生成全局唯一自增的ID，就不能保障Paxos算法的正确性。

该文提出了一种新的全局唯一自增ID的生成方法，同时会涉及工程上实现的细节。首先，简单介绍Paxos算法，其中着重说明全局唯一自增ID的生成的必要性;其次，列举其他一些常用的全局唯一自增的ID的生成方式以及它们的不足;最后，重点介绍新的全局唯一自增ID的生成方法及实验结果。

1  Basic Paxos

Paxos算法分为Basic Paxos算法和Multi-Paxos算法，而全局唯一自增ID的生成方法对两者并无区别，该文就以Basic Paxos算法作为例子来说明Paxos算法。

Paxos算法中的进程有3种身份：proposer、acceptor、learner。……