开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Paper Reading 02 基于持久性内存的哈希索引 -> 正文阅读

[数据结构与算法]Paper Reading 02 基于持久性内存的哈希索引

引言

本文将介绍2022之前发表在顶会或顶刊的几篇面向PMem的Hash索引。
它们分别是:

Level Hash(TOS’2019)
CCEH(FAST’2019)
Dash(VLDB’2020)

后续将从整体结构、读写和分裂操作、恢复操作和并发控制这几个方面介绍。

Level Hash

Overall architecture

Architecture

在这里插入图片描述

Level Hash逻辑上分为两层（顶层Top Level和底层Bottom Level），底层的桶数量为顶层
桶数量的一半，并且底层的每个桶都是顶层两个桶的溢出桶，比如底层下标为1的桶是顶层下标为2和3的桶的溢出桶。这种设计的优势是减少扩展和收缩代价，后面会详细介绍。

底层和顶层在物理上是连续的桶数组。

bucket

在这里插入图片描述

bitmap + KV数组。bitmap（Tokens）的每位阐明对应KV是否有效。

Read/Write Operations and SMO

Write

为了提高负载系数(load factor)，level-hash采用了布谷鸟哈希、基于共享的两层结构以及记录迁移。

首先根据两个哈希函数的值，定位到顶层TL的两个桶T1、T2，尝试插入到T1、T2中。（布谷鸟哈希）
如果T1和T2都没有空闲插槽，那么根据T1\T2定位到底层它们的溢出桶B1和B2，尝试插入到B1、B2中。（共享的两层结构）
如果B1和B2都也没有空闲插槽，那么尝试将T1\T2中的数据迁移顶层的另一个桶中，如果失败则尝试将B1\B2中的数据迁移底层的另一个桶中。（记录迁移）
还是失败则进行扩展。

Read

依次去T1、T2、B1、B2中查找。

Expand

在这里插入图片描述

在扩展之前，顶层TL有N个桶，底层BL有N/2个桶。

首先分配2N个桶作为新的顶层TL, 原来的顶层old TL变成了底层BL，原来的底层old BL
变成了临时层IL, 然后将临时层中的KVs, rehashing到新的TL中。

扩展后，哈希表的容量从1.5N个桶变成了3N个桶，且最多需要迁移0.5N个桶，这很大程度上减少了扩展代价。

Shrink

和expand类似，略

Recover

文中没有介绍，但如果不在expand状态，恢复时间复杂度为O(1)。

Concurrency

采用细粒度锁（fine-grained locking）slot-level，每个插槽都有一个锁，以提高并发度。

CCEH

Overall architecture

Architecture

在这里插入图片描述

CCEH分为3层: 目录(directory) + 段(segment) + 桶(bucket)。
相比传统的目录 + 桶的结构，CCEH将多个桶合成一个段，搜索时，首先根据哈希值的Segment index部分，索引到对应的段，再根据哈希值的bucket index部分,找到对应的桶。
这样做的好处是：一个目录项指向含有多个桶的段，大大减少了目录的大小，使目录有可能完全缓存在cpu caches中。
这样做的坏处：段可能因为某些桶满了而提前分裂，即使得负载系数减小。

Read/Write Operations and SMO

Split

先介绍分裂，因为cceh采用的分裂策略影响了其它操作。

在这里插入图片描述

首先分配一个新段，并将属于新段的kv拷贝到新段中。
更新指向新段的目录项和新段的局部深度
更新待分裂的段的局部深度

注意到，分裂操作，不会删除重复键，因为它对正常访问没有影响，可以留给write操作，用新插入的Kv覆盖。

Write

为了提高负载系数(load factor)，cceh采用了布谷鸟哈希和线性探测。

根据哈希值的高位，索引到相应的段
根据哈希值的低位，索引到相应的桶，采用线性探测（有探测距离限制，如最多探测4个桶）处理哈希冲突，同时检查是否有不属于这个段的数据，如果有则用待插入的kv覆盖它。
如果线性探测后仍插入失败，则根据另一个哈希函数的哈希值，索引到相应的桶，采用线性探测处理哈希冲突。
仍然失败，则进行段分裂

Read

过程和write操作类似。

Recover

在这里插入图片描述

根据目录项的局部深度和全局深度可以检测不一致。

注意到分裂时，目录项从右往左更新。

如图(a)，全局深度为4，第一个目录项的局部深度为3，假设，第一个目录项指向段S1, 理论上会有1 << (4 - 3) = 2个目录项指向S1, 即第一和第二个目录项都应指向S1, 且它们的局部深度应该相同。

如图(b)，第九个目录项的局部深度为2，则应该有4个目录项指向S2, 即第9-12个目录项都应该指向S2，但检查到第12个目录项指向S11，且局部深度为3，出现不一致，这说明S2发生了分裂。图?是恢复分裂后的结果。

Concurrency

对于bucket，使用读写锁。
对于segment，

可以使用读写锁
或者采用lock-free访问(CoW)的方案

Dash

Dash是一个设计面向真实PM的可扩展哈希的方法。

Overall architecture

Dash-EH

Architecture

在这里插入图片描述

Dash的整体架构与CCEH基本一致，不同的是Dash在每个Segment中增加了一些溢出桶Stash buckets，用于插入由于普通桶满后无法插入的溢出记录。

另外在Directory中增加了一个版本号Version和Clean标记，用于即时恢复。

Structure of bucket

在这里插入图片描述

一个桶大小为256字节，前32字节为元数据，后面跟着14个记录项。元数据看上去很复杂，但其实除去锁和counter，主要是bitmap和fingerprints。
而bitmap和fingerprints又分为两类，一个是服务正常插入的记录，另一个服务溢出记录。后面的操作详细介绍每个元数据的作用。

Dash-LH

Architecture

在这里插入图片描述

为了进一步减少目录的大小，Dash-LH采取了类似double expansion的策略，每个目录项指向一个segment数组，每stride项，所指向的segment数组大小翻倍。这里stride=4，即前4个目录项指向一个segment，接下来4个目录项指向大小为2的segment数组，…,以此类推。

Structure

普通桶结构和Dash-EH一样，溢出桶增加了next指针。

Read/Write Operations and SMO

Write

为了提高负载系数(load factor)，Dash采用了平衡插入(Balanced insert)、记录迁移(Displace)以及溢出桶(Stash)。

首先根据哈希值，定位到对应的Segment中对应的bucket b，并向后探测一个桶b+1（逻辑上加一）
如果桶b和桶b+1有空闲的插槽，插入到空闲插槽数多的桶中，即平衡插入(Balanced insert)。
- 如果插入到了桶b中，则将Alloc.bitmap的对应位置为1，表示对应项是有效的，同时将对应的fingerprint置为key的一个1字节哈希值。
- 如果插入到桶b+1中，除了更改Alloc.bitmap和fingerprint，还需将Membership的对应位置为1，表示对应项存储的是前一个桶的记录。
如果两个桶都没有空闲插槽，则尝试能否将两个桶中的某个记录迁移(Displace)。
- 首先尝试将桶b+1中属于它的记录迁移到桶b+2中，Membership对应位为0，说明相应的记录属于b+1, 如果桶b+2未满，则将b+1中第一个属于它的记录迁移到b+2中，再将KV插入到空闲的slot中。
- 如果b+1迁移失败，再尝试将桶b中原本属于b-1的记录迁移到桶b-1中。通过读取Membership可以知道哪些记录是属于b-1。
如果两个桶都迁移失败，则将记录插入到溢出桶Stash buckets中(Stash)。
- 探测所有的Stash buckets，起始bucket为b模溢出桶的数量。如果插入成功，假设插入到溢出桶index中。
  - 如果桶b的溢出记录不超过4个，那么更新fingerprints(有4个fingerprint特别留给溢出记录)，overflowBitmap和overflowIndex，分别置为：key对应一字节哈希值、对应位为1、对应项为index。
  - 如果桶b的溢出记录超过4个, 那么对桶b+1进行同样的操作，但需要额外更新overflowMembership表示溢出记录属于前一个桶。
  - 如果两个桶的溢出记录都超过4个，那么将b的overflowCount加一(overflowCount > 0 表示除了overflowBitmap所指的溢出记录，还有overflowCount个溢出记录)。
- 如果所有的溢出桶都没有空余，则Stash失败
如果以上都失败
- Dash-EH进行segment分裂
- Dash-LH分配一个新的溢出桶

Read

首先根据哈希值，定位到对应的Segment中对应的bucket b，并向后探测一个桶b+1（逻辑上加一）
首先在b中搜索，根据Alloc.bitmap和Membership可以知道哪些记录是有效且属于b的，对比fingerprint和key进行查找。
如果在b中搜索失败，再在b+1中搜索，步骤同上。
如果在b和b+1中搜索失败，去Stash buckets中搜索。根据overflowFingerprint和overflowIndex可以加速搜索。

SMO

Dash-EH

在这里插入图片描述

首先分配一个新的segment，将它的local depth设为原segment的local depth + 1, 并将它添加到segment链表中。
rehashing，记录迁移
更新目录和segment的local depth

Dash-LH

类似

Recover

即时恢复(Instant Recovery)

Dash的这种结构本来恢复操作的复杂度应该和CCEH一样，但是Dash通过将恢复分摊到每一个segment，实现了即时恢复。

每次recovery时，将全局的version加一，并开始处理负载。
当后续访问一个segment时，首先对比segment的version，如果不符合，则对segment进行恢复操作。即将恢复操作推迟到第一次访问segment的时候(lazy recovery)。

一个segment的恢复操作如下

清理buckets的锁
移除重复的key
重建overflow metadata
继续正在进行的SMO

Concurrency

Dash采取乐观并发控制(Optimistic Concurrency)和bucket-level锁。

综合比较

Hash	Architecture	Real PMem	Segment	Cuckoo Hash	Stash	Linear Probe	Movement	Fingerprint	RecoverSpeed	Concurrency
Level	PMem-only			$\checkmark$	$\checkmark$		$\checkmark$		Fast O(1)	slot-level, r/w lock
CCEH	PMem-only		$\checkmark$	$\checkmark$		multiple buckets			Medium O(n)	bucket-level, r/w lock
Dash	PMem-only	$\checkmark$	$\checkmark$		$\checkmark$	single bucket	$\checkmark$	$\checkmark$	Fast O(1)	bucket-level, OLC

这三种索引都是PMem-only的，只有Dash在真实PMem运行，其它两个使用模拟器。
CCEH和Dash都采用了Segment这一设计
在写优化方面(蓝色)，Level和CCEH都采取了布谷鸟哈希；Level和Dash都采取了溢出桶，Level是两个桶共用一个溢出桶，而Dash多个桶公用多个溢出桶；CCEH和Dash都采用了线性探测，CCEH探测多个桶，而Dash探测一个桶；Level和Dash都采用了迁移一个项的策略。
在读优化方面(红色)，只有Dash采用了fingerprint优化读。
在恢复速度方面，Level和Dash都是常数级，而CCEH需要扫描目录，复杂度是O(n)。
至于并发方面，Level和CCEH都是用读写锁，而Dash采用乐观锁；另外Level是slot-level锁，而CCEH和Dash是bucket-level锁。