有界下标可扩展哈希算法 - Bounded-index Extensible Hashing - Bihash

 ____    _   _                     _
| __ )  (_) | |__     __ _   ___  | |__
|  _ \  | | | '_ \   / _` | / __| | '_ \
| |_) | | | | | | | | (_| | \__ \ | | | |
|____/  |_| |_| |_|  \__,_| |___/ |_| |_|

概述

Bihash名字有若干层含义：

Hashing - Bihash本质上是一种哈希表，散列函数计算关键字得到哈希值，将哈希值作为索引值去查找哈希表，得到记录中存储的值；
Bounded - 哈希表数据结构的物理存储形式为顺序存储结构，顺序表的尺寸是固定长度，因此线性表的索引值是有范围，不能越界访问；
Extensible - 哈希表存在冲突的概率。在散列算法和处理散列冲突方法固定的情况下，扩大哈希表容量能够降低冲突的概率，但是无限制的扩大哈希表容量也会导致存储空间的浪费。Bihash具有依据当前哈希冲突事件，动态扩大哈希表容量的能力，节省存储空间的同时，能够降低冲突的概率。

VPP使用Bihash来解决一类键值（key/value）精确匹配查找问题。Bihash实现的优势包括：

哈希表容量可动态扩展，最高测试可达100M条记录数；
查找性能不会随着表中记录数量的增加而剧烈下降；
读操作不需要锁（实际上读操作需要自旋锁，VPP维护者对C11 Memory Model理解有偏差）；
模板实现机制，可以容易扩展，以实现特定长度的键值应用；

算法原理

Bihash数据结构

Bihash算法已经在数据库领域有若干年广泛的应用；
Bihash具有两级数据结构：

Bihash包含数量为（0x1 << log2_nbuckets）的Bucket组；每个Bucket具有偏移值（指针），指向Bucket的Page数组，Page数组中共计（0x1 << log2_pages）个Page；其中每个Page含有若干个（BIHASH_KVP_PER_PAGE）键/值对（key/value pairs）组成的键值对数组。

Bihash在合理哈希冲突范围内，执行线程安全，耗时固定的查找算法；

Bihash数据结构有一些优点。在实现上，每个Bucket长度为64 bits。目前主流的CPU架构（aarch64, x86）都支持64 bits原子操作。具体当对Bucket进行修改/更新操作时，按照如下流程进行:

对当前Bihash工作Bucket所指向内容进行复制操作，生成复制品Bucket；
原子性的将复制品Bucket指针赋值到Bihash工作Bucket数组；
在原来Bucket上，进行修改/更新操作；
完成修改/更新操作之后，在将原来Bucket的指针原子性的赋值到Bihash工作Bucket数组；

因此，读操作线程在对Bihash进行查找操作时，将不需要锁，来保证和写操作线程的读写一致性。（此处VPP维护者对Memory Model理解有误，后续将有详细的解释）

查找记录

在进行查找操作时，

Bihash通过散列函数计算关键字，得到哈希值hashCode；
哈希值的最低若干位（hashCode & ((0x1 << log2_nbuckets) - 1)）用于索引Bucket数组，得到工作Bucket；
每个Bucket包含若干连续Page（0x1 << log2_pages），组成Page数组。哈希值的次低若干位（（hashCode >> log2_nbuckets）& ((0x1 << log2_pages) - 1)）用于索引Page数组；
每个Page包含若干连续键值对（key/value pairs），Bihash通过逐次线性比较关键字与Page中的每个键值对的关键字，精确匹配记录，最终得到关键字对应的数值；

概括起来，首先通过哈希值的若干位索引Bihash中的Bucket数组，得到Bucket；然后再用哈希值的若干位索引Bucket指向的Page数组，得到Page；最后线性遍历Page中的键值对数组，得到键值对。

添加记录

向Bihash添加新记录时，若发生哈希冲突。Bucket的容量，可包含的Page数量，将被扩大，翻倍。将扩容之前Bucket中包含的键值对记录重新计算哈希值，重新散列添加到扩容之后的Bucket中。

在极小概率情况下，Bihash某个Bucket有可能遭遇连续两次自动扩容都无法解决的冲突。在这种情况下，Bucket包含的Page将不再进行哈希查找定位；Bucket中所有的Page和Page中的键值对，将退化为线性表，添加/删除/查找操作将基于线性表进行。

为充分利用内存，提高利用率，Bihash允许初始化时配置其中Bucket的数量。查找性能通常不会因为Bucket数组容量太大或者太小而变动很大。

删除记录

删除记录的过程与查找过程类似，首先定位待查询关键字是否在Bihash中存在对应的记录。若查询到对应记录，则将该键值对清空，同时，递减bucket->refcnt（其中记录当前Bucket下有效记录数）。当bucket->refcnt为零时，将释放回收Bucket指向的Page数组空间。

散列算法

作为哈希表，散列函数对Bihash性能很大。散列算法选取不好的话，极端情况下，将导致Bihash退化为线性表。

目前VPP Bihash借助intrinsics中计算CRC32 校验码的函数来加哈希值的计算。

   static_always_inline u32
   clib_crc32c (u8 * s, int len)
   {
     u32 v = 0;
     for (; len >= 8; len -= 8, s += 8)
       v = __crc32cd (v, *((u64 *) s));
     for (; len >= 4; len -= 4, s += 4)
       v = __crc32cw (v, *((u32 *) s));
     for (; len >= 2; len -= 2, s += 2)
       v = __crc32ch (v, *((u16 *) s));
     for (; len >= 1; len -= 1, s += 1)
       v = __crc32cb (v, *((u8 *) s));
     return v;
   }

代码实现

Bihash相关的代码文件如下，其中bihash_doc.h作为Bihash解释性文档，列举Bihash实例化时需要定义的宏和实现的函数，作为实例化的参考文件。bihash_template.h和bihash_template.c是Bihash的模板文件，包括Bihash基本数据结构模板，Bihash初始化，记录添加，删除，查找函数模板。其他的文件，比如bihash_8_8.h是Bihash实例文件，表示键值对中关键字和值的长度均为8个字节，此外，定义Bihash在特定应用中的宏，并通过包含bihash_template.h和bihash_template.c文件来实例化函数和数据结构。

lijian@net-arm-c2400-02:~/tasks/bihash$ find -name bihash*
./docs/gettingstarted/developers/bihash.md
./src/plugins/unittest/bihash_test.c
./src/vppinfra/bihash_template.h
./src/vppinfra/bihash_8_8.h
./src/vppinfra/bihash_vec8_8.h
./src/vppinfra/bihash_40_8.h
./src/vppinfra/bihash_template.c
./src/vppinfra/bihash_8_8_stats.h
./src/vppinfra/bihash_16_8.h
./src/vppinfra/bihash_all_vector.c
./src/vppinfra/bihash_doc.h
./src/vppinfra/bihash_24_8.h
./src/vppinfra/bihash_16_8_32.h
./src/vppinfra/bihash_48_8.h

如上述所示，目前VPP infra中已经提供若干Bihash实例化，包括关键字长度为8，16，20，24，40，48字节和不定长度的关键字类型，值的长度都为8字节。

比如，L2功能使用Bihash时，l2_fib.c包含bihash_8_8.h文件；bihash_8_8.h文件中，定义关键字和值长度均为8字节时的宏，和相关处理函数；然后l2_fib.c再包含bihash_template.h文件，实例化Bihash各种操作函数。

Bihash的实例化比较简单。利用已有模板和已有例子，进行修改即可。其中散列函数和关键字比较函数对性能影响比较大。如果关键字比较函数比较慢，那么查找过程也将比较慢。如果哈希值计算过程比较慢，那么查找过程也将比较慢。充分利用好CPU架构向量化计算功能，将能较好提升性能。

性能优化

本章节讨论目前正在进行的针对Bihash数据结构进行的优化方向。

参数设置

Bihash初始化支持参数，关键字/值长度，Bucket容量，Page中键值对数目，Bihash内存尺寸。推荐的Bucket容量设置为Bihash最大支持条目/Page中键值对数目（BIHASH_KVP_PER_PAGE）。Bucket数目设置对Bihash性能影响需要进行实验，验证。Bihash内存尺寸应该在充分考虑哈希冲突的情况下，尽量偏大，以满足完全容纳所有数据条目。

散列函数

目前VPP Bihash通过编译器intrinsics计算CRC32校验码作为关键字的哈希值；一方面可以考虑其他散列函数的实现算法，同时针对目前Bihash大部分应用关键字长度固定的特点，可以考虑在散列函数展开循环操作，降低branch-miss概率。

C11 Memory Model

Bihash中针对读写线程，进行内存同步时，使用full memory barrier。可以考虑应用C11中新定义的load-release/store-acquire模型进行读写线程间的内存同步。

Huge-page

当前为Bihash分配内存实在普通内存区域，可以考虑尝试为Bihash在Huge-page区域分配内存，并于普通内存区域进行性能对比。

其他哈希冲突解决办法

默认当哈希冲突严重到无法通过扩大Bucket中Page数量进行扩展时，Bucket将退化为线性表查找。可以考虑其他的哈希冲突解决办法。

Page结构内存对齐

Page结构内键值对长度固定，但并不能保证所有键值对对齐，考虑将键值对对其到Cache-Line size。

RCU数据模型

Bucket/Page数据预取

现在Bihash已经考虑到进行Bucket和键值对的预取操作。还需要更详细的软件剖析，针对特定aarch64架构进行数据预取的调整。

VPP Bihash实现与优化

概述