Guava

Stella981
• 阅读 631

背景

原有的去重方案是:

  1. 使用linux命令去重
    • 缺点
      1. 出现问题只能重来,控制粒度很粗。
      2. 程序与操作系统过渡耦合,如果系统中sort或者uniq命令出现问题,则去重功能不能使用。
      3. 使得push opt的用户数据以文件的形式存在,不方便多主机、操作系统共享,妨碍后期push opt多主节点发展。
    • 优点
      1. 实现简单
      2. 一般功能稳定
  2. 使用tair去重
    • 缺点
      1. 浪费大量珍贵的内存资源
      2. 不一定可靠,也可能丢失数据
      3. tair出现问题后,用户去重功能彻底不能使用。
    • 优点
      1. 一般不会出现问题;
      2. 访问迅速;
      3. 接近O(1)时间复杂度得知哪条重复。
      4. 适合分布式系统中去重

为什么使用布隆过滤器

原理

Guava
初始化:对于x,y,z三个数,经过{k1,k2,k3}三个hash函数,将向量空间中的某些位置标记为1,作为初始向量空间。

判断:当新进入一个数据,w,进过{k1,k2,k3}hash函数,在向量空间上所有位置均为1,表示命中这个数,这个数已经在bloomfilter中。如果部分为1或者全为0,表示这个数不在bloomfilter中。

性能分析

参考:csdn博客

如果hash函数个数为k个,那么bloom过滤器插入和判断一个数的时间复杂度是O(k),空间复杂度为O(size)。size为bloomfilter的位数组大小。

优缺点分析

  • 优点:常数时间复杂度,占用很少的内存。
  • 缺点:不会漏判一个已经发送过的token,但是可能误判一个每发送过的为发送了。此时发生了hash冲突。但是当hash空间一定大的时候,是可以降低冲突的。还有发送push,少发了几个是可以容忍的。(类似tair丢失极少量数据是可以容忍的)

使用

Guava的布隆过滤器通过调用BloomFilter类的静态函数创建,传递一个Funnel对象以及一个代表预期插入数量的整数。

Funnel对象的作用,将数据发送给一个接收器(Slink)。

package guava;

import com.google.common.base.Strings;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnel;
import com.google.common.hash.PrimitiveSink;
import org.junit.Before;
import org.junit.Test;

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.nio.charset.Charset;
import java.util.List;
import java.util.Map;
import java.util.Random;

/**
 * Created by hgf on 16/8/25.
 */
public class BloomFilterTest {

    private BloomFilter<String> bloomFilter;

    private final static String TOKEN = "token-[0-9]+";

    private final static String prefix = "token-";

    private List<String> tokens = Lists.newArrayList();

    private Map<String, Integer> map = Maps.newHashMap();

    private Map<String, Integer> reflect = Maps.newHashMap();

    @Before
    public void init() {
        Random random = new Random();

        for (int i = 0; i < 10000; i++) {
            tokens.add(prefix + random.nextInt(10000));
        }
        try {
            writeSource();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    @Test
    public void test() {
    //此处使用的是自定义funnel,可以使用guava默认实现的funnel。
    //全部实现在Funnels中。Funnels.stringFunnel(Charset.defaultCharset())
    //注意此处布隆过滤器大小,应估算的稍大
        bloomFilter = BloomFilter.create(stringFunnel(), tokens.size());

        int repeatTimes = 0;
        for (String token : tokens) {
            //参照数据
            Integer tmp = reflect.get(token);
            if (tmp == null) {
                reflect.put(token, 1);
            } else {
                reflect.put(token, tmp + 1);
            }

            //布隆过滤器数据
            boolean hasToken = bloomFilter.mightContain(token);
            if (hasToken) {
                Integer times = map.get(token);
                if (times == null) {
                    map.put(token, 2);
                } else {
                    map.put(token, times + 1);
                }
                repeatTimes++;
            } else {
                bloomFilter.put(token);
            }
        }

        System.out.println("随机token中重复次数:" + repeatTimes);
//        //打印重复的token
//        System.out.println("bloom filter 判断为重复的token数:" + map);

        compareResult();
    }

    private void compareResult() {

        int wrongCount = 0;
        for (String token : map.keySet()) {
            Integer tmp = map.get(token);
            if (!(tmp != null && tmp.intValue() == reflect.get(token).intValue())) {
                wrongCount++;
                System.out.println("错误统计:\t" + token + "\t" + tmp + "\t" + reflect.get(token));
            }
        }
        System.out.println("总统计出错,对比结果:" + wrongCount+"次");
    }

    private void writeSource() throws IOException {
        File file = new File("source.txt");
        try (BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(file))) {
            for (String token : tokens) {
                bufferedWriter.write(token);
                bufferedWriter.newLine();
            }
        }

    }

    public static Funnel<String> stringFunnel() {
        return StringFunnel.INSTANCE;
    }

    private enum StringFunnel implements Funnel<String> {
        INSTANCE;

        @Override
        public void funnel(String from, PrimitiveSink into) {
            if (isToken(from)) {
                into.putString(from, Charset.defaultCharset());
            }
        }

        private boolean isToken(String token) {
            return (!Strings.isNullOrEmpty(token) && token.matches(TOKEN));
        }

    }
}

输出结果

随机token中重复次数:3709
错误统计:   token-7746  2   1
错误统计:   token-5714  2   1
错误统计:   token-1718  3   2
错误统计:   token-7065  3   2
错误统计:   token-8875  4   3
错误统计:   token-3599  2   1
错误统计:   token-8563  2   1
总统计出错,对比结果:7次

注意点

预期插入数量是很关键的一个参数。当插入的数量接近或高于预期值的时候,布隆过滤器将会填满,这样的话,它会产生很多无用的误报点。

有另一个版本的 BloomFilter.create 方法,它额外接收一个参数,一个代表假命中概率水平的双精度数字(必须大于零且小于1)

假命中概率等级影响哈希表储存或搜索元素的数量。百分比越,哈希表的性能越好

场景

适用判断一个元素是否在某个集合(该集合往往数据量庞大)出现,并允许一定小概率错误的场景。
例如:判断一个url或者邮件地址或者token,是否出现在给定集合中。

  • 做缓存的时候,使用bloomfilter,不给只访问过一次的数据做缓存,数据量大但是大多都只需要访问一次。
  • 对大型分布式的NOSQL,使用布隆过滤器判断某一行数据是否存在,避免无谓的磁盘读写和查找。HBASE,BIGTABLE
  • 判断恶意网址。
  • 避免爬虫爬取同样的url,陷入爬取旋涡。
  • 推荐网站避免给用户推送同样的url。

与Tair方案对比

优势:

  • 判断重复节约大量内存空间。

劣势:

  • 在分布式场景中,目前需要自己包装服务。
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Easter79 Easter79
3年前
swap空间的增减方法
(1)增大swap空间去激活swap交换区:swapoff v /dev/vg00/lvswap扩展交换lv:lvextend L 10G /dev/vg00/lvswap重新生成swap交换区:mkswap /dev/vg00/lvswap激活新生成的交换区:swapon v /dev/vg00/lvswap
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
Android So动态加载 优雅实现与原理分析
背景:漫品Android客户端集成适配转换功能(基于目标识别(So库35M)和人脸识别库(5M)),导致apk体积50M左右,为优化客户端体验,决定实现So文件动态加载.!(https://oscimg.oschina.net/oscnet/00d1ff90e4b34869664fef59e3ec3fdd20b.png)点击上方“蓝字”关注我
Easter79 Easter79
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
为什么mysql不推荐使用雪花ID作为主键
作者:毛辰飞背景在mysql中设计表的时候,mysql官方推荐不要使用uuid或者不连续不重复的雪花id(long形且唯一),而是推荐连续自增的主键id,官方的推荐是auto_increment,那么为什么不建议采用uuid,使用uuid究
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这