概述

数据流不一样于数据库，有几个特色：数据流的实时性，致使其须要被当即处理，不然会永远消失。同时通常数据量太大太快，动态存储没法存储所有数据。因此在处理数据流的时候，通常会采用两种算法：一、利用采样和过滤的思想对流实时处理，去除没必要要的元素。二、存储固定长度的窗口，对进入窗口的元素进行整合、计算，而后再利用估计和几率提供近似的答案。算法

数据流模型

能够看到这个模型中有数据数据流、流处理器、动态存储和档案存储、标准查询和临时查询、输出数据流。流与数据库的区别在于，一个到达数据速率可控，一个到达数据速率不可控。数据库

流查询分为标准查询和临时查询。标准查询是内置在流处理器中，而且永久的被执行，隔必定时间输出结果。我认为标准查询是能够经过计算每个进入的新元素得出答案，例如筛选出最大值、求最新24个元素的平均值等。临时查询是针对当前数据流的状态，准确的回答须要计算整个流的状况。例如统计过去一个月某网站不重复的用户数量。数组

在流中采样数据

首先讨论对于流的一个子集进行查询，其结果具备的表明性的几率，也就是经过子集获得整个流的状况的正确几率。函数

例如，搜索引擎中，咱们想要知道，在过去一个月，常规用户的重复询问比例是多少。而且假设咱们可以存储1/10的流元素。如何选择1/10的元素，咱们能够用随机数，对每个元组赋予0-9的随机数，并选一个数字的元组进行存储。可是这种方式在回答一个用户的重复问题的平均次数这个问题，答案是错误的。具体几率计算以下：网站

假设一个用户在一个月中有s条查询出现一次，d条查询出现两次，而且没有多于两次的查询。因此会有条出现，条出现两次，条出现一次。重复查询出现的正确几率应该是，而咱们推测出的答案为，即。因此经过计算能够知道，对问题进行抽样不能很好的回答咱们这个随机问题，所以咱们选择对用户进行抽样。搜索引擎

首先咱们对用户进行存储，每当新一个查询流进来，咱们检查该用户是否在样本里，若是在样本中则存储。若是这个用户以前没有出现过，咱们能够对其0-9赋值，决定其是否在样本中。这个方法颇有限，可是须要咱们可以在主存中存储全部用户列表和他们是否在样本中的标志，由于数据流很快，咱们没有时间对硬盘进行读写。可是主存空间很宝贵，存储大量的用户也不符合实际。设计

因此咱们经过哈希函数来代替存储用户名列表。把哈希函数当成随机数发生器，对每个用户名进行计算，计算值对应0-9的10个桶，相同的用户名须要获得一样的结果，利用这个放弃存储，实现快速抽样和存储。code

关于采样的其余问题

一、利用哈希函数进行采样须要针对关键字，不一样的关键字，不一样的采样频率须要设置不一样的哈希函数。blog

二、随着新数据流的进入和新用户被断定为样本，咱们保留的查询数据会愈来愈多。若是咱们对于存储的元组有预算，那么随着时间变化，键值的比例须要一步步下降。为了确保在任什么时候候样本均由键值子集中的全部元组组成,咱们维持一个阈值，该阈值最初能够是最大的存储桶数。在任什么时候候，样本都由键知足的那些元组组成。当且仅当知足条件的流中的新元组才添加到样本中。若是样本的存储元组数超过了分配的空间，咱们将下降到并从样本中删除全部键哈希值为的元组。为了提升效率，每当须要从样本中抛出一些键值时，咱们能够将下降1以上，并删除具备多个最高哈希值的元组。经过在散列值上维护索引能够得到更高的效率，所以咱们能够找到其键快速散列到特定值的全部那些元组。索引

流过滤

咱们但愿从流中筛选出符合必定条件的元组，可是困难在集合太大难以存储，所以这里介绍“Bloom filtering”算法。经过一个例子来结束，咱们假设有一个包含一亿邮箱地址的集合S，这些邮箱都不是垃圾邮箱，都是可信任的邮箱，流中包含元素为：一个邮箱地址和邮件自己。咱们须要将新收的邮件和S集合进行对比，将垃圾邮件剔除，因此须要对流进行过滤。在这个例子中，一般一个邮箱地址有20字节，所以在主存中存储S集合全部数据是不可能的。

Bloom filtering

假设咱们有1GB的动态存储空间，将其当作一个比特（位）数组，在这种状况下，咱们就用8亿比特的空间。设计一个哈希函数h，将S的每个地址计算成一比特，并在主存中将这一位设置为1，其他全部位不变。由于咱们有一亿的邮箱，所以大约的位会是1。实际上被设置为1的位会略少于，由于存在两个地址哈希值相同。当新元素进入的时候，咱们对其邮箱地址哈希计算，若是结果位是0，那么能够确定这个地址不在集合S中，将其丢弃。不幸的是，会有一些垃圾邮件经过。大约有不在S中的邮件会经过，但考虑到收到邮件的主体（约80%）是垃圾邮件，所以可以过滤的垃圾邮件也是颇有成效的。此外，在应用的时候能够利用级联的方式一层一层过滤，每一次都会过滤掉。

Bloom filter须要包含三个成分：

1. 一个n位数组，初始全为0。
2. 哈希函数集合,,...，每个哈希函数映射键值到个桶中，由于数组有n位。
3. 一个集合S，其中包含m个键值。

当新键值进入流，对全部哈希函数进行计算，,,...,，全部的结果位都为1的时候让这个元素经过，只要有一位是0就丢弃。

Bloom filtering的几率分析

把每个比特当成目标，S中的元素当成飞镖，那么一个比特位被置1的几率等同于一个目标被一个或多个飞镖击中的几率。S集合中有一亿元素，即，有8亿的比特位，即。所以一个肯定的目标没有被击中的几率为即，被击中的几率就是，计算下来就是0.1175。咱们能够将这个结论推广，目标的数量是，飞镖的数量是，那么一个比特位仍然是0的几率是。

在流中统计不一样的元素个数

咱们提出第三个问题，想知道流中有多少个不一样的元素，从流的第一个或中间某个地方开始。具体的例子：一个网站有多少不重复的用户？输入是网站的登录集合流。

在解决这个问题，咱们须要规定一个策略，即仅估计不一样元素的数量，但使用的内存少于不一样元素的数量。经过将集合的元素散列为足够长的位串，能够估计不一样元素的数量。位串的长度必须足够长，以使散列函数的结果可能比集合的元素更多。咱们将选择许多不一样的哈希函数，并使用这些哈希函数对流的每一个元素进行哈希处理。哈希函数的重要属性是，当应用于同一元素时，它始终会产生相同的结果。

Flajolet-Martin Algorithm

算法的思想是：若是流中有不少不一样元素，那么就会有不少不一样的哈希值，就有可能出现其中一个值是不寻常的。而这个不寻常的值咱们能够发现是以许多0结尾的。

当咱们对流元素应用哈希函数，结果会以必定数量的0结尾。咱们将这个数量称为和的尾巴长度，并设置为流中任一元素的最大尾巴长度。而后咱们能够估计流中不一样元素的数量为个。一个给定的流元素的哈希函数值以致少个0结尾的几率是，假设流中有个不一样的元素，那么这些元素中没有一个的尾巴长度至少是的几率是，咱们能够将这个几率重写为。这个表达式能够变成的形式，这个式子大约是。

所以，找不到一个有r个0结尾的流元素的几率是。咱们能够概括出下面两点：一、若是的值比大得多，那么咱们找到尾巴长度至少为r的几率接近1。二、若是若是的值比小得多，那么咱们找到尾巴长度至少为r的几率接近0。