大数据去重(data deduplication)方案

大数据开发-Spark Join原理详解

数据去重(data deduplication)是大数据领域司空见惯的问题了。除了统计UV等传统用法之外,去重的意义更在于消除不可靠数据源产生的脏数据——即重复上报数据或重复投递数据的影响,使计算产生的结果更加准确。

介绍下经常使用的去重方案:

一、布隆过滤器(BloomFilter)

基本原理:

BloomFilter是由一个长度为m比特的位数组(bit array)k个哈希函数(hash function)组成的数据结构。位数组均初始化为0,所有哈希函数都可以分别把输入数据尽量均匀地散列。当要插入一个元素时,将其数据分别输入k个哈希函数,产生k个哈希值。以哈希值作为位数组中的下标,将所有k个对应的比特置为1。当要查询(即判断是否存在)一个元素时,同样将其数据输入哈希函数,然后检查对应的k个比特。如果有任意一个比特为0,表明该元素一定不在集合中。如果所有比特均为1,表明该集合有(较大的)可能性在集合中。为什么不是一定在集合中呢?因为一个比特被置为1有可能会受到其他元素的影响,这就是所谓“假阳性”(false positive)。相对地,“假阴性”(false negative)在BloomFilter中是绝不会出现的。

实现参考:

1、Guava中的布隆过滤器:com.google.common.hash.BloomFilter类

2、开源java实现:https://github.com/Baqend/Orestes-Bloomfilter

Redis Bloom Filter扩展:

基于redis做存储后端的BloomFilter实现,可以将bit位存储在redis中,防止计算任务在重启后,当前状态丢失的问题。

二、HyperLogLog(HLL)

HyperLogLog是去重计数的利器,能够以很小的精确度误差作为trade-off大幅减少内存空间占用,在不要求100%准确的计数场景下常用。

在用Flink做实时计算的过程中,可以用HLL去重计数,比如统计UV。

实现参考:

https://github.com/aggregateknowledge/java-hll

结合Flink,下面的聚合函数即可实现从WindowedStream按天、分key统计PV和UV。

WindowedStream<AnalyticsAccessLogRecord, Tuple, TimeWindow> windowedStream = watermarkedStream
  .keyBy("siteId")
  .window(TumblingEventTimeWindows.of(Time.days(1)))
  .trigger(ContinuousEventTimeTrigger.of(Time.seconds(10)));

windowedStream.aggregate(new AggregateFunction<AnalyticsAccessLogRecord, Tuple2<Long, HLL>, Tuple2<Long, Long>>() {
  private static final long serialVersionUID = 1L;

  @Override
  public Tuple2<Long, HLL> createAccumulator() {
    return new Tuple2<>(0L, new HLL(14, 6));
  }

  @Override
  public Tuple2<Long, HLL> add(AnalyticsAccessLogRecord record, Tuple2<Long, HLL> acc) {
    acc.f0++;
    acc.f1.addRaw(record.getUserId());
    return acc;
  }

  @Override
  public Tuple2<Long, Long> getResult(Tuple2<Long, HLL> acc) {
    return new Tuple2<>(acc.f0, acc.f1.cardinality());
  }

  @Override
  public Tuple2<Long, HLL> merge(Tuple2<Long, HLL> acc1, Tuple2<Long, HLL> acc2) {
    acc1.f0 += acc2.f0;
    acc1.f1.union(acc2.f1);
    return acc1;
  }
});

三、Roaring Bitmap 

布隆过滤器和HyperLogLog,虽然它们节省空间并且效率高,但也付出了一定的代价,即:

计量经济学导论08:平稳时间序列

  • 只能插入元素,不能删除元素;
  • 不保证100%准确,总是存在误差。

这两个缺点可以说是所有概率性数据结构(probabilistic data structure)做出的trade-off,毕竟鱼与熊掌不可兼得。

如果一定追求100%准确,普通的位图法显然不合适,应该采用压缩位图(Roaring Bitmap)。

基本原理:

将32位无符号整数按照高16位分桶,即最多可能有216=65536个桶,称为container。存储数据时,按照数据的高16位找到container(找不到就会新建一个),再将低16位放入container中。也就是说,一个RBM就是很多container的集合。

实现参考:

https://github.com/RoaringBitmap/RoaringBitmap

使用限制:

  • 对去重的字段只能用int或者long类型;
  • 对于无法有效压榨的字段(如随机生成的),占用内存较大

四、外部存储去重

利用外部K-V数据库(Redis、HBase之类)存储需要去重的键。由于外部存储对内存和磁盘占用同样敏感,所以也得设定相应的TTL,以及对大的键进行压缩。另外,外部K-V存储毕竟是独立于应用之外的,一旦计算任务出现问题重启,外部存储的状态和内部状态的一致性(是否需要同步)也是要注意的。

外部存储去重,比如Elasticsearch的 _id 就可以做“去重”功能,但是这种去重的只能针对少量低概率的数据,对全量数据去重是不合适的,因为对ES会产生非常大的压力。

 

参考:

高效压缩位图RoaringBitmap的原理与应用

谈谈三种海量数据实时去重方案

Flink基于RoaringBitmap的精确去重方案

 

【史上最全】Hadoop 核心 – HDFS 分布式文件系统详解(上万字建议收藏)

人已赞赏
经验教程

【一天一个基础系列】- java之泛型篇

2021-2-9 11:16:00

经验教程

大数据开发-Spark Join原理详解

2021-2-9 11:41:00

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索