分布式系统学习——OSDI2018PM哈希方案

Step 1

题目摘要引言

题目

为 Persistent Memory 设计的写优化 Hashing Index Scheme

摘要

由于 NVM 数据一致性和硬件限制的要求，原来为 DRAM 设计的传统索引技术在 PM 中效率低下。为了有效高效地在 PM 中建立数据索引，本文提出了一种高性能写优化的架构—— level hashing（层级 Hashing）。

level hashing（层级 Hashing）提供了基于共享的两层哈希表。不额外增加 NVM 写操作情况下就降低增删查改操作为常数复杂度。为了以较低开销实现一致性（这个是指什么的一致性？），level hashing 使用无日志（log-free）的一致性方案进行增删和 resize 操作。为了更高效 resize，level hashing 调整了 resize 方案，以 1/3 代替原有整表的代价。

引言

NVM 引入，对 DRAM 不足之处的补充，RcRAM，PCM，STT-RAM，3D XPoint。由于 byte-addressable 的优势和接近于 DRAM 的 latency，PM 可以直接与 CPU 通过内存总线相连。

NVM 的劣势:limited endurance and low write performance。

Tree 索引工作概述：传统的方式进行数据索引效率低下，因为没有考虑到数据一致性和 NVM 设备的特性（这部分需要再读引用文献 35，46，58，64，68）。现有的许多工作都对 tree-based 数据索引结构进行研究以适应 PM（这部分仍需再读文章）。

又谈 Hash 索引结构的必要性：与基于 tree 的索引结构不同，基于 hash 的结构式扁平的（相应，空间代价应该要更大一些？），能够实现 O(1)的查找速率（与总量 N 是独立的）。因而 哈希索引结构被广泛应用于主存系统，例如，它们是主内存数据库（27,33,38,65）的基本组件。

！下面的内容要重点关注，与后面的工作较为相关。

将哈希索引结构应用于 PM 所面临的挑战：

  • High Overhead for Consistency Guarantee.（为保证一致性的高二开销）：
  • Performance Degradation for Reducing Writes.（为减少写操作而导致的性能下滑）：
  • Cost Inefficiency for Resizing Hash Table.（重设哈希表大小的代价效益问题）：

为应对上述挑战，本文所提出的方法：

  • Low-overhead Consistency Guarantee.（低负担的一致性保证）
  • Write-optimized Hash Table Structure. （写优化的哈希表结构 ）
  • Cost-efficient Resizing. （代价效益 Resize）
  • Real Implementation and Evaluation. （实际实现和分析）

基本理论概况

结论部分

实现了单机 PM 上高效的哈希方式——level hashing，具备写优化、高性能、低负担的一致性保证与效益更好的 Resize 策略等性质。同时还支持高效的并发 multi-reader 和 multi-writier。

在 DRAM、PM 混合平台上的测试结果：

  • 和最先进的哈希方法对比：
    • 1.4-3.0 倍插入速率
    • 1.2-2.1 倍更新速率
    • 4.3 倍 Resize 调整思虑
    • 保证较高的搜索和删除性能（文章中没有体现出来）
  • 和最先进的并发哈希方法对比：
    • 1.6-2.1 倍吞吐量（throughput）

回答基本问题

  1. 类别

基于新型硬件对现有系统进行改良。

  1. 内容

暂时没有相关性，应该要补充很多 Tree 结构的文章。

  1. 正确性

源码开源在Level-Hashing

  1. 创新点

结合 PM 与 Hash Table，着重应对 Resize 地问题提供了解决方案，以小博大，获得了整体性能地提升。如果从 Hash 数据结构做出发点在 PM 上进行实现，这篇文章应该算不错地入门文章。

  1. 清晰度

粗略看条理比较清晰，

阅读选择

继续阅读！

Step 2

细读笔记

NVM 中的数据一致性

必须解决系统故障时易失性器间与非易失性器间间的数据一致性问题。CPU 和内存控制器可能会调整内存的写记录。我们需要使用缓存线路刷新指令（cache line flush instruction）和内存 fence 指令（memory fence instruction）来保证刷出了内存写内容。CFLUSH 和 MFENCE 指令由 Intel x86 指令集提供。

问题记录

未读（且值得读）文献记录

  • 现有数据索引低效的引用文献（35，46，58，64，68）
  • tree-based 数据索引结构研究
    • CDDS B-tree （58）
    • NV-tree （64）
    • wB+-Tree （17）
    • FP-Tree （46）
    • WORT （35）
    • FAST&FAIR （30）

Step 3

思路复现

证明与推理复现

实验验证复现