海量数据处理——从Top K引发的思考

MavenTalker

发布于 2019-07-19 10:58:16

7120

发布于 2019-07-19 10:58:16

文章被收录于专栏：歪脖贰点零歪脖贰点零

三问海量数据处理：

什么是海量数据处理，为什么出现这种需求？
如何进行海量数据处理，常用的方法和技术有什么？
如今分布式框架已经很成熟了，为什么还用学习海量数据处理的技术？

什么是海量数据处理，为什么出现这种需求？

如今互联网产生的数据量已经达到PB级别，如何在数据量不断增大的情况下，依然保证快速的检索或者更新数据，是我们面临的问题。所谓海量数据处理，是指基于海量数据的存储、处理和操作等。因为数据量太大无法在短时间迅速解决，或者不能一次性读入内存中。

从何解决我们上面提到的两个问题：时间问题和空间问题

时间角度，我们需要设计巧妙的算法配合合适的数据结构来解决；例如常用到的数据结构：哈希、位图、堆、数据库（B树），红黑树、倒排索引、Trie树等。

空间角度，我们只需要分而治之即可，两大步操作：分治、合并。MapReduce就是基于这个原理。

如今分布式框架已经很成熟了，为什么还用学习海量数据处理的技术？

这个问题，就相当于为什么要学习算法，因为大部分人在工作中都很少用到这些算法和高级的数据机构。武侠讲究内外兼修才是集大成着。算法就是内功，可以不用，不可以没有。算法更多的是理解和推到的过程，这就是为什么很多学数学和物理专业的学生，可以在计算机行业做的很好，因为他们的数学好，可以很好的理解各种推到过程和算法原理。最后一句话，知其然而后知其所以然，技术更好的成长。

这篇文章，我采用总分的结构进行写作，我们每次都会抛出一个问题，这个问题对应的海量数据处理的一个方面，我们从下面几个角度分析：

1、对应海量数据处理的那个技术，以及是时间角度和空间角度 2、分析这个问题，如何解决 3、提出解决方案，进行分析 4、详细讲解这处理这个问题时，用到的技术，例如什么是堆，hash等

抛出问题，寻找热门查询任何的搜索引擎（百度、Google等）都会将用户的查询记录到日志文件。对于百度这种公司，我们知道每天有很多Query查询，假设有100G的日志文件，只有一台4G内存的电脑，现在让你统计某一天热门查询的Top 100. （Top 100的统计是很有用意义的，可以提供给用户，知道目前什么是最热门的，关注热点，例如金庸老先生的去世，现在应该就是热门。）

分析问题，根据题目的描述，我们有100G日志文件，只有一台4G的电脑，这是空间不足的问题，我们需要分而治之。划分文件，将100G日志文件划分成K的小文件。K >= 100G / 4G = 25。这里我们去K=50（为什么不取25呢？），将所有的Query划分到50个小文件中，然后统计每一个小文件中的Query的频率，之后合并结果，得到最后的Top 100的Query。

需要我们处理的两个点：划分和合并。划分：保证相同的Query划分到同一个小文件中。统计：统计每个小文件中Query的频率合并：如何快速的合并得到结果。划分的时候我们需要用到一个叫做hash的技术，两步走，

hash(string) = key_index,
File_index = Key_index % K(50)

划分：

设计一个hash函数，需要保证的正string -> index的转换，这里不需要考虑冲突，只有保证相同的string对应一个key_index即可，一个好的hash函数会将均匀分布的数据，均匀分布到不同的文件中去。常用的Hash函数和原理

C++代码：

const unsigned int BIG_MOD = 1000003;
inline unsigned int hash_code(std::string&& key) {
    unsigned int value = 0;
    for(int i = 0; i < key.size(); i++) {
        value = value * 31 + (unsigned int) key[i];
        value %= BIG_MOD;
    }
return value;
}

统计：

这里给出两种方法， hash_map和Trie数。每一个小文件有一个输出结果，这里我们只需要输出前Top 100频率进行。

Hash_map这个原理跟前面的提到的hash函数基本一样，只是需要解决冲突问题，之后会在别的文章中专门提出。C++的结构map，或者Java中Hashmap或者Python中的dict基本使用方式一样。 Map[query]+=1.

HashMap的不足在于我们空间使用多，对于查询这种Query，很多的查询都是一样的，我们可以使用Trie树来解救，这是一个前缀树的结果，例如 Querys={“我爱你”，“爱你们”，“我”，“我”，“我爱你“，”金庸“}，构造的树的格式如需：

数据结果：
const int MAXN = 10000;
struct TreeNode {

string key;
int cnt;
int flag;
struct TreeNode *next[MAXN];
};

具体的Trie树细节，这里就不在继续展开，可以搜索相关文章，后续可能会继续退出Trie树的相关文章。基于上述两种方法，我们都可以直接得到Top 100的结果。输出文件格式如下：

Query1 Count1
.
.
.
Queryi Counti

合并：

读取所有的结果在内存中，根据Count排序取前100，时间复杂度是 O(nlogn),n是所有个数 n=50*100. 但是注意到我们只要前k个最大的，我可以使用堆排序，使用一个叫做最小堆的问题。维护k(100)大小的最小堆，每次插入新的元素，去掉最小的元素，时间复杂度 O(k+(n-k)logk),比排序小很多。这里同样可以使用Trie树，和上述的方式一样，注意这可以转化一个取第k个大小的问题，我们也可以使用快速排序中划分函数，进行找到第k个，前面的就是我们需要的目标。

结束：

到这里我们的问题已经可以结束了，但是却有几个问题需要提出来：这真的是热门Query统计吗？百度等公司是这么做的吗？相似的Query怎么处理？如何实时的更新热门榜单呢？Hash划分的时候，划分文件不平衡怎么办？如何保证平均划分？等等的问题，需要我们思考。