海量数据处理技术与方案

海量数据处理

1. 海量数据处理

...

1.1 什么是数据处理

数据的存储 + 计算

1.2 什么是海量数据处理

数据量太大，无法在短时间内迅速解决，或者是数据太大，导致无法一次性装入内存的数据处理

1.3 海量数据处理的常用方法

1. 巧用数据结构（bitmap、hash、布隆过滤器、堆）

2. 分治法：把规模大的数据转化为规模小的数据，逐个击破

3. 海量数据处理场景

4. 40亿个QQ号，如何判断一个QQ号是否存在?

5. 给定1000万个整数，内存限制1MB，如何对他们进行排序?

6. 给定1GB单词，内存限制1MB，如何找到出现频率最高的100个单词?

7. 内存限制4GB，如何对100亿URL查重?

8. 1000万字符串，其中有些是重复的，需要去重，保留没有重复的字符串。请怎么设计和实现?

9. 给定10亿个手机号，如何快速判断一个手机号是否存在?

10. 海量数据处理方法应用

3.1 bitmap 方法

3.1.1 问题拆解

问题场景

40亿个QQ号，如何判断一个QQ号是否存在?

问题拆解

1. 40亿QQ号存储位置：文件
2. 查找QQ号的时间要求：快速，1s内

3.1.2 问题思路

问题思路 1：hash结构

要快，用hash结构存储QQ号码，O(1) 时间内查找到某个QQ 号码

...

• QQ号码无符号整数 uint
• hash存储结构，key：号码，value：次数
• 所需内存：4byte * 40亿 / 1024 / 1024 / 1024 ≈ 14.9GB
• 思路缺点：需要较大的内存成本

如果条件限制是：内存限制为 1G 呢？

问题思路 2：Bitmap

1. 只存储必要信息(QQ号码一定要存吗？)
2. 字节存储 ---> 位存储

3.1.3 解决方案

整体思路

1. 只存储QQ号码存在与否(0/1)
2. 建立QQ号码与二进制位之间的映射

bitmap(二进制数组) 如何表示QQ号码

...

• key (数组索引下标)： QQ号码
• value： key这个索引对应的数组的 bit 值 (0/1)

索引可以理解为地址，不用额外存储，不占用内存地址

所需内存

• 最大qq号码：4个字节的最大无符号整数 = 2^32 - 1 ≈ 43 亿
• 所需内存 = 43 亿 / 8 / 1024 / 1024 / 1024 ≈ 521 MB

实现流程

1. 申请长度为 43 亿的二进制位数组
2. 遍历文件中的40亿个QQ号码，将二进制位数组中的对应值设置为 1
3. 根据给定QQ号码，到二进制数组中查找对应索引位置的值，若为 1 则存在，否则不存在

3.1.4 问题变形

利用bitmap去重

...

利用bitmap进行排序

...

3.1.5 bitmap 具体实现

如何定位号码在数组中的位置

• 需要多大的数组： size = (max_value + 8) / 8
• 对应第几个数组： byteIndex = num / 8
• 在字节的第几位： bitIndex = num % 8
• 比如现在有一堆号码
• 需要找到号码 8 的具体位置

...

如何将二进制位设置为 1

• byte[byteIndex] | 1 << bitIndex
• 将号码 8 对应的二进制位设置为 1

...

如何判断号码对应的二进制位是否为 1

• byte[byteIndex] & 1 << bitIndex

...

3.2 外部排序

。。