大数据去重方案

2022-12-11 Views 大数据数据去重

#大数据 #数据去重

非精确方案

BloomFilter

将数据通过一组哈希函数映射到一个超大的位数组上面，判断是用同一个哈希函数映射，如果位数组上都有值则已存在。
优点： 占用空间少
缺点： 判断存在时。该方案存在一定的误差。

HyperLogLog

待补充.

精确方案

SET内存去重

优点： 速度快
缺点： 内存有限，不适合大数据量场景

数据库去重

优点： 处理简单，支持大数据场景
缺点： 如果数据本身不是在数据库中，需要先写入数据库。数据量多网络IO则非常频繁

HASH分治去重

将数据hash拆分到不同的小文件中，然后再对这些小文件使用内存去重
优点： 能解决大数据场景
缺点： 如果没法预估数据量大小，则不好评估要拆分到多少个文件。另外处理完后需要维护这些文件的删除（是否有临时表的自动删除逻辑？待验证。）

SQLITE去重

单独把这个列出来，主要觉得跟传统的数据库还是有区别的，因为这个不需要网络IO。
优点： 处理简单，支持大数据场景，不需要网络IO。
缺点： 依赖第三组件，一般linux都默认安装有，另外SQLITE3的写锁是库级别的，并行去做多个去重需要建单独的库，不是同一个表库中使用不同的表。

Linux命令去重

sort -us --buffer-size=1G %s | wc -l

sort: 默认是按ASCII码进行排序的
选项：
    -u: 去掉重复
    -s: 通过禁止最后比较来实现稳定排序
    --buffer-size: 设置主内存的大小缓冲区， 可不设置。
 
wc: 打印出文本的行，词数，和字节数
选项：
    -l: 行数

本质是先排序，然后移除相邻重复行达到去重的效果。
优点： 性能优秀
缺点：

去重完后需要人工清理文件，中途程序挂了会导致文件未删。
终止了程序进程，这个linux进程依旧存在，需要人工删除。

Bitmap

对有限枚举的数据范围，比如int类型范围，生成一个超大的数组位。每个位表示一个值的映射。
优点： 性能高
缺点： 使用范围有限，无论数据很小，空间成本都是固定大

SQLITE去重和Linux命令去重性能简单测试

因业务要求数据准确，以及方案更为通用，只考虑选择的sqlite和linux去重两方案测试，其中sqlite3还能衍生出两个方式。以下是测试的记录：

sqlite3普通列： 表结构只有一个普通列，不设置主键唯一键，1亿个字符串，每次批量写10000，耗时115秒。使用select distinct 去重查询总数耗时300秒

sqlite3主键列： 表结构主键列，写列为主键，1亿个字符串，每次批量写10000，耗时3151秒。使用select distinct 去重查询总数耗时50秒

Linux命令去重： 1亿个字符串写如文件耗时15秒，使用前面的linux命令去重查询耗时55秒

性能测试结论

性能上： Linux命令去重 > sqlite3普通列 >> sqlite3主键列
当然测试并没有考虑到并发，机器资源利用率的指标，只能得出一个大体的结论。

总结

SET内存去重处理小数据量的场景中效果较好，但在处理大数据量的场景中会受到限制；Bitmap，BloomFilter和HyperLogLog去重都有其局限性；比较通用可靠的方案是Linux命令去重和SQLITE去重。
另外：flink也支持大数据去重，依赖内置的RocksDB数据库，但因我们这边业务场景上不适合flink，就没有考虑该方案进来。

WOLTZ笔记