一 流数据的特征
- 分发速度非常快，必须及时处理，否则将永远丢失。
- 即使分发速度较慢，同时多个数据流一起则超过了内存最大容量。
二 流数据的处理方法
2.1 流数据抽样
问题描述：过去的一个月中典型用户提交的重复查询比率是多少。假设我们只存储其中十分之一的流元素。
典型做法：对每个搜索查询产生一个随机数（比如0-9中间的一个随机数），并当且仅当为0时才存储。如果用户提交的查询足够多，大数定律会保证大部分用户所存储的比例非常接近1/10.
2.1.1 误区
如果想得到用户提交的平均重复查询数目，上述抽样会得到错误结果。
假设某个用户在你过去一个月中有s个查询只提交过一次，d个查询提交两次，不存在超过两次的提交。那么提交过一次查询数目达到我们所期望的s/10，而在出现过两次的d个查询中，只有d/100会在样本中出现2次，该值等于d乘以该查询两次出现在1/10样本中的概率。于是在整个中出现2次的d个查询中，有18d/100个查询样本在样本中出现一次。
本来，在所有搜索查询中重复搜索查询的比率正确答案是d/(s+d).但是，如果采用上述方法，我们得到的值为 d/10+18d/100个查询出现一次。
2.1.2 正确思路
我们不能从每个用户的搜索查询的抽样样本中得到正确答案。因此，必须要挑出1/10的用户并将它们所有的查询放入样本，而不考虑其他用户的搜索查询。每当一个新的查询到达流中时，我们会查找用户以判断其是否在已有样本中出现，若出现则放入样本，否则丢弃。如果没有出现该用户，我们产生一个0-9随机数，若为0则加入用户列表，并将其标记为”in”，否则，也加入用户列表，但是标记为”out”。
注意：引入哈希函数将每个用户哈希到编号0-9的10个桶中之一。但是桶中并不保存真正用户，事实上桶中没有任何数据。只是将哈希函数作为随机数生成器来使用。该哈希函数的一个重要特点就是，即使在相同用户上应用多次，其生成的随机数也相同。即，对任何用户都不需要存储其in/out决策，因为任何查询到来时都可以重构该决策。
2.2 流过滤
主要讨论的是使用布隆过滤器。
2.2.1 布隆过滤器简介
布隆过滤器也即Bloom Filter算法 一个布隆过滤器由以下几个部分组成
- n个位组成的数组，每个位初始值都是0。
- 一系列哈希哈书 $h_1,h_2,h_3…..h_k$ 组成的集合。每个哈希函数将“键”值映射到上述n个桶（对应于位数组的n个位）中。
- m个键值组成的集合S
布隆过滤器的目的是让所有键值在S中的流元素通过，而阻挡大部分键值不再S中的流元素，哈希函数hi及S中的键值K，将每个 $h_i(K)$对应的位置为1。
当键值为K的流元素到达时，检查所有的 $h_1(k)， h_2(k) ，h_3(k)….h_k(k)$ 对应的位是否全部都是1.如果是则允许该元素通过，如果有一位或多位为0，则认为K不可能在S中。则拒绝该元素通过。如果元素键值在S中出现一定会通过布隆过滤器，但是元素键值不在S中的元素也有可能会通过。我们需要了解如何基于位数组长度n，集合S的元素数目m及哈希函数的数目k来计算false positive概率。
2.2.1 Bloom Filter算法思路
- 我们有一个长度为n的比特数组，开始的时候将这个比特数组里所有的元素都初始化为0。
00000000000000000000
上面的比特数组n为20。
- 然后选取k个哈希函数，这k个哈希函数产生的结果的值的范围在0到n-1之间（对于上面的比特数组，即0到19）。对每个要添加进集合的对象进行哈希运算，然后将哈希计算结果作为数组的索引，将索引位置的比特位设置为1（不管该比特位原先为0还是为1）。
比如我们选取三个哈希函数，对于对象A哈希值为0，5，7。那么比特数组就为：
10000101000000000000
对象B的值为2，8，13，那么添加B后的比特数组为：
10100101100001000000
对象C为0，4，7（对象C的第一个哈希函数的值与对象A的相同了，没关系我们还是设置为1就可以了）：
10101101100001000000现在我们的Bloom Filter里已经有3个元素了。现在我们要判断某元素X是否在该集合中。就相当于我们要实现一个contains方法。
对元素X采用相同的三个哈希函数哈希，然后以这三个哈希值为索引去比特数组里找。如果三个索引位置的比特位都为1我们就认为该元素在集合中，否则不是。
2.2.3 Bloom Filter算法应用
比如假设我们有一个缓存服务器集群，集群里的不同的服务器承担的缓存也不尽相同。如果一个用户请求过来了，我们如何能快速的判断出用户请求的这个url在集群里哪台服务器上呢？因为每台服务器上缓存的url对应的页面非常庞大，我们全部弄到内存里代价也很高。我们就可以在每台服务器上放一个Bloom Filter，里面添加的都是本服务器上有缓存的那些url。这样即使Bloom Filter误报了，那就是把一个url发到了一个并不持有该url对应的缓存的服务器上，结果就是缓存未命中，缓存服务器只需要将该url打到后端的上游服务器就好了。
三 独立元素数目估计
3.1 FM算法（Flajolet-Martin）
基本思想是：如果流中看到的不同元素越多，那么我们看到的不同的哈希值也越多。我们看到的不同哈希值越多时，哈希函数的性质是对同一个数哈希结果都是一样的。
理想中的是：对同一批数据使用多个哈希函数，每个哈希函数上得到不同的 $2^R$ 的值（对流元素a应用哈希函数h,h(a)的尾部将以一些0结束，尾部0的数目成为a和h的尾长，假设目前所有已有元素a的最大尾长为R， $2^R$ 用来估计流中独立元素数目），然后求它们的平均值即可得到真实的m的近似值。
3.2 FM算法的问题
假设一个r，使得2^远大于m。存在某个概率p发现r是流中最大尾长，于是发现r+1是流中最大尾长的概率至少为p/2.因此，随着R的增长，每个可能的R对2^R的期望贡献也越大。2^R的期望值实际是无限大。
3.3 完美解决方案
取所有估计值得中位数，由于中位数不会受到偶然极大的2^R影响。缺陷是：它永远都是2的幂值,不论用多少哈希函数，都是在两个2 的幂之间，那么小至少是log2(m)的一个小的倍数。
我们可以：首先将哈希函数分成小组，每个小组内取平均值。然后再所有平均值中取中位数，组间取中位数可以将中位数的缺陷的影响降低到几乎没有的地步。每个组的大小至少是log2(m)的一个小的倍数。
四 矩估计
上述独立流元素计数推广到一般的问题，该问题称为矩计算，包括不同流元素出现的频率分布的计算。
4.1 矩定义
假定一个流由选自某个全集的元素够成，并假定该全集中所有元素都排好序，这样我们通过整数 i 来标记该序列中的第i 个元素，假设该元素出现的次数为mi,则流的k 阶矩是所有 i 上的(mi)^k 之和。
流的一阶矩是所有元素mi之和，也即整个流的长度，当前流所有元素个数；二阶矩是所有元素mi的平方和。
4.2 二阶矩的AMS算法
假设没有足够空间来计算流中所有元素的mi。我们仍然可以使用有限空间来估计流的二阶矩，空间越多结果越精确。对每个变量X 我们保存一下内容。
- 全集当中的一个特定元素，记为X.element。
- 一个整数，记为X.value，它是变量X的值。在流中均匀的随机选择1到n之间的一个位置。将X.element置为该位置上的元素，X.value初始为1，每再看到一个X.element 就将其对应的X.value 值加1。
因此二阶矩为 $5^2+4^2+3^2+3^2=59$ .假定维护3个变量 $X_1,X_2,X_3$ .假定随机位置为3,8,13。当到达位置3时，对应的元素为c，于是 $X_1.element=c$ ,此时 $X_1.value=1$ ,而位置4为b，5为d，6为a，X1的值均不改变，在位置7元素c再次出现，继续往后的话，位置12再出现c，因此 $X_1.value=3$ 。据此可以得到 $X_2.value=2$ 和 $X_3.value=2$ (注意，他们都是从该元素第一次出现之后，往后出现的才算)。
基于任意一个变量X，我们可以导出二阶矩的一个估计值为： n*(2*X.value-1)
根据本例中的值，我们可以通过二阶矩估算值得平均值为：(15*(2*3-1)+15*(2*2-1)+15*(2*2-1))/3=55 可知与精确值 59相当接近了。
4.3 无限流的处理
对于二阶矩以及多阶矩的估计当中，我们是假定流长度n 是一个常数。实际应用当中，n 会不断随着时间增长。因此在变量位置选择的时候需要谨慎。
- 一方面，如果只对所有元素做一次选择，流不断增长时，计算会偏向早期的元素
- 另一发面，如果选择的等待时间太久，那么早期的元素位置上变量不多，从而造成估算的可靠性不高。
- 比较合理的选择是，任何时候都尽可能保持足够多的变量，并在流增长时丢弃某些变量（在选择某个位置的概率和其他位置的概率必须相等）。