抛弃哈希表？持久化数据结构HAMT探究

引言

突然想聊聊这个问题的原因有二，一个持久化数据结构本身带来的可回滚的好处，这使得一种十分高效的forkless实现方案成为可能，虽然Redis想要支持意味着所有的数据结构都需要变成可持久化数据结构，这已经成了学术上难题而不是工程难题了；另一种是现在Redis社区已经在计划把HAMT引入Redis7.0，替换哈希表，这个代码已经写完了，但是社区还正在讨论，目前看来仲肥哥和oranagra对这个方案很赞同，那也就是五票已有两票，大概率我们可以在Redis7.0看到这个东西了。

不过目前这个PR的老哥貌似遇到了Heisenbug，过不了单测，也算是非常有意思了。

HAMT介绍

HAMT全称为Hash Array Mapped Trie，又被称为Ideal Hash Trees。其基于哈希值本身的长度以前缀树的形式进行分段索引，在64位哈希值时基本可以做到O（7）的常数级别查询，而且本身不需要rehash这种耗时的操作，在理论上还可以支持高效的快照操作（可持久化数据结构）。

这篇文章不想去讲这个数据结构的实现，有兴趣的朋友可以去在[1][2][6]中看到入门材料，想深入学习就可以看看[7]去看看论文是怎么讨论这个数据结构的。这篇文章想讨论的是其引入Redis7.0以后的优缺点，这篇文章的论点基本是社区中一些老哥的看法以及我自己的看法的结合体。

社区开始是讨论使用rax替代哈希表，但是说实话从理论上看radix tree就有些不合适，毕竟我们不能去假设用户的使用习惯是前缀较多的场景，而且目前没有好的SCAN和随机算法，但是社区貌似很喜欢前缀树这种优化方式，哎，不用key做前缀，用hash做前缀总可以来吧，好吧，HAMT就这样被提上了Redis7.0的日程。

但是对于替换这个操作我本人并不是非常赞成，我的想法是可以在启动时配置Redis Instance需要使用的数据结构，比如Classic Hash Table，HAMT，Radix Tree，Cuckoo hash，Linear Hashing、Litwin、Neimat ，Schneider等等。让用户根据特定的需求选择不同的数据结构，当然前提是实现以后性能不下降的情况。当然看起来提供module也是一个很好的选择。

这个东西被称为理想哈希表，那肯定是我们已有的这种链地址法多多少少有点问题，所以其不被称为“理想”。

基本已知的问题有以下几种：

1. rehash导致内存访问的延迟时间出现波峰(#8611)
2. rehash时可能导致一些内存的浪费，因为一般哈希表的负载在[0.5,1]之间。
3. 链地址法本身带来的可能的链式访问的问题，cuckoo hash可以解决这种问题，包括hotring也是在这个角度去做优化的。
4. rehash带来的代码复杂性，虽然现在实现的很好。

如果使用HAMT可以为我们带来哪些优势呢？

1. 抛弃了rehash
2. 8611中提到的大的zmalloc/zfree带来的问题也不复存在
3. 哈希函数优秀的情况下树的平衡度也很好
4. 常数级别访问
5. 内存使用优于链地址法，因为链地址法需要一个next指针。一般的负载因子是[0.5,1]，所以一般每个entry会浪费半个指针。但是新结构只需要在每个数据项中使用两个四字节的bitmap就可以标识子节点是否存在了。
6. SCAN以及Random key很好实现
7. 迭代期间所有操作安全
8. miss时相对于dict效率更高，因为后者需要遍历链表

暂时没有细看这个PR的实现，原因是看到huangzhw大佬说了这么一句话This PR is difficult. It takes me some time to understand it. 那我就暂时不看了吧，留点时间摸鱼他不爽嘛，等被merge了以后再看也不迟。

目前看zuiderkwast的介绍，目前应该是实现了基础的HAMT，包括了[1]中说的两种优化，但是论文上所说的resize the root table暂时没有实现。

仍存在的问题

可以在[5]中看到目前社区的reviewer们提出的一些有建设性的意见：

1. HAMT对于内存碎片的影响如何呢？因为线上是不允许使用defrag的，如果相对于dict碎片率太高我们也是不能接收的，但是看起来貌似没有产生大量碎片的地方，但是因为树结构的调整，分配数肯定是大于以前的。
2. 因为rehash的缘故，HAMT在中等数据集中的插入应该是优于dict的，但是在数据集稳定时dict应该是优于HAMT的。目前的dict从字典到值至少需要三次指针操作拿到值，dict->dictht->dictEntry->key-value。HAMT则需要更多的指针操作，因为目前我们有高度上的优化，所以在大数据集时这个问题更加明显，原因是哈希值中五位为一个层，也就是说数据量够大我们光是树上的遍历就需要13次的内存访问。对于10M的数据集(32^5 = 33M)，理想情况下就需要7次数据访问dict->dictSubNode->树上查找5次->key-value。hotring也是在这种指针访问上做优化的。

总结

基本上看起来对于Redis这种内存为王的Nosql数据库来说，HAMT将会是一个很大胆的尝试，这基本上把内存的使用降低到了极致，虽然没有利用到其可以作为持久化数据结构的特性。至于设置全局开关来选择不同数据结构来作为字典实际这种方法现在看起来很不错，但是也许module是个更好的做法。

参考：

1. 《Functional Go: 持久化数据结构简介》
2. 《Functional Go: HAMT 简介》
3. 《HASH ARRAY MAPPED TRIE-HAMT》
4. [NEW] Replace dict’s hash table with HAMT
5. Replace dict’s hash table with HAMT #8700
6. Introduction to HAMT
7. Ideal Hash Trees
8. Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections