Java使用极小的内存完成对超大数据的去重计数，用于实时计算中统计UV – lxw的大数据田地 http://lxw1234.com/archives/2015/09/516.htm

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

编程语言  lxw1234@qq.com  3年前 (2015-09-25)  15132℃  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）

1. [liuxiaowen@dev site_raw_log]$ head -5 small_cookies.txt
2. 7EDCF13A03D387548FB2B8
3. da5f0196-56036078075b9f-14892137
4. 1D0A83B604ADD4558970EE
5. 3DF76E7100025F553B1980
6. 72C756700C3CAA56035EE0
7. [liuxiaowen@dev site_raw_log]$ wc -l small_cookies.txt
8. 14892708 small_cookies.txt
9. [liuxiaowen@dev site_raw_log]$ awk ‘!a[$0]++{print $0}’ small_cookies.txt | wc -l
10. 3896911
11. [liuxiaowen@dev site_raw_log]$ ll small_cookies.txt
12. -rw-rw-r–. 1 liuxiaowen liuxiaowen 350153062 Sep 25 10:50 small_cookies.txt

测试数据集2：

• 文件名：big_cookies.txt
• 文件内容：每个cookieid一行
• 文件总记录数：547631464
• 去重记录数：190264959
• 文件总大小：12610638153（约11.8GB）

1. –总记录数
2. spark-sql> select count(1) from big_cookies;
3. 547631464
4. Time taken: 7.311 seconds, Fetched 1 row(s)
5. –去重记录数
6. spark-sql> select count(1) from (select cookieid from big_cookies group by cookieid) x;
7. 190264959
8. Time taken: 80.516 seconds, Fetched 1 row(s)
9. hadoop fs -getmerge /hivedata/warehouse/liuxiaowen.db/big_cookies/* big_cookies.txt
10. [liuxiaowen@dev site_raw_log]$ wc -l big_cookies.txt
11. 547631464 cookies.txt
12. //总大小
13. [liuxiaowen@dev site_raw_log]$ ll big_cookies.txt
14. -rw-r–r–. 1 liuxiaowen liuxiaowen 12610638153 Sep 25 13:25 big_cookies.txt

普通方法测试

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

代码如下：

1. package com.lxw1234.streamlib;
2. import java.io.BufferedReader;
3. import java.io.File;
4. import java.io.FileReader;
5. import java.io.IOException;
6. import java.util.HashSet;
7. import java.util.Set;
8. public class Test {
9. public static void main(String[] args) {
10. Runtime rt = Runtime.getRuntime();
11. Set set = new HashSet();
12. File file = new File(args[0]);
13. BufferedReader reader = null;
14. long count = 0l;
15. try {
16. reader = new BufferedReader(new FileReader(file));
17. String tempString = null;
18. while ((tempString = reader.readLine()) != null) {
19. count++;
20. set.add(tempString);
21. if(set.size() % 5000 == 0) {
22. System.out.println(“Total count:[” + count + “] Unique count:[” + set.size() + “] FreeMemory:[” + rt.freeMemory() + “] ..”);
23. }
24. }
25. reader.close();
26. } catch (Exception e) {
27. e.printStackTrace();
28. } finally {
29. if (reader != null) {
30. try {
31. reader.close();
32. } catch (IOException e1) {}
33. }
34. }
35. System.out.println(“Total count:[” + count + “] Unique count:[” + set.size() + “] FreeMemory:[” + rt.freeMemory() + “] ..”);
36. }
37. }

指定使用10M的内存运行，命令为：

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

运行结果如下：

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

基数估计方法测试

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

1. package com.lxw1234.streamlib;
2. import java.io.BufferedReader;
3. import java.io.File;
4. import java.io.FileReader;
5. import java.io.IOException;
6. import com.clearspring.analytics.stream.cardinality.AdaptiveCounting;
7. import com.clearspring.analytics.stream.cardinality.ICardinality;
8. public class TestCardinality {
9. public static void main(String[] args) {
10. Runtime rt = Runtime.getRuntime();
11. long start = System.currentTimeMillis();
12. long updateRate = 1000000l;
13. long count = 0l;
14. ICardinality card = AdaptiveCounting.Builder.obyCount(Integer.MAX_VALUE).build();
15. File file = new File(args[0]);
16. BufferedReader reader = null;
17. try {
18. reader = new BufferedReader(new FileReader(file));
19. String tempString = null;
20. while ((tempString = reader.readLine()) != null) {
21. card.offer(tempString);
22. count++;
23. if (updateRate > 0 && count % updateRate == 0) {
24. System.out.println(“Total count:[” + count + “] Unique count:[” + card.cardinality() + “] FreeMemory:[” + rt.freeMemory() + “] ..”);
25. }
26. }
27. reader.close();
28. } catch (Exception e) {
29. e.printStackTrace();
30. } finally {
31. if (reader != null) {
32. try {
33. reader.close();
34. } catch (IOException e1) {}
35. }
36. }
37. long end = System.currentTimeMillis();
38. System.out.println(“Total count:[” + count + “] Unique count:[” + card.cardinality() + “] FreeMemory:[” + rt.freeMemory() + “] ..”);
39. System.out.println(“Total cost:[” + (end – start) + “] ms ..”);
40. }
41. }

• 测试数据集1

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

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

运行结果如下：

• 测试数据集2

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

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

运行结果为：

测试结果

测试结果来看，基数估计算法统计的结果中误差的确是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