缓存和并发控制

原文： Sundial: Harmonizing Concurrency Control and Caching in a Distributed OLTP Database Management System

摘要

由于两个主要的限制因素，分布式事务的性能很差。 首先，分布式事务具有较高的延迟，因为它们对远程数据的每一次访问都会导致较长的网络延迟。 第二，这种高延迟增加了分布式事务之间发生争用的可能性，导致高终止率和低性能。

我们提出了Sundial，一种内存中的分布式乐观并发控制协议，它解决了这两个限制。 首先，为了降低事务终止率，Sundial根据事务的数据访问模式在运行时动态地确定事务之间的逻辑顺序。 Sundial通过将逻辑契约应用于每个数据元素来实现这一点，这允许数据库动态计算事务的逻辑提交时间戳。 第二，为了减少远程数据访问的开销，Sundial允许数据库在服务器的本地主存储器中缓存远程数据并保持缓存一致性。 使用逻辑租赁，Sundial将并发控制和缓存一致性集成到一个简单的统一协议中。 我们对最先进的分布式并发控制协议进行Sundial评估。 在高争用情况下，Sundial的性能优于下一个最佳协议高达57%。 Sundial的缓存方案在高访问偏差的工作负载中提高了高达4.6×的性能。

介绍

当联机事务处理(OLTP)应用程序的计算和存储需求超过单个服务器的资源时，企业通常将目光转向分布式数据库管理系统(DBMS)。 这样的系统将数据库分割成不相交的子集，称为分区，这些子集存储在多个无共享服务器上。 如果事务只在单个服务器上访问数据，那么这些系统就实现了很高的性能[2,3]。 但是，当事务访问分布在多个服务器[38]的数据时，性能会降低。 这有两个原因。 首先最主要的原因，过长的网络延迟导致分布式事务的执行时间长，使得它们比单分区事务慢。 第二，长的执行时间增加了事务之间发生争用的可能性，导致了更多的终止和性能下降。

最近改进分布式并发控制的工作集中在协议级和硬件级的改进上。 改进的协议可以减少事务[22,35,36,46]之间的同步开销，但由于高协调开销（例如锁阻塞)，仍然可以限制性能）。 硬件级的改进包括使用特殊的硬件，如优化的网络，使低延迟远程内存访问[20,48,55]，这可以增加系统的总体成本。 理想情况下，并发控制协议应该在低成本的商品硬件上实现良好的性能。

为了避免长时间的网络延迟，先前的工作大多建议在多个数据库服务器[16]中复制频繁访问的共享数据，从而使一些分布式事务成为本地事务。 这种复制需要分析数据库工作负载或手动识别热数据，这为用户增加了复杂性。 数据库最好通过缓存机制自动复制数据，而无需用户干预。

为了解决这些问题，我们引入了Sundial，一种内存中的分布式并发控制协议，它优于现有的方法。 为了解决长网络延迟问题，Sundial原生支持服务器本地主存中的数据缓存，而不需要附加协议或牺牲序列化性，并且只在有益的情况下使用缓存的数据。 为了解决协调分布式事务的高开销，Sundial采用了一种混合的悲观/乐观并发控制协议，该协议通过动态重新排序经历读写冲突的事务来减少中止。

Sundial后面的启用技术是一个称为逻辑租约的概念，它允许DBMS在执行序列化的同时动态地确定事务之间的逻辑顺序。 逻辑租约包括两个逻辑时间戳，指示元组有效的逻辑时间范围。 DBMS动态计算事务的提交时间戳，它必须与事务访问的所有元组的租约重叠。 先前的工作表明，逻辑租约在提高硬件缓存一致性[52]和多核并发控制协议[53]的性能和并发性方面是有效的。 据我们所知，本文是第一个将逻辑租约应用于分布式系统，也是第一次无缝地将并发控制和缓存结合在一个无共享数据库中。

为了评估Sundial，我们在分布式DBMS测试床中实现了它，并将其与三种最先进的协议进行了比较：MaaT[35]、Google F1[41]，带Wait-Die的两阶段提交。 我们使用两个具有不同争用设置和集群配置的OLTP工作负载。Sundial相比于其他最好的协议实现了高达57%的高吞吐量和41%的低延迟。 对于具有倾斜读的密集型工作负载，Sundial的缓存机制提高了最高4.6x的吞吐量。

背景和相关工作

并发控制为数据库事务提供了两个关键属性：原子性和隔离性。 原子性保证了事务的所有更改或任何更改都应用于数据库。 隔离指定事务何时可以看到其他事务的写入。 我们在本文中考虑了可串行化：并发事务产生的结果与顺序执行的结果相同。

虽然序列化是一个健壮且易于理解的隔离级别，但是提供序列化性的并发控制协议在DBMS中会产生大量同步开销。 这已经在多核[51]和分布式[25]设置中并发控制的可伸缩性研究中得到了证明。 在分布式DBMS中，由于数据库服务器之间的高网络延迟，问题更加严重。

常用的两类并发控制协议[9]：两阶段锁(2PL)和时间戳排序(T/O)。 2PL[11，21]协议是悲观的：事务只有在事务获得具有适当权限的锁（例如读或写)之后才访问元组）。 相反，T/O协议使用逻辑时间戳来确定事务的逻辑提交顺序。 T/O协议的变体包括多版本并发控制(MVCC)，它维护每个元组的多个版本以减少冲突；乐观并发控制(OCC)，其中只有在事务执行后才会检查冲突。 与2PL[51]相比，OCC可能会招致更多的中止，但具有非阻塞执行的优点。 Sundial将2PL和OCC的好处分别用于写-写和读-写冲突。 Sundial通过逻辑租赁（参见第3节）进一步减少了读写冲突导致的中止。

分布式并发控制

最近的研究提出了许多分布式并发控制协议[15,20,35,41,48]，这些协议都是基于2PL的变体(例如Spanner[15]和F1[41])或T/O(例如MaaT[35]和Lomet等人[34])。 在这些协议中，MaaT[35]是最接近Sundial的，它们都使用逻辑时间戳来动态调整事务之间的提交顺序，但使用了不同的技术。 MaaT要求所有冲突事务显式地相互协调以调整它们的时间戳间隔，这将会损害性能并导致更多的中止。 相反，冲突的事务在Sundial中不进行协调。 此外，Sundial使用缓存来减少网络延迟，而MaaT不支持缓存。

Lomet等人[34]提出了一种多版本并发控制协议，该协议使用时间戳范围懒惰地确定事务的提交时间戳。 该协议在多核和分布式设置中都有效。在冲突时，协议要求所有涉及的事务缩小其时间戳范围-这是Sundial通过逻辑租约避免的昂贵操作。 此外，他们的协议需要一个多版本数据库，而Sundial工作在一个单一版本数据库。第6.8节比较了Lomet等人的协议和Sundial的性能。

多核并发控制

快速事务处理在单服务器多核心系统中进行了深入的研究[28,32,37,47,49,50,53,54]。 其中一些技术也可以应用于分布式环境：我们将其中一些合并到我们的分布式并发控制协议中。 为多核处理器开发的其他技术由于不同的系统特性，如高网络延迟，不能很容易地在分布式设置中使用。

在本论文中，我们关注的是分布式并发控制协议的性能，因此不与单服务器多核系统设计的协议进行比较。

数据复制和缓存一致性

前边提到数据复制[16,38]可以减小分布式事务的开销，复制对于热（经常访问的）只读数据特别有效。 当跨服务器复制时，热数据可以在本地服务于读请求，大大减少了远程请求的数量。

数据复制有几个缺点。首先，数据库的用户需要配置工作负载，或者手动指定要复制的数据，这是一个快速发展的数据库中的艰巨任务。 其次，当DBMS更新被复制的数据时，会通知所有持有副本的服务器以保持一致性，这很复杂，增加了性能开销。 第三，全表复制会增加内存占用，如果复制的表很大，这是有问题的。

缓存是利用热点数据的更灵活的解决方案。具体来说，DBMS决定在没有用户干预的情况下在服务器的本地内存中缓存远程数据。 从本地缓存读取数据的查询不会与远程服务器联系，从而减少网络延迟和流量。 缓存协议中的关键挑战是保持缓存一致性（即避免机器读取陈旧的缓存数据）。 缓存一致性是并行计算中的一个经典问题，许多先前的工作存在于不同的研究领域， 包括多核和多套接字处理器[6,42,56]、分布式共享内存系统[27,31]、分布式文件系统[24]和数据库[5,23,39]。 在传统的DBMS中，缓存和并发控制是两个独立的层；它们都是众所周知的难以设计和验证[43]。 在第4节中，我们演示了如何借助租赁契约将并发控制和缓存一致性合并到单个轻量级协议中。

整合并发控制和缓存一致性

并发控制和缓存一致性的集成也是在数据共享系统[40]的背景下进行的研究。 例如包括IBM DB2[26]、Oracle RAC[13]、Oracle Rdb[33]以及最近的Microsoft Hyder[10]， 在这些系统中，集群中的服务器共享存储(即共享磁盘架构)，每个服务器都可以访问数据库中的所有数据， 并在本地缓冲区中缓存最近访问的数据。缓存一致性协议确保缓存中的数据新鲜度。

Sundial在两个方面不同于数据共享系统。 首先，Sundial是建立在无共享架构之上的，因此比使用共享磁盘的数据共享系统更有规模。 第二，现有的数据共享系统通常使用2PL进行并发控制；一致性协议也基于锁。 相比之下，Sundial对并发控制和缓存一致性都使用逻辑租赁，这降低了协议的复杂性，增加了并发（第4节）。

另一个相关的系统是G-Store[17]，它支持通过键值存储进行事务多键访问。 在事务启动之前，服务器启动分组协议，以收集事务将访问的密钥的独占所有权；事务完成之后，所有权被收回。 分组协议有两个缺点：(1)它要求DBMS在执行事务之前知道事务将访问哪些键，(2)不允许多个事务同时读取同一key。 这些问题在Sundial中不存在，它支持动态工作集和并发读取。

SUNDAIL并发控制

本节详细介绍了Sundial分布式并发控制协议。讨论假设通过局域网(LAN)连接的同质服务器集群。 数据跨服务器进行分区，每个元组映射到一个主服务器，该主服务器可以代表外部用户启动事务，以及代表对等服务器处理远程查询。 发起事务的服务器称为事务的协调器；参与事务的其他服务器称为参与者。

逻辑租约

逻辑租约基于逻辑时间，并指定并发操作之间的部分逻辑顺序。 每个数据元素都附带一个逻辑租约，使用两个64位时间戳wts和rts表示。 wts是最后一次写入元组的逻辑时间；rts是租约的结束，这意味着元组可以在逻辑时间ts读取，从而使wts≤ts≤rts。 事务只在当前租约到期后才写入元组，即在不少于rts+1的时间戳下写入元组。 由于租约在Sundial中是合乎逻辑的，所以写入事务不会在物理时间wait租约到期-它只是在逻辑时间提前跳转。

为了实现序列化，DBMS计算事务T的单个提交时间戳，这是一个逻辑时间，属于事务访问的所有元组的租约范围。 也就是说，对于T访问的所有元组，tuple.wts≤T.commit_ts≤tuple.rts。 从逻辑时间的角度来看，T的操作是在提交时间戳处原子执行的。 DBMS只使用事务访问的元组的租约来计算提交时间戳，因此不需要跨事务协调。

图1：逻辑租约示例 两个事务调度，T1和T2，访问元组A、B、C和D。T1和T2的操作分别用黄和绿来表示。由于逻辑时间戳是离散的，所以每个时间戳表示为图中的间隔。

图1，说明Sundial并发控制的高级思想。DBMS执行两个事务，T1和T2。T1读取具有逻辑租约[0,1]和[1,2]的元组A和B； T1还写入D并为新数据创建新的租约[1,1]。T1在时间戳1处提交，因为它与T1访问的所有租约重叠。

T2写入A，并创建新的[2,2]租约，它同时在[3,3]读取C。然而，在这个情况下，这两项租约并不重叠。 在这种情况下，DBMS将A上租约的结束从2扩展到3，这样T2执行的两个操作都在时间戳3处有效。 如果租约扩展成功，即系统中没有其他事务在时间戳3写入A，则DBMS在时间戳3提交T2。

请注意，在本例中，当T1提交时，T2已经修改了A，这是由T1读取的。 然而，这并不像传统的OCC协议那样导致T1中止，因为Sundial以逻辑顺序而不是物理时间顺序序列化事务。 物理和逻辑提交顺序可能不同，如示例所示-虽然T1在T2之后按物理时间顺序提交，但T1提交的逻辑时间戳较小。 这个Sundial的时间租约特性允许DBMS动态地确定事务的提交时间戳，这避免了由于读写冲突而导致的一些不必要的中止，并导致较低的中止率。

冲突处理

Sundial使用不同的方法来解决事务之间的不同类型的冲突。 在数据库[18,44]和软件事务内存[19]中也提出了这种混合方案。

Sundial使用悲观2PL处理写-写冲突。 我们之所以做出这种选择，是因为许多写都是读-修改-写，而对同一个元组的两个这样的更新总是冲突的(除非DBMS利用语义信息，如交换性)； 使用OCC处理这种冲突会导致除一个冲突事务之外的所有事务中止。 相反，Sundial使用OCC而不是2PL处理读写冲突，以实现更高的并发。 这防止事务在执行过程中等待锁。 更重要的是，这允许DBMS使用3.1节中讨论的逻辑租约技术动态调整事务的提交顺序以减少中止。

图2：读写冲突例子 在2PL，OCC和Sundial中两个存在读写冲突的事务处理

图2是一个示例，说明2PL、OCC和Sundial在处理读写冲突方面的区别。 在2PL中，DBMS在事务T1读取之前锁定的一个元组，此锁阻止T2写入到相同的元组。 这增加了T2的执行时间。在传统的OCC协议中，事务在正常执行期间不会持有锁。 因此，T2在T1之前提交，并在数据库中更新元组A，当T1尝试提交时，自上次T1读取它以来， A已经更改。然后，DBMS由于这种数据冲突终止了T1。

在本例中，终止T1是不必要的，因为在保持序列化性的两个事务之间存在逻辑提交顺序， 即T1在T2之前提交。Sundial能够使用逻辑租约识别此顺序。具体来说，T1读取带有租约[0,10]的A版本，并在该租约中的时间戳上提交(例如。 时间戳0)。 T2以新的[11,11]租约写入A，因此在时间戳11提交。 虽然T1按照物理时间顺序在T2之后作出提交决定，但这两个事务都能够按照逻辑时间顺序在T2之前提交T1。

协议阶段

图3：一个分布式事务的生命周期 一个分布式事务经过执行阶段和两阶段提交阶段-其中包含准备阶段和提交阶段

Sundial中分布式事务的生命周期如图3，包含三个阶段：(1)执行(2)准备(3)提交。 协调器在收到用户应用程序请求后启动新事务。在第一阶段执行阶段中，协调器执行事务的逻辑并向事务参与者发送请求。 事务完成执行阶段时，协调器开始两阶段提交。在两阶段提交的第一阶段准备阶段，协调器发送一个准备提交请求到参与事务的每个参与者（即在执行阶段访问的服务器）。 每个参与者响应一个OK或者ABORT。如果所有参与者包括协调者都同意事务可以提交， 则事务进入到最终阶段提交阶段。 协调者向每个参与者发送消息以完成事务。 否则，DBMS会终止事务并回滚其修改。为了确保事务的修改在服务器/网络故障中持续存在， DBMS在2PC协议期间在每个服务器的不同点设置日志记录（图3中的*表示)。

在Sundial中，只有在事务提交阶段更新元组时，租约的wts才会发生变化；租约的rts只在准备阶段或提交阶段发生变化。 元组的wts和rts只能增加，但永远不会减少。 在这三个阶段中，DBMS可以协调参与者计算事务提交时间戳或扩展逻辑租约。 DBMS在其正常运行时消息中捎带与时间戳相关的信息。 我们现在更详细地描述每个阶段的逻辑。

执行阶段

在执行阶段，事务在数据库中读取和写入元组并执行计算。 每个元组包含一个逻辑租约(即wts和rts)。 Sundial处理写-写冲突使用2PL等待-删除算法[9]。 因此，DBMS还维护当前锁持有者和等待锁的事务的等待列表。 每个元组都有以下格式，其中DB是数据库，DB[key]表示以key为主键的元组：

DB[key] = {wts, rts, owner, waitlist, data}

Sundial使用OCC处理读写冲突，因此DBMS维护每个事务的读集(RS)和写集(WS)。 两组数据结构如下所示。数据字段包含事务读取(RS)或写入(WS)的数据库元组的本地副本。

RS[key] = {wts, rts, data}, WS[key] = {data}

算法1： 事务T的执行阶段

当T开始时T.commit_ts初始化为0。缓存相关代码以*开头（详见第4节)

Function read(T, key)
    if key ∈ T.WS:
        return WS[key].data
    elif key ∈ T.RS:
        return RS[key].data
    else:
        *if key ∈ Cache and Cache.decide_read():
        *    T.RS[key].{wts, rts, data} = Cache[key].{wts, rts, data}
        else:
            n = get_home_node(key)
            # read_data() atomically reads wts, rts, and data and
            # return them back
            T.RS[key].{wts, rts, data} = RPCn::read_data(key)
        *   Cache[key].{wts, rts, data} = T.RS[key].{wts, rts, data}
        T.commit_ts = Max(T.commit_ts, T.RS[key].wts)
        return RS[key].data

Function write(T, key, data)
    if key ∉ T.WS:
        n = get_home_node(key)
        # lock() tries to lock the tuple DB[key]; if locking is successful,
        # it returns wts and rts of the locked tuple
        {success, wts, rts} = RPCn::lock(key)
        if not success or (key ∈ T.RS and wts ≠ T.RS[key].wts):
            Abort(T)
        else:
            T.commit_ts = Max(T.commit_ts, rts + 1)
    T.WS[key].data = data

对于读取请求，如果请求的元组已经在事务T的读或写集中，DBMS只需返回数据（第2-5行）。 否则，DBMS将远程过程调用(RPCn)发送到元组的主服务器n，后者原子地读取元组的wts、rts和数据，并将它们返回到协调器的读取集（第10-12行）。 然后，协调器将T.commit_ts更新为至少是元组的wts（第14行）， 这反映了T的逻辑提交时间必须不早于上一次写入元组的逻辑时间。最后返回数据（第15行）。

对于写操作，如果元组已经在T的写集中，DBMS只需更新写集中的本地数据（第17、25行）。 否则，DBMS通过向其主服务器发出RPC来锁定元组（第18-20行）。 RPC返回锁获取是否成功，如果成功，则返回锁定元组的wts和rts。 如果锁失败，或者如果锁定的密钥存在于读取集中，但返回的wts与读取集中的wts不匹配，则事务中止（第22行）。 否则，DBMS将事务的commit_ts提前到rts+1（第24行)，并更新写集中的数据(第25行）。 请注意，在T的执行阶段，其他事务不能读取T写集中的元组-它们只有在T提交后才可见（3.3.3节）。

Sundial的一个重要特征是，读取元组的事务不会阻止写入相同元组的另一个事务（反之亦然）。 如果元组被锁定，读取事务仍然读取元组的数据，并与其相关的逻辑租约。 读取事务的提交时间戳将小于持有锁的事务的提交时间戳。 但是，只要两个事务都找到满足其租约的提交时间戳，它们就能够提交。

准备阶段

算法2：事务T的准备阶段 协调器执行validate_read_set()，参与者执行renew_lease()

缓存相关代码以*开头

Function validate_read_set(T)
    for key ∈ T.RS.keys() \ T.WS.keys(): 
        if commit_ts > T.RS[key].rts: 
            n = get_home_node(key)
            # Extend rts at the home server
            resp = RPCn::renew_lease(key, wts, commit_ts)
            if resp == ABORT: 
            *   Cache.remove(key)
                return ABORT
    return COMMIT

# renew_lease() must be executed atomically
Function renew_lease(key, wts, commit_ts)
    if wts = DB[key].wts or (commit_ts > DB[key].rts and
      DB[key].is_locked()):
        return ABORT
    else:
        DB[key].rts = Max(DB[key].rts, commit_ts)
        return OK

准备阶段的目标是由DBMS确定事务的所有读写是否在计算commit_ts有效。 算法2显示了DBMS在准备阶段执行的逻辑；validate_read_set()在协调器上执行，协调器在参与者中调用renew_lease()。

由于写集中的所有元组都已锁定，DBMS只验证已读但未写的元组。 对于事务T的读集中的每个键，而不是写集（第2行），如果T.commit_ts在元组的租约范围内 (即tuple.wts≤T.commit_ts≤tuple.rts1)，则读取已经有效， 不需要做任何事情（第3行）。 否则，RPC将被发送到元组的主服务器以更新其租约 （第4-6行）。 如果续租失败，交易中止（第9行）。

参与者执行renew_lease()以执行租约续签。如果元组的当前wts与事务在执行阶段观察到的wts不同， 或者如果需要扩展但元组被不同的事务锁定，则DBMS不能扩展租约， ABORT返回给协调器（第13-14行）。 否则，DBMS通过将元组的RTS更新到至少commit_ts （行16)来扩展租约）。 在Sundial中，租约扩展是更改元组RTS的唯一方法。 每个元组的wts和rts都只能增加，但永远不会减少。

提交阶段

在提交阶段，数据库要么通过将写入集的所有写入复制到数据库并释放锁来提交事务，要么通过简单地释放锁来中止事务。算法3显示协调器执行的函数。如果锁获取在执行阶段失败，或者validate_read_set()返回ABORT，则abort()，否则执行commit()。

算法3：事务T的提交阶段

数据库提交或终止事务

缓存相关代码以*开头

Function commit(T)
    for key ∈ T.WS.keys(): 
        n = get_home_node(key)
        RPCn::update_and_unlock(key, T.WS[key].data, T.commit_ts)
    *   Cache[key].wts = Cache[key].rts = T.commit_ts
    *   Cache[key].data = T.WS[key].data

Function abort(T)
    for key ∈ T.WS.keys(): 
        n = get_home_node(key)
        # unlock() releases the lock on DB[key]
        RPCn::unlock(key)

Function update_and_unlock(key, data, commit_ts)
    DB[key].data = data
    DB[key].wts = DB[key].rts = commit_ts
    unlock(DB[key])

DBMS在提交阶段不会对事务的读集执行任何附加操作。 因此，如果事务没有写入参与者的任何元组，DBMS就会跳过该参与者的提交阶段。 Sundial应用这个小优化来减少网络流量。

索引和幻读

除了常规的读和写之外，索引必须支持插入和删除。因此，索引需要额外的并发控制机制来保证正确性。具体来说，如果事务使用索引两次读取一组元组，但由于另一个事务对该集合的插入或删除而获得不同的结果集，则会发生幻读。序列化不允许幻读。本节讨论如何避免幻读。

通过将插入和删除视为对索引节点的写入，并将查找或扫描视为对索引节点的读取，可以扩展基本的Sundial协议来处理索引访问。这样，每个索引节点(例如，B树索引中的叶节点或散列索引中的桶)都可以被视为规则元组，3.3节中讨论的协议可以应用于索引。逻辑租约也可以保持在更细的粒度（例如，叶节点中的每个指针或桶中的每个块），以避免由于错误共享而不必要的中止；在Sundial中，我们将逻辑租约附加到每个索引节点。为了确保对同一索引节点的多个索引查找/扫描返回一致的结果，以后的访问必须验证索引节点的版本没有更改。

图4：并行索引读取/扫描和插入-逻辑租赁嵌入到B树索引的叶节点，以使索引高并发的访问。

图4显示了两个并发访问哈希索引(图4a)和B树索引(图4b)的事务示例。在散列索引示例中，T1读取映射到具有[0,10]租约的给定桶的所有元组。然后T2将元组插入同一个桶中，并将桶上的租约更新为[11,11]。T1和T2有读写冲突，但不会相互阻塞；如果每个事务都找到满足所有访问租约的提交时间戳，则两个事务都可以提交。

在B树索引示例中，T1执行扫描，该扫描涉及两个叶节点LN1和LN2，并记录它们的逻辑租约 ([0,10] and [0,5]).扫描完成后，T2向LN1插入一个新的键。当T2提交时，它更新LN1的内容，以及它对[11,11]的逻辑租约。 类似于散列索引示例，T1和T2都可以按逻辑时间顺序在T2之前提交和T1提交。因此，并发扫描和插入不需要引起中止。

容错性

Sundial通过两阶段提交(2PC)协议容忍单服务器和多服务器故障，其中协调器和参与者在发送某些消息之前登录到持久存储（图3）。 在2PC期间，Sundial中的逻辑租约需要特殊处理：如果未能地记录逻辑租约，可能会导致不可序列化的调度，如清单1中的示例所示。

清单1: 当逻辑租约未被记录时，序列化冲突-元组A和B分别存储在服务器1和2中

T1 R(A)                 lease [0,9]
T2 W(A), W(B),commit    @ TS =10
Server 2 crashes
Server 2 recovers
T1 R(B)                 lease [0,0]

该示例包含两个事务(T1和T2)，它们分别访问存储在服务器1和2中的两个元组A和B。 当服务器2崩溃后恢复时，映射到服务器2的元组(即元组B)的逻辑租约将重置为[0,0]。 因此，DBMS在时间戳0时提交T1，因为T1访问的元组的租约(即[0,9]的A和[0,0]的B)重叠在0。 然而，这种执行违反了序列化性，因为T1观察到T2对B的写入，而不是对A的写入。 发生此违规是因为在服务器2从崩溃中恢复后，B上的逻辑租约丢失并重置为[0,0]。 如果服务器2没有崩溃，T1对B的读取将返回从时间戳10开始的租约， 导致T1由于不重叠的租约和失败的租约扩展而中止。

解决上述问题的一个简单解决方案是，每当逻辑租约发生变化时，就记录它们， 并在恢复后恢复它们。 然而，这会导致对持久存储的大量写入， 因为即使是读操作也可能会扩展租约，从而导致对日志的写入。

我们观察到，DBMS不会记录每次租赁变更，而只能记录一个大于服务器上所有租赁结束时间的上限时间戳UT。 恢复后，服务器上的所有租约都设置为[UT，UT]。 这保证将来读取到恢复的元组发生在元组的wts之后的时间戳上，时间戳不大于UT。 在清单1所示的示例中，T1对B的读取返回[UT，UT]的租约，其中UT大于或等于10。 这导致T1由于不重叠租赁而中止。 请注意，UT可以是租赁的松散上限。 这减少了UT的存储和日志记录开销，因为只有当最大租约超过最后记录的UT时才记录它。