面向命名数据网的高性能内核级网络缓存方法.pdf

Computer Engineering and Applications计算机工程与应用2023，59（16）面向命名数据网的高性能内核级网络缓存方法杨济科1，嵩天1，李天龙2，杨雅婷11.北京理工大学 网络空间安全学院，北京 1000812.北京理工大学 计算机学院，北京 100081摘要：命名数据网（named data networking，NDN）是一种以信息为中心的新型网络架构方案，网内缓存是其核心功能之一。现有缓存模块主要以应用级缓存实现为主，存在网络操作效率低、设备兼容性差、部署位置受限等问题。相比于应用级缓存模块，内核级缓存模块可以直接且广泛地部署于通用网络设备上，有助于推动网内缓存技术的规模应用以及NDN网络方案的实际部署。然而，由于NDN网内缓存机制涉及频繁的逐包缓存操作，将网内缓存功能引入内核将会影响内核处理性能。针对这一性能问题，设计并实现了一种内核级缓存方法。该方法维护一个哈希表进行缓存的精确查找，利用NDN名称的结构性，在节点间构建字典树支撑NDN缓存模糊匹配功能。提出使用细粒度的逐槽锁保护缓存查找表，原子操作保护替换队列，将缓存操作多线程并行化。在Linux内核中实现了所提的多线程缓存模块，实验结果表明，所提出的方法可以将缓存模块查找延迟降低至现有方案的一半，并且通过多线程将吞吐量提升至6.785 Mpacket/s。关键词：命名数据网；网内缓存；名称查找；多线程文献标志码：A中图分类号：TP393doi：10.3778/j.issn.1002-8331.2204-0068High-Performance Kernel-Level In-Network Caching for Named Data NetworkingYANG Jike1,SONG Tian1,LI Tianlong2,YANG Yating11.School of Cyberspace Science and Technology,Beijing Institute of Technology,Beijing 100081,China2.School of Computer Science and Technology,Beijing Institute of Technology,Beijing 100081,ChinaAbstract：Named data networking（NDN）is a new information-centric network architecture.In-network caching is oneof core functions in NDN.Current cache modules are mainly deployed in user-level,which brings issues of network opera-tion efficiency,compatibility among devices and limitation of deployment location.Comparing to user-level cache mod-ule,kernel-level cache module can be directly and widely deployed on general net devices,so it can boost the large-scaledeployment of in-network caching and the practical use of NDN solutions.However,due to the frequent per-packet cachingoperations in NDN,introducing cache into kernel may cause performance issues.To solve these performance issues,thispaper designs and implements a kernel-level cache method.The cache method uses a hash table for exact cache lookup andutilizes the naming conventions of NDN to construct a trie for prefix cache lookup.Furthermore,this paper presents anapproach of using fine-grained per-slot locks for lookup table and atomic operations for replacement queues to parallelizecache operations.The multi-thread cache module is implemented in the Linux kernel.The experimental results show thatthe proposed cache scheme reduces the lookup latency by half comparing to current solutions,and boosts the throughputup to 6.785 Mpacket/s via multithreading.Key words：named data networking;in-network caching;named lookup;multi-thread网络、通信与安全基金项目：国家重点研发计划（2020YFB1806000）。作者简介：杨济科（1996），男，硕士研究生，研究方向为信息中心网络、网内缓存；嵩天（1980），男，博士，教授，CCF高级会员，研究方向为网络体系结构、网络安全；李天龙（1997），男，博士研究生，研究方向为新一代互联网体系结构、信息中心网络；杨雅婷（1994），通信作者，女，博士，助理教授，研究方向为新一代互联网体系结构、信息中心网络，E-mail：。收稿日期：2022-04-06修回日期：2022-06-20文章编号：1002-8331（2023）16-0240-082402023，59（16）命名数据网（named data networking，NDN）1是一种以信息为中心的新型网络架构，它将网络从现有基于主机地址的端到端通信模式改为基于数据名称的内容获取模式。2009年Jacobson等人提出了信息中心网络（information-centric networking，ICN）2的基本框架，在其影响下Zhang等人3于2010年成立了NDN项目，对这种新型网络架构展开研究，该项目现已获得学术界和工业界的广泛关注。在NDN中，数据依据信息名称而非主机地址传输。因将传输数据与主机地址解耦，NDN可以在路由器上缓存经过的数据包，从而利用缓存包直接在网络中满足将来的数据请求，不用将请求发送至远端服务器。利用网内缓存，NDN可以降低内容获取延迟并提升网络性能。为了研究便利，现有的NDN缓存模块大多实现并运行在应用层。Mansilha等人4提出了DPDK-HCS，但是该方法依赖数据平面开发套件（data plane developmentkit，DPDK）实现，只能适用于特定的高端网络设备，不能直接运行在通用网络设备中。当前运用最广的NDN实现是NFD（NDN forwarding daemon）5，然而NFD为了研究便利而在应用层实现，未考虑实际运行性能，具有较高的内核空间到用户空间的拷贝与交换代价，存在网络操作效率低的问题。为应对现有应用级缓存实现带来的设备兼容性差、网络操作效率低等问题，内核级NDN缓存模块实现可成为一个突破口，适配通用网络设备，并且避免额外的用户空间与内核空间的信息交换，有助于NDN及其相关技术的进一步演进与部署。内核级缓存需要实现在软中断（Softirq）上下文中，通过锁机制保证多线程并行操作的正确性。内核包处理过程处于软中断上下文中，缓存操作也应处于同一上下文中以避免额外的切换代价。软中断由多个处理器分多线程并行执行，因此内核中的缓存模块需要通过锁机制支持线程间协同，以适应软中断上下文环境，避免共享的数据被同时访问或修改而发生错误。锁机制的并行效率是内核级缓存性能的关键，而锁的结构和查找结构是相关的，因此缓存查找结构也需要针对多线程进行设计。由于NDN缓存需要面对逐兴趣包的查找、逐数据包的插入和替换，每个操作都需要锁的保护进行。假如查找结构没有良好的多线程支持，只能使用粗粒度的锁协同，并发操作会因为锁的竞争而被阻塞，严重影响缓存的性能。如图1所示，缓存查找表上的粗粒度全局锁虽然可以保护并发访问的正确性，但是只允许单个线程同时访问，也就无法充分发挥出多线程缓存的性能。因此，在设计缓存查找数据结构的过程中，除了考虑其本身的查找和更新速度，还需要考虑对多线程并行的适应性。此外，缓存的模糊匹配也为查找结构设计带来了额外的挑战。NDN缓存查找时除精确匹配以外，还使用模糊匹配以更好地利用缓存中的数据。缓存模糊查找使用全子名称匹配（all sub-name matching）将兴趣包与以其名称为前缀的数据包匹配，这一匹配模式需要更复杂的缓存查找结构来支持，目前大多数NDN缓存方案并没有支持这一查找模式6。其不同于广受研究的转发信息表（forwarding information base，FIB）中模糊查找的最长前缀匹配（longest prefix matching），因此，传统面向FIB的名称查找研究并不直接适用于缓存模块。针对上述问题，本文设计了一种高性能的内核级NDN缓存模块，并在Linux内核中实现。该缓存模块支持低延迟的缓存精确匹配和模糊匹配查找，通过高效的缓存操作并行化提高吞吐量。本文的主要贡献集中在以下三点：（1）提出了一种快速缓存查找数据结构，该结构使用哈希表进行精确匹配，并在节点间构建字典树。在字典树上从名称前缀开始进行深度优先搜索实现模糊匹配，可以满足NDN缓存的快速查找需求。（2）针对内核软中断上下文的多线程环境，提出了基于锁和原子操作的并行缓存算法。算法使用逐槽锁保护缓存查找表，运用原子指针管理替换队列，从而实现高效并行缓存操作，显著提升缓存吞吐量。（3）为验证所提方法的真实有效性，在Linux内核中实现了上述缓存方法。实验结果验证了本文方案的有效性。1相关工作1.1NDN名称查找名称查找是缓存模块的关键组成，缓存模块需要通过兴趣名找到缓存中与兴趣匹配的数据包。现有查找方法可以分为两类：基于字典树的方法和基于哈希的方法。基于字典树的查找方法将名称存储在字典树结构中，可以压缩查找表存储空间。NCE7通过名称编码构建了一个内存高效的字典树。Song等人8设计了一个基于Patricia树的方法来解决10亿级的名称前缀查找。然而，基于字典树的查找方法性能与名称长度密切相关，且更新操作繁琐，因此更适用于转发信息表而非缓存查找。与之相对的，基于哈希的查找方法更适合长名称匹配并支持高频更新。Varvello等人9使用开放地址哈希表支持10 Gbit/s转发速率下的待定兴趣表（pending数据包数据包兴趣包兴趣包线程1线程2线程3线程4竞争锁!缓存查找表缓存替换队列数据存储区共享的缓存空间图1多线程缓存的锁竞争问题Fig.1Lock contention in multi-thread caching杨济科，等：面向命名数据网的高性能内核级网络缓存方法241Computer Engineering and Applications计算机工程与应用2023，59（16）interest table，PIT）操作。Huang等人10提出使用计数二分搜索在哈希表上实现最长前缀匹配，同时还可以支持快速的更新操作。Wang等人11设计了一个用于FIB查找的两阶段布隆过滤器NameFilter，它在第一阶段确定匹配的名称长度，第二阶段找到转发的出口。然而，上述基于哈希的查找方法实现的查找模式只有精确匹配和最长前缀匹配，而NDN需要缓存查找除精确匹配外，还支持全子名称匹配，将兴趣与包含其名称为前缀的数据包进行匹配，使得用户可以通过缓存尽快发现任意匹配的数据，并构造接下来请求的兴趣名6。这一模式目前没有被基于哈希的查找方法所支持。1.2高性能网内缓存实现目前关于NDN缓存的研究，更多聚焦于提升命中率的缓存策略，而关于网内缓存自身速度的研究并不多。NFD5使用C+标准库中的set实现了基于红黑树排序的缓存。Pan等人12利用了到达时间接近的兴趣包名称连续性，实现了位置感知跳表（locality-aware skiplist），以通过上一个被访问的具有相同前缀的包，快速找到当前的目标，而非从表头开始查找。Qazi等人13称B树时间复杂度低于跳表，因此使用B树对缓存构建两级索引，分别为文件树和块树。Zhang等人14使用基于压缩字典树的布隆过滤器快速过滤缓存中不存在的查找请求，降低了低命中率时的查找延迟。Khatouni等人15给出了一个CCN路由器的内核级实现CCN-par，使用线性哈希表索引缓存中的数据包，并用一个工作队列处理到达的网络包。然而这些方法未考虑并行化，限制了其通过多线程进一步提升吞吐量。而现有的并行缓存方法主要致力于将包分给不同的缓存线程，每个缓存线程只维护自己独占的缓存数据结构以避免协同问题。So等人16使用基本的链式哈希表做索引，将包的全名称哈希值作为线程分配依据，但是这样难以实现缓存的全子名称匹配。Mansilha等人4提出将同一前缀下的包分配给同一个处理器，以利用同一前缀下兴趣接连到达的规律，但是可能导致处理器间负载分配不均衡。NDN-DPDK17在发出和收到的包上附加额外标记，以将模糊匹配成功发回的包分配给原本负责处理请求的线程，需要路径上所有设备都对网络包做额外修改，而且仍然不完全支持缓存的模糊匹配。除此之外，上述的多线程方法使用了针对特定硬件的用户层网络驱动程序，也意味着它们无法移植进内核。就目前所知，如何在内核中实现并行缓存方法仍然是一个待解决的问题。2内核级缓存数据结构本文设计了一种多线程内核级NDN缓存模块，分为缓存查找表、替换队列和数据存储区三部分，结构如图2所示。缓存查找表和替换队列两个结构共同管理数据存储区中的数据。其中，缓存查找表由用于精确匹配的哈希表和用于模糊匹配的字典树共同组成。在哈希表上，一组细粒度的逐槽锁保证在内核软中断环境中缓存查找表上并行的查找和更新操作能够正确进行，同时也尽可能减少竞争锁造成的阻塞。替换队列包括一个先入先出的循环队列和原子性的队首队尾指针，同样保证了并行访问的正确性。缓存模块的调用处于内核软中断的包处理过程中。当NDN包到达缓存节点，网卡将包拷贝至内存后调用软中断唤醒随机处理器上的软中断线程执行内核包处理函数，包处理函数解析NDN包后，若为数据包，则调用缓存模块的插入函数，将包在内存中的地址传递给缓存模块进行缓存。缓存模块根据地址将数据拷贝至数据存储区，然后在逐槽锁的保护下将其插入缓存查找表，并使用原子操作将其置入替换队列。当缓存已被填满时触发替换操作，将替换队列队首的包替换出，并从查找表中删除。缓存处理完成后，软中断线程继续包转发操作。若解析为兴趣包，内核软中断线程调用缓存模块的查找函数，并传递兴趣包的名称等参数，缓存根据名称在查找表进行精确或模糊匹配，如果找到匹配的结果，则将数据存储区中对应数据写入网卡发送队列，向兴趣来源发回数据包。2.1缓存查找结构为了同时满足 NDN 缓存对长名称做快速精确匹配、对名称前缀做模糊匹配和高频更新的需求，本文提出一种将哈希表和字典树结合的混合数据结构用于缓存查找，结合两种结构的优势，抵消相应不足。两种结构的优势和不足分述如下：基于哈希表的结构可以对长名称进行快速的精确匹配查找，并支持多线存储数据存储区 字典树索引节点替换队列队首指针队尾指针循环队列缓存查找表数据数据包删除数据缓存模块删除兴趣包逐槽锁哈希表312312插入（原子性数据）图2缓存模块总体结构图Fig.2Overall diagram of cache module2422023，59（16）程环境下的高频更新。但是使用哈希表实现缓存的模糊匹配需要对缓存中每个数据名的每个前缀额外建立一次索引，会造成高额的内存资源浪费和额外更新代价。基于字典树的查找结构天然支持名称模糊匹配，但是其查找时内存访问次数与名称长度相关，在查找长名称时较慢，且其更新操作难以并行化实现。本文将哈希表和字典树结合构成了缓存查找表，利用了哈希表快速精确匹配的优势和字典树易于实现名称模糊匹配的特性。图3展示了缓存查找表结构图，其基本结构是一个链地址法的哈希表，处于同一哈希槽的节点组成链表相连，并且节点间按名称用孩子兄弟表示法构成组件级字典树。针对长名称的缓存精确匹配可以通过哈希表查找快速完成，仅需一次名称哈希和一次哈希表查找，如图3中的查找1所示。假如对输入名称进行哈希查找的结果不包含数据而只是一个前缀，则缓存从该前缀节点开始做字典树上的深度优先搜索，即可找到模糊匹配的数据，如图3中的查找2所示。在缓存数据时，先将数据名称插入哈希表，再通过哈希表查找父节点（名称比其短一个组件的），将其连接在父节点下。2.2并行查找机制内核软中断环境中的缓存操作会被多个处理器并行地执行，这在提升缓存吞吐量的同时也带来了多线程协同问题。在多个软中断线程同时访问共享的缓存查找表过程中，可能由于操作冲突造成以下问题：（1）重复插入。例如当“/a/1”和“/a/2”两个数据包同时到达路由器，并被分别交给两个内核软中断线程同时执行缓存操作，将它们插入缓存查找表时，两个线程均发现表中不存在所需前缀“/a”，因此两个线程各自向表中插入一次“/a”前缀节点。导致表中存在两个“/a”节点，并将本属于同一子树的“/a/1”和“/a/2”连接到不同的前缀节点下。为了避免重复插入，需要在每个线程执行查询-插入操作的过程中，阻止其他线程进行相同名称的插入操作。（2）无效插入。当两个线程同时将节点插入同一链表时，它们都将自身插入节点的下一节点指向当前的表头节点，并将链表头指针指向插入节点。但是链表头指针只能指向两个插入节点之一，实际上另一个节点并没有出现在链表中，也就无法被缓存找到。为了避免无效插入，需要阻止多个线程同时修改同一链表。在内核中，并行协同问题可以通过加锁进行线程同步解决，设计高效的锁机制是提升缓存性能的关键。对内核级缓存而言，并行协同问题最基本的解决方法是使用一个全局的读写锁保护整个缓存查找结构，包括哈希表和字典树，每个缓存线程在操作查找表之前需要先获取锁，结束操作后释放锁。但是这种粗粒度的锁只允许单一线程同时访问，很有可能成为系统的瓶颈。实际上本文提出的缓存查找结构中的哈希表部分允许多线程同时访问，因此可以缩小锁的保护范围，并对其进行拆分。在本文的设计中，为了发挥查找结构中哈希表允许并行更新的特性，将锁的范围从既保护哈希表又保护字典树，缩小到只保护哈希表，并在哈希表上将一个全局锁分解成对每个哈希槽各设置一个独立的细粒度锁。这种设计使得访问查找表虽然仍需获取一次锁，但是访问不同哈希槽的操作可以同时进行。而因为哈希表上不同的访问通常是发生在不同哈希槽上，所以各个线程间不易相互阻塞。如图4所示，三个处理器上的软中断子线程分别取得了三个相互独立的锁，可以同时在缓存查找表上进行插入和删除操作（操作1-x与操作2-x和3-x可以同时发生）。缩小范围并分解后的逐槽锁仍可以保护缓存操作的正确性。对于重复插入问题，因为精确匹配通过哈希表完成，而且同名称的节点会被插入到同一哈希槽中，字典树.root/A/B/A/a/B/a/B/a/1/B/a/2/B/a/3.哈希槽/A/a/3查找1：/B/a/2查找2：/B 在哈希表中精确匹配/B 获得模糊匹配结果在子树中DFS查找数据在哈希表中直接获得精确匹配结果（1-a）（2-c）（2-a）（2-b）哈希表图3缓存查找数据结构Fig.3Structure of cache lookup table.root/A/B/A/a/B/a/B/a/1/B/a/2/B/a/3/A/a/3线程3：插入/B/a/4线程2：删除/B/a/1线程1：删除/A/a/3逐槽锁./B/a/4.插入到哈希表中从哈希表中删除从字典树中删除插入到字典树中从哈希表中删除（1-a&2-a&3-a：分别获取对应哈希槽的锁）（3-a）（2-a）（1-a）（3-c）（3-c）（2-b）（1-b）（1-c）（3-b）图4逐槽锁保护的查找表与表上的并行操作Fig.4Parallel operations in lookup table with protectionof per-slot locks杨济科，等：面向命名数据网的高性能内核级网络缓存方法243Computer Engineering and Applications计算机工程与应用2023，59（16）所以缩小范围后的逐槽锁仍然可以阻止同时向表中插入同名节点，避免重复插入问题。对于无效插入问题，逐槽锁可以保护哈希表上的链表不被同时修改，确保了精确匹配的正确性，而字典树上即便发生无效插入，无效的节点仍然可以通过哈希表被定位，且使它无效的节点仍然可以代替它满足模糊匹配的需求。2.3并行替换机制内核级缓存的替换队列同样会被并行访问，在替换队列上的操作也需要考虑多线程协同问题以及使用全局锁的性能影响。不过与查找表不同的是，先入先出的替换队列可以通过原子操作非阻塞地并行化。原子操作是现代多核处理器向内核提供的一种特殊指令，它可以在一次硬件操作内完成，而不用考虑处理器之间的协同问题。因为原子操作是非阻塞的，所以使用原子操作协同的程序可以并行执行。并行非阻塞先入先出队列可以通过一个循环数组和头尾两个原子性的指针实现，如图2中的替换队列部分所示。尾指针指向循环数组中将插入的位置，而头指针指向将被替换出的位置。在向队列内插入或从队列中逐出元素时，每个线程原子性地对头尾指针做读取并自增，然后在得到的位置进行插入或删除操作。指针的原子性保证了得到位置的正确，而之后的操作便与单线程相同，不需要再考虑协同问题。3内核级缓存操作本章描述并行化后内核级缓存的插入、查找和替换三种操作的算法，并对它们的复杂度进行分析。3.1插入操作使用逐槽锁和原子操作并行化后的缓存插入操作如算法1所示。首先，缓存线程计算名称哈希，并获取对应哈希槽的锁，然后在哈希表中插入节点，如图4中3-a与3-b两步所示。在不同槽上进行的操作由于使用不同锁，可以不受阻塞地同时进行。然后，缓存线程将节点连接到字典树中，如图4中3-c所示。尽管这一步操作并没有被锁保护，可能导致字典树的兄弟链表上出现无效插入，但是未来的模糊匹配仍然会被后插入的节点满足，缓存操作仍然可以正确执行。最终，缓存线程通过原子操作找到替换队列的队尾，然后将节点插入到循环队列中。算法1 cache_insert（content）1.hash_index=hash（content.name）2.acquire_write_lock（lockshash_index）3.if content not in hash_tablehash_index then4.entry=newindex_entry（content）5.hash_tablehash_index.add（entry）6.release_write_lock（lockshash_index）7.parent=lookup（parent_name（content.name）8.entry.sibling=parent.latest_child9.parent.latest_child=entry10.bucket=atomic_get_and_inc（rear）11.FIFObucket.index_entry=entry12.else13.release_write_lock（lockshash_index）14.endif插入操作的时间复杂度是O(n+m)，其中n为数据名称长度，m为哈希表中对应槽中节点数量。m在理想情况下等于哈希表负载因子，在缓存大小恒定时为常数，故总时间复杂度为O(n)。并且因为名称哈希只需要一次内存访问，所以总共的访存次数仅为O(1)。3.2查找操作缓存的查找操作如算法2所示。查询过程首先是从哈希表中查找目标名称，哈希表查询计算名称的哈希值，然后在对应哈希槽的链表上查找与目标名称相同的节点。假如哈希查找命中且结果包含数据包，则将其作为精确匹配命中结果返回。如果哈希查找命中，但是结果只是一个前缀而不包含数据，则对该前缀节点在字典树上的子树进行深度优先搜索，并且将遍历到的第一个包含数据的节点作为模糊匹配的结果返回，如图3中的2-b与2-c所示。算法2 cache_lookup（name）1.hash_index=hash（name）2.acquire_read_lock（lockshash_index）3.for each entry in hash_tablehash_index do4.if entry.name=name then5.result=entry6.break7.endif8.endfor9.release_read_lock（lockshash_index）10.if not result.content then11.result=dfs_content_in_subtree（result）12.endif13.return result.content由于缓存基于哈希表进行精确匹配，缓存查找的速度基本不受名称长度影响。当目标名称长度增加时，单次查询所需要比较的节点数仍然只与哈希表中的名称数量有关，即查找的内存访问次数不随名称长度改变。名称长度只影响哈希值计算和匹配成功时的名称比较这两次操作的耗时，在整体查询延迟中占比较低。因此，该算法可以适应NDN缓存查找长名称的需求。3.3替换操作缓存替换操作如算法3所示。首先，通过原子操作对队列首指针进行读取并自增，得到需要换出的节点位2442023，59（16）置。然后，在对应哈希槽的锁保护下将节点从哈希表中删除（如图4中1-b与2-b所示）。只有在被删除节点是其父节点的最后一个子节点时，才将其从字典树中删除（如图4中1-c所示）。最终，释放节点存储的数据并删除节点。替换操作时间复杂度为O(1)。算法3 cache_evict（）1.entry=FIFOatomic_get_and_inc（front）2.hash_index=entry.hash_index3.acquire_write_lock（lockshash_index）4.remove_from_hash_table（entry）5.release_write_lock（lockshash_index）6.if entry.parent.latest_child=entry then7./*entry is the only child for its parent*/8.delete（entry.parent）9.endif10.free（entry.content）4实验与结果分析4.1实验设置为了验证本文所提缓存方法的可用性与性能，在Linux 4.14版本内核中实现，并修改内核的网络包处理流程，使其支持NDN包转发。之后将修改后的内核与缓存模块部署在一台使用i5-7267U处理器，有8 GB内存和6个网络接口的可编程路由器上。为了生成NDN流量，将2台服务器与4个树莓派分别配置为发布者和消费者，并且用以太网线将它们直接与路由器连接，如图5所示。每个发布者发布50 000个文件，其名称由Alexa热门站点数据集生成，每个文件包含1、10、100或1 000个1 KB大小的内容块。消费者在实验中向发布者发送兴趣包以获取文件，文件的流行度分布遵循参数=0.8的Zipf分布。消费者在请求时，有1%的概率使用名称前缀做模糊匹配获取文件中的任意一块，其余情况按顺序取文件的所有内容块。每组实验持续10 min，消费者每秒发出40 000个兴趣包。为了在相同环境下与 NFD 和字典树进行性能对比，将数据结构与算法在内核中实现。此外，在第4.3节中将本文方法与使用跳表的单线程缓存Locality-AwareSkip List12，使用线性哈希表的单线程内核级缓存CCN-par15，以及两种基于DPDK和内部包分发实现的用户级多线程缓存方法 DPDK-HCS4和 NDN-DPDK17进行了性能对比。4.2实验结果4.2.1兴趣处理延迟图6展示了本文方法与NFD和字典树在平均兴趣处理延迟方面的比较。横轴为缓存大小，从250 MB到4 GB，即为250 000至4 000 000个缓存的内容块。本文方法在缓存大小为 4 GB 时查找延迟为 332 ns，相比NFD有约一倍的速度提升。根据结果可以看出，本文方法的查找速度随缓存大小并无明显改变。与之相对的是，NFD在缓存大小增加时，查找耗时延长，这是因为红黑树深度随着节点数量增加，在查找时需要更多访存次数。而哈希表可以通过增加哈希槽的数量来维持恒定的负载因子，保证查找的平均访存次数不变。此外，字典树虽然与本文方法具有相同的时间复杂度，但是因为内存访问次数更多，所以需要更长的查询时间。4.2.2数据处理延迟数据处理延迟即缓存模块处理到达数据包所需要的时间，其操作包含对旧数据包的一次替换和删除，以及新数据包的拷贝和插入。三种方法的平均数据处理延迟如图 7 所示。本文方法的平均处理延迟为 800828 ns，可以看出本文方法在数据处理延迟上同样低于NFD与字典树。原因是本文方法除了访存次数少以外，还将锁竞争分散在了不同哈希槽上，而NFD与字典树需要竞争单一的全局锁，因此在获取锁上需要花费更长时间。4.2.3缓存吞吐量在前文的实验环境中，缓存吞吐量被消费者请求速率限制为 160 kpacket/s。为了测试出缓存的极限吞吐量，在一台使用两颗E5-2620处理器服务器上运行本地回环的发布者与消费者进行实验。在该环境中，缓存操消费者消费者消费者消费者发布者发布者缓存路由器每个消费者每秒发送40 000个请求图5实验环境网络拓扑Fig.5Network topology in experiment environment0.250.5124缓存大小/GB8006004002000兴趣处理延迟/nsNFD字典树本文方法图6平均兴趣处理延迟Fig.6Average interest processing latency杨济科，等：面向命名数据网的高性能内核级网络缓存方法245Computer Engineering and Applications计算机工程与应用2023，59（16）作被本地消费者的请求和发布者的回应所驱动，因此避免了消费者硬件带来的吞吐量限制。在实验中，缓存大小设置为4 GB，消费者请求特征与前文相同。图8展示了本文提出的并行方法与使用全局锁的吞吐量比较，在统计吞吐量时只计数据包。本文方法在16 线程下达到 6.785 Mpacket/s 的缓存吞吐量，即在1.5 KB数据包大小下可以支持81.42 Gbit/s的数据传输速率。与之相对的是，全局锁几乎无法通过多核并行提升速度。全局锁下的缓存吞吐量在2线程时达到极限的1.544 Mpacket/s，随后因为锁过度竞争导致的频繁上下文切换而降低。NFD和字典树因其并行化使用全局锁，吞吐量同样会受到限制。4.3比较与讨论对本文方法与其他高性能网内缓存方法的性能在表1中进行了对比：CCN-par所用的单线程任务队列，限制了其处理速率；Locality-Aware Skip List实现了较快的查找速度，但是无法在并行条件下支持更新，限制了其真实环境中的吞吐量；DPDK-HCS与NDN-DPDK通过多线程达到了可观的吞吐量，但是其内部包转发的线程间通信带来了较高的处理延迟。本文方法在处理延迟和吞吐量上相较现有方法均有明显提高，主要是因为本文方法的核心操作依赖哈希表，而哈希表查找访存次数更少，即降低了处理延迟。同时哈希表和先入先出队列可以通过逐槽锁和原子操作实现高效的并行化，以通过多线程并行达到高吞吐量。虽然在内存占用上，哈希表有更多额外开销，但是其相较于缓存中存储的数据包仍是可忽略的。5结束语为了提升NDN网内缓存的处理性能，本文提出了一种高性能内核级缓存方法。本文方法使用哈希表实现快速的精确匹配查找，同时利用哈希查找结果进行字典树搜索支持模糊匹配，并且实现高效并行操作以通过多线程提高缓存吞吐量。实验证明，本文方法在降低缓存处理延迟至现有方法一半的同时，达到了6.785 Mpacket/s的高缓存吞吐量。此外，这种内核级的方法不受平台限制，硬件兼容性强，有利于推进NDN网内缓存的实际应用部署。在未来的研究中，首先，将迁移本文方法至用户空间实现，与本文的内核空间实现进行性能对比，明确内核级缓存的优势与劣势；其次，为了支持在内存中索引TB规模的多级缓存，将优化缓存查找结构内存消耗；之后，将定位内存-硬盘的多级缓存中的性能问题并加以改进；最后，将使用真实NDN流量在实际环境中对缓存方法进行测试。参考文献：1 ZHANG L，AFANASYEV A，BURKE J，et al.Named datanetworkingJ.ACM SIGCOMM Computer CommunicationReview，2014，44（3）：66-73.2 JACOBSON V，SMETTERS D K，THORNTON J D，et al.Networking named contentC/Proceedings of the 5th Inter-national Conference on Emerging Networking Experimentsand Technologies，Rome，Dec 1-4，2009.New York：ACM，2009：1-12.3 ZHANG L，ESTRIN D，BURKE J，et al.Named data net-working（NDN）project：NDN-0001R/OL.（2010-10-31）2022-04-06.https：/named- MANSILHA R B，SAINO L，BARCELLOS M P，et al.Hier-124681216线程数86420吞吐量/（Mpacket/s）本文方法全局锁图8多线程吞吐量Fig.8Multi-thread throughput0.250.5124缓存大小/GB1 5001 0005000数据处理延迟/nsNFD字典树本文方法图7平均数据处理延迟Fig.7Average data processing latency方法CCN-par15DPDK-HCS4Locality-Aware Skip List12NDN-DPDK17本文方法兴趣处理/s5.007.400.5690.000.33数据处理/s43.0042.100.83吞吐量/（Mpacket/s）0.0500.5001.7961.8006.785表1处理时间与吞吐量比较Table 1Comparison inprocessingtimeandthroughput2462023，59（16）archical content stores in high-speed ICN routers：emula-tion and prototype implementationC/Proceedings of the2nd ACM Conference on Information-Centric Network-ing，2015：59-68.5 AFANASYEV A，SHI J，ZHANG B，et al.NFD developer sguide：NDN-0021R/OL.（2021-08-01）2022-0