精华内容
下载资源
问答
  • redis 布隆过滤器使用示例(guava)
    2019-11-22 21:16:02

    redis 布隆过滤器使用示例(guava)

     

     

    ******************

    示例

     

    ***************

    config 层

     

    DataConfig

    @Configuration
    public class DataConfig {
    
        @Bean
        public BloomFilter<String> initBloomFilter(){
            return BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()),100);
        }
    }
    

     

    ***************

    service 层

     

    BloomFilterService

    @Service
    public class BloomFilterService {
    
        @Resource
        private BloomFilter<String> bloomFilter;
    
        public void add(String s){
            bloomFilter.put(s);
        }
    
        public boolean contain(String s){
            return bloomFilter.mightContain(s);
        }
    }
    

     

    ***************

    controller 层

     

    HelloController

    @RestController
    public class HelloController {
    
        @Resource
        private BloomFilterService bloomFilterService;
    
        @RequestMapping("/add")
        public String add(){
            for (int i=0;i<100;i++){
                bloomFilterService.add("瓜田李下"+i);
            }
    
            return "success";
        }
    
        @RequestMapping("/get")
        public String contain(@RequestParam("value") String value){
            if (bloomFilterService.contain(value)){
                System.out.println("查找的值存在");
                return value+"存在";
            }else{
                System.out.println("查找的值不存在");
                return value+"不存在";
            }
        }
    }
    

     

     

    ******************

    控制台输出

     

    查找的值:瓜田李下 不存在
    查找的值:瓜田李下2 存在
    查找的值:瓜田李下3 存在
    查找的值:瓜田李下4 存在
    查找的值:瓜田李下5 存在
    查找的值:瓜田李下6 存在
    查找的值:海贼王 不存在
    查找的值:海贼王8 不存在
    查找的值:瓜田李下8 存在
    

     

     

    更多相关内容
  • PHP + Redis 实现布隆过滤器,当你的项目需要有大并发的时候,比如id是有序的int类型的时候,增加布隆过滤器可以防止缓存失效直接查询数据库导致的缓存穿透
  • 布隆过滤器是什么  布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比...
  • 布隆过滤器优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。本文将介绍布隆过滤器的原理以及Redis如何实现布隆过滤器,感兴趣的朋友跟随小编一起看看吧
  • 什么是『布隆过滤器布隆过滤器是一个神奇的数据结构,可以用来判断一个元素是否在一个集合中。很常用的一个功能是用来去重。在爬虫中常见的一个需求:目标网站 URL 千千万,怎么判断某个 URL 爬虫是否宠幸过?...
  • 在介绍布隆过滤器之前我们首先引入几个场景。 场景一 在一个高并发的计数系统中,如果一个key没有计数,此时我们应该返回0,但是访问的key不存在,相当于每次访问缓存都不起作用了。那么如何避免频繁访问数量为0的...
  • Redis 布隆过滤器

    2022-02-14 10:24:34
    什么是布隆过滤器 本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你“某样东西一定不存在或者可能存在”。 相比于传统的 ...

    什么是布隆过滤器

    本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”

    相比于传统的 List、Set、Map 等数据结构,它更高效、占用空间更少,但是缺点是其返回的结果是概率性的,而不是确切的。

    实现原理

    HashMap 的问题

    讲述布隆过滤器的原理之前,我们先思考一下,通常你判断某个元素是否存在用的是什么?应该蛮多人回答 HashMap 吧,确实可以将值映射到 HashMap 的 Key,然后可以在 O(1) 的时间复杂度内返回结果,效率奇高。但是 HashMap 的实现也有缺点,例如存储容量占比高,考虑到负载因子的存在,通常空间是不能被用满的,而一旦你的值很多例如上亿的时候,那 HashMap 占据的内存大小就变得很可观了。

    还比如说你的数据集存储在远程服务器上,本地服务接受输入,而数据集非常大不可能一次性读进内存构建 HashMap 的时候,也会存在问题。

    布隆过滤器数据结构

    布隆过滤器是一个 bit 向量或者说 bit 数组,长这样:

    如果我们要映射一个值到布隆过滤器中,我们需要使用多个不同的哈希函数生成多个哈希值,并对每个生成的哈希值指向的 bit 位置 1,例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7,则上图转变为:

    Ok,我们现在再存一个值 “tencent”,如果哈希函数返回 3、4、8 的话,图继续变为:

    值得注意的是,4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位,因此它被覆盖了。现在我们如果想查询 “dianping” 这个值是否存在,哈希函数返回了 1、5、8三个值,结果我们发现 5 这个 bit 位上的值为 0,说明没有任何一个值映射到这个 bit 位上,因此我们可以很确定地说 “dianping” 这个值不存在。而当我们需要查询 “baidu” 这个值是否存在的话,那么哈希函数必然会返回 1、4、7,然后我们检查发现这三个 bit 位上的值均为 1,那么我们可以说 “baidu” 存在了么?答案是不可以,只能是 “baidu” 这个值可能存在。

    这是为什么呢?答案跟简单,因为随着增加的值越来越多,被置为 1 的 bit 位也会越来越多,这样某个值 “taobao” 即使没有被存储过,但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ,那么程序还是会判断 “taobao” 这个值存在。

    支持删除么

    感谢评论区提醒,传统的布隆过滤器并不支持删除操作。但是名为 Counting Bloom filter 的变种可以用来测试元素计数个数是否绝对小于某个阈值,它支持元素删除。可以参考文章 Counting Bloom Filter 的原理和实现

    如何选择哈希函数个数和布隆过滤器长度

    很显然,过小的布隆过滤器很快所有的 bit 位均为 1,那么查询任何值都会返回“可能存在”,起不到过滤的目的了。布隆过滤器的长度会直接影响误报率,布隆过滤器越长其误报率越小。

    另外,哈希函数的个数也需要权衡,个数越多则布隆过滤器 bit 位置位 1 的速度越快,且布隆过滤器的效率越低;但是如果太少的话,那我们的误报率会变高。

    k 为哈希函数个数,m 为布隆过滤器长度,n 为插入的元素个数,p 为误报率

    如何选择适合业务的 k 和 m 值呢,这里直接贴一个公式:

    如何推导这个公式这里只是提一句,因为对于使用来说并没有太大的意义,你让一个高中生来推会推得很快。k 次哈希函数某一 bit 位未被置为 1 的概率为:

     

    插入n个元素后依旧为 0 的概率和为 1 的概率分别是:

     

     

    标明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为 1,但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中(False Positives),该概率由以下公式确定

     

    最佳实践

    常见的适用常见有,利用布隆过滤器减少磁盘 IO 或者网络请求,因为一旦一个值必定不存在的话,我们可以不用进行后续昂贵的查询请求。

    另外,既然你使用布隆过滤器来加速查找和判断是否存在,那么性能很低的哈希函数不是个好选择,推荐 MurmurHash、Fnv 这些。

    大Value拆分

    Redis 因其支持 setbit 和 getbit 操作,且纯内存性能高等特点,因此天然就可以作为布隆过滤器来使用。但是布隆过滤器的不当使用极易产生大 Value,增加 Redis 阻塞风险,因此生成环境中建议对体积庞大的布隆过滤器进行拆分。

    拆分的形式方法多种多样,但是本质是不要将 Hash(Key) 之后的请求分散在多个节点的多个小 bitmap 上,而是应该拆分成多个小 bitmap 之后,对一个 Key 的所有哈希函数都落在这一个小 bitmap 上。

    展开全文
  • Redis 布隆过滤器总结

    千次阅读 2022-01-24 19:51:06
    四、Redis布隆过滤器使用 Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中,给 Redis 提供了强大的布隆去重功能。而在Java开发中,...

    前言: 开发中,经常有让我们判断一个集合中是否存在某个数的case;大多数情况下,只需要用map或是list这样简单的数据结构。但是在高并发环境下,所有的case都会极端化,如果这是一个十分庞大的集合(给这个庞大一个具体的值吧,一个亿),简单的一个HashMap,不考虑链表所需的指针内存空间,一亿个int类型的整数,就需要380多M(4byte × 10 ^8),十亿的话就是4个G,不考虑性能,光算算这内存开销,即使现在满地都是128G的服务器,也不好吃下这一壶。

    在海量数据面前,需要高效的去重数据结构布隆过滤器。布隆过滤器有着很棒的性能,也有着很广泛的应用场景,比如垃圾邮件的过滤,缓存击穿等。


    一、为什么会出现布隆过滤器?

    1.1、抖音推送去重

    (1)问题描述

    抖音你有刷到过重复的推荐内容吗?这么多的推荐内容要推荐给这么多的用户,它是怎么保证每个 用户在看推荐内容时,保证不会出现之前已经看过的推荐视频呢?也就是说,抖音是如何实现 推送去重 的呢?

    (2)解决方案

    你会想到服务器记录了用户看过的所有历史记录,当推荐系统推荐短视频时会从每个用户的历史记录里进行筛选,过滤掉那些已经存在的记录。问题是当用户量很大,每个用户看过的短视频又很多的情况下,这种方式,推荐系统的去重工作在性能上跟的上么

    实际上,如果历史记录存储在关系数据库里,去重就需要频繁地对数据库进行 exists 查询,当系统并发量很高时,数据库是很难抗住压力的。你可能又想到了Redis缓存,但是这么多用户这么多的历史记录,如果全部缓存起来,那得需要浪费多大的内存空间啊,并且这个存储空间会随着时间呈线性增长,服务器撑不住啊?不缓存性能又跟不上,咋办呢?

     布隆过滤器(Bloom Filter) 就是这样一种专门用来判断是否存在解决去重问题的高级数据结构。它能在解决去重的同时,在空间上能节省 90% 以上。

    1.2、用户登录和签到

    在移动应用的业务场景中,我们需要保存这样的信息:一个 key 关联了一个数据集合。

    常见的场景如下:

    • 给一个 userId ,判断用户登陆状态;

    • 显示用户某个月的签到次数和首次签到时间;

    • 两亿用户最近 7 天的签到情况,统计 7 天内连续签到的用户总数;

    通常情况下,我们面临的用户数量以及访问量都是巨大的,比如百万、千万级别的用户数量,或者千万级别、甚至亿级别的访问信息。所以,我们必须要选择能够非常高效地统计大量数据(例如亿级)的集合类型。

    如何选择合适的数据集合,我们首先要了解常用的统计模式,并运用合理的数据类型来解决实际问题。

    四种统计类型:

    1. 二值状态统计;

    2. 聚合统计;

    3. 排序统计;

    4. 基数统计。

    本文将介绍二值状态统计类型,会用到 String、Set、Zset、List、hash 以外的拓展数据类型 Bitmap 和布隆过滤器来实现。

    也就是集合中的元素的值只有 0 和 1 两种,在签到打卡和用户是否登陆的场景中,只需记录签到(1)或 未签到(0)已登录(1)未登陆(0)

    假如我们在判断用户是否登陆的场景中使用 Redis 的 String 类型实现(key -> userId,value -> 0 表示下线,1 - 登陆),假如存储 100 万个用户的登陆状态,如果以字符串的形式存储,就需要存储 100 万个字符串了,内存开销太大。可以使用高级数据结构bitmap或者布隆过滤器实现。


    二、布隆过滤器简介

    2.1、布隆过滤器是什么?

    布隆过滤器(Boolm Filter)是1970年由布隆提出的一种算法。实际上是一个很长的二进制向量和一系列随机映射哈希函数。其实就是一种数据结构,类似于Hash、Set,主要用于检索一个元素是否在一个集合中。当布隆过滤器说某个值存在时,这个值 可能不存在;当它说不存在时,那么一定不存在。你也可以把它简单理解为一个不怎么精确的 set 结构,当你使用它的 contains 方法判断某个对象是否存在时,它可能会误判。但是布隆过滤器也不是特别不精确,只要参数设置的合理,它的精确度可以控制的相对足够精确,只会有小小的误判概率。

    在编程中,我们想要判断一个元素是不是在一个集合中,一般会想到将所有元素保存起来,然后比较确定。链表、树等数据结构都是这种思路。但是,随着集合中元素的增加,需要的存储空间越来越大,检索的速度也就越来越慢了。

    布隆过滤器相对于Hash、Set等数据结构不同的时,它无需存储key,对于每个key,只需要k个比特位,每个存储一个标志,用来判断key是否在集合中。所以,它可以实现高效的插入和查询,并且在时间和空间方面都具有巨大的优势,都是常数。

    2.2、布隆过滤器的使用场景

    基于上述的功能,我们大致可以把布隆过滤器用于以下的场景之中:

    • 大数据判断是否存在来实现去重:这就可以实现出上述的去重功能,如果你的服务器内存足够大的话,那么使用 HashMap 可能是一个不错的解决方案,理论上时间复杂度可以达到 O(1) 的级别,但是当数据量起来之后,还是只能考虑布隆过滤器。

    • 判断用户是否访问过:判断用户是否阅读过某视频或文章,比如抖音或头条,当然会导致一定的误判,但不会让用户看到重复的内容。

    • 解决缓存穿透:我们经常会把一些热点数据放在 Redis 中当作缓存,例如产品详情。通常一个请求过来之后我们会先查询缓存,而不用直接读取数据库,这是提升性能最简单也是最普遍的做法,但是 如果一直请求一个不存在的缓存,那么此时一定不存在缓存,那就会有大量请求直接打到数据库上,造成 缓存穿透,布隆过滤器也可以用来解决此类问题。

    • 爬虫/ 邮箱等系统的过滤:平时不知道你有没有注意到有一些正常的邮件也会被放进垃圾邮件目录中,这就是使用布隆过滤器误判导致的。

    2.3、布隆过滤器的原理

    当一个元素被加入集合时,通过N个Hash函数将这个元素进行Hash,算出一个整数索引值,然后对数组长度进行取模运算,从而得到一个位置,每个Hash函数都会得到一个不同的位置,然后再把位数组中的几个位置点都置为1。

    检索时,也会把哈希的几个位置算出来,然后看看位数组中对应的几个位置是否都为1,只要有一个位为0,那么就说明布隆过滤器里不存在这个元素。

    但是,这几个位置都为1,并不能完全说明这个元素就一定存在其中,有可能这些位置为1是因为其他元素的存在,这就是布隆过滤器会出现误判的原因。

    简而言之就是,布隆过滤器可以判断某个元素一定不存在,但是无法判断一定存在。

    所以,我们可以得出布隆过滤器的优缺点如下:

    优点

    1)占用空间极小,插入和查询速度极快;

    2)布隆过滤器可以表示全集,其它任何数据结构都不能;

    缺点

    1)误算率随着元素的增加而增加;

    2)一般情况下无法删除元素;


     三、bitmap和布隆过滤器关系

    在Redis4.0之前,只能通过bitmap来实现,在Redis4.0之后,官方提供了module能力,这时候,官方提供的RedisBloom才算正式出道。

    3.1、海量整数中是否存在某个值:bitmap

    bitmap使用位数代表数的大小,bit中存储的0或者1来标识该整数是否存在。计算一下bitmap的内存开销,如果是1亿以内的数据查找,我们只需要1亿个bit = 12MB左右的内存空间,就可以完成海量数据查找了,这是极其诱人的一个内存缩减。

    (1)bitmap概述

    我们知道,计算机是以二进制为底层的存储单位,一个字节等于8位。比如“big”字符串是由三个字符组成,这三个字符对应的ASCII码分别为98,105,103,对应的二进制存储如下:

    基本命令如下:

    # 设置字节值
    setbit key offset value
    # 获取字节值
    gitbit key offset
    # 获取指定范围内为1的元素个数
    bitcount key [start end]

    (2)bitmap原理

    这是一个能标识0-9的“bitmap”,其中4321这四个数存在,具体模型如下:

    例如说往bitmap里面存储一个数字11,那么首先需要通过向右移位(因为一个byte相当于8个bit),计算出所存储的byte[]数组的索引定位,这里计算出index是1。由于一个byte里面存储了八个bit位,所以通过求余的运算来计算postion,算出来为3。

    这里假设原有的bitmap里面存储了4和12这2个数字,那么它的结构如下所示:

     这个时候,我们需要存储11进来,那么就需要进行或运算了:

    同理,当我们判断数字是否存在的时候,也需要进行相应的判断,代码如下:

      public boolean contain(int number) {
            int index = number >> 3;
            int position = number & 0x07; 
            return (bytes[index] & (1<<position)) !=0;
        }

    (3)整合一下简单版的bitmap代码如下:

    public class MyBitMap {
     
        private byte[] bytes;
        private int initSize;
     
        public MyBitMap(int size) {
            if (size <= 0) {
                return;
            }
            initSize = size / (8) + 1;
            bytes = new byte[initSize];
        }
     
        public void set(int number) {
            //相当于对一个数字进行右移动3位,相当于除以8
            int index = number >> 3;
            //相当于 number % 8 获取到byte[index]的位置
            int position = number & 0x07;
            //进行|或运算  参加运算的两个对象只要有一个为1,其值为1。
            bytes[index] |= 1 << position;
        }
     
     
        public boolean contain(int number) {
            int index = number >> 3;
            int position = number & 0x07;
            return (bytes[index] & (1 << position)) != 0;
        }
     
        public static void main(String[] args) {
            MyBitMap myBitMap = new MyBitMap(32);
            myBitMap.set(30);
            myBitMap.set(13);
            myBitMap.set(24);
            System.out.println(myBitMap.contain(2));
        }
     
    }

    (4)bitmap缺陷

    使用简单的byte数组和位运算,就能做到时间与空间的完美均衡,但是bitmap还存在问题!

    试想一下,如果我们明确这是一个一亿以内,但是数量级只有10的集合,我们使用bitmap,同样需要开销12M的数据,如果是10亿以内的数据,开销就会涨到120M,bitmap的空间开销永远是和他的数据取值范围挂钩的,只有在海量数据下,他才能够大显身手。

    再说说刚刚提到的那个极端case,假设这个数据量在一千万,但是取值范围好死不死就在十个亿以内,那我们不可避免还是要面对120M的开销,有方法应对么?

    3.2、布隆过滤器 

    (1)布隆过滤器简介

    如果面对笔者说的以上问题,我们结合一下常规的解决方案,譬如说hash一下,我将十亿以内的某个数据,hash成一亿内的某个值,再去bitmap中查怎么样,如下图,布隆过滤器就是这么干的:

    利用多个hash算法得到的值,减小hash碰撞的概率,但只要存在碰撞,就一定会有错误判断,我们无法百分百确定一个值是否真的存在,但是hash算法的魅力在于,我不能确定你是否存在,但是我可以确定你是否真的不存在,这也就是以上的实现为什么称之“过滤器”的原因了。

    在Redis4.0之后。我们可以将RedisBloom作为一个模块加载到Redis Server中,从而获取强大的布隆过滤器能力。

    在RedisBloom中,布隆过滤器有两个基本命令,分别是:

    1)bf.add添加元素到布隆过滤器中,类似于集合的sadd命令,不过bf.add命令只能一次添加一个元素,如果想一次添加多个元素,可以使用bf.madd命令。

    2)bf.exists:判断某个元素是否在过滤器中,类似于集合的sismember命令,不过bf.exists命令只能一次查询一个元素,如果想一次查询多个元素,可以使用bf.mexists命令。

    布隆过滤器提供默认参数的布隆过滤器,它在我们第一次使用bf.add命令时自动创建的。

    (2)Redis自定义参数的布隆过滤器

    Redis还提供了自定义参数的布隆过滤器,想要尽量减少布隆过滤器的误判,就要设置合理的参数。

    在使用bf.add命令添加元素之前,使用bf.reserve命令创建一个自定义的布隆过滤器。

    bf.reserve命令有三个参数,分别是:

    key:

    error_rate:期望错误率,期望错误率越低,需要的空间就越大。

    capacity:初始容量,当实际元素的数量超过这个初始化容量时,误判率上升。

    示例如下:

    127.0.0.1:6379> BF.RESERVE customFilter 0.0001 600000
    OK

    如果对应的key已经存在时,在执行bf.reserve命令就会报错。如果不使用bf.reserve命令创建,而是使用Redis自动创建的布隆过滤器,默认的error_rate是 0.0001,capacity是 60。

    布隆过滤器的error_rate越小,需要的存储空间就越大,对于不需要过于精确的场景,error_rate设置稍大一点也可以。

    布隆过滤器的capacity设置的过大,会浪费存储空间,设置的过小,就会影响准确率,所以在使用之前一定要尽可能地精确估计好元素数量,还需要加上一定的冗余空间以避免实际元素可能会意外高出设置值很多。

    总之,error_rate和 capacity都需要设置一个合适的数值。


    四、Redis布隆过滤器的使用

    Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中,给 Redis 提供了强大的布隆去重功能。而在Java开发中,可以使用各种现成的布隆过滤器客户端,包括Google出品的Guava BloomFilter类和Redisson的RBloomFilter接口访问布隆过滤器。

    4.1、使用 Google 开源的 Guava 中自带的布隆过滤器

    Guava 中布隆过滤器的实现算是比较权威的,所以实际项目中我们不需要手动实现一个布隆过滤器。

    首先我们需要在项目中引入 Guava 的依赖:

    <dependency>
        <groupId>com.google.guava</groupId>
        <artifactId>guava</artifactId>
        <version>28.0-jre</version>
    </dependency>
    

    实际使用如下:

    我们创建了一个最多存放 最多 1500 个整数的布隆过滤器,并且我们可以容忍误判的概率为百分之一(0.01)

    // 创建布隆过滤器对象
    BloomFilter<Integer> filter = BloomFilter.create(
            Funnels.integerFunnel(),
            1500,
            0.01);
    // 判断指定元素是否存在
    System.out.println(filter.mightContain(1));
    System.out.println(filter.mightContain(2));
    // 将元素添加进布隆过滤器
    filter.put(1);
    filter.put(2);
    System.out.println(filter.mightContain(1));
    System.out.println(filter.mightContain(2));
    

    在我们的示例中,当 mightContain() 方法返回 true 时,我们可以 99% 确定该元素在过滤器中,当过滤器返回 false 时,我们可以 100% 确定该元素不存在于过滤器中。

    Guava 提供的布隆过滤器的实现还是很不错的 ,但是它有一个重大的缺陷就是只能单机使用 (另外,容量扩展也不容易),而现在互联网一般都是分布式的场景。为了解决这个问题,我们就需要用到 Redis 中的布隆过滤器了。

    4.2、通过Redisson使用布隆过滤器

    Redisson是一款超快速轻量级Redis Java客户端,提供了许多常用的Java对象和功能,包括布隆过滤器。

    public interface RBloomFilter<T> extends RExpirable {
     
        boolean tryInit(long var1, double var3);  //初始化布隆过滤器,var1表示大小,var3表示容错率
     
        boolean add(T var1);                      //添加对象
        boolean contains(T var1);                 //判断对象是否存在
     
        long getExpectedInsertions();             //返回预计插入数量
        double getFalseProbability();             //返回容错率
        int getHashIterations();                  //返回hash函数个数
     
        long count();                             //对象插入后,估计插入数量
        long getSize();                           //布隆过滤器位数组的大小
     
    }

    下面的示例代码演示了如何用Redisson的RBloomFilter接口使用布隆过滤器:

    RBloomFilter<SomeObject> bloomFilter = redisson.getBloomFilter("sample");
    // 初始化布隆过滤器
    // expectedInsertions = 55000000
    // falseProbability = 0.03
    bloomFilter.tryInit(55000000L, 0.03);
    
    bloomFilter.add(new SomeObject("field1Value", "field2Value"));
    
    bloomFilter.add(new SomeObject("field5Value", "field8Value"));
    
    
    bloomFilter.contains(new SomeObject("field1Value", "field8Value"));
    
    bloomFilter.count();

    布隆过滤器是一种概率数据结构:能确认元素不存在于集合中,但只能提供元素出现在集合中的概率。

    • falseProbability参数定义了使用给定RBloomFilter发生误报的概率。

    • expectedInsertions参数定义了每个元素的预期插入次数。RBloomFilter对象最多支持2 ^32 bit。

    Redisson还能通过RClusteredBloomFilter接口在Redis中支持分布式布隆过滤器。RClusteredBloomFilter的内存效率更高,可以缩小所有Redis节点使用的内存。RClusteredBloomFilter对象最多支持2^64 bit。请注意,RClusteredBloomFilter只支持Redisson集群模式使用。

    以下示例代码演示了如何使用RClusteredBloomFilter接口:

    RClusteredBloomFilter<SomeObject> bloomFilter = redisson.getClusteredBloomFilter("sample");
    // 初始化布隆过滤器
    // expectedInsertions = 255000000
    // falseProbability = 0.03
    bloomFilter.tryInit(255000000L, 0.03);
    bloomFilter.add(new SomeObject("field1Value", "field2Value"));
    bloomFilter.add(new SomeObject("field5Value", "field8Value"));
    bloomFilter.contains(new SomeObject("field1Value", "field8Value"));

    Redis布隆过滤器总结:

    Redis中大名鼎鼎的布隆过滤器,在一些大数据场景下,判断是否存在来实现去重,布隆过滤器有着极为出色的性能,在大厂中应用范围是极其广的,只要你想在大厂搬砖,一定会在面试敲门的时候被问到的。


    参考链接:

    Redis 实战篇:巧用 Bitmap 实现亿级海量数据统计

    美团面试题:BloomFilter(布隆过滤器)原理与使用,深入浅出BloomFilter原理

    一千万个整数里面快速查找某个整数,你会怎么去做?

    展开全文
  • 布隆过滤器和set和map是平级的,是判断一定不存在还是可能存在的数据结构。 key进来多个hash进行散列映射。 布隆过滤器:https://www.jianshu.com/p/2104d11ee0a2 ——————————————————01————...
  • redis布隆过滤器使用

    万次阅读 多人点赞 2019-03-10 18:48:05
    1.使用场景:推荐系统给用户推荐新闻,避免重复推送。 需要考虑问题:从用户观看历史中筛选出没有看过的新闻进行推送...1.2.这时布隆过滤器就可以很好的解决这个需求了,可以节约90%以上的空间,缺点就是稍微有那么...

    1.使用场景:推荐系统给用户推荐新闻,避免重复推送。

    需要考虑问题:从用户观看历史中筛选出没有看过的新闻进行推送,就需要数据库中频繁的使用exists进行查询,但是当用户量很大时,数据库很难顶住压力。

    解决方法:

    1.1.使用缓存?但是日子长了,会浪费很大空间,不是长久之计,不是很好的解决办法。

    1.2.这时布隆过滤器就可以很好的解决这个需求了,可以节约90%以上的空间,缺点就是稍微有那么一点不准确,存在一定的误判率,但是对于这个新闻推送的可以忽略。

    2.什么布隆过滤器

    2.1其实布隆过滤器可以看成是一个不是很准确的set结构,只是在使用它的contains方法判断某个对象是否存在时会出现误判。但是它也不是特别的不精准,只要参数设置合理,那么它的精确度可以控制的足够精准,只会有小小的误判。

    2.2当布隆过滤器说某个值存在时,那可能就不存在,如果说某个值不存在时,那肯定就是不存在了。

    打个比方,当一个人说认识你时可能不认识你,当一个人说不认识你时那肯定就不认识了。当它说见过你时,可能根本没有见过面,只不过可能你的脸和它所认识人中某个人的脸相似度比较高,所以产生误判。

    2.3对于上面的场景,当用户看过的新闻,肯定会被过滤掉,对于没有看多的新闻,可能会过滤极少的一部分(误判),但是绝大部分都可以准确识别。这样可以完全保证推送给用户的新闻都是无重复的。

    3.centos安装redis的bloomfilter插件

    https://blog.csdn.net/u013030276/article/details/88350641

    4.bloomfilter使用

    4.1 bf.add

    语法:[bf.add  key  options]

    127.0.0.1:6379> bf.add users user3
    
    (integer) 1

    4.2 bf.exists

    语法:[bf.exists  key  options]

    127.0.0.1:6379> bf.exists users user1
    
    (integer) 1
    
    127.0.0.1:6379> bf.exists users user3
    
    (integer) 0

    4.3 bf.madd

    语法:[bf.add  key  ...options]

    127.0.0.1:6379> bf.madd users user4 user5 user6 user7
    
    1) (integer) 1
    
    2) (integer) 1
    
    3) (integer) 1
    
    4) (integer) 1

    4.4 bf.mexists

    语法:[bf.add  key  ...options]

    127.0.0.1:6379> bf.mexists users user4 user5 user6 user7 user8
    
    1) (integer) 1
    
    2) (integer) 1
    
    3) (integer) 1
    
    4) (integer) 1
    
    5) (integer) 0

    4.5 bf.reserve创建Filter

    语法:[bf.reserve  key  error_rate initial_size]

    127.0.0.1:6379> bf.reserve books 0.001 10000
    
    OK

    5.代码实现

    5.1引入依赖

    jedis3.0没有rebloom的相关方法,只能通过引入rebloom.jar。

    https://github.com/RedisLabs/JReBloom

    pom.xml引入:

    <dependencies>
       <dependency>
          <groupId>com.redislabs</groupId>
          <artifactId>jrebloom</artifactId>
          <version>1.0.1</version>
       </dependency>
    </dependencies>

    5.2对自己见过的元素判断是否不存在

    @Test
    public void test3() {
        setJedisPool();
        Client client = new Client(jedisPool);
        jedisPool.getResource().del("book");
        for (int i = 0; i < 10000; i++) {
            String book = "book" + i;
            client.add("book", book);
            boolean ret = client.exists("book", book); // 判断自己见过的,没有出现误判
            if (!ret) {
                System.out.println(i);
            }
        }
        jedisPool.close();
    }

    5.3使用默认Filter参数(),对自己没有见过的,判断是否存在

    @Test
    public void test4() {
        setJedisPool();
        Client client = new Client(jedisPool);
        int count = 0;
        jedisPool.getResource().del("book");
        for (int i = 0; i < 10000; i++) {
            String book = "book" + i;
            boolean ret = client.exists("book", book); // 判断自己没见过的,误判数153个,15.3%
            if (ret) {
                count++;
                System.out.println(i + "误判数:" + count);
            }
            client.add("book", book);
        }
        jedisPool.close();
    }

    10000个元素,判断自己没见过的,误判数153个,1.53%

    对于超过1.5%的误判率怎么办呢?

    默认的Filter的initial_size=100,error_rate=0.1;

    5.4创建Filter(initial_size,error_rate),对自己没有见过的,判断是否存在

    @Test
    public void test5() {
        setJedisPool();
        Client client = new Client(jedisPool);
        int count = 0;
        jedisPool.getResource().del("book");
        client.createFilter("book", 9000, 0.001);
        for (int i = 0; i < 10000; i++) {
            String book = "book" + i;
            boolean ret = client.exists("book", book); // 判断自己没见过的,10000,0.001误判数0个;9000,0.001误判1个;
            if (ret) {
                count++;
            }
            System.out.println(book + "--" + ret + "--误判数:" + count);
            client.add("book", book);
        }
        jedisPool.close();
    }

    设置预计放入的元素个数=10000,错误率=0.001误判数0个;

    设置预计放入的元素个数=9000,错误率=0.001误判1个;

    注意事项:

    布隆过滤器的initial_size估计的过大,所需要的空间就越大,会浪费空间,估计的过小会影响准确率,因此在使用前一定要估算好元素数量,还需要加上一定的冗余空间以避免实际元素高出预估数量造成误差过大。

    布隆过滤器的error_rate越小,所需要的空间就会越大,对于不需要过于准确的,error_rate设置的稍大一点也无所谓。

    6.布隆过滤器原理

    每个布隆过滤器对应到 Redis 的数据结构里面就是一个大型的位数组和几个不一样的无偏 hash 函数。所谓无偏就是能够把元素的 hash 值算得比较均匀。

    向布隆过滤器中添加 key 时,会使用多个 hash 函数对 key 进行 hash 算得一个整数索引值然后对位数组长度进行取模运算得到一个位置,每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。

    向布隆过滤器询问 key 是否存在时,跟 add 一样,也会把 hash 的几个位置都算出来,看看位数组中这几个位置是否都为 1,只要有一个位为 0,那么说明布隆过滤器中这个 key 不存在。如果都是 1,这并不能说明这个 key 就一定存在,只是极有可能存在,因为这些位被置为 1 可能是因为其它的 key 存在所致。如果这个位数组比较稀疏,判断正确的概率就会很大,如果这个位数组比较拥挤,判断正确的概率就会降低。

    7.空间计算

     布隆计算器

    展开全文
  • 基于Redis布隆过滤器,内含scrapy示例程序,github地址:https://github.com/kongtianyi/BloomFilterRedis
  • 一、什么是布隆过滤器 布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询...
  • 布隆过滤器 本质上布隆过滤器是一种数据结构,可以用来告诉你 “某样东西一定不存在或者可能存在”。 如果我们平时常用的List,set,map ,tree 来实现同样的效果,set和map都是采用map的数据结构,时间复杂度是O1级别...
  • 什么是布隆过滤器 布隆过滤器(Bloom Filter)是由Howard Bloom在1970年提出的一种比较巧妙的概率型数据结构,它可以告诉你某种东西一定不存在或者可能存在。当布隆过滤器说,某种东西存在时,这种东西可能不存在;...
  • 使用场景1.2:布隆过滤器2:布隆过滤器的安装 (不要下载 master 版本)2.1: 找到源码压缩包地址2.2:linux 系统中进行下载2.3:编译2.4:启动 redis 挂载 redisbloom.so2.5:启动 redis 客户端3:布隆过滤器使用4...
  • - 目录 -大家都知道,在计算机中,IO一直是一个瓶颈,很多框架以及技术甚至硬件都是为了降低IO操作而生,今天聊一聊过滤器,先说一个场景:我们业务后端涉及数据库,当请求消息查...
  • 布隆过滤器使用(技术方案要尽可能通用) 开发时使用redis布隆过滤器的时候,用的是本地加载官方组件并启动redis,并没有考虑到阿里云是否支持;结果默认是不支持的... 好在后来跟对方协商,对方可以提供定制化版的...
  • 一般来说,一个合理的请求过来我们会先在Redis里判断这个用户是否是会员,因为从缓存里读数据返回快。如果这个会员在缓存中不存在那么我们会去DB中查询一下。 现在试想,有千万个不同IP的请求(不要以为没有,我们...
  • 本文是《玩转Redis》系列第【11】篇,本文关键字:玩转Redis、Bloom filter、布隆过滤器、无偏hash函数; - 布隆过滤器的底层原理 - 布隆过滤器的底层结构 - 最佳hash函数数量与错误率的关系 - 所需存储空间与...
  • php redis 布隆过滤器

    2022-01-14 09:48:34
    https://www.cnblogs.com/bogiang/p/15165904.html
  • redis布隆过滤器

    千次阅读 2020-02-19 13:13:36
    # 布隆过滤器 ### 定义 布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。 ### 用处 布隆过滤器可以用于检索一个元素是否在一个集合中。具体使用有: ...
  • redis布隆过滤器简单使用 布隆过滤器无法直接在redis里使用,需要redis4.0以上的版本才能安装插件使用, 安装方法请我的以前的博客:https://blog.csdn.net/weixin_42564514/article/details/104880452 当然也...
  • SpringBoot + Redis布隆过滤器
  • Redis-布隆过滤器(Bloom Filter)详解

    千次阅读 2021-12-09 16:26:21
    什么是布隆过滤器 布隆过滤器(Bloom Filter)是 1970 年由布隆提出的,是一种非常节省空间的概率数据结构,运行速度快,占用内存小,但是有一定的误判率且无法删除元素。它实际上是一个很长的二进制向量和一系列...
  • 1、布隆过滤器 使用场景 1.布隆过滤器的特性是:去重,多数去重场景都跟这个特性有关。比如爬虫的时候去掉相同的URL,推送消息去掉相同的消息等。 2.解决缓存击穿的问题。 3.反垃圾邮件,从数十亿个垃圾邮件列表...
  • 项目中使用redis实现布隆过滤器的几种方式: 先占个位,假期结束回来详细说明。 第一种: redis 安装bloom 过滤器模块, redisTemplate 执行lua 脚本 第二种: redis 安装bloom 过滤器模块, 由于redisTemplate 不...
  • 鉴于github网络不稳定,此处提供免费下载,供广大学习爱好者使用

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,726
精华内容 6,690
关键字:

redis布隆过滤器使用

友情链接: timerdisplay.rar