问题背景
flink广播变量适用于解决活动配置、白名单等应用场景,根据活动配置或者白名单过滤数据后再做后续加工处理。广播出去的变量存在于每个节点的内存中,所以这个数据集不能太大。如果海量数据中,需要过滤出几百万甚至上亿的白名单用户数据,用广播变量广播大量用户uid,显然不合适。
另外,实际的场景,白名单用户可能会增删,增加了要能检查出来,删除了不一定需要,宁可放过,不能错杀(主要是后面数据不关心因误判导致多余用户的数据)。
解决方案
根据前面问题描述,布隆过滤器是一个很好的解决方案,不需要太大的内存,也满足宁可放过不许错杀的要求。
标准布隆过滤器
使用标准布隆过滤器,任务启动时候先将白名单用户写入布隆过滤器。然后数据流进来时,使用布隆过滤器检查用户是否已经存在:如果存在,有可能实际不存在;如果不存在,那就一定不存在。
优点:
- Bloom filter 优点就是它的插入和查询时间都是常数
- 查询元素却不保存元素本身,具有良好的安全性
缺陷:
- 可能误判,实际用户不存在白名单
- 不能增加白名单,不能删除白名单
计数布隆过滤器
标准Bloom filter对于需要精确检测结果的场景将不再适用,而带计数器的Bloom filter的出现解决了这个问题。Counting Bloom filter实际只是在标准Bloom filter的每一个位上都额外对应得增加了一个计数器,在插入元素时给对应的 k (k 为哈希函数个数)个 Counter 的值分别加 1,删除元素时给对应的 k 个 Counter 的值分别减 1。 优点:
缺点:
布谷鸟过滤器
布谷鸟过滤器,它可以代替布隆过滤器进行集合近似隶属度测试。 布谷鸟过滤器支持动态添加和删除项,同时实现比布隆过滤器更高的性能。对于存储了许多条目且设置较低假阳性率的应用程序,布谷鸟过滤器比空间优化过的布隆过滤器具有更低的空间开销。我们的实验结果还表明,布谷鸟过滤器在时间和空间上的性能都优于此前那些扩展了布隆过滤器以支持删除的数据结构。
优点:
- 支持删除操作
- 性能比标准过滤器高
- 空间利用率比标准过滤器高
缺点:
|