dpdk

DPDK Hash

本文主要介绍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官网的统计数据：

image-20240228092113761

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如出一辙。

下图是哈希表逻辑上的结构图：

image-20240228100048365

Data Structure

rte_hash_parameters

用于创建哈希表的参数结构体，包括哈希表的名字、哈希表中条目的数量、哈希表key的长度和哈希表计算主哈希值的函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * Parameters used when creating the hash table.
 */
struct rte_hash_parameters {
	const char *name;		/**< 哈希表的名字 */
	uint32_t entries;		/**< 哈希表的条目数. */
	uint32_t reserved;		/**< Unused field. Should be set to 0 */
	uint32_t key_len;		/**< 待存储key的长度. */
	rte_hash_function hash_func;	/**< 用于计算主哈希的函数. */
	uint32_t hash_func_init_val;	/**< Init value used by hash_func. */
	int socket_id;			/**< 分配内存时使用的numa id */
	uint8_t extra_flag;		/**< Indicate if additional parameters are present. */
};

lcore_cache

per-cpu cache，即每个cpu核心对应的本地缓存结构，包括一个数组和数组当前有效长度，数组中保存的是void*，一般是指向某个空闲可用的对象，每个线程需要获取空闲对象或释放对象时优先从线程所在cpu对应的cache中获取或释放。

对应哈希表结构图中深绿色的部分。

1
2
3
4
5
6

struct lcore_cache {
	unsigned len; /**< Cache len */
	void *objs[LCORE_CACHE_SIZE]; /**< Cache objects */
} __rte_cache_aligned;

rte_hash_key

哈希表存储的<key， value>键值对。值的大小是固定的8byte，可用于存储不超过8 byte的对象或大对象的指针；key是变长的，其长度需要在创建哈希表时设定。

对应哈希表结构图中黄色的部分。

1
2
3
4
5
6
7
8
9
/* Structure that stores key-value pair */
struct rte_hash_key {
	union {
		uintptr_t idata;
		void *pdata;
	};
	/* Variable key size */
	char key[0];
} __attribute__((aligned(KEY_ALIGNMENT)));

创建哈希表时，需要结合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
2
3
4
5
6
7
8
9
10
/** Bucket structure */
struct rte_hash_bucket {
	hash_sig_t sig_current[RTE_HASH_BUCKET_ENTRIES];

	uint32_t key_idx[RTE_HASH_BUCKET_ENTRIES];

	hash_sig_t sig_alt[RTE_HASH_BUCKET_ENTRIES];

	uint8_t flag[RTE_HASH_BUCKET_ENTRIES];
} __rte_cache_aligned;

rte_hash

哈希表结构体。我们主要关注其中重要的数据成员。

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
28
29
30
31
32
33
34
35
36
37
38
/** A hash table structure. */
struct rte_hash {
	char name[RTE_HASH_NAMESIZE];   /**< 哈希表的名字 */
	uint32_t entries;               /**< 哈希表的容量，可以容纳的条目数 */
	uint32_t num_buckets;           /**< 哈希桶数 */

	struct rte_ring *free_slots;
	/**< ring，存放key数组中空闲位置的下标 */
	uint8_t hw_trans_mem_support;
	/**< Hardware transactional memory support */
	struct lcore_cache *local_free_slots;
	/**< per-cpu cache，也是存放key数组中空闲位置的下标 */
	enum add_key_case add_key; /**< Multi-writer hash add behavior */

	rte_spinlock_t *multiwriter_lock; /**< Multi-writer spinlock for w/o TM */

	/* Fields used in lookup */

	uint32_t key_len __rte_cache_aligned;
	/**< Length of hash key. */
	rte_hash_function hash_func;    /**< 计算主哈希值的函数. */
	uint32_t hash_func_init_val;    /**< Init value used by hash_func. */
	rte_hash_cmp_eq_t rte_hash_custom_cmp_eq;
	/**< Custom function used to compare keys. */
	enum cmp_jump_table_case cmp_jump_table_idx;
	/**< Indicates which compare function to use. */
	enum rte_hash_sig_compare_function sig_cmp_fn;
	/**< Indicates which signature compare function to use. */
	uint32_t bucket_bitmask;
	/**< 和主哈希进行&运算获得对应哈希桶的下标 */
	uint32_t key_entry_size;         /**< 键值对的大小 */

	void *key_store;                /**< 存放键值对的数组，即上述key数组 */
	struct rte_hash_bucket *buckets;
	/**< Table with buckets storing all the	hash values and key indexes
	 * to the key table.
	 */
} __rte_cache_aligned;

除了上述结构图中提到的哈希桶数组、ring、per-cpu cache、键值对数组外，还需要一些属性，比如哈希表的名字、键值对大小、条目数、哈希函数等等。

Operations

rte_hash_create

创建哈希表。传入rte_hash_parameters参数以描述哈希表的各项数值成员。

  1. 检查哈希表条目总数是否合法，不能超过RTE_HASH_ENTRIES_MAX（1<<30）或小于8（一个哈希桶条目的数量也是8），key的长度不能为0

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    if (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;
    	}

  2. 计算键值对的数量，如果需要用到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);
    	}

  3. 创建ring

  4. 计算哈希桶的数量并分配哈希桶数组。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    const 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

  5. 计算键值对大小并分配键值对数组

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    const 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;
    	}

  6. 初始化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
2
3
4
5
6
7
8
9
10
...
if (h->hw_trans_mem_support)
		rte_free(h->local_free_slots);

	if (h->add_key == ADD_KEY_MULTIWRITER)
		rte_free(h->multiwriter_lock);
	rte_ring_free(h->free_slots);
	rte_free(h->key_store);
	rte_free(h->buckets);
	...

rte_hash_secondary_hash

从哈希值是由主哈希生成的，可以理解为再次哈希了一次：

1
2
3
4
5
6
7
8
9
10
11
/* Calc the secondary hash value from the primary hash value of a given key */
static inline hash_sig_t
rte_hash_secondary_hash(const hash_sig_t primary_hash)
{
	static const unsigned all_bits_shift = 12;
	static const unsigned alt_bits_xor = 0x5bd1e995;

	uint32_t tag = primary_hash >> all_bits_shift;

	return primary_hash ^ ((tag + 1) * alt_bits_xor);
}

由从哈希值再次调用一次secondary hash，得到的值并不是主哈希值。

rte_hash_lookup

有了对cuckoo哈希和dpdk哈希表整体结构的了解，就不难理解哈希表的查找、插入二号删除过程了。在执行这三种操作时，dpdk还支持传入一个部分哈希值以提高效率的方法，暂且忽略这些，而专注于普通的查、加、删的执行过程。

不论是否提供了部分hash值，dpdk的查找都是通过下述函数执行的，只不过把相应的hash值设为了空。

  1. 首先根据key的主哈希值，在主哈希桶中查找entry，如果找到匹配主哈希值的entry，且其对应的key数组下标不为空（0），则从key数组中找到对应的键值对，并判断key是否匹配。
  2. 根据key的从哈希值，在从桶中比较。这两个桶的比较稍微有些不同
    1. 主桶中比较时，需要比较主哈希值，以及判断是否对应的key下标合法
    2. 从桶中比较时，需要比较主哈希值，从哈希值，但是不需要判断key数组下标是否合法，这个下标一定合法，即不为0
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

static inline int32_t
__rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
					hash_sig_t sig, void **data)
{
	uint32_t bucket_idx;
	hash_sig_t alt_hash;
	unsigned i;
	struct rte_hash_bucket *bkt;
	struct rte_hash_key *k, *keys = h->key_store;

	bucket_idx = sig & h->bucket_bitmask;
	bkt = &h->buckets[bucket_idx];

	/* Check if key is in primary location */
	for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
		if (bkt->sig_current[i] == sig &&
				bkt->key_idx[i] != EMPTY_SLOT) {
			k = (struct rte_hash_key *) ((char *)keys +
					bkt->key_idx[i] * h->key_entry_size);
			if (rte_hash_cmp_eq(key, k->key, h) == 0) {
				if (data != NULL)
					*data = k->pdata;
				/*
				 * Return index where key is stored,
				 * subtracting the first dummy index
				 */
				return bkt->key_idx[i] - 1;
			}
		}
	}

	/* Calculate secondary hash */
	alt_hash = rte_hash_secondary_hash(sig);
	bucket_idx = alt_hash & h->bucket_bitmask;
	bkt = &h->buckets[bucket_idx];

	/* Check if key is in secondary location */
	for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
		if (bkt->sig_current[i] == alt_hash &&
				bkt->sig_alt[i] == sig) {
			k = (struct rte_hash_key *) ((char *)keys +
					bkt->key_idx[i] * h->key_entry_size);
			if (rte_hash_cmp_eq(key, k->key, h) == 0) {
				if (data != NULL)
					*data = k->pdata;
				/*
				 * Return index where key is stored,
				 * subtracting the first dummy index
				 */
				return bkt->key_idx[i] - 1;
			}
		}
	}

	return -ENOENT;
}

rte_hash_add_key

哈希库中插入新的键值对，可以选择提供一个哈希值，目前仅考虑普通的插入操作流程。

  1. 首先，需要在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;
    		}
    	}

  2. 在主桶和从桶中检查是否已经有插入当前待插入的key，如果找到则更新key对应的data

  3. 尝试在主桶中找到一个空闲的slot，如果没有，则尝试将主桶中某个元素push到其从桶中。此处有一个递归push的操作。

reference

[1] DPDK官方文档https://doc.dpdk.org/guides-19.11/prog_guide/ring_lib.html