持久内存有一些特性，如果不善加利用，往往无法感受其独到之处，如可按字节寻址、持久性和原地更新等等，这有助于我们构建速度比所有要求序列化或者刷新到磁盘的数据结构快的多的新数据结构。
当然这不会那么容易，需要一定的付出：精心设计算法，保持数据一致性等等。下面介绍如何设计此类数据结构和算法，以及它们应该具有哪些属性。
在设计适用于持久内存的数据结构时,碎片化是最关键的因素之一。为了有效利用持久内存，应该在设计数据结构时确保最大限度地降低碎片化程度。
- 内部和外部碎片化
内部碎片化是指已分配的众多内存块中超额预留的空间。内存分配器通常以固定大小的块（chunk）和桶（bucket）的形式返回内存地址。分配器必须确定每个桶的大小，以及它要提供多少个大小不同的桶。如果内存分配请求的大小与预定义的桶大小不匹配，分配器就会返回一个较大的桶。这很容易理解，例如应用程序请求分配200kib的内存，但分配器有大小为128kib和256kib的桶，那么该请求将从可用的256kib桶分配。由于内部对齐的要求，分配器通常必须返回大小可被16整除的内存块。举个例子，你去乘坐公交车，上车以后发现门口座位上坐着一个3岁的小孩，小孩在椅子中央端坐，椅子周围还有很多余地，但你无法入座，座椅的余地就是内部碎片。
内存分配时为什么必须被16整除？
视处理器体系结构而定，所有的内存分配必须起始于可被 4、8 或 16 整除。"段基址是 16 的整数倍"，这是因为, 在计算有效地址时, 是段寄存器的值左移四位 + 偏移地址.，左移四位等效于乘以 16, 所以最后的结果就是段基址是 16 的倍数了。在英特尔硬件上，原子持久存储为8字节。
如果可用内存分散在小内存块中，就会出现外部碎片化。举个例子，好比你周末去乘地铁，开门以后你冲进去发现座位上已经有不少人了，虽然人和人之间还有一些空隙，但是有点窄了你无法入座，这个空隙是外部碎片。
将一组元素存储到持久内存中华时，可以使用以下几种数据结构：
- 链表：各个节点从持久内存分配
- 向量：动态数组，一种大块的预分配内存的数据结构，当有新元素加入而空间不足时，它将分配一个容量更大的新数组，并将所有元素从旧数组移动到新数组中。
- 段向量：一列由固定大小的段组成的链表。如果任何段中都没有剩余可用空间，则会分配一个新段。
考虑对这些数据结构进行碎片化处理： - 对于链表，碎片化率取决于节点大小。如果节点足够小，内部碎片化率就较高。在节点分配期间，每次分配器都会以某种对齐方式返回不同于节点大小的内存地址空间。
- 使用动态数组会减少内存分配数量，但每次分配的大小不同，多数采用前一次分配大小的2倍来实现，这会导致较高的外部碎片化。
- 使用段向量，段的大小是固定的，因此每次分配的大小相同。这实际上消除了外部碎片化，因为我们可以为每个已释放的段分配一个新的段。
- 原子性和一致性
数据一致性需要确保数据的正确存储顺序，以及数据被持久性地保存。系统必须使用额外的机制来保证存储大于8字节长度的数据原子性。下面介绍几种机制并探讨他们的内存和时间开销。在时间开销方面，重点是分析刷新次数和所使用的内存屏障，因为它们对性能的影响最大。- 事务
可以使用事务来确保数据的原子性和一致性。“支持版本控制的有序数组”就是使用事务的数据结构。使用事务是确保一致性的最简单解决方案。尽管使用事务可以轻松实现大多数操作的原子性，但有两点需要注意：第一，使用日志记录的事务通常会引入额外的内存和时间开销。第二，在使用撤销日志的情况下，内存开销与你修改的数据大小成正比，而时间开销则取决于快照数量。在修改快照数据之前，每个快照必须实现持久化。
设计适用于持久内存的数据结构时，建议使用面向数据的方法，因为这样存储数据后，CPU处理的方式对缓存非常友好。（> SoA和AoS） - 写时复制和版本控制
另一种保持一致性的方法是写时复制CoW技术。尽管这种方法比事务更快，但实现难度更大，因为必须手动将数据持久化。、cow通常适用于多线程系统，在该系统中可以使用引用计数、垃圾回收等机制释放不再使用的副本。
版本控制是类似于CoW的概念。它保存数据字段的多个版本，每次修改都会创建新版本的字段，并存储有关信息。
- 事务
- 选择性持久化
持久内存的读写速度比磁盘快，但比DRAM慢。我们可以实现混合数据结构，将一部分存储在DRAM中，一部分存储在持久内存中，从而加速性能。在DRAM中缓存热数据可以降低访问延迟，并提升总体性能。
数据并不总是需要存储在持久内存中的，可以在应用程序重新启动时重构数据，因为可以从DRAM访问数据且不需要事务，所以可改进运行时性能。 - 数据结构示例
- 使用事务的散列表
一个使用事务实现的散列表和使用libpmemobj-cpp实现的容器。 - 使用事务和选择性持久化的散列表。
- 支持版本控制的有序数组。
总结
为了保持数据一致性，事务是最简单、最不易出错的方法。写时复制和版本控制的效果更好，但是正确实现的难度极大。
网友评论