海量数据问题

简介

综合转载于:

数据流采样

  • 问题: 在一个无限的整数数据流,如何从中等概率随机抽取 k 个整数出来? — 采样问题

K = 1 时

抽样方法:

  • 当第一个整数到达时,保存该整数
  • 当第二个整数到达时,以 $\frac{1}{2}$ 的概率使用该整数替换第一个整数,以 $\frac{1}{2}$ 的概率丢弃该整数
  • 当第 i 个整数到达时,以 $\frac{1}{i}$ 的概率使用第 i 个整数替换被选中的整数, 以 $1 - \frac{1}{i}$ 的概率丢弃 第i个整数

归纳法 - 验证分析

  • n = 1 时, 被选中的概率为 100%, 成立
  • 设 $n = m , m \ge 1$ 时,命题成立,即前 m 个数,每一个被选中的概率为 $\frac{1}{m}$
  • 当 $ n = m + 1 $ 时, 第 m + 1 个数被选中的概率为 $\frac{1}{m+1}$, 前 m 个数被选中的概率为 $\frac{1}{m} * (1-\frac{1}{m+1}) = \frac{1}{m+1}$ , 成立。

K > 1 时

抽样方法

  • 前 k 个整数到达时,全部保留
  • 第 i 个整数到达时, 以 $\frac{k}{i}$ 的概率替换 k 个数中的某一个,以 $1-\frac{k}{i} $ 丢弃

归纳法 - 验证分析

  • $n \le k$ 时, 被选中的概率为100%, 成立

  • 假设 $n = m, m > k$ 时, 你命题成立, 即前m 个数, 每一个被选中的概率为 $\frac{1}{m}$

  • 当 $ n = m + 1 $ 时, 第 m+1 个数被选中的概率为 $\frac{k}{m+1}$, 前 m 个数被选中的概率为:

基数统计

  • 题目: 计算一个数据流中不同元素的个数?

1. HashSet

采用 hashet,不断加入, 最终的hashset大小就是所求答案。 缺点: 单机内存存不下

2. bitmap

  • 前提: 假设已经知道不同元素的个数的上限,假设为 N

我们可以建立一个长度为N的 bit 数组, 每个元素与 bit 数组的某一位一一对应, 该位为1,则表示此元素在集合中,为 0 表示不再集合中,最终的答案为 bitmap 中1的个数。

  • 缺点: bitmap 与实际情况下不同元素的个数无关,而与不同元素的个数上限有关。

3. Linear Counting

基本思路:

  • 选择一个哈希函数 h, 其结果服从均匀分布
  • 开一个长度为 m 的bitmap,初始化为 0
  • 数据流每来一个元素,计算哈希值并对m取模,然后将该位置置1
  • 最后,若 bitmap 中还有 u 个bit 为 0, 则不同元素的总数近似为 $-m log\frac{u}{m}$

m的选择

对于 bitmap 长度的选择,主要由两个因素决定:基数大小以及容许的误差。 假设基数大小大约为n, 允许误差大约为 $\epsilon$, 则 m 需要满足如下约束:

4. Loglog Counting

基本思路:

  • 均匀随机化。 选择哈希函数 h 的几大条件:
    • h 应该尽可能减少冲突
    • h 的结果是几乎服从均匀分布的。
    • 哈希后的结果是固定长度的。
  • 对于每个元素,计算出哈希值,每个哈希值是等长的,长度为 L

5. HyperLogLog Counting

频率估计

  • 题目: 计算数据流中任意元素的出现的次数

1. HashMap

  • 用 HashMap 来记录每个元素出现的次数。
  • 缺点: 占用内存大,单机内存无法存下这个巨大的 HashMap

2. 数据分片 + HashMap

假设有 n 台机器, 那么每台机器都有一个HashMap, 第 i 台处理 hash(elem) % n == i-1的元素。

查询时, 先计算元素在哪台机器上,然后去那台机器上的HashMap读取。

3. Count-Min Sketch

  • 选定 d 个哈希函数, 并建立一个 d * m 的二维整数数组作为哈希表
  • 对于每个元素,分别使用 d 个hash 函数计算相应哈希值,并对 m 取余,然后在对应的位置上增1,二维数组中的每个整数称为 sketch。
  • 对于要查询的元素,取出 d 个sketch, 返回最小的哪一个。(d 个sketch 都是该元素的近似频率,返回任意一个均可)

优点: 省内存;

缺点:对于出现次数较少的元素,准确性很差。主要是由于 hash 冲突比较严重

4. Count-Mean-Min Sketch

对 Count-Min Sketch 做了改进。

  • 来了一个查询,按照 Count-Min Sketch 的正常流程,取出它的d个sketch
  • 对于每个hash函数,估算一个噪音 = 该行所有整数(除了被查询的这个元素)的平均值
  • 真正的sketch = 该行的sketch - 该行的噪音
  • 返回 d 个sketch 的中位数

Top k

  • 有1亿个浮点数,如果找出最大的10000个?

1. 直接

最容易想到的方法是将数据全部排序,然后在排序后的集合中进行查找,最快的排序算法的时间复杂度一般为O(nlogn),如快速排序。但是在32位的机器上,每个float类型占4个字节,1亿个浮点数就要占用400MB的存储空间,对于一些可用内存小于400M的计算机而言,很显然是不能一次将全部数据读入内存进行排序的。其实即使内存能够满足要求(我机器内存都是8GB),该方法也并不高效,因为题目的目的是寻找出最大的10000个数即可,而排序却是将所有的元素都排序了,做了很多的无用功。

2. 局部淘汰法

该方法与排序方法类似,用一个容器保存前10000个数,然后将剩余的所有数字——与容器内的最小数字相比,如果所有后续的元素都比容器内的10000个数还小,那么容器内这个10000个数就是最大10000个数。如果某一后续元素比容器内最小数字大,则删掉容器内最小元素,并将该元素插入容器,最后遍历完这1亿个数,得到的结果容器中保存的数即为最终结果了。此时的时间复杂度为O(n+m^2),其中m为容器的大小,即10000。

3. 分治法

将1亿个数据分成100份,每份100万个数据,找到每份数据中最大的10000个,最后在剩下的100*10000个数据里面找出最大的10000个。如果100万数据选择足够理想,那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的10000个数据的方法如下:用快速排序的方法,将数据分为2堆,如果大的那堆个数N大于10000个,继续对大堆快速排序一次分成2堆,如果大的那堆个数N大于10000个,继续对大堆快速排序一次分成2堆,如果大堆个数N小于10000个,就在小的那堆里面快速排序一次,找第10000-n大的数字;递归以上过程,就可以找到第1w大的数。参考上面的找出第1w大数字,就可以类似的方法找到前10000大数字了。此种方法需要每次的内存空间为10^6*4=4MB,一共需要101次这样的比较。

4. Hash

如果这1亿个书里面有很多重复的数,先通过Hash法,把这1亿个数字去重复,这样如果重复率很高的话,会减少很大的内存用量,从而缩小运算空间,然后通过分治法或最小堆法查找最大的10000个数。

5. 最小堆

首先读入前10000个数来创建大小为10000的最小堆,建堆的时间复杂度为O(mlogm)(m为数组的大小即为10000),然后遍历后续的数字,并于堆顶(最小)数字进行比较。如果比最小的数小,则继续读取后续数字;如果比堆顶数字大,则替换堆顶元素并重新调整堆为最小堆。整个过程直至1亿个数全部遍历完为止。然后按照中序遍历的方式输出当前堆中的所有10000个数字。该算法的时间复杂度为O(nmlogm),空间复杂度是10000(常数)。

时间复杂度取决于建堆是插入建的O(nmlogm),还是bottom-up建的(O(nlogm))。

实际运行:单机+单核+足够大内存

如果需要查找10亿个查询次(每个占8B)中出现频率最高的10个,考虑到每个查询词占8B,则10亿个查询次所需的内存大约是10^9 * 8B=8GB内存。如果有这么大内存,直接在内存中对查询次进行排序,顺序遍历找出10个出现频率最大的即可。这种方法简单快速,使用。然后,也可以先用HashMap求出每个词出现的频率,然后求出频率最大的10个词。

实际运行:单机+多核+足够大内存

这时可以直接在内存总使用Hash方法将数据划分成n个partition,每个partition交给一个线程处理,线程的处理逻辑同(1)类似,最后一个线程将结果归并。

该方法存在一个瓶颈会明显影响效率,即数据倾斜。每个线程的处理速度可能不同,快的线程需要等待慢的线程,最终的处理速度取决于慢的线程。而针对此问题,解决的方法是,将数据划分成c×n个partition(c>1),每个线程处理完当前partition后主动取下一个partition继续处理,知道所有数据处理完毕,最后由一个线程进行归并。

实际运行:单机+单核+受限内存

这种情况下,需要将原数据文件切割成一个一个小文件,如次啊用hash(x)%M,将原文件中的数据切割成M小文件,如果小文件仍大于内存大小,继续采用Hash的方法对数据文件进行分割,知道每个小文件小于内存大小,这样每个文件可放到内存中处理。采用(1)的方法依次处理每个小文件。

实际运行:多机+受限内存

这种情况,为了合理利用多台机器的资源,可将数据分发到多台机器上,每台机器采用(3)中的策略解决本地的数据。可采用hash+socket方法进行数据分发。

实际运行:MapReduce

从实际应用的角度考虑,(1)(2)(3)(4)方案并不可行,因为在大规模数据处理环境下,作业效率并不是首要考虑的问题,算法的扩展性和容错性才是首要考虑的。算法应该具有良好的扩展性,以便数据量进一步加大(随着业务的发展,数据量加大是必然的)时,在不修改算法框架的前提下,可达到近似的线性比;算法应该具有容错性,即当前某个文件处理失败后,能自动将其交给另外一个线程继续处理,而不是从头开始处理。

top K问题很适合采用MapReduce框架解决,用户只需编写一个Map函数和两个Reduce 函数,然后提交到Hadoop(采用Mapchain和Reducechain)上即可解决该问题。具体而言,就是首先根据数据值或者把数据hash(MD5)后的值按照范围划分到不同的机器上,最好可以让数据划分后一次读入内存,这样不同的机器负责处理不同的数值范围,实际上就是Map。得到结果后,各个机器只需拿出各自出现次数最多的前N个数据,然后汇总,选出所有的数据中出现次数最多的前N个数据,这实际上就是Reduce过程。对于Map函数,采用Hash算法,将Hash值相同的数据交给同一个Reduce task;对于第一个Reduce函数,采用HashMap统计出每个词出现的频率,对于第二个Reduce 函数,统计所有Reduce task,输出数据中的top K即可。

直接将数据均分到不同的机器上进行处理是无法得到正确的结果的。因为一个数据可能被均分到不同的机器上,而另一个则可能完全聚集到一个机器上,同时还可能存在具有相同数目的数据。

题目变形

  1. 有10000000个记录,这些查询串的重复度比较高,如果除去重复后,不超过3000000个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。请统计最热门的10个查询串,要求使用的内存不能超过1GB。

  2. 有10个文件,每个文件1GB,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。按照query的频度排序。

  3. 有一个1GB大小的文件,里面的每一行是一个词,词的大小不超过16个字节,内存限制大小是1MB。返回频数最高的100个词。

  4. 提取某日访问网站次数最多的那个IP。

  5. 10亿个整数找出重复次数最多的100个整数。

  6. 搜索的输入信息是一个字符串,统计300万条输入信息中最热门的前10条,每次输入的一个字符串为不超过255B,内存使用只有1GB。

  7. 有1000万个身份证号以及他们对应的数据,身份证号可能重复,找出出现次数最多的身份证号。

Heavy Hitters

  • 题目: 寻找数据流中出现最频繁的 k 个元素?

1. HashMap + Heap

用一个 HashMap存放所有元素出现的次数,用一个小根堆,容量为k,存放目前出现过的最频繁的 k 个元素:

  • 元素过来时,更新 HashMap, 并且在堆中查找该元素,如果找到,则+1并调整堆; 如果没有找到,则将该元素次数与堆顶元素比较,如果大于,则把堆顶元素替换为该元素,并调整堆。
  • 时间复杂度为 $O(n (k + logk))$, 空间复杂度为 $O(n)$

2. 多机 HashMap + Heap

  • 将数据分片, 第 i 台机器只处理 $hash(elem) % n == i-1$ 的元素
  • 每台机器都有一个 HashMap 和 Heap, 格子计算出 top k 元素
  • 将每台机器的 Heap, 通过网络汇总到一台机器上,并将多个Heap合成一个 Heap

3. Count-Min Sketch + Heap

4. Lossy Counting

5. SpaceSaving

范围查询

  • 题目:给定一个无限的整数数据流,如何查询在某个范围内的元素出现的总次数?

1. Array of Count-Min Sketches

成员查询 - Bloom Filter

  • 题目:给定一个无限的数据流和一个有限集合,如何判断数据流中的元素是否在这个集合中?

布隆过滤器本质上是二进制向量 + 一系列随机映射函数, 主要用于检测某元素是否在一个集合中。

  • 优点: 空间效率和查询时间都远远超过一般的算法

布隆过滤器原理

  • 加入元素:当一个元素被加入到集合时,通过 K 个哈希函数将这个元素映射成一个位数组中的K个点,把它们置为1。
  • 检索元素:查看对应的 K 个点是否都为1 : 如果存在任意一个为 0, 被检元素一定不在; 如果都为1,则很可能存在。

布隆过滤器与Bitmap 区别

布隆过滤器使用了 k 个哈希函数,每个元素对应 k 个bit,从而降低了冲突的概率

布隆过滤器缺点

  • 存在误判:即可能要查找的元素不在容器内,但 k 个位置上都是 1
  • 删除困难:一旦删除元素,不能简单将对应 k 个位置置为 0

布隆过滤器实现

假设要存的数据量为n, 期望的误判率为 fpp,我们需要计算 Bit 数组的大小 m, hash 函数的个数 k,并选择合适的哈希函数。

  • Bit 数组大小选择:
  • 哈希函数选择:
一分一毛,也是心意。