EI Madrigal's Space
0%

海量数据处理

Posted on Edited on In
汇总一些常见的大数据问题

IP白名单系统

设计一个10亿级别的IP白名单系统，支持增删改查。

如果用string存储每个IP，那么大约需要15GB的内存； 如果直接将每一位看作十进制的数，用int存储，但是单个int无法存储255.255.255.255这么大的数；

如果将每个小段都用二进制表示，那么所有的IP地址都可以用32位的unsigned int表示。

所以采用\(2^{32}-1\)大小的bit数组来映射所有的IP地址，大约需要内存512MB。

首先看增加操作，将IP地址转为unsigned int后，将bit数组中对应位置1即可：

1
2
3
4
void set(unsigned int ip) {
    int byte = ip / 8, bit = ip % 8;
    arr[byte] = arr[byte] | 1 << (7 - bit);
}

再看查找操作，只需判断该IP地址对应位置是否为1即可： 

1
2
3
4
bool has(unsigned int ip) {
    int byte = ip / 8, bit = ip % 8;
    return arr[byte] & 1 << (7 - bit) > 0;
}

后续还有IP地址转unsigned int以及非法判断，并发处理等问题。

找众数

一个文件包含40亿个32位的无符号整数，使用内存限制1GB找到众数。

32位无符号数范围是\(0\sim 2^{32}-1(4,294,967,295)\)

傻白甜做法就是用一个Hashmap统计每个数的频率，key是4B，value是4B，一条记录8B，最差情况下40亿个数都不同，共需40亿*8B大约32GB。

哈希分割+多线程

https://www.bilibili.com/video/BV13g41157hK?p=11 29min

10亿IP地址bitmap?原理？把IP转为unsigned int，用bitset0

Spark