“有界漂移租约给出一个较小而完整的时间证明:单个诚实授予者、双方速率界和从请求发送起计算的保守截止,使持有者的有效区间早于授予者改授。该构造还未证明本页Raft的选举、提交或提前移交,因此不能…”
形式陈述
权限有期限,两个钟各自计时
租约把某项权限授给持有者一段有限时间。本页采用一个诚实、串行处理的授予者S,为一个资源每次只授给一个客户端;它不在自己记录的期限之前把同项权限改授别人。使用请求与回复取得授权,消息可延迟或丢失,双方读不到对方当前内存;本页不实现授予服务的复制和崩溃恢复。[1, §§2,5]
真实时间用t表示,仅供证明。客户端持续时间钟C和授予者钟S满足,对任意t₂≥t₁,
授予者有同形条件,参数ρ_S;0≤ρ_C,ρ_S<1。这个条件允许速率随时间变化,但禁止回拨,也禁止长时间停钟。两端起始读数可以任意偏离,不要求对齐绝对日期。
客户端在发送本次唯一请求q的时刻t₀记录c₀=C(t₀)。授予者在收到后某个时刻g≥t₀原子检查资源已可授予,并记录到期读数E=S(g)+L,L>0。它只有在S(t)≥E时才可重新授予。回复绑定资源、客户端、q和本次L;不存在未声明的提前撤销或续期。
客户端从c₀起计算自己的截止读数
收到有效匹配回复且当前C(t)<D,才能使用本次权限;C(t)≥D立即视为失效。到达等号也不能再使用,不从收到回复的读数重新启动完整期限。
直觉
最危险的是授予者快、持有者慢
授予者钟越快,L个单位越早走完;客户端钟越慢,它眼中的有效期越晚结束。所以安全缩短比例必须同时考虑最快的S和最慢的C。只知道两端“误差都不大”,却不把误差方向代入计算,会漏掉两者相向偏离的情况。
网络延迟会吃掉客户端能用的时间,但不应延长它。请求发送先于授予,从更早的t₀启动保守计时,会让客户端最多早停一会儿。若回复迟到到没有剩余时间,结果就是本次租约没有可用窗口;安全性不保证每次申请都能成功使用。
两条不等式给出权限不重叠
设当前t≥t₀且C(t)<D。用客户端速率下界,
授予者要积累L个单位,按其速率上界,到期真实时刻e至少是g+L/(1+ρ_S)。再用g≥t₀,得到客户端声称有效的每个时刻都满足t<e。S此时不会把权限交给另一人;故不同客户端的有效持有区间不相交。
这份证明不使用请求和回复延迟的已知上界。失联客户端只会失去后续可用窗口,不能逼授予者提前交接。活性则还取决于消息最终交付、请求处理和授予者继续运行。
例子与边界
11个授予单位只给9个客户端单位
取ρ_C=ρ_S=1/10、L=11,安全客户端时长是11×(9/10)/(11/10)=9。具体选C(t)=100+0.9t,S(t)=700+1.1t:
| 事件 | 真实时刻 | 客户端读数 | 授予者读数 |
|---|---|---|---|
| 发送请求,记c₀=100 | 0 | 100 | 700 |
| 授予,记E=713.2 | 2 | 101.8 | 702.2 |
| 正常回复到达 | 4 | 103.6 | 704.4 |
| 客户端到D=109,停止 | 10 | 109 | 711 |
| 授予者到E,可以改授 | 12 | 110.8 | 713.2 |
实际可用窗口从回复4到客户端到期10,不是从0就有权限;发送请求本身没有授权。两端失效之间留出两单位空档,这是请求在途时间带来的保守余量。
若正常回复在4到达后重新计9个客户端单位,错误截止是C(4)+9=112.6,对应真实14。授予者12已能换人,12到14之间两人都可能自认有效。若完全不缩短,从c₀直接加11,则慢客户端到110/9≈12.22才失效,同样越过真实12。
迟到回复和旧请求不能复活权限
保持授予发生在2,但回复改到11才送达。此时C(11)=109.9≥109,客户端应拒绝把它设为有效,尽管授予者还要到12才到期。把q与c₀保存在一起,才能把收到的L代入本次原始计时起点;只记录最后收到回复的时刻不够。
旧q的重复回复也不能开启新期限。最简单接口每次申请使用新身份、同一时刻至多一个未决申请;成功或过期后将该q退休,重复回复忽略。本页没有把同一客户端的续租、多个并行申请或提前释放默认为已支持;增加这些操作时,要另证旧回复不能恢复已交出的权限。
暂停的对象是进程,还是时钟
客户端线程从9暂停到13,只要C仍按合同走,恢复后读到111.7,便知道D已过,不能继续受租约保护的本地动作。这个保证要求每次需要权限的原子动作在当时检查有效性;不是启动一个任意长任务后便永久免检。
若虚拟机暂停时连用于租约的钟也停止,真实13的C可能还停在108.1,客户端会误以为有效。这违反了速率下界。某个API叫“monotonic”只表示不倒退,未必证明在所需暂停类型下持续以足够速率前进;实现必须兑现本页的具体不等式。
推论与应用
本地许可不能收回在途外部写
即使在真实9读C=108.1并通过检查,客户端也可能随后暂停,或让已发消息到13才到达存储。授予者12已换人,旧写仍可能产生效果。刚才证明的是检查时刻的权限,不是任意延迟操作的效果时刻。
对需要保护的外部资源,可以调用资源端fencing接口:新持有者先完成Activate(e)并收到确认,资源在同一原子步骤检查代际和业务修改,随后拒绝旧代请求。比如新42已激活,迟到41应被拒绝;若激活还未到资源,不能把协调端的发放时刻当成资源已撤销旧代的证明。
租约证明和这一资源接口各自有责任。缓存本地读取可以在受保护的原子读取点检查期限;跨进程写、长时间工作和多分片效果则须另外安排提交屏障。仅在客户端“再查一次”无法关闭检查和外部效果之间的时间窗口。
失败模型要覆盖授予者的记忆
本页授予者不崩溃。如果它重启后忘记尚未到期的E并立即授予另一人,旧客户端仍可能有效,证明前提就已失效。持久保存剩余权限、可信持续时间、恢复等待或复制协议可以形成不同解决方案,但不能只把内存owner清空就宣告恢复完成。[1, §2, pp.203;§5, pp.207–208]
每个资源记录owner、请求身份和截止读数,核心状态为常数个字段;每次授予、匹配回复或有效性检查为常数次比较和有理算术。真实服务还要为串行化、消息、身份验证及所选持久化支付成本。下载器的多资源字典访问按期望常数计,大整数和Fraction运算另计位成本;保存完整执行日志随事件数增长。
在时钟证书终结任务中,提交双方期限及t<e证明,重放迟到回复和暂停,再给出有无资源代际检查的两份外部效果记录。
参考资料
- Cary G. Gray、David R. Cheriton,Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency,SOSP1989,pp.202–210;§2定义有限期权限与恢复等待,§5(pp.207–208)分析快授予者钟、慢客户端钟及有界漂移。本文选单资源独占接口,并自行给出从请求发送起计时的双速率不等式,不冒称原文就是同一授予状态机。
- Mike Burrows,The Chubby lock service for loosely-coupled distributed systems,OSDI2006,§2.4的迟到请求、sequencer与接收方检查;本页借用旧fencing接口处理外部效果,而非将时钟条件当作接收方验证的替代品。