探秘持久内存（PMem）中无锁实现多线程安全的持久化数据结构

2021 年 12 月 07 日
本文字数：2955 字
阅读完需：约 10 分钟

来源：原创

如需转载，请注明来自 MemArk 技术社区（MemArk 技术社区 - 助力先进存储架构演进）

关于作者

杨俊，博士毕业于香港科技大学计算机系，在数据库和存储系统上有超过十年的丰富研究和实践经验；现就职于第四范式任系统架构师，同时也是分级存储技术社区 MemArk (https://memark.io/) 的核心成员。近期，由于其在持久内存编程核心社区 Persistent Memory Programming （https://pmem.io/）的卓越贡献，成为被该社区吸纳的中国第一位社区核心贡献者（reviewer）。本文将会介绍作者最近一次的代码贡献，对该社区的后续技术发展有深远影响。

一、背景

持久内存(PMem) 虽然可以保证写入 PMem 的数据掉电重启后不会丢失，但写入 PMem 的数据往往需要先写到 CPU Cache 里，再通过一系列 CPU 指令把数据刷到 PMem 中。由于 PMem 和 CPU 的硬件限制，向 PMem 中写入大于 8 字节的数据并持久化无法保证写操作的原子性（即如果在持久化写入数据过程中掉电，无法保证数据完整写完），所以在 PMem 中保证持久化数据结构的数据一致性是非常有挑战性的。如果该持久化数据结构还需要支持正确的多线程写操作，保证数据一致性将变得更加复杂。本文主要描述此背景下的持久化数据的一致性、可见性问题。

本文适合对于持久化编程有一定基础了解的开发者阅读，本文主要包含内容：

介绍 PMem 无锁编程中的数据可见性、一致性问题及解决方法。
介绍本文作者最近刚合入 libpmemobj-cpp 的一个 PR，专门为方便实现 Single-Writer-Multiple-Reader（SWMR)多线程持久化数据结构的一种自带原子性的持久化指针（Atomic Persistent Pointer）。可在此具体参考该 PR 的讨论开发过程。

二、PMem 的无锁编程

数据可见性是 PMem 无锁编程的非常重要的难点之一。例如某一线程使用 STORE 指令修改了一个内存数据，新数据可能在未持久化到 PMem 时（仍在 CPU Cache 中）就被另一线程读取。假设有如下两个线程分别使用带来原子性的 atomic_write 和 atomic_read 来写入和读取数据：

// 线程1// pmem->a初始化为0atomic_store(&pmem->a, 1);                      // 可见性：是, 持久化：未知pmem_persist(&pmem->a, sizeof(pmem->a));        // 可见性：是, 持久化：是 // 线程2// pmem->b初始化为0if (atomic_load(&pmem->a) == 1) {    pmem->b = 1;                                // 可见性：是, 持久化：未知    pmem_persist(&pmem->b, sizeof(pmem->b));    // 可见性：是, 持久化：是}

复制代码

根据程序崩溃中止的时间点不同，我们从线程 2 的角度来分析 a 和 b 的值的各种可能性：

如果在线程 1 开始前程序中止，则：pmem->a=0，pmem->b=0
如果在两个线程都完成后程序中止，则：pmem->a=1，pmem->b=1
如果在线程 1 结束后程序中止，则：pmem→a=1，pmem→b=0

图 1：数据一致性问题

但是如图 1 所示，如果考虑到 PMem 的持久化特性带来的数据可恢复性，如果在线程 1 刚执行完 atomic_store 未执行 pmem_persist 时，而线程 2 执行完 pmem_persist 后系统掉电，由于 pmem->a 并未持久化 pmem->b 已持久化，将会导致 pmem->a=0,pmem->b=1 这种未预料到的情况发生。

导致这种数据与程序逻辑不一致的问题出现的主要原因，是线程 2 的操作依赖于未被持久化的数据。所以避免这种数据不一致的方法之一，就是在读取数据之后马上进行一次额外的持久化操作，比如线程 2 可以改成：

// 线程2// pmem->b初始化为0if (atomic_load(&pmem->a) == 1) {    pmem_persist(&pmem->a, sizeof(pmem->a));    // 可见性：是, 持久化：是    pmem->b = 1;                                // 可见性：是, 持久化：未知    pmem_persist(&pmem->b, sizeof(pmem->b));    // 可见性：是, 持久化：是}

复制代码

这种方法可以有效避免 pmem->a=0，pmem->b=1 的情况出现（前提是写入线程只有一个，读者可以思考如果写入线程不只一个，此方法会有什么问题）。但是代价也不小，因为每次读取都需要进行一次额外的持久化操作。为了进一步优化性能，我们提出了一种持久化智能指针，不仅支持原子操作，且能根据实际情况，只进行必要的持久化操作。

三、支持原子操作的持久化指针

以下为支持原子操作的智能化指针的具体实现逻辑：

为了支持无锁编程，我们必须使用 8 字节作为持久化指针的大小，但是 pmdk 和 libpmemobj-cpp 中，公开资料中可供使用的持久化指针(persistent_ptr)是 16 字节的“宽指针”。在与 Intel 团队沟通交流后，我们了解到了一个仍处于实验测试阶段的新持久化指针：self_relative_ptr（自偏移指针）。这种持久化指针，巧妙地通过保存数据的地址与此指针对象本身在 PMem 中的地址之间偏移量（8 字节），将持久化指针缩小为 8 字节，为持久化指针带来了支持原子操作的可能。
在 self_relative_ptr 的基础上，我们进一步发现，支持原子操作的数据地址都必须是 8 字节对齐的，所以其地址的低 3 位始终为 0。于是，我们通过复用指针地址最低位，作为 dirty_flag 来区分读取前需要先持久化的指针。最终我们实现了一种支持原子操作的持久化指针：atomic_persistent_aware_ptr。该类最重要的两个 API 就是类似于 atomic 标准类的 store/load，可以原子性的读取和写入 self_relative_ptr 对象，具体流程如下：

a. Store

- 修改传入的 self_relative_ptr 对象所指向的地址，将最低位设为 1，表示此指针未持久化

- 将修改后 self_relative_ptr 中通过原子写，保存到内部的 atomic 对象中

b. Load

- 通过原子读，得到内部 atomic 对象中的 self_relative_ptr

- 如果该 self_relative_ptr 最低位为 1，则进行一次持久化操作，并使用 CAS(compare-and-swap，标准 atomic 类支持的一种原子操作，在条件成立时赋值）将内部 atomic 对象中的 self_relative_ptr 的最低位清零

- 返回最低位清零后的 self_relative_ptr
不难发现，上述操作只在 Load 时，self_relative_ptr 最低位为 1 时才进行持久化操作，并在持久化后将最低位清 0，有效的避免了重复进行持久化操作，且保证了数据可见时已持久化。
读者可能还注意到，我们将持久化操作与写操作（Store）进行了分离，可以说是一种对写多读少场景的优化，与此对应的，我们也实现了一个针对写少读多场景的优化。具体详情可参考源代码。

以上实现逻辑已经合入 libpmemobj-cpp，具体源代码可以参考：atomic_persistent_aware_ptr 。在此持久化指针的基础上，正确实现上述的例子将会变得非常简单，且不会出现 a=0，b=1 的数据不一致情况出现：

// 使用libpmemobj-cpp的transaction分配PMem对象可以保证无内存泄露self_relative_ptr<int> one;try {    pmem::obj::transaction::run(pop, [&] {        one = nvobj::make_persistent<int>();    //在PMem中分配一个int        *one = 1;                               //设为1        pmem_persist(one, sizeof(int));         //持久化    });} catch (...) {    ASSERT_UNREACHABLE;}  // 线程1atomic_persistent_aware_ptr<int> a;a.store(one);                                   //直接使用atomic_persistent_aware_ptr提供的store函数写入 // 线程2atomic_persistent_aware_ptr<int> b;if (*(a.load()) == 1) {                         //直接使用atomic_persistent_aware_ptr提供的load函数读取    b.store(one);}