一种面向高速数据流的通用流级过滤方法

：
1.本发明涉及高速数据流(如网络流)中的大小流分离，具体涉及一种面向高速数据流的通用流级过滤方法。


背景技术：

2.对高速数据流的实时处理一直以来都是一个热门的研究课题，也是分析现实世界中如网络流量、谷歌搜索关键词以及推特推文这样规模庞大且迅速的数据流的基本任务。不失一般性地，数据流可以被定义为一串连续不断的数据项集合，其中的每个数据项《f,e,t》都带有表示流归属关系的流标签f、用于标识的元素标签e和表示到达时间的时间窗口索引t。通常，数据流处理任务有三种典型的测量目标：流大小(带有相同流标签的数据项的数量)、流基数(带有相同流标签的独立元素的数量)和流持续性(流在不同时间窗口出现的数量)。测量结果可为诸如web缓存、网络管理、异常检测等应用提供必要决策依据，因此数据流处理是实现应用多样化不可或缺的环节。
3.尽管已有诸多数据流处理相关的研究被提出，现有的工作依旧存在很多不足之处。一方面，受数据流流速以及存储资源的限制，现有数据流处理机制在吞吐性能和测量准确性上仍然存在较大的改进空间；另一方面，实际场景的数据流通常存在显著的偏斜性，这使得现有数据流处理机制未能充分地利用有限的片上存储空间。因此，部分工作如cold filter和loglog filter提出通过一个过滤结构按照流大小对数据流中的小流过滤，并将通过的大流对应的数据项传至后续的数据流测量模块，实现数据流中大小流的分离测量。然而，这些过滤结构仅能够在以流大小为测量目标的数据流处理任务下实现大小流的分离，未不能在更加多变的测量目标下实现一种通用流级过滤结构设计。
4.为了解决上述流级过滤结构设计中存在的问题，本发明旨在设计一种面向高速数据流的通用流级过滤结构，能够灵活地根据不同的测量目标(如流的大小测量，基数测量，以及持续性测量)有效实现数据流中大流和小流的分离。


技术实现要素：

5.鉴于上述问题，本发明提供了一种面向高速数据流的通用流级过滤方法，包括实时编码过滤和阈值估计两部分，
6.所述实时编码过滤部分，根据当前测量周期下的测量目标对流的统计信息采用不同的编码方式，用于过滤分离数据流中的大、小流；
7.所述阈值估计部分，用于获得大流初始到达时为了集齐赠券而未能通过过滤结构的部分数据项的统计信息。
8.进一步的，所述实时编码过滤部分，包括，
9.设立用于分离数据流大、小流的过滤结构；
10.在测量周期内，首先，将到达过滤结构的数据项根据其流标签，通过流-过滤单元映射函数随机映射到过滤结构的任意过滤单元中；
11.其次，根据当前周期的测量目标选择对应的数据项-比特位映射编码函数，将该数据项映射到过滤器单元中的比特位并置位；
12.之后，根据数据项获得的比特位的置位情况，判断该数据项是否通过过滤结构，将通过过滤结构的大流作为数据流测量任务中主要被关注的对象。
13.进一步的，所述过滤结构包含了m个过滤单元的数组r，每个过滤器单元包含l个比特位；在每个测量周期的初始时刻过滤结构内的所有比特位的值均设置为0；l表示赠券类型数量的预设值，每个过滤器单元的l个比特位与需要集齐的l种赠券类型相关对应。
14.进一步的，所述流-过滤单元映射函数hm(
·
)通过哈希计算得到：hm(f)＝h
′
(f)mod m，且h
′
(
·
)为一个均匀分布的独立哈希函数。
15.进一步的，当到达的数据项使对应流的实际测量结果发生变化时，存在一个预设的概率p(0＜p≤1/l)使得该数据项能够以l
×
p的概率在被映射到的过滤器单元r[hm(f)]中将任意一个比特位置1，在此过程中被映射单元的每一个比特位被置1的概率都是p；其中对于在测量周期内设定的完全不同的测量目标，包括流的大小测量，基数测量，以及持续性测量，数据项在过滤器单元的概率置位存在不同的计算方式：
[0016]
1)当测量目标为流大小测量时，所述数据项-比特位映射编码函数hc＝h
′c；具体的，
[0017]
在以流大小为测量目标的测量周期下，当任意数据项《f，e，t》的到达时，与流存在映射关系的过滤器单元r[hm(f)]的第h
′c(f，e，t)个比特位将被置1，其中h
′c(f，e，t)是基于流大小测量目标的赠券抽取函数，计算方式为：
[0018][0019]
其中，r是当一个数据项到达时，在[0，1)之间随机生成的数值；
[0020]
2)当测量目标为流基数测量时，所述数据项-比特位映射编码函数hc＝h
″c；具体的，
[0021]
在以流基数为测量目标的测量周期下，当任意数据项《f，e，t》的到达时，与流存在映射关系的过滤器单元r[hm(f)]的第h
″c(f，e，t)个比特位将被置1，其中h
″c(f，e，t)是基于流基数测量目标的赠券抽取函数，计算方式为：
[0022][0023]
其中，h(
·
)为一个值域范围在[0，x)之间的均匀分布的独立哈希函数，符号为异或运算符；
[0024]
3)当测量目标为流持续性测量时，所述数据项-比特位映射编码函数hc＝h
″′c，具体的，
[0025]
在以流持续性为测量目标的测量周期下，当任意数据项《f，e，t》的到达时，与流存在映射关系的过滤器单元r[hm(f)]的第h
″′c(f，e，t)个比特位将被置1，其中h
″′c(f，e，t)是基于流持续性测量目标的赠券抽取函数，计算方式为：
[0026]
[0027]
其中，h(
·
)为一个值域范围在[0，x)之间的均匀分布的独立哈希函数，符号为异或运算符。
[0028]
进一步的，数据项是否通过过滤结构依据如下，
[0029]
获取到达的数据项《f，e，t》被哈希映射到的过滤器单元r[hm(f)]中各比特位的置位情况，当且仅当过滤器单元中的比特位都被置为1时，允许数据项《f，e，t》通过过滤结构；否则，数据项被阻塞。
[0030]
进一步的，所述阈值估计部分，包括，
[0031]
(1)通过概率推导分析过滤结构中的哈希冲突；
[0032]
(2)对单个过滤单元的编码特性进行概率分析，得到任意一个过滤单元上被映射了若干数据项(或非重复数据项)时过滤单元中的比特位都被置为1的概率，以及任意一个过滤单元上被映射了若干数据项或非重复数据项时过滤单元中的比特位刚好都被置为1的概率；
[0033]
(3)基于上述概率分析结果进一步推导得出任意通过过滤结构的流所消耗的数据项或非重复数据项规模的期望。
[0034]
进一步的，过滤结构内流间的哈希冲突通过如下步骤分析：
[0035]
(1.1)用公式(1)计算任意某个过滤器单元r[i]被映射的流的数量为ri的概率；
[0036][0037]
(1.2)用公式(2)计算当某个过滤器单元r[i]中存在ri条冲突流时，该过滤单元中冲突流的实际测量结果的和为ni的概率；
[0038][0039]
(1.3)用公式(3)计算过滤器单元r[i]中各冲突流的实际测量结果的和为ni的概率；
[0040][0041]
其中，m为高速数据流中流的数量，nf为数据流中某条流f的实际测量结果；用符号ri表示某个过滤器单元r[i]实际被映射的流的数量；符号ni则与当前周期下的测量目标项关联，表示了该过滤单元中多条冲突流各自实际测量结果的和。
[0042]
进一步的，对单个过滤单元特性进行概率分析具体如下：
[0043]
(2.1)计算某个过滤器单元r[i]中到达了实际测量结果之和为ni的数据项时，过滤器单元r[i]中有li个比特位被置为1的概率，计算方式为公式(4)；
[0044][0045]
(2.2)用符号表示过滤器单元r[i]中的比特位都被置为1时，该单元所需要的最小规模数据项的实际测量结果；根据步骤(2.1)的计算所得，推导过滤器单元r[i]中到达了
实际测量结果之和为的数据项时，过滤器单元r[i]中刚好所有比特位都被置为1的概率，计算方式为公式(5)；
[0046][0047]
其中，用符号li表示过滤器单元r[i]中被置1的比特位的数量。
[0048]
进一步的，通过概率推导得出任意通过过滤结构的流所消耗的数据项规模的期望，具体如下：
[0049]
(3.1)根据公式(3)和公式(4)，可以推导得到任意过滤器单元的所有比特位都被置为了1的概率，计算方式为公式(6)；
[0050][0051]
(3.2)根据公式(3)、公式(5)和公式(6)的计算所得，可以得到任意过滤器单元仅消耗了规模的数据项就将所有比特位都被置为了1的概率，计算方式为公式(7)；
[0052][0053]
(3.3)最终，通过计算公式(7)所得概率的期望可以得到任意通过过滤结构的流为集齐赠券所消耗数据项规模的期望，有公式(8)；
[0054][0055]
本发明提供的一种面向高速数据流的通用流级过滤结构，能够灵活地根据不同的测量目标(如流的大小测量，基数测量，以及持续性测量)有效实现数据流中大流和小流的分离。
附图说明：
[0056]
图1是实时编码过滤流程图；
[0057]
图2是阈值估计流程图。
具体实施方式：
[0058]
为了使本发明的目的、技术方案及优点，更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。
[0059]
参考图1-2，本发明提出的面向高速数据流的通用流级过滤结构，具体实现主要包含实时编码过滤和阈值估计两部分。所述实时编码过滤部分，用于获得通过过滤结构的大流；所述阈值估计部分用于获得大流初始到达时为了集齐赠券而未能通过过滤结构的部分数据项。
[0060]
其中，实时编码过滤部分在过滤器结构的每一个记录单元引入了赠券收集问题模型，并将每一个单元中的编码过滤过程视为赠券收集过程。每一条到达的流必须在其映射的过滤器单元中消耗一定数量的数据项来收集所有类型的赠券。在此情形下，数据流中的
大流有充足的数据项去集齐所有类型的赠券并通过过滤结构，而小流则会因为未能集齐赠券而被阻塞在过滤环节，这使得本发明提出的流级过滤结构能够灵活地根据不同的测量目标(如流的大小测量，基数测量，以及持续性测量)有效实现数据流中大流和小流的分离。
[0061]
所述实时编码过滤部分，具体的实现方式如下：
[0062]
1)设立用于分离数据流大小流的过滤结构，所述结构是一个包含了m个过滤单元的数组r，每个过滤器单元包含l个比特位。在每个测量周期的初始时刻过滤结构内的所有比特位的值均设置为0。需要说明的是，l是用来表示赠券类型数量的预设值，每个过滤器单元的l个比特位与需要集齐的l种赠券类型相关对应。
[0063]
2)在一个测量周期内，某个到达过滤结构的数据项《f，e，t》会被映射到过滤器单元r[hm(f)]，hm(
·
)作为流与过滤器单元间的映射函数通过哈希计算得到：hm(f)＝h
′
(f)mod m，且h
′
(
·
)一个均匀分布的独立哈希函数。当到达的数据项使对应流的实际测量结果发生变化时，存在一个预设的概率p(0＜p≤1/l)使得该数据项能够以l
×
p的概率在被映射到的过滤器单元r[hm(f)]中将任意一个比特位置1，在此过程中被映射单元的每一个比特位被置1的概率都是p。而为了实现一个通用的流级过滤结构，对于在测量周期内设定的完全不同的测量目标(如流的大小测量，基数测量，以及持续性测量)，数据项在过滤器单元的概率置位存在不同的计算方式。
[0064]
2.1)当测量目标为流大小测量时，所述数据项-比特位映射编码函数hc＝h
′c；具体的，在以流大小为测量目标的测量周期下，当任意数据项《f，e，t》的到达时，与流存在映射关系的过滤器单元r[hm(f)]的第h
′c(f，e，t)个比特位将被置1，其中h
′c(f，e，t)是基于流大小测量目标的赠券抽取函数，计算方式为：
[0065][0066]
r是当一个数据项到达时在[0，1)之间随机生成的数值。
[0067]
2.2)当测量目标为流基数测量时，所述数据项-比特位映射编码函数hc＝h
″c；具体的，在以流基数为测量目标的测量周期下，当任意数据项《f，e，t》的到达时，与流存在映射关系的过滤器单元r[hm(f)]的第h
″c(f，e，t)个比特位将被置1，其中h
″c(f，e，t)是基于流基数测量目标的赠券抽取函数，计算方式为：
[0068][0069]
h(
·
)一个值域范围在[0，x)之间的均匀分布的独立哈希函数，符号为异或运算符。
[0070]
2.3)当测量目标为流持续性测量时，所述数据项-比特位映射编码函数hc＝h
″′c，具体的，在以流持续性为测量目标的测量周期下，当任意数据项《f，e，t》的到达时，与流存在映射关系的过滤器单元r[hm(f)]的第h
″′c(f，e，t)个比特位将被置1，其中h
″′c(f，e，t)是基于流持续性测量目标的赠券抽取函数，计算方式为：
[0071][0072]
h(
·
)一个值域范围在[0，x)之间的均匀分布的独立哈希函数，符号为异或运算
符。
[0073]
3)步骤2)实现了在某个基于特定测量目标的测量周期内编码记录到达数据项的过程，在此之后需要判断是否让到达的数据项通过过滤结构。判断依据如下，获取到达的数据项《f，e，t》被哈希映射到的过滤器单元r[hm(f)]中各比特位的置位情况，当且仅当过滤器单元中的比特位都被置为1时，数据项(f，e，t》才允许通过过滤结构；否则，数据项被阻塞。
[0074]
通过过滤结构的大流作为数据流测量任务中主要被关注的对象，其最终的测量结果还包含大流初始到达时为了集齐赠券而未能通过过滤结构的部分数据项。因此，阈值估计部分对过滤结构中的哈希冲突和单个过滤单元特性进行了概率分析，推导得出了任意通过过滤结构的流为集齐赠券所消耗的数据项规模的期望。具体的实现方式如下：
[0075]
(1)通过概率推导构建过滤结构中任意单元的哈希冲突。记m为高速数据流中流的数量，nf为数据流中某条流f的实际测量结果。用符号ri表示某个过滤器单元r[i]实际被映射的流的数量。符号ni则与当前周期下的测量目标项关联，表示了该过滤单元中多条冲突流各自实际测量结果的和。
[0076]
(1.1)用公式(1)计算任意某个过滤器单元r[i]被映射的流的数量为ri的概率。
[0077][0078]
(1.2)用公式(2)计算当某个过滤器单元r[i]中存在ri条冲突流时，该过滤单元中冲突流的实际测量结果的和为ni的概率。
[0079][0080]
(1.3)用公式(3)计算过滤器单元r[i]中各冲突流的实际测量结果的和为ni的概率。
[0081][0082]
(2)对单个过滤单元特性进行概率分析。用符号li表示过滤器单元r[i]中被置1的比特位的数量。
[0083]
(2.1)计算某个过滤器单元r[i]中到达了实际测量结果之和为ni的数据项时，过滤器单元r[i]中有li个比特位被置为1的概率，计算方式为公式(4)。
[0084][0085]
(2.2)用符号表示过滤器单元r[i]中的比特位都被置为1时，该单元所需要的最小规模数据项的实际测量结果。根据步骤(2.1)的计算所得，可以推导过滤器单元r[i]中到达了实际测量结果之和为的数据项时，过滤器单元r[i]中刚好所有比特位都被置为1的概率，计算方式为公式(5)。
[0086][0087]
(3)通过概率推导得出任意通过过滤结构的流所消耗的数据项规模的期望。
[0088]
(3.1)根据公式(3)和公式(4)，可以推导得到任意过滤器单元的所有比特位都被置为了1的概率，计算方式为公式(6)。
[0089][0090]
(3.2)根据公式(3)、公式(5)和公式(6)的计算所得，可以得到任意过滤器单元仅消耗了规模的数据项就将所有比特位都被置为了1的概率，计算方式为公式(7)。
[0091][0092]
(3.3)最终，通过计算公式(7)所得概率的期望可以得到任意通过过滤结构的流为集齐赠券所消耗数据项规模的期望，即过滤结构的过滤阈值，有公式(8)。
[0093][0094]
以上仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。

技术特征：
1.一种面向高速数据流的通用流级过滤方法，其特征在于：包括实时编码过滤和阈值估计两部分，所述实时编码过滤部分，根据当前测量周期下的测量目标对流的统计信息采用不同的编码方式，用于过滤分离数据流中的大、小流；所述阈值估计部分，用于获得大流初始到达时为了集齐赠券而未能通过过滤结构的部分数据项的统计信息。2.如权利要求1所述的一种面向高速数据流的通用流级过滤方法，其特征在于：所述实时编码过滤部分，包括，设立用于分离数据流大、小流的过滤结构；在测量周期内，首先，将到达过滤结构的数据项根据其流标签，通过流-过滤单元映射函数随机映射到过滤结构的任意过滤单元中；其次，根据当前周期的测量目标选择对应的数据项-比特位映射编码函数，将该数据项映射到过滤器单元中的比特位并置位；之后，根据数据项获得的比特位的置位情况，判断该数据项是否通过过滤结构，将通过过滤结构的大流作为数据流测量任务中主要被关注的对象。3.如权利要求2所述的一种面向高速数据流的通用流级过滤方法，其特征在于：所述过滤结构包含了m个过滤单元的数组r，每个过滤器单元包含l个比特位；在每个测量周期的初始时刻过滤结构内的所有比特位的值均设置为0；l表示赠券类型数量的预设值，每个过滤器单元的l个比特位与需要集齐的l种赠券类型相关对应。4.如权利要求2所述的一种面向高速数据流的通用流级过滤方法，其特征在于：所述流-过滤单元映射函数h
m
(
·
)通过哈希计算得到：h
m
(f)＝h
′
(f)mod m，且h
′
(
·
)为一个均匀分布的独立哈希函数。5.如权利要求2所述的一种面向高速数据流的通用流级过滤方法，其特征在于：当到达的数据项使对应流的实际测量结果发生变化时，存在一个预设的概率p(0<p≤1/l)使得该数据项能够以l
×
p的概率在被映射到的过滤器单元r[h
m
(f)]中将任意一个比特位置1，在此过程中被映射单元的每一个比特位被置1的概率都是p；其中对于在测量周期内设定的完全不同的测量目标，包括流的大小测量，基数测量，以及持续性测量，数据项在过滤器单元的概率置位存在不同的计算方式：1)当测量目标为流大小测量时，所述数据项-比特位映射编码函数h
c
＝h
′
c
；具体的，在以流大小为测量目标的测量周期下，当任意数据项<f，e，t>的到达时，与流存在映射关系的过滤器单元r[h
m
(f)]的第h
′
c
(f，e，t)个比特位将被置1，其中h
′
c
(f，e，t)是基于流大小测量目标的赠券抽取函数，计算方式为：其中，r是当一个数据项到达时，在[0，1)之间随机生成的数值；2)当测量目标为流基数测量时，所述数据项-比特位映射编码函数h
c
＝h
″
c
；具体的，在以流基数为测量目标的测量周期下，当任意数据项<f，e，t>的到达时，与流存在映射关系的过滤器单元r[h
m
(f)]的第h
″
c
(f，e，t)个比特位将被置1，其中h
″
c
(f，e，t)是基于流基数测量目标的赠券抽取函数，计算方式为：
其中，h(
·
)为一个值域范围在[0，x)之间的均匀分布的独立哈希函数，符号为异或运算符；3)当测量目标为流持续性测量时，所述数据项-比特位映射编码函数h
c
＝h
″′
c
，具体的，在以流持续性为测量目标的测量周期下，当任意数据项<f，e，t>的到达时，与流存在映射关系的过滤器单元r[h
m
(f)]的第h
″′
c
(f，e，t)个比特位将被置1，其中h
″′
c
(f，e，t)是基于流持续性测量目标的赠券抽取函数，计算方式为：其中，h(
·
)为一个值域范围在[0，x)之间的均匀分布的独立哈希函数，符号为异或运算符。6.如权利要求2所述的一种面向高速数据流的通用流级过滤方法，其特征在于：数据项是否通过过滤结构依据如下，获取到达的数据项<f，e，t>被哈希映射到的过滤器单元r[h
m
(f)]中各比特位的置位情况，当且仅当过滤器单元中的比特位都被置为1时，允许数据项<f，e，t>通过过滤结构；否则，数据项被阻塞。7.如权利要求1所述的一种面向高速数据流的通用流级过滤方法，其特征在于：所述阈值估计部分，包括，(1)通过概率推导分析过滤结构中的哈希冲突；(2)对单个过滤单元的编码特性进行概率分析，得到任意一个过滤单元上被映射了若干数据项(或非重复数据项)时过滤单元中的比特位都被置为1的概率，以及任意一个过滤单元上被映射了若干数据项或非重复数据项时过滤单元中的比特位刚好都被置为1的概率；(3)基于上述概率分析结果进一步推导得出任意通过过滤结构的流所消耗的数据项或非重复数据项规模的期望。8.如权利要求7所述的一种面向高速数据流的通用流级过滤方法，其特征在于：过滤结构内流间的哈希冲突通过如下步骤分析：(1.1)用公式(1)计算任意某个过滤器单元r[i]被映射的流的数量为r
i
的概率；(1.2)用公式(2)计算当某个过滤器单元r[i]中存在r
i
条冲突流时，该过滤单元中冲突流的实际测量结果的和为n
i
的概率；(1.3)用公式(3)计算过滤器单元r[i]中各冲突流的实际测量结果的和为n
i
的概率；其中，m为高速数据流中流的数量，n
f
为数据流中某条流f的实际测量结果；用符号r
i
表
示某个过滤器单元r[i]实际被映射的流的数量；符号n
i
则与当前周期下的测量目标项关联，表示了该过滤单元中多条冲突流各自实际测量结果的和。9.如权利要求7所述的一种面向高速数据流的通用流级过滤方法，其特征在于：对单个过滤单元特性进行概率分析具体如下：(2.1)计算某个过滤器单元r[i]中到达了实际测量结果之和为n
i
的数据项时，过滤器单元r[i]中有l
i
个比特位被置为1的概率，计算方式为公式(4)；(2.2)用符号表示过滤器单元r[i]中的比特位都被置为1时，该单元所需要的最小规模数据项的实际测量结果；根据步骤(2.1)的计算所得，推导过滤器单元r[i]中到达了实际测量结果之和为的数据项时，过滤器单元r[i]中刚好所有比特位都被置为1的概率，计算方式为公式(5)；其中，用符号l
i
表示过滤器单元r[i]中被置1的比特位的数量。10.如权利要求9所述的一种面向高速数据流的通用流级过滤方法，其特征在于：通过概率推导得出任意通过过滤结构的流所消耗的数据项规模的期望，具体如下：(3.1)根据公式(3)和公式(4)，可以推导得到任意过滤器单元的所有比特位都被置为了1的概率，计算方式为公式(6)；(3.2)根据公式(3)、公式(5)和公式(6)的计算所得，可以得到任意过滤器单元仅消耗了规模的数据项就将所有比特位都被置为了1的概率，计算方式为公式(7)；(3.3)最终，通过计算公式(7)所得概率的期望可以得到任意通过过滤结构的流为集齐赠券所消耗数据项规模的期望，有公式(8)；

技术总结
本发明涉及高速数据流(如网络流)中的大小流分离，是一种面向高速数据流的通用流级过滤方法，包括实时编码过滤和阈值估计两部分，所述实时编码过滤部分，用于获得通过过滤结构的大流；所述阈值估计部分用于获得大流初始到达时为了集齐赠券而未能通过过滤结构的部分数据项。本发明提供的一种面向高速数据流的通用流级过滤结构，能够灵活地根据不同的测量目标(如流的大小测量，基数测量，以及持续性测量)有效实现数据流中大流和小流的分离。量)有效实现数据流中大流和小流的分离。量)有效实现数据流中大流和小流的分离。


技术研发人员：卜霄菲 吴晓灿 黄河 孙玉娥
受保护的技术使用者：沈阳师范大学
技术研发日：2023.07.19
技术公布日：2023/9/16