写在前面：与传统的数据库数据处理相比，流式数据的实时处理在现实生活中更加常见，尤其是在互联网的应用背景下，数据的采集和数据驱动的应用都要求数据分析系统具有对流式数据的实时处理能力。为了能更好的研究流式数据上的在线应用问题，需要对流式数据及其实时处理有个大致的了解，本文参考了部分流式挖掘的研究综述、论文和教辅书籍，从流式数据的采集、表示、处理三个方面简单总结了流式数据的特征、模型和基本处理方法，并给出了流式数据处理中存在的部分研究挑战。如有任何错误，欢迎批评指正！
一 流式数据的采集
1 流式数据来源
（1）现有的时态数据分析系统通常会采用更底层的分布式采集机制进行实时数据的采集。分布式数据源产生的数据必须被实时、可靠地采集到一个或多个数据分析中心。日志记录确保数据交付的可靠性，触发器确保数据的及时性。
（2）大规模实时分析系统不仅从多个数据源采集数据来构建一个数据流，还可以通过不同的数据源构建多个数据流，并根据其关联性计算答案。
2 流式数据特征
（1）数据持续到达且到达速度快。
（2）无法预知所有数据何时能够全部到达。
（3）多数据流场景中不同数据流的数据交付存在不同程度的时延。
（4）实时数据规模宏大，通常难以被全部存储或存储访问代价大。
二 流式数据的表示
1 流式数据表示的基本假设
存储空间有限且不大。
2 流式数据表示目的
快速应对基于流数据的查询和计算。以此为目的的数据流表示方式应该根据不同的查询计算需求来设计。数据流表示方法的一个关键数学特性是线性特性，数据随时间流逝带来的变化不仅易于被识别，而且易于基于原始数据进行更新。
3 流式数据模型
流式数据的输入模型根据不同的时序范围可以划分为三种子模型，包括界标模型（landmark model）、窗口模型（window model）和快照模型（snapshot model）。
界标模型标记数据的起始时间，其对应的查询范围是初始时间到当前时间为止的数据。
窗口模型记录的是固定范围内的数据，有两种类型，分别是时间驱动（即窗口涵盖的时间长度固定）和数据驱动（即窗口涵盖的数据量固定）。窗口又可以分为三种形式，分别是滚动窗口（数据无重叠）、滑动窗口（数据部分重叠）和会话窗口（相邻窗口间存在间隔）。输出结果将根据完整窗口内容生成。针对窗口模型的操作包括两种，一种涉及单一时刻下的事件，一种跨越多个时刻的事件。
快照模型按照时刻记录数据，通常将数据操作限定在单个时间戳下或时间戳之间的数据上。
流式数据还有一些其他的导出模型，包括直方图和索引等，用于对流式数据中重要的内容能通过一个远小于数据集规模的结构（称为概要数据结构）被保存下来。研究和实践中，通常采用数据抽样、小波分析、数据过滤等方法得到数据流的导出模型。
三 流式数据的处理
流式数据通常是边采集边分析，原始数据并不保存。为了能够保证数据流上操作的有效性，对数据流的处理通常包括数据抽样、数据过滤、数据计算等。
1 流当中的数据抽样
数据流上需要解决的一个一般性问题是从流中选择一个子集，以便能够对它进行查询并给出统计性上对整个流具有代表性的结果。
常见的数据抽样做法为采用哈希函数将所有数据映射到b个桶中的1个，然后选取其中a个桶作为样本。可以根据不同的应用需求，设定不同的哈希函数和b个桶中选a个桶的策略。
2 流过滤
另一个常见的流数据处理方式是选择或称为过滤，即只接受流中满足某个准则的元组集合，被接受的元组会以流的方式传递给另一个过程，而其他元组将被忽略。
流过滤中存在的挑战是当选择准则是较为复杂的集合元素查找时，面对规模大的数据，难以在内存中进行处理，过滤起来会很困难。
常见的解决方法是采用布隆过滤器，简单来说布隆过滤器是通过多个哈希函数对不同的元组进行编码，在过滤时，只保留被所需样本集所包含的元组。
3 流中独立元素的数目统计
独立元素统计问题是计算流中从头或从某个已知的过去时刻开始所出现的不同的元素数目。
naive的解决方法是在内存中保存当前已有的所有流元素列表。这种方法适用于独立元素不多，搜索结构能全部放入内存中，可以给出独立元素的精确个数。当面对独立元素个数多或需要立刻处理多个流的情况时，将无法在内存中存储所需数据。有两种解决方法，一种是使用更多的机器；另一种是将搜索结构的大部分存到一个二级存储器中，对流元素进行分批处理，但通常会面临很大的时间代价。
FM算法通过将全集中的元素哈希到一个足够长的位串，对独立元素个数进行估计。其基本思想是，如果流中看到的不同元素越多，那么我们看到的哈希值也会越多，同时也越可能看到其中有一个“异常”，采用该“异常”的哈希值进行独立元素数目的估计。
4 矩估计
矩计算是对不同流元素出现频率分布的计算。k阶矩的定义为，全集中每个元素出现次数的k次方之和。二阶矩估计的常用方法为AMS算法。
5 窗口内的计数问题
窗口内的计数问题关注的是内存中无法容纳整个窗口时，需要对二进制流进行处理给出一个近似求解算法。最简单情况下的处理算法是DGIM，该算法能够使用O(log^2N)位来表示大小为N位的窗口，同时能保证窗口内1数目的估计错误率不高于50%。
6 衰减窗口
不将最近的元素与过去的元素截然分开，而是对最近的元素赋予更高的权重，常见的应用是最常见元素问题，即从数据流中总结出最近出现最频繁的元素。该问题的挑战在于，面对大量的不同元素时，计数方法效率不高且只能产生近似的估计结果。
衰减窗口给窗口内的数据赋予一个平滑的不断衰减的权重，使得元素在流中出现的越早，其权重也越小。
四 流式数据处理研究的主要挑战
挑战1：所有数据何时才会全部到达难以预估，因此对数据分析的最终一致性带来挑战。
（一般会尽可能地处理已到达、可用的数据，并在其余数据到达时根据需要来重算结果。）
挑战2：多数据流的时延问题导致数据处理的时态一致性难以得到保证，即能否在一定时间内基于多数据流获得充分可信的结果。
（数据流时态一致性理论和实践仍处于起步阶段，例如有界延时调度理论[Leontyev and Anderson, 2010]的建模方式。）
挑战3：针对快速增长且不断变化的海量数据，设计与实现新颖的数据表示和处理方法，特别是要与学习、建模方法相整合。当前的算法在建模方面非常高效，但却难以随时间推移而更新模型。此外，没有太好的方法可以针对数据流去识别和检测模型变更。
挑战4：分布式环境下，时态数据的实时采集、存储和传输。
参考文献
[1] 金澈清, 钱卫宁, 周傲英. 流数据分析与管理综述[J]. 软件学报, 2004, 15(8): 1172-1181.
[2] Salman Ahmed Shaikh, Komal Mariam, Hiroyuki Kitagawa, Kyoung-Sook Kim. GeoFlink: A Distributed and Scalable Framework for the Real-time Processing of Spatial Streams[C]. CIKM, 2020.
[3] Jure Lekovec, Anand Rajaraman, Jeffrey David Ullman 著, 王斌 译. 《大数据：互联网大规模数据挖掘与分布式处理（第2版）》. 人民邮电出版社, 2015.
[4] 美国国家学术院国家研究委员会 组编, 华东师范大学数据科学与工程研究院 译. 《海量数据分析前沿》. 清华大学出版社, 2015.
网友评论