大规模软硬协同哈希表设计与实现
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

紫金山实验室自立课题; 国家自然科学基金面上项目(62176264)


Hardware-software Co-design and Implementation for Large Scale Hash Tables
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    哈希表在网络报文处理, 尤其是带状态的报文处理中发挥着重要作用. 伴随着网络流量的快速增长, 传统软件哈希表难以满足网络性能需求, 而查找是影响哈希表性能的关键之一, 如何提升哈希表的查找速率也一直是一个难点问题. 经研究表明, 现有的网络流量呈现Pareto分布特征, 即存在少数的大流量数据——大象流. 基于当前数据中心广泛采用的软硬协同计算模式, 提出了一种基于DPDK+FPGA的大规模软硬协同哈希表架构. 根据现有网络流量特征, 将流量分成大象流与背景流. 同时也将哈希表分成硬件表与软件表. 在FPGA中构造小规模硬件表, 卸载所有报文的哈希计算, 以及大象流的哈希查找. 在软件中基于DPDK构建大规模软件表, 利用FPGA卸载哈希计算, 加速背景流的查找. 软件拥有所有流信息, 利用采样法识别大象流并将大象流的键值对信息(key-value)更新到FPGA的硬件表中, 以加速软件中大规模软件表的查找速率. 采用Xilinx U200加速卡和通用服务器作为硬件平台, 实现了软硬协同的大规模哈希表, 并利用测试仪构造了符合当前网络特征的流量数据, 以DPDK精确转发为例, 验证了软硬协同哈希表的性能. 结果表明, 在大象流哈希查找完全卸载的情况下, 其性能相较DPDK原有的精确转发提升了64%–75%; 在大象流未卸载的情况下, 其性能提升了5%–48%.

    Abstract:

    Hash tables play an important role in network message processing, especially in the processing of messages with states. With the rapid growth of network traffic, the hash tables of traditional software can hardly meet the needs of network performance, and search is one of the key factors affecting the performance of hash tables. In addition, the improvement in the search rate of hash tables has always been a difficult problem. The research reveals that the existing network traffic presents the characteristics of Pareto distribution, namely that there is a small number of massive traffic data—elephant flow. On the basis of the computing mode of software-hardware co-design used in the current data center, a large-scale hash table architecture with software-hardware co-design is proposed on the basis of DPDK+FPGA. According to the characteristics of existing network traffic, this method divides the traffic into elephant flow and background flow, and meanwhile, the hash table is divided into a hardware table and a software table. A small-scale hardware table is constructed in FPGA to unload the hash calculation of all messages and the hash search of elephant flow. In the software, a large-scale software table is constructed on the basis of DPDK, and the hash calculation is unloaded by FPGA to speed up the search of background flow. As the software has all the flow information, the sampling method is used to identify the elephant flow and update the key-value pair of the elephant flow to the hardware table of FPGA, so as to accelerate the search rate of the large-scale software table in the software. The Xilinx U200 accelerator card and general server are employed as the hardware platform to realize the large-scale hash table with software-hardware co-design, and the traffic data in line with the current network characteristics is constructed by the tester. The accurate forwarding of DPDK is used as an example to verify the performance of the hash table with hardware-software co-design. The results reveal that when the hash search of elephant flow is completely unloaded, its performance is 64%–75% higher than the original accurate forwarding of DPDK; when the elephant flow is not unloaded, its performance is improved by 5%–48%.

    参考文献
    相似文献
    引证文献
引用本文

杨文韬,张士军,张进,唐寅,于洪涛.大规模软硬协同哈希表设计与实现.计算机系统应用,2023,32(1):61-74

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2022-02-21
  • 最后修改日期:2022-03-23
  • 录用日期:
  • 在线发布日期: 2022-10-28
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号