海量数据处理技巧

大家好，又见面了，我是你们的朋友全栈君。

数据时代来临，数据量的爆炸式增长是最为显著的特征。当高性能硬件的普及还跟不上这样的数据大潮时，如何在有限的时空资源内处理海量数据成为了计算机科学以及数理统计等领域最大的挑战。

所谓“数据处理”，在本文中特指通过计算机技术，对海量数据进行存储、统计、查询等操作。我将在下面介绍一些基本的海量数据处理的方法，供大家参考。需要明确的一点是，现实情况复杂多变，所以对于海量数据处理这样大的主题，是不可能用一篇博客就说清楚的。但方法论可以一通百通，我们通过一些已经被无数次实验证明有效的方法，就能大致理解对此类问题的解决思路，之后在面临新的问题时，至少能找到一个大致的方向。

1. 海量数据处理的困难

海量数据处理的困难用一句话概括，就是时空资源不够。具体来说，

• 时间受限：无法在有限时间内，完成针对海量数据的某项处理工作；
• 空间受限：无法将海量数据一次性读入内存

对于时间受限的问题，我们一般的解决办法是高效的算法配合恰当的数据结构，比如哈希表，Bloom Filter，堆，倒排索引，tire树）；而对于空间受限的问题，一般的解决办法是“大而化小，分而治之”的策略，既然一次性行不通，那就一部分一部分读，每读入一部分可以生成一个小文件，小文件是可以直接读入内存的，我们这样分割大数据之后，再依次处理小文件的数据。

注意，本文我只介绍对于海量数据执行一些简单的数据处理（比如存储，查重，排序，统计数量等）时的一些通用的方法，至于更复杂的计算，涉及具体算法性能层面的东西，由于世界上算法以千万记，面对不同情况，又有着无数变形，所以不可能总结出来。

2. 海量数据处理方法归纳

July的博客 教你如何迅速秒杀掉：99%的海量数据处理面试题 对海量数据处理的方法进行了细致的总结，这篇文章写的非常全面，建议大家一读。但我读完之后，窃以为许多问题和解决思路有所重复，没必要全部都详细探究。为了理清思路、抓重点，我将那篇文章中涉及的问题以及相应方法更加简化地总结为如下7点。

2.1 哈希映射 + 统计 + 排序

解决问题：海量数据不能一次性读入内存，而我们需要对海量数据进行的计数、排序等操作
使用工具：hash函数（hash表）；堆

这种方法是典型的“分而治之”的策略，也是解决空间限制最常用的方法。基本思路可以用下图表示。先借助哈希算法，计算每一条数据的hash值，按照hash值将海量数据分布存储到多个桶中（所谓桶，一般可以用小文件实现）。根据hash函数的唯一性，相同的数据一定在同一个桶中。如此，我们再依次处理这些小文件，最后做合并运算即可（有点类似于Map-Reduce的思想）。

注：一般用hash函数将数据映射到桶的方法是：

$$\begin{equation}bucket_{ID} = H(m_i)~~ \%~~ n\end{equation}$$

其中$m_i$为第$i$条数据，bucket_ID为桶标号，n为要设置的桶数量。关于桶数量（即小文件数量）设置的基本的原则是：每个小文件的大小比内存限制要小。比如处理1G的大文件，内存限制为1M，那就可以把大文件分成2000个小文件（甚至更多），这样每个小文件的大小约500K（甚至更小），我们就可以轻松读入内存处理了。下面看一些具体的例子：

问题1 top-k筛选：海量数据存储于多个文件，任何一条数据都可能存在于任何一个文件当中，现需要筛选出现的次数最多的$k$条数据。
解决思路：

• 依次遍历这些文件，通过hash映射，将每个文件的每条数据映射到新构造的多个小文件中（设生成了$n$个小文件）；
• 依次统计每个小文件中出现次数最多的$k$条数据，构成hash表，hash表中每个键值对的形式为 dataItem: count；
• 利用堆排序，依次遍历这些hash表，在$n * k$条数据中，找出count值最大的$k$个；

这里之所以使用堆排序，也是为了能尽可能地提高排序效率。就上例而言，堆排序的时间复杂度为$nk \log(k)$

问题2 对比查重：现有A和B两个大文件，每个文件都存储着海量数据，要求给出A，B中重复的数据。
解决思路：

• 遍历A中的所有数据，通过hash映射将他们分布存储在$n$个小文件中，记为$\{a_1, a_2, \dots, a_n\}$；
• 遍历B中的所有数据，通过hash映射将他们分布存储在$n$个小文件中，记为$\{b_1, b_2, \dots, b_n\}$；
• 根据hash函数性质可知，A和B中的相同数据一定被映射到序号相同的小文件，所以我们依次比较$\{a_i, b_i\}$即可；
• 如果问题更进一步，要求返回重复次数最多的$k$条数据，则可以将对比小文件找到的数据存入hash表，键为数据，值为该数据出现的次数。再用大小为$k$的堆，排序找出即可。

2.2 Trie树处理海量字符串数据

解决问题：当需要处理的是海量字符串数据时，有时Trie树会比直接上面说的hash映射的策略更高效。
使用工具：Trie树；堆

Trie树是一种非常强大的处理海量字符串数据的工具。尤其是大量的字符串数据中存在前缀时，Trie树特别好用。Trie树在字典的存储，字符串的查找，求取海量字符串的公共前缀，以及字符串统计等方面发挥着重要的作用。用于存储时，Trie树因为不重复存储公共前缀，节省了大量的存储空间；用于以字符串的查找时，Trie树依靠其特殊的性质，实现了在任意数据量的字符串集合中都能以$O(len)$的时间复杂度完成查找（$len$为要检索的字符串长度）；在字符串统计中，Trie树能够快速记录每个字符串出现的次数。下面看几个问题实例。

注：有关Trie树的详细讲解可以参考我之前的博客 Trie树的构建和应用

问题3 数据去重：一个超大文件（不能直接读入内存），里面包含海量字符串数据，但字符串数据种类有限（可见含有大量重复），现需要对字符串去重。并统计去重后每个字符串出现的次数
解决思路：

• 将大文件分割成多个小文件，依次遍历每个小文件，读取其中存储的每一个字符串，构建Trie树，并在每一个终止节点记录该节点代表的字符串（即从根节点到该节点的字符组成的字符串）当前出现的次数，解决问题的时间复杂度为$O(N * len)$，其中$N$为字符串总数，$len$为字符串的平均长度；

• 如果问题更进一步，需要排序，那就再建一个堆，读取Trie树，将字符串依次插入堆，时间复杂度为$O(N' * len * \log N')$，其中$N'$是去重后字符串的数量；

至于Trie树在存储，求取公共前缀等方面的应用可以参考我上面给出的博客，这里不再赘述。

总结一下，Trie树对于海量字符串数据，在数据种类有限（构建的Trie树可以完全读入内存）时，能够使我们轻松的进行存储，查找，计数等工作。

2.3 Bloom Filter

解决问题：数据字典的构建；判定目标数据是否存在于一个海量数据集；集合求交
使用工具：Bloom Filter；hash函数

以存在性判定为例，Bloom Filter通过对目标数据的映射，能够以$O(k)$的时间复杂度判定目标数据的存在性，其中$k$为使用的hash函数个数。这样就能大大缩减遍历查找所需的时间。

注：有关Bloom Filter树的详细讲解可以参考我之前的博客 Bloom Filter原理与实现，下面我假设你已经知道了Bloom Filter的工作原理。直接看问题4：

问题4 集合求交：与上面的问题2类似，只不过现在不是A和B两个大文件，而是A, B, C, D….多个大文件。
解决思路：

• 依次遍历每个大文件中的每条数据，遍历每条数据时，都将它插入Bloom Filter；
• 如果已经存在，则在另外的集合（记为$S$）中记录下来；

• 如果不存在，则插入Bloom Filter；
• 最后，得到的$S$即为所有这些大文件中元素的交

问题5 unsigned int型整数存在性判定：判定一个unsigned int型整数是否在一个大的unsigned int型整数数据集中。
解决思路：

• 假设unsigned int型整数数据集长度为$N$，则申请一个大小为512M的数组作为Bloom Filter；
• 遍历数据集，按照遍历到的整数（记为$a$）将Bloom Filter的第$a$位变成1；
• 检查Bloom Filter中，目标数据所代表的位是0还是1；

问题5用的其实是一种简化了的Bloom Filter，不再采取hash映射的方式，而是直接根据整数的大小确定要改变的位数，这在某些特殊情况下（比如数据种类不多时）非常有效。

2.4 多层桶结构

解决问题：海量数据求取第$k$大数
使用工具：hash函数

多层桶结构其实和最开始我们用hash映射分割大文件的思路是一致的，都是一种“分而治之”的策略。只不过多层桶结构是对有些桶分割之后再分割，构成了一种层次化的结构，它主要应用于一次分割的结果依然不能解决内存限制的情况。比如下面的问题6：

问题6 求取海量整数的中位数。
解决思路：

• 依次遍历整数，按照其大小将他们分拣到$n$个桶中。但是现在出现了一种不好的情况，就是可能有的桶数据量很小，有的则数据量很大，大到内存放不下了；
  • 对于那些太大的桶，我们就再分割成更小的桶，当然分割的准则还是依据数据大小，这样，其实是构成了一种类似于不平衡的多叉树的结构；
  • 根据多叉树第一层的数量统计结果，我们可以知道中位数在哪个节点中，如果该节点还有孩子，就判断在其哪个孩子节点中，直到找到叶子节点，最后找出目标。

  • 2.5 倒排索引

    这个不详细说了，在文档数据的检索，尤其是关键字查询领域有着极为广泛的应用。其实这个思路也可以推广开来，当存在海量的文件，且每个文件包含的数据种类有限，而我们的任务又是依据数据查文件时，倒排索引都可以排上用场。

    2.6 外排序

    解决问题：海量数据的排序
    实用工具：归并算法

    外排序是经典的排序方法之一，主要是针对大数据不能直接读入内存的情况，通过内存与外存之间的数据交换，实现海量数据排序的。我大致介绍一下外排序的算法思路，详细的解释可以参照博客：排序之外部排序

    问题7 海量数据排序。
    解决思路：

    • 依次读取数据，将数据按照大小范围，生成一定数量的“归并段”并写入外存，注意归并段中的数据是排好序的；
    • 对归并段执行归并排序，每两个归并段排序之后的结果作为新的归并段写入外存；
    • 重复执行上一步，知道完全排序完毕，最终的排序结果会存在外存中；

    2.7 MapReduce

    MapReduce是一种计算模型，分为”Map”和”Reduce”两个阶段。

    • Map：将大量数据分割后（或者将困难任务分解后）“各个击破”；
    • Reduce：将“各个击破”的结果按照一定的规律进行合并操作；

    这样做的好处是可以在任务被分解后，可以通过大量机器进行并行计算，从而突破时间或者空间的限制。时间上显然更快，空间上，单个机器只需要处理空间允许的数据量即可。举个简单的例子就是归并排序，我们先将数据集分割成小数据集，使用多个机器排序每个分割后的小数据集（Map），再将处理好的归并段依次归并（Reduce）。

    本文求尽量全面总结海量数据处理的思路，不求对每种思路的深入探讨。因为这些方法要么在我之前的博客中已有详细说明，要么比较通用，网上的介绍很充分。

    不得不说海量数据处理时，面临的问题是千变万化的，所以本文也会持续更新，希望读者们也能不断补充我遗漏的知识。