大数据处理相关知识点汇总

朴灿烈づ我的快乐病毒、 2022-01-28 01:09 296阅读 0赞

### 大数据处理相关知识点汇总 ###

*  简单统计
 *   *  Map-Reduce概念介绍
     *   *  用Map-Reduce方法统计一篇文章中每个单词出现的个数。
 *  海量数据处理
 *   *  解题关键
     *   *  请对10亿个IPV4的ip地址进行排序，每个ip只会出现一次
         *  请对10亿人的年龄进行排序。
         *  有一个包含20亿个全是32位整数的大文件，在其中找到出现次数最多的数，但是内存限制只有2G。
         *  32位无符号整数的范围是0-4294967295。现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然有没出现过的数。可以使用最多10M的内存，只用找到一个没出现的数即可，改如何找。
         *  某搜索公司一天的用户搜索词汇是海量的，假设有百亿的数据量，请设计一种求出每天最热100词的可行办法。
         *  工程师常使用服务器集群来设计和实现数据缓存，以下是常见的策略。1.无论是添加、查询还是删除数据，都先将数据的id通过哈希函数转换成一个哈希值，即为key。2.如果目前机器有N台，则计算key%N的值，这个值就是该数据所属的机器编号，无论是添加、删除还是查询操作，都只在这台机器上进行。请分析这种缓存策略可能带来的问题，并提出改进的方案。

# 简单统计 #

## Map-Reduce概念介绍 ##

Map-Reduce分为两个阶段：**Map阶段和Reduce阶段**。

*  **Map阶段**：使用哈希函数把任务分成若干个子任务，在分布式计算中节点可能是一台电脑或者是一个计算节点。
 *  **Reduce阶段**：把子任务并发处理，然后合并结果。

### 用Map-Reduce方法统计一篇文章中每个单词出现的个数。 ###

*  文章预处理：1. 去掉文章中的标点符号。2.对连字符-的处理。3.对于缩写的处理。4.对于大小写的处理。
 *  Map阶段：对每个单词生成词频为1的记录，如：(dog, 1)，一个单词可能有多个词频为1的记录。通过哈希函数得到每个单词的哈希值，并根据该值分成若干个子任务。
 *  Reduce阶段：每个子任务中包含若干种单词，但同一种单词不会分配进不同的子任务中。所以单个子任务中同一种单词的词频进行合并。
 *  所有子任务统一合并，即得每种单词的词频统计。

# 海量数据处理 #

## 解题关键 ##

*  **分而治之。通过哈希函数将大任务分流到机器，或分流成小文件**。
 *  常用的**HashMap**或**BitMap**。
 *  难点：通讯、时间和空间的估算。

### 请对10亿个IPV4的ip地址进行排序，每个ip只会出现一次 ###

IPV4的ip数量约等于42亿，申请长度为232的bit类型的数组，**bitmap**中每个位置上是一个bit，只可表示0或1两种状态。将10亿个ip地址依次放入bitmap中，即ip地址所对应的下标置1，最后再顺序输出ip地址即可。

### 请对10亿人的年龄进行排序。 ###

可以认为年龄在0-200之间，创建一个长度为200的数组，然后按照年龄**计数排序**即可。

### 有一个包含20亿个全是32位整数的大文件，在其中找到出现次数最多的数，但是内存限制只有2G。 ###

初步方案：使用hashmap记录所有数出现的次数，key为具体的数，使用4字节整型；value为这个数出现的次数，使用4字节整型。所以一条记录key-value保守估计占有8字节。当记录条数为2亿时，大约为1.6G内存，如果20亿都是不同的数，哈希表内存不够存放。

改进方案：将大文件使用哈希函数进行分流，假设分成16个小文件，同一种数不会被分流到不同文件上，对于不同的数，每个文件中含有整数的种数也几乎一样。所以对每个小文件用哈希表进行次数统计。全部处理完成后，只要选出16个小文件中哪个第一名最大即可。

### 32位无符号整数的范围是0-4294967295。现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然有没出现过的数。可以使用最多10M的内存，只用找到一个没出现的数即可，改如何找。 ###

**0 - 232\-1 范围分成64个区间**，单个区间应该装下 232/64 个数。总共的范围为42亿，但数一共为40个亿，所以**必然会有区间计数不足 232/64**。此时只要关注一个计数不足的区间，并用**bitmap统计区间中的数**出现情况即可。

### 某搜索公司一天的用户搜索词汇是海量的，假设有百亿的数据量，请设计一种求出每天最热100词的可行办法。 ###

**使用哈希函数进行分流**至每台机器，如果机器中文件依旧很大，可以**再次进行哈希函数分流**成小文件，处理每一个小文件，得到每个小文件中词汇的词频统计。建立记录后，**利用小根堆或外排序来进行TOP100的筛选**。

### 工程师常使用服务器集群来设计和实现数据缓存，以下是常见的策略。1.无论是添加、查询还是删除数据，都先将数据的id通过哈希函数转换成一个哈希值，即为key。2.如果目前机器有N台，则计算key%N的值，这个值就是该数据所属的机器编号，无论是添加、删除还是查询操作，都只在这台机器上进行。请分析这种缓存策略可能带来的问题，并提出改进的方案。 ###

**潜在问题：如果增加或删除机器时，数据迁移的代价很大。**  
根据哈希函数得到的哈希值结果%N， 当机器数N发生变化时，所有数据必须重新计算哈希值，以及对新的机器数M取余，来决定各自数据的归属。

**解决方案：一致性哈希算法**  
假设数据id通过哈希值计算后的结果为0 - 232，将这些数字收尾相连，形成**环形**。然后将机器id计算出哈希值，**确定机器在环中的位置**。**一条数据如何确定归属于哪台机器，将数据通过哈希函数计算后，在环中顺时针找寻离这个哈希值最近的机器位置，这台机器就是该数据的归属。**  
添加机器时，只需要计算新机器顺时针下一台机器中的数据id，从下一台机器中迁移部分数据进入新机器即可；删除机器时，只要将删除的机器数据全部顺时针的复制到下一台机器即可。