数据流处理—摘要的艺术

数据极客 2015-07-11

大数据时代,数据流式处理已经是司空见惯的广泛需求。例如Web用户行为分析数据,用户查询,网络监控,乃至金融交易等时间序列数据流。著名的Lambda架构模式,就把数据处理分为批量和流式,兵分两路分别处理。一系列面向数据流的框架,例如Storm,Spark Streaming,Samza,Heron等等专门为流式处理的工具,构成了不同公司大数据框架的基石之一。然而,这并不是本文所要讲述的内容,拿着开源软件组装系统,还谈不上处理的“艺术”,什么可以称为艺术呢?自然是算法。


有这么一些流式处理中的常见问题,需要借助于算法解决,比如在数据流中找出最频繁项。这种应用场景有:广告点击分析,新闻趋势分析,热搜榜,以及网络安全中的流量攻击等等。这种问题可以简单地采用一种称为Space-saving的算法来解决:初始化一个链表纪录频率以及频繁项列表,链表长度取决于TopK,当从数据流中看到一个元素时,如果已经存在,则增加计数器,否则就插入到链表中频率最低的那项中。Space-saving算法十分简单和有效,算得上数据流算法中的入门之选。

接下来的问题是:如何计算数据流中任意元素的频率。在此之前,我们可以先看一下另外一个更简单一些的问题,那就是:如何查看数据流中某元素是否存在——这显然是用常见的的近似数据结构Bloom Filter来计算。Bloom Filter是一种有假阳性(false positive)的概率数据结构,给定n位的数组,k个hash函数,m个待过滤的元素,则Bloom Filter假阳性概率是(1-e^(-km/n))^k,推导:元素不能落入指定的位置的概率是 (n - 1) / n,那么m个元素,hash了k次,仍未落入指定位置的概率是(1 - 1/n)^(km),即当n较大时,指定位置为0的概率近似于e^(-km/n),为1的概率为1-e^(-km/n)。而假阳性的概率,是k个hash函数产生的k个指定位置, 都为1的概率: (1-e^(-km/n))^k。


我们可以把Bloom Filter延伸使得可以计算任意元素的频率,这就是最常见的Sketch算法——Count-min Sketch。Sketch的意思是摘要,就是说我们针对数据流的某种统计侧面做摘要,从而用更小的空间提供数据流的统计分析。

假定有一个数据处理任务,需要计算一个数据集中共现词的频度。如果数据集中包含78M的关键词,其中不同关键词数目大约63K,不同的共现词对则可能达到1亿多。常规的做法可能不得不去求助Hadoop,然而有Count-min Sketch算法,则可以用几十分之一的空间单机达到一样的功能。


第三个场景来自针对数据流中基数(不同元素)的统计。在12年我们采用HyperLoglog进行大规模日志系统构建时,该算法还不为多数人所知,目前HyperLoglog的知名度可能已经快赶上Bloom Filter了。HyperLoglog基于Loglog改进而来,它的思想是:设a为待估集合(哈希后)中的一个元素,H是一个哈希函数应用于所有元素,假设H的结果均匀并且几乎无碰撞,那么a可以看做一个长度固定的比特串(也就是a的二进制表示),又因为a服从均与分布,所以a的每个比特位为0和1的概率各为0.5,且相互之间是独立的。设P为a的比特串中第一个1出现的位置,取Pmax为P的最大值,那么我们可以取2^Pmax为基数的粗糙估计。下面解释为什么这样估计:由于比特串每个比特都独立且服从0-1分布,因此从左到右扫描上述某个比特串寻找第一个1的过程可以看作是一个伯努利过程。在一次这样的过程中,投掷一次就得到正面的概率为1/2,投掷k次得到正面的概率为1/2^k。因此进行n次伯努利过程,所有投掷次数都不大于k的概率就为(1-1/2^k)^n;至少有一次投掷次数大于等于k的概率为1-(1-1/2^k)^n。当n>>2^k时,至少有一次投掷次数为k的概率几乎为1;当n<<2^k时,至少有一次过程投掷次数等于k的概率几乎为0。一次伯努利过程对应一个元素的比特串,反面对应0,正面对应1,投掷次数k对应第一个1出现的位置,Pmax为所有元素中首个1的位置最大的,如果基数远远大于2^Pmax,则Pmax为基数的概率几乎为0,如果基数远小于2^Pmax,则Pmax为基数的概率也几乎为0,因此就拿2^Pmax做为基数估计的最佳值。不过如果直接使用它进行基数估计会由于偶然性而存在较大误差。因此,Loglog采用了分桶多次估计取平均的思想来消减误差。而HyperLoglog则是针对Loglog在基数不大的情况误差较大的修正。对于HyperLoglog的运用不应停止于此,事实上,它还可以拿来做不同集合之间的求交和求并的结果后的基数估计,例如对于一个广告系统统计后台,如果需要在秒级返回两个campaign的目标用户重叠的数量,就是HyperLoglog施展的场景了。


下面一个问题是寻找数据流中的中间值,例如数据流中排序占前75%的值是多少,术语叫Quantile问题。数据流的Quantile探测可以用于监控领域,比如实时监控系统延迟值以及分布,也可用于分布式数据库的查询优化(探测查询延迟分布)。利用Count-min Sketch是个可行方案,但有时候我们几乎不想使用任何额外内存,这时可以考虑Frugal Streaming算法:
中值估计:
median_est = 0
for val in stream:
if val > median_est:
median_est += 1
elif val < median_est:
median_est -= 1
75%值估计
quantile_75 = 0
for val in stream:
r = random()
if val > quantile_75 and r > 1 - 0.75:
quantile_75 += 1
elif val < quantile_75 and r > 0.75:
quantile_75 -= 1
Frugal Streaming算法成功的假设依赖于数据流中数据值分布的稳定,然而,如果存在突发性的分布变化,例如系统中突然存在大量延迟响应,
那么该算法无法迅速发现该变化。

摘要技术不光运用在数据流式处理,也可以用到各种数据挖掘场景,例如图像搜索,利用摘要对图像生成指纹,变图像距离为汉明距离;聚类中的局部敏感哈希LSH也可以归入此类;甚至对于矩阵分解,也可以用摘要技术变大型矩阵为小矩阵降低计算开销,可广泛应用于推荐引擎,等等诸多此类,这些展开话题就很大了。



本站仅按申请收录文章,版权归原作者所有
如若侵权,请联系本站删除
觉得不错,分享给更多人看到