DPDK Hash Library原理-DPDK中文网

0.前言

本文主要翻译至DPDK的官方编程指南，在谷歌翻译的基础上根据自己的理解做了一些修改。网上搜索的很多中文翻译大多是翻译后直接黏贴上来，有时候连语句都读不通。希望本文能够对你有所帮助。

1.介绍

DPDK提供了一个哈希库，用于创建用于快速查找的哈希表。哈希表是一种数据结构，它经过优化，用于搜索由唯一键标识的一组哈希条目。为了提高性能，DPDK散列要求所有键在创建散列时具有相同的字节数。

2.Hash API概述

哈希表的主要配置参数有：

表中哈希条目的总数
键的大小(以字节为单位)
用于描述其他设置的额外标志，例如多线程操作模式和可扩展桶功能(稍后将进行描述)

哈希表还允许配置一些底层实现相关参数，如:

将键转换为哈希值的哈希函数

哈希库的主要方法有:

添加带有键的条目：键作为输入参数。如果新条目成功地添加到指定键的哈希表中，或者指定键的哈希表中已经有一个条目，则返回该条目的位置。如果操作不成功，例如由于哈希表中缺少空闲条目，则返回一个负值。
带键删除条目：键作为输入参数。如果在哈希表中找到具有指定键的条目，则从哈希表中删除该条目，并返回在哈希表中找到该条目的位置。如果哈希表中不存在具有指定键的条目，则返回一个负值
查找带有键的条目：键作为输入参数。如果在哈希表中找到具有指定键的条目(即，查找命中)，则返回条目的位置，否则(即，查找未找到)返回负值。

除了上述基本方法之外，哈希库API还提供了一些更高级的方法来查询和更新哈希表：

添加/查找/删除带有键和预计算哈希值的条目：键及其预计算的哈希值均作为输入参数，这使用户能更快地执行这些操作，因为已经计算了哈希值。
添加/查找条目并带上键和数据：添加时不仅允许用户存储键，而且可以带上数据，一个8字节的整数或指向外部数据的指针（如果数据大小超过8个字节）。键和数据都作为输入参数。
以上两个选项的组合：用户可以提供键、预先计算的哈希值以及数据。
能够在调用delete时不释放哈希表中条目的位置。这对于多线程场景非常有用，在这种情况下，即使条目被删除，读者仍然会继续使用该位置。

API还包含一个方法允许用户批量查找条目，这比单个条目查找性能更高，查找函数在执行当前操作时预取下一个条目，这极大地降低了内存访问导致的性能开销。

用户可以使用单独的表来管理与每个键关联的实际数据，该表记录了哈希的条目数和每个条目的位置，如以下各节所述的“流分类”用例所示，用户也可以存储实际数据在哈希表本身中。

在L2/L3转发示例中，程序根据包的五元组信息在哈希表中查找对应的流，再决定要将包转发到哪个端口。当然，这个表也可以用于更复杂的特性，并提供许多可以在包和流上执行的其他功能和操作。

3.多进程支持

哈希库可以在多进程环境中使用。唯一的只能在单进程模式下使用的函数是rte_hash_set_cmp_func（），该函数用于设置一个自定义的比较函数，由于该函数被分配给当前进程的函数指针（因此在多进程模式下不支持）。

4.多线程支持

哈希库支持多线程，并且用户可以在哈希表创建时通过设置适当的标志来指定所需的操作模式。在所有操作模式下，查找都是线程安全的，这意味着可以从多个线程同时调用查找。

对于并发写入和并发读写，以下标志值定义了相应的操作模式：

如果设置了“多个写者”的标志（RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD），则允许多个线程写入表。键的添加、删除和表重置受到保护。如果仅设置此标志，无法保护“读者”免受正在进行的写入操作的影响。
如果设置了读/写并发（RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY），则多线程读/写操作是安全的（即，应用程序不需要“停止读者访问哈希表，一直等待写者完成更新为止”。读者和写者可以同时在表上进行操作）。该库使用读写锁提供并发。
除了这两个标志值外，如果还设置了事务性内存标志（RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT），那么如果硬件支持，读写锁将使用硬件事务性内存（例如Intel®TSX）来保证线程安全。如果平台支持Intel®TSX，建议设置事务性内存标志，因为这将加快并发表操作。否则，由于软件锁定机制相关的开销，并发操作将变慢。
如果设置了无锁读/写并发（RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF），则将提供不使用读写锁的读/写并发。对于不支持事务性内存的平台（例如，当前基于ARM的平台），建议设置此标志以实现更高的性能可伸缩性。如果设置了此标志，则默认设置（RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL）标志。
如果设置了“在删除时不释放”（RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL）标志，则在调用delete（）时不会释放哈希表中条目的位置。当设置无锁读/写并发标志时，默认情况下启用此标志。在所有读者都停止引用该位置之后，应用程序应释放该位置。在需要时，应用程序可以利用RCU机制来确定读者何时停止引用该位置。

5.可扩展的桶（Bucket ）功能支持

通过额外的标志来启用此功能（默认情况下未设置）。设置（RTE_HASH_EXTRA_FLAGS_EXT_TABLE）时（在极不可能的情况下，由于哈希冲突过多而导致无法插入键盘），哈希桶将使用链表进行扩展，以插入这些失败的键。对于插入哈希表的键个数能达到容量的100％且不能容忍任何键插入失败（即使很少）的工作负载（例如，电信工作负载），此功能非常重要。请注意，启用“无锁读写并发”标志后，用户需要调用“ rte_hash_free_key_with_position” API才能释放空存储桶和已删除的键，以保持100％的容量保证。

6.实施细节（不可扩展的桶）

哈希表有两个主要的表：

第一张表是一个桶的数组，每个桶都包含多个条目，每个条目都包含给定键的签名（在下面说明），以及到第二个表的索引。注：下文提到的主和备桶都是在这张表里。
第二张表也是一个数组，它存储了哈希表中所有的键及其与每个键关联的数据。

哈希库使用Cuckoo哈希算法来解决冲突。对于任何输入键，都有两个可能的桶（主和备）用来将该键存储在哈希表中（最终只会存在主或备中的一处），因此在查找键时仅需要检查这两个存储区中的条目。哈希库使用哈希函数（函数可配置）将输入键转换为4字节哈希值。使用部分键哈希[partial-key]，从哈希值中获取桶索引和2字节签名。

一旦桶被标识后，键添的加、删除和查找操作的范围将缩小到这两个桶中的条目（很有可能条目位于主存储桶中）。

为了加快桶的搜索逻辑，每个哈希条目将2字节键签名与每个哈希表条目的完整键一起存储。对于较大的输入键，如果直接将它与桶中保存的键进行比较，会比将它的2字节签名与桶中的键签名进行比较花费更多的时间。因此，仅在签名匹配时才进行完整键的比较。我们仍然需要进行完整键比较，是因为来自同一个桶的两个输入键仍可能具有相同的2字节签名，当然这个事件相对较少，因为哈希函数为输入键集提供良好的均匀分布。

查找示例：

首先，计算哈希值并得到2字节签名和主桶的索引。如果签名存储在此处（很有可能），我们将其键与提供的键进行比较，如果匹配，则返回其存储位置和/或与该键关联的数据。如果签名不在主桶中，则在第二个桶（备桶）中查找，并执行相同的步骤。如果两者都不匹配，则该键不在表中，将返回负值。

添加示例：

像查找一样，主桶和备桶也得到了识别。如果主存储桶中有一个空条目，则将签名存储在该条目中，并将键和数据（如果有）添加到第二个表中，并将第二个表中的索引存储在第一个表的条目中。如果主桶中没有空间，则将该桶上的条目之一推送到其备桶位置，然后将要添加的键插入其位置。为了知道被驱逐条目的替代存储桶在哪里，使用了一种称为部分键哈希[partial-key]的机制。如果备桶中有空间，被逐出的条目将存储在其中。如果没有，则重复相同的过程（其中一个条目被推送），直到找到一个空条目。请注意，尽管第一个表中有条目移动，但第二个表却没有被触及，这将对性能产生很大影响。

在极少数情况下，经过一定数量的移位后找不到空条目，则认为无法添加键（除非设置了可扩展桶标志，在这种情况下桶被扩展以插入键，稍后会说明）。如果键是随机的，此方法将使用户获得90％以上的表利用率，而不必删除任何存储的条目（例如使用LRU替换策略）或分配更多的内存（可扩展的存储桶或重新哈希）。

删除示例：

与查找类似，该键在其主桶和备桶中进行搜索。如果找到了键，则将该条目标记为空。如果哈希表配置为“删除时无释放”或“无锁读/写并发”，则键的位置不会释放。在读者不再引用该位置之后，用户有责任释放该位置。

7.实施细节（带有可扩展桶）

设置RTE_HASH_EXTRA_FLAGS_EXT_TABLE标志后，哈希表实现仍使用相同的Cuckoo哈希算法将键存储到第一表和第二表中。但是，在极少数情况下，在达到一定数量的布谷鸟移位之后还是无法插入键，此键的备桶将扩展带有额外桶的链表，并且该键将存储在此链表中。

在查找某个键的情况下，如前所述，在主、备桶中查找都没有匹配项，则会在扩展桶（额外桶的链表）中逐一查找可能的匹配项，如果没有匹配项，则认为该键不在表中。

删除方法与未设置RTE_HASH_EXTRA_FLAGS_EXT_TABLE标志的情况基本相同，除了以下这点：如果从任何桶中删除了一个键并创建了一个空位置，则与此桶相关联的扩展桶中的最后一个条目将被移入该空位置，从而缩短链表。

8.哈希表中的条目分布

如上所述，在Cuckoo哈希实现里会将条目推入备桶位置，因此，随着用户向哈希表添加条目的增多，其在桶中的分布将发生变化，其中大多数位于主桶位置，少数位于备桶位置，随着条目增加，备桶位置将增加。此信息非常有用，因为随着更多条目被逐出到备桶位置，性能可能会降低。

请参阅下表，其中显示了随着表利用率的提高而产生的条目分布示例。

例1：使用jhash算法在带有1024个随机条目的示例表测量条目分布

例2：使用jhash算法，通过具有100万随机条目的示例表测量条目分布

注：表中的值是使用随机键和Jhash的平均最大表利用率。

9.用例：流分类

流分类用于将每个输入数据包映射到它所属的连接/流。该操作是必需的，因为每个输入数据包的处理通常是在它们的连接上下文中完成的，因此，将同一组操作应用于来自同一条流的所有数据包。

使用流分类的应用程序通常要管理流表，每条流在此表中都有与其相关联的条目。流表条目的大小是由应用程序指定，典型值为4、16、32或64个字节。

使用流分类的应用程序通常从数据包中读取多个字段组成键，依次来唯一标识流。例如使用数据包的IP和传输层头的以下字段组成的5元组：源IP地址，目标IP地址，协议，源端口，目标端口。

DPDK哈希提供了一种通用方法来实现应用程序的流分类机制。给定一个实现为数组的流表，应用程序应创建一个条目数与流表相同的哈希对象，并且哈希键大小设置为所选流键（如五元组）的字节数。

应用程序侧的流表操作如下所述：

添加流：将流键添加到哈希。如果返回的位置有效，则使用它来访问流表中的流条目，以添加新流或更新与现有流关联的信息。否则，流添加失败，例如，由于缺少用于存储新流的空闲条目。
删除流：从哈希表中删除流键。如果返回的位置有效，则使用它来访问流表中的流条目，以使与流关联的信息失效。
释放流：释放流键位置。如果设置了“删除时不释放”或“无锁的读/写并发”标志，请等到读取器没有引用添加/删除流程中返回的位置，然后释放该位置。 RCU机制可用于确定读者何时不再参考该位置。
查找流：在哈希中查找流键。如果返回的位置有效（流查找命中），则使用返回的位置访问流表中的流条目。否则（流查找未命中）表示当前数据包没有注册流。

10.参考文献

DPDK官方文档：http://doc.dpdk.org/guides-20.02/prog_guide/hash_lib.html
Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching (2nd Edition), 1998, Addison-Wesley Professional
[partial-key] Bin Fan, David G. Andersen, and Michael Kaminsky, MemC3: compact and concurrent MemCache with dumber caching and smarter hashing, 2013, NSDI

原创：一觉醒来写程序本文链接：https://www.cnblogs.com/realjimmy/p/12911004.html