乐趣区

关于机器学习:探秘持久内存PMem中无锁实现多线程安全的持久化数据结构

jiezi

起源：原创
如需转载，请注明来自 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 初始化为 0
atomic_store(&pmem->a, 1);                      // 可见性：是, 长久化：未知
pmem_persist(&pmem->a, sizeof(pmem->a));        // 可见性：是, 长久化：是
 
// 线程 2
// pmem->b 初始化为 0
if (atomic_load(&pmem->a) == 1) {
    pmem->b = 1;                                // 可见性：是, 长久化：未知
    pmem_persist(&pmem->b, sizeof(pmem->b));    // 可见性：是, 长久化：是
}

依据程序解体停止的工夫点不同，咱们从线程 2 的角度来剖析 a 和 b 的值的各种可能性：

  1. 如果在线程 1 开始前程序停止，则：pmem->a=0，pmem->b=0
  2. 如果在两个线程都实现后程序停止，则：pmem->a=1，pmem->b=1
  3. 如果在线程 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 初始化为 0
if (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 的状况呈现（前提是写入线程只有一个，读者能够思考如果写入线程不只一个，此办法会有什么问题）。然而代价也不小，因为每次读取都须要进行一次额定的长久化操作。为了进一步优化性能，咱们提出了一种长久化智能指针，不仅反对原子操作，且能依据理论状况，只进行必要的长久化操作。

三、反对原子操作的长久化指针

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

  1. 为了反对无锁编程，咱们必须应用 8 字节作为长久化指针的大小，然而 pmdk 和 libpmemobj-cpp 中，公开材料中可供使用的长久化指针 (persistent_ptr) 是 16 字节的“宽指针”。在与 Intel 团队沟通交流后，咱们理解到了一个仍处于试验测试阶段的新长久化指针：self_relative_ptr（自偏移指针）。这种长久化指针，奇妙地通过保留数据的地址与此指针对象自身在 PMem 中的地址之间偏移量（8 字节），将长久化指针放大为 8 字节，为长久化指针带来了反对原子操作的可能。
  2. 在 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
  1. 不难发现，上述操作只在 Load 时，self_relative_ptr 最低位为 1 时才进行长久化操作，并在长久化后将最低位清 0，无效的防止了反复进行长久化操作，且保障了数据可见时已长久化。
  2. 读者可能还留神到，咱们将长久化操作与写操作（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;}
 
 
// 线程 1
atomic_persistent_aware_ptr<int> a;
a.store(one);                                   // 间接应用 atomic_persistent_aware_ptr 提供的 store 函数写入
 
// 线程 2
atomic_persistent_aware_ptr<int> b;
if (*(a.load()) == 1) {                         // 间接应用 atomic_persistent_aware_ptr 提供的 load 函数读取
    b.store(one);
}

四、浏览更多

MemArk 社区官网：https://memark.io/
分级存储技术专栏
Join Slack Workspace
扫码进入分级存储微信技术探讨群（点击关上二维码）

退出移动版