微信搜索lxw1234bigdata | 邀请体验:数阅–数据管理、OLAP分析与可视化平台 | 赞助作者:赞助作者

Java使用极小的内存完成对超大数据的去重计数,用于实时计算中统计UV

编程语言 lxw1234@qq.com 26277℃ 1评论

关键字:streamlib、基数估计、实时计算uv、大数据、去重计数

一直在想如何在实时计算中完成对海量数据去重计数的功能,即SELECT COUNT(DISTINCT) 的功能。比如:从每天零点开始,实时计算全站累计用户数(UV),以及某些组合维度上的用户数,这里的用户假设以Cookieid来计。

想想一般的解决办法,在内存中使用HaspMap、HashSet?或者是在Redis中以Cookieid为key?感觉都不合适,在数以亿计用户的业务场景下,内存显然也成了瓶颈。

如果说,实时计算的业务场景中,对UV的计算精度并不要求100%(比如:实时的监测某一网站的PV和UV),那么可以考虑采用基数估计算法来统计。这里有一个Java的实现版本 stream-lib:https://github.com/addthis/stream-lib

采用基数估计算法目的就是为了使用很小的内存,即可完成超大数据的去重计数。号称是只使用几KB的内存,就可以完成对数以条数据的去重计数。但基数估计算法都不是100%精确的,误差在0~2%之间,一般是1%左右。

本文使用stream-lib来尝试对两个数据集进行去重计数。相关的文档和下载见文章最后。

测试数据集1:

  • 文件名:small_cookies.txt
  • 文件内容:每个cookieid一行
  • 文件总记录数:14892708
  • 去重记录数:3896911
  • 文件总大小:350153062(约334M)
[liuxiaowen@dev site_raw_log]$ head -5 small_cookies.txt 
7EDCF13A03D387548FB2B8
da5f0196-56036078075b9f-14892137
1D0A83B604ADD4558970EE
3DF76E7100025F553B1980
72C756700C3CAA56035EE0
[liuxiaowen@dev site_raw_log]$ wc -l small_cookies.txt 
14892708 small_cookies.txt
[liuxiaowen@dev site_raw_log]$ awk '!a[$0]++{print $0}' small_cookies.txt | wc -l
3896911
[liuxiaowen@dev site_raw_log]$ ll small_cookies.txt 
-rw-rw-r--. 1 liuxiaowen liuxiaowen 350153062 Sep 25 10:50 small_cookies.txt

测试数据集2:

  • 文件名:big_cookies.txt
  • 文件内容:每个cookieid一行
  • 文件总记录数:547631464
  • 去重记录数:190264959
  • 文件总大小:12610638153(约11.8GB)
--总记录数
spark-sql> select count(1) from big_cookies;
547631464                                                                       
Time taken: 7.311 seconds, Fetched 1 row(s)
--去重记录数
spark-sql> select count(1) from (select cookieid from big_cookies group by cookieid) x;
190264959                                                                       
Time taken: 80.516 seconds, Fetched 1 row(s)

hadoop fs -getmerge /hivedata/warehouse/liuxiaowen.db/big_cookies/* big_cookies.txt

[liuxiaowen@dev site_raw_log]$ wc -l big_cookies.txt
547631464 cookies.txt
//总大小
[liuxiaowen@dev site_raw_log]$ ll big_cookies.txt 
-rw-r--r--. 1 liuxiaowen liuxiaowen 12610638153 Sep 25 13:25 big_cookies.txt

普通方法测试

所谓普通方法,就是遍历文件,将所有cookieid放到内存的HashSet中,而HashSet的size就是去重记录数。

代码如下:

package com.lxw1234.streamlib;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashSet;
import java.util.Set;

public class Test {
	public static void main(String[] args) {
		Runtime rt = Runtime.getRuntime();
		Set set = new HashSet();
		File file = new File(args[0]);
	    BufferedReader reader = null;
	    long count = 0l;
	    try {
	    	reader = new BufferedReader(new FileReader(file));
	    	String tempString = null;
	    	while ((tempString = reader.readLine()) != null) {
	    		count++;
	    		set.add(tempString);
	    		if(set.size() % 5000 == 0) {
	    			System.out.println("Total count:[" + count + "]  Unique count:[" + set.size() + "] FreeMemory:[" + rt.freeMemory() + "] ..");
	    		}
	    	}
	    	reader.close();
	    } catch (Exception e) {
	    	e.printStackTrace();
	    } finally {
	    	if (reader != null) {
		    	try {
		    		reader.close();
		    	} catch (IOException e1) {}
	    	}
	    }
	    System.out.println("Total count:[" + count + "]  Unique count:[" + set.size() + "] FreeMemory:[" + rt.freeMemory() + "] ..");
	}
}

指定使用10M的内存运行,命令为:

java -cp /tmp/teststreamlib.jar -Xms10M -Xmx10M -XX:PermSize=10M -XX:MaxPermSize=10M  \
com.lxw1234.streamlib.Test /home/liuxiaowen/site_raw_log/small_cookies.txt

运行结果如下:

streamlib

10M的内存,仅仅够存65000左右的cookieid,之后就报错,内存不够了。大数据集更不用说。

基数估计方法测试

采用streamlib中的基数估计算法实现ICardinality,对两个结果集的总记录数和去重记录数进行统计,代码如下:

package com.lxw1234.streamlib;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

import com.clearspring.analytics.stream.cardinality.AdaptiveCounting;
import com.clearspring.analytics.stream.cardinality.ICardinality;

public class TestCardinality {

	public static void main(String[] args) {
		Runtime rt = Runtime.getRuntime();
		long start = System.currentTimeMillis();
		long updateRate = 1000000l;
		long count = 0l;
		ICardinality card = AdaptiveCounting.Builder.obyCount(Integer.MAX_VALUE).build();
		
		File file = new File(args[0]);
	    BufferedReader reader = null;
	    try {
	    	reader = new BufferedReader(new FileReader(file));
	    	String tempString = null;
	    	while ((tempString = reader.readLine()) != null) {
	    		card.offer(tempString);
	    		count++;
	    		if (updateRate > 0 && count % updateRate == 0) {
	                System.out.println("Total count:[" + count + "]  Unique count:[" + card.cardinality() + "] FreeMemory:[" + rt.freeMemory() + "] ..");
	            }
	    	}
	    	reader.close();
	    } catch (Exception e) {
	    	e.printStackTrace();
	    } finally {
	    	if (reader != null) {
		    	try {
		    		reader.close();
		    	} catch (IOException e1) {}
	    	}
	    }
	    long end = System.currentTimeMillis();
	    System.out.println("Total count:[" + count + "]  Unique count:[" + card.cardinality() + "] FreeMemory:[" + rt.freeMemory() + "] ..");
		System.out.println("Total cost:[" + (end - start) + "] ms ..");
	}
}

  • 测试数据集1

指定使用10M的内存运行,测试数据集1命令为:

java -cp /tmp/stream-2.9.1-SNAPSHOT.jar:/tmp/teststreamlib.jar -Xms10M -Xmx10M -XX:PermSize=10M -XX:MaxPermSize=10M  \
com.lxw1234.streamlib.TestCardinality /home/liuxiaowen/site_raw_log/small_cookies.txt

运行结果如下:

streamlib

  • 测试数据集2

同样指定使用10M的内存运行,测试数据集2命令为:

java -cp /tmp/stream-2.9.1-SNAPSHOT.jar:/tmp/teststreamlib.jar -Xms10M -Xmx10M -XX:PermSize=10M -XX:MaxPermSize=10M  \
com.lxw1234.streamlib.TestCardinality /home/liuxiaowen/site_raw_log/big_cookies.txt

运行结果为:

streamlib

测试结果

streamlib

 

测试结果来看,基数估计算法统计的结果中误差的确是0~2%,如果可以接受这个误差,那么这个方案完全可以用于实时计算中的不同维度UV统计中。

从运行结果图上可以看到,虽然指定了10M内存,但空闲内存(FreeMemory)一直在差不多7M以上,也就是说,5.4亿的数据去重计数,也仅仅使用了3M左右的内存。

相关下载

以上程序需要依赖stream-2.9.1-SNAPSHOT.jar,我编译好了一份,

点击下载stream-2.9.1-SNAPSHOT.jar

你也可以从官网中下载源码,编译。

相关文章:

http://blog.csdn.net/hguisu/article/details/8433731

http://m.oschina.net/blog/315457

您可以关注 lxw的大数据田地 ,或者 加入邮件列表 ,随时接收博客更新的通知邮件。

 

如果觉得本博客对您有帮助,请 赞助作者

转载请注明:lxw的大数据田地 » Java使用极小的内存完成对超大数据的去重计数,用于实时计算中统计UV

喜欢 (18)
分享 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(1)个小伙伴在吐槽
  1. 基数估计算法要求样本hash后均匀分布,但实际情况是不满足的,错误率不稳定,2000W级别uv去重误差波动会超过20%,生产不可用。
    xxx2017-07-28 15:57 回复