Redis-布隆过滤器

布隆过滤器

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。Hash面临的问题就是冲突，解决方法也简单，就是使用多个Hash。

可以把布隆过滤器理解为一个不怎么精确的set结构（set结构带有去重功能），当使用它的contains方法判断某个对象是否存在时，它可能会误判。但是布隆过滤器也不是特别不精确，只要参数设置得合理，它的精确度也是可以控制得相对足够精确，只会有小小的误判概率。

一般我们可以将它用来防止缓存穿透问题，减少数据存储空间问题，降低数据库IO访问量。

Redis中的布隆过滤器

布隆过滤器是作为一个插件加载到Redis Server中的，所以我们如果要用它的话，就得去安装，不过也是可以在安装Redis服务的时候就把它装好了（比如，docker安装）
RedisBloom官网

注意，redis在4.0以后才支持loadmodule插件功能

安装

  • docker

    1
    docker pull redislabs/rebloom
    2
    docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom
    3
    docker exec -it redis-redisbloom bash
    4
    # redis-cli
    5
    # 127.0.0.1:6379> 
    6
    # 127.0.0.1:6379> BF.ADD newFilter foo
    7
    (integer) 1
    8
    # 127.0.0.1:6379> BF.EXISTS newFilter foo
    9
    (integer) 1

  • 手动安装

    需要先下载Bloom过滤器模块

    1
    wget https://github.com/RedisBloom/RedisBloom/archive/v2.2.1.tar.gz
    2
    tar zxvf v2.2.1.tar.gz
    3
    cd RedisBloom-2.2.1/
    4
    make
    5
    # 启动是指定redisbloom.so路径
    6
    redis-server --loadmodule /home/RedisBloom-2.2.1/redisbloom.so --daemonize yes
基本用法

  • 常用方法

    1
    # bf.add用来添加元素，一次只能添加一个元素，添加重复将返回0
    2
    127.0.0.1:6379> bf.add test user1
    3
    (integer) 1
    4
    127.0.0.1:6379> bf.add test user2
    5
    (integer) 1
    6
    127.0.0.1:6379> bf.add test user2
    7
    (integer) 0
    8
    127.0.0.1:6379> bf.add test user3
    9
    (integer) 1
    10
    11
    # bf.exists用来判断元素是否存在
    12
    127.0.0.1:6379> bf.exists test user4
    13
    (integer) 0
    14
    127.0.0.1:6379> bf.exists test user3
    15
    (integer) 1
    16
    17
    # bf.madd用来一次性添加多个元素
    18
    127.0.0.1:6379> bf.madd test user1 user5
    19
    1) (integer) 0
    20
    2) (integer) 1
    21
    22
    # bf.mexists用来一次性查询多个元素是否存在
    23
    127.0.0.1:6379> bf.mexists test user1 user6
    24
    1) (integer) 1
    25
    2) (integer) 0
    26
    27
    # 查看key的空间容量
    28
    127.0.0.1:6379> BF.DEBUG test
    29
    1) "size:4"
    30
    2) "bytes:138 bits:1104 hashes:8 hashwidth:64 capacity:100 size:4 ratio:0.005"

  • 提高精准度

    有时候我们希望调整精确度，让布隆过滤器的误判率降低，这时候就得使用bf.reserve

    注意，必须在bf.add之前显示的声明key，如果对应的 key 已经存在，bf.reserve会报错。同时设置的错误率越低，需要的空间越大。如果不使用 bf.reserve，默认的error_rate是 0.01，默认的initial_size是 100

    bf.reserve [key] [error_rate] [initial_size]
    error_rate:越低，需要的空间越大
    initial_size：表示预计放入的元素数量，当实际数量超出这个数值时，误判率会上升，所以需要提前设置一个合理的数值

    1
    127.0.0.1:6379> bf.reserve user_data 0.001 100000
    2
    OK
    3
    127.0.0.1:6379> bf.add user_data user1
    4
    (integer) 1

  • python实现

    1
    '''
    2
    redis4.0+ 新增插件功能（可以额外增加布隆过滤器模块）
    3
    '''
    4
    import redis
    5
    6
    client = redis.StrictRedis(host='127.0.0.1',port=6379)
    7
    8
    client.delete("user_data")
    9
    # 主动设置元素值和错误率(一般比实际高出一些，做冗余)
    10
    client.execute_command('bf.reserve','user_data',0.001,120000)
    11
    for i in range(100000):
    12
        user_id = "id_%d" % i
    13
        client.execute_command('bf.add', "user_data", user_id)
    14
        ret = client.execute_command('bf.exists', 'user_data',user_id + '1') # 故意增加1，测试布隆过滤器对于未见过的元素误判率
    15
        if ret == 1:
    16
            print(i)
    17
            break
    18
    19
    """
    20
    100000个元素测试结果：
    21
        默认参数下：第152个元素的时候出现误判
    22
        修改误判率后：未发现误判率(不过占用内存空间也上升，将近232KB)
    23
        
    24
    127.0.0.1:6379> BF.DEBUG user_data
    25
    1) "size:100000"
    26
    2) "bytes:237305 bits:1898440 hashes:11 hashwidth:64 capacity:120000 size:100000 ratio:0.0005"
    27
    """
注意事项

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

布隆过滤器的error_rate越小，需要的存储空间就越大，对于不需要过于精确的场合，error_rate设置稍大一点也无伤大雅。

当实际元素数量开始超出阈值时，应该对布隆过滤器进行重建（重建之前记得存储所有原始数据），重新分配一个size更大的过滤器，再将所有的历史元素批量add进去（这就要求我们在其他的存储器中记录所有的历史元素）或者用堆叠法，另开一个新的布隆过滤器，只是在代码中判断的时候需要一起判断

空间占用估计

一般在估算空间占用的时候，都有一个简单的计算公式。麻烦的话也可以使用在线的布隆计算器

1
'''
2
n:预计元素数量
3
f：错误率
4
l：位数组的长度
5
k：hash函数的最佳数量，最佳数量会有最低的错误率
6
'''
7
f = 0.6185 ^ (l/n)
8
k = 0.7 * (l/n) # 约等于

当实际元素超出预计的时候，我们需要了解实际的误判率，就可以使用以下公式计算

1
'''
2
t:表示实际元素和预计元素的倍数
3
k:最佳数量
4
f：错误率
5
'''
6
f = (1 - 0.5 ^ t) ^ k

其余布隆过滤器（建议还是使用原生rebloom module插件）

除了redis4.0之后支持的rebloom module以外，还有其他第三方也在实际项目中使用（可作为替代原生方案）

  • pyreBloom

    redis布隆过滤器python版本的库，不过不支持重连和重试，使用时最好在做一层封装

    • 安装

      1
      # pyreBloom需要hiredis支持（redis数据库的简约C客户端库），以及gcc环境，采用Cython
      2
      # 这是pyreBloom的一个分支，但速度更快一点，具有更好的API并支持Python 2.6 +，3.3 +，PyPy 2和PyPy 3
      3
      pip install pyreBloom-ng
      4
      5
      # 上面安装的时候报错，我采用原来的方式
      6
      git clone https://github.com/seomoz/pyreBloom.git
      7
      cd pyreBloom/
      8
      pip install -r requirements.txt -i https://mirrors.aliyun.com/pypi/simple
      9
      10
      # 这一步的成功条件是需要安装hiredis
      11
      python setup.py install

      • hiredis

        redis数据库的简约C客户端库,是redis官方的C语言客户端，支持所有命令（command set），管道（pipelining），时间驱动编程（event driven programming）

        1
        # From https://github.com/paulasmuth/recommendify/issues/6#issuecomment-4496616
        2
        # via https://github.com/seomoz/pyreBloom/issues/7#issuecomment-21182063
        3
        #
        4
        # On Mac:
        5
        brew install hiredis
        6
        7
        # With Ubuntu:
        8
        apt-get install libhiredis-dev
        9
        10
        # From source:
        11
        git clone https://github.com/redis/hiredis
        12
        cd hiredis && make && sudo make install

    • 使用

      1
      # 目前python3.7并没有通过测试（python2.7是可以的），怀疑不支持，所以我们建议redis官方插件
      2
      import pyreBloom
      3
      p = pyreBloom.pyreBloom('myBloomFilter', 100000, 0.01)
      4
      # 可以找出理论上将消耗多少位空间
      5
      p.bits
      6
      # 获取需要多少哈希来满足误报率
      7
      p.hashes
      8
      9
      tests = ['hello', 'how', 'are', 'you', 'today']
      10
      p.extend(tests)
      11
      12
      p.contains('hello')
      13
      # True
      14
      p.contains(['hello', 'whats', 'new', 'with', 'you'])
      15
      # ['hello', 'you']
      16
      'hello' in p
      17
      # True

      如果需要使用封装好的推荐使用已经存在的项目

      1
      git clone https://github.com/luw2007/bloomfilter.git && \
      2
      cd bloomfilter && \
      3
      pip install -r requirements.txt && \
      4
      python setup.py install

  • orestes-bloomfilter

    redis布隆过滤器java版本的库

  • 原生python 调用setbit 构造 BloomFilter

  • lua脚本

赏

拿钱去买猫粮~

微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

优秀的判断力来自经验，<br>但经验来自于错误的判断。<br><br>~余生只想爱胖爱生活<br><br>真正的勇士敢于直面惨淡的人生，<br>敢于正视淋漓的鲜血。