16 PMDK内部：重要算法和数据结构
第5章到第10章描述了持久内存开发工具包（PMDK）中包含的大多数库以及如何使用它们。
本章介绍了libpmemobj内建的基本算法和数据结构。在我们首先描述了库的总体架构之后，讨论了各个组件以及它们之间的交互，这使得libpmemobj结成一个整体的系统。
16.1 持久内存池：高层体系结构概述
图16-1显示了libpmemobj包含许多相互独立的组件，这些组件构建在彼此之上以提供事务对象存储。
一切都建立在libpmem及其持久性原语之上，库使用这些原语将数据传输到持久性内存并持久化它。这些原语通过libpmemobj专有API公开给在持久内存上执行低级操作的应用程序，例如手动缓存flush。这些API是公开的，因此高层库可以检测、截获和扩展所有store到持久内存。这对于运行时分析工具（如第12章所述的Valgrind pmemcheck）的检测非常有用。更重要的是，这些函数是本地和远程数据复制的拦截点。
复制的实现方式，确保在调用drain之前写入的所有数据都将按照配置安全地存储在复制副本中。drain操作是一个barrier屏障，它等待硬件缓冲区完成其flush操作，以确保所有写操作都已到达介质。这是通过在执行内存复制或flush时启动对副本的写操作，然后在drain调用中等待这些写操作完成来实现的。此机制保证复制池和非复制池具有相同的行为和排序语义。
libpmem提供的持久性原语之上是一个抽象，用于对事务数据进行fail-safe修改，称为统一日志记录。统一日志是一个单一的数据结构和两种不同日志类型的API，在libpmemobj中使用它们来确保故障安全：事务和原子操作。这是库中最关键的、对性能敏感的模块之一，因为它几乎是每个API的热代码路径。统一日志是一个混合的DRAM和持久内存数据结构，通过运行时上下文访问，该运行时上下文组织需要在单个故障安全原子事务中执行的所有内存操作，并且允许关键性能优化。
持久内存分配器在事务或单个原子操作的统一日志上下文中操作。这是libpmemobj中最大、最复杂的模块，用于管理与内存池关联的潜在大量持久内存。
持久内存池中存储的每个对象都由PMEMoid（持久内存对象标识符）类型的对象句柄表示。实际上，这样的句柄是全局范围内唯一的对象标识符（OID），这意味着来自不同池的两个对象永远不会有相同的OID。OID不能用作指向对象的直接指针。每次程序试图读取或写入对象数据时，它必须通过将对象的OID转换为指针来获取对象的当前内存地址。与内存地址相反，在对象的生命周期内，除了realloc()之外，给定对象的OID值不会更改，并在关闭和重新打开池后保持有效。因此，如果一个对象包含对另一个持久对象的引用（例如，要构建链接的数据结构），则该引用必须是OID而不是内存地址。
原子API和事务API是使用持久内存分配器和统一日志的组合构建的。最简单的公共接口是原子API，它在统一的日志上下文中运行单个分配器操作。日志上下文不会在外部公开，而是在单个函数调用中创建、初始化和销毁。
最通用的接口是事务API，它基于快照的undo日志记录和内存分配和释放的redo日志记录的组合。这个API具有ACID（原子性、一致性、隔离性、持久性）属性，它是一个相对较薄的层，将统一日志和持久内存分配器的实用性结合在一起。
对于需要对持久内存分配器进行低层访问的专有事务性用例，有一个“action” API。action API本质上是一个传递到原始内存分配器接口的过程，同时也是可用性的助手。与通用事务相比，该API可以用来创建低开销的算法，从而以易用性为代价来减少内存栅栏。
所有公共接口都在PMEMoids上生成和操作，作为指针的替代。这会带来空间开销，因为PMEMoids是16字节。转换为普通指针也有性能开销。好处是，对象可以在应用程序的不同实例甚至不同的持久内存池之间安全地引用。
池管理API打开、映射和管理驻留在持久内存中的文件或设备。这是配置复制、初始化元数据和堆以及创建所有运行时数据的位置。这也是中断事务的关键恢复所在。一旦恢复完成，所有先前的事务要么提交要么中止，持久状态是一致的，日志是干净的，可以再次使用。
16.2 内存映射的不确定性：持久内存对象标识符
对于任何持久性内存应用程序来说，一个重要的概念是如何表示对象在内存池中的相对位置，甚至在内存池之外。也就是说，如何实现指针？您可以依赖普通指针，它们与应用程序的虚拟地址空间的开头相关，但这需要注意很多问题。使用这样的指针将取决于持久内存池始终位于映射它的应用程序的虚拟地址空间中的同一位置。由于地址空间布局随机化（ASLR），这在现代操作系统上很难（如果有可能）以可移植的方式实现。因此，用于持久内存编程的通用库必须提供专门的持久指针。图16-2显示了从对象A到对象B的指针。如果基址改变，指针将不再指向对象B。
通用相对持久指针的实现应满足以下两个基本要求：
- 指针必须跨应用程序重启保持有效；
- 指针应该在有许多持久内存池的情况下明确地标识内存位置，即使它不位于其原始派生的池中。
除了前面的要求之外，您还应该考虑一些潜在的性能问题：
- 传统指针的额外空间开销。这一点很重要，因为大的胖指针将占用更多的内存空间，而且单个CPU缓存线所能容纳的胖指针数量会更少。这潜在地增加了在pointer-chasing沉重数据结构（如B-树算法中的结构）上的操作成本；
- 将持久指针转换为实际指针的成本。由于解引用是一种非常常见的操作，因此此计算必须尽可能轻量级，并且应涉及尽可能少的指令。这是为了确保持久指针的使用是高效的，并且在编译期间不会产生太多的代码膨胀；
- 通过解引用方法防止编译器优化。复杂的指针转换可能会对编译器的优化过程产生负面影响。理想情况下，转换方法应该避免依赖于外部状态的操作，因为这将防止自动向量化。
在保持低开销和C99标准符合性的同时满足上述要求是非常困难的。我们探讨了几种选择：
- 相对于池的开始，8字节的偏移指针很快被排除，因为它不满足第二个要求，需要为了转换方法而提供一个池基指针；
- 8字节自关联指针，其中指针的值是对象位置和指针位置之间的偏移量。这可能是最快的实现，因为转换方法可以实现为“ptr+（*ptr）”。然而，这并不能满足第二个基本要求。此外，它还需要一个特殊的赋值方法，因为指向同一对象的指针的值会因指针的位置而异；
- 带有内嵌入内存池标识符的8字节偏移指针，允许库满足第二个要求。这是对第一种方法的扩充，该方法利用虚拟地址空间的可用大小小于大多数现代cpu上指针的大小的事实，将标识符另外存储在指针值的未使用部分。然而，这种方法的问题是池标识符的位数相对较少（在现代CPU上为16位），并且可能随着将来的硬件而缩小；
- 带有池标识符的16字节胖偏移指针。这是最明显的解决方案，与前面的解决方案类似，但有8字节偏移指针和8字节池标识符。胖指针以空间开销和一些运行时性能为代价，提供了最佳的实用程序。
libpmemobj使用16字节偏移指针的最通用方法。这允许您做出自己的选择，因为所有其他指针类型都可以直接从中派生。比C99更具表现力的语言libpmemobj绑定，如C++，也可以提供不同类型的指针，具有不同的折衷考虑。
图16-3显示了用于将libpmemobj持久指针PMEMoid转换为有效C指针的转换方法。原则上，这种方法非常简单。我们通过池标识符查找池的基址，然后向其添加对象偏移量。方法本身是静态内联的，并在libpmemobj的公共头文件中定义，以避免对每个差异进行函数调用。问题是查找方法，对于与动态库链接的应用程序，它意味着调用不同的编译单元，对于一个非常常见的执行操作来说，这可能代价高昂。为了解决这个问题，translation方法对每个线程有一个最后基址的缓存，这样就不必在每次取消引用时调用查找，因为在这种情况下，来自同一个池的持久指针被紧密地一起访问。
池查找方法本身是使用存储标识符-地址对的基数树实现的。此树有一个无锁读取操作，这是必需的，因为每个非缓存指针转换都必须获取一个线程安全的锁，这将对性能产生严重的负面影响，并可能串行化对持久内存的访问。
16.3 持久线程本地存储：使用通道
在PMDK开发的早期，我们发现持久内存编程非常类似于多线程编程，因为它需要限制内存更改（通过锁定或事务）对其他线程或程序实例的可见性。但这并不是唯一的相似之处。另一个相似性，我们在本节中讨论，就是有时低层代码需要存储一个执行线程所特有的数据。在持久化的情况下，我们通常需要将数据与事务而不是线程相关联。
在libpmemobj中，我们需要一种方法来创建正在运行的事务与其持久日志之间的关联。它还需要一种在意外中断后重新连接到这些日志的方法。解决方案是使用名为“lane”的数据结构，它只是一个持久字节缓冲区，也是事务本地缓冲区。
Lane通道数量有限，大小固定，位于池的起点。每次事务开始时，它都会选择其中一条通道进行操作。因为通道数量有限，所以可以并行运行的事务数量也有限。因此，通道的大小相对较小，这样通道的数量就足够大，以大于在可预见的将来可以在当前平台和平台上并行运行的多个应用程序线程。
通道机制的挑战在于选择算法，即为特定事务选择哪条通道。它是一个调度程序，分配资源（通道）来执行工作（事务）。
最早版本libpmemobj中实现的原始算法只是从池中选择了第一个可用的通道。这种方法有一些问题。首先，要实现有效地相当于一个后进先出（last-in，First-out）的lane数据结构，无论它是作为链表还是数组实现的，都需要在堆栈前面进行大量同步，从而降低性能。第二个问题是lane数据的错误共享。当两个或多个线程操作正在修改的数据时，会发生错误共享，从而导致CPU缓存抖动。如果多个线程在相同编号的通道上不断地争用以启动新事务，就会发生这种情况。第三个问题是将通信量横跨交织的DIMMs。交织是一种技术，通过将物理内存分散到所有可用的DIMMs上，允许顺序通信利用交织集中所有DIMMs的吞吐量。这类似于跨多个磁盘驱动器的条带化（RAID0）。根据交织块的大小和平台配置，使用原始的通道分配算法可能会持续使用相同的物理DIMM，从而降低总体性能。
为了缓解这些问题，libpmemobj中的通道调度算法更加复杂。它没有使用后进先出的数据结构，而是使用一个8字节的自旋锁数组，每个通道一个。每个线程最初都被分配了一个主通道号，分配的方式是尽量减少通道数据和自旋锁数组的错误共享。该算法还尝试将通道均匀地分布在交织的dimm上。只要活动线程比通道少，就不会有线程共享通道。当线程尝试启动事务时，它将尝试获取其主通道自旋锁，如果失败，它将尝试获取数组中的下一个通道。
最终通道调度算法决策考虑了对各种不同的通道调度方法大量的研究。与原始实现相比，有了很大性能提升，特别是在多线程工作负载情况下。
16.4 确保电源故障原子性：redo和undo日志
libpmemobj用于确保电源故障安全的两个基本概念是重做和撤消日志记录。重做日志用于确保内存分配的原子性，而撤消日志用于实现事务性快照。在讨论许多不同的可能实现方法之前，本节将描述基本思想。
16.4.1 事务重做日志
重做日志记录是一种方法，通过这种方法，以原子方式执行的一组内存修改将存储在日志中，并推迟到所有修改持久化到存储中为止。一旦完成，日志将被标记为完成，并处理（应用）内存修改；然后可以丢弃日志。如果处理在完成之前中断，则会重复日志，直到成功为止。图16-4显示了事务重做日志记录的四个阶段。
在持久内存的上下文中，这种日志记录方法的好处是，所有日志条目都可以一次写入并刷到存储中。重做日志记录的最佳实现只使用两个同步屏障：一次将日志标记为完成，一次将其丢弃。这种方法的缺点是内存修改不能立即可见，这使得编程模型更加复杂。重做日志有时可以与load/store检测技术一起使用，这些技术可以将内存操作重定向到记录的位置。然而，这种方法很难高效地实现，并且不太适合于通用库。
16.4.2 事务撤消日志
撤消日志记录是一种方法，通过这种方法，在修改之前，需要原子修改的组（撤消事务）的每个内存区域都会快照到日志中。一旦所有内存修改完成后，将丢弃日志。如果事务被中断，日志中的修改将回滚到其原始状态。图16-5显示了事务撤销日志记录的三个阶段：
与重做日志方法相比，这种类型的日志可能具有更低的性能特征，因为它需要为创建的每个快照设置一个屏障，快照本身必须是故障安全原子的，这就带来了它自己的挑战。撤销日志的一个好处是，这些更改可以立即可见，允许使用自然的编程模型。
这里的重要观察结果是，redo和undo日志是个不错的设计。对于性能关键的代码和延迟修改不是问题的地方，都可以使用重做日志；对于易用性很重要的地方，使用撤消日志。这一观察结果引领libpmemobj当前设计，一个事务同时采用了这两个算法。
16.4.3 libpmemobj统一日志记录
libpmemobj中的redo和undo日志都共享相同的内部接口和数据结构，称为统一日志（简称ulog）。这是因为redo和undo日志只在日志阶段的执行顺序上有所不同，或者更准确地说，在提交或恢复时应用日志。然而，在实践中，有些性能考虑需要在算法的某些部分进行定制化。
ulog数据结构包含：一个包含元数据的缓存线头和一个可变长度的数据字节数组。标题包括：
- 头和数据的校验和，仅用于重做日志；
- 日志中事务的单调递增生成数，仅用于撤消日志；
- 数据数组的总长度（字节）；
- 组中下一个日志的偏移量。
最后一个字段用于创建参与单个事务的所有日志的单一链接列表。这是因为不可能在事务开始时预测日志的总所需大小，因此库不能提前分配确切的所需长度的日志结构。相反，日志是按需分配的，并以原子方式链接到列表中。
统一日志支持两种故障安全插入条目的方式：
- 批量插入采用一个日志条目的数组，准备日志的头，并创建头和数据的校验和。一旦完成，执行一个非临时拷贝，然后是一个屏障，以将此结构存储到持久内存中。这是一组延迟内存修改形成重做日志的方式，在事务结束时只有一个附加的屏障。在这种情况下，头中的校验和用于验证整个日志的一致性。如果该校验和不匹配，则在恢复期间跳过该日志；
- 缓冲区插入只需要一个条目，将其与当前生成号一起进行校验和，然后通过非临时存储区（后跟一个屏障）将其存储在持久内存中。此方法用于在快照时创建撤消日志。事务中的撤消日志不同于重做日志，因为在提交的快速路径中，它们需要作废而不是应用。不是费力地将零写入日志缓冲区，而是通过增加生成号使日志无效。这是因为数字是校验和数据的一部分，所以更改生成号将导致校验和失败。此算法允许libpmemobj只为事务设置一个额外的屏障（在快照所需的屏障之上），以确保日志的故障安全，从而产生非常低的开销事务。
16.5 持久分配：传统持久分配器接口
libpmemobj中的内部分配器接口比典型的易失性动态内存分配器复杂得多。首先，它必须确保其所有操作的故障安全性，并且不允许任何内存因中断而无法访问。第二，它必须是事务性的，这样堆上的多个操作可以与其他修改一起原子化地完成。最后，它必须在池状态下操作，从特定文件分配内存，而不是依赖操作系统提供的匿名虚拟内存。所有这些因素都促成了一个内部API，它与标准的malloc()和free()很不相似，如清单16-1所示。
Listing 16-1. The core persistent memory allocator interface that splits heap operations into two distinct steps
int palloc_reserve(struct palloc_heap *heap, size_t size,...,
struct pobj_action *act);
void palloc_publish(struct palloc_heap *heap,
struct pobj_action *actv, size_t actvcnt,
struct operation_context *ctx);所有在API中称为“actions“的内存操作都被分解为两个单独的步骤：
第一步预留执行操作所需的状态。对于分配，这意味着检索空闲内存块，将其标记为预留，并初始化对象的内容。此预留存储在用户提供的运行时变量中。库保证，如果应用程序在预留时崩溃，则持久状态不受影响。这就是为什么这些动作变量不能是持久的；
第二步是执行预留的行为，称为“publication发布”。预留可以单独发布，但这个API的真正功能在于它能够将许多不同的操作组合在一起并发布。
内部分配器API还有一个函数来创建一个操作，该操作将在发布时将内存位置设置为给定值。这用于修改目标指针值，有助于使libpmemobj的原子API实现故障安全。
所有需要执行故障安全原子操作的内部分配器APIs都将操作上下文作为参数，该参数是单个日志的运行时实例。它包含各种状态信息，例如日志的总容量和当前条目数。它公开了创建批量或单个日志项的函数。分配器的函数将记录并处理持久日志中属于所提供的操作上下文实例的所有元数据修改。
16.6 持久内存堆管理：持久内存的分配器设计
上一节描述了libpmemobj内部使用的内存分配接口，但这只是分配器冰山的一角。在深入讨论这个主题之前，我们先简要描述一下普通易失性分配器背后的原理，这样您就可以了解持久性内存是如何影响现状的。
传统的易失性内存分配程序负责高效地（在时间和空间上）管理操作系统提供的内存页。准确地说，对于一般的案例，应该如何做到这一点是计算机科学的一个活跃的研究领域；可以使用许多不同的技术。它们都试图利用分配和释放模式中的规则性来最小化堆碎片。
最常用的通用内存分配程序基于一种算法，我们称之为“页面重用和线程缓存分离（segregated fit with page reuse and thread caching）”。
它的工作原理是对许多不同的大小使用一个自由列表，如图16-6所示，直到某个预定义的阈值，之后直接从操作系统分配是明智的。这些空闲列表通常称为bin或bucket，可以通过各种方式实现，例如简单的链表或带有边界标记的连续缓冲区。每个传入的内存分配请求都被取整以匹配其中一个空闲列表，因此必须有足够的空闲列表来最小化每次分配的过度配置空间量。该算法近似于一个最佳匹配分配策略，该策略从可用的内存块中为请求选择剩余空间最少的内存块。
使用这种技术可以使内存分配器在保持最佳匹配的内存效率的同时，具有平均的场景下 O（1）复杂度。另一个好处是，内存块的取整和随后的隔离迫使分配模式具有某种规律性，否则可能不会显示任何规律性。
一些分配器还按地址对可用内存块进行排序，如果可能，则分配与先前选择的块在空间上并置的内存块。这通过增加重用同一物理内存页的可能性来提高空间效率。它还保留了分配的内存对象的时间局部性，这可以最小化缓存并降低页表缓冲（TLB）不中率。
内存分配器的一个重要进步是多线程应用程序的可伸缩性。大多数现代内存分配器实现某种形式的线程缓存，其中绝大多数分配请求直接从专门分配给给定线程的内存中得到满足。只有当分配给线程的内存完全耗尽时，或者如果请求非常大，分配才会与其他线程争夺操作系统资源。
这允许分配器实现在快速路径上没有任何类型的锁，甚至没有原子锁。这可能会对性能产生潜在的重大影响，即使在单线程情况下也是如此。这种技术还可以防止分配器导致线程之间的错误共享，因为线程总是从自己的内存区域进行分配。此外，释放路径通常会将内存块返回到其源线程缓存，从而再次保留本地性。
我们在前面提到volatile分配器管理操作系统提供的页面，但没有解释它们如何获取这些页面。这将变得非常重要，稍后我们将讨论如何改变持久性内存的事情。内存通常是按需从操作系统请求的，可以通过sbrk()移动应用程序的中断segment段，也可以通过匿名mmap()创建由页缓存支持的新虚拟内存映射。实际的物理内存通常在第一次写入页面之前不会被分配。当分配器决定不再需要页时，它可以使用unmap()完全删除映射，也可以告诉操作系统释放备份物理页，但保留虚拟映射。这使得分配器可以在以后重用相同的地址，而不必再次进行内存映射。
所有这些如何具体地转换成持久内存分配器和libpmemobj？
应用程序重新启动后，永久堆必须可恢复。这意味着所有状态信息必须位于持久内存中或在启动时重新构造。如果有任何活动的簿记过程，则需要从中断点重新启动这些过程。持久内存中不能保存任何易失性状态，例如线程缓存指针。事实上，分配器根本不能对任何指针进行操作，因为堆的虚拟地址可以在多次重新启动之间有所改变。
在libpmemobj中，堆被延迟重建并且分阶段进行。整个可用内存被划分为大小相等的区域（除了最后一个区域，它可以比其他区域小），每个区域的开头都有元数据。每个区域随后被划分为大小可变的内存块，称为块chunks。每当有一个分配请求，并且运行时状态指示没有内存来满足它时，就会处理区域的元数据，并初始化相应的运行时状态。这将最小化池的启动时间，并在许多单独的分配请求中分摊重建堆状态的成本。
任何运行时状态都有三个主要原因。首先，持久内存的访问延迟可能高于DRAM，这可能会影响放置在其上的数据结构的性能。第二，将运行时状态与持久状态分离可以使工作流首先在运行时状态中保留并初始化内存，然后才将分配反映在持久状态上。这一机制在前一节中已经描述过。最后，维护复杂持久性数据结构的故障安全性是昂贵的，并且将它们保存在DRAM中允许分配程序避开这一成本。
libpmemobj采用的运行时分配方案与前面描述的块重用和线程缓存相分离。libpmemobj中称为bucket的空闲列表被放置在DRAM中，并作为指向持久内存块的指针vectors来实现。这个数据结构的持久表示是一个位图，位于一个较大的缓冲区的开头，从中分割出较小的块。libpmemobj中的这些缓冲区称为runs，大小可变，并从前面提到的块中分配。非常大的分配直接作为chunks分配。图16-7显示了libpmemobj实现。
持久分配器还必须确保出现故障时的一致性，否则，在应用程序不正常关闭后，内存可能无法访问。解决方案的一部分是我们在上一节中概述的API。另一部分是分配器内部算法的仔细设计，确保无论应用程序何时中止，状态都是一致的。这也得益于重做日志，重做日志用于确保非连续持久元数据更改组的原子性。
持久内存分配最有影响的方面之一是这些内存如何从操作系统被提供。我们之前解释过，对于通用易失性分配器，内存通常是通过背后由页面缓存支撑的匿名内存映射获取的。相反，持久堆必须使用基于文件的内存映射，背后由持久内存直接支持。这种差异可能很微妙，但它对分配器的设计方式有着重大影响。分配器必须管理整个虚拟地址空间，保留堆中任何潜在非连续区域的信息，并避免虚拟地址空间的过度供应。易失性分配器可以依赖于操作系统将非连续的物理页合并为连续的虚拟页，而如果没有显式和复杂的技术，持久性分配器就不能这样做。此外，对于某些文件系统实现，分配器不能假定在第一页出现故障时分配了物理内存，因此对于内部块分配要保守。
从基于文件的映射分配的另一个问题是感觉问题。普通的分配器，由于内存过度使用，似乎永远不会耗尽内存，因为它们分配的虚拟地址空间实际上是无限的。地址空间膨胀会带来负面的性能影响，内存分配程序会主动努力避免这种情况，但在典型的应用程序中也不容易测量。相反，内存堆是从有限资源、持久性内存设备或文件中分配的。更不容易衡量，这加剧了堆碎片化这一常见现象，造成了持久内存分配器的效率低于易失性内存分配器的感觉。实际上的情况是，操作系统在幕后做了很多工作来隐藏传统内存分配器的碎片。
16.7 ACID事务: 高效低层持久事务
我们刚才描述的四个组件——lane、重做日志、撤消日志和事务性内存分配器——构成了libpmemobj实现我们在第4章中定义的ACID事务的基础。
事务的持久状态由三个日志组成。首先是一个撤销日志，其中包含用户数据的快照。第二个是外部重做日志，其中包含用户执行的分配和释放。第三个是内部重做日志，用于执行原子元数据分配和释放。从技术上讲，这不是事务的一部分，但如果需要，则需要分配日志扩展。如果没有内部重做日志，则无法在事务中保留然后发布新日志对象，该事务已在外部重做日志中有了用户自制分配器的操作。
所有三个日志都有单独的操作上下文实例，这些实例存储在通道的运行时状态中。此状态在池打开时初始化，也就是在应用程序的前一个实例的所有日志被处理或丢弃时初始化。没有特殊的持久变量指示日志中过去的事务是否成功。这些信息直接来自于日志中存储的校验和。
当事务开始且不是嵌套事务时，它获取一个lane，该lane不能包含任何有效的未提交日志。事务的运行时状态存储在一个线程本地变量中，这是一旦获取lane变量后存储的位置。
事务分配器操作使用外部重做日志及其关联操作上下文来调用适当的保留方法，该方法反过来创建一个分配器操作，以便在事务提交时发布。分配器操作存储在易失性数组中。如果事务中止，则取消所有操作，并丢弃关联的状态。内存分配的完整重做日志仅在事务提交时创建。如果在创建重做日志时库被中断，则下次打开池时，校验和将不匹配，并且将通过撤消日志回滚来中止事务。
事务快照使用撤消日志及其上下文。第一次创建快照时，将在外部重做日志中创建新的内存修改操作。发布时，该操作会增加关联的撤消日志的生成号，从而使其内容无效。这保证了如果外部日志被完全写入和处理，它会自动放弃撤消日志，提交整个事务。如果丢弃外部日志，则会处理撤消日志，并中止事务。
为了确保不存在同一内存位置的两个快照（这将是对空间的低效利用），应用程序每次要创建撤消日志条目时都会查询一个运行时范围树。如果新范围与现有快照重叠，则会对输入参数进行调整以避免重复。同样的机制也用于防止新分配数据的快照。每当分配事务中的新内存时，都会将保留内存范围插入范围树中。快照新对象是多余的，因为它们将在中止时被自动丢弃。
为了确保事务中执行的所有内存修改在提交后在持久内存上是持久的，ranges树还用于遍历所有快照并对修改后的内存位置调用适当的flush函数。
16.8 变量延迟重新初始化：将易失性状态存储在持久内存
在为持久性内存开发软件时，将运行时（易失性）状态存储在持久性内存位置中通常是有用的。然而，保持这种状态的一致性是非常困难的，特别是在多线程应用程序中。
问题是运行时状态的初始化。一种解决方案是在应用程序启动时简单地遍历所有对象，然后初始化volatile变量，但这可能会显著增加具有大型持久池的应用程序的启动时间。另一个解决方案是延迟重新初始化变量到访问时点，这就是libpmemobj为其内置锁所做的事情。该库还通过API公开此机制，以便与自定义算法一起使用。
易失性状态的延迟重新初始化是使用无锁算法实现的，该算法依赖于存储在持久内存和池头中的每个易失性变量旁边的一个生成号。每次打开池时，池头驻留副本都会增加两个。这意味着有效的生成号总是偶数。当访问volatile变量时，将根据存储在池头中的变量检查其生成号。如果它们匹配，则意味着可以使用该对象并将其简单地返回给应用程序；否则，需要在返回之前初始化该对象，以确保初始化是线程安全的，并且在应用程序的单个实例中只执行一次。
原始的实现可以使用双重检查的锁，其中线程将尝试在初始化之前获取锁，并再次验证生成号是否匹配。如果仍然不匹配，则初始化对象并增加数字。为了避免使用锁带来的开销，实际实现首先使用比较和交换将生成号设置为等于池的生成号减去1的值，该值是表示正在进行初始化操作的奇数。如果这个比较和交换失败，算法会循环回来检查生成号是否匹配。如果成功，正在运行的线程将初始化该变量，并再次增加生成数——这次是偶数，该偶数应与存储在池头中的数字匹配。
16.9 本章小结
本章描述了libpmemobj的体系结构和内部工作原理。我们还讨论了在libpmemobj的设计和实现过程中所做选择的原因。有了这些知识，您可以准确地推理使用此库编写的代码的语义和性能特征。
