精华内容
下载资源
问答
  • 主要介绍了python使用布隆过滤器的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • Redis原生是不带有布隆过滤器的,Redis 4.0之后支持插件,可以安装插件,这样就可以使用布隆过滤器了。 项目地址: https://github.com/RedisBloom/RedisBloom (我自己fork的地址:...

    Redis原生是不带有布隆过滤器的,Redis 4.0之后支持插件,可以安装插件,这样就可以使用布隆过滤器了。

    项目地址:
    https://github.com/RedisBloom/RedisBloom
    (我自己fork的地址:https://github.com/M000M/RedisBloom)

    安装布隆过滤器插件步骤:

    1. git clone 项目地址
    2. 进入项目RedisBloom
    3. make 编译代码
    4. 可以看到 redisbloom.so 文件
    5. 重新启动redis,带上相应的插件就能使用布隆过滤器了
    6. 执行命令
      redis-server redis-6379.conf --loadmodule (RedisBloom项目所在的路径)/RedisBloom/redisbloom.so [INITIAL_SIZE 100000] (INITIAL_SIZE可以不写,使用默认的)
    7. 登录Redis客户端就可以使用Bloom Filter了
    8. 命令 bf.add 添加; bf.exists 判断对应的布隆过滤器中是否存在指定的值
      在这里插入图片描述
      1. 新建布隆过滤器
      bf.reserve {key} {error_rate} {size}
      error为容错率,取值范围我饿 0 ~ 1;数值越小,占用内存越大,占用CPU资源越大;
      size为容量,添加的条目超过这个数值后,性能将开始下降;实际降级将取决于超过的程度;随着条目呈指数增长,性能将呈线性下降;
      2. 添加过滤器与值
      bf.add {key} {value}
      当key对应的Bloom Filter不存在时,将添加新的名为key的Bloom Filter,使用默认的error_rate和size;
      3. 判断Bloom Filter中是否存在某个值
      bf.exists {key} {value}
      存在返回1,否则返回0
    展开全文
  • scrapy使用布隆过滤器实现增量爬取 之前看了很多关于scrapy-redis使用bloomfilter进行持久化存储进行url去重的例子,可是发现没有一种适用于scrapy,于是萌生了基于现有scrapy-redis-bloomfilter库进行改写的想法。 ...
  • 使用布隆过滤器的基于云的迭代标签搜索协议
  • 此时便可以使用布隆过滤器来解决。 请求到来时,先用布隆过滤器判断数据是否有效,布隆过滤器可以判断元素一定不存在和可能存在,对于一定不存在的数据,则可以直接丢弃请求。对可能存在的请求,再去访问Redis获取...

    引言
     在海量数据面前如何去过滤,及查找数据。下面有几个问题:

    1. 总共有50亿个电话号码,现在已经知道10万个号码,如何在这100亿个电话号码中去快速判断这些10万个号码是否存在?

    2. 垃圾邮件过滤。

    3.wps文字处理软件错误单词的检测。

    4. 网络爬虫重复URL检测。

    5. Hbase行过滤器。
       上面的问题都有一些特点,数据量很大,并且要在海量数据中查找其中几条或者部分数据。看看常规的解决方法及问题:

    1. 所有数据放在数据库,通过数据库查询,但是实现快速查询有点困难。

    2. 数据全部放在集合里,数据所占空间:50亿 * 8字节 = 大约40G,内存浪费而且数据量更大内存空间不一定够。

    3. Redis的hyperloglog,查询不够准确。

    当数据量较小,内存又足够大时,使用hashMap或者hashSet等结构就好了。但是如果当这些数据量很大,数十亿甚至更多,内存装不下且数据库检索又极慢的情况,在1970年伯顿.布隆就提出了可以用很小的空间来解决上面那些类似问题。

    布隆过滤器基本原理

    用一个很长的二进制向量( 也可以理解成bit数组)和若干个哈希函数,这些哈希函数通过计算你要找到的值是否映射在这个二进制向量中。

    布隆过滤器初始化的时候bit数组里的值都是0.

    当我们将一个元素加入布隆过滤器中的时候,会进行如下操作:

    1. 使用布隆过滤器中的哈希函数对元素值进行计算,得到哈希值(也就是bit数组中的索引位置,有多少个个哈希函数就会得到多少个哈希值)。

    2. 根据得到的哈希值,在bit数组中把这些哈希值对应下标的值都置为 1。

    当我们判断一个元素是否存在于布隆过滤器的时候,会进行如下操作:

    1. 对给定元素再次进行相同的哈希计算;

    2. 得到值之后判断位数组中的每个元素是否都为 1,如果值都为 1,那么说明这个值在布隆过滤器中,如果存在一个值不为 1,说明该元素不在布隆过滤器中。

    布隆过滤器解决穿透问题

    使用redis时候在某种情况下,可能会出现缓存雪崩和缓存穿透。
    缓存穿透:大量请求访问时,Redis没有命中数据,导致请求绕过了Redis缓存,直接去访问数据库了。数据库难以承受大量的请求。
    此时便可以使用布隆过滤器来解决。
    请求到来时,先用布隆过滤器判断数据是否有效,布隆过滤器可以判断元素一定不存在和可能存在,对于一定不存在的数据,则可以直接丢弃请求。对可能存在的请求,再去访问Redis获取数据,Redis没有时,再去访问数据库。

    ps:对于穿透几种解决方案
    解决方案:有很多种方法可以有效地解决缓存穿透问题,最常见的则是采用布隆过滤器,将所有可能存在的数据哈希到一个足够大的bitmap中,一个一定不存在的数据会被 这个bitmap拦截掉,从而避免了对底层存储系统的查询压力。另外也有一个更为简单粗暴的方法(我们采用的就是这种),如果一个查询返回的数据为空(不管是数 据不存在,还是系统故障),我们仍然把这个空结果进行缓存,但它的过期时间会很短,最长不超过五分钟。

    代码实现
    pom

    <dependency>
                <groupId>com.google.guava</groupId>
                <artifactId>guava</artifactId>
                <version>22.0</version>
            </dependency>
    

    核心类

    package com.config;
     
    import com.google.common.base.Preconditions;
    import com.google.common.hash.Funnel;
    import com.google.common.hash.Hashing;
    import org.springframework.beans.factory.annotation.Configurable;
     
    @Configurable
    public class BloomFilterHelper<T> {
        private int numHashFunctions;
        private int bitSize;
        private Funnel<T> funnel;
     
        public BloomFilterHelper(Funnel<T> funnel, int expectedInsertions, double fpp) {
            Preconditions.checkArgument(funnel != null, "funnel不能为空");
            this.funnel = funnel;
            bitSize = optimalNumOfBits(expectedInsertions, fpp);
            numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
        }
     
        public int[] murmurHashOffset(T value) {
            int[] offset = new int[numHashFunctions];
     
            long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();
            int hash1 = (int) hash64;
            int hash2 = (int) (hash64 >>> 32);
            for (int i = 1; i <= numHashFunctions; i++) {
                int nextHash = hash1 + i * hash2;
                if (nextHash < 0) {
                    nextHash = ~nextHash;
                }
                offset[i - 1] = nextHash % bitSize;
            }
     
            return offset;
        }
     
        /**
         * 计算bit数组长度
         */
        private int optimalNumOfBits(long n, double p) {
            if (p == 0) {
                p = Double.MIN_VALUE;
            }
            return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
        }
     
        /**
         * 计算hash方法执行次数
         */
        private int optimalNumOfHashFunctions(long n, long m) {
            return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
        }
     
    }
    
    

    封装出来的工具类

    package com.redislock;
     
    import com.config.BloomFilterHelper;
    import com.google.common.base.Preconditions;
    import org.springframework.stereotype.Component;
    import redis.clients.jedis.JedisCluster;
     
    @Component
    public class RedisBloomFilter<T> {
        private JedisCluster cluster;
     
        public RedisBloomFilter(JedisCluster jedisCluster) {
            this.cluster = jedisCluster;
        }
     
        /**
         * 根据给定的布隆过滤器添加值
         */
        public <T> void addByBloomFilter(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {
            Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");
            int[] offset = bloomFilterHelper.murmurHashOffset(value);
            for (int i : offset) {
                //redisTemplate.opsForValue().setBit(key, i, true);
                cluster.setbit(key, i, true);
            }
        }
     
        /**
         * 根据给定的布隆过滤器判断值是否存在
         */
        public <T> boolean includeByBloomFilter(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {
            Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");
            int[] offset = bloomFilterHelper.murmurHashOffset(value);
            for (int i : offset) {
                //if (!redisTemplate.opsForValue().getBit(key, i)) {
                if (!cluster.getbit(key, i)) {
                    return false;
                }
            }
     
            return true;
        }
    }
    
    

    redis 配置

    
    spring.redis.cluster.nodes=127.0.0.1:7000,127.0.0.1:7001,127.0.0.1:7002,127.0.0.1:7003,127.0.0.1:7004,127.0.0.1:7005
    spring.redis.password=
    #连接池最大连接数(使用负值表示没有限制)
    spring.redis.pool.max-active=8
    #连接池最大阻塞等待时间(使用负值表示没有限制)
    spring.redis.pool.max-wait=-1
    #连接池中的最大空闲连接
    spring.redis.pool.max-idle=8
    #连接池中的最小空闲连接
    spring.redis.pool.min-idle=0
    #连接超时时间(毫秒)
    spring.redis.timeout=0
    spring.redis.commandTimeout=5000
    
    @Configuration
    public class RedisConfig {
        private Logger logger = LoggerFactory.getLogger(RedisConfig.class);
     
        @Value("${spring.redis.cluster.nodes}")
        private String clusterNodes;
        @Value("${spring.redis.timeout}")
        private int timeout;
        @Value("${spring.redis.pool.max-idle}")
        private int maxIdle;
        @Value("${spring.redis.pool.max-wait}")
        private long maxWaitMillis;
        @Value("${spring.redis.commandTimeout}")
        private int commandTimeout;
     
        @Bean
        public JedisCluster getJedisCluster() {
            String[] cNodes = clusterNodes.split(",");
            Set<HostAndPort> nodes = new HashSet<>();
            // 分割出集群节点
            for (String node : cNodes) {
                String[] hp = node.split(":");
                nodes.add(new HostAndPort(hp[0], Integer.parseInt(hp[1])));
            }
            JedisPoolConfig jedisPoolConfig = new JedisPoolConfig();
            jedisPoolConfig.setMaxIdle(maxIdle);
            jedisPoolConfig.setMaxWaitMillis(maxWaitMillis);
            return new JedisCluster(nodes, commandTimeout, jedisPoolConfig);
     
        }
     
     
        /**
         * redis序列化
         *
         * @param connectionFactory
         * @return
         */
        @Bean
        public RedisTemplate<String, Serializable> redisTemplate(LettuceConnectionFactory connectionFactory) {
            RedisTemplate<String, Serializable> redisTemplate = new RedisTemplate<>();
            redisTemplate.setKeySerializer(new StringRedisSerializer());
            redisTemplate.setValueSerializer(new GenericJackson2JsonRedisSerializer());
            redisTemplate.setConnectionFactory(connectionFactory);
            return redisTemplate;
        }
     
    }
    
    

    测试

    @SpringBootApplication
    @EnableDiscoveryClient
    @ComponentScan(value = {"com.annotaion", "cn.springcloud", "com.config", "com.redislock"})
    public class Ch34EurekaClientApplication implements ApplicationRunner {
     
        private static BloomFilterHelper<CharSequence> bloomFilterHelper;
     
        @Autowired
        RedisBloomFilter redisBloomFilter;
     
        public static void main(String[] args) {
            SpringApplication.run(Ch34EurekaClientApplication.class, args);
     
        }
     
        @PostConstruct
        public void init() {
            bloomFilterHelper = new BloomFilterHelper<>(Funnels.stringFunnel(Charset.defaultCharset()), 1000, 0.1);
        }
     
        @Override
        public void run(ApplicationArguments args) throws Exception {
     
     
     
    //******* Redis集群测试布隆方法*********
            int j = 0;
            for (int i = 0; i < 100; i++) {
                redisBloomFilter.addByBloomFilter(bloomFilterHelper, "bloom", i+"");
            }
            for (int i = 0; i < 1000; i++) {
                boolean result = redisBloomFilter.includeByBloomFilter(bloomFilterHelper, "bloom", i+"");
                if (!result) {
                    j++;
                }
            }
            System.out.println("漏掉了" + j + "个");
        }
    }
    
    展开全文
  • 布隆过滤器使用测试 1.添加布隆过滤器依赖 <!--引入布隆过滤器--> <dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId>...

    1.布隆过滤器可以解决redis缓存穿透问题

    2.使用布隆过滤器需要先预热key

    布隆过滤器使用测试

    1.添加布隆过滤器依赖

    <!--引入布隆过滤器-->
    <dependency>
    	<groupId>com.google.guava</groupId>
    	<artifactId>guava</artifactId>
    	<version>22.0</version>
    </dependency>

    2.测试demo

    //布隆过滤器测试
    public class BlongTest {
    
        //设置预热key 1000000万条
        private static Integer size = 1000000;
    
        public static void main(String[] args) {
            //创建一个布隆过滤器  size期望插入值  0.01误判率
            BloomFilter<Integer> integerBloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, 0.00001);
            for (int i = 0; i < size; i++) {
                //往布隆过滤器putkey
                integerBloomFilter.put(i);
            }
            //存放误判key的值
            List<Integer> list = new ArrayList<>();
    
            for (int i = size; i < size + 10000; i++) {
                //判断布隆过滤器存在key则加入数组
                if (integerBloomFilter.mightContain(i)) {
                    list.add(i);
                }
            }
            System.out.println(list.size()); //98 误判数
            //100万数据 误判率设置0.03(默认值)  二向数组长度值7298440  ==730万
            //100万数据 误判率设置0.01          二向数组长度值9585058  ==960万
            //100万数据 误判率设置0.001         二向数组长度值14377587 ==1437万
            //100万数据 误判率设置0.0001        二向数组长度值19170116 ==1917万
            //100万数据 误判率设置0.00001       二向数组长度值23962645 ==2396万
            //使用布隆过滤器需要先预热key
            //误判率减少10倍,数组长度大约增500万 ,一般默认0.03或者0.01就行
        }
    }

     

    展开全文
  • 使用布隆过滤器,先将数据库里面的数据放进布隆过滤器,然后使用布隆过滤器来判断是否存在对应的数据。 示例代码如下: private static int size = 1000_000; private static BloomFilter<Integer> ...

          解决缓存穿透有两种思路:

          1.当查询数据库不存在时,构造一个伪对象

          2.使用布隆过滤器,先将数据库里面的数据放进布隆过滤器,然后使用布隆过滤器来判断是否存在对应的数据。

             示例代码如下:

            

    private static int size = 1000_000;
    
        private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, 0.0001);
    
        static {
            for (int i = 0; i < size; i++) {
                bloomFilter.put(i);
            }
            System.out.println("write over!");
        }
    
        public static void main(String[] args) {
            StopWatch stopWatch = new StopWatch();
            stopWatch.start("布隆过滤器计算任务");
            boolean contain = bloomFilter.mightContain(20);
            stopWatch.stop();
            System.out.println(contain + "耗时" + stopWatch.prettyPrint());
    
    
        }

    展开全文
  • 文章目录如何判断一个元素是不是在一个集合里什么是布隆过滤器布隆过滤器的原理布隆过滤器应用的经典场景布隆过滤器优势和劣势使用GooleGuava实现BloomFilter 如何判断一个元素是不是在一个集合里 一般想到的是将...
  • Redis使用布隆过滤器

    2020-08-11 10:14:29
    现有50亿个电话号码,现有10万个电话号码,如何要快速准确的判断这些电话号码是否已经存在? 布隆过滤器是一种类似set的...Redis布隆过滤器的基本使用 在Redis中,布隆过滤器有两个基本命令,分别是: bf.add:添
  • python使用布隆过滤器

    2020-08-18 09:38:34
    # 可自动伸缩的布隆过滤器 bloom = ScalableBloomFilter(initial_capacity=100,error_rate=0.001) # 添加内容 bloom.add('daqi') print('daqi'in bloom) # 定长的布隆过滤器 bloom1 = BloomFilter(capacity=10000)...
  • 如何在springboot项目中redis使用布隆过滤器防止缓存穿透。 先引入依赖 <!--使用Redis--> <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-...
  • 它实际上是由一个很长的二进制向量(位向量)和一系列随机映射函数组成,布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率(假正例...
  • scrapy使用布隆过滤器

    2019-03-28 11:57:14
    pip install scrapy-redis-bloomfilter 在settings中这样配置: # Ensure use this Scheduler SCHEDULER = "scrapy_redis_bloomfilter.scheduler.Scheduler" # Ensure all spiders share same duplicates filter...
  • 场景 在实现聊天室时,需要对用户发布的信息进行敏感词过滤。敏感词过滤是cpu密集型服务,为提高聊天互动的实时性,除了做...采用BllomFilter 布隆过滤器,guava库有现成的实现,其核心思路是采用hash + bitmap, ...
  • 本文主要描述,使用布隆过滤实现高效缓存。文中采用数组做为缓存,如果需要高并发命中,则需将文中的数组换成Redis数据库。 布隆过滤 布隆缓存的创建过程如下: 1,先定义缓存bit数组(BitArray),数组的长度...
  • 文章目录布隆过滤器 - Redis 布隆过滤器,Guava 布隆过滤器 BloomFilter1、布隆过滤器的起源,用途2、布隆过滤器的概念3、布隆过滤器的优缺点1、优点2、缺点4、应用场景5、布隆过滤器的工作原理6、布隆过滤器的设计 ...
  • ctx: Trigger.TriggerContext): TriggerResult = //每来一次数据 TriggerResult.FIRE_AND_PURGE } // 自定义一个布隆过滤器,主要就是一个位图和hash函数 class Bloom(size: Long) extends Serializable{ private ...
  • FCache Extensions (version 1.0.3) ...Table of Contents Install phpize ./configure make clean && make make test make install ...extension=fcache.so ...fcache.data_dir="/usr/home/zhujun5/data" ...
  • self.bit_size = 1 的String类型最大容量为512M,现使用256M self.seeds = [5, 7, 11, 13, 31, 37, 61] self.key = key self.blockNum = blockNum self.hashfunc = [] for seed in self.seeds: self.hashfunc...
  • 文章目录布隆过滤器 - Redis 布隆过滤器,Guava 布隆过滤器 BloomFilter - 代码实践1、通过guava 实现的布隆过滤器2、通过 redisson 实现的布隆过滤器3、通过Jedis 实现的布隆过滤器 布隆过滤器 - Redis 布隆过滤器...
  • 在企业级搜索引擎中,常用一个称为布隆过滤器(Bloom Filter)的算法来实现对已经抓取过的URL进行过滤。 布隆过滤器算法我们经常要判断一个元素是否在一个集合里面,最直接的方法是将集合中的全部元素存储在计算机中...
  • 确定m(布隆过滤器的位数)的公式如下: m = - nlogp / (log2)^2; 其中p =期望的假阳性概率 确定k(哈希函数数)的公式如下: k = m/n log(2) ; 其中k =哈希函数的数量,m =位数,n =过滤器中的项目数 散列是一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,328
精华内容 8,931
关键字:

使用布隆过滤器