How Should We Think about Persistent Data Structures?
How Should We Think about Persistent Data Structures?
复制标题
我们应该如何看待持久数据结构？
DOI：
10.1145/3519270.3538455
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Scott, Michael L.
中科院分区：
文献类型：
--
作者：
Scott, Michael L.
对于具有非易失性内存（NVM）但具有易失性缓存的机器，大多数关于持久数据结构的工作都假设每个操作都必须保证能够在返回调用者后发生的任何崩溃中幸存下来。然而，大多数程序员不想保留现有的瞬态结构：他们希望避免对传统上保存在块结构文件和数据库中的结构进行序列化和反序列化。对于这些，程序员习惯于缓冲语义，这允许延迟持久性——要么延迟一小段时间，要么直到执行显式同步操作。 Rochester 的 Montage 系统的实验证实，缓冲持久性可以接近 NVM 中非持久性结构的性能，这可以说是人们所希望的最好的，并且比具有更严格语义的系统快得多。随着 NVM 的激增，将会有越来越多的机会来软化（瞬态、字节可寻址）内存和（持久、块结构）存储之间的传统界限。当我们寻求形式化持久数据结构的开发时，PODC/DISC 社区不仅要考虑替代的正确性标准，还要考虑不断发展的硬件特性。需要考虑的问题包括逐出和非逐出回写之间的选择、非易失性缓存的引入，以及 NVM 带宽和延迟可能随访问粒度、局部性和并发 DRAM 活动而发生很大变化的可能性。
For machines with nonvolatile memory (NVM) but volatile caches, most work on persistent data structures has assumed that every operation must be guaranteed to survive any crash that occurs after returning to the caller. Most programmers, however, don't want to persist existing transient structures: they want to avoid serializing and deserializing structures traditionally kept in block-structured files and databases. For these, programmers are accustomed to buffered semantics, which allow persistence to be delayed-either for a brief period of time or until the execution of an explicit sync operation. Experiments with Rochester's Montage system confirm that buffered persistence can approach the performance of non-persistent structures placed in NVM-arguably the best one could hope for, and dramatically faster than systems with stricter semantics. As NVM proliferates, there will be more and more opportunities to soften the traditional boundary between (transient, byte-addressable) memory and (persistent, block-structured) storage. As we seek to formalize the development of persistent data structures, the PODC/DISC community will want to con-sider not only alternative correctness criteria, but also evolving hardware characteristics. Issues to be considered include the choice between evicting and non-evicting write-back, the introduction of nonvolatile caches, and the possibility that NVM bandwidth and latency may vary greatly with access granularity, locality, and concurrent DRAM activity.