海量数据处理

发表于 更新于 分类于
本文字数： 3.4k 阅读时长 ≈ 3 分钟
海量数据优化。

海量数据处理

一. 简述

二. 常见方案

  • Hash方法
  • Bitmap方法
  • Bloom filter方法
  • 数据库优化
  • 倒排索引
  • 外排序
  • Trie树
  • 堆
  • 双层桶
  • MapReduce

2.1 Hash

详细内容：《散列表》

Hash方法用来快速存取，因为其查找时间复杂度为 O(1) ，可以用来统计海量数据和分类等。

2.2 Bitmap

Bitmap即位图，使用位数组来表示某些元素是否存在。适用于海量数据的快速查找、判重和删除等。

生成一个N位长的二进制串，假设集合为{2, 7, 4, 9, 1, 10}，则为10位的串，将值对应下标设置为1，结果为：1101001011，因为数组下标本身有序，所以最终相当于做了一次排序（时间复杂度为O(n)，以空间N换时间，并且要提前直到数组中取值范围）。

2.3 Bloom Filter

判断元素是否存在于一个集合中，常规做法需要存储所有元素然后再进行比较查找，比如拦截垃圾邮件的功能，需要记录发送垃圾邮件的地址，假设发送者不断注册随机地址，每个地址需要16B，一亿个地址就需要1.6GB左右的空间。

Bloom Filter：

  • 可以用来检测一个元素是否属于某个集合。
  • 结合了位图与散列函数，牺牲准确率来换取空间和时间效率的提高，判断不属于时绝对准确，但判断属于时则未必准确。
  • 初始化为一个m位的位数组，定义k个不同的散列函数能把集合元素映射到位数组，当向集合中插入元素时，根据k个散列函数得到k个位，将这些位置为1。当需要查询元素是否属于集合时，只要根据散列函数计算出其对应的k个位，并判断：如果有任一位不为1就可以判断元素不在该集合；全为1则可能在集合中。
  • 如何根据输入元素个数n，来确定位数组m的大小和Hash函数。k = (ln2) * (m/n) 时错误率最小，要求错误率不大于E时，m至少要等于 n * lg(1/E) 才能表示任意n个元素的集合。但m仍要取更大一些，因为要保证位数组至少一半为0，所以应该 m >= nlg(1/E) * lgE ，大概就是nlg(1/E)的1.44倍。

Bloom Filter只能判断插入元素，删除元素则会影响多个元素的检测。可以通过扩展方法支持元素的删除操作：

  • CBF（Counting Bloom Filter）将位数组的位扩展为Counter
  • SBF（Spectral Bloom Filter）用counter中的最小值近似表示集合元素出现的次数。

2.4 数据库优化

  1. 数据分区：减少需要处理的数据规模。
  2. 索引：正确的构建索引，大表索引本身比较占物理空间，创建和维护都比较耗费时间，要考虑索引的填充因子和聚集非聚集。
  3. 批处理：对数据进行切分，最后将结果合并。
  4. 临时表或中间表：大表变小表，保留中间数据。
  5. ……

2.5 倒排索引

倒排索引也叫反向索引，用来存储在全文搜索下某个单词在一个或一组文档的位置。

分类：

  • 一条记录的水平反向索引包含每个引用单词的文档的列表。
  • 一个单词的水平反向索引又包含每个单词在一个文档中的位置。

假设有文本内容：

1
2
3
D1: The GDP increased
D2: The text is this
D3: My name is

倒排索引：

  • The：D1，D2
  • GDP：D1
  • increased：D1
  • text：D2
  • is：D2，D3
  • name：D3
  • …

正向索引为文档到单词，反向则是单词到文档。在处理复杂的多关键字查询时，反向索引可以先完成查询的交、并逻辑运算，再对记录进行存取，把对记录的查询转换为对地址集合的查询。一般多应用于文档检索系统，常见的关系型数据库中的全文索引就是倒排索引。

2.6 外排序

待排序元素数目较多，无法一次放入内存时，需要以文件的形式存放于外存，排序时分批调入内存处理。适用于大数据的排序和去重，效率很低且消耗大量I/O。

一般采用归并排序来实现：

  1. 生成若干初始归并段，文件预处理。
  2. 把含有n个记录的文件，按内存大小划分为若干长度为L的子文件，分别将子文件调入内存，排序后送回外存。
  3. 进行多路归并，将初始段进行多遍归并，最后形成整个文件的单一归并段。

2.7 Trie树

Trie树，又叫字典树或键树。用于快速字符串检索的多叉树结构，统计和排序大量的字符串，原理是利用字符串的公共前缀来减少时空开销，可以减少无谓的字符串比较，查询效率高于散列表。

基本特性：

  • 根节点不包含字符，除根节点外都只包含一个字符。
  • 从根节点到某一阶段，路径上经过的字符串连接起来构成对应的字符串。
  • 每个节点的所有子节点包含的字符都不相同。

该结构重复度高比较消耗内存，当公共前缀率较低时不建议使用该方案。

2.8 堆

采用堆的数据结构，只需扫描一遍就可以得到所有前n元素，适合海量的数据处理。

求海量数据中前n大/小的值中位数：

堆类型 作用
最大堆 求前n小
最小堆 求前n大
双堆 中位数

2.9 双层桶

桶排序的思想是把[0, 1)划分为n个大小相同的子区间，每个子区间代表一个桶，将n个记录分配到各个桶中。关键字均匀分布在各个桶中，对关键字进行插入排序，将各非空桶中的记录连接起来。

桶排序的平均时间复杂度为 O(n) ，最坏情况为 O(n^2^) ，只适用于关键字取值范围小的情况，否则所需桶数目过多会浪费空间和计算时间。适合于寻找第K大的数、寻找中位数、寻找不重复或重复的数字等。

2.10 MapReduce

MapReduce常用于云计算技术，是一种并行计算的分布式编程模型，支持大型分布式集群系统在大数据集上工作。

核心操作是：

  • Map：映射，把一组键值对映射为一组新的键值对，通过Map程序将数据切割为不相干的区块，分配给大量的计算机达到分布式计算的效果。
  • Reduce：化简，通过指定并发的Reduce函数将结果汇总，保证所有的键值对共享相同的键组。

Hadoop框架实现了MapReduce算法，把应用程序分割为许多很小的工作单元，每个单元可以在集群节点上重复执行。还提供了一个分布式文件系统GFS等。

分布式计算会导致网络间进行大量频繁的数据交换，输入数据保存在机器的本地磁盘上，系统划分数据段，将原始文件划分到各个段中，并进行备份分配到不同的机器上。从而可以保证大部分数据都可以本地读取，减少对网络带宽的占用。

三. 案例

3.1 Top K 问题

在海量数据中找到出现频率最高的前K个数据。较好的方案为：分治 + Trie树/hash + 小顶堆。

将数据集通过Hash分解为多个小的数据集，然后使用Trie树或Hash统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中频率最高的前K个数，最后合并所有数据集算出最终的Top K。

假设有1亿个浮点数，找出最大的10000个数？

  • 全排序：全部数据一次排序，比较快的排序算法如快排一般为 O(nlogn)，每个浮点数占4B，1亿个大概需要400M内存。
  • 局部淘汰法：用一个容器放置前10000个数，依次与容器内最小数字相比，只要大于最小数字就交换。时间复杂度为 O(n + m^2^)，m为容器大小。
  • 分治法：将1亿条数据切分为100份，每份100万条，找出每份中最大的10000个（通过快排将数据分为两堆，大堆个数大于10000，继续对大堆快排成两堆；如果小于10000，则对小堆快排一次，找到第10000-n大的数字，递归该流程），最后在100*10000个中找到最终的最大10000。
  • Hash法：先通过Hash去重，再通过分治或最小堆求出结果。
  • 最小堆：先读入前10000个数来创建大小为10000的小顶堆。建堆的时间复杂度为 O(mlogm) ，m即大小10000。遍历后续数字并与堆顶比较，当大于堆顶时则替换堆顶元素并重新调整小顶堆。最后按中序遍历输出堆中数字。时间复杂度为 O(mlogm) ，空间复杂度为m。

解决该问题比较适合采用MapReduce框架来解决，只需编写一个Map函数和两个Reduce函数，然后提交到Hadoop上即可。

  • 通过Map将数据划分到不同机器处理。采用Hash算法，将Hash值相同的数据交给同一个Reduce Task。
  • 每个机器通过Reduce算出各自出现次数最多的前N个数据，最后汇总。采用HashMap统计每个词的出现频率，第二个Reduce统计所有Reduce Task输出数据中的Top K。

3.2 重复问题

可以使用Bitmap即位图法来实现。

如从文件中解析出不同号码个数，假设为8位，则存储8位整数需要99Mbit，约等于12MB内存。

3.3 排序问题

分治法或位图法。

参考：

🔗