关于海量数据处理的一些话题

这两天跟朋友聊了些关于海量数据的处理问题…    咱们暂且不提那些hadoop、spark的集群解决方案,就单单说海量数据的处理方式,一般面试题中会有设计…

该文章写的有些乱,欢迎来喷 ! 另外文章后续不断更新中,请到原文地址查看更新. 

 http://xiaorui.cc/?p=3735


第一个话题,在一个几百G的文件中如何找到最多的那个ip? 

你就算把所有的ip地址放到hash里面,也才2^32 = 4G的内存使用量,所以说直接干脆粗暴的读取文件,这样ip地址为key,数量为value。 数据都到手了后,用小堆和快排都可以拿到最多的ip….   

如果就给你100M内存,那咋办? 

可以读取文件通过hash的方式把ip地址放到1000个文件里面,这样一样的ip都放在一块了,然后这个时候你可以针对1000个文件遍历结果。  遍历的时候,只保存那个hash最大的值就可以了…. 

总的来说,解决思路就是, 首先通过hash取摸的方式分割文件, 遍历小文件把结果存储到当前内存hash里,但如果撑爆内存,可以把结果也放到一个个的文件里,然后通过快排和小顶堆来拿取文件.     如果是取TOPK,那么用固定数量的小顶堆最合适了。


第二个话题,如果 a,b 两个文件都有50亿的url,求相同的url有多少…

a,b 都按照url取摸分区分拆到不同的文件里面,这样 a_1.txt 跟 b_1.txt做对比,先把a_1.txt url 放到hashset里,然后让b_1.txt 对比hashset, 如果有,就放到一个result_set里,result_set 也可以落地,没有匹配到就drop..      

还有一个方法,就是使用省内存的bloomfilter, 但是会出现一定的偏差.


第三个话题,有一万个关键词,给你一段文本,用最合适的算法拿到匹配到的关键词.

AC自动机…. trie和KMP匹配模式的组合, 适合匹配条件多时候,如果只有几十条,跟直接O(N) 正则匹配一个德行.


第四个话题,海量数据的去重,最省内存的方案.

bloomfilter , bitmap .  但是会产生一些的误差,一般来说都是可以接受的.

就先这样…  


大家觉得文章对你有些作用! 如果想赏钱,可以用微信扫描下面的二维码,感谢!
另外再次标注博客原地址  xiaorui.cc

发表评论

邮箱地址不会被公开。 必填项已用*标注