用于CUCKOO散列流查找的并发性的技术

摘要

本文描述了用于CUCKOO散列流查找的并发性的技术。用于在网络设备处支持流查找表并发性的技术。该流转发表包括多个候选桶，该多个候选桶各自包括一个或多个条目。该网络设备包括流查找表写模块，该流查找表写模块被配置成用于经由原子指令执行密钥/值对的移位操作以便将该密钥/值对从一个候选桶移动到另一个候选桶以及使与由该移位操作影响的这些桶相关联的版本计数器递增。该网络设备另外包括流查找表读模块，该流查找表读模块用于在该流查找表上执行查找操作期间检查这些版本计数器以便确定移位操作是否影响这些桶的目前读取值。在此描述并要求保护其他实施例。

说明书

背景

现代计算设备正在变成个人、商务以及社交用途的非常普遍的工具。这样，许多现代计算设备能够连接到各种数据网络，包括互联网和公司内部网，以便通过这种网络检索并传输/接收数据通信。经常，连接到一个网络的计算设备需要与连接到不同网络上的计算设备通信。为了促成这种计算设备之间的通信，网络通常包括一个或多个网络设备(例如，网络交换机、网络路由器等等)以便基于存储在流查找表中的网络流将通信(即，网络分组)从一个计算设备路由到另一个计算设备。传统上，已经在这些网络设备的专用网络处理器上执行网络分组处理(例如，分组交换)。

网络虚拟化技术(例如，网络功能虚拟化(NFV)和中央控制器网络架构(例如，软件定义网络(SDN)))及其使用要求已经介绍了基于软件的网络分组处理。这种基于软件的网络分组处理已经导致支持用通用处理器在网络设备上执行网络分组处理的网络基础设施，由此增加可扩展性、可配置性和灵活性。通常，网络分组流标识库使用在其上执行网络流查找的散列表(即，流查找表)。然而，在散列过程中，可能发生散列冲突。

一个这种方法(Cuckoo(布谷鸟)散列)已经作为用于使用网络分组输入/输出(I/O)引擎(例如，用于快速网络分组处理(例如，流查找表查找、软件路由器/交换机功能等等)的数据平面开发工具(DPDK))数据平面库和网络接口控制器驱动器在流查找表查找过程中解决散列冲突的存储器高效的、高性能的散列方案出现。然而，读写并发可能对于有效地在通用处理器上利用Cuckoo散列是有必要的。换言之，当通用处理器的核正在更新流查找表时，通用处理器的另一个核应当能够并行地执行流查找，而无需锁定流查找表。

附图简要描述

通过举例而非通过限制在附图中示出在此描述的概念。为了说明简单和清晰，图中所示元素无需按比例绘制。当认为合适时，已经在附图中重复参照标号以便表明相应的或类似的元素。

图1是用于cuckoo散列并发的系统的至少一个实施例的简化框图；

图2是图1的系统的网络设备的至少一个实施例的简化框图；

图3是图2的网络设备的环境的至少一个实施例的简化框图；

图4是可由图2的网络设备使用的双向功能、四向关联Cuckoo散列表的至少一个实施例的简化示意图；

图5和图6是可由图2的网络设备执行的用于执行流查找表查找的方法的至少一个实施例的简化流程图；以及

图7是可由图2的网络设备执行的用于支持读写并发的流查找表的密钥/值对的原子移位操作的方法的至少一个实施例的简化流程图。

附图详细描述

尽管本公开的概念可受到各种修改和替代形式，已经通过举例在附图中示出并且将在此详细地描述其特定实施例。然而，应当理解的是不旨在将本公开的概念限制为所公开的具体形式，而是相反，本发明涵盖与本公开和所附权利要求书一致的所有修改、等效方案和替代方案。

在说明书中对“一个实施例”、“实施例”、“说明性实施例”等等的引用表明所描述的实施例可包括具体的特征、结构或特性，但是每个实施例可无需包括该具体的特征、结构或特性。而且，这种短语无需指代相同的实施例。而且，当结合实施例描述具体的特征、结构或特性时，认为其在本领域普通技术人员结合显式地或未显式地描述的其他实施例实施这种特征、结构或特性的知识范围内。此外，应当认识到列表中包括的“A、B和C中的至少一个”形式的项目可意味着(A)；(B)；(C)；(A和B)；(A和C)；(B和C)；或者(A、B和C)。类似地，以“A、B、和C中的至少一个”的形式列出的项目可指(A)；(B)；(C)；(A和B)；(A和C)；(B和C)；或(A、B和C)。

在某些情况下，可在硬件、固件、软件、或其任何组合中实现所公开的实施例。所公开的实施例还可被实现为由一个或多个瞬态或非瞬态机器可读(例如计算机可读)存储介质携带或存储在其上的指令，这些指令可由一个或多个处理器读取并执行。机器可读存储介质可被实施为任何用于存储或传输机器(例如，易失性或非易失性存储器、介质盘、或其他介质设备)可读形式的信息的存储设备、机构、或其他物理结构。

在附图中，可用特定安排和/或排序示出某些结构或方法特征。然而，应当认识到可不要求这种特定安排和/或排序。相反地，在某些实施例中，可用与说明性附图中示出的不同的方式和/或顺序安排这种特征。此外，具体附图中包括结构或方法特征不意味着日音示在所有实施例中要求这种特征以及在某些实施例中可不包括这种特征或者这种特征可与其他特征组合。

现在参照图1，在说明性实施例中，用于cuckoo散列流查找并发的系统100包括经由一个或多个网络设备106通过网络104通信的计算设备102和远程计算设备108。网络设备106通过处理并路由从计算设备102到远程计算设备108并且反之亦然的网络分组促成通过网络104的网络通信(即，网络分组)。例如，计算设备102可尝试将封装在一个或多个网络分组中的数据(即，网络分组的有效载荷)传输到远程计算设备108。为此，负责处理并路由网络分组的每个网络设备106基于通常在网络分组中提供的信息(例如，在互联网协议(IP)网络分组的头部中)来这样做。

在使用时，如以下进一步详细描述的，网络设备106可从计算设备(例如，计算设备102、另一个网络设备106等等)接收网络分组、基于在网络设备106处存储的策略处理网络分组并且将网络分组转发到目标计算设备(例如，另一个网络设备106、远程计算设备108等等)。为了标识目标计算设备，网络设备106在流查找表(即，将流条目映射到网络流的下一个目标的散列表)上执行基于散列的查找操作以便确定网络分组的流。为此，查找操作在与网络分组有关的信息(例如，目的地IP地址、目的地媒体访问控制(MAC)地址、五元组流标识等等)上执行散列并且使用该结果检查流查找表。

流查找表包括包含或者与网络分组的参数相对应的特定值或者指示流条目未包括在特定流的参数集合中的匹配字段。每个散列表条目或桶可包括一个或多个密钥/值对，其中，密钥标识某个数据项(例如，网络分组流标识符)而值提供该数据在另一个位置(诸如另一个表)中的位置(例如，与网络分组流标识符相对应的流数据)。此外，每个桶可支持多于一个密钥/值对。例如，如果散列表是四向关联表，则一个桶可支持四个密钥/值对条目。此外，每个密钥可被映射到多于一个桶。例如，散列函数阵列可被提供为使得不同的桶可基于哪一个散列函数被应用到密钥而被映射到该密钥。

为了支持流查找表的读写并发，网络设备106将版本计数器与流查找表中的一个或多个散列表条目或桶相关联，每次修改相关联的桶时对这些条目或桶进行递增。不像要求在每个查找操作下进行版本计数器的状态比较的传统并发支持方法，使用被原子地写入和/或读取的加载/存储指令(例如，流送传输单指令多数据(SIMD)扩展2(SSE2)加载/存储指令)可确保与所发现的密钥相关联的值有效。这样，仅当未在其相应的桶内发现密钥时要求执行版本计数器状态比较，由此减少了与在每个查找上执行比较相关联的开销。

计算设备102可被实施为任何类型的能够执行在此描述的功能的计算或计算机设备，包括但不限于计算机、桌上计算机、工作站、膝上计算机、笔记本计算机、平板计算机、移动计算设备、可穿戴计算设备、网络电器、web电器、分布式计算系统、基于处理器的系统和/或消费者电子设备。类似地，远程计算设备108可被实施为任何类型的能够执行在此描述的功能的计算或计算机设备，包括但不限于计算机、智能电话、平板计算机、膝上计算机、笔记本计算机、移动计算设备、可穿戴计算设备、多处理器系统、服务器(例如，独立式、机架式、刀片式等等)、网络电器(例如，物理的或虚拟的)、web电器、分布式计算系统、基于处理器的系统和/或消费者电子设备。在使用时，远程计算设备108被配置成用于通过网络104经由网络设备106与计算设备102通信。

网络104可被实施为任何类型的有线或无线通信网络，包括蜂窝网络(例如，全球移动通信系统(GSM))、数字用户线(DSL)网络、有线网络、电话网络、局域网或广域网、全球网(例如，互联网)或其任何组合。网络设备106可被实施为任何类型的能够促成计算设备102和远程计算设备108之间的有线和/或无线网络通信的计算设备。例如，网络设备106可被实施为计算机、路由器、交换机、网络中枢、服务器、存储设备、计算设备等等。另外，网络104可包括促成计算设备102和远程计算设备108之间的通过网络104的通信的任何数量的网络设备106。

网络设备106各自可被实施为任何类型的能够管理通信并执行在此描述的功能的计算或计算机设备，包括但不限于通用计算设备、网络电器(例如，物理的或虚拟的)、web电器、路由器、交换机、多处理器系统、服务器(例如，独立式、机架式、刀片式等等)、分布式计算系统、基于处理器的系统、桌上计算机、膝上计算机、笔记本计算机、平板计算机、智能电话、移动计算设备、可穿戴计算设备、消费者电子设备或其他计算设备。在某些实施例中，诸如在SDN和/或网络功能虚拟化(NFV)架构中，网络设备106中的一个或多个可运行一个或多个虚拟机(VM)以便在软件中实现网络设备106的物理网络功能。换言之，某些网络设备106或其功能可被虚拟化。

如图2所示，说明性网络设备106包括处理器202、输入输出(I/O)子系统208、存储器210、数据存储设备214以及通信电路216。当然，在其他实施例中，网络设备106可包括替代或附加组件，诸如通常在服务器、路由器、交换机或其他网络计算设备中发现的那些。此外，在某些实施例中，说明性组件中的一个或多个可被结合到另一个组件中或者以其他方式形成其一部分。例如，在某些实施例中，存储器210或其部分可被结合到一个或多个处理器202中。

处理器202可被实施为能够执行在此描述的功能的任何类型的处理器。处理器202可被实施为单核处理器或多核处理器、多个处理器、数字信号处理器、微控制器、图形处理单元(GPU)、通用GPU(GPGPU)、加速处理单元(APU)、现场可编程门阵列(FPGA)或其他处理器或处理/控制电路。存储器210可被实施为能够执行在此描述的功能的任何类型的易失性或非易失性存储器或数据存储设备。在操作中，存储器210可存储在网络设备106的操作期间使用的各种数据和软件，诸如操作系统、应用、程序、库和驱动程序。存储器210经由I/O子系统208通信地耦合到处理器202，其可被实施为用于促成与网络设备106的处理器202、存储器210、以及其他组件的输入/输出操作的电路和/或组件。例如，I/O子系统208可被实施为或以其他方式包括用于促成输入/输出操作的存储器控制器中枢、输入/输出控制中枢、集成传感器中枢、固件设备、通信链路(即，点到点链路、总线链路、导线、线缆、光导、印刷电路板迹线等等)和/或其他组件及子系统。在某些实施例中，I/O子系统208可形成片上系统(SoC)的一部分并且可与网络设备106的处理器202、存储器210和其他组件一起结合到单个集成电路芯片上。

说明性网络设备106包括可被实施为片上高速缓存或处理器上高速缓存的高速缓存存储器204。在某些实施例中，高速缓存存储器204可被实施为计算设备102的处理器202可比访问存储器208更快速地访问的任何类型的高速缓存存储器。例如，在某些实施例中，高速缓存存储器204可以是片外高速缓存但是驻留在与处理器202相同的SoC上。

在使用时，如以下将进一步详细描述的，网络流信息被写入流查找表206，该表向转发表212提供映射信息，该转发表可能太大而不能存储在高速缓存存储器204中。网络流信息可包括诸如例如与特定网络流相对应的流标识符和流元组(例如，源IP地址、源端口号、目的地IP地址、目的地端口号以及协议)等信息。应当认识到网络流信息可包括与特定网络流相对应的任何其他类型或组合信息。在某些实施例中，连接到网络设备106的网络控制器(未示出)(诸如软件定义网络(SDN)控制器)可定义流(即，计算流的路由)并且提供所定义的流从而沿着该流所标识的传输路径进入每个网络设备106的流查找表206中。

尽管说明性流查找表206存储在高速缓存存储器204中，但是在某些实施例中，流查找表206的至少一部分可存储在网络设备106的存储器210(即，主存储器)中。由于与不得不执行对存储器210中的转发表212中的网络流信息的查找相关联的时延，密钥/值对可存储在流查找表206(即，散列表或散列查找表)中将输入值(例如，与所接收的网络分组有关的数据)映射到转发表212的转发表条目的条目中。

数据存储设备214可被实施为被配置成用于数据的短期或长期存储的任何类型的设备，诸如例如存储器设备和电路、存储器卡、硬盘驱动器、固态驱动器、或其他数据存储设备。在某些实施例中，数据存储设备214可用于存储一个或多个信任执行环境的内容。当由数据存储设备214存储时，信任执行环境的内容可被加密以便防止未授权软件的访问。

通信电路216可被实施为能够使得能够通过网络104在网络设备106和计算设备102、另一个网络设备106和/或远程计算设备108之间进行通信的任何通信电路、设备或其集合。通信电路216可被配置成用于使用任何一种或多种通信技术(例如，无线通信或有线通信)和相关联的协议(例如，以太网、WiMAX等等)来使这种通信生效。说明性通信电路216另外包括网络接口卡(NIC)218。NIC 218可将网络设备106连接到计算设备102、另一个网络设备106或远程计算设备108。NIC 218可被实施为一个或多个扩充卡、子卡、网络接口卡、控制器芯片、芯片组或可由网络设备106使用的其他设备。例如，NIC 218可被实施为通过扩展总线(诸如PCI Express(快速))耦合到I/O子系统208的扩展卡。

现在参照图3，在使用中，网络设备106在操作期间建立环境300。在说明性环境300中，网络设备106包括网络通信模块310和流查找表管理模块320。说明性环境300另外包括可包含网络流相关的信息的流查找表数据302。环境300的各个模块可被实施为硬件、固件、软件或其组合。例如，环境300的各个模块、逻辑和其他组件可形成网络设备106的处理器或其他硬件组件的一部分或以其他方式由其建立。这样，在某些实施例中，环境300的模块中的任何一个或多个可被实施为电气设备的电路或集合(例如，网络通信电路、流查找表管理电路等等)。此外或可替代地，在某些实施例中，说明性模块中的一个或多个可形成另一个模块的一部分和/或说明性模块和/或子模块中的一个或多个可被实施为单独的或独立的模块。

网络通信模块310被配置成用于促成网络设备106和目标计算设备(例如，另一个网络设备106、远程计算设备108等等)之间的网络通信。换言之，网络通信模块310被配置成用于接收并处理由网络设备106所接收的网络分组并且准备并传输来自网络设备106的网络分组。相应地，网络通信模块310的至少一部分功能可由通信电路216并且更具体地由NIC 218执行。此外，网络通信模块310可通过解析网络分组的至少一部分处理所接收的网络分组以便确定所接收的网络分组的网络流信息(例如，五元组流标识、源IP/MAC/端口、目的地IP/MAC/端口等等)和/或通过用经更新的网络流信息更新网络分组来准备用于传输的网络分组。

流查找表管理模块320被配置成用于管理流查找表(例如，图1的流查找表206)的流查找表数据302。如先前所描述的，流查找表206包括各自包括一个或多个密钥/值对和相应的版本计数器的多个桶。流查找表管理模块320包括流查找表读模块322和流查找表写模块324以便支持从流查找表和到流查找表的并发读写。

流查找表读模块322被配置成用于在流查找表上执行读操作以便从流查找表数据302读。流查找表读模块322可被配置成用于在流查找表数据302上执行查找，在图5中示出了其实施例。在某些实施例中，流查找表读模块322可被配置成用于并行地执行多个读操作而无需任何锁或互斥器。如先前所描述的，版本计数器可基于流查找表的结构与每个散列表桶相关联(例如，流查找表的方向关联的方向号)。不像传统的要求在读前和读后操作比较版本计数器的读/写冲突检测方法，如果未在读/查找操作期间在流查找表206中的预期位置或桶中发现密钥/值对的密钥，流查找表读模块322仅在读操作之后执行版本计数器比较。

流查找表写模块324被配置成用于在流查找表上执行写操作以便向流查找表数据302写。流查找表写模块324可被进一步配置成用于当更新或将密钥/值对插入到流查找表数据302中时执行移位过程，如图7所示。每当流查找表写模块324访问桶以便修改并且当流查找表写模块324修改该桶时，流查找表写模块324使版本计数器递增。

在某些实施例中，可通过使用固有的加载和存储指令基于网络设备106的处理器202的架构减少与版本计数器检查和比较相关联的开销。例如，在架构(IA)实施例中，IA固有指令可包括“mm_load(mm_加载)”以便读密钥和“mm_store(mm_存储)”以便写密钥。此外，为了支持原子操作，密钥/值对可基于流查找表的条目的大小存储在单个高速缓存对齐的数据结构中。例如，如果流查找表数据302中的条目的大小等于16字节，该单个高速缓存对齐的数据结构可具有小于或等于16字节的大小。结果是，流查找表写模块324可在单个操作中对密钥/值对进行移位，而不是针对密钥的一个写操作和针对值的另一个写操作。相应地，如果在流查找表中发现了密钥/值对(即，由流查找表读模块322读取)，与所发现的密钥相关联的值可被假设为有效。换言之，如果在流查找表中发现了密钥/值对，可以假设其不是在被更新的过程中。

现在参考图4，说明性Cuckoo散列表400可被实施为支持将桶404(即，多个条目)映射到一个或多个条目402以便存储密钥/值对的集合关联散列流查找表。说明性Cuckoo散列表400是包括多个桶404的双向功能、四向关联Cuckoo散列表，所述多个桶各自包括四个条目402以便存储密钥/值对。此外，每个桶被映射到相应的版本计数器406。尽管说明性Cuckoo散列表400中的版本计数器406的每个版本计数器被示出为与桶404中的多于一个桶相对应，应当认识到在某些实施例中版本计数器406各自可仅与桶404中的一个桶相对应(即，每个桶404可具有其自身的版本计数器406)。此外，尽管在说明性实施例中示出了四向集合关联散列表，但是应当认识到可使用可替代的集合关联散列表。

现在参考图5，在使用中，网络设备106可执行用于在流查找表处执行查找的方法500。方法500以框502开始，其中，网络设备106确定是否已经请求对流查找表(例如，图2的流查找表206)的查找。如果没有，方法返回到框502以便继续确定是否请求过流查找表206查找。应当认识到在某些实施例中，方法500不用做轮询方法(即，在预定的时间间隔采样)，并且可在接收到指示已经请求过流查找表查找的消息或通知时初始化(即，开始)方法500。如果网络设备106确定流查找表206查找已经被请求过(例如，经由轮询或接收消息)，则方法前进到框504。

在框504，网络设备106计算与查找请求相关联的标识符(例如，目的地IP地址、五元组流标识、目的地MAC地址等等)的候选桶。为此，网络设备106可将不同的散列函数应用到标识符，其中，每个候选桶基于不同的散列函数与不同的候选桶相对应。相应地，每个标识符可被映射到多个候选桶并且每个候选桶可基于不同的散列函数。例如，图4的Cuckoo散列表400(即，双向功能、四向关联)包括用于将密钥/值对输入Cuckoo散列表400中的两个候选桶。相应地，在这种两候选桶实施例中，在框506处，网络设备106通过将第一散列应用到密钥计算第一候选桶并且通过将第二散列应用到密钥计算第二候选桶。在框508处，网络设备106读取用于在框504处计算的每个候选桶的密钥。在说明性实施例中，在框510处，网络设备106读取第一和第二候选桶的密钥。在框512处，网络设备106确定是否在框508处读取的任何候选桶中发现过密钥。在说明性实施例中，网络设备106确定是否在框506处计算并且在框510处读取的第一或第二候选桶中的任一个中发现密钥。

如果络设备106确定在框508处读取的任何候选桶中发现密钥，方法500前进到框514，其中，在方法500前进到框516之前从与在其中发现密钥的候选桶相对应的候选桶读取值。在返回到框502之前，在框516，方法500返回在框514处读取的值，其中，方法500继续确定是否请求过对流查找表206查找。然而，如果网络设备106确定未在框512处的任何候选桶中发现过密钥，方法500前进到框518。

在框518处，网络设备106读取在框504处计算的候选桶中的每个候选桶的版本计数器。相应地，在说明性实施例中，在框520处，网络设备106读取与在框506处计算的候选桶的第一和第二版本计数器相对应的第一和第二版本计数器。在框522处，网络设备106确定在框518处读取的任何版本计数器是否是奇数。如果任何版本计数器是奇数，方法500返回到框518以便再次读取版本计数器。这种状况可指示目前正在发生移位，诸如以下在图7中描述的原子移位操作。换言之，密钥可从一个桶移动到另一个桶，并且密钥可能已经从一个桶被删除但是尚未添加到另一个桶。相应地，方法500可继续检查版本计数器(即，在框522处)并且继续返回到框518直到在框518处读取的所有版本计数器是偶数。

如果网络设备106在框522处确定版本计数器都是偶数，则方法500前进到框524。类似于框508，在框524处，网络设备106重新读取用于在框504处计算的每个候选桶的密钥。在两候选桶实施例中，在方法500前进到框528之前，在框526处，网络设备106重新读取第一和第二候选桶的密钥。在框528处，如图6所示，网络设备106确定是否在框524处读取的任何候选桶中发现密钥。在两候选桶实施例中，网络设备106确定是否在框506处计算的并且在框526处读取的第一或第二候选桶中的任一个中发现密钥。

如果在框528处读取的任何候选桶中发现过密钥，方法500前进到框514，其中，从与在其中发现过密钥的候选桶相对应的候选桶读取值。如果未发现密钥，则方法500前进到框530，其中，网络设备106重新读取候选桶的版本计数器。在说明性实施例中，在前进到框534之前，在框532处，网络设备106重新读取第一和第二候选桶的版本计数器。在框534处，网络设备106确定在框530处重新读取的当前版本计数器值是否等于在框518处读取的先前版本计数器值。如果不是，则方法500返回框518以便读取在框504处计算的候选桶的版本计数器。如果在框630处重新读取的当前版本计数器值等于在框518处读取的先前版本计数器值，则在回到框502以便继续确定是否请求过流查找表查找之前，网络设备106返回“未发现”密钥的指示。

现在参照图7，在使用时，网络设备106可执行用于支持读写并发的流查找表(诸如图1的流查找表206)的密钥/值对的原子移位操作的方法700。如上所述，网络设备106计算流标识符(例如，目的地IP地址、五元组流标识、目的地MAC地址等等)的候选桶，其中，候选桶包括一个或多个密钥/值条目。作为将密钥/值对散列化并存储在这些候选桶条目之一中的副产品，现有的密钥/值条目可被重新定位到替代的候选桶。在单个密钥/值对插入期间这种重新定位或移位可发生多次。

方法700以框702开始，其中，网络设备106确定是否已经更新流查找表206。如果没有，方法返回到框702以便继续确定是否已经更新流查找表206。应当认识到在某些实施例中，方法700不用做轮询方法(即，在预定的时间间隔采样)，并且可在接收到指示已经更新流查找表查找206的流条目的消息或通知时初始化(即，开始)方法700。如果网络设备106确定流查找表206被更新过(例如，经由轮询或接收消息)，则方法前进到框704。

在框704，网络设备106使被映射到与经更新的流条目相对应的候选桶的任何版本计数器递增。例如，图4的Cuckoo散列表400包括用于每个密钥的两个候选桶。在这种实施例中，网络设备106在框706将与第一候选桶相对应的版本计数器和与第二候选桶相对应的版本计数器增量。在框708处，网络设备106使用原子指令将密钥/值对从第一候选桶移除。在框710处，网络设备106使用原子指令将密钥/值写入第二候选桶。换言之，代替正常的写操作，固有指令(诸如“mm_store”)可用于将密钥写入相应的候选桶(即，第二候选桶)以便移位。如先前所提及的，指令原子性的结果是，在任一个候选桶中发现的密钥可指示有效值。在框712处，网络设备106再次将与经更新的流条目相对应的任何桶版本计数器增量。在包括两个候选桶以便输入密钥/值对的实施例中(例如，图4的Cuckoo散列表400)，在框714处，网络设备106再次将第一候选桶的版本计数器和第二候选桶的版本计数器增量。

示例

以下提供在此公开的设备、系统、和方法的说明性示例。设备、系统、和方法的实施例可包括以下所描述的示例中的任何一个或多个以及任何组合。

示例1包括一种支持流查找表并发性的网络设备，该网络设备包括：与该网络设备的处理器相关联的高速缓存存储器，该高速缓存存储器用于存储包括多个条目和多个候选桶的流查找表，其中，每个候选桶被映射到版本计数器并且包括该多个条目中的一个或多个以便存储映射到网络分组的流的密钥/值对，并且其中，该多个候选桶包括被映射到第一版本计数器的第一候选桶和被映射到第二版本计数器的第二候选桶；流查找表写模块，该流查找表写模块用于经由原子指令执行密钥/值对的移位操作以便响应于确定该密钥/值对在该流查找表中更新或者被插入到该流查找表中之一将该密钥/值对从该第一候选桶移动到该第二候选桶；以及流查找表读模块，该流查找表读模块用于在该流查找表上执行查找操作。

示例2包括示例1所述的主题，并且其中，该流查找表包括将密钥映射到该多个候选桶中的每一个的集合关联散列流查找表。

示例3包括示例1和2中任一项所述的主题，并且其中，该集合关联散列流查找表包括集合关联Cuckoo散列表。

示例4包括示例1-3中任一项所述的主题，并且其中，该集合关联散列流查找表包括双向功能、四向关联Cuckoo散列表。

示例5包括示例1-4中任一项所述的主题，并且其中，该密钥/值对包括具有小于或等于该多个条目之一的大小的大小的单个高速缓存对齐数据结构。

示例6包括示例1-5中任一项所述的主题，并且其中，该第一候选桶是基于应用到流标识符的第一散列函数确定的，而该第二候选桶是基于应用到该流标识符的不同于该第一散列函数的第二散列函数确定的。

示例7包括示例1-6中任一项所述的主题，并且其中，执行该密钥/值对的该移位操作包括(i)增加该第一和第二版本计数器，(ii)从该第一候选桶移除该密钥/值对，(iii)将该密钥/值写入该第二候选桶，以及(iv)增加该第一和第二版本计数器。

示例8包括示例1-7中任一项所述的主题，并且其中，执行该查找操作包括(i)使用多于一个散列函数来为密钥计算该第一和第二候选桶，(ii)确定该密钥是否在该第一或第二候选桶中的任一个内，以及(iii)响应于确定该密钥在该第一候选桶内从与来自该第一候选桶的该密钥相对应的条目读取值或者响应于确定该密钥在该第二候选桶内从与来自该第二候选桶的该密钥相对应的条目读取该值。

示例9包括示例1-8中任一项所述的主题，并且其中，响应于确定该密钥不在该第一或第二候选桶中的任一个内，该查找操作进一步包括(i)读取该第一和第二版本计数器以及(ii)确定该第一或第二版本计数器之一是否是奇数。

示例10包括示例1-9中任一项所述的主题，并且其中，响应于确定该第一或第二版本计数器之一是奇数，该查找操作进一步包括重新读取该第一和第二版本计数器。

示例11包括示例1-10中任一项所述的主题，并且其中，响应于确定该第一或第二版本计数器都不是奇数，该查找操作进一步包括(i)确定该第一或第二候选桶中的任一个是否包括该密钥以及(ii)响应于确定该密钥在该第一或第二候选桶中的任一个中返回与该密钥相对应的该值。

示例12包括示例1-11中任一项所述的主题，并且其中，响应于确定该第一或第二版本计数器都不是奇数，该查找操作进一步包括(i)确定该第一或第二候选桶中的任一个是否包括该密钥以及(ii)响应于确定该密钥不在该第一或第二候选桶中的任一个中返回未发现该密钥的指示。

示例13包括一种支持流查找表并发的方法，该方法包括：存储包括多个条目和多个候选桶的流查找表，其中，每个候选桶被映射到版本计数器并且包括该多个条目中的一个或多个以便存储映射到网络分组的流的密钥/值对，并且其中，该多个候选桶包括被映射到第一版本计数器的第一候选桶和被映射到第二版本计数器的第二候选桶；经由原子指令执行密钥/值对的移位操作以便响应于确定该密钥/值对在该流查找表中更新或者被插入到该流查找表中之一将该密钥/值对从该第一候选桶移动到该第二候选桶；以及在该流查找表上执行查找操作。

示例14包括示例13所述的主题，并且其中，在该流查找表上执行该查找操作包括在将密钥映射到该多个候选桶中的每一个的集合关联散列流查找表上执行该查找操作。

示例15包括示例13和14中任一项所述的主题，并且其中，在该流查找表上执行该查找操作包括在集合关联Cuckoo散列表上执行该查找操作。

示例16包括示例13-15中任一项所述的主题，并且其中，在该集合关联散列流查找表上执行该查找操作包括在双向功能、四向关联Cuckoo散列表执行该查找操作。

示例17包括示例13-16中任一项所述的主题，并且其中，经由述原子指令执行该密钥/值对的该移位操作包括执行具有小于或等于该多个条目之一的大小的大小的单个高速缓存对齐数据结构的该移位操作。

示例18包括示例13-17中任一项所述的主题，并且其中，该第一候选桶是基于应用到流标识符的第一散列函数确定的，而该第二候选桶是基于应用到该流标识符的不同于该第一散列函数的第二散列函数确定的。

示例19包括示例13-18中任一项所述的主题，并且其中，执行该密钥/值对的该移位操作包括(i)增加该第一和第二版本计数器，(ii)从该第一候选桶移除该密钥/值对，(iii)将该密钥/值写入该第二候选桶，以及(iv)增加该第一和第二版本计数器。

示例20包括示例13-19中任一项所述的主题，并且其中，执行该查找操作包括(i)使用多于一个散列函数为密钥计算该第一和第二候选桶，(ii)确定该密钥是否在该第一或第二候选桶中的任一个内，以及(iii)响应于确定该密钥在该第一候选桶内从与来自该第一候选桶的该密钥相对应的条目读取值或者响应于确定该密钥在该第二候选桶内从与来自该第二候选桶的该密钥相对应的条目读取该值。

示例21包括示例13-20中任一项所述的主题，并且其中，执行该查找操作进一步包括用于(i)响应于确定该密钥不在该第一或第二候选桶中的任一个中而读取该第一和第二版本计数器以及(ii)确定该第一或第二版本计数器之一是否是奇数。

示例22包括示例13-21中任一项所述的主题，并且其中，执行该查找操作进一步包括响应于确定第一或第二候选桶中的任一个的第一或第二版本计数器之一是奇数而重新读取该第一或第二候选桶中的任一个的第一和第二版本计数器。

示例23包括示例13-22中任一项所述的主题，并且其中，执行该查找操作进一步包括(i)确定该第一或第二候选桶中的任一个是否包括该密钥，以及(ii)响应于确定该密钥在该第一或第二候选桶中的任一个中返回与该密钥相对应的该值。

示例24包括示例13-23中任一项所述的主题，并且其中，执行该查找操作进一步包括(i)确定该第一或第二候选桶中的任一个是否包括该密钥以及(ii)响应于确定该密钥在该第一或第二候选桶中的任一个中返回未发现该密钥的指示。

示例25包括计算设备，该计算设备包括处理器和存储器，该存储器其中存储有多条指令，当由该处理器执行时，该多条指令致使该计算设备执行示例13至24中任一项所述的方法。

示例26包括一种或多种机器可读存储介质，包括存储在其上的多条指令，响应于被执行，该多条指令致使计算设备执行如示例13至24中任一项所述的方法。

示例27包括一种支持流查找表并发的计算设备，该计算设备包括：用于存储包括多个条目和多个候选桶的流查找表的装置，其中，每个候选桶被映射到版本计数器并且包括该多个条目中的一个或多个以便存储映射到网络分组的流的密钥/值对，并且其中，该多个候选桶包括被映射到第一版本计数器的第一候选桶和被映射到第二版本计数器的第二候选桶；用于经由原子指令执行密钥/值对的移位操作以便响应于确定该密钥/值对在该流查找表中更新或者被插入到该流查找表中之一将该密钥/值对从该第一候选桶移动到该第二候选桶的装置；以及用于在该流查找表上执行查找操作的装置。

示例28包括示例27所述的主题，并且其中，用于在该流查找表上执行该查找操作的该装置包括用于在将密钥映射到该多个候选桶中的每一个的集合关联散列流查找表上执行该查找操作的装置。

示例29包括示例27和28中任一项所述的主题，并且其中，用于在该流查找表上执行该查找操作的该装置包括用于在集合关联Cuckoo散列表上执行该查找操作的装置。

示例30包括示例27-29中任一项所述的主题，并且其中，用于在该集合关联散列流查找表上执行该查找操作的该装置包括用于在双向功能、四向关联Cuckoo散列表执行该查找操作的装置。

示例31包括示例27-30中任一项所述的主题，并且其中，用于经由该原子指令执行该密钥/值对的该移位操作的该装置包括用于执行具有小于或等于该多个条目之一的大小的大小的单个高速缓存对齐数据结构的移位操作的装置。

示例32包括示例27-31中任一项所述的主题，并且其中，该第一候选桶是基于应用到流标识符的第一散列函数确定的，而该第二候选桶是基于应用到该流标识符的不同于该第一散列函数的第二散列函数确定的。

示例33包括示例27-32中任一项所述的主题，并且其中，用于执行该密钥/值对的该移位操作的装置包括用于(i)增加该第一和第二版本计数器，(ii)从该第一候选桶移除该密钥/值对，(iii)将该密钥/值写入该第二候选桶，以及(iv)增加该第一和第二版本计数器的装置。

示例34包括示例27-33中任一项所述的主题，并且其中，用于执行该查找操作的装置包括用于(i)使用多于一个散列函数为密钥计算该第一和第二候选桶，(ii)确定该密钥是否在该第一或第二候选桶中的任一个内，以及(iii)响应于确定该密钥在该第一候选桶内从与来自该第一候选桶的该密钥相对应的条目读取值或者响应于确定该密钥在该第二候选桶内从与来自该第二候选桶的该密钥相对应的条目读取该值的装置。

示例35包括示例27-34中任一项所述的主题，并且其中，用于执行该查找操作的装置进一步包括用于(i)响应于确定该密钥不在该第一或第二候选桶中的任一个中而读取该第一和第二版本计数器以及(ii)确定该第一或第二版本计数器之一是否是奇数的装置。

示例36包括示例27-35中任一项所述的主题，并且其中，用于执行该查找操作的装置进一步包括用于响应于确定该第一或第二候选桶中的任一个的第一或第二版本计数器之一是奇数而重新读取第一或第二候选桶中的任一个的第一和第二版本计数器的装置。

示例37包括示例27-36中任一项所述的主题，并且其中，用于执行该查找操作的装置进一步包括用于(i)确定该第一或第二候选桶中的任一个是否包括该密钥以及(ii)响应于确定密钥在第一或第二候选桶中的任一个中返回与该密钥相对应的该值的装置。

示例38包括示例27-37中任一项所述的主题，并且其中，用于执行该查找操作的装置进一步包括用于(i)确定该第一或第二候选桶中的任一个是否包括该密钥以及(ii)响应于确定该密钥在该第一或第二候选桶中的任一个中返回未发现该密钥的指示的装置。