尧图网站建设 
文档教程知识库【免费下载链接】translations Chinese translations for classic software development resources项目地址https://gitcode.com/gh_mirrors/tr/translations点击查看免费下载PaxosLease 是 Leslie Lamport 的 Paxos 算法面向**租约Lease**问题的自然特化变种它用经典的两阶段准备/提议协议协商谁持有租约却彻底去掉了 Paxos 中接受者响应前写盘的硬性要求也完全不需要结点间时钟同步。本文以本仓库 translations 中的经典论文译稿 paxoslease/README.rst 为主体展开读完你将掌握租约与锁的本质差异、请求者/接受者两轮通信获取租约的完整算法与伪代码、租约不变式的证明思路以及延长租约、释放租约、多资源租约等实战扩展和 Keyspace 参考实现的落地方案。1. 从锁到租约问题的背景在并发编程中**锁Lock**是进程用来同步共享资源访问的基本原语。但在锁以不设置过期时间的方式分配、且没有监督进程的系统中一旦锁的持有者在释放锁之前失效Failure其它进程就可能永久阻塞。在高可用系统中我们期望避免单点失效导致整个系统阻塞而且重启一个失效的分布式系统比重启一个多线程程序要困难得多。因此在分布式系统中租约Lease取代锁以避免饿死的情况。租约就是有过期时间的锁如果锁的持有者失效了或是与其它结点断开连接它的租约会自动过期其它结点就可以重新获得租约。论文对系统做了如下基本假设系统由一组**请求者Proposer和一组接受者Acceptor**组成各自运行各自的算法系统没有拜占庭问题——结点之间不会通过不遵守各自算法来作弊也不会被 Hack接受者的数目是固定不变的。1.1 朴素的多数派投票算法为什么不行一个朴素的多数派投票式算法可以正确地解决分布式租约问题——这里正确的意思是任何时候租约不会被多于一个结点持有。但这个简单算法在存在多个请求者时会频繁阻塞因此需要一个更成熟的方案。朴素算法的流程如下请求者启动一个本地超时计时器超时时间 T 秒然后向接受者发送请求时长为 T 的租约接受者收到请求后启动一个时长为 T 秒的定时器然后发送接受消息给请求者超时之后接受者清除自己的状态如果接受者收到请求但自己的状态不是空则接受者不回应或发送拒绝消息为确保任何时间只有一个请求者能获得租约请求者必须收到多数派接受者的接受消息这样它获取租约直到本地定时器超时。当有多个请求者时很可能没有请求者能得到多数派请求者会一直互相阻塞。例如有 3 个请求者 1、2、3 和 3 个接受者 A、B、C如果分布状态是A 接受 1 的请求、B 接受 2 的请求、C 接受 3 的请求那么没有一个请求者得到多数派的接受。系统必须等到超时过期、接受者清空自己的状态请求者再重试——但很可能再次阻塞。论文给出的解决方法是采用 Paxos 方案引入**准备Prepare和提议Propose**两个阶段从而完全避免这类阻塞问题。另一个替代思路是让系统阻塞但引入一个撤销机制让请求者撤销自己的请求从而使某个其它请求者获得租约。2. 为什么是无盘的 PaxosPaxos 解决的是复制状态机Replicated State Machine的一致性问题每个结点有一个本地状态机拷贝希望在下一个状态转换上结点间达成一致。Paxos 是基于多数派的算法它假设多数派结点没有宕机且彼此可以通信。Paxos 的一致性处理发生在一个状态转换上因此在实践中需要逐次运行多个 Paxos 实例来协商出一序列的状态转换。经典 Paxos 中接受者在发送响应之前要先把自己的状态记录到盘上以保证一旦一个值状态转换被选定之后一直选定该值——即不管出现何种错误所有状态机都经历相同的状态转换序列。这正是 paxos-made-simple/README.rst 译稿中所述Acceptor 在真正送出响应之前会将记录写入可靠性存储设备的要求。与经典 Paxos 不同PaxosLease 的接受者从不把状态写入存储租约具有临时性超时即可清空状态不需要持久化承诺。同时对比此前基于 Paxos 的分布式租约算法如 FatLeasePaxosLease 有两点关键简化不做任何时钟同步假设不对结点的本地时钟做时间同步假设也不需要全局同步避免连续运行 Paxos 实例FatLease 为了租约命令连续地运行 Paxos 实例而 PaxosLease 利用租约的临时性完全避免了这样的复杂性是一个更简单和优雅的算法。PaxosLease 处理的是一个特殊的复制状态机形式为为了获得租约请求者结点提交的值是结点 i 持有租约在租约过期后该值自动返回没有结点持有租约如图 1 状态机所示请求者也可以在前一次租约过期之前再次提交结点 i 持有租约值来延长租约或在过期之前释放租约可选操作。类似于 PaxosPaxosLease 本质上处理了所有相关的失效情况结点停止和重启网络分割不通消息丢失和乱序传输中的消息延时。3. 核心定义与数据结构一个 PaxosLease 单元由请求者和接受者组成假设有n个接受者和任意个请求者。实践中结点常常同时扮演请求者和接受者的角色但这是实现问题不影响算法讨论。3.1 四类消息请求者发送准备请求Prepare Request和提议请求Propose Request给接受者接受者回应的是准备响应Prepare Response和提议响应Propose Response。消息结构如下消息组成准备请求投票编号提议请求投票编号、响应结果、已经接受了的提案准备响应投票编号、租约提议响应投票编号、响应结果提案Proposal由投票编号和租约两者组成租约又由请求者 id希望成为租约持有者的结点和时间间隔 T组成。3.2 接受者状态接受者存储的状态信息只有两项承诺的最高编号接受者忽略投票编号小于该值的消息已经接受的提案最后一个接受的提案投票编号 租约。注意接受者决不重置已承诺的最高投票编号除非在重启的时候。3.3 时间上限与投票编号系统有一个全局已知的最大租约时间 M请求者请求的租约时间间隔T总是满足T M。每个请求者的投票编号是全局唯一且单调递增的。实践中可以用如下字段组合实现可以处理最坏情况请求者 id字段重启计数器字段每次请求者启动时递增并写到可靠的存储中请求次数计数器字段。3.4 租约不变式PaxosLease 保证租约不变式Lease Invariant在任何给定的时间点不会有多于 1 个请求者持有租约。整个算法的正确性证明第 5 节就是围绕这一不变式展开的。4. 基本算法两轮通信获得租约这一节给出从请求者和接受者两个视角出发的算法基本流程。请求者发送准备和提议请求接受者回应准备和提议响应。一切正常时请求者获得租约需要两轮通信。步骤 1请求者广播准备请求一个请求者想要获得租约时长T M。它生成投票编号[request.ballotNumber]然后发送准备请求给多数派的接受者Proposer::Propose() { state.ballotNumber NextBallotNumber() request.type PrepareRequest request.ballotNumber state.ballotNumber Broadcast(request) }步骤 2接受者处理准备请求接受者收到准备请求时检查[request.ballotNumber]是否高于自己在[state.highestPromised]里承诺的本地投票编号最大值。如果请求的投票编号更低可以丢弃消息或发送响应结果为拒绝的准备响应如果相等或更高接受者用接受的回答构造准备响应响应中包含当前已接受的提案[state.acceptedProposal]可能为空然后设置已承诺的最高投票编号为请求的投票编号并把响应发回请求者Acceptor::OnPrepareRequest() { if (request.ballotNumber state.highestPromised) return state.highestPromised request.ballotNumber response.type PrepareRespose response.ballotNumber request.ballotNumber response.acceptedProposal state.acceptedProposal // may be empty Send(response) }步骤 3请求者检查准备响应并广播提议请求者检查从接受者过来的准备响应。如果有多数派的接受者响应的是空的提案意味着他们可以接受新提案请求者就可以提交它自己作为租约的获得者时长T。请求者启动一个超时时间为T秒的定时器发送提议请求其中包含投票编号和租约它自己的请求者 id 和TProposer::OnPrepareResponse() { if (response.ballotNumber ! state.ballotNumber) return // some other proposal if (response.acceptedProposal empty) numOpen if (numOpen majority) return state.timeout T SetTimeout(state.timeout) request.type ProposeRequest request.ballotNumber state.ballotNumber request.proposal.proposerID self.proposerID request.proposal.timeout state.timeout Broadcast(request) } Proposer::OnTimeout() { state.ballotNumber empty // set in Proposer::Propose() state.leaseOwner false // set in Proposer::OnProposeResponse() }步骤 4接受者处理提议请求接受者收到提议请求时同样检查投票编号是否高于承诺的最高值若更低则丢弃或回复拒绝的提议响应。若相等或更高接受者接受这个提议启动超时时间为 T 的超时计时器把它已接受的提案设置为收到的提案若还存着前一个提案则丢弃。接受者用接受的回答构造提议响应其中包含投票编号。超时过期后接受者重置它已接受的提案为空Acceptor::OnProposeRequest() { if (request.ballotNumber state.highestPromised) return state.acceptedProposal request.proposal SetTimeout(state.acceptedProposal.timeout) response.type ProposeResponse response.ballotNumber request.ballotNumber Send(response) } Acceptor::OnTimeout() { state.acceptedProposal empty }步骤 5请求者确认持有租约请求者检查提议响应消息。如果有多数派的接受者响应了接受提案则请求者获得租约直到本地的定时器超时在第 3 步中启动。它收到多数派消息的最后一条的时间点就是它获得租约的时间点此时可以切换内部状态到我持有租约Proposer::OnProposeResponse() { if (response.ballotNumber ! state.ballotNumber) return // some other proposal numAccepted if (numAccepted majority) return state.leaseOwner true // I am the lease owner }配合图 2 的时间流程图可以看到关键时序请求者在发送提议请求之前开启定时器接受者只能在一段时间后开启他们的定时器——准确地说接受者在发送提议响应之前开启定时器。因此如果有多数派的接受者存下了状态并开启了定时器在请求者定时器过期前将不会有其它请求者能得到租约。4.1 重启、相对时间与沉默的租约持有者可以看到接受者没有把自己的状态存到存储上。重启时请求者以空白状态启动。为了保证重启中的结点不会破坏租约不变式结点要在重新加入网络前等待 M 秒——M 是全局已知的最大租约时间请求者请求的租约时长T总是 M秒。另一个重要结论消息传递的都是时间间隔相对时间这导致只有获取了租约的请求者才知道自己有租约。该请求者不能告诉其它结点它获取了租约类似经典 Paxos 的学习消息因为其它结点无法知道学习消息在传输过程中要消耗多少时间。因此每个请求者只有两种租约状态我没有租约我也不知道谁持有租约我持有租约。当然结果可以发出学习消息作为hint提示这可以用于高级应用或探索但超出论文范围。4.2 失败时的重试有可能一个请求者在第 3 步和第 5 步中没有得到多数派接受者的赞同响应。这种情况下请求者可以休眠一会儿再重新从第 1 步用更高的投票编号执行算法。5. 为什么正确租约不变式证明正式地说PaxosLease 保证如果请求者i发出的、投票编号为b、时长T的提案从多数派接受者那里收到了接受消息假定请求者在时间点t~start~ 启动定时器那么没有其它请求者能再接到多数派的接受消息直到t~end~ t~start~ T。证明思路假定请求者p用投票编号b获得了租约——它从多数派接受者那里收到类型为接受的空准备响应在t~start~ 启动定时器在t~acquire~ 从多数派接受者那里收到类型为接受的提议响应从而持有租约直到t~end~。令A₁ 为用空准备响应回应p准备请求的接受者多数派令A₂ 为接受p提案并发送接受提议响应的接受者多数派。任何两个多数派必有交集这是证明的核心支点。第一部分不存在b b的竞争者。在t~acquire~ 到t~end~ 时间内没有其它请求者q能以投票编号b b获得租约。要持有租约q必须得到多数派接受者 *A*₂ 的接受。令a为同时在 *A*₂ 和A₁ 中的接受者。因为b ba必须先接受了q的提案然后才发送准备响应给p。但若a给p发送的是空准备响应它的状态必须为空、它的定时器必须已经过期——即q的定时器过期了因此q已经失去租约。故p与q的租约没有重叠。第二部分不存在b b的竞争者。在t~acquire~ 到t~end~ 时间内没有其它请求者q能以投票编号b b获得租约。要持有租约q必须得到多数派接受者 *A*₁ 给它发送空准备响应。令a为同时在 *A*₁ 和A₂ 中的接受者。因为b ba必须先接受了p的提案然后才发送准备响应给q。但既然a接受了p的提案若它给q发送空准备响应其状态必须是空的、定时器必须已经过期——即p的定时器过期了因此p已失去租约。故p与q的租约没有重叠。两个部分合起来就证明了任何时刻不会有两个请求者同时认为自己是租约持有者——租约不变式成立。6. 活性LivenessPaxos 类型的算法包括 PaxosLease存在动态死锁的可能两个请求者可能连续生成越来越高的投票编号、不断发送准备请求接受者连续增加自己承诺的最高投票编号结果没有请求者能让接受者接受提案。实践中可以通过让请求者在重新执行算法前等待一小段随机的时间来规避。Paxos 类型算法的一个主要优点是没有静态死锁朴素投票算法中存在的那种阻塞因为请求者可以覆盖接受者的状态而算法又保证了多数派不会被覆盖。7. 延长租约在某些场景下一旦请求者持有资源后就希望持续持有而不是只持有原始租约时间。典型场景是分布式系统中租约指定 Master 结点后期望该结点能长时间作为 Master。为了适应这个需求只需要修改请求者的算法在第 3 步中如果多数派响应的是空的提案或已存在的提案即该提案中该请求者的租约还没有过期请求者可以再次提议自己为租约的持有者。这样允许请求者把租约延长O(T)的时间。接受者的算法无需修改。8. 释放租约前面的算法描述中租约都是在一定时间后自动过期的。但在某些场景下尽快释放租约让其它结点获取很重要——典型例子是分布式处理处理进程获得一个资源的租约执行其上的操作然后期望尽快释放租约好让其它处理进程继续获得。为此请求者可以发送一个特定释放消息给接受者消息中包含它要释放租约的投票编号。具体流程发送释放消息之前请求者把内部状态从我持有租约切换到我没有持有租约接受者收到释放消息时检查投票编号是否与已接受的投票编号相同相同则清空自己的状态否则不做任何操作请求者也可以发送释放消息给其它请求者作为 hint提示他们可以去获取租约了。9. 多个资源的租约算法定义的是关于一个资源 R的租约动作。实践中结点往往要处理多个资源例如分布式处理中要用的多个租约。PaxosLease 的做法是为各个资源运行独立的实例不同实例的消息、请求者和接受者状态上都标注资源标识。在论文给出的估算中一个结点同时作为请求者和接受者时每个 PaxosLease 实例消耗的内存不超过约 100 字节因此 1G 内存可以处理约 1 千万个资源的租约。再加上 PaxosLease 不需要硬盘同步和时钟同步该算法可以用于很多需要细粒度锁的场景。10. 参考实现Scalien Keyspace 中的 Master 租约协商在 Scalien 的分布式复制 key-value 存储Keyspace中PaxosLease 被用于Master 的租约协商。Keyspace 作为 PaxosLease 的参考实现包含了很多实践上的优化。由于基于开源AGPL 许可感兴趣的读者可以自由获取 Keyspace 实现。按原译文注释说明原 Scalien 网站已经没有内容了Keyspace 源代码可以在 Scalien 的 GitHub 代码工程中下载。这一落地场景印证了论文的观点PaxosLease 不需要磁盘同步和时钟同步非常适合谁当 Master这类需要轻量、快速、可自动切换的分布式角色协商问题——这正是分布式复制存储、分布式协调服务中最常见的一类需求。11. 宗谱Paxos 家族中 PaxosLease 的位置Leslie Lamport 在1990 年发明了 Paxos 算法但直到1998 年才在论文《The Part-Time Parliament》中发表。这篇论文对很多读者过于极客促使 Lamport 写了第二篇论文《Paxos Made Simple》本仓库有完整中文译稿 paxos-made-simple/README.rst其中推导了从 P1 到 P2 再到 P2^c 的一致性条件正是理解 PaxosLease 两阶段协议的理论基础。Paxos 通过引入准备和提议两个阶段、并让接受者在响应消息前把状态写入稳定存储解决了分布式一致性问题多轮 Paxos 可以顺序运行以协调复制状态机的状态转换。论文《Paxos Made Live - An Engineering Perspective》和《The Chubby Lock Service for Loosely-Coupled Distributed Systems》中描述的 Google 内部分布式实现栈使用了 Paxos这让 Paxos 流行起来。在 Google 的 Chubby 中多轮顺序执行 Paxos 以达成复制数据库下次写操作的一致性提供了思考复制状态机的另一种方法。《FaTLease: Scalable Fault-Tolerant Lease Negotiation with Paxos》描述的 FatLease 解决了和 PaxosLease 一样的问题但结构更复杂——它模仿了 Google 论文中的多轮 Paxos而不是 PaxosLease 所用的简单接受者状态超时另外 FatLease 需要结点同步时钟这一点使它在现实世界使用中没有吸引力。PaxosLease 的灵感正来自于 FatLease并解决了上述缺点。本仓库 README.md 将 paxoslease/README.rst 评价为可以说是最简单且可以实际使用的 Paxos 算法变种——这与其论文中的自我定位一致在租约这个特定问题上用接受者超时清空状态替代持久化用租约的临时性替代连续运行的多轮 Paxos既保留了 Paxos 的多数派与两阶段正确性内核又换来了无需写盘、无需时钟同步的极简实现。12. 小结PaxosLease 的核心价值可以概括为三点正确性继承 Paxos准备/提议两阶段 多数派交集保证了任何时刻至多一个租约持有者这一租约不变式并覆盖停止重启、网络分割、消息丢失乱序与延时四类失效实现大幅简化接受者无需写盘超时即清空状态、无需时钟同步全用相对时间间隔、无需连续运行多轮 Paxos利用租约临时性实战能力强支持延长租约O(T) 时间续约、主动释放租约释放消息 hint、多资源扩展每实例约 100 字节内存1G 内存可承载约千万级资源租约并有 Keyspace 这一 AGPL 开源参考实现验证了 Master 租约协商场景。如果你希望进一步夯实 Paxos 本身的数学基础可以继续阅读本仓库的姊妹译稿 paxos-made-simple/README.rst若要了解租约思想在真实工业系统如 Kafka 日志系统中的统一抽象应用还可参考 log-what-every-software-engineer-should-know-about-real-time-datas-unifying/README.md。参考文献原论文书目L. Lamport,The Part-Time Parliament, ACM Transactions on Computer Systems 16, 2 (May 1998), 133-169.L. Lamport,Paxos Made Simple, ACM SIGACT News 32, 4 (Dec. 2001), 18-25.T. Chandra, R. Griesemer, J. Redstone,Paxos Made Live - An Engineering Perspective, PODC 07: 26th ACM Symposium on Principles of Distributed Computing.M. Burrows,The Chubby Lock Service for Loosely-Coupled Distributed Systems, OSDI06: Seventh Symposium on Operating System Design and Implementation.F. Hupfeld et al.,FaTLease: Scalable Fault-Tolerant Lease Negotiation with Paxos, HPDC08, June 23-27, 2008, Boston, Massachusetts, USA.AGPL LicenseKeyspace 参考实现所采用的开源许可。说明本文基于本仓库中 paxoslease/README.rst 的中文译稿论文原名《PaxosLease: Diskless Paxos for Leases》作者 Marton Trencseni、Attila Gazso2012-09-19中译 2013-01-04整理展开文中伪代码与数据均为论文原文内容。赞分享文档教程知识库【免费下载链接】translations Chinese translations for classic software development resources项目地址https://gitcode.com/gh_mirrors/tr/translations点击查看免费下载相关推荐如何为Nimbus配置Google Drive、OneDrive等OAuth集成如何为Nimbus配置Google Drive、OneDrive等OAuth集成 Nimbus作为一款面向未来的文件存储解决方案The future of f使用Matcha-gtk-theme打造专业开发环境程序员桌面美化的10个技巧使用Matcha gtk theme打造专业开发环境程序员桌面美化的10个技巧 想要为你的Linux桌面打造一个既美观又高效的开发环境吗Matcha gtkFastViT T8未来路线图苹果视觉AI技术发展趋势分析FastViT T8未来路线图苹果视觉AI技术发展趋势分析 FastViT T8是苹果公司推出的一款高效视觉AI模型作为HuggingFace镜像项目中的重上一篇Academic Research Skills 27 种模式选型指南问 3 个问题3 分钟选对下一篇AI-Research-SKILLs 系统论文会议指南OSDI/NSDI/ASPLOS/SOSP 投稿要点、格式规范与截稿日程全解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 PaxosLease 算法详解：无需写盘与时钟同步的分布式租约协商（经典论文中文译读）
文档教程知识库【免费下载链接】translations Chinese translations for classic software development resources项目地址https://gitcode.com/gh_mirrors/tr/translations点击查看免费下载PaxosLease 是 Leslie Lamport 的 Paxos 算法面向**租约Lease**问题的自然特化变种它用经典的两阶段准备/提议协议协商谁持有租约却彻底去掉了 Paxos 中接受者响应前写盘的硬性要求也完全不需要结点间时钟同步。本文以本仓库 translations 中的经典论文译稿 paxoslease/README.rst 为主体展开读完你将掌握租约与锁的本质差异、请求者/接受者两轮通信获取租约的完整算法与伪代码、租约不变式的证明思路以及延长租约、释放租约、多资源租约等实战扩展和 Keyspace 参考实现的落地方案。1. 从锁到租约问题的背景在并发编程中**锁Lock**是进程用来同步共享资源访问的基本原语。但在锁以不设置过期时间的方式分配、且没有监督进程的系统中一旦锁的持有者在释放锁之前失效Failure其它进程就可能永久阻塞。在高可用系统中我们期望避免单点失效导致整个系统阻塞而且重启一个失效的分布式系统比重启一个多线程程序要困难得多。因此在分布式系统中租约Lease取代锁以避免饿死的情况。租约就是有过期时间的锁如果锁的持有者失效了或是与其它结点断开连接它的租约会自动过期其它结点就可以重新获得租约。论文对系统做了如下基本假设系统由一组**请求者Proposer和一组接受者Acceptor**组成各自运行各自的算法系统没有拜占庭问题——结点之间不会通过不遵守各自算法来作弊也不会被 Hack接受者的数目是固定不变的。1.1 朴素的多数派投票算法为什么不行一个朴素的多数派投票式算法可以正确地解决分布式租约问题——这里正确的意思是任何时候租约不会被多于一个结点持有。但这个简单算法在存在多个请求者时会频繁阻塞因此需要一个更成熟的方案。朴素算法的流程如下请求者启动一个本地超时计时器超时时间 T 秒然后向接受者发送请求时长为 T 的租约接受者收到请求后启动一个时长为 T 秒的定时器然后发送接受消息给请求者超时之后接受者清除自己的状态如果接受者收到请求但自己的状态不是空则接受者不回应或发送拒绝消息为确保任何时间只有一个请求者能获得租约请求者必须收到多数派接受者的接受消息这样它获取租约直到本地定时器超时。当有多个请求者时很可能没有请求者能得到多数派请求者会一直互相阻塞。例如有 3 个请求者 1、2、3 和 3 个接受者 A、B、C如果分布状态是A 接受 1 的请求、B 接受 2 的请求、C 接受 3 的请求那么没有一个请求者得到多数派的接受。系统必须等到超时过期、接受者清空自己的状态请求者再重试——但很可能再次阻塞。论文给出的解决方法是采用 Paxos 方案引入**准备Prepare和提议Propose**两个阶段从而完全避免这类阻塞问题。另一个替代思路是让系统阻塞但引入一个撤销机制让请求者撤销自己的请求从而使某个其它请求者获得租约。2. 为什么是无盘的 PaxosPaxos 解决的是复制状态机Replicated State Machine的一致性问题每个结点有一个本地状态机拷贝希望在下一个状态转换上结点间达成一致。Paxos 是基于多数派的算法它假设多数派结点没有宕机且彼此可以通信。Paxos 的一致性处理发生在一个状态转换上因此在实践中需要逐次运行多个 Paxos 实例来协商出一序列的状态转换。经典 Paxos 中接受者在发送响应之前要先把自己的状态记录到盘上以保证一旦一个值状态转换被选定之后一直选定该值——即不管出现何种错误所有状态机都经历相同的状态转换序列。这正是 paxos-made-simple/README.rst 译稿中所述Acceptor 在真正送出响应之前会将记录写入可靠性存储设备的要求。与经典 Paxos 不同PaxosLease 的接受者从不把状态写入存储租约具有临时性超时即可清空状态不需要持久化承诺。同时对比此前基于 Paxos 的分布式租约算法如 FatLeasePaxosLease 有两点关键简化不做任何时钟同步假设不对结点的本地时钟做时间同步假设也不需要全局同步避免连续运行 Paxos 实例FatLease 为了租约命令连续地运行 Paxos 实例而 PaxosLease 利用租约的临时性完全避免了这样的复杂性是一个更简单和优雅的算法。PaxosLease 处理的是一个特殊的复制状态机形式为为了获得租约请求者结点提交的值是结点 i 持有租约在租约过期后该值自动返回没有结点持有租约如图 1 状态机所示请求者也可以在前一次租约过期之前再次提交结点 i 持有租约值来延长租约或在过期之前释放租约可选操作。类似于 PaxosPaxosLease 本质上处理了所有相关的失效情况结点停止和重启网络分割不通消息丢失和乱序传输中的消息延时。3. 核心定义与数据结构一个 PaxosLease 单元由请求者和接受者组成假设有n个接受者和任意个请求者。实践中结点常常同时扮演请求者和接受者的角色但这是实现问题不影响算法讨论。3.1 四类消息请求者发送准备请求Prepare Request和提议请求Propose Request给接受者接受者回应的是准备响应Prepare Response和提议响应Propose Response。消息结构如下消息组成准备请求投票编号提议请求投票编号、响应结果、已经接受了的提案准备响应投票编号、租约提议响应投票编号、响应结果提案Proposal由投票编号和租约两者组成租约又由请求者 id希望成为租约持有者的结点和时间间隔 T组成。3.2 接受者状态接受者存储的状态信息只有两项承诺的最高编号接受者忽略投票编号小于该值的消息已经接受的提案最后一个接受的提案投票编号 租约。注意接受者决不重置已承诺的最高投票编号除非在重启的时候。3.3 时间上限与投票编号系统有一个全局已知的最大租约时间 M请求者请求的租约时间间隔T总是满足T M。每个请求者的投票编号是全局唯一且单调递增的。实践中可以用如下字段组合实现可以处理最坏情况请求者 id字段重启计数器字段每次请求者启动时递增并写到可靠的存储中请求次数计数器字段。3.4 租约不变式PaxosLease 保证租约不变式Lease Invariant在任何给定的时间点不会有多于 1 个请求者持有租约。整个算法的正确性证明第 5 节就是围绕这一不变式展开的。4. 基本算法两轮通信获得租约这一节给出从请求者和接受者两个视角出发的算法基本流程。请求者发送准备和提议请求接受者回应准备和提议响应。一切正常时请求者获得租约需要两轮通信。步骤 1请求者广播准备请求一个请求者想要获得租约时长T M。它生成投票编号[request.ballotNumber]然后发送准备请求给多数派的接受者Proposer::Propose() { state.ballotNumber NextBallotNumber() request.type PrepareRequest request.ballotNumber state.ballotNumber Broadcast(request) }步骤 2接受者处理准备请求接受者收到准备请求时检查[request.ballotNumber]是否高于自己在[state.highestPromised]里承诺的本地投票编号最大值。如果请求的投票编号更低可以丢弃消息或发送响应结果为拒绝的准备响应如果相等或更高接受者用接受的回答构造准备响应响应中包含当前已接受的提案[state.acceptedProposal]可能为空然后设置已承诺的最高投票编号为请求的投票编号并把响应发回请求者Acceptor::OnPrepareRequest() { if (request.ballotNumber state.highestPromised) return state.highestPromised request.ballotNumber response.type PrepareRespose response.ballotNumber request.ballotNumber response.acceptedProposal state.acceptedProposal // may be empty Send(response) }步骤 3请求者检查准备响应并广播提议请求者检查从接受者过来的准备响应。如果有多数派的接受者响应的是空的提案意味着他们可以接受新提案请求者就可以提交它自己作为租约的获得者时长T。请求者启动一个超时时间为T秒的定时器发送提议请求其中包含投票编号和租约它自己的请求者 id 和TProposer::OnPrepareResponse() { if (response.ballotNumber ! state.ballotNumber) return // some other proposal if (response.acceptedProposal empty) numOpen if (numOpen majority) return state.timeout T SetTimeout(state.timeout) request.type ProposeRequest request.ballotNumber state.ballotNumber request.proposal.proposerID self.proposerID request.proposal.timeout state.timeout Broadcast(request) } Proposer::OnTimeout() { state.ballotNumber empty // set in Proposer::Propose() state.leaseOwner false // set in Proposer::OnProposeResponse() }步骤 4接受者处理提议请求接受者收到提议请求时同样检查投票编号是否高于承诺的最高值若更低则丢弃或回复拒绝的提议响应。若相等或更高接受者接受这个提议启动超时时间为 T 的超时计时器把它已接受的提案设置为收到的提案若还存着前一个提案则丢弃。接受者用接受的回答构造提议响应其中包含投票编号。超时过期后接受者重置它已接受的提案为空Acceptor::OnProposeRequest() { if (request.ballotNumber state.highestPromised) return state.acceptedProposal request.proposal SetTimeout(state.acceptedProposal.timeout) response.type ProposeResponse response.ballotNumber request.ballotNumber Send(response) } Acceptor::OnTimeout() { state.acceptedProposal empty }步骤 5请求者确认持有租约请求者检查提议响应消息。如果有多数派的接受者响应了接受提案则请求者获得租约直到本地的定时器超时在第 3 步中启动。它收到多数派消息的最后一条的时间点就是它获得租约的时间点此时可以切换内部状态到我持有租约Proposer::OnProposeResponse() { if (response.ballotNumber ! state.ballotNumber) return // some other proposal numAccepted if (numAccepted majority) return state.leaseOwner true // I am the lease owner }配合图 2 的时间流程图可以看到关键时序请求者在发送提议请求之前开启定时器接受者只能在一段时间后开启他们的定时器——准确地说接受者在发送提议响应之前开启定时器。因此如果有多数派的接受者存下了状态并开启了定时器在请求者定时器过期前将不会有其它请求者能得到租约。4.1 重启、相对时间与沉默的租约持有者可以看到接受者没有把自己的状态存到存储上。重启时请求者以空白状态启动。为了保证重启中的结点不会破坏租约不变式结点要在重新加入网络前等待 M 秒——M 是全局已知的最大租约时间请求者请求的租约时长T总是 M秒。另一个重要结论消息传递的都是时间间隔相对时间这导致只有获取了租约的请求者才知道自己有租约。该请求者不能告诉其它结点它获取了租约类似经典 Paxos 的学习消息因为其它结点无法知道学习消息在传输过程中要消耗多少时间。因此每个请求者只有两种租约状态我没有租约我也不知道谁持有租约我持有租约。当然结果可以发出学习消息作为hint提示这可以用于高级应用或探索但超出论文范围。4.2 失败时的重试有可能一个请求者在第 3 步和第 5 步中没有得到多数派接受者的赞同响应。这种情况下请求者可以休眠一会儿再重新从第 1 步用更高的投票编号执行算法。5. 为什么正确租约不变式证明正式地说PaxosLease 保证如果请求者i发出的、投票编号为b、时长T的提案从多数派接受者那里收到了接受消息假定请求者在时间点t~start~ 启动定时器那么没有其它请求者能再接到多数派的接受消息直到t~end~ t~start~ T。证明思路假定请求者p用投票编号b获得了租约——它从多数派接受者那里收到类型为接受的空准备响应在t~start~ 启动定时器在t~acquire~ 从多数派接受者那里收到类型为接受的提议响应从而持有租约直到t~end~。令A₁ 为用空准备响应回应p准备请求的接受者多数派令A₂ 为接受p提案并发送接受提议响应的接受者多数派。任何两个多数派必有交集这是证明的核心支点。第一部分不存在b b的竞争者。在t~acquire~ 到t~end~ 时间内没有其它请求者q能以投票编号b b获得租约。要持有租约q必须得到多数派接受者 *A*₂ 的接受。令a为同时在 *A*₂ 和A₁ 中的接受者。因为b ba必须先接受了q的提案然后才发送准备响应给p。但若a给p发送的是空准备响应它的状态必须为空、它的定时器必须已经过期——即q的定时器过期了因此q已经失去租约。故p与q的租约没有重叠。第二部分不存在b b的竞争者。在t~acquire~ 到t~end~ 时间内没有其它请求者q能以投票编号b b获得租约。要持有租约q必须得到多数派接受者 *A*₁ 给它发送空准备响应。令a为同时在 *A*₁ 和A₂ 中的接受者。因为b ba必须先接受了p的提案然后才发送准备响应给q。但既然a接受了p的提案若它给q发送空准备响应其状态必须是空的、定时器必须已经过期——即p的定时器过期了因此p已失去租约。故p与q的租约没有重叠。两个部分合起来就证明了任何时刻不会有两个请求者同时认为自己是租约持有者——租约不变式成立。6. 活性LivenessPaxos 类型的算法包括 PaxosLease存在动态死锁的可能两个请求者可能连续生成越来越高的投票编号、不断发送准备请求接受者连续增加自己承诺的最高投票编号结果没有请求者能让接受者接受提案。实践中可以通过让请求者在重新执行算法前等待一小段随机的时间来规避。Paxos 类型算法的一个主要优点是没有静态死锁朴素投票算法中存在的那种阻塞因为请求者可以覆盖接受者的状态而算法又保证了多数派不会被覆盖。7. 延长租约在某些场景下一旦请求者持有资源后就希望持续持有而不是只持有原始租约时间。典型场景是分布式系统中租约指定 Master 结点后期望该结点能长时间作为 Master。为了适应这个需求只需要修改请求者的算法在第 3 步中如果多数派响应的是空的提案或已存在的提案即该提案中该请求者的租约还没有过期请求者可以再次提议自己为租约的持有者。这样允许请求者把租约延长O(T)的时间。接受者的算法无需修改。8. 释放租约前面的算法描述中租约都是在一定时间后自动过期的。但在某些场景下尽快释放租约让其它结点获取很重要——典型例子是分布式处理处理进程获得一个资源的租约执行其上的操作然后期望尽快释放租约好让其它处理进程继续获得。为此请求者可以发送一个特定释放消息给接受者消息中包含它要释放租约的投票编号。具体流程发送释放消息之前请求者把内部状态从我持有租约切换到我没有持有租约接受者收到释放消息时检查投票编号是否与已接受的投票编号相同相同则清空自己的状态否则不做任何操作请求者也可以发送释放消息给其它请求者作为 hint提示他们可以去获取租约了。9. 多个资源的租约算法定义的是关于一个资源 R的租约动作。实践中结点往往要处理多个资源例如分布式处理中要用的多个租约。PaxosLease 的做法是为各个资源运行独立的实例不同实例的消息、请求者和接受者状态上都标注资源标识。在论文给出的估算中一个结点同时作为请求者和接受者时每个 PaxosLease 实例消耗的内存不超过约 100 字节因此 1G 内存可以处理约 1 千万个资源的租约。再加上 PaxosLease 不需要硬盘同步和时钟同步该算法可以用于很多需要细粒度锁的场景。10. 参考实现Scalien Keyspace 中的 Master 租约协商在 Scalien 的分布式复制 key-value 存储Keyspace中PaxosLease 被用于Master 的租约协商。Keyspace 作为 PaxosLease 的参考实现包含了很多实践上的优化。由于基于开源AGPL 许可感兴趣的读者可以自由获取 Keyspace 实现。按原译文注释说明原 Scalien 网站已经没有内容了Keyspace 源代码可以在 Scalien 的 GitHub 代码工程中下载。这一落地场景印证了论文的观点PaxosLease 不需要磁盘同步和时钟同步非常适合谁当 Master这类需要轻量、快速、可自动切换的分布式角色协商问题——这正是分布式复制存储、分布式协调服务中最常见的一类需求。11. 宗谱Paxos 家族中 PaxosLease 的位置Leslie Lamport 在1990 年发明了 Paxos 算法但直到1998 年才在论文《The Part-Time Parliament》中发表。这篇论文对很多读者过于极客促使 Lamport 写了第二篇论文《Paxos Made Simple》本仓库有完整中文译稿 paxos-made-simple/README.rst其中推导了从 P1 到 P2 再到 P2^c 的一致性条件正是理解 PaxosLease 两阶段协议的理论基础。Paxos 通过引入准备和提议两个阶段、并让接受者在响应消息前把状态写入稳定存储解决了分布式一致性问题多轮 Paxos 可以顺序运行以协调复制状态机的状态转换。论文《Paxos Made Live - An Engineering Perspective》和《The Chubby Lock Service for Loosely-Coupled Distributed Systems》中描述的 Google 内部分布式实现栈使用了 Paxos这让 Paxos 流行起来。在 Google 的 Chubby 中多轮顺序执行 Paxos 以达成复制数据库下次写操作的一致性提供了思考复制状态机的另一种方法。《FaTLease: Scalable Fault-Tolerant Lease Negotiation with Paxos》描述的 FatLease 解决了和 PaxosLease 一样的问题但结构更复杂——它模仿了 Google 论文中的多轮 Paxos而不是 PaxosLease 所用的简单接受者状态超时另外 FatLease 需要结点同步时钟这一点使它在现实世界使用中没有吸引力。PaxosLease 的灵感正来自于 FatLease并解决了上述缺点。本仓库 README.md 将 paxoslease/README.rst 评价为可以说是最简单且可以实际使用的 Paxos 算法变种——这与其论文中的自我定位一致在租约这个特定问题上用接受者超时清空状态替代持久化用租约的临时性替代连续运行的多轮 Paxos既保留了 Paxos 的多数派与两阶段正确性内核又换来了无需写盘、无需时钟同步的极简实现。12. 小结PaxosLease 的核心价值可以概括为三点正确性继承 Paxos准备/提议两阶段 多数派交集保证了任何时刻至多一个租约持有者这一租约不变式并覆盖停止重启、网络分割、消息丢失乱序与延时四类失效实现大幅简化接受者无需写盘超时即清空状态、无需时钟同步全用相对时间间隔、无需连续运行多轮 Paxos利用租约临时性实战能力强支持延长租约O(T) 时间续约、主动释放租约释放消息 hint、多资源扩展每实例约 100 字节内存1G 内存可承载约千万级资源租约并有 Keyspace 这一 AGPL 开源参考实现验证了 Master 租约协商场景。如果你希望进一步夯实 Paxos 本身的数学基础可以继续阅读本仓库的姊妹译稿 paxos-made-simple/README.rst若要了解租约思想在真实工业系统如 Kafka 日志系统中的统一抽象应用还可参考 log-what-every-software-engineer-should-know-about-real-time-datas-unifying/README.md。参考文献原论文书目L. Lamport,The Part-Time Parliament, ACM Transactions on Computer Systems 16, 2 (May 1998), 133-169.L. Lamport,Paxos Made Simple, ACM SIGACT News 32, 4 (Dec. 2001), 18-25.T. Chandra, R. Griesemer, J. Redstone,Paxos Made Live - An Engineering Perspective, PODC 07: 26th ACM Symposium on Principles of Distributed Computing.M. Burrows,The Chubby Lock Service for Loosely-Coupled Distributed Systems, OSDI06: Seventh Symposium on Operating System Design and Implementation.F. Hupfeld et al.,FaTLease: Scalable Fault-Tolerant Lease Negotiation with Paxos, HPDC08, June 23-27, 2008, Boston, Massachusetts, USA.AGPL LicenseKeyspace 参考实现所采用的开源许可。说明本文基于本仓库中 paxoslease/README.rst 的中文译稿论文原名《PaxosLease: Diskless Paxos for Leases》作者 Marton Trencseni、Attila Gazso2012-09-19中译 2013-01-04整理展开文中伪代码与数据均为论文原文内容。赞分享文档教程知识库【免费下载链接】translations Chinese translations for classic software development resources项目地址https://gitcode.com/gh_mirrors/tr/translations点击查看免费下载相关推荐如何为Nimbus配置Google Drive、OneDrive等OAuth集成如何为Nimbus配置Google Drive、OneDrive等OAuth集成 Nimbus作为一款面向未来的文件存储解决方案The future of f使用Matcha-gtk-theme打造专业开发环境程序员桌面美化的10个技巧使用Matcha gtk theme打造专业开发环境程序员桌面美化的10个技巧 想要为你的Linux桌面打造一个既美观又高效的开发环境吗Matcha gtkFastViT T8未来路线图苹果视觉AI技术发展趋势分析FastViT T8未来路线图苹果视觉AI技术发展趋势分析 FastViT T8是苹果公司推出的一款高效视觉AI模型作为HuggingFace镜像项目中的重上一篇Academic Research Skills 27 种模式选型指南问 3 个问题3 分钟选对下一篇AI-Research-SKILLs 系统论文会议指南OSDI/NSDI/ASPLOS/SOSP 投稿要点、格式规范与截稿日程全解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考