对于leases机制的一些思考

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
本作品 (李兆龙 博文, 由 李兆龙 创作)，由 李兆龙 确认，转载请注明版权。

文章目录

• • 引言
  • leases与缓存一致性
  • leases机制描述
  • leases时延分析
  • 对分布式锁的思考
  • 总结

引言

缓存是计算机科学中应用非常广泛的一种技术，其可以在大幅度的降低读取操作的开销以及服务器的负载，对于网络流量（总线通信开销）的减小也有不小的好处（可以利用局部性），所以在操作系统，以及分布式系统中出现了大量它的身影。但是缓存的出现也引入了一个问题，就是缓存一致性（Cache coherence），维基对缓存一致性的描述如下：

In computer architecture, cache coherence is the uniformity of shared resource data that ends up stored in multiple local caches. When clients in a system maintain caches of a common memory resource, problems may arise with incoherent data, which is particularly the case with CPUs in a multiprocessing system.
在计算机体系结构中，缓存一致性是最终存储在多个本地缓存中的共享资源数据的一致性。当系统中的客户机维护公共内存资源的缓存时，可能会出现数据不一致的问题，尤其是多处理系统中的cpu。

更为精确的定义可参考[1]的Definition段。

举个简单的例子，假设上方为clientA，CacheA，下方为clientB，CacheB，如果CacheA被修改以后CacheB被同步修改之前，clientB此时访问CacheB，就会造成clientB的脏读，因为clientB读到了一个过期的数据。

而缓存一致性描述的就是如何保证多个独立的进程分别修改了某个共享视图后在所有其它进程中能看到一致性的修改结果。

本文所聊的leases机制就是一种缓存一致性的解决方案。这篇文章是阅读了[2]以后的一些理解与总结。

leases与缓存一致性

首先在paper的文首就把lease的作用写的很清楚：

Leases are proposed as a time-based mechanism that provides efficient consistent access to cached data in distributed systems. Non-Byzantine failures affect performance, not correctness.
leases作为一种基于时间的机制，为分布式系统中的缓存数据提供高效的一致性访问。通过使用它，可以确保非拜占庭式的失效只会影响到性能，但是不会破坏正确性。

事实上在[5]和[6]这两篇文章中我都曾描述过这种机制，其实说“描述这种机制”有些不贴切，应该说描述过这种行为，但是当时我并没有意识到写的那些文字其实就是一个简单的leases机制。后悔晚生三十年啊哈哈哈。

文中提到其实缓存一致性在shared memory multiprocessor architectures中其实已经被深入的研究过了，因为我们知道目前CPU内部多核之间其实是拥有不同的L1，L2级别的cache的，多CPU之间的L3级别cache也是不共享的，那么一个核修改数据以后显然需要让全部的核看到最新的数据，此时显然也需要缓存一致性（也可能出现脏读，但那是内存模型讨论的问题[3]）。这里比较经典的当属MESI协议，Intel的处理器使用的从MESI中演化出的MESIF协议和AMD使用MOESI协议。这些协议我们在这里不在细说，但是本质都是基于总线进行消息通信的一个状态机。

在分布式系统中对于缓存一致性的研究显然很难参考以上的案例，因为前面说的那三种一切的大前提是拥有一个系统总线提供的可靠的同步广播通信方式。而在分布式系统中通信是不可信的，可能出现宕机，网络波动，网络分区等无法预知的事件。此时很好想象，最简单粗暴的方法就是轮询，即每一次操作都去访问主服务器，这样一定可以保证数据的一致性，但是性能一定会非常差。

leases可以很好的解决此类问题。

leases机制描述

事实上leases本身可以理解成一个租约（很多文章中也这么翻译），其实就是在一定的时间期限内在某些方面的权利的租约。放在分布式系统中，也就是描述某个客户端持有某个leases的某个时间段内的的读写权限。

leases机制要求每一个读操作和写操作之前必须获取一个针对于所操作数据的租约。当数据从服务端(数据主版本存储处)获取后，服务端也会返回一个租约来保证在租约期限内该数据不会被任何客户端修改，当持有租约时读操作就可以不必经过服务端，直接返回客户端的副本就可以了，此时保证这一定是最新的数据，因为写操作成功前必须延迟直到所有持有此租约的客户端的同意，反之，如果一个客户端持有租约时没有收到修改请求，那它保存的数据副本一定是最新的（租约未超时）。

当然从以上我们可以看出一个问题，就是所有的写操作必须经过所有持有此数据租约的客户端同意，倘若有一个客户端出现意外，那么这个写操作只能阻塞，直到故障恢复或者那个故障的客户端的租约过期。这也是我们前面提到的在非拜占庭式失效的情况下只会影响到性能，但是不会破坏正确性。

还有三个问题对整体的性能也有影响，一个是false sharing（不是cache line造成的那个），一个是续约开销，另一个是存储开销。

在这篇paper中false sharing描述的其实是一个客户端已经不再需要读取数据，但在其租约过期前，任何的修改操作仍然需要征求它的同意，这会增加客户端的请求延时及租约持有者及服务端的负载，滑稽的是如果没有租约此时的正确性也是可以保证的。所有如果有一种极端的情况，即某客户端在另一个客户端修改文件之前根本不会访问它，那么此时租约期限应该设置为0，当然这揭示出我们应该对任务进行评估，以分配不同的leases时间，而不应该所有的租约时间都相同。

还有就是续约开销。当某个客户端持有缓存时，如果后面有大量的请求会访问这个缓存，且满足读操作远多于写操作，此时如果租约时间太短的话会导致我们需要不停的续约，而这至少需要一个RTT，以及客户端和服务端的处理时间；而且续约还需要检查一致性，因为两次续约期间必然有时间间隔，此时写操作是不需要经过此客户端同意的，客户端并不清楚自己的缓存是否是最新的，当然可以和续约请求合并。所以显然上面的情况我们使用长租约会更加合适。

最后就是存储。其实这个比较灵活，而且paper中的描述也比较少。文中的大致意思是短租约可以降低服务端的存储需求，因为过期的记录可以重复使用，鉴于这篇文章是1989年发表，计算机的存储能力已经是今非昔比了，这种复用旧数据的做法不知还是否可以被接受（存储所有的状态开销不大，而且不方便DEBUG）。就我的理解或许是把存储上一个leases状态的结构体直接拿来复用，而不必再重新分配，可能类似于对象池，那长租约为什么不可以呢。。当然文章中也没有透漏太多细节，这里不再多说。

经过以上的讨论不难发现租约的时间选择是一个很大的问题，因为如果太长的话会导致在某个客户端失效时写操作阻塞时间过长且false sharing影响较大，而太短的话又会导致续约开销较高。所以这个时间的选择非常重要，文中通过一系列的推导和实验得出在V file caching mechanism中10秒是一个优秀的数字，这并不具有普适性。在GFS中初始值被设置60s，在Chubby中没有说初始的租约时间，因为Chubby的KeepAlive机制像是一种特殊的leases，其续约是经常发生的，Chubby的论文中描述了默认的续约保持时间是12s。所以一般来说这个时间是要基于任务的类型和如何利用leases的思想去实现缓存一致性来决定的。

为什么前面说道“利用leases的思想”？因为[2]只是leases最初的论文，后来有很多变种，可以参考[4]。这也很好理解，因为[2]中描述的是多机读写操作都支持的leases，但是其实很多情况下不需要这样，比如说分布式锁（不谈论其他功能）的实现，我们显然只需要对每个数据维护一个写租约就可以了，这样写的时候也不需要得到所有读租约的同意（当然Chubby中维护客户端缓存另说，这相当于认定了客户端优先级更高，因为缓存不失效时客户端取数据连网络通信都免了）。

通过以上讨论也可以看出其实leases是一个强一致性模型。

leases时延分析

在[2]3有这样一段文字：

• The choice of lease term is based on the trade-off between minimizing lease extension overhead versus minimizing false sharing.
• 租约期限的选择需要在最小化续约开销与最小化 false sharing 之间进行权衡。这种权衡最终是为了最小化服务端负载和客户端响应延时。

对于这个问题其实在[5]中我曾简单的分析过，现在让我们来看看大牛是如何分析的：

首先定义如下符号：

符号	描述
N	客户端数量
R	服务端读操作的柏松分布
W	服务端写操作的泊松分布
S	共享的cache数量
Mprop	消息传输时延（假设相同）
Mproc	发送者和接收者的处理时间
E	时钟偏移的度
ts	租约的时间

显然一个消息发送需要：$mprop+2mproc$

那么一个发送和响应就需要：$2mprop+4mproc$

考虑到leases中的通知为广播，有N个客户端持有租约，那么具体的过程就是写端并行发送N个请求，N个客户端处理后返回响应消息，写端串行处理，所以其实是并行发送需要$Mprop+2Mproc$，客户端并行处理和返回需要$Mprop+Mproc$，写端串行处理N个响应需要$nMproc$，总共需要$2Mprop+(n+3)Mproc$个时间。这也是一次写入的前置开销。

当得到所有的持有缓存的客户端同意时发起获取租约操作（当然实现时这个包可以带上写操作），那么在服务端看来这个租约的实际有效时间其实是：
$$tc=max(0,ts-(mprop+2mproc)-E)$$

当客户端收到租约响应时其实租约的有效时间只有：
$$tc=max(0,ts-(2mprop+4mproc)-E)$$

显然有一种比较特殊的情况，即Ts=0，可以看出在租约有效时间消耗较大时0租约比短租约要好，因为一个非零的Ts和为零的Tc意味着写操作受罚而读操作却未获利。即当Ts很小时，会导致Tc=0，这样租约已经没有意义了，因为缓存虽然存在但一直是无效的，所以读无法获利，相反写操作却还需要继续获得租约持有者的授权，因此反而不如没有租约。此时也就什么都不能做了。

倘若此时客户端还认为自己持有$ts$的租约的话就会出现问题，因为服务器已经放弃这个租约了（出现双锁）。一般而言可以认为$E$在一个常数范围内[7]（当然除了spanner以外貌似没有这么玩的，时钟仍然是一个大问题），而在包中加入时间戳的话很好在得到响应包是获取 $2mprop+4mproc$ 的值（用写端当前时间戳减去当初发送时的时间戳即可），就像是防止重传二义性时采取的措施那样。

当然服务端也可以采用一个较大的值作为租约的值，客户端就不必做这么多了，但是多大也不好选，因为没办法知道网络通信的状态，可能发响应包的时候网络极差，所以还是前者的安全性好证明一点。

如果一个缓存在一个租约期限内处理了期望的$RTc$个读操作，再算上引起租约请求的那一次读操作，那么一次租约请求的开销就平摊到了$1+RTc$个读操作上。那么服务端续约相关的消息处理速率就是：$2NR/(1+RTc)$（我的理解是几次读操作会触发一次服务器读）

而每个读操作的平均时延是：$2(Mprop+2Mproc)/(1+RTc)$

假设一个写请求本身持有租约，那么一次写授权的开销是：$Ta=2Mprop+(S+2)Mproc$

因此时延最多是Ta，服务端写负载最多是NSW。

在S>1且Ts>0时，服务端每单位时间将会接受和发送$Sum$个消息：
$$Sum=2NR/(1+RTc)+NSW$$

读写操作的平均时延为：

对于0租约，负载是2NR；如果满足如下条件，那么一个时长大于Ta的租约就能产生更小的负载，其实也就是续约的请求数大于用于维护一致性的请求数：
$$2NR>2NR/(1+Rtc)+NSW$$

好了，我推不下去了。有疑惑请直接看paper。

虽然没跟着paper推完，但是至少我们可以很清楚的看到客户端和服务端的有效租约时长$Tc$，且想减少请求的平均时延可以从$Mprop$，$Mprop$，$ta$，$W$的减小，以及$R$，$Tc$的增大来入手。

对分布式锁的思考

难道分布式锁所遇到的挑战不是分布式缓存一致性所遇到的挑战吗？

从这篇文章我们至少可以看出分布式锁其实就是一个与用户交互，用户持有租约的一个特殊的缓存一致性，此时我们所说的缓存就是“锁”本身这个数据，或者说对某个数据控制修改操作的权力。

实现一个安全的分布式锁最大的问题就是宕机后的死锁，为了避免这种情况我们要让锁带期限，使得持锁机器宕机在全局来看影响性能而不影响正确性。但是带期限的锁因为通信的时延以会导致有效租约变短，时钟偏移的度可能造成一个锁在同一个时间点被两个进程“正确”的持有。因为服务端快的话会导致服务器认为租约已经结束而客户端依然有效，如果客户端快的话不会影响正确性，但是会导致租约有效时间变短。

这个问题可以看做缓存的不一致，解决的思路就是在leases中所讨论的方法。

当然paper中所讨论的是多客户端，也就是同一个数据的读租约可以被多客户端持有，而只有一个客户端可以持有写租约，这更像是单写者，多读者问题。而平时讨论的分布式锁基本上本质是一个互斥锁，即得到锁可以视作得到一个读写租约。显然后者实现更为简单，因为写操作不必寻求相同数据的读租约同意，一个数据同一个时间点仅允许一个租约存在。

如此看来以前的文章[10]写的倒没什么大问题，但是格局还是太低，对问题的理解不够。

总结

其实GFS中对租约的应用也很有意思，限于精力就不再提了。而Chubby中的KeepAlive算是一种特殊的租约，也很有意思。至于ChubbyGo中使用的Token机制也很有趣，其站在另一个角度维护了分布式锁的有效性（请求中携带令牌，资源持有方可以对比锁服务器中最新的令牌很容易看出此请求是否过期，当然也有一些问题，可以参考[5]）。

好了就写到着吧，时候不早了，该刷题了。

参考：

1. https://en.wikipedia.org/wiki/Cache_coherence
2. 《Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency 》
3. 《浅谈内存屏障，C++内存序与内存模型》
4. 《租约机制简介》
5. 《ChubbyGo的安全性论证与展望》
6. 《从false sharing到缓存一致性，这其实与我们息息相关》
7. 《Time, Clocks and the Ordering of Events in a Distributed System》
8. 《泊松分布的现实意义是什么，为什么现实生活多数服从于泊松分布？》
9. 《构建可靠分布式系统的挑战》
10. 《浅谈分布式锁：安全与性能的取舍之道》
11. 《The Google File System》
12. 《The Chubby lock service for loosely-coupled distributed systems》