持久内存系统设计简介

持久内存系统提供一种通过Load/Store指令来以字节寻址的方式直接访问持久内存（PM）的接口，而不是通过文件系统的形式使用持久内存。其中，Mnemosyne, NV-Heaps与Heapo 是早期设计的解除代表，前两者发表在 ASPLOS 上，后者发表在 TOS 上。Mnemosyne 提供了一套简便易用的持久内存使用接口，而 NV-Heaps 和 Heapo 提供了基于（常用数据结构）对象的内存访问接口，是更高一层的抽象和封装。

我们 DDST 内存管理组也在 863 内存计算项目的驱使下，也开发了一套名为 Daisy 的持久内存系统，主要实现了对 PM 的持久区域抽象、持久区域管理以及持久内存下的数据一致性保证。

然而，在将我们组的工作整理成一篇论文的过程中，我遇到了许多设计层面的问题：

Introduction 模板

一个 Introduction 也许是论文中最重要的部分，不，它就是最重要的部分。Introduction 应当简明扼要地介绍论文工作的背景，研究点及其动机，相关工作解决的问题及其局限性，自身工作的特点、优势及贡献，实验如何开展，结果如何，有什么效果和影响，以及文章的布局结构又是如何。

虽然知道大概要以这样的标准来写一篇优秀的 Introduction，但实际上做的时候，则会因为自身水平的局限性和工作内容创新的局限性而与真正的优秀之作相距甚远。

初稿是粗糙且未经检查的不完全版本，果不其然，被老师打回来要求一字一句重新来过，模仿优秀论文的 Introduction 来写好我自己的文章。

所以，我整理了四套模板以供参考，第一套是老师给我的模板（多用于算法领域），另外三份则是持久内存系统的三大开山之作，对我的工作更具参考价值。

老师的模板

  • 问题是什么？
  • 为什么这个问题是有趣且重要的？
  • 它的难度/挑战在哪里？简单的方法为什么不行？
  • 针对这个问题，state-of-the-art的解决方案为什么不适用？其瓶颈在哪？
  • 关键的设计组成部分是什么？它的作用和功能是什么？有什么特殊限制么？
  • 本工作的贡献是什么，罗列三点：
    • 我们做了······
    • 我们还做了······
    • 我们做了一系列丰富的实验，并且结果体现了我们设计的优越性，超过某某方案多少······
  • 文章的谋篇布局介绍
    • 第二部分介绍了某某问题/背景······
    • 第三部分给出了一个概览/设计模型
    • 第四部分介绍了方案/机制/系统的实现
    • 第五部分讲述了实验并给出详细的分析
    • 第六部分介绍了相关的重要工作
    • 最后一部分对全文做出总结

Mnemosyne 风格

  • 第一段：引出故事的主角——Persistent Memory。
  • 第二段：介绍现有（操作）系统设计的特点，以及在新技术面前的局限性。
  • 第三段：介绍 Mnemosyne 自己的设计思想（第一层——抽象 PM 为内存直访）。
  • 第四段：介绍 Mnemosyne 将如何使用新型 PM 作为开发基础，即路线的选择——不是文件系统而是直接字节寻址内存的快速存取。
  • 第五段：提出设计目标——一个持久内存能系统所应该具备的功能：
    • 编程简便性
    • 支持一致性数据变更
    • 与现有处理器设计相兼容
  • 第六段：介绍核心工作——开发了一个怎样的系统：目的，功能。
    • 一个轻量级的内存系统（提供便捷的用户接口）
    • 提供持久区域的抽象
    • 持久化原语
    • 持久化内存事务及一致性保证
  • 第七段：介绍自己系统的特色，做分化——其他工作的使用条件与局限性
    • 细粒度（low-level）的接口
    • 不同级别的一致性保证
    • 不需要使用 object framework
  • 第八段：系统实现部分的简明介绍。
    • 在什么内核/系统上实现
    • 用什么模拟 PM
  • 第九段：实验评估部分的简要介绍。
    • Microbenchmark 是什么
    • 应用级 benchmark 是什么
    • 结果展示及评价
  • 第十段：标准段——贡献介绍
    • 一套管理和暴露持久内存给用户程序的层级架构
    • 数据一致性的保证和一套用户库函数
    • 软件事务内存机制的持久化策略
    • 一个新颖的原子写日志方法
  • 第十一段： 标准段——文章的组织结构
    • PM 概述（背景介绍）
    • Mnemosyne 设计
    • Mnemosyne 实现
    • Mnemosyne 的事务机制
    • Mnemosyne 性能实验及分析
    • 相关工作
    • 总结

NV-Heaps 风格

  • 第一段：Purpose-built 持久化数据结构的问题论证：选题内容基石稳固。
  • 第二段：举更具体的应用例子以充实持久数据结构的课题研究价值，并在下文中列出其操作瓶颈，指明 Motivation。
  • 第三段：引出 PM 新型硬件并简要介绍，为后文做铺垫
  • 第四段：揭示现在的持久对象数据设计对于利用 PM 提高性能是十分不合适的，需要 reengineering work。
  • 第五段：揭示直接应用传统内存管理方案到 PM 上的问题，进一步揭示 Motivation。
  • 第六段：NV-Heaps 的设计目标和主要特征。
    • 对于持久数据对象提供灵活、健壮的抽象
    • 自包含，可以像使用文件一样使用NV-Heaps提供的持久对象
  • 第七段：标准段——设计特色/贡献介绍
    • 指针安全性
    • 灵活的 ACID 事务机制
    • 熟悉的接口
    • 高性能
    • 可扩展性
  • 第八段：文章主要内容简介【注意：与Organization部分有很大区别，这里的介绍要突出重点】
  • 第九段：实验结果及简要分析
    • 和谁比？Berkeley DB
  • 第十段：标准段——文章的组织结构
    • NV-Heaps 概述
    • NV-Heaps 实现
    • 实验方法
    • 实验结果及分析
    • 总结

Heapo 风格

  • 第一段：引子——大数据时代对大容量内存的需求。
  • 第二段：介绍现如今内存瓶颈并解释其问题所在。
  • 第三段：介绍新型硬件及其显著的特性。为下文的技术利用做下铺垫。
  • 第四段：陈述工作内容——一个轻量级、灵活的 management layer for persistent memory，与文件系统的mmap机制划清界限。
  • 第五段：标准段——强调特性，即贡献点。
    • Native management layer for persistent heap
    • Global name space with local name space caching
    • 可扩展的对象机制设计
    • 静态绑定（区别于动态绑定，需要额外的工作量）：一段特殊的虚拟地址段保存下来，为本地持久堆空间所使用，所有进程共享全局持久堆空间
  • 第六段：Heapo的设计与众不同之处，比起mmap优越性如何。
    • 消除元数据冗余
  • 第七段：说明实验——如何进行，结果如何，意义多大。
  • 第八段：标准段——文章的组织结构。
    • 背景简介：PM，持久堆空间和字节 mmap
    • Heapo 设计
    • Heapo 实现
    • Heapo 实验
    • 相关工作
    • 总结

我决定采用的风格

以 Mnemosyne 风格模板为主，参考其他三部分的重要内容，整合成一份模板：

  • 第一段：引出故事的主角——PM。
  • 第二段：介绍现有操作系统的特点，以及为何不能直接适用新技术 PM。
  • 第三段：介绍 Daisy 的设计思想（抽象为 Load/Store，便捷熟悉的内存调用接口，细粒度的访问控制）
  • 第四段：介绍 Daisy 将如何使用新型 PM 作为开发基础，即路线的选择——不是文件系统也不是Object Store 的形式而是直接字节寻址内存的快速存取。
  • 第五段：说明 Daisy 的设计目标和主要特征。
  • 第六段：介绍核心工作——开发了一个怎样的系统，目的和功能。
  • 第七段：介绍系统特色，与众不同之处及优越性，与其他工作相区别（Related Work 初步）
  • 第八段：系统实现——在什么系统上构建和实现，模拟平台？
  • 第九段：实验评估部分的简要介绍。
  • 第十段：标准段——贡献介绍
  • 第十一段：标准段——文章组织结构
    • 相关工作（因为到了17年，持久内存的系统设计已经不是新颖的工作了）
    • Daisy 概述
    • Daisy 实现
    • Daisy 一致性保障机制
    • 实验评估
    • 总结

Daisy：说个故事给你听

Daisy 始于项目，但要终于科研。如果它不是一个具有创新性的或是极具工程应用潜力的研究，那么对于科研来说它也就毫无价值可言。

传统的内存，一般我们称之为 DRAM（硬件角度）易失性内存，当系统掉电后，运行中的数据会全部丢失。另外，在大数据时代，应用对内存的需求与日俱增，而 DRAM 因为价格昂贵、能耗较高、可扩展性不强等原因难以满足应用对大内存的需求（Memory Wall）。

而新型的持久内存硬件技术如 PCM, FeRAM, STT-RAM 等则有效缓解了传统 DRAM 的瓶颈：持久内存（PM）一方面可以具有类似 DRAM 的字节寻址、存取速度快的特性，另一方面又具有类似磁盘或 Flash 的非易失和大容量的特性。这就为持久内存系统的设计提供了新的机遇。

一个简单的想法是直接将 PM 当成是 DRAM 的地址空间扩展，按照传统的内存管理机制来管理 PM 的空间。这样虽然可以利用 PM 的大容量特性，但却无法有效利用它的非易失特性，因为对于 DRAM 和 PM 的混合内存区域，如果不加区分，用户将无法知道什么数据存储在 DRAM 中，什么数据又存储在 PM 中。

我们的目标是充分利用 PM 的非易失特性，使得任意的数据（结构）能够被有效且迅速地持久化到 PM 中并在有需要的时候能够快速取回这些数据（结构）。于是，re-engineering 的工作就成为了必须。

利用文件系统的 mmap 机制可以将块设备上的文件地址空间直接映射到进程地址空间（内存中），并在需要持久化的时候通过 msync 机制将内存中的内容同步到持久设备上。类似地，可以利用 mmap 机制构建一个基于 PM 的持久内存文件系统，但是文件系统存在较大的元数据开销，且在许多应用场景中，用户程序并不需要使用文件作为媒介来存储内容。

这激发了我们设计一个轻量级的持久内存系统，它可以提供类似传统的 malloc、free 那样便捷易用的接口来使用 PM；它能够用户透明地将分配给用户使用的内存区域管理起来，并且在系统故障后，用户能够快速方便地取回原来持久化过的数据；它能够保障系统数据和用户数据的一致性，并且提供对用户有好的一致性保障接口。

Daisy 与现有的持久内存系统均不相同，体现在以下几点：

  • 第一，Daisy 的内存映射机制基于动态地址映射而不是一般考虑的静态地址映射，并通过持久指针结构的设计有效解决了程序重新运行后的指针地址失效问题；
  • 第二，Daisy 通过持久 ID（pID）table 来细粒度地分配和管理供用户程序使用的持久区域，而不是通过持久object 的形式来使用持久区域，并且在插入删除等操作上速度非常快；
  • 第三，Daisy 通过简洁的 undo log 日志结构保障了系统数据和用户数据的一致性。

Daisy 的贡献主要有以下三个方面：

  • 第一，基于 pID table 的持久用户空间管理方案（这个方案新颖在何处，性能效果好吗）
  • 第二，基于动态地址映射的非易失指针（NVP）数据结构设计（如何证明？比起NV-Heaps又如何）
  • 第三，基于 undo log 的一致性保障机制及两套恢复算法：全局/局部（比起 Mnemosyne 的redo log有何优势，比起 Heapo 的 undo log 又有何优势）

Daisy 的系统框图如下：

应用 Daisy 的典型工作流程如下：

  • 数据写：p_malloc 申请持久内存 （第一次会通过 p_init 初始化一段用户堆地址空间）-> 将数据写入申请到的持久内存 -> 通过 p_bind 绑定该段数据结构 ID 到堆地址空间
  • 数据读：通过 p_get_bind_node 获取指定 ID 的数据结构所在持久内存的基址，按照地址顺序读取原先写入的数据；
  • 记录日志：通过 log_create 开辟一个日志空间并指定事务 ID，这一 ID 与需要被记录日志的持久化数据结构相同，再更新数据前，可以通过 transaction_record 执行一次原子写操作，记录到 undo log 数据结构中并更新相应的元数据。
  • 删除日志：当某段数据结构确认持久化完成时，通过 log_delete 删除日志与持久化数据结构的关系并使用 memset 将 log 所有键值对重置为 NULL 值。
  • 数据恢复：扫描活动事务列表 T_LIST，确定发生数据不一致的数据（结构）ID，找到对应的 undo log， 先自上而下恢复数据到旧值，再自下而上恢复持久空间到旧的状态。