RJ博客

如何让千万级别数据量去重更高效?

本文目录

假使现在要对如下数据格式的数据去重聚合: 其中UID为用户ID,KEYWORD为该用户搜索关键字, 现在要以KEYWORD维度统计某KEYWORD总共被搜索了多少次, 以及被多少不同的用户搜索过(UID去重)

UID

KEYWORD

A123
A123
A456
B123

要整理变成如下目标格式: 

KEYWORD

搜索次数 count(UID)搜索用户数 count(distinct UID)
12332
45611

其实直接用SQL语句是能出结果的:

SELECT `KEYWORD`,count(UID),count(distinct UID) FROM `表名` group by trim(`word`) ORDER BY count(uuid) DESC;

但是这条SQL语句对百万级别的数据还能勉强支持, 千万级别以上的数据就开始显得吃力了, 因为每次group by都得执行一次count(UID), 一次count(distinct UID),对于2000+W的数据要跑50+分钟才能跑完.

后来尝试了用Python来计算, 1.2G的数据从数据库读到内存要占用10G内存, 由于我运行着其他大程序, 内存不够直接把电脑卡死了.重启电脑后我再次运行脚本, 但是运行时间并不理想, 比起MySQL的50+分钟,python直接跑了2个多小时. 先看一下我的实现逻辑:

数据先按这种格式重组

lists['123']['click_count'] = 3
lists['123']['uuids'] = {'A','B'}

然后再count一下uuids的个数即总搜索用户数.

后来经测试发现, 问题就出在lists['123']['uuids'], 这里采用的是列表结构, 每次我往里面插入新的uuids的时候, 都得遍历列表的值, 判断无重复值才插入新的uuids, 时间就是耗费在这遍历搜索上面.

于是我把lists['123']['uuids']数据结构变成字典:

lists['123']['uuids']['A']=0
lists['123']['uuids']['B']=0

然后依旧是count一下uuids的个数即总搜索用户数. 统计逻辑上并没有什么大变化, 但是效率却快了很多, 因为字典的key是用hash tables实现的, 访问速度非常快, 时间复杂度基本是O(1), 所以在判断是否已有重复uuid上速度非常快.

进一步了解的可移步:http://liuzhijun.iteye.com/blog/2266358

至此, 计算时间从2个多小时, 里面变成1分钟内了, 效率提升了100多倍.


==== 注意 ====

python strip()会去除全角空格' ', 而php, mysql 的 trim() 都不会去除全角空格, 这对搜索词去重会有一定的影响, 当有用户输入全角的空格的时候, 统计的结果就会有细微的差异, 不过可以采取一些方法做到:

php: $Keyword=trim(trim($Keyword," "));
mysql: trim(both ' ' from trim(`word`))


相关推荐

发表评论