本文主要介绍DPDK哈希库的设计原理和主要实现代码。DPDK版本为18.05，哈希库的路径在dpdk/lib/librte_hash/。
主要涉及到的实现文件为：
- rte_hash.h：声明了创建哈希表所需要的参数信息（一个结构体）、以及对外提供的库函数接口
- rte_cuckoo_hash.h：cuckoo哈希库实现涉及的接口声明和结构体声明以及定义
- rte_cuckoo_hash.c：cuckoo哈希库实现函数
本文不会细究所有程序的实现，会忽略库中支持并发而添加的额外机制比如锁、rcu等等，主要分析哈希库使用到的管理数据结构、哈希库的创建和释放、哈希库的查找、插入和删除操作实现的大致过程。有兴趣可以直接查看源代码实现。
Introduction
DPDK提供了哈希库，供用户创建哈希表以进行快速查找。不同于教科书上常见的“数组+链表”形式的哈希表，以及数据库系统中使用到的扩展哈希和线性哈希，DPDK采用CuckooHash算法设计哈希库。
CuckooHash
cuckoo从不自己筑巢哺育雏鸟，而是产卵在别人的巢穴，被霸占巢穴的鸟会被cuckoo雏鸟驱逐
cuckoo哈希的思路在于，每个待插入的key可以通过两个哈希函数分别计算出两个哈希值，一个为primary哈希，另一个成为secondary哈希，即主哈希和从哈希。这两个哈希可以计算出两个索引，用于索引哈希桶，这两个哈希桶也被称为主哈希桶和从哈希桶，key可以存放在这两个桶之一，但是优先存放在主哈希桶。因此每次查找的时候需要在两个桶中搜索。删除操作也是，需要在两个桶中检查是否存在待删除的key。
如果试图插入一个新的key，步骤如下：
- 检查主哈希桶中是否有空闲位置，若有则插入并返回
- 检查从哈希桶中是否有空闲位置，若有则插入并返回
- 检查主哈希桶中的每个元素，如果其从哈希桶中有空闲位置，则将其移动到其从哈希桶，并将待插入的key插入主哈希桶，返回
- 执行一个递归的过程，尝试“驱逐”一个主桶中的元素，类似地，这个被驱逐的元素也尝试驱逐它的次桶中的元素，被驱逐的元素总是尝试去驱逐其次桶中的元素（如果次桶为满）或，次桶中有位置则移动到次桶，以次递归，尝试在主桶中找到一个位置插入新的key。当然递归是有次数限制的，如果尝试了指定次数还未成功，则返回失败，无法插入key
大部分情况下，key可以成功在主桶中找到位置，而随着哈希表利用率升高，从桶中的key数量也会占比越来越多。如下是来自dpdk官网的统计数据：
dpdk哈希表
在介绍dpdk哈希表数据结构和接口实现之前，有必要对dpdk哈希表有一个整体的逻辑概念。
首先哈希表使用两个数组存放信息：
- 哈希桶数组，每个元素是一个哈希桶，哈希桶中可以存放若干（DPDK中是8）个entry，每个entry保存<主哈希值，从哈希值，第二个数组的索引>
- key数组：存放<key，数据指针或数据本身>。
主哈希值和从哈希值的大小都是4byte，为了效率，查找的时候先比较哈希桶内的entry中哈希值和待搜索或删除的key的哈希值，如果相等，再取出该entry对应的key数组中的key和当前key比较。
如果需要插入key，不仅需要在主/从哈希桶中找到一个空闲的位置，还需要在key数组中找到一个位置。
哈希桶数组中找位置是通过哈希值&bucket_mask，每个哈希桶中有八个位置。而key存放在哪个key数组则没有限制。只需要找到一个空闲的位置，放入<key，数据或者指向数据的指针>，然后把该位置的下标，存放在哈希桶中的对应的entry就行，当然该entry还需要保存key的主/从哈希值。
因此，初始化时，所有key数组中的下标都是空闲的，放入ring中，并且哈希表有一个lcore_cache，其中每个core对应下标有一个本地缓存，存放的是可用的key下标，这里的做法和mempool如出一辙。
下图是哈希表逻辑上的结构图：
Data Structure
rte_hash_parameters
用于创建哈希表的参数结构体，包括哈希表的名字、哈希表中条目的数量、哈希表key的长度和哈希表计算主哈希值的函数：
1 | /** |
lcore_cache
per-cpu cache，即每个cpu核心对应的本地缓存结构，包括一个数组和数组当前有效长度，数组中保存的是void*，一般是指向某个空闲可用的对象，每个线程需要获取空闲对象或释放对象时优先从线程所在cpu对应的cache中获取或释放。
对应哈希表结构图中深绿色的部分。
1 |
|
rte_hash_key
哈希表存储的<key， value>键值对。值的大小是固定的8byte，可用于存储不超过8 byte的对象或大对象的指针；key是变长的，其长度需要在创建哈希表时设定。
对应哈希表结构图中黄色的部分。
1 | /* Structure that stores key-value pair */ |
创建哈希表时，需要结合key的长度和rte_hash_key的大小，分配足够大的key数组空间。
rte_hash_bucket
哈希桶结构体，代码中宏定义RTE_HASH_BUCKET_ENTRIES的值是8，也就是每个桶中可以存放8个entry。dpdk没有定义“bucket entry”这个概念的结构体，而是将entry中的值分为若干数组存储。sig_current、sig_alt即主、从哈希值的数组，而key_idx为同索引的sig_current和sig_alt对应的key数组中的key的下标。
至于flag数组，其表明当前entry是否是从主桶驱逐出到从桶的。后续分析接口实现的时候会看到其用处。
对应哈希表结构图中浅紫色的部分。
1 | /** Bucket structure */ |
rte_hash
哈希表结构体。我们主要关注其中重要的数据成员。
1 | /** A hash table structure. */ |
除了上述结构图中提到的哈希桶数组、ring、per-cpu cache、键值对数组外，还需要一些属性，比如哈希表的名字、键值对大小、条目数、哈希函数等等。
Operations
rte_hash_create
创建哈希表。传入rte_hash_parameters参数以描述哈希表的各项数值成员。
检查哈希表条目总数是否合法，不能超过RTE_HASH_ENTRIES_MAX（1<<30）或小于8（一个哈希桶条目的数量也是8），key的长度不能为0
1
2
3
4
5
6
7
8
9
10
11
12
13
14if (params == NULL) {
RTE_LOG(ERR, HASH, "rte_hash_create has no parameters\n");
return NULL;
}
/* Check for valid parameters */
if ((params->entries > RTE_HASH_ENTRIES_MAX) ||
(params->entries < RTE_HASH_BUCKET_ENTRIES) ||
!rte_is_power_of_2(RTE_HASH_BUCKET_ENTRIES) ||
(params->key_len == 0)) {
rte_errno = EINVAL;
RTE_LOG(ERR, HASH, "rte_hash_create has invalid parameters\n");
return NULL;
}计算键值对的数量，如果需要用到per-cpu，则键值对的数量会更多一些，并且需要分配per-cpu数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22/* Check extra flags field to check extra options. */
if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT)
hw_trans_mem_support = 1;
/* Store all keys and leave the first entry as a dummy entry for lookup_bulk */
if (hw_trans_mem_support)
/*
* Increase number of slots by total number of indices
* that can be stored in the lcore caches
* except for the first cache
*/
num_key_slots = params->entries + (RTE_MAX_LCORE - 1) *
(LCORE_CACHE_SIZE - 1) + 1;
else
num_key_slots = params->entries + 1;
...
if (hw_trans_mem_support) {
h->local_free_slots = rte_zmalloc_socket(NULL,
sizeof(struct lcore_cache) * RTE_MAX_LCORE,
RTE_CACHE_LINE_SIZE, params->socket_id);
}
创建ring
计算哈希桶的数量并分配哈希桶数组。
1
2
3
4
5
6
7
8
9
10
11
12
13const uint32_t num_buckets = rte_align32pow2(params->entries)
/ RTE_HASH_BUCKET_ENTRIES;
buckets = rte_zmalloc_socket(NULL,
num_buckets * sizeof(struct rte_hash_bucket),
RTE_CACHE_LINE_SIZE, params->socket_id);
if (buckets == NULL) {
RTE_LOG(ERR, HASH, "memory allocation failed\n");
goto err_unlock;
}
...
h->bucket_bitmask = h->num_buckets - 1;// 哈希桶数量对应的mask计算键值对大小并分配键值对数组
1
2
3
4
5
6
7
8
9
10const uint32_t key_entry_size = sizeof(struct rte_hash_key) + params->key_len;
const uint64_t key_tbl_size = (uint64_t) key_entry_size * num_key_slots;
k = rte_zmalloc_socket(NULL, key_tbl_size,
RTE_CACHE_LINE_SIZE, params->socket_id);
if (k == NULL) {
RTE_LOG(ERR, HASH, "memory allocation failed\n");
goto err_unlock;
}初始化ring，此时所有key数组中的位置都是空闲的，将所有下标（除了0）入队
1
2
3/* Populate free slots ring. Entry zero is reserved for key misses. */
for (i = 1; i < num_key_slots; i++)
rte_ring_sp_enqueue(r, (void *)((uintptr_t) i));
rte_hash_free
释放哈希表中各个组件即可，包括哈希桶、ring、key数组和per-cpu cache数组
1 | ... |
rte_hash_secondary_hash
从哈希值是由主哈希生成的，可以理解为再次哈希了一次：
1 | /* Calc the secondary hash value from the primary hash value of a given key */ |
由从哈希值再次调用一次secondary hash，得到的值并不是主哈希值。
rte_hash_lookup
有了对cuckoo哈希和dpdk哈希表整体结构的了解，就不难理解哈希表的查找、插入二号删除过程了。在执行这三种操作时，dpdk还支持传入一个部分哈希值以提高效率的方法，暂且忽略这些，而专注于普通的查、加、删的执行过程。
不论是否提供了部分hash值，dpdk的查找都是通过下述函数执行的，只不过把相应的hash值设为了空。
- 首先根据key的主哈希值，在主哈希桶中查找entry，如果找到匹配主哈希值的entry，且其对应的key数组下标不为空（0），则从key数组中找到对应的键值对，并判断key是否匹配。
- 根据key的从哈希值，在从桶中比较。这两个桶的比较稍微有些不同
- 主桶中比较时，需要比较主哈希值，以及判断是否对应的key下标合法
- 从桶中比较时，需要比较主哈希值，从哈希值，但是不需要判断key数组下标是否合法，这个下标一定合法，即不为0
1 |
|
rte_hash_add_key
哈希库中插入新的键值对，可以选择提供一个哈希值，目前仅考虑普通的插入操作流程。
首先，需要在key数组中获取一个空闲的位置。如果支持per-cpu cache，则优先考虑从当前cpu缓存中获取，如果缓存不够，则从ring中出队一些空闲的位置到当前cpu缓存中；如果没有per-cpu cache，则直接从ring中获取一个空闲的slot，注意ring中存放的全是key数组中空闲slot的下标
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27/* Get a new slot for storing the new key */
if (h->hw_trans_mem_support) {
lcore_id = rte_lcore_id();
cached_free_slots = &h->local_free_slots[lcore_id];
/* Try to get a free slot from the local cache */
if (cached_free_slots->len == 0) {
/* Need to get another burst of free slots from global ring */
n_slots = rte_ring_mc_dequeue_burst(h->free_slots,
cached_free_slots->objs,
LCORE_CACHE_SIZE, NULL);
if (n_slots == 0) {
ret = -ENOSPC;
goto failure;
}
cached_free_slots->len += n_slots;
}
/* Get a free slot from the local cache */
cached_free_slots->len--;
slot_id = cached_free_slots->objs[cached_free_slots->len];
} else {
if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0) {
ret = -ENOSPC;
goto failure;
}
}在主桶和从桶中检查是否已经有插入当前待插入的key，如果找到则更新key对应的data
尝试在主桶中找到一个空闲的slot，如果没有，则尝试将主桶中某个元素push到其从桶中。此处有一个递归push的操作。
reference
[1] DPDK官方文档https://doc.dpdk.org/guides-19.11/prog_guide/ring_lib.html
