一次放不下，拆分处理

量级估算

---

• GB在数量上是2的30次方，是billion级别，即大约10亿个字节
• MB在数量上是2的20次方，是million级别，即大约100万个字节
• 32位整型理论是40亿，但是考虑到正负数，最大值大约20亿
• 整型全部数字有2^32个，2^32bit=0.5*2^30byte=0.5GB=512MB，即容纳全部数字的位图只需要512M
• IP地址4字节，共2^32组合，即全部存储需要16G

目标特性

---

• 范围
  • 无限：单词，URL
  • 有限：整数，IP地址(32位)
• 重复性

处理方法

---

• 位图
• 哈希划分
• 范围划分
• 小文件归并

大数据存在性检测

---

大量IP, 判断某个IP是否存在

每个ip对应一个整数，都是32位

• 位图，精准判断
• 布隆过滤器，模糊判断

大数据查重

---

单文件50亿个url，每个64字节，内存限制500M, 找出重复的

哈希划分

1. 首先进行大小估算，单文件3200亿字节，即320G,肯定超出内存
2. 一次装不下，进行分治成1000个小文件，理论上每个小文件大概300M
3. 如果数据倾斜，个别小文件还是过大，继续哈希直到文件符合内存限制
4. 如果确实重复的很多，重复部分超过内存限制，流式读入去重

两文件各50亿个url,每个64字节，内存限制4G，找出共同的部分

哈希划分+配对比较

1. 首先进行大小估算，单文件3200亿字节，即320G,肯定超出内存
2. 一次装不下，进行分治成1000个小文件，分发方式是哈希%1000，这样每个小文件大概300M,同时好处是相同的url肯定位于相同的序号的小文件中
3. 内存加载一对序号相同的小文件，其中一个建立HashMap,另一个比对出结果

大数据单机排序

---

有限512MB内存下对10GB数据排序

• 位图
  条件：如果数据是int类型，并且没有重复的话，可以考虑位图，用一个bit表示一个数字

• 桶排序，范围划分
  条件：如果范围有限，分布比较均匀的话
  将数据按照所属范围分成若干小文件，即一定范围数字写入某一文件，每个文件内排序，因为范围也是有序的，顺序合并即可
  场景：按时间排序

• 分治归并
  条件：数据无需满足特殊要求，通用

1. 首先进行文件切分，10GB文件分成40份，每份256MB这样每次就可以同时加载两个文件
2. 依次将每份文件载入内存，进行排序，这样可以得到40份有序文件
3. 接下来使用归并排序，最基本的是2路归并，每次开两个文件，输出一个文件。还可以进行多路归并，减少IO次数。最终将所有文件合并为一个文件

大数据单机topN

---

统计词频

文件20亿个整数，内存2G，找出次数最多的数字

哈希划分，计数，结果归并

1. 20亿个整数，即使都是同一个数，也在int范围内，即计数采用4字节整型就够
2. 计算能容纳多少哈希记录，一条计数key和value各4个字节，一共8字节，2.5亿条记录占用2G，即内存能同时维护2.5亿个不同的数值
3. 全整数范围40亿个，哈希划分16个文件，每个文件不同数字不会超过2.5亿个，可以内存处理，计数结果输出成文件
4. 每个文件都可以统计出次数最多的数，不同文件结果进行归并，过程中找到最多

海量访问日志中找出访问某一网站次数最多的IP

哈希划分，计数

1. 过滤出访问某一网站的IP,写入文件
2. IP每段有2^8个取值，4段有2^32 = 4G种取值，全加载内存有难度，哈希分治到1024个小文件，每个4M个地址
3. 每个小文件内部统计次数，找到最多的IP
4. 汇总，找到全局最多

有一个1G大小的文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M，要求返回频数最高的100个词

哈希划分，计数排序，结果归并

1. 即使单词1个字节，最多出现10亿次，int计数即可
2. 单条kv最多20字节, 内存能计数50000个单词，即使单词1个字节最多有10亿个单词，可以划分20000个文件
3. 哈希切割，相同词聚在一起，满足内存限制
4. 加载每个小文件，统计产出词频文件，内部排好序或者使用小顶堆
5. 两两归并，只保留前100，最终产出一个文件

大数据缺失查找

---

文件40亿个无符号整数，内存1G，找出所有没出现的数字

位图，全部整数数量的位图，大概40亿个比特位，占用512M空间

内存10M，找出一个没出现的数字即可

1. 全部位图需要占用512M，按照范围划分成64份，每个范围8M可满足内存需求
2. 先找一个大概范围，计数统计64个区间上每个区间上出现的数字个数，如果个数小于范围，肯定缺失
3. 在区间上建立位图，找出一个缺失数字

大数据特征数查找

---

40亿个32位无符号整数，内存1G，找到所有出现两次的数

• 位图
  使用两位表示一个数据，80亿个比特位，符合1G
  两个比特位可以表示4种状态，没有，1次，两次，多次

• 分治
  统计词频，找出词频是2

40亿个32位无符号整数，内存10M，找中位数

粗略定位，精细统计

1. 200万个数约占内存8M, 可以按200万一个范围作为区间，这样能2000多个区间
2. 申请2000多的数组，先遍历一遍，进行区间词频统计，根据统计结果计算出中位数所在的区间
3. 申请200万容量数组，区间内再次词频统计，找出中位数