大数据处理 - Overview

本文主要介绍大数据处理的一些思路。

何谓海量数据处理?

所谓海量数据处理，无非就是基于海量数据上的存储、处理、操作。何谓海量，就是数据量太大，所以导致要么是无法在较短时间内迅速解决，要么是数据太大，导致无法一次性装入内存。

那解决办法呢?

• 针对时间: 我们可以采用巧妙的算法搭配合适的数据结构，如Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie树；

• 针对空间: 无非就一个办法: 大而化小，分而治之(hash映射);

• 集群|分布式: 通俗点来讲，单机就是处理装载数据的机器有限(只要考虑cpu，内存，硬盘的数据交互); 而集群适合分布式处理，并行计算(更多考虑节点和节点间的数据交互)。

具体思路

• 大数据处理 - 分治/hash/排序

• 就是先映射，而后统计，最后排序:

• 分而治之/hash映射: 针对数据太大，内存受限，只能是: 把大文件化成(取模映射)小文件，即16字方针: 大而化小，各个击破，缩小规模，逐个解决

• hash_map统计: 当大文件转化了小文件，那么我们便可以采用常规的hash_map(ip，value)来进行频率统计。

• 堆/快速排序: 统计完了之后，便进行排序(可采取堆排序)，得到次数最多的IP。

• 大数据处理 - Bitmap & Bloom Filter

• 布隆过滤器有着广泛的应用，对于大量数据的“存不存在”的问题在空间上有明显优势，但是在判断存不存在是有一定的错误率(false positive)，也就是说，有可能把不属于这个集合的元素误认为属于这个集合(False Positive)，但不会把属于这个集合的元素误认为不属于这个集合(False Negative)

• 大数据处理 - 双层桶划分

• 其实本质上还是分而治之的思想，重在“分”的技巧上！适用范围: 第k大，中位数，不重复或重复的数字；基本原理及要点: 因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。

• 大数据处理 - Trie树/数据库/倒排索引

• 适用范围: 数据量大，重复多，但是数据种类小可以放入内存；基本原理及要点: 实现方式，节点孩子的表示方式；扩展: 压缩实现

• 大数据处理 - 外排序

• 适用范围: 大数据的排序，去重；基本原理及要点: 外排序的归并方法，置换选择败者树原理，最优归并树

• 大数据处理 - Map & Reduce

• MapReduce是一种计算模型，简单的说就是将大批量的工作(数据)分解(MAP)执行，然后再将结果合并成最终结果(REDUCE)。这样做的好处是可以在任务被分解后，可以通过大量机器进行并行计算，减少整个操作的时间。但如果你要我再通俗点介绍，那么，说白了，Mapreduce的原理就是一个归并排序