实现键值对存储 第五部分 Hash table 实现

实现键值对存储-第五部分: Hash table 实现

原文链接

这篇文章是 IKVS 系列的第五部分,”实现一个键值对存储”.你也可以查看 Table of Contents 来查看其他部分.

在这篇文章中,我将会学习C++中实际的 hash table 来理解它的瓶颈在哪里.Hash 函数是 CPU-密集型的操作应该要进行优化.然而,大多数的 hash table 的机制都只是关注于高效的内存和I/O读取,这也是这篇文章主要的焦点.我将会学习三种不同的 C++中的hash table 的实现,同时包含内存中的和硬盘中的,并且会观察这些数据都是怎么组织和访问的.这篇文章将会包含以下内容.

[TOC]

kvstore-part5-intro

1. Hash tables

1.1 对 hash tables 的一个快速介绍

Hashtable 按理说是一个对人类来说最重要的数据结构.

— Steve Yegge

一个hash table 允许高效的访问关联数据.每一个条目都是一个键值对,只需要知道它的key就可以快速的检索或者分配.为了实现这个效果,key是使用hash函数来计算的,达到将这个key从它原始的表达转换为一个整数.然后使用这个整数作为索引来识别在存储条目值的数组中哪个位置是被访问的.很多key可以被hash到一个相同的值里,这意味着这些key会在这个数组位置碰撞.为了解决冲突问题,有很多中技术可以使用,比如在这个桶里使用 链表 或者 自平衡树等,或者使用 线性探查或者二次探查的开放式寻址.

从现在开始,我会假设你知道hash table 是什么.如果你觉得你需要复习一下相关知识,有一些好的资源是 Wikipidia[1] 上的 “Hash table” 这篇文章(还有页面底部的那些链接部分),还有就是 Cormen et. al [2] 的”Introduction to Algorithms” 这本书中的 Hash table 这个章节.

1.2 Hash 函数

hash 函数的选择是特别重要的.一个好的 hash 函数最基础的要求就是输出的hash 值应该要分布均匀.这样,发生碰撞的概率就最小化了,同时也缩小了bucket 中碰撞的条目的数量.

这里有很多可以用的hash函数,并且除非你准确的知道这些存储的数据会是什么,否则最安全的做法是使用一个平均情况下分配随机数据最均匀的那个,如果可以的话要适用于”雪崩效应”[3]的情况.有一部分人已经在对比hash函数的效率了 [4] [5] [6] [7],从他们的结论得知,MurmurHash3 [8] 和 CityHash [9] 在这篇文章写完的时候是最好的hash函数.

2. 实现

如同对比 hash 函数一样,现在也已经有一些博客和文章已经对比了 使用内存的 C++ hash table 库.我看过最值得注意的是 Nick Welch的 “Hash Table Benchmarks[10] 和 Jeff Preshing 的 “Hash Table Performance Tests[11], 但是还是有一些其他的文章也值得一看 [12] [13] [14]. 通过这些对比,我从 GCC 中的 TR1 派生出了 unordered_map 同时从 SparseHash 库中派生了 dense_hash_map — 之前被叫做 Google SparseHash —这是两个很值得学习的模块,并且下面我也会介绍到.此外,我还会介绍 Kyoto Cabinet 中的 HashDB 里的数据结构.当然 unordered_map 和 dense_hash_map 不会像 HashDB 那样和我的 key-value 存储项目关联性那么大,因为它们是内存内的 hash table . 虽然这样,对它们的内部数据结构的组织和它们的内存模式做一个简单的了解也是很有趣的.

对于这三个 hash table 库的介绍,我将会使用一个通用的例子,将一组城市的名字作为key,将它们的 GPS 坐标作为 value . unordered_map 的源码可以在 GCC 的源码中找到,它是在 libstdc++-v3 中. 我介绍的是基于 GCC v4.8.0中的 libstdc++-v3 release 6.0.18 [15],以及 SparseHash v2.0.2 [16] 中的 dense_hash_map , 还有 Kyoto Cabinet v1.2.76 [17] 中的 HashDB.

在 Matthew Austern 写的 “A Proposal to Add Hash Tables to the Standard Library (revision 4)[18] 还有 SparseHash 中的 “Implementation notes” 页面 [19] 中也可以找到关于实现的有意思的讨论.

2.1 TR1 的 unordered_map

TR1 中的 unordered_map 提供了一个使用链表(单独链路)方式处理碰撞的问题的 hash table . 数组的位置分配是在堆上的,并且根据负载因子来进行扩大或者缩小.一个叫做 _Hash_node 的节点结构是用来创建桶的链表.

1
2
3
4
5
6
7
/* from gcc-4.8.0/libstdc++-v3/include/tr1/hashtable_policy.h */
template
struct _Hash_node<_Value, false>
{
_Value _M_v;
_Hash_node* _M_next;
};

如果 key 和 value 都是整数类型的,它们可以被直接存储到这个结构的 _M_v 里.否则指针将会被使用并且需要一些额外的内存.桶数组在堆上就会被分配,但这并不影响 节点,它们使用的是 C++ 内存分配器中独立的调用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* from gcc-4.8.0/libstdc++-v3/include/tr1/hashtable.h */
Node* _M_allocate_node(const value_type& __v)
{
_Node* __n = _M_node_allocator.allocate(1);
__try
{
_M_get_Value_allocator().construct(&__n->_M_v, __v);
__n->_M_next = 0;
return __n;
}
__catch(...)
{
_M_node_allocator.deallocate(__n, 1);
__throw_exception_again;
}
}

因为节点是独立分配的,每个节点的分配可能会造成大量的内存浪费.这当然也取决于编译器和使用的操作系统的内存分配器.而且我甚至不讨论每种分配器的所有的系统调用.最原始的 SGI hash table 的实现会对节点进行资源预分配,但是这种策略在 TR1 的 unordered_map 实现中没有被保留.

下面的 图 5.1 提供了一个对于 TR1 的 unordered_map 的内存和访问模式.让我们来看看当我们根据key “johannesburg” 来查找关联的 GPS 坐标的时候会发生什么事.这个key 将会被 hash 然后映射到 bucket #0 .从那里我们跳转到这个bucket 对应的链表的第一个节点(bucket #0 左边橙色的箭头),并且我们可以访问堆里持有key “johannesburg” 数据的内存区域(Node 右边黑色的箭头).如果key 在第一个节点是无效的,我们可以指向到其他的节点.

至于CPU 的性能,人们不能指望将所有的数据都放在处理器同一个缓存行里.的确,给定了 bucket 数组的大小,初始化的 bucket 和初始化的节点将不会在同一个缓存行里,并且节点关联的额外的数据也不会在同一个缓存行中.子序列节点和关联的数据也不会在相同的缓存行里并且必须从 RAM 中检索.如果你并不熟悉CPU 优化和缓存行, 这篇 Wikipedia 上的 “CPU Cache” 文章将会是一个很好的介绍 [20].

Figure 5.1

2.2 SparseHash 的 dense_hash_map

SparseHash 库提供了两种 hash table 的实现, sparse_hash_map 和 dense_hash_map. sparse_hash_map 通过降低了速度提供了惊人的内存占用,并且使用制定的数据结构来获取结果,这就是 sparsetable. 想要了解更多的关于 sparsetables 和 sparse_hash_map 的信息可以去SparseHash 的 “Implementation notes” 页 [19].在这里我只会介绍 dense_hash_map.

dense_hash_map 使用二次内部探查处理碰撞问题.如同 unordered_map ,bucket 数组在一开始就在堆里分配了,并且会根据 hash table 的负载因子进行放大或者缩小. bucket 数组的元素是 std::pair 的实例,其中 KeyT 分别是 键和值的模板参数.在一个 64-位体系架构中保存字符串, 每一对的实例将会占用 16字节.

下图 5.2 提供了一个对于 dense_hash_map 的内存和访问模式的示意图.如果我们查找 “johannesburg” 的 GPS 坐标,我们一开始会在 bucket #0 中查找失败,因为它的数据是 “Paris” 的(bucket #0 右边的黑色箭头).所以我们会继续探查并跳转到 bucket (i + 1) = (0 + 1) = 1 (bucket #0 左边橙色的箭头),然后我们会在 bucket #1 中查找 “johannesburg” 对应的数据(bucket #1 右边黑色的箭头).这看起来和 unordered_map 很相似,但实际上是非常不同的.当然,就像 unordered_map 一样键和值将会被存储在堆内存中,这意味着键和值的查找将无法使用缓存行.但是bucket 中的碰撞条目的导航将会变得非常快.的确,在大多数的处理器中缓存行是 64byte , 而我们指定每一对占用16byte的容量,这将会显著的提高我们的速度,和 unordered_map 中的链表相反,它需要在RAM中跳转来得到接下去的节点.

通过二次内部探查提供的缓存行优化使得 dense_hash_map 在 使用内存的 hash table 中的性能测试成为胜利者(至少是我了解的那些).你应该花点时间看一看 Nick Welch 写的 “Hash Table Benchmarks” [10].

2.3 Kyoto Cabinet 的 HashDB

Kyoto Cabinet 实现了许多的数据结构,其中也包括 hash table . 比如这个 hash table , HashDB ,是用来在硬盘上持久化的,尽管这里有一个可选方案可以将他作为 std::map 的替代品. hash table 的元数据还有用户数据都是通过文件系统按顺序保存在唯一的一个硬盘文件中.

Kyoto Cabinet 通过在每一个 bucket 上使用独立的二分查找树来处理碰撞问题.bucket 数组有一个固定的大小并且永远不会调整大小,不管负载因子的状态是什么.这是它主要的缺陷.确实,如果在数据库的创建的时候定义的 bucket 数组的大小比实际的需求要小的花,那么当条目开始碰撞的时候性能将会变得很差.

对于一个使用 硬盘的 hash table 实现来说,要让 bucket 数组的大小可以调整是非常困难的.首先,这会要求 bucket 数组还有条目要存储在两个独立的文件里.这样子它们就可以分别增长了.第二,因为需要重新调整 bucket 数组的大小所以需要重新对 key 进行hash操作来对应到它们在新的bucket 数组中位置,这会需要从硬盘中读取所有的条目对应的key,这会非常的消耗性能或者可以说在数量大的数据库情况下来说是不可能的.一个可以避免重新hash的方法是存储 hash 后的key,但是这意味着每一个条目都需要额外 4 或 8 byte 的数据(根据 hash 是 32 还是 64 bit 长的).因为这些种种的复杂性,使用一个定长的 bucket 数组是更简单的,并且这也是 Kyoto Cabinet 中的 HashDB 采用的方法.

图 5.3 展示了存储在文件中的 HashDB 的结构.我从 clac_meta() 方法还有 kchashdb.h 文件底部中的 HashDB 类的代码属性的注释中中派生了这个内部结构.这个文件由以下的部分构成:

  • 数据库所有元数据的头部.
  • FreeBlock pool 用来持有数据区域中的可用空间
  • bucket 数组
  • 记录(数据区域)

一条记录会持有一个条目(键/值对),使用了一个单独连接的二叉搜索树的节点.下面是 Record 的结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* from kyotocabinet-1.2.76/kchashdb.h */
/**
* Record data.
*/
struct Record {
int64_t off; ///< offset
size_t rsiz; ///< whole size
size_t psiz; ///< size of the padding
size_t ksiz; ///< size of the key
size_t vsiz; ///< size of the value
int64_t left; ///< address of the left child record
int64_t right; ///< address of the right child record
const char* kbuf; ///< pointer to the key
const char* vbuf; ///< pointer to the value
int64_t boff; ///< offset of the body
char* bbuf; ///< buffer of the body
};

观察图 5.4 可以知道硬盘上的记录的组织.我从 kchashdb.h 中的 write_record() 方法中派生了这个结构. 注意它和 Record 的结构是不一样的: 使用硬盘的方式的目标是要最小化占用的空间,同时这个结构的目的还要让它在程序上能够便于使用.所有在 图 5.4 中的字段都是固定长度的,除了 key ,value ,还有 padding ,这些数据当然是根据条目里的数据大小来决定的. left 还有 right 字段是这个二叉搜索树节点的一部分,并在文件中保存了其他记录的偏移量.

Figure 5.3

Figure 5.3

Figure 5.4

如果我们想要访问key “Paris” 的值,我们将会从获取关联 bucket 初始记录的偏移开始,也就是 bucket #0.接下来我们会跳转到这个bucket 的二叉搜索树的头节点(bucket #0 左边的橙色的箭头),它持有了key “Johannesburg” 的数据. key “Paris” 的数据可以通过这个节点的右子节点来访问(“Johannesburg” 记录右边的黑色箭头).二分查找树需要一个 “可对比” 类型以此来对节点进行分类.这里使用的可以对比的类型是将hash 后的key 通过 fold_hash() 方法简化成一个更小的表示.

1
2
3
4
5
6
/* from kyotocabinet-1.2.76/kchashdb.h */
uint32_t fold_hash(uint64_t hash) {
_assert_(true);
return (((hash & 0xffff000000000000ULL) >> 48) | ((hash & 0x0000ffff00000000ULL) >> 16)) ^
(((hash & 0x000000000000ffffULL) << 16) | ((hash & 0x00000000ffff0000ULL) >> 16));
}

将条目和节点存储在一个记录中在一开始可能会看起来像一个设计错误,但是实际上是非常聪明的.为了存储一个条目的数据,通常需要管理3个不同的数据:bucket , 碰撞 ,还有条目.在给定的 bucket 数组中的bucket 必须按照定义顺序存储,它们只能这么存储并且没有什么可以提升的地方.然后假设我们不存储整数类型而是存储字符串或者可变长 byte 的数组之类的无法被存储在 bucket 自身的东西,另一个内存访问将会需要存储到 bucket 数组之外的区域.因此,在添加新的条目的时候,需要存储碰撞的数据结构和条目的键值.

如果碰撞数据和条目数据是独立存储的,除了需要访问bucket 之外,还需要访问两次硬盘,如果是设置值的情况,这会导致在硬盘上写入3次,可能还是在相隔很远的地方.这意味着磁盘上的随机写入模式,这对于I/O而言是最糟糕的事.现在因为 Kyoto Cabinet 的 HashDB 节点数据和条目数据被存储在了一起,它们可以仅通过一次写入磁盘而不用两次.的确,bucket 还是需要被访问的,但是如果 bucket 数组足够小,它将会被操作系统从磁盘中缓存到 RAM 中,这是 Kyoto Cabinet 最主要的假设,正如 specs 中 “Effective Implementation of Hash Database” 这一章节描述的那样[17].

然而这里还有一个需要关心的是将二分查找树节点和条目一起保存到磁盘上,这会降低读取的速度,至少是在碰撞开始发生的时候.的确,因为节点和条目存储在了一起,要解决 bucket 中的碰撞就意味着要找到记录中持有有效条目的二分查找树,这会需要在磁盘上进行许多随机的读取.这样就可以更好的理解为什么 Kyoto Cabinet 在条目的数量超过 bucket 的时候会出现这样的性能下降的原因.

最后,因为所有的东西都被存储在一个文件中,内存管理都是由 Kyoto Cabinet 自己来处理的,并不是像 unordered_map 还有 dense_hash_map 那样交给操作系统来管理.FreeBlock 结构持有了关于文件中空闲空间的信息,基本上是有关与偏移和大小,可以看下面的介绍:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* from kyotocabinet-1.2.76/kchashdb.h */
/**
* Free block data.
*/
struct FreeBlock {
int64_t off; ///< offset
size_t rsiz; ///< record size
/** comparing operator */
bool operator <(const FreeBlock& obj) const {
_assert_(true);
if (rsiz < obj.rsiz) return true;
if (rsiz == obj.rsiz && off > obj.off) return true;
return false;
}
};

所有的 FreeBlock 实例都是在 std::set 中加载的,允许使用 std::set 中的 upper_bound() 方法来检索空闲内存块,就像 fetch_free_block() 方法中那样,调整一个”最适合” 的内存分配策略.当空闲内存块的分布太过碎片化或者在 FreeBlock 池中没有剩余的空间的时候,文件会进行碎片整理.这个碎片整理的过程会移动记录来减小 数据库文件的大小.

3. 结论

在这篇文章中,我介绍了三种不同的 hash table 库的数据组织和内存访问模式. TR1 中的 unordered_map 和 SparseHash 中的 dense_hash_map 是在内存中的, Kyoto Cabinet 中的 HashDB 是在磁盘上的.这三个实现使用了不同的方式来处理碰撞问题,在性能上也有不同的表现.分离 bucket 数据,碰撞数据还有条目数据将会影响性能,这就是 unordered_map 使用的方法.通过将碰撞数据和bucket 存储到一起可以有效的提高速度,就像dense_hash_map 使用的方式 二次内部探查, 或者像 HashDB 使用的方式一样.这些方案都可以提高写入的速度,但是将碰撞数据和bucket 存储到一起还会提高读取速度.

还有一件事是我从学习这些哈希表的库的时候明白的,当设计一个哈希表的数据结构的时候,应该优先考虑将碰撞数据和bucket 数据保存在一起,而不是和条目保存在一起.这是因为就算哈希表是在磁盘上的,bucket 数组和碰撞数据也会小到可以存储在RAM中,这样子随机读取会比在磁盘上的消耗少很多.

4. References

[1] http://en.wikipedia.org/wiki/Hash_table
[2] http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844/
[3] http://en.wikipedia.org/wiki/Avalanche_effect
[4] http://blog.reverberate.org/2012/01/state-of-hash-functions-2012.html
[5] http://www.strchr.com/hash_functions
[6] http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed/145633#145633
[7] http://blog.aggregateknowledge.com/2012/02/02/choosing-a-good-hash-function-part-3/
[8] https://sites.google.com/site/murmurhash/
[9] http://google-opensource.blogspot.fr/2011/04/introducing-cityhash.html
[10] http://incise.org/hash-table-benchmarks.html
[11] http://preshing.com/20110603/hash-table-performance-tests
[12] http://attractivechaos.wordpress.com/2008/08/28/comparison-of-hash-table-libraries/
[13] http://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/
[14] http://blog.aggregateknowledge.com/2011/11/27/big-memory-part-3-5-google-sparsehash/
[15] http://gcc.gnu.org/
[16] https://code.google.com/p/sparsehash/
[17] http://fallabs.com/kyotocabinet/spex.html
[18] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html
[19] http://sparsehash.googlecode.com/svn/trunk/doc/implementation.html
[20] http://en.wikipedia.org/wiki/CPU_cache

About Me

我的博客 leonchen1024.com

我的 GitHub https://github.com/LeonChen1024

微信公众号

wechat

You forgot to set the business and currency_code for Paypal. Please set it in _config.yml.
You forgot to set the url Patreon. Please set it in _config.yml.
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×