X-Paxos —阿里巴巴的高性能分布式强一致性Paxos独立基础库

文章目录

[隐藏]

五，现状与未来

作为分布式系统的基石，Paxos（分布式共识算法）一直是计算机系统工程领域的热门话题. Paxos声称是最难理解的算法. 实施如此困难吗？ “ X-Paxos”是由Alibaba团队实现的高性能分布式强大且一致的Paxos独立基本库，旨在实现高性能，全球部署和Ali业务特性. X-Paxos的具体优势是什么？它可以为现有系统带来什么好处？

分布式共识算法（Consensus Algorithm）是分布式计算领域的一个基本问题. 它的最基本功能是在多个过程之间达成一定的协议（强协议）. 然后解决分布式系统的可用性问题（高可用性）. Paxos是最重要的分布式共识算法，许将其用作“分布式共识协议”的同义词（Google Chubby服务的发明者Mike Burrows说: “只有一个共识协议，那就是Paxos”）

关于Paxos的历史和原理，已经有很多经典论文可供参考，并且工厂内外都有详细的说明文章. 本文将不再重复. 有兴趣的学生可以阅读这些论文[1,2,3,4].

尽管Paxos的理论提出以来已经有17年了，但自Paxos首次工业化实现以来已经有11年了，但是直到最近几年，无论是顶级会议还是行业，Paxos的相关文章和项目仍然是无止境的.

转向行业，尽管使用Paxos和各种变体的产品层出不穷. 但是真正的工业级，独立的Paxos基础库仍然非常罕见: Google不会开源其所有Paxos基础库（甚至包括Paxos的库也不是该项目的开源库）； Facebook尚未宣布包含Paxos的产品. Apache具有Zookeeper，但是其协议不支持高吞吐量状态机复制，并且不提供用于快速访问的独立第三方库. 可以在Github上找到的独立Paxos库，最高的明星是phxpaxos，它是腾讯去年开源的（以后将作为竞争产品进行详细比较）.

到目前为止，几乎没有成熟，可靠的独立第三方Paxos库可供行业快速使用，并且开源Paxos生态系统还不成熟.

我们的初衷不是成为Paxos公共图书馆. X-Paxos诞生于阿里巴巴的分布式AliSQL X-Cluster，但是X-Paxos不属于AliSQL X-Cluster. Paxos是分布式系统的基石，X-Paxos可用于解决各种分布式系统中的一致性问题. 因此，在整个分布式设计的开始，我们独立设计了分布式一致性协议模块，并使其独立为X-Paxos. X-Paxos解决了AliSQL X-Cluster的分布式一致性问题，并且还可以快速为其他系统提供分布式一致性功能. 分布式一致性要求并非AliSQL X-Cluster独有. 许多系统具有如此高的可用性和强大的一致性要求. 我们在基本库中具有独立的Paxos功能，希望将此功能引入更多其他系统. 例如，团队中的学生将X-Paxos集成到独立的KVRocksDB中，并迅速实现了分布式KV引擎. CNZZ团队将X-Paxos集成到业务存储系统中，以构建新的分布式强一致性存储服务.

同时，它是制作X-Paxos的AliSQL X-Cluster. Google的论文“ Paxos made live”中有一段很好. 总体思路是: Paxos理论与现实世界之间存在巨大的差距. 实现Paxos时，通常需要经典的Paxos理论. 做一些扩展（特别是在实现高性能Paxos时，有更多扩展点，您可以参考后面的功能增强和性能优化），这通常导致实际的Paxos实现实际上是基于经过充分验证的协议. 这就是为什么该理论证明Paxos的实现比该Paxos的实现更加困难的原因. 因此，成熟的Paxos实现很难独立生成，并且经常需要与一个系统结合以通过一个或多个系统验证其可靠性和完整性. 这就是为什么大多数成熟的Paxos用例都与分布式结合使用的原因，例如最早的Paxos实现（Chubby）和当前的主要Paxos实现（Google MegaStore，Spanner，AWS DynamoDB，S3等）. X-Paxos依靠AliSQL X-Cluster来验证其可靠性和完整性.

我们的愿景是提供一个经过验证的，高度成熟且可靠的独立Paxos基础库. 通过简单的访问，它使后端服务具有简单的一致性，高可用性，自动灾难容忍和其他功能. Paxos真是晦涩难懂，已经变得平易近人，并带入了数百万的家庭.

X-Paxos的总体架构如下图所示，可以分为四个部分: 网络层，服务层，算法模块和日志模块.

网络层

网络层基于阿里巴巴非常成熟的网络库libeasy. libeasy的异步框架和线程池非常适合我们的整体异步设计. 同时，我们修改了libeasy的重新连接逻辑，以满足分布式协议的需求.

服务层

服务层是驱动整个Paxos操作的基础，为Paxos提供事件驱动，定时回调和其他核心操作功能. 每个Paxos实现都有与其紧密相关的驱动程序层. 驱动程序层的体系结构和性能与稳定性密切相关.

X-Paxos的服务层是一个基于C ++ 11功能的多线程异步框架. 通用状态机/回调模型存在诸如开发效率低，可读性差等问题，已被开发人员所批评. 协程有其单线程瓶颈，这限制了它们的应用场景. C ++ 11之后的新版本提供了诸如参数转发和变量模板参数之类的功能，这使我们可以实现新的异步调用模型.

例如，这是在X-Paxos中创建单个计划任务的实际代码行

new ThreadTimer(srv_->getThreadTimerService(), srv_, electionTimeout_, ThreadTimer::Oneshot,                  &Paxos::checkLeaderTransfer, this, targetId, currentTerm_.load(), log_->getLastLogIndex());  

上面的过程行包括创建计时器，设置任何回调函数，转发回调函数参数以及触发回调（Oneshot）后自动恢复内存. 同时，服务层支持嵌套的回调，即在回调函数中再次生成定时/即时任务，以实现有限数量的定时循环逻辑.

算法模块

当前的X-Paxos算法基于唯一提议者的multi-paxos [3]实现. 大量的理论和实践证明，基于提议者的独特的Paxos比Paxos /基本Paxos具有更好的性能. Paxos的大多数系统都使用这种方法.

本文不重复算法模块的基本功能. 有兴趣的学生可以参考相关论文[1,2,4]. X-Paxos在基本算法的基础上，结合Ali业务场景以及对高性能和生态的要求，进行了许多创新的功能和性能优化，使其比基本的多Paxos功能更加丰富，性能得到了显着提高在各种部署方案中. 在下一章中，将详细介绍这些优化.

日志模块

日志模块是算法模块的一部分，但是出于对极端性能的要求，我们隔离了日志模块并实现了默认的高性能日志模块；对性能和成本要求极高的用户，它可以与现有的日志系统结合使用，并与日志模块接口对接，以获得更高的性能和更低的成本. 这也是X-Paxos作为高性能独立库的独特优势，这将在下一章中详细介绍.

>>结合各种业务场景以构建开放的生态系统

X-Paxos基于标准的多用户系统，支持添加/删除具有多个角色的节点，并支持将领导者节点快速转移到其他节点（具有主要选举）.

Group和Ant的当前多站点和中央体系结构. 许多应用程序通常要求仅在没有城市级灾难恢复的情况下才写入中心的或调用其他分布式服务. 同时，它还要求在发生城市级灾难恢复时（同一城市中没有多个计算机机房），写入点可以切换到非中心位置，而不会丢失任何数据.

经典的游戏无法满足这些需求. 在经典理论中，大多数可以在强同步之后完成提交，并且大多数是非特定的，并且不能保证某个或多个特定节点将获得完整的数据并激活服务. 在实际实现中，地理位置较近的节点通常具有很强的一致性数据，而地理位置较远的节点则位于不一致程度较高的节点中，因此在灾难恢复期间永远不能将其激活为主节点，就像一个虚拟节点.

同时，当中央单节点发生故障并需要灾难恢复时，通常需要将主节点切换到同一中心中的另一个节点. 因为应用程序在多个位置的部署通常是不对称的，所以只有一个区域是完全链接的. 写入时，您需要将主节点切成特定区域. 这些要求都要求Paxos在选择母版时选择规则，并且经典理论中没有类似的功能. 添加权重还需要确保Paxos的正确性.

X-Paxos在协议中实现了战略多数和加权选择. 基于战略多数，用户可以指定一个节点/某些节点必须通过动态配置来维护强大的一致数据. 当出现灾难恢复需求时，他们可以立即激活主节点. 基于加权选择，用户可以指定每个节点的选择权重. 仅当高权重节点不可用时，低权重节点才会被激活.

在经典的多paxos实现中，每个节点通常包含三个功能: 提议者/接受者/学习者，并且每个节点都是功能齐全的节点. 但是在某些情况下，我们不需要所有节点都具有所有功能，例如:

当然，还有其他组合. 通过定制的节点角色组合，我们可以开发许多定制的功能节点，从而节省成本并丰富功能.

基于上一节中节点字符的自定义中单个学习者字符的功能，它引起了无限的想象. 学习者角色可以抽象为数据流订阅者（见证节点）. 可以将许多订户添加到整个群集. 提交新日志后paxos算法思想，这些订阅者将收到他们关心的日志流，基于订阅功能，我们可以使集群轻松实现下游订阅消耗，即时日志备份，配置更改推送等功能.

因此，我们将Learner角色分别打包到一个SDK中. 基于此SDK，用户可以为自己的集群快速添加，订阅，注册和流式传输订阅功能. 结合特定用途创建完整的生态.

例如，由AliSQL X-Cluster中的日志流SDK创建的生态系统:

使用X-Paxos，您还可以使用Witness SDK将分布式系统与其他下游系统快速连接以形成完整的生态系统.

我们以MySQL日志（binlog）备份为例:

SDK解决方案

除备份外，Witness SDK在下行流订阅（DRC），自封闭式高可用性系统（X-Driver），异步只读备用库等方有实际案例. 在不断添加更多的应用案例.

>>我们一直认为网络延迟不会影响吞吐量

除了在设计之初就具有强大的一致性和高可用性外，Paxos的高性能也至关重要，尤其是在应用于高性能分布式（例如AliSQL X-Cluster），协议的吞吐量和延迟时都提出了很高的要求. 同时，作为全球部署的分布式一致性协议，高延迟下的性能挑战变得尤为重要.

X-Paxos已经为高延迟网络做了许多协议优化尝试和测试，并通过合理的批处理和流水线结合了学术界现有的理论成果[5,6,7]，这是一套自行设计的方法. 并实现了适用于高延迟，高吞吐量和低延迟，高吞吐量网络的通信模式，极大地提高了X-Paxos的性能（请参阅下一部分进行比较）. 类似的优化在同类竞争对手中非常罕见.

批处理是指将多个日志合并为一条消息进行发送；批处理可以有效地减少由消息的粒度引起的额外损失，并提高吞吐量. 但是，太大的批处理很容易导致单个请求的延迟过大，从而导致大量并发请求，进而影响吞吐量和请求延迟.

管道是指在前一条消息返回结果之前将下一条消息同时发送到相应节点的机制. 通过增加并发消息的数量（流水线），可以有效减少并发单个请求的延迟，并且传输延迟当它小于传播延迟（高延迟和高吞吐量网络）时，可以有效地提高性能.

众所周知，批处理（邮件大小: M）和管道传输（邮件并发性: P）在以下关系下实现了最高吞吐量

M/R * P = D  

其中R是网络带宽，D是网络传播延迟（大约RTT / 2）

X-Paxos通过内置检测结合了以上理论，针对不同节点的部署延迟，并自适应地调整每个节点的Batching和Pipeling参数以实现整体最大吞吐量.

引入管道技术需要解决乱序日志的问题，尤其是在偏远的位置，因为窗口增加且乱序的可能性增加. X-Paxos实现了高效的乱序处理模块，可以屏蔽基础日志的乱序问题，并有效地存储乱序日志.

由于Paxos内部状态复杂，如何实现高效的单实例多线程Paxos成为一个巨大的挑战. 无论我们在github中提到的phxpaxos最多，还是在Oracle MySQL Group Replication中使用的xcom，它都是单线程实现. Phxpaxos使用单分区单线程，多实例聚合来提高总吞吐量，但是单分区的性能非常有限. xcom是基于协程的单线程实现. 单线程Paxos实现是在处理序列化/反序列化，分发和数据包发送逻辑时的串行执行，并且性能瓶颈很明显.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-173235-1.html