海量数据处理的几个思路

基本单位

应该知道的几个基本转换单位：

• 2¹⁰ = 1024 ≈ 10³
• 1 亿 = 10⁸（8 个零）

• 1 byte = 2³ bit = 8 bit

• 1 KB = 2¹⁰ byte = 1024 byte ≈ 10³ byte
• 1 MB = 2¹⁰ KB = 2²⁰ byte ≈ 10⁶ byte
• 1 GB = 2¹⁰ MB = 2²⁰ KB = 2³⁰ byte ≈ 10⁹ byte
• 1 GB ≈ 10 亿 byte

整数范围是 0 ~ 2³²，2³² ≈ 4 * 10⁹ = 40 亿，如果用 bit 位来表示整数范围，大概需要 2³² bit = 1/2 * 2³³ bit = 0.5 GB = 512 MB 大小。

1 个整数一般占用 4 byte，一亿个整数大概占用 4 * 10⁸ ≈ 0.4 GB ≈ 400 MB 大小。

海量数据类型

海量数据处理一般有以下几种：

• 对海量数据排序
• 海量数据中求 TopK
• 海量数据求中位数、第 K 大元素
• 判断一个数在海量数据中是否存在

海量数据的处理方法

海量数据处理主要是要解决单机内存不足，时间复杂度太高的问题，解决这类问题主要有以下几种方法：

• 分治思想。将数据拆分到多个文件或多台机器上分别处理，然后再合并求解：hash 分片取模，快速排序，归并排序
• 双位图、双堆
• 布隆过滤/ 位图
• Trie 树 / B+ 树索引 / 倒排索引
• 外排序
• 分布式处理 Hadoop/ Mapreduce

海量数据判重

问题

判断一个数在海量数据中是否存在？这个数可能是字符串，也可能是整数

使用 HashSet

判断一个数据是否存在，可以使用 HashSet 在 O(1) 的时间复杂度内判断。对于海量数据，不可能一次性加载进内存中构造 HashSet，那么可以将数据分拆到多台机器上，分别构造 HashSet。

数据的拆分可以使用范围拆分，也可以使用哈希取模拆分。哈希取模可以使相同的数散落到相同的机器上，对海量数据起到了去重的作用，节省内存。

判断一个数是否存在，就需要多台机器同时判断，最后给出结果。

使用 BitMap

如果海量数据是整数，那么可以使用一个 2³² 个 bit 位表示整数的范围，当然如果事前知道整个数据的范围大小，可以视情况确定使用的 bit 位个数。每个整数就对应 bit 数组的下标，每个 bit 位只能存储 0 或 1。

处理思路：遍历所有的整数，将出现的整数对应的比特数组下标对应的值置为 1，最后检查需要判断的那个数的下标对应的值是否为 1，就可以确定这个数是否存在。

如果要判断一个数在海量数据中是否有重复？

这时候一个 bit 位数组就无法判断了，需要使用 2-bitmap 实现。思路：遍历海量数据，将整数散落到第一个 bit 数组的下标，数组置为 1，如果遇到一个重复的数，发现第一个 bit 数组对应的位已经是 1，那么将第二个 bit 数组对应的位置为 1。因此，两个 bit 数组可以表示三种情况：00 - 对应的位置不存在；10 - 整数只出现一次；11 - 整数出现两次以上。

检查一个数是否重复，需要同时检查两个 bit 数组对应的位，如果是 11，说明是重复数组。

一个 2³² 个 bit 位的数组大概占用 512 MB 内存大小，因此在单机上就可以处理。

使用布隆过滤器

布隆过滤器的原理：将一个数经过 k 个 hash 函数运算，计算出 k 个不同的哈希值，然后将哈希值对应 bitmap 数组下标的位置置为 1。在查找时，也进行同样的操作，如果判断 k 个位置的值都为 1，就表示这个数据存在。

又以上原理可知，布隆过滤器可能存在误判，如果判断一个数存在，那么有可能不存在，但是如果判断出这个数不存在（有个别位置数值为 0），那么就肯定不存在的。

布隆过滤器用于对数据判断要求不高的场景，可以容忍一定的误判率。

Trie 树

Trie 树针对字符串数据，根节点不存储数据，将字符串拆分成一个个字符构造成一个字典树，因为用来表示字符串的字符个数有限，所以 Trie 树的高度不会很高，占用的内存也不会很大。

查找一个字符串数据是否存在的处理思路如下：

遍历这个字符串，针对每个字符去 Trie 树中从上往下匹配，如果每个字符在 Trie 树的一条路径中都能匹配，那么这个字符串就是存在的。

海量数据排序

外部排序

由于海量数据不能一次性读入内存中，需要对数据进行拆分，可以拆分成多个小文件或者拆分到多台机器中。然后对拆分的数据分别进行快速排序，最后对数据进行合并。

假设拆分成了 100 个小文件，并分别进行了排序，需要合并成一个有序的大文件，合并有两种方案：

方案一：

从这 100 个小文件中各取第一个字符串，放入数组中，然后比较大小，找出最小值，把最小的字符串放入合并后的大文件中，并将这个最小字符串从数组中删除，然后从这个最小字符串的来源文件中取第二个字符串放入数组中，再次找出最小值追加放入到大文件中。依次类推，直到所有的文件中的数据都放入到大文件中。

方案二：

这里用数组来存储每个字符串并找出最小值，每次都要遍历整个数组，显然不是很高效。这里可以用到优先级队列：维护一个小顶堆，堆顶的元素就是存储的最小字符串，每次只需要取出堆顶的元素放入到大文件中，然后再从小文件中取出下一个字符串插入到堆中，循环这个过程，就可以依次将所有的字符串有序的添加到大文件中。

在数组中找出最小值的时间复杂度为 O(n)，而往堆中插入或删除一个元素的时间复杂度为 O(logn)，所以，第二种方案会更高效。

BitMap

如果海量数据不存在重复数，那么可以使用 BitMap 进行排序，遍历一遍所有数据，将数据对应的 bit 数组的下标置为 1。最后从头遍历 bit 数组，就得到了排序后的数据。

如果存在重复的数据，那么可以申请多个 bit 数组，比如：2 个 bit 数组一个位最大是 11，最大可以表示 3 次重复的数。3 个 bit 数组最大是 111，最大可以表示 7 次重复的数。

此外还可以使用桶排序和计数排序对海量数据进行排序。

Trie 树

如果海量数据是字符串，可以使用 Trie 树来完成排序操作：

先读入海量数据字符串数据构建一个 Trie 树，最后按字典序先序遍历就能得到已排序的数据。为了处理数据重复的问题，可以使用 Trie 树的节点存储计数信息。

海量数据求 TopK

排序求 TopK

可以利用海量数据排序的几个方法，最后取出前 K 个大小的数据。

这种方法效率上不太高，而且比较浪费内存。

小顶堆求 TopK

如果海量数据在同一台机器中：

那么可以直接维护一个 K 大小的小顶堆，遍历数据插入到堆中（这里不需要将所有数据一次性加载进内存，而是分批加载），每次数据和堆顶元素比较大小，如果大于堆顶元素，那么将数据插入到堆中，然后删除堆顶元素，如果数据小于堆顶元素，则直接丢弃。最后留下来的 K 个数就是 TopK 元素。

如果海量数据分布在多台机器上：

如果每个数据是唯一的，而且只出现在一台机器中，那么可以对每台机器分别求 TopK，最后将每台机器的 TopK 再组合起来求一次 TopK。

如果数据有重复，且分布在多台机器上，则需要将相同的数据都散落到同一台机器中：遍历一遍所有数据，对每个数据进行哈希取模，然后统计每台数据的 TopK，最终组合所有的 TopK 找出最终的 TopK。

案例

https://blog.csdn.net/v_JULY_v/article/details/6279498

 

关注微信公众账号「曹当家的」，订阅最新文章推送