Redis系列九 推荐系统-布隆过滤器

来都来了 2020-12-11 18:37:24 ⋅ 1354 阅读

 

布隆过滤器

概念

布隆过滤器是一种空间利用率较高的概率型数据结构，用来测试一个元素是否在集合中。但是存在一定可能，导致结果误判。当布隆过滤器说某个值存在时，这个值可能不存在；当它说不存在时，那就肯定不存在.

特性：

  1. 与哈希表不同，布隆过滤器是一个大小固定的过滤器；
  2. 随着元素的增多，错误率逐渐上升；
  3. 不能删除其中的元素。

更多内容看–原理部分。

Mac 配置

第一步

下载布隆过滤器：地址

# git clone
➜  tmp git clone git@github.com:RedisBloom/RedisBloom.git
Cloning into 'RedisBloom'...
remote: Enumerating objects: 16, done.
remote: Counting objects: 100% (16/16), done.
remote: Compressing objects: 100% (14/14), done.
remote: Total 2258 (delta 5), reused 5 (delta 2), pack-reused 2242
Receiving objects: 100% (2258/2258), 627.74 KiB | 139.00 KiB/s, done.
Resolving deltas: 100% (1480/1480), done.
#
➜  tmp cd RedisBloom
➜  RedisBloom git:(master) ls
Dockerfile  Makefile    changelog   contrib     mkdocs.yml  ramp.yml    src
LICENSE     README.md   codecov.yml docs        opt         rmutil      tests
# make
➜  RedisBloom git:(master) make
# 将redisbloom.so文件放入指定目录
➜  RedisBloom git:(master) ls
Dockerfile    README.md     contrib       opt           rmutil
LICENSE       changelog     docs          ramp.yml      src
Makefile      codecov.yml   mkdocs.yml    redisbloom.so tests
 

第二步

更改 redis 配置文件

# brew 查看redis相关配置
➜  redis brew info redis
redis: stable 6.0.8 (bottled), HEAD
Persistent key-value database, with built-in net interface
https://redis.io/
/usr/local/Cellar/redis/5.0.5 (13 files, 3.1MB) *
  Poured from bottle on 2019-09-20 at 13:21:23
From: https://mirrors.tuna.tsinghua.edu.cn/git/homebrew/homebrew-core.git/Formula/redis.rb
License: BSD-3-Clause
==> Dependencies
Required: openssl@1.1 ✔
==> Options
--HEAD
        Install HEAD version
==> Caveats
To have launchd start redis now and restart at login:
  brew services start redis
Or, if you don't want/need a background service you can just run:
# 配置文件
  redis-server /usr/local/etc/redis.conf
==> Analytics
install: 46,064 (30 days), 146,808 (90 days), 583,167 (365 days)
install-on-request: 44,935 (30 days), 141,581 (90 days), 553,766 (365 days)
build-error: 0 (30 days)
 

配置文件地址：/usr/local/etc/redis.conf;


################################## MODULES #####################################

# Load modules at startup. If the server is not able to load modules
# it will abort. It is possible to use multiple loadmodule directives.
#
# loadmodule /path/to/my_module.so
# loadmodule /path/to/other_module.so

loadmodule /usr/local/Cellar/redis/redisbloom.so # 加载module，写入对应的path

################################## NETWORK #####################################
 

重启 redis

# 重启reis
➜  Integration git:(main) brew services restart redis
Stopping `redis`... (might take a while)
==> Successfully stopped `redis` (label: homebrew.mxcl.
==> Successfully started `redis` (label: homebrew.mxcl.
# 连接服务
➜  Integration git:(main) redis-cli
# nice work
127.0.0.1:6379> BF.ADD nice work
(integer) 1
127.0.0.1:6379>
 

基本操作

     
命令 功能 参数
BF.RESERVE 创建一个大小为 capacity，错误率为 error_rate 的空的 Bloom BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion 满后默认扩容2倍] [NONSCALING 不扩容抛异常]
BF.ADD 向 key 指定的 Bloom 中添加一个元素 item BF.ADD {key} {item}
BF.MADD 向 key 指定的 Bloom 中添加多个元素 BF.MADD {key} {item} [item…]
BF.INSERT 向 key 指定的 Bloom 中添加多个元素，添加时可以指定大小和错误率，且可以控制在 Bloom 不存在的时候是否自动创建 BF.INSERT {key} [CAPACITY {cap}] [ERROR {error}] [EXPANSION expansion] [NOCREATE] [NONSCALING] ITEMS {item…}
BF.EXISTS 检查一个元素是否可能存在于 key 指定的 Bloom 中 BF.EXISTS {key} {item}
BF.MEXISTS 同时检查多个元素是否可能存在于 key 指定的 Bloom 中 BF.MEXISTS {key} {item} [item…]
BF.SCANDUMP 对 Bloom 进行增量持久化操作 BF.SCANDUMP {key} {iter}
BF.LOADCHUNK 加载 SCANDUMP 持久化的 Bloom 数据 BF.LOADCHUNK {key} {iter} {data}
BF.INFO 查询 key 指定的 Bloom 的信息 BF.INFO {key}
BF.DEBUG 查看 BloomFilter 的内部详细信息（如每层的元素个数、错误率等） BF.DEBUG {key}   
# 初始化一个 错误率为 0.1 容量为 5 不自动扩容的
127.0.0.1:6379> BF.RESERVE bf:1 0.1 5 NONSCALING
OK
# 批量添加
127.0.0.1:6379> BF.MADD bf:1 1 2 3 4 5
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
5) (integer) 1
# 溢出报错
127.0.0.1:6379> BF.MADD bf:1 6 7 
1) (error) ERR non scaling filter is full
# 打印信息
127.0.0.1:6379> BF.INFO bf:1
 1) Capacity
 2) (integer) 5
 3) Size
 4) (integer) 160
 5) Number of filters
 6) (integer) 1
 7) Number of items inserted
 8) (integer) 5
 9) Expansion rate
10) (nil)
# 是否存在某个字段
127.0.0.1:6379> BF.EXISTS bf:1 4
(integer) 1
 

原理

工作方式

布隆过滤器是由一个长度为m比特的位数组与k个哈希函数组成的数据结构。比特数组均初始化为0，所有哈希函数都可以分别把输入数据尽量均匀地散列。

  1. 当插入一个元素时，将其数据通过k个哈希函数转换成k个哈希值，这k个哈希值将作为比特数组的下标，并将数组中的对应下标的值置为1。
  2. 当查询一个元素时，同样会将其数据通过k个哈希函数转换成k个哈希值（数组下标），查询数组中对应下标的值，如果有一个下标的值为0表明该元素一定不在集合中，如果全部下标的值都为1，表明该元素有可能在集合中。至于为什么有可能在集合中？ 因为有可能某个或者多个下标的值为 1 是受到其他元素的影响，这就是所谓的假阳性，下文会详细讲述。
  3. 无法删除一个元素，为什么呢？因为你删除的元素的哈希值可能和集合中的某个元素的哈希值有相同的，一旦删除了这个元素会导致其他的元素也被删除。

下图示出一个m=18, k=3的布隆过滤器示例。集合中的 x、y、z 三个元素通过 3 个不同的哈希函数散列到位数组中。当查询元素 w 时，因为有一个比特为 0，因此 w 不在该集合中。

假阳性相关更多参考： 大白话布隆过滤器，又能和面试官扯皮了！！！

简单来说，当位数组中1的个数越多，也就是存的数据越多，最后查询的时候返回存在的概率越大。

注意⚠️：仅此标记hash过后的位置，而不是存真实的数据。所以才节省空间。

空间占用估计

布隆计算器在线版。

布隆过滤器有两个参数

  1. 预计元素的数量 n
  2. 错误率 f。

公式根据这两个输入得到两个输出，第一个输出是位数组的长度 l，也就是需要的存储空间大小 (bit)，第二个输出是 hash 函数的最佳数量 k。hash 函数的数量也会直接影响到错误率，最佳的数量会有最低的错误率。

k=0.7*(l/n)  # 约等于
f=0.6185^(l/n)  # ^ 表示次方计算，也就是 math.pow
 

从公式中可以看出

  1. 位数组相对越长 (l/n)，错误率 f 越低，这个和直观上理解是一致的
  2. 位数组相对越长 (l/n)，hash 函数需要的最佳数量也越多，影响计算效率
  3. 当一个元素平均需要 1 个字节 (8bit) 的指纹空间时 (l/n=8)，错误率大约为 2%
  4. 错误率为 10%，一个元素需要的平均指纹空间为 4.792 个 bit，大约为 5bit
  5. 错误率为 1%，一个元素需要的平均指纹空间为 9.585 个 bit，大约为 10bit
  6. 错误率为 0.1%，一个元素需要的平均指纹空间为 14.377 个 bit，大约为 15bit

|||
|–|–|–|
|错误率{error_rate}|元素数量{capacity}|占用内存（单位M）|
| 0.001| 10万 | 0.19|
|0.001| 1百万| 1.89|
|0.001| 1千万| 18.9|
|0.001| 1亿| 188.6|
|0.0001| 10万| 0.25|
|0.0001|1百万|2.5|
|0.0001|1千万|24.6|
|0.0001|1亿|245.7|
|0.00001|10万|0.3|
|0.00001|1百万|3.01|
|0.00001|1千万3|0.1|
|0.00001|1亿|302.9|

占用内存（单位M） = bytes值/1024/1024。

从上述对比分析可以看出，错误率{error_rate}越小，所需的存储空间越大； 初始化设置的元素数量{capacity}越大，所需的存储空间越大，当然如果实际远多于预设时，准确率就会降低。

在1千万数据场景下，error_rate为0.001、0.0001、0.00001实际占用内存都是30M以下，此时如果对准确性要求高，初始化时将错误率设置低一点是完全无伤大雅的。

RedisBloom官方默认的error_rate是 0.01，默认的capacity是 100

在线计算相互关系—https://hur.st/bloomfilter/?n=10000000&p=1.0E-7&m=&k=

# 一百万
n = 10000000
# 错误率
p = 0.0000001 (1 in 9994080)
# 内存大小
m = 335477044 (39.99MiB)
# hash函数个数
k = 23
 

公式

n = ceil(m / (-k / log(1 - exp(log(p) / k))))
p = pow(1 - exp(-k / (m / n)), k)
m = ceil((n * log(p)) / log(1 / pow(2, log(2))));
k = round((m / n) * log(2));
 

场景

主要特征：某元素是否在集合中。

  1. 校验用户名是否已经存在，
  2. 推荐系统，如过滤已读新闻、抖音推荐；
  3. 爬虫过滤URL是否重复
  4. 缓存穿透，请求不存在的数据，redis中没有就每次从db中取
  5. 缓存击穿：最通俗的例子：新浪微博热搜，某个热点 5 分钟后 Redis 里面数据过期，然后该新闻不属于热搜，所以缓存失效

实战

选择合适的工具🔧，才能事半功倍。

  1. 往容器插入数据；
  2. 判断是否存在

注意事项：bigkey问题，如何设计key

缓存穿透

试想一下：

  1. 某人通过抓包拿到页面详情参数，然后jmeter帮你线上测试；
  2. 某人行为不存在鱼你的某个正常的集合里，频繁的帮你线上测试。

你应该会感谢他八辈祖宗吧！

  1. 平时是否只把redis当作kv缓存，甚至都么有考虑过缓存穿透？
  2. 一图胜千言，看下图，图片来源看完这篇缓存穿透的文章，保证你能和面试官互扯！！！

个性推荐

参考记一篇REDIS布隆过滤器的使用。

原文分析

  1. 业务需求：针对新用户推广告，老用户不推。
  2. 要求: 1. QPS至少要能撑住30W。2. 接口响应不能超过60ms
  3. 现状：数量级：6亿，设备多样性【需考虑】，总数*3=18亿。注：博主以设备纬度判断；
  4. 依据确认后，技术选型—REDIS 布隆过滤器
    1. 阿里云单机redis QPS 10w, 需要选择集群版, & 将key打到不同的节点上
    2. redis key 值的选择
      1. 如何存放这么多数据
      2. 截取md5(设备ID)前4位相同的放一个key中.
例:  deviceArray = [
        "202cb962ac59075b964b07152d234b70",
        "202cb35dac59075b964b07152d234b95",
        "202cb35dac09875b964b07152d234b88",
        ....
    ]
对应的写命令:
     BF.ADD app:old_users:202c 202cb962ac59075b964b07152d234b70
     BF.ADD app:old_users:202c 202cb35dac59075b964b07152d234b95
     BF.ADD app:old_users:202c 202cb35dac09875b964b07152d234b88
     ....
 

注意&总结

  1. 业务转化为技术选型
  2. 提前调研所租服务是否支持该技术
  3. 多看别人的实战
--[[
KEYS[1]: bf.key
ARGV[1]: 模拟循环次数

生成随机32位置 十六进制字符串
1. 采用模版替换
2. 十六进制的用法
3. 三目运算
--]]
local random = math.random
local function uuid()
    local template = "xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx"
    return string.gsub(
        template,
        "[xy]",
        function(c)
            -- 三目运算: local z = a>b and x or y
            -- 0x: 十六进制
            -- 0xf: 15
            -- 0xb: 11
            local v = (c == "x") and random(0, 0xf) or random(8, 0xb)
            return string.format("%x", v)
        end
    )
end

local index = 0
local key = KEYS[1] -- bf key
local totalNum = ARGV[1] -- 循环次数
while index < totalNum do
    local value, _ = uuid()
    redis.call("BF.ADD", key, value)
    index = index + 1
end
 
--[[
!是否存在
--]]
local exists = redis.call("BF.EXISTS", key, value)
return exists
 

参考

  1. Redis 缓存穿透问题及解决方案
  2. 看完这篇缓存穿透的文章，保证你能和面试官互扯！！！
  3. seckill-practice
  4. 记一篇 REDIS 布隆过滤器的使用
  5. Mac 系统 Redis 安装布隆过滤器
  6. Guava布隆过滤器(boomfilter)使用简介
  7. Bloom Filters – Introduction and Implementation
  8. 玩转Redis-Redis中布隆过滤器的使用及原理

注意：本文归作者所有，未经作者允许，不得转载

#redis
阅读全部

全部评论: 0 条

    我有话说:

    商城系统 DBShop V3.0 Beta 发布

    全新重构，首次亮相。 系统简介 DBShop企业级商城系统，使用PHP语言基于Laminas（Zendframework 3） + Doctrine 2 组合框架开发完成。可定制、多终端、多场景、多

    Redis系列四 锁

      本文目标 1. 熟悉乐观锁ABA概念 2. 理解掌握redis事务以及watch回滚； 3. 实战redis锁 乐观锁 乐观锁是一种不会阻塞其他线程并发的机制，它不会使用数据库的

    Redis系列六 Lua

      本文目标 学习lua基本语法 能够采用redis+lua lua 基本语法 Lua 是一种轻量小巧的脚本语言，用标准C语言编写并以源代码形式开放， 其设计目的是为了嵌入应用

    Redis系列七 Debug Lua

      调试redis+lua 学了lua的基本语法，了解了redis+lua的配套用法，但是却不知道怎么断点调试。学就学全面点， 官网中有dubug相关说明。地址：Redis Lua

    Redis系列一 基本用法&应用场景

        说明 redis的最基本使用方法以及使用场景。 字符串 // stringasync function stringFun() { const [key

    Redis系列八 抢红包

      本文概述 掌握红包的两种常见生成算法 掌握lua+redis 实现原子性抢红包 项目中还有mysql相关内容 了解jmeter的基本用法 遗留问题 redis同步DB时机问题

    Redis系列二：位图实战，实现打卡签到

    前言 如果要统计一篇文章的阅读量，可以直接使用 Redis 的 incr 指令来完成。 如果要求阅读量必须按用户去重，那就可以使用 set 来记录阅读了这篇文章的所有用户 id，获取

    Redis系列四 GEO附近的人

    GEO算法 GeoHash是一种地址编码方法。将二维的空间经纬度数据编码成一个字符串； 地球上的经度范围：[-180， 180]，纬度范围：[-90，90]。如果以本初子午线、赤道为界，地球可以分成4个部分。 我们先将平面切割成四个正方形，然...

    Flink + 强化学习搭建实时推荐系统

    如今的推荐系统，对于实时性的要求越来越高，实时推荐的流程大致可以概括为：推荐系统对于用户的请求产生推荐，用户对推荐结果作出反馈 (购买/点击/离开等等)，推荐系统再根据用户反馈作出新的推荐。这个过程

    「轻阅读」推荐系统中信息增强的小技巧

    实用的推荐系统的构建经验，如何进行信息增强。

    Redisson 3.13.6 发布，官方推荐的 Redis 客户端

    Redisson 3.13.6 已发布，这是一个 Java 编写的 Redis 客户端，具备驻内存数据网格（In-Memory Data Grid）功能，并获得了 Redis 的官方推荐

    「开源推荐」MeEdu v2.6 发布，基于 Laravel 的在线点播收费系统

    附源码

    为什么单线程的Redis能够达到百万级的QPS？

    作者：在江湖中coding链接：https://juejin.im/post/5e6097846fb9a07c9f3fe744 性能测试报告 查看了下阿里云 Redis 的性能测试报告如下，能够

    Redis 5.0.11、6.0.11、6.2 发布，修复 32 位系统上的整数溢出

    Redis 同时发布了 5.0.11、6.0.11 和 6.2 版本。对于使用 32 位 Redis 的用户来说，此次更新解决了一个重要的安全问题，即 32 位系统上的整数溢出（(CVE-2021

    BAT大牛Redis客户端与服务端交互原理

    Redis实例运行在单独的进程中，应用系统（Redis客户端）通过Redis协议和Redis Server

    精品推荐：Redis主从复制

    持久化保证了即使 redis 服务重启也会丢失数据，因为 redis 服务重启后会将硬盘上持久化的数据恢复到内存中，但是当 redis 服务器的硬盘损坏了可能会导致数据丢失，如果通过 redis 的

    Redisson 3.13.5 发布，官方推荐的 Redis 客户端

    Redisson 3.13.5 已发布，这是一个 Java 编写的 Redis 客户端，具备驻内存数据网格（In-Memory Data Grid）功能，并获得了 Redis 的官方推荐。 主要更新

    Redisson 3.15.0 发布，官方推荐的 Redis 客户端

    Redisson 3.15.0 已发布，这是一个 Java 编写的 Redis 客户端，具备驻内存数据网格（In-Memory Data Grid）功能，并获得了 Redis 的官方推荐

    Redisson 3.14.1 发布，官方推荐的 Redis 客户端

    Redisson 3.14.1 已发布，这是一个 Java 编写的 Redis 客户端，具备驻内存数据网格（In-Memory Data Grid）功能，并获得了 Redis 的官方推荐。 本次更新