type
status
date
slug
summary
tags
category
icon
password
Bitmap的基本思想是以一个bit位来表示一个元素对应的value，即使用bit数组下标来表示元素值，以大大缩小存储空间。BitMap一般用来快速查找、去重、删除等操作，但是它只能用于数字类型。那么如果要使用字符串类型的该怎么办呢？
这就需要先把字符串字典编码，生成字符串到数字的映射。本文参考kylin的全局字典编码配合RoaringBitmap以实现精准去重。

AppendTrie树

Trie树
Trie树又名前缀树，是是一种有序树，一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，根节点对应空字符串，而每个字符串对应的编码值由对应节点在树中的位置来决定。
AppendTrie树
Trie 树模型可以实现 Append，有两种方式：
  • 按照节点 ( 而不是位置 ) 保存 ID，从而保持已有 ID 不变。
  • 记录当前模型最大 ID，便于给新增节点分配 ID 。
但是这种模型会带来一个问题：假如基数特别大，Trie 树在内存中就会无限扩张。为了控制内存占用率，选择单颗子树设定阈值，超过即分裂，进而控制单颗子树内存消耗。分裂后，每棵树负责一个范围 ( 类似于 HBase 中的 region 分区 ) ；查询时候只需要查询一颗子树即可。
注：本文直接使用Kylin构建全局字典类AppendTrieDictionaryBuilder。

构建字典任务

BuildDictJob
SelfDefineSortableKey
GlobalDictionaryBuilder

分布式锁

DistributedLock
ZookeeperDistributedLock

精准去重-举例

此处举个使用精准去重的例子，我们使用flink消费kafka数据入ClickHouse的过程中按天去重。
使用字典
自定义MapFunction，把字符串通过字典转为编码id。
构建Bitmap
自定义ProcessFunction，此处我们使用性能较好的RoaringBitmap构建Bitmap，并且在第二天0时清空Bitmap。
自定义Sink
自定义Sink入ClickHouse：
任务
其他精准去重
  • 基于Redis自增id，实时生成编码，进行去重。
  • 使用Flink自带的RocksDB进行去重，此方式不适合大数据量。
此处我们提供RocksDB去重例子，RocksDBDistinctFunction：
参考：
大数据监控-Metrics2录入指标到OpenTSDB元数据平台-数据血缘