海量数据程序设计思路

massive-data-programming

bitmap

位图
存储方式属于hash
bitmap是将原本需要占用1个字节或者多个字节的整数，转化成对一个字节单位中的一个确定位置的比特的占用
- 如有：

int array[] = {1, 2, 3, 4, 5} //使用int型数组存储的数据在内存中，以32位整型为例，需要占用20个字节的空间

//使用bitmap
#include <stdio.h>

#define LEN 1
#define MASK 0xff		//表示8个比特位1
#define SHIFT 3

char bitmap[LEN];

void set(char i) {
    bitmap[i >> SHIFT] |= 1 << (i + 1);
}

int main(int argc, char const *argv[])
{
	int array[] = {1, 2, 3, 4, 5}; //使用int型数组存储的数据在内存中，以32位整型为例，需要占用20个字节的空间
	for (int i = 0; i < 5; ++i)
	{
		set(array[i]);
	}
	int x = bitmap[0];
	while (x > 0) {
		printf("%d", x % 2);
		x = x / 2;
		if (x == 0)
		{
			printf("0 -- revert");
		}
	}
	printf("\n");
	printf("%d\n", bitmap[0]);
	printf("%x\n", bitmap[0]);
	printf("%d\n", sizeof(bitmap[0]));
	return 0;
}

0 1 2 3 4 5 6 7
0 1 1 1 1 1 0 0
bitmap[0]
存储方法：使用字节中的位来存储一个整数
- 用整数/size 表示整数在bitmap中的索引位置
- 用整数模 size 表示整数在这个索引位置处应该将那个位置上的bit置为1
- 这样想要获取存储在bitmap中的整数值，只需要计算出该bit在整个bitmap中的位置
取模的方式是最简单的hash函数
应用
- Bit-Map做数据的查找、去重、排序等
- 如对于4,000,000,000个ip地址的存储，需要内存空间为16,000,000,000个字节，如果使用bitmap只需要500,000,000个字节，也就是500MB，大小从16GB缩小到了500MB，缩小了32倍；
- 例如，2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数
  - 将bit-map扩展一下，用2bit表示一个数即可：0表示未出现；1表示出现一次；2表示出现2次及以上，即重复，在遍历这些数的时候，如果对应位置的值是0，则将其置为1；如果是1，将其置为2；如果是2，则保持不变。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map，都是一样的道理。

0	1	2	3	4	5	6	7
0	1	1	1	1	1	0	0

分治法

对于海量数据处理的问题，现实情况基本不可能遇到，而且此类问题也经常会限制C程序所能使用的内存空间大小，而文件中经常包含上10亿行的字符数据；
此类问题涉及到
1. 对数据在有限的内存中存储的极端条件，例如bitmap
2. 对数据的操作要尽可能涉及少量的文件I/O操作
  - 传统的机械硬盘使用磁盘存储数据，每4kb作为一个页，因为磁头的机械移动，每次读写数据的平均花费8 ~ 11 ms
  - 当今的固态硬盘根据不同的封装方式，平均的一次I/O花费的时间在0.1ms左右
分治
- 类似于归并的分治思想 – divide-and-conquer
- 先将大数据量的文件分割成小的数据块或文件
- 在分别对小文件进行处理，处理小文件的时候每次也只进行一次读写
- 最终处理结果所花费的总读写文件次数位：分割的小文件的倍数
例题
要求：当前有一个100亿行的日志文件，每行中有一个v4的IP地址，且总共有10亿个ip地址，且每个IP随机出现多次，现在要求只使用100MB的内存空间，设计一个C程序，用最高效的方式输出每个ip地址及地址在日志中出现的次数；
- 100MB = 100 X 1000 X 1000 Byte 表示 1亿个字节， IP地址为4个字节，总共40亿个地址空间才能完全容纳
- 分析：
  - 不重复ip地址数量位1, 000, 000, 000个ip地址，顺序存储的话也需要4, 000, 000, 000个字节，4GB空间；
  - 地址在日志文件中随机分布；
  - 当前给定能够存储该结构的空间位100MB = 100, 000, 000字节；
  - 顺序存储的条件下需要将4GB空间分成40份；
  - 假设一个ip地址在整个文件中出现的最多次数为32位无符号整型的最大值；也就是一个32位的无符号整型就可以存储一个ip地址出现的次数；并且假设日志每行都有一个ip地址；那么总共要处理的地址数量位100亿个；
- Solution：
  - 假设总共每行出现1个ip地址，那么总ip地址数量10,000,000,000，不重复的是1,000,000,000个；
  - 将10,000,000,000分成400份，那么每一份都可以完全能读入主存；
  - 遍历日志文件，匹配ip地址，将地址按照二进制大小分为400份，对ipv4的所有地址转化为2进制，然后对100,000,000取模的方式将其分到400份的数组中，在100MB内存空间内初始化400个长度位25MB的数组，将ip地址更新到每个数组内，当数组满后，将数组写入文件一次并清空，再次满后，在追加到文件，那么平均的情况下要进行40 X400 次I/O操作，总耗时160000ms，也就是160s；
  - 这样对于400个文件来说，每个文件中都会包含所有的重复的无序的ip地址，这时候将文件逐个读入内存并，对数组排序(选择快速排序或者归并将时间复杂度降低到logn，假设每个文件为)，排序完成后，在输出每个ip地址出现的此处到一个文件，或者使用类似bitmap的方式，将每4个字节看成一个bit，并将该位置出现的ip地址的数量更新到4个字节的int中；本次共400X2次文件读写，总耗时为80,000ms为8s；
  - 所有结合分而治之即bitmap的思想，最大化的利用有限的内存，可以将整个问题的处理时间下降到数分钟的级别；

数据结构 B+TREE

海量数据处理方法，也可以参考MySQL底层的B+树的索引方式，将根节点存放在内存中，顺序查找孩子指针，指针指向磁盘或者硬盘中存储的对象，一次搜索将I/O操作降低到1次，又根据磁盘的局部性预读特性，可以用一次I/O查询一定范围内的数据；

海量数据处理面试题集锦