Paper Title: HTMFS: Strong Consistency Comes for Free with Hardware Transactional Memory in Persistent Memory File Systems
Link: https://www.usenix.org/system/files/fast22-yi.pdf
Year: FAST 2022
Keyword: NVM; File System; HTM

This head was adopted from here, please contact me if it’s not appropriate.

Motivation

Performance 和 strong crash consistency[^1] 一直是设计文件系统时的天平两端，很难权衡。本文结合 Persistent Memory(PM) 字节寻址能力和 Hardware Transactional Memory(HTM) 多操作原子性作为新的底层机制来设计 PM 上的文件系统，以图同时获得高性能和强一致性（不光是 strong crash consistency 还要保证 concurrent correctness）。

Background

HTM 及其对性能和一致性的意义

  • Transactional Memory 是类似 Lock 的一种新并发原语。使用者只需将代码段声明式地包裹在 xbegin 和 xend 之间，该代码段的所有内存访问就被保证具有原子性、隔离性和可串行性。这种原语比锁更高级、更易用。
  • Transactional Memory 只是一种抽象语义，其实现可以是硬件或软件的。硬件实现即 HTM 实际使用乐观并发控制(OCC)来保证上述性质。具体来说，cache 是 OCC 中维护 local copy 的地方，同时借助 cache coherence protocol 来进行冲突检测。HTM 因为足够底层，在很多情况下比锁更高效。
  • 只要将关键的内存访问用 HTM 包裹就自然的保证了并发正确性。与此同时，如果包裹的是 PM 的内存访问，那也就很自然的实现了 strong crash consistency（crash 发生时，HTM 保证不会将某操作的中间状态写入 PM）. 这减少了通过 logging 或 Copy-on-Write 实现崩溃一致性的 overhead.

Challenge

  • 事实上，大部分硬件平台上的 HTM 并不会在一个事务 commit 时 flush cache lines, 而只是让修改全局可见[^2]. 这使得 strong crash consistency 不再能保证。而在 HTM 中显式地 flush 又会触发 HTM abort[^3]. 幸运的是，本文提到的 Intel 新硬件平台为 cache 也提供了持久化保证：当某 cache line 全局可见时, 它就保证被持久化。这一保证使得 PM 上的事务 commit 与持久化等价。
  • HTM 因为依赖于 cache 作为 local copy, 所以其允许的内存访问量是有限的。而文件系统的很多操作会有大量的 memory access 以至于超出容量限制导致 abort.

Solution：HOP

为了解决文件系统操作容易超限的问题，首先观察到超限主要有如下两类情况：

  • 一类是本身较长的处理逻辑，比如 open 操作前必然先进行 path walk。这篇文章通过 OCC 来避免。
  • 另一类是大量的数据读写，这是作为文件系统必须要处理的情况。这篇文章通过 CoW 来避免。

利用 OCC 分解处理步骤

一次文件系统请求引起的内存访问有三种类型：读；不可见写（如内存分配）；可见写（如修改文件系统元信息）。HOP 只将可见写包在 HTM 中保证事务性。同时为了保证并发正确性，HOP 为每个共享数据都维护了时间戳（文章中称为 seqcount），读一个数据时会记录该时间戳并在与可见写同一个 HTM 中 validate，以此来确保整个请求的原子性。validate 失败时会重新尝试读取并重新执行 HTM.

以 touch /a/b/c 为例, 会先记录一路上 dentry 的时间戳，并在最后开启一个事务 validate 同时向 /a/b 目录插入新的 dentry.

通过这个方法，那些较长的处理逻辑可以被分解，只有可见写需要在 HTM 中，而这对绝大多数情况都足够了。

利用 CoW 处理大量数据读写

读请求不会受并发的写操作影响，只需要保证读到某一时刻的一致性状态即可[^4]。因此只需要记录所读页面的 seqcount 并在最后 validate 一下，并且不需要在 HTM 中。

写请求采用 CoW 做法，即先写到影子页中，最后在 HTM 里原子地替换指针。这里稍微有点 tricky 的是内存分配问题：当然不能将内存分配和可见写包在同一个 HTM 里，这会导致事务过长。依然采用类似 OCC 的做法，首先读取内存分配信息，在 DRAM 中进行内存分配并写影子页，最后在 HTM 里原子地将分配信息写回 PM. 然而，这样做存在安全隐患，假如系统在写影子页后 crash，因为此时分配信息还未持久化，恢复后影子页还属于未分配内存，而其中却有之前写过的数据，产生了信息泄露。

为了解决安全问题，这篇文章采用 undo logging 的方式在写影子页前先持久化日志，最后在之前提到的 HTM 里删除日志。这样的话，在崩溃恢复时就能通过日志清除掉上次进行一半的写入。

Other issues

Progress

HTM 这样的乐观并发控制并不保证 progress，因此需要自己设计 fallback-path. 这篇文章采用了两级 fall-back path. 如果 HTM abort 次数过多首先进入第一级：inode lock 保证并发正确性 + HTM 保证崩溃一致性，此时 HTM 中只执行可见写而不验证 seqcount，因此 abort 的几率小很多[^5]。但如果此时还是不停 abort 则进入第二级使用日志来保证崩溃一致性，完全不使用 HTM，此时一定能 make progress.

Prevent abort

HTM 的性能显然与 abort 的几率高度相关，通过实验发现主要有如下几个原因：

  • page fault：文章中通过预先触发 page fault 来避免中断带来的 abort.
  • conflict：利用上面说的 fallback path

[^1]: Operation atomicity in spite of power loss or system crash.
[^2]: 以 cache coherence 中的 MSI 模型为例, 只需 invalidate 所有其它 cache 中的该行数据就能达到修改全局可见的效果，无需真的 flush.
[^3]: flush 使得部分修改全局可见破坏了原子性，因此触发 abort.
[^4]: 这里类似 Linearizability 的概念
[^5]: 理论上来说可见写的内容应该已经被 inode lock 保证互斥性了，为什么还会 abort？我没有仔细考证