·69· 电信科学 2020 年第 10 期
用伪最大生成树表示哈希关系,以提前判断是否
会出现死循环。Li 等
[16]
存储辅助信息以提高找到
最短数据存储路径的概率,提高了存储访问速度。
Li 等
[17]
通过在哈希表中存储数据的多个副本,降
低了哈希冲突导致的多次寻址开销。Random-
walk
[18]
在冲突时随机选择数据进行替换,并从理
论上保证了多对数级的插入时间。基于 Stash 的
Cuckoo hashing 存储结构
[19-20]
使用小块的额外存
储空间作为 Stash,解决了哈希冲突导致的存储失
败的问题。
最近网络测量存储系统也有许多研究进展。
Narayana 等
[9]
实现了一个基于性能查询原语的网
络性能监控系统(Marple)。Gupta 等
[10]
实现了类
似 Marple 的以查询请求驱动的网络测量系统
(Sonata),但是通过交换机的预处理降低了交换机
上的存储开销和向服务器发送的数据量。Li 等
[21]
实现了一种追踪短时间内全部网络流的高精度轻
量级方案(Flowradar),保证了固定的存储空间开
销。Tammana 等
[22]
结合交换机和服务器的功能特点
实现了一个网络测量和调试系统(Switchpointer),
降低了交换机的存储开销。Fan 等
[23]
实现了一个
面向读密集、高并发型网络数据的存储系统
MemC3。Huang 等
[24]
实现了一个同时满足全精度
和资源高效性的网络测量框架,实现了全网全精
度的网络数据的测量和存储。
这些研究全都基于哈希表进行数据存储,主
要存在以下 4 个问题:基于 Cuckoo hashing 的存
储结构和算法过于复杂,无法部署在基于可编程
交换机的网络测量系统中;当前的网络测量系统
均使用传统单级哈希表作为存储结构,碰撞概率
会随着存储空间使用率的提升而增加,导致无法充
分利用交换机有限的存储资源;Sonata、OmniMon
等研究都没有提供有效的哈希冲突解决方案,导致
额外的带宽消耗;Flowradar、Switchpointer 等研究
具有较强假设或存在求解失败风险,不具有一般性。
针对上述问题,本文提出一种基于多级哈希
的网络存储结构和算法,可高效利用交换机有限
的存储资源,降低冲突发生率,减少额外的网络
带宽开销。
3 基于多级哈希的网络数据存储结构
网络数据存储结构设计分为 3 个步骤:对交
换机架构的分析、存储结构设计和数据替换策略
设计。首先,网络数据存储结构主要部署在交换
机上,需要遵循交换机架构的限制。其次,要充
分考虑交换机串行处理的特点,设计符合交换机
流式处理需求和资源要求的存储结构。最后,考
虑到数据中心网络流量的特点,设计相应的存储
数据更新算法。
3.1 交换机架构的限制
以 PISA(protocol independent switch arch)架
构为例分析现有交换机的局限性。PISA 由可编程
数据分组解析器和统一的匹配动作级(match
action stage,MAS)组成,其架构如图 1 所示。
收到数据分组后,数据分组解析器(parser)首先
将其解析为多组键值对数据并存储在特殊的数组
中。解析完成后,数据分组从第一级串行通过所
有 MAS。每一级包含若干匹配动作表(match
action table,MAT),它们以相同的处理模式处理
数据分组。MAT 首先通过 SRAM 和 TCAM 组成
的混合查找表结构匹配键值对中的关键字信息
(如 IPv4 目的地址),然后根据不同的匹配结果采
取相应的处理操作。比如,根据不同的匹配结果,
可以通过算术逻辑单元(arithmetic logical unit)
修改匹配成功数据分组的 MAC 地址,或者执行
分组丢失操作。完成 MAS 处理后,所有的键值对
以相同的解析模式组装为新的数据分组被发送出
去。PISA 架构从纷繁的数据面处理操作中抽象出
匹配动作处理模型,为数据分组处理提供了灵活
多样的解析、匹配和动作编程模型,赋予了交换
机更加强大的数据处理能力。
PISA 架构在满足百吉比特处理速度和 Tbit/s