海量数据处理的方法总结
共 6735字,需浏览 14分钟
·
2021-06-19 20:34
点击上方蓝色字体,选择“标星公众号”
优质文章,第一时间送达
作者 | 张维鹏
来源 | urlify.cn/i6jUJb
bit:位
byte:字节
1 byte= 8 bit
int 类型为 4 byte,共32位bit,unsigned int也是
2^32 byte = 4G
1G= 2^30 =10.7亿
海量数据处理概述:
分而治之/hash映射 + hash统计 + 堆/快速/归并排序;
Trie树/Bloom filter/Bitmap
数据库/倒排索引;
双层桶划分;
外排序;
分布式处理之Hadoop/Mapreduce。
一、分而治之/hash映射 + hashmap统计 + 快速/归并/堆排序
(1)按照 IP 地址的 Hash(IP)%1024 值,把海量IP日志分别存储到1024个小文件中。这样,每个小文件最多包含4MB个IP地址;
(2)对于每一个小文件,构建一个IP为key,出现次数为value的Hash map,同时记录当前出现次数最多的那个IP地址
(3)然后再在这1024组最大的IP中,找出那个频率最大的IP
(1)顺序读文件中,对于每个词x,按照 hash(x)/(1024*4) 存到4096个小文件中。这样每个文件大概是250k左右。如果其中的有的文件超过了1M大小,还可以按照hash继续往下分,直到分解得到的小文件的大小都不超过1M。
(2)对每个小文件,可以采用 trie树/hashmap 统计每个文件中出现的词以及相应的频率,并使用 100个节点的小顶堆取出出现频率最大的100个词,并把100个词及相应的频率存入文件。这样又得到了4096个文件。
(3)下一步就是把这4096个文件进行归并的过程了
(1)遍历文件a,对每个 url 根据某种hash规则,求取hash(url)/1024,然后根据所取得的值将 url 分别存储到1024个小文件(a0~a1023)中。这样每个小文件的大约为300M。如果hash结果很集中使得某个文件ai过大,可以在对ai进行二级hash(ai0~ai1024),这样 url 就被hash到 1024 个不同级别的文件中。
(2)分别比较文件,a0 VS b0,…… ,a1023 VS b1023,求每对小文件中相同的url时:把其中一个小文件的 url 存储到 hashmap 中,然后遍历另一个小文件的每个url,看其是否在刚才构建的 hashmap 中,如果是,那么就是共同的url,存到文件中。
(3)把1024个文件中的相同 url 合并起来
(1)顺序读取10个文件 a0~a9,按照 hash(query)%10 的结果将 query 写入到另外10个文件(记为 b0~b9)中,这样新生成的文件每个的大小大约也1G
(2)找一台内存2G左右的机器,依次使用 hashmap(query, query_count) 来统计每个 query 出现的次数。利用 快速/堆/归并排序 按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件c0~c9。
(3)对这10个文件 c0~c9 进行归并排序(内排序与外排序相结合)。每次取 c0~c9 文件的 m 个数据放到内存中,进行 10m 个数据的归并,即使把归并好的数据存到 d结果文件中。如果 ci 对应的m个数据全归并完了,再从 ci 余下的数据中取m个数据重新加载到内存中。直到所有ci文件的所有数据全部归并完成。
(1)在每台电脑上求出TOP10,采用包含10个元素的堆完成(TOP10小,用最大堆,TOP10大,用最小堆)
(2)求出每台电脑上的TOP10后,把这100台电脑上的 TOP10 合并之后,共1000个数据,在采用堆排序或者快排方式 求出 top10
(1)2.5亿个 int 类型 hash 到1024个小文件中 a0~a1023,如果某个小文件大小还大于内存,进行多级hash
(2)将每个小文件读进内存,找出只出现一次的数据,输出到b0~b1023
(3)最后数据合并即可
二、Trie树+红黑树+hashmap
用于存储时,Trie树因为不重复存储公共前缀,节省了大量的存储空间;
用于以字符串的查找时,Trie树依靠其特殊的性质,实现了在任意数据量的字符串集合中都能以O(len)的时间复杂度完成查找(len为要检索的字符串长度);
在字符串统计中,Trie树能够快速记录每个字符串出现的次数
(1)如果是上千万或上亿的 int 数据,现在的机器4G内存能存下。所以考虑采用 hashmap/搜索二叉树/红黑树 等来进行统计重复次数
(2)然后使用包含 N 个元素的小顶堆找出频率最大的N个数据
用 trie树 统计每个词出现的次数,时间复杂度是O(n*len)(len表示单词的平均长度)。
然后使用小顶堆找出出现最频繁的前10个词,时间复杂度是O(n*lg10)。
三、BitMap 与 Bloom Filter:
① 首先遍历文件,将每个文件按照数字的正数,负数标记到2个 bitmap 上,为:正数 bitmapA_positive,负数 bitmapA_negative
② 遍历另为一个文件,生成正数:bitmapB_positive,bitmapB_negative
③ 取 bitmapA_positive and bitmapB_positive 得到2个文件的正数的交集,同理得到负数的交集。
④ 合并,问题解决
(1)依次遍历每个大文件中的每条数据,遍历每条数据时,都将它插入 Bloom Filter;
(2)如果已经存在,则在另外的集合(记为S)中记录下来;
(3)如果不存在,则插入Bloom Filter;
(4)最后,得到的S即为所有这些大文件中元素的交集
四、多层划分:
按照升序顺序把这些数字,hash划分为N个范围段。假设数据范围是2^32 的unsigned int 类型。理论上第一台机器应该存的范围为0~(2^32)/N,第i台机器存的范围是(2^32)*(i-1)/N~(2^32)*i/N。hash过程可以扫描每个机器上的N个数,把属于第一个区段的数放到第一个机器上,属于第二个区段的数放到第二个机器上,…,属于第N个区段的数放到第N个机器上。注意这个过程每个机器上存储的数应该是O(N)的。
然后我们依次统计每个机器上数的个数,依次累加,直到找到第k个机器,在该机器上累加的数大于或等于(N^2)/2,而在第k-1个机器上的累加数小于(N^2)/2,并把这个数记为x。那么我们要找的中位数在第k个机器中,排在第(N^2)/2-x位。然后我们对第k个机器的数排序,并找出第(N^2)/2-x个数,即为所求的中位数的复杂度是O(N^2)的。