大数据设计

面试中设计的大数据设计题的场景通常不会太复杂，因此不需要给出细致的操作，给出大致的思路即可。但是有时候依旧考虑的不全面 :disappointed_relieved: :disappointed_relieved: :disappointed_relieved:借此机会记录下来巩固自己这方面的知识。

数据流采样

这是一个经典的采样问题，如果之前没见过一时半会想不出来解决办法。基本场景如下：

有一个无限的整数数据流，如何从中随机地抽取k个整数出来？使得每一个数被抽中的概率相同。
现实场景可以描述为：现有一台文件服务器用于源源不断接收其他系统服务器上传的服务日志，为了调查其他服务的质量，需要留下一些文件进行服务质量的调查，且储存的文件服务器大小有限，只能存储3000个服务日志，那么应当如何设置接收策略使得留下的文件能够代表其他服务的质量(言外之意就是留下的文件必须是等概率的，否则不公平)？

假设最后需要留存的整数（文件）为k个，那么有如下的证明：

K=1的时候

抽样方法如下：

• 当数据流(文件流)第一个数来到的时候，一定保留下来
• 第二个整数来的时候，以\frac{1}{2}的概率保存来的这个数，此时最开始的第一数和第二个数保留下来的概率均为\frac{1}{2}，实现了等概率。
• 当第i个数来到的时候，以1- \frac{1}{i}的概率丢弃这个数，也即以\frac{1}{i}的概率保留这个数？

如果i=n的时候，如何保证最后一步的操作是正确的呢？这可以使用数学归纳法证明：

• 当n=1的时候，这在之前的说明中已经证明了是正确的
• 当n=p的时候，假设是正确的，那么第p个数被保留的概率为\frac{1}{p}
• 当n=p+1的时候，那么被保留的概率为\frac{1}{p+1}，前面p个数被保留的概率为\frac{1}{p} \cdot\left(1-\frac{1}{p+1}\right)=\frac{1}{p+1}，第一部分的\frac{1}{p}表示前面p个数留下了一个，后面1-\frac{1}{p+1}表示第p+1个数没有被选中，两个独立事件的乘积最后构成了整个事件的概率。

k>1的时候

当需要保留下来整数(文件)的个数大于1的时候，也就是当样本总数为n的时候，最后留下的样本概率为\frac{k}{n}，此时依旧可以使用数学归纳法进行证明。

• 前面i个数 (1 ,2, 3 , 4 , 5 ...., i ) 达到的时候 (i \le k)，每一个都需要留下来，此时大家概率都是相等的，就是1.
• 当序号k+1到来的时候，第i个元素被k+1元素替换的概率为：k+1 个元素被选中的概率 * i 被选中替换的概率=\frac{k}{k+1} \times \frac{1}{k}=\frac{1}{k+1}。则被保留的概率为：1-\frac{1}{k+1}=\frac{k}{k+1}。，以此类推，k+2元素不被替换的概率为1-\frac{k}{k+2} \times \frac{1}{k}=\frac{k+1}{k+2}。那么到n元素到来的时候，被保留的概率为 = 被选中的概率 * 不被替换的概率 = 1 \times \frac{k}{k+1} \times \frac{k+1}{k+2} \times \frac{k+2}{k+3} \times \ldots \times \frac{n-1}{n}=\frac{k}{n}

蓄水池采样算法总结

蓄水池采样算法总结下来就是一个核心公式p=\frac{k}{n}，n为到来的序号，k为需要保留的数量。

基数估计

如何计算数据流中不同元素的个数？例如，独立访客(Unique Visitor，简称UV)统计。这个问题称为基数估计(Cardinality Estimation)，也是一个很经典的题目。

小数据量 - HashSet

小数据量直接使用HashSet，每来一个元素，就往里面塞，HashSet的大小就所求答案。但是在大数据的场景下，HashSet在单机内存中存不下，这种方法只适用于小数据量，对于大数据或者多机场景都不适合。

Bitmap

HashSet很大的缺点是需要储存原始数据，如果想要不储存元数数据，那么可以使用Bitmap的数据结构。Bitmap使用的前提需要大概知道数据不同元素的个数上限，也就是基数的最大值，假设为N。那么可以开一个长度为N的bit数组，每个元素和bit元素中的一位对应。每次一个元素到来之后通过hash映射找到所在的位置，记录为1。因此最后统计bitmap中1的个数就可以得到不同元素的个数。

这个方案的缺点是，bitmap的长度与实际的基数无关，而是与基数的上限有关。假如要计算上限为1亿的基数，则需要12.5MB (10^{8}bit = \frac{1}{8} * 10^{8} byte = 12.5 MB) 的bitmap，10种统计就需要125M。关键在于，这个内存使用与集合元素数量无关，即使仅有一个上限为1亿的基数，也要为其分配12.5MB内存。该算法的空间复杂度是 O(N_{max})

实际上目前还没有发现在大数据场景中准确计算基数的高效算法，因此在不追求绝对准确的情况下，使用近似算法算是一个不错的解决方案。

线性统计-Linear Counting

线性统计的基本思路为：

• 选择一个合适的哈希函数h，h的结果需要服从均匀分布
• 初始化一个长度为m的Bitmap
• 数据流来了一个元素，使用h进行映射，然后对m进行取模，将这个位置置为1
• 最后查询如果存在u个bit为0，那么不同元素的总数近似为 -m \log \frac{u}{m}

在使用线性统计的时候，最后的误差\epsilon主要由m , n决定，m>\frac{\epsilon^{t}-t-1}{(\epsilon t)^{2}}可以描述他们之间的约数关系，其中t=\frac{n}{m}。显然，进度越高，需要的m越大。

线性统计和Bitmap类似，只是节约了部分的内存，但是依旧和基数的最大值正相关，没有完全摆脱O(N_{max})的空间复杂度。

LogLog Counting

为了改善Linear Counting在空间复杂度上的缺点，引进了LogLog Counting，它的流程如下：

• 选取一个哈希函数h，需要满足三点条件：
  1. 哈希碰撞可以忽略不计(碰撞概率非常的低)
  2. h的结果是均匀分布的，即使没有h能够保证完全均匀分布，也需要保证尽可能的均匀分布
  3. 哈希结果的长度是固定的
• 计算第i个元素的哈希值X

• 找到X中第一个出现 1 的位置K，重复上一步的步骤，求出所有元素的X，及其所有的K。最后得出最大的K
• 那么不同的元素的个数为 2^k 个

LogLog Counting桶平均

直接使用一个方法统计基数，容易出现偶然因素，因此LogLog Counting引入了桶分组，可以理解为求数值平均值的方法。具体做法如下：

• 将之前的L位长的哈希值的前m为抽取出来，作为入桶的编号，显然桶的数量为2^m。
• 将前m位相同的数放到同一个桶当中
• 将之后的L-m位作为真正统计的部分，并且为每一个桶计算出第一个出现1的位置，记为p[i]，最后计算出平均值，那么基数的估计值为2^{\frac{1}{m} \sum_{0}^{m-1}p[i]}

最为重要的是，LogLog Counting的空间复杂度为O(Log_{2}Log_{2}(N_{max}))，内存占用少。

频率估计

如何统计数据流当中任意元素的频率也是一个经典得物问题

HashMap

最简单的方法就是使用HasMap，每次来一个元素就进行统计，这种方案在大数据情况下单机无法实现，不过如果可以有多台机器则可以实现统计。具体步骤如下：

• 为了机器的横向扩展性能，所有机器的接入方式采用一致性哈希的方式，这样的话机器集群的可扩展性和稳定性更强
• 对每一个需要统计的元素到来之后，取出前面的m为作为分配到某一台机器的编号(或直接进行取余操作)，达到指定的机器之后再进行统计。
• 需要查询的时候，同样去除前面m位，找到指定的机器再查询

Count-Min Sketch

计算步骤：

• 选定k个哈希函数，开一个k * m的二维数组作为哈希表
• 对于每个元素，分别使用k个哈希函数，计算对应的哈希值，并对m进行取余，随后在二维数组中的对应位置加一，二维数组中的每个值成为sketch
• 要查询某个元素的频率时，只需要取出d个sketch, 返回最小的那一个

Count-Min Sketch算法的优点是省内存，缺点是对于出现次数比较少的元素，准确性很差，因为二维数组相比于原始数据来说还是太小，hash冲突比较严重，导致结果偏差比较大。

Count-Mean-Min Sketch

Count-Min Sketch算法对于低频的元素，结果不太准确，主要是因为hash冲突比较严重，产生了噪音，例如当m=20时，二维数组当中每一行都有1000个数hash到这个20桶，平均每个桶会收到50个数，这50个数的频率重叠在一块了。Count-Mean-Min Sketch 算法做了如下改进：

• 统计阶段和之前的Count-Min Sketch
• 查询某个值的频率的时候，每个hash函数，估算出一个噪音，噪音等于该行所有整数(除了被查询的这个元素)的平均值
• 用该行的 sketch 减去该行的噪音，作为真正的sketch
• 最后返回的是所有行计算完字后的中位数

Top K元素

寻找数据流中出现最频繁的k个元素，也是极为常见的问题，例如搜索引擎的热搜榜，找出访问网站次数最多的前10个IP地址，等等。

HashMap + Heap

最直观的做法就是使用哈希表和小根堆进行统计，具体做法如下：

• 开辟一个大小为k的小根堆，以及一个用于储存频率的哈希表
• 每次从数据流来一个元素，如果在HashMap里已存在，则把对应的计数器增1，如果不存在，则插入，计数器初始化为1
• 在堆里查找该元素，如果找到，把堆里的计数器也增1，并调整堆；如果没有找到，把这个元素的次数跟堆顶元素比较，如果大于堆顶元素的出现次数，则把堆顶元素替换为该元素，并调整堆
• 空间复杂度O(n)。HashMap需要存放下所有元素，需要O(n)的空间，堆需要存放k个元素，需要O(k)的空间，跟O(n)相比可以忽略不急，总的空间复杂度是O(n)
• 时间复杂度O(n)。每次来一个新元素，需要在HashMap里查找一下，需要O(1)的时间；然后要在堆里查找一下，O(k)的时间，有可能需要调堆，又需要O(logk)的时间，总的时间复杂度是O(n(k+logk))，k是常量，所以可以看做是O(n)。

以上的单机做法对于大数据量并不适用，大数据情况下需要借助多机或者使用其他的统计方法来实现。

多机 HashMap + Heap

为了解决单机的缺点，引入了多机场景的HashMap以及小根堆的解决办法：

• 假设有8台机器，第1台机器只处理hash(elem)%8=0的元素，第2台机器只处理hash(elem)%8=1的元素，以此类推
• 每台机器都有一个HashMap和一个小根堆, 各自独立计算出 top k 的元素
• 把每台机器的小根堆，之后汇总到一台机器上，将多个小根堆合并成一个小根堆，就可以计算出总的top k个元素

单机 Count-Min Sketch + Heap

第一种方法当中，HashMap占用的空间过高，因此可以采用之前的Count-Min Sketch或者Count-Mean-Min Sketch来替代HashMap，其他的步骤和第一种方法相同。

• 空间复杂度O(dm)。m是二维数组的列数，d是二维数组的行数，也是选用的哈希函数的数量，堆需要O(k)的空间，不过k通常很小，堆的空间可以忽略不计。
• 时间复杂度O(nlogk)。每次来一个新元素，需要在二维数组里查找一下，需要O(1)的时间；然后要在堆里查找一下，为O(k)的时间复杂度，有可能需要调堆，又需要O(logk)的时间，总的时间复杂度是O(n(k+logk)。k为常数，因此可以认为时间复杂度为O(n)

范围查询

给定一个无限的整数数据流，如何查询在某个范围内的元素出现的总次数？这个问题被认为是 Range Query。

Array of Count-Min Sketches

之前的Count-Min Sketches或者Count-Mean-Min Sketches可以统计每一个元素的频率，那么可否将范围内的每一个元素的频率相加呢？答案是不可以，Count-Min Sketches存在误差，直接进行相加会存在误差累加的问题。因此需要寻求新的方法来解决。

解决的办法就是使用多个“分辨率”不同的Count-Min Sketch。第一个sketch数组的每个格子存放每个元素的频率，第二个sketch数组的每个格子存放两个元素的频率，具体而言，把该统计元素的哈希值直接右移一位，再找到它所在的位置。第三个sketch数组每个位置存放的是四个元素的频率(哈希值直接右移两位)....以此类推，最后一个sketch数组只有两个位置，放置的是哈希值末尾为0或者1的元素。

以下图选用16位最大值为例，需要统计的数据为: [7, 8, 7, 8, 9, 2, 3, 4, 1, 2, 13, 13, 16]，最终每个sketch统计如图所示，同时需要统计[3, 11]范围内的数据个数，那么从sketch4开始看，发现sketch4里没有覆盖一个完整的区间；接着往下找，sketch3当中发现有区间2，以及区间5完全在[3, 11]当中，并且由于区间3, 4和之前的有重复，所以不能统计；最后再看细化的sketch1，直接找到最后没有被覆盖的区间，发现为11。因此最后得到答案为：7+2+1+0=10个元素在[3, 11]之间。

Bloom Filter和Bitmap

布隆过滤器(Bloom Filter)和Bitmap均可以用于当做白名单的统计工具，或者用于查看某些元素是否存在。但是二者存在些许的不一样，个人认为Bitmap更适合准确的统计数值信息 (或者能够将待统计的信息和数值信息一一对应)， 需要提前知道统计数据的最大值。例如数据流的最大值为10^{10}，找出所有重复的数字，此时开一个1.25 GB=10^{10} bit大小的位图数组，每次来一个数就找到对应的位变为1。这样的话所有的额数都可以被精确的统计，缺点就是位图和最大值上限有很大的关系。

布隆过滤器则会出现误判的场景，还是上面的场景，但是数字流变成文本流，此时可以使用hash将文本变为数值，然后在布隆过滤器的位置进行操作，这样的话首先是会存在hash碰撞，尤其是布隆过滤器的大小过小，其次是如果某个元素不在布隆过滤器那么一定不在，如果判断出在其中，则不一定在其中。