这两天跟朋友聊了些关于海量数据的处理问题…    咱们暂且不提那些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 .  但是会产生一些的误差,一般来说都是可以接受的.

就先这样…  



对Python及运维开发感兴趣的朋友可以加QQ群 : 478476595 !!!
{ 2000人qq大群内有各厂大牛,常组织线上分享及沙龙,对高性能及分布式场景感兴趣同学欢迎加入该QQ群 }

另外如果大家觉得文章对你有些作用!   帮忙点击广告. 一来能刺激我写博客的欲望,二来好维护云主机的费用.
如果想赏钱,可以用微信扫描下面的二维码. 另外再次标注博客原地址  xiaorui.cc  ……   感谢!

构建高效的python requests长连接池

前文:      最近在搞全网的CDN刷新系统,在性能调优时遇到了requests长连接的一个问题,以前关注过长连接太多造成浪费的问题,但因为系...

阅读全文

不要粗暴的销毁python线程

前言:     不要试图用强制方法杀掉一个python线程,这从服务设计上就存在不合理性。 多线程本用来任务的协作并发,如果你使用强制手段干掉线...

阅读全文

基于timerfd epoll开发的io定时器 [下]

接着上下文 接着上文, 上次内容是说epoll timerfd的原理和函数方法,下文主要是python epoll timerfd的之间的调用. 该文章写的有些乱,欢...

阅读全文

发表评论