持久内存的易失性优势：第二部分 - Dormando (2019 年 5 月 8 日)
鉴于这个对我们来说全新的硬件平台，我们希望找到新的方向来探索。我们发现的结果令人着迷：问题比预期的要无聊得多。
未来：实验观察
我们对数据结构进行了小型调查：DRAM 和 PMEM 非常相似，但 PMEM 的延迟更大。Memcached 具有传统的 链式哈希表。是否有任何更现代的数据结构可以减少对 PMEM 的往返次数，从而产生影响？
我们还没有找到任何能够带来巨大改进的东西。本文的其余部分将介绍其中一些想法以及它们的结果。
事实证明，我们现有的数据结构在面对 PMEM 时已经过优化。 LRU 算法 试图最大程度地减少对频繁访问项目的 LRU 的修改。从那里，大多数内存访问发生在项目元数据中，这些元数据适合 DRAM 缓存行（64b）。PMEM 自己的缓存行是 256 字节，通常会包含元数据和整个键。这意味着比较键以找到匹配项，以及由此产生的元数据检查，会导致对底层 PMEM 进行单次获取。
频繁访问的项目也受益于处理器缓存，因此热门或最近的键会在无需任何进一步工作的情况下获得性能提升。
链式哈希表
理论：当桶很深时，链式哈希表的性能很差，这可能会加剧 PMEM 的延迟。
现实：memcached 在平均深度超过每个桶 1.5 个项目之前会自动调整哈希表大小。性能差异很小。
主要关注的是链式哈希表。哈希表是通过指向指针的扁平数组实现的。一个键被哈希到一个桶号，如果桶是非空的，则找到一个项目。然后必须将键与请求进行比较，以确保它是请求的精确项目。
在发生冲突的情况下，桶通过单链表“增长”更深。项目结构中的一个指针指向下一个哈希表项目。这意味着每个找到的不是所需项目的项目都会创建一个额外的往返 PMEM。
当 Memcached 中的条目数量（“负载”）达到原始数组大小的 150% 时，它会自动将哈希表的大小翻倍。哈希表密度将在 50% 到 150% 的负载之间变化。如果哈希算法完全公平，平均桶深度在最坏情况下为 1.5。实际上，最坏情况会高于 1.5，但不会高很多。
为了进行快速测试，我们用 201,326,591 个条目填充了 Memcached，足以使哈希表负载略低于 150%。然后我们强制哈希表扩展，将其负载降至 50%。在这种设置下，我们运行了之前提到的“现实”负载测试，该测试使用大量客户端连接。
在这里，我们查看了系统调用密集型测试的平均延迟，只改变哈希表的大小。所有请求都来自持久内存。随着服务器变得更繁忙，时钟稳定下来，延迟略有下降，然后随着服务器过载，延迟开始上升。这些测试的 p99 延迟是随机的，因为测试的本质是大量排队的连接，并且性能彼此接近。只有实际平均值在多次测试运行中显示出一致的差异。
我们看到，超大的哈希表确实赢了。注意延迟有多接近：最坏情况下的哈希表平均每秒损失 5 微秒。如果你需要榨取每一滴性能，扩大哈希表的大小可以有所帮助。否则，它并不是一个巨大的胜利。
引用计数燃烧
理论：每次读取都会导致对持久内存的写入：引用计数更新、LRU 突变等。这可能会导致一个大问题。
现实：几乎没有区别。禁用引用计数和 LRU 重新排序的基准测试表明，性能仅提高了 5%。
大多数内存访问都在项目内存之外：连接缓冲区、统计计数器，甚至哈希计算在大多数情况下都在请求输入缓冲区上执行，而不是在项目内存上执行。
为了满足一个 GET 请求，项目内存几乎没有被触碰。
- 项目键与请求缓冲区进行比较，以完成哈希表查找。
- 测试过期时间。
- 如果匹配，则增加引用计数。
- 如果一些位标志和“最后访问时间”没有被最近更新，则可能会更新它们。
- 键值被异步写入客户端套接字。
- 引用计数减少。
由于 Intel PMEM 以 256 字节的切片加载内存，对于大多数工作来说，足够小的项目可能只产生一次读取。其余的小读取由 CPU 缓存处理。LRU、最后访问时间和标志并不总是更新。对于繁忙的项目，只有两个字节的引用计数会被调整。即使项目元数据在代码中被引用了几次，但访问 PMEM 的延迟惩罚是固定的。
分层内存
理论：最近插入的项目最有可能被访问或替换。将项目刷新到 PMEM 时，它们的使用频率较低，这应该可以提高性能。
现实：它更慢
该LRU 算法方便地将内存分为 HOT（新）、WARM（频繁访问）和 COLD（不常访问）。如果 COLD 项目在 PMEM 上，而 HOT/WARM 留在 DRAM 中会怎样？
在缓存已满的情况下，每个新的 SET 都会导致
- 尾部 HOT 必须转换为 COLD，并复制到 PMEM。
- 要做到这一点：尾部 COLD 必须被逐出以腾出空间用于来自 HOT 的项目。
- 最后，HOT 获取其项目数据。
这使得设置的时间增加了一倍，并且读取性能的改进不足以抵消这一点。非常频繁地访问的项目将驻留在处理器缓存中，这使得 PMEM 性能变得无关紧要。
缓冲区缓存
理论：频繁访问的项目使用 RAM 缓冲区缓存。
现实：可能实际上更好，但这是一个很大的改变。
与分层方法相比，来自新项目的 SET 将保持不变。当访问项目时，它可以概率性地被拉入 DRAM 中的缓冲区缓存。进一步的读取将命中缓存的项目。利用随机机会将减少为不常访问的项目从缓冲池中逐出内存的开销。
原始项目将保留在 PMEM 中，并且一个指向哈希表的假项目。假项目将指向真实项目；在 DELETE 或 OVERWRITE 或从缓冲池中删除时，原始内存将被恢复或释放。
需要进行大量的代码更改才能实现，并且读取性能的改进将很小；可能只对极其敏感的应用程序有用。变得非常热的键将与没有缓冲区缓存的性能相同，同样是因为 CPU 缓存。
自适应基数树
理论：ART 可以用于 DRAM，以避免在查找期间检查 PMEM 以比较键，而无需使用大量内存。
现实：可以工作，但难以扩展，并且链式表目前性能良好。
自适应基数树 是一种非常有趣且相对较新的数据结构。使用 ART，您无需对键进行哈希运算即可查找它。在确定匹配是否有效之前，也不需要将完整键与最终节点进行比较。Memcached 现有的链式哈希表可能需要多次从 PMEM 中获取数据才能找到一个项目；而 ART 可能会完全保留在 DRAM 中，只有在成功匹配时才获取项目数据。此外，由于其排序特性，甚至可以 直接在 PMEM 中运行 ART。
An Inefficient Memcached Key
departmentname:appname:subsystem:userdata:picnum:{id}
ART Prefix Compression
[departmentname:][appname:][subsystem:][userdata:][picnum:]{id}
不幸的是，ART 在细节方面存在不足：Memcached 可以存储数亿个具有相似前缀的键，但它们在末尾的数字会有所不同。这会导致在 DRAM 中进行多次跳转才能找到一个条目。此外，关于此类结构的并发性研究 很少。现有的方法需要在查找的每个阶段进行锁定。并发写入会导致查找完全重启。相比之下，Memcached 的链式哈希表只需要一个互斥锁来进行查找，并且我们很乐意避免的哈希计算是在获取任何锁之前完成的。
未来可能存在潜力；我们一直在关注这个领域。
外部引用计数器
理论：查找项目需要两次写入引用计数。将此移至 DRAM 可以节省性能和设备寿命。
现实：间接寻址很慢，性能提升最多 5%。可能值得尝试。
由于许多项目可以同时被请求，因此危险指针和类似的结构对于 Memcached 的扩展性很差。目前，我们只能使用引用计数。与一些学术论文的想法相反；引用计数器不是用于锁定或并发，而是用于安全性和正确性。键和值通过散射-聚集网络复制到客户端。如果客户端读取数据速度很慢，则在将项目的内存发送到客户端之前可能会经过很长时间。如果没有写时复制和引用计数，项目的内存可能会被“删除”然后重新使用。然后，错误的数据将被发送到客户端。这是一个灾难性的错误。
一个想法是，如果项目的键和值足够小，则存在一个大小截止点，在这个截止点上，在锁定项目时将值简单地复制到缓冲区比两次增加引用计数更快。这在当前情况下尤其如此，因为现在需要一个完整的互斥锁来递减引用计数，尽管这在将来可能会得到解决。
项目不携带自己的互斥锁：一个单独的较小的互斥锁表会被检查，具有相似哈希位的项目会共享互斥锁。这个表可以扩展为包含一个 [POINTER,refcount] 数组，用于每个锁，并根据需要进行扩展或收缩。如果一个项目没有引用，则它将没有引用计数内存。这可以为每个项目节省两个字节。
这是一个复杂的更改，最大影响是性能提升不到 5% 以及节省两个字节的内存。使用外部引用计数器，我们也可能会对 DRAM 进行更多访问。最终，DRAM 中的外部引用计数器可能比通过 PMEM 内联访问项目元数据更慢。
结论
现有的 memcached 与英特尔®傲腾™ DC 持久内存模块配合得很好。提高性能将是一个挑战，甚至可能不值得去做。这让我们可以专注于功能和稳定性，而无需投入大量时间来使服务“与 PMEM 兼容”。
尽管如此，我们仍处于现代持久内存的早期阶段。目前我们的哈希表位于 RAM 中，但也许也可以将其移至 PMEM。是否存在即使客户端连接缓冲区也可以简单地使用 PMEM 的场景？
我们一直以来为了节省内存而跳过或遗漏了哪些其他功能？