从原理到实战：如何通过布隆过滤器防止缓存击穿

2024-06-03 09:08
文章标签 实战 原理 过滤器 缓存 布隆 击穿 防止

本文主要是介绍从原理到实战：如何通过布隆过滤器防止缓存击穿，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

java互联网架构 2020-03-07 15:18:48

为什么引入

我们的业务中经常会遇到穿库的问题，通常可以通过缓存解决。如果数据维度比较多，结果数据集合比较大时，缓存的效果就不明显了。

因此为了解决穿库的问题，我们引入Bloom Filter。

适合的场景

  • 数据库防止穿库 Google Bigtable，Apache HBase和Apache Cassandra以及Postgresql 使用BloomFilter来减少不存在的行或列的磁盘查找。避免代价高昂的磁盘查找会大大提高数据库查询操作的性能。如同一开始的业务场景。如果数据量较大，不方便放在缓存中。需要对请求做拦截防止穿库。
  • 缓存宕机 缓存宕机的场景，使用布隆过滤器会造成一定程度的误判。原因是除了Bloom Filter 本身有误判率，宕机之前的缓存不一定能覆盖到所有DB中的数据，当宕机后用户请求了一个以前从未请求的数据，这个时候就会产生误判。当然，缓存宕机时使用布隆过滤器作为应急的方式，这种情况应该也是可以忍受的。
  • WEB拦截器 相同请求拦截防止被攻击。用户第一次请求，将请求参数放入BloomFilter中，当第二次请求时，先判断请求参数是否被BloomFilter命中。可以提高缓存命中率
  • 恶意地址检测 chrome 浏览器检查是否是恶意地址。首先针对本地BloomFilter检查任何URL，并且仅当BloomFilter返回肯定结果时才对所执行的URL进行全面检查（并且用户警告，如果它也返回肯定结果）。
  • 比特币加速 bitcoin 使用BloomFilter来加速钱包同步。

开源项目地址：https://github.com/luw2007/bloomfilter

我们先看看一般业务缓存流程：

从原理到实战：如何通过布隆过滤器防止缓存击穿

 

先查询缓存，缓存不命中再查询数据库。然后将查询结果放在缓存中即使数据不存在，也需要创建一个缓存，用来防止穿库。

这里需要区分一下数据是否存在。如果数据不存在，缓存时间可以设置相对较短，防止因为主从同步等问题，导致问题被放大。

这个流程中存在薄弱的问题是，当用户量太大时，我们会缓存大量数据空数据，并且一旦来一波冷用户，会造成雪崩效应。

对于这种情况，我们产生第二个版本流程:redis过滤冷用户缓存流程

从原理到实战：如何通过布隆过滤器防止缓存击穿

 

我们将数据库里面中命中的用户放在redis的set类型中，设置不过期。这样相当把redis当作数据库的索引，只要查询redis，就可以知道是否数据存在。

redis中不存在就可以直接返回结果。如果存在就按照上面提到一般业务缓存流程处理。

聪明的你肯定会想到更多的问题：

  1. redis本身可以做缓存，为什么不直接返回数据呢？
  2. 如果数据量比较大，单个set，会有性能问题？
  3. 业务不重要，将全量数据放在redis中，占用服务器大量内存。投入产出不成比例？

问题1需要区分业务场景，结果数据少，我们是可以直接使用redis作为缓存，直接返回数据。结果比较大就不太适合用redis存放了。比如ugc内容，一个评论里面可能存在上万字，业务字段多。

redis使用有很多技巧。bigkey 危害比较大，无论是扩容或缩容带来的内存申请释放， 还是查询命令使用不当导致大量数据返回，都会影响redis的稳定。这里就不细谈原因及危害了。

解决bigkey 方法很简单。我们可以使用hash函数来分桶，将数据分散到多个key中。减少单个key的大小，同时不影响查询效率。

问题3是redis存储占用内存太大。因此我们需要减少内存使用。重新思考一下引入redis的目的。redis像一个集合，整个业务就是验证请求的参数是否在集合中。

从原理到实战：如何通过布隆过滤器防止缓存击穿

 

这个结构就像洗澡的时候用的双向阀门：左边热水，右边冷水。

大部分的编程语言都内置了filter。拿python举例，filter函数用于过滤序列， 过滤掉不符合条件的元素，返回由符合条件元素组成的列表。

我们看个例子：

$ python2
Python 2.7.10 (default, Oct  6 2017, 22:29:07)
[GCC 4.2.1 Compatible Apple LLVM 9.0.0 (clang-900.0.31)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> s = {2, 4}
>>> filter(lambda x:x in s, [0, 1, 2])
[2]

集合s中存在 2，4两个数字，我们需要查询 0，1，2 那些在集合s中。 lambda x:x in s构造一个匿名函数，判断入参x是否在集合s中。过滤器filter依次对列表中的数字执行匿名函数。最终返回列表[2]。

redis中实现set用了两种结构：intset和hash table。非数字或者大量数字时都会退化成hash table。那么是否好的算法可以节省hash table的大小呢？

其实早在1970年由Burton Howard Bloom提出的布隆过滤器（英语：Bloom Filter）。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。

它的优点是空间效率和查询时间都远远超过一般的算法， 缺点是有一定的误识别率和删除困难。

BloomFilter原理

我们常见的将业务字段拼接之后md5，放在一个集合中。md5生成一个固定长度的128bit的串。如果我们用bitmap来表示，则需要

2**128 = 340282366920938463463374607431768211456 bit

判断一个值在不在，就变成在这个bitmap中判断所在位是否为1。但是我们全世界的机器存储空间也无法存储下载。因此我们只能分配有限的空间来存储。比如:

从原理到实战：如何通过布隆过滤器防止缓存击穿

 

当只有一个hash函数时：很容易发生冲突。

从原理到实战：如何通过布隆过滤器防止缓存击穿

 

可以看到上面1和2的hash结果都是7，发生冲突。如果增加hash函数，会发生什么情况？

从原理到实战：如何通过布隆过滤器防止缓存击穿

 

我们使用更多的hash函数和更大的数据集合来测试。得到下面这张表

从原理到实战：如何通过布隆过滤器防止缓存击穿

 

由此可以看到当增加hash方法能够有效的降低碰撞机率。比较好的数据如下：

从原理到实战：如何通过布隆过滤器防止缓存击穿

 

但是增加了hash方法之后，会降低空间的使用效率。当集合占用总体空间达到25%的时候， 增加hash 的效果已经不明显

从原理到实战：如何通过布隆过滤器防止缓存击穿

 

上面的使用多个hash方法来降低碰撞就是BloomFilter的核心思想。

算法优点：

  • 数据空间小，不用存储数据本身。

算法本身缺点：

  • 元素可以添加到集合中，但不能被删除。
  • 匹配结果只能是“绝对不在集合中”，并不能保证匹配成功的值已经在集合中。
  • 当集合快满时，即接近预估最大容量时，误报的概率会变大。
  • 数据占用空间放大。一般来说，对于1％的误报概率，每个元素少于10比特，与集合中的元素的大小或数量无关。查询过程变慢，hash函数增多，导致每次匹配过程，需要查找多个位（hash个数）来确认是否存在。

对于BloomFilter的优点来说，缺点都可以忽略。毕竟只需要kN的存储空间就能存储N个元素。空间效率十分优秀。

如何使用BloomFilter

BloomFilter 需要一个大的bitmap来存储。鉴于目前公司现状，最好的存储容器是redis。从github topics: bloom-filter中经过简单的调研。

redis集成BloomFilter方案：

  • 原生python 调用setbit 构造 BloomFilter
  • lua脚本
  • Rebloom - Bloom Filter Module for Redis (注：redis Module在redis4.0引入)
  • 使用hiredis 调用redis pyreBloom

原生python 方法太慢，lua脚本和module 部署比较麻烦。于是我们推荐使用pyreBloom，底层使用。

pyreBloom:master λ ls
Makefile      bloom.h       bloom.pxd     murmur.c      pyreBloom.pyx
bloom.c       bloom.o       main.c        pyreBloom.c

从文件命名上可以看到bloom 使用c编写。pyreBloom 使用cython编写。

bloom.h 里面实现BloomFilter的核心逻辑，完成与redis server的交互；hash函数；添加，检查和删除方法的实现。

从原理到实战：如何通过布隆过滤器防止缓存击穿

 

pyreBloom.pyx

import math

import random

cimport bloom

class pyreBloomException(Exception):

'''Some sort of exception has happened internally'''

pass

cdef class pyreBloom(object):

cdef bloom.pyrebloomctxt context

cdef bytes key

property bits:

def __get__(self):

return self.context.bits

property hashes:

def __get__(self):

return self.context.hashes

def __cinit__(self, key, capacity, error, host='127.0.0.1', port=6379,

password='', db=0):

self.key = key

if bloom.init_pyrebloom(&self.context, self.key, capacity,

error, host, port, password, db):

raise pyreBloomException(self.context.ctxt.errstr)

def __dealloc__(self):

bloom.free_pyrebloom(&self.context)

def delete(self):

bloom.delete(&self.context)

def put(self, value):

if getattr(value, '__iter__', False):

r = [bloom.add(&self.context, v, len(v)) for v in value]

r = bloom.add_complete(&self.context, len(value))

else:

bloom.add(&self.context, value, len(value))

r = bloom.add_complete(&self.context, 1)

if r < 0:

raise pyreBloomException(self.context.ctxt.errstr)

return r

def add(self, value):

return self.put(value)

def extend(self, values):

return self.put(values)

def contains(self, value):

#If the object is 'iterable'...

if getattr(value, '__iter__', False):

r = [bloom.check(&self.context, v, len(v)) for v in value]

r = [bloom.check_next(&self.context) for i in range(len(value))]

if (min(r) < 0):

raise pyreBloomException(self.context.ctxt.errstr)

return [v for v, included in zip(value, r) if included]

else:

bloom.check(&self.context, value, len(value))

r = bloom.check_next(&self.context)

if (r < 0):

raise pyreBloomException(self.context.ctxt.errstr)

return bool(r)

def __contains__(self, value):

return self.contains(value)

def keys(self):

'''Return a list of the keys used in this bloom filter'''

return [self.context.keys[i] for i in range(self.context.num_keys)]

原生pyreBloom方法:

cdef class pyreBloom(object):
cdef bloom.pyrebloomctxt context
cdef bytes
property bits:
property hashes:
// 使用的hash方法数
def delete(self):
// 删除，会在redis中删除
def put(self, value):
// 添加 底层方法, 不建议直接调用
def add(self, value):
// 添加单个元素，调用put方法
def extend(self, values):
// 添加一组元素，调用put方法
def contains(self, value):
// 检查是否存在，当`value`可以迭代时，返回`[value]`, 否则返回`bool`
def keys(self):
// 在redis中存储的key列表

由于pyreBloom使用hiredis库，本身没有重连等逻辑，于是做了简单的封装。

#coding=utf-8

'''

bloom filter 基础模块

可用方法:

extend, keys, contains, add, put, hashes, bits, delete

使用方法:

>>> class TestModel(BaseModel):

... PREFIX = "bf:test"

>>> t = TestModel()

>>> t.add('hello')

1

>>> t.extend(['hi', 'world'])

2

>>> t.contains('hi')

True

>>> t.delete()

'''

import logging

from six import PY3 as IS_PY3

from pyreBloom import pyreBloom, pyreBloomException

from BloomFilter.utils import force_utf8

class BaseModel(object):

'''

bloom filter 基础模块

参数：

SLOT: 可用方法类型

PREFIX: redis前缀

BF_SIZE: 存储最大值

BF_ERROR: 允许的出错率

RETRIES: 连接重试次数

host: redis 服务器IP

port: redis 服务器端口

db: redis 服务器DB

_bf_conn: 内部保存`pyreBloom`实例

'''

SLOT = {'add', 'contains', 'extend', 'keys', 'put', 'delete',

'bits', 'hashes'}

PREFIX = ""

BF_SIZE = 100000

BF_ERROR = 0.01

RETRIES = 2

def __init__(self, redis=None):

'''

初始化redis配置

:param redis: redis 配置

'''

#这里初始化防止类静态变量多个继承类复用，导致数据被污染

self._bf_conn = None

self._conf = {

'host': '127.0.0.1', 'password': '',

'port': 6379, 'db': 0

}

if redis:

for k, v in redis.items():

if k in self._conf:

self._conf[k] = redis[k]

self._conf = force_utf8(self._conf)

@property

def bf_conn(self):

'''

初始化pyreBloom

'''

if not self._bf_conn:

prefix = force_utf8(self.PREFIX)

logging.debug(

'pyreBloom connect: redis://%s:%s/%s, (%s%s%s)',

self._conf['host'], self._conf['port'], self._conf['db'],

prefix, self.BF_SIZE, self.BF_ERROR,

)

self._bf_conn = pyreBloom(

prefix, self.BF_SIZE, self.BF_ERROR, **self._conf)

return self._bf_conn

def __getattr__(self, method):

'''调用pyrebloom方法

没有枚举的方法将从`pyreBloom`中获取

:param method:

:return: pyreBloom.{method}

'''

#只提供内部方法

if method not in self.SLOT:

raise NotImplementedError()

#捕获`pyreBloom`的异常, 打印必要的日志

def catch_error(*a, **kwargs):

'''多次重试服务'''

args = force_utf8(a)

kwargs = force_utf8(kwargs)

for _ in range(self.RETRIES):

try:

func = getattr(self.bf_conn, method)

res = func(*args, **kwargs)

#python3 返回值和python2返回值不相同，

#手工处理返回类型

if method == 'contains' and IS_PY3:

if isinstance(res, list):

return [i.decode('utf8') for i in res]

return res

except pyreBloomException as error:

logging.warn(

'pyreBloom Error:%s%s', method, str(error))

self.reconnect()

if _ == self.RETRIES:

logging.error('pyreBloom Error')

raise error

return catch_error

def __contains__(self, item):

'''跳转__contains__方法

:param item: 查询元素列表/单个元素

:type item: list/basestring

:return: [bool...]/bool

'''

return self.contains(item)

def reconnect(self):

'''

重新连接bloom

`pyreBloom` 连接使用c driver，没有提供timeout参数，使用了内置的timeout

同时为了保证服务的可靠性，增加了多次重试机制。

struct timeval timeout = { 1, 5000 };

ctxt->ctxt = redisConnectWithTimeout(host, port, timeout);

del self._bf_conn 会调用`pyreBloom`内置的C的del方法，会关闭redis连接

'''

if self._bf_conn:

logging.debug('pyreBloom reconnect')

del self._bf_conn

self._bf_conn = None

_ = self.bf_conn

进阶：计数过滤器(Counting Filter)

提供了一种在BloomFilter上实现删除操作的方法，而无需重新重新创建过滤器。在计数滤波器中，阵列位置（桶）从单个位扩展为n位计数器。实际上，常规布隆过滤器可以被视为计数过滤器，其桶大小为一位。

插入操作被扩展为递增桶的值，并且查找操作检查每个所需的桶是否为非零。然后，删除操作包括递减每个桶的值。

存储桶的算术溢出是一个问题，并且存储桶应该足够大以使这种情况很少见。如果确实发生，则增量和减量操作必须将存储区设置为最大可能值，以便保留BloomFilter的属性。

计数器的大小通常为3或4位。因此，计算布隆过滤器的空间比静态布隆过滤器多3到4倍。相比之下， Pagh，Pagh和Rao（2005）以及Fan等人的数据结构。（2014）也允许删除但使用比静态BloomFilter更少的空间。

计数过滤器的另一个问题是可扩展性有限。由于无法扩展计数布隆过滤器表，因此必须事先知道要同时存储在过滤器中的最大键数。一旦超过表的设计容量，随着插入更多密钥，误报率将迅速增长。

Bonomi等人。（2006）引入了一种基于d-left散列的数据结构，它在功能上是等效的，但使用的空间大约是计算BloomFilter的一半。此数据结构中不会出现可伸缩性问题。一旦超出设计容量，就可以将密钥重新插入到双倍大小的新哈希表中。

Putze，Sanders和Singler（2007）的节省空间的变体也可用于通过支持插入和删除来实现计数过滤器。

Rottenstreich，Kanizo和Keslassy（2012）引入了一种基于变量增量的新通用方法，该方法显着提高了计算布隆过滤器及其变体的误报概率，同时仍支持删除。

与计数布隆过滤器不同，在每个元素插入时，散列计数器以散列变量增量而不是单位增量递增。要查询元素，需要考虑计数器的确切值，而不仅仅是它们的正面性。如果由计数器值表示的总和不能由查询元素的相应变量增量组成，则可以将否定答案返回给查询。

这篇关于从原理到实战：如何通过布隆过滤器防止缓存击穿的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1026554。

相关文章

网页解析 lxml 库--实战

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库，完全使用 Python 语言编写，它对 XPath表达式提供了良好的支 持，因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块，该模块专门用来解析 HTML/XML 文档，下面来介绍一下 lxml 库
阅读更多...
性能分析之MySQL索引实战案例

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
深入探索协同过滤：从原理到推荐模块案例

深入探索协同过滤：从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤（UserCF）2. 基于物品的协同过滤（ItemCF）3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代，推荐系统成为连接用户与内容的桥梁。本文聚焦于
阅读更多...
hdu4407(容斥原理)

hdu4407(容斥原理)

题意：给一串数字1,2，......n，两个操作:1、修改第k个数字，2、查询区间[l,r]中与n互质的数之和。 解题思路：咱一看，像线段树，但是如果用线段树做，那么每个区间一定要记录所有的素因子，这样会超内存。然后我就做不来了。后来看了题解，原来是用容斥原理来做的。还记得这道题目吗？求区间[1,r]中与p互质的数的个数，如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和
阅读更多...
C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

哈喽，你好啊，我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记，这是第6篇； 接下来实现实时显示当前选中红球数量，蓝球数量； 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时，在对应的位置显示实时已选择的红球、蓝球的数量； 02 标签名称 分别设置Label标签名称为：lblRedCount、lblBlueCount
阅读更多...
缓存雪崩问题

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库，瞬间耗尽数据库资源，导致数据库无法使用。 解决方案： 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内，大量缓存数据同时失效，导致所有请求直接涌向数据库，瞬间增加数据库的负载压力，可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k
阅读更多...
滚雪球学Java(87)：Java事务处理：JDBC的ACID属性与实战技巧！真有两下子！

滚雪球学Java(87)：Java事务处理：JDBC的ACID属性与实战技巧！真有两下子！

咦咦咦，各位小可爱，我是你们的好伙伴——bug菌，今天又来给大家普及Java SE啦，别躲起来啊，听我讲干货还不快点赞，赞多了我就有动力讲得更嗨啦！所以呀，养成先点赞后阅读的好习惯，别被干货淹没了哦~ 🏆本文收录于「滚雪球学Java」专栏，专业攻坚指数级提升，助你一臂之力，带你早日登顶🚀，欢迎大家关注&&收藏！持续更新中，up！up！up！！ 环境说明：Windows 10
阅读更多...
hdu4407容斥原理

hdu4407容斥原理

题意： 有一个元素为 1~n 的数列{An}，有2种操作（1000次）： 1、求某段区间 [a,b] 中与 p 互质的数的和。 2、将数列中某个位置元素的值改变。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.Inpu
阅读更多...
hdu4059容斥原理

hdu4059容斥原理

求1-n中与n互质的数的4次方之和 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWrit
阅读更多...
寻迹模块TCRT5000的应用原理和功能实现（基于STM32）

寻迹模块TCRT5000的应用原理和功能实现（基于STM32）

目录 概述 1 认识TCRT5000 1.1 模块介绍 1.2 电气特性 2 系统应用 2.1 系统架构 2.2 STM32Cube创建工程 3 功能实现 3.1 代码实现 3.2 源代码文件 4 功能测试 4.1 检测黑线状态 4.2 未检测黑线状态 概述 本文主要介绍TCRT5000模块的使用原理，包括该模块的硬件实现方式，电路实现原理，还使用STM32类
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2